Topology Control for Ad-Hoc Networks: A Comprehensive Review for Table Driven and On-Demand Routing Protocols

Jeferson Wilian de Godoy Stênico, Lee Luan Ling

.
School of Electrical and Computer Engineering State University of Campinas—UNICAMP, Campinas, Brazil.

DOI: 10.4236/cn.2013.53029                

Abstract

Routing on ad-hoc network has become a major research issue among the networking communities due to its increasing complexity and the surge of challenging problems. One major factor contributing to this tendency is that every terminal of an ad-hoc network is also functioning as a network router. In this paper we provide a comprehensive review about the principles and mechanisms of routing protocols used in ad-hoc networks. For comparison purposes, we discuss some relevant technical issues of two well-known routing strategies, namely On-Demand (Proactive routing) and Table-Driven (Reactive routing). In particular, focus our attention on two major and well-known routing protocols: AODV (Ad-hoc On-Demand Distance Vector Protocol) and OLSR (Optimized Link State Routing Protocol). Our study has no intention to suggest any definite solution for any ad-hoc network, because it is the case depending on dictated by the nature and varying factors of networks. Instead, we demonstrate our major perception and describe general models that may assist us while modeling a given network.

Keywords

Ad-Hoc; Distributed Protocols; On-Demand Protocols; Routing Tables

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	http://www.ietf.org/
[2]	C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proceedings of the Conference on Communications Architectures, Protocols and Applications, Vol. 24, No. 4, 1994, pp. 234-244. doi:10.1145/190314.190336
[3]	C. Maihofer, “A Survey of Geocast Routing Protocols,” IEEE Communications Surveys & Tutorials, Research & Technology (RIC/TC), Vol. 6, No. 2, 2004, pp. 32-42.
[4]	S. Ratnasamy, “Capturing Complexity in Networked Systems Design: The Case for Improved Metrics,” 2006.
[5]	M. S. Corson and A. Ephremides, “A Distributed Routing Algorithm for Mobile Wireless Networks,” Wireless Networks, Vol. 1, No. 1, 1995, pp. 61-81. doi:10.1007/BF01196259
[6]	E. M. Gafni and D. P. Bertsekas, “Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology,” IEEE Transactions on Communications, Vol. 29, No. 1, 1981, pp. 11-18. doi:10.1109/TCOM.1981.1094876
[7]	E. M. Royer and C. K. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications, Vol. 6, No. 2, 1999, pp 46-55. doi:10.1109/98.760423
[8]	G. Jayakumar and G. Ganapathy, “Performance Comparison of Mobile Ad-hoc Network Routing Protocol,” International Journal of Computer Science and Network Security, Vol. 7 No. 11, 2007, pp. 77-84.
[9]	J. Raju and J. J. Garcia-Luna-Aceves, “A Comparison of On-Demand and Table-Driven Routing for Ad-Hoc Wireless Networks,” IEEE International Conference on Communications, Vol. 3, New Orleans, 18-22 June 2000, pp. 1072-1706.
[10]	A. Huhtonen, “Comparing AODV and OLSR Routing Protocols,” Heleniski University of Technology, Espoo, 2004.
[11]	C. E. Perkins and E. M. Royer, “Ad-Hoc On-Demand Distance Vector Routing,” Proceeding of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, 25-26 February 1999, pp. 90-100. doi:10.1109/MCSA.1999.749281
[12]	Y. C. Hu and D. B. Johnson, “Implicit Source Routes for On-Demand Ad Hoc Network Routing,” Proceedings of the 2001 ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc 2001), Long Beach, May 2001, pp. 1-10.
[13]	V. D. Park and M. S. Corson, “A Highty Adaptative Distributed Routing Algorithm for Mobile Wireless Network,” Proceeding of IEEE INFOCOM’97, 6th Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, April 1997, p. 1405.
[14]	C. K. Toh, “A Novel Distributed Routing Protocol to Support Ad hoc Mobile Computing,” IEEE 15th Annual International Phoenix Conference on Computers and Communications, Phoenix, 27-29 March 1996, pp. 480-486.
[15]	R. Dube, C. D. Rais, K. Y. Wang and S. K. Tripathi, “Signal Stability-Based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks,” IEEE Personal Communications, Vol. 4, No. 1, 1997, pp. 36-45. doi:10.1109/98.575990
[16]	S. Murthy and J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” Journal of Mobile Networks and Applications. Routing in Mobile Communications Networks, Vol. 1, No. 2, 1996, pp 183-197. doi:10.1007/BF01193336
[17]	C. C. Chiang, H. K. Wu, W. Liu and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” IEEE Singapore International Conference on Networks, October 1997, pp. 197-211.
[18]	C. Perkins, E. B. Royer and S. Das, “Ad-Hoc On-Demand Distance Vector (AODV) Routing,” RFC 3561 IETF Network Working Group, 2003.
[19]	J. Haerri, F. Filali and C. Bonnet, “Performance Comparison of AODV and OLSR in VANETs Urban Environments under Realistic Mobility Patterns,” The 5th IFIP Mediterranean Ad Hoc Networking Workshop, June 2006, pp. 14-17.
[20]	S. Gowrishankar, T. G. Basavaraju, M. Singh and S. K. Sarkar, “Scenario Based Preformance Analysis of AODV and OLSR in Mobile and Ad-hoc Networks,” The 24th South East Asia Regional Computer Conference, November 2007, pp. 8.1-8.6.
[21]	A. B. R. Kumer, L. C. Reddy and P. S. Hiremath, “Performance Comparison of Wireless Mobile Ad-Hoc Network Routing Protocol,” International Journal of Computer Science and Network Security, Vol. 8 No. 6, 2008, pp. 337-343.