A battery-powered sensor node that computes and then transmits under a deadline has two ways to save energy, and they compete for the same spare time. The processor can run slower when a task finishes early, which is dynamic voltage and frequency scaling (DVFS, meaning lowering clock speed and supply voltage to cut power). The radio, however, may need that same spare time for retransmissions when the wireless channel fades. A good controller decides jointly how fast to compute and when to spend radio slots, given the current channel state. Computing such a controller exactly requires dividing time into steps. A fine step grid gives exact results but produces too many states. A coarse grid is tractable, but it can silently change which deadlines are met.
We propose to separate "is this coarse grid safe?" from "what is the best controller?" and to answer the first question with randomized polynomial identity testing. This is the technique of deciding whether two algebraic expressions are identical by evaluating them at random points modulo a large prime, with a provably tiny chance of error. The joint processor–channel system on a given grid is a probabilistic automaton whose input letters are the controller's actions and observations. Two grids yield identical closed-loop behavior under every possible controller exactly when their automata are equivalent as weighted languages, and that equivalence reduces to polynomial identity testing. A coarse grid that passes the test can be used to synthesize the controller with no loss relative to the fine grid. A grid that fails produces a concrete counterexample trace, which indicates where the grid must be refined.
Core Claim
Consider a coarse time grid for the joint DVFS-and-retransmission problem. It can be certified as exactly equivalent to the fine grid for all controllers simultaneously, including history-dependent ones, in time roughly linear in the model's nonzero transitions. The certificate also survives re-tuning of deadlines, energy weights, and policies. Only a change in channel statistics or task timing forces re-certification, and at that point re-certification is cheap enough to run on reconfiguration instead of offline.
The "for all controllers" part follows from a factorization argument. Model each step as reading a letter $(a, o)$, where $a$ is the chosen frequency level and radio action and $o$ is the observed outcome: task done or not, packet acknowledged or not, and the energy quantum spent. The probability of a closed-loop trace is then the controller's probability of its actions multiplied by the automaton's weight on the word. If two automata assign equal weight to every word, every controller induces the same distribution over deadline outcomes and energy. Comparing a few scalar numbers, such as miss probability under one policy, cannot give this guarantee.
Research Program
The system model combines a DAG of computation tasks with an end-to-end deadline and a wireless transmission stage. The DAGs are taken from E3S and BOTS. The wireless stage is modeled as a two-state Markov (good/bad) fading channel, in the spirit of the unknown-Markov fading models of Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading Channels. Radio activity is grouped into periodic rounds, as in The Time-Triggered Wireless Architecture. The processor has 20 discrete frequency levels, following Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice. Task execution times are distributions truncated at the worst-case execution time. We use the dual typical/worst-case view of Precise Scheduling of DAG Tasks with Dynamic Power Management, which treats slack as the gap between the two estimates.
Candidate coarse grids come from the temporal discretization literature, used here as a proposal generator rather than a guarantee. Several papers prove that optimal decisions align with release dates and deadlines under deterministic timing: Throughput maximization in multiprocessor speed-scaling and Calibrations scheduling with arbitrary lengths and activation length show this, and the patrolling reduction of Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency turns continuous time windows into discrete visit cycles. None of these results survives random arrival times caused by retransmissions. We therefore start from event boundaries plus radio-round boundaries, add geometric $(1+\epsilon)$ refinement near the deadline as in A Fully Polynomial-Time Approximation Scheme for Speed Scaling with a Sleep State, and then test whether the result is exact.
The certification step reuses the method of Language Equivalence for Probabilistic Automata. That paper maps an automaton's language to a multivariate polynomial, checks it by randomized evaluation over sparse transition matrices in $O(n \cdot |M|)$ time, where $n$ is the number of states and $|M|$ the number of nonzero transitions, and extracts counterexample words cheaply. We apply it to the fine-grid and coarse-grid automata. Estimated channel and execution probabilities are rationals. Following Algorithmic Applications of Baur-Strassen's Theorem, arithmetic runs modulo a random prime near $2^{61}$, which keeps number sizes bounded. Since the polynomial's degree is on the order of the automaton size, the Schwartz–Zippel bound gives a per-check false-equivalence probability of about $(n_{\text{fine}} + n_{\text{coarse}})/p$. This is negligible, and repetition drives it lower. We follow Faster Generic Identification in Tree-Shaped Structural Causal Models in reusing evaluation points across the many related checks that arise during refinement. That paper proves such reuse remains sound and reports a 5,000x speedup over symbolic tools.
One concern raised by Differential Elimination for Dynamical Models via Projections does not arise here: mapping to a finite field can obscure real-valued constraints. Our inputs are already rational probabilities, and we only need exact equality, not stability. The one requirement is that probability denominators are nonzero modulo $p$, and the implementation checks this.
When a check fails, the counterexample word names the earliest step whose timing or channel outcome the coarse grid merges incorrectly. We split the coarse grid there and repeat, which amounts to counterexample-guided refinement. On the final certified grid, the controller is computed by dynamic programming and deployed as a lookup table, so each decision at runtime is a table read. Exactness also has a cost. A grid that is only approximately equivalent always fails the test, so the approach yields no approximate certificates. We will measure how often this forces grids back toward fine size.
Baselines
The naive reference point is a static worst-case design in the style of The Time-Triggered Wireless Architecture. It reserves a fixed number of retransmission rounds sized for the bad channel state and runs computation at the speed that meets the deadline under worst-case execution times. That paper reports approximately 30% radio energy reduction from grouping communication into rounds with sleep intervals, and MILP synthesis times of seconds to minutes on a laptop, on the 27-node FlockLab testbed. We re-implement its timing and energy models from the released artifact, The Time-Triggered Wireless Architecture (Artifact). The same task sets, channel statistics, and deadlines are used for every method. Beating this baseline means lower total energy at an equal or lower measured deadline-miss rate.
The strongest existing processor-side method is decoupled runtime slack reclamation. The processor reruns a fast DVFS solver whenever slack appears, and the radio independently retransmits until an acknowledgement or the deadline arrives. For the solver we use SPG-speed from Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice, which that paper reports runs in under 1 ms for 1,000-task graphs, against about 60 ms for CVX-speed and under 200 ms for the integer program. We also compare against the dual-estimate scheme of Precise Scheduling of DAG Tasks with Dynamic Power Management, which reports at least 29.2% power saving over MCFS_Li on BOTS. For joint compute-plus-fading energy under shared deadlines, no reported result was found on Lacuna, so these baselines must be run by us. They receive the same channel traces and the same frequency levels. Beating them means reducing energy or miss rate at matched settings, which is the effect the coupling should produce when fades consume the slack the processor had assumed.
The fine-grid dynamic program is the exactness upper bound. Our certified coarse grid must match its energy and miss probability exactly, up to floating-point reporting, while using fewer states and less synthesis time.
Two ablations isolate the certification ingredient. The first uses the boundary-point grid without any certification, deploying whatever it yields; this shows what the discretization theorems give on their own under stochastic arrivals. The second replaces randomized testing with deterministic equivalence checking, meaning Tzeng-style checking with QR decomposition, on the same automata. For certification cost, the strongest reported number is Kiefer et al.'s: on Herman's protocol with $N=15$, the randomized check took about 4 seconds against 93 seconds for the deterministic QR baseline, and it finished on Grade where deterministic tools timed out at 10 minutes.
Why not just…?
Why not just compare deadline-miss probability and expected energy on both grids? Doing so is a linear solve per policy and is cheaper than an equivalence check. It is a real alternative if the controller is fixed forever. It certifies nothing about the optimal controller on the coarse grid, though, because that controller is not known until the grid is trusted. It also says nothing once deadlines or energy weights are re-tuned. We will measure how often scalar agreement under a reference policy coexists with disagreement under the policy optimized on the coarse grid. If this almost never happens on realistic instances, the all-controllers guarantee is of mostly theoretical value, and we will report that.
Why not just minimize the fine automaton by probabilistic bisimulation? Bisimulation quotients are deterministic, exact, and fast, so this is the most serious threat. Bisimulation is strictly finer than trace equivalence, however. It refuses to merge time points whose futures differ only in branching structure, not in the distributions of observable traces. Whether that matters for timing grids is an empirical question that the experiments settle directly. For each instance we compare the certified coarse-grid size against the bisimulation quotient size. If the two are consistently similar, the randomized component adds little beyond counterexample-guided refinement, and the proposal should be reframed around bisimulation.
Why not just solve the fine grid, or re-solve a MILP online? The TTW MILP takes seconds to minutes, which rules out re-solving when channel statistics drift. The fine-grid dynamic program is exact but grows with the tick resolution times the number of channel and slack states. Our timing experiments measure the crossover point between them.
Why not just add a worst-case retransmission margin to a runtime DVFS solver? This combination is the decoupled baseline above. Its weakness is structural: the margin is either too small, causing misses in bad-channel periods, or too large, forfeiting the quadratic energy savings of stretching computation over slack. The joint controller removes this trade-off only if coupling actually occurs on the traces, and the experiments will show whether it does.
Proposed Experiments
Workloads are E3S graphs of about 10 tasks with tight deadlines, where Energy Minimization in DAG Scheduling on MPSoCs at Run-Time found APX-D-sched often failed; BOTS with 43 tasks; and GENOME graphs of 50 to 1,000 tasks for scaling. Each workload is followed by a transmission stage. Channel models include Gilbert–Elliott chains fitted to fading patterns in the style of Pattern A and Pattern B, run on the 2-link collocated and 5-link sparse topologies. We also include one 802.11-like contention model, sanity-checked against the 0.918914 minimum delivery probability within 10,000 µs reported by Probabilistic Model Checking of the IEEE 802.11 Wireless LAN Protocol. Radio energy and round timing come from the TTW artifact.
Metrics are total node energy, deadline-miss rate from 10^5 Monte Carlo runs per configuration, certified grid size relative to the fine grid and to the bisimulation quotient, certification and synthesis wall-clock time, and the number of refinement rounds.
Four checks decide whether the proposal succeeds. First, on every instance where our method certifies a grid, the controller synthesized on that grid must reproduce the fine-grid optimum's energy and miss rate; any mismatch beyond sampling noise would indicate an implementation error or a false certificate. Second, certified grids must be substantially smaller than both the fine grid and the bisimulation quotient on a meaningful fraction of instances; otherwise the bisimulation objection wins. Third, re-certification after a channel-statistics change must run fast enough to use on reconfiguration, on the order of the SPG-speed budget and not the TTW MILP's seconds to minutes. Fourth, under bad-channel stress the joint controller must reduce energy at a matched miss rate compared with decoupled slack reclamation; if the channel rarely consumes processor slack on realistic traces, the coupling is not worth the machinery.
References
- Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading Channels
- The Time-Triggered Wireless Architecture
- Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice
- Precise Scheduling of DAG Tasks with Dynamic Power Management
- Throughput maximization in multiprocessor speed-scaling
- Calibrations scheduling with arbitrary lengths and activation length
- Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
- A Fully Polynomial-Time Approximation Scheme for Speed Scaling with a Sleep State
- Language Equivalence for Probabilistic Automata
- Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter, and Matchings
- Faster Generic Identification in Tree-Shaped Structural Causal Models
- Differential Elimination for Dynamical Models via Projections with Applications to Structural Identifiability
- The Time-Triggered Wireless Architecture (Artifact)
- Probabilistic Model Checking of the IEEE 802.11 Wireless Local Area Network Protocol