Distributed Quantum-Assisted Robust AoII Minimization in Satellite-Ground Integrated Edge Networks

1

Distributed Quantum-Assisted Robust AoII Minimization in Satellite-Ground Integrated Edge Networks

arXiv:2610.05651v1 [cs.NI] 5 Oct 2026

Mohammad Arif Hossain, Member, IEEE, Tanzimul Alam Fahim, Weiqi Liu, Member, IEEE, and Nirwan Ansari, Life Fellow, IEEE

Abstract—Mission-critical edge applications in 6G-and-beyond networks, such as autonomous systems, disaster response, and infrastructure monitoring, require that the edge decision-maker’s estimate of a monitored process remain correct, not merely up to date. Satellite-ground integrated networks (SAGIN) often provide the only connectivity in infrastructure-limited or disaster-affected regions, yet satellite handover and shadowing interrupt links, during which the process may change state several times, leaving the edge node’s estimate substantially wrong. Age of information (AoI) tracks only elapsed time and cannot distinguish a harmless delay from a dangerous error. We instead adopt the age of incorrect information (AoII), which penalizes both the duration and magnitude of estimation error, and formulate, to our knowledge, the first network-level, multi-node AoII minimization problem over SAGIN under stochastic handover and shadowing. We propose SENTINEL, a distributed hybrid quantum-classical framework that jointly schedules update rates, satellite-to-basestation associations, and bandwidth allocation to minimize the worst-case time-average AoII. Because AoII is history dependent, it resists per-slot optimization; a renewal-interval decomposition that separates source dynamics from channel disruption yields a closed-form AoII cost per inter-delivery interval. The resulting robust scheduling problem, VANGUARD, is formulated as a QUBO, mapped to an Ising Hamiltonian, and solved via distributed QAOA with ADMM-based coordination across satellite and ground domains. Every returned schedule carries a certified worst-case AoII over all disruption scenarios. Simulations show that SENTINEL outperforms learning-based and random baselines, matches a state-aware threshold policy in small networks while additionally providing a worst-case guarantee, and remains close to an exact minimax reference. Index Terms—6G, age of incorrect information (AoII), alternating direction method of multipliers (ADMM), mission-critical edge computing, quantum approximate optimization algorithm (QAOA), remote estimation, robust optimization, satellite-ground integrated network (SAGIN), semantic communication

I. I NTRODUCTION Next-generation (6G-and-beyond) wireless networks are envisioned to push intelligence and autonomy to the network edge [1], supporting mission-critical applications such as autonomous and tactical systems, disaster response, industrial control, digital twins, and remote infrastructure monitoring. Mohammad Arif Hossain is with the QRISE Center and Department of Engineering Technology, Middle Tennessee State University (MTSU), TN 37132 USA (e-mail: Mohammad.Hossain@mtsu.edu), Tanzimul Alam Fahim is with the Computational Science PhD Program at MTSU, Murfreesboro, TN 37132 USA, Weiqi Liu is with the Department of Computer Science and Computer Information Systems, Auburn University at Montgomery, AL 36117 USA, and Nirwan Ansari is with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, NJ 07102 USA.

These applications require edge nodes to maintain an accurate belief about a physical process, such as the state of a disaster zone, the condition of infrastructure, or the position of a tactical asset, and to act on it without human verification. The value of information is therefore determined not only by how quickly it arrives, but by whether the edge decision-maker’s estimate remains correct. Terrestrial mobile edge computing (MEC) offers high capacity and low delay, but its availability is bounded by ground infrastructure, which is often scarcest where mission-critical monitoring is needed most. Satellite networks can extend connectivity and computing capabilities to infrastructure-limited, contested, or disaster-affected regions, motivating satellite-ground-integrated edge networks as a candidate architecture for resilient, correctness-aware edge intelligence [2]. In a satellite-ground integrated network (SAGIN), edge nodes (UEs) transmit status updates to edge servers hosted at terrestrial base stations (BSs) or satellites (SATs). BSs offer stable, low-delay links, whereas SATs provide coverage where terrestrial infrastructure is limited or destroyed. Satellite links, however, are subject to stochastic disruption from orbital dynamics, atmospheric shadowing, Doppler shifts, and handover. For mission-critical monitoring, such a disruption is not merely a delay problem: while a link is unavailable, the monitored process continues to evolve and may pass through several states before connectivity is restored, leaving the edge with an estimate that is not simply stale but possibly substantially incorrect, often without the edge node being aware of it. This distinction between staleness and incorrectness is invisible to age of information (AoI) [3], [4], which tracks only the elapsed time since the last received update and treats every unit of delay as equally costly, regardless of whether the process has changed. Age of incorrect information (AoII) [5], [6] captures this distinction: it remains zero while the edge estimate matches the true state and accrues only while the two diverge, weighted by the severity of the mismatch. AoII has so far been studied mainly for a single source and monitor over a point-to-point channel, typically under threshold or semi-Markov policies. Extending it to SAGIN raises two open challenges. First, AoII depends on the entire trajectory of a Markovian source since the estimate last diverged, making it structurally incompatible with the per-slot combinatorial formulations used in prior SAGIN resource allocation. Second, in SAGIN, the duration and severity of estimation error are driven by handover-

2

and shadowing-induced outages that can span multiple state transitions, so the allocation policy must be robust to the worstcase outage pattern rather than its expected behavior. Classical methods can approximate robust solutions through relaxation, decomposition, or robust counterparts, but they typically require accurate disruption models and become computationally prohibitive when scheduling, association, and worstcase outage selection are optimized jointly. Reinforcement learning (RL) adapts without a complete analytical model, but it optimizes expected cumulative reward rather than worst-case estimation error, offers no certified bound on how wrong an edge belief can become during an adverse disruption, and is difficult to train reliably over the resulting combinatorial decision space. This motivates an approach that directly exploits the combinatorial binary structure of the robust AoII problem. To this end, we propose SENTINEL, a distributed hybrid quantum-classical framework for correctness-aware edge orchestration in SAGIN under stochastic handover and shadowing uncertainty, which directly targets the worst-case timeaverage AoII across all monitored edge nodes. The key enabler is a renewal-interval decomposition: since each monitored source evolves as a Markov chain with known dynamics, the expected AoII accumulated between two successful updates can be computed offline in closed form as a function of the inter-delivery interval alone. This decouples source dynamics from channel disruption, so the only quantity the network must reason about under uncertainty is the channelinduced inter-delivery interval, which fits naturally into a discretized-scenario, binary-variable robust formulation. The resulting robust scheduling problem, VANGUARD, can thus be formulated as a quadratic unconstrained binary optimization (QUBO) problem, mapped to an Ising Hamiltonian, and solved via the quantum approximate optimization algorithm (QAOA). To remain practical on near-term quantum hardware [7], where a centralized VANGUARD QUBO would require prohibitively many qubits, SENTINEL partitions the SAGIN into local satellite-ground domains. Each local controller solves a sub-QUBO capturing its own disruption uncertainty and resource constraints, while a classical ADMM-based coordinator reconciles the bandwidth of satellites shared by several domains. Every returned schedule is evaluated exactly under all disruption scenarios, so its worst-case AoII is certified regardless of whether the quantum solver reaches the global optimum. The main contributions of this paper are summarized as follows: • We propose SENTINEL, a distributed hybrid quantumclassical framework for Satellite-ground Edge Network orchestration for Trustworthy Intelligence and Node-level Estimation via quantum-classicalL coordination, which addresses stochastic satellite handover and shadowing uncertainty through robust minimax AoII optimization. • We formulate the robust scheduling problem VANGUARD, short for Value-of-information-aware, uncertAintyrobust, Network-wide Generation, Update-scheduling, Association, and Resource orchestration under Disruption. VANGUARD minimizes the worst-case time-average AoII over a bounded uncertainty set that captures shadowing,

Doppler, and handover failures, subject to bandwidth, visibility, update rate, and AoII budget constraints. • We derive a renewal-interval decomposition that separates each source’s Markovian dynamics from the satellite channel’s disruption pattern, yielding a closed-form expected AoII cost per inter-delivery interval and reconciling AoII’s history dependence with per-slot combinatorial optimization. • We discretize update rates, association, bandwidth levels, and the uncertainty set into a unified robust QUBO, map it to an Ising Hamiltonian, and solve it via a distributed hybrid QAOA in which local satellite-ground domains solve sub-QUBOs in parallel under ADMM-based classical consensus. • We evaluate SENTINEL under dynamic SAGIN settings with stochastic handover and shadowing, comparing it with random, threshold-based, and learning-based baselines and validating its solution quality against an exact minimax reference. The remainder of this paper is organized as follows. Section II reviews related work. Section III presents the system model, including the Markovian source, the AoII renewalinterval decomposition, and the disruption-aware communication and orchestration models. Section IV formulates VANGUARD and its binary reformulation. Section V develops the QUBO, Ising, and distributed QAOA solution. Section VI presents simulation results, and Section VII concludes the paper. II. S TATE OF THE A RT This paper lies at the intersection of satellite-ground integrated edge computing, freshness- and semantics-aware information metrics [8]–[10], robust resource allocation, learningbased scheduling, and quantum-assisted combinatorial optimization, which we review in turn. 1) Satellite-Ground Integrated Edge Computing: Satelliteground integrated edge computing extends MEC [11] beyond terrestrial coverage by equipping satellites and base stations with edge servers [12]–[14], and must contend with heterogeneous delays, orbital topology dynamics, limited onboard resources, and stochastic link degradation. Most existing works focus on task offloading and latency under deterministic or average-case channel assumptions [15], [16]; none treat the correctness of the delivered information, rather than its delivery speed, as the primary objective. 2) Age of Information and Age of Incorrect Information: AoI has been widely studied as a timeliness metric in wireless and IoT networks [3], [4], [8], [17], [18], but it is contentagnostic, penalizing elapsed time regardless of whether the monitored process has changed. AoII addresses this by jointly penalizing the duration and magnitude of estimation error [5], and has been analyzed for single-source, single-monitor systems under threshold and semi-Markov policies [6], [19] and over unreliable, power-constrained channels [20]. It has not yet been formulated as a network-level, multi-node scheduling problem, nor has it been examined under satellite outages that span multiple source state transitions.

3

3) Robust Resource Allocation Under Satellite Link Uncertainty: Robust optimization minimizes cost against the worstcase realization of an uncertain parameter within a bounded set [21], [22], and has been applied to power control, beamforming, and scheduling under channel uncertainty. Robust allocation for satellite-ground MEC remains comparatively unexplored, and existing formulations treat uncertainty as a channel or delay perturbation rather than as a driver of estimation error at the edge. 4) Learning-Based Scheduling for Freshness: Reinforcement learning [23], [24] has been applied to AoI- and AoIIaware scheduling in point-to-point and small multi-user systems. However, it optimizes the expected reward, requires extensive training on representative disruption patterns, and provides no certified bound on the estimation error under adverse or unseen disruptions. 5) Quantum-Assisted Combinatorial Optimization: QUBO formulations [25], [26] solved via QAOA [27], [28] or quantum annealing [29] have been applied to channel assignment, scheduling, and resource allocation in wireless networks [30]. This paradigm suits robust minimax problems: once the uncertainty set is discretized, adversarial scenario selection is itself combinatorial and can be encoded jointly with the resource decision in a single QUBO. However, QAOA has not been applied to information freshness or correctness objectives, nor has it been combined with a distributed architecture for satellite-ground networks. 6) Research Gap and Motivation: To the best of our knowledge, no existing work (i) formulates AoII as a networklevel, multi-node, or robust minimax scheduling problem; (ii) targets information correctness, rather than delay or throughput, in robust SAGIN resource allocation; or (iii) applies quantum-assisted optimization to freshness- or correctnessaware scheduling. SENTINEL addresses all three by casting worst-case AoII minimization under satellite handover and shadowing uncertainty as a QUBO solved via distributed hybrid QAOA with ADMM-based classical coordination. III. S YSTEM M ODEL We consider a satellite-ground-integrated edge network in which distributed edge nodes monitor time-varying physical processes and transmit status updates to remote edge servers to support mission-critical decision-making under stochastic satellite link disruptions. Let 𝒰, 𝒮, and ℬ denote the sets of monitoring edge nodes (UEs), satellites (SATs), and ground base stations (BSs), respectively, with UEs indexed by 𝑢 𝑖 , SATs by 𝑠 𝑗 , and BSs by 𝑏 𝑛 . Each UE observes a physical process of operational relevance, such as the condition of critical infrastructure, a hazard indicator in a disaster-affected area, or the status of a tactical asset, and must deliver timely and correct status updates to an edge server hosted at a BS or a visible SAT. Both SATs and BSs host edge servers that maintain a running estimate of each monitored process and act on it. BS-hosted servers benefit from stable, low-delay links, while SAT-hosted servers extend coverage to regions where terrestrial infrastructure is limited, damaged, or unavailable. Time is slotted, 𝑡 ∈ {0, 1, 2, . . .}, with slot duration 𝑇𝑠 .

