Hierarchical routing over dynamic wireless networks

Dominique Tschopp, Suhas N. Diggavi, Matthias Grossglauser

TL;DR

This paper introduces a novel hierarchical routing algorithm for dynamic wireless networks that leverages the "doubling dimension" property of network graphs. This approach achieves low routing overhead and efficient routes, even in the face of constantly changing network topologies due to node mobility.

What Problem Does This Paper Address?

Designing efficient routing algorithms for wireless ad hoc networks is a significant challenge. These networks are inherently dynamic, with nodes frequently moving, which causes the network topology (how nodes are connected) to change over time. Maintaining up-to-date routing information in such dynamic environments incurs substantial control traffic overhead, consuming precious network resources like bandwidth and power. The authors aim to develop low-overhead routing schemes that can maintain efficient routes (routes that are not excessively longer than the shortest possible path) in these dynamic wireless networks. They specifically focus on the trade-off between control traffic overhead and route quality (stretch).

Methods

The core of the paper's approach lies in exploiting a geometric property of wireless network graphs called the "doubling dimension." A graph with a low doubling dimension means that any "large" ball of connections can be covered by a constant number of "small" balls. The authors demonstrate that many realistic wireless network models, including geometric random graphs and those based on signal-to-interference-plus-noise ratio (SINR), exhibit this doubling property.

They propose a hierarchical routing algorithm that uses this property to build a layered structure of "beacons." Nodes are organized into clusters at different levels, with beacons acting as representatives for these clusters. The algorithm uses a "beaconing phase" to establish these hierarchical routes and a "forwarding phase" to send data. The key idea is that by organizing nodes hierarchically based on their proximity, routing decisions can be made more efficiently, reducing the need for global network knowledge and thus lowering control traffic. They also introduce the concept of "smoothness" for sequences of network graphs, meaning that connectivity changes gradually over time, which is crucial for maintaining efficient routes in dynamic settings.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Doubling Dimension as a Network Property: The paper highlights that the "doubling dimension" is a powerful metric for characterizing the complexity of wireless network topologies, and it can be low even in networks with obstacles or non-uniform node distributions.
  • Hierarchical Routing for Dynamics: A hierarchical approach, leveraging the doubling dimension, is shown to be effective for managing dynamic network topologies and reducing routing overhead.
  • Low-Overhead, Low-Stretch Routes: The proposed algorithm aims to achieve both low control traffic and routes with a small stretch (close to the shortest path), a difficult combination in dynamic wireless networks.
  • Robustness to Obstacles: The algorithm's reliance on the doubling dimension, rather than specific geometric positions, makes it robust to network features like obstacles that can disrupt traditional geographic routing.
  • Smoothness of Topology Changes: The concept of "smoothness" in topology changes is introduced as a key requirement for maintaining efficient routes in dynamic environments.

Key Results

  • The paper develops a routing strategy based on a hierarchical set of beacons with scoped flooding, maintaining cluster membership in a lazy manner.
  • A worst-case analysis shows that the algorithm can maintain constant stretch routes with an average network-wide traffic overhead of $O(n \log^2 n)$ bits per mobility time step.
  • A load-balanced version of the algorithm requires $O(\log^3 n)$ bits per node per mobility time.
  • The paper proves that various wireless network models, including geometric random graphs and SINR-based connectivity, exhibit the doubling property.
  • It also demonstrates that sequences of connectivity graphs arising from uniform speed-limited mobility models are "smooth," meaning distances change gradually.
  • Theoretical bounds are provided for control traffic and route stretch, with simulations showing that practical performance is significantly better than worst-case bounds.

Limitations and Future Work

  • Worst-Case Bounds: The authors acknowledge that their theoretical bounds on control traffic and stretch are worst-case and may be conservative. Simulations suggest that practical performance is much better.
  • Practical Implementation: While the paper provides theoretical foundations, practical implementation details like handling collisions and parallelizing beaconing are mentioned as areas for future work.
  • Non-Doubling Networks: The paper focuses on doubling networks. It's noted that the algorithms and bounds would not apply to non-doubling networks, and their behavior in such cases is not analyzed.
  • More Sophisticated Models: The authors suggest that their techniques might offer insights for designing algorithms for more complex wireless network models.

Summary updated

Abstract

In dynamic networks the topology evolves and routes are maintained by frequent updates, consuming throughput available for data transmission. We ask whether there exist low-overhead schemes for these networks, that produce routes that are within a small constant factor (stretch) of the optimal route-length. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks. For a class of models for wireless network that fulfill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintain the routes over a changing topology. This scheme needs only node identities and integrates location service along with routing, therefore accounting for the complete overhead. We analyze the worst-case (conservative) overhead and route-quality (stretch) performance of this algorithm for the aforementioned class of models. Our algorithm allows constant stretch routing with a network wide control traffic overhead of O(n log2 n) bits per mobility time step (time-scale of topology change) translating to O(log2 n) overhead per node (with high probability for wireless networks with such mobility model). We can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. Numerics show that these bounds are quite conservative.
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