Nebulizer Mesh Ultrasonic

Arxiv:Cs/0702154V1 [Cs.It] 27 Feb 2007

On the Capacity of the Single Source Multiple Relay Single

Abstract

In this paper, we derive the information theoretic capacity of a special class of mesh networks. A mesh network is a heterogeneous wireless network in which the transmission among power limited nodes is assisted by powerful relays, which use the same wireless medium.

We investigate the mesh network when there is one source, one destination, and multiple relays, which we call the single source multiple relay single destination (SSMRSD) mesh network. We derive the asymptotic capacity of the SSMRSD mesh network when the relay powers grow to infinity. Our approach is as follows. We first look at an upper bound on the information theoretic capacity of these networks in a Gaussian setting. We then show that this bound is achievable asymptotically using the compress-and-forward strategy for the multiple relay channel. We also perform numerical computations for the case when the relays have finite powers. We observe that even when the relay power is only a few times larger than the source power, the compress-and-forward rate gets close to the capacity. The results indicate the value of cooperation in wireless mesh networks. The capacity characterization quantifies how the relays can cooperate, using the compress-and-forward strategy, to either conserve node energy or to increase transmission rate.

Introduction

Wireless networks have been finding more applications and capturing much research attention in recent years. The advantage of mobile clients makes ad-hoc wireless networking an attractive solution for home and enterprise users. However, with an almost unlimited number of ways of interacting and cooperating, analysis of these multi-terminal networks is difficult. To date, the capacity of even the simple three-node channel is not known, except for special cases, for example, the multiple access channel , the degraded relay channel , the degraded broadcast channel . However, this did not hinder research in channels with more nodes.

Recently, mesh networks have been drawing interest from both the research arena and the in- dustry. Mesh networks ( and the references therein) are peer-to-peer multihop wireless networks with powerful relays. One practical setup of the mesh network is depicted in Fig. 1. It consists of mesh routers (stationary and line powered) and mesh clients (mobile and battery powered).

mesh networks. The standard defines a network of wireless access points (mesh routers) commu- nicating wirelessly with each other and serving mesh clients in their proximity. In other words, mesh routers act as relays. The access points forward data packets via multi-hopping. They do not need to connect to the wired backbone.

In this paper, we study the information theoretic capacity of a class of mesh networks, which multiple relay single destination (SSMRSD) mesh network, which we model by the multiple relay channel . The multiple relay channel captures the scenario where the transmission from the source to the destination is aided by several relay nodes, which themselves have no

1

Figure 1: A mesh network. data to send. As such, the SSMRSD mesh network is a multiple relay channel where the relays can transmit at large power. One can treat the SSMRSD mesh network as an excerpt of the general mesh network where we consider just one of the source-destination pairs. We note that the capacity of the general multiple relay channel has not been found, except for special cases, e.g., the degraded multiple relay channel. The capacity of the SSMRSD mesh network, which is not a degraded multiple relay channel [8, Theorem 2.3], has not been found.

We investigate rates achievable by the compress-and-forward coding strategy on the SSMRSD mesh network. The coding technique was first introduced by Cover and El Gamal for the single relay channel and later extended to the multiple relay channel by Kramer et al. . In the compress-and-forward strategy, the source transmits to both the relays and the destination. The relays do not decode the data, but simply quantize, compress, and send them to the destination.

We categorize the compress-and-forward strategy as a cooperative coding strategy. To understand why, we contrast it with a non-cooperative coding strategy, the multihop strategy. In the multihop strategy, when one node transmits, only the next hop listens. Though other nodes over-hear the transmission, they regard it as noise. On the other hand, in the cooperative strategy, instead of ignoring the useful transmission, nodes that over-hear the transmissions of other nodes (though the information might not be intended for them) help to forward the data, fully or partially, to the destination.

We show that the compress-and-forward strategy approaches the capacity of the SSMRSD mesh network as the relay powers grow. Our approach is as follows. First, we study an upper bound on the capacity of the SSMRSD mesh network, which is derived from a max-flow min-cut argument.

We then study achievable rates of the compress-and-forward coding strategy on the multiple relay channel. We show that when the power constraints at the relays are relaxed (which is the case in the SSMRSD mesh network), the compress-and-forward technique approaches the capacity upper bound asymptotically. Using the single relay channel as an example, we numerically investigate the performance of the compress-and-forward strategy as the relay power grows.

Our Contributions In This Paper Are As Follows:

1. We derive an achievable rate expression for the compress-and-forward strategy on the Gaus- sian multiple relay channel. 2. We derive the capacity asymptotically of the SSMRSD Gaussian mesh network as the relay powers grow to infinity.

