Contributors

Part I Challenges for Wireless Sensor Networks

1 Composition and Scaling Challenges in Sensor Networks: An Interaction-Centric View
T. Abdelzaher

1.1 Introduction
1.2 Functional Interactions
1.2.1 Troubleshooting Interactive Complexity
1.2.2 Troubleshooting Examples
1.3 Data Interactions
1.3.1 Privacy and Data Aggregation
1.3.2 Perturbation Examples and Time-Series Data
1.4 Temporal Interactions
1.4.1 Temporal Analysis of Distributed Systems
1.4.2 Reduction-Based Analysis and Delay Composition Algebra
1.5 Interactions of System Dynamics
1.5.1 Sources of Dynamics in Software
1.5.2 Examples of Dynamic Interactions
1.6 Summary
References
 

Part II Models, Topology, Connectivity

2 Scheduling and Power Assignments in the Physical Model
Alexander Fanghänel and Berthold Vöcking

2.1 Introduction
2.1.1 Outline
2.2 Notation and Preliminaries
2.2.1 Robustness of the Physical Model
2.3 Scheduling with the Linear Power Assignment
2.3.1 Measure of Interference and Lower Bounds
2.3.2 Upper Bounds for the Linear Power Assignment
2.4 Scheduling with the Square Root Power Assignment
2.4.1 Scheduling Directed Requests
2.4.2 Scheduling Bidirectional Requests
2.5 The Gap of Oblivious Power Schemes
2.6 Summary and Open Problems
References
 

3 Maintaining Connectivity in Sensor Networks Using Directional Antennae
Evangelos Kranakis, Danny Krizanc, and Oscar Morales

3.1 Introduction
3.1.1 Antenna Orientation Problem
3.1.2 Preliminaries and Notation
3.1.3 Related Work
3.1.4 Outline of the Presentation
3.2 Orienting the Sensors of a Point Set
3.2.1 Sensors with One Antenna
3.2.2 Sensors with Multiple Antennae
3.3 Lower Bounds
3.3.1 One Antenna Per Sensor
3.3.2 Two Antennae Per Sensor
3.4 Sum of Angles of Antennae
3.4.1 Further Questions and Open Problems
3.5 Orienting Planar Spanners
3.5.1 Basic Construction
3.6 Conclusion
References
 

4 Optimal Placement of Ad Hoc Devices Under a VCG-Style Routing Protocol
Peter Widmayer, Luzi Anderegg, Stephan Eidenbenz, and Leon Peeters

4.1 Introduction
4.1.1 Model and Notation
4.1.2 The Device Placement Problem
4.1.3 Related Work
4.2 Placing Multiple Identical Devices for a Single Commodity
4.2.1 The Optimal Position of a Single Additional Device
4.2.2 Multiple Identical Devices
4.3 Single Device Placement for Multiple Commodities
4.3.1 Single Maximization Diagram Approach
4.3.2 Multiple Maximization Diagrams Approach
4.4 Placing Multiple Individual Devices for a Single Commodity
4.5 Placing Multiple Devices for Multiple Commodities
4.5.1 Set Devices
4.5.2 Element Devices
4.5.3 Global Destination Device
4.5.4 Element-Set Chain Devices
4.5.5 Set-Destination Chain Devices
References
 

5 Population Protocols and Related Models
Paul G. Spirakis

5.1 Introduction
5.2 Population Protocols
5.2.1 The Model
5.2.2 Stable Computation
5.3 Mediated Population Protocols
5.3.1 Formal Definition
5.3.2 Computational Power
5.4 The GDM Model
5.4.1 Formal Definition
5.4.2 Weakly Connected Graphs
5.4.3 All Possible Directed Graphs
5.5 Community Protocols
5.5.1 The Model
5.5.2 Computational Power
5.6 Logarithmic Space Machines
5.7 Algorithmic Verification of Population Protocols
5.7.1 Necessary Definitions
5.7.2 NP-Hardness Results
5.7.3 An Efficiently Solvable Special Case
5.7.4 Algorithmic Solutions for BPVER
5.8 Open Problems
References
 

6 Theoretical Aspects of Graph Models for MANETs
Josep Díaz, Dieter Mitsche, and Paolo Santi

