PaperlayerView exact revision on arXiv

Source-linked AI summary

Resource-Constrained Semantic-Aware Remote Estimation with Overlapping Sensor Coverage

Bowen Sun, Nikolaos Pappas

arXiv:2609.07563v1cs.ITmath.IT

TL;DR

The paper studies remote estimation when multiple Markov sources share overlapping, unreliable and delayed sensor links under global and per-sensor transmission budgets. It formulates joint source–sensor scheduling as a constrained Markov decision process and establishes a low-dimensional Lagrangian structure with bounded-size optimal policy mixtures. Numerical results illustrate the value structure, a case requiring randomization, and interactions between budget multipliers.

  • Problem

    Remote estimation must select which source information to transmit and when, while overlapping sensors have different link qualities and both global and per-sensor budgets constrain transmissions.

    Source: §1 · p. 1

  • Method

    The paper formulates joint source–sensor scheduling as a finite average-cost constrained Markov decision process and analyzes its occupation measures and Lagrangian dual.

    Source: §1 · pp. 1–2, §3.4 · p. 4

  • Results

    The K+1 transmission constraints are linearly dependent, leaving K effective transmission costs and an optimal mixture of at most K+1 deterministic policy–recurrent-class components; numerical instances confirm the value structure and a budget requiring randomization.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The structural results provide an exact reference for evaluating scalable approximations to scheduling with overlapping coverage.

    Source: §1.1 · p. 2

    Developing scalable scheduling approximations for overlapping coverage is left to future work.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

We study semantic-aware remote estimation of multiple finite-state Markov sources observed by K sensors with overlapping coverage. The sensors share a time-division multiple-access uplink and differ in transmission reliability, delivery delay, and transmission budget. In each slot, the scheduler jointly selects a source and one of its monitoring sensors, or remains idle, to minimize the long-run average cost of actuation error subject to global and per-sensor transmission-frequency constraints. We formulate this problem as a finite average-cost constrained Markov decision process. We show that the transmission resource functions have rank at most K, although the global constraint may still restrict the feasible region. Consequently, the Lagrangian depends only on K effective transmission costs, and an optimal constrained solution can be represented using at most K+1 deterministic policy-recurrent-class components. We further characterize the piecewise-affine concave Lagrangian value function and derive projected dual subgradient ascent over an explicitly bounded multiplier set. Numerical results illustrate the value-function structure, the need for policy randomization in a representative instance, and the interaction between global and per-sensor transmission budgets.

1 Introduction

The paper formulates semantic-aware scheduling for Markov sources with overlapping sensor coverage, where source–sensor choices must account for state-dependent actuation costs and communication constraints. It establishes structural properties of the constrained problem and positions the resulting exact analysis as a reference for scalable approximations.

1.1 Related work

  • Unlike freshness or general mismatch metrics, cost of actuation error scores mismatches by their actuator consequences, which can differ for distinct state pairs.The related-work discussion distinguishes this model through finite-state Markov sources, asymmetric semantic costs, arbitrary bipartite coverage, and both global and per-sensor budgets.Source: §1 · p. 1, §1.1 · p. 2

1 Introduction

  • The scheduler jointly chooses a source–sensor pair or idles on a shared TDMA uplink, minimizing long-run average actuation error under global and per-sensor transmission-frequency budgets.Sensors covering a source may differ in reliability and delay, so link quality cannot be reduced to a single scalar.Source: §1 · p. 1
  • The K+1 transmission constraints are linearly dependent, reducing the Lagrangian to K effective transmission costs and the optimal mixture to at most K+1 deterministic policy–recurrent-class components.The analysis also accommodates multichain policies, including deterministic schedulers that leave some sources unupdated indefinitely.Source: §1 · pp. 1–2
  • Numerical instances confirm the piecewise-linear value structure and frequency plateaus, show a budget requiring randomization, and exhibit the predicted exchange between global and per-sensor multipliers.The evaluated instances are small enough for exact occupation-measure linear programming.Source: §1 · p. 2

1.1 Related work

  • The exact CMDP analysis provides a reference for evaluating scalable approximations, whose development for overlapping coverage is left to future work.The discussion contrasts the multi-sensor vector-multiplier setting with the single-transmitter scalar-multiplier problem, where a line search suffices.Source: §1.1 · p. 2

2 System Model and Problem Formulation

The model combines finite-state Markov sources, overlapping sensor coverage, delayed and unreliable links, and a shared TDMA channel. It defines actuation error and long-run transmission constraints in a fully observed finite CMDP.

2.1 Network and sensing graph

  • Sensors observe nonempty source subsets whose union covers all sources; the sensing graph represents this relation and permits overlapping coverage.A source monitored by multiple sensors can be updated through links with differing reliability and remaining transmission budgets.Source: §2.1 · p. 2
  • Each source evolves as an independent, irreducible, aperiodic finite-state Markov chain, and the product source chain has the same properties.A source is called slowly evolving when its transition matrix is diagonally dominant, and rapidly evolving otherwise.Source: §2.1 · p. 2
  • Sensor uplinks have independent slot-wise transmission outcomes, sensor-specific success probabilities and fixed delays of zero or one slot, with immediate error-free acknowledgements.The transition kernels and delays are known, and the scheduler uses a reliable local control plane to obtain source states and track receiver estimates.Source: §2.1 · pp. 2–3
  • The centralized scheduler knows current source states and past actions and acknowledgements before choosing at most one sensing edge, or an idle action, per slot.It samples the selected source; successful transmission replaces that source's receiver estimate, while failure retains the previous estimate.Source: §2.1 · pp. 2–3, §2.2 · p. 3