3. We show, using numerical computations, how the compress-and-forward rate approaches the capacity as the relay power grows. More specifically, we show that the rate achievable by the compress-and-forward strategy is close to the capacity even when the relay power is only a few times higher than the source power.

2

4. We study and compare coding strategies on the SSMRSD mesh network. The comparison of different coding strategies motivates code designers to design practical coding schemes based on certain types of cooperation, to drive the transmission rate toward the theoretical limits.

Knowing the network capacity as a function of transmission powers, and understanding how nodes should cooperate help network designers in network deployment. Most research on the capacity or transmission rate of mesh networks, e.g., Jun et al. , Kodialam and Nandagopal , Roy et al. , is based on non-cooperative multihop coding strategies. Data are forwarded hop-by-hop from the mesh clients to the gateway through relays and simultaneous transmissions use orthogonal channels, e.g., using time division multiple access (TDMA) or frequency division multiple access (FDMA), to avoid interference. In this paper, we give examples to show that the rate achievable by the TDMA multihop strategy is lower than that of the compress-and-forward strategy. The FDMA multihop strategy can be analyzed similarly.

The rest of the paper is organized as follows. Section 2 introduces the channel model. In Section 3, we establish a useful theorem that we will need in later sections. In Section 4, we investigate an upper bound on the capacity of the SSMRSD mesh network. This is followed by an investigation of the rates achievable by the compress-and-forward strategy, in Section 5. By allowing the power constraint of the relays to increase, we show, in Section 6, that the rate achiev- able by the compress-and-forward strategy approaches the capacity asymptotically. In Section 7, we investigate the behavior of the compress-and-forward rate when the relay power is finite. In addition, we compare the performance of the compress-and-forward and the decode-and-forward strategies for different relay positions. We conclude this paper in Section 8.

Channel Model

Figure 2: The multiple relay channel. Fig. 2 depicts the multiple relay channel. The multiple relay channel can be completely de-

(1)

on Y2 × Y3 × · · · × YT , for each (x1, x2, . . . , xT −1) ∈X1 × X2 × · · · × XT −1. In this paper, we only consider memoryless channels. Node 1 is the source node and node T is the destination node. Nodes 2 to T −1 are purely relay nodes. Messages are generated at node 1 and are to be transferred to node T . We follow the definitions of capacity, achievable rate (RW ) used by Kramer et al. [9, Section III.A].

In the Gaussian multiple relay channel, node j, j = 2, . . . , T , receives

(2)

where Xi, input to the channel from node i, is a random variable with power constraint E[X2 i ] ≤Pi. Pi is the average transmission power constraint on node i. Yj is the received signal at node j. Zj, the receiver noise at node j, is an independent zero mean Gaussian random variable with variance Nj. λij is the channel gain from node i to node j. λij depends on the antenna gains, the carrier frequency of the transmission, and the distance between the transmitter and the receiver.

We study achievable rates for the T -node Gaussian multiple relay channel. More specifically, we investigate the performance of the compress-and-forward strategy when the relay powers grow large. This models the SSMRSD mesh network, in which the relays are line powered and can transmit at high power. We define R ≜{2, 3, . . ., T −1} as the set of all relay nodes. We use the notation X{1,...,m} ≜(X1, . . . , Xm).

A Cut-Set Bound And Independent Gaussian Inputs

In this section, we establish a useful theorem which we will need in the sequel.

We Consider

a T -node multiple relay channel where nodes 1, . . . , T −1 send X1, . . . , XT −1 into the channel respectively. The channel inputs are subject to power constraints E[Xi] ≤Pi for i = 1, . . . , T −1. Nodes 2, . . . , T receive the following signals from the channel.

(3)

where Zj ∼N(0, Nj), j = 2, 3, . . . , T , are independent Gaussian noise. Since the values of the channel gain do not matter in the analyses in this section, we have set them to be 1. We consider the cut-set bound on the rate at which we can transmit information from the source to the relays and the destination, assuming that the relays and the destination can cooperate. The following theorem establishes that the optimal input distribution to maximize this bound is such that the the source and the relays send independent Gaussian inputs.

Theorem 1 Consider a T -node Gaussian multiple relay channel. A sufficient condition on the

(4)

is that the inputs are Gaussian and X1 is independent of XR. It follows that independent Gaussian inputs X1, . . . , XT −1 also achieve (4). Proof:[Proof of Theorem 1] First, we consider the case T = 3, which means there is one relay.

(5)

is achieved when X1 and X2 are independent Gaussian inputs. From [9, Proposition 2], we know the optimal input distribution is Gaussian. We let

