Scalable Computing and Communications: Theory and Practice

2

–––––––––––––––––––––––

Reliable Minimum Connected Dominating Sets for Topology Control in Probabilistic Wireless Sensor Networks

Jing (Selena) He, Shouling Ji, Yi Pan, and Yingshu Li

2.1   TOPOLOGY CONTROL IN WIRELESS SENSOR NETWORKS (WSNs)

To ensure sufficient coverage of an area or to protect against node failures, one major characteristic of WSNs is the possibility of deploying many redundant nodes in a small area. These are clear advantages of a dense network deployment; however, there are also disadvantages. To be specific, in a relatively crowded network, many typical wireless networking problems are aggravated by the large number of neighbors, such as many nodes interfering with each other. In order to avoid too many interferences, nodes might use short transmission power to talk to nearby nodes directly; thus, routing protocols might have to recompute routes even if only small node movements have happened [1].

Some of these problems can be overcome by topology-control techniques. Instead of using the possible connectivity of a network to its maximum possible extent, a deliberate choice is made to restrict the topology of the network. The topology of a network is determined by the subset of active nodes and the set of active links along which direct communication can occur. Formally speaking, a topology-control algorithm takes a graph G = (V, E) representing the network, where V is the set of all nodes in the network and there is an edge (v₁, v₂) ∈ E ⊆ V² if and only ...