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 trade-offs of energy versus latency and computation versus communication using these knobs, significant energy conservation is achieved.
Author(s): Yang Yu, Viktor K. Prasanna, Bhaskar Krishnamachari
Publisher: World Scientific Publishing Company
Year: 2006
Language: English
Pages: 202
Contents ......Page 12
Preface ......Page 8
1.1 Overview ......Page 17
1.2.1 Hardware ......Page 18
1.2.2 Wireless Networking ......Page 20
1.3 Evolution of Sensor Nodes ......Page 21
1.3.2 Next Generation Wireless Sensor Nodes ......Page 22
1.3.3 Why Microscopic Sensor Nodes? ......Page 28
1.4 Applications of Interest ......Page 29
1.4.1 Data Gathering Applications ......Page 30
1.4.2 Computation-Intensive Applications ......Page 31
1.5 Research Topics and Challenges ......Page 33
1.6 Focus of This Book ......Page 35
2.1 Data-Centric Paradigm ......Page 39
2.2 Collaborative Information Processing and Routing ......Page 40
2.3.1 Motivation ......Page 43
2.3.2 Consideration for Collaborative Information Processing and Routing ......Page 45
2.4.1 Hardware Layer ......Page 47
2.4.2 Physical Layer ......Page 48
2.4.3 MAC Layer ......Page 50
2.4.4 Routing Layer ......Page 51
2.4.5 Application Layer ......Page 53
2.4.6 Summary ......Page 54
3.1.1 Mathematics and Graphs ......Page 57
3.1.2 Network Topology Graph ......Page 58
3.1.3 Application Graph ......Page 59
3.1.4 Performance Metrics ......Page 61
3.2 Energy Models ......Page 63
3.2.1 Voltage Scaling ......Page 64
3.2.2 Rate Adaptation ......Page 65
3.2.3 Tunable Compression ......Page 68
4.1.1 Motivation ......Page 71
4.1.2 Technical Overview ......Page 72
4.2 Related Work ......Page 73
4.3.1 System Model ......Page 74
4.3.3 Task Allocation ......Page 76
4.4 Integer Linear Programming Formulation ......Page 77
4.5 Heuristic Approach ......Page 79
4.5.1 Phase 1 ......Page 80
4.5.2 Phase 2 ......Page 82
4.5.3 Phase 3 ......Page 83
4.6.1 Synthetic Application Graphs ......Page 89
4.6.2 Application Graphs from Real World Problems ......Page 97
4.7 Summary ......Page 103
5.1.1 Motivation ......Page 105
5.1.2 Technical Overview ......Page 107
5.2 Related work ......Page 108
5.3 Models and Assumptions ......Page 109
5.3.1 Data Gathering Tree ......Page 110
5.3.2 Data Aggregation Paradigm ......Page 111
5.4 Problem Definition ......Page 112
5.5.1 A Numerical Optimization Algorithm ......Page 113
5.5.2 Performance Analysis for a Special Case ......Page 116
5.5.3 A Dynamic Programming-Based Approximation Algorithm ......Page 119
5.6 A Distributed On-Line Protocol ......Page 121
5.7.1 Simulation Setup ......Page 124
5.7.2 Performance of the Off-Line Algorithms ......Page 127
5.7.3 Performance of the On-Line Protocol ......Page 130
5.8 Summary ......Page 133
6.1 Overview ......Page 137
6.1.1 Technical Overview ......Page 138
6.2 Related Work ......Page 139
6.3.1 Nomenclature ......Page 141
6.3.2 Network Model ......Page 142
6.3.3 Flow-Based Data Gathering ......Page 143
6.3.4 Discussion ......Page 144
6.3.5 An Example ......Page 145
6.4 Problem Definition ......Page 146
6.5.1 Example Revisited ......Page 147
6.5.2 Determining the Optimal Flow ......Page 148
6.6.1 Analysis for a Grid Deployment ......Page 151
6.6.2 Tradeoffs Between SPT and MST ......Page 155
6.7 A Randomized O(log²v) Approximation......Page 158
6.8.1 Simulation Setup ......Page 161
6.8.2 Results ......Page 162
6.9 Summary ......Page 164
7.1 Concluding Remarks ......Page 169
7.2.1 Adaptive Fidelity Algorithms ......Page 171
7.2.2 A Broad View of Future Research ......Page 172
Bibliography ......Page 177
Appendix A Correctness of EMR-Algo ......Page 191
Appendix B Performance Bound of SPT and MST for TDG problem with grid deployment ......Page 197
Index ......Page 199
