Age-Optimal Transmission of Rateless Codes in an Erasure Channel

Songtao Feng, Jing Yang

Abstract

In this paper, we examine a status updating system where updates generated by the source are sent to the monitor through an erasure channel. We assume each update consists of $k$ symbols and the symbol erasure in each time slot follows an independent and identically distributed (i.i.d.) Bernoulli process. We assume rateless coding scheme is adopted at the transmitter and an update can be successfully decoded if $k$ coded symbols are received successfully. We assume perfect feedback available at the source, so that it knows whether a transmitted symbol has been erased instantly. Then, at the beginning of each time slot, the source has the choice to start transmitting a new update, or continue with the transmission of the previous update if it is not delivered yet. We adopt the metric "Age of Information" (AoI) to measure the freshness of information at the destination, where the AoI is defined as the age of the latest decoded update at the destination. Our objective is to design an optimal online transmission scheme to minimize the time-average AoI. The transmission decision is based on the instantaneous AoI, the age of the update being transmitted, as well as the number of successfully delivered symbols of the update. We formulate the problem as a Markov Decision Process (MDP) and identify the monotonic threshold structure of the optimal policy. Numerical results corroborate the structural properties of the optimal solution.

Introduction

In real-time monitoring applications—such as tracking stock prices, patient vitals, or autonomous vehicle telemetry—the value of data is intrinsically linked to its "freshness." Traditional metrics like throughput or latency often fail to capture the timeliness of information from the receiver's perspective. To address this, the Age of Information (AoI) metric was introduced, defined as the time elapsed since the most recent update received by the monitor was generated at the source.

Evolution of Age of Information (AoI) over time with successful and failed update transmissions.

This paper investigates the minimization of AoI in a system using rateless codes over an erasure channel. In such a channel, symbols are lost with a certain probability. Rateless codes allow the source to send a continuous stream of symbols until the destination successfully decodes the update (requiring $k$ symbols). This creates a fundamental trade-off: should the source continue an ongoing transmission that has already made some progress, or preempt it to start a brand-new, fresher update?

System Model and MDP Formulation

We model the status-updating system as a discrete-time Markov Decision Process (MDP). Time is slotted, and in each slot, the source transmits one coded symbol. The channel is an i.i.d. Bernoulli process with success probability $p$. The state of the system is represented by the triplet $(\delta, d, l)$:

  • $\delta$: The current AoI at the destination.
  • $d$: The age of the update currently being transmitted.
  • $l$: The number of symbols successfully delivered for the current update.

At the start of each slot, the source decides whether to continue the current transmission or discard it and start a new one. The goal is to find a stationary policy that minimizes the long-term average AoI.

Optimal Policy Structure

Through theoretical analysis using value iteration and inductive proofs, we identify several key properties of the optimal policy:

  1. Zero-Wait Optimality: It is always optimal to transmit in every slot. Idling provides no benefit to AoI minimization.
  2. Threshold Structure: The optimal decision follows a threshold policy based on the progress $l$. For a given destination age $\delta$ and current update age $d$, there exists a threshold $\tau$. If $l < \tau$, the source should preempt the current update; otherwise, it should continue.
  3. Monotonicity: This threshold $\tau$ is non-decreasing with respect to the age of the current update $d$. As an update gets older, it must have achieved more progress to justify its continued transmission. If an old update has made little progress, the "sunk cost" is too high, and it is better to start fresh.
Optimal transmission policy as a function of current update age $d$ and progress $l$ (for $p=0.5, k=10, \delta=20$). Dots indicate the decision to preempt, while crosses indicate continuing.

Key Results and Numerical Validation

Numerical simulations corroborate our theoretical findings. The optimal threshold-based policy significantly outperforms a "persistent" policy, which always completes every update it starts. The performance gain is particularly pronounced in noisy channels (low $p$), where the ability to preempt stale, slow-moving updates is critical for maintaining information freshness. Conversely, in very reliable channels, the incentive to preempt decreases as updates are likely to finish quickly regardless of their current age.

Conclusion

This work characterizes the optimal transmission strategy for rateless codes in status-updating systems. We prove that the optimal policy is a monotonic threshold policy that balances the progress of an update against its increasing age. Future work could extend this model to scenarios with delayed feedback or bursty channel erasures, which would further refine the decision-making process in practical wireless environments.

Summary updated

Abstract

In this paper, we examine a status updating system where updates generated by the source are sent to the monitor through an erasure channel. We assume each update consists of $k$ symbols and the symbol erasure in each time slot follows an independent and identically distributed (i.i.d.) Bernoulli process. We assume rateless coding scheme is adopted at the transmitter and an update can be successfully decoded if $k$ coded symbols are received successfully. We assume perfect feedback available at the source, so that it knows whether a transmitted symbol has been erased instantly. Then, at the beginning of each time slot, the source has the choice to start transmitting a new update, or continue with the transmission of the previous update if it is not delivered yet. We adopt the metric "Age of Information" (AoI) to measure the freshness of information at the destination, where the AoI is defined as the age of the latest decoded update at the destination. Our objective is to design an optimal online transmission scheme to minimize the time-average AoI. The transmission decision is based on the instantaneous AoI, the age of the update being transmitted, as well as the number of successfully delivered symbols of the update. We formulate the problem as a Markov Decision Process (MDP) and identify the monotonic threshold structure of the optimal policy. Numerical results corroborate the structural properties of the optimal solution.
BibTeX
@inproceedings{feng2019age,
  author = {Songtao Feng and Jing Yang},
  title = {{Age-Optimal Transmission of Rateless Codes in an Erasure Channel}},
  booktitle = {ICC},
  year = {2019},
  url = {https://openreview.net/forum?id=EjQWuR2W7o},
}
Figure