On Capacity Scaling in Arbitrary Wireless Networks

We consider the problem of characterizing per node throughput scaling in arbitrary extended wireless networks. Recently, Ozgur, Leveque, and Tse (2007) obtained a complete characterization of throughput scaling for random extended networks (i.e., nodes are placed in a square region uniformly at random) under a fast-fading channel model. They proposed a hierarchical cooperative communication scheme to establish this result. However, their results are strongly dependent on the ``regularity'' induced with high probability by the random node placement. As a main result of this paper, we propose a more general hierarchical cooperative communication scheme that works for arbitrarily placed nodes with a minimum-separation requirement. Under our scheme, we obtain exactly the same per node throughput scaling as in Ozgur et al., showing that much less regularity is necessary for successful hierarchical cooperation. Our result holds under both fast- and slow-fading channel model. For small path-loss exponents $alpha in (2,3]$, we show that our scheme is order optimal for all node placements with minimum-separation requirement. As a special case, we recover the results of Ozgur et al. for random networks and for both fast as well as slow fading. For extended networks with random node placement, the following threshold phenomenon exists: for $alpha leq 3$, the hierarchical cooperative scheme achieves the optimal throughput scaling; for $alpha > 3$, multi-hop communication achieves the optimal throughput scaling. We establish that for arbitrary node placement, due to the lack of ``regularity'', such a threshold phenomenon does not exist. In other words, there are node placements such that multi-hop communication is not order optimal for $alpha > 3$. We then present a family of schemes that smoothly ``interpolate'' between multi-hop and hierarchical cooperative communication, depending upon the ``level of regularity'' in the node placement. We establish optimality of these schemes under adversarial node placement for $alpha > 3$.