L+: Scalable Landmark Routing and Address Lookupfor Multi-hop Wireless NetworksBenjie Chen Robert MorrisLaboratory for Computer ScienceMassachusetts Institute of TechnologyCambridge, Massachusetts, 02139{benjie,rtm}@lcs.mit.eduAbstractThis paper proposes and analyzes modifications to the Land-mark routing system that make it better suited to large ad hocwireless networks. Most existing ad hoc routing algorithmsscale badly in the sense that they generate protocol overheadwhose per-node cost grows linearly with the total number ofnodes. The Landmark routing protocol solves this problemby use of hierarchical addresses that contain routing hints;as a result, however, a node’s address changes as the net-work topology changes. The Landmark system tracks nodeaddresses with a distributed ID-to-address location service,but queries to this service require communication with ran-dom non-local nodes, which scales badly in large networks.The main contribution of this paper is a set of modifi-cations to the Landmark address lookup service to make itmore scalable. The paper also improves the Landmark hier-archy maintenance and routing algorithms to help them reactbetter to mobile nodes. Finally, it presents a simulation eval-uation of the resulting system, L+, from the point of view ofscalability in wireless ad hoc networks. The evaluation showsthat the per-node bandwidth requirement of L+grows veryslowly as the number of nodes in the network increases. Thisis consistent with our analysis that the per-node communica-tion cost of L+is O(log N).1 IntroductionThis paper addresses the problem of scalable routing in largead hoc wireless networks of mobile nodes. Such networks areof interest because they do not rely on fixed infrastructure.As a result these networks can support a number of promis-ing new technologies such as ubiquitouscomputing[24], sen-sor networks, rooftop networks [1, 19], and wireless PDAs.A major obstacle to the use of large ad hoc networks is thelack of an adequately scalable routing system. This paper de-scribes and analyzes modifications to the Landmark routingsystem [22, 21, 23] to make it suitable for large ad hoc wire-less networks.An important way in which wireless ad hoc networks dif-fer from wired networks, and wireless networks with wiredbackbones, is that they are likely to have severely constrainedcapacities. Each node’s radio is likely to have the same capac-ity; an engineered high-capacity wireless backbone is likelyto be awkward in many ad hoc scenarios. More fundamen-tally, the nodes are embedded on a plane, with connectivityonly to nearby nodes. Assuming uniform node density, theexpected distance between a random pair of nodes is O(√N)in both physical distance and number of hops, where N is thetotal number of nodes; similarly, the cross section bandwidthof the network is also O(√N). This means that if commu-nication patterns tend to be long-distance, or even random,the average amount of traffic that any one node can origi-nate scales as1√N[7, 12]. That is, the more nodes there are,the less long-distance traffic any one node can originate. Thisholds true even if the area of the universe (and thus the degreeof spectrum re-use) scales with the number of nodes.As a consequence of this capacity constraint, the domi-nant traffic patterns in large ad hoc networks will probablyneed to be local [12]; this would allow each node to origi-nate an amount of traffic independent of the total size of thesystem. However,it is not enough that the traffic pattern be lo-cal: the per-node overhead generated by the routing protocolmust also grow slowly with total network size. One conse-quence of this is that, ideally, the per-node routing overheadshould be a constant independent of the size of the system.More practically, the per-node overhead should be a slowlygrowing function of the system size, such as O(log N ). Forexample, this rules out standard distance-vector, which has aper-node communication cost of O(N ). For reactive proto-cols, which query for routes to destinations only as needed,capacity constraints suggest that queries should travel a dis-tance proportional to the distance between the nodes desiringto communicate; otherwise local communication will gener-ate global routing traffic, which won’t scale well.Few existing ad hoc routing protocols conform to the re-strictions described above. For example, DSDV [17] uses a1distance-vector algorithm that imposes O(N ) per-node com-munication cost, where N is the number of nodes in the net-work, while DSR [4] and AODV [18] flood queries globallyeven for local communication. As a consequence, we shouldexpect these protocols’overheadto exhaust node radio capac-ities relatively quickly as networks grow larger. In practice,the situation is not this simple. If the network topology doesnot change, these protocol’s overheads can be made arbitrar-ily small. Even if the topology changes, DSR and AODV havecaching and local re-query mechanisms that limit the cost offinding and repairing routes. Still, the overall scaling argu-ment suggests that these protocols might work badly in verylarge ad hoc networks. Section 5 shows that this is true.More scalable ad hoc routing protocols do exist. For ex-ample, the combination of geographic forwarding and theGLS location service [13] provides a routing system thatscales as O(log N ). However, both geographic forwardingand GLS require that nodes know their geographic locations,perhaps using the Global Positioning System (GPS). This de-pendence is likely to be impractical for many uses of ad hocnetworks.Landmark routing is a potentially scalable protocol thatdoes not depend on GPS. Instead of using geographic loca-tions as addresses, Landmark addresses nodes using their po-sitions in a dynamically maintained hierarchy. Landmark ad-dresses effectively encode an abbreviated route in the form ofa path down the hierarchy. These addresses allow packets tobe routed with very little per-node state, and thus little per-node routing overhead. Landmark limits the number of nodesin the network that any one node knows about to O(log N ).Thus the per-node routing overhead is O(log N ). However,since a node’s address may change when the network topol-ogy changes, the complete Landmark system includes a dis-tributed database that maps each node’s permanent ID to itscurrent address. Queries to this database require global com-munication; thus the complete Landmark system as