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

Start Free Trial

No credit card required