Advanced Wireless Networks - 4G Technologies

in Equation (19.85). The LEGO algorithm can be efficiently implemented using lo-

summarized as below.

Algorithm 1: LEGO

(1) Update the remote receiver weights for every link during downlink transmission:

w 1(p) = arg max γ1(p)

w1(p)

(2)Set the remote transmit weights to a scaled version of the conjugated receive weights,

g1(p) = w1(p) πl (p)/[w1H (p)Rεr εr w1(p)]

(3)For each link p, estimate the associated post-beamforming interference power y1( p) and relay this information back to the base station.

(4)Update the base receiver weights for every link during uplink transmission:

w 2( p) = arg max γ2( p).

w2( p)

(5)For each link p, estimate the associated post-beamforming interference power y2( p).

(6)Update the target SINR for each link, by optimizing the linearized model over each aggregate set m:

for q Q(m),

γ( p) = α[γˆ ( p) − γ ( p)] + γ ( p), for some 0 < α ≤ 1(α is initially set to 1).

(7)Update the downlink transmit powers π2(q):

π2(q) = γ (q)y1(q)/ T12(q, q)

(8)Update the uplink transmit powers π1(q) and relay them back to the remote units. π1(q) = γ (q)y2(q)/ T21(q, q).

(9)Set the base transmit weights to a scaled version of the conjugated receive weights,

g2( p) = w2( p) π2( p)/ w2H ( p)Rεr εr w2( p)

(10) Return to step 1.

References [54, 55] provide a numerical example of a four-cell wireless network as illustrated in Figure 19.22. Each 1 km radius cell contains two remote units (RU), each of which communicates to two base stations. The base stations have eight antennae and the RUs two antennae. There are eight independent 50 kHz channels and thus each RU has 16 transmit

790 NETWORK INFORMATION THEORY

modes [i.e. each Q(m) contains 16 links]. The performance of LEGO is compared with a standard power management algorithm, that seeks to transmit a constant power for each link from each base station, and a single antenna network, that uses frequency division multiplexing to isolate each RU into a separate channel. Background radiation is assumed to be thermal white noise at room temperature, with an added 10 dB noise figure. As can be seen from the figure, the performance improvement of the LEGO algorithm is significant.

Figure 19.22 (a) Cell network geometry; (b) LEGO performance: worst case capacity vs worst transmit power. (Reproduced by permission of IEEE [55].)

19.7 CAPACITY OF SENSOR NETWORKS WITH MANY-TO-ONE TRANSMISSIONS

In sensor networks the many-to-one throughput capacity is the per source data throughput, when all or many of the sources are transmitting to a single fixed receiver or sink [58–63]. Earlier in this chapter we have shown that the achievable per node throughput in a wireless network is θ W/(n log n) , where W is the transmission capacity and n is the total number of nodes in the network.

The result was based on the assumption that communications are one-to-one, and that sources and destinations are randomly chosen. It does not apply to scenarios where there are communication hot spots in the network. Since many-to-one communication causes the sink to become a point of traffic concentration, the throughput achievable per source node in this case is reduced. In this section we are only interested in the case where every source gets an equal (on average) amount of original data (not including relayed data) across to the sink. This is because otherwise throughput can be maximized by having only the sensors closest to the destination transmit. Equal share of throughput from every sensor is desired for applications like imaging where each sensor represents a certain region of the whole field and data from each part are equally important. When distributed data compression is used, this is again approximately the case. However, when conditional coding is used this may no longer be true, since the amount of processed data can vary from source to source. In order to achieve the above goal we use the following assumptions about the network architecture.

19.7.1 Network architecture

(1)The network is deployed in a field of circular shape. There are n nodes, sources (we will use nodes, sources and sensors interchangeably in subsequent discussions) deployed in a network. A sink/destination is located at the center of the network/circle. Each node is not only a source of data, but also a relay for some other sources to reach the sink.

(2)A network where the nodes are randomly placed following a uniform distribution will be referred to as a randomly deployed network or a random network. In such a network we have no direct control over the exact location of the nodes. A network where we can determine the exact locations of the nodes will be referred to a as an arbitrary network.

(3)Two network organizational architectures are considered: (a) a flat architecture where nodes communicate with the sink via possibly multi-hop routes by using peer nodes as relays; and (b) hierarchical architecture, where clusters are formed so that sources within a cluster send their data (via a single hop or multihop depending on the size of the cluster) to a designated node known as the clusterhead. The clusterhead can potentially perform data aggregation and processing and then forward data to the sink. In this study, we will assume that the clusterheads serve as simple relays and no data aggregation is performed. We will also assume that the communication between nodes and clusterheads and communication between clusterheads and the sink are on separate frequency channels so that the two layers do not interfere.

