## 3 Data Routing Approaches in WSNs
### Fault-Tolerant Approaches
#### 3.3.2 Fault Recovery  
An Adaptive routing protocol for fast Recovery from large-scale Failure (ARF) is proposed in [73] for applying a fast fault-tolerant mechanism in a routing tree for large scale sensor networks. ARF comprises a Routing Table, Table Manager, Link Estimator, Parent Selector, Cycle Detector, Forwarding Module, Routing Recoverer, Timer, and Dispatcher. In this approach, each node has its own parent, but it maintains a list of its neighbors as possible parents and counts its unsuccessful packet transmissions. Whenever a node cannot receive a signal from a neighbor, it considers the neighbor failed and extracts its ID from the list of possible parents. Also, when a parent of a node dies, the parent selector of the node starts the Routing Recoverer to select another node in the list of its possible parents as its parent. Moreover, when there isn't any alternative for replacing the parent, the node is considered orphan. In this case, the orphan node shortens its transmission interval and asks its neighbor nodes for a parent by a control message with the flag of orphan. When a neighbor node who has a reliable parent receives the orphan message, it attempts to help the nodes by shortening its transmission interval. Therefore, when the orphan receives a control message from a possible parent, it considers the sender as its parent and again extends its transmission interval. The ARF algorithm depends on the parent node selection and routing tree construction. Whenever these two are carried out fast, the failure recovery is performed fast, too. The time complexity of  
Figure 10: Virtual grid of cells. initialization process of ARF is O (V) where V is the average number of neighbor nodes. Also, the process of link quality computing takes O (logV) and selecting back-up parent in parent procedure takes O (logV) time. Regarding the fact that a node can have maximum V\(-\)1 edges, the loop of finding parent runs V\(-\)1 times in a worst case. Therefore, the time complexity of parent procedure is O (V logV) in the worst case. In [50] the authors proposed a cellular approach for fault detection and recovery. In the proposed mechanism, network area is separated into a virtual grid of cells. Each virtual grid is assigned a cell manager and a secondary manager as a back-up. The back-up managers handle the cell in case of cell manager's failure or when it cannot do its task (Figure 10). The cell managers in each cell perform and manage a fault-tolerant mechanism. At the initialization phase, selection of the cell managers is done based on their coordinates in the cell. In this mechanism, the node with the highest coordinates in the cell is selected as the cell manager and the node with the next highest coordinates is selected as the back-up manager. Later on, these selections are performed based on the residual energy of the nodes and the nodes with highest residual energy are selected as the managers. A cell manager receives the data of their members by one-hop communication and transmits it to its neighboring cell managers. In this approach, fault recovery in done in each cell separately. When the energy level of a node goes below a threshold, the node is considered a failed node; therefore, it sends a message to the cell manager to inform it about its status; then, it changes its status to low computational mode. Moreover, when the energy level of the cell manager goes below the threshold, it sends a notification message to its members and the back-up manager. Therefore, the members consider the back-up manages as their new cell manager. On the other hand, a back-up manager considers itself the new cell manager and selects another node as the back-up manager upon receiving the notification message of the cell manager. For instance, in Figure 10, when the energy level of the cell manager goes below threshold, it sends a message to a, b, c and d to report its status. Hence, one of these nodes (like b) which have the highest residual energy will be selected as the cell manager.