49  WSN Coverage Algorithms

In 60 Seconds

Coverage maintenance algorithms fall into three categories: geometry-based (OGDC achieves near-optimal triangular lattice coverage with O(n) message complexity), force-based (virtual forces push mobile sensors away from over-covered areas and toward gaps, converging in 10-20 iterations), and schedule-based (rotation of active sensor sets extends lifetime by 5-10x while guaranteeing continuous coverage). The Zhang-Hou crossing theorem enables efficient verification: checking only O(n^2) crossing points of sensing boundaries suffices to prove coverage of an infinite continuous area.

Key Concepts
  • Crossing Coverage Theory: Zhang-Hou theorem proving that checking finite crossing points verifies infinite area coverage
  • OGDC Algorithm: Optimal Geographical Density Control - distributed algorithm achieving near-optimal triangular lattice coverage
  • Virtual Force Algorithm: Coverage repair using simulated attractive/repulsive forces for mobile sensor repositioning
  • Coverage Hole Detection: Identifying uncovered regions using Voronoi diagrams and crossing analysis
  • Rotation Scheduling: Alternating active sensor sets to extend network lifetime while maintaining coverage

49.1 Learning Objectives

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

  • Apply Zhang-Hou crossing theory to verify area coverage using finite intersection point checks instead of infinite test points
  • Implement OGDC distributed coverage algorithms with optimal triangular lattice spacing of sqrt(3) x Rs
  • Evaluate virtual force algorithms that reposition mobile sensors using simulated repulsive and attractive forces for coverage repair
  • Design rotation schedules that organize sensors into disjoint active sets to extend network lifetime by 2-3x
MVU: Minimum Viable Understanding

Core concept: Coverage verification reduces from checking infinite points to finite crossings using Zhang-Hou theorem. Why it matters: OGDC achieves 95%+ coverage with only 40-60% of sensors active, extending network lifetime 2-3x. Key takeaway: Optimal sensor spacing is sqrt(3) x Rs (triangular lattice) - memorize this for deployment planning.

Coverage algorithms are like clever strategies for making sure every inch of a playground is being watched – without wasting anyone’s energy!

49.1.1 The Sensor Squad Adventure: The Great Coverage Challenge

Sammy the Temperature Sensor had a problem. The school principal said, “I need to know that EVERY corner of the schoolyard is being watched. How can you prove it to me?”

Lila the Light Sensor had a brilliant idea. “We do not need to check every single blade of grass! We just need to check the CROSSING POINTS – the spots where our watching circles overlap. If all those spots are covered, then EVERYTHING in between is covered too!” The principal was amazed. “That is much faster than checking a million points!”

Max the Motion Detector figured out the best way to spread out. “If we stand in a TRIANGLE pattern, with each of us exactly 1.73 times our watching distance apart, we cover the most ground with the fewest friends awake. That is the OGDC triangle trick!”

Bella the Button Sensor, who was riding a robot, had another idea. “What about the gaps? I can MOVE to fill them! Imagine invisible magnets – covered areas push me away, and gaps pull me toward them. I just follow the forces until I find the perfect spot!”

49.1.2 Key Words for Kids

Word What It Means
Crossing Point Where two sensor watching-circles overlap – checking these proves everything is covered
OGDC A smart way to decide which sensors sleep and which stay awake
Triangular Lattice Standing in triangle patterns to cover the most area with fewest sensors
Virtual Force Imaginary pushes and pulls that help moving sensors find the best positions

What are coverage algorithms? Coverage algorithms are systematic methods for ensuring a sensor network monitors every part of its target area efficiently. Instead of keeping all sensors active (which drains batteries quickly), these algorithms figure out the minimum set of sensors needed.

Three key algorithms in this chapter:

Algorithm What It Does Best For
Crossing Theory Proves an area is fully covered by checking only intersection points Verifying coverage
OGDC Selects which sensors should be active vs sleeping Extending battery life
Virtual Force Moves mobile sensors to fill coverage gaps Drone swarms, robots

