“fl

 

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 fulfillment
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 Affinnative Action/Equal Opportunity Employer

-.-.-.—--.-.-----.------.-- —.-....- _ - _

_.—:-.------c-c-.—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 fulfillment 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 multi-hop 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 end-to-end 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 multi-hop 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 channel-decode the incoming packets as data reaches

the final destination. We use iteratively decodable Low Density Parity Check (LDPC)

codes in order to illustrate the efficiency 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 end-to-end
channel coding, and show that OPERA performs considerably better. In addition,
further motivated by resource limitation of sensor nodes and the well-known 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
multi-hop WSN. We present various scenarios for a WSN to achieve rate-compatibility
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 pair-wise fashion to individ-
ual nodes. Under the proposed Distributed Progressive Error Recovery Paradigm
(D-OPERA), nodes collaborate, in a distributed pair-wise 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 lab-mates 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
flavor 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 financed 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 sacrifices to finance my
education. They counted every single day as I had been away from them, first for
five years during high school and then again, for five 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 well-wishers 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 financed 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 first three years of my stay in United
States. And to my students whose bright faces, will to progress and ability to excel
on receiving fine 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 End-to-end 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 Pair-wise D-OPERA ...........................
5.1.1 Pairing ...............................
5.2 Local Minimization Problem .......................
5.2.1 Warm Start and Algorithm Convergence ............
5.3 Results ...................................
5.3.1 D-OPERA for a Pair .......................
5.3.2 Multiple flows D-OPERA ....................
6 Progressive Error Recovery with Path Diversity ..........
6.1 Introduction and Motivation .......................
6.2 Background ................................
6.2.1 Directed Diffusion of Interest ..................
6.3 Multi-Path Distributed Reliability Framework .............
6.3.1 Phase I: Data Partitioning ...................

6.3.2 Phase II: Multi-Path 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 Multi-Path Multi-Stream 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 Coefficients oz(e.,;nd),fi(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 Coefficients 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),fi(emd),7(emd),t/J(emd) ,emZ-n = 0.01, 6mm; 2 0.08,
imam = 150, R = 0.52, Me) = 0.20796 + 0.27162 + 0.52291 ....... 96

4 Coefficients a(€ind),fi(emd),7(emd),t/)(emd) emm = 0.01, 6mm; = 0.08,
Imam = 150, R = 0.5, PEG (3,6) Regular LDPC ............ 97

5 Coefficients (1(6ind),fi(€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 ..........

End-to-end 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 ....................

D-OPERA Pair-wise iteration assignment ................
Expected Bit Error Rate vs Energy for D-OPERA ...........
Processing Budget vs Functional Evaluations of D for D—OPERA

Processing Budget vs Algorithmic Runs .................

D-OPERA vs OPERA for Multiple Flows ...............

A multi-hop wireless sensor network with multiple paths to destination
node ....................................
MDR vs end-to—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 D-OPERA with I‘(l)pair = 6 and end-to-end 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- end-to—end channel coding

iii- OPERA with r(z)b,,dge, = 6 iv-D-OPERA with r(l)pa,-,. = 6

JPEG 2000 encoded Lenna image with PERA and D-OPERA 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- end-to-end channel coding with e = 0.07
iii- PERA with E = 0.18 iv-D-OPERA with 6 = 0.143 .........

Multi—Path Multi-Stream reliability architecture for video transmission
in Wireless Sensor Networks .......................

MMDR vs end-to—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 End-to-End
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 multi-hop 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 (in-network 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 significantly 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 finite complexity processing achieves a

significant 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
benefits that can be achieved due to finite 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 finite 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—to-end path. We propose a Distributed
Progressive Error Recovery Algorithm (D-OPERA) that recovers errors for a W SN
in a distributed manner. Nodes collaborate, in pair-wise 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 significance 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 path-diversity 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,
rate-compatible 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, multi-functional 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 flipped 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=0|X=0) = 1—6
PT(Y = 0|X =1) = 6
Pr(Y =: 1|X = 0) = e

PT(Y =1|X =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 efficiency 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 end-to-end 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 effi-
ciency. They show that some FEC coding schemes can improve the energy efficiency of
a communication link, several others, including retransmissions are energy inefficient.
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
significantly impacts energy efficiency, 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
efficient than those that use BCH codes, which were shown to be 15% more energy
efficient than the best performing convolutional codes.

All these works are based on end-to-end 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, in-network processing can be highly beneficial.
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 end-to-end channel coding. In addition,
keeping in view the energy efficiency of LDPC codes in sensor networks [31], the pro-
posed paradigm uses them to achieve enhanced throughput while maintaining energy

efficiency.

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 sufficiently 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) = arenaefitmdfl + 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),fi(ei,,d),7(emd) and Il’(€ind) are the statistical coefficients

[21].

16

Figure 3.2 gives the root mean square error in the proposed statistical model. It
is evident from the figure 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, significant
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 in-network 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 first solve
the problem for a single path line network, which can then be mapped to the entire

network.

4. 1 Problem Formulation

A multi-hop 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 quasi-stationary
2. Each node is capable of decoding the received messages

3. All nodes have equal significance and similar capabilities in processing and com-

munication
4. Nodes are left unattended after deployment

20

 

6 6 0

W”"‘:O’a""fit‘sfi

 

 

 

Figure 4.1. A Multi-hop 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 multi-hop 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) Zfix foo eflu/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 first 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 (4-5)

