Preface ........................................................ ix
Contributors ................................................... xv
1 Applications, Models, Problems, and Solution Strategies ...... 1
Hai Liu, Amiya Nayak, and Ivan Stojmenovic
1.1 Wireless Sensors ........................................ 1
1.2 Single-Hop Wireless Sensor Networks ..................... 2
1.3 Multihop Wireless Sensor Networks ....................... 3
1.4 Event-Driven, Periodic, and On-Demand Reporting ......... 4
1.5 Unit Disk Graph Modeling, Hop Count Metric, and
Probabilistic Reception ................................. 7
1.6 Adjustable Transmission Range and Power Metric .......... 9
1.7 Cost Metrics ........................................... 10
1.8 Sleep and Active State Modeling ........................ 11
1.9 Architectures for Wireless Sensor and Actuator
Networks ............................................... 12
1.10 Simple Models and Application of Wireless Sensor and
Actuator Networks ...................................... 15
1.11 Generating Connected Wireless Sensor and Actuator
Networks ............................................... 17
1.12 Generating Mobile Wireless Sensor and Actuator
Networks ............................................... 19
1.13 Problems at Physical, MAC, and Transport Layers ........ 19
1.14 Problems at the Network Layer .......................... 22
1.15 Localized Protocols as the Solution Framework .......... 25
1.16 Implementation of Sensor Motes ......................... 27
1.17 Experiments On Test Beds ............................... 28
1.18 Experiences with the Development of Sensor Network
Systems ................................................ 29
References .................................................. 30
2 Energy-Efficient Backbones and Broadcasting in Sensor and
Actuator Networks ........................................... 33
Hai Liu, Amiya Nayak, and Ivan Stojmenovic
2.1 Backbones .............................................. 33
2.2 Grid Partitioning-Based Backbones ...................... 35
2.3 Clustering-Based Backbones ............................. 36
2.4 Connected Dominating Sets as Backbones ................. 38
2.5 Overview of Broadcasting Techniques .................... 48
2.6 Physical Layer-Based Flooding, Neighbor Detection and
Route Discovery ........................................ 58
2.7 Parameterless Broadcasting for Delay Tolerant-
Networks ............................................... 59
2.8 Backbones and Broadcasting in Sensor-Actuator
Networks ............................................... 61
2.9 RNG and LMST ........................................... 64
2.10 Minimal Energy Broadcasting ............................ 66
References .................................................. 70
3 Sensor Area Coverage ........................................ 75
Hai Liu, Amiya Nayak, and Ivan Stojmenovic
3.1 Problems, Models, and Assumptions ...................... 75
3.2 Coverage and Connectivity Criteria ..................... 78
3.3 Area-Dominating Set Based Sensor Area Coverage
Algorithm .............................................. 81
3.4 Asynchronous Sensor Area Coverage ...................... 83
3.5 Synchronous Sensor Area Coverage ....................... 85
3.6 Multicoverage By Sensors ............................... 88
3.7 Physical Layer-Based Sensing, Protocols, and Case
Studies ................................................ 89
3.8 Operation Range Assignment in WSANs .................... 90
References .................................................. 91
4 Geographic Routing in Wireless Sensor and Actuator
Networks .................................................... 95
Hai Liu, Amiya Nayak, and Ivan Stojmenovic
4.1 Flooding-Based Routing and Georouting in Sensor
Networks ............................................... 96
4.2 Greedy, Projection, and Direction-Based Routing ........ 97
4.3 Applications of Cost to Progress Ratio Framework to
Georouting ............................................ 100
4.4 Memorization-Based Georouting with Guaranteed
Delivery .............................................. 103
4.5 Guaranteed Delivery without Memorization .............. 105
4.6 Beaconless Georouting ................................. 114
4.7 Georouting with Virtual and Tree Coordinates .......... 117
4.8 Georouting in Sensor and Actuator Networks ............ 118
4.9 Link Quality Metric in Sensor and Actuator Networks ... 119
4.10 Physical Layer Aspects and Case Studies of
Georouting ............................................ 120
References ................................................. 122
5 Multicasting, Geocasting, and Anycasting in Sensor and
Actuator Networks .......................................... 127
Arnaud Casteigts, Amiya Nayak, and Ivan Stojmenovic
5.1 Multicasting .......................................... 127
5.2 Geocasting with Guaranteed Delivery ................... 134
5.3 Rate-Based Multicasting ............................... 143
5.4 Anycasting with Guaranteed Delivery ................... 147
References ................................................. 150
6 Sink Mobility in Wireless Sensor Networks .................. 153
Xu Li, Amiya Nayak, and Ivan Stojmenovic
6.1 Introduction .......................................... 153
6.2 Energy Hole Problem ................................... 155
6.3 Energy Efficiency by Sink Mobility .................... 160
6.4 Sink Mobility in Delay-Tolerant Networks .............. 162
6.5 Sink Mobility in Real-Time Networks ................... 172
References ................................................. 181
7 Topology Control in Sensor, Actuator, and Mobile Robot
Networks ................................................... 185
Arnaud Casteigts, Amiya Nayak, and Ivan Stojmenovic
7.1 Introduction .......................................... 185
7.2 General Approaches In Static Sensor Networks .......... 186
7.3 The Minimum Spanning Tree ............................. 187
7.4 Data Aggregation ...................................... 189
7.5 Spanning Trees in Uncontrolled Dynamic Topologies ..... 193
7.6 Detection of Critical Nodes and Links ................. 195
7.7 Biconnected Robot Team Movement for Sensor
Deployment ............................................ 197
7.8 Augmentation Algorithm for Robot Self Deployment ...... 198
7.9 Biconnectivity From Connectivity without Additional
Constraints ........................................... 200
7.10 Biconnectivity from Connectivity with Additional
Constraints ........................................... 203
References ................................................. 206
8 Location Service in Sensor and Mobile Actuator Networks .... 209
Xu Li, Amiya Nayak, and Ivan Stojmenovic
8.1 Introduction .......................................... 209
8.2 Classification of Location Services ................... 210
8.3 Location Update Policies .............................. 212
8.4 Flooding-Based Algorithms ............................. 212
8.5 Quorum-Based Algorithms ............................... 219
8.6 Home-Based Approaches References ...................... 229
9 Coordination in Sensor, Actuator, and Robot Networks ....... 233
Hai Liu, Veljko Malbasa, Ivan Mezei, Amiya Nayak, and
Ivan Stojmenovic
9.1 Sensor-Actuator Coordination .......................... 233
9.2 Task Assignment in Multirobot Systems ................. 236
9.3 Selecting Best Robot(s) when Communication Cost is
Negligible ............................................ 238
9.4 Selecting Best Robot(s) with Nonnegligible
Communication Costs ................................... 240
9.5 Dynamic Task Assignment ............................... 244
9.6 Deploying Sensors to Improve Connectivity ............. 245
9.7 Fault-Tolerant Semipassive Coordination Among
Actuators ............................................. 247
9.8 Dispersion of Autonomous Mobile Robots ................ 248
9.9 Distributed Boundary Coverage by Robots ............... 249
9.10 Clustering Robot Swarms ............................... 250
9.11 Robot Teams for Exploration and Mapping ............... 251
9.12 Coordinated Actuator Movement for Energy-Efficient
Sensor Reporting ...................................... 252
9.13 Flying Robots ......................................... 258
References ................................................. 259
10 Sensor Placement in Sensor and Actuator Networks ........... 263
Xu Li, Amiya Nayak, David Simplot-Ryl, and Ivan
Stojmenovic
10.1 Introduction .......................................... 263
10.2 Movement-Assisted Sensor Placement .................... 264
10.3 Mobile Sensor Migration ............................... 265
10.4 Sensor Placement by Actuators ......................... 266
10.5 Coverage Maintenance by Actuators ..................... 271
10.6 Sensor Self-Deployment ................................ 272
10.7 Sensor Relocation ..................................... 287
References ................................................. 292
Index ......................................................... 295
|
