Topology Control for Ad-Hoc Networks: A Comprehensive Review for Table Driven and On-Demand Routing Protocols ()
1. Introduction
A routing algorithm can be viewed as a part of the set of software or programs executed by the network layer and is responsible for transporting traffic packets from their sources to their destinations. Routing algorithms on Ad-hoc networks have become a never-ending developing issue. IETF (Internet Engineering Task Force) [1] has created a specific working group to address the problems and standards of routing algorithms on mobile ad-hoc networks.
One of the major challenges of routing on ad-hoc networks is the loss of communication. The phenomenon happens either when terminals are turned off or when they move out of covered regions. Losses of communication cause serious problems on networks. Suitable solution to this kind of problem should be considered as early as during network design on the architecture level [2].
Network performance depends directly on the quality of routing algorithms [3,4]. Routing problems and strategies have been widely investigated in recent years. Many routing protocols and algorithms have proposed implemented and used to solve routing problems [5-7]. In practice, those protocols were designed to deal with network operational constraints such as energy consumption of mobile nodes, limited bandwidth and high bit error rates.
There is no consensus about the best routing strategy for ad-hoc networks. Each protocol presents some advantages as well as disadvantages, which are connected to a specific scenario [8]. Therefore, from a network designer’s point of view, the search of routing protocol should focus on the one better suiting the scenario, instead of the best one under certain criteria. In this paper we provide a close comparison between two major routing perceptions for networks under ad-hoc network environment: table-driven and on-demand protocols. A table-driven protocol constantly scans the network in order to maintain and update optimal routing paths between every pair of terminals. An on-demand protocol, on the other hand, literally generates some routing directions on-demand not necessarily optimal ones.
In literature there are many research works illustrate different aspects of routing over ad-hoc networks [3,8- 10]. The most popular table-driven ones include: OLSR (Optimized Link State Routing), DSDV (Destination-Sequenced Distance-Vector Routing), WRP (Wireless Routing Protocol) and CGSR (Cluster-head Gateway Switch Routing). For on-demand categories, we cite: AODV (Ad-hoc On-demand Distance Vector Routing), DSR (Dynamic Source Routing), LMR (Lightweight Mobile Routing), TORA (Temporally Ordered Routing Algorithm), ABR (Associatively-Based Routing) and SSR (Signal Stabile Routing).
In this paper, a brief survey regarding different routing mechanisms by considering basic features and functionalities within their classifications is given. In addition, we focus on a comparison between two major routing protocols: OLSR (Optimized Link State Routing) and AODV (Ad-hoc On-demand Distance Vector), estimating their performances under various scenarios through simulation.
This paper is organized as follows. In Section 2 we present and describe the characteristics of the routing mechanism for each above mentioned routing protocol, starting with one belonging to the on-demand category and then the table-driven ones. In Section 3, we define a complexity measure of OLSR and AODV protocols and provide a comparison analysis based on the defined measures. In Section 4, we present and compare networking simulation results for AODV and OLSR protocols, In Section 5 we present our comments and conclusions. Finally in Section 6 we provide some clues regarding possible future work.
2. Routing Mechanisms
Today, with a tremendous number of routing techniques and protocols, as wireless communication technology is increasing on daily basis, there not exists a single optimal solution for routing. Technologically speaking, a routing algorithm has the goal of mapping the network topology onto a routing table. Construction, upgrade and maintenance costs vary according to the routing method chosen. Given the dynamic nature of an ad-hoc network, protocols developed for wired networks are considered efficient. Also, routing has shown great a challenge with the consumption of energy and bandwidth, and achieves a good level of quality service. We distinguish between proactive and reactive protocols (on-demand and tabledriven respectively). On this section will list some of these protocols, emphasizing the AODV and OLSR protocols.
2.1. On-Demand Protocols
2.1.1. AODV
AODV protocol was originally designed as an adaptive routing protocol for scenarios where there are terminals with high mobility. The protocol intends to avoid waste by bandwidth caused by traffic control messages (used for routing table information updating). Instead of usingthe traditional routing table approach, this protocol discovers routes “on-demand”. Whenever two terminals intend to establish a connection, this routing protocol is invoked to initiate a Route Discovery process which is a flooding mechanism used to learn the current network routing environment. Once a route between two terminals is established, the route and routing information is saved at two terminal nodes for a determined period of time so that the same route can be used by new data as long as it is necessary. As a result, there is a considerable reduction in transmitting overhead information.
An important aspect of AODV routing is the maintenance of existing routes. Since the nodes are mobile, their movement may cause rupture of the established route links, therefore making the route no longer valid. To validate the integrity of already established routes can be done by sending hello packets [11]. Whenever a terminal fails to receive hello messages, the source node removes the corresponding route and updated its cache information.
Figure 1(a) illustrates the propagation of the broadcast RREQs (route request packets) across the network. AODV utilizes sequence numbers to determine an up-to-date path to a destination, i.e. every entry in the routing table is associated with a sequence number. The sequence number act as a route timestamp, ensuring freshness of