(4)Throughout the section we will assume that the sources transmit following a schedule that consists of time slots.

(5)To simplify the resulting expressions, we assume the field has an area of 1. Nodes share a common wireless channel using omnidirectional antennas. We assume nodes use a fixed transmission power and achieve a fixed transmission range. We adopt the commonly used interference model, as earlier in this chapter. Let Xi and X j be two

19.7.2 Capacity results

In this section we summarize capacity results for the network defined above. For formal proofs of the results the reader is referred to References [58–63].

19.7.2.1 Capacity in a flat network

(1)The maximum per node throughput in the network is upper bounded by W/n.

(2)λ = W/n can be achieved when every source can directly reach the sink.

(3)λ = W/n is not achievable if not every source can directly reach the destination and

> r.

(4)λ = W/n may be achieved in an arbitrary network when not every source can directly reach the destination and < r.

When the sink cannot directly receive from every source in the network, and assuming that the channel allocation does not take into account difference in traffic load, then λ = W/n is not achievable with high probability regardless of the value of . In this case we will use the upper bound on throughput by deriving the maximum number of simultaneous transmissions.

Denote by Ar the area of a circle of radius r, i.e. Ar = πr2. Let random variable Vr denote the number of nodes within an area of size Ar and assume a total area of 1. We then have [58–63]:

(5) In a randomly deployed network with n nodes,

Pr n Ar − √αn n ≤ Vr ≤ n Ar + √αn n → 1 as n → ∞

where the sequence {αn } is such that limn→∞ αn/n = ε, ε being positive but arbitrarily small.

(6)If a network has randomly deployed sources and the transmission range r is such that not all sources can directly reach the sink, then with high probability the throughput upper bound λ = W/n is not achievable.

(7)A randomly deployed network using multihop transmission for many-to-one communication can achieve throughput

λ ≥ W πr2 − √ε / n 4πr2 + 4πr + π 2 + √ε

with high probability, when no knowledge of the traffic load is assumed and ε is as given in (1).

In the following we will use a concept of virtual sources. As an example consider a simple network consisting of three sources and a sink, shown in Figure 19.24(a). The distance between adjacent nodes is r. Regardless of the value of , when one source transmits, it interferes with all other sources in this network. Therefore only one source can transmit at a time. The number of interfering neighbors for any of the sources is two, which is the highest degree of the graph that represents the interference relationship in this network. Thus a schedule of length 3 allows all sources to transmit once during the schedule. The

794 NETWORK INFORMATION THEORY

Figure 19.24 (a) Chain network (b) virtual sources.

load on the source closest to the sink, source 3, is 3λ, since it carries the traffic of all three sources. The achievable throughput is then calculated as 3λ = W/3, thus λ = W/9.

The way the schedule was calculated previously assigned the same share of the resources (time) to all the sources. Since we used the source with the highest need of resource (the one carrying the most traffic) to calculate the amount of resource needed, every other source is wasting resource. In our example we are giving every source the possibility of making three transmissions. Source 3 does indeed need all three transmissions, but source 2 only needs two and source 1 only needs one, hence a total of six transmissions. Now consider a similar network, only this time we have three sources that can reach the sink, shown in Figure 19.24(b). We create a schedule where each one of the sources gets to transmit once and once only. However this time not all sources generate data. Using labels shown in Figure 19.24(b), source 1 generates a packet and transmits it to source 2a. Source 2a relays the packet to source 3a, which then relays it to the sink. Then source 2b generates a packet and transmits it to source 3b, which relays it to the sink. Finally source 3c generates and transmits a packet to the destination. We can view each raw of sources in this network as an equivalent of a single source in the previous example, i.e. 2a and 2b combined are equivalent to 2 in Figure 19.24(a); 3a, 3b and 3c combined are equivalent to 3, in terms of interference and traffic load. We will define sources 2a, 2b and 3a, 3c as virtual sources in the sense that they each represent one actual source in the network but they are co-located in one physical source. Adopting this concept, in this network the highest number of interfering neighbors is five (with a total of six virtual sources all in one interference area) and therefore there exists a schedule of length 6 that enables every virtual source to transmit once. Since the traffic load is the same for all virtual sources, the resources will be shared equally and no source will be wasting its share. In this case we get λ = W/6. Note that this is the largest λ that could be obtained for the example in Figure 19.24(a). This concept allows us to define a ‘traffic load-aware’ schedule in the following way.

(1)For each source node, create one virtual source for every source node whose traffic goes through this node, including itself.

(2)Counting all the virtual sources we can determine the number of interfering neighbors (virtual sources) k . The new maximum degree of the interference graph is then k − 1.

(3)A schedule of length s ≤ k exists which is equally shared among virtual sources.

