418 WSN Coverage: Knowledge Checks

418.1 Learning Objectives

By the end of this chapter, you will be able to:

Verify Coverage Understanding: Test knowledge of coverage types and algorithms
Apply Zhang-Hou Theorem: Calculate connectivity requirements from sensing range
Analyze Deployment Scenarios: Evaluate grid, random, and OGDC deployment strategies
Solve Coverage Problems: Apply concepts to real-world WSN deployment challenges
Identify Misconceptions: Recognize and avoid common coverage design errors

418.2 Prerequisites

Required Chapters: - WSN Coverage: Production Framework - Framework overview - WSN Coverage Fundamentals - Coverage concepts - WSN Coverage - Coverage types

Technical Background: - Sensor range models - Geometric coverage calculations - Energy optimization concepts

Estimated Time: 35 minutes

Related Chapters

Framework Reference: - WSN Coverage: Production Framework - Production-ready implementation - WSN Coverage Review - Complete review overview

Related WSN Topics: - WSN Coverage Implementations - Algorithm details - WSN Overview Fundamentals - Network architecture - WSN Routing - Energy-aware routing

Learning: - Quizzes Hub - More practice quizzes - Knowledge Gaps Hub - Address learning gaps

For Beginners: How to Use These Quizzes

What is this chapter? Comprehensive knowledge checks covering all WSN coverage concepts with detailed explanations.

Quiz Structure: - 4 quiz sections covering different aspects - Multiple choice questions with detailed explanations - Understanding check scenarios for deeper learning

How to approach: 1. Try to answer before revealing explanation 2. Read explanations even for correct answers 3. Note topics requiring more study 4. Return to prerequisite chapters as needed

Key Topics Covered:

Quiz	Focus Area
Quiz 1	Coverage Optimization (fault tolerance, scheduling)
Quiz 2	Comprehensive Review (Zhang-Hou, OGDC, barrier)
Quiz 3	Deployment Analysis (grid spacing, point coverage)
Quiz 4	Advanced Concepts (theorems, algorithms)

418.3 Quiz 1: WSN Coverage Optimization

Understanding Check: Fault Tolerance Requirements

Scenario: You’re deploying a nuclear power plant perimeter monitoring WSN across 100m x 100m. Sensors have 15m sensing range. Regulations require fault-tolerant monitoring - every point must be monitored by at least 3 sensors simultaneously (k=3 coverage).

Think about: 1. How many sensors would naive 1-coverage deployment require? 2. Does k=3 coverage simply mean “deploy 3x sensors”? 3. What real-world failure scenarios does k=3 coverage protect against?

Key Insight: Theoretical 1-coverage needs ~14 sensors (10,000 m^2 / 707 m^2 per sensor). For k=3, you might expect 14 x 3 = 42 sensors. But practical deployment requires ~128 sensors (2-3x theoretical due to random placement inefficiencies and packing geometry). This extra cost buys critical reliability: if 1 sensor fails, 2 others still monitor that point. Energy optimization: with 128 sensors providing k=3, rotation scheduling lets only 1/3 (43 sensors) run actively while others sleep, extending network lifetime 3x while maintaining fault tolerance. Nuclear facilities often use k=5 coverage despite 5x sensor cost because radiation detection gaps are unacceptable.

Question 1: A WSN deploys 100 sensors for k=2 coverage. After 6 months, 30 sensors have failed. How can the system determine if k=2 coverage is still maintained without exhaustive point-by-point verification?

Explanation: Crossing-based coverage verification (Megerian et al., 2005) provides efficient k-coverage checking: Instead of verifying millions of points, check coverage at crossing points where sensor coverage boundaries intersect. Theorem: If all crossing points have k-coverage, the entire area has k-coverage. How it works: (1) Identify crossings: Find points where k sensor coverage circles intersect. (2) Check coverage: At each crossing, count how many sensors cover that point. (3) Verify k-coverage: If all crossings have >=k sensors, entire area has k-coverage. Complexity reduction: Area has infinite points, but finite crossings. For N sensors: O(N^2) crossings vs. O(infinity) points. With 70 remaining sensors: ~2,450 crossings to check vs. millions of area points. Algorithm: For each crossing point, count overlapping sensor ranges. If minimum count >= k, k-coverage maintained. Real application: After sensor failures, automated coverage verification runs crossing algorithm in seconds, determining if k=2 maintained or if replacement sensors needed. Much faster than full area scan or manual verification. Alternative: Coverage holes can also be detected geometrically using Voronoi diagrams and Delaunay triangulation, identifying regions farthest from active sensors.

