“ﬂ
LIE“? ARY
Michigan State
University
This is to certify that the
dissertation entitled
A PROGRESSIVE RELIABILITY FRAMEWORK FOR
WIRELESS SENSOR NETWORKS
presented by
SAAD BIN QAISAR
has been accepted towards fulﬁllment
of the requirements for the
PhD. degree in Electrical Engineering
/ ////5
/Major Professor’ s Signature
Y M514 /(/:/) ,1. OGCI
T I ,I I
/’
Date
MSU is an Afﬁnnative Action/Equal Opportunity Employer
...—.... —..... _  _
_.—:.cc.—n—.—.o..
PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.
DATE DUE DATE DUE DATE DUE
5/08 KIProj/Aoc8Pres/CIRCIDateDm.hdd
‘A PROGRESSIVE RELIABILITY
FRAMEWORK FOR WIRELESS SENSOR
NETWORKS
By
Saad Bin Qaisar
A DISSERTATION
Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Electrical Engineering
2009
ABSTRACT
A PROGRESSIVE RELIABILITY
FRAMEWORK FOR WIRELESS SENSOR
NETWORKS
By
Saad Bin Qaisar
This dissertation investigates a new framework for achieving high data rates and
negligible error probabilities by distributing the processing over multihop networks.
In particular, we consider the case of reliable data transmission in energy constrained
Wireless Sensor Networks (WSNs). Low rate channel coding can increase reliability
and eliminate the need of costly retransmissions of sensor data. However, low rate
channel coding on endtoend basis puts a considerable burden in terms of transmit
energy on resource constrained sensor nodes. We propose a setup that progressively
provides reliability as information traverses the multihop wireless sensor network.
Precisely, we propose an Optimal Progressive Error Recovery Algorithm (OPERA)
under which, individual intermediate sensors that are relaying data toward the base
station, partially and optimally channeldecode the incoming packets as data reaches
the final destination. We use iteratively decodable Low Density Parity Check (LDPC)
codes in order to illustrate the efﬁciency of the proposed architecture. The proposed
OPERA setup optimally distributes the decoding iteration budget over the entire
network with minimal energy expenditure. We provide a comparison between our it
eration assignment algorithm with both random iteration assignment and endtoend
channel coding, and show that OPERA performs considerably better. In addition,
further motivated by resource limitation of sensor nodes and the wellknown sensor
reachback problem, we propose a version of OPERA that is proportionally fair to
individual sensor nodes using rate adaptivity in channel coding. We use systematic
puncturing of LDPC codes to develop a rate compatible framework that is fair to
individual nodes by both, progressive decrease in parity as information reaches the
destination node, and restricting the per node processing based on their location in the
multihop WSN. We present various scenarios for a WSN to achieve ratecompatibility
and discuss associated complexity/ energy usage and distortion/ reliability tradeoffs.
Further motivated by distributed architectures, we propose a distributed version of
OPERA in which decoding iterations are assigned in a pairwise fashion to individ
ual nodes. Under the proposed Distributed Progressive Error Recovery Paradigm
(DOPERA), nodes collaborate, in a distributed pairwise manner to allocate the
processing budget to individual nodes and obtain near optimal performance. We
further investigate the performance of proposed framework when multiple paths are
available for data originating nodes to the destination. We apply the OPERA frame—
work to both still images as well as video streams and present an architecture for
reliably transmitting video in WSNs without fast depleting their energy resources.
Copyright by
Saad Bin Qaisar
2009
Dedicated to the memory of Dr.Randy Pausch @ Carnegie Melon
University who played such a vital role in helping me understand time
management principles.
Taught man that which he knew not. (The Clot : 05)
vi
ACKNOWLEDGMENTS
This dissertation, like any other manuscript, could not have been possible without
active support of a large number of people who helped me to make it a reality.
Thanks to my dissertation advisor, Dr. Hayder Radha for providing me right mix
of guidance and academic freedom that helped me tremendously over the years to
grow as a researcher in Electrical Engineering. His insights and suggestions have
contributed greatly to this dissertation. I would also like to express my gratitude to
my dissertation committee members for their valuable comments that assisted me in
improving the quality of the dissertation.
Special thanks goes to my labmates who had been so supportive throughout my
stay at WAVES Lab. To Shirish Karande with whom I had very fruitful discussions
that assisted me in shaping my basic approach to problem solving. To Kiran Misra
who assisted me during problem formulation. Usman Ilyas whose wits and humor adds
ﬂavor to each and every day at WAVES. And to Rami Halloush, Sohraab Soltani and
‘N ima’ whose presence adds value to our research group.
My family had been a constant support throughout the long and challenging phase
of completing this dissertation. They provided tremendous support without which
I won’t be where I am, today. My father Qaisar who, with his limited resources as
vii
a school teacher, supported and ﬁnanced education for three girls and a boy who
are leading successful lives today as doctors and engineers. To my mother Yasmin
(Jasmine) who spent sleepless nights praying for my success, providing meals to me
in my study so that I had more time to focus on next exam or next challenge in
my life and instilling in me fundamental traits that helped me shape into a ‘better
person’ each passing day. Both my parents made countless sacriﬁces to ﬁnance my
education. They counted every single day as I had been away from them, ﬁrst for
ﬁve years during high school and then again, for ﬁve years during graduate school.
I am fortunate to have such wonderful siblings in form of my sisters Uzma, Irum
and Fariha who have always been sincere wellwishers for my success. And I won’t
forget to thank my surrogate mom, Dr.Colleen Vallad Hix who did not let me feel
the absence of all my family members as I switched from one class to next, one paper
to another.
My gratitude goes to National University of Sciences and Technology (NUST) and
Higher Education Commission, Pakistan who ﬁnanced my graduate studies through
their fellowship programs that have enabled so many students like me to attain higher
education at centers of excellence, worldwide.
Since the completion of this dissertation marks the end of twenty four years of my
student life, I also owe thanks to my high school teachers who were instrumental in
my success. My house masters Rashid Husseini & Abdul Qayyum and my teach
ers Mr.Ashfaq & Imtiaz Kassana(late) at Cadet College Hasan Abdal who worked
feverishly in carving out various aspects of my personality.
Special thanks goes to Suzanne Shoemaker, a senior training specialist @ Emergent
viii
BioDefense for teaching me believe in my abilities . To Carol Gould who had been such
a great host during last one year of my dissertation writing. To my friend, Khawar
Khurshid with whom I shared ups and downs of ﬁrst three years of my stay in United
States. And to my students whose bright faces, will to progress and ability to excel
on receiving ﬁne mentoring gave me my best moments in academia. And lastly, to
my friend Sally McClintock, who, through her creation LATTICE, was instrumental
in providing me a base which added so much to my insight on a land that was foreign
to me yesterday and a second home, today.
ix
TABLE OF CONTENTS
LIST OF TABLES .............................. xiii
LIST OF FIGURES ............................. xiv
1 Introduction ................................ 1
1.1 Processing Within the Network ..................... 2
1.1.1 Motivation for this Work ..................... 3
1.2 Overview of Contributions ........................ 3
1.3 Organization ............................... 5
2 Background and Previous Works ................... 7
2.1 Wireless Sensor Networks ........................ 8
2.2 Binary Symmetric Channel ........................ 9
2.3 Previous Work .............................. 11
3 LDPC Statistical Model ......................... 13
3.1 LDPC Codes ............................... 14
3.2 Statistical Model ............................. 15
4 Centralized Processing Allocation ................... 19
4.1 Problem Formulation ........................... 20
4.2 Optimal Progressive Error Recovery Algorithm ............. 23
4.3 Fairness .................................. 25
4.3.1 Bounded OPERA (OPERAbound) ............... 26
4.3.2 Rate Compatible OPERA (OPERArc) ............. 28
4.3.3 OPERA with Power Control ................... 29
4.4 Simulation Setup ............................. 29
4.5 Results ................................... 31
4.5.1 Endtoend vs OPERA for a Line Network ........... 31
4.5.2 OPERA with Multiple Flows .................. 32
4.5.3 Random Assignment Vs OPERA ................ 35
4.5.4 OPERA with fairness ....................... 36
4.5.5 OPERA with Power Control ................... 41
5 Distributed Processing Allocation ...................
5.1 Pairwise DOPERA ...........................
5.1.1 Pairing ...............................
5.2 Local Minimization Problem .......................
5.2.1 Warm Start and Algorithm Convergence ............
5.3 Results ...................................
5.3.1 DOPERA for a Pair .......................
5.3.2 Multiple ﬂows DOPERA ....................
6 Progressive Error Recovery with Path Diversity ..........
6.1 Introduction and Motivation .......................
6.2 Background ................................
6.2.1 Directed Diffusion of Interest ..................
6.3 MultiPath Distributed Reliability Framework .............
6.3.1 Phase I: Data Partitioning ...................
6.3.2 Phase II: MultiPath Distributed Iteration Assignment
6.4 Simulation Setup .............................
6.5 Results and Discussion ..........................
7 Application: Still Images ........................
7.1 Preliminaries and Motivation ......................
7.2 Simulation Setup .............................
7.3 Results and Discussion ..........................
8 Application: Wireless Video ......................
8.1 Introduction ................................
8.2 Background ................................
8.2.1 Video Coding Techniques ....................
8.2.2 Multipath Transport (MPT) ...................
8.3 MultiPath MultiStream Distributed Reliability ............
8.3.1 Prioritized Data Partitioning ...................
8.3.2 Path Assignment .........................
8.3.3 Distributed Progressive Error Recovery .............
8.3.4 Unequal Error Protection ....................
8.4 Simulation Setup .............................
8.5 Results ...................................
9 Conclusion and Future Work ......................
APPENDICES ................................
Appendix: A ..................................
xi
43
44
46
47
48
49
50
51
55
56
57
57
57
58
60
62
69
75
77
77
78
79
80
8O
81
81
82
83
BIBLIOGRAPHY
xii
LIST OF TABLES
8.1 H.264 Encoder Parameters ........................ 83
1 Coefﬁcients oz(e.,;nd),ﬁ(emd),ry(eind),w(eind) ,fmin = 0.01, em” = 0.08,
[max = 150, R = 0.50,A(6) = 0.20766 + 0.27192 + 0.52291 ....... 94
2 Coefﬁcients a(e,nd),B(eind),7(emd),w(emd) ,emm = 0.01, 6mm; 2 0.08,
[max = 150, R = 0.51, A(6) = 0.20796 + 0.27102 + 0.52261 ....... 95
3 Coefficients a(eind),ﬁ(emd),7(emd),t/J(emd) ,emZn = 0.01, 6mm; 2 0.08,
imam = 150, R = 0.52, Me) = 0.20796 + 0.27162 + 0.52291 ....... 96
4 Coefficients a(€ind),ﬁ(emd),7(emd),t/)(emd) emm = 0.01, 6mm; = 0.08,
Imam = 150, R = 0.5, PEG (3,6) Regular LDPC ............ 97
5 Coefﬁcients (1(6ind),ﬁ(€ind)a’7(€ind),¢(€ind) ,emin = 0.005, em” =
0.08, 1me = 150, R=0.569,A(6) 20.20766+0.27162+0.52261 . . . 98
xiii
2.1
2.2
3.1
3.2
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
LIST OF FIGURES
A wireless Sensor Network ........................
A binary symmetric channel with error probability 6 ..........
Bit Error Rate as a function of Decoding iterations and Channel Error
probability for a rate PEG (3,6) regular LDPC code with 6min = 0.025
and em“; = 0.07 .............................
Root Mean Square Error vs Decoding Iterations for proposed statistical
model ...................................
A Multi—hop line network .........................
Selection of Next Optimal Point [D1, I‘(I)1,E] for Dynamic Program
ming algorithm ..............................
A wireless sensor network with tree topology ..............
Progressive decrease in parity for a multihop WSN ..........
Endtoend vs OPERA for a Line Network ...............
Optimum curves for Expected Bit Error Rate vs. Energy spent for
OPERA with varying network size ...................
OPERA vs Random Iteration assignment ................
OPERAbO’LLTLd With per nOde a)lcap : 300 and b)lcap = 30 ......
OPERAbound With [cap I 30 and lcap : 25, RN : 0.50 ........
10
16
17
21
24
27
29
32
35
37
38
OPERA vs OPERATC for a) RN2 = 0.51 and b) RN2 = 0.51,RN3 = 0.52 39
OPERAbT‘C With RN2 : 0.51 [cap = 30, [cap = 60 and RN2 : 0.51,
RN3 = 0.52, [cap : 60, leap = 90 .....................
xiv
4O
4.12 OPERA vs 1) OPERATC for a) RN2 = 0.51 and b)RN2 = 0.51, RN3 :
5.1
5.2
5.3
5.4
5.5
6.1
6.2
6.3
7.1
7.2
7.3
0.98mW,PN3 = 0.96mW b)PN1 = ITTLWJDN2 = 0.98mW :PN3 =
0.96mW ,RN2 = 0.51, RN3 = 0.52 ....................
DOPERA Pairwise iteration assignment ................
Expected Bit Error Rate vs Energy for DOPERA ...........
Processing Budget vs Functional Evaluations of D for D—OPERA
Processing Budget vs Algorithmic Runs .................
DOPERA vs OPERA for Multiple Flows ...............
A multihop wireless sensor network with multiple paths to destination
node ....................................
MDR vs endto—end for I‘(l—),Da,Tp1 = 4, I‘(—),m,n,~p2 = 6 and I‘(—),Da,,.p3 =
8 , em, = 0.1125,0.1175, 0.1190 .....................
MDR vs end—to—end for i) I‘(l)pm,.p1 2: 4, F(l)pairp2 = 4, I‘(l)pa.,,.p3 = 4
— — — 
ii) P(l)pairp1 = 4, P(l)pairp2 = 6: P(l)pairp3 = 8 iii)r(l)pairp1 = 6)
F(l)pairp2 = 8, F(l)pairp3 = 10, em = 0.1190, 6,,2 = 0.1364, 6,,3 =
0.1190 ...................................
Average PSNR for DOPERA with I‘(l)pair = 6 and endtoend for
R = 0.5 LDPC encoded JPEG2000 image ...............
JPEG2000 encoded ‘boats’ image with egg 2 0.14(clockwise from left)
i original image after source encoding ii endto—end channel coding
iii OPERA with r(z)b,,dge, = 6 ivDOPERA with r(l)pa,,. = 6
JPEG 2000 encoded Lenna image with PERA and DOPERA for a
pair decoding budget of 6 iterations R = 0.5 ..............
XV
41
46
50
51
52
56
63
64
70
71
72
7.4
8.1
8.2
8.3
8.4
JPEG2000 encoded ’lenna’ image with (clockwise from left) i original
image after source encoding ii endtoend channel coding with e = 0.07
iii PERA with E = 0.18 ivDOPERA with 6 = 0.143 .........
Multi—Path MultiStream reliability architecture for video transmission
in Wireless Sensor Networks .......................
MMDR vs endto—end transmission with R = 0.5,K = 4,N =
4,r(z)pa,,. :2 8 206a,. = 0.12 b)ea,, = 0.125 ....... . .........
Frame 2(P) for Foreman QCIF sequence ................
Average YPSNR for both MMDR with I‘( )mir = 10 and EndtoEnd
for R = 0.5 LDPC encoded H.264 video. ................
xvi
73
85
86
CHAPTER 1
Introduction
This monograph investigates theoretical and practical aspects of data reliability in
energy constrained Wireless Sensor Networks through processing within the network.
1.1 Processing Within the Network
In a multihop Wireless Sensor Network (WSN), reliable delivery of information to
the base station is of prime importance for many applications. In many wireless
sensor networks, such as machine monitoring and vehicle detection networks [4], the
actual data needs to be transferred with an extremely low probability of error. End
to—end Forward Error Correction (FEC) and retransmission based schemes prove too
costly for energy constrained sensor nodes [4]. In this work, we propose a more
practical approach that is based on optimally distributing iterative channel decoding
over sensor network. In such a paradigm, the guarantee with which the base station,
or collector, gets the data from a sensor is a function of the processing within the
intermediate nodes between source and destination (innetwork processing [38]).
“Full processing” and “forwarding” represent two extremes of in network process
ing. Full processing implies complete decoding and re—encoding the information‘sent
by the source without considering any complexity or delay constraints, thus achieving
the channel capacity. Under forwarding, each intermediate node is only allowed to
forward the received information without any processing thus signiﬁcantly reducing
the achievable data rate (assuming no path diversity). Most of the WSN applications
have complexity or delay constraints and full processing may not be feasible. “Partial
processing” provides an intermediate ground between forwarding and full processing.
Allowing intermediate link nodes to perform ﬁnite complexity processing achieves a
signiﬁcant portion of the ultimate capacity in fairly noisy networks [38].
1.1.1 Motivation for this Work
Partial recovery from errors at intermediate sensor nodes has not been studied thor
oughly, and probably no work has been published in this area (to the best of our
knowledge). A related context was mentioned by Fragouli et al. who discussed the
beneﬁts that can be achieved due to ﬁnite length processing at intermediate nodes [38].
Thus, motivated by achieving data reliability in sensor networks while maintaining
energy efficiency, we study progressive recovery of errors in WSNs through partial
decoding at intermediate nodes.
1.2 Overview of Contributions
This monograph makes several research contributions: a versatile reliability frame—
work for Wireless Sensor Networks that provides error robustness to the data by par
tial processing of LDPC encoded data, a statistical model for variation of errorrate
with decoding iterations for LDPC codes, novel algorithms that form corner stone of
processing assignment within the network: both in centralized and distributed fashion
and a fairness based framework that ensures maximization in network lifetime using
a novel rate compatibility structure.
We present an architecture that distributes processing over the multi—hop network
such that resulting bit error rate is minimized at the destination node. In this context,
we present a centralized processing allocation algorithm (OPERA) that assigns iter
ations to individual nodes such that network throughput is maximized with minimal
expenditure of energy within the network. We cast the problem of optimal processing
within the network as rate distortion optimization and employ dynamic programming
to reach the solution. We use iteratively decodable Low Density Parity Check codes
to show efficiency of our scheme. We present a statistical model for variation of error
rate after each LDPC decoding iteration. The model is vital for the partial process
ing setup where information about error rates at the end of a prescribed number of
iterations is critical for optimal distribution of the iteration budget.
We not only present iteration assignment algorithm, but also fairness based frame
work that is proportionally fair such that sensor nodes with fewer energy resources
spend lesser computational and transmit energy than those that are resource rich.
Precisely, we introduce two enhancements for the centralized iteration assignment
technique. A rate compatible version that uses systematic puncturing of LDPC codes
to achieve fairness, and a ﬁnite processing based bounded version that puts a com
putational upper bound on each node in order to achieve both fairness as well as
network lifetime maximization.
Though OPERA provides a progressive reliability framework, it assumes a central
processor with complete topological knowledge of the network including the associated
link error rates and separation between the nodes. Such global knowledge may not
be available in more aggressive sensor network deployments where the network is
remotely deployed, and left unattended afterwards [35]. Therefore, motivated by
aforementioned facts and the centrality of OPERA, we further investigate provision of
reliability in a distributed fashion over the end—toend path. We propose a Distributed
Progressive Error Recovery Algorithm (DOPERA) that recovers errors for a W SN
in a distributed manner. Nodes collaborate, in pairwise fashion, to distribute the
progressive decoding budget. We discuss the convergence properties of the proposed
scheme and ways to put least burden on the individual nodes in terms of algorithm
computational overhead using warm start.
We investigate the performance of proposed framework with path diversity and
selective processing budgeting based on signiﬁcance of data to be transmitted over a
given link. We investigate how variation in processing budget allocation to pairs of
nodes affects the overall network performance at the destination node.
We consider two applications of the proposed framework: one to still images and
second to video streams. Firstly, we show the performance of proposed framework
when used in conjunction with still images for transmission of visual content in vi
sual sensor networks. Secondly, we use the pathdiversity framework to develop an
architecture for reliable delivery of video content within a sensor network. We show
the performance gains that can be achieved using the proposed framework.
1.3 Organization
The rest of the monograph is organized as follows. ’We formulate the problem in
Chapter 2. Chapter 3 provides background on LDPC codes and relevant theorems,
ratecompatible LDPC coding and presents a statistical model for variation in channel
error probability with number of decoding rounds for a given LDPC code. Chapter
4 discusses the proposed approach for progressive error recovery using in—network
processing in a centralized fashion and provides a fairness based architecture, whereas,
we present a distributed architecture for processing assignment in Chapter 5. Chapter
6 discusses the proposed progressive error recovery framework in conjunction with
path diversity. Chapter 7 and 8 apply the proposed framework to both still images
and video data. We give the future directions accompanied by conclusion in Chapter
9.
CHAPTER 2
Background and Previous Works
In this chapter, we provide background to fundamental concepts that have been
used throughout this monograph. Firstly, we provide a brief overview of Wireless
Sensor Networks and associated research challenges.
At the end, we talk about previous works on reliability in wireless sensor networks.
2.1 Wireless Sensor Networks
Recent advances in micro—electro—mechanical systems (MEMS) technology, wireless
communications and digital electronics have enabled the development of low—cost,
low power, multifunctional sensor nodes that are small in size and have an ability
to communicate over short distances [4]. A traditional sensor network may consist
of numerous sensor nodes spread over a large geographical area. A unique feature of
sensor nodes is their ability of cooperatively undertaking certain tasks. Nodes use
their processing capabilities to locally carry out simple computations and transmit
only the required and partially processed data.
Sensor networks enjoy a vast range of applications including those in surveillance,
monitoring, intelligence, healthcare, military and product quality assurance. Amore
recent development is the conception of wireless multimedia and visual sensor net
works that promise to add multimedia carrying capabilities to sensor nodes that have
limited power, computational capacities and memory [3]. The realization of such a
network necessitates overcoming various challenges including new architectures for
collaborative, distributed and resource—constrained processing that allow for reliable
delivery of multimedia content to the destination node. This monograph aspires to
[a] Sensor Node
Q Base Station
Figure 2.1. A wireless Sensor Network
overcome few of these challenges by proposing an energy efficient reliability framework
for sensor networks.
2.2 Binary Symmetric Channel
A binary symmetric channel is a communications channel model used in coding and
information theory. In this channel model, a transmitter intends to send a bit to
the receiver and receiver wishes to receive it. In most of the cases, it is assumed
that bit would be transmitted correctly, though, at times, it would be ﬂipped with a
small ’crossover error probability’ 6. A binary symmetric channel is used frequently
in information theory due to its ease of analysis.
Figure 2.2. A binary symmetric channel with error probability 6
As shown in Figure 2.2, a BSC can transmit only one of two symbols, say a 0 or 1. A
binary symmetric channel with crossover probability 6 is a channel with binary input
and binary output and error probability 6. If X is the transmitted random variable,
and Y is the received variable, then the channel is characterized by the conditional
probabilities:
PT(Y=0X=0) = 1—6
PT(Y = 0X =1) = 6
Pr(Y =: 1X = 0) = e
PT(Y =1X =1) 2 1— 6 (2.1)
where 0 g 6 31/2.
10
The capacity of a binary symmetric channel is 1 — H (e), where H (e) is the binary
entropy function [8] .
2.3 Previous Work
Few efforts have been made for energy efﬁciency based reliability in sensor networks
using forward error correction. Shih et a1. [35] use convolutional codes and their
punctured derivatives. They conclude that for convolutional encoding and Viterbi
decoding, on endtoend coding should be used above error probability greater than
as transceiver power dominates at high probabilities of error.
Sankarasubramaniam et a1. [30] study the energy efficiency based packet size op
timization in sensor networks and examine the effect of error control on energy efﬁ
ciency. They show that some FEC coding schemes can improve the energy efﬁciency of
a communication link, several others, including retransmissions are energy inefﬁcient.
They give a performance comparison between binary BCH codes and convolutional
codes concluding that the binary BCH codes outperformed the best convolutional
codes by almost 15%. Their work highlights the fact that number of FEC parities
signiﬁcantly impacts energy efﬁciency, more so than the decoding energy consump
tions.
Sartipi et a1. [31] presented a framework in which they consider combined source and
channel coding with LDPC codes for sensor networks. A system with forward error
correction (F EC) can provide an objective reliability while using less transmission
power than a system without FECNVe propose to use LDPC codes for F EC. They
11
show that wireless sensor networks using LDPC codes are almost 45% more energy
efﬁcient than those that use BCH codes, which were shown to be 15% more energy
efﬁcient than the best performing convolutional codes.
All these works are based on endtoend error recovery thus catering for worst
case channel conditions. In terms of power consumption, transmitting an additional
single bit of data is much costlier than the instructions used for computations in a
sensor node [18]. For example, in a recent study, a single bit of data transmission has
been shown to be equivalent to 2000 computational instructions executed in a sensor
node [12]. Thus, energy tradeoff between communication and computation makes a
case for processing the data inside the network rather than simply transmitting the
sensor readings. Therefore, for improved reliability of data from a source node to the
collector and conservation of energy, innetwork processing can be highly beneﬁcial.
The proposed progressive error recovery framework ensures this by partial decoding
of packets and hence enhancing the data reliability at the destination with introduc
tion of minimal complexity as compared to endtoend channel coding. In addition,
keeping in view the energy efﬁciency of LDPC codes in sensor networks [31], the pro
posed paradigm uses them to achieve enhanced throughput while maintaining energy
efﬁciency.
12
CHAPTER 3
LDP C Statistical Model
13
3.1 LDPC Codes
LDPC codes have gained considerable attention due to their near capacity perfor
mance. Gallager provided an algorithm for decoding of LDPC codes that is near op
timal [10]. The algorithm iteratively computes the distribution of variables in graph
based models, and comes under different names/variations including Sum Product
Algorithm (SPA), Belief Propagation Algorithm (BP), or more generally, Message
Passing Algorithm (MPA). Richardson et a1. [29] [27] give concentration theorem for
LDPC codes.
Theorem 3.1.1 ( LDPC Concentration Theorem) Let Pena) be the expected
fraction of incorrect messages which are passed in the lth iteration of LDPC de
coding, where expectation is over all instances of the code, the choice of the message
and realization of the noise. For any 6 > 0 , the probability that the actual fraction
of incorrect messages which are passed in the lth iteration for any particular such
instance lies outside the range converges to zero exponentially fast in n to the mean
of the ensemble.
Thus, for a sufﬁciently large n, we can pick up any LDPC code and the results
achieved would have small deviation from the ensemble mean.
Although the concentration theorem provides a highly critical and fundamental
observation regarding the performance of LDPC codes, the theorem does not provide
a precise estimation model of the performance of LDPC decoding at the end of an
arbitrary lth iteration. Such precise estimation is crucial for the proposed OPERA
framework; in particular, when optimizing the distribution of LDPC decoding it
14
erations among sensor nodes, a precise estimation for LDPC decoding model (as a
function of the number of iterations) is required to provide the desired optimization.
Consequently, before proceeding, we show a set of simulations that enable us to de
rive an estimation model for the performance of LDPC decoding as a function of an
arbitrary lth decoding iteration.
For the simulations, we employ a degree seven density evolution optimized irregular,
Progressive Edge Growth(PEG) based LDPC codes [15] with variable node degree
polynomial A09) 2 0.20796 + 0.27192 + 0.52201, message length k = 1024 bits. The
results obtained are equally valid for any randomly picked LDPC code. We use a log
domain Sum Product Algorithm (LSPA) [10] for iterative decoding of the code which
has advantages in terms of implementation, computational complexity and numerical
stability [42] which is critical in the context of sensor networks.
3.2 Statistical Model
Figure 3.1 shows the expected bit error rate obtained as number of decoding iterations
are increased for different channel error probabilities averaged over 1000 runs for an
LDPC code, operating below code capacity. We see a sharp decrease in bit error rate
as decoding iterations are increased. In fact, the decrease is exponential in nature.
Based on the above observations, we develop an exponentially decaying statistical
model for the variation of bit error rate with decoding iterations. This model is then
used in subsequent chapters for our proposed progressive error recovery mechanism.
Equation (3.1) expresses the relationship between the estimated bit error rate f for
15
006
Bit
Error
Rate
w
WWW
30 40 50 60 73 an 90
Decoding Iterations
Figure 3.1. Bit Error Rate as a function of Decoding iterations and Channel Error
probability for a rate PEG (3,6) regular LDPC code with 6min = 0.025 and 6mm; 2
0.07
a given channel error probability and the number of decoding iterations for our code
as
fetid, i) = arenaeﬁtmdﬂ + wease’i'ivnd” (3.1)
Where 6mm 3 6 S cm“, 0 < l S Imam , is the corresponding index value with
respect to 6mm and a(e,nd),ﬁ(ei,,d),7(emd) and Il’(€ind) are the statistical coefﬁcients
[21].
16
Figure 3.2 gives the root mean square error in the proposed statistical model. It
is evident from the ﬁgure that the statistical model provides a close enough approxi
mation of the LDPC error rate variation with number of iterations.
x10—4
14 1. I l r r 1 I. I
1 ..............................................................
10.. ..
Lu
g 8 ................. .
a:
6.... ...................................................
4 
2 . . . i g . . .
1 2 3 4 5 6 7 8 9 10
Decoding Iterations
Figure 3.2. Root Mean Square Error vs Decoding Iterations for proposed statistical
model
Therefore, as evident from equation (3.1) and LDPC decoding curves, signiﬁcant
enhancements in performance can be achieved as the number of LDPC decoding
iterations are increased at the receiver provided the channel error probability is below
the achievable performance bound [6] for the ensemble of codes. This result can be
used to formulate an innetwork processing framework to maximize the achievable
17
reliability at the destination.
18
CHAPTER 4
Centralized Processing Allocation
19
For the centralized processing distribution problem, we are looking for an optimal
tuple [D, I‘(l),E] such that F(l) S Falbudget i.e. a minimal overall bit error rate that
meets the budget constraint. The problem can be viewed as one that allocates the
overall iteration budget F(l) budget among all nodes in the network such that distortion
is minimum.
The computational complexity of optimally mapping the iterations to the network
is high, as NT M region consists of all possible operating points obtained by choosing
all possible combinations of iteration assignments within the budget constraint. The
hull of the NTM region would provide the desired optimal solution. We ﬁrst solve
the problem for a single path line network, which can then be mapped to the entire
network.
4. 1 Problem Formulation
A multihop wireless channel can be represented as a cascade of channels (Figure 4.1).
Consider a line network with N nodes in cascade. We make following assumptions
regarding the network:
1. The nodes in the network are quasistationary
2. Each node is capable of decoding the received messages
3. All nodes have equal signiﬁcance and similar capabilities in processing and com
munication
4. Nodes are left unattended after deployment
20
6 6 0
W”"‘:O’a""ﬁt‘sﬁ
Figure 4.1. A Multihop line network
5. Each node has preset number of transmission power levels and at a given time,
all nodes are transmitting at same power level.
6. Nodes transmit to a central coordinator over a multihop network
The links between the nodes are assumed to be binary symmetric with each node
transmitting at power level PT per bit. Relay nodes are allowed not only to forward
the incoming information, but also to process it. In order to obtain channel error
probability for a binary symmetric channel (BSC), the general expression for Signal
to Interference Noise Ratio (SINR) can be given as in Equation (4.1):
Pr
SINR:
PA+ZPint
(4.1)
where PA is the ambient noise power, and Pint is the interference power of any
concurrent transmissions elsewhere in the network. Sources of ambient noise may
include other devices operating in the same frequency band or other networks co—
located with the WSN. Let T9; be the set of all the transmitting nodes in the network
and {nut 6 Tx} be the subset of nodes simultaneously transmitting over a certain
subchannel, with transmit power Pt for each node. Then the SINR at node njfor a
transmission from node ni,i 6 T; can be calculated as in [14]:
21
P.
S I N R = P (4.2)
PA + Zteryéi W
Where d(ni, nj) is the separation between n, and nj, and a > 2.
If Q(;1t) Zﬁx foo eﬂu/2 du, then the channel error probability 6 as described
in [26] is:
e(n,)— — Q((\/2 (SINR(n,))) (4.3)
The source node no generates k message bits which are encoded using a rate R code.
The resulting codeword is transmitted over the ﬁrst link with error probability 61.
Node 711 performs [1 LDPC decoding iterations and the bit error rate in the resulting
packet is a function of 61 and l1:
61, = f(€1,11) (44)
After partial processing at the second node, the error rate in the resultant packet is:
I
62’ = f(€2.l2) * 61 (45)
where 61 * 62 : 62(1 — 61) + 61(1 — 62) For the cascade line network, we deﬁne the
total number of decoding iterations in the entire network as:
Nl
' = Z 13 (4.6)
j=1
where lj is the number of decoding iterations at node nj.
For N hops in cascade, the overall distortion measure D can be expressed as:
D = f(f(f(f(€1,l1)* €2.12) * €jalj) * €N—1»lN—1) * 6N (47)
22
For an endtoend path with E = 61, E2, . . . ,ej, . . . , €N—1 and given iteration budget
F(Z)budget1 we intend to ﬁnd an iteration assignment vectorl = l1, l2, ..., lj, . . . , lN_1 in
such a way that the net throughput is maximized at the final destination. Conversely,
D(F) is minimized. We refer the tuple [D, F(l),E] as Network Throughput Measure
(NTM).
The problem can be seen as a budget constrained allocation problem, such that D
is minimized subject to constraint I‘(l) S Palbudget' From the constraint highlighted
above, our problem becomes similar to minimizing a distortion measure given a budget
constraint under a rate distortion framework. Therefore, an algorithm providing NTM
operating point with minimum distortion D while remaining within budget constraint
is desirable.
4.2 Optimal Progressive Error Recovery Algo
rithm
To find out the optimal hull of NTM region, we employ a dynamic programming
approach similar to the method used in determination of the RD region for optimal
quantizer design [33]. The algorithm stated is greedy in nature and it is possible
that it may not ﬁnd the optimum tuple [D, F(l),E], though it does provide optimal
solution under various practical scenarios [24] [33] [36].
The starting point of our algorithm is the case when no iterations are assigned to
any intermediate nodes. Hence, D is maximum and F(l) minimum. Thus the tuple
23
[D0, I‘(l)0, E] has DO closest to the D axis. The algorithm then adds a single iteration
to intermediate nodes, one by one in a greedy fashion, and selects the node where the
minimum D is achieved. This provides the next operating point [D1, F(l1),E]. The
procedure is repeated till I‘(l) S Palbudget is satisﬁed and all the iterations are now
assigned.
.i [002), “has, 3.]
' [D‘°'”,I‘(I)‘°’”,E]
[0' , r(1’)',g] = [D‘°'”,l‘(l)‘°'”, 5]
4
r(1’)
Figure 4.2. Selection of Next Optimal Point [D1, I‘(l)1,E] for Dynamic Programming
algorithm
Thus, the algorithm maximizes the separation between optimal point achieved in
the prior run D‘ and the new points D+ obtained in the current run for all interme—
diate nodes on the path. This corresponds to maximizing the gradient between the
two points.
24
Mathematically, we have:
_ — _ +
l = arginaxj=1.N_1 [ P. D_+ (4.8)
W ) Wj)
where, we take I‘(l—) — F(l+) = 1.
For a multipath multihop network with nodes transmitting to a central coordinator,
iterations are assigned to individual paths and the results are averaged over all the
paths after decoding at base station to obtain expected bit error rate.
4.3 Fairness
Any discussion about performance of a rate control scheme must address the issue of
fairness, since there exist situations where a given scheme might maximize network
throughput, while denying access to some network nodes. Fairness is particularly
a concern in WSN scenarios where network lifetime maximization is a prime design
objective. In a typical WSN, after collecting the data of interest, the sensors must
reachback [5] and transmit the information to a single receiver. This may introduce
higher complexity at few nodes closer to the receiver, than others, considering a
network with multiple flows across sets of nodes that may not necessarily be disjoint.
Any fairness framework for rate maximization scheme should thus consider both,
reach—back and network lifetime maximization, in consideration.
Though OPERA maybe optimal in throughput sense, it may not necessarily be fair
to nodes that have greater traffic loads primarily because of their closer vicinity to
the base station and greater number of ﬂows passing through them leading to the
base station. In other words, we do not intend to aggravate the sensor reachback
25
problem [5]. A fairness based scheme is thus greatly desired that addresses these
issues. Such a scheme is particularly important in remote deployments of the net
work where network lifetime maximization is a prime concern. Thus, in this section,
we propose a version of OPERA that is proportionally fair such that sensor nodes
with lesser energy resources spend lesser computational and transmit energy than
those that are resource rich. Precisely, we propose two enhancements for OPERA. A
rate compatible version OPERATC that uses systematic puncturing of Low Density
Parity Check codes to achieve fairness, and a finite processing based bounded ver
sion OPERAbound that puts a computational upper bound on each node in order to
achieve both fairness as well as network lifetime maximization.
4.3.1 Bounded OPERA (OPERAbound)
We introduce an upper ceiling to the processing a node can perform for each flow
passing through it based on maximum processing capacity [cap of the node. Since
most widely used sensor network routing algorithms are different forms of shortest
path routing algorithm, we consider the routes from individual nodes to the base
station forming a tree rooted at the base station [16]. We distribute the processing
capacity leap based on the number of ﬂows passing through the node. With the
assumption of all the nodes transmitting simultaneously back to the base station, the
number of ﬂows passing through a node is simply the depth of subtree rooted at
that node. Thus, greater the depth, greater the number of ﬂows passing through the
node, and lower is the number of iterations it can perform per ﬁow. Therefore, per
26
flow iteration budget for jth node is Simply 1ij (lge t = lcap/stub, where, stub IS the
number of nodes in the subtree for that node. For the scenario where stub > leap,
only leap flows are randomly chosen and no decoding iterations are allocated to rest
of the ﬂows.
Base
Station
Figure 4.3. A wireless sensor network with tree topology
Figure 4.3 elaborates this further. Consider two reference nodes A and B in a
multihop network with all nodes transmitting their trafﬁc back to the base station.
The subtree, rooted at A has six child nodes whereas, B has only one. Thus, each flow
passing through A gets 1 / 6th the processing capacity of A, whereas, single flow passing
through B gets full processing capacity of B, ensuring network lifetime maximization
by more just usage of network resources.
27
4.3.2 Rate Compatible OPERA (OPERAM)
OPE RA"; addresses sensor reachback problem with the introduction of network par
titioning. For a multihop WSN with N nodes, we form a partition {N33}er based
upon their proximity to the base station, where I belongs to set of integers. The
partitions thus formed satisfy following two conditions.
(1:61
NxﬂN§=,{x,y}EI,a:7éy (4.10)
As illustrated in Figure 4.4, we start by assigning rate R N1 mother code to partition
N1. Moving further down over the endtoend path, rate RN33 punctured codes
are assigned to each partition Nx till we reach the destination node. The resulting
distortion over the endto—end path is thus given as:
D =fN;,;(N_1)(fo(N—2)(fo(j—1)(fN$1 (61’ ll) * 62’ [2) (4.11)
* ...6j,lj) *"'€N—1’lN—l) * 6N
where, f Nltjkj, l j) is the bit error rate achieved at jth node belonging to partition
N1 after lj decoding iterations with channel error probability ej. The distortion
obtained is used in Equation (4.6) to get the optimal iteration assignment I.
It is pertinent to mention here the tradeoff in design of network partitions. If the
rate is increased signiﬁcantly through parity drop with respect to primary rate, then
the message may not remain decodable at the destination node. On the contrary,
If very few bits are dropped, then we are not fair with resource constrained nodes.
Thus, a balance should be maintained between performance and energy tradeoff.
28
@ :Q
:3: :1: L l l i in]
07>0.o+,+0 syn6076
8, 1' 8]. 1+1 8N4 N
Figure 4.4. Progressive decrease in parity for a multihop WSN
4.3.3 OPERA with Power Control
PER/1pc addresses the fairness issue by variation in transmit power for individual
nodes as information reaches closer to the destination node. We use network par
titioning in a similar fashion as for ratecompatible PERA. We start by assigning
transmit power PN1 to partition N1. Power levels PNJ; are assigned to each partition
NJ; as we move further down over the endto—end path till we reach the destination
node. The resulting distortion at the destination node can be given as in (11) which
is used in (9) to obtain the desired iteration assignment.
4.4 Simulation Setup
For the proposed OPERA scheme, we assume that if e < 6mm , only one iteration,
is sufﬁcient to completely decode the LDPC code, on average, a behavior confirmed
29
from the trend in Figures 3.1 and 7?. and [29]. A node behaves as a forwarding
node if either 6 > em” or no iteration is assigned to it. We set 6mm = 0.01 and
6mm; = 0.08 (See [6] and [29] for tighter bound on 6mm). For a single path, we ﬁx
11061.net = 60 iterations. We take per bit transmit power PT = ImW, per second,
for each node unless speciﬁed otherwise (e.g. in case of power control).
The total energy spent by sensor nodes per packet delivery to the destination node
is the function of computational energy and the transmission energy. We have
Etotal = ETrans. + EComp. (4~12)
where, Ecomp is the computational energy spent per packet for partial processing
within the network and ETrans.iS the per packet transmission energy for endto—end
delivery.
Fossorier et a1. [9] in their work on low complexity LDPC iterative decoding, tab
ulate a comparison of mathematical operations required for one iteration of vari
ous LDPC decoding algorithms including MPA. Assuming each node a sensor mote
equipped with Atmel Atmega128L processor, and 2000:1 ratio between per bit trans
mit energy and computation energy spent per instruction [12], and average number
of ones per column in a parity check matrix of a code from ensemble of (n,)\,p)
LDPC codes [32] as (fol A(9)d6) we provide performance curves for OPERA in
the subsequent section using PEG irregular LDPC codes.
For a Wireless Sensor Network with multiple flows, we consider N nodes spread
over a 107nx10m square grid according to a random distribution, with base station at
30
coordinates (5,5). Transmission range of each node is limited to r = 2m. Since the
most widely used wireless sensor network routing algorithms (DSR, AODV, Directed
Diffusion) are different forms of shortest path routing algorithms, we assume that at
any given time the routes from individual nodes to the base station form a tree rooted
at the base station [16]. We are thus discounting the possibility of using bifurcated
routing i.e. multiple paths from source to destination. Hence, we assume that all
the network nodes sending trafﬁc back to the base station on shortest paths already
established through some routing algorithm.
4.5 Results
4.5.1 Endtoend vs OPERA for a Line Network
We consider 100 instances of a line network for N = 5 with variation in separation
between the nodes. The results achieved are averaged over all occurrences. We
= 0.731 and Rand For
take endtoend maximum and minimum rates R min'
endmax
OPERA, we consider multiple rates ROPER A = 0602,0569. All the results are
averaged over 1000 runs. Figure 4.5 shows the performance comparison between
OPERA and endto—end schemes with average end—to—end equivalent error probability
Eendeq It is essential to note here that both OPERA and endtoend results here
are after decoding at the destination node. For endtoend case, Etotal = Emms
whereas, (12) gives the total energy for OPERA. The results show that OPERA
outperforms endto—end channel decoding with much lesser energy required for a given
31
0.1 1 T . W E . .
. __________ — OPERA R=0.602 i_ ]
o— OPERA R=0.569] i
0.08» ' . j — EndtoEnd
0.0a
0.07;
0.05
0.04»
0.0%
Expected Bit Error Rate
0.021 ,  ~"~
0.01 _§ ....... y __________
16 6 . 7
. . 10
Total Energy J
Figure 4.5. Endto—end vs OPERA for a Line Network
performance.
4.5.2 OPERA with Multiple Flows
Figure 4.6 presents the variation in throughput using OPERA for a network with
multiple ﬂows leading to the base station. The plots show that it is feasible to
optimally tradeoff complexity/energy usage with distortion/ reliability by varying
the assignment of iterations. The two extremes of the ComplexityDistortion curve in
Figure 4.6. represent the performance that is offered when two extremes of innetwork
processing is employed. When we do not conduct any decoding at intermediate
nodes, the accumulation of errors increases exponentially. In such a scenario a large
number of packets eventually received at the collector may have zero or very little
32
0.012 t I 1 t I I t
C OPERA N=50
0 OPERA N=100
0.01  —— OPERA N=150
% 0.008 
a:
r»
0‘]
g 0006— ~
'0
0
‘6
E 0.004 . . ~ 
1
0.002— _
0 1 ﬁ """ . ._
5 5.5 6 6.5 7 7.5 8 8.5 9
Energy J
Figure 4.6. Optimum curves for Expected Bit Error Rate vs. Energy spent for
OPERA with varying network size
information utility. In other extreme when decoding is employed at all or almost all
the intermediate nodes, the data reliability can be increased significantly, but the
energy consumption also increases. Thus, in such an operation mode, even though
the throughput of a sensor network is improved, the network lifetime is decreased.
Our proposed approach allows us to ﬁnegranularly operate at a large number of
intermediate points. Thus in an actual deployment, the operating point can be chosen
in accordance with the current demands of the network. If an important event is being
sensed, we may choose to operate at high in—network processing point, as against that
33
if the network is in more passive state, we may prefer saving energy despite getting
noisy readings.
The results in 4.6 further show that as the number of nodes increase the amount
of innetwork processing required to achieve improvement in reliability reduces. This
can be explained by highlighting that, as the node density increases, the number of
error prone links decrease. Since error recovery is primarily required only due to
the presence of noisy links, decrease in the number of noisy links naturally leads to
reduced requirement of network processing.
The above observation has important implications about adapting the functional
usage of a sensor network through its lifetime. We illustrate our point by way of
an example: Let us say that a network initially composed of 150 sensors demands
a functional usage represented by an error probability of 0.004. To support such a
demand with innetwork processing, we shall have to spend 5.70 Joules. With time as
sensors die the density of sensors reduces; let’s say our density drops to 100 sensors.
At such point if the functional demand is not reduced the amount of energy that will
have to be spent is in fact increased to 6.4 Joules. This increase in energy spending
may setoff a chain reaction eventually leading to the death of a network. Thus, as the
density reduces, it may be essential to adapt the functional demands from a network.
The ComplexityDistortion curves obtained by our analysis can provide important
guidelines on how these demands should be reduced as sensors start dieing.
34
—0— OPERA N=150
+ Random N=150
O)
01
r
A
I
Expected Bit Error Rate
(a)
i
N
n.
.—L
__._.__ .__._____.___._.._...__
i s .
(5.5 5.55 5.6 5.65 5.7 5.75 5.
Energy J
Figure 4.7. OPERA vs Random Iteration assignment
4.5.3 Random Assignment Vs OPERA
We compare the efﬁciency of our iteration assignment algorithm with random assign
ment when the decision to add iteration at a given node over the path is random such
as by tossing a coin. The procedure is repeated until all the iterations are assigned
to an endtoend path. Figure 4.7 shows the efﬁciency of OPERA as compared to
random assignment. The gap between the two curves indicates the enhancement in
throughput we get by progressive iteration assignment through OPERA than ran
domly.
35
4.5.4 OPERA with fairness
Bounded OPERA
Figure 4.8 gives a comparison between iteration assignments for OPERAbmmd with
leap = 300 and leap = 30, respectively, N = 150 and Falbudget = 60 iterations. In
both the cases, we achieve reliable communication after destination node decoding,
though, distribution of iterations is much more fair in the latter without concentration
of processing load on few nodes and leaving the rest with underutilized capacity.
Though, if lcap is further reduced, the path budget may not get fully distributed over
the endtoend paths, thus, deteriorating performance. Figure4.9 highlights this effect
by comparing OPERAbound throughput curves for both [cap = 30 and [cap = 25. A
careful selection of [cap is thus signiﬁcant in achieving throughput gains.
Rate Compatible OPERA
We consider two cases for OPERA“ with variation in network partitioning for
N = 150. Nodes transmit at mother code rate RN1 = 0.5 when they are ei
ther a data originating node or belong to N1. As the code block enters subse
quent network partition, the block is subjected to rate variation as: a)RN23 = 0.5
b)RN2 2 051,ij3 2 0.52.
We set 11051.net = 60 iterations for each path. It is assumed that each node
knows the puncturing rate of the frame it would be receiving. Such information can
be passed once during the initialization phase of the network, when all nodes maybe
communicating at same rate.
36
a
U ' I 0‘ 0 0 OT I 6 0 .I 00 I 1
9» 0 0 ' 0 O I a
t "0 . 'I " 0 I
0 0 4
8‘  ' . 0 0 0 a
0
o 0 I 60 14 . 0
7— A
0 2 0 0 2
6'0 8 7 I 27 ) " 0 0
0 I . on
0 ° ' ' . 60 1
51 o 0 0.
' 0
° 2 o 60 ,0 o
4— 0 
o o  189 178 . a
3 ‘ 6 . "‘/ '0 0 j. _
1 i a 10 11 . 0
0 O
2~ , 0 \. —
o 0
1— ‘ . 0 )0 ' _
g 0 0 o O . ‘
0 1 1 ‘ 1 1 1 1 I . '
0 1 2 3 4 5 6 7 8 9 10
10 I I I l I r
O ‘ I 0 . o I 0
9 . , 0 . .. I 30 O .'
o
8“ . 0 ‘ 6 30 ~
0 30
. ' 20 2‘ . 24
7 . 00 a
o 17 2  11 0° '°
6] 0.... . g. . 2 1,, —..3
l ‘ a
O 0 0 7
5_ 0 : 0 ...... 
0 0 O .l
4» 7 18 o 0 H
0 00 16 I 14 21 I 20
3 0 " o I.
o 0 o 4 20 24 ' 30
2_ 30 ° 0 , '23
. . .. \.~
I o 0 30 .
1—° . o 0 ° . 30 o‘ o" ~
30 o . t
G 1 1 ‘ 1 I 1 1 M m ’ v1 '
O 1 2 3 4 5 B 7 8 10
Figure 4.8. OPERAbmmd with per node a)lcap = 300 and b)lcap = 30
37
x10"
I
__ OPERA bound [cap 25
.... OPERA bow d [cap 30
Expected Bit Error Rate
o . .
5.4 5.6
5.
Energy J
Figure 4.9. OPERAbound with [cap 2 30 and leap = 25, RN 2 0.50
Figure 4.10 shows the performance of OPE RATC as compared to OPERA. We see
that OPERArC consumes lesser energy than OPERA initially. This energy saving is
due to lesser number of transmissions by the nodes closer to destination, though, price
paid is the loss in decoding performance at the destination node. As in—network pro
cessing is increased, OPE RATC approaches OPERA in terms of throughput achieved
for given energy budget with more fair energy distribution. The results also indicate
the tradeoff in using higher coding rates, greater number of network partitions and
throughput, with less energy usage by resource constrained nodes at the cost of some
decrease in performance. Therefore, we can strike a compromise between desired re
38
0.03 ___..._ _1___,___ y _________Tg. mm.“ ,__,..._ ..
, +OPERA 0.5
0.025 —————————————— ~ — — _._ OPERAc 0.5051052]
93
g 0.02..
3
t
LL]
a 0.015
'O l
s !

12 0.01~ — ~ ...............  
LU
0005— 
(53" 5.4 53 5.6 5.7 . . . . 6.3
EnergyJ
Figure 4.10. OPERA vs OPERATC for a) RN2 = 0.51 and b) RN2 = 0.51,RN3 =
0.52
liability level and network energy resources with variation in network partitions and
coding rates.
Bounded Rate Compatible OPERA
Figure 4.11 gives the performance curves for OPERAbrC with variation in leapThe
plots show that it is practicable to tradeoff distortion / reliability with network lifetime
by variation in both the puncturing rates as well as maximum processing individual
sensor nodes can perform. When we have lower leap and higher coding rates, packet
errors may persist despite increase in intermediate node decoding.
In such a scenario, packets eventually received at the collector may have very little
information utility. On the other hand, when [cap is increased and lower coding rates
39
0.03, . . 1 _  :m _. ‘77, ._ _.
] + OPERAbrC R 0.5 0.51 Icap 30
0 025] + OPERA“: R 0.5 0.51 leap 60
' + OPERA)": R 0.5 0.51 0.52 lmp 30 .
+ OPERAbrc R 0.5 0.51 0.52 Icap 60 '
g 002’, , . —.— OPERA)rc R 0.5 0.51 0.52 Icap 90 '
m 1 l 1 r .1
2
LL] 1
a 0.015
s 1
§ i
If] 0.01]:
0.005
(5.3 537' ' f " . . 50.8 " .
Energy (J)
Figure 4.11. OPERAbrC with RN2 = 0.51 leap = 30, leap = 60 and RN2 = 0.51,
RN3 = 0.52, [Cap : 60, (cap : 90
are used in network partitions, data reliability can be increased signiﬁcantly at the
expense of greater energy usage. Thus, in such scenarios, even though throughput
for sensor network is improved, price paid is a reduced network lifetime. The curves
given here provide us the ﬂexibility to select intermediate Operating points. For a real
sensor network deployment, event based operating point selection can be employed.
When a signiﬁcant event is sensed, lower coding rates at intermediate nodes with
higher leap can be used. When the network is inactive, we can increase coding rates
and/ or decrease [cap for enhanced network lifetime.
40
0.03 I I I I I I l I I l
‘ +OPERA 0.5
+ OPERArc 0.5 0.51
0.025 . +OPERAm0.50.510.52 .1
+OPERApc
o +OPERA 0.5051052
‘5 0.025  _ ”9°
0:
5 — ;
LIJ ’. 
g 0.0155 \ ~ 
'O
9 .
0
0 .
0.005— .4 ..
\
'\ \ 1
0 l I l l l \ v _ ; _.
5.45 5.5 5.55 5.6 5.65 5.7 5.75 5. 5.85 .9 5.95
EnergyJ
Figure 4.12. OPERA vs 1) OPERA“; for a) RN2 = 0.51 and b)RN2 = 0.51, RN3 =
0.52, 2) OPERAPC & OPERArcpc for a)PN1 = 1mW,PN2 = 0.98mW,PN3 =
0.96mW b)PN1 = 1mW,PN2 = 0.98mW ,PN3 = 0.96mW ,RN2 = 0.51, RN3 = 0.52
4.5.5 OPERA with Power Control
We use identical partitions for OPERAPC as in OPERA”; with RN = 0.50,PN1 =
1mW,PN2 = 098le and PN3 = 0.96mW. Figure 4.12 compares the performance
of OPERA with OPERAPC. We see that though there are some energy savings using
power control, the price paid is degradation in decoding performance. We further
provide results in the ﬁgure when power control is used in conjunction with rate
compatible puncturing of LDPC codes: OPERATCPC, taking PN1 = 1mW,PN2 =
41
0.98mW,PN3 = 0.96mW/,sz1 = 0.5O,RN2 = 0.51 ,RN3 = 0.52. Again, we see
some power savings though the reliability of information content also suffers. Thus,
based on the application demands 81. network conditions, we can switch between
OPERATCOPERAPC & OPERATCPC to achieve fairness.
42
CHAPTER 5
Distributed Processing Allocation
43
In previous chapters, we presented a scheme that provides progressive reliability
to WSN data as it traverses the multihop network. Though optimal, it assumes
complete topological knowledge of the entire network. Such knowledge may not be
available in realworld sensor network deployments. Thus, we are interested in place
ment of decoding iterations, in a distributed fashion, at the individual relays that
achieves the highest decode and forward rate. Particularly, we are looking for a
distributed progressive error recovery scheme that satisﬁes the following goals:
Maximizes the throughput at the destination node in a distributed fashion
0 Each node performs at least a single iteration
0 Provides a decent approximation to the centralized counterpart: OPERA
0 Minimal transmission and computational overhead on the individual sensor
nodes
0 Makes minimal or no assumptions regarding knowledge of the endto—end path
0 Offers a fair amount of asynchrony in distributing the processing budget
0 Applicable to any iteratively decodable channel code
5. 1 PairWise DOPERA
For the iteration assignment problem, we are looking for an algorithm that does not
require complete network knowledge and works fairly asynchronously to provide max
imum reliability at the destination node. A simplistic approach can be to distribute
44
iteration budget equally among all the nodes. That does not necessarily maximize
throughput, especially, when the variance among individual channel error rates is
high. On the other extreme, giving individual nodes control of their iteration assign
ment values over a domain may result in each node choosing the maximum value
for enhanced throughput which renders the ﬁnite iteration assignment problem ir
relevant. Therefore, we are looking for a scheme that both ensures fair amount of
asynchrony with increased throughput at the destination along with optimal use of
nodes’ computational resources.
We propose a scheme in which nodes compute iteration assignments in a pair—wise
fashion using a LeaderFollower relationship. We assume that each node maintains
an estimate of the error conditions of its associated channel based on some network
parameter such as Link Quality Indicator, which is normally the case for WSNs
[16]. The proposed DOPERA scheme uses a three step approach. In the initial
phase, nodes pair in LeaderFollower relationship. Leader nodes then solve a local
minimization problem and obtain estimates for iteration assignment. The resulting
follower node iteration assignment is then transmitted to the follower node in the last
step. Figure 5.1 shows this diagrammatically.
In order to cater for dynamism in the network, each follower node periodically
reports its channel error 6 S probability to the maser node. Leader node compares
both A63 and A6 M against a preset threshold 6T H (where A6 = lenew — 601d). If
either A65 or AEM or both exceed 6TH, iteration assignment is carried out again.
The periodic report frequency for the follower node can be designed based on the
conditions in which nodes would be deployed and desired reliability levels.
45
0 0,0 0,0 0
[12 [34
t5 6 6 [ii
0 2 : Oz—~
Figure 5.1. DOPERA Pairwise iteration assignment
5.1. 1 Pairing
For a given flow, we group the nodes in pairs. Starting from the base station, the
ﬁrst node encountered is labeled as follower, second leader, and so on till all or all
except a single node is left. Each pair is given a local budget of W iterations
with any leftover node getting W iterations. The pairing of nodes does not
require complete network knowledge and can be achieved with quite an ease. The
only information required in the process is number of nodes over the endto—end path
and total endto—end iteration budget. We assume that information about total nodes
is available through an underlying routing scheme which is usually the case for multi
hop wireless sensor networks [16]. Total iteration budget can either be passed to
nodes during individual link establishment phase, or programmed in individual nodes
prior to network deployment.
A side issue in distributed iteration assignment can be when iteration budget is not
46
completely divisible by N — 2 and leaves a remainder. This is handled in our work
by rounding to nearest lower integer and adding any leftover iterations to the leader
node closer to the data originator node, assuming data having greater survivability
chance if provided further reliability closer to the originator than destinations, where
errors may have accumulated to an extent that may lead decoding ineffective.
5.2 Local Minimization Problem
For DOPERA, each leader node now solves a local minimization problem in which
it attempts to minimize the local bit error rate with the condition that iteration
assignment is within the local budget constraint. Mathematically, it solves:
Minimize
Dloc = Pe(€La lL) * Pel€Fa lF)
Such That
2ri
lLl—lF: N_(—3
Or
Minimize
Dloc = f(€L, lL) * f(€F1lF)
Such That
(11 + lF) = Fallocal
We assume that the function f (e, l) : ER —> if? is convex and twice differentiable [21].
We interpret this as the problem of allocating a single resource, with a ﬁxed total
amount F(l) local to two, otherwise, independent activities.
47
The problem can be solved using elimination. Thus, we have: Min—
imize
fL(F(l)zocai lF1€L) * fear, 6F)
Subject to
177 = Fallocaz
IL > 0
lp > 0
where 1 E 311332 is a unit vector with rank 1 = 1 guaranteeing at least a single
solution. Though standard elimination techniques (see for example [7]) can be used
for the solution of minimization problem, they maybe computationally cumbersome
for energy starved sensor nodes in terms of function evaluations and convergence
properties. We instead turn to Newton’s method for constrained optimization that
provides faster convergence with quadratic approximation of the function Djoc that
has advantages in terms of computational complexity with high accuracy and very
fast convergence when the algorithm is initialized with good initial values that are
close to optimal. Details of Newton methods can be found in any standard text (for
example [7]) and are not mentioned due to brevity concerns .
5.2.1 Warm Start and Algorithm Convergence
The resource constrained nature of sensor nodes asks for low algorithm computa
tional overhead and fast convergence. Faster convergence can be achieved in case of
Newton’s method when initialized to suitable values of the optimization variable. We
48
consider four approaches for providing DOPERA a warm start:
DOPERA Unitary start: Both the nodes start with a single iteration
D—OPERA Equal start: Both the nodes start with equal number of iterations
DOPERA MaxMin start: One of the nodes starts with only one iteration,
whereas, the other starts with Falocall — 1, based on the associated channel error
rate with e L 2 e F implying l L 2 I F and viceversa.
DOPERA Proportional start: proportional assignment based on the error rates
é
WHERE,“ (rounded to lower integer value). For the case with a
with l L =
Leader/ Follower node getting zero iteration, a single iteration is borrowed from the
Follower/ Leader node to ensure nonzero assignment.
For all these approaches, we note down the resulting error performance, number
of function valuations and the algorithmic runs required to reach to a convergent
solution. The resulting performance curves are presented in subsequent sections.
5.3 Results
For the simulation setup, we keep the assumptions regarding code choice and sensor
motes as for the centralized case in chapter 5. We present both the cases here, ﬁrst
when we are given only a pair of nodes to be assigned decoding iterations and secondly,
an extension of the proposed technique over multiple flows.
49
5.3.1 DOPERA for a Pair
We consider 100 realizations of a LeaderFollower node pair in cascade over the end
to—end line network (Figure(4.1)) with each realization resulting in different channel
error probabilities for the pair. The results are averaged over all the realizations.
Leader node executes the algorithm and computes the iteration assignment for the
pair.
007:“ " ‘ ‘ ‘ ‘ “ ' " " '“““""'"'::'r.‘::_'t;:tw__:;::fif' "'""'_Z"_;‘“
i —0— DOPERA Unita i
o i —0— End to End ;
' O DOPERA Equal
—>— DOPERA maxmin
0.0 + DOPERA Proportional
1r
UJ
co
3
it
UJ
Figure 5.2. Expected Bit Error Rate vs Energy for DOPERA
Figure 5.2 shows the performance of our scheme for both DOPERA with all the
initialization options and endtOend channel coding. The results clearly indicate that
D—OPERA outperforms endto—end channel coding by a considerable margin with best
performance achieved with D—OPERA Proportional.
Figure 5.3 and Figure 5.4 analyze the convergence characteristics of the proposed
50
30'? T 7" 7W 77"",*.7 ' WT: T ' ’i’" L
‘ ''— DOPERA Unitary F]
‘ O— DOPERA Equal ]
,, . >— DOPERA MaxMin .
+DOPERA ProesPnaI . 1
251
#5. .
Function Evaluations
5 101's ' 20 2'5] ' so 36 4o
Processing Budget (Iterations)
Figure 5.3. Processing Budget vs Functional Evaluations of D for D—OPERA
solution with differing warm starts. We see that both in terms of algorithmic iterates,
as well as function evaluations, best convergence characteristics are achieved when the
algorithm is initialized with proportionate number of iterations for both the nodes.
5.3.2 Multiple ﬂows DOPERA
We consider a wireless sensor network with 150 nodes spread over 10mz10m rectangu
lar grid according to a random distribution. We place the base station at coordinates
(5, 5). The transmission range of each individual sensor node is limited to a maximum
transmission range of r = 2m. Since most widely used sensor network routing pro
tocols are some form of shortest path routing algorithm [16], we assume that at any
given time, the routes from individual nodes to the base station form a tree rooted at
51
] —— DOPERA Unitary ]
—0— DOPERA Equal !
l + D~OPERA MaxMn [
‘ + DOPERA Proportional
Algorithm Runs
i 2
Processing Budget (Iterations)
Figure 5.4. Processing Budget vs Algorithmic Runs
base station. Palbudget is varied from 6 to 40 per flow. The results in Figure 5.5 are
after complete decoding at the destination node for both OPERA and DOPERA.
The results clearly show that DOPERA provides a close enough approximation to its
centralized counterpart, OPERA. The curves also reafﬁrm our observation in previous
chapters concerning signiﬁcance of partial decoding at intermediate hops. When no
decoding is performed at intermediate nodes, accumulation of errors grows exponen
tially. In such situation, most of the packets received at the destination may have
very little or no information utility. On other extreme, when sufficient decoding is
employed at all intermediate nodes, data reliability increases signiﬁcantly at the cost
of energy consumption. Our technique allows to ﬁnegranularly operate at number of
intermediate points with variation in 110171111961
52
D—OPERA
OPERA
6
Energy (J)
Figure 5.5. DOPERA vs OPERA for Multiple Flows
53
CHAPTER 6
Progressive Error Recovery with
Path Diversity
54
6.1 Introduction and Motivation
We present scenarios in which the proposed partial decoding scheme can provide sig
niﬁcant performance beneﬁts as compared to the end—toend counterpart when mul
tiple paths are available leading to the destination node. We develop our framework
in conjunction with directed diffusion paradigm [17], though the scheme is equally
applicable to any other routing scheme in place with minor modiﬁcations.
We investigate the setting when there is asymmetry in the signiﬁcance of data
generated by individual nodes due to differing reliability demands set forth by each
type of data. An example of such an application can be in security & surveillance
related scenarios where events such as presence of fast moving objects in the vicinity
of sensor maybe of more interest than slow ones, or viceversa. In such a case,
we intend to provide one of the events greater reliability than the other alongwith
minimal energy consumption. Our scheme caters for that by introducing selective
budgetng of network resources for each type of event. The proposed architecture is
especially viable for Wireless Multimedia Sensor Networks (WMSNs) [3] where, there
can be multiple streams of data originating at a source node, and each may require
different level of reliability. For instance, for environmental monitoring applications,
we may have both acoustic and video data feeds that need to be transmitted back
to the base station. Likewise, in some surveillance applications, network designer
maybe willing to dedicate more network energy resources to audio data than video
or viceversa. Similarly, applications where there can be variation in sensor data
reliability demands such as monitoring and sensing, storage of potentially relevant
55
activities, trafﬁc avoidance and control, advanced health care delivery etc [3] are
good contenders for our proposed framework.
We further show that the proposed framework provides ﬂexibility to operate at
much higher error rates with greater energy efﬁciency. MDR provides an added ad
vantage in that, unlike traditional reliability schemes where only one path is available
to reach back to the destination node,providing multiple paths for sensor data offers
greater network lifetime by introducing a delay in network partitioning [34].
6.2 Background
82191 83191
81 P 84p,
3 81p: 82.02 $0 83172 841’2
8
5
81 p3 . p 3
8. 8“”:
P3 . 83p}
Figure 6.1. A multihop wireless sensor network with multiple paths to destination
node
56
6.2.1 Directed Diffusion of Interest
For the scope of our work, we assume that a routing scheme such as directed diffusion
[17] is already in place. In directed diffusion, a destination node initiates a request
for data by ﬂooding interests for named data. It uses attributevalue pairs in order to
name data [17]. Each interest contains attributes such as type of interest, timestamp,
active duration & rectangular region over which event is expected to take place. The
interests are passed over the network in a manner that each node knows only its
immediate neighbor. Thus, interest may reach the source node through multiple
paths. Hence, as indicated in Figure 6.1, several paths are available for sending back
the data to the destination node which are selectively reinforced based on network
application and demands. Our proposed methodology employees these paths to route
the data back to destination node.
6.3 MultiPath Distributed Reliability Framework
6.3.1 Phase I: Data Partitioning
We propose a framework that provides reliability to wireless sensor data maintaining
energy efﬁciency during the process. This is achieved in two phases: in ﬁrst phase,
data is partitioned into multiple streams based on its signiﬁcance/ genre. On the
basis of partitions thus obtained, we decide on processing budget at each intermediate
node, for the path assigned to that data stream. In the second phase, this budget
is distributed using an optimization algorithm carried out at selected intermediate
57
nodes. Both the phases are presented in subsequent subsections.
In the ﬁrst phase, nodes partition the data into multiple data sets based on its
signiﬁcance. The decision on signiﬁcance can either be source based or destination
based. For the destination based case, destination node initiates an interest for an
event that is passed on over the network. The interest may reach the node through
multiple paths. We propose a new ﬁeld in directed diffusion interest: ‘importance’
specifying signiﬁcance of the data. The ﬁeld can be adapted to have multiple values
based on application in which sensor network is deployed and the precise details are
left for network designer. The information passed by ‘importance ’ ﬁeld is used by the
source nodes to decide the local decoding budget for each pair of nodes over the end
to end path.
In source based scheme, the decision on signiﬁcance of data is local to the data
originating node.
6.3.2 Phase II: Multi—Path Distributed Iteration Assignment
Once the source node is decided on data genre and signiﬁcance level it belongs to,
it assigns the resulting data stream to an endto—end path. We assume that each
path has equal likelihood to be chosen for a type of data. After path selection and
hand shaking procedures, intermediate nodes decode the data with ﬁnite number of
decoding iterations as it traverses the multihop network. A question though remains
on the exact number of decoding iterations carried out by each node. We address
this by nodes computing iteration assignments in a pairwise fashion having a Leader
58
Follower relationship.
In our scheme, each node maintains an estimate of the error conditions of its associ
ated channel based on some network parameters such as Link Quality Indicator [16].
In the initial phase, nodes pair as LeaderFollower. Pairing of nodes does not require
global knowledge and can be achieved with quite an ease during link establishment
phase. Starting from the source node, ﬁrst node encountered is labeled as Lead,
second Follower and so on till all or all except a single node is left.
Assuming F a summation operator, each pair has a local pair budget of
F ()Pairpz determined based on signiﬁcance level of data stream that needs to be
distributed within Lead & Follower nodes such that resulting distortion Dpairpi is
minimum for that set of nodes. Each Lead node asks Follower node for their channel
error probability 6;”. Lead node uses both e F and e L to formulate a local minimization
problem:
Minimize . Dpairpi = f(eL,lL) =1: f(eF,lF)
Such That
1L + lF = Falpairpi
IL > 0
lF > 0
where
61* 62 = 61(1— 62) + 62(1 61)
We assume that the function f (e,l) : §R —> ER is convex and twice differen
tiable [23]. We use Newton’s method for constrained optimization to solve the min
imization problem at the Leader node due to its advantages in terms of computa
tional complexity and faster convergence when the algorithm is initialized with good
initial values [7]. For the given minimization problem, we initialize the algorithm
with iteration values proportional to the channel error rates such that for the lead
nodel — —€L—I‘(_)  (rounded to lower inte er value) ensurin fast conver n e
within few algorithmic runs. Any leftover node without a pair in the pairing process
F l 
( )pa" iterations. We have already shown the pairwise iteration assign
is assigned
ment in Figure 5.1 for a single endtOend path starting from channel error probability
exchanges between Leader and Follower nodes, iteration assignments based on New
ton’s optimization and eventually, decoding at intermediate hops.
In order to cater for dynamic network conditions over multiple paths, each Follower
node periodically reports its channel error probability 6 F to its Leader. The Leader
compares both 66 L and 66 F against a preset threshold 6T H (where 66 = [enew — Eoldll
If either of 66 L or 66 F exceeds 6TH, iteration assignment is recomputed at the Leader
node and passed on to Follower. The rate at which Follower reports 6 F to Leader can
be adapted based on conditions in which network is to be deployed and the reliability
desired.
6.4 Simulation Setup
We consider a source node with multiple paths leading to base station setup through
a multipath reinforcement scheme such as directed diffusion [17]. We assume three
data streams originating at a source node each requiring different reliability level
based on either destination based or source based partitioning. Source node speciﬁes
60
the desired reliability level for each stream based on which level it belongs to. We
assume that 6191 is the averaged equivalent error probability [22] over all the hops
for endto—end path p1,ep2 for path p2 and so on. Thus Gav is the composite error
probability for the network averaged over all the paths. We use multiple realizations
of the endto—end multihop links with variation in error probability such that number
of nodes for each path is Npl = 4,Np2 = 5,Np3 = 4 . Each realization results in a
different individual link error probability such that there is minimal deviation for
each path from average equivalent error probability. We assume all the nodes having
uniform energy levels initially.
We set the information packet size to be k = 1024 bits which is encoded with a
rate R = 0.569 code. We use an LDPC code with degree distribution polynomial
MO) = 0.20706 + 0.27102 + 0.52261 [27] , though, by concentration property of LDPC
codes [27], the deductions made here are equally applicable to any randomly picked
code from LDPC ensemble.
The transmission range of each individual sensor node is limited to a maximum
transmission range r = 2m. We set em,” = 0.005 and 6mm; 2 0.08. We take per hit
transmit power PT = lle, per second, for each node. We assume that if 6 < 6min,
only one iteration is enough to decode the information bits which is usually the.
case [22] [21]. We further assume each node equipped with an Atmel Atmega128L
processor and 2000:1 ratio between per bit transmission energy and computation
energy spent per instruction [12]. The average number of ones per column in a
parity check matrix of a (n, A, p) code from ensemble of LDPC codes is taken as:
(f01 A(6) d6)’1 [32]. Fossorier et a1. [9] give a comparison of mathematical operations
61
required for one LDPC decoding iteration for various LDPC decoding algorithms
including sum product algorithm [27]. This information is used to determine the
computational energy spent by sensor nodes for a single LDPC decoding iteration.
We use logdomain sum product algorithm for LDPC decoding due to its advantages
in terms of computational complexity. All results are averaged over 100 runs. For the
endto—end case, the total energy is the transmission cost of delivering information
bits reliably across the multihop network, whereas, energy costs for MDR involve
both transmission and computations within the network.
At the destination node, decoding is performed for each data stream. The resulting
bit error rate and energy levels are sampled such that there is one to one correspon
dence between energy levels for all the paths and the bit error rates thus achieved for
each path during that run. The results are averaged to obtain expected bit error rate
for corresponding energy level.
6.5 Results and Discussion
Figure 6.2 gives a performance comparison between proposed MDR scheme and end
tOend channel coding with variation in endto—end channel error probability em, .The
results clearly establish that the proposed MDR scheme outperforms endtoend chan
nel coding by considerable margin for level of reliability achieved for a given energy
budget. The plots further indicate that for endto—end approach, as the energy bud
get is increased, the corresponding decrease in bit error rate is relatively irregular
till enough redundancy is not added to sustain the information bits over entire end
62
to—end path, at which time though there is a sharper decrease, energy cost is also
signiﬁcantly higher. For MDR approach, rather than adapting the whole packet size
for different reliability levels at much higher energy costs, we achieve the ﬂexibility to
operate at ﬁxed packet sizes with greater energy efﬁciency by relatively inexpensive
processing within the network, thus ensuring network lifetime maximization.
0.14 I I I I I I
. ..‘s. MDR 0.1125
. . ; ; + endtoend 0.1125
5 } ' f 'I' MDR 0.1175
0.12,... . .. , .. , . .................... I endto.end0,1175
lOI' MDR 0.1190
_ . endto—end 0.119(l
1 i i ..... _
s i
E  s ,
b ‘ T I ' 3
g 008 _, . ..... ‘ ... . .. xi ................... ‘ . ......... _
Lu . . _ _
E 1 i i i . ’
330.06" .. .' ‘ ....... 1, _ . .. ..... ..
é. : E 1 l
a E! .
0.04 _. if! .. . ........... ..r
E.
; 9
0.02.. .. _ .5» ........... .,
, l‘.
: \’’
 K
0 1M 1
5 5.5 6.. 8.5
Energy (J)
Figure 6.2. MDR vs endto—end for I‘(.)pa,,Tp1 = 4, I‘(l)pa,,;.,.1,,2 = 6 and I‘(l—)],a,~,.p3 = 8
, Cay = 0.1125, 0.1175, 0.1190
Figure 6.3 shows the variation of expected bit error rate for MDR scheme when
pairwise budget I‘(l)pa,,. is varied for each data stream. We see that careful choice of
I‘( )pazT is important in ensuring desired level of reliability. We intend to maximize
63
throughput at the destination node, but at the same time, do not want to create a
partition within the network by draining out all the nodes on that path. The results
further indicate the efﬁcacy of MDR in allowing us to operate at endtoend channel
error rates as high as 61,2 = 0.1364 and still maintaining energy efﬁciency.
0.1 I I I I I I I
2"“ 1 g : : ; ruM0R444
’9, g i ' ; ; rIlMDR468
6,. 5 . . ; lrvIMDR6810
‘ R
.0
o
on
I
Expected Bit Error Rate
0
O
05
‘ '1
.0
o
A
1
I
O
Figure 6. 3. MDR vs endtoend for i) Ill—Mair],1 = 4, I‘( )paz'rp22 4I‘,(l)pa,,.p3=
ii) I‘l(lpairpl : 4: F(l—)pairp2 = 6, P(l)pairp3 = 8 iii)l.—‘(l)]Dm'rp1 = “()pairpz = 8,
P(l)pai1‘p3= 10, Epl = 0.1190, Epg =2 0.1364, 6193 = 0.1190
The plots in Figure 6.2 & Figure 6.3 further show that it is feasible to tradeoff
complexity/ energy usage with distortion/ reliability for a given sensor network. The
two extremes of the energy/ distortion curves in Figure 6.3 indicate the performance
64
that is achieved when two extremes of in—network processing is employed. When
no decoding is performed at intermediate nodes, the accumulation of errors is ex
ponential. Thus, any packets received at the destination node may have very little
or no information utility. On the other hand, when complete decoding budget is
distributed among all the pairs over all the paths, the information reliability is max
imum, though, network energy consumed also increases proportionally resulting in
decreased network lifetime. Our proposed scheme allows to ﬁnegranularly operate at
intermediate points by adjusting the functional demands of the network such that a
balance is maintained between desired reliability level and network lifetime. Again,
this can be achieved by adapting the pair budget assigned to individual streams over
the network lifetime.
65
CHAPTER 7
Application: Still Images
66
7 .1 Preliminaries and Motivation
In this chapter, we investigate the performance of proposed progressive error recovery
paradigm in conjunction with still images.
As of today, most of the wireless sensor networks deployed handle data that is of
scalar physical phenomena such as pressure, humidity, temperature, location etc [3].
Wide scale availability of CMOS devices such as CMOS cameras and audio sensors
has made it possible to integrate large selection of image and audio processing appli
cations with sensor networks. Though these developments have opened wide range
of possibilities, they have also brought forth various research challenges including
provision of data reliability with minimal overheads.
In this work, we utilize the progressive error resilience framework in order to provide
error resilience to sensor visual observations as they traverse the multihop network
towards the destination node. We propose to use partial channel decoding of visual
data as it approaches the destination node. Unlike some of the prior existing work
where full channel decoding/encoding was conducted under a Network Embedded
FEC (NEF) framework [41], here we use progressive error recovery paradigm dis
cussed in previous chapters. We show that the proposed paradigm, when used in
conjunction with visual data, signiﬁcantly enhances received image quality as com
pared to prevalent reliability schemes for a given network energy budget. We further
show that little bit of processing at intermediate nodes can greatly enhance the peak
signal to noise ratio (PSNR) quality of wireless visual data without compromising
on energy efﬁciency. \lVe illustrate that our approach is suitable for lowpower visual
67
sensor networks through rigorous simulations.
7.2 Simulation Setup
We conduct simulations based on both OPERA and DOPERA presented in chap
ters 4 and 5. In order to support image transfer, additional features have been added
to the application that enables the fragmentation and reassembly of the compressed
image ﬁles. We use standard image sequences ‘Boats’ and ‘Lenna’ for our simulations
. The images are JPEG2000 encoded, packetized, LDPC channel encoded and trans
mitted through a cascade of binary symmetric channels. A reverse process including
LDPC decoding, reframing and JPEG2000 decoding is conducted at the receiver.
Due to the nature Of our problem, for the scope of this work, we do not take source
encoding complexity into consideration and assume that sensor nodes are capable of
successfully encoding the images. We use Peak Signal to Noise Ratio (PSNR) in order
to measure quality of received images.
The captured image at the source node is ﬁrst encoded using a J PEG2000 encoder
with a compression ratio of 20:1. The JPEG2000 encoded bit stream is then packe
tized with k = 1024 information bits in each packet and fed to an LDPC encoder with
a degree distribution polynomial:).(6) = 0.20766 + 0.27162 + 0.52261 and code rate R
. The resultant packets are then transmitted over multihop network with associated
channel error probabilities 6.
In order to estimate the total energy consumption Etotal of the network for trans
porting a data packet over endtoend path, we set transmission power of each node
68
PT 2 ImW with 122000 ratio between transmission cost and computation cost [12].
Fossorier et a1. [9] give a comparison of mathematical operations required for LDPC
decoding, per iteration, for various LDPC decoding algorithms including sum product
algorithm. We use logdomain sumproduct algorithm due to its advantages in terms
of computational complexity [27]. The average number of ones in an LDPC parity
check matrix is taken as (f01 MO) d6)‘1 [32].We assume that each node is sending mes
sage back to a central coordinator over a multihop WMSN with number of nodes N=4
over the endtoend path. We assume each node equipped with Atmel Atmega128L
processor. For the statistical model, we assume 6mm = 0.005 and em” = 0.08. We
use different realization of the network for each run such that average endtoend
equivalent error probability eeq remains constant. All the results are averaged over
hundred runs.
7 .3 Results and Discussion
Figure 7.1 shows the performance of proposed DPERA scheme in comparison to end
toend channel coding with Etotal = 6.5.] for both end—to—end and DOPERA, with
I‘(—)pa,,. = 4. We see that DOPERA performs significantly better as compared to
the conventional endto—end channel coding in terms of received image quality.
Figure 7.2 highlights this further. We see that for endtoend equivalent channel
probabilities as high as egg 2 0.14, DOPERA shows excellent PSNR characteristics.
In comparison, for endtoend scheme, in order to achieve similar levels of reliability,
we may need much bigger packet lengths (and hence more redundant transmissions)
69
+ PSNR DOPERA
—I— PSNR endto—end
N
U!
I
PSNR (dB)
I
I
L
5 1 i i i i i 'i i
0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15
Channel Error Probability
Figure 7.1. Average PSNR for DOPERA with I‘( )pair = 6 and endto—end for
R = 0.5 LDPC encoded JPEG2000 image
leading to signiﬁcantly higher consumption of energy. Even if more redundancy is
added for endtoend scheme, endto—end error probabilities of the order of 10—1
maybe above the capacity of even best available channel codes.
For the proposed D—OPERA architecture, further savings in terms of energy can be
achieved using prioritization of the data, such that data having greater signiﬁcance
is assigned a path with higher POW“. and lower signiﬁcance data lower (I‘(l)pai,..
For instance, in JPEG2000 progressive coding of image using multiple layers [37],
some layers may require higher protection against channel errors than others based
on their energy efﬁciency and contribution to ﬁnal PSNR. In this work, we restrict
our discussion to uniform F( )pair over the endto—end path.
70
Figure 7.2. JPEG2000 encoded ‘boats’ image with seq 2 0.14(clockwise from left) i
original image after source encoding ii endto—end channel coding iii OPERA with
r(z),,,,dge, = 6 ivD—OPERA with mom, = 6
Figure 7.3 gives the performance curves for proposed OPERA and DOPERA
schemes for J PEG2000 encoded Lenna image sequence over a line network with N = 4
and an LDPC code rate of R = 0.5. The curves visibly Show the performance gains
achieved in using OPERA / DOPERA. For an iteration budget of only six iterations
to be distributed over a pair of nodes, the gain in peak signal to noise ratio is tremen
dous for progressive error recovery. For endtoend scheme,we start getting decoding
71
+ OPERA
+ D—OPERA
. .— End—to—End_
30—“
N
U"
l
PSNR (dB)
N
O
.s
01
l
5 I I l l
0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2
Channel Error Probability
Figure 7.3. JPEG 2000 encoded Lenna image with PERA and DOPERA for a pair
decoding budget of 6 iterations R = 0.5
failure for J PEGZOOO encoded Lenna at approximately 7% channel error probability.
In contrast, we do not encounter decoding failure for error rate as high as 14% and
18% for DOPERA and OPERA, respectively, with the assumption that 6 remains
below code capacity [28] on individual hops.
For the progressive recovery paradigm, the choice of F(_)pa,,. is an issue that requires
vigilance for the network designer & should be chosen based on the conditions in
which network is expected to operate. For instance, too high I‘(l_)pmr may lead to
faster depletion of node resources, Whereas, too low I‘(l)pa,,. may not provide desired
reliability. Hence, a balance should be struck while setting this parameter.
72
’lenna’ image with (clockwise from left) i original
Figure 7.4. JPEG2000 encoded
image after source encoding ii— end
0.07 iii— PERA
end channel coding with e =
to
OPERA with e = 0.143
= 0.18 iv—D
with e
73
CHAPTER 8
Application: Wireless Video
74
8.1 Introduction
Wide scale availability of lowcost hardware such as CMOS cameras and microphones
has fostered the development of sensor networks to carry multimedia content [3]. For
instance, Crossbow’s Imote2 multimedia board [1] adds multimedia capabilities to the
Imote2 platform for Wireless Sensor Networks (WSNS) allowing for capturing images,
video as well as audio for playback. This opens door for a variety of applications for
WSNS along with posing certain challenges in terms of reliably routing the multimedia
content from sensor nodes back to the base station. An example of such an application
can be in surveillance and security related scenarios where video data captured by a
remotely deployed camera mounted on a sensor node might need to be reliably sent
back to the central base station. An inherent problem in applications involving video
data is the amount of data generated along with ensuring minimal expenditure of
energy in routing it back to the base station. Using a single path to the destination
would fast deplete resources on that path, resulting in early network partitions and
lesser than expected network lifetime.
In [20], Puri et al. discuss the challenges faced by any video transmission scheme
for wireless sensor networks. They conclude that a broadband network of wireless
video sensors is subjected to three principal constraints: limited processing capabil
ities, limited power/ energy budget and information loss endemic to the harshloss
prone wireless communication environment. A related issue is the high transmission
costs for energy ravenous sensor nodes. According to some studies, there is a 1:2000
ratio between transmission cost and computational cost [12] in WSNs, thus making a
75
strong case in favor of in—network processing. Any data reliability framework should
keep these limitations under consideration. These limitations and the information
losses call for robust coding algorithms, protocols and architectures that build error
robustness within the WSNs.
Motivated by both error prone nature of links as well as sensor energy limitations,
we provide an architecture that can be used in order to reliably transport video con
tent in W'SNs. The proposed framework ensures near optimal use of network resources
as well as network lifetime maximization by avoiding partitions in the network due
to over usage of few paths. Particularly, we propose a strategy to add reliability
in WSNs using a three prong approach that builds on: a) multistream coding of
video b) multipath transport and c) distributed progressive error recovery through
partial recovery of sensor data at intermediate nodes (discussed later).To the best of
our knowledge, no work exists in this regard with these three components working
together in WSNs. We propose a solution that is best suited to multi—stream coding
of video as prevalent in most modern video coding architectures [20]. The proposed
architecture is distributed in nature such that no complete knowledge is assumed
regarding endto—end network conditions. Using LDPC codes, we compare the per
formance of the proposed framework with endtoend channel coding and Show that
it signiﬁcantly outperforms it in terms of energy efﬁciency for level of reliability thus
achieved.
76
8.2 Background
In this section, we provide a quick overview on few of the concepts used in the proposed
framework.
8.2.1 Video Coding Techniques
In order to understand the WSN video reliability problem, we take a quick glance on
the nature of coding techniques available for coding video content. Possible candidates
for WSN can be adapted form of either of layered coding (LC), multiple description
coding (MDC) or distributed video coding (DVC).
A typical layered coder includes one base layer and one or more successive enhance
ments layers that can be used together to achieve a desired level of video resolution
at the destination. The base layer has higher priority than the enhancement layers
as the loss of base layer makes the information received from the enhancement layers
useless [25].
Multiple description coding fragments a single media stream into M independent
sub streams (.M > 2) referred to as descriptions. These descriptions are then sent
over multiple channels and combined at the receiver depending on the desired video
resolution [40].
Predictive video coding (PVC) as used in H.26x or MPEGx employs two modes
in order to encode video: Intra—coding (1) mode exploiting the spatial correlation in
the frame that contains the current block by using a block transform such as the
discrete cosine transform (DCT), Intercoding or motion compensated predictive (P)
77
mode that exploits both spatial and temporal correlation in the video sequence [20].
Thus, in PVC, the encoded video frames can be partitioned into an I—stream and a
Pstream.
A more recent work on low complexity encoding of sensor video data is characterized
by distributed video coding (DVC) which incorporates concepts from source coding
with side information, creating an intracoded Iframe along with a side information
counterpart WynerZiv (WZ) frame [20]. The DVC framework, using its PRISM
architecture, promises to provide robustness, light sourceencoder architecture and
flexibility in distributing the computational burden of motion estimation between
transmitter and receiver. We can notice here as well that data can be partitioned
into multiple streams consisting both intra—coded as well as side information frames.
In summary, video coding techniques currently in vogue create multiple streams
of data that may differ in their signiﬁcance. Any video sensor reliability framework
should consider these facts in the design of the technique.
8.2.2 Multipath Transport (MPT)
MPT has been studied at length for both wired and wireless data [19]. Multipath
routing focuses on ﬁnding maximally disjoint paths from source to destination node.
Various routing algorithms used in sensor networks such as directed diffusion, dynamic
source routing (DSR), adhoc on demand distance vector (AODV) return multiple
paths to the destination node [19]. Routing diversitywhere packets are purposely
sent on different routes to insure against the failure of a. single route—can increase error
78
robustness in WSNs [13]. Thus, sensor energy limitations and multistream nature of
generated video content makes an appealing case in favor of MPT for avoiding early
network partitions through load balancing and provision of error resilience.
8.3 Multi—Path Multi—Stream Distributed Relia
bility
We discussed various video coding techniques that can be potentially adapted for use
with WSNs. One thing is common in all of them, data can be partitioned into various
streams. These streams can either be self sufﬁcient in that only one of them can be
used to decode the information (such as in MDC) or hierarchical in the sense that
we need one of them in order to decode the second one. We propose a multistream
multipath distributed reliability (MMDR) framework that is generic in nature such
that any technique used for encoding, till the time it has streams, we are good. The
framework uses a three prong strategy:
1. Source encode the video data into multiple streams and channel code the re
sulting streams
2. Assign the video to multiple paths for ensuring load balancing and error re
silience
3. Use partial decoding at intermediate nodes through distributed progressive error
recovery framework (discussed subsequently) to recover from channel induced
errors
79
Figure 8.1 gives the details of the proposed MMDR setup in WSNS. In the initial
phase, the video data is source encoded such that we attain multiple streams. These
streams are then channel coded before assigning to various paths. In the subsequent
subsections, we present the details on the components of the proposed architecture.
8.3.1 Prioritized Data Partitioning
The source encoded video is partitioned into M streams based on the signiﬁcance of
data towards decoding of video. e.g. assuming that we are using H.264 [25] for coding
video, the encoded video frames are split based on whether they are intracoded (1
frames) or intercoded (Pframes). These streams are then channel encoded before
they are fed to a path assignment block.
8.3.2 Path Assignment
We assume that certain multipath routing scheme such as directed diffusion is already
working underneath that returns multiple paths to the destination [17] [11]. These
schemes also return information on the level of reliability for each path. Based on
this information, K paths are chosen and partitioned M streams of data are assigned
to selected paths. A special case in MMDR is when K < M during path assignment
phase. In such a scenario, packets from multiple streams may share the same path
and intermediate nodes might need information on signiﬁcance of packets. Thus,
any protocol designed based on MMDR should build that capacity within the packet
streams. We restrict our discussion here for cases when K 2 1M.
80
For the example H.264 data, since intracoded I frames contain greater amount
of data than their P counterparts, they may require further splitting over further
paths for better load balancing, though, P frame streams may also requiring be split,
depending on number of paths available for reaching back to destination and group
of pictures (GOP) size used for encoding video. Intelligent data partitioning schemes
are thus required that partition the frames at their boundaries such that despite losses
in datasets for one frame other frames remain unaffected. For the scope of this work,
we assume that is the case.
8.3.3 Distributed Progressive Error Recovery
We employ distributed progressive error recovery paradigm proposed in chapter 5 in
conjunction with proposed MMDR framework.
8.3.4 Unequal Error Protection
The proposed architecture can be optionally combined with Unequal Error Protection
(UEP), where, the channel coding rate is varied based on various node and network
parameters. This does not come without few challenges though. In most of UEP
literature, the packet size n is kept constant, but information bits k are varied based
on [39]. Again, there are M streams and K g M channel codes maybe used to
encode them though a related issue is, for each variation in information bits, we may
need a different channel code to encode it. Thus, since sensor networks are randomly
deployed, tradeoff in sensor networks is greater amount of storage for each LDPC
81
code that might be required at each node depending on type of code used to encode
that particular stream.
8.4 Simulation Setup
In most of the prevalent video coding architectures, video encoding is the primary
computationally extensive task with complexity dominated by the motionsearch op
eration. For the scope of this work, we assume that sensors have the capability to
encode video though, efﬁcient source coding of video still remains a wider research
problem. In addition, we further assume that we are not facing motion estimation
complexity issues that maybe encountered in coding over video sensor nodes and con
ﬁne our focus towards data reliability aspects using progressive error recovery within
the network. We consider a sensor node transmitting to a base station with multiple
paths leading to the base station obtained through some underlying routing scheme
such as directed diffusion [17]. We keep the assumptions regarding sensor nodes and
the LDPC codes same as chapter 7.
The total energy for endto—end transmission is taken as the transmission cost in
transmitting n bits over endtoend multihop path, whereas, energy estimate for a
single path in MMDR involves both transmit and computation energy for in—network
processing. We set number of paths K = 4 with multiple realizations of the multihop
network for each run such that average endto—end equivalent error probability em,
remains constant. All the results are averaged over 100 runs. We use two paths in
order to send packets belonging to I frame and two for P frame. We set GOP size
82
Table 8.1. H.264 Encoder Parameters
Parameter Value
Sequence Foremanqcif
YUV Format 422:0
QP 28
Proﬁle IDC High
Entropy Coding CABAC
Sequence Type IPP
Error Concealment On
equal to 6. Both I & P—frame data is equally divided on each corresponding path
such that despite losses in datasets for one frame other frames remain unaffected. On
receive side, a resequencer collects all the packets, and assigns them to corresponding
streams, which are then fed to channel and source decoding modules to obtain the
reconstructed video ( 8.1).
8.5 Results
In this section, we present some preliminary simulation results that illustrate the
efﬁciency of the proposed MMDR architecture in WSNs with use of an H.264 video
encoder[2]
Figure 8.2 shows the performance of MMDR framework as compared to endto
end channel coding. We see that MMDR outperforms endtoend channel coding
by signiﬁcant margin, achieving reliable communication with much higher energy
efﬁciency for average endto—end equivalent error probabilities as high as em, = 0.125
with a pair budget of F( )pair 2 8.
83
Figure 8.3 shows the transmitted and reconstructed frame for both endtoend
channel coding and MMDR framework under different channel conditions with dif
ferent pairwise iteration budgets. The results clearly indicate much improved per
formance under MMDR for same energy levels used during endtoend transmission.
Figure 8.4 uses peak signaltonoise ratio (PSNR) in order to measure quality of
video sequences for different endto—end equivalent channel error probabilities. For
a channel coding rate R=O.5 and average endtoend equivalent error probability as
high as 0.14, the plots clearly establish that MMDR outperforms endtoend channel
coding by considerable margins.
The results indicate that MMDR provides reliability to video streams in WSNs
without fast depleting the energy resources of video sensors. They further depict that
little bit of processing at intermediate nodes can greatly enhance video quality at the
destination node. Use of path diversity gives the added ﬂexibility in terms of added
lifetime for WSNs. The ratedistortion curves obtained in Figure 8.2 and Figure 8.4
provide insight onto ﬁne tuning the functional demands from the network in terms
of adjusting the expected bit error rate/PSNR at the destination node for amount of
energy spent in transmitting the bits reliably over endtoend path.
84
88 Eggnog
_
_
_ .888
_
.35 89>
£5 Eggs:
Essa ass?
.888
3525
AIN 583ml ANEmgmi
Al 58%; AEmsmL
2883881
.2822
was
sees
as
a 0%;
steam
.9220
5.59:)
4 0:52.30
2:333
A 3.55.10
.885
89>
Egg—=2
ﬁguoﬁ Eweacm
Figure 8.1. MultiPath MultiStream reliability architecture for video transmission
in Wireless Sensor Networks
85
...v. .  MMDR 0.12
+ endto—end 0.12
'O'~MMDRO.1250 
end—to—end 0.1250
Expected BER
Energy(J)
Figure 8.2. MMDR vs end—toend transmission with R = 0.5,K = 4,N = 4,F(l)pa,,. =
8 a)€av = 0.12 b)eav = 0.125
86
Vania 7‘ Inn“l": ...... 4:
(a) i No losses ii With 10% losses (em, = 0.10 ) and end2end
scheme iii With em) = 0.10 & MMDR scheme and P(l)pair = 6
rI
(b) i No losses ii With 11.75% losses (em, = 0.1175) and end
2end scheme iii With 11.75% losses 8:: DPERA scheme with
I‘(l)pair = 8
..Ir
Figure 8.3. Frame 2(P) for Foreman QCIF sequence
87
40 I I I l I I I I
35 ,   . +YPSNRMMDR a
' ‘ ~ i +YPSNR endtoend
30~ ~
65
1°,
o:25 ‘
2
(D
O.
20_ ..1 ..... ‘: Q . ..
15~ .
10 l 1 i i 1 1 l
0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15
Channel Error Probability
Figure 8.4. Average YPSNR for both MMDR with F ( )pair 2 10 and Endto—End for
R = 0.5 LDPC encoded H.264 video.
88
CHAPTER 9
Conclusion and Future Work
89
In this work, we have presented a progressive error recovery paradigm that provides
reliability to sensor network data in a progressive fashion. We have presented a
framework that signiﬁcantly enhances the decoding reliability at the receiver at the
cost of processing within the network through partial decoding. We present both
centralized and distributed approaches in order to map the decoding iterations to
WSN for an iteratively decodable channel code.
The centralized approach presented optimally maps the decoding iterations to the
intermediate nodes and performs signiﬁcantly better than random assignment. We
give bounds on the performance of the algorithm for computational energy spent
within the network for partial decoding of ensembles of LDPC codes. In addition,
we have proposed a methodological approach for wireless sensor network resilience
against channel induced errors that ensures fairness to individual sensor nodes through
rate adaptivity and introduction of bounds on processing at individual nodes. We give
performance curves for variation in throughput at destination node using systematic
puncturing of LDPC codes and discuss associated energy/ throughput tradeoffs.
In addition, we have presented a distributed error recovery algorithm that ensures
complete distribution of all the iterations to intermediate nodes. The bit error rates
thus achieved outperform endtoend channel coding by considerable margin for the
amount of energy spent within the network. The setup obtained requires minimal
exchange of messages needing only two extra transmissions per pair of nodes (follower
node error rate and iteration assignment). We make no assumption regarding com
plete topological knowledge for the end to end path. The methodology thus achieved
ensures pairwise asynchrony in iteration assignment. The proposed proportional
90
warmstart provides fast convergence and guarantees minimal algorithmic overhead.
Given a statistical model for variation of bit error rate with decoding iterations, our
scheme is applicable to any iteratively decodable code.
Further, we have presented a multipath distributed reliability scheme for wireless
sensor networks. It provides a novel methodology to provide reliability to a Wireless
Sensor Network, in a distributed fashion, in scenarios when there is asymmetry in the
signiﬁcance of data. The scheme is particularly useful in network conditions when
high levels of endtoend corruption are expected in the data sent over the multihop
network. We show that how little bit of processing within the network carried out
in an intelligent fashion can tremendously help in ensuring reliability of data at the
destination.
We have shown the effectiveness of the proposed architecture with the help of rel
evant simulations using JPEG2000 images with LDPC codes. The proposed frame
work provides signiﬁcantly better performance than prevalent endtoend reliability
schemes.
Further motivated by the stringent requirements due to resource constrained nature
of sensor nodes, we have proposed an architecture to provide reliability to video in
WSNs. We have described the architectural platform, theoretical foundations, as well
as the bridge from theory to video practice, and presented promising experimental
results based on realworld video sequences that establish the efﬁcacy of our proposed
solution over prevalent reliability schemes in WSNS.
The proposed framework can be extended to other prevalent video coding tech
niques including but not limited to DVC, SVC or MDC. As indicated in ﬁgure 8.1, a
91
future extension of this work can be when the packets are unequally protected using
different LDPC codes. Similarly, adaptation of the framework with distributed video
coding is another area that can be investigated.
92
Appendix: A
93
Table 1.
Coefﬁcients 0(5ind)aﬂffindla7(€ind),¢(€ind) ,emin = 0.01, 6mm: = 0.08,
in,” = 150, R = 0.509(6) = 0.207196 + 0.271492 + 0.52201
62ml 0(6ind) ﬁféz'nd) 7(6ind) ¢(€ind)
1 0.000000 0.000000 0.000000 0.000000
2 0.000000 0.000000 0.000000 0.000000
3 0.000000 0.000000 0.000000 0.000000
4 0.000000 0.000000 0.000000 0.000000
5 0.77040 0.49120 0.788700 0.49920
6 1.04800 0.57960 1.071000 0.58730
7 0.95840 —0.49130 0.981200 0.49900
8 3.98e— 18 6.07400 0.062490 1.38600
9 0.00036 0. 11460 0.046340 1 . 13800
10 7.110€8 1.716000 0.046970 1.04200
11 1.346e—5 0.576800 0.076540 1.27000
12 0.058820 1.11000 0.005659 0.29750
13 0.414500 3. 70900 0.035520 0.56830
14 0.414500 3. 70900 0.035520 0.56830
15 0.072770 0.73810 0.00013 0.194400
16 0.097310 0.73360 0.05287 1.71600
17 1.315e—7 1.419000 0.068030 0.50910
18 0.160900 0.77600 0.49400 2.83200
19 0.086340 0.44410 0.00198 0.142800
20  1.70300 0.27440 1.791000 0.28160
21 0.00019 0.225600 0.094360 0.37780
22 0.020100 0.33230 0.078730 0.32970
23 5.860€6 0.439700 0.094610 0.24380
24 ~9.053e7 0.577800 0.098810 —0.22640
25 0.004318 0.054790 0.095930 0. 13270
26 0.003394 0.051480 0.089930 0.09533
27 1.125e5 0.235300 0.089780 0.11180
28 0.04832 0.07443 0.123900 0.07443
29 0.43230 0.08299 0.519000 0.08480
94
Table 2. Coefﬁcients a(€ind)aﬁffindlﬂféindliwkind) ,emm = 0.01, 6mm: = 0.08,
(max = 150, R = 0.51, /\(6) = 0.20766 + 0.271192 + 0.52261
Eind a(€ind) [3(Eind) 7(52'nd) wkind)
1 0.000000 0.000000 0.000000 0.000000
2 0.000000 0.000000 0.000000 0.000000
3 0.000000 0.000000 0.000000 0.000000
4 0.91380 0.42110 0.936800 0.42890
5 1.77200 0.65740 1.809000 0.66450
6 1.30600 0.51590 1.337000 —0.52340
7 1.61900 0.58400 1.654000 0.59110
8 1.85300 0.63560 1.901000 0.64230
9 0.044220 1.15700 0.020120 0.98420
10 1.2110 2.061000 0.055540 0.82360
11 0.00012 0.128900 0.062320 0.74030
12 1.200000 0.33280 1.253000 —0.33960
13 1.34900 0.38230 1.404000 0.38900
14 1.26200 0.34670 1.316000 0.35340
15 1.24700 0.28500 1.305000 0.29170
16 0.98590 0.23840 1.047000 0.24550
17 4.074e6 0.659300 0.064800 0.36950
18 0.00111 0.039210 0.070600 0.34820
19 5.808e8 0.835800 0.077180 —0.38230
20 1.184e—5 0.256500 0.082110 0.38260
21 3.646e5 0.231600 0.072100 0. 18360
22 0.009536 0. 14580 0.063390 0. 14360
23 0.04482 0.11370 0.123500 0.11360
24 0.076050 0.39250 0.031780 0.000994
25 0.047450 0.00811 0.002011 0.019310
26 0.071720 ~0.51340 0.045690 0.000358
27 0.069430 0.63150 0.053900 3.098€5
28 0.01408 0.03402 0.051920 0.000232
29 0.04448 0.44580 0.060100 4.565e—5
95
Table 3. Coefﬁcients a(e,nd),6(e,nd),7(e,nd),i,b(e,nd) ,emm = 0.01, emax = 0.08,
imam = 150, R = 0.52, W) = 0.20766 + 0.27162 + 0.522191
52nd 0(6md) ﬁ(€ind) 7(62'nd) wfeind)
1 000095 014510 0.021970 .0.75990
2 000421 O.33890 0.032100 0.75180
3 0.014430 4.29300 0.052580 4.43700
4 499.1 4.19800 199.2000 4.19800
5 0.199200 2.28500 0.007481 0.37550
6 0.073890 4.02700 5.693e6 0.533800
7 0.083440 4.07900 5.137e—7 0.934800
8 0.071620 6.765% 5.554e—6 0.605700
9 0.064960 0.60780 1.651€5 0.618400
10 0.475000 0.78070 6.45020 0.91870
11 0.146000 O.58710 011250 099370
12 0.146000 —0.58710 0.11250 0.99370
13 0.142300 0.58830 .0.10570 4.01100
14 O.84500 0.09831 0.903800 0.10580
15 0.72450 0.08762 0.784700 0.09519
16 0.00536 0.045930 0.076600 0.19390
17 0.142400 0.04939 0.213700 0.08161
18 000010 0.326100 0.079070 0.17040
19 002459 001793 0.098860 0.08698
20 ~5.471e5 0.151500 0.072670 0.05144
21 0.027500 0.000000 0.027500 0.000000
22 0.028750 0.000000 0.028750 0.000000
23 0.030000 0.000000 0.030000 0.000000
24 0.031250 0.000000 0.031250 0.000000
25 0.032500 0.000000 0.032500 0.000000
26 0.033750 0.000000 0.033750 0.000000
27 0.035000 0.000000 0.035000 0.000000
28 0.037500 0.000000 0.037500 0.000000
29 0.040000 0.000000 0.040000 0.000000
96
Table 4.
Coefﬁcients “(Eindlamfindla’lkindlwwfeind) 6min = 0.01, 6mm; = 0.08,
[max = 150, R = 0.5, PEG (3,6) Regular LDPC
Emd a(€ind) ﬁ(52nd) 7(6468) Wand)
1 0.000000 0.000000 0.000000 0.000000
2 0.000000 0.000000 0.000000 0.000000
3 0.000000 0.000000 0.000000 0.000000
4 0.69460 0.37620 0.712600 0.38410
5 0.97150 —0.471 10 0.998500 0.47830
6 1. 17000 0.48130 1.206000 0.48830
7 1. 12600 0.41540 1.167000 0.42230
8 0.31130 1.09000 0.30790 1.37700
9 0.175600 0.92100 0.26610 1.96300
10 0.435400 0.66820 0.38940 —0.74800
11 0.050130 0.36520 0.017250 0.36810
12 0.068400 0.27110 0.000198 0.000539
13 0.009578 0.04029 0.063590 0.24560
14 0.065780 —0.14410 0.005974 0.00118
15 0.054300 0. 14570 0.022660 0.00015
97
Table 5. Coefficients a(emd),ﬁ(6,nd),'y(eind),1/J(emd) ,em.,:n = 0.005, emax = 0.08,
[max = 150, R = 0.569,/\(9) = 0.20706 + 0.27162 + 0.52261
Eind 00527726) 5(6md) 7(6md) Wand)
1 0.020270 1.924000 0.027520 2.060000
2 0.023630 2.398000 0.027520 0.000000
3 0.235400 0.318700 0.000000 0.327400
4 0.000398 0.491000 0.242800 1.441000
5 0.000458 0.381900 0.034490 1.272000
6 0.045160 1.050000 0.039560 0.0000000
7 0.046460 0.82750 0.000000 0.286900
8 0.001199 0.322400 0.051330 0.735200
9 0.000270 0. 151600 0.055600 0.572200
10 0.057380 0.429300 1.033e14 0.157400
11 0.114100 0.311200 0.051560 0.282500
12 0.064360 0.271100 0.001997 0.042900
13 0.061870 0.196400 0.003563 0.000210
14 0.055990 —0. 160700 0.012830 0.000351
15 0.040590 0.139000 0.029850 0.000183
16 0.029480 0.221600 0.049870 4.751e—5
98
Bibliography
99
BIBLIOGRAPHY
[1] Crossbow Imote? Multimedia Board [MB 400 for Wireless Sensor Networks,
Product File, 2008.
[2] Jm reference software jvtad010, 2008.
[3] IF. Akyildiz, T. Melodia, and KR. Chowdhury. A survey on wireless multimedia
sensor networks. Computer Networks, 51(4):921—960, 2007.
[4] IF Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor
networks. IEEE Communications Magazines, 40(8):102—114, 2002.
[5] J. Barros and SD. Servetto. The sensor reachback problem. submitted to the
IEEE' Trans. Inform. Theory.
[6] L. Bazzi, TJ Richardson, and RL Urbanke. Exact thresholds and optimal codes
for the binarysymmetric channel and Gallager’s decoding algorithm A. IEEE
Transactions on Information Theory, 50(9):2010—2021, 2004.
[7] SP. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University
Press, 2004.
[8] TM. Cover, J.A. Thomas, J. Wiley, and W. InterScience. Elements of informa
tion theory. 1991.
[9] MPC Fossorier, M. Mihaljevic, and H. Imai. Reduced complexity iterative decod
ing of lowdensity parity checkcodes based on belief propagation. IEEE Trans
actions on Communications, 47(5):673—680, 1999.
[10] R. Gallager. Lowdensity paritycheck codes. IEEE Transactions on Information
Theory, 8(1):21—28, 1962.
[11] D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highlyresilient, energy
efﬁcient multipath routing in wireless sensor networks. ACM SI CM OBILE Mo
bile Computing and Communications Review, 5(4):11—25, 2001.
[12] Ramesh Govindan. Ieee comsoc wireless sensor networks tutorial.
http: //www.comsoc.org/freetutorials/nsc/ , 2006.
100
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
VK Goyal. Multiple description coding: Compression meets the network. IEEE
Signal Processing Magazine, 18(5):74—93, 2001.
P. Gupta and PR Kumar. The capacity of wireless networks. IEEE Transactions
on Information Theory, 46(2):388—404, 2000.
X.Y. Hu, E. Eleftheriou, and DM Arnold. Regular and irregular progressive edge
growth tanner graphs. IEEE Transactions on Information Theory, 51(1):386—
398, 2005.
Muhammad Usman Ilyas and Hayder Radha. Increasing network lifetime of an
ieee 80215.4 wireless sensor network by energy efﬁcient routing. In Proceedings
of IEEE International Conference on Communications (I CC 06), 2006.
C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva. Di
rected diffusion for wireless sensor networking. IEEE/ACM Transactions On
Networking, 11(1), 2003.
S. Madden, M.J. Franklin, J .M. Hellerstein, and W. Hong. TAG: a Tiny AGgre
gation Service for AdHoc Sensor Networks. Proceedings of the ACM Symposium
on Operating System Design and Implementation (OSDI), 2002.
S. Mao, S. Lin, SS Panwar, Y. Wang, and E. Celebi. Video transport over ad
hoc networks: Multistream coding with multipath transport. IEEE Journal on
Selected Areas in Communications, 21(10):17211737, 2003.
R. Puri, A. Majumdar, P. Ishwar, K. Ramchandran, P.P. Inc, and CA San Jose.
Distributed video coding in wireless sensor networks. IEEE Signal Processing
Magazine, 23(4):94—106, 2006.
SB Qaisar, S. Karande, K. Misra, and H. Radha. Optimally Mapping an Iterative
Channel Decoding Algorithm to a Wireless Sensor Network. IEEE International
Conference on Communications, ICC ’07., pages 3283—3288, 2007.
SB Qaisar and H. Radha. Optimal Progressive Error Recovery for Wireless
Sensor Networks using Irregular LDPC Codes. pages 232—237, 2007.
SB. Qaisar and H. Radha. Low complexity distributed reliability for Wireless
Sensor Networks. Conference on Information Sciences and Systems, CISS’08.,
pages 647—652, 2008.
H. Radha, M. Vetterli, and R. Leonardi. Image compression using binary space
partitioning trees. IEEE Transactions on Image Processing, 5(12):1610—1624,
1996.
101
[25] HM Radha, M. Van der Schaar, and Y. Chen. The MPEG4 ﬁnegrained scalable
video coding method for multimediastreaming over IP. IEEE Transactions on
Multimedia, 3(1):53—68, 2001.
[26] T.S. Rappaport. Wireless Communications: Principles and Practice. IEEE Press
Piscataway, NJ, USA, 1996.
[27] T. Richardson, A. Shokrollahi, and R. Urbanke. Design of provably good low
density parity check codes. IEEE Trans. Inform. Theory, 47:619—637, 2001.
[28] TJ Richardson, MA Shokrollahi, and RL Urbanke. Design of capacity
approaching irregular lowdensity paritycheckcodes. IEEE Transactions on In
formation Theory, 47(2):619—637, 2001.
[29] T.J. Richardson and R.L. Urbanke. The capacity of lowdensity paritycheck
codes under messagepassing decoding. IEEE Transactions on Information The
ory, 47(2):599—618, 2001.
[30] Y. Sankarasubramaniam, IF Akyildiz, and SW McLaughlin. Energy eﬂiciency
based packet size optimization in wireless sensor networks. Proceedings of the
First IEEE International Workshop on Sensor Network Protocols and Applica
tions, pages 1—8, 2003.
[31] M. Sartipi and F. Fekri. Source and channel coding in wireless sensor networks
using LDPC codes. First Annual IEEE Communications Society Conference on
Sensor and Ad Hoc Communications and Networks (SECON), pages 309—316,
2004.
[32] I. Sason and R. Urbanke. Paritycheck density versus performance of binary
linear block codes over memoryless symmetric channels. IEEE Transactions on
Information Theory, 49(7):1611—1635, 2003.
[33] GM. Schuster and AK. Katsaggelos. RateDistortion Based Video Compression:
Optimal Video Frame Compression and Object Boundary Encoding. Kluwer Aca
demic Publishers, 1997.
[34] RC Shah and JM Rabaey. Energy aware routing for low energy ad hoc sensor
networks. 1, 2002.
[35] E. Shih, S.H. Cho, N. Ickes, R. Min, A. Sinha, A. Wang, and A. Chandrakasan.
Physical layer driven protocol and algorithm design for energyefﬁcient wireless
sensor networks. Proceedings of the 7th annual international conference on Mobile
computing and networking, pages 272287, 2001.
102
[36] G.J. Sullivan and T. Wiegand. Ratedistortion optimization for video compres
sion. IEEE Signal Processing Magazine, 15(6):74—90, 1998.
[37] D8. Taubman, M.W. Marcellin, and M. Rabbani. JPEG2000: Image com
pression fundamentals, standards and practice. Journal of Electronic Imaging,
112286, 2002.
[38] D. Tuninetti and C. Fragouli. Processing along the way: forwarding vs. coding.
ISI TA 2005.
[39] M. van der Schaar and H. Radha. Unequal packet loss resilience for ﬁnegranular
scalability video. IEEE Transactions on Multimedia, 3(4):381394, 2001.
[40] Y. Wang, A.R. Reibman, and S. Lin. Multiple description coding for video
delivery. Proceedings of the IEEE, 93(1):57—70, 2005.
[41] M. Wu, S.S. Karande, and H. Radha. Networkembedded FEC for optimum
throughput of multicast packet video. Signal Processing: Image Communication,
20(8):728—742, 2005.
[42] H. Wymeersch, H. Steendam, and M. Moeneclaey. Logdomain decoding of
LDPC codes over GF (q). IEEE International Conference on Communications,
2004.
103