Each UE may transmit its status updates to either a BS or a visible SAT, with SAT visibility governed by the elevation angle. UEs are assumed to have low mobility over the decision interval, whereas the satellite-ground topology is dynamic due to orbital motion. Unlike conventional SAGIN edge computing models, in which the quantity of interest is task completion delay, SENTINEL targets the correctness of the estimate held by the edge server, which depends jointly on (i) the intrinsic dynamics of the monitored process, (ii) when each UE samples and transmits an update, and (iii) whether that update is delivered before the process changes state again. Satellite handover and shadowing introduce stochastic disruption into the delivery process, during which the monitored process may pass through multiple states before the next update succeeds. As a result, allocation decisions made under a nominal channel assumption can leave the edge server with a substantially incorrect estimate rather than merely a delayed one. SENTINEL adopts a distributed hybrid quantum-classical decision architecture rather than centralized optimization or learning-based orchestration. The network is partitioned into 𝐾 local satellite-ground domains indexed by 𝒦 = {1, 2, . . . , 𝐾 }, where the 𝑘-th domain is D 𝑘 = (𝒰𝑘 , 𝒮𝑘 , ℬ𝑘 ) ,

(1)

with 𝒰𝑘 ⊆ 𝒰, 𝒮𝑘 ⊆ 𝒮, and ℬ𝑘 ⊆ ℬ the UEs, visible SATs, and available BSs in domain 𝑘. The UE subsets {𝒰𝑘 } 𝑘 ∈𝒦 form a partition of 𝒰, whereas a SAT may be visible to, and therefore shared by, several domains; this shared resource is the source of inter-domain coupling. Each domain has a classical controller that observes the local network and disruption state, constructs a local robust binary optimization problem targeting worst-case AoII, and solves it with a hybrid QAOA solver. A classical ADMM-based coordinator then reconciles the bandwidth that the domains use at shared SATs. A. Communications Model We adopt a standard SAGIN physical-layer geometry and channel model, since satellite handover and shadowing affect the delivery process regardless of whether the payload is a computation task or a status update. UE, BS, and SAT positions are converted from geodetic to earth-centered, earthfixed (ECEF) coordinates to compute inter-node distances, and the nominal path loss (in dB) between UE 𝑢 𝑖 and SAT 𝑠 𝑗 is   𝑢𝑠 𝑢𝑠 𝑢𝑠
𝑢𝑠 𝑢𝑠 + 𝜉 log (2) 𝜑𝑢𝑠 = 𝜍 + 𝜁 log 𝑓 10 𝑐 10 𝑑 𝑖 𝑗 , 𝑖𝑗 where 𝑑𝑖𝑢𝑠𝑗 = ∥r𝑢𝑖 −r𝑠𝑗 ∥ is the Euclidean distance between 𝑢 𝑖 and 𝑠 𝑗 in ECEF coordinates, 𝑓𝑐𝑢𝑠 is the carrier frequency, 𝜍 𝑢𝑠 is the reference path loss, and 𝜁 𝑢𝑠 and 𝜉 𝑢𝑠 are the frequency- and distance-dependence coefficients. The UE-BS path loss 𝜑𝑢𝑏 𝑖𝑛 is computed analogously using the haversine ground distance 𝑢𝑏 , and BS links are assumed terrestrial and stable. The 𝑑𝑖𝑛 nominal uplink data rate from 𝑢 𝑖 to 𝑠 𝑗 is ! 𝑢𝑠 𝑝 𝑖 · 10− 𝜑𝑖 𝑗 /10 𝑢𝑠 𝑢𝑠 , (3) 𝑅𝑖 𝑗 = 𝛽𝑖 𝑗 log2 1 + 𝑁0 𝛽𝑖𝑢𝑠𝑗 + 𝜐 𝑢𝑏 defined analogously, where 𝑝 is the with the UE-BS rate 𝑅𝑖𝑛 𝑖 UE transmit power, 𝑁0 is the noise power spectral density,

4

Space segment Space segment

LEO Satellites LEO Satellites

Air segment Air segment UAV UAV

UAV UAV

Ground segment Ground segment Server Server UE UE

Small Base Small Base Station Station

Smart Vehicle Smart Vehicle

Smart Camera Smart Camera

Smart Bulbs Smart Bulbs

Macro Base Macro Base Station Station D2D D2D

Multi-RAT Access Multi-RAT Access Point Point Inter-satellite link

Backhaul link

Smart Sensors Smart Sensors D2D link

Space/air–ground link

Edge (MEC) server

Fig. 1. System model for correctness-aware monitoring over SAGIN under satellite disruption.

and 𝜐 is the aggregate co-channel interference, which we treat as a fixed worst-case bound so that the rate of each link does not depend on the association decisions of other UEs. SAT 𝑠 𝑗 can serve 𝑢 𝑖 only if 𝑉𝑖 𝑗 ≥ Θ, where 𝑉𝑖 𝑗 = arcsin(𝜇𝑖 𝑗 ) and 𝜇𝑖 𝑗 is the inner product between the unit line-of-sight vector from 𝑢 𝑖 to 𝑠 𝑗 and the unit zenith vector at 𝑢 𝑖 ’s location. B. Monitored Source and Estimation Model Each UE 𝑢 𝑖 observes a physical process 𝑋𝑖 (𝑡) modeled as a discrete-time Markov chain over a finite state space X𝑖 with transition matrix 𝑃𝑖 , where each state represents an operationally meaningful severity or status level (e.g., a hazard tier, a structural-integrity level, or an asset status). Each UE controls a generation indicator 𝑔𝑖 (𝑡) ∈ {0, 1} that specifies whether a status update is sampled and transmitted in slot 𝑡. We assume that 𝑇𝑠 exceeds the maximum propagation and transmission delay of a successful update, so that an update sampled at the start of slot 𝑡 is either delivered within that slot or lost. Let 𝑡 𝑖,𝜅 denote the 𝜅-th slot in which an update from 𝑢 𝑖 is successfully delivered, and 𝑌𝑖,𝜅 = 𝑡𝑖,𝜅+1 − 𝑡𝑖,𝜅 the corresponding inter-delivery interval. The edge server assigned to 𝑢 𝑖 maintains the estimate 𝑋ˆ 𝑖 (𝑡) = 𝑋𝑖 (𝑡𝑖,𝜅 ),

𝑡𝑖,𝜅 ≤ 𝑡 < 𝑡 𝑖,𝜅+1 ,

(4)

which remains fixed between deliveries while the true process may continue to evolve. Let Λ𝑖 (𝑡) = max{𝜏 ≤ 𝑡 : 𝑋𝑖 (𝜏) =

𝑋ˆ 𝑖 (𝜏)} denote the most recent slot at which the estimate was correct. Following [5], the instantaneous AoII of 𝑢 𝑖 is

Δ𝑖𝐼 𝐼 (𝑡) = 𝑡 − Λ𝑖 (𝑡) 𝑓𝑖 𝑋𝑖 (𝑡), 𝑋ˆ 𝑖 (𝑡) , (5) where 𝑓𝑖 (𝑥, 𝑥) ˆ ≥ 0, with 𝑓𝑖 (𝑥, 𝑥) = 0, is a distortion function capturing the operational severity of a mismatch (e.g., 𝑓𝑖 (𝑥, 𝑥) ˆ = |𝑥 − 𝑥| ˆ for an ordered severity chain). Unlike AoI, Δ𝑖𝐼 𝐼 (𝑡) returns to zero without a new delivery whenever 𝑋𝑖 (𝑡) revisits 𝑋ˆ 𝑖 (𝑡), and it can become positive immediately after a delivery if the source moves away from the delivered value. The scheduling decisions {𝑔𝑖 (𝑡)}, together with the association and resource allocation decisions, determine the delivery slots {𝑡𝑖,𝜅 } 𝜅 ≥1 and hence the AoII trajectory of 𝑢 𝑖 . C. Link Disruption and Renewal Model Satellite links are subject to stochastic degradation from atmospheric shadowing, Doppler-induced residual frequency offset, and handover interruptions. The realized path loss under disruption scenario ℓ is 𝑢𝑠 𝑢𝑠 𝜑˜ 𝑢𝑠 𝑖 𝑗 (ℓ) = 𝜑𝑖 𝑗 + 𝛿𝑖 𝑗 (ℓ), dp

(6)

where 𝛿𝑖𝑢𝑠𝑗 (ℓ) = 𝛿𝑖sh𝑗 (ℓ) + 𝛿𝑖 𝑗 (ℓ) + 𝛿𝑖ho𝑗 (ℓ) aggregates the shadowing, Doppler, and handover components, and each scenario also specifies the length 𝑇𝑖dis 𝑗 (ℓ), in slots, of the window over which this perturbation applies. The bounded uncertainty set

5

TABLE 1. Key Notations Symbol 𝒰, 𝒮, ℬ ℳ =𝒮∪ℬ 𝒦, D 𝑘 𝛼𝑖 𝑗 , 𝜔𝑖𝑛 𝑢𝑏 𝛽𝑖𝑢𝑠 𝑗 , 𝛽𝑖𝑛 𝐵𝑠𝑗 , 𝐵𝑛𝑏 𝑢𝑏 𝑅𝑖𝑢𝑠 𝑗 (ℓ ), 𝑅𝑖𝑛 𝑉𝑖 𝑗 , Θ ℒ, Ω 𝑇𝑖dis 𝑗 (ℓ ), 𝜏𝑖𝑚𝑞 (ℓ ) 𝑇𝑠 𝑋𝑖 (𝑡 ), 𝑋ˆ 𝑖 (𝑡 ) X𝑖 , 𝑃𝑖 , 𝜋𝑖 𝑓𝑖 ( 𝑥, 𝑥ˆ ) Δ𝑖𝐼 𝐼 (𝑡 ), Δ𝑖𝐼 𝐼,max 𝑡𝑖,𝜅 , 𝑌𝑖,𝜅 Ψ𝑖 (𝑌 ) 𝜌𝑖 , 𝜌¯𝑖ℎ 𝑞 𝛽¯𝑚 𝑥𝑖𝑚𝑞ℎ 𝒜𝑖 (ℓ) 𝜓𝑖𝑚𝑞ℎ 𝜂, 𝜂𝑘 𝑧 𝑗𝑘, 𝑢𝑗𝑘, 𝜚

Definition Sets of UEs, SATs, and BSs Set of serving nodes Set of domains; 𝑘-th domain Association of 𝑢𝑖 with 𝑠 𝑗 , 𝑏𝑛 Bandwidth allocated to 𝑢𝑖 by 𝑠 𝑗 , 𝑏𝑛 Bandwidth capacity of 𝑠 𝑗 , 𝑏𝑛 Uplink rate of 𝑢𝑖 to 𝑠 𝑗 (scenario ℓ), to 𝑏𝑛 Elevation angle of 𝑠 𝑗 at 𝑢𝑖 ; minimum elevation Scenario set (𝐿 scenarios); uncertainty set Disruption window; induced outage (slots) Slot duration Monitored source of 𝑢𝑖 ; edge estimate State space, transition matrix, stationary distribution Distortion function Instantaneous AoII; AoII budget 𝜅-th delivery slot; inter-delivery interval Expected AoII accumulated over an interval of length 𝑌 Update rate of 𝑢𝑖 ; ℎ-th rate level (𝐻𝑖 levels) 𝑞-th bandwidth level of node 𝑚 (𝑄𝑚 levels) 1 if 𝑢𝑖 uses node 𝑚, bandwidth level 𝑞, rate level ℎ Admissible combinations (𝑚, 𝑞, ℎ) of 𝑢𝑖 Time-average AoII cost under scenario ℓ Network and local worst-case AoII (epigraph) ADMM bandwidth target, scaled dual, penalty

