AoI-Aware Markov Decision Policies for Caching

Soohyun Park, Soyi Jung, Minseok Choi, Joongheon Kim

TL;DR

This paper introduces a two-stage framework that combines Markov Decision Processes (MDP) and Lyapunov optimization to manage content caching in connected vehicular networks. By intelligently timing data updates at roadside units, the proposed method successfully balances the critical tradeoff between data freshness (Age-of-Information) and network communication costs.

What Problem Does This Paper Address?

Smart and autonomous vehicles rely heavily on real-time data—such as traffic conditions, localized maps, and safety alerts—to make rapid driving decisions. To deliver this data with minimal latency, vehicular networks utilize Roadside Units (RSUs) as edge caches.

However, traffic data is highly time-sensitive. If an RSU serves stale data, it could compromise driving safety. This introduces the concept of Age-of-Information (AoI), a metric that measures the time elapsed since the piece of data was originally generated at the source.

To keep AoI low, a Macro Base Station (MBS) must frequently transmit fresh updates to the RSUs. But here lies the catch: frequent updates consume massive network bandwidth and drive up system costs. The authors tackle this fundamental challenge: How can a network maximize data freshness for fast-moving vehicles while minimizing communication costs and delivery latency?

Methods

The authors propose a two-stage joint cache replacement and content delivery scheme split into two distinct mathematical frameworks:

  1. Cache Management via MDP (MBS to RSUs): The macro base station (MBS) monitors the AoI of all contents across the RSUs. It uses a Markov Decision Process (MDP) to decide which RSU should update what content at any given time slot. The reward function is designed to maximize data freshness (penalizing high AoI) while minimizing the negative reward associated with the network cost of pushing updates.

  2. Service Control via Lyapunov Optimization (RSU to Vehicles): Once the data is at the edge, individual RSUs must decide when to transmit it to User Vehicles (UVs). The authors use Lyapunov optimization to dynamically balance vehicle latency (represented as a queue backlog) against RSU communication costs, ensuring the system remains stable and data is delivered before it expires.

Datasets

The paper does not use real-world datasets. Instead, the authors evaluate their approach using a custom synthetic simulation environment. The setup models a straight road divided into multiple regions covered by RSUs, where content requests from vehicles, initial AoI values, and regional traffic conditions are randomly generated over 1,000 simulation iterations.

Key Insights and Ideas

  • Deconstructed Optimization: Instead of trying to solve a massive, monolithic optimization problem, the authors elegantly split the problem. The MBS handles macro-level data freshness using MDP, while the RSUs handle micro-level delivery latency using Lyapunov drift.
  • Dynamic Thresholding: The Lyapunov control mechanism naturally adapts to extreme network states. If the vehicle request queue is empty, it prioritizes cost-saving by holding off transmissions. If the queue builds up, it automatically shifts priority to clearing the backlog, maintaining a stable equilibrium without requiring manual tuning.

Key Results

The simulation results validate that the proposed joint policy effectively navigates the cost-freshness-latency tradeoff:

  • Strict Freshness Guarantees: The MDP successfully triggers updates before any piece of cached content exceeds its maximum allowable age limit ($A_h^{max}$), as shown in the periodic resets of Content #1 and #2 in the simulation plots.
  • Queue Stability: Compared to a "Cost only" baseline (which ignores latency, causing the queue to explode) and a "Latency only" baseline (which ignores cost), the proposed algorithm successfully caps the vehicle queue backlog to a stable threshold (under 300 units over 1,000 time units).
Fig. 1: Simulation results.

Limitations and Future Work

While the theoretical framework is sound, the evaluation relies on a simplified simulation environment. The model assumes a straight-road topology, uniform file sizes for all content types, and randomized vehicle request patterns.

In reality, vehicular environments feature complex topologies (like urban intersections), highly variable vehicle speeds, and heterogeneous content sizes (e.g., small text alerts vs. large HD map updates). Future work would benefit from validating this framework against realistic traffic mobility traces and exploring how the MDP scales when the number of contents and RSUs grows significantly.

Summary updated

Abstract

We consider a scenario that utilizes road side units (RSUs) as distributed caches in connected vehicular networks. The goal of the use of caches in our scenario is for rapidly providing contents to connected vehicles under various traffic conditions. During this operation, due to the rapidly changed road environment and user mobility, the concept of age-of-information (AoI) is considered for (1) updating the cached information as well as (2) maintaining the freshness of cached information. The frequent updates of cached information maintain the freshness of the information at the expense of network resources. Here, the frequent updates increase the number of data transmissions between RSUs and MBS; and thus, it increases system costs, consequently. Therefore, the tradeoff exists between the AoI of cached information and the system costs. Based on this observation, the proposed algorithm in this paper aims at the system cost reduction which is fundamentally required for content delivery while minimizing the content AoI, based on Markov Decision Process (MDP) and Lyapunov optimization.
BibTeX
@inproceedings{park2022aoi,
  author = {Soohyun Park and Soyi Jung and Minseok Choi and Joongheon Kim},
  title = {{AoI-Aware Markov Decision Policies for Caching}},
  booktitle = {ICDCS},
  year = {2022},
  doi = {10.1109/icdcs54860.2022.00130},
}
Figure