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 ...

Start Free Trial

No credit card required