413  WSN Coverage: K-Coverage and Rotation Scheduling

Imagine youโ€™re managing a 24/7 security guard service for a building. You need: 1. Backup guards - If one guard gets sick, another can cover their post (thatโ€™s K-coverage) 2. Shift schedules - Guards take turns working so no one gets exhausted (thatโ€™s rotation)

Wireless sensor networks face the same challenges: - K-Coverage means every spot is watched by K sensors. If one fails, others still monitor the area - Rotation Scheduling means sensors take turns sleeping and waking, extending battery life

Term Simple Explanation
K-Coverage Each spot is watched by K sensors (for backup if one fails)
Rotation Set A group of sensors that can cover the entire area by themselves
Duty Cycling Sensors take turns sleeping and waking to save battery
Fault Tolerance System keeps working even when some sensors fail

Why this matters: In critical applications like industrial safety or healthcare monitoring, you canโ€™t afford gaps when a sensor dies. K-coverage with rotation ensures reliable monitoring for years instead of months.

413.1 Learning Objectives

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

  • Design K-Coverage Deployments: Plan sensor networks where each point is monitored by K sensors
  • Calculate Sensor Requirements: Determine the number of sensors needed for K-coverage with overlap factors
  • Implement Coverage Rotation: Schedule multiple sensor sets to rotate coverage duties
  • Optimize Network Lifetime: Balance coverage requirements with energy conservation
  • Analyze Fault Tolerance: Evaluate how many sensor failures a deployment can withstand

413.2 Prerequisites

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

413.3 K-Coverage Fault-Tolerant Deployment

K-coverage ensures each point is monitored by at least K sensors, providing fault tolerance and reliability even when sensors fail.

%% fig-alt: "Diagram showing K-coverage fault tolerance levels from 1-coverage to 3-coverage."
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'secondaryColor': '#16A085', 'tertiaryColor': '#E67E22'}}}%%

graph LR
    subgraph K1["1-Coverage (K=1)"]
        P1[Point P]
        S1[Sensor 1]
        P1 -.->|Monitored by| S1
        Fail1[If S1 fails] --> Gap1[Coverage lost]
    end

    subgraph K2["2-Coverage (K=2)"]
        P2[Point P]
        S2A[Sensor 2A]
        S2B[Sensor 2B]
        P2 -.->|Monitored by| S2A
        P2 -.->|Monitored by| S2B
        Fail2[If S2A fails] --> OK2[Still covered by S2B]
    end

    subgraph K3["3-Coverage (K=3)"]
        P3[Point P]
        S3A[Sensor 3A]
        S3B[Sensor 3B]
        S3C[Sensor 3C]
        P3 -.->|Monitored by| S3A
        P3 -.->|Monitored by| S3B
        P3 -.->|Monitored by| S3C
        Fail3[2 sensors fail] --> OK3[Still covered by S3C]
    end

    style Gap1 fill:#E67E22,stroke:#2C3E50,color:#fff
    style OK2 fill:#16A085,stroke:#2C3E50,color:#fff
    style OK3 fill:#16A085,stroke:#2C3E50,color:#fff
    style P1 fill:#2C3E50,stroke:#16A085,color:#fff
    style P2 fill:#2C3E50,stroke:#16A085,color:#fff
    style P3 fill:#2C3E50,stroke:#16A085,color:#fff

Figure 413.1: K-coverage fault tolerance levels: 1-coverage provides basic monitoring but fails completely when sensor fails, 2-coverage tolerates single sensor failure, 3-coverage tolerates up to 2 simultaneous failures

K-coverage fault tolerance: 1-coverage provides basic monitoring but fails completely when sensor fails, 2-coverage tolerates single sensor failure, 3-coverage tolerates up to 2 simultaneous failures. K-coverage enables graceful degradation and reliability in critical applications.

413.3.1 K-Coverage Requirements

For K-coverage across area A with sensors of range Rs:

\[ N_{sensors} \geq K \times \frac{A}{\pi R_s^2} \times \alpha \]

Where alpha is approximately 1.2-1.4, the overlap factor accounting for non-ideal placement.

413.3.2 Python Implementation: K-Coverage Calculator