where 61 * 62 : 62(1 — 61) + 61(1 — 62) For the cascade line network, we define the

total number of decoding iterations in the entire network as:

N-l

' = 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 (4-7)

22

For an end-to-end path with E = 61, E2, . . . ,ej, . . . , €N—1 and given iteration budget
F(Z)budget1 we intend to find 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 find 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 satisfied 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
reach-back [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 flows passing through them leading to the

base station. In other words, we do not intend to aggravate the sensor reach-back

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 flows passing through the node. With the
assumption of all the nodes transmitting simultaneously back to the base station, the
number of flows passing through a node is simply the depth of sub-tree rooted at
that node. Thus, greater the depth, greater the number of flows passing through the

node, and lower is the number of iterations it can perform per fiow. 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 sub-tree 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 flows.

 

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 traffic 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
NxflN§=<I>,{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 end-to-end path, rate RN33 punctured codes
are assigned to each partition Nx till we reach the destination node. The resulting

distortion over the end-to—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 significantly 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 syn-6076
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 rate-compatible 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 end-to—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 sufficient 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 fix
11061.net = 60 iterations. We take per bit transmit power PT = ImW, per second,
for each node unless specified 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 end-to—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 traffic back to the base station on shortest paths already

established through some routing algorithm.

4.5 Results

4.5.1 End-to-end 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 end-to-end 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 end-to—end schemes with average end—to—end equivalent error probability
Eendeq- It is essential to note here that both OPERA and end-to-end results here
are after decoding at the destination node. For end-to-end case, Etotal = Emms

whereas, (12) gives the total energy for OPERA. The results show that OPERA

outperforms end-to—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 — End-to-End

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. End-to—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 flows leading to the base station. The plots show that it is feasible to
optimally trade-off complexity/energy usage with distortion/ reliability by varying
the assignment of iterations. The two extremes of the Complexity-Distortion curve in
Figure 4.6. represent the performance that is offered when two extremes of in-network
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 --fi """ . ._
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 life-time is decreased.
Our proposed approach allows us to fine-granularly 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 in-network 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 life-time. 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 in-network 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 set-off 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 Complexity-Distortion 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 efficiency 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 end-to-end path. Figure 4.7 shows the efficiency 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 end-to-end 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 significant 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 trade-off 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 significantly 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 flexibility to select intermediate Operating points. For a real
sensor network deployment, event based operating point selection can be employed.
When a significant 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 figure 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 multi-hop network. Though optimal, it assumes
complete topological knowledge of the entire network. Such knowledge may not be
available in real-world 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 satisfies 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 end-to—end path
0 Offers a fair amount of asynchrony in distributing the processing budget

0 Applicable to any iteratively decodable channel code

5. 1 Pair-Wise D-OPERA

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 finite 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 Leader-Follower 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 D-OPERA scheme uses a three step approach. In the initial
phase, nodes pair in Leader-Follower 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. D-OPERA Pair-wise iteration assignment

5.1. 1 Pairing

For a given flow, we group the nodes in pairs. Starting from the base station, the
first 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 end-to—end path
and total end-to—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 D-OPERA, 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
lL-l—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 fixed 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 D-OPERA a warm start:
D-OPERA Unitary start: Both the nodes start with a single iteration
D—OPERA Equal start: Both the nodes start with equal number of iterations
D-OPERA Max-Min 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 vice-versa.

D-OPERA 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 non-zero 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, first
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 D-OPERA for a Pair

We consider 100 realizations of a Leader-Follower 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— D-OPERA Unita i

o i —0— End to End ;

' -O- D-OPERA Equal
—>— D-OPERA max-min

0.0 + D-OPERA Proportional
1r
UJ
co
3
it
UJ

 

 

 

 

 

 

 

Figure 5.2. Expected Bit Error Rate vs Energy for D-OPERA

Figure 5.2 shows the performance of our scheme for both D-OPERA with all the
initialization options and end-tO-end channel coding. The results clearly indicate that
D—OPERA outperforms end-to—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

‘ '-'— D-OPERA Unitary F]
‘ -O— D-OPERA Equal ]
,, . ->— D-OPERA Max-Min .
+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 flows D-OPERA

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

 

] —— D-OPERA Unitary ]
—0— D-OPERA Equal !
l + D~OPERA Max-Mn [
‘ + D-OPERA 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 D-OPERA.
The results clearly show that D-OPERA provides a close enough approximation to its
centralized counterpart, OPERA. The curves also reaffirm our observation in previous
chapters concerning significance 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 significantly at the cost
of energy consumption. Our technique allows to fine-granularly operate at number of

intermediate points with variation in 110171111961-

52

 

 

   
   

 

 

D—OPERA
OPERA

 

 

 

 

 

 

 

6
Energy (J)

 

Figure 5.5. D-OPERA 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-
nificant performance benefits as compared to the end—to-end 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 modifications.

We investigate the setting when there is asymmetry in the significance 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 vice-versa. In such a case,
we intend to provide one of the events greater reliability than the other along-with
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 vice-versa. Similarly, applications where there can be variation in sensor data

reliability demands such as monitoring and sensing, storage of potentially relevant

55

activities, traffic avoidance and control, advanced health care delivery etc [3] are
good contenders for our proposed framework.

We further show that the proposed framework provides flexibility to operate at
much higher error rates with greater energy efficiency. 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 multi-hop 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 flooding interests for named data. It uses attribute-value 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 Multi-Path Distributed Reliability Framework

6.3.1 Phase I: Data Partitioning

We propose a framework that provides reliability to wireless sensor data maintaining
energy efficiency during the process. This is achieved in two phases: in first phase,
data is partitioned into multiple streams based on its significance/ 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 first phase, nodes partition the data into multiple data sets based on its
significance. The decision on significance 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 field in directed diffusion interest: ‘importance’
specifying significance of the data. The field 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 ’ field 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 significance 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 significance level it belongs to,
it assigns the resulting data stream to an end-to—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 finite number of
decoding iterations as it traverses the multi-hop 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 pair-wise 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 Leader-Follower. 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, first 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 significance 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 pair-wise iteration assign-

is assigned
ment in Figure 5.1 for a single end-tO-end 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 specifies

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 end-to—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 end-to—end multi-hop 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 log-domain sum product algorithm for LDPC decoding due to its advantages
in terms of computational complexity. All results are averaged over 100 runs. For the
end-to—end case, the total energy is the transmission cost of delivering information
bits reliably across the multi-hop 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-
tO-end channel coding with variation in end-to—end channel error probability em, .The
results clearly establish that the proposed MDR scheme outperforms end-to-end chan-
nel coding by considerable margin for level of reliability achieved for a given energy
budget. The plots further indicate that for end-to—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
significantly higher. For MDR approach, rather than adapting the whole packet size
for different reliability levels at much higher energy costs, we achieve the flexibility to
operate at fixed packet sizes with greater energy efficiency by relatively in-expensive

processing within the network, thus ensuring network lifetime maximization.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0.14 I I I I I I
. ..‘s. MDR 0.1125
. . ; ; + end-to-end 0.1125
5 } ' f '-I-' MDR 0.1175
0.12,... . .. , .. , . .................... I end-to.end0,1175-
l-OI' MDR 0.1190
_ -.- end-to—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 end-to—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
pair-wise budget I‘(l-)pa,-,. is varied for each data stream. We see that careful choice of

I‘( )paz-T 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 efficacy of MDR in allowing us to operate at end-to-end channel

error rates as high as 61,2 = 0.1364 and still maintaining energy efficiency.

 

 

 

 

 

 

0.1 I I I I I I I
2"“ 1 g : : ; r-u-M0R444
’9, g i ' ; ; r-I-lMDR468
6,. 5 . . ; l-rv-IMDR6810
‘ R

.0

o

on
I

Expected Bit Error Rate
0
O
05

‘ '1

.0

o

A
1

I
O

 

 

 

 

 

 

Figure 6. 3. MDR vs end-to-end 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 fine-granularly 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 multi-hop 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, significantly 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 efficiency. \lVe illustrate that our approach is suitable for low-power visual

67

sensor networks through rigorous simulations.

7.2 Simulation Setup

We conduct simulations based on both OPERA and D-OPERA 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 files. 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, re-framing 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 first 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 multi-hop 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 end-to-end 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 log-domain sum-product 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 multi-hop WMSN with number of nodes N=4
over the end-toend 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 end-to-end
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-
to-end channel coding with Etotal = 6.5.] for both end—to—end and D-OPERA, with
I‘(—)pa,-,. = 4. We see that D-OPERA performs significantly better as compared to
the conventional end-to—end channel coding in terms of received image quality.
Figure 7.2 highlights this further. We see that for end-to-end equivalent channel
probabilities as high as egg 2 0.14, D-OPERA shows excellent PSNR characteristics.

In comparison, for end-to-end scheme, in order to achieve similar levels of reliability,

we may need much bigger packet lengths (and hence more redundant transmissions)

69

 

 

 

+ PSNR D-OPERA
—I— PSNR end-to—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 D-OPERA with I‘( )pair = 6 and end-to—end for
R = 0.5 LDPC encoded JPEG2000 image

leading to significantly higher consumption of energy. Even if more redundancy is
added for end-to-end scheme, end-to—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 significance
is assigned a path with higher POW“. and lower significance 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 efficiency and contribution to final PSNR. In this work, we restrict

our discussion to uniform F( )pair over the end-to—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- end-to—end channel coding iii- OPERA with

r(z),,,,dge, = 6 iv-D—OPERA with mom, = 6

 

 

 

 

 

Figure 7.3 gives the performance curves for proposed OPERA and D-OPERA
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 / D-OPERA. 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 end-to-end 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 D-OPERA 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 D-OPERA 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_)pm-r 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 low-cost 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 harsh-loss
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) multi-stream 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 end-to—end network conditions. Using LDPC codes, we compare the per-
formance of the proposed framework with end-to-end channel coding and Show that
it significantly outperforms it in terms of energy efficiency 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 MPEG-x 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), Inter-coding 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
P-stream.

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 intra-coded I-frame along with a side information
counterpart Wyner-Ziv (WZ) frame [20]. The DVC framework, using its PRISM
architecture, promises to provide robustness, light source-encoder 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 significance. 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 finding maximally disjoint paths from source to destination node.
Various routing algorithms used in sensor networks such as directed diffusion, dynamic
source routing (DSR), ad-hoc on demand distance vector (AODV) return multiple
paths to the destination node [19]. Routing diversity-where 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 multi-stream 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 sufficient 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 multi-stream
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 significance 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 intra-coded (1-
frames) or inter-coded (P-frames). 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 significance 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 intra-coded 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 motion-search op-
eration. For the scope of this work, we assume that sensors have the capability to
encode video though, efficient 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-
fine 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 end-to—end transmission is taken as the transmission cost in
transmitting n bits over end-to-end multi-hop 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 multi-hop
network for each run such that average end-to—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

Profile 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
efficiency 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 end-to-
end channel coding. We see that MMDR outperforms end-to-end channel coding
by significant margin, achieving reliable communication with much higher energy
efficiency for average end-to—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 end-to-end
channel coding and MMDR framework under different channel conditions with dif-
ferent pair-wise iteration budgets. The results clearly indicate much improved per-
formance under MMDR for same energy levels used during end-to-end transmission.

Figure 8.4 uses peak signal-to-noise ratio (PSNR) in order to measure quality of
video sequences for different end-to—end equivalent channel error probabilities. For
a channel coding rate R=O.5 and average end-to-end equivalent error probability as
high as 0.14, the plots clearly establish that MMDR outperforms end-to-end 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 flexibility in terms of added
lifetime for WSNs. The rate-distortion curves obtained in Figure 8.2 and Figure 8.4
provide insight onto fine 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 end-to-end 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

 

 

 

 

 

figuofi Eweacm

 

 

Figure 8.1. Multi-Path Multi-Stream reliability architecture for video transmission

in Wireless Sensor Networks

85

 

 

    
  

...v. . - MMDR 0.12

+ end-to—end 0.12
'--O'~MMDRO.1250 -
end—to—end 0.1250

   

 

Expected BER

 

 

 

Energy(J)

 

 

 

Figure 8.2. MMDR vs end—to-end 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 end-2-end

scheme iii- With em) = 0.10 & MMDR scheme and P(l)pair = 6

r-I

 

 

 

 

(b) i- No losses ii- With 11.75% losses (em, = 0.1175) and end-
2-end scheme iii- With 11.75% losses 8:: D-PERA 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 end-to-end
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 End-to—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 significantly 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 significantly 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 end-to-end 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 pair-wise asynchrony in iteration assignment. The proposed proportional

90

warm-start 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 multi-path 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
significance of data. The scheme is particularly useful in network conditions when
high levels of end-to-end corruption are expected in the data sent over the multi-hop
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 significantly better performance than prevalent end-to-end 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 real-world video sequences that establish the efficacy 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 figure 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.

Coefficients 0(5ind)aflffindla7(€ind),¢(€ind) ,emin = 0.01, 6mm: = 0.08,
in,” = 150, R = 0.509(6) = 0.207196 + 0.271492 + 0.52201

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

62ml 0(6ind) fifé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.053e-7 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.125e-5 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. Coefficients a(€ind)afiffindlflfé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.21-10 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.074e-6 0.659300 0.064800 -0.36950
18 -0.00111 0.039210 0.070600 -0.34820
19 -5.808e-8 0.835800 0.077180 —0.38230
20 -1.184e—5 0.256500 0.082110 -0.38260
21 -3.646e-5 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. Coefficients 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) fi(€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.693e-6 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.471e-5 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.

Coefficients “(Eindlamfindla’lkindlwwfeind) 6min = 0.01, 6mm; = 0.08,

[max = 150, R = 0.5, PEG (3,6) Regular LDPC

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Emd a(€ind) fi(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),fi(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.033e-14 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 jvt-ad010, 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 binary-symmetric 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 low-density parity checkcodes based on belief propagation. IEEE Trans-
actions on Communications, 47(5):673—680, 1999.

[10] R. Gallager. Low-density parity-check codes. IEEE Transactions on Information
Theory, 8(1):21—28, 1962.

[11] D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-resilient, energy-
efficient 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 efficient 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 Ad-Hoc 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):1721-1737, 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 MPEG-4 fine-grained 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 low-density parity-checkcodes. IEEE Transactions on In-
formation Theory, 47(2):619—637, 2001.

[29] T.J. Richardson and R.L. Urbanke. The capacity of low-density parity-check
codes under message-passing decoding. IEEE Transactions on Information The-
ory, 47(2):599—618, 2001.

[30] Y. Sankarasubramaniam, IF Akyildiz, and SW McLaughlin. Energy efliciency
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. Parity-check 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. Rate-Distortion 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 energy-efficient wireless
sensor networks. Proceedings of the 7th annual international conference on Mobile
computing and networking, pages 272-287, 2001.

102

[36] G.J. Sullivan and T. Wiegand. Rate-distortion 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 fine-granular-
scalability video. IEEE Transactions on Multimedia, 3(4):381-394, 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. Network-embedded 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. Log-domain decoding of
LDPC codes over GF (q). IEEE International Conference on Communications,
2004.

103