Age-Optimal Target Wake Time: Provably Good Wake Schedules for Energy-Constrained Wi-Fi Status Updating

Age-Optimal Target Wake Time: Provably Good Wake Schedules for Energy-Constrained Wi-Fi Status Updating Haoyu Wang∗ , Bo Sheng∗ , Xiaoqian Zhang† ∗ University of Massachusetts Boston, Boston, MA, USA

{haoyu.wang001, bo.sheng}@umb.edu † University of Nebraska Omaha, Omaha, NE, USA

arXiv:2608.21596v1 [cs.NI] 21 Aug 2026

xiaoqianzhang@unomaha.edu

Abstract—Target Wake Time (TWT), introduced in IEEE 802.11ax, lets an access point schedule exactly when each station wakes, transmits, and dozes. Existing TWT schedulers optimize energy or throughput, treating information freshness at best as a constraint and offering no performance guarantees. We design the wake schedule itself for freshness: minimize the weighted average Age of Information (AoI) over stations subject to perstation energy budgets, where the decision variables are the TWT triples (wake interval, offset, service period duration). We derive a renewal-exact AoI model for TWT under per-SP block fading and validate it against packet-level 802.11ax simulation with ∼1% mean error. We show that, unlike preemptive scheduling, non-preemptive TWT packing can be infeasible at schedule density 1, and identify the granularity condition under which a small-first best-fit packer provably succeeds. Around this we build H ARMONIC -G REEDY, a scheduler combining a convex relaxation, anchor-optimized power-of-two rounding, and a bestof-uniform safeguard, and prove it is a constant-factor approximation: 4/ ln 2 ≈ 5.77 under a mild granularity assumption and 6/ ln 2 ≈ 8.66 unconditionally. We implement the complete system in ns-3 – a TWT wake/doze mechanism integrated with the power-save architecture, plus the scheduler – and show that it is the only scheduler that stays near a relaxation lower bound across all regimes: against a strong energy-greedy baseline it ties when per-station energy floors already pin the periods, and wins by 4–36% exactly where the schedule density is binding and must be redistributed by AoI weight or channel quality rather than by energy budget – the regime our analysis identifies. Index Terms—Age of Information, Target Wake Time, IEEE 802.11ax, scheduling, energy efficiency, ns-3

I. I NTRODUCTION Real-time monitoring applications – industrial sensing, health wearables, smart-building telemetry – send small periodic status updates over Wi-Fi while running on batteries. Two trends collide in such systems. On one hand, the relevant performance metric is not throughput or even delay, but the Age of Information (AoI) [1], [2]: the time elapsed since the generation of the freshest delivered update. On the other, the dominant energy cost is simply being awake: a station that wakes rarely is efficient but stale; one that wakes often is fresh but dies quickly. IEEE 802.11ax [3] introduced Target Wake Time (TWT) precisely to manage this trade-off mechanically: the AP and a

station agree on a periodic schedule of service periods (SPs) – a wake interval T , an offset ϕ, and an SP duration d – and the station dozes outside its SPs. TWT thus exposes, for the first time in mainstream Wi-Fi, the exact control surface that AoI theory wants to optimize: when each source is allowed to deliver. Yet existing TWT schedulers optimize energy or throughput, treat freshness at best as a constraint, and offer no guarantees (Section II). This paper designs the TWT schedule itself for freshness, with guarantees. Our contributions: Model (Sections III–IV): a renewal-exact expression for time-average and peak AoI of a TWT station under perSP block fading, including the per-wake overhead cw . A structural lemma shows that batching retransmission attempts within an SP is never beneficial without wake overhead; the per-wake cost cw is thus exactly what separates TWT schedule design from abstract sampling models. • Hardness structure (Section V): a three-station example with schedule density (the fraction of air time the SPs P reserve, i di /Ti ) exactly 1 that is infeasible under every placement – non-preemptive TWT packing fundamentally differs from preemptive utilization bounds (harmonic rate-monotonic is optimal at density 1 only because preemption can split service across gap copies). • Algorithm and guarantees (Sections VI–VII): H ARMONIC -G REEDY, combining a water-filling convex relaxation, power-of-two period rounding with an anchor chosen by a candidate-argmin rule (evaluate a small, provably sufficient set of grid anchors and keep the best), small-first best-fit packing of power-of-two-sized reservations, and a best-of-uniform safeguard. We prove a deterministic 4/ ln 2 ≈ 5.77 approximation under a mild granularity assumption, and 6/ ln 2 ≈ 8.66 unconditionally. The packing analysis gives a tight granularity threshold d ≤ t0 (1 − U ). • System (Section VIII): a complete ns-3 implementation – a TWT wake/doze mechanism integrated with the 802.11 power-save architecture, with SP-boundary queue •

gating and TSF-anchored offsets – validated against the analytical model with ∼1% mean error, plus five protocol findings about deploying TWT (e.g., doze announcements cannot be acknowledged over a faded channel; pending retransmissions must be gated or they erase the energy savings). • Evaluation (Section IX): against both a naive (equalinterval) and a strong (energy-greedy) baseline, plus a relaxation lower bound. We separate two effects – period diversity, which the energy-greedy baseline already captures, and AoI-weighting, which we isolate in uniformbudget binding-density regimes where only our scheduler wins (4–6.5% over both baselines, up to 36% at scale with mixed modulation rates), exactly where the theory predicts. II. R ELATED W ORK Age of Information. Since its introduction as a freshness metric [1], AoI has grown into a broad field spanning queueing, sampling, and estimation [2], [4], [5]. Foundational results characterize the freshness-optimal update policy for a single source [6], the effect of packet management and queue discipline [7]–[9], and AoI’s role in IoT [10]. AoI now also serves as a system-level metric in edge-AI applications – federated unlearning in mobile edge computing [11], digitaltwin healthcare [12] – which presuppose, rather than design, the delivery schedule beneath them. Variants such as the Age of Incorrect Information [13] refine the metric for estimation. Our renewal model (Sec. IV) specializes this machinery to the TWT service-period structure. AoI scheduling. Minimizing weighted AoI across many sources over a shared channel is the closest body of work. Centralized per-slot policies and their optimality were established for broadcast networks with reliable and unreliable links [14], [15] and with stochastic arrivals [16], [17]; the restless-bandit structure yields Whittle-index policies that are near-optimal and, in cases, asymptotically optimal [18]. These works schedule which source transmits in each slot under a centralized controller; we instead design periodic wake agreements fixed in advance, where a sleeping station is unreachable between its service periods – a constraint absent from slotby-slot models. A parallel line constrains energy explicitly – energy-harvesting sources [19], [20], retransmission/ARQ budgets [21], and distributed freshness optimization [22] – but optimizes transmission timing rather than a negotiated periodic wake schedule with a hard duty-cycle budget. Closest in spirit are sleep-wake AoI optimization for CSMA sensors [23], which tunes continuous wake rates under battery constraints but has no negotiated periodic structure, and ageagnostic cyclic schedulers [24], which optimize deterministic transmission patterns but model neither energy nor sleeping. A pull-based line measures freshness only when the monitor asks: the Query Age of Information [25] and Whittle-index policies that optimize age at query instants [26]. TWT is structurally dual: the delivery opportunities, not the queries,

