## 3 Cluster Formation
### Failure Management
#### 3.3.1 Permanent-Fault Management
Therefore, the failure of boundary nodes is simply ignored. 2. _Pre-Boundary Node Failure Recovery Algorithm_: failure of pre-boundary nodes affects the connectivity of its healthy children nodes. Therefore, a healthy child of a failing pre-boundary node follows a procedure for finding a suitable healthy parent by sending a joint message to its neighbors. A healthy boundary child searches for a suitable neighbouring parent having two conditions: neighbor is not among the children of the failing pre-boundary node and the neighbor itself is not a failing node. The healthy child first searches within the cluster and checks whether the supportable degree of the neighbor is within the limit \(D\). If no suitable parent found within the cluster, the node searches outside of the cluster considering two limitations numbers \(D\) and \(S\) of the new parent and cluster, respectively. 3. _Internal Node Failure Recovery Algorithm_: the healthy child of a failed internal node may be a pre-boundary or another internal node. Both types of healthy children search for suitable parents according to the same procedure in section (2) and if a suitable parent is not found, the child establishes a cluster of its own including all its children. The only difference between parent selection of pre-boundary and internal nodes is in the scope of the search. While the pre-boundary node searches for a new parent either within the cluster or inside the neighbouring clusters, the internal healthy child only searches inside the cluster. 4. _CH Node Failure Recovery Algorithm_: CH failure triggers a new CH selection phase among children of the failing CH based on the merit of energy status. Then, the cluster formation phase is performed within the cluster considering cluster size limits and supportable degree limits. The analysis presented by the paper shows acceptable level of overhead for the failure detection and recovery mechanism, and the algorithm provides fast failure recovery strategy. However, dependency of the fault-management technique on a specific clustering approach and its single support of permanent faults due to energy depletion limit the applicability of the approach. [PERSON] _et al._[93] proposed a fault-tolerant clustering approach based on an inter-cluster monitoring mechanism. The algorithm addresses the permanent failure of CHs as the bottleneck of cluster-based protocols and provides a fault detection and run-time recovery mechanism using consensus model of the neighbouring CHs to agree on a faulty CH. The fault detection and recovery mechanisms of the approach exploit the time slot feature of the Time Division Multiple-Access (TDMA) MAC protocol by adding two new time slots named \"Route Update\" and \"Status Update\". During _Route Update_ slots, cluster members turn on their receivers to receive the new association in the time slot and CH updates; and _Status Update_ slot is used by the CH to exchange the latest information about its cluster members and the status of the CH itself with other CHs. The fault detection is done by periodic exchange of _status updates_ through inter-CH communication. A CH is considered completely failed only when its _status update_ is not received by all other CHs. To answer the CHs' link-failure situation, the algorithm uses the broadcast forwarding of _status updates_ by other CHs. However, the forwarding algorithm entails a large amount of redundant message transmission, especially in fault-free fully connected scenarios. The paper addressesthis redundancy in two ways. First, a Multiplicative Increase Linear Decrease (MILD) [97] mechanism is applied to the period of the exchange of status updates. The mechanism increases the intervals of _status updates_ when there is no fault detected in the network, while it linearly decreases the intervals for faulty networks. Another solution given by the paper to avoid message redundancy in healthy systems is the use of an \"_experience_\" based model.