(6)

where W and X2 are independent Gaussian random variables, such that E[W 2] = PW and P1 = α2P2 + PW .

= 1

2 log(2πe)2(PW N2 + PW N3 + N2N3).



.

(9B)

Setting α = 0 maximizes the mutual information. This completes the proof for T = 3. Now, we extend this result to T = 4 or the two-relay channel. The generalization from the two- relay channel to the multiple-relay channel is straight forward. We need to show that a sufficient condition on the input distribution function to achieve

4

is that X1 and (X2, X3) are independent Gaussian inputs. From [9, Proposition 2], (10) is achieved by Gaussian inputs X1, X2, and X3. Now, we combine the relay inputs to form XR = X2 + X3. The destination receives Y4 = X1 + XR + N4. From the single relay case T = 3, we know that choosing X1 to be independent of XR is optimal. Certainly, choosing independent X1, X2, and X3 maximizes the mutual information term. This proves the case of T = 4.

Now, we demonstrate that (10) can indeed be achieved with any correlation between X2 and X3, as long as X1 is independent of (X2, X3). We let X2 = βX3 + W, where X1, X3 and W are independent Gaussian inputs. Here, E[W 2] = PW and P2 = β2P3 + PW .

H(Y2, Y3, Y4|X1, X2, X3) = 1

2 log(2πe)3N2N3N4.

= 1

2 log(2πe)3 [P1(N2N3 + N2N4 + N3N4) + N2N3N4] .



.

(13)

We note that this is independent of β. This means that (10) can be achieved with any correlation between X2 and X3. We can easily generalize this result to any T > 4 and hence obtain Theorem 1.

The Multi-Terminal Network

