Advanced Wireless Networks - 4G Technologies

760 NETWORK INFORMATION THEORY

f = (g) if g = O( f ); f = (g) if f = O(g) as well as g = O( f ). Thus, all O(·) results are upper bounds, all (·) results me lower bounds, and all (·) results are sharp order estimates for the transport capacity. For n nodes located in an area of A square meters, it is shown in Section 19.2 that the transport capacity is of order O[√(An)] under a noninformation theoretic protocol model. If A itself grows like n, i.e. A = (n), then the scaling law is O[√(An)] = O(n), which coincides with the information-theoretic scaling law here. In fact, A must grow at least this rate since nodes are separated by a minimum distance ρmin > 0, i.e. A = (n), and so the O(n) result here is slightly stronger than the O[√(An)] result in the previous section.

where c2(γ , δ, ρmin) is as in Equation (19.44).

19.3.5 Multihop and feasible lower bounds under high attenuation

The O(n) upper bound on transport capacity is tight for regular planar networks in media with γ > 0 or δ > 3, and it is achieved by multihop. The ‘multihop strategy’ is defined as the following. Let denote the set of all paths from source s to destination d , where by such a path π we mean a sequence (s = j0, j1, . . . , . . . , jz = d ) with jq =jr for q =r. The total traffic rate R to be provided to the source destination pair (s , d ) is split over the paths in in such a way that if traffic rate λπ ≥ 0 is to be carried over path π , then

π P λπ = R . On each path π , packets are relayed from node to next node. On each such hop, each packet is fully decoded, treating all interference as noise. Thus, only point- to-point coding is used, and no network coding or multiuser estimation is employed. Such a strategy is of great interest and it is currently the object of much protocol development activity.

The following result implies that, when γ > 0 or δ > 3, the sharp order of the transport capacity for a regular planar network is (n), and that it can be attained by multihop.

(r5) In a regular planar network with either γ > 0 or δ > 1, and individual power constraint Pind

and S(x) denotes the Shannon function S(x) := log(1 + x) /2.

This order of distance weighted sum of rates is achievable by multihop. Multihop is order-optimal in a random scenario over a regular planar network in media with γ > 0 or δ > 3, providing some theoretical justification for its use in situations where traffic is diffused over the network.

Consider a regular planar network with either γ > 0 or δ > 1, and individual power constraint Pind. The n source–destination pairs are randomly chosen as follows: every source s is chosen as the node nearest to a randomly (uniformly i.i.d.) chosen point in the domain,

and similarly for every destination d . Then lim Prob [ R = c/√(n log n) is feasible for

n→∞

every {1, 2, . . . , n}] = 1 for some c > 0. Consequently, a distance weighted sum of rates CT = [n/√(log n)] is supported with probability approaching one as η → ∞. This is within a factor l/√log n of the transport capacity (n) possible when δ > 3.

(r6) A vector of rates (R1, R2, . . . , Rm ) can be supported by multihop in a planar network in media with γ > 0 or δ > 1, if the traffic can be load balanced such that no node is overloaded and no hop is too long.

This is a fairly straightforward result saying nothing about order optimality, and is provided only in support of the above theme that multihop is an appropriate architecture for balanceable scenarios.

(r7) A set of rates (R1, R2, . . . Rm ) for a planar network can be supported by multihop if no hop is longer than a distance ρ¯ , and for every 1 ≤ i ≤ n, the traffic to be relayed by node i

19.3.6 The low-attenuation regime

In this scenario no absorption, i.e. γ = 0, and small path loss exponent are assumed. In this case coherent relaying with interference subtraction (CRIS) is considered an interesting strategy for information transmission in the following scenarios. For a source–destination pair (s, d), the nodes are divided into groups, with the first group containing only the source, and the last group containing only the destination d. Call the higher numbered groups ‘downstream’ groups, although they need not actually be closer to the destination. Nodes

by 0, 1, . . . , M, with 0 as the source, M as the destination, and the other M − 1 nodes serving as M − 1 stages of relaying.

(r11) Any rate R satisfying the following inequality is achievable from 0 to M:

For the network setting in (r11), Theorem 3.1 in Gupta and Kumar [36] shows that a rate R0 is achievable if there exist some {R1, R2, . . . , RM−1} such that

From the above, recursively for m = M − 2, M − 1, . . . , 0, it is easy to prove that