occur at negotiated instants, and our objective remains the continuous-time average. TWT and Wi-Fi. TWT was introduced in IEEE 802.11ax to manage energy and contention [3], [27], [28], and is extended in Wi-Fi 7 (802.11be) – notably restricted TWT for latencysensitive traffic and multi-link operation [29], [30] – making schedule design increasingly central [31]. TASPER [32] schedules TWT SPs to maximize throughput and energy efficiency subject to AoI constraints, proves NP-hardness, and gives a heuristic without guarantees; timely-throughput TWT grouping maximizes deadline-met throughput via drift-pluspenalty [33]; experimental IIoT schedulers [34] respect AoI deadlines deterministically; and TWT mechanism implementations and measurement studies [35]–[37] provide the platform context. Single-device closed-form AoI analyses exist for the cellular sleep-mode analogue of TWT (DRX) [38] and, most recently, for the TWT mechanism itself [39] – performance analysis of given configurations, not schedule design across a station population, which is what we do here. To our knowledge no prior work makes AoI the objective of TWT schedule design or provides approximation guarantees. Periodic real-time scheduling. Our packing analysis connects to classical real-time theory. Rate-monotonic scheduling is optimal for preemptive periodic tasks [40], and harmonic task sets are schedulable up to utilization 1 – but only because preemption can split a job across the gaps left by higherrate tasks. TWT service periods are contiguous and nonpreemptive, which is exactly why our Proposition 2 shows density 1 can be infeasible. The relevant non-preemptive analogue is the pinwheel problem and distance-constrained scheduling [41]–[43], whose density thresholds and harmonic constructions inform our small-first best-fit packer; we adapt them to the AoI-weighted, energy-budgeted TWT setting. III. S YSTEM M ODEL N stations are associated with one AP. Station i holds a TWT agreement (Ti , ϕi , di ), where Ti is its wake interval (the time between consecutive wake-ups), ϕi its offset (the start of its first SP on the shared clock), and di its SP duration (the contiguous awake time per wake): the station wakes at times ϕi +kTi , k = 0, 1, . . . , stays awake for di , and dozes otherwise (Fig. 1; Table I collects notation). SPs of different stations must not overlap: keeping them disjoint is the scheduler’s responsibility, and it is precisely what designs contention away. Station i samples its source at the start of each SP (generateat-will) and transmits the update uplink within the SP. Channel. We model per-SP block fading: the channel coherence time exceeds the SP duration, so all transmission attempts within one SP share fate; an SP succeeds with probability pi ∈ (0, 1], independently across SPs. This is the regime in which the retransmission policy genuinely matters for AoI. At the opposite extreme – per-attempt i.i.d. loss – a few inSP retries drive the per-SP success probability to 1 and the channel dimension of the problem disappears; we verify this empirically in Section IX.

IV. S INGLE -S TATION S TRUCTURE

TABLE I N OTATION . (Ti , ϕi , di ) ρi ; Timin pi qi , ki , si cw,i δi wi ; ai Āi , Āpeak i U dmax t0 , level j ρ⋆ ; λ

TWT triple: wake interval, offset, SP duration duty-cycle budget; energy floor di /ρi per-SP success probability (block fading) per-attempt success, attempts per SP, attempt airtime per-wake overhead (ramp-up, synchronization) mean in-SP delivery delay AoI weight; cost coefficient wi (1/pi − 1/2) time-average and P peak AoI schedule density i di /Ti largest SP duration maxk dk harmonic grid anchor; grid period t0 2j scheduler density target; water-filling multiplier

T1 STA 1 doze (radio off)

d1 SP

STA 2

ϕ2 − ϕ1

T2 = 2T1

time

Successful SPs form a renewal process; the standard renewal-reward AoI argument [1], [2] then gives the following, which is the linchpin that turns TWT scheduling into a linear objective (Section V). Proposition 1 (TWT AoI). With wake interval T , per-SP success probability p, and mean in-SP delivery delay δ, 1 1 T , Āpeak = δ + . − Ā = δ + T p 2 p Sketch. Let G be the number of wake intervals between successive successful SPs. Since each SP succeeds independently with probability p, G is geometric on {1, 2, . . . }, so E[G] = 1/p and E[G2 ] = (2 − p)/p2 . The inter-delivery time is X = GT . After a successful delivery the AoI drops to the in-SP delay (mean δ) and then grows linearly until the next success, so each renewal cycle contributes area δX + X 2 /2. Dividing expected area by expected cycle length gives Ā = δ + E[X 2 ]/(2E[X]) = δ + T (1/p − 1/2), and the per-cycle peak δ + X averages to Āpeak = δ + E[X] = δ + T /p.

Fig. 1. TWT wake schedules: station i wakes for di every Ti at offset ϕi on a common (TSF-anchored) grid; the scheduler chooses the triples so that service periods are disjoint.

When the channel is per-attempt i.i.d. with success probability q and the SP holds k attempts, p = 1 − (1 − q)k and d = ks + cw with s the per-attempt airtime. Choosing k under the energy-tight period T = d/ρ reveals a clean dichotomy:

Energy. The station’s energy cost is its awake time: each wake costs a fixed overhead cw,i (radio ramp-up, synchronization) plus the SP airtime. Station i has a duty-cycle budget ρi : di /Ti ≤ ρi , equivalently Ti ≥ Timin := di /ρi . Objective. Let Ai (t) be the age of the freshest update from station i delivered P to the AP. We minimize the weighted timeaverage AoI i wi Āi ; Section VII notes that all results carry to weighted peak AoI. Scope. We deliberately study the cleanest setting that isolates schedule design: uplink status updates, generate-at-will sampling, scheduled non-overlapping SPs (so contention is designed away), and per-SP block fading. These assumptions are standard in AoI scheduling [14], [24] and matched to monitoring IoT, the dominant TWT use case. Three violations deserve comment. Stochastic arrivals: if updates arrive randomly rather than on demand, the wake schedule itself stays feasible unchanged, but the sampled update may already be stale at wake time; the objective acquires an arrival-age component that couples the stations only through the density constraint, turning the design into a constrained-MDP problem (Section X). Contention: traffic from non-TWT stations can collide with SPs; such losses enter the model through pi as long as they are independent across SPs, and where that cannot be assumed, 802.11be restricted TWT provides protected SPs. Intra-SP channel variation: block fading is the boundary case in which retransmission policy matters at all – under perattempt i.i.d. loss, in-SP retries drive the SP success probability to 1 and the problem degenerates gracefully (Section IV; verified empirically in Section IX). Downlink AoI (broadcast TWT, AP-side delivery) is likewise deferred to Section X.

Lemma 1 (batching needs overhead). With cw = 0, the single attempt k ∗ = 1 is optimal for every q: writing f (k) = (k + cw /s)(1/p(k) − 1/2), one computes f (2) − f (1) = q/(2(2 − q)) > 0. With cw > 0, k ∗ > 1 for sufficiently large cw /s at any fixed q. The per-wake overhead is thus load-bearing: it is exactly what distinguishes TWT schedule design from abstract sampling models, and we keep it in the model throughout. We validated Proposition 1 against packet-level 802.11ax simulation (Section IX): measured time-average AoI matches within 0.02% (p ≈ 1, two parameter sets) and within 0.6– 1.2% (seed-averaged) under per-SP block fading with p ∈ {0.8, 0.6, 0.4}, with measured duty cycles equal to d/T to four decimals. V. T HE M ULTI -S TATION P ROBLEM P By Proposition 1 the schedule cost is J(T ) = i ai Ti + C with ai := wi (1/pi − 1/2) and C a T -independent constant; the design problem is P min i ai Ti T,ϕ