(4)The achievable throughput per node is simply the share obtained by any virtual source in the network, i.e. λ = W/s ≥ W/ k.

The concept of virtual source is used in References [58–63] to prove the following theorems:

(8) A randomly deployed network using multi-hop transmission for many-to-one com-

edge of the traffic load is assumed. lh+ and n+h are the upper bounds on the number of virtual sources per actual source and the number of actual sources respectively, that are h hops away from the sink with high probability.

(9)A randomly deployed network using multihop transmission for many-to-one communication can achieve a throughput arbitrarily close to W/{n(2 − πr2)}, when knowledge of the traffic load is assumed and = 0.

In a hierarchical network with H clusters (heads) we assume that each cluster head creates a cluster containing the sources closest to it. Within each cluster the communication is either via a single hop or via multihop, while the communication from clusterheads to the sink is assumed to be done via a single hop on a different channel. We assume that cluster heads cannot transmit and receive simultaneously. In order to avoid boundary problems, we will assume there is at least a distance of 2(2r + ) between any two clusterheads. We will also assume that each cluster covers an area of same size, as though not necessarily the same shape. Following these two assumptions and using result (5), we have with high probability that the number of nodes in each cluster is within (αn n) of n/H , where αn is such that limn→∞ αn /n = ε. Therefore the clusters essentially form a Voronoi tessellation of the field, where every cluster (or Voronoi cell) contains a circle of radius 2r + . Consequently sources located near the boundary between two clusters will not have a higher number of interfering neighbors (in terms of virtual sources), due to low traffic load, than the ones closer to the clusterheads. Thus previous results are directly applicable and we do not have to be concerned with the boundary.

The question of interest is whether there exists an appropriate number of clusters H that would allow the network to achieve λ = W/n with high probability using clustering, when clusterheads have the same transmission capacity W as the sources. That W/n remains to be the upper bound is again obvious considering the fact that the sink cannot receive from more than one node (at rate W ), and that there are n sources in the network. In References [58–63] the following results are proven:

(10)In a network using clustering, where cluster heads have the same transmission capacity W as the sources, there exists an appropriate number of clusters H and an appropriate range of transmission r that would allow the network to achieve λ = W/n with high probability as n → ∞. The range of transmission r must satisfy

796NETWORK INFORMATION THEORY

(11)In a network using clustering, where cluster heads have transmission capacity W , there exists an appropriate number of clusters H and an appropriate range of transmission r, as n → ∞ , that allows the network to achieve λ = W /n with

high probability. W /n is also the upper bound on throughput in this scenario. The

REFERENCES

[1]A. Ephremides and B. Hajek, Information theory and communication networks: an unconsummated union, IEEE Trans. Inform. Theory, vol. 44, no. 6, 1998, pp. 2416– 2434.

[2]S. Glisic, Adaptive WCDMA, Theory and Practice. Wiley: Chichester 2003.

[3]A. Baiocchi et al., Effects of user mobility on the capacity of a CDMA cellular network, Eur. Trans. Telecommun., vol. 7, no. 4, 1996, pp. 305–314.

[4]A.M. Viterbi and A.J. Viterbi, Erlang capacity of a power controlled CDMA system, IEEE J. Select. Areas Commun., vol. 11, no. 6, 1993, pp. 892–899.

[5]M.A. Landolsi, V.V. Veeravalli and N. Jain, New results on the reverse link capacity of CDMA cellular networks, Proc. IEEE VTC’96, 1996, pp. 1462–1466.

[6]J.C. Liberti Jr and T.S. Rappaport, Analytical results for capacity improvements in CDMA, IEEE Trans. Vehicular Technol., vol. 43, no. 3, 1994, pp. 680–690.

[7]A.F. Naguib, A. Paulraj and T. Kailath, Capacity improvement with base-station antenna arrays in cellular CDMA, IEEE Trans. Vehicular Technol., vol. 43, no. 3, 1994, pp. 691–698.

[8]L. Tomba, Outage probability in CDMA cellular systems with discontinuous transmission, Proc. IEEE ISSSTA’96, 1996, pp. 481–485.

[9]S. H¨am¨al¨ainen, H. Holma and A. Toskala, Capacity evaluation of a cellular CDMA uplink with multiuser detection, Proc. IEEE ISSSTA’96, 1996, pp. 339–343.

[10]H. Holma, A. Toskala and T. Ojanper¨a, Cellular coverage analysis of wideband MUDCDMA system, Proc. IEEE PIMRC’97, 1997, pp. 549–553.

[11]J. Blanz, A. Klein, M. Naβhan and A. Steil, Capacity of a cellular mobile radio system applying joint detection, COST 231 TD94 002, 1994.

