# An Energy-Efficient Fail Recovery Routing in TDMA MAC Protocol-Based Wireless Sensor Network
## 3 Proposed Route-Recovery Algorithms  
### Energy Model of Convergent Network  
A single sensor node failure can cause branch isolation and thus leave many nodes with broken routes to the sink node. To recover the connectivity, we propose a route-recovery method called maximum connectivity local rerouting (MCR). It quickly replaces the faulty parent node with a backup parent among the child nodes, and thus restricts the rerouting process to only the local nodes within one hop subtree of the faulty node. For example, consider an example network in Figure 4a, where a parent node p is faulty. Here, MCR selects \(c_{k}\) among p's child nodes as a backup parent \(MCR\_BP(p)\). For fast recovery in the event of a fault, MCR operates in two stages. The first stage is a processing step for backup parent selection, which is conducted as a part of the proactive routing algorithm. The second stage is a recovery step during which a real-time rerouting operation is conducted only when a fault occurs. The recovery step instantly replaces the faulty node by the pre-selected backup parent node. Hence it does not interrupt the forwarding operations of all other nodes. The first stage of MCR, the preprocessing algorithm, is executed during the network initialization period. It examines every child node \(c_{i}\) of each parent node p for two connectivity conditions: (1) How many sibling nodes of \(c_{i}\) are covered by \(c_{i}\)'s wireless range; and (2) whether \(c_{i}\) can reach its grandparent \(g\) (the parent of \(p\)). This method selects one of the child nodes who best satisfies the above two conditions as a backup parent for its primary parent. If \(p\) fails in the future, \(c_{i}\) instantly replaces \(p\)'s role. In other words, \(c_{i}\) receives the data from \(p\)'s child nodes and forwards the aggregated data to the grandparent \(g\). The key advantage of this recovery process is that the selected \(MCR\_BP\)\(c_{i}\) inherits the time slot of \(p\), which eliminates the need for time slot rescheduling of many nodes around \(p\). For example, consider the example subtree of Figure 3. Suppose that the MCR algorithm's preprocessing step selected node 3 as the backup \(MCR\_BP\); If the parent node 6 fails, node 3 takes over the parent's role of node 6 and the time slot Slot6. Once node 3 receives and aggregates other sibling's data, it then transmits the aggregate data to the grandparent node using Slot6. The proposed algorithm, therefore, recovers the communication failures without disturbing the surrounding nodes except the siblings of \(c_{i}\). In contrast, most of the previous fail recovery algorithms either re-allocate the parent or reroute the orphan child (the node who lost a primary parent) nodes to another parents in the neighborhood, thus disrupting many neighbor nodes. The MCR algorithm's preprocessing procedure for the backup parent selection is illustrated in Figure 4b. It searches for the best candidate of a backup parent for every parent node \(p_{j}\) amongst \(p_{j}\)'s child nodes to prepare for the event when \(p_{j}\) ever fails. Procedure Select-MCR_BP  
Let's assume \(G(V,\ E)\) represents our network [36], where \(V\) is a set of vertices (nodes) and \(E\) is the number of edges (lines). For each parent node, \(p_{j}\ \in\ V\) of \(G(V,\ E)\) repeats the following steps:  
* For each child node \(c_{i}\) of a parent node \(p_{j}\): (1) Measure \(Connectivity(c_{i})\) = number of other child nodes \(c_{k}\) of \(p_{j}\) such that all \(c_{k}\) are in the wireless range \(W_{i}\) of \(c_{i}\). (2) Measure \(Distance(c_{i},g)\) = the distance from \(c_{i}\) to grandparent \(g\) of \(c_{i}\) (parent of \(p\)). * Select \(c_{m}\) as a MCR backup parent \(MCR_{BP}\) of \(p_{j}\) such that \(Connectivity(c_{m})\) is maximum and \(Distance(c_{m})<W_{m}\), where \(W_{m}\) is the wireless range of \(c_{m}\).