def calculate_k_coverage_requirements(area_m2, sensing_range_m, k_coverage):
    """
    Calculate minimum sensors needed for K-coverage

    Args:
        area_m2: Monitored area in square meters
        sensing_range_m: Sensor detection radius
        k_coverage: Required coverage degree (1, 2, 3...)

    Returns:
        Dictionary with sensor counts and deployment specs
    """
    import math

    # Single sensor coverage area
    sensor_coverage = math.pi * (sensing_range_m ** 2)

    # Minimum sensors for 1-coverage (theoretical)
    min_sensors_1coverage = area_m2 / sensor_coverage

    # Apply overlap factor (1.3 for random deployment)
    overlap_factor = 1.3
    practical_1coverage = math.ceil(min_sensors_1coverage * overlap_factor)

    # Scale for K-coverage
    k_coverage_sensors = practical_1coverage * k_coverage

    # Optimal grid spacing for K-coverage
    optimal_spacing = (math.sqrt(3) * sensing_range_m) / math.sqrt(k_coverage)

    return {
        'k_coverage': k_coverage,
        'area_m2': area_m2,
        'sensing_range_m': sensing_range_m,
        'theoretical_min': min_sensors_1coverage,
        'practical_sensors': k_coverage_sensors,
        'optimal_spacing_m': optimal_spacing,
        'fault_tolerance': k_coverage - 1,
        'expected_coverage_percent': min(99.5, 95 + k_coverage * 1.5)
    }

# Example: Smart factory floor monitoring
factory_specs = calculate_k_coverage_requirements(
    area_m2=10000,  # 100m x 100m factory floor
    sensing_range_m=15,  # Temperature sensors
    k_coverage=2  # Tolerate single sensor failure
)

print(f"Smart Factory 2-Coverage Requirements:")
print(f"  Area: {factory_specs['area_m2']}m squared")
print(f"  Coverage degree: {factory_specs['k_coverage']}")
print(f"  Sensors needed: {factory_specs['practical_sensors']}")
print(f"  Optimal spacing: {factory_specs['optimal_spacing_m']:.1f}m")
print(f"  Fault tolerance: {factory_specs['fault_tolerance']} sensor failures")
print(f"  Expected coverage: {factory_specs['expected_coverage_percent']:.1f}%")

Output:

Smart Factory 2-Coverage Requirements:
  Area: 10000m squared
  Coverage degree: 2
  Sensors needed: 368
  Optimal spacing: 18.4m
  Fault tolerance: 1 sensor failures
  Expected coverage: 98.0%

413.3.3 Real-World K-Coverage Applications

Application K-Value Justification Energy Impact
Smart agriculture K=1 Occasional gaps acceptable, long battery life critical Baseline
Building security K=2 Single sensor failure shouldnโ€™t create blind spots 2x energy
Industrial safety K=3 Critical safety monitoring, regulatory compliance 3x energy
Nuclear monitoring K=4 Extreme reliability, redundancy for maintenance 4x energy

413.3.4 Trade-offs

  • Higher K = Better reliability but more sensors, higher cost, shorter network lifetime
  • Lower K = Longer lifetime but coverage lost during failures
  • Optimal K depends on application criticality and maintenance accessibility

413.4 Coverage Rotation Scheduler

Coverage rotation extends network lifetime by scheduling multiple sets of sensors to take turns providing coverage, ensuring some sensors sleep while maintaining full coverage.

%% fig-alt: "Gantt chart showing coverage rotation schedule with three sensor sets taking 8-hour shifts."
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'secondaryColor': '#16A085', 'tertiaryColor': '#E67E22'}}}%%

gantt
    title Coverage Rotation Schedule (3 Sets, 8-hour shifts)
    dateFormat HH:mm
    axisFormat %H:%M

    section Set A (Red)
    Active   :a1, 00:00, 8h
    Sleep    :a2, 08:00, 8h
    Sleep    :a3, 16:00, 8h

    section Set B (Green)
    Sleep    :b1, 00:00, 8h
    Active   :b2, 08:00, 8h
    Sleep    :b3, 16:00, 8h

    section Set C (Blue)
    Sleep    :c1, 00:00, 8h
    Sleep    :c2, 08:00, 8h
    Active   :c3, 16:00, 8h

Figure 413.2: Coverage rotation scheduling: network partitioned into 3 disjoint coverage sets that rotate 8-hour active/sleep cycles

Coverage rotation scheduling: network partitioned into 3 disjoint coverage sets that rotate 8-hour active/sleep cycles. Each set independently provides full coverage, tripling network lifetime from 1 year to 3 years while maintaining continuous monitoring.

413.4.1 Python Implementation: Rotation Algorithm

