💻 computer science

Toward an ILP Approach of Temporal Coverage in Sensor Networks

This paper proposes and evaluates two Integer Linear Programming (ILP) approaches for orchestrating the activation and charging cycles of energy-neutral sensors to ensure continuous temporal and spatial coverage in outdoor monitoring networks, analyzing the trade-offs between implementation complexity, solving time, and solution optimality.

Original authors: Mohammed Salem MOUMNI, Lakhdar LOUKIL, Houssam-Eddine ZAHAF, Pierre-Emmanuel HLADIK

Published 2026-06-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammed Salem MOUMNI, Lakhdar LOUKIL, Houssam-Eddine ZAHAF, Pierre-Emmanuel HLADIK

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a team of security guards patrolling a large museum at night. Their job is to make sure every single exhibit (a "Point of Interest") is watched at all times. However, there's a catch: these guards don't have unlimited battery power. They have solar panels on their uniforms that charge them up, but they only charge slowly. When they are actively watching an exhibit, they burn energy faster than the solar panels can recharge them.

If a guard runs out of battery, they must stop watching and stand still in the sun to recharge. If they stand still, the exhibit they were watching is left unguarded. The big challenge is: How do you schedule these guards so that every exhibit is always watched, no guard ever runs out of battery, and the whole system can run forever?

This paper proposes a mathematical way to solve this puzzle using two different strategies, which the authors call NPA and FPA.

The Two Strategies

The authors use a method called Integer Linear Programming (ILP). Think of this as a super-smart calculator that tries billions of possible schedules to find the perfect one.

1. The "Strict Timer" Approach (Non-Preemptive Approach - NPA)

Imagine a guard who follows a very rigid rule: "Once I start watching, I must watch for exactly 10 minutes. Once I stop, I must recharge for exactly 20 minutes. I cannot stop early, and I cannot start watching until my battery is 100% full."

How it works: The guard switches between "Active" (watching) and "Passive" (charging) in big, unbreakable blocks of time.
The Good News: It's very easy to manage. The guards just need a simple timer. They don't need to make complex decisions on the fly.
The Bad News: It's very rigid. If one guard finishes their 10-minute shift but the next guard isn't ready to start yet, there might be a tiny gap where the exhibit is unguarded. Because the rules are so strict, this method often fails to find a solution when the energy situation is tight (like a cloudy day).

2. The "Flexible Manager" Approach (Full-Preemptive Approach - FPA)

Imagine a guard who is allowed to be much more flexible. "I can watch for 3 minutes, stop to recharge for 2 minutes, watch for 4 minutes, and then recharge again. I can start watching even if my battery isn't 100% full, as long as I have enough to last the next few minutes."

How it works: The guard can switch on and off as often as needed. The schedule is broken into tiny pieces, allowing the system to fill in gaps perfectly.
The Good News: It is much more likely to find a solution, even when energy is scarce. It can patch up tiny gaps that the "Strict Timer" approach misses.
The Bad News: It's complicated. The guards have to switch on and off constantly. This requires a lot of coordination and "synchronization," which can be messy and harder to implement in real life.

The Results: A Race Between Rigidity and Flexibility

The authors ran thousands of computer simulations to see which approach wins. Here is what they found:

Who finds a solution? The Flexible Manager (FPA) wins easily. When the energy situation gets tough (like when the guards are very hungry and the sun is weak), the Strict Timer (NPA) gives up and says, "It's impossible!" The Flexible Manager keeps trying until it finds a way to make it work.
Who is faster to calculate? The Flexible Manager (FPA) is also faster for the computer to solve. Even though it has more variables, the rigid rules of the Strict Timer actually make the math harder for the computer to navigate.
Who is smoother? The Strict Timer (NPA) wins here. Because it switches on and off less often, the guards have fewer "mode changes." This means less wear and tear and less coordination overhead. The Flexible Manager switches on and off so much that it might be too chaotic for real-world sensors to handle efficiently.

The Bottom Line

The paper concludes that if you need a solution that is guaranteed to work even in difficult energy conditions, the Flexible Manager (FPA) is the better choice. It is the "safety net" that ensures the museum never goes unguarded.

However, if you can guarantee that energy is plentiful and you want a simpler, smoother system with fewer switches, the Strict Timer (NPA) is a good option, provided the energy conditions aren't too harsh.

The authors suggest that the future might lie in a hybrid approach: a system that is mostly flexible but tries to group switches together to keep things simple, getting the best of both worlds. They also note that their current model assumes the energy source (like the sun or radio waves) is steady, and future work will look at what happens when the energy is unpredictable, like a sunny day turning cloudy.

Technical Summary: Toward an ILP Approach of Temporal Coverage in Sensor Networks

Problem Statement

The paper addresses the challenge of ensuring temporal coverage in outdoor sensor networks powered by energy harvesting. While spatial coverage (ensuring every Point of Interest, or POI, is monitored by at least one sensor) is a well-studied problem, maintaining continuous temporal coverage is difficult when sensors rely on limited energy sources that fluctuate or are insufficient to sustain continuous operation.

