Theory and Practice of Wireless Sensor Networks: Cover, Sense, and Inform

Preface
Book Overview
Book Organization
Acknowledgments
Contents
Part I Foundations of Wireless Sensor Networks
1 General Introduction
1.1 Introduction
1.1.1 Major Tasks
1.1.2 Chapter Organization
1.2 Major Challenges
1.2.1 Limited Resources and Capabilities
1.2.2 Location Management
1.2.3 Sensor Deployment
1.2.4 Time-Varying Network Characteristics
1.2.5 Network Scalability, Heterogeneity, and Mobility
1.2.6 Sensing Application Requirements
1.3 Sample Sensing Applications
1.4 Book Motivations
1.5 Design Requirements
1.6 Book Contributions
1.7 Conclusion
2 Fundamental Concepts, Definitions, and Models
2.1 Introduction
2.1.1 Major Tasks
2.1.2 Chapter Organization
2.2 Terminology
2.3 Deterministic and Stochastic Sensing Models
2.4 Network Connectivity and Fault Tolerance
2.5 Energy Consumption Model
2.6 Percolation Model
2.6.1 Why a Continuum Percolation Model?
2.7 Default Network Model
2.8 Random and Group Mobility Models
2.8.1 Random Waypoint Mobility Model (RWP)
2.8.2 Reference Point Group Mobility Model (RPGM)
2.8.3 Manhattan Mobility Model (MMM)
2.8.4 Why Group and Random Mobility Models?
2.9 Conclusion
Part II Percolation Theory-Based Coverage and Connectivity in Wireless Sensor Networks
3 A Planar Percolation-Theoretic Approach to Coverage and Connectivity
3.1 Introduction
3.1.1 Major Tasks
3.1.2 Chapter Organization
3.2 Phase Transition in Sensing Coverage
3.2.1 Estimation of the Shape of Covered Components
3.2.2 Critical Density of Covered Components
3.2.3 Critical Radius of Covered Components
3.2.4 Characterization of Critical Percolation
3.2.5 Numerical Results
3.3 Phase Transition in Network Connectivity
3.3.1 Integrated Sensing Coverage and Network Connectivity
3.4 Discussion
3.5 Related Work
3.6 Conclusion
4 A Spatial Percolation-Theoretic Approach to Coverage and Connectivity
4.1 Introduction
4.1.1 Major Tasks
4.1.2 Chapter Organization
4.2 Three Percolation Problems
4.2.1 Sensing Coverage Percolation
4.2.2 Network Connectivity Percolation
4.2.3 Coverage and Connectivity Percolation
4.3 Further Discussion
4.3.1 Practicality and Generalizability Issues
4.3.2 Sensor Deployment in Spatial Fields
4.3.3 Relaxations of Assumptions
4.4 Related Work
4.5 Conclusion
Part III Convexity Theory-Based Connected k-Coverage in Wireless Sensor Networks
5 A Planar Convexity Theory-Based Approach for Connected k-Coverage
5.1 Introduction
5.1.1 Major Tasks
5.1.2 Chapter Organization
5.2 Achieving Connected k-Coverage
5.2.1 Connected k-Coverage Problem Modeling
5.2.2 Sufficient Condition to Ensure k-Coverage
5.3 Centralized k-Coverage Protocol
5.3.1 Planar Deployment Field Slicing
5.3.2 Sensor Selection
5.3.3 Slicing Grid Dynamics
5.4 Clustered k-Coverage Protocol
5.4.1 Cluster-Head Selection and Attributed Roles
5.4.2 The T-CRACCk Protocol
5.4.3 The D-CRACCk Protocol
5.5 Triggered-Scheduling Driven k-Coverage
5.5.1 K-Coverage Checking Algorithm and Sensor Selection
5.5.2 State Transition Diagram of Trig-DIRACCk
5.5.3 Ensuring Network Connectivity
5.6 Self-scheduling Based k-Coverage
5.6.1 K-Coverage Candidacy Algorithm
5.6.2 State Transition Diagram of Self-DIRACCk
5.6.3 Tri-DIRACCk Versus Self-DIRACCk
5.7 Relaxation of Assumptions
5.7.1 Relaxing the Unit Disk Model
5.7.2 Relaxing the Sensor Homogeneity Model
5.8 Performance Evaluation
5.8.1 Simulation Settings
5.8.2 Simulation Results
5.8.3 Comparison of Self-DIRACCk with CCP
5.9 Related Work
5.10 Conclusion
6 Planar Convexity Theory-Based Approaches for Heterogeneous, On-Demand, and Stochastic Connected k-Coverage
6.1 Introduction
6.1.1 Major Tasks
6.1.2 Chapter Organization
6.2 Heterogeneous Connected k-Coverage
6.2.1 Random Deployment Approach
6.2.2 Pseudo-random Deployment Approach
6.2.3 Performance Evaluation
6.3 On-Demand Connected k-Coverage
6.3.1 Pseudo-random Sensor Placement
6.3.2 Sensor Mobility for k-Coverage of a Region of Interest
6.3.3 Performance Evaluation
6.4 Stochastic Connected k-Coverage
6.4.1 Stochastic k-Coverage Characterization
6.4.2 Stochastic k-Coverage-Preserving Scheduling
6.4.3 Simulation Results
6.5 Related Work
6.5.1 Sensor Heterogeneity
6.5.2 Sensor Mobility
6.5.3 Probabilistic Sensing Model
6.6 Conclusion
7 Spatial Convexity Theory-Based Approaches for Connected k–Coverage
7.1 Introduction
7.1.1 Major Tasks
7.1.2 Chapter Organization
7.2 Equilateral Spherical Triangle-Based Approach
7.2.1 Problem Analysis: The Curse of Dimensionality
7.2.2 Distributed k-Coverage Protocol
7.2.3 Performance Evaluation
7.3 Reuleaux Tetrahedron-Based Approach
7.3.1 Proposed Solution
7.3.2 Problem Analysis
7.3.3 Optimized Spatial k-Coverage
7.3.4 Using Reuleaux Tetrahedra for Sphere Coverage
7.3.5 Reuleaux Tetrahedron-Based Spatial k-Coverage
7.3.6 Assumption Relaxation
7.3.7 Simulation Results
7.4 Related Work
7.5 Conclusion
Part IV Applied Computational Geometry-Based Connected k-Coverage in Wireless Sensor Networks
8 A Planar Regular Hexagonal Tessellation-Based Approach for Connected k-Coverage
8.1 Introduction
8.1.1 Major Tasks
8.1.2 Chapter Organization
8.2 Study of Planar Pavers
8.2.1 Paving Metric
8.2.2 Planar Regular Convex Paver Quality
8.3 Regular Hexagonal Centroid-Based Connected k-Coverage
8.3.1 Achieving Optimal Coverage
8.3.2 Problems with k-Coverage for k ge2
8.4 Regular Hexagonal Area Stretching-Based Connected k-Coverage
8.4.1 Foundational Study
8.4.2 Random Regular Hexagonal Tessellation
8.4.3 Hexagonal Cone-Based Pseudo-Random k-Coverage
8.4.4 Hexagonal Perimeter-Based Pseudo-Random k-Coverage
8.4.5 Edge Problem
8.4.6 Discussion
8.5 Possible Extensions
8.5.1 Extension 1: Using Non-Deterministic Sensing Model
8.5.2 Extension 2: Heterogenous Sensor Deployment
8.6 Performance Evaluation
8.6.1 Simulation Setup
8.6.2 Simulation Results
8.7 Related Work
8.8 Conclusion
9 A Planar Irregular Hexagonal Tessellation-Based Approach for Connected k-Coverage
9.1 Introduction
9.1.1 Major Tasks
9.1.2 Chapter Organization
9.1.3 Planar Tiling Using Congruent Tiles
9.2 Achieving Planar k-Coverage Using Hexagonal Tiles
9.2.1 Ensuring 1-Coverage
9.2.2 Ensuring k-Coverage
9.3 Achieving Planar k-Coverage Using Irregular Hexagonal Tiles
9.3.1 Irregular Hexagonal Tiling with  IRH( r/2 )
9.3.2 Irregular Hexagonal Tiling with  IRH( r/3 )
9.3.3 Irregular Hexagonal Tiling with  IRH( r/n )
9.3.4 Discussion on Planar Sensor Density
9.4 A k-Coverage Protocol Using Irregular Hexagonal Tiling
9.4.1 Generating Reference Irregular Hexagon and k-Coverage
9.4.2 Expanding Hexagonal Grid and k-Coverage
9.4.3 Example
9.4.4 Problem of Side-Effect
9.5 Performance Evaluation
9.5.1 Simulation Setup
9.5.2 Simulation Results
9.6 Related Work
9.7 Conclusion
10 A Polyhedral Space Filler Tessellation-Based Approach for Connected k-Coverage
10.1 Introduction
10.1.1 Major Tasks
10.1.2 Chapter Organization
10.2 Investigating Polyhedral Space-Fillers
10.2.1 Cubic Space-Filler
10.2.2 Regular Right Hexagonal Prism Space-Filler
10.2.3 Truncated Octahedral Space-Filler
10.2.4 Great Rhombicuboctahedral Space-Filler
10.2.5 Rhombic Dodecahedral Space-Filler
10.2.6 Elongated Dodecahedral Space-Filler
10.2.7 Rhombic Triacontahedral Space-Filler
10.2.8 Sommerville’s Largest Tetrahedral Space-Filler
10.2.9 Baumgartner’s Tetrahedral Space-Filler
10.2.10 Goldberg’s Equilateral Octahedral Space-Filler
10.3 Solving the Connected Coverage Problem
10.3.1 Sensor Selection Algorithm
10.3.2 Performance Evaluation
10.4 Connected k-Coverage Problem
10.4.1 Achieving Spatial k-Coverage
10.4.2 Ensuring Spatial Connected k-Coverage
10.4.3 Discussion
10.4.4 Sensor Selection Protocol
10.5 Performance Evaluation
10.5.1 Simulation Setup
10.5.2 Simulation Results
10.6 Related Work
10.7 Conclusion
Part V Connectivity and Fault-Tolerance Measures of k-Covered Wireless Sensor Networks
11 Planar Unconditional and Conditional Network Connectivity and Fault-Tolerance Measures for k-Covered Wireless Sensor Networks
11.1 Introduction
11.1.1 Major Tasks
11.1.2 Chapter Organization
11.2 Unconditional Fault-Tolerance Measures
11.2.1 Homogeneous Sensors
11.2.2 Heterogeneous Sensors
11.3 Conditional Fault-Tolerance Measures
11.3.1 Homogeneous Sensors
11.3.2 Heterogeneous Sensors
11.4 Related Work
11.5 Conclusion
12 Spatial Unconditional and Conditional Network Connectivity and Fault-Tolerance Measures for k-Covered Wireless Sensor Networks
12.1 Introduction
12.1.1 Major Tasks
12.1.2 Chapter Organization
12.2 Unconditional Connectivity
12.2.1 Homogeneous Sensors
12.2.2 Heterogeneous Sensors
12.2.3 Boundary Effects
12.3 Conditional Connectivity
12.3.1 Homogeneous Sensors
12.3.2 Heterogeneous Sensors
12.4 Discussion
12.4.1 Relaxing the Assumption of k ≥ 4
12.4.2 Sensor Placement Strategy
12.4.3 Sink-Independent Connectivity Measures
12.4.4 Spatial Sensing Applications
12.5 Relaxing the Unit Sphere Model: Convex Model
12.5.1 Homogeneous Sensors
12.5.2 Heterogeneous Sensors
12.6 Underwater Sensor Networks
12.7 Related Work
12.8 Conclusion
Part VI Geographic Data Forwarding, Gathering, and Delivery in Wireless Sensor Networks
13 A Planar Checkpoints-Based Approach for Geographic Forwarding on Always-on Sensors
13.1 Introduction
13.1.1 Major Tasks
13.1.2 Chapter Organization
13.2 The WLDT Protocol
13.2.1 Long-Range Versus Short-Range Forwarding
13.2.2 A Two-Step Data Forwarding Protocol
13.2.3 Illustrative Example
13.3 Analysis of WLDT
13.4 Short-Range Versus Long-Range
13.4.1 Energy Gain
13.4.2 Controlled Short-Range Data Forwarding
13.5 Discussion
13.6 Related Work
13.7 Conclusion
14 A Planar Energy-Delay Trade-off Based Approach for Geographic Forwarding on Always-on Sensors
14.1 Introduction
14.1.1 Major Tasks
14.1.2 Chapter Organization
14.2 A Slicing Approach
14.2.1 Slicing of Communication Range
14.2.2 Selection of Candidate Proxy Forwarders
14.2.3 Uniform Energy Depletion Characterization
14.3 Trading-off Energy with Delay
14.3.1 Simple Analytical Bounds
14.3.2 Multi-objective Optimization Approach
14.3.3 TED Detailed Description
14.4 Relaxation of Several Key Assumptions
14.4.1 Relaxing the Sensor Homogeneity Model
14.4.2 Relaxing the Communication Disk Model
14.4.3 Relaxing the Dense Network Model
14.4.4 Relaxing the Energy Consumption Model
14.4.5 Relaxing the Always-on Sensors Model
14.5 Simulation Results
14.5.1 Simulation Settings
14.5.2 Impact of Selection Space Size
14.5.3 Using the Energy × Delay Metric
14.5.4 Impact of Variability of k
14.5.5 Impact of Sensor Heterogeneity
14.6 Related Work
14.7 Conclusion
15 A Planar Approach for Solving the Energy Sink-Hole Problem with Always-on Sensors
15.1 Introduction
15.1.1 Major Tasks
15.1.2 Chapter Organization
15.2 Energy Sink-Hole Problem Analysis
15.2.1 Base Protocol Average Energy Consumption
15.2.2 Nominal Communication Range–Based Data Forwarding
15.2.3 Adjustable Communication Range-Based Data Forwarding
15.3 Using Heterogeneous Sensors
15.3.1 Multi-tier Architecture
15.3.2 NEAR Performance Evaluation
15.4 Sink Mobility and Energy Aware Voronoi Diagram
15.4.1 Why Energy Aware Voronoi Diagram?
15.4.2 EVEN Detailed Description
15.4.3 EVEN Performance Evaluation
15.5 Related Work
15.5.1 Balancing Energy Consumption
15.5.2 Minimizing Energy Consumption
15.5.3 Mobility-Based Forwarding Protocols
15.6 Conclusion
Part VII Joint k-Coverage and Geographic Data Forwarding and Gathering in Wireless Sensor Networks
16 Planar and Spatial Approaches for Joint k-Coverage and Data Collection Using Homogeneous Duty-Cycled Sensors
16.1 Introduction
16.1.1 Major Tasks
16.1.2 Chapter Organization
16.2 A Planar Approach for Joint k-Coverage and Data Collection
16.2.1 Potential Fields Based Modeling Approach
16.2.2 Data Forwarding Without Aggregation
16.2.3 Data Forwarding with Aggregation
16.2.4 Generalizability of GEFIB
16.2.5 Performance Evaluation
16.3 A Spatial Approach for Joint k-Coverage and Composite Forwarding
16.3.1 First Hybrid Geographic Forwarding
16.3.2 Second Hybrid Geographic Forwarding
16.4 Related Work
16.5 Conclusion
17 A Planar Approach for Joint k-Coverage and Data Collection Using Sparsely Deployed Duty-Cycled Sensors
17.1 Introduction
17.1.1 Major Tasks
17.1.2 Chapter Organization
17.2 Heterogeneous k-Coverage
17.3 Mobile k-Coverage
17.3.1 Four-Tier Sensor Network Architecture
17.3.2 k-Coverage Approach Design Decisions
17.3.3 Achieving Mobile k-Coverage
17.4 Data Gathering Algorithms
17.4.1 Direct Data Gathering
17.4.2 Chain-Based Data Gathering
17.5 Impact of Sensor Heterogeneity
17.6 Performance Evaluation
17.6.1 Simulation Setup
17.6.2 Simulation Results
17.7 Related Work
17.8 Conclusion
18 Planar Approaches for Joint k-Coverage and Data Collection Using Heterogeneous Duty-Cycled Sensors
18.1 Introduction
18.1.1 Major Tasks
18.1.2 Chapter Organization
18.2 Basic Two-Tier Architecture
18.2.1 Impact of the Energy Sink-Hole Problem
18.2.2 Energy Consumption Analysis
18.3 Three-Tier Architecture with Constant Band Width
18.3.1 Proposed Architecture
18.3.2 Joint Mobility and Routing
18.3.3 Architecture 1: 1 Static Sink—1 Mobile Proxy Sink
18.3.4 Architecture 2: 1 Static Sink—N Mobile Proxy Sinks
18.3.5 Architecture 3: N Static Sinks—1 Mobile Proxy Sink
18.3.6 Architecture 4: N Static Sinks – N Mobile Proxy Sinks
18.3.7 Performance Evaluation
18.4 Three-Tier Architecture with Varying Band Widths
18.4.1 Proposed Architecture
18.4.2 Static Data Collection Schemes
18.4.3 Mobile Data Collection
18.4.4 Performance Evaluation
18.5 Conclusion
Part VIII Connected k-Barrier Coverage in Wireless Sensor Networks
19 A Planar Approach for Physical Security Using Connected k-Barrier Coverage
19.1 Introduction
19.1.1 Major Tasks
19.1.2 Chapter Organization
19.2 Tiling-Based k-Barrier Coverage
19.2.1 Intruder’s Abstract Path Counting
19.2.2 Intruder’s Abstract Path Analysis
19.2.3 Square Lattice-Based Sensor Deployment
19.2.4 Hexagonal Lattice-Based Sensor Deployment
19.2.5 Square Lattice Versus Hexagonal Lattice
19.2.6 Discussion
19.3 Generalization
19.4 Source-to-Destination Path Analysis
19.4.1 Square k-barrier Covered Sensor Belt
19.4.2 Rectangular k-barrier Covered Sensor Belt
19.5 Other Possible Generalizations
19.6 Performance Evaluation
19.6.1 Simulation Setup
19.6.2 Simulation Results
19.7 Related Work
19.8 Conclusion
20 A Spatial Approach for Physical Security Through Connected k-Barrier Coverage
20.1 Introduction
20.1.1 Major Tasks
20.1.2 Chapter Organization
20.2 Spatial k-Barrier Coverage Problem Analysis
20.2.1 Simple Cubic Lattice
20.2.2 Body Centered Cubic (BCC) Lattice
20.2.3 Face Centered Cubic (FCC) Lattice
20.2.4 Hexagonal Close-Packed (HCP) Lattice
20.3 Polyhedral Space-Filling Lattice
20.3.1 Intruder’s Path Analysis
20.3.2 Intruder’s Path Representation and Counting
20.4 Performance Evaluation
20.4.1 Simulation Setup
20.4.2 Numerical Versus Simulation Results
20.5 Related Work
20.6 Conclusion
Part IX Applications of Wireless Sensor Networks and Concluding Remarks
21 An Overview of Sensing Hardware, Standards, Operating Systems, Software Development, and Applications and Systems
21.1 Introduction
21.1.1 Major Tasks
21.1.2 Chapter Organization
21.2 Sensing Hardware
21.2.1 Mote Hardware
21.2.2 Sensor Technology
21.2.3 Gateways
21.3 Sensing Software
21.3.1 Industry Standards
21.3.2 Operating Systems
21.4 Sensing Software Development: Challenges and Solutions
21.4.1 Sensing Application Models
21.4.2 Debugging
21.4.3 Memory
21.4.4 Sensing
21.4.5 Protocols and Radio Communication
21.4.6 Security
21.5 Sensing Applications and Systems
21.5.1 Healthcare Industry
21.5.2 Agriculture Industry
21.5.3 Environmental Industry
21.5.4 Industry
21.5.5 Military
21.6 Future Applications and Technologies
21.6.1 Marine Deployments
21.6.2 Smart Homes
21.7 Conclusion
22 Summary and Further Extensions
22.1 Summary of Book Contributions
22.2 Further Extensions
References