Hierarchical Routing over Dynamic Wireless Networks

Dominique Tschopp, Suhas N. Diggavi, Matthias Grossglauser

Abstract: Wireless network topologies change over time and maintaining routes requires frequent updates. Updates are costly in terms of consuming throughput available for data transmission, which is precious in wireless networks. In this paper, we ask whether there exist low-overhead schemes that produce low-stretch routes. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks.

Introduction

In mobile ad-hoc networks (MANETs), the constant movement of nodes creates a volatile topology where links frequently break and reform. Traditional routing protocols often struggle in these environments because every topological change triggers network-wide updates, consuming significant bandwidth for control traffic. This paper proposes a hierarchical routing framework that leverages the inherent geometry of wireless connectivity to maintain "low-stretch" routes—paths that are close to the shortest possible—while keeping signaling overhead to a minimum.

The Doubling Property

The core innovation of this work is the application of the doubling dimension to dynamic wireless graphs. A metric space is considered "doubling" if any ball of radius $2R$ can be covered by a constant number of balls of radius $R$. The authors demonstrate that most realistic wireless topologies, even those with obstacles, possess this property. This geometric constraint allows the complexity of routing to be reduced from a global problem to a local one.

Illustration of the doubling property: a ball of radius 2R can be covered by a constant number of balls of radius R.

Hierarchical Protocol Mechanism

The proposed scheme utilizes a hierarchy of "beacons" where level-$i$ beacons cover a radius of $2^i$. This structure enables "scoped flooding," ensuring that updates only propagate as far as necessary to maintain route integrity.

To further reduce overhead, the algorithm employs lazy updates. By formalizing the "smoothness" of mobility—the observation that physical nodes move continuously rather than teleporting—the authors show that shortest path distances change predictably. Updates to the beacon hierarchy are only triggered when a node has moved significantly relative to its current level. Additionally, the protocol incorporates a scheduling mechanism to manage interference and analyze traffic bounds.

Spatial and temporal scheduling for node transmissions to manage interference and control traffic overhead.

Evaluation and Key Results

The framework was evaluated using Geometric Random Graphs (GRG), SINR models, and Uniform Speed-Limited (USL) mobility models. Key findings include:

  • Guaranteed Performance: The algorithm ensures that routes are at most a constant factor longer than the absolute shortest path.
  • Scalable Overhead: The theoretical per-node overhead scales polylogarithmically ($O(\log^3 n)$) with network size. In simulations of 10,000 nodes, the actual overhead was significantly lower than the conservative theoretical bounds.
  • Empirical Efficiency: In 1,000-node simulations, the "stretch" (the ratio of the chosen route to the shortest path) remained consistently below 1.5, outperforming theoretical worst-case predictions.

Conclusion

By exploiting the doubling dimension of wireless networks, this hierarchical approach provides a scalable solution for routing in dynamic environments. While the current analysis assumes certain MAC layer abstractions and specific geometric properties, the results offer a robust theoretical and practical foundation for efficient communication in mobile networks.

Summary updated

Abstract

Wireless network topologies change over time and maintaining routes requires frequent updates. Updates are costly in terms of consuming throughput available for data transmission, which is precious in wireless networks. In this paper, we ask whether there exist low-overhead schemes that produce low-stretch routes. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks.
BibTeX
@inproceedings{tschopp2008hierarchical,
  author = {Dominique Tschopp and Suhas N. Diggavi and Matthias Grossglauser},
  title = {{Hierarchical Routing over Dynamic Wireless Networks}},
  booktitle = {Random Struct. Algorithms},
  year = {2008},
  url = {https://openreview.net/forum?id=EcEnDyMw3njO},
}
Figure