Wireless Sensor Networks The Morgan Kaufmann Series in Networking Series Editor, David Clark, M.I.T. Forfurtherinformationonthesebooksandforalistofforthcomingtitles,pleasevisitourwebsiteat http:www.mkp.com WirelessSensorNetworks:AnInformationProcessing TelecommunicationsLawintheInternetAge Approach SharonK.Black FengZhaoandLeonidasGuibas OpticalNetworks:APracticalPerspective,2e NetworkRecovery:ProtectionandRestorationofOptical, RajivRamaswamiandKumarN.Sivarajan SONET-SDH,IP,andMPLS InternetQoS:ArchitectureandMechanisms JeanPhilippeVasseur,MarioPickavet,andPiet ZhengWang Demeester TCP/IPSocketsinJava:PracticalGuideforProgrammers Routing,Flow,andCapacityDesigninCommunication MichaelJ.DonahooandKennethL.Calvert andComputerNetworks MichalPióroandDeepankarMedhi TCP/IPSocketsinC:PracticalGuideforProgrammers KennethL.CalvertandMichaelJ.Donahoo CommunicationNetworking:AnAnalyticalApproach AnuragKumar,D.Manjunath,andJoyKuri MulticastCommunication:Protocols,Programmingand Applications TheInternetandItsProtocols:AComparativeApproach RalphWitmannandMartinaZitterbart AdrianFarrel MPLS:TechnologyandApplications ModernCableTelevisionTechnology:Video,Voice,and BruceDavieandYakovRekhter DataCommunications,2e WalterCiciora,JamesFarmer,DavidLarge,and High-PerformanceCommunicationNetwork,2e MichaelAdams JeanWalrandandPravinVaraiya BluetoothApplicationProgrammingwiththeJavaAPIs InternetworkingMultimedia CBalaKumar,PaulJ.Kline,andTimothyJ. JonCrowcroft,MarkHandley,andIanWakemann Thompson UnderstandingNetworkedApplications:AFirstCourse Policy-BasedNetworkManagement:SolutionsfortheNext DavidG.Messerschmitt Generation IntegratedManagementofNetworkedSystems:Concepts, JohnStrassner Architectures,andtheirOperationalApplication ComputerNetworks:ASystemsApproach,3e Heinz-GerdHegering,SebastianAbeck,andBernhard LarryL.PetersonandBruceS.Davie Neumair NetworkArchitecture,Analysis,andDesign,2e VirtualPrivateNetworks:MarkingtheRightConnection JamesD.McCabe DennisFowler MPLSNetworkManagement:MIBs,Tools,and NetworkedApplications:AGuidetotheNewComputing Techniques Infrastructure ThomasD.Nadeau DavidG.Messerschmitt DevelopingIP-BasedServices:SolutionsforServiceProviders WideAreaNetworkDesign:ConceptsandToolsfor andVendors Optimiztion MoniqueMorrowandKateelVajayananda RobertsS.Cahn Wireless Sensor Networks: An Information Processing Approach Feng Zhao Microsoft Corporation Leonidas J. Guibas Stanford University AMSTERDAM•BOSTON•HEIDELBERG•LONDON NEWYORK•OXFORD•PARIS•SANDIEGO SANFRANCISCO•SINGAPORE•SYDNEY•TOKYO MorganKaufmannPublishersisanimprintofElsevier Copyright page Contents Preface xiii 1 Introduction 1 1.1 Unique Constraints and Challenges 2 1.2 Advantages of Sensor Networks 6 1.2.1 Energy Advantage 7 1.2.2 Detection Advantage 8 1.3 Sensor Network Applications 9 1.3.1 Habitat Monitoring 10 1.3.2 Tracking Chemical Plumes 12 1.3.3 Smart Transportation 13 1.4 Collaborative Processing 16 1.5 Key Definitions of Sensor Networks 17 1.6 The Rest of the Book 20 v vi Contents 2 Canonical Problem: Localization and Tracking 23 2.1 A Tracking Scenario 25 2.2 Problem Formulation 27 2.2.1 Sensing Model 28 2.2.2 Collaborative Localization 30 2.2.3 Bayesian State Estimation 32 2.3 Distributed Representation and Inference of States 38 2.3.1 Impact of Choice of Representation 38 2.3.2 Design Desiderata in Distributed Tracking 42 2.4 Tracking Multiple Objects 45 2.4.1 State-Space Decomposition 45 2.4.2 Data Association 48 2.5 Sensor Models 51 2.6 Performance Comparison and Metrics 58 2.7 Summary 61 3 Networking Sensors 63 3.1 Key Assumptions 63 3.2 Medium Access Control 65 3.2.1 The S-MAC Protocol 66 3.2.2 IEEE 802.15.4 Standard and ZigBee 67 3.3 General Issues 68 Contents vii 3.4 Geographic, Energy-Aware Routing 70 3.4.1 Unicast Geographic Routing 72 3.4.2 Routing on a Curve 81 3.4.3 Energy-Minimizing Broadcast 83 3.4.4 Energy-Aware Routing to a Region 87 3.5 Attribute-Based Routing 91 3.5.1 Directed Diffusion 92 3.5.2 Rumor Routing 97 3.5.3 Geographic Hash Tables 99 3.6 Summary 101 4 Infrastructure Establishment 103 4.1 Topology Control 103 4.2 Clustering 106 4.3 Time Synchronization 107 4.3.1 Clocks and Communication Delays 109 4.3.2 Interval Methods 111 4.3.3 Reference Broadcasts 115 4.4 Localization and Localization Services 117 4.4.1 Ranging Techniques 119 4.4.2 Range-Based Localization Algorithms 120 4.4.3 Other Localization Algorithms 125 4.4.4 Location Services 127 4.5 Summary 132 viii Contents 5 Sensor Tasking and Control 135 5.1 Task-Driven Sensing 136 5.2 Roles of Sensor Nodes and Utilities 138 5.3 Information-Based Sensor Tasking 142 5.3.1 Sensor Selection 142 5.3.2 IDSQ: Information-Driven Sensor Querying 147 5.3.3 Cluster Leader–Based Protocol 152 5.3.4 Sensor Tasking in Tracking Relations 162 5.4 Joint Routing and Information Aggregation 167 5.4.1 Moving Center of Aggregation 168 5.4.2 Multistep Information-Directed Routing 174 5.4.3 Sensor Group Management 179 5.4.4 Case Study: Sensing Global Phenomena 185 5.5 Summary 187 6 Sensor Network Databases 189 6.1 Sensor Database Challenges 192 6.2 Querying the Physical Environment 195 6.3 Query Interfaces 197 6.3.1 Cougar Sensor Database and Abstract Data Types 198 6.3.2 Probabilistic Queries 199 6.4 High-Level Database Organization 200 6.5 In-Network Aggregation 203 6.5.1 Query Propagation and Aggregation 203 Contents ix 6.5.2 TinyDB Query Processing 205 6.5.3 Query Processing Scheduling and Optimization 207 6.6 Data-Centric Storage 211 6.7 Data Indices and Range Queries 213 6.7.1 One-Dimensional Indices 215 6.7.2 Multidimensional Indices for Orthogonal Range Searching 217 6.7.3 Nonorthogonal Range Searching 221 6.8 Distributed Hierarchical Aggregation 223 6.8.1 Multiresolution Summarization 224 6.8.2 Partitioning the Summaries 225 6.8.3 Fractional Cascading 227 6.8.4 Locality-Preserving Hashing 230 6.9 Temporal Data 232 6.9.1 Data Aging 233 6.9.2 Indexing Motion Data 234 6.10 Summary 236 7 Sensor Network Platforms and Tools 239 7.1 Sensor Node Hardware 240 7.1.1 Berkeley Motes 242 7.2 Sensor Network Programming Challenges 245 7.3 Node-Level Software Platforms 247 7.3.1 Operating System: TinyOS 248