Wave Schedules Designed for Low-Rank Recovery

Battery-powered and energy-harvesting sensor networks save power by sleeping almost all the time and waking in short, coordinated bursts. One classic way to coordinate the bursts is wave scheduling, where groups of nodes spaced far enough apart that their radios cannot interfere wake together, so the network sweeps through "waves" of activity without collisions. Every sleep slot, though, is a reading that never gets taken. The usual repair is tensor completion: arrange the readings as a multi-way array (sensor × time-of-day × day) and fill the holes by assuming the array is approximately low-rank, meaning it can be written as a product of a few small factors. The two halves are designed separately. Schedulers choose wake times to avoid collisions and save energy. Completion methods are tested on holes that fall at random. Duty cycling does not make random holes. It makes rigid, repeating ones, and low-rank completion is known to fail badly on structured gaps.

This note proposes that the sleep schedule is a sampling design, and that we should pick it so the holes it creates are ones low-rank completion can fill. The specific claim is this. Within the hard constraints of a collision-free wave schedule, the assignment of wake phases to cells, and how those phases shift from one period to the next, decides whether completion succeeds or collapses. At equal energy and with collision freedom kept, a schedule chosen to maximize a computable recoverability score on its induced observation pattern should recover the field nearly as well as idealized random sampling. A schedule with fixed phases, which is the natural default, should fail.

Core Claim and Why the Default Fails

Wave scheduling and routing in sensor networks splits the network into grid cells and wakes cells spaced $g$ apart in periodic waves. Its pipelined variant repeats a local $g \times g$ pattern, and the paper reports order-of-magnitude energy savings over IEEE 802.11. In that design each cell wakes at a fixed offset within every period. Arrange the readings as a tensor indexed by cell, slot-within-period, and period. A fixed-offset schedule then observes each cell at exactly one slot index, forever. Whole fibers of the tensor, all periods for a given cell and slot, are never seen. No low-rank model can identify what happens inside a fiber that is never sampled. This is a sharper form of the failure reported in Large-Scale Traffic Data Imputation with Spatiotemporal Semantic Understanding. That paper evaluates on PeMS traffic data, and its LRTC-TNN tensor completion baseline degrades to an MAAPE (a bounded percentage error) of 69.45 under 90% non-random missingness. This is the evidence that motivates the gap.

The remedy keeps the wave structure, so collision freedom and zero contention are preserved. What changes is the phase each cell class receives in each period, and those phases are chosen against an explicit score. Let $\Omega \subset \{1..N\} \times \{1..P\} \times \{1..K\}$ be the set of observed (cell, slot, period) entries induced by a schedule $s$. Here $N$ is the number of cells, $P$ the number of slots per period, and $K$ the number of periods. For each unfolding $k$ of the tensor that a tensor-train solver uses, form the bipartite graph $B_k(\Omega)$ linking the row and column indices of every observed entry. Matrix completion from deterministic masks is known to work when this graph is well connected, roughly when its normalized adjacency has a large gap between its top two singular values. We therefore pick

$$ s^\star = \arg\max_{s \in \mathcal{W}_g(\rho)} \; \min_{k} \; \mathrm{gap}\big(B_k(\Omega(s))\big), $$

where $\mathcal{W}_g(\rho)$ is the set of collision-free wave schedules with spacing $g$ and per-node awake fraction $\rho$, and $\mathrm{gap}$ is one minus the ratio of the second to the first singular value. Taking the minimum over unfoldings means no single reshaping of the data is left with a disconnected sampling graph.

Low-rank tensor train (TT) completion, from Efficient tensor completion: Low-rank tensor train, supplies the solver. A tensor train writes a many-way array as a chain of small three-way pieces. That paper's main argument is that TT unfoldings are balanced, whereas Tucker-style unfoldings are "skinny" and limit recovery. It reports TMac-TT at RSE (relative squared error) 0.109 against 0.384 for Tucker-based TMac on Lenna with 90% missing pixels. Its Ket Augmentation, which reshapes a low-order array into a higher-order one, interacts directly with our score, because reshaping slot and period indices into more modes changes which bipartite graphs must be well connected.