Understanding Check: Energy vs. Redundancy Trade-offs

Scenario: Your precision agriculture WSN has 200 soil sensors deployed with k=4 coverage (every point monitored by 4 sensors). Battery life with all 200 sensors active 24/7 is only 6 months. Replacement labor costs $50/sensor visit.

Think about: 1. Can you put 3/4 of the sensors to sleep and still maintain monitoring? 2. What’s the lifetime extension if sensors are active only 25% of the time? 3. What are the operational risks of rotation scheduling?

Key Insight: With k=4 coverage, organize 200 sensors into 4 disjoint sets of 50 sensors each, where each set provides complete 1-coverage. Activate one set at a time, rotating every 6 hours. Result: 50 active sensors (75% sleeping), 4x lifetime extension to 24 months. Cost savings: Avoid 3x battery replacement cycles over 24 months = $30,000 saved (200 sensors x 3 replacements x $50/visit). Trade-offs to consider: Sleeping sensors can’t respond until next rotation (6-hour latency), rotation requires time synchronization overhead, and if active group suffers failures, coverage degrades until next rotation. Agricultural monitoring tolerates 6-hour response delays, making this optimization practical.

Question 2: A forest fire detection WSN uses random aerial deployment, scattering 500 sensors over 5 km^2. Each sensor has Rs=30m. What is the expected coverage percentage?

Explanation: Random deployment coverage probability: For Poisson distributed sensors with density lambda (sensors per unit area), coverage probability = **1 - e^(-lambda*A) where A is sensor coverage area. Calculate lambda: 500 sensors / 5 km^2 = 100 sensors/km^2 = 0.0001 sensors/m^2. Sensor coverage area: A = piRs^2 = pi(30)^2 = 2,827 m^2. Expected coverage parameter: lambdaA = 0.0001 x 2,827 = 0.2827. Coverage probability per point: 1 - e^(-0.2827) = 24.6%. This is very sparse! For good random coverage (~95%): Need lambdapiRs^2 = 3 -> lambda = 3/(piRs^2) = 3/2827 = 0.00106 sensors/m^2 -> Need ~5,300 sensors for 95% coverage. Lesson**: With 500 sensors over 5 km^2, coverage is only ~25% - insufficient for fire detection! For 90% coverage with random deployment, need ~2,300 sensors. This illustrates why random deployment is inefficient compared to planned placement or OGDC optimization.

Understanding Check: Fixing Coverage Gaps

Scenario: Your environmental monitoring WSN deployed 300 sensors with OGDC algorithm activating 110 (36%). Coverage analysis detects 3 gaps totaling 150 m^2. Labor cost to redeploy: $20,000. You have 190 sleeping sensors already in place.

Think about: 1. Should you redeploy the entire network with better planning? 2. Can you just increase transmission power to extend sensing range? 3. What’s the minimum intervention to fill 150 m^2 of gaps?

Key Insight: Selective activation is optimal: Use Voronoi diagrams to identify 8 sleeping sensors near gap boundaries, activate them selectively -> 118 active sensors (39%) achieves 100% coverage. Comparison: Redeploying all 300 costs $20K labor and weeks of downtime (impractical). Increasing transmission power doesn’t extend sensing range - that’s a physics limitation, not power (confusion with communication range!). Mobile robots could relocate sensors but cost $500+/robot. Energy impact: 39% active (118 sensors) vs. 100% active (all 300) = 2.5x lifetime extension while achieving complete coverage. This demonstrates WSN deployment reality: over-provision by 2-3x, activate minimum needed, keep redundant sensors sleeping as repair pool.

Question 3: A WSN provides k=3 coverage using 300 sensors. The system wants to implement rotation scheduling to extend lifetime. What is a critical requirement for safe rotation?