For m = 0, this inequality is exactly (r11), showing a higher achievable rate. The right-hand side (RHS) in (r11) can be maximized over the choice of order of the M − 1 intermediate nodes. The relaying can also be done by groups, and the next result addresses this. As above, maximization can be done over the assignment of nodes to the groups.

Consider again the Gaussian multiple-relay channel using coherent multistage relaying with interference subtraction. Consider any M + 1 groups of nodes sequentially denoted by N0, N1, . . . NM with N0 = {s} as the source, NM = {d} as the destination, and the other M − 1 groups as M − 1 stages of relay. Let ni be the number of nodes in group Ni , i {0, 1, . . . , M}. Let the power constraint for each node in group Ni be Pi /ni ≥ 0.

(r12) Any rate R satisfying the following inequality is achievable from s to d:

N j}, i, j {0, 1, . . . , M}.

As pointed out earlier, more on the results (r1)–(r12) can be found in Xie and Kumar [33].

764 NETWORK INFORMATION THEORY

19.4 COOPERATIVE TRANSMISSION IN WIRELESS MULTIHOP AD HOC NETWORKS

The technique discussed in this section allows us to transmit reliably to far destinations that the individual nodes are not able to reach without rapidly consuming their own battery resources, even when using multihop links discussed so far. The results are of interest in both ad hoc and sensor networks. The key idea is to have the nodes simply echo the source’s (leader) transmission operating as active scatterers while using adaptive receivers that acquire the equivalent network signatures corresponding to the echoed symbols. The active nodes in the network operate either as regenerative or nonregenerative relays. The intuition is that each of the waveforms will be enhanced by the accumulation of power due to the aggregate transmission of all the nodes while, if kept properly under control, the random errors or the receiver noise that propagate together with the useful signals will cause limited deterioration in the performance. The avalanche of signals triggered by the network leaders forms the so-called opportunistic large array (OLA).

In contrast to Sections 19.2 and 19.3, we are interested in this section in a method that utilizes the network as a distributed modem, where one or few sources are effectively transmitting data and all the other users are operating as repeaters. A fresh look into the concept of repeaters as a form of cooperative transmission came recently from References [37–40].

We will assume that, in a network of N nodes transmitting over a shared medium, each node is part of a multiple stage relay of a single source transmitting toward a remote receiver whose position is unknown to all the nodes. If no node in the network is powerful enough to communicate reliably with the remote receiver, the problem is referred to as the reach-back problem. Coordination among nodes in a large network is an extremely difficult task. In a cooperative transmission mechanism for which cooperation is obtained in a distributed fashion the source (leader) transmits a pulse with complex envelope pm (t) out of an M-ary set of waveforms. The resulting signal at the ith receiver is ri (t) = si,m (t) + ni (t) where si,m (t) is the network-generated signature of the mth symbol. If N nodes echo exactly the same symbol,

N

si,m (t) = Ai,n (t) pm t − τi,n (t) , m = 0, . . . , M − 1

n=1

where ni (t) is the ith receiver AWGN with variance N0, τi,n (t) is the delay of the link between the ith and the nth node, including the asynchronism of the beginning of transmission for each node n, and Ai,n (t) is the product of a complex fading coefficient ωi,n (t), the transmit power Pt and the channel average gain, e.g. (1 + di,n )−αi,n (log–normal fading), where di,n is the distance, and αi,n the decay constant between the ith and nth nodes.

The following assumptions are used:

(a1) Ai,n (t) and τi,n (t) are constant over multiple symbol durations Ts ; the nodes are quasi-stationary for a time much greater than Ts .

(a2) The delays are τi,1 < τi,2 ≤ · · · ≤ τi,N , where the minimum delay τi,1 corresponds to the leader. To avoid ISI, the upper bound for the effective symbol rate is Rs = 1/ Ts ≤ 1/ τ , where τ is the maximum delay spread of si,m (t) for all i. The

766 NETWORK INFORMATION THEORY

The received OLA response is

For every possible path in the network, there is a contribution to the summation in Equation (19.55a) that has an amplitude equal to the product of all the path link gains traveled so far and a delay equal to the sum of all the path delays. Theoretically, the number of reflections N → ∞ because the signals and their amplified versions keep cycling in the network and adding up. If properly controlled, the contributions will keep adding up and then opportunistically serve the purpose of enhancing the signal. Hence, the key for the nonregenerative design is to control the noise that accompanies the useful signal. In both regenerative and nonregenerative cases, the received signal can be rewritten as the following convolution:

where gi (t) is the network impulse response, which is analogous to that of a multipath channel. Based on Equation (19.46), the idea is to let the nodes operate as regenerative and nonregenerative repeaters and avoid any complex coordination procedure to forward their signals at the network layer and share the bandwidth at the MAC layer. In addition, no channel state information is used. The information flow is carried forward using receivers that are capable of tracking the unknown network response gi (t) or, directly, the signature

waveforms i,m ( ) i ( )* m ( ). We should expect that the OLA behaves as a frequency- s t = g t p t

selective channel. Nodes’ mobility causes changes of the response gi (t) over time. If most of the network is stationary and N is large, the inertia of the system will be such that mobile nodes will cause small changes in gi (t).

Since the transmission channel is bandlimited with passband bandwidth W , the signature waveform pm (t) will have to be bandlimited and, therefore, uniquely expressible through its samples taken at the Nyquist rate 1/ Tc, where Tc = 1/ W . In general, pm (t) corresponds to a finite number of samples Np and is approximately time limited with duration Tp ≈ Np / W . Introducing the vectors pm , gi and ri such that

{pm }k = pm (kTc), k = 0, . . . Np − 1

{gi }k = ∫ sinc(π W τ )gi (kTc + li TC − τ )dτ, k = 0, . . . Ni − 1

{ri }k = ri (kTc + li Tc)k = 0, . . . , Ni + Np − 2 {ni }k = ni (kTc + li Tc), k = 0, . . . , Ni + Np − 2

where Ni is the number of samples needed to represent gi (t), we have

19.4.1 Transmission strategy and error propagation

The transmission of the OLA is led by a predetermined source node in the network. All the other nodes form multiple stages of relays to either flood the network with the information from the source, or just to pass the information to a remote receiver. The intermediate nodes in OLA have a choice of whether to relay or not, depending on the performance at that node. In the regenerative scheme, the OLA nodes has the choice of retransmitting its detected symbol or staying silent. Only nodes that are connected actively reply, where connectivity is defined as follows.

Definition 1

The ith regenerative node is connected if, based on its estimates of all possible signatures Gi pm and receiver noise variance, the pairwise symbol error probability of the ith receiver

not considering error propagation) is below a fixed upper-bound ε , i.e. max Pr{m → μ} ≤

m

ε, μ =m, m = 0, . . . , M − 1.

In the Ns samples contained in each symbol period, the time instant selected for the

detection and subsequent echo is the first sample ¯ i ≤ s at which the node is connected.

N N

If there is no such sample, the node will never echo the signal (but it may obviously detect the information at his own risk.)

In the nonregenerative scheme, every node that achieves the SNR constraint amplifies the signal coming from the other nodes as well as their receiver noise. Hence, the noise ni has a rather complex structure since it includes the noise that comes from every node that has transmitted previously and all its subsequent amplifications along with the signal. Since the geographical area in an ad hoc or sensor network is limited, the delay spread of each node response will also be limited, as far as the signal-to-noise contribution is concerned. Considerations on the SNR can be deduced by considering the inherent recursive structure of the signal composition. Details can found in Scaglione and Hong [40].

Definition 2

The ith nonregenerative node is said to be connected if the signal to noise ratio at the node

is above a fixed threshold ¯.

ξi ξi > ξ

19.4.2 OLA flooding algorithm

In this section, we compare numerically OLA with the more traditional ways of flooding the network described in Chapter 13. The flooding algorithm in Royer and Toh [41] is commonly indicated as one of the simplest ways of distributing information in the network or of searching for a path to the desired destination to initialize table-driven protocols. Some interesting alternatives are the probabilistic scheme [42] and the scalable broadcast algorithm [43]. Most of these methods require the MAC and physical layer to provide virtual transmission pipes (obtained typically with contention) that connect each pair of nodes, which imitates wired networks. The approach is legitimate but obviously inefficient. In fact, in solving the network broadcast problem, it is natural to utilize and integrate in the design the fact that wireless devices are physically broadcasting. This is precisely what happens in the OLA, where, contrary to the networking approaches, the transmission protocol and