Research Program

The first piece is analysis. We will characterize which wave schedules leave fibers or slices of the tensor unsampled. We will show that fixed-offset pipelined waves always do. We will also show that phase hopping across periods, with offsets drawn from residues of co-prime periods, gives every cell class every slot index within a bounded number of periods. That last idea extends the Prime-Co-Prime staggering in Amalgamated Intermittent Computing Systems (AICS). AICS uses co-prime duty periods to desynchronize energy-harvesting nodes for event coverage without any radio coordination, and reports a 69.7% cut in redundant active time. It never asks what those patterns mean for reconstructing the field, and we add that question.

The second piece is a schedule optimizer. The search space is the phase assignment per cell class per period, constrained to $\mathcal{W}_g(\rho)$. Because the gap score is cheap to evaluate on masks of this size, local search or simulated annealing over phase permutations is enough. Like the scheduler in The Time-Triggered Wireless Architecture (TTW), which builds static schedule tables offline with mixed-integer programming and runs them on FlockLab, the optimized schedule is computed offline and shipped as a short phase table or a seed. Nodes need only a shared clock, which the wave or TTW round structure already provides. The open question is whether a seed-generated pseudo-random hopping sequence already achieves near-optimal gap. If it does, the optimizer collapses to a one-line rule, and that would be a useful finding in itself.

The third piece is energy and latency accounting. Every schedule we compare is charged the same awake fraction $\rho$. Schedules that break wave structure are also charged for collisions and idle listening under the radio energy model used for wave scheduling and MAC comparisons in Wireless Sensor Networks:A case study for Energy Efficient Environmental Monitoring.

The scope is deliberately narrow. The claim matters when a sleeping node does not sense: intermittent or energy-harvesting devices, or high-rate sensing where keeping the microcontroller awake is the dominant cost. If sensing is cheap and decoupled from the radio, the problem largely disappears, and we treat that case as a baseline rather than hide it.

Baselines

The naive reference is the default pipelined wave schedule from Wave scheduling and routing in sensor networks, with fixed per-cell offsets, followed by the same TT completion solver. It has the same awake fraction, solver, rank budget and tuning grid as our method. We predict it fails in the fiber-missing way described above. Beating it by a wide margin is necessary but not sufficient.

The strongest scheduling competitor is idealized independent random wake-up at the same awake fraction, with collisions ignored when we measure reconstruction. This gives the mask the completion literature is most comfortable with, and it is the upper reference for recovery. It is not deployable as-is. Optimal Radius for Connectivity in Duty-Cycled Wireless Sensor Networks shows that random sleep forces a larger transmission radius than deterministic overlapping schedules for connectivity, and random access forfeits the collision freedom of waves. Our method beats this baseline in the sense that matters if it comes within a small margin of its reconstruction error, which we set in advance at 10% relative, while keeping zero collisions and the wave energy cost. If the gap is larger, the claim fails.

The prior-art scheduling competitor is AICS-style Prime-Co-Prime staggering, applied per cell without our score. This isolates whether co-prime structure alone is enough, or whether optimizing for recoverability adds anything.

The strongest completion competitor is GT-TDI from Large-Scale Traffic Data Imputation with Spatiotemporal Semantic Understanding, a graph-transformer imputer run server-side. On PeMS District 7 that paper reports MAAPE 7.18 at 90% non-random missingness and 6.52 at 90% random missingness, against 69.45 for LRTC-TNN in the non-random case. Those masks are not ours, so the numbers are a reference point rather than a direct comparison. We will run GT-TDI on our default-wave masks with the authors' configuration and a matched hyperparameter budget. The question is whether redesigning the schedule lets a lightweight TT solver reach error comparable to a heavy learned imputer that is fed the default schedule's data.

