POSTPRINT (ACCEPTED VERSION), DOI: 10.1109/LCOMM.2012.021612.112589

1

Decentralized-Precoding Aided Rateless Codes
for Wireless Sensor Networks
Shinya Sugiura, Member, IEEE

Abstract—In this letter, we propose a novel decentralizedprecoding aided rateless code, which is conceived for WirelessSensor Networks (WSNs). More specifically, the proposed algorithm allows a collection of source nodes to precode theirinformation symbols in an uncoordinated manner. The precoded
symbols are then channel-encoded by a distributed rateless codeat each sensor node. This architecture enables us to eliminate anerror floor imposed on the conventional Luby Transform (LT)code based WSNs, without requiring a central coordinator or
any elaborate cooperations between the nodes. Our simulation
results demonstrate that the proposed distributed rateless codeis capable of attaining achievable BER performance comparable
to that of a Raptor code coordinated by a central coordinator,
while outperforming a distributed LT code.
Index Terms—Distributed storage, fountain codes, graphicalcodes, network coding, rateless codes, sensor network, belief
propagation algorithm.

I. I NTRODUCTION
Wireless Sensor Networks (WSNs) [1], [2] consist of unreliable devices, sensors or vehicles, which can be used for
instance as a distributed storage system [3]. Typically, theemployment of an efficient Forward Error Correction (FEC)
scheme is necessary for such a virtual storage system, inorder to protect source information stored in distributed sensor
nodes. Furthermore, it is desirable for WSNs to be able tocomplete the channel-encoding process in a decentralized anddistributed manner, which is for the sake of avoiding any
substantial overhead and energy consumption.
In comparison to the conventional fixed-rate FEC schemes,
the recent class of rateless codes [4] is capable of producing
a potentially infinite length of codeword, implying that its
code rate as well as the amount of redundancy does nothave to be fixed before the transmissions. The first practical
rateless code, which is the so-called Luby Transform (LT) code[5], was invented for the Internet Binary Erasure Channels(BECs). While LT codes tend to exhibit a high error floor
for noisy channels, such as Additive White Gaussian Noise(AWGN) and Rayleigh fading channels, Raptor codes [6] wereconceived for the sake of combating this limitation, where ahigh-rate Low-Density Parity-Check (LDPC) channel encoder
is inserted as a precoder in advance of the LT encoder. As theresult, Raptor codes benefit from an error-free performance innoisy channel environments as well as from a practically low
decoding complexity.
c
Copyright ⃝2012
IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained
from the IEEE by sending a request to pubs-permissions@ieee.org.
The author is with Toyota Central R&D Laboratories, Inc., Nagakute, Aichi,
480-1192, Japan (e-mail: sugiura@ieee.org).

Owing to their beneficial characteristics, rateless codes wereapplied to several WSN scenarios [7], [8]. For instance, in[7] an LT code was employed at source nodes to spreadtheir channel-coded information symbols to WSNs without
necessitating any negotiation between the nodes. Furthermore,
the destination receiver can decode the information symbols bygathering any subset of the LT-coded symbols, which enables
the band-efficient implementation of Incremental Redundancy(IR), which is especially useful for broadcast- or multicastscenarios. However, since most of the previous studies related
to distributed storage are based on LT codes, rather than
Raptor codes, the above-mentioned error floor imposed bynoisy channels is unavoidable. Unfortunately, it is impracticalto configure a Raptor-coded WSN, because it requires theinsertion of a precoder, which has to be aided with a central
coordinator or with substantial information exchanges between
the nodes, as mentioned in [7]. One exceptional approach isconstituted by the exploitation of random walk [9], where
the redundant channel-encoded symbols are generated during
the additional transmissions in advance of the distributed LT
coding. Note that the achievable performance of this scheme
over noisy channels was not documented.
Against this background, the novel contributions of this letter are as follows. We first propose an efficient decentralizedprecoding aided rateless code, where source nodes generate
redundant symbols in an uncoordinated manner. More specifically, the redundant symbols are calculated so as to haveappropriate correlations with the source symbols. Hence, this
distributed-precoding architecture allows us to eliminate anerror floor imposed on the distributed LT code, similarly tothe centralized Raptor code. Importantly, owing to the factthat the proposed precoding scheme does not rely on either
cooperative precoding or an additional random walk process,the cost imposed on encoding the source information is as
low as that of the distributed LT code [7]. Furthermore, whilemost of the previous studies with respect to the distributed
rateless codes considered a BEC, we provide simulation resultsof several distributed rateless codes in the context of binaryinput AWGN channels.
The remainder of this letter is organized as follows. Section
II provides the conventional rateless-code assisted WSN andthe proposed decentralized-precoding aided rateless codes. The
related numerical analysis is carried out in Section III. Finally,
our conclusions are presented in Section IV.
II. P ROPOSED D ISTRIBUTED R ATELESS C ODESIn this section, we firstly describe the network model
adopted in this letter. Then, we highlight the conventional

