Hierarchical Routing over Dynamic Wireless Networks

Dynamic networks are those where the topology changes over time and therefore efficient routes need to be maintained by frequent updates. Such updates could be costly in terms of consuming throughput available for data transmission, which is a precious resource in wireless networks. In this paper, we ask the question whether there exist low-overhead schemes for dynamic wireless networks, that could 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 mobile 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 maintains the routes over a changing topology. This scheme needs only node identities and therefore 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 wireless network connectivity and mobility models. In particular for these models, we show that our algorithm allows constant stretch routing with a network wide control traffic overhead of $O(n\log^2 n)$ bits per mobility time step (time-scale of topology change) translating to $O(\log^2 n)$ overhead per node (with high probability for wireless networks with such mobility model). Additionally, we can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. We also demonstrate through numerics that these worst-case bounds are quite conservative in terms of the constants derived theoretically.