Ti ≥ Timin . (1) P Disjointness implies the density bound U = i di /Ti ≤ 1, but the converse fails in a structural way: s.t. SPs pairwise disjoint,

Proposition 2 (density 1 can be unpackable). Let t0 be a base period and consider stations A1 : (T =t0 , d=t0 /2), A2 : (T =t0 , d=t0 /4), B: (T =2t0 , d=t0 /2), with U = 1. No placement of offsets makes the SPs disjoint.

must avoid A1 , A2 in both windows: needs free measure t0 /2 > t0 /4 B (dB = t0 /2) A1 0

A2

free

A1 t0

A2

free 2t0

Fig. 2. Proposition 2: at density 1, the per-window free set has measure t0 /4, but B’s contiguous SP needs t0 /2 of it – in every window, under every placement.

Proof. Both A1 and A2 have period t0 , so their SPs trace the same pattern in every base window [kt0 , (k+1)t0 ), and the free set S left in each window, of measure t0 /4, is likewise identical from window to window. Now place B: its SP is a contiguous interval of length t0 /2 ≤ t0 , so it meets at most two consecutive windows, splitting into (at worst) a suffix of one window and a prefix of the next. Each piece must avoid A1 and A2 , i.e. lie inside that window’s copy of S; and since S repeats identically, the two pieces occupy disjoint parts of the same per-window set. Their lengths sum to t0 /2, forcing |S| ≥ t0 /2 > t0 /4 – a contradiction (Fig. 2). Remark 1. Under preemptive scheduling the same instance is feasible (harmonic rate-monotonic is optimal at utilization 1): preemption splits B’s service across the two gap copies. TWT SPs are contiguous by design, so utilization intuition from real-time scheduling does not transfer. Any packing guarantee must involve granularity, which our analysis makes precise (Lemma 5). A second structural fact bounds every period from below: Lemma 2 (long SPs dominate periods). In any feasible schedule, Ti ≥ dmax := maxk dk for all i. Proof. Suppose some station A had TA < dB for a station B. The wake starts of A are spaced TA apart, so at least one falls strictly inside B’s SP of length dB , and the A-SP beginning there overlaps it. Hence every period is at least the longest SP duration. The following small instance is carried through Sections VI–VII to make each stage of the design concrete. Example 1 (running). Three stations with equal SPs di = 4 ms, uniform duty budgets ρi = 0.5 (energy floors Timin = 8 ms), reliable channels (pi = 1, so ai = wi /2), and weights w = (8, 2, 1), i.e. a = (4, 1, 12 ). At the floors the density would be 3 · 4/8 = 1.5 > 1: the air time the stations want exceeds what exists, so the density constraint binds and the periods must be differentiated – by weight, not by budget, since the budgets are identical: exactly the regime our evaluation isolates (Section IX). VI. T HE H ARMONIC -G REEDY S CHEDULER Algorithm 1 lists the scheduler. Line 1 sizes each station’s SP by the single-station dichotomy of Section IV and precomputes the cost coefficients ai . Line 2 solves the convex

Algorithm 1 H ARMONIC -G REEDY Require: per station i: weight wi , duty budget ρi , per-attempt success qi , attempt airtime si , wake overhead cw,i ; density target ρ⋆ Ensure: disjoint TWT triples (Ti , ϕi , di ) with di /Ti ≤ ρi 1: size SPs: ki ← energy-tight optimal attempts (Lemma 1); di ← ki si + cw,i ; pi ← 1 − (1 − qi )ki ; ai ← wi (1/pi − 12 ); Timin ← di /ρi p 2: relax: Ti ← max(Timin , dmax , λdi /ai ), bisecting λ ≥ 0 P until i di /Ti ≤ ρ⋆ (Lemma 3) 3: anchor and round: fold each Ti by powers of two into (Tmin /2, Tmin ], Tmin = mini TiP ; among these candidate anchors pick the t0 minimizing i ai ⌈Ti ⌉t0 , where ⌈·⌉t0 rounds up on the grid {t0 2j } (Corollary 1); set Ti ← ⌈Ti ⌉t0 4: re-expand: for stations with pi < 1, grow ki (hence di ) into the rounding slack, capped by ρi – extra attempts at fixed Ti are free for AoI 5: pack: in increasing-Ti order, place each ϕi by small-first best-fit (certified variant: dyadic reservations; practical variant: first-fit of the true di ; SectionPVII) P 6: safeguard: Tu ← max(maxi Timin , i di ); if i ai Tu beats the rounded cost, or packing failed, return the uniform schedule (offsets staggered back-to-back) instead

relaxation below; its water-filling solution shortens the periods of high-weight, poor-channel stations first. Line 3 snaps the ideal periods onto a power-of-two grid – this is what makes the later packing tractable – with the grid anchor chosen by the candidate-argmin rule analyzed in Corollary 1. Line 4 reinvests the slack that rounding up creates into extra transmission attempts. Line 5 places offsets, and line 6 guards against the octave-quantization pathology discussed at the end of this section. The relaxation of line 2 replaces disjointness by its density consequence: o nX X di J ∗ = min ai Ti : ≤ 1, Ti ≥ max(Timin , dmax ) , Ti i i (2) Every feasible schedule satisfies the constraints of (2) – disjoint SPs occupy at most the full timeline, and Lemma 2 supplies the dmax floor – so J ∗ lower-bounds (1). Lemma 3 (water-filling). (2)
is convex; its solution is Ti (λ) = p max Timin , dmax , λdi /ai with λ ≥ 0 the density multiplier (found by bisection). Sketch. The objective is linear and each di /Ti is convex on Ti > 0, so (2) is a convex program and KKT conditions are sufficient. For fixed λ the Lagrangian separates across stations; its i-th termpai Ti +λdi /Ti is strictly convex with unconstrained minimizer λdi /ai , so the coordinatewise minimizer over the min feasible ray is that value clipped Pat the floor max(Ti , dmax ) – exactly Ti (λ). The density i di /Ti (λ) is continuous and nonincreasing in λ, so bisection finds the smallest λ at which it meets the density budget (λ = 0 if the floors alone satisfy it),

