Routing in dynamic ad hoc wireless networks

Routing packets is a central function of multi-hop wireless networks. Traditionally, there have been two paradigms for routing, either based on the geographical coordinates of the nodes (geographic routing), or based on the connectivity graph (topology-based routing). The former implicitly assumes that geometry determines connectivity, whereas the latter does not exploit this inherent geometry of wireless networks, and assumes a general graph instead. We explored ideas that attempt to bridge these two paradigms. We do so by investigating routing techniques based on metric embeddings of the connectivity graph. If this graph is closely related to the underlying geometry of the nodes, then it is possible to embed the graph in a low-dimensional normed space. This keeps the overhead of the routing protocol low. We specifically explored embeddings of dynamic networks induced by channel fading and mobility. This motivated the novel problem of stable embeddings, where the additional goal is to maintain an embedding over time, such that the evolution of the embedding faithfully captures the evolution of the underlying graph itself. This is crucial to limit the control overhead of the routing protocol, and to ensure that our approach is scalable. This work also resulted in filing two patents.

We have continued to develop this approach more formally and have made connections to routing and graph embedding theory. The doubling number of a metric space is the number of balls of radius r/2 needed to cover a ball of radius r. For example a Euclidean space has a low doubling number. A metric space having a low (constant independent of the cardinality of the metric space) doubling number is called “doubling. A graph induces a metric space by considering the shortest path distance between nodes as the metric distance. Dense wireless ad hoc networks tend to produce random graphs that on an average have the geometric property that make them “close to a doubling metric space. For graphs with this property, we have provable bounds on the overhead and quality of routing even for dynamic networks. We model the dynamics of the graph topology through a constrained walk on the set of doubling metric spaces. To the best of our knowledge, this is the first formal investigation into provable bounds for dynamic networks.

We have continued the formal investigation, by examining wireless networks defined by variants of a geometric random graph (including walls, holes etc), which capture some of the underlying geometric properties of the connectivity graph in wireless networks. In particular, we examined dynamic random networks the topology evolves and routes are maintained by frequent updates, consuming throughput available for data transmission. We asked 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. 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. This is done by making a connection between wireless networks defined above to dynamic doubling metric spaces studied earlier by us. This connection allows us to 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 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). We can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. Through some numerics we saw that these bounds are quite conservative.