The key insight: You do not need to check every point in an area to verify coverage. The Zhang-Hou theorem says: if all crossing points (where sensor circles intersect) are covered, then everything is covered. This reduces an impossible task (checking infinite points) to a manageable one (checking a finite number of crossings).

Practical impact: OGDC can keep 40-60% of sensors sleeping while maintaining 95%+ coverage, effectively doubling or tripling network lifetime.

49.2 Prerequisites

Before diving into this chapter, you should be familiar with:

Fundamentals:

Implementations:

Review:

49.3 Coverage Maintenance Algorithms

~15 min | Intermediate | P05.C29.U03

49.3.1 Crossing Coverage Theory

Sensor coverage crossings showing intersection points between sensor coverage disks
Figure 49.1: Crossings in sensor coverage - points where sensing ranges of multiple sensors intersect, critical for ensuring complete area coverage
Uncovered crossings example showing gaps in coverage
Figure 49.2: Example of uncovered crossings in sensor network - gaps in coverage occur when sensor ranges do not overlap at boundary points

Theorem (Zhang and Hou):

A continuous region is completely covered if and only if: 1. There exist crossings in the region 2. Every crossing is covered

Definitions:

Crossing:
Intersection point between: - Two sensor coverage disk boundaries, OR - Monitored space boundary and a disk boundary
Crossing-based coverage verification diagram illustrating how all points within sensor coverage disks are guaranteed covered when every crossing point at disk boundary intersections is verified as covered
Figure 49.3: Crossing-based coverage verification showing how checking finite crossing points verifies coverage of infinite area

Why Crossings Matter:

If all crossings are covered, then all points are covered. This reduces the coverage verification problem from checking infinite points to checking finite crossings.

49.3.2 Optimal Geographical Density Control (OGDC)

OGDC algorithm overview showing distributed coverage optimization
Figure 49.4: Optimal Geographical Density Control (OGDC) algorithm overview - distributed coverage algorithm that activates minimal sensors while ensuring complete area coverage

OGDC is a distributed, localized algorithm that achieves near-optimal coverage with minimal active sensors.

Key Idea:

Nodes self-organize into a triangular lattice pattern, which is provably near-optimal for disk coverage.

Optimal Spacing:

For sensors with sensing range Rs, optimal spacing between active sensors is:

\[ d_{optimal} = \sqrt{3} \cdot R_s \]

This minimizes overlap while maintaining complete coverage.

Context: The optimal triangular lattice spacing formula sqrt(3) × Rs comes from geometry - it’s the tightest packing that maintains complete coverage with circular sensing disks. This is the single most important deployment metric for WSN coverage.

Formula: \[ d_{optimal} = \sqrt{3} \cdot R_s \approx 1.732 \cdot R_s \]

Worked Example: A warehouse deploys motion sensors with Rs = 12m sensing radius.

Optimal OGDC spacing: d = sqrt(3) × 12m = 20.8m

For a 200m × 100m warehouse: - Sensors per row: ceil(200m / 20.8m) = 10 sensors - Number of rows: ceil(100m / (20.8m × sin(60°))) = ceil(100m / 18m) = 6 rows - Total sensors: 10 × 6 = 60 sensors

Compare to naive grid (spacing = Rs = 12m): - Grid sensors: ceil(200/12) × ceil(100/12) = 17 × 9 = 153 sensors

Savings: OGDC needs only 60 sensors vs 153 for naive grid - that’s 61% fewer sensors (93 sensors × $65 each = $6,045 saved) while maintaining the same 95%+ coverage.

OGDC triangular lattice diagram showing sensors arranged with sqrt(3) times sensing range spacing, forming hexagonal coverage pattern that minimizes overlap while maintaining complete area coverage
Figure 49.5: OGDC triangular lattice formation showing optimal sqrt(3) x Rs spacing between active nodes

49.3.3 OGDC Algorithm Phases

OGDC coverage patterns showing progressive sensor activation
Figure 49.6: OGDC Coverage Patterns - Demonstrating how OGDC algorithm progressively activates sensors to achieve full coverage with minimal active nodes

Phase 1: Starting Node Selection

