# DARAL: A Dynamic and Adaptive Routing Algorithm for Wireless Sensor Networks
## 3 Dynamic and Adaptive Routing Algorithm (DARAL)
### Sub-Network Concept  
_DARAL_ routing is based on the use of sub-networks. Every sub-network possesses a sub-network ID (vID), which unequivocally identifies the sub-network in the whole network. Each cluster or sub-network groups a certain number of nodes, due to the number of nodes user-limited by the parameter \(L_{nodes}\), hence the load balance of _DARAL_. If the limit \(L_{nodes}\) is reached by a VC, that VC does not send any _ASSOCIATION_REP_ anymore, at least, as long as the number of connected nodes remains unchanged.  
VCs manage the sub-networks, possessing two different routing tables, one for the local nodes in the sub-network and another for routing tasks. VCs know only the routes below their position, for example in Figure 6, the VC from sub-network 3, knows the nodes in its sub-network and the nodes in sub-network 4. In Figure 6, the network root, (VC in sub-network 1) also knows the complete routing table. The particularity of _DARAL_ is that a message being routed between two different sub-networks is not completely processed. A VC in the route only needs to analyse the _Destination Virtual Network ID_, and look for it in the routing table, to know the next step in the route. Only messages that have already reached their destination sub-network are completely processed. Then, the VC of that sub-network looks for the destination address in the local nodes table.  
Figure 7: Dynamical role selection process (DRSP).  
Sub-network IDs (vIDs) are only generated by the network root. Once a vID is generated, all the VCs in the route update their routing tables, adding a new entry to them. On the other hand, if a new EN connects to a sub-network, the VC of that sub-network informs every node above him, sending an _ASSOCIATION_INFORM_ message. Every VC that receives an _ASSOCIATION_INFORM_ updates its own routing table.  
Due to this routing mechanism, it is necessary to check periodically the status of the different sub-networks, as well as the connectivity of the ENs. Figure 8 shows this process, which is fired by the user-defined timer \(T_{alive}\). When \(T_{alive}\) is expired, a VC sends a _KEEP_ALIVE_REQ_ message to its sub-network, checking the connectivity of every node. If a node does not respond like in Figure 9, another user-defined timer \(T_{down}\) is fired. When \(T_{down}\) expires, a purging request is generated by the VC, asking the VCs above him to remove that node from the routing tables.  
If the connectivity problem is detected by ENs and not by a VC, those ENs wait until the user-defined timer \(T_{recomect}\) is expired. If the timer expires and there is no answer from the VC, those ENs restart and begin with _DARAL_ and the _DRSP_, doubling the value of \(T_{recomect}\). If the time expires  
Figure 8: Message flow in a successful control check or keep alive operation.  
Figure 9: Message flow in a control check or keep alive operation with errors.  
once more, \(T_{reconnect}\) returns to its normal value, following a scheme \(t\)-2\(t\)-...-\(t\)-2\(t\). After restarting, the nodes reconnect the network and the routing tables are updated with the new information. If the keep alive process starts during the disconnection, a purge process is fired.