2.2 Reconstruction and cost of actuation error

  • The actuator's estimate incorporates sensor delay, while each source's generally asymmetric, state-dependent mismatch cost is weighted by its importance and charged at the current actuation epoch.A successful update changes only the selected source's receiver estimate; other source estimates remain unchanged.Source: §2.2 · p. 3, §2.3 · p. 3

2.3 State, transitions, and budgets

  • The state transition factors across sources: source states evolve independently, and only the selected source's receiver estimate may change, with update success governed by the chosen sensor.The source transition kernel and sensor success probability determine these respective transitions.Source: §2.3 · p. 3
  • Because at most one sensor transmits per slot, the global and per-sensor transmission indicators are linearly dependent and span a space of dimension at most K.The per-slot action set enforces the TDMA limit; long-run transmission frequencies are constrained by global and sensor-specific budgets.Source: §2.3 · p. 3

2.4 CMDP formulation

  • The hierarchical scheduling problem is a fully observed average-cost CMDP over history-dependent randomized policies, with long-run actuation cost minimized subject to global and per-sensor frequency limits.Stationary Markov deterministic and randomized policies are included within the allowed policy classes.Source: §2.4 · p. 3

3 Structure of the Constrained Optimum

The paper avoids assuming threshold or monotonicity in the joint policy and instead establishes structural guarantees for the constrained optimum, including attainment, a bounded mixture size, and a piecewise-linear dual with K effective transmission costs.

3 Structure of the Constrained Optimum

  • The analysis requires no threshold or monotonicity structure for the optimal joint policy, establishing guarantees that hold despite asymmetric CAE and overlapping coverage.It establishes existence and attainment, bounds the randomized policy’s deterministic components, and characterizes the dual and independent transmission costs.Source: §3 · p. 3

3.1 Strict feasibility and reachability

  • A strictly feasible policy makes the finite MDP communicating, supporting dual analysis and average-cost results independent of the initial state.The state-independent policy activates each sensor with positive probability and satisfies every transmission-frequency constraint with slack.Source: §3.1 · p. 3

3.2 Lagrangian relaxation and existence

  • For each nonnegative multiplier vector, the inner problem has a stationary deterministic optimal policy, and its optimal gain is independent of the initial state.The proof accommodates multichain policies, including deterministic schedulers that stop updating a source and freeze its estimate.Source: §3.2 · p. 4

3.3 The dual is piecewise linear and concave

  • The inner value is concave and piecewise linear, and a constraint-violation vector from an inner-optimal deterministic policy supplies a dual supergradient.One Bellman solve therefore yields both the dual value and a search direction.Source: §3.3 · p. 4

3.4 Existence and the size of the optimal mixture

  • The constrained optimum is attained and independent of the initial state, and an optimal solution needs at most K+1 deterministic policy–recurrent-class components.If the binding constraints have rank r≤K, at most r+1 components are needed.Source: §3.4 · p. 4

3.5 Effective transmission costs and the degenerate dual direction

  • The Lagrangian depends on K effective transmission costs, while the dual is affine along a redundant multiplier direction.Removing that direction does not make coordinatewise search globally optimal because the dual may be nondifferentiable.Source: §3.2 · p. 4, §3.5 · p. 5

3.6 Computing the optimum

  • Strict feasibility bounds the multipliers, and projected subgradient ascent uses constraint violations from inner-optimal policies to update them.Because deterministic policies may induce multichain models, implementation should use multichain policy iteration or the average-cost linear program; a primal solution can then be recovered from the encountered policy–recurrent-class columns.Source: §3.6 · p. 5

4 Numerical Results

The experiments illustrate the piecewise-linear value structure, show a budget that requires policy randomization, and track how a per-sensor budget changes the optimal cost and multipliers.

4.1 Setup

  • Three sources share two sensors: sensor 1 covers all sources with reliability 0.9 and one-slot delay, while faster sensor 2 covers sources 2 and 3 with reliability 0.55 and no delay.The global transmission budget is 0.5, and the per-sensor budgets are 0.35 and 0.30.Source: §4.1 · p. 5

4.2 Piecewise-linear structure and randomization

  • 0.05% duality gap after 200 outer iterations; the inner value is nondecreasing, concave, and piecewise linear, with slopes matching transmission-frequency plateaus, and a budget between plateaus requires randomization.The duality gap is 3.7% after 40 iterations.Source: Figure 2 · p. 5, §4.2 · pp. 5–6

4.3 Effective transmission costs under a per-sensor budget

  • As the sensor-1 budget increases, the exact optimum cost decreases until the budget reaches 0.2, then stays flat while the global and sensor-1 multipliers exchange roles.The sensor-1 multiplier drops from 3.86 to 0 as the global multiplier rises from 0 to 3.86; their effective cost remains continuous.Source: Figure 3 · p. 6, §4.3 · p. 6

5 Conclusion

The paper establishes structural results for semantic-aware remote estimation with overlapping sensor coverage and confirms them numerically.

5 Conclusion

  • An optimal policy can be implemented by randomizing once among at most K+1 stationary deterministic policies.The paper also characterizes the piecewise-linear concave Lagrangian value.Source: §5 · p. 6
  • Numerical results confirm the structural properties and illustrate the projected dual subgradient method’s performance.Source: §5 · p. 6
  • Scalable scheduling for larger systems is left for future work.Source: §5 · p. 6
Loading 2609.07563v1…