Bibliographic record and links to related information available from the Library of Congress catalog.
Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.
Contents 1 Introduction 1 2 Information-theoretic Bounds on Sensor Network Performance 11 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 SensorNetworkModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 TheLinearGaussianSensorNetwork . . . . . . . . . . . . . . . . . 16 2.3 DigitalArchitectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.1 DistributedSourceCoding . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 DistributedChannelCoding . . . . . . . . . . . . . . . . . . . . . . 33 2.3.3 End-to-endPerformanceofDigitalArchitectures . . . . . . . . . . . 44 2.4 ThePriceofDigitalArchitectures . . . . . . . . . . . . . . . . . . . . . . . 47 2.5 Bounds on General Architectures . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6 ConcludingRemarks andSome InterestingQuestions . . . . . . . . . . . . . 55 Bibliography 57 3 In-Network Information Processing in Wireless Sensor Networks 63 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.2 CommunicationComplexityModel . . . . . . . . . . . . . . . . . . . . . . 68 3.3 Computing Functions Over Wireless Networks: Spatial Reuse and Block Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.3.1 GeographicalModelsofWirelessCommunicationNetworks . . . . 73 3.3.2 Block Computation and Computational Throughput . . . . . . . . . 75 3.3.3 SymmetricFunctionsandTypes . . . . . . . . . . . . . . . . . . . . 76 3.3.4 TheCollocatedNetwork . . . . . . . . . . . . . . . . . . . . . . . . 77 3.3.5 Subclasses of Symmetric Functions: Type-sensitive and Type-threshold 79 3.3.6 Results on Maximum Throughput in Collocated Networks . . . . . . 81 3.3.7 Multi-Hop Networks: The Random Planar Network . . . . . . . . . 85 3.3.8 OtherAcyclicNetworks . . . . . . . . . . . . . . . . . . . . . . . . 88 3.4 Wireless Networks with Noisy Communications: Reliable Computation in a CollocatedBroadcastNetwork . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.4.1 TheSumof theParityof theMeasurements . . . . . . . . . . . . . . 91 3.4.2 ThresholdFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.5 Towards anInformationTheoreticFormulation . . . . . . . . . . . . . . . . 93 3.6 ConcludingRemarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Bibliography 101 4 The Sensing Capacity of Sensor Networks 103 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.1.1 Large-ScaleDetectionApplications . . . . . . . . . . . . . . . . . . 104 4.1.2 SensorNetworkas anEncoder . . . . . . . . . . . . . . . . . . . . . 107 4.1.3 InformationTheoryContext . . . . . . . . . . . . . . . . . . . . . . 109 4.2 SensingCapacityofSensorNetworks . . . . . . . . . . . . . . . . . . . . . 111 4.2.1 SensorNetworkModelwithArbitraryConnections . . . . . . . . . . 111 4.2.2 Random Coding and Method of Types . . . . . . . . . . . . . . . . . 114 4.2.3 SensingCapacityTheorem . . . . . . . . . . . . . . . . . . . . . . . 116 4.2.4 Illustration of Sensing Capacity Bound . . . . . . . . . . . . . . . . 124 4.3 Extensions tootherSensorNetworkModels . . . . . . . . . . . . . . . . . . 126 4.3.1 ModelswithLocalizedSensing . . . . . . . . . . . . . . . . . . . . 128 4.3.2 TargetModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.4 DiscussionandOpenProblems . . . . . . . . . . . . . . . . . . . . . . . . . 131 Bibliography 133 4 Law of Sensor Network Lifetime and Its Applications 137 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.2 LawofNetworkLifetime andGeneralDesignPrinciple . . . . . . . . . . . . 139 4.2.1 Network characteristics and lifetime definition . . . . . . . . . . . . 139 4.2.2 Lawof lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 4.2.3 Ageneraldesignprinciplefor lifetimemaximization . . . . . . . . . 142 4.3 Fundamental Performance Limit: A Stochastic Shortest Path Framework . . . 143 4.3.1 Problemstatement . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.3.2 SSPformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 4.3.3 Fundamental performance limit on network lifetime . . . . . . . . . 149 4.3.4 Computing the limiting performance with polynomial complexity in networksize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.4 DistributedAsymptoticallyOptimalTransmissionScheduling . . . . . . . . 154 4.4.1 Dynamicprotocol for lifetimemaximization . . . . . . . . . . . . . 154 4.4.2 DynamicnatureofDPLM . . . . . . . . . . . . . . . . . . . . . . . 155 4.4.3 Asymptotic optimality of DPLM . . . . . . . . . . . . . . . . . . . . 157 4.4.4 Distributedimplementation . . . . . . . . . . . . . . . . . . . . . . 159 4.4.5 Simulationstudies . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 4.5 ABriefOverviewofNetworkLifetimeAnalysis . . . . . . . . . . . . . . . . 166 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Bibliography 169 5 Detection in Sensor Networks 175 5.1 CentralizedDetection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 5.2 The Classical Decentralized Detection Framework . . . . . . . . . . . . . . . 178 5.2.1 AsymptoticRegime . . . . . . . . . . . . . . . . . . . . . . . . . . 182 5.3 Decentralized Detection in Wireless Sensor Networks . . . . . . . . . . . . . 184 5.3.1 SensorNodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 5.3.2 NetworkArchitectures . . . . . . . . . . . . . . . . . . . . . . . . . 186 5.3.3 DataProcessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.4 WirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.4.1 Detection under Capacity Constraint . . . . . . . . . . . . . . . . . . 191 5.4.2 WirelessChannelConsiderations . . . . . . . . . . . . . . . . . . . 193 5.4.3 CorrelatedObservations . . . . . . . . . . . . . . . . . . . . . . . . 199 5.4.4 AttenuationandFading . . . . . . . . . . . . . . . . . . . . . . . . . 201 5.5 NewParadigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 5.5.1 ConstructiveInterference . . . . . . . . . . . . . . . . . . . . . . . . 206 5.5.2 MessagePassing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 5.5.3 Cross-LayerConsiderations . . . . . . . . . . . . . . . . . . . . . . 209 5.5.4 EnergySavingsviaCensoringandSleeping . . . . . . . . . . . . . . 210 5.6 ExtensionsandGeneralizations . . . . . . . . . . . . . . . . . . . . . . . . . 211 5.7 DiscussionandConcludingRemarks . . . . . . . . . . . . . . . . . . . . . . 213 Bibliography 215 6 Distributed Estimation Under Bandwidth and Energy Constraints 221 6.1 DistributedQuantization-Estimation . . . . . . . . . . . . . . . . . . . . . . 223 6.2 Maximum Likelihood Estimation . . . . . . . . . . . . . . . . . . . . . . . . 224 6.2.1 Known Noise pdf with Unknown Variance . . . . . . . . . . . . . . 226 6.3 Unknown noise pdf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 6.3.1 Lower bound on the MSE . . . . . . . . . . . . . . . . . . . . . . . 237 6.4 EstimationofVectorparameters . . . . . . . . . . . . . . . . . . . . . . . . 237 6.4.1 ColoredGaussianNoise . . . . . . . . . . . . . . . . . . . . . . . . 240 6.5 Maximum a Posteriori Probability Estimation . . . . . . . . . . . . . . . . . 244 6.5.1 Mean-SquaredError . . . . . . . . . . . . . . . . . . . . . . . . . . 246 6.6 Dimensionality Reduction for Distributed Estimation . . . . . . . . . . . . . 248 6.6.1 Decoupled Distributed Estimation-Compression . . . . . . . . . . . 249 6.6.2 Coupled Distributed Estimation-Compression . . . . . . . . . . . . . 254 6.7 Distortion-RateAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 6.7.1 Distortion-RateforCentralizedEstimation . . . . . . . . . . . . . . 258 6.7.2 Distortion-RateforDistributedEstimation . . . . . . . . . . . . . . . 264 6.7.3 D-R Upper Bound via Convex Optimization . . . . . . . . . . . . . . 268 6.8 ClosingComments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 6.9 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 Bibliography 273 7 Distributed Learning in Wireless Sensor Networks 277 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 7.2 ClassicalLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 7.3 DistributedLearninginWirelessSensorNetworks . . . . . . . . . . . . . . . 288 7.3.1 AGeneralModel forDistributedLearning . . . . . . . . . . . . . . 290 7.3.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 7.4 DistributedLearninginWSNswithaFusionCenter . . . . . . . . . . . . . . 296 7.4.1 AClusteredApproach . . . . . . . . . . . . . . . . . . . . . . . . . 296 7.4.2 StatisticalLimitsofDistributedLearning . . . . . . . . . . . . . . . 297 7.5 DistributedLearninginAd-hocWSNswithIn-networkProcessing . . . . . . 302 7.5.1 Message-passingAlgorithms forLeast-SquaresRegression . . . . . . 303 7.5.2 OtherWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 7.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 Bibliography 315 8 GraphicalModels and Fusion in Sensor Networks 325 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 8.2 GraphicalModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 8.2.1 DefinitionsandProperties . . . . . . . . . . . . . . . . . . . . . . . 328 8.2.2 Sum?Product Algorithms . . . . . . . . . . . . . . . . . . . . . . . 330 8.2.3 Max?Product Algorithms . . . . . . . . . . . . . . . . . . . . . . . 332 8.2.4 LoopyBeliefPropagation . . . . . . . . . . . . . . . . . . . . . . . 333 8.2.5 Nonparametric Belief Propagation . . . . . . . . . . . . . . . . . . . 334 8.3 FromSensorNetworkFusiontoGraphicalModels . . . . . . . . . . . . . . 336 8.3.1 Self-LocalizationinSensorNetworks . . . . . . . . . . . . . . . . . 336 8.3.2 Multi-Object Data Association in Sensor Networks . . . . . . . . . . 340 8.4 MessageCensoring,Approximation,andImpactonFusion . . . . . . . . . . 343 8.4.1 MessageCensoring . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 8.4.2 TradingOffAccuracyforBits inParticle-BasedMessaging . . . . . 345 8.5 TheEffectsofMessageApproximation . . . . . . . . . . . . . . . . . . . . 348 8.6 OptimizingtheUse ofConstrainedResources inNetworkFusion . . . . . . . 351 8.6.1 Resourcemanagement forobject trackingin sensornetworks . . . . . 354 8.6.2 DistributedInferencewithSevereCommunicationConstraints . . . . 360 8.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 Bibliography 373 9 Randomized Cooperative Transmission in Large-Scale Sensor Networks 379 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 9.2 Transmit cooperation in sensor networks . . . . . . . . . . . . . . . . . . . . 381 9.2.1 Physical Layer Model for Cooperative Radios . . . . . . . . . . . . . 381 9.2.2 Cooperative schemes with centralized code assignment . . . . . . . . 384 9.3 Randomized distributed cooperative schemes . . . . . . . . . . . . . . . . . 386 9.3.1 Randomized code construction and system model . . . . . . . . . . . 386 9.4 Performance of Randomized Cooperative Codes . . . . . . . . . . . . . . . . 390 9.4.1 Characterizationof theDiversityOrder . . . . . . . . . . . . . . . . 391 9.4.2 SimulationsandNumericalEvaluations . . . . . . . . . . . . . . . . 395 9.5 Analysis of Cooperative Large-scale Networks utilizing Randomized CooperativeCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 9.5.1 NumericalEvaluationsandFurtherDiscussions . . . . . . . . . . . . 402 9.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 9.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 Bibliography 411 10 Application Dependent Shortest Path Routing in Ad-Hoc Sensor Networks 415 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 10.1.1 MajorClassifications . . . . . . . . . . . . . . . . . . . . . . . . . . 417 10.2 Fundamental SPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 10.2.1 BroadcastRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 10.2.2 StaticShortestPathRouting . . . . . . . . . . . . . . . . . . . . . . 421 10.2.3 AdaptiveShortestPathRouting . . . . . . . . . . . . . . . . . . . . 432 10.2.4 OtherApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 10.3 SPRforMobileWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . 434 10.3.1 Broadcast Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 10.3.2 ShortestPathRouting . . . . . . . . . . . . . . . . . . . . . . . . . 436 10.3.3 OtherApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 10.4 SPRforAd-HocSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . 441 10.4.1 AShortSurveyofCurrentProtocols . . . . . . . . . . . . . . . . . . 441 10.4.2 AnArgument forApplicationDependentDesign . . . . . . . . . . . 443 10.4.3 ApplicationDependentSPR:AnIllustrativeExample . . . . . . . . . 444 10.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 10.6 AShortReviewofBasicGraphTheory . . . . . . . . . . . . . . . . . . . . 457 10.6.1 UndirectedGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 10.6.2 DirectedGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 Bibliography 461 11 Data-Centric and CooperativeMAC Protocols for Sensor Networks 467 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 11.2 Traditional Medium Access Control Protocols: Random Access and DeterministicScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 11.2.1 Carrier Sense Multiple Access (CSMA) . . . . . . . . . . . . . . . . 471 11.2.2 Time-Division Multiple Access (TDMA) . . . . . . . . . . . . . . . 472 11.3 EnergyEfficientMACProtocols forSensorNetworks . . . . . . . . . . . . . 473 11.4 Data-CentricMACProtocols forSensorNetworks . . . . . . . . . . . . . . . 478 11.4.1 DataAggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 11.4.2 DistributedSourceCoding . . . . . . . . . . . . . . . . . . . . . . . 479 11.4.3 SpatialSamplingof aCorrelatedSensorField . . . . . . . . . . . . . 482 11.5 Cooperative MAC Protocol for Independent Sources . . . . . . . . . . . . . 485 11.6 Cooperative MAC Protocol for Correlated Sensors . . . . . . . . . . . . . . 492 11.6.1 DataRetrieval fromCorrelatedSensors . . . . . . . . . . . . . . . . 492 11.6.2 Generalized Data-Centric Cooperative MAC . . . . . . . . . . . . . 505 11.6.3 MACforDistributedDetectionandEstimation . . . . . . . . . . . . 511 11.7 DiscussionandFutureResearchDirections . . . . . . . . . . . . . . . . . . 515 Bibliography 519 12 Game Theoretic Activation and Transmission Scheduling in UnattendedGround Sensor Networks: A Correlated Equilibrium Approach 525 12.1 Introduction and Background . . . . . . . . . . . . . . . . . . . . . . . . . . 526 12.1.1 UGSN Sensor Activation and Transmission SchedulingMethodology 527 12.1.2 Fundamental Tools and Literature . . . . . . . . . . . . . . . . . . . 528 12.2 Unattended Ground Sensor Network: Capabilities and Objectives . . . . . . . 533 12.2.1 Practicalities: Sensor Network Model and Architecture . . . . . . . . 533 12.2.2 EnergyEfficientSensorActivationandTransmissionControl . . . . 536 12.3 Sensor Activation as the Correlated Equilibrium of a Noncooperative Game . 538 12.3.1 From Nash to Correlated Equilibrium - An Overview . . . . . . . . . 539 12.3.2 Adaptive Sensor Activation through Regret Tracking . . . . . . . . . 543 12.3.3 ConvergenceAnalysis ofRegret-basedAlgorithms . . . . . . . . . . 548 12.4 Energy Efficient Transmission Scheduling in UGSN - A Markov Decision ProcessApproach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551 12.4.1 Outline of Markov Decision Processes and Supermodularity . . . . . 553 12.4.2 Optimal Channel-Aware Transmission Scheduling as a MarkovDecisionProcess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554 12.4.3 Optimality of Threshold Transmission Policies . . . . . . . . . . . . 559 12.5 NumericalResults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 12.5.1 UGSNSensorActivationAlgorithm . . . . . . . . . . . . . . . . . . 565 12.5.2 Energy Throughput Tradeoff via Optimal Transmission Scheduling . 570 12.6 DiscussionandExtensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 12.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 12.7.1 ListofSymbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 12.7.2 ProofofLemma12.4.3 . . . . . . . . . . . . . . . . . . . . . . . . . 577 12.7.3 ProofofTheorem12.4.4 . . . . . . . . . . . . . . . . . . . . . . . . 578 Bibliography 581
Library of Congress Subject Headings for this publication:
Sensor networks.
Wireless LANs.
Signal processing -- Digital techniques.