which is complementary slackness. Full proof: appendix. Two implementation-driven design elements deserve emphasis, both discovered by simulation. First, the anchor matters: rounding to powers of two of an arbitrary base can double a period. Writing Tmin = mini Ti for the smallest relaxed period, we instead choose the anchor among the ideal periods folded into (Tmin /2, Tmin ] – each candidate makes one station’s rounding lossless – which is provably no worse than the average over random anchors (Corollary 1) and empirically much better. Second, the safeguard matters: when the relaxation’s period spread is sub-octave (all ideal periods within a factor 2), the harmonic grid cannot express the differentiation and rounding losses dominate. For example, ideal periods of 30 and 50 ms (ratio 1.67 < 2) round to the same power-of-two grid level, so the harmonic schedule cannot give the more important station a shorter period and merely pays the rounding cost; the safeguard then returns the uniform schedule instead. We call this the octave quantization effect and quantify it in Section IX. Example 2 (continued). On the instance of Example 1, waterfilling clamps station 1 to its floor and spreads the remaining density by weight: P T ∗ = (8, 13.7, 19.3) ms, density exactly 1, ∗ relaxed cost J = i ai Ti∗ = 55.3 (a lower bound). Folding T ∗ into (4, 8] gives the anchor candidates {8, 6.83, 4.83}; rounding up on each candidate grid costs {64.0, 81.9, 67.6}, so line 3 picks t0 = 8 and T = (8, 16, 32) ms – station 1’s rounding is lossless and the cost is 1.16× the relaxation bound. The uniform alternative Tu = max(8, 3·4) = 12 ms would cost 66.0 > 64.0, so the safeguard keeps the harmonic schedule. Packing in increasing-period order places ϕ = (0, 4, 12) ms, disjoint over the 32 ms hyperperiod. VII. A PPROXIMATION G UARANTEES The practical scheduler packs true SP durations at density 0.9. A worst-case certificate for that exact configuration would have to survive adversarial duration mixes; we instead analyze a deliberately conservative variant of Algorithm 1 and charge the difference to the constants. The analyzed variant differs in two ways. First, it runs the relaxation at a density target ρ⋆ (fixed to 1/4 in Theorem 1), leaving the packing stage guaranteed headroom. Second, it packs dyadic reservations: each station reserves the smallest grid divisor t0 /2m ≥ di and transmits only for di inside its reservation, so reservations consume schedule space but no energy. Packing is small-first bestfit (SF-BF): process stations by increasing period; place each into a minimum-size free block of sufficient size, carving from the left and returning the staircase remainder. The analysis then proceeds in three steps: a structural invariant on the free blocks SF-BF maintains (Lemma 4), a sufficient packing threshold (Lemma 5), and the end-to-end guarantees (Theorems 1 and 2, sharpened by the anchor rule of Corollary 1). Lemma 4 (count invariant). When SF-BF serves a request of size q from a chosen free block of size b, the staircase blocks it returns have sizes in [q, b) – sizes at which, by bestfit minimality of b, no free block currently exists. Consequently

new free blocks are only created at sizes whose count is zero, and at the start of level-j processing every size has at most 2j free blocks. Both bounds are tight. Lemma 5 (packing threshold). If every reservation satisfies P d′i ≤ t0 (1−U ) with U = i d′i /Ti , SF-BF places all stations. Conversely (cf. Proposition 2), a station of level ≥ 1 must satisfy d′ ≤ t0 (1 − U0 ) where U0 is the lower-level utilization: the threshold is tight up to the requesting station’s own density share. Proof sketch. Suppose a request of size q fails at level j. Every free block is then smaller than q, and since each of the sizes q/2, q/4, . . . carries at most 2j blocks (Lemma 4), the total free measure is below 2j q. On the other hand, the stations placed so far occupy at most a fraction U of the level-j window of length t0 2j , leaving free measure at least t0 2j (1 − U ) ≥ 2j q under the stated granularity – a contradiction. Full proofs are in the appendix, and all lemmas are additionally machine-checked on ∼3,000 randomized harmonic instances. Theorem 1. Under the granularity assumption di ≤ t0 /4, H ARMONIC -G REEDY (analysis variant, ρ⋆ = 1/4) returns a feasible schedule of cost at most 8 · OPT. Corollary 1 (candidate-argmin anchor). The rounded cost, as a function of the anchor phase θ ∈ [0, 1) (t0 = Tmin 2−θ ), is piecewise strictly decreasing with minima exactly at the folded candidates; hence the candidate-argmin anchor satP isfies mincand C ≤ Eθ [C] = (1/ ln 2) i ai Ti , improving Theorem 1 deterministically to 4/ ln 2 ≈ 5.77. Theorem 2 (unconditional). Without any granularity assumption, scaling the relaxation solution by s = 6 (which simultaneously enforces the density budget and, via Lemma 2, the long-SP margin t0 > 3dmax ) yields a 12-approximation, and 6/ ln 2 ≈ 8.66 with the candidate-argmin anchor. The constant 6 is optimal for this accounting. Example 3 (concluded). On Example 1 after rounding, U = 4/8 + 4/16 + 4/32 = 0.875, so Lemma 5 would require d ≤ t0 (1 − U ) = 1 ms; the instance violates the threshold (d = 4 ms) yet packs anyway – the condition is sufficient, not necessary, and the certified variant’s ρ⋆ = 1/4 exists precisely to guarantee it in the worst case. The achieved cost, 1.16× the relaxation bound, is typical of the gap between certificate and behavior: across every regime of Table III the practical variant lands within 1.05–1.25× the relaxation lower bound – itself unachievable in general – against the 5.77× worstcase certificate. The bound’s role is to exclude pathological instances, not to predict typical loss. Proposition 3 (peak AoI). All of the above holds verbatim for weighted peak AoI: by Proposition 1 the objective is again linear in T with coefficients apeak = wi /pi . i For N = 2 the problem admits an exact solution, with a structural twist:

Theorem 3 (exact N =2). Feasibility forces a rational period ratio T2 /T1 = p/q with T1 ≥ q(d1 + d2 ). For each q the cost J(r, q) = (a1 + a2 r) max(T1min , T2min /r, q(d1 +d2 )) is quasiconvex in r = p/q – strictly decreasing while the T2min /r term is active, then strictly increasing. Its integer-numerator optimum is therefore one of the two grid neighbors of the continuous minimizer, and q ranges over a finite, explicit set, yielding an exact O(Q) algorithm (verified against exhaustive search on 4,000 instances). Notably, non-integer ratios are strictly optimal on an open set of instances – both energy floors can bind only at a fractional ratio – so the harmonic restriction has a real price already at N = 2, precisely the rounding loss our analysis charges for. Full proof: appendix. VIII. I MPLEMENTATION IN NS -3 We implement the full system in ns-3.1 It comprises a Twt PowerSaveManager realizing individual implicit TWT as a subclass of the 802.11 power-save architecture, and the scheduler as a pluggable policy module. Three mechanism elements proved essential, each corresponding to a measured failure mode: (i) deferral, not wake-on-traffic: channel access requested outside an SP must not wake the radio – queued frames contend automatically at the next SP start; (ii) SPboundary queue gating: without it, pending retransmissions keep the station awake until the fade lifts (we measured a retry storm of 1.5 × 105 transmissions), erasing the energy savings. We gate by freezing rather than dropping: at SP end we mark the station’s per-access-category EDCA queues blocked through ns-3’s existing power-save block-reason mechanism (the same hook the standard PS manager uses), and release it at the next SP start. Blocked frames are not dequeued for transmission, so their sequence numbers, retry counts, and Block-Ack state are preserved untouched; the deferred updates simply ride the next SP. This restores the exact k-attempts-perSP structure the model assumes and keeps the PHY in sleep between SPs; (iii) TSF-anchored offsets: per-station offsets must live on a common absolute time grid – otherwise the computed disjointness has no shared reference and is silently lost. We further document protocol findings on TWT deployment: beacon-loss monitoring disassociates dozing stations; downlink frames (including ADDBA responses) buffered for a dozing station deadlock the uplink through asymmetric Block Ack state; and doze announcements are best-effort by nature – a PM indication cannot be acknowledged over a channel the AP cannot hear, which is precisely why TWT is schedulebased. Scheduler cost. The scheduler runs on the AP once per (re)association or renegotiation epoch, not per frame. Lines 1– 2 of Algorithm 1 are O(N ) (the bisection runs a fixed number of iterations to machine precision), anchor selection evaluates N candidate grids at O(N ) each, and packing touches each SP 1 Code, data, and a reproduction guide are available at https://github.com/ Haoyu2/age-optimal-twt – an ns-3 contrib module plus the src/wifi mechanism patch, with the raw sweep results, released to support artifact evaluation.