6.1 Introduction
6.2 Static Properties
6.3 Mobility Models for MANETs
6.4 Structural Properties of Random Waypoint Mobile Networks
6.4.1 RWP Node Spatial Distribution
6.4.2 RWP Average Nodal Speed
6.4.3 The ``Perfect'' Simulation
6.5 Formal Studies of Connectivity on MANETs' Models
6.5.1 Connectivity Threshold for Mobility Models
6.5.2 Connectivity Periods on Mobile Models
6.5.3 The Effect of Mobility to Speed up Message Dissemination in Sparse Networks
6.6 Conclusions
References
 

7 Networked Distributed Source Coding
Shizheng Li and Aditya Ramamoorthy

7.1 Introduction
7.2 Basics of Distributed Source Coding
7.2.1 Slepian--Wolf Theorem
7.2.2 Equivalence Between Slepian--Wolf Coding and Channel Coding
7.2.3 Distributed Source Coding with a Fidelity Criterion
7.3 Networked Distributed Source Coding: An Introduction
7.4 Networked Distributed Source Coding: Single Terminal
7.4.1 Optimal Rate and Flow Allocation
7.5 Networked Distributed Source Coding: Multiple Terminals
7.5.1 A network Coding Primer
7.5.2 Multicasting Correlated Sources over a Network
7.5.3 Separating Distributed Source Coding and Network Coding
7.5.4 Practical Joint Distributed Source Coding and Network Coding
7.5.5 Resource Allocation for Multicasting Correlated Sources over a Network
7.6 Conclusion
References
 

Part III Localization, Time Synchronization, Coordination

8 The Spatial Smoothing Method of Clock Synchronization
in Wireless Networks
Arvind Giridhar and P.R. Kumar

8.1 Introduction
8.2 Synchronizing Two Clocks
8.3 A Network of Clocks
8.4 Estimating Node Offsets from Edge Offsets
8.4.1 Geometric Graphs
8.5 Spatial Smoothing
8.6 Estimating Nodal Skews
8.7 Properties of the Least-Squares Solution
8.8 The Distributed Spatial Smoothing Algorithm Based on Coordinate Descent
8.9 Convergence Analysis of the Spatial Smoothing Algorithm
8.10 Decomposition Techniques to Speed Up Convergence
8.11 Conclusion
References
 

9 Algorithmic Aspects of Sensor Localization
Sajal K. Das, Jing Wang, R.K. Ghosh, and Rupert Reiger

9.1 Introduction
9.1.1 Importance of Localization
9.1.2 Generic Approach to Solution
9.1.3 Known Algorithmic Approaches
9.1.4 Inherent Challenges
9.1.5 Chapter Organization
9.2 Range-Free Localization
9.2.1 Anchor-Based Approaches
9.2.2 Anchor-Free Approaches
9.3 Range-Based Localization
9.3.1 Range Measurements
9.3.2 Localization Problems Using Range Measurements
9.3.3 Anchor-Based Approaches
9.3.4 Anchor-Free Approaches
9.4 Techniques with Additional Hardware
9.4.1 Angle Measurement
9.4.2 Localization with Angle Measurement
9.5 Techniques Based on Iterative Process
9.6 Mobility-Assisted Localization
9.7 Statistical Techniques
9.8 Summary on Localization Techniques
9.8.1 Localization Accuracy
9.8.2 Computation and Communication Costs
9.8.3 Network and Anchors Density
9.8.4 Summary of Performances
9.9 Open Issues
9.10 Conclusions
References
 

10 Spatio-temporal Context in Wireless Sensor Networks
Anahit Martirosyan and Azzedine Boukerche

10.1 Introduction
10.1.1 What Is Context?
10.2 Node Localization in WSNs
10.2.1 The Task of Localization Algorithms for WSNs
10.2.2 Estimation of Distances and Angles
10.2.3 Trilateration
10.2.4 Multilateration
10.2.5 Localization Algorithms for WSNs
10.3 Temporal Event Ordering in WSNs
10.3.1 Delaying Techniques
10.3.2 Heartbeat
10.3.3 Temporal Message Ordering Scheme
10.3.4 Ordering by Confirmation
10.3.5 An Efficient Algorithm for Preserving Events' Temporal Relationships in Wireless Sensor Actor Networks
10.3.6 Comparison of Features of the Temporal Event Ordering Algorithms
10.4 Time Synchronization in WSNs
10.4.1 Time Synchronization Techniques
10.4.2 Synchronization Algorithms for WSNs
10.4.3 Comparison of Features of the Time Synchronization Algorithms
10.5 Summary
References
 

