Multi hop routing principles in ad hoc networks

In conventional wired networks, an issue of data routing is considered to be a mature field, where effective and reliable solutions exist, as well as dedicated hardware is placed in the network purely for this specific task (routers). However, due to unique properties of wireless ad hoc networks, such as dynamic topology, wireless transmission medium as well as energy consumption and computational constraints, the task of development of an effective multi-hop routing scheme becomes non-trivial.

In order to face with such challenges, the research community has developed a large number of routing algorithms for wireless ad hoc networks, which operate with different efficiency in specific networks. A major class of ad hoc network routing protocols is intended to minimize such main network attributes like control overhead, packet loss ratio, packet delay and energy consumption rate, while maximizing a network throughput [1] .

Usually, this class of protocols is divided into three large subclasses, based on their underlying route discovery logic:

• reactive, also called as on-demand protocols:

those protocols are based on the on-demand strategies, i.e. a route (network path) is created only when the source node requests a data transmission to some destination node in the network. For this purpose, a route discovery procedure must be invoked each time a data entity has to be transmitted. During the route discovery phase, a source node sends a route request message (RREQ) and waits for route reply messages (RREP) from its direct neighbors. When the first RREQ message arrives to the destination node, it sends back RREP message, containing the information about the path. In such way, the route gets established when the source receives RREP packet from the destination node, and the data transmission can be triggered. When the data transmission has been finished, the established route becomes inactive after some predefined timeout interval. Some well-known reactive ad hoc routing protocols: DSR [2] , AODV [3] .

• proactive or table-driven protocols:

are based on conventional “table-driven” routing techniques, when the information about the routes from each node to all the possible destinations is gathered on-the fly during the data transmission. In this case, each node has its own routing table containing information about the paths from it to all the other nodes in the network. The global routing information is continuously being updated and exchanged between the nodes by broadcasting control packets to the network. Eventually, all nodes in the network obtain an actual global route table, so that a classical algorithms (Bellman-Ford, Dijkstra) from a graph theory can be used by a node to find a path to any possible destination in the network.

The route update mechanism in proactive protocols becomes a challenging problem in the conditions of wireless ad hoc networks due to their specific features, such as power consumption restrictions, dynamic topology, noisy wireless environment. Thus, they are not widely used in ad hoc networks in their initial concept, however, a proper modifications of the proactive scheme have been realized in OLSR [4] and B.A.T.M.A.N. [5] , so now they are most commonly used as the routing layer in ad hoc networks. Some well-known proactive protocols: DSDV [6] , OLSR, B.A.T.M.A.N.

• hybrid protocols:

those protocols use both reactive and proactive techniques, depending an current transmission environment. Example of such protocols – HWMP [7] , used in IEEE 802.11s MAC mesh standard.