Explanation: Coverage-aware rotation requires verification before deactivation: (1) Before sleep: Before putting sensor S into sleep state, verify that remaining active sensors still provide k-coverage of all points previously covered by S. (2) Coverage algorithm: Run crossing-based verification or localized coverage check on S’s sensing area. (3) Safe deactivation: Only if k-coverage maintained without S, allow it to sleep. Otherwise, S must remain active (cannot be rotated out). (4) Dynamic adjustment: As sensors fail or batteries deplete, rotation sets may need recomputation to maintain coverage. Why critical: Without verification, rotation could create temporary coverage holes. Example: k=3 coverage with 300 sensors. Rotation divides into 3 sets of 100 sensors each. But if geographic distribution is uneven, some areas might have only 3 sensors total (not 3 in each rotation set) -> rotating out 2 of these 3 creates coverage hole (k=1 instead of k=3). Safe rotation algorithm: (1) Organize into k disjoint sets ensuring each set provides 1-coverage. (2) Before deactivating set Si, verify set Sj (next active) maintains coverage. (3) Graceful handoff: Activate Sj before deactivating Si to avoid coverage gaps. (4) Monitor failures: If active set experiences failures reducing coverage below threshold, activate backup sensors from sleeping sets. Real system: Industrial monitoring with k=3 requirement runs coverage verification every rotation cycle (4 hours), ensuring safety even as sensors fail over time.

Question 4: A virtual force algorithm is used to improve WSN coverage after random deployment. How does this algorithm work?

Explanation: Virtual force algorithms (Zou & Chakrabarty, 2003) improve coverage through simulated physics: (1) Repulsive forces: Sensors too close together (overlapping coverage) repel each other, spreading out to reduce redundancy. Force proportional to 1/distance^2. (2) Attractive forces: Coverage holes exert attractive force on nearby sensors, pulling them toward uncovered regions. (3) Boundary forces: Virtual obstacles at deployment boundaries prevent sensors from moving outside target area. (4) Equilibrium: System iterates until forces balance, reaching stable configuration with improved coverage. Algorithm: For each sensor: (a) Calculate forces from all neighbors (repulsive) and coverage holes (attractive). (b) Compute net force vector. (c) Move sensor incrementally in force direction. (d) Repeat until convergence (forces < threshold). Requirements: Mobile sensors with locomotion capability (wheeled robots, aerial drones). Not applicable to static sensors! Performance: Improves random deployment coverage from 75% to 95% through iterative repositioning. Costs: (1) Mobility hardware: Expensive and energy-intensive. (2) Localization: Sensors must know their positions (GPS, trilateration). (3) Computation: Force calculations require neighbor positions. Applications: Underwater sensor networks (AUVs can relocate), aerial drone swarms, disaster response robots. Not practical for scattered static sensors. Alternative for static networks: Use virtual forces to plan initial deployment, then execute with static sensors.

418.4 Quiz 2: Comprehensive Review

Question 1: A deployment uses grid placement with sensors spaced 25m apart in rows and columns. Each sensor has Rs=15m sensing range. What coverage issue will occur?

Explanation: Coverage gap analysis: (1) Horizontal/vertical coverage: Sensors spaced 25m apart with Rs=15m -> gaps between adjacent sensors = 25 - 2x15 = -5m -> overlapping coverage (good). (2) Diagonal distance: Corner-to-corner distance = sqrt(25^2 + 25^2) = 35.4m. (3) Diagonal coverage: For complete coverage, diagonal distance must be <= 2xRs = 30m. Actual diagonal (35.4m) > 30m -> coverage gaps exist at grid cell centers. Correct grid spacing: For circular sensing (Rs=15m), grid spacing should be <= Rs x sqrt(2) = 15 x 1.41 = 21.2m to avoid diagonal gaps. With 25m spacing, square gaps exist at cell centers, farthest from all four corner sensors. Gap size: Center of 25x25m cell is 12.5m from each edge, distance to nearest sensor = sqrt(12.5^2 + 12.5^2) = 17.7m. Since Rs=15m, center point is 2.7m beyond sensing range - uncovered! Solutions: (1) Reduce grid spacing to <=21m. (2) Add sensors at cell centers (but increases deployment cost). (3) Use triangular lattice instead (OGDC optimal spacing sqrt(3) x 15 = 26m avoids gaps). Lesson: Grid deployment seems intuitive but requires careful spacing calculation to avoid coverage holes.

