Real-Time Reconstruction of Markov Sources over MPR Channels

Pansee S. Elessawy; Nikolaos Pappas

Source-linked AI summary

Real-Time Reconstruction of Markov Sources over MPR Channels

Pansee S. Elessawy, Nikolaos Pappas

arXiv:2608.27116v1Aug 27, 2026cs.ITcs.NI

TL;DR

The paper asks how to sample and transmit two binary Markov sources over a shared MPR channel so that real-time reconstruction and remote actuation remain accurate under per-sensor constraints. It derives closed-form error expressions and tractable policy searches for independent randomization, alongside a coordinated time-sharing benchmark. The main result is that MPR improves the task-oriented objective only when concurrent reception is reliable for both sources; otherwise, avoiding simultaneous transmissions can be equally effective.

Problem
The paper addresses the limited study of real-time reconstruction and actuation for multiple Markov sources sharing an MPR channel, where update probabilities are coupled across sensors.
Method
It derives closed-form RTE and CAE expressions, reduces independent-policy optimization to finite boundary-branch searches, and analyzes coordinated time sharing over joint actions.
Results
MPR is useful only when simultaneous reception is reliable for both sources; otherwise, policies avoiding simultaneous transmissions can be equally effective.
Takeaways & Limitations
Concurrent decoding should be evaluated through reconstruction and actuation errors, because MPR capability alone does not guarantee a task-level improvement.

Abstract

from arXiv · show

This paper studies the real-time reconstruction and remote actuation of two binary Markov sources over a shared wireless channel with multi-packet reception (MPR). Unlike many existing collision-based formulations that discard simulta- neous transmissions, we exploit MPR and evaluate communica- tion through reconstruction and actuation errors rather than raw delivery rates. We consider two sensors observing the sources and aim to find sampling policies that minimize the weighted real- time reconstruction error (RTE), or equivalently the weighted cost of actuation error (CAE) for the considered binary sources, under per-sensor sampling constraints. We first obtain closed- form expressions for the RTE and CAE in terms of the effective update probabilities. When the sensors randomize independently, the MPR-induced update-rate map becomes bilinear, and the constrained optimization is nonconvex. We exploit the geometry of the achievable update-rate region to show that the search over Pareto-efficient independently randomized policies reduces to a finite set of one-dimensional boundary-branch searches with closed-form candidates. As a benchmark, we allow time sharing among joint sensor actions, and we prove that at most two Pareto- extreme modes are sufficient, and use this benchmark to quantify the loss caused by independent randomization. Numerical results reveal that MPR capability alone is not sufficient; simultaneous decoding improves the task-oriented objective only when con- current reception is reliable for both sources; otherwise, policies that avoid simultaneous transmissions can be equally effective.

I. INTRODUCTION

The paper frames real-time monitoring over shared MPR channels as a task-oriented sampling problem, where reconstruction and actuation quality matter more than raw packet delivery. It develops analytical and optimization tools for independent and coordinated sensor policies, then shows that MPR helps only when concurrent reception is reliable for both sources.

Motivation: Task-oriented communication selects timely, significant updates under limited bandwidth, channel access, and energy rather than transmitting every observation.The motivation spans monitoring, tracking, and remote actuation in cyber-physical and autonomous systems.
System setting: MPR permits multiple simultaneous packets to be decoded, but each source’s update probability depends on both sensors’ sampling decisions.This coupling links physical-layer reception with reconstruction and actuation performance.
Contributions: The paper derives closed-form steady-state RTE and CAE expressions for binary Markov sources under synchronize-or-hold estimation.The effective update probabilities determine the resulting reconstruction and actuation errors.
Contributions: Independent randomized policies yield a sampling-constrained MPR optimization with a bilinear update-rate map and nonconvex structure.The analysis introduces a budget-aware total-success envelope separating dominant-transmitter and cooperative MPR regimes.
Contributions: Pareto-efficient independent policies need not fully randomize source selection, reducing the search to finitely many one-dimensional boundary branches with closed-form candidates.The Pareto-reduction result excludes policies requiring both sensors to randomize between both sources.
Contributions: A coordinated time-sharing benchmark needs at most two Pareto-extreme joint-action modes and quantifies the performance loss from independent randomization.Numerical comparisons show MPR is useful only when simultaneous reception is reliable for both sources.