11 Coordination Problems in Ad Hoc Radio Networks
Dariusz R. Kowalski

11.1 Introduction
11.1.1 Model and Problems
11.1.2 Results
11.2 Wake-Up on a Multiple-Access Channel
11.2.1 Deterministic Synchronization
11.2.2 Randomized Synchronization
11.2.3 Explicit Constructions
11.3 Wake-Up in Multi-hop Radio Networks
11.3.1 Deterministic Wake-Up
11.3.2 Randomized Wake-Up
11.4 Leader Election and Clock Synchronization
11.4.1 Leader Election Protocol
11.4.2 Clock Synchronization
11.5 Mutual Exclusion
11.5.1 From Wake-Up to Mutual Exclusion
11.6 Remarks and Open Problems
References
 

Part IV Data Propagation and Collection
 

12 Probabilistic Data Propagation in Wireless Sensor Networks
Sotiris Nikoletseas and Paul G. Spirakis

12.1 Introduction
12.1.1 A Brief Overview of Wireless Sensor Networks
12.1.2 Critical Challenges
12.1.3 Models and Relations Between Them
12.1.4 The Energy Efficiency Challenge in Routing
12.2 LTP: A Single-Path Data Propagation Protocol
12.2.1 The Protocol
12.2.2 Analysis of the Expected Hops Efficiency
12.2.3 Local Optimization: The Min-Two Uniform Targets Protocol (M2TP)
12.2.4 Tight Upper Bounds to the Hops Distribution of the General Target Protocol
12.3 PFR--A Probabilistic Multi-path Forwarding Protocol
12.3.1 The Protocol
12.3.2 Properties of PFR
12.3.3 The Correctness of PFR
12.3.4 The Energy Efficiency of PFR
12.3.5 The Robustness of PFR
12.4 An Experimental Comparison of LTP, PFR
12.5 Conclusions
References
 

13 Oblivious Routing for Sensor Network Topologies
Costas Busch, Malik Magdon-Ismail, and Jing Xi

13.1 Introduction
13.1.1 Geometric Networks
13.1.2 Mesh Networks
13.2 Geometric Networks
13.2.1 Preliminaries on Geometric Networks
13.2.2 Oblivious Routing on Geometric Networks
13.2.3 Applications of Geometric Networks
13.3 Mesh Networks
13.3.1 Preliminaries on Mesh Networks
13.3.2 Oblivious Routing on Two-Dimensional Mesh Networks
References

14 Scheduling Algorithms for Tree-Based Data Collection in Wireless Sensor Networks
Ozlem Durmaz Incel, Amitabha Ghosh, and Bhaskar Krishnamachari

14.1 Introduction
14.2 Classification Approach and Methodology
14.2.1 Design Objectives
14.2.2 Design Constraints and Assumptions
14.3 Scheduling Algorithms for Data Collection
14.3.1 Algorithms on Minimizing Schedule Length
14.3.2 Algorithms on Minimizing Latency
14.3.3 Algorithms with Other Objectives
14.3.4 Algorithms with Joint Objectives
14.3.5 Taxonomy
14.4 Future Research Directions/Open Problems
14.5 Conclusions
References
 

15 Position-Based Routing in Wireless Ad Hoc and Sensor Networks
Nathalie Mitton, Tahiry Razafindralambo, and David Simplot-Ryl

15.1 Introduction
15.2 Geometric Routing Based on Geographic Coordinates
15.2.1 Greedy and Directional Approaches
15.2.2 Guaranteed Delivery Approaches
15.2.3 Anycasting
15.3 Virtual Coordinate Systems
15.3.1 Landmark-Based Coordinate System
15.3.2 Tree-Based Coordinate System
15.4 Conclusion
References