POSTPRINT (ACCEPTED VERSION), DOI: 10.1109/LCOMM.2012.021612.112589

distributed LT-code [7] based WSNs, which is followed by the
proposal of the novel distributed rateless-coding framework.

2

k=0

A. Network Model
Let us consider a WSN, which consists of N storage sensor
nodes, K source nodes as well as the communication links
between them. We assume for simplicity that each source node
has a single binary information symbol dk ∈ {−1, 1} (k =1, · · · , K), which is saved at the N sensor nodes. Moreover, acommon destination node communicates with a subset of thesensor nodes in order to attain the stored source information.
Hence, the following two-phase transmissions are consideredin this scenario. In the broadcast phase, the K source nodes
transmit their symbols to the N sensor nodes, where thereceived symbols are channel encoded at each sensor node.
Then, in the collection phase the destination node receives
the channel-coded symbols in order to decode the K source
symbols.1
B. The Conventional Distributed LT Codes
The distributed LT code enables each of the N sensor nodes
to independently generate its own channel-coded symbol.
This also allows the destination node to decode the symbols
received from any subset of the N channel coded symbols,
which is achieved as the explicit benefit of the LT-code based
rateless code. More specifically, in the broadcast phase, the Ksource nodes independently transmit their symbols to the N
sensor nodes, noting that in this scheme any restriction may
not be imposed on the type of the Medium Access Control(MAC) protocol employed. Then, letting the nth sensor nodeof the interest, en number of source symbols randomly chosen,
according to a predetermined probability generating functionΩ(x) [5]. Finally, a symbol cn is determined by XORing the en
number of selected symbols, which is stored at the nth sensor
node. Here, the associated edge information, represented by
the indices of the selected source symbols, is also saved in
the memory of the associated sensor node.
To be more specific, Ω(x) is represented byΩ(x) = δ1 x + δ2 x2 + · · · + δk xk + · · · + δK xK ,(1)

where δk (k = 1, · · · , K) represents the particular fraction ofcheck nodes having∑K the degree δk , noting that we have therelationship of
k=1 δk = 1. Also, the average number ofedges connected from∑the variable nodes to the check nodes
K−1
is given by Ω′ (1) = k=1 kδk . Here, the check nodes are
represented by XOR operations at the sensor nodes, while thevariable nodes correspond to the source symbols of the source
nodes [10].
In the collection phase, the destination node receives (1 +ϵ)K < N output symbols from arbitrary sensor nodes together
with the associated edge information, where ϵ represents the
portion of overhead symbols received at the destination node.
Then, the Belief Propagation (BP) algorithm [10] is invoked
1 In order to elaborate a little further, although we considered in this letterthe scenario of K source nodes, each having a single source bit, the proposed
scheme can be readily applicable to a more general scenario of K/B source
nodes, each having B ≥ 1 source bits.

Pk < P ?

Start

k=k+1

No
Generate dζ from di

Broadcast dζBroadcast dk
Generate Pk

Yes

No

k=K?
Yes
End

Fig. 1. Flowchart of the proposed decentralized-precoding assisted source
transmissions.