[12]J. Blanz, A. Klein, M. Naβhan and A. Steil, Performance of a cellular hybrid C/TDMA mobile radio system applying Joint detection and coherent receiver antenna diversity, IEEE J. Select. Areas Commun., vol. 12, no. 4, 1994, pp. 568–579.

[13]S. Manji and N.B. Mandayam, Outage probability for a zero forcing multiuser detector with random signature sequences, Proc. IEEE VTC’98, 1998, pp. 174–178.

[14]W. Huang and V.K. Bhargava, Performance evaluation of a DS/CDMA cellular system with voice and data services, Proc. IEEE PIMRC’96, 1996, pp. 588–592.

[15]V.H. MacDonald, The cellular concept, Bell Syst. Tech. J., vol., 58, 1979, pp. 15–41.

[16]G.K. Chan, Effects of sectorization on the spectrum efficiency of cellular radio systems,

IEEE Trans. Vehicular Technol., vol. 41, 1992, 217–225.

[17]S.G. Glisic and P. Pirinen, Co-channel interference in digital cellular TDMA networks, in Encyclopedia of Telecommunications, J. Proakis (ed.). Wiley: Chichester, 2003.

REFERENCES 797

[18]S.C. Swales, M. A. Beach, D.J. Edwards and J.P. McGeehan, The performance enhancement of multibeam adaptive base station antennas for cellular land mobile radio systems, IEEE Trans. Vehicular Technol., vol. 39, 1990, pp. 56–67.

[19]J.H. Winters, Smart antennas for wireless systems, IEEE Person. Commun., vol. 5, 1998, pp. 23–27.

[20]P. Petrus, R.B. Ertel and J.H. Reed, Capacity enhancement using adaptive arrays in an AMPS system, IEEE Trans. Vehicular Technol., vol. 47, 1998, pp. 717–727.

[21]P.E. Mogensen, P.L. Espensen, P. Zetterberg, K.I. Pedersen and F. Frederiksen, Performance of adaptive antennas in FH-GSM using conventional beamforming, Wireless Person. Commun., vol. 14, 2000, pp. 255-274.

[22]E. Kudoh and T. Matsumoto, Effect of transmitter power control imperfections on capacity in DS/CDMA cellular mobile radios, Proc. IEEE ICC’92, 1992, pp. 237– 242.

[23]A.J. Paulraj and C.B. Papadias, Space–time processing for wireless communications,

IEEE Signal Process. Mag., vol. 14, 1997, pp. 49–83.

[24]L.C. Godara, Applications of antenna arrays to mobile communications, part I: performance improvement, feasibility, and system considerations, Proc. IEEE, vol. 85, 1997, pp. 1031–1060.

[25]J. Litva and T. K.-Y. Lo, Digital Beamforming in Wireless Communications. Artech House: Boston, MA, 1996.

[26]J.H. Winters, Optimum combining in digital mobile radio with cochannel interference,

IEEE Trans. Vehicular Technol., vol. VT-33, 1984, pp. 144–155.

[27]P. Zetterberg, A comparison of two systems for downlink communication with base station antenna arrays, IEEE Trans. Vehicular Technol., vol. 48, 1999, pp. 1356– 1370.

[28]P. Zetterberg and B. Ottersten, The spectrum efficiency of a base station antenna array system for spatially selective transmission, IEEE Trans. Vehicular Technol., vol. 44, 1995, pp. 651–660.

[29]W.S. Au, R.D. Murch and C.T. Lea, Comparison between the spectral efficiency of SDMA systems and sectorized systems, Wireless Personal Commun., vol. 16, 2001, pp. 15–67.

[30]L.-C. Wang, K. Chawla and L.J. Greenstein, Performance studies of narrow-beam trisector cellular systems, Int. J. Wireless Inform. Networks, vol. 5, 1998, pp. 89–102.

[31]S. Glisic et al. Effective capacity of advanced wireless cellular networks (invited paper), in PIMRC2005, Berlin, 11–14 September 2005.

[32]P.Gupta and P.R. Kumar, The capacity of wireless networks, IEEE Trans. Inform. Theory, vol. 46, no. 2, 2000 , pp. 388–404.

[33]L.-L. Xie and P.R. Kumar, A network information theory for wireless communication: scaling laws and optimal operation, IEEE Trans. Inform. Theory, vol. 50, no. 5, 2004 , pp. 748–767.

[34]A. Okabe, B. Boots and K. Sugihara, Spatial Tessellations Concepts and Applications of Voronoi Diagrams. Wiley: New York, 1992.

[35]J.A. Bondy and U. Murthy, Graph Theory with Applications. Elsevier: New York, 1976.

[36]P. Gupta and P.R. Kumar, Toward an information theory of large networks: an achievable rate region, IEEE Trans. Inform. Theory, vol. 49, 2003, pp. 1877–1894.