Part V Energy Optimization

16 Energy-Balanced Data Propagation in Wireless Sensor Networks
Pierre Leone, Sotiris Nikoletseas, and José D.P. Rolim

16.1 Introduction
16.1.1 The Main Idea
16.1.2 Roadmap
16.2 The Model and the Problem
16.3 The EBP Distributed Data Propagation Protocol
16.4 Basic Definitions--Preliminaries
16.5 The General Solution
16.6 A Closed Form for the Forwarding Probability
16.7 A Generalized Algorithm
16.7.1 A Remark About the Underlying Assumption
16.8 On the Optimality of Energy-Balance Protocols
16.8.1 Learning the Protocol's Parameters
16.8.2 A Simple Distributed Strategy
16.9 Conclusions
References
 

17 Dense, Concentric, and Non-uniform Multi-hop Sensor Networks
Sajal K. Das, Alfredo Navarra, and Cristina M. Pinotti

17.1 Introduction
17.2 Related Work
17.2.1 About Localization
17.2.2 About the Energy Hole Problem
17.3 Our Model and Assumptions
17.3.1 Basic Modular Arithmetic
17.4 Localization Problem
17.4.1 Correctness and Performance Analysis
17.4.2 Improvements
17.4.3 The Cooperative Protocol
17.4.4 Experimental Results
17.5 Energy Hole Problem
17.5.1 General Non-uniform Sensor Distribution Strategy
17.5.2 Energy Depletion Analysis
17.5.3 Sub-balanced Energy Depletion
17.5.4 q-Switch Routing and Comparison with Other Node Distribution Strategies
17.6 Concluding Remarks
References
 

18 Prolong the Lifetime of Wireless Sensor Networks Through Mobility: A General Optimization Framework
Jun Luo and Liu Xiang

18.1 Mobile Elements in Wireless Sensor Networks: Stir Up the Pond
18.2 Balancing Traffic Load with Mobile Sinks: The Case of Constrained Mobility
18.2.1 Network Model and Problem Formulation
18.2.2 Complexity Analysis of MNL
18.2.3 Duality Theory and TMNTM
18.2.4 A Primal--Dual Algorithm to Solve MNL
18.2.5 Numerical Results
18.2.6 Summary
18.3 Balancing Traffic Load with Mobile Sinks: The Case of Unconstrained Mobility
18.3.1 Node-Associated Transmission Energy
18.3.2 Link-Associated Transmission Energy
18.3.3 Summary
18.4 Energy Conservation with Mobile Nodes: The Extreme Usage of the Substitution Effect
18.4.1 MNL with Multiple Mobile Nodes (MNL--MMN)
18.4.2 Theorem, Complexity, and Algorithm
18.4.3 Numerical Results
18.4.4 Summary
18.5 Energy Conservation with Mobile Relays: Using Mechanical Data Transportation Smartly
18.5.1 The Single Mobile Relay Positioning (SMRP) Problem
18.5.2 A Variation of SMRP
18.5.3 Summary
18.6 Conclusion
References

 

Part VI Mobility Management

19 Information Spreading in Dynamic Networks: An Analytical Approach
Andrea Clementi and Francesco Pasquale

19.1 Introduction
19.1.1 Warm-Up and Road Map
19.2 Edge-Markovian Evolving Graphs
19.2.1 The Upper Bound
19.2.2 The Lower Bounds
19.3 Stationary Markovian Evolving Graphs
19.3.1 Flooding Time and Expansion Properties
19.3.2 Stationary Edge-MEGs
19.3.3 Parsimonious Flooding in Stationary Edge-MEGs
19.3.4 Stationary Geometric-MEGs
19.3.5 Stationary Geometric-MEGs Under the Connectivity Threshold
19.4 Radio Broadcasting in Dynamic Networks
19.4.1 The Worst-Case Evolving Graph
19.4.2 The Random Evolving Graph: Case p Known
19.4.3 The Random Evolving Graph: Case p Unknown
19.5 Conclusions and Open Problems
References

 

20 Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
Shlomi Dolev and Nir Tzachar