Question 2: A point coverage problem must monitor 50 critical locations (points of interest) with minimum sensors. Each sensor can monitor points within Rs=25m. What approach solves this efficiently?

Explanation: Point coverage monitors discrete locations (POIs) rather than continuous area. Minimum Set Cover approach: (1) Candidate sensors: Identify all potential sensor locations that could cover POIs. (2) Set cover formulation: Each sensor covers a subset of POIs within Rs. Goal: Select minimum sensors whose coverage sets cover all POIs. (3) Algorithm: Greedy set cover - repeatedly select sensor covering most uncovered POIs until all covered. (4) Optimization: Integer Linear Programming (ILP) for optimal solution, or approximation algorithms for large-scale. Why other options fail: (A) Area coverage is overkill - wastes sensors covering unimportant regions between POIs. If 50 points span 1 km^2 but are sparse, area coverage needs 100+ sensors vs. set cover needing 10-20. (B) Random deployment is inefficient and provides no guarantees. (D) One sensor per point ignores that single sensor can cover multiple nearby points. If Rs=25m and 5 POIs cluster within 20m, one sensor covers all 5. Example: Smart building monitoring 50 critical equipment locations. Area coverage approach: 120 sensors for complete building coverage. Minimum set cover: 18 sensors strategically placed, each covering 3-8 equipment POIs within Rs=25m -> 85% sensor reduction. Application domains: Industrial monitoring (critical machinery), infrastructure (structural stress points), environmental (pollution hotspots).

Question 3: According to the Zhang-Hou Theorem, a WSN has sensors with sensing range Rs = 10m. What is the minimum communication range Rc required to guarantee that complete coverage implies network connectivity?

Explanation: The Zhang-Hou Theorem (2005) states: If communication range Rc >= 2 x sensing range Rs, then complete coverage implies connectivity. For Rs = 10m: Rc >= 2 x 10m = 20m. Why this matters: (1) Coverage doesn’t guarantee connectivity: A network can have complete area coverage but be partitioned into disconnected components unable to communicate. (2) Design simplification: When Rc >= 2Rs, designers only need to verify coverage - connectivity comes “for free”. (3) Cost trade-off: Larger communication range requires more power, but eliminates need for separate connectivity algorithms. Practical application: When selecting radio hardware, choose transceivers with Rc >= 2Rs to simplify network design. If cost constraints force Rc < 2Rs, must run separate coverage AND connectivity protocols. Real example: Agricultural WSN with Rs=15m chose Zigbee radios with Rc=40m (2.67xRs), guaranteeing connectivity whenever coverage is achieved - one algorithm instead of two.

Question 4: The OGDC (Optimal Geographical Density Control) algorithm achieves near-optimal coverage by organizing sensors into a specific geometric pattern. What pattern does OGDC create, and why?

Explanation: OGDC creates a triangular lattice with optimal spacing = sqrt(3) x Rs = 1.73 x Rs. Why triangular lattice is optimal: (1) Proven efficiency: For disk coverage (circular sensing ranges), triangular lattice is provably near-optimal, requiring minimum sensors for complete coverage. (2) Optimal spacing: Nodes positioned at distance sqrt(3) x Rs ensure coverage with minimal overlap. (3) Packing efficiency: Better than square grid (2x Rs spacing) or hexagonal (less efficient for disks). OGDC algorithm: (1) Distributed execution: Nodes self-organize without central controller. (2) Localized decisions: Each node only needs neighbor information. (3) Starting node: Random selection with exponential backoff. (4) Iterative activation: Nodes activate if they sponsor significant uncovered area. (5) Power-off messages: Active nodes broadcast, preventing nearby activation. Performance: Achieves >95% coverage with ~40-60% of nodes active -> 40-60% energy savings. Real deployment: Forest fire detection with 200 sensors, OGDC keeps 75 active (62% savings), maintaining 98% coverage vs. 100% all-active. Extends network lifetime from 8 months to 25 months.

Question 5: A border security system uses barrier coverage to detect intruders crossing a 200m border. What is the difference between weak barrier coverage and strong barrier coverage?