Two ablations isolate the key ingredient. In the first, the schedule is held fixed at $s^\star$ while the solver swaps TT completion for Tucker-based completion; this tests whether balanced unfoldings matter. In the second, the solver is held fixed while the schedule varies across fixed-phase, seeded pseudo-random hopping, Prime-Co-Prime and score-optimized. All solvers get the same rank search range and number of restarts.

Why not just…?

Why not just let nodes wake at random? Random masks are what completion handles best, and for reconstruction alone this is a real threat; it may simply win. The cost is in the network. Deterministic overlapping schedules reach connectivity at the minimum transmission radius while random sleep does not Optimal Radius for Connectivity in Duty-Cycled Wireless Sensor Networks, and uncoordinated access pays for collisions and idle listening that waves avoid Wave scheduling and routing in sensor networks. The experiments report reconstruction error and energy-including-collisions together. The proposal stands only if the wave-constrained schedule gets close to random's reconstruction at clearly lower network cost.

Why not just run a strong deep imputer on whatever the default schedule delivers? GT-TDI already handles non-random gaps well on PeMS. It needs semantic side information and pre-training, and it runs only on a server. More fundamentally, no imputer can recover a cell-slot fiber that is never observed, except by borrowing from correlated cells. The head-to-head on default-wave masks measures how much of the gap learning closes. If GT-TDI on default masks matches TT completion on optimized masks, schedule design adds little for well-instrumented networks with training data. Its value would then be limited to cold-start deployments, which we will report as such.

Why not just decouple sensing from the radio, sensing always and transmitting in waves? Where sensing is cheap and power is continuous, this is the right answer, and it makes the missing-data problem nearly vanish. We include it as an energy-matched baseline in which sensing energy is charged honestly. For intermittent nodes like the MSP430 swarms in Amalgamated Intermittent Computing Systems, a powered-down node cannot sense at all. The experiments sweep the ratio of sensing cost to radio cost to locate the crossover point where our approach stops mattering.

Why not just raise the duty cycle? Raising it trades battery life for coverage. Our comparisons hold the awake fraction fixed, and we also report the fraction the default schedule would need to match the optimized schedule's error. That number is the energy saved.

Proposed Experiments

The main testbed is trace-driven. We take complete ground-truth fields and impose the observation masks each schedule would produce. The fields are PeMS District 7 (1,740 sensors, 100 days, 10-minute intervals, as used by GT-TDI); the Populus tomentosa forestry multi-sensor series from L2: Accurate Forestry Time-Series Completion and Growth Factor Inference, restricted to its densely observed stretches; and the Dataport residential energy data used by Active Collaborative Sensing for Energy Breakdown. That last paper chooses which homes get sensors month by month using completion uncertainty, which is static placement. We make the analogous decision at the level of slot-by-slot sleep. For each dataset, sensors are mapped to grid cells by location, where location metadata exists, or by a fixed hash otherwise, with $g$ set from a disk interference model. Awake fractions range from 5% to 30%. Metrics are MAAPE and RMSE on held-out entries, broken down separately for entries lying in fibers that a schedule never observes. The network side reports energy per period, collisions, and end-to-end latency, using the radio model above. For a hardware sanity check we replay the chosen schedules as round tables on a FlockLab-scale deployment following The Time-Triggered Wireless Architecture, which reports roughly 30% energy savings for representative payload sizes. The goal there is to confirm that phase hopping adds no measurable synchronization or energy cost.

Three outcomes settle the claim. The first is whether default fixed-phase waves produce large error concentrated in unobserved fibers while hopping schedules do not. If not, the mechanism is wrong. The second is whether the gap score rank-orders schedules by actual reconstruction error across datasets and awake fractions, measured by rank correlation between score and error. If not, the optimizer has no foundation. The third is whether the score-optimized or seeded-hopping wave schedule lands within the preset 10% margin of idealized random wake at equal awake fraction, with zero collisions. If seeded hopping already matches the optimizer, the practical recommendation is the simple rule, and the contribution is the diagnosis plus the score that certifies it.