20.1 Introduction
20.2 Self-Stabilizing and Self-Organizing Distributed Algorithms
20.2.1 Spanders, Spanning Expanders
20.2.2 Distributed Expander Construction, Related Work
20.3 System Settings
20.4 Expander Extraction
20.4.1 The Complete Graph
20.4.2 An Arbitrary Expander
20.5 Expansion Monitoring
20.5.1 Monitoring by Random Sampling
20.5.2 Mixing Rate-Based Monitoring
20.5.3 Self-Stabilizing Distributed Monitoring
20.6 Distributed Hierarchical Spanner Construction
References

 

21 Computing by Mobile Robotic Sensors
Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro

21.1 Introduction
21.1.1 Distributed Computing and Mobile Entities
21.1.2 Robots, Sensors, and Mobility
21.1.3 Mobile Robotic Sensors
21.2 Modeling Mobile Robotic Sensors
21.2.1 Capabilities
21.2.2 Behavior
21.2.3 Synchronization
21.2.4 Memory
21.3 Self-Deployment
21.3.1 Introduction
21.3.2 Uniform Deployment on Linear Borders
21.3.3 Uniform Deployment Along Circular Borders
21.3.4 Uniform Deployment in Rectangular Spaces
21.3.5 Incremental Deployment and Filling
21.4 Pattern Formation
21.4.1 Forming Scale-Free Patterns
21.4.2 Circle Formation
21.5 Gathering
21.5.1 Asynchronous Gathering
21.5.2 Semi-Synchronous Gathering
21.5.3 Fully Synchronous Gathering
21.5.4 Coalescence
21.6 Conclusions and Open Problems
References

 

Part VII Security Aspects

22 Security and Trust in Sensor Networks
Przemysaw Baskiewicz and Mirosaw Kutyowski

22.1 Security in (Wireless) Sensor Networks
22.1.1 Types of Attacks
22.1.2 Threats
22.2 Information and Node Authentication
22.2.1 Chaining Protocols
22.2.2 Asymmetric Methods
22.2.3 Sensing Mobile Artifacts
22.2.4 Communication Authentication: A Framework Example
22.3 Key Management
22.3.1 Master Key Schemes
22.3.2 Random Assignment Schemes
22.3.3 Polynomial Share
22.3.4 Multi-group Deployment
22.3.5 Powerful Third Party
22.3.6 Dynamic Key Structures
22.3.7 LEAP: A Full Key Infrastructure
22.4 Encoding
22.4.1 Multiple Paths
22.4.2 Block Ciphers
22.5 Compromised Node Detection
22.5.1 Alert-Based Protocols
22.5.2 Detect and Tolerate
22.5.3 Suicidal Pointer
References
 

23 Key Management in Sensor Networks
Dahai Xu, Jeffrey Dwoskin, Jianwei Huang, Tian Lan, Ruby Lee, and Mung Chiang

23.1 Introduction
23.1.1 Motivation
23.1.2 Summary of Our Study Between Representative Probabilistic and Deterministic Schemes
23.2 Fragility Analysis for Probabilistic Key Management
23.2.1 SAP for a Static Network
23.2.2 SAP for a Mobile Network
23.3 Secret-Protecting Processor Architecture
23.3.1 Reduced Hardware Architecture
23.3.2 Expanded Sensor-Mode SP Architecture
23.4 Security and Economics Analysis of SP Architecture-Based Solution
23.4.1 Attacks on Protected Keys
23.4.2 Attacks on Changing the TSM or the Device Key
23.4.3 Economics Analysis
23.5 Simulation Results
23.5.1 Comparison of Probabilistic and Deterministic Key Predistribution
23.5.2 Security Improvement with SP architecture
23.6 Implications to Related Work
23.6.1 Reinforcements on the Basic EG Scheme
23.6.2 Selective Node Capture
23.7 Key Establishment Approach
23.7.1 An Analytical Framework for Key Establishment
23.7.2 Characterization of Optimal Resilience
23.7.3 Low-Complexity Algorithm for Key Establishment
23.7.4 Numerical Simulations
23.7.5 Proof of Theorem 1
23.7.6 Proof of Theorem 2
23.8 Concluding Remarks
References
 

24 Key Predistribution in Wireless Sensor Networks when Sensors are within Communication Range
Sushmita Ruj, Amiya Nayak, and Ivan Stojmenovic

