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