Wireless Sensor Networks: Signal Processing and Communications Perspectives

Wireless Sensor Networks......Page 4
Contents......Page 8
List of Contributors......Page 16
1 Introduction......Page 20
Part I Fundamental Properties and Limits......Page 26
2.1 Introduction......Page 28
2.2 Sensor Network Models......Page 29
2.2.1 The Linear Gaussian Sensor Network......Page 31
2.3.1 Distributed Source Coding......Page 33
2.3.2 Distributed Channel Coding......Page 43
2.3.3 End-to-end Performance of Digital Architectures......Page 50
2.4 The Price of Digital Architectures......Page 52
2.5 Bounds on General Architectures......Page 55
2.6 Concluding Remarks......Page 57
Bibliography......Page 58
3.1 Introduction......Page 62
3.2 Communication Complexity Model......Page 65
3.3.1 Geographical Models of Wireless Communication Networks......Page 68
3.3.3 Symmetric Functions and Types......Page 70
3.3.4 The Collocated Network......Page 71
3.3.5 Subclasses of Symmetric Functions: Type-sensitive and Type-threshold......Page 72
3.3.6 Results on Maximum Throughput in Collocated Networks......Page 74
3.3.7 Multi-Hop Networks: The Random Planar Network......Page 76
3.3.8 Other Acyclic Networks......Page 78
3.4 Wireless Networks with Noisy Communications: Reliable Computation in a Collocated Broadcast Network......Page 79
3.4.1 The Sum of the Parity of the Measurements......Page 80
3.5 Towards an Information Theoretic Formulation......Page 81
3.6 Conclusion......Page 84
Bibliography......Page 85
4.1 Introduction......Page 88
4.1.1 Large-Scale Detection Applications......Page 89
4.1.2 Sensor Network as an Encoder......Page 90
4.1.3 Information Theory Context......Page 92
4.2.1 Sensor Network Model with Arbitrary Connections......Page 93
4.2.2 Random Coding and Method of Types......Page 95
4.2.3 Sensing Capacity Theorem......Page 97
4.2.4 Illustration of Sensing Capacity Bound......Page 102
4.3 Extensions to Other Sensor Network Models......Page 103
4.3.1 Models with Localized Sensing......Page 105
4.3.2 Target Models......Page 106
4.4 Conclusion......Page 107
Bibliography......Page 108
5.1 Introduction......Page 112
5.2.1 Network Characteristics and Lifetime Definition......Page 113
5.2.2 Law of Lifetime......Page 114
5.3 Fundamental Performance Limit: A Stochastic Shortest Path Framework......Page 115
5.3.1 Problem Statement......Page 116
5.3.2 SSP Formulation......Page 117
5.3.3 Fundamental Performance Limit on Network Lifetime......Page 119
5.3.4 Computing the Limiting Performance with Polynomial Complexity in Network Size......Page 120
5.4 Distributed Asymptotically Optimal Transmission Scheduling......Page 122
5.4.1 Dynamic Protocol for Lifetime Maximization......Page 123
5.4.2 Dynamic Nature of DPLM......Page 124
5.4.3 Asymptotic Optimality of DPLM......Page 125
5.4.4 Distributed Implementation......Page 126
5.4.5 Simulation Studies......Page 127
5.5 A Brief Overview of Network Lifetime Analysis......Page 132
Bibliography......Page 133
Part II Signal Processing for Sensor Networks......Page 136
6 Detection in Sensor Networks......Page 138
6.1 Centralized Detection......Page 139
6.2 The Classical Decentralized Detection Framework......Page 140
6.3 Decentralized Detection in Wireless Sensor Networks......Page 143
6.3.1 Sensor Nodes......Page 144
6.3.2 Network Architectures......Page 145
6.4 Wireless Sensor Networks......Page 146
6.4.1 Detection under Capacity Constraint......Page 148
6.4.2 Wireless Channel Considerations......Page 150
6.4.3 Correlated Observations......Page 153
6.4.4 Attenuation and Fading......Page 155
6.5.1 Constructive Interference......Page 158
6.5.2 Message Passing......Page 159
6.5.4 Energy Savings via Censoring and Sleeping......Page 160
6.6 Extensions and Generalizations......Page 161
6.7 Conclusion......Page 162
Bibliography......Page 163
7 Distributed Estimation under Bandwidth and Energy Constraints......Page 168
7.2 Maximum Likelihood Estimation......Page 169
7.2.1 Known Noise pdf with Unknown Variance......Page 171
7.3 Unknown Noise pdf......Page 175
7.4 Estimation of Vector Parameters......Page 179
7.4.1 Colored Gaussian Noise......Page 181
7.5 Maximum a Posteriori Probability Estimation......Page 184
7.5.1 Mean-Squared Error......Page 185
7.6 Dimensionality Reduction for Distributed Estimation......Page 186
7.6.1 Decoupled Distributed Estimation-Compression......Page 187
7.6.2 Coupled Distributed Estimation-Compression......Page 190
7.7 Distortion-Rate Analysis......Page 191
7.7.1 Distortion-Rate for Centralized Estimation......Page 193
7.7.2 Distortion-Rate for Distributed Estimation......Page 197
7.7.3 D-R Upper Bound via Convex Optimization......Page 199
7.8 Conclusion......Page 200
7.9 Further Reading......Page 201
Bibliography......Page 202
8.1 Introduction......Page 204
8.2.1 The Supervised Learning Model......Page 207
8.2.2 Kernel Methods and the Principle of Empirical Risk Minimization......Page 208
8.2.3 Other Learning Algorithms......Page 210
8.3 Distributed Learning in Wireless Sensor Networks......Page 211
8.3.1 A General Model for Distributed Learning......Page 212
8.3.2 Related Work......Page 215
8.4 Distributed Learning in WSNs with a Fusion Center......Page 216
8.4.2 Statistical Limits of Distributed Learning......Page 217
8.5 Distributed Learning in Ad-hoc WSNs with In-network Processing......Page 220
8.5.1 Message-passing Algorithms for Least-Squares Regression......Page 221
8.6 Conclusion......Page 227
Bibliography......Page 228
9.1 Introduction......Page 234
9.2 Graphical Models......Page 235
9.2.1 Definitions and Properties......Page 236
9.2.2 Sum-Product Algorithms......Page 237
9.2.3 Max-Product Algorithms......Page 238
9.2.5 Nonparametric Belief Propagation......Page 239
9.3.1 Self-Localization in Sensor Networks......Page 241
9.3.2 Multi-Object Data Association in Sensor Networks......Page 243
9.4 Message Censoring, Approximation, and Impact on Fusion......Page 245
9.4.1 Message Censoring......Page 246
9.4.2 Trading Off Accuracy for Bits in Particle-Based Messaging......Page 247
9.5 The Effects of Message Approximation......Page 249
9.6 Optimizing the Use of Constrained Resources in Network Fusion......Page 252
9.6.1 Resource Management for Object Tracking in Sensor Networks......Page 253
9.6.2 Distributed Inference with Severe Communication Constraints......Page 258
9.7 Conclusion......Page 262
Bibliography......Page 265
Part III Communications, Networking and Cross-Layered Designs......Page 270
10.1 Introduction......Page 272
10.2.1 Physical Layer Model for Cooperative Radios......Page 273
10.2.2 Cooperative Schemes with Centralized Code Assignment......Page 275
10.3.1 Randomized Code Construction and System Model......Page 276
10.4.1 Characterization of the Diversity Order......Page 279
10.4.2 Simulations and Numerical Evaluations......Page 282
10.5 Analysis of Cooperative Large-scale Networks Utilizing Randomized Cooperative Codes......Page 284
10.5.1 Numerical Evaluations and Further Discussions......Page 287
10.7 Appendix......Page 291
Bibliography......Page 293
11.1 Introduction......Page 296
11.2 Fundamental SPR......Page 298
11.2.1 Broadcast Routing......Page 299
11.2.2 Static Shortest Path Routing......Page 300
11.2.4 Other Approaches......Page 308
11.3.1 Broadcast Methods......Page 309
11.3.2 Shortest Path Routing......Page 310
11.3.3 Other Approaches......Page 312
11.4.1 A Short Survey of Current Protocols......Page 313
11.4.3 Application Dependent SPR: An Illustrative Example......Page 315
11.6.1 Undirected Graphs......Page 324
11.6.2 Directed Graphs......Page 325
Bibliography......Page 326
12.1 Introduction......Page 330
12.2.1 Carrier Sense Multiple Access (CSMA)......Page 332
12.2.2 Time-Division Multiple Access (TDMA)......Page 333
12.3 Energy-Efficient MAC Protocols for Sensor Networks......Page 334
12.4.1 Data Aggregation......Page 337
12.4.2 Distributed Source Coding......Page 338
12.4.3 Spatial Sampling of a Correlated Sensor Field......Page 340
12.5 Cooperative MAC Protocol for Independent Sources......Page 342
12.6 Cooperative MAC Protocol for Correlated Sensors......Page 346
12.6.1 Data Retrieval from Correlated Sensors......Page 347
12.6.2 Generalized Data-Centric Cooperative MAC......Page 355
12.6.3 MAC for Distributed Detection and Estimation......Page 359
12.7 Conclusion......Page 362
Bibliography......Page 363
13.1 Introduction......Page 368
13.1.1 UGSN Sensor Activation and Transmission Scheduling Methodology......Page 369
13.1.2 Fundamental Tools and Literature......Page 370
13.2 Unattended Ground Sensor Network: Capabilities and Objectives......Page 372
13.2.1 Practicalities: Sensor Network Model and Architecture......Page 373
13.2.2 Energy-Efficient Sensor Activation and Transmission Control......Page 374
13.3.1 From Nash to Correlated Equilibrium – An Overview......Page 377
13.3.2 Adaptive Sensor Activation through Regret Tracking......Page 379
13.3.3 Convergence Analysis of Regret-based Algorithms......Page 382
13.4 Energy-Efficient Transmission Scheduling......Page 384
13.4.1 Outline of Markov Decision Processes and Supermodularity......Page 385
13.4.2 Optimal Channel-Aware Transmission Scheduling as a Markov Decision Process......Page 386
13.4.3 Optimality of Threshold Transmission Policies......Page 389
13.5.1 UGSN Sensor Activation Algorithm......Page 393
13.5.2 Energy Throughput Tradeoff via Optimal Transmission Scheduling......Page 397
13.6 Conclusion......Page 400
13.7.1 List of Symbols......Page 401
13.7.3 Proof of Theorem 13.4.4......Page 402
Bibliography......Page 404
Index......Page 408