Network-Coded Relaying in Multiuser Multicast D2D Network

Abstract

D2D communication trades short-range communication for achieving high communication rate and short communication latency. Relay aided D2D communication can further tackle the problem of intermediate obstacles blocking the communication. In this work, multidevice multicast communication via a layer of parallel relay nodes is considered. Two relaying strategies, respectively, called the conventional relaying (CR) and network-coded relaying (NCR), are proposed. The throughput of these two schemes is analytically derived and evaluated through numerical study. Theoretically, NCR shows advantage over CR in twofold: one is higher throughput and the other is requiring less relay nodes and, hence, consuming less aggregate power. Numerical studies verify the analysis and show that the throughput performance gap between the two schemes increases significantly, actually exponentially with the number of devices.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Mingjun Dai 1,2,3 and Shengli Zhang 1,2,3 and Hui Wang 1,2,3 and Bin Chen 1,2,3 and Xiaohui Lin 1,2,3 and Hongwei Liu 1,2,3 and Li Zhang 1,2,3

Academic Editor:Lingyang Song

1, Shenzhen Key Lab of Advanced Communication and Information Processing, The College of Information Engineering, Shenzhen University, Shenzhen 518060, China
2, The State Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China
3, Shenzhen Key Laboratory of Media Security, Shenzhen University, Shenzhen 518060, China

Received 25 June 2014; Revised 22 July 2014; Accepted 22 July 2014; 12 August 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The main idea of D2D communication is to use short-range communication to trade for high rate communication, short delivery latency, and low aggregate consumption power [1-3]. Sometimes, due to the mobility of devices (devices move out of the communication coverage) or due to the fact that intermediate obstacles are blocking the communication, the communication link may be down intermittently [4]. These facts render relay-aided D2D communication necessary.

For relay-aided communication networks [5, 6], there are mainly two categories of strategies adopted by intermediate relay, including physical-layer relaying and network-coded relaying. For simple topology, for example, the point-to-point D2D communication via intermediate relays [7], capacity is given by the physical-layer technique in certain scenarios [8-10]. However, for complex topology, physical-layer technique tends to be unwieldy, while network coding (NC) [11, 12] shows significant advantages. Typical topology examples include interference network [13], multicast multihop network [14], intracell uplink relay network [15], and multiple unicasts networks [16] including three-node Alice-and-Bob relay network, two unicasts X-topology, cross topology, and wheel topology [17-25].

The full-duplex relay assumption in the above investigations is not practical [26]. In practice, if "cheap" relay is adopted, namely, half-duplex relay [27], which cannot transmit and receive simultaneously, the advantage of NC shown in the above investigations may be lost due to the orthogonal transmission nature of the multiple transmitters.

In this paper, we investigate a more general and practical model by considering the scenario where multiple devices exchange information via a layer of intermediate relays, namely, relay-aided D2D multicasting communication. For this model, we propose two relaying protocols based on the physical-layer and NC technique, respectively. Details of each technique are illustrated below.

Physical-Layer Technique. Firstly, for the special case where there is a single relay, the communication stage when all the devices transmit simultaneously can be viewed as multiple access channel (MAC) [28]. After this MAC stage, the relay broadcasts superimposed signals originating from the devices, and the corresponding channel can be viewed as broadcast channel (BC). In the BC stage, power allocation among all the information streams originating from different devices may degrade the system performance. In addition, due to heavy burden on the single relay, multiple cheap relays cooperately share the burden become a preference. One natural solution is that a lot of parallel relays are deployed between the devices, with each relay serving a single device, respectively, a device, a relay that serves it, and the other destination devices form a multicast single relay network. We call this strategy conventional multicast relaying (CMCR). The most desirable feature of this scheme is the simple operation at each relay. However, since each relay only decodes one device's information while treating the other devices' signals as interference, the performance of CMCR is interference-limited [29].

NC Technique . After the MAC stage, each relay firstly applies NC operation on some information flows originating from different devices and then multicasts the resultant information flow to all the devices. Each device can employ the idea of side information-aided decoding [30]. More specifically, each device performs decoding utilizing the message originating from itself. We call this strategy network-coded multicast relaying (NCMCR). The most desirable feature of NCMCR is that the interference can be reduced to some extent, since more devices' signals are decoded at each relay and hence less devices' signals are treated as interference. Besides, this does not involve power allocation among the information streams at each relay node, which also embodies NC's advantage over the physical relaying technique.

2. System Model