The specific problem context involves sensors where the energy consumption rate during the active state ( $c(S_j)$ ) exceeds the energy harvesting rate ( $h(S_j)$ ). Consequently, sensors cannot operate indefinitely without interruption. They must alternate between an active state (monitoring POIs, consuming net energy) and a passive state (harvesting energy to recharge). The core challenge is to orchestrate the activation and charging cycles of multiple sensors to guarantee that every POI is covered at all times, while respecting individual battery constraints and ensuring the schedule is sustainable over an infinite horizon.

Methodology

The authors propose a system model based on Integer Linear Programming (ILP) to generate feasible sensor schedules. The system consists of $m$ POIs and $n$ sensors, where each sensor has a fixed coverage set, a battery capacity, a consumption rate, and a harvesting rate. The authors assume a linear charging profile within a defined energy window $[e_{min}, e_{max}]$ and constant harvesting rates (targeting stable sources like RF).

Two distinct ILP formulations are developed to solve the scheduling problem:

Non-Preemptive Approach (NPA):
- Mechanism: Sensors follow strict switching rules based on battery levels. A sensor transitions from passive to active only when fully charged and remains active for a fixed duration until the battery reaches a lower threshold. State transitions are not allowed mid-cycle.
- Modeling: This approach abstracts energy dynamics into temporal constraints. It does not explicitly track instantaneous energy levels in the ILP; instead, it enforces feasibility by constraining the duration and ordering of passive and active intervals.
- Trade-off: This simplifies implementation (requiring only timers) and reduces the number of state switches but limits scheduling flexibility.
Fully Preemptive Approach (FPA):
- Mechanism: Sensors can switch states at any time, provided the battery level remains above a minimum threshold. State transitions are not bound to full charging/discharging cycles.
- Modeling: This approach explicitly tracks the energy level $e(S_i, t)$ at each discrete time step within the ILP. It includes constraints for energy accumulation, consumption, and the requirement that the battery level at the end of a hyperperiod must be at least equal to the initial level to ensure replayability.
- Trade-off: This offers greater flexibility to find feasible schedules under tight energy constraints but increases the complexity of the ILP and the number of required state switches (synchronization overhead).

Key Theoretical Foundations:

Hyperperiod: The schedule is designed to be cyclic, repeating over a computed hyperperiod $H$ .
Validity and Replayability: The authors establish conditions (Theorem 1) ensuring that the battery never depletes during the hyperperiod (validity) and that the energy state at the end of the cycle allows for infinite repetition (replayability/energy neutrality).
Feasibility Pre-filter: A lightweight check based on Lemma 3 is applied before solving the ILP to verify if the sum of the ratios of harvesting to consumption rates for sensors covering a POI is at least 1.

Key Contributions

Dual ILP Formulations: The paper presents two distinct ILP models (NPA and FPA) for the temporal coverage problem in energy-harvesting sensor networks.
Theoretical Proof of Dominance: The authors prove (Lemma 4 and Lemma 5) that the FPA approach dominates the NPA approach; any schedule feasible under NPA is also feasible under FPA, but FPA can find solutions in scenarios where NPA fails due to its lack of preemption.
Infinite Horizon Guarantee: The work demonstrates that the finite schedules produced by the ILP are valid over the system's potentially infinite lifetime by enforcing energy neutrality over the hyperperiod.
Discretization Analysis: The paper quantifies the approximation error introduced by discretizing continuous time in the FPA model (Lemma 6), bounding the error by half the consumption rate per time step.

Experimental Results

The authors evaluated both approaches using synthetic scenarios generated via a modified UUniFast algorithm, varying the inflation factor (the ratio of consumption to harvesting) from 1.2 to 6.

Feasibility: FPA consistently found feasible solutions for inflation factors up to 3.2, whereas NPA's feasibility dropped significantly as the inflation factor increased. FPA maintained high feasibility until the inflation factor approached 5, where energy constraints became theoretically impossible to satisfy.
Solving Time: NPA required significantly more computational time, often reaching the 480-second timeout limit as the problem became more constrained. FPA exhibited much faster convergence and remained computationally efficient even for difficult instances.
Synchronization Overhead: NPA produced schedules with very few state switches (low synchronization cost), resulting in smooth activation patterns. In contrast, FPA resulted in a significantly higher number of mode changes per time unit, implying higher implementation complexity and potential energy waste due to switching.
Discretization Sensitivity: As the time discretization step ( $\Delta t$ ) decreased, the solving time for NPA increased sharply, while FPA's solving time increased more gradually. NPA also required approximately twice as many binary decision variables as FPA due to auxiliary variables for block starts.

Significance and Claims

The paper claims to fill a gap in the literature by providing exact, optimal scheduling via ILP for sensors that both consume and harvest energy, specifically addressing the derivation of a finite, repeatable hyperperiod that guarantees continuous temporal coverage over an infinite horizon.

The authors position their work as a comparative analysis of two strategies:

FPA is presented as the robust solution for difficult energy environments, capable of finding feasible schedules where rigid approaches fail, albeit with higher synchronization costs.
NPA is presented as a practical alternative for scenarios where implementation simplicity and low switching overhead are prioritized over finding a solution in highly constrained energy conditions.

The paper concludes that while FPA outperforms NPA in terms of feasibility and solving time, NPA offers "better quality" solutions in terms of stability and lower synchronization overhead. The authors suggest that future work should explore hybrid methods to balance these trade-offs and extend the framework to stochastic energy harvesting rates (e.g., solar or wind) and real-world deployment traces.