Wireless sensor networks save energy by electing a few nodes per round as cluster heads. These are local hubs that collect readings from nearby nodes and relay them to a base station. Because being a hub drains a battery quickly, protocols rotate the role from round to round. Every widely used rotation rule is a heuristic, including coin-flip self-election, residual-energy thresholds, and swarm search. None of them says how far its schedule is from the best possible one. The theory of greedy approximation, which gives such guarantees for selecting good subsets, has been seen as a poor fit here: its proofs assume a fixed set of candidates with fixed value, while battery drain changes both every round.
This note argues that the mismatch is mostly a matter of formulation. Treat each pair (node, round) as a separate candidate. A schedule is then one subset of these pairs. A node's battery becomes a cap on how many of its own pairs can be chosen, and the per-round number of heads becomes a cap on each round's pairs. Both caps are matroid constraints. A matroid is a family of "allowed" subsets with an exchange property under which greedy selection keeps a constant-factor guarantee. Per-round energy savings, written as a facility-location score (each member benefits from its nearest head), is submodular, meaning it shows diminishing returns. A greedy planner over the whole rotation horizon therefore has a worst-case bound against the optimal multi-round schedule. The open question is whether that planning step buys real network lifetime over the obvious alternative, which is to re-run a good greedy election every round. The experiments are designed to answer it.
Core Claim
Let $V$ be the $N$ sensor nodes, $T$ the planning horizon in rounds, and $S_t \subseteq V$ the set of cluster heads in round $t$. The per-round value is the transmission energy that clustering saves relative to sending directly to the sink:
$$f_t(S_t) = \sum_{j \in V_t} \max\Big(0,\ \max_{i \in S_t} \big[d(j,\mathrm{sink})^{\alpha} - d(j,i)^{\alpha}\big]\Big),$$
Here $V_t$ is the set of nodes still alive in round $t$, $d$ is distance (or a measured link cost), and $\alpha \in [2,4]$ is the path-loss exponent. This is the same facility-location form that Coresets for Data-efficient Training of Machine Learning Models uses: CRAIG picks a representative training subset by greedily maximizing exactly this kind of objective. We reuse the method, not the application. The objective $F(\mathcal{S}) = \sum_t f_t(S_t)$ over the lifted ground set $V \times \{1,\dots,T\}$ is monotone and submodular, because it is a sum of submodular functions on disjoint blocks.
Two constraints define the feasible schedules. The first is $|S_t| \le k$ for every round $t$, with $k \approx \sqrt{N}$, which is the energy-optimal head count derived in Optimal Power Consumption Analysis of Two-level Hierarchical Model and Non-hierarchical Model. The second is $|\{t : i \in S_t\}| \le r_i$ for every node $i$, where $r_i = \lfloor (B_i - b_i)/c_i \rfloor$. In this formula, $B_i$ is node $i$'s battery, $c_i$ is an upper bound on one round of head duty, and $b_i$ is a reserve set aside for member traffic.
Each of the two constraints is a partition matroid. The classical result for greedy selection over the intersection of two matroids gives at least a $1/3$ approximation of the best feasible schedule. This changes the status of Gap 3 in the research file: role rotation does not break the guarantee. It becomes a constraint inside it.
The claim has two honest boundaries. First, the guarantee holds only for the capped-duty model. The upper bound $c_i$ is made valid by capping cluster membership, so that head cost cannot exceed what was budgeted. Second, member-side drain sits outside the proof. It is covered by the reserve $b_i$ and checked empirically. Rather than hiding these simplifications, the experiments measure how much they cost.
Relation to Prior Work
Three papers already connect greedy guarantees to sensor networks. The closest is Submodular Optimization with Routing Constraints. It handles non-additive path costs through a cost-benefit greedy rule for one agent on a flat topology, and it has no notion of depletion or rotation. We adopt its benefit-per-cost ratio as a variant of our planner, for the case where inter-head relay cost is charged to the schedule. Our new element is the multi-round, battery-capped structure.
Maximizing a Submodular Utility for Deadline Constrained Data Collection in Sensor Networks proves 1/2 and 1/3 greedy bounds for choosing which nodes report over a fixed tree. It explicitly leaves open forming the topology itself and ignores energy, and those are exactly the parts we optimize. Distributed Submodular Maximization motivates a decentralized version: its two-stage local-then-global greedy maps naturally onto members → heads → sink. However, it assumes free and reliable communication, so we treat it as an implementation route rather than the core contribution.
The heuristic protocols constrain and motivate the design. OEE-WCRD shows that combining residual energy with distance in head election roughly doubles lifetime over LEACH. That is strong evidence that energy-aware rotation matters, but it offers no guarantee. Its authors also concede that the work is validated only in idealized disk-model simulation, so we add measured-link experiments. Enhanced Pelican Optimization Algorithm for Cluster Head Selection in Heterogeneous Wireless Sensor Networks represents the metaheuristic line, which searches well but gives no bound.
Research Program
The work has three parts.
The first is the planner. We implement lazy greedy over the lifted ground set. It maintains a priority queue of marginal gains for (node, round) pairs and skips any pair whose node has used up its duty cap or whose round already has $k$ heads. Members are then assigned to their nearest head, subject to the membership cap that keeps $c_i$ valid. Inter-head relaying to the sink uses a minimum spanning tree in the base version. A cost-benefit variant instead scores each pair by marginal savings divided by marginal relay cost, following Submodular Optimization with Routing Constraints. For that variant we report the bi-criteria guarantee that its α-submodularity analysis supports, and we do not claim the clean 1/3.
The second part handles the fact that the planner's energy estimates will be wrong in practice. We deploy it in receding-horizon form. Every $H$ rounds, it re-plans the next $T$ rounds from measured residual batteries, so that estimation error does not accumulate.
The third part covers lifetime directly. The planner above maximizes total savings over a fixed horizon. Lifetime, the first round in which coverage falls below a threshold, is the quantity practitioners care about. We find it by binary search on $T$: for each candidate $T$, we ask whether a schedule exists that meets per-round coverage, solved with greedy submodular cover. We then report the resulting logarithmic-factor guarantee for that problem.
Baselines
The naive reference point is LEACH-style probabilistic self-election, in which each node becomes a head with probability $k/N$ per round, along with its SEP and TSEP variants for heterogeneous batteries. These are the standard comparisons in the literature. We include them so that our absolute numbers can be compared with published ones.
The strongest published heuristic in the file is OEE-WCRD. It elects heads using a per-round threshold built from the product of residual energy and neighbor distance. In its own simulation, OEE-WCRD reports nodes alive up to 6,500 rounds and 11.8×10^6 packets delivered. Under the same setup, LEACH, SEP, and TSEP reach zero alive nodes at 3,500, 4,500, and 5,000 rounds. Those figures come from the authors' own parameters, so we will reimplement OEE-WCRD in our simulator rather than compare across papers. Beating it means a statistically reliable gain in rounds-to-last-node-death and in packets delivered on the same seeds, energy model, and node layouts. We will also require at least parity on first-node death, so that we cannot win simply by sacrificing some nodes early.
The ablation that isolates the key ingredient is the most important baseline. Myopic greedy re-election runs the same facility-location greedy every round. Its gains are weighted by residual energy, and it excludes nodes below a reserve. Its code, objective, and $k$ are identical to ours, and the only difference is that it does not plan across rounds. If the planned schedule fails to beat it, the contribution shrinks to "a guarantee for a heuristic that already works." We will report that outcome as such.
We also include K-means geometric clustering with rotation to the most-charged node near each centroid. A metaheuristic (Pelican Optimization) gets the same wall-clock budget as our planner. Finally, an exact integer program over the lifted formulation, solved on small instances, supplies the true optimum for measuring the empirical approximation ratio. All methods share the energy model, $k=\sqrt{N}$, and seeds, and every tunable baseline receives the same hyperparameter search budget.
Why not just…?
Why not just re-run a good energy-weighted greedy election every round? This is the real threat, because with homogeneous batteries and uniform layouts myopic re-election may already be near-optimal. Planning should pay off when the deployment is uneven. One case is a node that alone covers a remote region and is drained early by myopic picks. Another is a set of nodes with very different batteries, where the timing of duty matters. We test both regimes explicitly. If the gap appears only in the adversarial cases, we will say that planning is insurance rather than a routine gain.
Why not just tune OEE-WCRD or LEACH thresholds? Tuned thresholds may match average lifetime on the layout they were tuned for. They give no bound, though, and their gains do not carry over when the energy model or layout shifts. The evidence that energy-distance balancing matters comes from OEE-WCRD itself. We tune its weights under the shared budget and then evaluate on held-out layouts and on link costs measured from real traces.
Why not just solve the integer program exactly? For a few dozen nodes and a short horizon, that is exactly what we do: it is the ground truth for measuring the ratio. The lifted problem has $NT$ binary variables, though, so exact solution stops being practical at realistic sizes. Re-planning every $H$ rounds needs something cheap enough for the base station to run repeatedly, and lazy greedy is.
Proposed Experiments
The simulation setting follows the OEE-WCRD-style rounds model, using first-order radio energy with $\alpha \in \{2, 4\}$, $N \in \{100, 400, 1600\}$, and both uniform and clustered layouts with homogeneous and two-tier batteries.
The first decisive check is the empirical approximation ratio against the integer program on small instances. We expect it to sit far above the worst-case 1/3. If it does not, the planner is not useful.
The second check compares the planned schedule with myopic re-election on lifetime metrics across the regimes above, with confidence intervals over 30 seeds.
For data fidelity, we replay readings from the Thermal Image Temperature dataset used in Novel Light Weight Compressed Data Aggregation using sparse measurements for IoT networks. We report reconstruction error at the sink as nodes die. That paper gives no scalar savings figure, so we have no prior number to beat and report our own. For sensing utility, we replay Beijing Air Quality readings. Here we compare against the published claim that cost-benefit greedy beats plain greedy, which Submodular Optimization with Routing Constraints reports without a scalar, so no reported numeric result was found on Lacuna for that benchmark.
The third check concerns robustness to physical links. We replace disk-model distances with noisy, asymmetric link costs and measure how fast the planner's lifetime advantage, and its ratio to the exact optimum, decays as the error in the $c_i$ estimates grows. We also test whether re-planning every $H$ rounds recovers the loss.
If time allows, we will run a small mote deployment of the kind used for LWCDA, to check that the re-planning messages do not cost more energy than the planning saves.
References
- Coresets for Data-efficient Training of Machine Learning Models
- Optimal Power Consumption Analysis of Two-level Hierarchical Model and Non-hierarchical Model
- Submodular Optimization with Routing Constraints
- Maximizing a submodular utility for deadline constrained data collection in sensor networks
- Distributed Submodular Maximization
- OEE-WCRD: Optimizing Energy Efficiency in Wireless Sensor Networks through Cluster Head Selection Using Residual Energy and Distance Metrics
- Enhanced Pelican Optimization Algorithm for Cluster Head Selection in Heterogeneous Wireless Sensor Networks
- Novel Light Weight Compressed Data Aggregation using sparse measurements for IoT networks