Table of contents for Protocols and architectures for wireless sensor networks / Holger Karl, Andreas Willig.

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.


Counter
Contents
Preface xix
Audience and Prerequisites . . . . . . . . . . . . . . xix
Division of Work . . . . . . . . . . . . . . . . . . . xix
Acknowledgements . . . . . . . . . . . . . . . . . . xix
A guide to the book xxi
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 . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 Characteristic requirements . . . . . . . . . . . . . . . . . 8
1.4.2 Required mechanisms . . . . . . . . . . . . . . . . . . . . 9
1.5 Why are sensor networks different? . . . . . . . . . . . . . . . . . 11
1.5.1 Mobile ad hoc networks and wireless sensor networks . . . 11
1.5.2 Fieldbusses and wireless sensor networks . . . . . . . . . . 14
1.6 Enabling technologies . . . . . . . . . . . . . . . . . . . . . . . . . 15
I Architectures 17
2 Single node architecture 19
2.1 Hardware components . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.1 Sensor node hardware overview . . . . . . . . . . . . . . . 20
2.1.2 Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Microcontrollers vs. microprocessors and ASICs . . . . . . 22
Some examples for microcontrollers . . . . . . . . . . . . . 23
Intel StrongARM . . . . . . . . . . . . . . . . . . . 23
Texas Instruments MSP 430 . . . . . . . . . . . . . 23
Atmel ATmega . . . . . . . . . . . . . . . . . . . . 24
2.1.3 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.4 Communication device . . . . . . . . . . . . . . . . . . . . 24
Choice of transmission medium . . . . . . . . . . . . . . . 24
Basics of radio frequency communication . . . . . . . . . . 24
Transceivers . . . . . . . . . . . . . . . . . . . . . . . . . 28
Advanced radio concepts . . . . . . . . . . . . . . . . . . . 30
Wakeup radio . . . . . . . . . . . . . . . . . . . . . 30
Spread spectrum transceivers . . . . . . . . . . . . . 31
Ultra wideband communication . . . . . . . . . . . 31
Antennas . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Non-radio frequency wireless communication . . . . . . . . 32
Optical . . . . . . . . . . . . . . . . . . . . . . . . 32
Ultrasound . . . . . . . . . . . . . . . . . . . . . . 33
Some example radio transceivers . . . . . . . . . . . . . . . 34
RFM TR1000 family . . . . . . . . . . . . . . . . . 34
Chipcon CC1000 & CC2420 family . . . . . . . . . 34
Infineon TDA 525x family . . . . . . . . . . . . . . 34
2.1.5 Sensors and actuators . . . . . . . . . . . . . . . . . . . . . 35
Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Actuators . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.1.6 Power supply of sensor nodes . . . . . . . . . . . . . . . . 36
Storing energy: Batteries . . . . . . . . . . . . . . . . . . . 36
Traditional batteries . . . . . . . . . . . . . . . . . 36
Unconventional energy stores . . . . . . . . . . . . 38
DC-DC conversion . . . . . . . . . . . . . . . . . . 38
Energy scavenging . . . . . . . . . . . . . . . . . . . . . . 39
2.1.7 On-board and off-board communication . . . . . . . . . . . 40
2.2 Energy consumption of sensor nodes . . . . . . . . . . . . . . . . . 41
2.2.1 Operation states with different power consumption . . . . . 41
2.2.2 Microcontroller energy consumption . . . . . . . . . . . . . 43
Basic power consumption in discrete operation states . . . . 43
Intel StrongARM . . . . . . . . . . . . . . . . . . . 43
Texas Instruments MSP 430 . . . . . . . . . . . . . 44
Atmel ATmega . . . . . . . . . . . . . . . . . . . . 44
Dynamic voltage scaling . . . . . . . . . . . . . . . . . . . 44
2.2.3 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2.4 Radio transceivers . . . . . . . . . . . . . . . . . . . . . . 46
Modeling energy consumption during transmission . . . . . 46
Modeling energy consumption during reception . . . . . . . 47
Some numbers . . . . . . . . . . . . . . . . . . . . . . . . 48
Dynamic scaling of radio power consumption . . . . . . . . 49
2.2.5 Relationship between computation and communication . . . 50
2.2.6 Power consumption of sensor and actuators . . . . . . . . . 51
2.3 Operating Systems and Execution Environments . . . . . . . . . . . 51
2.3.1 Embedded operating systems . . . . . . . . . . . . . . . . . 51
2.3.2 Programming paradigms and Application Programming Interfaces
Sequential programming . . . . . . . . . . . . . . . . . . . 52
Process-based concurrency . . . . . . . . . . . . . . . . . . 52
Event-based programming . . . . . . . . . . . . . . . . . . 53
Interfaces to the operating system . . . . . . . . . . . . . . 54
2.3.3 Structure of operating system and protocol stack . . . . . . 55
2.3.4 Dynamic energy & power management . . . . . . . . . . . 56
Probabilistic state transition policies . . . . . . . . . . . . . 56
Controlling dynamic voltage scaling . . . . . . . . . . . . . 57
Trading off fidelity against energy consumption . . . . . . . 57
2.3.5 Case study: TinyOS & nesC . . . . . . . . . . . . . . . . . 58
2.4 Some examples of sensor nodes . . . . . . . . . . . . . . . . . . . 62
2.4.1 The "Mica mote" family . . . . . . . . . . . . . . . . . . . 62
2.4.2 EYES nodes . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3 Network architecture 67
3.1 Sensor network scenarios . . . . . . . . . . . . . . . . . . . . . . . 68
3.1.1 Types of sources and sinks . . . . . . . . . . . . . . . . . . 68
3.1.2 Single-hop vs. multi-hop networks . . . . . . . . . . . . . . 69
3.1.3 Multiple sinks and sources . . . . . . . . . . . . . . . . . . 71
3.1.4 Three types of mobility . . . . . . . . . . . . . . . . . . . . 71
3.2 Optimization goals & figures of merit . . . . . . . . . . . . . . . . 73
3.2.1 Quality of service . . . . . . . . . . . . . . . . . . . . . . . 73
3.2.2 Energy efficiency . . . . . . . . . . . . . . . . . . . . . . . 74
3.2.3 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.2.4 Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.3 Design principles for WSNs . . . . . . . . . . . . . . . . . . . . . 77
3.3.1 Distributed organization . . . . . . . . . . . . . . . . . . . 77
3.3.2 In-network processing . . . . . . . . . . . . . . . . . . . . 78
Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Distributed source coding & distributed compression . . . . 79
Distributed & collaborative signal processing . . . . . . . . 80
Mobile code/Agent-based networking . . . . . . . . . . . . 80
3.3.3 Adaptive fidelity & accuracy . . . . . . . . . . . . . . . . . 81
3.3.4 Data centricity . . . . . . . . . . . . . . . . . . . . . . . . 81
Address data, not nodes . . . . . . . . . . . . . . . . . . . 81
Implementation options for data-centric networking . . . . . 82
Overlay networks & distributed hash tables . . . . . 83
Publish/subscribe . . . . . . . . . . . . . . . . . . . 83
Databases . . . . . . . . . . . . . . . . . . . . . . . 84
3.3.5 Exploit location information . . . . . . . . . . . . . . . . . 85
3.3.6 Exploit activity patterns . . . . . . . . . . . . . . . . . . . 85
3.3.7 Exploit heterogeneity . . . . . . . . . . . . . . . . . . . . . 85
3.3.8 Component-based protocol stacks and cross-layer optimization
3.4 Service interfaces of WSNs . . . . . . . . . . . . . . . . . . . . . . 87
3.4.1 Structuring applicaton/protocol stack interfaces . . . . . . . 87
3.4.2 Expressability requirements for WSN service interfaces . . 89
3.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.5 Gateway concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.5.1 The need for gateways . . . . . . . . . . . . . . . . . . . . 92
3.5.2 WSN to Internet communication . . . . . . . . . . . . . . . 93
3.5.3 Internet to WSN communication . . . . . . . . . . . . . . . 94
3.5.4 WSN tunneling . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4 Fundamental limits 97
II Communication protocols 99
5 Physical layer 103
6 MAC Protocols 105
6.1 Fundamentals of (Wireless) MAC protocols . . . . . . . . . . . . . 106
6.1.1 Requirements and Design Constraints for Wireless MAC
Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.1.2 Important Classes of MAC Protocols . . . . . . . . . . . . 109
Fixed Assignment Protocols . . . . . . . . . . . . . 109
Demand Assignment Protocols . . . . . . . . . . . . 109
Random Access Protocols . . . . . . . . . . . . . . 110
6.1.3 The Specifics of Wireless Sensor Networks . . . . . . . . . 113
6.1.4 Classification of MAC Protocols . . . . . . . . . . . . . . . 115
6.2 Low Duty Cycle Protocols / Wakeup Concepts . . . . . . . . . . . . 116
6.2.1 STEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.2.2 S-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.2.3 The Mediation Device Protocol . . . . . . . . . . . . . . . 122
6.2.4 Wakeup Radio Concepts . . . . . . . . . . . . . . . . . . . 124
6.2.5 Further Solutions . . . . . . . . . . . . . . . . . . . . . . . 125
6.3 Contention-Based Protocols . . . . . . . . . . . . . . . . . . . . . 126
6.3.1 CSMA Protocols . . . . . . . . . . . . . . . . . . . . . . . 126
6.3.2 PAMAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.3.3 Further Solutions . . . . . . . . . . . . . . . . . . . . . . . 130
6.4 Schedule-Based Protocols . . . . . . . . . . . . . . . . . . . . . . 130
6.4.1 LEACH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.4.2 SMACS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.4.3 TRAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4.4 Further Solutions . . . . . . . . . . . . . . . . . . . . . . . 138
6.5 How about IEEE 802.11 and Bluetooth? . . . . . . . . . . . . . . . 138
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7 Link Layer Protocols 141
7.1 Fundamentals: Tasks and Requirements . . . . . . . . . . . . . . . 142
7.2 Error Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.2.1 Causes and Characteristics of Transmission Errors . . . . . 144
7.2.2 ARQ Techniques . . . . . . . . . . . . . . . . . . . . . . . 145
Key Ingredients of ARQ Protocols . . . . . . . . . . . . . . 145
Standard ARQ Protocols . . . . . . . . . . . . . . . . . . . 147
How to use Acknowledgements? . . . . . . . . . . . . . . . 149
When to Retransmit? . . . . . . . . . . . . . . . . . . . . . 150
7.2.3 FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
Block Coding FEC . . . . . . . . . . . . . . . . . . . . . . 152
Convolutional Codes . . . . . . . . . . . . . . . . . . . . . 153
Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Multi-Hop FEC . . . . . . . . . . . . . . . . . . . . . . . . 156
7.2.4 Hybrid Schemes . . . . . . . . . . . . . . . . . . . . . . . 157
7.2.5 Power Control . . . . . . . . . . . . . . . . . . . . . . . . 159
7.2.6 Further Mechanisms to Combat Errors . . . . . . . . . . . . 160
7.2.7 Error Control: Summary . . . . . . . . . . . . . . . . . . . 161
7.3 Framing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.3.1 Adaptive Schemes . . . . . . . . . . . . . . . . . . . . . . 164
7.3.2 Intermediate Checksum Schemes . . . . . . . . . . . . . . 166
7.3.3 Combining Packet Size Optimization and FEC . . . . . . . 167
7.3.4 Treatment of Frame Headers . . . . . . . . . . . . . . . . . 169
7.3.5 Framing: Summary . . . . . . . . . . . . . . . . . . . . . . 169
7.4 Link Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
7.4.1 Link Discovery . . . . . . . . . . . . . . . . . . . . . . . . 170
7.4.2 Link Quality Characteristics . . . . . . . . . . . . . . . . . 170
7.4.3 Link Quality Estimation . . . . . . . . . . . . . . . . . . . 171
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8 Naming and Addressing 175
8.1 Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.1.1 Use of Addresses and Names in (Sensor) Networks . . . . . 177
8.1.2 Addressing Management Tasks . . . . . . . . . . . . . . . 178
8.1.3 Requirements for Addresses . . . . . . . . . . . . . . . . . 179
8.1.4 Addressing Overhead . . . . . . . . . . . . . . . . . . . . . 181
8.2 Address and Name Management in Wireless Sensor Networks . . . 182
8.3 Assignment of MAC Addresses . . . . . . . . . . . . . . . . . . . 182
8.3.1 Distributed Assignment of Networkwide Addresses . . . . . 183
8.4 Distributed Assignment of Locally Unique Addresses . . . . . . . . 185
8.4.1 Address Assignment Algorithm . . . . . . . . . . . . . . . 186
8.4.2 Address Selection and Representation . . . . . . . . . . . . 188
8.4.3 Further Schemes . . . . . . . . . . . . . . . . . . . . . . . 191
8.5 Content-Based and Geographic Addressing . . . . . . . . . . . . . 191
8.5.1 Content-Based Addressing . . . . . . . . . . . . . . . . . . 192
8.5.2 Geographic Addressing . . . . . . . . . . . . . . . . . . . . 196
8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
9 Time Synchronization 199
9.1 Introduction to the Time Synchronization Problem . . . . . . . . . 200
9.1.1 The need for Time Synchronization inWireless Sensor Networks
9.1.2 Node Clocks and the Problem of Accuracy . . . . . . . . . 201
9.1.3 Properties and Structure of Time Synchronization Algorithms203
9.1.4 Time Synchronization in Wireless Sensor Networks . . . . . 205
9.2 Protocols based on Sender-Receiver Synchronization . . . . . . . . 207
9.2.1 Lightweight Time Synchronization Protocol (LTS) . . . . . 207
Pair-wise Synchronization . . . . . . . . . . . . . . . . . . 209
Networkwide Synchronization . . . . . . . . . . . . . . . . 210
Centralized Multihop LTS . . . . . . . . . . . . . . 210
Distributed Multihop LTS . . . . . . . . . . . . . . 211
9.2.2 How to increase accuracy and estimate drift? . . . . . . . . 213
Increasing Accuracy . . . . . . . . . . . . . . . . . . . . . 213
Drift Estimation . . . . . . . . . . . . . . . . . . . . . . . 213
9.2.3 Timing-Sync Protocol for Sensor Networks (TPSN) . . . . 215
Pair-wise Synchronization . . . . . . . . . . . . . . . . . . 215
Networkwide Synchronization . . . . . . . . . . . . . . . . 218
9.3 Protocols based on Receiver-Receiver Synchronization . . . . . . . 219
9.3.1 Reference-Broadcast Synchronization (RBS) . . . . . . . . 219
Synchronization in a Broadcast Domain . . . . . . . . . . . 219
An example . . . . . . . . . . . . . . . . . . . . . . 220
Achievable Precision for a Single Pulse . . . . . . . 220
Comparison of RBS and TPSN . . . . . . . . . . . 222
Using Multiple Pulses . . . . . . . . . . . . . . . . 222
Multiple Nodes and RBS Costs . . . . . . . . . . . 222
RBS and Post-Facto Synchronization . . . . . . . . 223
Network Synchronization over Multiple Hops . . . . . . . . 224
Timestamp Conversion Approach . . . . . . . . . . 224
How to Create the Broadcast Domains? . . . . . . . 225
9.3.2 HRTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Synchronization in a Broadcast Domain . . . . . . . . . . . 227
Network Synchronization over Multiple Hops . . . . . . . . 229
9.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
10 Localization and Positioning 235
10.1 Properties of positioning . . . . . . . . . . . . . . . . . . . . . . . 236
10.2 Possible approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 237
10.2.1 Proximity . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
10.2.2 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . 238
Lateration versus angulation . . . . . . . . . . . . . . . . . 238
Determining distances . . . . . . . . . . . . . . . . . . . . 239
Received Signal Strength Indicator . . . . . . . . . . 239
Time of Arrival . . . . . . . . . . . . . . . . . . . . 240
Time Difference of Arrival . . . . . . . . . . . . . . 241
Discussion . . . . . . . . . . . . . . . . . . . . . . 241
Determining angles . . . . . . . . . . . . . . . . . . . . . . 242
10.2.3 Scene analysis . . . . . . . . . . . . . . . . . . . . . . . . 242
10.3 Mathematical basics for the lateration problem . . . . . . . . . . . . 243
10.3.1 Solution with three anchors and correct distance values . . . 243
10.3.2 Solving with distance errors . . . . . . . . . . . . . . . . . 244
10.4 Single-hop localization . . . . . . . . . . . . . . . . . . . . . . . . 245
10.4.1 Active Badge . . . . . . . . . . . . . . . . . . . . . . . . . 246
10.4.2 Active office . . . . . . . . . . . . . . . . . . . . . . . . . 246
10.4.3 RADAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
10.4.4 Cricket . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
10.4.5 Overlapping connectivity . . . . . . . . . . . . . . . . . . . 247
10.4.6 Approximate point in triangle . . . . . . . . . . . . . . . . 248
10.4.7 Using angle of arrival information . . . . . . . . . . . . . . 249
10.5 Positioning in multi-hop environments . . . . . . . . . . . . . . . . 249
10.5.1 Connectivity in a multi-hop network . . . . . . . . . . . . . 250
A semidefinite program feasibility formulation . . . . . . . 250
Multi-dimensional scaling . . . . . . . . . . . . . . . . . . 251
10.5.2 Multi-hop range estimation . . . . . . . . . . . . . . . . . . 251
10.5.3 Iterative & collaborative multilateration . . . . . . . . . . . 252
10.5.4 Probabilistic positiong description & propagation . . . . . . 254
10.6 Impact of anchor placement . . . . . . . . . . . . . . . . . . . . . . 255
10.7 Matching locations and positions . . . . . . . . . . . . . . . . . . . 256
10.8 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
10.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
11 Topology control 259
11.1 Motivation and basic ideas . . . . . . . . . . . . . . . . . . . . . . 260
11.1.1 Options for topoloy control . . . . . . . . . . . . . . . . . . 260
11.1.2 Aspects of topology control algorithms . . . . . . . . . . . 262
A caveat to connectivity . . . . . . . . . . . . . . . . . . . 263
11.2 Flat network topologies . . . . . . . . . . . . . . . . . . . . . . . . 265
11.2.1 Some complexity results . . . . . . . . . . . . . . . . . . . 265
11.2.2 Are there magic numbers? - Bounds on critical parameters . 266
Controlling transmission range . . . . . . . . . . . . . . . . 267
Controlling the number of neighbors . . . . . . . . . . . . . 268
11.2.3 Some example constructions and protocols . . . . . . . . . 269
The relative neighborhood graph . . . . . . . . . . . . . . . 269
The Gabriel graph . . . . . . . . . . . . . . . . . . . . . . 270
Delaunay triangulation . . . . . . . . . . . . . . . . . . . . 270
Local Minimum Spanning Tree (LMST)-based construction . 271
Relay regions and enclosures . . . . . . . . . . . . . . . . . 271
Cone-based topology control . . . . . . . . . . . . . . . . . 272
Centralized algorithms for (bi-)connectivity, minimizing maximum
power . . . . . . . . . . . . . . . . . . . . 273
A distributed, common power protocol - COMPOW . . . . 275
The K-NEIGH protocol . . . . . . . . . . . . . . . . . . . 275
11.2.4 Further reading on flat topology control . . . . . . . . . . . 276
11.3 Hierarchical networks by dominating sets . . . . . . . . . . . . . . 277
11.3.1 Motivation & definition . . . . . . . . . . . . . . . . . . . 277
11.3.2 A hardness result . . . . . . . . . . . . . . . . . . . . . . . 278
11.3.3 Some ideas from centralized algorithms . . . . . . . . . . . 278
Growing a tree . . . . . . . . . . . . . . . . . . . . . . . . 278
A na"yve approach . . . . . . . . . . . . . . . . . . . 278
Judiciously choosing grey nodes . . . . . . . . . . . 280
Connecting separate components . . . . . . . . . . . . . . . 281
Finding a non-connected dominating set . . . . . . . 281
Ensuring connectivity - building a Steiner tree . . . 282
11.3.4 Some distributed approximations . . . . . . . . . . . . . . 282
Distributedly growing a tree . . . . . . . . . . . . . . . . . 282
Connecting a dominating set . . . . . . . . . . . . . . . . . 283
Marking nodes with unconnected neighbors . . . . . . . . . 283
A non-optimal connected dominating set construction 283
Two pruning heuristics . . . . . . . . . . . . . . . . 284
A degree and position-based pruning heuristic . . . . 285
Span . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
Role-based hierarchical self organization . . . . . . . . . . 286
11.3.5 Further reading . . . . . . . . . . . . . . . . . . . . . . . . 286
11.4 Hierarchical networks by clustering . . . . . . . . . . . . . . . . . 287
11.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
11.4.2 A basic idea to construct independent sets . . . . . . . . . . 291
11.4.3 A generalization and some performance insights . . . . . . 292
11.4.4 Connecting clusters . . . . . . . . . . . . . . . . . . . . . . 293
11.4.5 Rotating clusterheads . . . . . . . . . . . . . . . . . . . . . 293
Using virtual identifiers for rotation . . . . . . . . . . . . . 294
Low-Energy Adaptive Clustering Hierarchy (LEACH) . . . . 294
11.4.6 Some more algorithm examples . . . . . . . . . . . . . . . 295
A Weighted Clustering Algorithm . . . . . . . . . . . . . . 295
An emergent algorithm for cluster establishment . . . . . . 296
11.4.7 Multi-hop clusters . . . . . . . . . . . . . . . . . . . . . . 297
NP-completeness and a heuristic . . . . . . . . . . . . . . . 297
Fixing the size of clusters by growth budgets . . . . . . . . 297
When to use multi-hop clusters . . . . . . . . . . . . . . . . 298
11.4.8 Multiple layers of clustering . . . . . . . . . . . . . . . . . 298
11.4.9 Passive clustering . . . . . . . . . . . . . . . . . . . . . . . 299
11.4.10 Further reading . . . . . . . . . . . . . . . . . . . . . . . . 300
11.5 Combining hierarchical topologies and power control . . . . . . . . 301
11.5.1 Pilot-based power control . . . . . . . . . . . . . . . . . . 301
11.5.2 Ad hoc Network Design Algorithm (ANDA) . . . . . . . . . 301
11.5.3 CLUSTERPOW . . . . . . . . . . . . . . . . . . . . . . . 302
11.6 Adaptive node activity . . . . . . . . . . . . . . . . . . . . . . . . 302
11.6.1 Geographic Adaptive Fidelity (GAF) . . . . . . . . . . . . . 303
11.6.2 Adaptive Self-Configuring sEnsor Networks Topologies (ASCENT)304
11.6.3 Turning off nodes based on sensing coverage . . . . . . . . 304
11.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
12 Routing protocols 307
12.1 The many faces of forwarding and routing . . . . . . . . . . . . . . 308
12.2 Gossiping and agent-based unicast forwarding . . . . . . . . . . . . 310
12.2.1 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
12.2.2 Randomized forwarding . . . . . . . . . . . . . . . . . . . 311
12.2.3 Random walks . . . . . . . . . . . . . . . . . . . . . . . . 312
Rumor routing . . . . . . . . . . . . . . . . . . . . . . . . 312
Random walks with known destination . . . . . . . . . . . 313
12.2.4 Further reading . . . . . . . . . . . . . . . . . . . . . . . . 314
12.3 Energy-efficient unicast . . . . . . . . . . . . . . . . . . . . . . . . 314
12.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
12.3.2 Some example protocols . . . . . . . . . . . . . . . . . . . 317
Attracting routes by redirecting . . . . . . . . . . . . . . . 317
Distance vector routing on top of topology control . . . . . 318
Maximizing time to first node outage as a flow problem . . . 318
Maximizing time to first node outage by a max min optimization
The max min zPmin approximation . . . . . . . . . 319
The zone routing approximation . . . . . . . . . . . 319
Maximizing number of messages . . . . . . . . . . . . . . 319
Bounding the difference between routing protocols . . . . . 320
12.3.3 Multi-path unicast routing . . . . . . . . . . . . . . . . . . 321
Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Sequential Assignment Routing . . . . . . . . . . . . . . . 321
Constructing energy-efficient secondary paths . . . . . . . . 322
Simultaneous transmissions over multiple paths . . . . . . . 323
Trade-off analysis . . . . . . . . . . . . . . . . . . . . . . . 323
12.3.4 Further reading . . . . . . . . . . . . . . . . . . . . . . . . 324
12.4 Broadcast and multicast . . . . . . . . . . . . . . . . . . . . . . . 326
12.4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
12.4.2 Source-based tree protocols . . . . . . . . . . . . . . . . . 329
12.4.3 A greedy heuristic - Shortest Path Tree (SPT) . . . . . . . . 329
Broadcasting using minimum cost spanning tree - Prim's
algorithm . . . . . . . . . . . . . . . . . . . . . . 330
Some Steiner tree approximations for multicasting . . . . . 330
Broad-/mulitcasting with a finite set of power levels . . . . . 331
Exploiting wireless multicast advantage for broadcast: Broadcast
Incremental Power (BIP) . . . . . . . . . . . 331
Exploiting wireless multicast advantage for multicast: Pruning
broadcast trees by Multicast Incremental Power
(MIP) . . . . . . . . . . . . . . . . . . . . . . . . 334
Embedded wireless multicast advantage - Transforming existing
graphs . . . . . . . . . . . . . . . . . . . . 334
A distributed, position-based approach to the wireless multicast
advantage . . . . . . . . . . . . . . . . . . 335
12.4.4 Shared, core-based tree protocols . . . . . . . . . . . . . . 335
12.4.5 Mesh-based protocols . . . . . . . . . . . . . . . . . . . . 336
12.4.6 Further reading on broadcast & multicast . . . . . . . . . . 337
12.5 Geographic routing . . . . . . . . . . . . . . . . . . . . . . . . . . 337
12.5.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
12.5.2 Some examples for geographic routing . . . . . . . . . . . 338
Cartesian Routing . . . . . . . . . . . . . . . . . . . . . . 338
GeoCast . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
Location Based Multicast (LBM) . . . . . . . . . . . . . . . 339
Location Aided Routing (LAR) . . . . . . . . . . . . . . . . 339
Voronoi-based approaches . . . . . . . . . . . . . . . . . . 339
Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
GeoGRID . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
Unicast Routing with Area Delivery (URAD) . . . . . . . . . 339
Trajectory-based forwarding . . . . . . . . . . . . . . . . . 339
12.5.3 Other stuff, to be sorted . . . . . . . . . . . . . . . . . . . 340
12.5.4 Effects of localization errors . . . . . . . . . . . . . . . . . 340
12.6 Mobile nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
13 Data-centric networking 343
13.1 Data centric routing . . . . . . . . . . . . . . . . . . . . . . . . . . 344
13.2 Data gathering and aggregation . . . . . . . . . . . . . . . . . . . . 344
13.3 Convergecast/data gathering . . . . . . . . . . . . . . . . . . . . . 344
13.4 Data dissemination . . . . . . . . . . . . . . . . . . . . . . . . . . 345
14 Transport layer 347
15 Quality of Service 349
16 Higher-layer support 351
16.1 Exploiting temporal and spatial correlation . . . . . . . . . . . . . . 352
16.2 Advanced In-Network Processing . . . . . . . . . . . . . . . . . . 352
16.2.1 Data fusion . . . . . . . . . . . . . . . . . . . . . . . . . . 352
16.2.2 Distributed Signal Processing . . . . . . . . . . . . . . . . 352
16.2.3 Distributed Source Coding . . . . . . . . . . . . . . . . . . 352
16.2.4 Network coding . . . . . . . . . . . . . . . . . . . . . . . . 352
16.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
16.4 Middleware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
16.5 Database abstraction . . . . . . . . . . . . . . . . . . . . . . . . . 352
16.6 Distributed Data Storage . . . . . . . . . . . . . . . . . . . . . . . 352
16.7 Distributed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 352
16.8 Management & Maintenance . . . . . . . . . . . . . . . . . . . . . 352
16.9 Application-specific support . . . . . . . . . . . . . . . . . . . . . 352
16.9.1 Field sampling . . . . . . . . . . . . . . . . . . . . . . . . 352
16.9.2 Target detection . . . . . . . . . . . . . . . . . . . . . . . . 352
16.9.3 Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
16.9.4 Contour-/edge-detection . . . . . . . . . . . . . . . . . . . 352
16.9.5 Cross-layer lifetime maximization . . . . . . . . . . . . . . 352
17 Conclusions 353
A Acronyms 357
A.1 Willig Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
A.2 Karl Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
B Glossary 363
C Scratch space 365
C.1 Willig Scratch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
C.2 Karl scratch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

Library of Congress Subject Headings for this publication:

Sensor networks.
Wireless LANs.