Information Processing And Routing In Wireless Sensor Networks

by Viktor K Prasanna, Bhaskar Krishnamachari, Yang Yu

Overview

This book presents state-of-the-art cross-layer optimization techniques for energy-efficient information processing and routing in wireless sensor networks. Besides providing a survey on this important research area, three specific topics are discussed in detail — information processing in a collocated cluster, information transport over a tree substrate, and information routing for computationally intensive applications. The book covers several important system knobs for cross-layer optimization, including voltage scaling, rate adaptation, and tunable compression. By exploring tradeoffs of energy versus latency and computation versus communication using these knobs, significant energy conservation is achieved.

Product Details

ISBN-13:	9789812701466
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	12/07/2006
Pages:	204
Product dimensions:	6.20(w) x 9.10(h) x 0.80(d)

Table of Contents

Preface     vii
Introduction to Wireless Sensor Networks     1
Overview     1
Enabling Technologies     2
Hardware     2
Wireless Networking     4
Collaborative Signal Processing     5
Evolution of Sensor Nodes     5
Military Networks of Sensors     6
Next Generation Wireless Sensor Nodes     6
WINS from UCLA     6
Motes from UC Berkeley     7
Medusa from UCLA     9
PicoRadio from UC Berkeley     10
[mu]AMPS from MIT     11
Why Microscopic Sensor Nodes?     12
Applications of Interest     13
Data Gathering Applications     14
Habitat Study     14
Environmental Monitoring     15
Computation-Intensive Applications     15
Structural Health Monitoring     15
Heavy Industrial Monitoring     16
Research Topics and Challenges     17
Focus of This Book     19
Background     23
Data-Centric Paradigm     23
Collaborative Information Processing and Routing     24
Cross-Layer Optimization for Energy-Efficiency     27
Motivation     27
Consideration for Collaborative Information Processing and Routing     29
A Brief Survey of Cross-Layer Optimization for Energy-Efficient Collaborative Information Processing and Routing     31
Hardware Layer     31
Physical Layer     32
MAC Layer     34
Routing Layer     35
Application Layer     37
Summary     38
Energy Models     41
Definitions and Notations     41
Mathematics and Graphs     41
Network Topology Graph     42
Application Graph     43
Performance Metrics     45
Energy Models     47
Voltage Scaling     48
Rate Adaptation     49
Tunable Compression     52
Information Processing within a Collocated Cluster     55
Overview     55
Motivation     55
Technical Overview     56
Chapter Organization     57
Related Work     57
Problem Definition     58
System Model     58
Application Model     60
Task Allocation     60
Integer Linear Programming Formulation      61
Heuristic Approach     63
Phase 1     64
Phase 2     66
Phase 3     67
Simulation Results     73
Synthetic Application Graphs     73
Simulation Setup     74
Small Scale Problems     75
Large Scale Problems     77
Impact of the Number of Voltage Levels     79
Incorporating Rate Adaptation     80
Application Graphs from Real World Problems     81
LU Factorization     81
Fast Fourier Transformation (FFT)     83
Summary     87
Information Transportation over a Tree Substrate     89
Overview     89
Motivation     89
Technical Overview     91
Chapter Organization     92
Related work     92
Models and Assumptions     93
Data Gathering Tree     94
Data Aggregation Paradigm     95
Problem Definition     96
Off-Line Algorithms for PTP     97
A Numerical Optimization Algorithm     97
Performance Analysis for a Special Case     100
A Dynamic Programming-Based Approximation Algorithm      103
A Distributed On-Line Protocol     105
Simulation Results     108
Simulation Setup     108
Performance of the Off-Line Algorithms     111
Performance Overview     111
Impact of Radio Parameters     112
Performance of the On-Line Protocol     114
Performance Overview     115
Impact of Network Parameters     115
Adaptability to System Variations     116
Summary     117
Information Routing with Tunable Compression     121
Overview     121
Technical Overview     122
Chapter Organization     123
Related Work     123
Models and Assumptions     125
Nomenclature     125
Network Model     126
Flow-Based Data Gathering     127
Discussion     128
An Example     129
Problem Definition     130
Optimal Flow in a Given Tree     131
Example Revisited     131
Determining the Optimal Flow     132
Analytical Study of SPT and MST     135
Analysis for a Grid Deployment     135
Tradeoffs Between SPT and MST      139
Tradeoffs for Entropy Model E1     140
Tradeoffs for Entropy Model E2     141
SPT is optimal for Entropy Model E3     142
Summary of Grid Deployment     142
A Randomized O(log[superscript 2] v) Approximation     142
Simulation Results     145
Simulation Setup     145
Results     146
Main Results     146
Impact of the number of source nodes R     148
Impact of the communication range r     148
Summary     148
Conclusions     153
Concluding Remarks     153
Future Work     155
Adaptive Fidelity Algorithms     155
A Broad View of Future Research     156
Mobile Sensor Nodes     156
Routing Diversity     157
Sleep Scheduling     158
Bibliography     161
Correctness of EMR-Algo     175
Performance Bound of SPT and MST for TDG problem with grid deployment     181
Index     183