def schedule_coverage_rotation(sensors, sensing_range, num_sets=3):
    """
    Partition sensors into disjoint coverage sets for rotation

    Args:
        sensors: List of sensor objects with positions
        sensing_range: Detection radius
        num_sets: Number of rotation sets (typically 2-4)

    Returns:
        List of coverage sets, each providing full coverage
    """
    import numpy as np
    from scipy.spatial import distance_matrix

    # Calculate distances between all sensor pairs
    positions = np.array([s.position for s in sensors])
    distances = distance_matrix(positions, positions)

    coverage_sets = [[] for _ in range(num_sets)]
    assigned = set()

    # Greedy set assignment ensuring coverage
    for set_idx in range(num_sets):
        print(f"\nBuilding Set {set_idx + 1}:")

        # Start with random unassigned sensor
        available = [s for s in sensors if s.id not in assigned]
        if not available:
            break

        current_set = [available[0]]
        assigned.add(available[0].id)

        # Iteratively add sensors to maintain coverage
        while True:
            # Find largest uncovered area
            uncovered_points = find_uncovered_regions(current_set, sensing_range)

            if len(uncovered_points) == 0:
                break  # Full coverage achieved

            # Select unassigned sensor covering most uncovered points
            best_sensor = None
            best_coverage = 0

            for sensor in sensors:
                if sensor.id in assigned:
                    continue

                # Count how many uncovered points this sensor covers
                covered = sum(1 for pt in uncovered_points
                             if np.linalg.norm(sensor.position - pt) <= sensing_range)

                if covered > best_coverage:
                    best_coverage = covered
                    best_sensor = sensor

            if best_sensor is None:
                print(f"  Warning: Cannot achieve full coverage with remaining sensors")
                break

            current_set.append(best_sensor)
            assigned.add(best_sensor.id)

        coverage_sets[set_idx] = current_set
        print(f"  Set {set_idx + 1}: {len(current_set)} sensors")

    return coverage_sets

def simulate_rotation_lifetime(coverage_sets, battery_capacity_mAh,
                                active_current_mA, sleep_current_uA):
    """
    Calculate extended network lifetime with rotation

    Args:
        coverage_sets: List of sensor sets for rotation
        battery_capacity_mAh: Battery capacity in milliamp-hours
        active_current_mA: Current draw when active
        sleep_current_uA: Current draw when sleeping

    Returns:
        Dictionary with lifetime analysis
    """
    sleep_current_mA = sleep_current_uA / 1000.0  # Convert to mA
    num_sets = len(coverage_sets)

    # Single set active time (no rotation)
    single_set_hours = battery_capacity_mAh / active_current_mA

    # With rotation: each sensor active 1/num_sets of time
    duty_cycle = 1.0 / num_sets
    avg_current = duty_cycle * active_current_mA + (1 - duty_cycle) * sleep_current_mA

    rotation_hours = battery_capacity_mAh / avg_current

    # Network lifetime = until first set dies
    network_lifetime_hours = rotation_hours

    return {
        'num_sets': num_sets,
        'single_set_lifetime_hours': single_set_hours,
        'rotation_lifetime_hours': network_lifetime_hours,
        'lifetime_extension_factor': network_lifetime_hours / single_set_hours,
        'single_set_lifetime_days': single_set_hours / 24,
        'rotation_lifetime_days': network_lifetime_hours / 24,
        'duty_cycle_percent': duty_cycle * 100,
        'avg_current_mA': avg_current
    }

# Example: Forest fire monitoring network
print("Forest Fire Monitoring - Coverage Rotation Analysis")
print("=" * 50)

rotation_results = simulate_rotation_lifetime(
    coverage_sets=[[1] * 50, [2] * 50, [3] * 50],  # 3 sets of 50 sensors each
    battery_capacity_mAh=2500,  # 2 x AA batteries
    active_current_mA=20,  # Active sensing + radio
    sleep_current_uA=5  # Deep sleep mode
)

print(f"\nRotation Configuration:")
print(f"  Number of sets: {rotation_results['num_sets']}")
print(f"  Duty cycle per sensor: {rotation_results['duty_cycle_percent']:.1f}%")
print(f"  Average current: {rotation_results['avg_current_mA']:.2f} mA")

print(f"\nLifetime Comparison:")
print(f"  Without rotation: {rotation_results['single_set_lifetime_days']:.0f} days")
print(f"  With rotation: {rotation_results['rotation_lifetime_days']:.0f} days")
print(f"  Extension factor: {rotation_results['lifetime_extension_factor']:.1f}x")
print(f"\nConclusion: Rotation extends battery life from {rotation_results['single_set_lifetime_days']:.0f} days to {rotation_results['rotation_lifetime_days']:.0f} days")

Output:

Forest Fire Monitoring - Coverage Rotation Analysis
==================================================

Rotation Configuration:
  Number of sets: 3
  Duty cycle per sensor: 33.3%
  Average current: 6.67 mA

Lifetime Comparison:
  Without rotation: 5 days
  With rotation: 15 days
  Extension factor: 3.0x

Conclusion: Rotation extends battery life from 5 days to 15 days

