Wireless Networks 8, 137–151, 2002 2002 Kluwer Academic Publishers. Manufactured in The Netherlands.Query Localization Techniques for On-Demand Routing Protocolsin Ad Hoc NetworksROBERT CASTAÑEDADivision of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249-0667, USASAMIR R. DAS and MAHESH K. MARINADepartment of Electrical & Computer Engineering and Computer Science, University of Cincinnati, Cincinnati, OH 45221-0030, USAAbstract. Mobile ad hoc networks are characterized by multi-hop wireless links, absence of any cellular infrastructure, and frequent hostmobility. Design of efficient routing protocols in such networks is a challenging issue. A class of routing protocols called on-demandprotocols has recently found attention because of their low routing overhead. We propose a technique that can reduce the routing overheadeven further. The on-demand protocols depend on query floods to discover routes whenever a new route is needed. Our technique utilizesprior routing histories to localize the query flood to a limited region of the network. Simulation results demonstrate excellent reductionof routing overheads with this mechanism. This also contributes to a reduced level of network congestion and better end-to-end delayperformance of data packets.Keywords: ad hoc networks, routing protocols, on-demand routing, flooding1. IntroductionA mobile, ad hoc network is an autonomous system of mo-bile hosts connected by wireless links. There is no static in-frastructure such as a base station. If two hosts are not withinradio range, all message communication between them mustpass through one or more intermediate hosts that double asrouters. The hosts are free to move around randomly, thuschanging the network topology dynamically. Thus, routingprotocols must be adaptive and able to maintain routes in spiteof the changing network connectivity. Such networks arevery useful in military and other tactical applications such asemergency rescue or exploration missions, where cellular in-frastructure is unavailable or unreliable. Commercial applica-tions are also likely where there is a need for ubiquitous com-munication services without the presence or use of a fixed in-frastructure. Examples include home-area wireless network-ing [17], on-the-fly conferencing applications, networking in-telligent devices or sensors, communication between mobilerobots, etc.Design of efficient routing protocols is the central chal-lenge in such dynamic wireless networks. Much work hasbeen done in this area starting from the seventies, when theUS Defense Research Agency, DARPA supported the PRNET(Packet radio Network) [13] and SURAN (Survivable Adap-tive Networks) [21] projects. They supported automatic routeset up and maintenance in a packet radio network with mod-erate mobility. Interest in such networks has recently growndue to the common availability of wireless communicationdevices that can connect laptops and palmtops and operatein license free radio frequency bands (such as the Industrial-Scientific-Military or ISM band in the US). In an interest torun internetworking protocols on ad hoc networks, a work-ing group for Mobile, Ad hoc Networking (MANET) [16]has been formed within the Internet Engineering Task Force(IETF), whose charter includes developing a routing frame-work for running IP-based protocols in ad hoc networks. Sev-eral new routing protocols have been proposed in connectionwith the MANET working group efforts [16]. Of particu-lar interest is the new class of on-demand, source-initiatedprotocols, that set up and maintain routes from a source toa destination on an “as needed” basis. This approach is insharp contrast with the traditional shortest path-based proto-cols (e.g., link-state and distance vector [14]) that have beenused successfully in dynamic, wireline networks, includingthe Internet.1.1. On-demand protocols and floodingThe motivation behind the on-demand protocols1is that the“routing overhead” (typically measured in terms of the num-ber of routing packets transmitted, as opposed to data pack-ets) is typically lower than the shortest path protocols as onlythe actively used routes are maintained. However, as somerecent performance evaluation work has shown [7], the rout-ing overhead still approaches that of the shortest path proto-cols, if a moderate to large number of routes needs to be ac-tively maintained (when, for example, there is a moderate tolarge number of active peer-to-peer conversations). This is be-cause the on-demand protocols discover routes via a floodingtechnique, where the source (or any node seeking the route)floods the entire network with a query packet in search of a1In this paper, we use the term “on-demand routing” synonymously withprotocols that search routes via flooding. Note that on-demand routing is ageneral paradigm which is used in other contexts as well (e.g., QOS rout-ing).138 CASTAÑEDA, DAS AND MARINAroute to the destination. After receiving the query, each non-destination node propagates it to its neighbors via a wirelessbroadcast. Each query carries a unique identifier which helpsprevent multiple propagation of the same query by the samenode. This technique guarantees that the query reaches allnodes in the same connected component. Thus, if the desti-nation is reachable from the source, the query will eventuallyreach the destination.The sequence of hops traversed by the first query messagereceived by the destination defines the route to be used forsending data packets. On receiving the first query, the destina-tion replies to the source by sending a route reply message. Ifthe wireless links are bidirectional, the reply goes back to thesource just by retracing the route in the opposite direction.2The actual mechanics of doing this varies from protocol toprotocol. For example, the DSR (Dynamic Source Routing)protocol [12], builds the route incrementally as a sequence ofnodes visited by the query, and stores it in the header of thequery packet. The reply packet carries this route and simplytraverses it backwards. The AODV (Ad Hoc On-Demand Dis-tance Vector) routing protocol [20], on the other hand, main-tains the route in a distributed fashion using routing tables inthe nodes on the route.Flooding is straightforward to implement. However, asmentioned before, network-wide flooding incurs a consid-erable overhead and diminishes the performance advantageof on-demand protocols. Although several optimizations ofthe