Density-Independent, Scalable Search in Ad Hoc Networks

Konferenz: PIMRC 2005 - 16th Annual IEEE International Symposium on Personal Indoor and Mobile Radio Communications
11.09.2005 - 14.09.2005 in Berlin, Germany

Tagungsband: PIMRC 2005

Seiten: 8Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

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.