Protocols and Architectures for Wireless Sensor Networks

Preface xiii List of abbreviations xv A guide to the book xxiii 1 Introduction 1 1.1 The vision of Ambient Intelligence 1 1.2 Application examples 3 1.3 Types of applications 6 1.4 Challenges for WSNs 7 1.4.1 Characteristic requirements 7 1.4.2 Required mechanisms 9 1.5 Why are sensor networks different? 10 1.5.1 Mobile ad hoc networks and wireless sensor networks 10 1.5.2 Fieldbuses and wireless sensor networks 12 1.6 Enabling technologies for wireless sensor networks 13 Part I Architectures 15 2 Single-node architecture 17 2.1 Hardware components 18 2.1.1 Sensor node hardware overview 18 2.1.2 Controller 19 2.1.3 Memory 21 2.1.4 Communication device 21 2.1.5 Sensors and actuators 31 2.1.6 Power supply of sensor nodes 32 2.2 Energy consumption of sensor nodes 36 2.2.1 Operation states with different power consumption 36 2.2.2 Microcontroller energy consumption 38 2.2.3 Memory 39 2.2.4 Radio transceivers 40 2.2.5 Relationship between computation and communication 44 2.2.6 Power consumption of sensor and actuators 44 2.3 Operating systems and execution environments 45 2.3.1 Embedded operating systems 45 2.3.2 Programming paradigms and application programming interfaces 45 2.3.3 Structure of operating system and protocol stack 47 2.3.4 Dynamic energy and power management 48 2.3.5 Case Study: TinyOS and nesC 50 2.3.6 Other examples 53 2.4 Some examples of sensor nodes 54 2.4.1 The “Mica Mote” family 54 2.4.2 EYES nodes 54 2.4.3 BTnodes 54 2.4.4 Scatterweb 54 2.4.5 Commercial solutions 55 2.5 Conclusion 56 3 Network architecture 59 3.1 Sensor network scenarios 60 3.1.1 Types of sources and sinks 60 3.1.2 Single-hop versus multihop networks 60 3.1.3 Multiple sinks and sources 62 3.1.4 Three types of mobility 62 3.2 Optimization goals and figures of merit 63 3.2.1 Quality of service 64 3.2.2 Energy efficiency 65 3.2.3 Scalability 66 3.2.4 Robustness 67 3.3 Design principles for WSNs 67 3.3.1 Distributed organization 67 3.3.2 In-network processing 67 3.3.3 Adaptive fidelity and accuracy 70 3.3.4 Data centricity 70 3.3.5 Exploit location information 73 3.3.6 Exploit activity patterns 73 3.3.7 Exploit heterogeneity 73 3.3.8 Component-based protocol stacks and cross-layer optimization 74 3.4 Service interfaces of WSNs 74 3.4.1 Structuring application/protocol stack interfaces 74 3.4.2 Expressibility requirements for WSN service interfaces 76 3.4.3 Discussion 77 3.5 Gateway concepts 78 3.5.1 The need for gateways 78 3.5.2 WSN to Internet communication 79 3.5.3 Internet to WSN communication 80 3.5.4 WSN tunneling 81 3.6 Conclusion 81 Part II Communication Protocols 83 4 Physical layer 85 4.1 Introduction 85 4.2 Wireless channel and communication fundamentals 86 4.2.1 Frequency allocation 86 4.2.2 Modulation and demodulation 88 4.2.3 Wave propagation effects and noise 90 4.2.4 Channel models 96 4.2.5 Spread-spectrum communications 98 4.2.6 Packet transmission and synchronization 100 4.2.7 Quality of wireless channels and measures for improvement 102 4.3 Physical layer and transceiver design considerations in WSNs 103 4.3.1 Energy usage profile 103 4.3.2 Choice of modulation scheme 104 4.3.3 Dynamic modulation scaling 108 4.3.4 Antenna considerations 108 4.4 Further reading 109 5 MAC protocols 111 5.1 Fundamentals of (wireless) MAC protocols 112 5.1.1 Requirements and design constraints for wireless MAC protocols 112 5.1.2 Important classes of MAC protocols 114 5.1.3 MAC protocols for wireless sensor networks 119 5.2 Low duty cycle protocols and wakeup concepts 120 5.2.1 Sparse topology and energy management (STEM) 121 5.2.2 S-mac 123 5.2.3 The mediation device protocol 126 5.2.4 Wakeup radio concepts 127 5.2.5 Further reading 128 5.3 Contention-based protocols 129 5.3.1 CSMA protocols 129 5.3.2 Pamas 131 5.3.3 Further solutions 132 5.4 Schedule-based protocols 133 5.4.1 Leach 133 5.4.2 Smacs 135 5.4.3 Traffic-adaptive medium access protocol (TRAMA) 137 5.4.4 Further solutions 139 5.5 The IEEE 802.15.4 MAC protocol 139 5.5.1 Network architecture and types/roles of nodes 140 5.5.2 Superframe structure 141 5.5.3 GTS management 141 5.5.4 Data transfer procedures 142 5.5.5 Slotted CSMA-CA protocol 142 5.5.6 Nonbeaconed mode 144 5.5.7 Further reading 145 5.6 How about IEEE 802.11 and bluetooth? 145 5.7 Further reading 146 5.8 Conclusion 148 6 Link-layer protocols 149 6.1 Fundamentals: tasks and requirements 150 6.2 Error control 151 6.2.1 Causes and characteristics of transmission errors 151 6.2.2 ARQ techniques 152 6.2.3 FEC techniques 158 6.2.4 Hybrid schemes 163 6.2.5 Power control 165 6.2.6 Further mechanisms to combat errors 166 6.2.7 Error control: summary 167 6.3 Framing 167 6.3.1 Adaptive schemes 170 6.3.2 Intermediate checksum schemes 172 6.3.3 Combining packet-size optimization and FEC 173 6.3.4 Treatment of frame headers 174 6.3.5 Framing: summary 174 6.4 Link management 174 6.4.1 Link-quality characteristics 175 6.4.2 Link-quality estimation 177 6.5 Summary 179 7 Naming and addressing 181 7.1 Fundamentals 182 7.1.1 Use of addresses and names in (sensor) networks 182 7.1.2 Address management tasks 183 7.1.3 Uniqueness of addresses 184 7.1.4 Address allocation and assignment 184 7.1.5 Addressing overhead 185 7.2 Address and name management in wireless sensor networks 186 7.3 Assignment of MAC addresses 186 7.3.1 Distributed assignment of networkwide addresses 187 7.4 Distributed assignment of locally unique addresses 189 7.4.1 Address assignment algorithm 189 7.4.2 Address selection and representation 191 7.4.3 Further schemes 194 7.5 Content-based and geographic addressing 194 7.5.1 Content-based addressing 194 7.5.2 Geographic addressing 198 7.6 Summary 198 8 Time synchronization 201 8.1 Introduction to the time synchronization problem 201 8.1.1 The need for time synchronization in wireless sensor networks 202 8.1.2 Node clocks and the problem of accuracy 203 8.1.3 Properties and structure of time synchronization algorithms 204 8.1.4 Time synchronization in wireless sensor networks 206 8.2 Protocols based on sender/receiver synchronization 207 8.2.1 Lightweight time synchronization protocol (LTS) 207 8.2.2 How to increase accuracy and estimate drift 212 8.2.3 Timing-sync protocol for sensor networks (TPSN) 214 8.3 Protocols based on receiver/receiver synchronization 217 8.3.1 Reference broadcast synchronization (RBS) 217 8.3.2 Hierarchy referencing time synchronization (HRTS) 223 8.4 Further reading 226 9 Localization and positioning 231 9.1 Properties of localization and positioning procedures 232 9.2 Possible approaches 233 9.2.1 Proximity 233 9.2.2 Trilateration and triangulation 234 9.2.3 Scene analysis 237 9.3 Mathematical basics for the lateration problem 237 9.3.1 Solution with three anchors and correct distance values 238 9.3.2 Solving with distance errors 238 9.4 Single-hop localization 240 9.4.1 Active Badge 240 9.4.2 Active office 240 9.4.3 Radar 240 9.4.4 Cricket 241 9.4.5 Overlapping connectivity 241 9.4.6 Approximate point in triangle 242 9.4.7 Using angle of arrival information 243 9.5 Positioning in multihop environments 243 9.5.1 Connectivity in a multihop network 244 9.5.2 Multihop range estimation 244 9.5.3 Iterative and collaborative multilateration 245 9.5.4 Probabilistic positioning description and propagation 247 9.6 Impact of anchor placement 247 9.7 Further reading 248 9.8 Conclusion 249 10 Topology control 251 10.1 Motivation and basic ideas 251 10.1.1 Options for topology control 252 10.1.2 Aspects of topology-control algorithms 254 10.2 Controlling topology in flat networks – Power control 256 10.2.1 Some complexity results 256 10.2.2 Are there magic numbers? – bounds on critical parameters 257 10.2.3 Some example constructions and protocols 259 10.2.4 Further reading on flat topology control 265 10.3 Hierarchical networks by dominating sets 266 10.3.1 Motivation and definition 266 10.3.2 A hardness result 266 10.3.3 Some ideas from centralized algorithms 267 10.3.4 Some distributed approximations 270 10.3.5 Further reading 273 10.4 Hierarchical networks by clustering 274 10.4.1 Definition of clusters 274 10.4.2 A basic idea to construct independent sets 277 10.4.3 A generalization and some performance insights 278 10.4.4 Connecting clusters 278 10.4.5 Rotating clusterheads 279 10.4.6 Some more algorithm examples 280 10.4.7 Multihop clusters 281 10.4.8 Multiple layers of clustering 283 10.4.9 Passive clustering 284 10.4.10 Further reading 284 10.5 Combining hierarchical topologies and power control 285 10.5.1 Pilot-based power control 285 10.5.2 Ad hoc Network Design Algorithm (ANDA) 285 10.5.3 Clusterpow 286 10.6 Adaptive node activity 286 10.6.1 Geographic Adaptive Fidelity (GAF) 286 10.6.2 Adaptive Self-Configuring sEnsor Networks’ Topologies (ASCENT) 287 10.6.3 Turning off nodes on the basis of sensing coverage 288 10.7 Conclusions 288 11 Routing protocols 289 11.1 The many faces of forwarding and routing 289 11.2 Gossiping and agent-based unicast forwarding 292 11.2.1 Basic idea 292 11.2.2 Randomized forwarding 292 11.2.3 Random walks 293 11.2.4 Further reading 294 11.3 Energy-efficient unicast 295 11.3.1 Overview 295 11.3.2 Some example unicast protocols 297 11.3.3 Further reading 301 11.3.4 Multipath unicast routing 301 11.3.5 Further reading 304 11.4 Broadcast and multicast 305 11.4.1 Overview 305 11.4.2 Source-based tree protocols 308 11.4.3 Shared, core-based tree protocols 314 11.4.4 Mesh-based protocols 314 11.4.5 Further reading on broadcast and multicast 315 11.5 Geographic routing 316 11.5.1 Basics of position-based routing 316 11.5.2 Geocasting 323 11.5.3 Further reading on geographic routing 326 11.6 Mobile nodes 328 11.6.1 Mobile sinks 328 11.6.2 Mobile data collectors 328 11.6.3 Mobile regions 329 11.7 Conclusions 329 12 Data-centric and content-based networking 331 12.1 Introduction 331 12.1.1 The publish/subscribe interaction paradigm 331 12.1.2 Addressing data 332 12.1.3 Implementation options 333 12.1.4 Distribution versus gathering of data – In-network processing 334 12.2 Data-centric routing 335 12.2.1 One-shot interactions 335 12.2.2 Repeated interactions 337 12.2.3 Further reading 340 12.3 Data aggregation 341 12.3.1 Overview 341 12.3.2 A database interface to describe aggregation operations 342 12.3.3 Categories of aggregation operations 343 12.3.4 Placement of aggregation points 345 12.3.5 When to stop waiting for more data 345 12.3.6 Aggregation as an optimization problem 347 12.3.7 Broadcasting an aggregated value 347 12.3.8 Information-directed routing and aggregation 350 12.3.9 Some further examples 352 12.3.10 Further reading on data aggregation 355 12.4 Data-centric storage 355 12.5 Conclusions 357 13 Transport layer and quality of service 359 13.1 The transport layer and QoS in wireless sensor networks 359 13.1.1 Quality of service/reliability 360 13.1.2 Transport protocols 361 13.2 Coverage and deployment 362 13.2.1 Sensing models 362 13.2.2 Coverage measures 364 13.2.3 Uniform random deployments: Poisson point processes 365 13.2.4 Coverage of random deployments: Boolean sensing model 366 13.2.5 Coverage of random deployments: general sensing model 368 13.2.6 Coverage determination 369 13.2.7 Coverage of grid deployments 374 13.2.8 Further reading 375 13.3 Reliable data transport 376 13.3.1 Reliability requirements in sensor networks 377 13.4 Single packet delivery 378 13.4.1 Using a single path 379 13.4.2 Using multiple paths 384 13.4.3 Multiple receivers 388 13.4.4 Summary 389 13.5 Block delivery 389 13.5.1 PSFQ: block delivery in the sink-to-sensors case 389 13.5.2 RMST: block delivery in the sensors-to-sink case 395 13.5.3 What about TCP? 397 13.5.4 Further reading 399 13.6 Congestion control and rate control 400 13.6.1 Congestion situations in sensor networks 400 13.6.2 Mechanisms for congestion detection and handling 402 13.6.3 Protocols with rate control 403 13.6.4 The CODA congestion-control framework 408 13.6.5 Further reading 411 14 Advanced application support 413 14.1 Advanced in-network processing 413 14.1.1 Going beyond mere aggregation of data 413 14.1.2 Distributed signal processing 414 14.1.3 Distributed source coding 416 14.1.4 Network coding 420 14.1.5 Further issues 421 14.2 Security 422 14.2.1 Fundamentals 422 14.2.2 Security considerations in wireless sensor networks 423 14.2.3 Denial-of-service attacks 423 14.2.4 Further reading 425 14.3 Application-specific support 425 14.3.1 Target detection and tracking 426 14.3.2 Contour/edge detection 429 14.3.3 Field sampling 432 Bibliography 437 Index 481