## 3 Data Routing Approaches in WSNs
### Fault-Tolerant Approaches
#### 3.3.1 Fault Prevention
In this approach, two heuristic mechanisms to specify the potential locations of the relay nodes are proposed: _grid based mechanism_ and _intersection based mechanism_. In the grid based approach, the whole network is considered as a virtual grid and the  
Figure 8: The operation of Directed Diffusion Algorithm. relay nodes are placed at the center and corners of each cell. In large scale sensor networks where the number of deployed nodes in the sensing environment is high and finding the location of the sensor nodes is difficult, this mechanism seems to be useful. On the other hand, when the locations of the sensor nodes are known and they are deployed in specific places of sensing area, an intersection based mechanism can be used which can calculate the correct positions of the relay nodes wherein they can cover all the sensor nodes. According to the proposed formulation of the approach, among the potential relay nodes, some relay nodes which cannot be considered as a cluster head may be used, too. Such relay nodes are exploited to maintain the survivability of the relay nodes and improving the network lifetime. Moreover, the proposed routing scheme considers the energy level of the critical relay nodes to provide more reliable data transmission. The proposed approach is proper for the applications in which the sensor nodes are immobile and the routing schedule and the placement of the relay nodes are managed by the base station. In [71] the authors proposed a distributed shortest hop multipath algorithm for satisfying fault-tolerance and load balancing in WSNs. The proposed Shortest Hop Multipath (SHM) algorithm is an improved version of Chang-Roberts distributed spanning tree (CRDST) algorithm which is able to construct a balanced spanning tree by defining and using different types of messages in a correct sequence order. CRDT uses two messages in its algorithm: _probe_ message which is transmitted by the nodes for requesting a membership and _echo_ message as an acknowledgement to the _probe_ message. When all the nodes in the networks received their acknowledgement, the algorithm is finished. SHM criticizes this approach by notifying that the constructed spanning tree in CRDST is unbalanced and it cannot ensure Breadth-First-Search (BFS) tree formation after termination. Therefore, SHM ensures the BFS tree formation by utilization of \(\beta\) synchronizes approach [72]. The proposed algorithm is performed layer by layer and the operation of the nodes is switched to another layer when the nodes of one layer finished their functions (Figure 9). Figure 9: Process of shortest hop multi paths construction in SHM [71]. SHM defines two types of nodes: initiator and non-initiator. The initiator node is the sink node which is used as the root of the spanning tree and other nodes (internal and leaf nodes) act as non-initiator nodes. Five types of messages are defined in this approach: _probe_ message for parent request, _ack_ message which is the acknowledgment of _probe_, _pulse_ message which is sent by the sink node for specifying the proper level for sending the _probe_ message and finally _pulseAck_ and _pulseNack_ as the acknowledgements of _pulse_ message which have used for termination detection. Thus, the process of tree construction and shortest hop multi paths generation in SHM is done by taking advantage of these messages based on \(\beta\) synchronize approach. In this approach, initiator begins the next step when it receives all expected messages and the generation of BFS tree is done after each execution. Figure 10 depicts this process.