OGDC starting node selection using exponential backoff
Figure 49.7: OGDC Starting Node Selection - Exponential backoff mechanism to randomly select initial active sensor 
def ogdc_select_starting_node(nodes, volunteer_probability=0.1):
    """
    Phase 1: Randomly select starting node using exponential backoff
    """
    for node in nodes:
        if random.random() < volunteer_probability:
            # Volunteer to be starting node
            backoff_time = random.uniform(0, MAX_BACKOFF)
            node.backoff_timer = backoff_time

    # Node with shortest backoff becomes starting node
    time.sleep(max(n.backoff_timer for n in nodes))

    # First node whose timer expires wins
    starting_node = min(nodes, key=lambda n: n.backoff_timer)

    starting_node.activate()
    starting_node.broadcast_start_message()

    return starting_node

class StartMessage:
    def __init__(self, sender_id, sender_position, preferred_direction):
        self.sender_id = sender_id
        self.position = sender_position
        self.direction = preferred_direction  # Random angle 0-360 degrees

Phase 2: Iterative Node Activation

OGDC iterative node activation based on power-off messages
Figure 49.8: OGDC Phase 2 Iterative Activation - Additional sensors activated based on power-off messages from neighbors to maintain coverage

49.3.4 OGDC Performance

Coverage Quality:

  • Achieves >95% coverage with ~60% of nodes
  • Near-optimal (within 5% of theoretical minimum)

Energy Efficiency:

  • 40-60% nodes sleep at any time
  • Network lifetime extends by 1.67-2.5x

Scalability:

  • Distributed: No central coordinator
  • Localized: Only neighbor communication
  • Scales to thousands of nodes

49.3.5 Virtual Force Algorithm

Virtual force algorithms (Zou and Chakrabarty, 2003) improve coverage through simulated physics:

Algorithm Components:

  1. Repulsive forces: Sensors too close together (overlapping coverage) repel each other, spreading out to reduce redundancy. Force is proportional to 1/distance squared.

  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.

Virtual force algorithm diagram showing mobile sensors experiencing repulsive forces from nearby sensors to reduce overlap and attractive forces from coverage holes to fill gaps, with boundary forces preventing sensors from leaving the target area
Figure 49.9: Virtual force algorithm showing repulsive forces spreading sensors apart and attractive forces pulling them toward coverage holes

Algorithm Steps:

