# DARAL: A Dynamic and Adaptive Routing Algorithm for Wireless Sensor Networks
## 2 Routing Algorithms for WSN
_AODV_ is a routing algorithm that discovers the routes using Route Request (RREQ) and Route Reply (RREP) messages, ensuring that there are no loops and, at the same time, trying to find the shortest possible route. A certain origin node broadcasts a RREQ to their neighbour nodes, looking for a certain destination node. These neighbours look in their routing tables for the destination node. If there is not any match, these neighbours also broadcast the original RREQ to other nodes, and the process continues until a node finds the destination node in its routing table. However, if there is a match, the node with the match resends the original RREQ to the destination node and once the destination node processes the RREQ, it answers with a RREP that is routed towards the originnode, setting the route and closing the route discovery process. As this routing method is on-demand fired, and it is based on a minimal number of hops, it does not ensure neither energy-efficiency, nor convergence time or control overhead efficiency. Moreover, _AODV_ only stores one route for a destination node, resulting in an additional use of resources if there is any problem with that route, due to the necessity of discovering a new one. The lack of a mechanism to ensure energy, convergence time efficiency and a minimal control overhead results in a waste of resources for constrained scenarios with low-/medium-densities, due to the instability of links and routes. On the other hand, _RPL_ routes are based on Destination Oriented Directed Acyclic Graphs (DODAGs). A _DODAG_ is a graph based on nodes and links forming the path to the network root, which is basically the sink or network coordinator. Thus, _RPL_ has been designed and optimized for the transmission of data from sensor nodes towards the root node, following a many-to-one scheme. For the construction and maintenance of a _DODAG_, _RPL_ nodes locally multicast _DODAG_ Information Object (DIO) messages pseudo-periodically, which contain information that allows a node to discover an existing _DODAG_, jointly with its configuration parameters. Once a node receives a DIO message from a neighbour, it will be able to join an existing _DODAG_. However, if a node is trying to connect the network and does not receive any DIO message, it can send a _DODAG_ Information Solicitation (DIS) message to request the immediate transmission of DIO messages. Once the DIS message is sent, additional DIS messages may be sent until a DIO message is received in response. However, if a DIO message is not received after a certain time, the node may decide to become the root of a new _DODAG_. _RPL_ also supports downwards routes by using Destination Advertisement Object (DAO) messages, which are generated and sent upwards by non-root nodes to announce themselves as possible destination nodes. The lack of energy and convergence time efficiency, jointly with the control overhead, results, as in the _AODV_ case, in a waste of resources. This problem was analysed by [PERSON] et al. in [7], where an optimized _RPL DODAG_-route forming method (O-RPL) was proposed to reduce the convergence time for dense scenarios [7]. This also shows an interesting test-bed to analyse both the convergence time and control overhead in terms of node degree (density). As described above, existing routing algorithms present some drawbacks related to the lack of an integrated QoS, an efficient convergence time and a minimal control overhead in the network formation stage for Smart City/IoT scenarios, considering these scenarios as low-/medium-density environments. With this goal in mind, we propose a new routing algorithm based on the LQI, which is hierarchically organized in sub-networks, that improves the convergence time and the message control overhead for Smart City/IoT scenarios with a small-/medium-density where the coverage is a critical parameter.