# An Energy-Efficient Fail Recovery Routing in TDMA MAC Protocol-Based Wireless Sensor Network
## 3 Proposed Route-Recovery Algorithms
### Neighbor-Extended Maximal Connectivity Routing
Otherwise, the child node should have sent a request for a new TDMA slot to NBP, and this also would have triggered the time-consuming process of rebuilding the time slot table for the entire network. Now consider case 2, where parent node \(p_{j}\) has more than one child nodes \(c_{i}\)'s. If the MCR algorithm finds no \(MCR\_BP\) that can reach the grandparent \(g\), it selects the \(MCP\_BP\) with the maximum \(Connectivity(c_{i})\). In this case, the NE-MCR algorithm searches for neighbor backup parent NBPs in the neighbor subtrees. For the child node \(c_{j}\) (including \(MCR\_BP\)), NE-MCR conducts a search within the wireless range of \(c_{j}\) and selects a NBP \(p_{ji}\) that is a local optimum for \(c_{j}\), if such an NBP exists. The objective function which evaluates the optimality of NBP is described in Section 4. Once \(c_{j}\) determines its \(Optimal_{local}(p_{ji})\), it forwards a message \(M(c_{j},p_{ji},d_{j})\) to \(MCR\_BP\). The \(MCR\_BP\) collects the messages on \(Optimal_{local}(p_{ji})\) of all child nodes, and determines the globally optimum NBP (\(Optimal_{global}(p_{ji})\)). If the algorithm determines \(Optimal_{global}(p_{ji})\) that is originally found by \(c_{j}\), it assigns \(slot(p_{j})\) to \(c_{j}\). Then, it requests \(c_{j}\) to send \(M_{Child{Req}}\) message to \(p_{ji}\). Like in Case 1, if \(p_{j}\) ever fails in the forwarding operations for Case 2, \(c_{j}\) uses \(slot(p_{j})\) to transmit data to \(Optimal_{global}(p_{ji})\). Then, \(c_{j}\) changes its role from a child to \(MCR\_BP\) and forwards the data from the isolated subtree under \(p_{j}\) to \(Optimal_{global}\left(p_{ji}\right)\). If the \(Optimal_{global}\left(p_{ji}\right)\) is originally found by \(MCR\_BP\), it keeps using \(slot\left(p_{j}\right)\) and sends a registration request message to the \(Optimal_{global}\left(p_{ji}\right)\). Figure 6 illustrates a flow diagram of the overall NE-MCR algorithm, where the procedure Select-NE-\(MCR\_BP\) is highlighted with a blue dotted line. The NE-MCR algorithm conducts a search for \(Optimal_{global}\left(p_{ji}\right)\) only within the wireless range of \(c_{j}\)'s that are either \(MCR\_BP\) or one of its siblings. The NE-MCR algorithm considers as candidates of NBP only the neighbor nodes that do not share the same parent with the current isolated nodes. For example, Figure 7 shows a subtree, where the target parent node is market by a red circle, while its child nodes are market by purple colors. Among the child nodes, a node is selected as \(MCR\_BP\). For the target parent node, the MCR algorithm is conducted only by the purple nodes (\(MCR\_BP\) and its siblings). The green nodes do not participate in the search operation, since they share the same parent (or grandparent) with the purple nodes. For candidates of NBP, only the blue nodes within the wireless range circles are eligible. To measure the optimality of candidate NBPs, we utilize the aggregated packet length of each NBP and the distance between \(c_{j}\) and each NBP. In the current work, we assume that the selected NBP has an extra time slot available to receive additional data. When NE-MCR determines the \(Optimal_{global}\left(p_{ji}\right)\) with a closer distance to the child nodes \(c_{j}\)'s, it can reduce the transmission power of \(c_{j}\)'s and, therefore, can allow \(c_{j}\)'s to conserve more energy. Many literatures [24; 35; 38] have emphasized the critical effect of transmission distance on the energy consumption. To the best of our knowledge, however, no prior fault recovery methods like our method have been reported that minimize the distance from the  
Figure 6: A flow diagram of proposed NE-MCR algorithm. Figure 7: Avoid the same branch concept in NE-MCR algorithm. backup parent to the child nodes in the isolated subtree. In the following section, we discuss how we estimate the energy consumption during the search procedures for backup parents.