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

7.9 BICONNECTIVITY FROM CONNECTIVITY WITHOUT ADDITIONAL CONSTRAINTS

We now discuss some scenarios where mobile robots were already randomly deployed but still assumed one-connected. From this initial connected network, the objective is to turn the network biconnected using only localized movement decisions and minimizing the total movements of robots. The solution presented in this section comes from Das et al. (2009).

From a global point of view, a biconnected network is a network that does not contain any critical nodes nor critical links, that is, that remains connected if any node or link is individually removed. Since a link is critical only if at least one of its end point nodes is critical, making the network biconnected comes to turn every critical node into noncritical. By looking at the Figure 7.11, it appears intuitively clear that the global criticality of a node (e.g., N) cannot be locally decided, since it depends on some remote edges (e.g., AB), whose existence is locally unknown.

The algorithm is based on the concept of p-hop criticality, already discussed in 7.6. More practically, each node is assumed to collect information about its p-hop neighbors through exchanging and relaying hello messages over multiple hops. If the p-hop neighborhood of a node n appears to n as disconnected without itself, then n locally decides that it is p-hop critical (we will simply say critical in the following text). In the example depicted in Figure 7.11, N will decide that it is ...