Routing Techniques in Wireless Ad Hoc Networks—Classification and Comparison∗Xukai Zou, Byrav Ramamurthy and Spyros Magliveras⊕Dept. of Computer Science and Engineering⊕Dept. Of Mathematical SciencesUniversity of Nebraska-Lincoln Florida Atlantic UniversityLincoln, NE 68588-0115, U.S.A. Boca Raton, FL 33431, U.S.Aemail: {xkzou, byrav}@cse.unl.edu [email protected] (and forwarding) is a core problem in networks for deliv-ering data from one node to another. Today wireless networks arebecoming popular because of their “3 Anys”– Any person, Any-where and Any time. Wireless ad hoc networks are termed asmobile distributed multihop wireless networks without predeter-mined topology (preexisting fixed infrastructure) or central con-trol. In this paper, we present a comprehensive review for routingfeatures and techniques in wireless ad hoc networks. For morethan a dozen typical existing routing protocols, we compare theirproperties according to different criteria, and categorize them ac-cording to their routing strategies and relationships.Keywords. Routing protocols, Wireless communications, Adhoc networks.1 INTRODUCTIONRouting (and forwarding) is a core problem in networks for de-livering data from one node to another. Today, wireless networksare becoming popular because of their “3 Anys”–Any person,Anywhere and Any time [22, 25]. However, wireless networkshave special limitations and properties such as limited bandwidth,highly dynamic topology, link interference, limited range of links,and broadcast. Therefore, routing protocols for wired networkscannot be directly used in wireless networks; routing protocolsfor wireless networks need to be designed and implemented sep-arately [28].There are two typical categories of wireless networks [13, 24]:cellular (one hop) networks and wireless ad hoc (multi hop) net-works. Wireless ad hoc networks (formerly called packet radionetworks) are defined as mobile distributed multihop wirelessnetworks [7]. In a wireless ad hoc network, there is no prede-termined topology (preexisting fixed infrastructure) and no cen-tral control. The nodes in ad hoc networks communicate withoutwired connections among themselves by creating a network “onthe fly” [7]. Wireless ad hoc networks are traditionally used inbattlefield communications, law enforcement, disaster recovery(fire, earthquake, etc.), and emergency search and rescue. Re-cently, wireless ad hoc networks have been extensively used incivilian forums (i.e., “ad hoc personal” communications) such as∗This work was supported, in part, by the Nebraska ResearchInitiative (NRI)–Mobile Communications Research Project.electronic classrooms, convention centers, construction sites, andspecial events (concerts, festivals, etc.) [13, 20].There have been several routing protocols proposed for wirelessad hoc networks. There have also been several articles writtenwhich compare the performance and characteristics of differentprotocols [1, 5, 24, 26]. Among them, three articles [1, 5, 26]compare a few (up to four) protocols based on the simulation ofthe compared protocols and the authors of [24] provide a com-prehensive survey including qualitative comparisons of nine pro-tocols.In this paper, we identify various techniques used for classifyingrouting protocols for wireless ad hoc networks (Section 2), whichwill help the understanding of current protocols and the designingof new protocols . Moreover, we examine more than a dozentypical routing protocols, giving qualitative comparisons of theircharacteristics and categorizing them according to their routingstrategies and relationships (Section 3).2 CLASSIFICATIONThere are different criteria for designing and classifying routingprotocols for wireless ad hoc networks. For example, what rout-ing information is exchanged; when and how the routing infor-mation is exchanged, when and how routes are computed and soon. We will discuss these criteria in this section.Link state routing (LSR) vs. distancevector routing (DVR)As with conventional wired networks, Link state routing (LSR)and distance vector routing (DVR) are two underlying mecha-nisms for routing in wireless ad hoc networks. In LSR [28], rout-ing information is exchanged in the form of link state packets(LSP). The LSP of a node includes link information about itsneighbors. Any link change will cause LSPs to be flooded intothe entire network immediately. Every node can construct andmaintain a global network topology from the LSPs it receives,and compute, by itself, routes to all other nodes. The problemwith LSR is that excessive routing overhead may be incurred be-cause nodes in a wireless ad hoc network move quickly and thenetwork topology changes fast.In DVR [28], every node maintains a distance vector which in-cludes, but is not limited to, the triad (destination ID, next hop,(shortest) distance) for every destination. Every node periodicallyexchanges distance vectors with its neighbors. When a node re-ceives distance vectors from its neighbors, it computes new routesand updates its distance vector. The complete route from a sourceto a destination is formed, in a distributed manner, by combiningthe next hop of nodes on the path from the source to the desti-nation. The problems with DVR are slow convergence and thetendency of creating routing loops.Precomputed routing vs. on-demandroutingDepending on when the route is computed, routing protocols canbe divided into two categories: precomputed routing and on-demand routing.Precomputed routing is also called proactive routing or table-driven routing [24]. In this method, the routes to all destinationsare computed a priori. In order to compute routes in advance,nodes need to store the entire or partial information about linkstates and network topology. In order to keep the information upto date, nodes need to update their information periodically orwhenever the link state or network topology changes. The ad-vantage of precomputed routing is that when a source needs tosend packets to a destination, the route is already available, i.e.,there is no latency. The disadvantage is that some routes maynever be used. Another problem is that the dissemination of rout-ing information will consume a lot of the scarce wireless networkbandwidth when the link state and network topology change fast(this is especially true in a wireless ad hoc network). The conven-tional LSR and DVR are examples of proactive routing. We willuse
View Full Document
Unlocking...