for decoding the K source symbols. In this process, the mutual
information increases upon increasing the number of iterations
between check- and variable-nodes.
C. The Proposed Decentralized-Precoding Aided RatelessCodes
Fig. 1 depicts the broadcast phase of the proposed ratelesscode, where the K source nodes transmit in total M > K
precoded symbols. This implies that (M −K) redundant symbols are added in this precoding process. Here, a certain MAC
protocol, such as Time-Division Multiple Access (TDMA) and
Carrier Sense Multiple Access (CSMA), is assumed to be
employed, where each of the K source nodes carries out its
transmissions from the first to the Kth source nodes in order,
without loss of any generality.2
More specifically, as portrayed in Fig. 1, the kth source nodebroadcasts its own symbol dk to the other source nodes as wellas to the sensor nodes. Then, the kth source node generates areal-valued random variable Pk , which is uniformly distributed
between 0 and 1. Here, if Pk is lower than a preassigned
threshold P , the kth source node’s transmission is completed.
Otherwise, the kth source node calculates another symbol dζfrom the (k−1) previously-transmitted source symbols di (i =1, · · · , k−1). More specifically, min(k−1, e) out of the (k−1)
source symbols are chosen so that the selected symbols havethe least number of connections at the instant of the kth node’stransmission [11].3 The integer∑Kvalue e obeys the probability
generating function Ω̄(x) = d=1 δ̄k xk , similarly to Eq. (1).
Then, a redundant symbol dζ is generated by XORing theselected min(k − 1, e) source symbols, which is transmitted
to the N sensor nodes.4 Finally, the N sensor nodes operate
the distributed LT encoding of Section II-B based on the M
precoded symbols, which are received during the broadcast
phase.
2 In order to expound a little further, our rateless code does not support MAC
protocols, relying on purely simultaneous transmissions from the nodes, which
are for example Code-Division Multiple Access (CDMA) and Orthogonal
Frequency Division Multiple Access (OFDMA). We note nevertheless thatthe hybrid scheme, such as Time-Division (TD)/CDMA and TD/OFDMA
schemes, may still be applicable to the proposed rateless code.
3 This is possible because edge information corresponding to the first (k−1)
source nodes are known at the moment of the kth source node’s transmission.
4 To avoid potential errors for the packets saved at storage nodes, Cyclic
Redundancy Checking (CRC) codes are typically employed at the source
nodes, which enables error detection at the source- and storage-nodes.

POSTPRINT (ACCEPTED VERSION), DOI: 10.1109/LCOMM.2012.021612.112589

3

Check node
Variable node

Sourcesymbols
Edge interleaver

100
…

…

Precode…

10-1

Redundant
symbols

LT code10-2
BER

Edge interleaver

Outputsymbols20
Proposed x
40
Proposed x
60
Proposed x
80
Proposed x

LT codeRaptor code
Proposed

10-3

10-4

Fig. 2. Tanner graph of the proposed decentralized-precoding aided ratelesscode.

To provide further insights, in the proposed precoding
scheme the edges connected from the check nodes to the variable nodes are directional, rather than symmetrically random.
This indicates that the redundant check node of the kth source
node, satisfying the relationship of Pk ≥ P , potentially has
the connections with the previously transmitted (k − 1) source
symbols, rather than with the rest of the (K − k) source
symbols, unlike the conventional Raptor code. Although thisrestriction may induce some performance degradation, we will
demonstrate later in Section III that the proposed rateless codeis capable of attaining the performance comparable to that of
the Raptor code.
We note that the above-mentioned value P , which is introduced as the threshold of the statistical redundant-symbol
generations, corresponds to the average code-rate of the proposed decentralized precoder, hence the normalized transmission rate of the proposed rateless code may be defined by
R = P/(1 + ϵ). Furthermore, a higher P value leads to thelower number of redundant symbols, hence resulting in the
degradation of the error-correction capability. This implies thatthe optimization of P imposes a design tradeoff between theachievable error-rate performance and the transmission rate.
Fig. 2 shows the Tanner graph of the proposed ratelesscode, which forms a two-stage serial-concatenated graph code,i.e. the precoder equivalent to the systematic Low-Density
Generator Matrix (LDGM) code and the LT encoder. While
there are several potential solutions of this graph code, in thisletter we employ the tandem iterative detection [12], which istypical for the conventional Raptor code. To be more specific,
the soft outputs of the inner LT decoder are calculated withthe aid of the number of inner iterations ILT , which are theninput to the outer iterative decoder, where we have the numberof outer iterations Ipre . Hence, the total number of iterations
becomes (ILT + Ipre ). Also, we note that a higher numberof edges dζ associated with the redundant symbols of Fig. 2
imposes a higher complexity at the distributed precoder andthe destination node’s receiver.
III. S IMULATION R ESULTS
In this section the performance of our distributed ratelesscode is characterized by carrying out Monte Carlo simulations.
We also considered two benchmark schemes, namely the

10-5

10-6
1.0

1.1

1.2
R

-1

(a)

1.3

1.4

1.0

1.1

1.2

1.3

1.4

-1
R