Refer to Figure 1. Consider M devices, denoted as _Ui for i={1,2,...,M}[triangle, =]M , exchanging information over a layer of N parallel relays, denoted as _Ri for i={1,2,...,N}[triangle, =]N . Define device terminal set U[triangle, =]{_U1 ,_U2 ,...,_UM } and relay node set R[triangle, =]{_R1 ,_R2 ,...,_RN } . Device _Ui multicasts information _mi to the other devices U/{_Ui } , i∈M . The devices are assumed to be so far away that the wireless link between them can be neglected. We assume that the communication between any pair of devices experiences two hops, that is, through certain relay nodes. Each node in the network is assumed to have one single antenna and operates in half-duplex mode. Node i∈U∪R is subject to power constraint _Pi . For simplicity, we consider additive white Gaussian noise (AWGN) at the receiver.

Figure 1: The general model.

[figure omitted; refer to PDF]

The communication between any pair of devices is performed in two time slots. During the first time slot, the devices simultaneously distribute their data while the relays listen. During the second time slot, the relays forward the messages to the devices.

Let _Xi [m] , _Yi [m] , and _wi [m] be, respectively, the transmitted symbol from node i , the received symbol, and the thermal noise at node i , at time m , respectively, i∈U∪R . The first hop's input-output relationship is represented by the following formula: [figure omitted; refer to PDF] which is subject to [figure omitted; refer to PDF] For simplicity, we assume that _Pi =P and _wi [m]~CN(0,^σ2 ) for all i∈U∪R . Define signal-to-noise ratio (SNR) Γ[triangle, =]P/^σ2 . The second hop's input-output relationship depends on the selected transmission scheme and is hence detailed in the following sections. Define _Rmi and _{Rmi ,mj} as the data rate of information flow originating from source _Ui and the data rate of information flows originating from sources _Ui and _Uj , respectively, i,j∈U , i...0;j .

Remark 1.

Throughout this paper, we assume that matched-filter receiver is used; hence, the achievable rate in each hop can be denoted by its capacity, and we let C(x)[triangle, =]_log...2 (1+x) .

3. Proposed Transmission Protocols

For easy understanding, we first consider the special case where there are three devices in Section 3.1. We then generalize the above results to an arbitrary number of devices together with mathematical analysis, that is, to M>3 , in Section 3.2.

3.1. Proposed Schemes for Three Devices

We describe the conventional method, the proposed method, and the refined proposed method, respectively.

3.1.1. Conventional Multicast Relaying (CMCR)

Refer to Figure 2. Relay _Ri adopts decode-and-forward (DF) strategy to relay device _Ui 's signal to the other devices, i∈{1,2,3}[triangle, =]_U3 . In the following, we derive the achievable rate of each device. Note that there are totally two stages of transmission and the achievable rate is the minimum of these two stages.

Figure 2: Conventional relaying.

[figure omitted; refer to PDF]

In the first stage, since relay _Ri only decodes the message originating from device _Ui , the signals originating from other devices' are treated as interference, i∈_U3 . In this case, the achievable rate region is [figure omitted; refer to PDF] which is simplified to [figure omitted; refer to PDF]

In the second stage, device _Ui intends to decode the messages from relays _Rj 's for j∈_U3 /{i} . This stage can be viewed as a two-user MAC by treating the signal from relay _Ri as interference. In this case, the achievable rate region is [figure omitted; refer to PDF] From (5), we obtain that the achievable rate region of the message rate originating from device i in the second stage is [figure omitted; refer to PDF]

Combining (4) and (6), we obtain that the achievable rate region of each device by CMCR is [figure omitted; refer to PDF]

3.1.2. Network-Coded Multicast Relaying (NCMCR)

Refer to Figure 3. Device _Ui selects relays _Rj for all j∈_U3 \{i} as the intermediate relays to forward its message to the other devices. Relay _Rj performs the following procedures. Firstly, it decodes the messages from devices _Ui for i∈_U3 \{j} . Afterwards, it performs exclusive OR (XOR) operation on the decoded information bits. Finally, it encodes the resultant information bits into new codeword and sends the resultant codeword out. We derive the achieved rate region in the following.

Figure 3: Network-coded relaying.

[figure omitted; refer to PDF]

In the first stage, relay _Ri needs to decode the signals from devices _Uj 's for j∈_U3 \{i} . This stage can be viewed as a two-user MAC. The achievable rate region is [figure omitted; refer to PDF] From (9), we obtain the achievable rate region of device _Ui in the first stage as [figure omitted; refer to PDF]

In the second stage, since device _Ui intends to decode the messages from relays _Rj 's for j∈_U3 \{i} , the channel can also be viewed as a two-user MAC. The achievable rate region at decoder _Ui is [figure omitted; refer to PDF] Note that [figure omitted; refer to PDF] From (11) and (12), we obtain that the achievable rate region of device _Ui in the second stage is [figure omitted; refer to PDF]

