Paper Menu >>
Journal Menu >>
![]() Int. J. Communications, Network and System Sciences, 2010, 3, 816-820 doi:10.4236/ijcns.2010.310110 Published Online October 2010 (http://www.SciRP.org/journal/ijcns) Copyright © 2010 SciRes. IJCNS Reliable Multicast with Network Coding in Lossy Wireless Networks Wei Yan, Shengyu Yu, Yueming Cai Institute of Communications Engineering, PLA University of Science and Technology, Nanjing, China E-mail: caiym@vip.sina.com Received July 7, 2010; revised August 12, 2010; accepted Septembe r 15 , 20 1 0 Abstract To reduce the feedbacks between access point and all nodes in lossy wireless networks, a clustered system model consisting of a cluster head and multiple common nodes is investigated. Network coding has been proposed for more efficient retransmissions in reliable multicast. However, in existing schemes the access point retransmits coded packets, which causes severe delay and considerable feedbacks. In this paper, an XOR scheme based on clustered model is presented. For this scheme, the cluster head broadcasts combined packets by XORing lost packets appropriately to recover lost packets locally. We also analyze the perform- ance in terms of expected number of transmissions. Simulation results verify theoretic analysis. And our re- sults show that proposed XOR offers a compromise between ARQ and random linear network coding. Keywords: Multicast, Network Coding, ARQ, Wireless 1. Introduction In wireless networks, multicast is an effective way to distribute information from a source to multiple destina- tions due to the wireless broadcast nature [1]. As fading is intrinsic in wireless links and different destinations may endure independent signal fading, it is hard to gu ar an - tee reliable transmissions for all destinations. Automatic repeat request (ARQ) is an existing approach to transmit information reliably and effectively over an error-prone network [2]. However, we can note that if a packet is not received successfully, it will be retransmitted. Using ARQ in reliable multicast, we can easily find that it may cause severe delay and considerable feedbacks, especially with a large number of destinations or high loss probability of broadcast channel. In this paper, we mainly focus on designing a practical and simple multicast protocol in lossy wireless networks. Data packets are transmitted by store-and-forward mechanism in traditional networks. Network coding is the generalized approach to packet routing that allows an intermediate router to encode an outgoing packet by mixing multiple incoming packets appropriately [3]. Re- cently, network coding has been applied to wireless net- works and received significant attention to improve mul- ticast efficiency while guaranteeing reliab ility [4,5], such as XOR, random linear network coding (RLNC) sche mes. In [4], Katti et al. implemented a simple XOR-based testbed deployment in multi-hop wireless networks and showed a substantial network throughput over the current approach. In [6], transmission strategies were designed for a source and multiple destinations network by XO Ring a maximum set of lost packets from different receivers. In [7], the authors presented a multicast protocol with network coding exploiting a relay to further improve throughput. In [8], XOR Rescue (XORR) was proposed to solve the feedback overhead. The access point (AP) in XORR probabilistically estimated reception status based on the Bayesian-learning estimation technique. This sche- me was hard to make a trade-off, as it depended on many dynamic parameters such as the number of users and wireless channel conditions [5] quantified the reliability benefit of RLNC in lossy wireless networks by comput- ing the expected number of transmissions. But it did not consider the complexity and overhead of the feedback mechanism. And random linear network coding scheme was difficult to implement yet. For energy-limited wire- less networks such as wireless sensor networks (WSNs) or mobile ad-hoc networks (MANETs), a practical and simple reliable multicast protocol was more important for uninterrupted data transmission without replenishing batteries frequently. In traditional reliable multicast of the lossy wireless ![]() W. YAN ET AL. Copyright © 2010 SciRes. IJCNS 817 networks, all nodes send the feedback messages to the access point. In this paper, the nodes are divided into several clusters. Only the clu ster h ead sends th e feedb ack to the access point, which can greatly reduce the amount of feedbacks between the access point and all nodes. Moreover, to take full advantage of the feedback mes- sages from common nodes, the cluster head combines lost packets appropriately to help common nodes recover lost packets locally. We present an XOR scheme based on clustered model and analyze the performance in terms of expected number of transmissions. And we select ARQ and RLNC in simulation results for comparison. This paper is organized as follows. Section 2 provides the system model and protocol description in detail. In Section 3, we present some theoretical analysis on the performance of ARQ and XOR. In Section 4, simulation results and discussions are presented. Finally, we con- clude the conclusions in Section 5. 2. System Model and Protocol Description In a typical data multicast transmission from AP to a lot of nodes, the nodes are divided into several clusters. As depicted in Figure 1, our system model is the scenario where the AP broadcasts the packets to a single cluster, which consists of a cluster head (CH) and K common nodes (CNs). The cluster head takes responsibility to deliver the packet to common nodes in the cluster. Namely, common node can not communicate with the other common nodes and communication links only exist between the CH and CNs. The AP can be considered as an unmanned aerial vehicle (UAV) or stratospheric tele- communication platform, which conveys the information to the nodes on the ground. Due to high signal attenua- tion, communications from the AP to the nodes suffer from high loss rates. However, the communications among the nodes on the ground always experience good channel quality. So the nodes on the ground can cooper- ate together to recover lost packet locally. A three-phase transmission mechanism for reliable packet delivery from the AP to all nodes is considered in Figure 1. System model. this paper. In the first phase, the AP broadcasts a suffi- cient number of packets to all nodes in the cluster such that every packet is received by at least one of the nodes. For each packet, every CN sends an ACK (ACKnowl- edgment) message or NACK (Negative ACKnowledg- ment) message to the CH after the AP’s transmission. If there is at least one of successful receivers in the cluster, the CH sends an ACK message to the AP. If none of the nodes receives the packet successfully, the CH sends a NACK message to the AP and then the AP retransmits the lost packet. The second phase depends on whether the CH receives the all packets successfully. If the CH receives the all packets successfully, the second phase has already achieved. If not, the CH chooses cooperative cluster head (CCH) from the nodes which receive cor- rectly. Then the CCHs send corresponding packets to the CH until the CH has the all packets. During the third phase, the CH helps all CNs recover the lost packets. For ARQ, the CH multicasts the corresponding lost packets such that all CNs receive the all packets in the third phase. That is, one lost pack et transmission is com- pleted if every CN has this packet. For XOR, the CH multicasts the combined packets by XORing different lost packets appropriately in the third phase. Let M denote the packet number of a data block. After the first phase, the CH sets up a feedback matrix K M F according to the ACKs/ NACKs from the CNs, where ,; 1,2,,1,2,ijiKjMF denotes whet- her CN i receives packet j successfully. If node i receives packet j successfully, ,0ijF and if not, ,1ij F. According to the feedback matrix, the CH forms a combined packet by XORing a maximum set of the lost packets from different common nodes. In this way, the number of the packets for transmission from the CH to all common nodes is reduced. For instance, as shown in Figure 2, a feedback matrix for three common nodes and data block size 9M is given. The com- bined packets are 13 , 456, 78 and 9. He- nce, Only 4 packets need to be sent, compared to 8 transmi ssi ons wi t hout networ k c od ing. We define C as the set of packet sequences for a new combined packet. The set R denotes the searched rows. The set E denotes the packet sequences avoiding the decoding failure which can’t be chosen as an element. of the set C. For K CNs and data block size M, the 39 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 F Figure 2. An example of feedback matrix for three common nodes and 9M . ![]() W. YAN ET AL. Copyright © 2010 SciRes. IJCNS 818 detailed algorithm for general combination of lost pack- ets is given in Algorithm 1. Algorithm 1: Input: K M F C E R Find a row i of K M F where max ,:sum iF Find a column j of the row i with ,1ij F, and CC j foreach 1, 2,,iK do if ,1ijF then R Ri foreach iR do foreach 1, 2,,jM do if ,1ijF then EE j foreach 1, 2,,nM do if 1, 2,,nME then foreach 1, 2,,iKR do if ,1in F then CC n R Ri foreach 1, 2,,jM do if ,1ijF then EE j Output: C Through clustering the nodes, the amount of feedbacks can greatly reduce between all nodes and the AP. For ease of performance analysis, in this paper, we assume all ACKs/NACKs are instantaneous and reliable. Trans- missions from the AP, over a wireless link to all nodes on the ground, are subject to random losses. We assume that losses for all nodes are described by independent Bernoulli processes with parameter 0 p . Similarly, local transmissions between CH and CNs are subject to ran- dom losses, where the loss process is Bernoulli with pa- rameter 1 p . In practice, the channels between AP and all nodes have relatively lower channel gains than the cor- responding channels among the nodes, that is 01 pp. 3. Performance Analysis In thi s section, w e provide theo retical ana lysis on th e num- ber of transmissions per packet for ARQ and XOR. With three phase model, N, the number of transmissions per packet, includes three components of X, Y and Z X, Y and Z separately denote the number of transmissions in three different phase. For ARQ, NXYZ. For XOR, N i s give n by NXYZM . 3.1. Distribution of the Number of Transmissions 1) ARQ Performance In the first phase, the probability distribution function of X is give n b y [5]: 1 0 1 K x PXxp (1) In the second phase, we have 01 0 01 110 = 1 y y PY yppp pp (2) Let W denote the number of common nodes that have received a copy of the packet. The probability dis- tribution of W can be expressed as 00 1w K w K PW wpp w (3) Hence, we can obtain that the probability distribution function of Z is 0 1 0 01 =1 =1 K w KKw z w K z PZ zPW wPZzWw PW wp pp (4) 2) XOR Performance The probability that a packet transmitted by the AP is received by at least one node in a cluster is given by 1 0 1K p . Similar to the first phase of RLNC [5], X has a negative binomial distribution with success probabil- ity 1 0 1K p . Therefore, the probability distribution of X is 1 1 00 11 1 M K xM K x PX xpp M (5) In the second phase, the CH assigns the CCHs to trans- mit lost packets according to feedback matrix. Let a ran- dom variable U denote the number of packets suc- cessfully received by the CH. The probability distribu- tion of Y can be computed as 0 M U PYyPYyU uPU u (6) where 11 11 1 Mu y Mu y PYyU upp Mu and 00 1u K u M PU upp u . In the third phase, CH broadcasts the combined pack- ![]() W. YAN ET AL. Copyright © 2010 SciRes. IJCNS 819 ets to CNs. When data block size M goes to , the number of transmissions is dominated by the CN which has the maximum lost packets [6]. For ease of analysis, we assume that at least one CN has lost M packets. Therefore, the expectation of Z is 1 11 lim 1 MEZ M p (7) 3.2. Asymptotic Analysis 1) ARQ Performance The average number of transmissions in the first and second phase is separately given by: 1 00 1 1K x EXPX xp (8) and 0 0 01 11 y y EYyPY y p yPY yPY yp (9) The average number of CNs receiving the packet suc- cessfully is 0 0 1 W w EWwPWwp K (10) To simplify the analysis, the number of CNs receiving the packet unsuccessfully is replaced by its mean value, i.e., each packet from CH is required by 0 pK CNs. Based on the analysis [5], the expected number of trans- missions is 0 1111 0 ln 11 lim lnln 1ln loglog K pK EZ pppp pK K (11) where is Euler’s constant. Therefore, for ARQ, the expected number of transmissions per packet scales as log K . 2) XOR Performance In the first phase, we can obtain 1 0 11 lim 1K MEX Mp (12) The expectation of U can be computed as 0 0 1 M u EUuPUup M (13) For simplicity, we assume the number of packets suc- cessfully received by the CH is EU . It is also ob- tained that 0 1 1 lim 1 M p EY M p (14) Hence, for XOR, the expected number of transmis- sions per packet scales as 1 according to (7), (12) and (14). 4. Simulations In this section, simulation results on the expected number of transmissions for different schemes are discussed. For ARQ, Figure 3 shows the expected number of transmis- sions for a wide range of values of K and different loss probabilities. The horizontal axis shows 2 log K , and it can be seen that the four curves are very close to straight line. Hence, the simulation results validate the logarith- mic scale. For XOR, the expected number of transmis- sions for data block size 128M versus different loss probabilities is shown in Figure 4. The expected number of transmissions approaches a constant value with in- creasing the number of CNs. Figure 5 and Figure 6 show that the expected number of transmissions f or different schemes wit h 01 0.5, 0.05pp And 01 0.5, 0.2pp , respectively. As seen, XOR of- fers a compromise between ARQ and RLNC. An inter- esting observation is that the expected number of trans- missions for XOR is almost close to ARQ with32 CNs. When 8K , XOR can obtain the best performance gain. For different probabilities and data block size, an open problem arises as to how many CNs to make XOR a chi e v e maximal performance gain over ARQ. For XOR and RLNC with32,64,128M , it can be seen that the ex- pected number of transmissions reduces with increasing data block size. Similar to RLNC, XOR has the same result that a moderate block size suffices to obtain the advantage applying network coding. 0 1 23 45 678 910 1. 5 2 2. 5 3 3. 5 4 4. 5 5 5. 5 6 6. 5 Number of CNs (log 2 (k )) Expected number of transm issions p 0 =0.5 p 1 =0.05 p 0 =0.5 p 1 =0.2 p 0 =0.4 p 1 =0.05 p 0 =0.4 p 1 =0.2 Figure 3. The performance of ARQ for different probabili- ties. ![]() W. YAN ET AL. Copyright © 2010 SciRes. IJCNS 820 020 4060 80 100 120 140160 180 200 1.5 2 2.5 3 3.5 4 4.5 5 5.5 Number of CNs (k) Expected num ber of transm issi ons p 0 =0.5 p 1 =0.05 p 0 =0.5 p 1 =0.2 p 0 =0.4 p 1 =0.05 p 0 =0.4 p 1 =0.2 Figure 4. The performance of XOR for different probabili- ties. 05 10 1520 25 30 35 2 2. 2 2. 4 2. 6 2. 8 3 3. 2 3. 4 Number of CNs Expect ed num ber of t rans m i s s i ons ARQ XOR M=32 XOR M=64 XOR M = 128 RLNC M =32 RLNC M =64 RLNC M =128 Figure 5. Expected number of transmissions for different schemes with 01 0.5, 0.05pp. 0510 15 20 25 30 35 2 2.5 3 3.5 4 4.5 Number of CNs E xpected num ber of tra nsm i ssions ARQ XOR M=32 XOR M=64 XOR M =128 RLNC M=32 RLNC M=64 RLNC M=128 Figure 6. Expected number of transmissions for different schemes with01 0.5, 0.2pp. 5. Conclusions In this paper, we investigated network coding for reliable multicast and presented an XOR scheme based on clus- tered model in lossy wireless networks. Instead of access point, cluster head retransmits the combined packets to recover the lost packets for multiple common nodes. We provide theoretical analysis in terms of expected number of transmissions and extensive simulations. Simulation results show that proposed XOR can achieve maximal performance gain with some common nodes for different probabilities and data block size. And our XOR can offer a compromise between ARQ and RLNC. It must be em- phasized, however, that clustered network was consid- ered in this paper. In the future, the extension to a decen- tralized network is an interesting topic in lossy wireless networks, which requires further research. 6. Acknowledgements This work is supported by the Important National Sci- ence & Technology Specific Project under Grant 2010 ZX03006-002-04, the National Natural Science Founda- tion of China under Grant No. 60972051, the National 863 Project of China under Grant No. 2009AA01Z235 and the Project of Natural Science Foundation of Jiangsu province under Grant No. BK2010101. 7. References [1] P. Chaporkar and S. Sarkar, “Wireless Multicast: Theory and Approaches,” IEEE Transactions on Information Theory, Vol. 51, No. 6, 2005, pp. 1954-1972. [2] S. Lin and D. Costello, “Error Control Coding,” Prentice Hall, Uppser Saddle River, New Jersey, 2004. [3] R. Ahlswede, N. Cai, R. Li and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, Vol. 46, No. 4, 2000, pp. 1204-1216. [4] S. Katti, H. Rahul, W. Hu, D. Katabi, et al., “XORs in the Air: Practical Wireless Network Coding,” Proceedings ACM SIGCOMM, Pisa, Italy, September 2006, pp. 497-510 [5] M. Ghaderi, D. Towsley and J. Kurose, “Reliability Gain of Network Coding in Lossy Wireless Networks,” De- partment of Computer Science, University of Calgary, Technical Report: TR-07-08, January 2008. [6] D. Nguyen, T. Nguyen and B. Bose, “Wireless Broadcast with Network Coding,” Technical Report: OSU-TR-2006 -06, Oregon State University, June 2006. [7] P. Fan, Z. Chen, W. Chen and K. B. Letaief, “Reliable Relay Assisted Wireless Multicast Using Network Cod- ing,” IEEE Journal of Selected Areas in Communications, Vol. 27, No. 5, 2009, pp. 749-762. [8] F. C. Kuo, K. Tan, X. Y. Li, et al., “XOR Rescue: Ex- ploiting Network Coding in Lossy Wireless Networks,” IEEE Sensor, Mesh and Ad Hoc Communications and Networks Conference (SECON), Rome, Italy, June 2009, pp. 1-9. |