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. It has been shown earlier that a throughput-capacity ( a uniform rate over all source-destination pairs) of (formula shown here) is achievable in random planar networks, and the capacity is achieved by straight-line routes [8]. In reality, both the network model and traffic demands are likely to be highly nonuniform. 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.