instance of the hyperperiod. Measured on a single commodityVM core (median of 20 runs, heterogeneous synthetic workloads): 0.7 ms at N = 64 stations, 9 ms at N = 256, and 43 ms at N = 512 – negligible against association signaling. The runtime state is one triple per station plus the per-AC gating flags, and the data path adds only the two O(1) queue gate/ungate operations per SP boundary, reusing the existing power-save block-reason hook. IX. E VALUATION Setup. All experiments use 802.11ax at 2.4 GHz over a 20 MHz channel (HeMcs3 unless stated otherwise), with 10– 50 stations of heterogeneous weights, duty budgets, and perSP fading. Each station delivers one status update per wake interval, and the AP integrates AoI exactly, event by event. Runs last 300 s over 10 seeds; we report 95% confidence intervals. Baselines. We compare H ARMONIC -G REEDY against two baselines. Equal-interval gives all stations a single common period (the naive TWT schedule). Energy-greedy is a strong heuristic in the spirit of energy-efficiency-first TWT schedulers such as TASPER [32]: it gives each station its shortest budget-feasible period max(Timin , dmax ), uniformly stretches to feasibility if overbooked, and reuses our rounding, packing and safeguard. It is period-diverse but AoI-weight-unaware, so it isolates the value of our weighted period assignment: any margin of H ARMONIC -G REEDY over Energy-greedy is attributable to that step alone. The two baselines let us separate two questions – does period diversity help (Energy-greedy vs. Equal-interval), and does AoI-weighting help beyond it (H ARMONIC -G REEDY vs. Energy-greedy). Slot-based AoI policies (max-weight, Whittle index [14], [18]) are not directly comparable: they assume the scheduler can reach any station in any slot, whereas a dozing TWT station is unreachable between its negotiated SPs, and re-deriving index policies over wake agreements is the stochastic-arrivals extension of Section X. The relaxation lower bound plays the comparison role instead: it bounds the cost of every feasible TWT schedule – hence of any AoI policy adapted to TWT – and H ARMONIC G REEDY stays within 5–25% of it below. Energy–freshness frontier. Figure 3 sweeps the duty-cycle budgets (8× weight skew): the schedulers trace the AoI– energy trade-off, with H ARMONIC -G REEDY dominating in the energy-constrained region where ideal-period spread exceeds an octave and coinciding with the baseline where the safeguard detects collapse. Model validation. (Fig. 4, Table II) Across the loss grid e ∈ {0, 0.1, . . . , 0.6}, measured AoI tracks δ + T (1/p − 1/2) with mean error ∼1%: 0.003% at p = 1 on every seed, and a worst single seed of 4.4% at p=0.4 – consistent with the geometric-tail variance of a 300 s run. The measured renewal components E[G] and E[G2 ]/2E[G] are within 1% of their predicted values T /p and T (1/p − 1/2). Period diversity vs. AoI-weighting. (Fig. 5, Table III) The two effects separate cleanly by regime. When budgets are heterogeneous, the per-station energy floors Timin = di /ρi

Equal-interval Harmonic-Greedy

70 60 50 40 30 20

Equal-interval

Energy-greedy

Harmonic-Greedy

50 40 30 20 10 0

0.02 0.04 0.06 0.08 0.10 mean station duty cycle (awake fraction)

Fig. 3. Weighted mean AoI vs. mean duty cycle across energy budgets (8× weight skew, 10 stations, 5 seeds).

model: δ + T(1/p − 1/2)

275 time-average AoI [ms]

60 weighted mean AoI [ms]

weighted mean AoI [ms]

80

measured (ns-3)

250 225 200 175 150 125 0.0

0.1 0.2 0.3 0.4 0.5 per-SP loss probability e (p = 1 − e)

0.6

Fig. 4. Single-station validation: measured time-average AoI (3 seeds, 95% CI) vs the renewal model, across per-SP loss probabilities (T =100 ms, d=8 ms).

already pin the periods, so “minimize every period then pack” is near-optimal: Energy-greedy captures essentially the whole gain over equal-interval and H ARMONIC -G REEDY only matches it (het-budget skew: 18.8 vs 19.1 ms, both vs 20.9 for equal-interval; fading+skew similar). We report this plainly – period diversity, not AoI-weighting, drives those gains, and the LB column confirms both schedulers already sit near the optimum there. When budgets are uniform, Energy-greedy collapses to equal-interval (identical floors give identical periods), and only the AoI-weighted assignment redistributes the binding schedule density toward the stations that matter: under uniform budgets with binding density, H ARMONIC -G REEDY wins 6.5% with weight skew (16.0 vs 17.2 ms) and 4.3% with skew plus fading – the latter via the channel-aware coefficient ai ∝ 1/pi . This is the regime that isolates the paper’s contribution. Weighted peak AoI tracks the same pattern (Proposition 3); duty cycles equal di /Ti to four decimals and SPs never overlap in all runs. Near-optimality. The LB column of Table III is the re-

het-budget skew

het-budget fade+skew

uniform skew

uniform fade+skew

Fig. 5. Weighted mean AoI by regime (10 seeds, 95% CI). With heterogeneous budgets (left) the strong energy-greedy baseline already matches H ARMONIC -G REEDY; with uniform budgets and binding density (right) it collapses to equal-interval and only AoI-weighting wins.

laxation optimum – a lower bound on any feasible schedule. H ARMONIC -G REEDY is the only scheduler that stays close to LB in every regime; Energy-greedy is near-LB when energy floors pin the periods but drifts away once the binding density must be redistributed by weight or channel rather than by budget. The residual gap to LB is the price of harmonic rounding and contiguous (non-preemptive) packing, which Proposition 2 shows is unavoidable in general. Scaling and decomposition. (Fig. 7, Fig. 6) The pipeline runs cleanly to N = 50 stations (exact duty cycles, zero SP overlap, predictions within 2%). Heterogeneous SP sizes – alternating HeMcs0/HeMcs7, 700-byte updates, airtimes differing ∼3× – give the cleanest decomposition of the two effects at scale (3 seeds, CIs within 0.1 ms). At N =50: equalinterval 38.5 ms; Energy-greedy 29.5 ms (a 23% gain from period diversity alone, as fast stations need not wait for slow ones); and H ARMONIC -G REEDY 24.6 ms (a further 17% from AoI-weighting, for 36% over equal-interval). Both ingredients contribute and H ARMONIC -G REEDY beats the strong baseline outright here, because diverse airtimes create both period diversity and a binding density that AoI-weighting can exploit. (N =20 shows the same split: 16.8 → 13.3 → 11.2 ms.) Certified vs. practical variant. H ARMONIC -G REEDY has two configurations that share the relaxation, anchor rule, and safeguard but differ in the packing stage (Sec. VI). The certified variant (dyadic reservations, ρ⋆ =1/4) is the one Theorems 1–2 bound; the practical variant (ρ⋆ =0.9, firstfit of true SP durations) is the one that produces the gains above. The conservative ρ⋆ =1/4 is forced by the two factorof-two losses the worst-case packing analysis must absorb in series: rounding each SP duration up to a dyadic reservation can double the schedule density, and the packing threshold (Lemma 5) admits a request only when d′ ≤ t0 (1 − U ), which the count invariant satisfies for U ≤ 1/2; starting from ρ⋆ =1/4 leaves exactly the headroom for both. The practical variant instead packs the true SP durations greedily, so neither loss applies and density 0.9 is feasible – but it has