A. Real-Time Reconstruction Error

The paper models reconstruction through a four-state Markov chain coupling each binary source with its receiver estimate. Under synchronize-or-hold estimation, the steady-state error is characterized by the effective update probability and has source-correlation-dependent curvature.

Markov characterization: Each source and its estimate form a four-state Markov chain whose transitions reflect source evolution followed by successful synchronization or estimate holding.A decoded update synchronizes the estimate with the current source value; otherwise, the previous estimate is retained.
Error metric: The instantaneous reconstruction error is the probability that the source and estimate occupy either mismatch state.The steady-state RTE is obtained from the stationary distribution of this joint process.
Closed-form error: For qi > 0, the two mismatch states have equal stationary probabilities, yielding a closed-form RTE for source i.The equality follows from the stationary balance equations.
Zero-update endpoint: At qi = 0, the exact zero-update process is reducible and its time-average error depends on the initial estimate.The optimization instead uses a continuous-extension value corresponding to the vanishing-positive-update limit.
Monotonicity: The RTE decreases strictly with effective update probability qi.For two sources, the weighted objective is F(q1, q2) = w1E1(q1) + w2E2(q2), with positive source-importance weights.

B. Cost of Actuation Error

For binary Markov sources, the paper defines actuation-error costs over mismatch states and shows that weighted CAE reduces to weighted RTE with modified weights. This equivalence depends on equal steady-state probabilities of the two mismatch states.

CAE assigns potentially asymmetric costs to the two mismatch states between each binary source and its reconstruction.
For binary sources, the only erroneous states are (0,1) and (1,0), whose steady-state probabilities are equal under the considered estimator.
Weighted CAE minimization is equivalent to weighted RTE minimization after replacing the source weights with modified weights.
This CAE–RTE equivalence is specific to binary sources and can fail for multi-state sources or state-dependent sampling policies.
The paper therefore uses weighted RTE as the objective in the remainder of the analysis.

III. SAMPLING-CONSTRAINED INDEPENDENT MPR OPTIMIZATION

The paper formulates independent randomized sampling under per-sensor transmission budgets and maps feasible policies to effective update-rate pairs. Although the policy optimization is generally nonconvex because the map is bilinear, the equivalent update-rate formulation permits Pareto-frontier analysis and a budget-aware total-success envelope.

Each sensor selects silence or one of two source-transmission actions, with total transmission probability constrained by its budget Γ_k.
Independent randomization produces bilinear effective update probabilities q1 and q2, making the policy-space optimization generally nonconvex.
The achievable update-rate region contains all pairs generated by feasible independent policies, and optimizing over this region has the same value as optimizing over policies.
Every global minimizer lies on the Pareto frontier because each source error decreases strictly with its effective update probability.
The total-success envelope is bounded by the maximum of single-sensor and cooperative corner values under the sampling budgets.
The envelope includes contributions from single-sensor transmission and simultaneous same-source or different-source transmissions.

C. Dominant-Transmitter Regimes

When one sensor’s single-transmitter mode dominates the total-success envelope, the Pareto frontier is generated by allocating that sensor’s budget between the two sources. Optimization along this frontier becomes one-dimensional with finitely many closed-form candidates.

If sensor 1 alone attains the largest envelope value, its policy edge generates an achievable Pareto frontier segment.
The sensor-1 frontier segment is generated by u1 = Γ1θ and u2 = Γ1(1−θ), with 0 ≤θ≤1, while sensor 2 remains silent.
When the dominance inequality is strict, every Pareto-efficient update-rate point lies on this single segment.
The sensor-2 dominant case is symmetric to the sensor-1 case.
Along the dominant segment, the weighted objective becomes a one-dimensional function ϕ(θ) of the source-allocation parameter.
The global minimizer is found by evaluating the two endpoints and any unique interior stationary candidate, then selecting the smallest objective value.