(b)

Fig. 3.
Achievable BER performance of the distributed LT code, thecoordinated Raptor code and the proposed decentralized-precoding aided
rateless code, each employing BPSK modulation under the assumption of
AWGN channel, exhibiting SNR = 5 dB. Furthermore, we employed (a)Ω̄(x) = x60 and (b) Ω̄(x) = x20 , x40 , x60 and x80 as the precoder’srandom generating functions.

distributed LT code of Section II-B as well as the Raptor code[6], which was assumed to be coordinated by a central node.
In our simulations, we set the LT-code’s random distributionΩ(x) used at the N sensor nodes as [13]Ω(x) = 0.007969x + 0.493570x2 + 0.166220x3+ 0.072646x4 + 0.082558x5 + 0.056058x8+ 0.037229x9 + 0.055590x19 + 0.025023x65+ 0.0003135x66 ,(2)
while that of the proposed precoder Ω̄(x) = xDc was chosen
as follows: Dc = 20, 40, 60 and 80. The maximum number of
inner and outer iterations was set to (ILT , Ipre ) = (200, 200).
Furthermore, the threshold P was chosen as P = 0.95, whichcorresponds to the average outer code-rate. We also considered
the Binary Phase-Shift Keying (BPSK) modulation and the
AWGN channels for the links between the sensor nodes andthe destination node.
Fig. 3(a) shows the achievable BER performance of thethree rateless codes, namely the LT code, the Raptor code andthe proposed rateless code at the Signal-to-Noise Ratio (SNR)of 5 dB. For the Raptor code and the proposed rateless code,
we assumed for K = 9 500 source bits and the P = 0.95 coderate precoder. More specifically, the Raptor code employed
the systematic LDPC precoder, where each source symbol
has the degree four and the edges to the redundant checknodes selected uniformly, similarly to [11]. Moreover, 10 000
source bits as well as the probability generating functionΩ(x) of Eq. (2) was used for the distributed LT code. Here,POSTPRINT (ACCEPTED VERSION), DOI: 10.1109/LCOMM.2012.021612.112589

Channel (DCMC) capacity [15]. Observe in Fig. 4 that both theproposed rateless code and the Raptor code exhibited a similar
performance, which approached the DCMC capacity limit,
while outperforming the LT code. In the simulated scenario,
the LT code’s throughput was approximately 24% lower thanother two codes at high SNRs.

1.4
Throughput [bits/symbol]

CCMC capacity limit

1.2

DCMC capacity limit

1.0
0.8
0.6
0.4

LT codeRaptor code
Proposed

0.2
0.0
-5

0

5

10

4

15

SNR [dB]

Fig. 4. Effective throughputs of the distributed LT code, the coordinatedRaptor code and the proposed decentralized-precoding aided rateless code,
each employing BPSK modulation under the assumption of AWGN channel
Here, Ω̄(x) = x60 was used at the proposed scheme’s precoder.

we note that since the distributed LT code did not utilize aprecoder, its normalized throughput may be simply expressed
as R = 1/(1 + ϵ). The random generating function Ω̄(x) of
our rateless code’s precoder was given by Ω̄(x) = x60 . It was
found from Fig. 3(a) that the proposed rateless code closely
approached the performance of the coordinated Raptor code,
while a marginal performance loss was seen for BER = 10−6 .
As predicted, the LT-code based system exhibited a high errorfloor for approximately BER = 10−4 in the simulated regime.5
Next, Fig. 3(b) investigates the effects of the random
generating function Ω̄(x) = xDc on the achievable BER
performance of the proposed rateless code, where we varied
Dc as Dc = 20, 40, 60 and 80. It can be seen in Fig. 3(b)that the Dc = 60 scenario attained a higher transmission
rate for BER = 10−6 than other Dc scenarios. Furthermore,
the scenarios of Dc = 20 and 80 exhibited an error floor,
similarly to the distributed LT code of Fig. 3(a). This ensuresthat the appropriate design of Ω̄(x) is vital for our distributed
rateless code. More specifically, although an increase in thevalue of Dc tended to result in the performance improvement,
an excessively high Dc may degrade the performance owing
to the so-called marginalization problem [10], which is causedby the associated graph codes with cycles.
Finally, in Fig. 4 we compared the effective throughputsof the three rateless codes and their bounds. In each frametransmission of K source bits, the initial number of thereceived symbols was set to 10 000 and additional 100 bits
were received until the iterative decoder output the correct K
source symbols. Here, we also plotted the two corresponding
capacity-limit curves, which are represented by Continuous
input Continuous output Memoryless Channel (CCMC) capacity [14] and Discrete input Continuous output Memoryless
5 Although we employed the fixed number of edges at the proposedprecoder’s redundant check nodes, which is represented by Ω̄(x) = xDc , it ispossible to reduce a marginal performance gap between the Raptor code andthe proposed code of Fig. 3(a) by considering its distribution Ω̄(x), similarly
to Eq. (2). However, the detailed optimization and analysis will be left for
our future study.