For each sensor: 1. Calculate forces from all neighbors (repulsive) and coverage holes (attractive) 2. Compute net force vector 3. Move sensor incrementally in force direction 4. Repeat until convergence (forces below 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:

  • Mobility hardware: Expensive and energy-intensive
  • Localization: Sensors must know their positions (GPS, trilateration)
  • 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.

49.4 Algorithm Comparison

Algorithm Type Coverage Active Sensors Complexity Best For
Crossing Theory Verification 100% verified N/A O(N squared) Coverage checking
OGDC Activation 95-98% 40-60% O(N log N) Static WSN
Virtual Force Repositioning 90-95% 100% O(N squared) Mobile sensors
Grid Deployment Placement 100% 100% O(1) Accessible terrain

Worked Example: Wildfire Detection Network Using OGDC Rotation

Scenario: A national park deploys a WSN for early wildfire detection across a 5 km x 3 km forested ridgeline. Sensors detect smoke particulates and temperature anomalies. The park requires continuous coverage for a 6-month fire season with no battery replacements mid-season.

Given:

  • Deployment area: 15 square km (5,000 m x 3,000 m)
  • Sensor sensing range: Rs = 50 m (smoke detection radius)
  • Sensor battery life when active: 45 days continuous
  • Budget: 800 sensors available for aerial scattering deployment
  • Coverage requirement: 95% area coverage at all times
  • Fire season: 180 days (April to September)
  • Random aerial deployment (non-uniform distribution)

Step 1 – Calculate minimum sensors for coverage: Optimal triangular lattice spacing: d = sqrt(3) x Rs = sqrt(3) x 50 = 86.6 m. Sensors per row: 5,000 / 86.6 = 58 sensors. Number of rows: 3,000 / (86.6 x sin(60 degrees)) = 3,000 / 75 = 40 rows. Minimum sensors for 100% coverage in ideal grid: 58 x 40 = 2,320. With random aerial scattering (non-uniform), need 1.5x density for 95% coverage: approximately 3,480 sensors in an ideal scenario. However, we only have 800 sensors.

Step 2 – Determine achievable coverage with 800 sensors: With 800 randomly scattered sensors across 15 square km: density = 53 sensors per square km. Each sensor covers pi x 50^2 = 7,854 square metres. Total coverage area if no overlap: 800 x 7,854 = 6.28 square km = 42% of 15 square km. With typical random overlap factor of 0.7: effective coverage approximately 4.4 square km = 29%. This is insufficient. OGDC cannot create coverage from nothing – it can only optimise which sensors are active.

Step 3 – Redesign: Focus on high-risk ridgeline corridor: Concentrate sensors along 5 km ridgeline (where fires start from lightning strikes), covering a 500 m wide band = 2.5 square km. Sensors needed for 95% coverage of band: 2,500,000 / 7,854 / 0.7 = 455 sensors per active set. Available: 800 sensors in 2.5 square km = 320 sensors per square km = ample density.

Step 4 – Apply OGDC rotation for 180-day season: OGDC selects optimal active set from available nodes:

Round Active sensors Sleeping sensors Duration Cumulative
Round 1 455 (Set A) 345 45 days Day 1-45
Round 2 345 remaining + reuse 110 from Set A 345 sleeping 45 days Day 46-90
Round 3 Re-run OGDC on refreshed pool – 45 days Day 91-135
Round 4 Final rotation – 45 days Day 136-180

Total rotations possible: 800 / 455 = 1.76 full non-overlapping sets. With partial overlap and staggered duty cycling, OGDC achieves 3.5 effective rotations by sharing sensors between sets.

Step 5 – Verify lifetime meets 180-day requirement: Each sensor is active for at most 180 / 1.76 = 102 days across the season (not continuous – interspersed with sleep periods). Battery capacity = 45 days continuous. With OGDC duty cycling at 50% average: effective life = 45 / 0.50 = 90 days active. Shortfall: 102 - 90 = 12 days.

Solution: Reduce active set to 400 sensors (sacrificing 2% coverage from 95% to 93%). Now 800 / 400 = 2.0 full rotations. Each sensor active approximately 90 days. Matches 45-day battery with 50% duty cycle.

Result: OGDC rotation achieves 93% ridgeline coverage for the full 180-day fire season with 800 sensors, zero mid-season battery replacements. Without rotation (all 800 active from day 1), coverage would drop to zero on day 45 – only 25% of the fire season.

Key Insight: OGDC rotation does not increase the number of sensors you have – it extends their useful life by sharing the workload. The critical design decision was narrowing the coverage area from 15 square km (impossible with 800 sensors) to a 2.5 square km high-risk corridor. Coverage algorithms optimise how you use sensors, but cannot substitute for having enough sensors in the first place.

49.5 How It Works: OGDC Triangular Lattice Formation

The OGDC algorithm achieves near-optimal coverage through a two-phase distributed process that self-organizes sensors into a triangular lattice pattern.

Phase 1 - Starting Node Election (Distributed Backoff): Each sensor node that volunteers to be the starting node sets a random backoff timer between 0 and MAX_BACKOFF milliseconds. The node with the shortest timer wins and becomes the first active sensor, broadcasting a START message containing its position and a randomly chosen “preferred direction” angle (0-360 degrees). This randomization prevents collisions and ensures fair election without central coordination.

Phase 2 - Iterative Wavefront Expansion: When a sensor receives a START or POWER_OFF message from an active neighbor, it calculates the distance to that neighbor. If the distance is greater than the optimal spacing threshold (sqrt(3) x Rs ≈ 1.732 x Rs), the sensor recognizes it’s in an uncovered region and activates itself, broadcasting its own POWER_OFF message. This triggers neighbors to perform the same calculation, creating a wavefront of activations that spreads across the deployment area.

Termination Condition: The algorithm converges when no more sensors activate because all remaining dormant sensors are within the optimal spacing distance of already-active sensors. At this point, the network has self-organized into a near-optimal triangular lattice with 95-99% coverage using only 40-60% of deployed sensors.

Why It Works: The sqrt(3) x Rs spacing is mathematically proven to be optimal for disk coverage models. By having each sensor activate only when it’s far enough from existing active sensors, OGDC approximates this optimal pattern in a fully distributed manner without requiring global knowledge or centralized planning.

49.6 Try It Yourself: Coverage Algorithm Simulation

Objective: Implement a simple OGDC simulator to visualize how triangular lattice coverage forms from random deployment.

Setup:

import numpy as np
import matplotlib.pyplot as plt

# Deployment parameters
AREA_SIZE = 200  # 200m x 200m area
NUM_SENSORS = 150  # Randomly scattered sensors
SENSING_RANGE = 20  # Rs = 20m
OGDC_SPACING = np.sqrt(3) * SENSING_RANGE  # Optimal spacing: 34.6m

# Random sensor deployment
np.random.seed(42)
sensors_x = np.random.uniform(0, AREA_SIZE, NUM_SENSORS)
sensors_y = np.random.uniform(0, AREA_SIZE, NUM_SENSORS)
active = np.zeros(NUM_SENSORS, dtype=bool)  # All sensors start sleeping

# Step 1: Select starting node (random)
starting_node = np.random.randint(0, NUM_SENSORS)
active[starting_node] = True
print(f"Starting node: {starting_node} at ({sensors_x[starting_node]:.1f}, {sensors_y[starting_node]:.1f})")

# Step 2: Iterative activation
for iteration in range(20):  # Limit iterations
    newly_activated = []
    for i in range(NUM_SENSORS):
        if active[i]:
            continue  # Skip already active sensors

        # Calculate distance to nearest active sensor
        distances = np.sqrt((sensors_x[i] - sensors_x[active])**2 +
                           (sensors_y[i] - sensors_y[active])**2)
        min_distance = np.min(distances) if len(distances) > 0 else float('inf')

        # Activate if beyond optimal spacing from all active sensors
        if min_distance > OGDC_SPACING:
            active[i] = True
            newly_activated.append(i)

    if len(newly_activated) == 0:
        print(f"Convergence after {iteration} iterations")
        break
    print(f"Iteration {iteration}: Activated {len(newly_activated)} sensors")

# Step 3: Visualize coverage
plt.figure(figsize=(10, 10))
for i in range(NUM_SENSORS):
    if active[i]:
        circle = plt.Circle((sensors_x[i], sensors_y[i]), SENSING_RANGE,
                           color='green', alpha=0.2)
        plt.gca().add_patch(circle)
        plt.plot(sensors_x[i], sensors_y[i], 'go', markersize=8)
    else:
        plt.plot(sensors_x[i], sensors_y[i], 'rx', markersize=6)

plt.xlim(0, AREA_SIZE)
plt.ylim(0, AREA_SIZE)
plt.title(f"OGDC Coverage: {np.sum(active)}/{NUM_SENSORS} active ({100*np.sum(active)/NUM_SENSORS:.1f}%)")
plt.xlabel("X Position (m)")
plt.ylabel("Y Position (m)")
plt.grid(True, alpha=0.3)
plt.legend(['Active sensors', 'Sleeping sensors'], loc='upper right')
plt.savefig('ogdc_coverage.png', dpi=150)
plt.show()

print(f"\nResults: {np.sum(active)} active sensors out of {NUM_SENSORS} deployed")
print(f"Energy savings: {100*(1 - np.sum(active)/NUM_SENSORS):.1f}% of sensors sleeping")

What to Observe:

  1. How many iterations does OGDC need to converge? (Typically 8-15 for 150 sensors)
  2. What percentage of sensors are active? (Should be 35-45% for Rs=20m, area=200x200)
  3. How does the triangular lattice pattern emerge visually? (Green circles should form honeycomb-like pattern)
  4. What happens if you change SENSING_RANGE to 15m or 30m? (Smaller Rs → more active sensors)

Extension Challenge: Modify the code to implement rotation scheduling: After OGDC converges, mark the active set as “Round 1”, then re-run OGDC on only the sleeping sensors to create “Round 2”, and so on. Calculate the total network lifetime improvement from rotation.

49.6.1 Interactive: OGDC Sensor Savings Calculator

Compare naive grid deployment against OGDC triangular lattice to see how many sensors you save.

49.7 Concept Relationships

Concept Builds On Enables Conflicts With
Zhang-Hou Crossing Theorem Disk sensing model, Geometric coverage O(N^2) verification (finite checks), Coverage hole detection Naive infinite-point verification, Probabilistic coverage
OGDC Triangular Lattice Distributed activation, Optimal sqrt(3) x Rs spacing 95-99% coverage with 40-60% active sensors, 2-3x lifetime extension Centralized placement, Random activation schedules
Virtual Force Algorithm Mobile sensors, Simulated physics (repulsion/attraction) Coverage hole repair, 75% → 95% improvement in 10-20 iterations Static sensor networks, High mobility energy cost
Crossing-Based Verification Zhang-Hou theorem, Intersection point analysis Deterministic coverage proof, Coverage gap identification Grid sampling approximation, Statistical confidence approaches
Rotation Scheduling Redundant deployment, OGDC optimal sets 2.5-3x network lifetime, Fault tolerance through backups Single coverage set, All-sensors-always-on operation

49.8 See Also

  • WSN Coverage Fundamentals - Zhang-Hou theorem and coverage vs connectivity relationship foundational to crossing verification
  • WSN Coverage Types - Area, point, and barrier coverage problem formulations that these algorithms solve
  • WSN Coverage Implementations - Hands-on Python labs implementing OGDC, virtual force, and crossing verification
  • WSN Coverage Optimization - Advanced optimization techniques building on OGDC triangular lattice principles
  • WSN Stationary Mobile - Mobile sink strategies that use virtual force concepts for coverage-aware repositioning

Common Pitfalls

A common mistake is assuming a covered area is also connected — sensors may detect events but have no path to relay data. Coverage requires each point to be within sensing range; connectivity requires a communication path to the sink. Always verify both properties independently: use Rc ≥ 2Rs as a sufficient (not necessary) condition for coverage implying connectivity.

OGDC assumes uniform deployment, but boundary nodes cover half-circles rather than full circles, creating systematic under-coverage at deployment edges. Deploy 20-30% more sensors near boundaries or use a larger deployment area with a shrinkage buffer to ensure interior coverage meets specifications.

Reporting ‘200 sensors in 1 km²’ says nothing about actual coverage — 200 clustered sensors leave 90% uncovered. Always measure coverage ratio (fraction of area within sensing range of active nodes) using grid sampling or crossing-point analysis, not just sensor count per unit area.

49.9 Summary

This chapter covered three key coverage algorithms:

Key Takeaways:

  1. Crossing Theory - Zhang-Hou theorem enables efficient coverage verification by checking O(N squared) crossing points instead of infinite area points.

  2. OGDC Algorithm - Distributed, localized algorithm achieving near-optimal triangular lattice (sqrt(3) x Rs spacing) with 40-60% energy savings.

  3. Virtual Force - Mobile sensor repositioning using simulated physics (repulsive between sensors, attractive toward holes). Best for drone swarms and disaster response.

  4. Algorithm Selection - Use crossing theory for verification, OGDC for static WSN activation, virtual force for mobile sensor coverage repair.

49.10 Knowledge Check

49.11 What’s Next?

Now that you can apply coverage algorithms, the next chapter provides hands-on labs and Python implementations.

Topic Chapter Description
Coverage Implementations WSN Coverage Implementations Build and test coverage systems with practical Python labs and code examples
Coverage Fundamentals WSN Coverage Fundamentals Revisit foundational sensing models and coverage-connectivity relationships
Coverage Types WSN Coverage Types Review area, point, and barrier coverage problem formulations
Production Framework WSN Coverage: Production Framework Enterprise-ready OGDC deployment with Cisco Smart Cities case study
Stationary and Mobile WSN WSN Stationary Mobile Fundamentals Mobile sink strategies using virtual force concepts for coverage-aware repositioning
WSN Routing WSN Routing Energy-aware routing protocols that maintain connectivity alongside coverage