E. Cooperative Envelope Regime

The cooperative envelope exploits simultaneous transmissions carrying different sources, but it is active only when concurrent reception is sufficiently reliable relative to budget-adjusted single-sensor modes. The general Pareto analysis also shows that one sensor need not randomize between both sources at efficient policies.

The cooperative envelope uses both sampling budgets and different-source simultaneous transmissions to combine success probabilities a and b.
For full budgets, simultaneous different-source transmission is useful only when a + b exceeds the best single-sensor success probability M.
If a + b < M, the cooperative term cannot be active and an optimal tradeoff can be achieved with one sensor silent.
Under sampling constraints, cooperation is active only when Γ exceeds both budget-adjusted single-sensor terms Γ1s1 and Γ2s2.
When the cooperative conditions fail, the Pareto-relevant operation is generated by one silent sensor whose counterpart allocates its budget between the two sources.
For fixed transmission intensities, a Pareto-efficient independent policy can be chosen so that at least one sensor selects only a single source when transmitting.

B. Boundary Maximization at Fixed Imbalance

At fixed transmission intensities and update-rate imbalance, maximizing total update success can be restricted to the boundary of the conditional source-selection square. Consequently, fully mixed source selection is unnecessary for Pareto-efficient independent policies.

The boundary condition is equivalent to p ∈ {0, 1} or q ∈ {0, 1}, meaning at least one conditional source-selection rule is deterministic.
For fixed t1, t2 and imbalance D = q1 − q2, the feasible selection set is a line segment inside the diamond |m| + |r| ≤ 1.
When a + b = c, all feasible selections with the same imbalance have the same total update success Q.
When a + b > c, the fixed-imbalance objective is strictly convex, so its maximum occurs at an endpoint on the diamond boundary.
Replacing a fully mixed policy by a boundary policy preserves t1, t2, and D while weakly increasing both update probabilities, thereby weakly improving the objective.
The independent-policy search therefore reduces from the two-dimensional selection square to four boundary branches.

E. Branch-Level Pareto Reduction

After restricting independent policies to boundary branches, each fixed-intensity branch reduces to a Pareto-relevant line segment rather than a two-dimensional triangle. The segment optimum has a closed-form finite candidate set.

On each boundary branch and fixed outer intensity, the other sensor’s achievable update rates form the convex hull of three vertex-induced points.
Thus, the other sensor need only randomize between at most two constrained vertex actions on each branch.
Because two vertices lie on one coordinate axis, every triangle point is weakly dominated by a point on the segment joining an axis point A and off-axis point B.
Along a Pareto segment, the minimizer is found by checking both endpoints and, when feasible, one interior stationary candidate.
Applying this segment solution to every branch converts the independent optimization into one-dimensional branch searches over the remaining transmission intensity.
For the p = 1 example, every interior point of the feasible triangle is replaceable by a dominated-free point on A–B, where the branch optimum lies.

A. Coordinated Joint-Action Policy

The coordinated benchmark directly time-shares among joint sensor actions, making effective update probabilities linear in the joint-action distribution. Its achievable update-rate region is a compact convex polygon whose optimum lies on the Pareto frontier.

A coordinated policy assigns probabilities τrs to the nine joint actions formed by silence, transmission of X1, and transmission of X2.
Each deterministic joint action induces an update-rate vector, including simultaneous-transmission outcomes (a, b) and (b, a).
The effective update probabilities q1(τ) and q2(τ) are linear functions of τ, while the weighted objective is F(q1, q2) = w1E1(q1) + w2E2(q2).
The coordinated achievable update-rate region is a compact convex polygon because it is the linear image of a compact feasible polytope.
With positive weights and decreasing error functions, every global minimizer lies on the region’s Pareto frontier.
An optimal coordinated update-rate vector lies at a Pareto-extreme point or on an edge between two adjacent Pareto-extreme points, so at most two modes suffice.

