On Optimal Geographic Routing in Wireless Networks with Holes and Non-Uniform Traffic

Geographic forwarding has been widely studied as a routing strategy for large wireless networks, mainly due to the low complexity of the routing algorithm, scalability of the routing information with network size and fast convergence times of routes. On a planar network with no holes, it has been shown earlier that a uniform traffic demand of $Theta(1/sqrt{nlog{n}})$ is achievable. However, in a network with routing holes (regions on the plane which do not have active nodes), geographic routing schemes such as GPSR or GOAFR could cause the throughput capacity to significantly drop due to concentration of traffic on the face of the holes. Similarly, geographic schemes could fail to support non-uniform traffic patterns due to spatial congestion (traffic concentration) caused by greedy "straight-line" routing. In this paper, we first propose a randomized geographic routing scheme that can achieve a throughput capacity of $Theta(1/sqrt{n})$ (within a poly-logarithmic factor) even in networks with routing holes. Thus, we show that our scheme is throughput optimal (up to a poly-logarithmic factor) while preserving the inherent advantages of geographic routing. We also show that the routing delay incurred by our scheme is within a poly-logarithmic factor of the optimal throughput-delay trade-off curve. Next, we construct a geographic forwarding based routing scheme that can support wide variations in the traffic requirements (as much as $Theta(1)$ rates for some nodes, while supporting $Theta(1/sqrt{n})$ for others). We finally show that the above two schemes can be combined to support non-uniform traffic demands in networks with holes.