Hierarchical Routing Over Dynamic Wireless Networks
A major challenge in the design of wireless ad hoc networks is the need for distributed routing algorithms that consume a minimal amount of network resources. This is particularly important in dynamic networks, where the topology can change over time, and therefore routing tables must be updated frequently. Such updates incur control traffic, which consumes bandwidth and power. It is natural to ask whether there exist low-overhead schemes for dynamic wireless networks that could produce and maintain efficient routes. In this paper the authors consider dynamically changing connectivity graphs that arise in wireless networks. The performance metric for the algorithms is the average signaling overhead incurred over a long time-scale when the topology changes continuously.