D. Pareto-Edge Search

The coordinated benchmark is solved by a finite search over Pareto vertices and edge candidates. Because independent policies embed into the coordinated class, the benchmark lower-bounds independent performance and defines their gap.

Algorithm 1 constructs the coordinated feasible set and update-rate polygon, extracts Pareto vertices and edges, and evaluates each edge’s feasible stationary candidate.
The Pareto-edge candidate set contains all vertices and every feasible interior stationary candidate, yielding a global minimizer over the coordinated region.
Every feasible independent policy can be represented by a feasible coordinated policy with the same update-rate pair through τrs = a1,r a2,s.
The coordinated optimum is therefore a lower bound on the independent randomized optimum because the coordinated update-rate region contains the independent region.
The independent–coordinated gap measures the performance loss caused by restricting the sensors to independent randomization.
The gap is zero exactly when some coordinated-optimal update-rate point is achievable by a feasible independent randomized policy.

VIII. NUMERICAL RESULTS

The numerical results compare achievable update-rate geometry and policy performance across collision, capture, and MPR regimes. Coordination enlarges the feasible tradeoff, while MPR improves the task objective only when concurrent reception is useful for both sources, particularly at larger budgets.

Update-rate regions: The coordinated update-rate region contains the independent region and reaches a lower objective contour.Because the objective decreases in both update rates, coordination enlarges the feasible update-rate tradeoff.
Budget-aware regimes: The budget-aware envelope separates independent policies into sensor-1 dominant, sensor-2 dominant, and cooperative regimes.With reduced simultaneous-transmission probabilities, Fig. 5 confirms the three cases predicted by the analysis.
Policy comparison: Collision and capture channels do not improve the task-oriented objective over optimized single-active scheduling.Collision overlap yields no useful receptions, while capture provides only one decoded packet during simultaneous transmission.
Policy comparison: At larger sampling budgets, optimized independent MPR and coordinated MPR outperform TDMA, whereas policies remain close at small budgets.Single-active access cannot fully exploit larger sampling opportunities when MPR can use simultaneous transmissions.
Policy comparison: MPR improves the task-oriented objective only when concurrent reception is sufficiently reliable for both sources.The conclusion identifies reliable concurrent reception, especially at larger budgets, as the condition for clear improvement.

APPENDIX A BRANCH-LEVEL UPDATE-RATE EXPRESSIONS

The appendix details how the four boundary branches generate update-rate vectors for the independent randomized optimization. Each branch fixes one sensor as source-deterministic and represents the other sensor’s feasible actions through constrained vertices and affine mappings.

Branch reduction: Theorem 7 reduces the conditional source-selection square to four boundary branches.On each branch, one sensor is source-deterministic while the other may still randomize over its constrained action.
Affine branch geometry: On a fixed branch, the update-rate mapping from the non-deterministic sensor’s action probabilities is affine.The source-deterministic sensor’s policy variables are fixed, making the induced update rates affine in the other sensor’s two action probabilities.
Affine branch geometry: Every feasible non-deterministic policy is a convex combination of the three constrained vertex actions.For sensor 2, the vertices are (0, 0), (Γ2, 0), and (0, Γ2); the analogous vertices apply to sensor 1.
Branch-specific expressions: Branches p = 1 and p = 0 fix sensor 1’s source selection and vary its intensity x over [0, Γ1].The corresponding branch expressions use sensor 2’s constrained vertices to generate update-rate vectors.
Branch-specific expressions: Branches q = 1 and q = 0 fix sensor 2’s source selection and vary its intensity z over [0, Γ2].The q = 0 branch is symmetric to q = 1 after swapping source labels and update-rate coordinates.