weighted mean AoI [ms]

40

TABLE II S INGLE - STATION MODEL VALIDATION ( SUMMARY ).

Equal-interval Energy-greedy Harmonic-Greedy

30

Regime p ≈ 1, T =100/8 ms p ≈ 1, T =50/4 ms block fading p=0.8/0.6/0.4

Predicted

Error

δ + T /2 δ + T /2 δ + T (1/p − 1/2)

0.016% 0.065% ≤ 1.2% (mean)

20

TABLE III W EIGHTED MEAN AO I ( MS ; MEAN ± 95% CI OVER 10 SEEDS ), 10 STATIONS , 300 S . E QUAL = EQUAL - INTERVAL , EG = ENERGY- GREEDY ( STRONG BASELINE ), H-G = OURS , LB = RELAXATION LOWER BOUND ( UNACHIEVABLE ). T OP : HETEROGENEOUS BUDGETS – EG ALREADY NEAR - OPTIMAL , H-G MATCHES . B OTTOM : UNIFORM BUDGETS , BINDING DENSITY – EG COLLAPSES TO E QUAL , ONLY H-G (AO I- WEIGHTING ) WINS .

10

0

N = 20

N = 50

Fig. 6. Heterogeneous modulation rates (HeMcs0/HeMcs7 alternating, 700byte updates, 8× weight skew, 3 seeds): the gain decomposes into period diversity (energy-greedy over equal-interval) and AoI-weighting (H ARMONIC G REEDY over energy-greedy); 36% total at N =50.

Regime

Equal

EG

H-G

LB

het. budget, skew het. budget, fade+skew

20.9 51.3

19.1 45.1

18.8 44.7

15.8 35.7

unif. budget, skew unif. budget, fade+skew

17.2 41.6

17.2 41.6

16.0 39.8

15.2 35.9

weighted mean AoI [ms]

80 Equal-interval Energy-greedy Harmonic-Greedy

70 60 50 40 30 20 10

20 30 40 number of stations N

50

Fig. 7. Scaling with the number of stations (8× weight skew, heterogeneous budgets, 3 seeds): all three schedulers track closely once the schedule is capacity-bound (energy floors pin the periods).

no worst-case certificate. The two are thus not interchangeable: the theorem certifies the template (relaxation, anchor rule, packing, safeguard), while the high-density practical variant is what we evaluate throughout. Under its conservative budget the certified variant’s safeguard returns the uniform schedule in the heterogeneous-budget regimes, so it tracks equal-interval there rather than the practical variant; closing this gap – a tighter packing analysis that certifies a density target near 0.9 – is open (Sec. X). X. C ONCLUSION TWT turns freshness-versus-energy into a schedule design problem. We formulated it with AoI as the objective, derived a renewal-exact model validated at the packet level, exposed the non-preemptive structure that separates TWT packing from classical utilization bounds, and built H ARMONIC -G REEDY – to our knowledge the first TWT scheduler with approximation

guarantees – together with an exact N =2 solution and an open ns-3 implementation. For practitioners, the evaluation reads as a regime map. When per-station energy floors pin the periods, energy-first scheduling is already near-optimal and AoI-weighting adds nothing. When the schedule density binds under uniform budgets or mixed modulation rates, AoI-weighted assignment is the only policy that redistributes air time toward the stations that matter, worth 4–36%. Four directions remain open. Tighter packing certificates: the certified ρ⋆ =1/4 is conservative only because the worstcase analysis absorbs two compounding factor-of-two losses in series – dyadic duration rounding can double the density, and the non-preemptive threshold (a consequence of the density-1 infeasibility of Proposition 2) admits requests only up to half the window; the practical ρ⋆ =0.9 variant never triggers either worst case, so an amortized packing argument would likely certify a density target near 0.9 – the single highest-leverage next step. Stochastic arrivals: index policies over wake agreements, with asymptotic-optimality machinery. Exact solutions beyond N =2. Downlink AoI: broadcast TWT with AP-side schedule-aware delivery. R EFERENCES [1] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in Proc. IEEE INFOCOM, 2012. [2] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, 2021. [3] IEEE, “IEEE standard 802.11ax-2021: Enhancements for high-efficiency WLAN,” IEEE Std 802.11ax-2021, 2021. [4] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” Foundations and Trends in Networking, vol. 12, no. 3, 2017. [5] B. Wu, J. Huang, and S. Yu, ““X of Information” continuum: A survey on AI-driven multi-dimensional metrics for next-generation networked systems,” IEEE Communications Surveys & Tutorials, vol. 28, pp. 5307– 5344, 2026.

