Title Details

IVAN STOJMENOVIC is currently editor in chief of four journals (including IEEE Transactions on Parallel and Distributed Systems). He has h-index 35 and over 5,000 citations. Stojmenovic was the recipient of the Royal Society Research Merit Award, UK, and the Excellence in Research Award of the University of Ottawa 2008–09. He has chaired and/or organized more than fifty workshops and conferences. He became an IEEE Fellow in 2008.

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 225

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