Combining (10) and (13), we obtain that the achievable rate region of device _Ui by NCMCR is [figure omitted; refer to PDF]

3.1.3. Refined NCMCR

Combining (8) and (14), we can obtain [figure omitted; refer to PDF] which shows the advantage of NCMCR over CMCR. However, for more than 3 devices, the number of relays needed by intuitively applying NCMCR should be ^CM2 , while CMCR requires only M relays.

In the following, we propose a method based on NCMCR to reduce the number of relays required to be even less than the number of devices. Without loss of generality, we first illustrate the case for M=3 . We remove relay _R1 and keep the operations performed on the other relay nodes the same as those described in Section 3.1.2 (refer to Figure 4). Obviously, the decoding at device _U1 can be made the same as before. Now, let us consider the decoding operation at devices _U2 and _U3 . Without loss of generality, we consider node _U2 only. It intends to decode _m1 and _m3 . Since _m2 is available to _U2 and hence can be viewed as side information [31], node _U2 first performs XOR operation on _m2 with _m1 [ecedil]5;_m2 which is forwarded by relay _R2 , obtaining _m1 . Afterwards, _U2 performs XOR operation again on _m1 and _m1 [ecedil]5;_m3 which is forwarded by relay _R3 , obtaining _m3 . We name this protocol as refined network-coded multicast relaying (RNCMCR). In the following, we derive the achievable rate region of RNCMCR.

Figure 4: Two relays.

[figure omitted; refer to PDF]

In the first stage, consider relay _R2 . It needs to decode the message from devices _U1 and _U2 , respectively. The channel can be viewed as a two-user MAC. The achievable rate region is, therefore, [figure omitted; refer to PDF] Similarly, for relay _R3 in the first stage, we have [figure omitted; refer to PDF] We then obtain that the achievable rate region of device _Ui in the first stage is [figure omitted; refer to PDF]

In the second stage, for device _U2 , we have [figure omitted; refer to PDF] We then obtain that the achievable rate region of device _Ui in the second stage is [figure omitted; refer to PDF]

Combining (18) with (20), we obtain that the achievable rate region of device _Ui by RNCMCR is [figure omitted; refer to PDF] which is the same as (14). It naturally indicates a conjecture that, for M devices, M-1 relays are enough for RNCMCR without performance penalty with respect to that composed of ^CM2 relays. In the next subsection, we analytically verify this conjecture and compare RNCMCR with CMCR.

3.2. Analysis for General Number of Devices

We first derive the achievable rate region obtained by CMCR and RNCMCR, respectively. We then compare these two schemes.

3.2.1. CMCR

Following the above derivation steps, we can obtain that the achievable rate region by CMCR for M devices and M relays in each stage is as follows.

Stage 1 . Consider [figure omitted; refer to PDF] where t[triangle, =]1/Γ .

Stage 2 . Consider [figure omitted; refer to PDF]

By jointly considering these two stages, we obtain [figure omitted; refer to PDF] where the proof of (25) is given in The Appendix.

3.2.2. RNCMCR

Following the above derivation steps, we can obtain that the achievable rate region by RNCMCR for M devices and M-1 relays in each stage as follows.

Stage 1 . Consider [figure omitted; refer to PDF]

Stage 2 . Consider [figure omitted; refer to PDF]

By jointly considering these two stages, we obtain [figure omitted; refer to PDF]

3.2.3. Comparison

Comparing (25) with (29), we obtain [figure omitted; refer to PDF] It reveals the fact that RNCMCR outperforms CMCR twofold. On one hand, it uses less relays and hence needs less aggregate power budget. On the other hand, according to (30), RNCMCR outperforms CMCR in terms of achievable rate.

4. Numerical Study

In this section, we compare the achievable throughput of different schemes, where throughput is defined as the sum rate of all devices in the network. We set σ=1 .

For M=3 , the achievable throughput of NCMCR and CMCR is plotted in Figure 5. We can see that the performance improvement in the high SNR region is around 33% .

Figure 5: Throughput comparison at different SNRs, M=3 .

[figure omitted; refer to PDF]

In Figure 6, we consider the case where M=100 . We can see that the performance improvement is much more significant than the M=3 case.

Figure 6: Throughput comparison at different SNRs, M=100 .

[figure omitted; refer to PDF]

To show the advantage under different number of devices, we plot Figure 7 with the horizontal axis representing the number of devices. We can see that the performance advantage increases linearly with respect to the logarithm of M . This indicates that our proposed scheme scales well with the network size (in terms of the number of devices).

