Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking

Abstract

As devices with wireless networking become more pervasive, mobile ad hoc networks are becoming increasingly important, motivating the development of highly scalable ad hoc networking techniques. In this paper, we present the design and evaluation of a novel protocol for scalable routing in ad hoc networks as part of the Safari project. We develop a probabilistic, self-organizing network hierarchy formation protocol that recursively forms the nodes of the ad hoc network into an adaptive, proximity-based hierarchy of cells. We develop a hybrid routing protocol that uses this hierarchy and also develop an ondemand reactive routing protocol to scale to large numbers of nodes. The mapping of unique node identifiers to hierarchical addresses is done using a distributed hash table that leverages the hierarchical network structure. We evaluate this scalable routing protocol through analysis and simulations, showing individually as well as together the performance of the hierarchy formation protocol, the overhead of address mapping, and the performance of the routing protocol. As devices with wireless networking become more pervasive, mobile ad hoc networks are becoming increasingly important, motivating the development of highly scalable ad hoc networking techniques. In this paper, we present the design and evaluation of a novel protocol for scalable routing in ad hoc networks as part of the Safari project. We develop a probabilistic, self-organizing network hierarchy formation protocol that recursively forms the nodes of the ad hoc network into an adaptive, proximity-based hierarchy of cells. We develop a hybrid routing protocol that uses this hierarchy and also develop an on-demand reactive routing protocol to scale to large numbers of nodes. The mapping of unique node identifiers to hierarchical addresses is done using a distributed hash table that leverages the hierarchical network structure. We evaluate this scalable routing protocol through analysis and simulations, showing individually as well as together the performance of the hierarchy formation protocol, the overhead of address mapping, and the performance of the routing protocol.