Optimal Geographic Routing for Wireless Networks with Near-Arbitrary Holes and Traffic

We consider the problem of throughput-optimal routing over large-scale wireless ad-hoc networks. Gupta and Kumar (2000) showed that a throughput capacity (a uniform rate over all source-destination pairs) of thetas( 1/radicn log n ) is achievable in random planar networks, and the capacity is achieved by straight-line routes. In reality, both the network model and the traffic demands are likely to be highly non-uniform. In this paper, we first propose a randomized forwarding strategy based on geographic routing that achieves near-optimal throughput over random planar networks with an arbitrary number of routing holes (regions devoid of nodes) of varying sizes. Next, we study a random planar network with arbitrary source-destination pairs with arbitrary traffic demands. For such networks, we demonstrate a randomized local load-balancing algorithm that supports any traffic load that is within a poly-logarithmic factor of the throughput region. Our algorithms are based on geographic routing and hence inherit their advantageous properties of low- complexity, robustness and stability.