Figure 7: Throughput comparison with respect to M , Γ=50 dB.

[figure omitted; refer to PDF]

5. Conclusion

The throughput of a D2D communication aided by a multidevice multicast two-hop Gaussian parallel relay network is analyzed. Both conventional relaying (CR) strategy and network-coded relaying (NCR) strategy together with refined version are proposed. Their achievable rates are evaluated theoretically and numerically. Comparison results show that NCR outperforms CR; the advantage increases linearly with respect to the logarithm of the number of devices, which indicates that the proposed scheme scales well with the network size.

Acknowledgments

This work was supported by Grants from Natural Science Foundation of China (61301182, 61372078, 60602066, 60773203, and 61171071), from the National 973 project (2013CB336700), from Natural Science Foundation of Guangdong Province (S2013040016857), from Specialized Research Fund for the Doctoral Program of Higher Education from The Ministry of Education (20134408120004), from Yumiao Engineering from Education Department of Guangdong Province (2013LYM_0077), from the Open Research Fund of the State Key Laboratory of Integrated Services Networks, Xidian University (ISN15-06), from Foundation of Shenzhen City (JC201005280404A, JC201005250035A, JC201005250047A, JCYJ20120613115037732, JCYJ20120613174214967, ZDSY20120612094614154, GJHS20120621143440025, JCYJ20120613115442060, and C201005250085A), and from Natural Science Foundation of Shenzhen University (00036107).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] L. Song, D. Niyato, Z. Han, E. Hossain Wireless Device-to-Device Communications and Networks , Cambridge University Press, 2013.

[2] L. Song, D. Niyato, Z. Han, E. Hossain, "Game-theoretic resource allocation methods for device-to-device communication," IEEE Wireless Communications , vol. 21, no. 3, pp. 136-144, 2014.

[3] C. Xu, L. Song, D. Zhu, M. Lei, "Subcarrier and power optimization for device-to-device underlay communication using auction games," in Proceedings of the IEEE International Conference on Communications (ICC), Sydney, Australia, June 2014.

[4] H. Cui, L. Song, B. Jiao, "Multi-pair two-way amplify-and-forward relayingwith very large number of relay antennas," IEEE Transactions on Wireless Communications , vol. 13, no. 5, pp. 2636-2645, 2014.

[5] L. Song, "Relay selection for two-way relaying with amplify-and-forward protocols," IEEE Transactions on Vehicular Technology , vol. 60, no. 4, pp. 1954-1959, 2011.

[6] F. Sun, E. de Carvalho, P. Popovki, C. Thai, "Coordinated direct and relay transmission with linear non-regenerative relay beamforming," IEEE Transactions on Vehicular Technology , vol. 60, no. 4, pp. 1954-1959, 2011.

[7] L. Song, J. Shen, S. Sun, "Research progress on device-to-device communication in China," IEEE COMSOC MMTC E-Letter , vol. 9, no. 1, pp. 46-48, 2014.

[8] T. M. Cover, A. A. El Gamal, "Capacity theorems for the relay channel," Institute of Electrical and Electronics Engineers. Transactions on Information Theory , vol. 25, no. 5, pp. 572-584, 1979.

[9] A. Host-Madsen, J. Zhang, "Capacity bounds and power allocation for wireless relay channels," IEEE Transactions on Information Theory , vol. 51, no. 6, pp. 2020-2040, 2005.

[10] G. Kramer, M. Gastpar, P. Gupta, "Cooperative strategies and capacity theorems for relay networks," IEEETransactions on Information Theory , vol. 51, no. 9, pp. 3037-3063, 2005.

[11] R. Ahlswede, N. Cai, S. R. Li, R. W. Yeung, "Network information flow," Institute of Electrical and Electronics Engineers. Transactions on Information Theory , vol. 46, no. 4, pp. 1204-1216, 2000.

[12] L. Song, G. Hong, B. Jiao, M. Debbah, "Joint relay selection and analog network coding using differential modulation in two-way relay channels," IEEE Transactions on Vehicular Technology , vol. 59, no. 6, pp. 2932-2939, 2010.