Ω is discretized into 𝐿 scenarios ℒ = {1, . . . , 𝐿} spanning the nominal, single-link worst-case, and global worst-case realizations. The corresponding scenario rate 𝑅𝑖𝑢𝑠𝑗 (ℓ) follows 𝑢𝑠 from (3) with 𝜑𝑢𝑠 𝑖 𝑗 replaced by 𝜑˜ 𝑖 𝑗 (ℓ), and an update sampled in slot 𝑡 is delivered under scenario ℓ only if 𝑅𝑖𝑢𝑠𝑗 (ℓ) 𝑇𝑠 ≥ 𝐷 𝑖 and 𝑉𝑖 𝑗 ≥ Θ. In a task-offloading setting, scenario ℓ mainly perturbs the achievable data rate. In SENTINEL, it also determines the length of the induced outage or degraded-throughput window and therefore the inter-delivery interval 𝑌𝑖,𝜅 (ℓ), which is the number of slots from 𝑡 𝑖,𝜅 until the next slot in which 𝑔𝑖 (𝑡) = 1 and the delivery condition above holds. A more severe scenario yields a longer 𝑌𝑖,𝜅 (ℓ), over which 𝑋𝑖 (𝑡) may pass through several states before the next delivery succeeds. This coupling between the channel scenario and the inter-delivery interval is what ties the disruption model to the AoII objective.

D. Renewal-Interval AoII Decomposition Because Δ𝑖𝐼 𝐼 (𝑡) depends on the full trajectory of 𝑋𝑖 (𝑡) since the estimate was last correct, it cannot be written as a per-slot function of the current channel state, and therefore cannot be substituted directly into a per-slot QUBO cost coefficient in the way task completion time is in SAGIN offloading formulations. We resolve this by exploiting the renewal structure of the delivery process. Under the same-slot delivery assumption of Section III-B, the estimate is exact at each delivery slot, so Δ𝑖𝐼 𝐼 (𝑡𝑖,𝜅 ) = 0. Between two consecutive deliveries at 𝑡 𝑖,𝜅 and 𝑡𝑖,𝜅+1 = 𝑡 𝑖,𝜅 + 𝑌𝑖,𝜅 , the estimate is fixed

at 𝑥ˆ = 𝑋𝑖 (𝑡 𝑖,𝜅 ) and the AoII evolves according to the source’s own Markov dynamics, independently of the channel.
To evaluate this evolution, let 𝑃˜𝑖, 𝑥ˆ = 𝑃𝑖 I − e 𝑥ˆ e⊤𝑥ˆ denote the taboo matrix obtained by setting the 𝑥-th ˆ column of 𝑃𝑖 to zero, so that [ 𝑃˜𝑖,𝑎 𝑥ˆ ] 𝑥ˆ 𝑦 is the probability of moving from 𝑥ˆ to 𝑦 in 𝑎 steps without revisiting 𝑥. ˆ Let f𝑖, 𝑥ˆ be the vector with entries 𝑓𝑖 (𝑦, 𝑥), ˆ 𝑦 ∈ X𝑖 . The AoII at 𝑠 slots after a delivery equals 𝑎 𝑓𝑖 (𝑦, 𝑥) ˆ exactly when the source was last at 𝑥ˆ at slot 𝑠 − 𝑎 and has since moved to 𝑦 without returning. Hence 𝑠      ∑︁  𝑎 𝑃𝑖𝑠−𝑎 𝑥ˆ 𝑥ˆ 𝑃˜𝑖,𝑎𝑥ˆ f𝑖, 𝑥ˆ 𝑥ˆ , E Δ𝑖𝐼 𝐼 (𝑡 𝑖,𝜅 + 𝑠) 𝑥ˆ =

(7)

𝑎=1

and the expected AoII accumulated over an interval of length 𝑌 is 𝑌 −1 ∑︁   Ψ𝑖 (𝑌 | 𝑥) ˆ = E Δ𝑖𝐼 𝐼 (𝑡 𝑖,𝜅 + 𝑠) 𝑥ˆ , (8) 𝑠=1

and its average over the delivered state is ∑︁ Ψ𝑖 (𝑌 ) = 𝜋𝑖 ( 𝑥) ˆ Ψ𝑖 (𝑌 | 𝑥), ˆ

(9)

𝑥ˆ ∈ X𝑖

where 𝜋𝑖 is the stationary distribution of 𝑃𝑖 . The averaging over 𝜋𝑖 is valid because the update decisions do not depend on the realized source state, so the delivered state is distributed according to 𝜋𝑖 when the source is in steady state. Both quantities depend only on 𝑌 and 𝑃𝑖 and are computed once per UE offline for all 𝑌 ≤ 𝑌 max . By the renewal-reward theorem, the time-average AoII of 𝑢 𝑖 over an interval of length 𝑌 is Ψ𝑖 (𝑌 )/𝑌 . Equation (9) decouples the source’s intrinsic dynamics from the channel’s disruption pattern. The only channel-dependent quantity the network must reason about under uncertainty is the inter-delivery interval, which under scenario ℓ is deterministic for a given allocation and is denoted 𝑌𝑖 (ℓ). The resulting AoII cost is obtained by evaluating the precomputed ratio Ψ𝑖 (𝑌𝑖 (ℓ))/𝑌𝑖 (ℓ). This is the key step that makes the robust AoII objective compatible with the per-scenario, binaryvariable structure of the QUBO formulation developed in Section V. E. Quantum-Compatible Resource and Scheduling Block Model Hybrid QAOA requires a binary decision space, whereas the 𝑢𝑏 are conupdate rates 𝜌𝑖 and the bandwidth allocations 𝛽𝑖𝑢𝑠𝑗 , 𝛽𝑖𝑛 tinuous, and the uncertainty set Ω is continuous prior to discretization. We therefore discretize the bandwidth of each serv𝑄𝑚 ing node 𝑚 ∈ ℳ = 𝒮 ∪ ℬ into 𝑄 𝑚 levels { 𝛽¯1𝑚 , . . . , 𝛽¯𝑚 }, the 𝐻𝑖 1 min update rate of 𝑢 𝑖 into 𝐻𝑖 levels { 𝜌¯ 𝑖 , . . . , 𝜌¯ 𝑖 } ⊂ [𝜌𝑖 , 𝜌𝑖max ], and Ω into the 𝐿 scenarios of ℒ. We define the unified binary decision variable   1, if 𝑢 𝑖 uses node 𝑚, bandwidth    𝑥 𝑖𝑚𝑞ℎ = (10) level 𝑞, and update-rate level ℎ,    0, otherwise,  which jointly encodes association, bandwidth allocation, and update scheduling. The continuous decisions areÍrecovered as Í Í 𝛼𝑖 𝑗 = 𝑞,ℎ 𝑥𝑖 𝑗𝑞ℎ , 𝜔𝑖𝑛 = 𝑞,ℎ 𝑥𝑖𝑛𝑞ℎ , 𝛽𝑖𝑢𝑠𝑗 = 𝑞,ℎ 𝛽¯𝑞𝑗 𝑥𝑖 𝑗𝑞ℎ ,

6

Í 𝑢𝑏 = Í ℎ ¯𝑞 𝛽𝑖𝑛 𝑞,ℎ 𝛽 𝑛 𝑥 𝑖𝑛𝑞ℎ , and 𝜌𝑖 = 𝑚,𝑞,ℎ 𝜌¯ 𝑖 𝑥 𝑖𝑚𝑞ℎ . The disruption scenario does not index 𝑥 𝑖𝑚𝑞ℎ , because it is realized by the environment rather than chosen by the UE. Instead, each variable carries 𝐿 precomputed AoII cost coefficients, one per scenario, so that no AoII trajectory needs to be simulated online (Section IV-A). After infeasible combinations are removed (Section IV-A), the number of binary decision variables is ∑︁ ∑︁ ∑︁ 𝑁𝑥 = |𝒜𝑖 | ≤ 𝑄 𝑚 𝐻𝑖 , (11) 𝑖 ∈𝒰

𝑖 ∈𝒰 𝑚∈ℳ

