Algorithms for Sensor and Ad Hoc Networks : Advanced Lectures

by Wagner, Dorothea; Wattenhofer, Roger

• ISBN13: 9783540749905
• ISBN10: 354074990X
• Format: Paperback
• Copyright: 2007-10-23
• Publisher: Springer Verlag

Summary

Wireless ad hoc and sensor networks have gained an incredible research momentum. Computer scientists and engineers of all flavors are embracing the area. Sensor networks have been adopted by researchers from many different fields, ranging from hardware technology to operating systems, from antenna design to databases, from information theory to networking, from graph theory to computational geometry.The purpose of this monograph - outcome of a GI-Dagstuhl Seminar held in Dagstuhl Castle in November 2005 - is to give a first overview of algorithmic results on wireless ad hoc and sensor networks. Its focus is on algorithms and protocols that allow for an analysis of their efficiency and efficacy. Many chapters deal with distributed algorithms, in particular local and localized algorithms.Importance is attached to topics combining both interesting aspects of wireless networks and attractive algorithmic methods. Each chapter provides a survey of some part of the field, whilst selected results are described in more detail. The structure and content of the book would make it a suitable basis for an advanced course.

Table of Contents

Preface	p. V
Applications of Sensor Networks	p. 1
Introduction	p. 1
Applications of Sensor Networks	p. 2
Current Hardware Platforms	p. 14
Upcoming Applications	p. 19
Chapter Notes	p. 20
Modeling Sensor and Ad Hoc Networks	p. 21
Introduction	p. 21
Distributed Algorithms	p. 22
Communication	p. 27
Energy	p. 33
Mobility	p. 34
Chapter Notes	p. 35
Clustering	p. 37
Introduction	p. 37
Models	p. 40
Clustering Algorithms for Unit Disk Graphs	p. 41
Clustering Algorithms for General Graphs	p. 54
Conclusionsand Open Problems	p. 59
Chapter Notes	p. 60
MAC Layer and Coloring	p. 63
Introduction	p. 63
Algorithms for Vertex Coloring	p. 69
Conclusion	p. 78
Chapter Notes	p. 79
Topology Control	p. 81
Introduction	p. 81
Quality Criteria	p. 83
Locally Defined Geometric Graphs and Further Proximity Graphs	p. 85
Localized Algorithms	p. 92
Chapter Notes	p. 98
Interference and Signal-to-Noise-Ratio	p. 99
Introduction	p. 99
Interference Models	p. 100
Low-Interference Topologies	p. 103
Topology Scheduling	p. 108
Flow and Path Scheduling	p. 112
Chapter Notes	p. 116
Lower Bounds	p. 117
Introduction	p. 117
A Lower Boundon3-Coloringa Ring	p. 119
Locally Checkable Labelings	p. 126
Minimum-Weight Spanning Trees	p. 128
Chapter Notes	p. 130
Facility Location	p. 131
Introduction	p. 131
Problem Definition	p. 132
Centralized Approximations	p. 136
Simple Distributed Approximation	p. 144
Fast Distributed Approximation	p. 147
Discussionand Outlook	p. 157
Chapter Notes	p. 158
Geographic Routing	p. 161
Introduction	p. 161
Related Work	p. 164
Models and Preliminaries	p. 166
Greedy Routing	p. 170
Routing with Faces	p. 171
A Lower Bound	p. 179
Combining Greedy and Face Routing	p. 181
Conclusion	p. 184
Chapter Notes	p. 184
Compact Routing	p. 187
Introduction	p. 187
Definitions	p. 189
Overview	p. 190
Algorithms	p. 195
Chapter Notes	p. 202
Pseudo Geometric Routing for Sensor Networks	p. 203
Introduction	p. 203
Routing Algorithmsfor Sensor Networks	p. 204
Virtual Coordinate Based Routing	p. 206
Beacon Vector Routing	p. 206
Algorithmic View	p. 210
Related Work	p. 212
Chapter Notes	p. 213
Minimal Range Assignments for Broadcasts	p. 215
Introduction	p. 215
The Algorithm RAPMST and Its Analysis	p. 217
Distributed Computation of an MST	p. 222
Further Advances	p. 229
Conclusion and Open Questions	p. 234
Chapter Notes	p. 235
Data Gathering in Sensor Networks	p. 237
Introduction	p. 237
Network Model	p. 239
Minimum Energy Data Gathering	p. 240
Maximum Lifetime Data Gathering	p. 256
Chapter Notes	p. 262
Location Services	p. 265
Introduction	p. 265
Grid Location Service (GLS)	p. 266
Locality-Aware Location Service (LLS)	p. 272
Mobility-Aware Location Service (MLS)	p. 279
Outlook	p. 280
Chapter Notes	p. 281
Positioning	p. 283
Introduction	p. 283
Hardness Results	p. 284
Algorithms	p. 290
Chapter Notes	p. 304
Security	p. 305
Introduction	p. 305
Symmetric Key Distribution	p. 310
Public-Key Distribution	p. 318
Open Questions	p. 322
Chapter Notes	p. 322
Trust Mechanisms and Reputation Systems	p. 325
Introduction	p. 325
General Trust Models	p. 328
Reputation-Based Trust Protocols in Ad Hoc Networks	p. 333
Open Problems	p. 334
Chapter Notes	p. 335
Selfish Agents and Economic Aspects	p. 337
Introduction	p. 337
Mechanism Design	p. 337
Network Model	p. 339
Unicast in Selfish Networks	p. 339
Multicast in Selfish Networks	p. 351
Chapter Notes	p. 357
Time Synchronization	p. 359
Introduction	p. 359
Time Synchronization Approaches	p. 361
Synchronizing Clocks in the Presence of Faults	p. 367
Theoretical Bounds for Clock Synchronization and Ordering ofEvents	p. 373
Gradient Clock Synchronization	p. 377
Chapter Notes	p. 379
Bibliography	p. 381
Author Index	p. 407
Subject Index	p. 409
Table of Contents provided by Publisher. All Rights Reserved.