# An Energy-Efficient Fail Recovery Routing in TDMA MAC Protocol-Based Wireless Sensor Network
## 3 Proposed Route-Recovery Algorithms
### Neighbor-Extended Maximal Connectivity Routing  
To address the out-of-reach problem described above, we propose an enhanced recovery algorithm called Neighbor Extended MCR (NE-MCR), which is conducted after MCR. In addition to solving the out-of-reach problem of MCR, NE-MCR further reduces the energy consumption. It conducts an extended recovery process only for the nodes that failed to find their backup parent (BP) during their MCP process due to the out-of-reach problem. NE-MCR searches for a neighbor backup parent (NBP) in the neighborhood of the sibling nodes. Suppose that an \(MCR\_BP\) has been chosen by MCR but has an out-of-reach problem. Then this \(MCR\_BP\) broadcasts a special out-of-reach message to all its sibling nodes to trigger the NE-MCR algorithm. Then NE-MCR algorithm executes an individual search for the local optimum NBP in each sibling node of the \(MCR\_BP\). Hence, \(MCR\_BP\) node is an initiator of NE-MCR's procedure of selecting an NBP. In the end, \(MCR\_BP\) receives the results of searches from the sibling nodes, compares them, and determines which NBP to choose as the optimum NBP. The detailed procedure of NE-MCR algorithm is presented below. Figure 5: Comparison of the number of isolated nodes for the WSN of 1000 nodes when the number of faults is increased. Procedure Select-NE-MCR_BP  
For each parent node \(p_{j}\in V\) of \(G(V,\ E)\), if \(MCR\_BP\) fails to reach grandparent \(g\), repeat the following steps:  
* For each child node \(c_{i}\) of a parent node \(p_{j}\): 1. Select \(c_{k}\) as a \(MCR\_BP(p_{j})\) if it has a maximal \(Connectivity(c_{k})\) with other siblings; 2. \(c_{k}\) informs its child nodes \(c_{j}\) about the out-of-reach problem; 3. Every \(c_{j}\) examines each parent's neighbor \(p_{ji}\) (\(Distance(c_{j},p_{ji})<W_{j}\)) for the following conditions: 1. Verify if the \(Distance(c_{j},p_{ji})\) is minimal; 2. Verify if the aggregated packet length \(Length_{\Sigma}(l_{ji})\) of \(p_{ji}\) is minimal; 3. Verify if \(p_{ji}\) has an extra time slot \(t_{ji}^{extra}\) to receive \(c_{j}\)'s data; 4. If \(p_{ji}\) best satisfies all three conditions, it sends \(Optimal_{local}(p_{ji})\) to \(c_{k}\); 5. \(c_{k}\) for each received \(\{Optimal_{local}(p_{ji})\}\) from \(c_{j}\): 6. Determine \(Optimal_{global}(p_{ji})\) with conditions (a), (b) and (c); 7. If \(Optimal_{global}(p_{ji})\) is determined by \(c_{j}\) then assign \(slot(p_{j})\) to \(c_{j}\); 8. Else, keep \(slot(p_{j})\) assigning to \(MCR\_BP(p_{j})\); 9. Send registration request message \(M(c_{j},\ slot(p_{j}))\) to \(Optimal_{global}(p_{ji})\). The operations of Procedure Select-NE-MCR_BP are described below for two cases:  
* Case 1: parent node \(p_{j}\) has only one child \(c_{1}\). * Case 2: \(p_{j}\) has more than one child nodes \(c_{i}\)'s. First, consider case 1. Let \(p_{j}\) be the target parent node and let \(c_{1}\) be a child node of \(p_{j}\). Also let \(g\) be the grandparent node of \(c_{1}\). Suppose that \(c_{1}\) cannot reach its grandparent \(g\); in this case, NE-MCR carries out a single local search from \(c_{1}\), and then it selects the optimum NBP within the wireless range of \(c_{1}\). Then c1 sends a registration request message \(M(c_{1},\ slot(p_{j}))\) to the NBP. Here, \(slot(p_{j})\) indicates the time slot of \(p_{j}\) allocated for its transmission in TDMA protocol. Then NBP registers \(c_{1}\) with \(slot(p_{j})\), so upon the event when \(p_{j}\) ever fails, NBP expects to receive data from \(c_{1}\) not from \(p_{j}\) during \(slot(p_{j})\). Like the MCR algorithm, for any pi that fails, the NE-MCR algorithm recycles \(p_{j}\)'s time slot for its child node \(c_{1}\). Therefore, the fail recovery process requires no updates in time slot scheduling, leading to a low complexity and low power process. Additionally, it reduces the overhead of the whole fail recovery procedure.