where 𝒜𝑖 is the admissible set of 𝑢 𝑖 . This number grows linearly in the numbers of UEs, serving nodes, and discrete levels, and quickly exceeds the qubit budget of near-term quantum devices, which motivates the distributed domain decomposition developed next. F. Distributed Hybrid Quantum-Classical Orchestration Model Each local domain D 𝑘 constructs a local binary decision vector x 𝑘 = {𝑥𝑖𝑚𝑞ℎ | 𝑢 𝑖 ∈ 𝒰𝑘 , (𝑚, 𝑞, ℎ) ∈ 𝒜𝑖 , 𝑚 ∈ 𝒮𝑘 ∪ ℬ𝑘 } from a local network state s 𝑘 = [𝚿 𝑘 , V 𝑘 , X 𝑘 , B 𝑘 , E 𝑘 , 𝚵 𝑘 ]. Here, 𝚿 𝑘 contains the precomputed AoII cost functions Ψ𝑖 (·) of the local UEs, V 𝑘 the UE-SAT elevation angles, X 𝑘 each UE’s transition matrix 𝑃𝑖 and AoII budget Δ𝑖𝐼 𝐼,max , B 𝑘 the available bandwidth levels, E 𝑘 the satellite ephemeris data, and 𝚵 𝑘 the disruption scenario set restricted to domain 𝑘. Each local controller assembles a local QUBO targeting worst-case AoII, solves it with a hybrid QAOA solver, and submits its candidate decision to a classical coordinator. The coordinator uses ADMM-based iterations, detailed in Section V, to reconcile the bandwidth of shared SATs and the network-wide worst-case AoII level across domains, and to enforce a globally consistent worst-case AoII bound. The quantum solving latency 𝜏𝑘𝑄 and the consensus latency 𝐶 𝜏 delay the moment at which a new allocation takes effect. We conservatively account forthis overhead by extending each inter-delivery interval by 𝜖𝑖 = (𝜏𝑘𝑄𝑖 +𝜏𝐶 )/𝑇𝑠 slots, where 𝑘 𝑖 ∈ 𝒦 is the domain to which 𝑢 𝑖 belongs. For the combination selected by 𝑢 𝑖 , with inter-delivery interval 𝑌𝑖 (ℓ) under scenario ℓ, the effective worst-case time-average AoII is
Ψ𝑖 𝑌𝑖 (ℓ) + 𝜖 𝑖 𝐼 𝐼 e , (12) Δ𝑖 = max ℓ ∈ℒ 𝑌𝑖 (ℓ) + 𝜖 𝑖 which reduces to maxℓ Ψ𝑖 (𝑌𝑖 (ℓ))/𝑌𝑖 (ℓ) when the orchestration overhead is small relative to the slot duration. IV. P ROBLEM F ORMULATION The objective of SENTINEL is to minimize the worst-case time-average AoII across all monitored UEs under stochastic satellite handover and shadowing uncertainty by jointly optimizing update scheduling, association, and bandwidth
al𝑢𝑏 } location. Let z𝑖 = 𝜌𝑖 , {𝛼𝑖 𝑗 } 𝑗 , {𝜔𝑖𝑛 } 𝑛 , {𝛽𝑖𝑢𝑠𝑗 } 𝑗 , {𝛽𝑖𝑛 𝑛 collect the decisions of 𝑢 𝑖 , where 𝜌𝑖 is its update generation rate, and let 𝑌𝑖 (z𝑖 , 𝝃) denote its inter-delivery interval (in slots) under disruption realization 𝝃 ∈ Ω, as defined in Section III-C. By the renewal-reward argument of Section IIID, the time-average AoII of 𝑢 𝑖 is Ψ𝑖 (𝑌𝑖 )/𝑌𝑖 . We formulate

the robust Value-of-information-aware, uncertAinty-robust, Network-wide Generation, Update-scheduling, Association, and Resource orchestration under Disruption (VANGUARD) problem as
1 ∑︁ Ψ𝑖 𝑌𝑖 (z𝑖 , 𝝃) 𝒫1 : min max {z𝑖 }𝑖 ∈𝒰 𝝃 ∈Ω |𝒰| 𝑌𝑖 (z𝑖 , 𝝃) ∑︁ ∑︁𝑖 ∈𝒰 s.t. C1 : 𝛼𝑖 𝑗 + 𝜔𝑖𝑛 = 1, ∀ 𝑖 ∈ 𝒰, 𝑗 ∈𝒮

C2 :

∑︁

𝑛∈ℬ

𝛼𝑖 𝑗 𝛽𝑖𝑢𝑠𝑗 ≤ 𝐵 𝑠𝑗 , ∀ 𝑗 ∈ 𝒮,

𝑖∈𝒰

C3 :

∑︁

𝑢𝑏 𝜔𝑖𝑛 𝛽𝑖𝑛 ≤ 𝐵𝑛𝑏 , ∀ 𝑛 ∈ ℬ,

𝑖∈𝒰

Ψ𝑖 𝑌𝑖 (z𝑖 , 𝝃) ≤ Δ𝑖𝐼 𝐼,max , ∀ 𝑖 ∈ 𝒰, ∀ 𝝃 ∈ Ω, C4 : 𝑌𝑖 (z𝑖 , 𝝃)
C5 : 𝛼𝑖 𝑗 𝑉𝑖 𝑗 − Θ ≥ 0, ∀ 𝑖 ∈ 𝒰, ∀ 𝑗 ∈ 𝒮, C6 : 𝜌𝑖min ≤ 𝜌𝑖 ≤ 𝜌𝑖max , ∀ 𝑖 ∈ 𝒰, C7 : 𝛼𝑖 𝑗 , 𝜔𝑖𝑛 ∈ {0, 1}, ∀ 𝑖, 𝑗, 𝑛. Here, 𝐵 𝑠𝑗 and 𝐵 𝑛𝑏 are the bandwidth capacities of SAT 𝑠 𝑗 and BS 𝑏 𝑛 , Δ𝑖𝐼 𝐼,max is the AoII budget of 𝑢 𝑖 , 𝜌𝑖min > 0 and 𝜌𝑖max are its minimum required and maximum sustainable update rates, and Θ is the minimum elevation angle. C1 requires each UE to route its updates through exactly one serving node, SAT or BS, in each decision interval. C2 and C3 enforce the bandwidth capacity of each SAT and BS. C4 is the robust correctness constraint, which requires the expected time-average AoII of every UE to stay within its budget under every disruption realization in Ω, including the worst case. In a task-offloading formulation, this role is played by a completion deadline. The constraint is stated in expectation because the instantaneous AoII of a Markov source cannot be bounded deterministically: the source may remain in a mismatched state for an entire inter-delivery interval. C5 allows 𝑢 𝑖 to associate with 𝑠 𝑗 only when 𝑠 𝑗 is above the minimum elevation angle. C6 bounds the update rate of each UE by its freshness requirement and its energy or channelaccess budget. C7 enforces binary association. Problem 𝒫1 is a mixed-integer nonlinear minimax program. Even with a single disruption scenario and fixed update rates, it contains the generalized assignment problem, in which UEs with node-dependent costs and bandwidth demands are assigned to capacity-limited nodes, and is therefore NP-hard. The inner maximization adds a further difficulty. Because Ψ𝑖 (·) is a nonlinear, source-specific function of the interdelivery interval, the realization that maximizes the network AoII is not necessarily the one with the worst channel conditions; it also depends on how the volatility of each monitored source interacts with the outage that the realization induces. In addition, the feasible association set defined by C5 changes at every decision interval as satellites move. A. Robust Binary Reformulation To make 𝒫1 compatible with quantum-assisted binary search, we use the discretization of Section III-E: bandwidth

7

𝑞 levels 𝛽¯𝑚 , update-rate levels 𝜌¯ 𝑖ℎ ∈ [𝜌𝑖min , 𝜌𝑖max ], the scenario set ℒ, and the binary variable 𝑥𝑖𝑚𝑞ℎ in (10). Outage and inter-delivery interval. Each scenario ℓ ∈ ℒ specifies, for every UE-SAT link, a disruption window of 𝑢𝑠 𝑇𝑖dis 𝑗 (ℓ) slots during which the path loss equals 𝜑˜ 𝑖 𝑗 (ℓ) in (6). Let 𝑅𝑖𝑚𝑞 (ℓ) denote the rate in (3) when 𝑢 𝑖 is served by node 𝑞 𝑚 with bandwidth 𝛽¯𝑚 under scenario ℓ. The link is in outage throughout the window if this rate cannot deliver an update within one slot, so the induced outage duration is (  dis (ℓ) I 𝑅 𝑇𝑖𝑚 𝑖𝑚𝑞 (ℓ) 𝑇𝑠 < 𝐷 𝑖 , 𝑚 ∈ 𝒮, 𝜏𝑖𝑚𝑞 (ℓ) = (13) 0, 𝑚 ∈ ℬ,

where BS links are terrestrial and unaffected by satellite disruption. The bandwidth level therefore matters for AoII: a larger allocation can keep the rate above the delivery threshold during shadowing, whereas a complete handover interruption causes an outage at any bandwidth. We assume that a UE whose update fails during an outage transmits a fresh sample as soon as the link is restored. The worst case occurs when the outage begins at a scheduled sampling slot, which gives the inter-delivery interval ' & 1 + 𝜏𝑖𝑚𝑞 (ℓ), (14) 𝑌𝑖𝑚𝑞ℎ (ℓ) = ℎ 𝜌¯ 𝑖 𝑇𝑠 and the corresponding time-average AoII cost coefficient
Ψ𝑖 𝑌𝑖𝑚𝑞ℎ (ℓ) (ℓ ) 𝜓𝑖𝑚𝑞ℎ = , (15) 𝑌𝑖𝑚𝑞ℎ (ℓ) which is precomputed offline for every (𝑖, 𝑚, 𝑞, ℎ, ℓ) from 𝑃𝑖 and the scenario set. Robust pre-elimination. The scenario is realized by the environment rather than chosen by the UE, so it does not index the decision variable. Instead, each variable 𝑥𝑖𝑚𝑞ℎ carries 𝐿 cost coefficients, and every selection is evaluated under all scenarios. We define the admissible set 𝒜𝑖 of 𝑢 𝑖 as the combinations (𝑚, 𝑞, ℎ) for which (i) 𝑚 ∈ ℬ, or 𝑚 ∈ 𝒮 with 𝑉𝑖𝑚 ≥ Θ; (ii) the nominal rate satisfies 𝑅𝑖𝑚𝑞 𝑇𝑠 ≥ 𝐷 𝑖 ; and (ℓ ) (iii) maxℓ ∈ℒ 𝜓𝑖𝑚𝑞ℎ ≤ Δ𝑖𝐼 𝐼,max . Condition (i) enforces C5, and condition (iii) is the discrete counterpart of C4. Because each UE selects exactly one combination, 𝑢 𝑖 satisfies its AoII budget under every scenario if and only if its selected combination belongs to 𝒜𝑖 . The robust budget is therefore enforced by removing variables rather than adding penalty terms, thereby reducing the number of qubits. With these definitions, the quantum-compatible robust binary reformulation of VANGUARD is ∑︁ 1 ∑︁ (ℓ ) 𝒫2 : min max 𝜓𝑖𝑚𝑞ℎ 𝑥 𝑖𝑚𝑞ℎ x ℓ ∈ℒ |𝒰| 𝑖 ∈𝒰 (𝑚,𝑞,ℎ) ∈𝒜𝑖 ∑︁ s.t. D1 : 𝑥𝑖𝑚𝑞ℎ = 1, ∀ 𝑖 ∈ 𝒰, (𝑚,𝑞,ℎ) ∈𝒜𝑖

D2 :

∑︁

∑︁

𝛽¯𝑞𝑗 𝑥 𝑖 𝑗𝑞ℎ ≤ 𝐵 𝑠𝑗 , ∀ 𝑗 ∈ 𝒮,

𝑖 ∈𝒰 ( 𝑗,𝑞,ℎ) ∈𝒜𝑖

D3 :

∑︁

∑︁

𝛽¯𝑛𝑞 𝑥𝑖𝑛𝑞ℎ ≤ 𝐵𝑛𝑏 , ∀ 𝑛 ∈ ℬ,

𝑖 ∈𝒰 (𝑛,𝑞,ℎ) ∈𝒜𝑖

D4 : 𝑥𝑖𝑚𝑞ℎ ∈ {0, 1}, ∀ 𝑖 ∈ 𝒰, (𝑚, 𝑞, ℎ) ∈ 𝒜𝑖 .

Constraint D1 ensures that each UE selects exactly one combination of serving node, bandwidth level, and update-rate level. Constraints D2 and D3 enforce the discrete bandwidth capacity of each SAT and BS, and D4 defines the binary domain. To convert the minimax objective into a standard minimization, we introduce an auxiliary variable 𝜂 representing the worst-case time-average AoII and write the equivalent epigraph form 𝒫3 : min 𝜂 x, 𝜂

s.t. E1 :

1 ∑︁ |𝒰| 𝑖∈𝒰

∑︁

(ℓ ) 𝜓𝑖𝑚𝑞ℎ 𝑥 𝑖𝑚𝑞ℎ ≤ 𝜂,

(𝑚,𝑞,ℎ) ∈𝒜𝑖

∀ ℓ ∈ ℒ, D1–D4. At the optimum, E1 is tight for at least one scenario, so 𝜂 equals the worst-case objective of 𝒫2 . To obtain a fully binary problem, 𝜂 is restricted to a uniform grid of resolution Δ 𝜂 and Í 𝑀𝜂 −1 𝑏 encoded with 𝑀 𝜂 bits as 𝜂 = Δ 𝜂 𝑏=0 2 𝑣 𝑏 , 𝑣 𝑏 ∈ {0, 1}, where 𝑀 𝜂 is chosen so that the grid covers [0, max𝑖 Δ𝑖𝐼 𝐼,max ]. The inequality constraints E1, D2, and D3 are converted into quadratic equality penalties with binary slack variables in Section V. The epigraph form also provides a certificate that does not depend on the solver. For any schedule x returned by the hybrid QAOA procedure, the 𝐿 left-hand sides of E1 can be evaluated exactly, so the worst-case time-average AoII of that schedule over all scenarios in ℒ is known with certainty, whether or not the solver has reached the global optimum. V. P ROPOSED S OLUTION The robust VANGUARD problem 𝒫1 is NP-hard (Section IV). Even Î after the binary reformulation, its feasible set contains up to 𝑖∈𝒰 |𝒜𝑖 | schedules, and solving 𝒫3 centrally on a quantum processor would require 𝑁 𝑥 decision qubits plus the epigraph and slack qubits, which exceeds the capacity of near-term devices. SENTINEL addresses this in three steps: (i) each domain 𝑘 transforms its local sub-problem 𝒫3(𝑘 ) into a QUBO that jointly encodes association, bandwidth allocation, update scheduling, and worst-case epigraph minimization of AoII; (ii) the QUBO is mapped to an Ising Hamiltonian and solved by hybrid QAOA; and (iii) the local solutions are coordinated through an ADMM-based classical consensus step. A. QUBO Formulation A QUBO problem has the standard form min

w⊤ Qw,

(16)

w∈ {0,1} 𝑁

where Q ∈ R 𝑁 × 𝑁 is a symmetric coefficient matrix. For domain 𝑘, the local AoII cost under scenario ℓ is ∑︁ 1 ∑︁ (ℓ ) 𝜓𝑖𝑚𝑞ℎ 𝑥𝑖𝑚𝑞ℎ , (17) 𝑐 𝑘(ℓ ) (x 𝑘 ) = |𝒰| 𝑖∈𝒰 𝑘 (𝑚,𝑞,ℎ) ∈𝒜𝑖

Í so that the network cost in E1 is 𝑘 ∈𝒦 𝑐 𝑘(ℓ ) (x 𝑘 ). The local subproblem 𝒫3(𝑘 ) minimizes a local epigraph variable 𝜂 𝑘 subject

8

to 𝑐 𝑘(ℓ ) (x 𝑘 ) ≤ 𝜂 𝑘 for all ℓ ∈ ℒ and to D1 to D3 restricted Í Í Í to domain 𝑘. Because maxℓ 𝑘 𝑐 𝑘(ℓ ) ≤ 𝑘 maxℓ 𝑐 𝑘(ℓ ) ≤ 𝑘 𝜂 𝑘 , the sum of the local epigraph variables is an upper bound on the network-wide worst-case AoII, with equality when all domains attain their worst case under the same scenario. To cast 𝒫3(𝑘 ) into the form (16), each constraint is converted into a quadratic penalty. An equality constraint ℎ(x) = 0 is penalized as 𝜆 ℎ(x) 2 . An inequality constraint 𝑔(x) ≤ 0 is first written as 𝑔(x) + 𝑠 = 0 with a non-negative slack Í 𝐵−1 𝑏 2 𝑦 𝑏 , 𝑦 𝑏 ∈ {0, 1}, and then penalized as 𝑠 = Δ 𝑏=0 𝜆 (𝑔(x) + 𝑠) 2 . For the penalty to vanish at every feasible point, the slack must be able to represent −𝑔(x) exactly. We (ℓ ) therefore round the cost coefficients 𝜓𝑖𝑚𝑞ℎ /|𝒰| up to integer multiples of the epigraph resolution Δ 𝜂 , which keeps 𝜂 𝑘 a valid 𝑞 upper bound, choose the bandwidth levels 𝛽¯𝑚 and capacities as integer multiples of a resolution Δ𝛽 , set the slack step Δ equal to the resolution of the corresponding constraint, and use 𝐵 = ⌈log2 (𝑔 max /Δ + 1)⌉ bits, where 𝑔 max is the largest value that −𝑔(x) can take. The local epigraph variable is encoded Í 𝑀𝜂 −1 𝑏 as 𝜂 𝑘 = Δ 𝜂 𝑏=0 2 𝑣 𝑏 . Collecting all binary variables of domain 𝑘 into w 𝑘 = (x 𝑘 , v 𝑘 , y 𝑘 ), the unconstrained QUBO objective is 𝐹 (w 𝑘 ) = 𝐹epi + 𝐹assoc + 𝐹cap + 𝐹scen + Γ𝑘 (x 𝑘 ; z 𝑘 , u 𝑘 ),

(18)

where each term is described below. Epigraph objective term. The local epigraph variable enters as a linear term, 𝐹epi = Δ 𝜂

𝑀∑︁ 𝜂 −1

2𝑏 𝑣 𝑏 .

(19)

𝑏=0

Single-association penalty. Constraint D1 requires each UE to select exactly one admissible combination (𝑚, 𝑞, ℎ):

where 𝑠ℓ is the binary-encoded slack for scenario ℓ. This term is where robustness enters the QUBO: each variable 𝑥𝑖𝑚𝑞ℎ appears in all 𝐿 squared terms with its scenario-specific coefficient, so a schedule that performs well under the nominal scenario but poorly under a disruptive one is penalized unless 𝜂 𝑘 rises to cover it. The per-UE AoII budget and the visibility and update-rate limits need no penalty terms, because the corresponding combinations have already been removed from 𝒜𝑖 (Section IV-A). Coordination term. For each shared SAT 𝑗 ∈ 𝒮𝑘sh , the coordinator assigns domain 𝑘 a bandwidth target 𝑧 𝑗 𝑘 and maintains a scaled dual variable 𝑢 𝑗 𝑘 (Section V-D). The local QUBO includes the augmented Lagrangian term
2 𝜚 ∑︁ 𝑏 𝑗 (x 𝑘 ) − 𝑧 𝑗 𝑘 + 𝑢 𝑗 𝑘 , (23) Γ𝑘 (x 𝑘 ; z 𝑘 , u 𝑘 ) = 2 sh 𝑗 ∈𝒮𝑘

where 𝜚 > 0 is the ADMM penalty parameter. Because 𝑏 𝑗 (x 𝑘 ) is linear in x 𝑘 , this term contributes linear and pairwise terms to the QUBO and steers the bandwidth used by domain 𝑘 at each shared SAT toward its target. The matrix Q (𝑘 ) is assembled by collecting the coefficients of all linear and pairwise terms of 𝐹 (w 𝑘 ), with linear coefficients on the diagonal because 𝑤 2 = 𝑤 for binary 𝑤, and pairwise coefficients split equally between the two symmetric off-diagonal entries. On the feasible set, all penalty terms vanish for a suitable choice of slack bits, so 𝐹 (w 𝑘 ) = 𝜂 𝑘 + Γ𝑘 . The penalty weights must be large enough that no infeasible assignment attains a lower value. Proposition 1. Let 𝛿1 = 1, 𝛿2 = 𝛿3 = Δ𝛽 , and 𝛿4 = Δ 𝜂 denote the smallest nonzero residual of the corresponding penalized constraint, let 𝜂max = Δ 𝜂 (2 𝑀𝜂 − 1), and let Γ𝑘max and Γ𝑘min be the largest and smallest values of Γ𝑘 over {0, 1} |x𝑘 | . If

2

∑︁ © ∑︁ ª 𝐹assoc = 𝜆1 𝑥 𝑖𝑚𝑞ℎ − 1® , ­ 𝑖 ∈𝒰𝑘 « (𝑚,𝑞,ℎ) ∈𝒜 𝑘 ¬ 𝑖

𝜂max + Γ𝑘max − Γ𝑘min (20)

where 𝒜𝑖𝑘 contains the combinations in 𝒜𝑖 whose node belongs to 𝒮𝑘 ∪ ℬ𝑘 and 𝜆 1 > 0. Expanding the square 2 yields linear terms, since 𝑥 𝑖𝑚𝑞ℎ = 𝑥 𝑖𝑚𝑞ℎ , and pairwise terms ′ ′ ′ 𝑥𝑖𝑚𝑞ℎ 𝑥𝑖𝑚 𝑞 ℎ between the variables of the same UE. Capacity penalty. Constraints D2 and D3 limit the bandwidth of each SAT and BS: ∑︁
2 𝐹cap = 𝜆2 𝑏 𝑗 (x 𝑘 ) + 𝑠 𝑗 − 𝐵 𝑠𝑗 𝑗 ∈𝒮𝑘o

+ 𝜆3

∑︁

2 𝑏 𝑛 (x 𝑘 ) + 𝑠 𝑛 − 𝐵𝑛𝑏 ,

(21)

𝑛∈ℬ𝑘

Í Í 𝑞 𝑥𝑖𝑚𝑞ℎ is the bandwhere 𝑏 𝑚 (x 𝑘 ) = 𝑖 ∈𝒰𝑘 (𝑚,𝑞,ℎ) ∈𝒜 𝑘 𝛽¯𝑚 𝑖 width used at node 𝑚 by domain 𝑘, and 𝑠 𝑗 and 𝑠 𝑛 are binaryencoded slacks. The first sum runs over the set 𝒮𝑘o of SATs visible only to the domain 𝑘. The capacity of the remaining SATs, collected in 𝒮𝑘sh = 𝒮𝑘 \𝒮𝑘o , is shared with other domains and is handled by the coordination term below. Epigraph scenario penalty. Constraint E1 requires the local AoII cost under every scenario to be at most 𝜂 𝑘 : 2 ∑︁  𝐹scen = 𝜆4 𝑐 𝑘(ℓ ) (x 𝑘 ) + 𝑠ℓ − 𝜂 𝑘 , (22) ℓ ∈ℒ

𝜆𝑙 >

𝛿𝑙2

,

𝑙 = 1, . . . , 4,

(24)

and 𝒫3(𝑘 ) is feasible, then every global minimizer of 𝐹 (w 𝑘 ) is feasible for 𝒫3(𝑘 ) and optimal for the local problem with coordination term Γ𝑘 . Proof. By the choice of grids, the left-hand side of every penalized constraint is an integer multiple of its resolution 𝛿𝑙 . Let w★ be a feasible assignment whose slack bits represent the constraint gaps exactly, so all penalties vanish and 𝐹 (w★) = 𝜂★𝑘 + Γ𝑘 (x★) ≤ 𝜂max + Γ𝑘max . Let w† be an assignment whose x or v part violates some constraint 𝑙. Since the slack is non-negative, it cannot offset a positive violation, so the residual of constraint 𝑙 is at least 𝛿𝑙 in magnitude for every choice of slack bits, and the corresponding penalty is at least 𝜆𝑙 𝛿𝑙2 . Because 𝐹epi ≥ 0 and all other penalties are non-negative, 𝐹 (w† ) ≥ 𝜆𝑙 𝛿𝑙2 + Γ𝑘min > 𝜂max + Γ𝑘max ≥ 𝐹 (w★). Hence, no infeasible assignment is a global minimizer. On the feasible set, 𝐹 = 𝜂 𝑘 + Γ𝑘 , once the slack bits are chosen optimally, so a global minimizer of 𝐹 also minimizes 𝜂 𝑘 + Γ𝑘 over the feasible set. □ The bound (24) is sufficient rather than necessary. Because very large penalty weights compress the relative energy

9

differences among feasible schedules and make the QAOA landscape harder to optimize, in practice, we set each 𝜆𝑙 slightly above this bound. B. Ising Hamiltonian Mapping Quantum processors operate on qubits described by Pauli operators. The local QUBO over w 𝑘 is mapped to an Ising Hamiltonian through the substitution 𝑤𝑎 =

1 − 𝜎𝑎𝑧 , 2

(25)

where 𝑎 indexes all 𝑁ˆ 𝑘 qubits of domain 𝑘, namely the decision qubits 𝑥𝑖𝑚𝑞ℎ , the epigraph qubits 𝑣 𝑏 , and the slack qubits, and 𝜎𝑎𝑧 is the Pauli-𝑍 operator on qubit 𝑎. The number of qubits is ∑︁ ∑︁ ∑︁ ∑︁ 𝑁ˆ 𝑘 = |𝒜𝑖𝑘 | + 𝑀 𝜂 + 𝐵𝑗 + 𝐵𝑛 + 𝐵ℓ , (26) 𝑗 ∈𝒮𝑘

𝑖 ∈𝒰𝑘

𝑛∈ℬ𝑘

ℓ ∈ℒ

where 𝐵 𝑗 , 𝐵 𝑛 , and 𝐵ℓ are the slack bit counts. Substituting (25) into w⊤𝑘 Q (𝑘 ) w 𝑘 and discarding additive constants gives the cost Hamiltonian ∑︁ ∑︁ 𝐻𝐶(𝑘 ) = ℎ 𝑎 𝜎𝑎𝑧 + 𝐽𝑎𝑎′ 𝜎𝑎𝑧 𝜎𝑎𝑧′ , (27) 𝑎

𝑎<𝑎′

with local fields and couplings 1 ∑︁ (𝑘 ) ℎ𝑎 = − 𝑄 ′, 2 𝑎′ 𝑎𝑎

𝐽𝑎𝑎′ =

1 (𝑘 ) 𝑄 ′, 2 𝑎𝑎

(28)

which follow from the symmetry of Q (𝑘 ) . By the Proposition, the ground state of 𝐻𝐶(𝑘 ) encodes an optimal feasible schedule for domain 𝑘. We use the standard transverse-field mixer ∑︁ (𝑘 ) = 𝜎𝑎𝑥 , (29) 𝐻𝑀 𝑎

𝜎𝑎𝑥

where is the Pauli-𝑋 operator on qubit 𝑎. Constraint(𝑘 ) on the one-hot groups preserving XY mixers can replace 𝐻 𝑀 of D1, at the cost of deeper circuits. The depth-𝑝 QAOA state is 𝑝 Ö (𝑘) (𝑘) ˆ |𝜸, 𝜽⟩ = 𝑒 −i𝜃𝑙 𝐻𝑀 𝑒 −i𝛾𝑙 𝐻𝐶 |+⟩ ⊗ 𝑁𝑘 , (30) 𝑙=1 ˆ where |+⟩ ⊗ 𝑁𝑘 is the uniform superposition over all 𝑁ˆ

𝑘 qubits and the variational parameters (𝜸, 𝜽) are optimized classically to minimize E (𝜸, 𝜽) = ⟨𝜸, 𝜽 |𝐻𝐶(𝑘 ) |𝜸, 𝜽⟩. (31)

C. Solution Quality, Certification, and Resource Scaling As 𝑝 → ∞, the optimal QAOA energy converges to the ground-state energy of 𝐻𝐶(𝑘 ) [27], because QAOA can then (𝑘 ) approximate adiabatic evolution from 𝐻 𝑀 to 𝐻𝐶(𝑘 ) [29]. The depth required for a given accuracy, however, depends on the minimum spectral gap along this path, which is generally unknown and may be small. No general approximation guarantee is available for constrained QUBOs of this type at finite depth, so we assess QAOA solution quality empirically in Section VI against an exact minimax reference. The worst-case guarantee of SENTINEL therefore does not rest on QAOA optimality. After the variational parameters are

optimized, the QAOA state is sampled, each measured bitstring is decoded into a schedule x, and schedules that violate D1 to D3 are discarded. For every remaining schedule, the network Í AoII 𝑘 𝑐 𝑘(ℓ ) (x 𝑘 ) is evaluated exactly for all ℓ ∈ ℒ, and the schedule with the smallest maximum is returned. The reported value is therefore the exact worst-case time-average AoII of the returned schedule over ℒ, whether or not the solver has reached the global optimum. The distributed decomposition reduces both the width and the gate count of the QAOA circuits, as the following result shows. (𝑘) Í ˆ −i𝛾𝐻𝐶 Proposition 2. Let 𝑁ˆ = 𝑘 𝑁 𝑘 . The cost layer 𝑒 of domain 𝑘 requires at most 𝑁ˆ 𝑘 ( 𝑁ˆ 𝑘 − 1)/2 two-qubit 𝑍 𝑍 ˆ rotations. Under a balanced partition with 𝑁ˆ 𝑘 = 𝑁/𝐾, the per-domain count is at most 𝑁ˆ 2 /(2𝐾 2 ) and the total over all domains is at most 𝑁ˆ 2 /(2𝐾), compared with up to 𝑁ˆ ( 𝑁ˆ −1)/2 for a centralized Hamiltonian over the same variables. Proof. Each nonzero 𝐽𝑎𝑎′ in (27) requires one 𝑍 𝑍 rotation, and there are at most 𝑁ˆ 𝑘 ( 𝑁ˆ 𝑘 − 1)/2 qubit pairs in domain 𝑘. The bound is attained up to a constant factor because 𝐹scen squares a sum over all local decision variables and the epigraph ˆ bits, which couple every pair of them. Substituting 𝑁ˆ 𝑘 = 𝑁/𝐾 and summing over the 𝐾 domains gives the stated counts. □ Decomposition thus reduces the qubit count per domain by a factor of 𝐾 and the number of two-qubit gates per QAOA layer by up to 𝐾 overall and 𝐾 2 per domain. On hardware with limited connectivity, where dense coupling must be implemented through SWAP networks, this reduction translates directly into shallower compiled circuits. D. SENTINEL Distributed Robust QAOA Algorithm The domains are coupled through the bandwidth of the SATs they share, since D2 limits the total bandwidth that UEs from all domains may use at each SAT. SENTINEL handles this coupling with the sharing form of ADMM [31]. For each shared SAT 𝑠 𝑗 , let 𝒦𝑗 ⊆ 𝒦 denote the 𝐾 𝑗 = |𝒦𝑗 | domains to which it is visible. The coordinator assigns each domain 𝑘 ∈ 𝒦𝑗 a bandwidth target 𝑧 𝑗 𝑘 and maintains a scaled dual variable 𝑢 𝑗 𝑘 , and the local QUBOs include the coordination term (23). SENTINEL iterates between the 𝐾 local hybrid QAOA solvers and the coordinator. At each coordination round 𝑟, the following steps are executed. Local QUBO construction and Ising mapping. Each domain D 𝑘 assembles Q (𝑘 ) from (18) over its admissible variables, using the current targets z 𝑘(𝑟 ) and duals u 𝑘(𝑟 ) , and converts it to 𝐻𝐶(𝑘 ) via (28). The admissible sets 𝒜𝑖 and the (ℓ ) coefficients 𝜓𝑖𝑚𝑞ℎ do not change between rounds and are computed once before the first round. Hybrid QAOA. The depth-𝑝 QAOA circuit is initialized in ˆ |+⟩ ⊗ 𝑁𝑘 , and a classical optimizer (COBYLA) updates (𝜸, 𝜽) to minimize E (𝜸, 𝜽). After convergence, bitstrings are sampled, and the sample with the lowest value of 𝐹 among those satisfying the local constraints is selected as x̂ 𝑘(𝑟+1) . Consensus update. For each shared SAT 𝑠 𝑗 , the coordinator computes the bandwidth 𝑏 𝑗 ( x̂ 𝑘(𝑟+1) ) used by each domain 𝑘 ∈

10

) 𝒦𝑗 and sets 𝑎˜ 𝑗 𝑘 = 𝑏 𝑗 ( x̂ 𝑘(𝑟+1) ) + 𝑢 (𝑟 𝑗 𝑘 . The targets areÍupdated by projecting { 𝑎˜ 𝑗 𝑘 } 𝑘 ∈𝒦𝑗 onto the capacity constraint 𝑘 𝑧 𝑗 𝑘 ≤ 𝐵 𝑠𝑗 , and the duals by the scaled ADMM rule:

n o ∑︁ 1 max 0, 𝑎˜ 𝑗 𝑘 ′ − 𝐵 𝑠𝑗 , 𝐾𝑗 𝑘 ′ ∈𝒦𝑗 (𝑟+1)
(𝑟+1) (𝑟 ) − 𝑧 (𝑟+1) . 𝑢 𝑗 𝑘 = 𝑢 𝑗 𝑘 + 𝑏 𝑗 x̂ 𝑘 𝑗𝑘 𝑧 (𝑟+1) = 𝑎˜ 𝑗 𝑘 − 𝑗𝑘

(32) (33)

If the domains exceed the capacity of a SAT, (32) lowers every target at that SAT by an equal share of the excess, and (33) accumulates the remaining violation, so the next local QUBOs penalize bandwidth use at that SAT more strongly. Incumbent update. The coordinator assembles the network (𝑟+1) schedule x̂ (𝑟+1) = ( x̂1(𝑟+1) , . . . , x̂𝐾 ). If it satisfies D1 to D3, its exact network worst-case AoII ∑︁

𝜂 x̂ (𝑟+1) = max 𝑐 𝑘(ℓ ) x̂ 𝑘(𝑟+1) (34) ℓ ∈ℒ

𝑘 ∈𝒦

is computed, and the schedule replaces the incumbent x★ if 𝜂( x̂ (𝑟+1) ) < 𝜂★. Termination. The algorithm stops when the primal resid
1/2 Í (𝑟+1) ual ) − 𝑧 (𝑟+1) )2 and the dual residual 𝑗,𝑘 (𝑏 𝑗 ( x̂ 𝑘 𝑗𝑘 Í (𝑟+1) (𝑟 ) 2
1/2 𝜚 𝑗,𝑘 (𝑧 𝑗 𝑘 − 𝑧 𝑗 𝑘 ) both fall below 𝜖, or when 𝑅max rounds are reached. If no feasible network schedule has been found by then, a greedy repair moves UEs from overloaded SATs to the admissible combination with the smallest increase in worst-case cost at a node with spare capacity. The incum𝑢𝑏 , together bent is decoded into 𝜌𝑖 , 𝛼𝑖 𝑗 , 𝜔𝑖𝑛 , 𝛽𝑖𝑢𝑠𝑗 , and 𝛽𝑖𝑛 ★ with its certified worst-case AoII 𝜂 and the worst-case Í scenario ℓ★ = arg maxℓ 𝑘 𝑐 𝑘(ℓ ) (x★𝑘). The complete procedure is summarized in Algorithm 1. Convergence. For convex local problems, the sharing form of ADMM converges, with both residuals tending to zero [31]. Here the local problems are binary and therefore non-convex, so ADMM is used as a heuristic and convergence is not guaranteed in general [31]. SENTINEL does not rely on convergence for either feasibility or certification. The incumbent is replaced only by network schedules that satisfy D1-D3, and its worst-case AoII (34) is evaluated exactly. The number of rounds, therefore, affects the quality of the returned schedule but not the validity of its reported worst-case AoII. The penalty parameter 𝜚 is adapted by residual balancing [31], and Section VI reports the observed convergence behavior under varying levels of satellite handover and shadowing disruption. E. Complexity Analysis We analyze the computational cost of SENTINEL across offline precomputation, QUBO assembly, Ising mapping, hybrid QAOA execution, and coordination. Offline precomputation. Evaluating (7) for all 𝑥ˆ ∈ X𝑖 and 𝑠 ≤ 𝑌 max requires the diagonal entries of 𝑃𝑖𝑠 and the vectors 𝑃˜𝑖,𝑎 𝑥ˆ f𝑖, 𝑥ˆ , which cost O (𝑌 max |X𝑖 | 3 ), plus the double sum, which (ℓ ) costs O (|X𝑖 |(𝑌 max ) 2 ). The coefficients 𝜓𝑖𝑚𝑞ℎ then require Í O (𝐿 𝑖 |𝒜𝑖 |) table lookups. This step is performed once for a given set of sources and scenarios and is not repeated in each round.

Algorithm 1: SENTINEL: Distributed Robust QAOA for VANGUARD Input : 𝒰, 𝒮, ℬ, {𝑃𝑖 }, {𝐵 𝑠𝑗 }, {𝐵𝑛𝑏 }, {Δ𝑖𝐼 𝐼,max }, { 𝜌¯ 𝑖ℎ }, 𝑞 { 𝛽¯𝑚 }, Θ, ℒ, 𝑝, 𝜚, 𝜖, 𝑅max , Δ 𝜂 , 𝑀 𝜂 . 𝑢𝑏 ; 𝜂★; Output: x★ decoded into 𝜌𝑖 , 𝛼𝑖 𝑗 , 𝜔𝑖𝑛 , 𝛽𝑖𝑢𝑠𝑗 , 𝛽𝑖𝑛 ★ ℓ . 𝐾 1 Partition the network into 𝐾 domains {D 𝑘 } 𝑘=1 and identify the shared SATs. (ℓ ) 2 Compute Ψ𝑖 (·) via (9), the coefficients 𝜓 𝑖𝑚𝑞ℎ via (15), and the admissible sets 𝒜𝑖 . (0) (0) 𝑠 ★ 3 Initialize 𝑧 𝑗 𝑘 ← 𝐵 𝑗 /𝐾 𝑗 , 𝑢 𝑗 𝑘 ← 0, 𝜂 ← +∞, 𝑟 ← 0. 4 repeat 5 for each domain 𝑘 = 1, . . . , 𝐾 in parallel do 6 Assemble Q (𝑘 ) from (18) with z 𝑘(𝑟 ) , u 𝑘(𝑟 ) . 7 Map Q (𝑘 ) → 𝐻𝐶(𝑘 ) via (28). ˆ 8 Initialize QAOA: |𝜓⟩ ← |+⟩ ⊗ 𝑁𝑘 . 9 repeat 10 Execute the depth-𝑝 QAOA circuit; estimate E (𝜸, 𝜽). 11 Update (𝜸, 𝜽) via COBYLA. until (𝜸, 𝜽) converged; 12 Sample bitstrings; select the best locally feasible sample x̂ 𝑘(𝑟+1) . Update 𝑧 (𝑟+1) via (32) and 𝑢 (𝑟+1) via (33). 𝑗𝑘 𝑗𝑘 (𝑟+1) (𝑟+1) 14 if x̂ satisfies D1–D3 and 𝜂( x̂ ) < 𝜂★ then ★ (𝑟+1) ★ (𝑟+1) x ← x̂ , 𝜂 ← 𝜂( x̂ ). 15 𝑟 ← 𝑟 + 1. until residuals ≤ 𝜖 or 𝑟 ≥ 𝑅max ; ★ 16 if 𝜂 = +∞ then apply greedy repair to x̂ (𝑟 ) and set it as x★. Í (ℓ ) ★ ★ ★ 17 Decode x ; set ℓ = arg maxℓ 𝑘 𝑐 𝑘 (x 𝑘 ). 13

QUBO assembly and Ising mapping. Assembling Q (𝑘 ) requires evaluating all pairwise terms of 𝐹 (w 𝑘 ), and the Ising mapping (28) reads every entry of Q (𝑘 ) . Both steps are classical and cost O ( 𝑁ˆ 𝑘2 ), with 𝑁ˆ 𝑘 given by (26). Hybrid QAOA execution. Each QAOA layer contains at most 𝑁ˆ 𝑘 ( 𝑁ˆ 𝑘 − 1)/2 two-qubit 𝑍 𝑍 rotations and 𝑁ˆ 𝑘 singlequbit rotations (Proposition 2). If the classical optimizer runs for 𝐼QAOA iterations and each energy estimate uses 𝑁shot circuit executions, the cost per domain per round is   𝑘 𝐶QAOA = O 𝐼QAOA 𝑝 𝑁shot 𝑁ˆ 𝑘2 . (35) Í Coordination. The updates (32) and (33) cost O ( 𝑗 𝐾 𝑗 ) per round, and the exact worst-case evaluation (34) costs O (𝐿|𝒰|), since each UE contributes one selected coefficient per scenario. Overall complexity. The local solvers run in parallel, so the wall-clock time of each round is determined by the largest ˆ domain. Under balanced partitioning with 𝑁ˆ 𝑘 ≈ 𝑁/𝐾, the wall-clock cost over 𝑅max rounds is    𝑁ˆ 2 𝐶SENTINEL = O 𝑅max 𝐼QAOA 𝑝 𝑁shot 2 + 𝐿|𝒰| , (36) 𝐾

11

and the total quantum work summed over all domains is O (𝑅max 𝐼QAOA 𝑝 𝑁shot 𝑁ˆ 2 /𝐾). The number of qubits 𝑁ˆ grows linearly with the number of UEs, admissible combinations, and scenarios, since each scenario adds only its slack bits. Comparison with centralized baselines. Table 2 summarizes the comparison. Exhaustive search over 𝒫2 evaluates all Î 𝑖 |𝒜𝑖 | one-hot schedules under 𝐿 scenarios. Exact branchand-bound on the integer linear program 𝒫3 has the same exponential worst case, although it is typically much faster in practice. Centralized QAOA requires all 𝑁ˆ qubits on a single ˆ device. SENTINEL requires only about 𝑁/𝐾 qubits per device and reduces the per-round circuit cost by a factor of up to 𝐾 2 , at the price of up to 𝑅max coordination rounds. Its main advantage is therefore the reduction in qubit count, which is what makes robust VANGUARD instances of realistic size executable on near-term hardware. TABLE 2. Complexity Comparison of Solution Methods Method Exhaustive search (𝒫2 ) Branch-and-bound (𝒫3 ), worst case Centralized robust QAOA SENTINEL (distributed robust QAOA) Threshold policy (non-robust)

Qubits per device N/A N/A 𝑁ˆ 𝑁ˆ /𝐾 N/A

Time complexity
Î O 𝐿 |𝒰| 𝑖 |𝒜𝑖 |
Î O 𝐿 |𝒰| 𝑖 |𝒜𝑖 | O (𝐼QAOA 𝑝 𝑁shot 𝑁ˆ 2 )
O 𝑅max 𝐼QAOA 𝑝 𝑁shot 𝑁ˆ 2 /𝐾 2 O ( |𝒰| | X𝑖 | )

We evaluate SENTINEL through system-level simulation of the satellite-ground integrated topology, with the parameters summarized in Table 3. SENTINEL is compared with three baselines: a Random scheduler, which selects the serving node and transmission slots uniformly at random; an AoII-threshold policy, in which each UE transmits whenever its current AoII exceeds a fixed threshold; and a proximal policy optimization (PPO) scheduler trained with a throughput-oriented reward. All results are averaged over UEs, time slots, and independent random seeds, and are reported with 95% confidence intervals. We first compare SENTINEL with these baselines (Figs. 2–8) and then validate the solution quality of all solvers against an exact minimax reference (Section VI-A).

17.5

AoII threshold PPO Random SENTINEL

Average AoII

15.0 12.5 10.0 7.5 5.0 2.5 0.0

5

10

Number of UEs

15

Parameter Network Number of UEs Number of BSs Number of LEO satellites Satellite altitude UE distribution Number of domains 𝐾 Channel and resources UE transmit power UE / SAT antenna gain BS / satellite carrier frequency BS / satellite system bandwidth 𝑞 Bandwidth levels 𝛽¯𝑚 (𝑄𝑚 = 3) Thermal-noise density Maximum spectral efficiency Minimum satellite elevation angle Status-update packet size 𝐷𝑖 Source and AoII Source states | X𝑖 | Transition matrix 𝑃𝑖

AoII distortion function AoII budget Δ𝑖𝐼 𝐼,max Update periods 1/( 𝜌¯𝑖ℎ 𝑇𝑠 ) (𝐻𝑖 = 4) AoII-threshold baseline

VI. P ERFORMANCE E VALUATION

20.0

TABLE 3. Simulation Parameters

20

Fig. 2. Average AoII versus number of UEs. Fig. 2 shows the time-average AoII as the number of UEs increases from 5 to 20. SENTINEL achieves the lowest AoII at 5 UEs and is comparable to the AoII-threshold policy at 10

Disruption Number of scenarios 𝐿 Shadowing/handover loss Disruption window 𝑇𝑖dis 𝑗 (ℓ ) Disruption probability per SAT link Timing and solver Slot duration 𝑇𝑠 Orchestration interval Simulation duration QAOA depth 𝑝, optimizer, shots Quantum backend ADMM 𝜚, 𝜖 , 𝑅max Edge processing (latency reporting only) Independent runs

Value {5, 10, 15, 20} 2 2 550 km Uniform over a 20 × 20 km2 area 2 (one BS per domain; both SATs shared) 23 dBm 30 dBi / 30 dBi 3.5 GHz / 12 GHz 20 MHz / 50 MHz {2.5, 5, 10} MHz −174 dBm/Hz 4 bit/s/Hz 5◦ 20 kbits 4 ordered severity levels Birth-death chain, self-transition probability ∼ U [0.90, 0.99] per UE 𝑓𝑖 ( 𝑥, 𝑥ˆ ) = | 𝑥 − 𝑥ˆ | 5 {5, 10, 20, 50} slots Threshold = 5, same rate cap 𝜌𝑖max 6 (nominal, mild/severe shadowing, handover of each SAT, joint) 6 or 12 dB / complete link loss {0, 20, 50} slots 10% per orchestration interval 10 ms 100 slots (1 s) 60,000 slots (10 min) 2, COBYLA (200 iterations), 1024 Qiskit Aer simulator 1, 10−2 , 20 500 cycles/bit; BS 120, SAT 60 Gcycles/s 30 random seeds

UEs, whereas at 15 and 20 UEs the threshold policy attains a lower AoII and SENTINEL approaches the Random policy. Unlike schedulers that consider only link quality, SENTINEL selects each UE’s serving node, bandwidth, and update rate based on the AoII cost of its source for every disruption scenario. As a result, volatile sources receive higher update rates, and UEs are steered away from links whose outages would leave the edge estimate wrong for long periods. The AoII-threshold policy achieves a low AoII across all network sizes because each UE observes its own source and transmits only when its current AoII exceeds the threshold, whereas SENTINEL assigns update rates without observing the source state. The Random policy ignores both the source state and the channel, resulting in a higher AoII. PPO yields the highest AoII because its throughput-oriented reward does not account

12

for estimation error; under congestion, it gives low priority to UEs whose estimates are the most inaccurate. AoII threshold PPO Random SENTINEL

2.0

1.0 1.5 0.8 1.0 Delivery ratio

BS delivered E2E latency (ms)

2.5

does not maximize throughput, but it maintains a stable rate while achieving the lowest AoII. This illustrates that throughput and estimation correctness are different objectives: many high-rate transmissions carry values that the edge server already holds and therefore do not reduce AoII.

0.5 0.0

5

10

Number of UEs

15

20

0.0

AoII threshold PPO Random SENTINEL 5

10

Number of UEs

15

20

Fig. 5. Delivery ratio versus number of UEs. Fig. 5 presents the delivery ratio, defined as the fraction of transmitted updates that are successfully delivered. Both SENTINEL and the AoII-threshold policy maintain high delivery ratios at all network sizes. Because both transmit fewer updates, contention is lower and scheduled updates fail less often. SENTINEL additionally avoids associations that are likely to experience outages under the disruption scenarios. Random scheduling delivers roughly half of its updates because it ignores channel quality, resource availability, and disruptions. PPO varies noticeably across network sizes, which suggests that its learned policy is sensitive to changes in topology and load. These results indicate that accounting for estimation correctness also improves reliability by avoiding unnecessary contention and outage-prone links.

AoII threshold PPO Random SENTINEL 0.8

AoII threshold PPO Random SENTINEL

150 Fresh update ratio

Average sum rate (Mbps)

200

0.4 0.2

Fig. 3. Average end-to-end latency of delivered updates versus number of UEs. Fig. 3 compares the average end-to-end latency of successfully delivered updates, including transmission, propagation, and edge processing delay. Edge processing is modeled only to report this latency and is not part of the optimization. SENTINEL achieves the lowest delivered latency across all network sizes because it sends fewer unnecessary updates and assigns each UE to a node with sufficient bandwidth to deliver quickly. The latency of Random scheduling grows steadily with the number of UEs, since more simultaneous transmissions share the same resources and each receives a lower rate. PPO shows a similar increase under heavier load. The AoII-threshold policy keeps latency moderate by suppressing updates, although its latency also grows with the number of UEs. These results show that reducing AoII does not come at the cost of higher delivery latency.

0.6

100

0.6 0.4

50 0.2 0

5

10

Number of UEs

15

20

Fig. 4. Average sum rate versus number of UEs.

0.0

5

10

Number of UEs

15

20

Fig. 6. Informative update ratio versus number of UEs. Fig. 4 compares the average network throughput. PPO achieves the highest sum rate, which is consistent with its throughput-oriented reward: it favors UEs with strong channels and transmits whenever resources allow. Random scheduling also benefits from multi-user diversity as the number of UEs grows. The AoII-threshold policy has the lowest throughput because it deliberately suppresses transmissions. SENTINEL

Fig. 6 shows the informative update ratio, defined as the fraction of delivered updates that change the edge server’s estimate, that is, updates for which 𝑋𝑖 (𝑡 𝑖,𝜅 ) differs from the estimate held just before delivery. Only such updates reduce AoII, so this metric measures how useful each transmission is rather than whether it was delivered. SENTINEL achieves

13

20.0 17.5

Disruption: handover outage

Disruption: handover outage 0.8 0.7

AoII threshold PPO Random SENTINEL

0.6 Fresh update ratio

the highest ratio because it matches each UE’s update rate to the volatility of its source, so that slowly varying sources are not sampled more often than needed. The AoII-threshold policy also performs well, since it transmits only after the estimate has become wrong. Random scheduling has an almost constant ratio because its transmissions are independent of the source state. PPO has the lowest ratio because many of its delivered updates carry values that the edge server already holds. These results show that delivering many packets is not sufficient for correctness-aware monitoring; transmissions should be directed to the updates that actually correct the estimate.

0.5 0.4 0.3 0.2 0.1 0.0

6

8

10

12 14 Number of UEs

16

18

20

Fig. 8. Informative update ratio versus number of UEs under handover outage.

AoII threshold PPO Random SENTINEL

Average AoII

15.0 12.5 10.0 7.5 5.0 2.5 0.0 6

8

10

12 14 Number of UEs

16

18

20

Fig. 7. Average AoII versus number of UEs under handover outage. Fig. 7 compares the average AoII in the handover-outage scenario as the number of UEs increases. SENTINEL maintains a low AoII at small network sizes, indicating that edge estimates remain accurate despite intermittent satellite disruptions. The AoII-threshold policy achieves a comparable AoII at 5 and 10 UEs and a lower AoII at 15 and 20 UEs. This is expected because each UE observes its own source and transmits as soon as its estimate becomes wrong, whereas SENTINEL assigns update rates without observing the source state. The threshold policy, however, relies on a manually chosen threshold and ignores link quality, bandwidth availability, and disruption uncertainty, so it provides no bound on AoII during outages. SENTINEL jointly selects the serving node, bandwidth, and update rate for each UE across all disruption scenarios and provides a certified worst-case AoII for the resulting schedule. PPO yields the highest AoII because its throughput-oriented reward does not account for estimation error. The Random policy performs in between, since it considers neither channel conditions nor the source state. Fig. 8 compares the informative update ratio under the handover outage scenario, that is, the fraction of delivered updates that change the edge server’s estimate. SENTINEL achieves the highest ratio at every network size, so most of its delivered updates correct the estimate rather than repeat a value the server already holds. This follows from matching each UE’s update rate to the volatility of its source and from avoiding links that are likely to fall into outage, so that fewer transmissions are spent on slowly varying sources or lost

during disruption. The AoII-threshold policy also performs well, approaching SENTINEL as the number of UEs grows. Because the threshold rule does not coordinate UEs, several UEs with incorrect estimates may transmit simultaneously and compete for the same resources, and updates delayed by this contention can arrive after the source has returned to the estimated value. PPO and Random have much lower ratios because many of their delivered updates carry values that the edge server already holds. These results indicate that SENTINEL uses network resources more effectively than the baselines when satellite links are disrupted. A. Validation Against the Exact Minimax Optimum To quantify how far each solver is from the robust optimum, we compare it with an exact reference. Enumerating the QUBO of Section V-A is impractical even for small instances: with 3 UEs, 4 serving nodes, and 𝐿 = 10 disruption scenarios, the epigraph and slack encodings already yield 𝑁ˆ = 42 binary variables, most of which are auxiliary. We therefore compute the reference directly from the problem’s combinatorial structure. When each UE uses a fixed bandwidth and update rate, and each serving node can host a limited number of UEs, minimizing the largest scenario-worst-case AoII cost over all UE-node associations is a bottleneck assignment problem. We solve it exactly by searching over the distinct worst-case cost values and testing feasibility at each candidate threshold with a bipartite max-flow computation. The solver required 7.7 ms on an instance with 550 UEs and 15 serving nodes. We cross-validated it against brute-force enumeration of all 𝑀 𝐼 associations, where 𝐼 is the number of UEs and 𝑀 the number of serving nodes, on 500 random instances, with no objective mismatches and no capacity violations. An exact reference is therefore available at every network scale considered in this paper. Table 4 reports the mean optimality gap, defined as the percentage by which the worst-case AoII of each solver exceeds the exact minimax optimum. It covers four settings: smallscale validation (3 to 8 UEs), a network-size sweep (10 to 100 UEs), a disruption-severity sweep from mild to extreme, and a multi-scenario sweep with 𝐿 ∈ {1, 3, 5} disruption scenarios.

14

TABLE 4. Mean Optimality Gap (%) Above the Exact Minimax Optimum Evaluation setting Small-scale validation (3–8 UEs) Network-size sweep (10–100 UEs) Disruption-severity sweep Multi-scenario robustness (𝐿 ∈ {1, 3, 5})

Greedy 27.72 22.65 21.91 40.10

Greedy+LS 2.17 6.93 4.30 16.18

SA 12.49 34.10 55.11 60.91

SENTINEL 2.17 6.93 4.30 16.18

Three observations follow. First, SENTINEL is near-optimal at a small scale, remaining within 2.2% of the exact optimum, and it attains the exact optimum on individual instances with up to 50 UEs in the size and severity sweeps. Second, plain greedy association consistently performs 20% to 40% above the optimum, indicating that disruption-aware minimax association is a hard combinatorial problem for which myopic policies incur substantial AoII penalties. Third, the gap of every solver grows with network size: at 100 UEs, even greedy association with local search remains 23.1% above the optimum, which indicates remaining room for improvement at scale. VII. C ONCLUSION This paper has studied correctness-aware edge orchestration in satellite-ground integrated networks under stochastic handover and shadowing disruption. We formulated the robust VANGUARD problem to minimize the worst-case timeaverage AoII across all monitored edge nodes, and derived a renewal-interval decomposition that expresses the expected AoII of each inter-delivery interval in closed form, thereby reconciling the history dependence of AoII with per-slot combinatorial optimization. The resulting robust binary program was transformed into a QUBO, mapped to an Ising Hamiltonian, and solved by the proposed SENTINEL framework, in which local satellite-ground domains solve subproblems in parallel with hybrid QAOA while an ADMM-based coordinator reconciles the bandwidth of shared satellites. Because every candidate schedule is evaluated exactly under all disruption scenarios, SENTINEL returns a schedule together with a certified worst-case AoII, regardless of whether the quantum solver reaches the global optimum. Simulation results showed that SENTINEL achieves a lower AoII than the learning-based baseline across all network sizes and, in most settings, than random scheduling, along with lower delivered end-to-end latency and a higher informative update ratio. A state-aware threshold policy that observes the source directly attains a comparable AoII in small networks and a lower AoII in the largest networks, but provides no worst-case guarantee. Comparison with an exact minimax reference showed that SENTINEL remains within 2.2% of the optimum at small scale and attains the optimum on individual instances with up to 50 UEs, whereas simulated annealing on the monolithic QUBO degrades sharply as the network grows. The monolithic encoding already requires 42 qubits for three UEs, which motivates the distributed decomposition adopted in SENTINEL. Future work will proceed in three directions. First, the optimality gap across all evaluated methods grows with network size, reaching 23% at 100 UEs, and widens as more disruption

scenarios are simultaneously protected against, which calls for stronger coordination mechanisms at scale. Second, the domain-level QAOA circuits will be executed on quantum hardware under realistic noise and shot budgets to complement the present simulation-based evaluation. Third, we will combine the robust allocation of SENTINEL with state-aware update triggering, so that each UE can transmit as soon as its estimate becomes incorrect while retaining the worst-case guarantee of the robust schedule. R EFERENCES [1] W. Saad, M. Bennis, and M. Chen, “A vision of 6G wireless systems: Applications, trends, technologies, and open research problems,” IEEE Netw., vol. 34, no. 3, pp. 134–142, May 2020. [2] M. Giordani and M. Zorzi, “Non-terrestrial networks in the 6G era: Challenges and opportunities,” IEEE Netw., vol. 35, no. 2, pp. 244–251, Mar. 2021. [3] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in Proc. IEEE INFOCOM, Orlando, FL, USA, Mar. 2012, pp. 2731–2735. [4] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE J. Sel. Areas Commun., vol. 39, no. 5, pp. 1183–1210, May 2021. [5] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” IEEE/ACM Trans. Netw., vol. 28, no. 5, pp. 2215–2228, Oct. 2020. [6] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: An enabler of semantics-empowered communication,” IEEE Trans. Wireless Commun., vol. 22, no. 4, pp. 2621–2635, Apr. 2023. [7] J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, Aug. 2018. [8] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” Found. Trends Netw., vol. 12, no. 3, pp. 162– 259, 2017. [9] E. C. Strinati and S. Barbarossa, “6G networks: Beyond Shannon towards semantic and goal-oriented communications,” Comput. Netw., vol. 190, p. 107930, May 2021. [10] H. Xie, Z. Qin, G. Y. Li, and B.-H. Juang, “Deep learning enabled semantic communication systems,” IEEE Trans. Signal Process., vol. 69, pp. 2663–2675, 2021. [11] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” IEEE Commun. Surveys Tuts., vol. 19, no. 4, pp. 2322–2358, 2017, 4th Quart. [12] J. Liu, Y. Shi, Z. M. Fadlullah, and N. Kato, “Space-air-ground integrated network: A survey,” IEEE Commun. Surveys Tuts., vol. 20, no. 4, pp. 2714–2741, 2018, 4th Quart. [13] N. Kato, Z. M. Fadlullah, F. Tang, B. Mao, S. Tani, A. Okamura, and J. Liu, “Optimizing space-air-ground integrated networks by artificial intelligence,” IEEE Wireless Commun., vol. 26, no. 4, pp. 140–147, Aug. 2019. [14] Z. Zhang, W. Zhang, and F.-H. Tseng, “Satellite mobile edge computing: Improving QoS of high-speed satellite-terrestrial networks using edge computing techniques,” IEEE Netw., vol. 33, no. 1, pp. 70–76, Jan. 2019. [15] N. Cheng, F. Lyu, W. Quan, C. Zhou, H. He, W. Shi, and X. Shen, “Space/aerial-assisted computing offloading for IoT applications: A learning-based approach,” IEEE J. Sel. Areas Commun., vol. 37, no. 5, pp. 1117–1129, May 2019. [16] C. Zhou, W. Wu, H. He, P. Yang, F. Lyu, N. Cheng, and X. Shen, “Deep reinforcement learning for delay-oriented IoT task scheduling in SAGIN,” IEEE Trans. Wireless Commun., vol. 20, no. 2, pp. 911–925, Feb. 2021. [17] 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 Trans. Inf. Theory, vol. 63, no. 11, pp. 7492–7508, Nov. 2017. [18] 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 Trans. Netw., vol. 26, no. 6, pp. 2637– 2650, Dec. 2018. [19] S. Kriouile and M. Assaad, “Minimizing the age of incorrect information for real-time tracking of Markov remote sources,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021, pp. 2978–2983.

15

[20] Y. Chen and A. Ephremides, “Minimizing age of incorrect information for unreliable channel with power constraint,” in Proc. IEEE Global Commun. Conf. (GLOBECOM), Dec. 2021, pp. 1–6. [21] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust Optimization. Princeton, NJ, USA: Princeton Univ. Press, 2009. [22] D. Bertsimas and M. Sim, “The price of robustness,” Oper. Res., vol. 52, no. 1, pp. 35–53, Feb. 2004. [23] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, Feb. 2015. [24] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv:1707.06347, 2017. [25] A. Lucas, “Ising formulations of many NP problems,” Front. Phys., vol. 2, p. 5, Feb. 2014. [26] F. Glover, G. Kochenberger, and Y. Du, “Quantum bridge analytics I: A tutorial on formulating and using QUBO models,” 4OR, vol. 17, no. 4, pp. 335–371, Dec. 2019. [27] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” arXiv:1411.4028, 2014. [28] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, “Variational quantum algorithms,” Nat. Rev. Phys., vol. 3, no. 9, pp. 625–644, Sep. 2021. [29] T. Albash and D. A. Lidar, “Adiabatic quantum computation,” Rev. Mod. Phys., vol. 90, no. 1, p. 015002, Jan. 2018. [30] M. Kim, D. Venturelli, and K. Jamieson, “Leveraging quantum annealing for large MIMO processing in centralized radio access networks,” in Proc. ACM SIGCOMM, Beijing, China, Aug. 2019, pp. 241–255. [31] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.

Related documents

• Distributed Quantum-Assisted Robust AoII Minimization in Satellite-Ground Integrated Edge Networks#1201664
• DRL-Driven Edge-Aware Utility Optimization for Multi-Slice 6G Networks#222573
• LEO Satellite Network Orchestration with Heterogeneous Graph Neural Networks#324849
• Renewables Power the Orbit? Achieving Sustainable Space Edge Computing via QoS-Aware Offloading#155187
• Active Inference-Based Adaptive Routing for Heterogeneous Edge AI Services#120477