Figure 3: A cut in the multi-terminal network. Consider a T -node multi-terminal network where node i transmits Xi and node j receives Yj. The channel is characterized by the channel transition probability p(y1, . . . , yT |x1, . . . , xT ). If the rate from node i to node j, Rij, is achievable, then the following must be satisfied [17, Theorem

(14)

for some joint probability function p(x1, . . . , xT ) for all T ⊂{1, . . . , T } where i ∈T and j /∈T . T c is the complement of T in {1, . . . , T }. We can interpret this theorem as follows. The achievable rate from node i to node j must be smaller than the rate of all possible cuts separating nodes i and j. Fig. 3 depicts a possible

5

cut. We define the cut rate for the cut separating T and T c as the right side of (14). It is the maximum achievable rate from nodes in T to nodes in T c when all nodes on the same side of the cut are allowed to cooperate.

The Ssmrsd Mesh Network

Consider a T -node Gaussian SSMRSD mesh network where • Node 1 is the source node with power constraint E[X2

1] ≤P1. The Source Only Transmits

and does not receive. • Node T is the destination node, which only receives and does not transmit. • Nodes 2 to T −1 are relays with large power constraints, E[X2

I ] ≤Pi And Pi >> P1,

∀i = 2, . . . , T −1. The relays can transmit and receive at the same time. We note that any cut rate with 1 ∈T and T ∈T c is an upper bound of the rate from the source to the destination. Since the relays can transmit with large power, if we include any relay node in set T , the cut rate (defined as (14)) is large. Hence the minimum cut rate occurs when the cut separates T = {1} and T c = {2, . . . , T }. So the upper bound of the capacity of the SSMRSD

(15)

for some joint probability function p(x1, . . . , xT −1). From Theorem 1, independent Gaussian inputs maximize this upper bound in the Gaussian channel.

The Discrete Memoryless Multiple Relay Channel

In this section, we investigate achievable rates of the multiple relay channel using the compress- and-forward strategy. Setting Ut = Xt, ∀t ∈R in the compress-and-forward strategy for the multiple relay channel introduced by Kramer et al. [9, Theorem 3], we can achieve rates up to

#

p∗(yR, yT |x1, xR).

For All S ⊆R, All Partitions {Bm}M

m=1 of S, and all r(m) ∈{2, . . . , T } \ Bm. We define Sc as

The Complement Of S In R And Bc

m as the compliment of Bm in R. U is the part which is to be decoded by all relays. Setting Ut = Xt means each relay decodes all other relays’ codewords. We note that in the compress-and-forward strategy, all channel inputs X1, . . . , XT −1 are independent.

The Gaussian Multiple Relay Channel

We consider the Gaussian multiple relay channel. The inputs to the channel from node i, Xi, is constrained by E[Xi] ≤Pi. We let the input distribution to the channel be independent Gaussian.

6

Using the compress-and-forward strategy with Uj = Xj, the received signal of node r(m) can be

Λir(M)Xi

+ Zr(m).

(19B)

The term inside the summation on the RHS of (17) can be evaluated as



.

(20)

We note that all Xi are independent, as seen from (18). Using the compress-and-forward strategy, node j’s quantized received signal is

(21)

where Wj ∼N(0, Qj) are independent quantization noise.

The Lhs Of (17) Is

I( ˜YS; YS|XR, ˜YSc, YT ) = H( ˜YS|XR, ˜YSc, YT ) −H( ˜YS|YS, XR, ˜YSc, YT )

Pλ1S(1)Λ1S(D)P1

... ... ...

Pλ1S(1)Λ1S(D)P1

. . .

(24)

s(i) are the ordered elements in S and D = |S|.



.



.

√Λ12Λ1T P1

... ... ...

√Λ12Λ1T P1

. . .

Λ1T P1 + Nt

.

(29)

Hence we have the following theorem for the T -node Gaussian multiple relay channel. Theorem 2 Consider a memoryless T -node Gaussian multiple relay channel. Using independent Gaussian input Xi, i = 1, . . . , T −1, with power constraints E[X2

(31)

for all S ⊆R, {s(1)...s(D)} = S, all partitions {Bm}M m=1 of S, and all r(m) ∈{2, . . . , T } \ Bm. R is the set of all relays.

We note that the achievability of (30) makes use of the Markov lemma [18, Lemma 4.1], which requires strong typicality. Though strong typicality does not extend to continuous random variables, one can generalize the Markov lemma for Gaussian inputs and thus show that (30) is achievable .

The Capacity Of The Gaussian Ssmrsd Mesh Network

Recalling that the Gaussian SSMRSD mesh network is a multiple relay channel with powerful relays, we investigate how (31) can be satisfied for some small Qi in the mesh network. To see the effect of these powerful nodes, we will look at the scenario when the relay power constraints grow without bound, i.e., Pi →∞, ∀i ∈R. While this may not be practical, it allows us to characterize the capacity and to study how the rates scale with the relay powers. We assume that all the channel gains λij, the transmit power P1, and the receiver noise Ni are finite. Under these

Conditions:

1. Λ(D) is finite when P1, Ni, λ1i are finite and Qi are approaching zero, ∀i ∈R. 2. (λ1jP1 + Nj), ∀j ∈R ∪{T } are finite. 3. The RHS of (31) approaches zero as λijPi →∞, ∀i ∈R, ∀j ∈R ∪{T }.

(32)

while (31) can still be satisfied for all S ⊆R, all partitions {Bm}M

M=1 Of S, And All R(M) ∈

{2, . . . , T } \ Bm. When Qi →0, the quantized received signals approach the received signals, that

(33)

for all ∀i ∈R. The achievable rate of the compress-and-forward strategy becomes

(34)

We see that (34) has the same form as the capacity upper bound (15) of the SSMRSD mesh network. The upper bound (15) is maximized is over all possible input distributions but the achievable rate (34) is achievable with independent Gaussian inputs. However, Theorem 1 states that the cut-set upper bound is maximized by using independent Gaussian inputs. Hence, the compress-and-forward strategy approaches a cut-set upper bound of the SSMRSD mesh network asymptotically. This is summarized in the following theorem.

Theorem 3 The achievable rate of the compress-and-forward strategy approaches the capacity of the Gaussian SSMRSD mesh network asymptotically as the relay powers grow. The capacity is

(35)

Similar to Theorem 2, the achievability of (35) requires generalization of the Markov lemma to Gaussian input distributions .

The Effect Of Relay Position And Power

In the previous section, we have shown that in the multiple relay channel when the relay powers get large, the achievable rate of the compress-and-forward strategy approaches the capacity. While the assumption that the relay powers grow to infinity is not valid in any practical scenario, we investigate the case of finite relay powers in this section. We study, using the single relay channel as an example, how close the achievable rate of the compress-and-forward strategy gets to the capacity when we increase the relay power. In addition, we investigate how the relay position affects the result.

7.1

Comparing Different Coding Strategies and the Cut-Set Bound We recall that the cut-set bound for the single relay channel is

Where L(X) = 1

2 log(1 + x). In the numerical analyses in this section, we use this cut-set bound as a basis of comparison. We compare achievable rates of different coding strategies normalized to this bound.

Related Journal Articles & DOI Links

Selected peer-reviewed publications relevant to 12 Lead ECG Acquisition. Click the DOI to access the full paper (may require institutional access).

Why Choose Us?

Bangalore guidance for robotics, Spectre and autonomous systems projects.