[13] S. Bhadra, P. Gupta, S. Shakkottai, "On network coding for interference networks," in Proceedings of the IEEE International Symposium on Information Theory (ISIT '06), pp. 207-211, Seattle, Wash, USA, July 2006.

[14] Y. H. Kim, N. S. Seo, Y. Y. Kim, "A network coding based multicasting (NETCOM) over IEEE 802.11 multi-hop," in Proceedings of the IEEE 65th Vehicular Technology Conference (VTC '07), pp. 845-848, Dublin, Ireland, April 2007.

[15] Y. Chen, S. Kishore, J. Li, "Wireless diversity through network coding," in Proceeding of the IEEE Wireless Communications and Networking Conference (WCNC '06), vol. 3, pp. 1681-1686, Las Vegas, Nev, USA, April 2006.

[16] M. Dai, H. Y. Kwan, C. W. Sung, "Linear network coding strategies for the multiple access relay channel with packet erasures," IEEE Transactions on Wireless Communications , vol. 12, no. 1, pp. 218-227, 2013.

[17] L. Song, Y. Li, A. Huang, B. Jiao, A. V. Vasilakos, "Differential modulation for bidirectional relaying with analog network coding," IEEE Transactions on Signal Processing , vol. 58, no. 7, pp. 3933-3938, 2010.

[18] F. Sun, T. M. Kim, A. J. Paulraj, E. de Carvalho, P. Popovski, "Cell-edge multi-user relaying with overhearing," IEEE Communications Letters , vol. 17, no. 6, pp. 1160-1163, 2013.

[19] C. Li, L. Yang, W. Zhu, "Two-way MIMO relay precoder design with channel state information," IEEE Transactions on Communications , vol. 58, no. 12, pp. 3358-3363, 2010.

[20] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, "XORs in the air: practical wireless network coding," IEEE/ACM Transactions on Networking , vol. 16, no. 3, pp. 497-510, 2008.

[21] C. Li, L. Yang, Y. Shi, "An asymptotically optimal cooperative relay scheme for two-way relaying protocol," IEEE Signal Processing Letters , vol. 17, no. 2, pp. 145-148, 2010.

[22] S. Zhang, S. C. Liew, P. P. Lam, "Hot topic: physical-layer network coding," in Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MOBICOM '06), pp. 358-365, Los Angeles, Calif, USA, September 2006.

[23] M. Effros, T. Ho, S. Kim, "A tiling approach to network code design for wireless networks," in Proceedings of the Information Theory Workshop, Punta del Este, Uruguay, March 2006.

[24] B. Ghelber, R. Dabora, "The value of cooperation between relays in the multiple-access channel with multiple relays," European Transactions on Telecommunications , vol. 23, no. 4, pp. 341-359, 2012.

[25] M. Dai, H. Wang, X. Lin, S. Zhang, B. Chen, "Opportunistic relaying with analog and digital network coding for two-way parallel relay channels," IET Communications , vol. 8, no. 12, pp. 2200-2206, 2014.

[26] M. Dai, P. Wang, S. Zhang, B. Chen, H. Wang, X. Lin, C. Sun, "Survey on cooperative strategies for wireless relay channels," Transactions on Emerging Telecommunications Technologies , 2014.

[27] P. Rost, G. Fettweis, "Analysis of decode-and-forward, compress-and-forward and combined protocols for multiterminal half-duplex relay networks with random schedules," European Transactions on Telecommunications , vol. 24, no. 2, pp. 196-211, 2013.

[28] P. Wang, L. Ping, "On maximum eigenmode beamforming and multi-user gain," IEEE Transactions on Information Theory , vol. 57, no. 7, pp. 4170-4186, 2011.

[29] P. Wang, L. Ping, "MIMO multiple access via maximum eigenmode beamforming," IEEE Transactions on Vehicular Technology , vol. 61, no. 2, pp. 900-906, 2012.

[30] T. M. Cover, J. A. Thomas Elements of Information Theory , John Wiley & Sons, New York, NY, USA, 2006.

[31] M. Dai, K. W. Shum, C. W. Sung, "Data dissemination with side information and feedback," to appear in IEEE Transactions on Wireless Communications, 2014

[32] P. Larsson, N. Johansson, K.-E. Sunell, "Coded bi-directional relaying," in Proceedings of the 5th Scandianavian Workshop on Wireless Ad-Hoc Networks, Stockholm, Sweden, May 2005.

Appendix

Appendix

Proof for (25)

Proof.

Since the case where M=2 is just the Alice-and-Bob model which has been considered in [32] and the case where M=3 has been analyzed previously, it suffices to prove for the cases M...5;4 that the following equation holds: [figure omitted; refer to PDF] It is equivalent to prove [figure omitted; refer to PDF]

At high SNR, we have t[arrow right]0 . Hence, (A.4) is equivalent to [figure omitted; refer to PDF] Note that f(x)[triangle, =](1+(1/x)^)x-1 monotonically increases with respect to x when x>0 and li_{mx[arrow right]∞} f(x)=e<3...4;M-1 when M...5;4 . We hence obtain (25).