On the scalability of rendezvous-based location services for geographic wireless ad hoc routing

Geographic routing protocols allow stateless routing by taking advantage of the location information of mobile nodes and thus are highly scalable. A central challenge in geographic routing protocols is the design of scalable distributed location services that track mobile node locations. A number of location services have been proposed, but little is known about the relative performance of these location services. In this paper, we perform a detailed performance comparison of three rendezvous-based location services that cover a range of design choices: a quorum-based protocol (XYLS) which disseminates each nodes location to O(root N) nodes, a hierarchical protocol (GLS) which disseminates each node's location to 0(logN) nodes, and a geographic hashing-based protocol (GHLS) which disseminates each node's location to 0(l) nodes. We present a quantitative model of protocol overheads for predicting the performance tradeoffs of the protocols for static networks. We then analyze the performance impact of mobility on these location services. Finally, we compare the performance of routing protocols equipped with the three location services with two topology-based routing protocols, AODV and DSR, for a wide range of network sizes. Our study demonstrates that when practical mobile ad hoc network (MANET) sizes are considered, the constants matter more than the asymptotic costs of location service protocols. In particular, while GLS scales better asymptotically, GHLS transmits fewer control packets and delivers more data packets than GLS in MANETs of sizes considered practical today and in the near future. Additionally, in contrast to the complex GLS design, the simplicity of GHLS provides significant resilience to performance degradation from mobility. Finally, although XYLS has a comparable packet delivery ratio to GHLS, it achieves this ratio with a higher overhead. (c) 2007 Elsevier B.V. All rights reserved.