[6] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” IEEE Transactions on Information Theory, vol. 63, no. 11, 2017. [7] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” IEEE Transactions on Information Theory, vol. 62, no. 4, 2016. [8] A. M. Bedewy, Y. Sun, and N. B. Shroff, “Minimizing the age of information through queues,” IEEE Transactions on Information Theory, vol. 65, no. 8, 2019. [9] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” IEEE Transactions on Information Theory, vol. 65, no. 3, 2019. [10] M. A. Abd-Elmagid, N. Pappas, and H. S. Dhillon, “On the role of age of information in the internet of things,” IEEE Communications Magazine, vol. 57, no. 12, 2019. [11] Z. Ding, B. Wu, and J. Huang, “SCALE: Sensitivity-aware federated unlearning with information freshness optimization for mobile edge computing,” in Proc. IEEE International Conference on Distributed Computing Systems (ICDCS), 2026, pp. 1476–1486. [12] B. Wu, J. Huang, and Q. Duan, “Real-time intelligent healthcare enabled by federated digital twins with AoI optimization,” IEEE Network, vol. 40, no. 2, pp. 184–191, 2026. [13] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” IEEE/ACM Transactions on Networking, vol. 28, no. 5, 2020. [14] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” IEEE/ACM Transactions on Networking, vol. 26, no. 6, 2018. [15] R. Talak, S. Karaman, and E. Modiano, “Optimizing information freshness in wireless networks under general interference constraints,” IEEE/ACM Transactions on Networking, vol. 28, no. 1, 2020. [16] Y.-P. Hsu, E. Modiano, and L. Duan, “Scheduling algorithms for minimizing age of information in wireless broadcast networks with random arrivals,” IEEE Transactions on Mobile Computing, vol. 19, no. 12, 2020. [17] I. Kadota and E. Modiano, “Minimizing the age of information in wireless networks with stochastic arrivals,” IEEE Transactions on Mobile Computing, vol. 20, no. 3, 2021. [18] V. Tripathi and E. Modiano, “A whittle index approach to minimizing functions of age of information,” IEEE/ACM Transactions on Networking, 2024, dOI 10.1109/TNET.2024.3452006. [19] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in Proc. IEEE Int. Symp. Information Theory (ISIT), 2015. [20] M. A. Abd-Elmagid and H. S. Dhillon, “Average peak age-ofinformation minimization in UAV-assisted IoT networks,” IEEE Transactions on Vehicular Technology, vol. 68, no. 2, 2019. [21] E. T. Ceran, D. Gündüz, and A. György, “Average age of information with hybrid ARQ under a resource constraint,” IEEE Transactions on Wireless Communications, vol. 18, no. 3, 2019. [22] R. Talak, S. Karaman, and E. Modiano, “Distributed scheduling algorithms for optimizing information freshness in wireless networks,” in Proc. IEEE SPAWC, 2018. [23] A. M. Bedewy, Y. Sun, R. Singh, and N. B. Shroff, “Optimizing information freshness using low-power status updates via sleep-wake scheduling,” in Proc. ACM MobiHoc, 2020. [24] E. O. Gamgam, N. Akar, and S. Ulukus, “Minimizing age of information with generate-at-will status updates and age-agnostic cyclic scheduling,” arXiv preprint arXiv:2311.18791, 2023. [25] F. Chiariotti, J. Holm, A. E. Kalør, B. Soret, S. K. Jensen, T. B. Pedersen, and P. Popovski, “Query age of information: Freshness in pull-based communication,” IEEE Transactions on Communications, vol. 70, no. 3, pp. 1606–1622, 2022. [26] J. Liu and H. Chen, “Optimizing AoI at query in multiuser wireless uplink networks: A Whittle index approach,” arXiv preprint arXiv:2411.02108, 2024. [27] B. Bellalta, “IEEE 802.11ax: High-efficiency WLANs,” IEEE Wireless Communications, vol. 23, no. 1, 2016. [28] E. Khorov, A. Kiryanov, A. Lyakhov, and G. Bianchi, “A tutorial on IEEE 802.11ax high efficiency WLANs,” IEEE Communications Surveys & Tutorials, vol. 21, no. 1, 2019. [29] D. López-Pérez, A. Garcia-Rodriguez, L. Galati-Giordano, M. Kasslin, and K. Doppler, “IEEE 802.11be extremely high throughput: The next

generation of Wi-Fi technology beyond 802.11ax,” IEEE Communications Magazine, vol. 57, no. 9, 2019. [30] A. Garcia-Rodriguez, D. López-Pérez, L. Galati-Giordano, and G. Geraci, “IEEE 802.11be: Wi-Fi 7 strikes back,” IEEE Communications Magazine, vol. 59, no. 4, 2021. [31] M. Yang, B. Li, and Z. Yan, “Target wake time in IEEE 802.11 WLANs: Survey, challenges, and opportunities,” Computer Communications, 2025. [32] F. Busacca, C. Puligheddu, F. Raviglione, R. Rusca, C. Casetti, C. F. Chiasserini, and S. Palazzo, “Target wake time scheduling for timesensitive and energy-efficient Wi-Fi networks,” IEEE Transactions on Mobile Computing, vol. 25, no. 3, pp. 3469–3487, 2026. [33] R. Roy, R. V. Bhat, P. Hathi, N. Akhtar, and N. M. Balasubramanya, “Maximization of timely throughput with target wake time in IEEE 802.11ax,” in Proc. IEEE International Conference on Communications (ICC), 2023, pp. 647–652. [34] G. Rajendran and S. Agnihotri, “Deterministic scheduling over Wi-Fi 6 using target wake time: An experimental approach,” arXiv preprint arXiv:2505.00447, 2025. [35] S. K. Venkateswaran et al., “IEEE 802.11ax target wake time: Design and performance analysis in ns-3,” in Proc. Workshop on ns-3 (WNS3), 2024, doi:10.1145/3659111.3659115. [36] E. Mozaffariahrar, M. Menth, and S. Avallone, “Implementation and evaluation of IEEE 802.11ax target wake time feature in ns-3,” in Proc. Workshop on ns-3 (WNS3), 2024. [37] M. Nurchis and B. Bellalta, “Target wake time: Scheduled access in IEEE 802.11ax WLANs,” IEEE Wireless Communications, vol. 26, no. 2, 2019. [38] H.-C. Lin, K.-H. Lin, and H.-Y. Wei, “Age of information for powersaving devices with DRX mechanism,” in Proc. IEEE International Conference on Communications (ICC), 2023, pp. 3234–3239. [39] P.-H. Ting, C.-W. Tsai, W.-D. Shen, and H.-Y. Wei, “Information freshness and energy efficiency tradeoffs in IEEE 802.11: Age of information performance analysis of target wake time mechanism,” IEEE Transactions on Green Communications and Networking, vol. 10, pp. 2778–2788, 2026. [40] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” Journal of the ACM, vol. 20, no. 1, pp. 46–61, 1973. [41] R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel, “The pinwheel: A real-time scheduling problem,” in Proc. Hawaii Int. Conf. System Sciences (HICSS), 1989. [42] C.-C. Han and K.-J. Lin, “Scheduling distance-constrained real-time tasks,” in Proc. IEEE Real-Time Systems Symposium (RTSS), 1992. [43] M. Y. Chan and F. Chin, “General schedulers for the pinwheel problem based on double-integer reduction,” IEEE Transactions on Computers, vol. 41, no. 6, 1992.

A PPENDIX Fix a unit u > 0 with t0 = 2L u. A block of size s = 2k u is an interval [rs, (r+1)s), r ∈ N (aligned). Periods are j Ti = t0 2ji (level ji , window j = t0 2 ); reservations are P W ′ ki ′ di = 2 u ≤ t0 ; U = i di /Ti . SF-BF processes levels in increasing order, duplicating the free set at each level transition (valid: everything placed so far is Wj -periodic), and serves each request from a minimum-size sufficient free block, carving from the left. Lemma 6 (staircase carving). Carving a request q from the left end of a block B = [b, b + s), q ≤ s, leaves [b + q, b + s), which is the disjoint union of exactly one aligned block of each size q, 2q, . . . , s/2 (empty if q = s). Proof. With s = 2M q, define Il = [b + 2l q, b + 2l+1 q) for l = 0, . . . , M −1. These are disjoint with union [b + q, b + s), and Il has size 2l q and left endpoint b + 2l q, a multiple of 2l q since b is a multiple of s ≥ 2l+1 q.

