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