IV. C ONCLUSIONSIn this letter, we proposed the novel rateless code conceived
for WSNs, which can be operated in a fully decentralizedmanner, while combating the error-floor limitation of the conventional LT-code based counterpart. More specifically, eachsource node stochastically generates a redundant symbol, suchthat it has correlations with the previously transmitted source
symbols. Hence, the resultant graph-code structure becomessimilar to that of a centralized Raptor code. It was shownin our simulations that the proposed decentralized ratelesscode is capable of approaching the BER performance of the
Raptor code, while outperforming the distributed LT code.
The proposed rateless-code architecture may also be useful for
improving multi-source cooperative communications based on
the distributed LT code [16].
R EFERENCES[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey
on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8,
pp. 102–114, 2002.
[2] F. Wang and J. Liu, “Networked wireless sensor data collection: Issues,challenges, and approaches,” IEEE Communications Surveys & Tutorials, 2011, doi:10.1109/SURV.2011.060710.00066, 12 pages in press.
[3] A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran,“Network coding for distributed storage systems,” IEEE Transactions
on Information Theory, vol. 56, no. 9, pp. 4539–4551, 2010.
[4] N. Bonello, S. Chen, and L. Hanzo, “Low-density parity-check codes
and their rateless relatives,” IEEE Communications Surveys & Tutorials,
vol. 13, no. 1, pp. 3–26, Feb. 2011.
[5] M. Luby, “LT codes,” in the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’02), 2002, pp. 271–280.
[6] A. Shokrollahi, “Raptor codes,” IEEE Transactions on Information
Theory, vol. 52, no. 6, pp. 2551–2567, 2006.
[7] A. Dimakis, V. Prabhakaran, and K. Ramchandran, “Decentralized
erasure codes for distributed networked storage,” IEEE Transactions on
Information Theory, vol. 52, no. 6, pp. 2809–2816, 2006.
[8] K. Pang, Z. Lin, Y. Li, and B. Vucetic, “Design of distributed networkchannel codes for wireless sensor networks,” in IEEE International
Conference on Communications (ICC 2011), Kyoto, Japan, 5–9, June
2011, pp. 1–5.
[9] Z. Kong, S. Aly, and E. Soljanin, “Decentralized coding algorithms
for distributed storage in wireless sensor networks,” IEEE Journal on
Selected Areas in Communications, vol. 28, no. 2, pp. 261–267, 2010.
[10] T. Richardson and R. Urbanke, Modern coding theory. Cambridge
University Press, 2008.
[11] N. Bonello, R. Zhang, S. Chen, and L. Hanzo, “Reconfigurable ratelesscodes,” IEEE Transactions on Wireless Communications, vol. 8, no. 11,
pp. 5592–5600, 2009.
[12] A. Venkiah, C. Poulliat, and D. Declercq, “Jointly decoded Raptor
codes: Analysis and design for the biawgn channel,” EURASIP Journal on Wireless Communications and Networking, 2009, 11 pages,
doi:10.1155/2009/657970.
[13] R. Palanki and J. Yedidia, “Rateless codes on noisy channels,” inInternational Symposium on Information Theory (ISIT 2004), Chicago,
Illinois, USA, 27 June – 2 July 2004, pp. 1–12.
[14] J. Proakis, Digital communications. McGraw-Hill, New York, 2001.
[15] S. X. Ng and L. Hanzo, “On the MIMO channel capacity of multidimensional signal sets,” IEEE Transactions on Vehicular Technology, vol. 55,
no. 2, pp. 528–536, 2006.
[16] S. Puducheri, J. Kliewer, and T. Fuja, “The design and performanceof distributed LT codes,” IEEE Transactions on Information Theory,
vol. 53, no. 10, pp. 3740–3754, 2007.