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.

Papers

  1. D. Tschopp, S. N. Diggavi, M. Grossglauser, and J. Widmer, European Patent Number EP1883185: Method and apparatus for beacon management for routing on virtual coordinates, 2008.
    Note: European Patent Number EP1883185
  2. 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 near-optimal routes. We show that random geometric graphs and variants have a nice property that they are doubling metric spaces, with high probability. This enables us to design hierarchical routing schemes with provable performance that account for the user mobility and scale well with network size.
  3. Download: gc.pdf 
    Abstract:
    This paper studies the scaling capacity of asymptotically large wireless networks. It shows that even restricted one-dimensional mobility allows the total capacity of the wireless network scales linearly with the number of nodes. This implies that per-node capacity scales as a constant, demonstrating that even restricted mobility can be used to provide non-diminishing throughput for large-scale wireless networks. This is demonstrated by utilizing the multi-user diversity which is instantiated through node-mobility.
  4. Download:  
    Abstract:
    Hierarchical cooperation, introduced by Ozgur, Leveque and Tse showed that linear scaling is possible in wireless network capacity, asymptotically in network size. In this paper, we investigate the impact of absence of channel state information on the performance of hierarchical cooperation. If the product of coherence time and coherence bandwidth of the wireless channel is on the order of the number of nodes in the network, we show that non-coherent hierarchical cooperation achieves the same order rate as the coherent version. If the product is smaller than the number of nodes, we show that non-coherent hierarchical cooperation can still yield sizable gains over multihop communication, but may not achieve the same order rate as the coherent version.
  5. Abstract:
    We ask whether there exist low- overhead schemes for dynamic wireless networks, that produce routes that are within a small constant factor (stretch) of the op- timal route-length. For a class of models for wireless network that ful- fill 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 topol- ogy with provable performance guarantees. This scheme needs only node identities and integrates location service along with routing, therefore accounting for the complete overhead.
  6. D. Tschopp, S. N. Diggavi, and M. Grossglauser, "Routing in mobile wireless networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 38.
  7. Abstract:
    We develop wireless routing based on an embedding of the connectivity graph to overcome shortcomings of geographic routing and topology-based routing.
  8. Note: invited paper
    Download: tdgwita2007.pdf 
  9. S. N. Diggavi, M. Grossglauser, and D. N. C. Tse, "Even one-dimensional mobility increases capacity of wireless adhoc networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Lausanne, 2002, p. 352.

-