# DARAL: A Dynamic and Adaptive Routing Algorithm for Wireless Sensor Networks
## 3 Dynamic and Adaptive Routing Algorithm (DARAL)
### Cluster Creation Using the Dynamic Role Selection Process (DRSP)  
As Figure 3 shows, a node selects the best link to connect with and, once it is chosen, the node evaluates the LQI to adopt one of two possible roles in the network, EN or VC. EN is basically limited to receiving and sending messages, reducing as much as possible its active time, thus saving energy. On the other hand, VCs are the key elements in \(DARAL\), being used to widen the network coverage range and to route messages among sub-networks. VCs play both roles at the same time, which can be seen in Figure 6, as ENs for the network they belong to and as VC to the sub-network that they own. In Figure 6, every VC shows their two vIDs, the _original vID_ from the network where they belong, and the _additional vID_ from the sub-network that they manage.  
_DRSP_ is based on two user-defined parameters: \(TH_{\textit{baselinevel}}\) and \(TH_{\textit{role}}\). \(TH_{\textit{baselinevel}}\) is basically a threshold granting a minimum QoS for the link with the VC. Any link with a LQI below \(TH_{\textit{baselinevel}}\) is not established. On the other hand, \(TH_{\textit{role}}\) defines the threshold for the role. If the LQI is above \(TH_{\textit{role}}\) a node configures itself as EN, due to the good QoS of the link. However, if the LQI is below \(TH_{\textit{role}}\) (and above \(TH_{\textit{baselinevel}}\)), a node adopts the role of VC, considering that from that point in advance the QoS will worsen even more. \(DARAL\) is based on the concept that a high LQI (above \(TH_{\textit{role}}\)) means  
Figure 4: Message flow in a VC association operation.  
Figure 5: Message flow in an EN association operation.  
a better QoS and a nearest position, allowing grouping nodes and a traffic concentration, hence the adoption of EN role. A worse LQI (below \(TH_{role}\)) represents a point where the QoS is not good enough, and if the distance continues increasing, that QoS will worsen. To reduce the impact of the deterioration in the QoS, a VC acts as a concentrator, which allows for expanding the network coverage.  
Figure 7 shows a UML description of \(DRSP\), detailing how it is carried out. First of all, it is necessary to set some internal parameters to their default values, and then collect some VC answers. The third step is the selection of the answer with the higher LQI, and then the \(TH_{baselevel}\) is evaluated. If the LQI is below \(TH_{baselevel}\), the process finishes. Otherwise, if it is above \(TH_{baselevel}\), then it continues evaluating the \(TH_{role}\) value. If the LQI is above the \(TH_{role}\), then the role is set to EN, the node status changes to _CONNECTED_, and the node is marked as non-VC. If the LQI is below \(TH_{role}\) (and above \(TH_{baselevel}\)), then the role is set as VC, the status is set to _AWAITING_, and the node is marked as VC. The _AWAITING_ status means that a VC is connected and can receive messages, but, at the moment, cannot route packets. This status changes to connected when that VC receives a vID for its new sub-network.  
Finally, the algorithm evaluates the node role adopted to send an _ASSOCIATION_PAN_ID_REQ_, if the role is VC, or an _ASSOCIATION_REP_ACK_, if the role is an EN. At the end, different timers, like packet delivery time or connection status time, are set.  
Each node in the network, except for the coordinator, executes \(DRSP\), dynamically creating the network hierarchy. The nodes analyse the potential connections and choose the best one. Once the node is established, the connection continues. If the node is an EN, it does nothing more, and only communicates with its VC when it is needed. However, if the node is a VC, the node asks for a vID due to the creation of a new sub-network. Once the new vID is set, the sub-network is also created and the node acts as a potential father for other nodes, continuing the process until no more nodes ask for connection.  
Figure 6: Example of virtual sub-networks’ organization.