## 4 Partitioning Detection and Connectivity Restoration
### Pre-Failure Planning  
Failure of a critical actor disconnects the neighbors and they are unable to coordinate because they have limited network information. Therefore, PCR pursues pre-failure planning to identify critical actors and designate them an appropriate backup. **Distinguishing critical/non-critical actors:** As stated above, the failure of critical actor partitions the inter-actor network into disjoint segments. The absence of a non-critical node does not affect the connectivity. PCR opts to distinguish between critical/non-critical nodes and designate a backup for each of these critical actors. The existing algorithms to determine cut-vertices in a graph can be categorized into centralized and distributed. Centralized algorithms [24, 25] may not be suitable for large scale dynamic networks due to the fact they involve huge communication overhead in maintaining network state information. Frequent changes in the WSAN topology favors distributed and highly localized algorithms. Some localized algorithms such as [26] require only 1-hop neighbors' positional information at the expense of lower accuracy of cut-vertices identification. Basically, some nodes are marked as critical while they are not cut-vertices globally. However, no critical node will be missed and the accuracy of determining non-critical ones is 100%. The fact that PCR prefers to designate a non-critical backup, such a category of approaches fits well and the reduced accuracy is not a major concern. Therefore, PCR employs a simple localized cut-vertex detection procedure that only requires 1-hop positional information to detect critical/non-critical nodes. The procedure is based on [26] and runs on each node in a distributed manner. An actor is critical if its immediate neighbors become disconnected without it, non-critical otherwise. Leaf nodes are also determined as non-critical. For instance, Figure 4(a) shows the 1-hop critical/non-critical nodes. The details of the procedure are provided in [27]. **Figure 4.** Determine critical nodes and assign backup: (**a**) 1-hop critical/non-critical and (**b**) designate backup using PCR. **Backup selection:** The critical actors choose and designate an appropriate backup among neighbors once the critical/non-critical nodes are differentiated. Several criteria can be defined when choosing a backup, depending on the application-level interests. The selection of a backup among 1-hop neighbors is based on the following ordered criteria:  
1. _Neighbor Actor Status_ (_NAS_): Each critical actor prefer to designate a non-critical node as backup since moving such a node will not affect inter-actor connectivity. Moreover, this will restrict the scope of recovery and reduce movement overhead. 2. _Actor Degree_ (_AD_): The number of neighbors reflects the actor degree. In case a non-critical node in the neighborhood is not available, PCR prefers to designate a least degree critical node as backup since few nodes will lose direct communication links to that backup when it moves. However, moving a critical node may trigger a series of cascaded relocations that we will discuss later in this section. 3. _Inter-actor Distance_ (_ID_): A nearby neighbor is preferred in case multiple neighbors have the same AD. This will help to shorten the recovery time and reduce the movement overhead that is crucial for resource-constrained mission-critical applications. An actor may be selected as backup for more than one node. A primary node selects another backup using the same procedure specified above in case a backup fails or moves outside the range of its primary. Since the backup selection criterion is based on 1-hop information, therefore, it may not always lead to an optimal solution. However, being highly localized helps PCR scale for large networks. Figure 4(b) shows the setup where each critical actor designates another as backup where the arrowhead points towards the primary. Note that PCR provides redundancy without requiring extra resources in terms of actors.