Routing in dynamic ad hoc wireless networks
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.