Lemma 7 (count invariant). (i) A successful SF-BF allocation creates new free blocks only at sizes whose current count is 0. (ii) At the start of level-j processing, every size has count at most 2j . Both bounds are tight. Proof. (i) Let q be the request and b the minimum size of a free block with b ≥ q. The staircase sizes of Lemma 6 lie in [q, b); by minimality of b no free block has size in [q, b), so each created size moves from count 0 to 1. (ii) Induction: level 0 starts from the single block [0, t0 ); by (i) the maximum count never increases during a level; the transition duplicates the free set, doubling counts. Tightness of (ii): when intermediate levels carry no requests, the transition doubling compounds unimpeded, so a level-j request can meet 2j blocks of one size (construction verified mechanically). Lemma 8 (failure bound). If a level-j request q fails, the free measure satisfies |F | < 2j q. Proof. All free blocks have size ≤ q/2; distinct sizes are q/2, q/4, . . . , u, each with count ≤ 2j (Lemma 7), so |F | ≤ 2j (q − u) < 2j q. Proof of the packing threshold (Lemma 5 in the paper). Suppose a request q = d′i at level j fails. The occupied measure within [0, Wj ) is Wj times the density of the stations placed so far, at most Wj U , so |F | ≥ Wj (1 − U ) = 2j t0 (1 − U ) ≥ 2j q by hypothesis, contradicting Lemma 8. For the converse, generalize Proposition 2: let level-0 stations occupy measure (1 − ϵ)t0 of the base window with one contiguous free gap of length ϵt0 . A station of level ≥ 1 must place its contiguous SP inside one periodic copy of the gap (it cannot straddle the level-0 pattern), so d′ ≤ ϵt0 = t0 (1 − U0 ) is necessary, where U0 is the lower-level utilization. Proof of Theorem 1 (8-approximation). Lower bound: any feasible schedule has disjoint SPs, hence density ≤ 1 and Ti ≥ Timin , so OPT − C ≥ J ∗ where J ∗ solves (2) (with the dmax constraint dropped; it is also valid by Lemma 2). Density scaling: for ρ ≤ 1, T ∗ (1)/ρ is feasible for density target ρ (density scales by ρ, the floors still hold), so J(T (ρ)) ≤ J ∗ /ρ; we run the relaxation at ρ⋆ = 1/4. Rounding: round each Ti up to the grid t0 2j , t0 ≤ Tmin (factor < 2 on cost; density only decreases); round each di up to a dyadic divisor d′i of t0 (factor < 2, possible since di ≤ t0 /4 < t0 ). The resulting density satisfies U ≤ 2· 41 = 12 , and d′i ≤ t0 /2 = t0 (1− 12 ) ≤ t0 (1−U ). Packing: Lemma 5 places everything; each station transmits only di inside its reservation, so true duty cycles satisfy di /Ti′ ≤ di /Timin = ρi – reservations cost no energy. Chain: cost ≤ 2 · J(T (1/4)) ≤ 2 · 4J ∗ ≤ 8 (OPT − C). Proof of Corollary 1 (candidate-argmin anchor). For θ ∈ [0, 1) let t0 (θ) = Tmin 2−θ and ℓi (θ) = 2⌈z⌉−z , z = yi + θ, yi = log2 (Ti /Tmin ), the per-station rounding factor. (a) For R 1 1−f 2 df = θ uniform, frac(z) is uniform and E[2⌈z⌉−z ] = 0 P 1/ ln 2; by linearity Eθ [C(θ)] = (1/ ln 2) i ai Ti . (b) On any interval free of breakpoints (θ with frac(yi + θ) = 0 for some i), every frac(yi + θ) increases without wrapping, so every

ℓi – and hence C – strictly decreases. As θ approaches a breakpoint from below, the wrapping station’s factor tends to 1, its value at the breakpoint (an exact power of two rounds to itself), so C is left-continuous there and attains its infimum at a breakpoint. The breakpoints are θc = 1 − frac(yc ), i.e. t0 (θc ) = Tc /2⌈yc ⌉ : exactly the folded candidates. (c) mincand C = minθ C ≤ Eθ [C]. Proof of Theorem 2 (unconditional). By Lemma 2 the relaxation may include Ti ≥ dmax . Set T̂ = 6 T ∗′ : density ≤ 1/6, every period ≥ 6dmax , cost 6J ∗′ . Any folded-candidate anchor satisfies t0 > T̂min /2 ≥ 3dmax . Round periods (factor < 2, or 1/ ln 2 in the candidate-argmin sense) and reservations (di ≤ dmax < t0 /3 < t0 , factor < 2): the density becomes U ′ ≤ 2/6 = 1/3 and d′i < 2dmax < 23 t0 ≤ t0 (1 − U ′ ), so Lemma 5 packs. Cost ≤ 2 · 6 J ∗′ ≤ 12 OPT. Optimality of s = 6 for this accounting: the packing condition reads 2dmax ≤ 2s dmax (1 − 2s ), i.e. s ≥ 6. Write J = a1 T1 +a2 T2 , T1 ≤ T2 , energy floors T1min , T2min . Lemma 9. Any feasible two-station schedule has T2 /T1 rational. Proof. If T2 /T1 is irrational, the differences {jT2 − kT1 : j, k ∈ N} are dense in R (an irrational rotation equidistributes), so some pair of SP start times differs by a value in (−d1 , d2 ) – and those two SPs overlap. Lemma 10. Let T2 /T1 = p/q reduced, p ≥ q ≥ 1. The schedule is feasible iff T1 ≥ q(d1 + d2 ). Proof. Since gcd(p, q) = 1, the starts of station 2’s SPs modulo T1 form q equally spaced phases (spacing T1 /q). Station 1’s contiguous SP cannot straddle an SP of station 2, so it must fit in one inter-phase gap of length T1 /q − d2 : feasibility ⇐⇒ T1 /q − d2 ≥ d1 . Sufficiency: place ϕ1 in any gap. Theorem 4 (exact N =2). Let J(r, q) = (a1 + a2 r) max(T1min , T2min /r, q(d1 +d2 )) and
 J(⌈r∗ ⌉,1)  T min 1 rq∗ = max 1, max(T min2, q(d1 +d2 )) , Q = (a1 +a2 )(d . 1 +d2 ) 1

Then the optimum equals minq≤Q minp J(p/q, q) over p ∈ {⌊qrq∗ ⌋, ⌈qrq∗ ⌉} with p ≥ q – an O(Q) exact algorithm. Proof. Lemmas 9–10 reduce the problem to min J(p/q, q) over reduced rationals with the stated feasible region: for fixed r and q the objective increases in T1 , so the optimal T1 is the smallest feasible value – the active maximum inside J. For fixed q, J(·, q) is quasiconvex on [1, ∞): while T2min /r is the active maximum, J = a1 T2min /r + a2 T2min strictly decreases; once the maximum is constant in r, J strictly increases. Hence the integer numerator minimum is attained at one of the two grid neighbors of the continuous minimizer rq∗ . Finally J(r, q) ≥ (a1 + a2 ) q(d1 + d2 ), so all q > Q are dominated by the q = 1 candidate defining Q. (Non-reduced fractions replicate a smaller-q ratio with a tighter packing floor and are dominated.) Non-integer optimality: T1min = 10,

T2min = 15, d1 + d2 = 1 gives ratio 3/2 cost 10a1 + 15a2 , beating every integer ratio; continuity extends the strict gap to a neighborhood.

Related documents

• World Radio Coverage of Climate Change or Global Warming, 2000-2026 - March 2026#14566
• Robust Assessment of Free-Living Physical Behaviors and Activity Intensity Using Dual-Wearable Multitask Learning: Development and Evaluation Study From the Multicenter WEALTH Project.#469350
• Reachable-Set Decomposition for Real-Time Aggregation of Multi-Zone HVAC Fleets#1069800
• Association between unpredictable work schedule changes and sleep disorders among wage workers: evidence from national Working Conditions Surveys in Korea and Europe.#625863
• Early Time-Restricted Eating for Cardiovascular Health#1127599