24.1 Introduction
24.1.1 Shared-Key Discovery
24.1.2 Network Models
24.1.3 Performance Measures and Notation
24.1.4 Identifying Compromised Nodes
24.1.5 Node and Key Revocation
24.2 Key Predistribution Schemes in WSN
24.2.1 Blom's Scheme
24.2.2 Blundo et al.'s Scheme
24.3 The Basic and Q-Composite Schemes
24.4 Random Pairwise Schemes
24.4.1 Chan--Perrig--Song Scheme
24.4.2 Liu--Ning--Li Polynomial-Pool-Based Key Predistribution
24.4.3 Probabilistic scheme of Zhu et al.
24.5 Grid-Based Key Predistribution Schemes
24.5.1 PIKE Scheme of Chan and Perrig
24.5.2 Liu--Ning--Du Scheme
24.5.3 Martin--Paterson--Stinson's Improvement of Liu et al.'s Scheme
24.6 Key Predistribution Using Combinatorial Structures
24.6.1 Çamtepe and Yener's Scheme
24.6.2 Lee and Stinson's Schemes
24.6.3 Chakrabarti--Maitra--Roy Scheme
24.6.4 Ruj and Roy Scheme
24.6.5 Key Predistribution Schemes Using Codes
24.7 Key Predistribution in Multi-hop Networks
24.8 Conclusion
References
 

Part VIII Tools, Applications, and Use Cases

25 Realistic Applications for Wireless Sensor Networks
John A. Stankovic, Anthony D. Wood, and Tian He

25.1 Introduction
25.2 Challenges
25.2.1 From Raw Data to Knowledge
25.2.2 Robust System Operation
25.2.3 Openness and Heterogeneity
25.2.4 Security
25.2.5 Privacy
25.2.6 Real Time
25.2.7 Energy Management
25.2.8 Control and Actuation
25.2.9 Challenges and Applications
25.3 Surveillance Application---VigilNet
25.3.1 Application Requirements
25.3.2 VigilNet Architecture
25.3.3 The Programming Interface
25.3.4 System Work Flow
25.3.5 VigilNet Summary
25.4 Healthcare Applications---AlarmNet
25.4.1 Application Requirements
25.4.2 AlarmNet Architecture
25.4.3 Query Management
25.4.4 Circadian Activity Rhythms
25.4.5 Dynamic Context-Aware Privacy
25.4.6 AlarmNet Summary
25.5 Environmental Science Applications---Luster
25.5.1 Application Requirements
25.5.2 Luster's Architecture
25.5.3 Luster Summary
25.6 Summary
References
 

26 High-Level Application Development for Sensor Networks: Data-Driven Approach
Animesh Pathak and Viktor K. Prasanna

26.1 Introduction
26.1.1 Node-Level Programming
26.1.2 High-Level Abstractions for WSNs
26.1.3 Macroprogram Compilation
26.2 Data-Driven Macroprogramming
26.2.1 Programming Model
26.2.2 Runtime System
26.3 Compilation Process
26.3.1 Input
26.3.2 Output
26.3.3 Process Overview
26.3.4 Challenges
26.4 Compilation Framework
26.5 Srijan: Graphical Toolkit for Data-Driven WSN Macroprogramming
26.6 Evaluation
26.6.1 Reference Applications
26.6.2 Evaluation of the Compiler
26.6.3 Evaluation of the Toolkit
26.7 Concluding Remarks
References
 

27 Toward Integrated Real-World Sensing Environment --- Applications and Challenges
Srdjan Krco and Konrad Wrona

27.1 Introduction
27.2 Military Perspective
27.3 Civilian Perspective
27.4 Selected WSN Applications and Traffic Models
27.4.1 Control and Automation Domain Applications
27.4.2 Transport Applications
27.4.3 Environmental Monitoring for Emergency Services
27.4.4 Health Monitoring Application Traffic Model
27.4.5 Traffic Model Summary
27.5 Characteristics of the WCDMA Networks
27.6 Network Dimensioning Methodology
27.7 Results
27.7.1 Common Channels Analysis
27.8 Conclusions
References