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)
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
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.
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,ijiKjMF denotes whet-
her CN i receives packet j successfully. If node i
receives packet j successfully,

,0ijF 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.
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 
,1ijF then


R
Ri
foreach iR do
foreach


1, 2,,jM do
if 
,1ijF 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  ,1ijF 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.
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.
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.