Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

7.10 BICONNECTIVITY FROM CONNECTIVITY WITH ADDITIONAL CONSTRAINTS

We are interested here, in the same problem as in the previous section, that is, to achieve biconnectivity of mobile robots starting from a random (but connected) topology. Here however, the objective is also to maximize the overall coverage and minimize the network diameter at the same time. Every robot n is assumed to have a communication range, and a coverage range. The first, denoted c(n), indicates up to which distance other nodes can receive messages from c(n). The second, denoted s(n), is the radius defining the area where the robot is to serve. For example, if n is a sensor, then s(n) corresponds to its sensing range. If n is an actuator, then s(n) may correspond to the area in which sensors are monitored by n. The ratio between these ranges is usually considered to satisfy cr(n) > 2 × sr(n). The overall coverage of the network is defined as the union of the coverage areas of all the robots. One can intuitively see that the closer the robots, the smaller the overall coverage due to potential overlappings.

The diameter of a network is defined as the “largest” shortest path between any two nodes. More formally, if d(u, υ) is the length of the shortest path between two vertices u and υ, then the diameter of a graph G = (V, E) is defined as max(d(u, υ) : u, υ ∈ V). Because the diameter bounds the number of hops of transmissions, making it small is crucial for most real-time applications. It can be intuitively ...