Density-Independent, Scalable Search in Ad Hoc Networks

Conference: PIMRC 2005 - 16th Annual IEEE International Symposium on Personal Indoor and Mobile Radio Communications
09/11/2005 - 09/14/2005 at Berlin, Germany

Proceedings: PIMRC 2005

Pages: 8Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Haas, Zygmunt J.; Barr, Rimon (Wireless Networks Laboratory, Cornell University, Ithaca, NY 14850, USA)

We analyze the asymptotic cost of discovering a route within a flat ad hoc network and we show that one can discover a route with cost that is proportional only to the area of the network and that is independent of the number of network nodes. Furthermore, we show that this is optimal and that bordercasting (a query propagation protocol where a node retransmits a query to a set of nodes at some hop-distance away) possesses this density-independence property. We present the design of bordercast and the associated maintenance protocols, and we evaluate their performance. In particular, we highlight that the aggregation of local information by boredercasting at each network node is a fundamental building block for the construction of scalable protocols in flat ad hoc networks.