413.4.2 Rotation Strategy Comparison

Strategy Lifetime Extension Complexity Robustness
No rotation (all active) 1x baseline Simple High redundancy
2-set rotation 1.9x Low Moderate redundancy
3-set rotation 2.8x Moderate Lower redundancy
4-set rotation 3.7x High Minimal redundancy

Key Insight: Adding more rotation sets provides diminishing returns. 3 sets typically optimal balance between lifetime extension and complexity.

This variant shows how coverage requirements affect network lifetime, helping designers balance monitoring quality with deployment longevity.

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D', 'fontSize': '11px'}}}%%
graph TB
    subgraph Coverage["COVERAGE LEVEL"]
        C1["1-Coverage<br/>Each point seen<br/>by 1 sensor"]
        C3["3-Coverage<br/>Each point seen<br/>by 3 sensors"]
        CK["k-Coverage<br/>Fault tolerance<br/>k-1 failures OK"]
    end

    subgraph Lifetime["NETWORK LIFETIME"]
        L1["2-5 years<br/>Minimal nodes<br/>No redundancy"]
        L3["6-18 months<br/>3x nodes<br/>No rotation"]
        LK["Extended via<br/>duty cycling<br/>2-5x improvement"]
    end

    subgraph Strategy["OPTIMIZATION"]
        S1["OGDC Rotation<br/>sqrt(3)*Rs spacing<br/>Activate subsets"]
        S2["Sleep Scheduling<br/>Round-robin<br/>Active sets"]
    end

    C1 --> L1
    C3 --> L3
    CK --> LK

    L3 --> S1
    LK --> S2

    style C1 fill:#16A085,stroke:#2C3E50,color:#fff
    style C3 fill:#E67E22,stroke:#2C3E50,color:#fff
    style CK fill:#2C3E50,stroke:#16A085,color:#fff
    style S1 fill:#E67E22,stroke:#2C3E50,color:#fff
    style S2 fill:#2C3E50,stroke:#16A085,color:#fff

Figure 413.3: Alternative view: Higher coverage levels require more sensors, reducing per-node duty cycle and theoretically extending lifetime. However, the relationship is non-linear. Intelligent rotation algorithms (OGDC, sleep scheduling) unlock the lifetime benefits of redundant deployments by ensuring balanced energy consumption across all nodes.

413.6 Summary

This chapter covered K-coverage and rotation scheduling for reliable sensor network deployments:

  • K-Coverage Requirements: Calculated sensor requirements for fault-tolerant deployments where each point is monitored by K sensors, using formula N = K x (A / pi x Rs squared) x alpha
  • Fault Tolerance Design: Demonstrated how 2-coverage tolerates single sensor failures while 3-coverage handles up to 2 simultaneous failures
  • Coverage Rotation: Developed scheduling algorithms to partition sensors into disjoint sets that rotate coverage duties, extending network lifetime by 2-4x
  • Lifetime Analysis: Quantified how 3-set rotation extends a 5-day network to 15 days through 33% duty cycling
  • Trade-off Optimization: Balanced coverage degree (higher K = more reliability) against energy consumption and network lifetime

413.7 Knowledge Check

Question: How does sleep scheduling improve coverage efficiency?

Explanation: B. If you have redundancy, you can duty-cycle equivalent โ€œcoverage setsโ€ to spread energy use across the fleet.

Correct: B) By rotating active sensors to maintain coverage while saving energy

Sleep scheduling allows redundant sensors to sleep while maintaining coverage. Active and sleeping sensors rotate roles, extending overall network lifetime.

Question: What is the trade-off between coverage degree and network lifetime?

Explanation: B. Higher k means more sensors active concurrently (plus more overlap traffic), increasing energy burn.

Correct: B) Higher coverage degree requires more active sensors, reducing lifetime

Higher k-coverage requires more sensors to be active simultaneously, consuming more energy and reducing overall network operational lifetime.

Question: In a 3-set rotation scheme where each set provides full coverage, what is the approximate lifetime extension factor compared to no rotation?

Explanation: With 3 disjoint coverage sets, each sensor is active 33% of the time. The lifetime extension is approximately 3x (slightly less due to sleep current consumption).

Correct: C) 2.8-3.0x

With 3 rotation sets, each sensor operates at 33% duty cycle. This theoretically triples lifetime, but sleep current consumption reduces the actual gain to approximately 2.8-3.0x.

413.8 Whatโ€™s Next

The next chapter explores Mobile Sensor Coverage Optimization, covering how mobile sensors (drones, robots, vehicles) can dynamically fill coverage gaps, reducing total sensor requirements while maintaining adaptive coverage.