2007新书：Wireless Sensor Networks Signal Processing and Communication

infotech

Wireless Sensor Networks Signal Processing and Communication

Contents
List of Contributors xiii
1 Introduction 1
Part I Fundamental Properties and Limits 7
2 Information-theoretic Bounds on Sensor Network Performance 9
Michael Gastpar
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Sensor Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 The Linear Gaussian Sensor Network . . . . . . . . . . . . . . . . . 12
2.3 Digital Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Distributed Source Coding . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Distributed Channel Coding . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 End-to-end Performance of Digital Architectures . . . . . . . . . . . 31
2.4 The Price of Digital Architectures . . . . . . . . . . . . . . . . . . . . . . . 33
2.5 Bounds on General Architectures . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3 In-Network Information Processing in Wireless Sensor Networks 43
Arvind Giridhar and P. R. Kumar
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Communication Complexity Model . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Computing Functions over Wireless Networks: Spatial Reuse and Block
Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 Geographical Models of Wireless Communication Networks . . . . 49
3.3.2 Block Computation and Computational Throughput . . . . . . . . . 51
3.3.3 Symmetric Functions and Types . . . . . . . . . . . . . . . . . . . 51
3.3.4 The Collocated Network . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.5 Subclasses of Symmetric Functions: Type-sensitive and
Type-threshold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.6 Results on Maximum Throughput in Collocated Networks . . . . . 55
vi CONTENTS
3.3.7 Multi-Hop Networks: The Random Planar Network . . . . . . . . . 57
3.3.8 Other Acyclic Networks . . . . . . . . . . . . . . . . . . . . . . . 59
3.4 Wireless Networks with Noisy Communications: Reliable Computation in
a Collocated Broadcast Network . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.1 The Sum of the Parity of the Measurements . . . . . . . . . . . . . 61
3.4.2 Threshold Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5 Towards an Information Theoretic Formulation . . . . . . . . . . . . . . . 62
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4 The Sensing Capacity of Sensor Networks 69
Rohit Negi, Yaron Rachlin, and Pradeep Khosla
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.1.1 Large-Scale Detection Applications . . . . . . . . . . . . . . . . . . 70
4.1.2 Sensor Network as an Encoder . . . . . . . . . . . . . . . . . . . . 71
4.1.3 Information Theory Context . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Sensing Capacity of Sensor Networks . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Sensor Network Model with Arbitrary Connections . . . . . . . . . 74
4.2.2 Random Coding and Method of Types . . . . . . . . . . . . . . . . 76
4.2.3 Sensing Capacity Theorem . . . . . . . . . . . . . . . . . . . . . . . 78
4.2.4 Illustration of Sensing Capacity Bound . . . . . . . . . . . . . . . . 83
4.3 Extensions to Other Sensor Network Models . . . . . . . . . . . . . . . . . 84
4.3.1 Models with Localized Sensing . . . . . . . . . . . . . . . . . . . . 86
4.3.2 Target Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5 Law of Sensor Network Lifetime and Its Applications 93
Yunxia Chen and Qing Zhao
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.2 Law of Network Lifetime and General Design Principle . . . . . . . . . . . 94
5.2.1 Network Characteristics and Lifetime Definition . . . . . . . . . . . 94
5.2.2 Law of Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.2.3 A General Design Principle For Lifetime Maximization . . . . . . . 96
5.3 Fundamental Performance Limit: A Stochastic Shortest Path Framework . . 96
5.3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.2 SSP Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.3 Fundamental Performance Limit on Network Lifetime . . . . . . . . 100
5.3.4 Computing the Limiting Performance with Polynomial Complexity
in Network Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4 Distributed Asymptotically Optimal Transmission Scheduling . . . . . . . . 103
5.4.1 Dynamic Protocol for Lifetime Maximization . . . . . . . . . . . . 104
5.4.2 Dynamic Nature of DPLM . . . . . . . . . . . . . . . . . . . . . . . 105
5.4.3 Asymptotic Optimality of DPLM . . . . . . . . . . . . . . . . . . . 106
5.4.4 Distributed Implementation . . . . . . . . . . . . . . . . . . . . . . 107
5.4.5 Simulation Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
CONTENTS vii
5.5 A Brief Overview of Network Lifetime Analysis . . . . . . . . . . . . . . . 113
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Part II Signal Processing for Sensor Networks 117
6 Detection in Sensor Networks 119
Venugopal V. Veeravalli and Jean-Fran¸cois Chamberland
6.1 Centralized Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.2 The Classical Decentralized Detection Framework . . . . . . . . . . . . . . 121
6.2.1 Asymptotic Regime . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.3 Decentralized Detection in Wireless Sensor Networks . . . . . . . . . . . . 124
6.3.1 Sensor Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.3.2 Network Architectures . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.3.3 Data Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.4 Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.4.1 Detection under Capacity Constraint . . . . . . . . . . . . . . . . . 129
6.4.2 Wireless Channel Considerations . . . . . . . . . . . . . . . . . . . 131
6.4.3 Correlated Observations . . . . . . . . . . . . . . . . . . . . . . . . 134
6.4.4 Attenuation and Fading . . . . . . . . . . . . . . . . . . . . . . . . 136
6.5 New Paradigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.5.1 Constructive Interference . . . . . . . . . . . . . . . . . . . . . . . 139
6.5.2 Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.5.3 Cross-Layer Considerations . . . . . . . . . . . . . . . . . . . . . . 141
6.5.4 Energy Savings via Censoring and Sleeping . . . . . . . . . . . . . 141
6.6 Extensions and Generalizations . . . . . . . . . . . . . . . . . . . . . . . . 142
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7 Distributed Estimation under Bandwidth and Energy Constraints 149
Alejandro Ribeiro, Ioannis D. Schizas, Jin-Jun Xiao, Georgios B. Giannakis and
Zhi-Quan Luo
7.1 Distributed Quantization-Estimation . . . . . . . . . . . . . . . . . . . . . . 150
7.2 Maximum Likelihood Estimation . . . . . . . . . . . . . . . . . . . . . . . 150
7.2.1 Known Noise pdf with Unknown Variance . . . . . . . . . . . . . . 152
7.3 Unknown Noise pdf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.3.1 Lower Bound on the MSE . . . . . . . . . . . . . . . . . . . . . . . 160
7.4 Estimation of Vector Parameters . . . . . . . . . . . . . . . . . . . . . . . . 160
7.4.1 Colored Gaussian Noise . . . . . . . . . . . . . . . . . . . . . . . . 162
7.5 Maximum a Posteriori Probability Estimation . . . . . . . . . . . . . . . . . 165
7.5.1 Mean-Squared Error . . . . . . . . . . . . . . . . . . . . . . . . . . 166
7.6 Dimensionality Reduction for Distributed Estimation . . . . . . . . . . . . . 167
7.6.1 Decoupled Distributed Estimation-Compression . . . . . . . . . . . 168
7.6.2 Coupled Distributed Estimation-Compression . . . . . . . . . . . . 171
7.7 Distortion-Rate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7.7.1 Distortion-Rate for Centralized Estimation . . . . . . . . . . . . . . 174
viii CONTENTS
7.7.2 Distortion-Rate for Distributed Estimation . . . . . . . . . . . . . . 178
7.7.3 D-R Upper Bound via Convex Optimization . . . . . . . . . . . . . 180
7.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8 Distributed Learning in Wireless Sensor Networks 185
Joel B. Predd, Sanjeev R. Kulkarni, and H. Vincent Poor
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
8.2 Classical Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.2.1 The Supervised Learning Model . . . . . . . . . . . . . . . . . . . . 188
8.2.2 Kernel Methods and the Principle of Empirical Risk
Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.2.3 Other Learning Algorithms . . . . . . . . . . . . . . . . . . . . . . 191
8.3 Distributed Learning in Wireless Sensor Networks . . . . . . . . . . . . . . 192
8.3.1 A General Model for Distributed Learning . . . . . . . . . . . . . . 193
8.3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
8.4 Distributed Learning in WSNs with a Fusion Center . . . . . . . . . . . . . 197
8.4.1 A Clustered Approach . . . . . . . . . . . . . . . . . . . . . . . . . 198
8.4.2 Statistical Limits of Distributed Learning . . . . . . . . . . . . . . . 198
8.5 Distributed Learning in Ad-hoc WSNs with In-network Processing . . . . . 201
8.5.1 Message-passing Algorithms for Least-Squares Regression . . . . . 202
8.5.2 Other Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
9 Graphical Models and Fusion in Sensor Networks 215
M¨ujdat C¸ etin, Lei Chen, John W. Fisher III, Alexander T. Ihler,
O. Patrick Kreidl, Randolph L. Moses, Martin J. Wainwright,
Jason L. Williams, and Alan S. Willsky
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.2 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
9.2.1 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . . . 217
9.2.2 Sum-Product Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 218
9.2.3 Max-Product Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 219
9.2.4 Loopy Belief Propagation . . . . . . . . . . . . . . . . . . . . . . . 220
9.2.5 Nonparametric Belief Propagation . . . . . . . . . . . . . . . . . . . 220
9.3 From Sensor Network Fusion to Graphical Models . . . . . . . . . . . . . 222
9.3.1 Self-Localization in Sensor Networks . . . . . . . . . . . . . . . . . 222
9.3.2 Multi-Object Data Association in Sensor Networks . . . . . . . . . 224
9.4 Message Censoring, Approximation, and Impact on Fusion . . . . . . . . . 226
9.4.1 Message Censoring . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
9.4.2 Trading Off Accuracy for Bits in Particle-Based Messaging . . . . . 228
9.5 The Effects of Message Approximation . . . . . . . . . . . . . . . . . . . 230
9.6 Optimizing the Use of Constrained Resources in Network Fusion . . . . . . 233
9.6.1 Resource Management for Object Tracking in Sensor Networks . . 234
9.6.2 Distributed Inference with Severe Communication Constraints . . . 239
CONTENTS ix
9.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
Part III Communications, Networking and Cross-Layered
Designs 251
10 Randomized Cooperative Transmission in Large-Scale Sensor Networks 253
Birsen Sirkeci-Mergen and Anna Scaglione
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
10.2 Transmit Cooperation in Sensor Networks . . . . . . . . . . . . . . . . . . 254
10.2.1 Physical Layer Model for Cooperative Radios . . . . . . . . . . . . 254
10.2.2 Cooperative Schemes with Centralized Code Assignment . . . . . . 256
10.3 Randomized Distributed Cooperative Schemes . . . . . . . . . . . . . . . . 257
10.3.1 Randomized Code Construction and System Model . . . . . . . . . 257
10.4 Performance of Randomized Cooperative Codes . . . . . . . . . . . . . . . 260
10.4.1 Characterization of the Diversity Order . . . . . . . . . . . . . . . . 260
10.4.2 Simulations and Numerical Evaluations . . . . . . . . . . . . . . . . 263
10.5 Analysis of Cooperative Large-scale Networks Utilizing Randomized
Cooperative Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10.5.1 Numerical Evaluations and Further Discussions . . . . . . . . . . . 268
10.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
10.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
11 Application Dependent Shortest Path Routing in Ad-Hoc Sensor Networks 277
Saswat Misra, Lang Tong, and Anthony Ephremides
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
11.1.1 Major Classifications . . . . . . . . . . . . . . . . . . . . . . . . . . 279
11.2 Fundamental SPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
11.2.1 Broadcast Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
11.2.2 Static Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . 281
11.2.3 Adaptive Shortest Path Routing . . . . . . . . . . . . . . . . . . . . 289
11.2.4 Other Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
11.3 SPR for Mobile Wireless Networks . . . . . . . . . . . . . . . . . . . . . . 290
11.3.1 Broadcast Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
11.3.2 Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . . . . 291
11.3.3 Other Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
11.4 SPR for Ad-Hoc Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . 294
11.4.1 A Short Survey of Current Protocols . . . . . . . . . . . . . . . . . 294
11.4.2 An Argument for Application Dependent Design . . . . . . . . . . . 296
11.4.3 Application Dependent SPR: An Illustrative Example . . . . . . . . 296
11.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
11.6 A Short Review of Basic Graph Theory . . . . . . . . . . . . . . . . . . . . 305
11.6.1 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
11.6.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
x CONTENTS
12 Data-Centric and Cooperative MAC Protocols for Sensor Networks 311
Yao-Win Hong and Pramod K. Varshney
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
12.2 Traditional Medium Access Control Protocols: Random Access and
Deterministic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
12.2.1 Carrier Sense Multiple Access (CSMA) . . . . . . . . . . . . . . . 313
12.2.2 Time-Division Multiple Access (TDMA) . . . . . . . . . . . . . . . 314
12.3 Energy-Efficient MAC Protocols for Sensor Networks . . . . . . . . . . . . 315
12.4 Data-Centric MAC Protocols for Sensor Networks . . . . . . . . . . . . . . 318
12.4.1 Data Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
12.4.2 Distributed Source Coding . . . . . . . . . . . . . . . . . . . . . . . 319
12.4.3 Spatial Sampling of a Correlated Sensor Field . . . . . . . . . . . . 321
12.5 Cooperative MAC Protocol for Independent Sources . . . . . . . . . . . . . 323
12.6 Cooperative MAC Protocol for Correlated Sensors . . . . . . . . . . . . . . 327
12.6.1 Data Retrieval from Correlated Sensors . . . . . . . . . . . . . . . . 328
12.6.2 Generalized Data-Centric Cooperative MAC . . . . . . . . . . . . . 336
12.6.3 MAC for Distributed Detection and Estimation . . . . . . . . . . . 340
12.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
13 Game Theoretic Activation and Transmission Scheduling in Unattended
Ground Sensor Networks: A Correlated Equilibrium Approach 349
Vikram Krishnamurthy, Michael Maskery, and Minh Hanh Ngo
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
13.1.1 UGSN Sensor Activation and Transmission Scheduling
Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
13.1.2 Fundamental Tools and Literature . . . . . . . . . . . . . . . . . . . 351
13.2 Unattended Ground Sensor Network: Capabilities and Objectives . . . . . . 353
13.2.1 Practicalities: Sensor Network Model and Architecture . . . . . . . 354
13.2.2 Energy-Efficient Sensor Activation and Transmission Control . . . . 355
13.3 Sensor Activation as the Correlated Equilibrium . . . . . . . . . . . . . . . 358
13.3.1 From Nash to Correlated Equilibrium – An Overview . . . . . . . . 358
13.3.2 Adaptive Sensor Activation through Regret Tracking . . . . . . . . 360
13.3.3 Convergence Analysis of Regret-based Algorithms . . . . . . . . . 363
13.4 Energy-Efficient Transmission Scheduling . . . . . . . . . . . . . . . . . . . 365
13.4.1 Outline of Markov Decision Processes and Supermodularity . . . . 366
13.4.2 Optimal Channel-Aware Transmission Scheduling as a Markov
Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.4.3 Optimality of Threshold Transmission Policies . . . . . . . . . . . . 370
13.5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
13.5.1 UGSN Sensor Activation Algorithm . . . . . . . . . . . . . . . . . 374
13.5.2 Energy Throughput Tradeoff via Optimal Transmission
Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
13.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
CONTENTS xi
13.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
13.7.1 List of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
13.7.2 Proof of Lemma 13.4.3 . . . . . . . . . . . . . . . . . . . . . . . . 383
13.7.3 Proof of Theorem 13.4.4 . . . . . . . . . . . . . . . . . . . . . . . . 383
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
Index 389

grissom555

感謝分享

chentiejian

好书，多谢了，呵呵，正需要

WXY650713

好书，支持。

mnbvcxz0717

多谢分享

xiaocun

xingbowang

好书,FengZhao 是无线传感器网络协同信号处理方面的专家。这本书很值得看。

chenxinkai

very good!

fuhua98

Part2 和Part3呢？

w20082008

同上！！！其他呢