Explanation: Weak k-Barrier Coverage: Every crossing path must intersect the sensing ranges of at least k sensors, BUT gaps may exist along the path. An intruder’s path touches k sensors, but portions of the journey may be unmonitored between sensors. Detection: Path-level guarantee (intruder detected at k points during crossing). Strong k-Barrier Coverage: Every point on every crossing path is within sensing range of at least k sensors simultaneously. No gaps exist anywhere along any crossing path. Detection: Continuous monitoring guarantee (intruder monitored throughout entire crossing). Practical implications: (1) Weak barrier: Fewer sensors (lower cost), but intruder can move undetected between sensor zones. Sufficient for detection-only requirements. (2) Strong barrier: More sensors (higher cost), provides continuous tracking. Required for tracking intruder movement and predicting exit location. Example: 200m border, Rs=20m. Weak 1-barrier: ~10 sensors (crossing must hit >=1). Strong 1-barrier: ~14 sensors (complete continuous coverage). Weak 2-barrier: ~20 sensors. Strong 2-barrier: ~28 sensors. Application choice: Airport perimeter (high security) -> strong 2-barrier. Wildlife migration monitoring (presence detection) -> weak 1-barrier.

418.5 Quiz 3: Deployment Analysis

Question 1: A deployment uses grid placement with sensors spaced 25m apart in rows and columns. Each sensor has Rs=15m sensing range. What coverage issue will occur?

418.6 Quiz 4: Advanced Concepts

Question 1: According to the Zhang-Hou Theorem, a WSN has sensors with sensing range Rs = 10m. What is the minimum communication range Rc required to guarantee that complete coverage implies network connectivity?

Question 2: The OGDC (Optimal Geographical Density Control) algorithm achieves near-optimal coverage by organizing sensors into a specific geometric pattern. What pattern does OGDC create, and why?

Question 3: A border security system uses barrier coverage to detect intruders crossing a 200m border. What is the difference between weak barrier coverage and strong barrier coverage?

418.7 Summary

These knowledge checks covered the essential concepts of WSN coverage optimization.

Key Takeaways from Quizzes:

Coverage Verification
- Crossing-based verification is O(N^2) vs. O(infinity) for point-by-point
- Voronoi/Delaunay methods detect holes geometrically
- After failures, automated verification determines if k-coverage maintained
Deployment Strategies
- Grid spacing must account for diagonal distances (spacing <= Rs*sqrt(2))
- Random deployment follows Poisson distribution - inefficient for dense coverage
- Point coverage uses minimum set cover - much more efficient than area coverage
Theorems and Algorithms
- Zhang-Hou: Rc >= 2Rs guarantees connectivity from coverage
- OGDC: Triangular lattice with sqrt(3)*Rs spacing is near-optimal
- Virtual force: Simulated physics for mobile sensor repositioning
Barrier Coverage
- Weak barrier: Path intersects k sensors (detection guarantee)
- Strong barrier: Every point on path covered by k sensors (tracking guarantee)
- Application determines which is appropriate
Energy Optimization
- Rotation scheduling with k-coverage provides kx lifetime extension
- Verify coverage before deactivating sensors
- Sleeping sensors serve as repair pool for gap filling

418.8 Further Reading

Coverage Theory: - Megerian, S., et al. (2005). “Worst and best-case coverage in sensor networks.” IEEE Transactions on Mobile Computing, 4(1), 84-92. - Zhang, H., & Hou, J. C. (2005). “Maintaining sensing coverage and connectivity in large sensor networks.” Ad Hoc & Sensor Wireless Networks, 1(1-2), 89-124.

Coverage Algorithms: - Wang, X., et al. (2003). “Integrated coverage and connectivity configuration in wireless sensor networks.” ACM SenSys. - Tian, D., & Georganas, N. D. (2002). “A coverage-preserving node scheduling scheme for large wireless sensor networks.” ACM WSNA.

Barrier Coverage: - Kumar, S., et al. (2005). “Barrier coverage with wireless sensors.” ACM MobiCom. - Chen, A., et al. (2007). “Local barrier coverage in wireless sensor networks.” IEEE Transactions on Mobile Computing.

Deployment: - Zou, Y., & Chakrabarty, K. (2003). “Sensor deployment and target localization based on virtual forces.” IEEE INFOCOM.

418.9 What’s Next?

Having completed the knowledge checks, you’re ready to explore mobile sensor network concepts.

Continue to WSN Stationary Mobile Fundamentals ->

Or return to the review overview:

Return to WSN Coverage Review ->