1 4

(19.42)

(19.43)

(19.44)

and substituting Equation (19.40) in Equation (19.66) gives nT L 16WTH 2 (19.45)

Substituting Equation (19.63) in Equation (19.67) yields the result (r 1). For the physical model suppose X i is transmitting to X j(i) over the mth subchannel at power level Pi at some time, and let denote the set of all simultaneous transmitters over the mth subchannel at that time. The initial constraint introduced by (a6) can be represented as S = I

(19.46)

By also including the signal power of X i in the denominator, the signal-to-interference requirement for X j(i) can be written as S = I

+1

+1 Pi N + ( ) /2 4

(since |X k X j(i) | 2/ ).

Summing over all transmitter receiver pairs, Pi +1 i |X i X j(i) | N + ( ) /2 4

2 ( /2)

+1

r (h, b) 2 2

The rest of the proof proceeds along lines similar to the protocol model, invoking the convexity of r instead of r 2 . For the consideration of the special case where Pmax /Pmin < , we start with Equation (19.46). From it, it follows that if X i is transmitting to X j at the same time that X k is transmitting to X , both over the same subchannel, then

where := ( Pmin /Pmax ) 1. Thus the same upper bound as for the protocol model carries over with de ned as above. 19.2.4 Arbitrary networks: lower bound on transport capacity There is a placement of nodes and an assignment of traf c patterns such that the network can achieve W n/ (1 + 2 ) n + 8 b-m/s under the protocol model, W n/ n + 8 16 2 2 +

6 2 2

1/

under the physical model, both whenever n is a multiple of 4. To prove it, consider the protocol model and de ne r := 1/ (1 + 2 ) n/4 + 2 Recall that the domain is a disk of unit area, i.e. of radius 1/ in the plane. With the center of the disk located at the origin, place transmitters at locations [ j(1 + 2 )r r, k(1 + 2 )r ] and [ j(1 + 2 )r, k(1 + 2 )r r ] where | j + k| is even. Also place receivers at [ j(1 + 2 )r r, k(1 + 2 )r ] and [ j(1 + 2 )r, k(1 + 2 )r r ] where | j + k| is odd. Each transmitter can transmit to its nearest receiver, which is at a distance r away, without interference from any other transmitter receiver pair. It can be veri ed that there are at

least n/2 transmitter receiver pairs, all located within the domain. This is based on the fact that for a tessellation of the plane by squares of side s, all squares intersecting a disk of radius R 2s are entirely contained within a larger concentric disk of radius R. The number of such squares is greater than (R 2s)2 /s 2 . This proves the above statement for s = (1 + 2 )r and R = 1/ . Restricting attention to just these pairs, there are a total of n/2 simultaneous transmissions, each of range r , and each at W b/s. This achieves the transport capacity indicated. For the physical model, a calculation of the SIR shows that it is lower-bounded at all receivers by (1 + 2 ) 16 2 2 +

6 2 2

Choosing to make this lower bound equal to yields the result. In the protocol model, there is a placement of nodes and an assignment of traf c patterns such that the network can achieve 2W/ b-m/s for n 2 1 4W (1 + ) b-m/s, for n 8 1 W n (1 + 2 ) n + 8 b-m/s, for n = 2, 3, 4, , 19, 20, 21 and 1 4 n/4 W (1 + 2 ) 4 n/4 + 8 b-m/s, for all n With at least two nodes, clearly 2W/ b-m/s can be achieved by placing two nodes at diametrically opposite locations. This veri es the formula for the bound for n 8. With at least eight nodes, four transmitters can be placed at the opposite ends of perpendicular diameters, and each can transmit toward its receiver located at a distance 1/ (2 + 2 ) towards the center of the domain. This yields 4W/ (1 + ) b-m/s, verifying the formula up to n = 21. 19.2.5 Random networks: lower bound on throughput capacity In this section we show that one can spatially and temporally schedule transmissions in a random graph so that, when each randomly located node has a randomly chosen destination, each source destination pair can indeed be guaranteed a virtual channel of capacity 1 cW (1 + )2 n log n b/s with probability approaching 1 as n , for an appropriate constant c > 0. We will show how to route traf c ef ciently through the random graph so that no node is overloaded. 19.2.5.1 Spatial tessellation In the following a Voronoi tessellation of the surface S 2 of the sphere is used. For a set of p points {a1 , a2 , , a p } on S 2 the Voronoi cell V (ai ) is the set of all points which are closer to ai than to any of the other a j s, i.e. [34], V (ai ) := {x S 2 : |x ai | = min |x a j |}