Wireless Sensor Networks – Signal Processing and Communications Perspectives

Ananthram Swami, Army Research Laboratory, USA. Qing Zhao, Assistant Professor, University of California, USA. Yao-Win Hong, Assistant Professor, National Tsing hua University, Taiwan, ROC. Lang Tong, Professor, Cornell University, USA.

List of Contributors. 1. Introduction. Part I. Fundamental Properties and Limits. 2. Information-theoretic Bounds on Sensor Network Performance (Michael Gastpar). 2.1 Introduction. 2.2 Sensor Network Models. 2.2.1 The Linear Gaussian Sensor Network. 2.3 Digital Architectures. 2.3.1 Distributed Source Coding. 2.3.2 Distributed Channel Coding. 2.3.3 End-to-end Performance of Digital Architectures... 2.4 The Price of Digital Architectures. 2.5 Bounds on General Architectures. 2.6 Concluding Remarks and Some Interesting Questions. Bibliography. 3 In-Network Information Processing in Wireless Sensor Networks (Arvind Giridhar and P. R. Kumar). 3.1 Introduction. 3.2 Communication Complexity Model. 3.3 Computing Functions Over Wireless Networks: Spatial Reuse and Block Computation . 3.3.1 Geographical Models of Wireless Communication Networks. 3.3.2 Block Computation and Computational Throughput. 3.3.3 Symmetric Functionsand Types. 3.3.4 The Collocated Network. 3.3.5 Subclasses of Symmetric Functions: Type-sensitive and Type-threshold. 3.3.6 Results on Maximum Throughput in Collocated Networks. 3.3.7 Multi-Hop Networks: The Random Planar Network. 3.3.8 Other Acyclic Networks. 3.4 Wireless Networks with Noisy Communications: Reliable Computation in a Collocated Broadcast Network. 3.4.1 The Sum of the Parity of the Measurements. 3.4.2 Threshold Functions. 3.5 Towards an Information Theoretic Formulation. 3.6 Conclusion. Bibliography. 4 The Sensing Capacity of Sensor Networks (Rohit Negi, Yaron Rachlin, and Pradeep Khosla). 4.1 Introduction. 4.1.1 Large-Scale Detection Applications. 4.1.2 SensorNetworkas an Encoder. 4.1.3 Information Theory Context. 4.2 Sensing Capacity of Sensor Networks. 4.2.1 Sensor Network Model with Arbitrary Connections. 4.2.2 Random Coding and Method of Types. 4.2.3 Sensing Capacity Theorem. 4.2.4 Illustration of Sensing Capacity Bound. 4.3 Extensions to other Sensor Network Models. 4.3.1 Models with Localized Sensing. 4.3.2 Target Models. 4.4 Discussion and Open Problems. Bibliography. 5. Law of Sensor Network Lifetime and Its Applications (Yunxia Chen and Qing Zhao). 5.1 Introduction. 5.2 Law of Network Lifetime and General Design Principle. 5.2.1 Network characteristics and lifetime definition. 5.2.2 Law of lifetime. 5.2.3 A general design principle for lifetime maximization. 5.3 Fundamental Performance Limit: A Stochastic Shortest Path Framework. 5.3.1 Problemstatement. 5.3.2 SSPformulation. 5.3.3 Fundamental performance limit on network lifetime. 5.3.4 Computing the limiting performance with polynomial complexity in network size. 5.4 Distributed Asymptotically Optimal Transmission Scheduling. 5.4.1 Dynamicprotocol for lifetimemaximization. 5.4.2 Dynamicnature of DPLM . 5.4.3 Asymptotic optimality of DPLM. 5.4.4 Distributedimplementation. 5.4.5 Simulation studies. 5.5 A Brief Overview of Network Lifetime Analysis. 5.6 Conclusion. Bibliography. Part II. Signal Processing for Sensor Networks. 6. Detection in Sensor Networks. 6.1 Centralized Detection. 6.2 The Classical Decentralized Detection Framework. 6.2.1 AsymptoticRegime. 6.3 Decentralized Detection in Wireless Sensor Networks. 6.3.1 Sensor Nodes. 6.3.2 Network Architectures... 6.3.3 Data Processing. 6.4 Wireless Sensor Networks. 6.4.1 Detection under Capacity Constraint. 6.4.2 Wireless Channel Considerations. 6.4.3 Correlated Observations. 6.4.4 Attenuation and Fading. 6.5 New Paradigms. 6.5.1 Constructive Interference. 6.5.2 Message Passing. 6.5.3 Cross-Layer Considerations. 6.5.4 Energy Savings via Censoringand Sleeping. 6.6 Extensions and Generalizations. 6.7 Discussion and Concluding Remarks. Bibliography. 7. Distributed Estimation Under Bandwidth and Energy Constraints (Alejandro Ribeiro, Ioannis D. Schizas, Jin-Jun Xiao, Georgios B. Giannakis and Zhi-Quan Luo). 7.1 Distributed Quantization-Estimation. 7.2 Maximum Likelihood Estimation. 7.2.1 Known Noise pdf with Unknown Variance. 7.3 Unknown noise pdf. 7.3.1 Lower bound on the MSE. 7.4 Estimation of Vector parameters. 7.4.1 Colored Gaussian Noise. 7.5 Maximum a Posteriori Probability Estimation. 7.5.1 Mean-Squared Error. 7.6 Dimensionality Reduction for Distributed Estimation. 7.6.1 Decoupled Distributed Estimation-Compression. 7.6.2 Coupled Distributed Estimation-Compression. 7.7 Distortion-RateAnalysis. 7.7.1 Distortion-Rate for Centralized Estimation. 7.7.2 Distortion-RateforDistributedEstimation. 7.7.3 D-R Upper Bound via Convex Optimization. 7.8 Conclusion. 7.9 Further Reading. Bibliography. 8. Distributed Learning in Wireless Sensor Networks (Joel B. Predd, Sanjeev R. Kulkarni, and H. Vincent Poor). 8.1 Introduction. 8.2 Classical Learning. 8.3 Distributed Learningin Wireless Sensor Networks. 8.3.1 A Genera lModel for Distributed Learning. 8.3.2 Related Work. 8.4 Distributed Learningin WSNs with a Fusion Center. 8.4.1 A Clustered Approach. 8.4.2 Statistical Limits of Distributed Learning. 8.5 Distributed Learningin Ad-hocWSNs with In-network Processing. 8.5.1 Message-passing Algorithms for Least-Squares Regression. 8.5.2 Other Work. 8.6 Conclusion. Bibliography. 9. Graphical Models and Fusion in Sensor Networks (M..ujdat CC 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. 9.2 Graphical Models. 9.2.1 Definitions and Properties. 9.2.2 Sum-Product Algorithms. 9.2.3 Max-Product Algorithms. 9.2.4 Loopy Belief Propagation. 9.2.5 Nonparametric Belief Propagation. 9.3 From Sensor Network Fusion to Graphical Models. 9.3.1 Self-Localization in Sensor Networks. 9.3.2 Multi-Object Data Association in Sensor Networks. 9.4 Message Censoring, Approximation,and Impacton Fusion. 9.4.1 Message Censoring. 9.4.2 Trading Off Accuracy for Bits in Particle-Based Messaging. 9.5 The Effects of Message Approximation . 9.6 Optimizing theUse of Constrained Resources in Network Fusion. 9.6.1 Resource management forobject trackingin sensor networks. 9.6.2 Distributed Inference with Severe Communication Constraints. 9.7 Conclusion. Bibliography. Part III. Communications, Networking and Cross-Layered Designs. 10. Randomized Cooperative Transmission in Large-Scale Sensor Networks (Birsen Sirkeci-Mergen and Anna Scaglione). 10.1 Introduction. 10.2 Transmit cooperation in sensor networks. 10.2.1 Physical Layer Model for Cooperative Radios. 10.2.2 Cooperative schemes with centralized code assignment. 10.3 Randomized distributed cooperative schemes. 10.3.1 Randomized code construction and system model. 10.4 Performance of Randomized Cooperative Codes. 10.4.1 Characterization of the Diversity Order. 10.4.2 Simulations and Numerical Evaluations. 10.5 Analysis of Cooperative Large-scale Networks utilizing Randomized Cooperative Codes. 10.5.1 Numerical Evaluations and Further Discussions. 10.6 Conclusion. 10.7 Appendix. Bibliography. 11. Application Dependent Shortest Path Routing in Ad-Hoc Sensor Networks (Saswat Misra, Lang Tong, and Anthony Ephremides). 11.1 Introduction. 11.1.1 Major Classifications. 11.2 Fundamental SPR. 11.2.1 Broadcast Routing. 11.2.2 Static Shortest Path Routing. 11.2.3 Adaptive Shortest Path Routing. 11.2.4 Other Approaches. 11.3 SPR for MobileWireless Networks. 11.3.1 Broadcast Methods. 11.3.2 Shortest Path Routing. 11.3.3 Other Approaches. 11.4 SPRf or Ad-Hoc Sensor Networks. 11.4.1 A Short Survey of Current Protocols. 11.4.2 An Argument for Application Dependent Design. 11.4.3 Application Dependent SPR:An Illustrative Example. 11.5 Conclusion. 11.6 A Short Review of Basic Graph Theory. 11.6.1 Undirected Graph.s 11.6.2 DirectedGraphs. Bibliography. 12. Data-Centric and CooperativeMAC Protocols for Sensor Networks (Yao-Win Hong and Pramod K. Varshney). 12.1 Introduction. 12.2 Traditional Medium Access Control Protocols: Random Access and Deterministic Scheduling. 12.2.1 Carrier Sense Multiple Access (CSMA) . 12.2.2 Time-Division Multiple Access (TDMA). 12.3 Energy Efficient MAC Protocols for Sensor Networks. 12.4 Data-Centric MAC Protocols for Sensor Networks. 12.4.1 Data Aggregation. 12.4.2 Distributed Source Coding. 12.4.3 Spatial Samplingof a Correlated Sensor Field. 12.5 Cooperative MAC Protocol for Independent Sources. 12.6 Cooperative MAC Protocol for Correlated Sensors. 12.6.1 Data Retrieval from Correlated Sensors. 12.6.2 Generalized Data-Centric Cooperative MAC. 12.6.3 MAC for Distributed Detection and Estimation. 12.7 DiscussionandFutureResearchDirections. Bibliography. 13. Game Theoretic Activation and Transmission Scheduling in Unattended Ground Sensor Networks: A Correlated Equilibrium Approach (Vikram Krishnamurthy, Michael Maskery, and Minh Hanh Ngo). 13.1 Introduction. 13.1.1 UGSN Sensor Activation and Transmission Scheduling Methodology. 13.1.2 Fundamental Tools and Literature. 13.2 Unattended Ground Sensor Network: Capabilities and Objectives. 13.2.1 Practicalities: Sensor Network Model and Architecture. 13.2.2 Energy Efficient Sensor Activation and Transmission Control. 13.3 Sensor Activation as the Correlated Equilibrium of a Noncooperative Game. 13.3.1 From Nash to Correlated Equilibrium - An Overview. 13.3.2 Adaptive Sensor Activation through Regret Tracking. 13.3.3 Convergence Analysis of Regret-based Algorithms. 13.4 Energy Efficient Transmission Scheduling in UGSN - A Markov Decision Process Approach. 13.4.1 Outline of Markov Decision Processes and Supermodularity. 13.4.2 Optimal Channel-Aware Transmission Scheduling as a Markov Decision Process. 13.4.3 Optimality of Threshold Transmission Policies. 13.5 Numerical Results. 13.5.1 UGSN Sensor Activation Algorithm. 13.5.2 Energy Throughput Tradeoff via Optimal Transmission Scheduling. 13.6 Discussion and Extensions . 13.7 Appendix. 13.7.1 List of Symbols. 13.7.2 Proof of Lemma13.4.3. 13.7.3 Proof of Theorem13.4.4. Bibliography. Index.