Minimizing AoI in Mobile Edge Computing: Nested Index Policy with Preemptive and Non-preemptive Structure

Ning Yang, Yibo Liu, Shuo Chen, Meng Zhang, Haijun ZhangarXiv 2025 · DOI · arXiv

Introduction

In modern Internet of Things (IoT) applications and autonomous driving, the timeliness of data is paramount. Information freshness is often measured by the Age of Information (AoI), defined as the time elapsed since the most recent update was generated. In Mobile Edge Computing (MEC) environments, minimizing AoI is challenging due to stochastic computation times, heterogeneous server capabilities, and the complexity of scheduling across multiple users.

System Architecture

The researchers consider a multi-user MEC system where various tasks (e.g., sensor data, traffic monitoring, industrial automation) are offloaded from users to edge nodes for processing.

System model for multi-user MEC task scheduling.

The system must decide which tasks to offload and which server to utilize, balancing the urgency of data freshness against the costs and constraints of the edge infrastructure. This involves managing a "real-world" messiness where multiple users compete for resources across multiple servers with varying capabilities.

The Nested Index Policy Framework

To address the "curse of dimensionality" inherent in large-scale scheduling, the authors model the problem as a Restless Multi-Arm Bandit (RMAB). In an RMAB, the state of each "arm" (user/task) can change even when it isn't being scheduled. The core innovation is a Nested Index Policy based on a multi-layer Markov Decision Process (MDP).

Multi-layer MDP and Indexability

The system state is decomposed into layers to allow for granular decision-making:

  • Layer 1: Represents users who aren't currently executing a task.
  • Layer 2: Represents users with tasks currently in progress.

By extending Whittle’s Index—a value representing the "urgency" of scheduling a specific task—into a nested version, the policy accounts for server-specific costs and state transitions across these layers. The authors rigorously proved "intra-indexability," ensuring that the index remains a reliable decision tool as server costs vary.

Preemptive vs. Non-preemptive Scheduling

A key strength of this framework is its universality. It can handle both preemptive and non-preemptive task structures by adjusting state transitions within the MDP. This flexibility is critical for different application requirements.

Comparison of control flows for preemptive and non-preemptive AoI management.
  • Preemptive Scheduling: Allows a fresh incoming task to interrupt and replace a task currently in progress. This is highly effective for minimizing AoI but may not be suitable for all data types.
  • Non-preemptive Scheduling: Requires a task to be completed once started to ensure data integrity, though it may lead to higher AoI if newer updates arrive during processing.

Key Results and Performance

Numerical simulations mimicking a complex MEC environment with 50 users and heterogeneous servers demonstrated the policy's superiority over standard benchmarks like Max-Age Matching (MAMP) and Max-Age Reducing (MARP).

  • Optimality Gap Reduction: The Nested Index Policy reduced the gap to the theoretical lower bound by 25.43% in non-preemptive scenarios and by a significant 61.84% in preemptive scenarios.
  • Scalability: The policy exhibits asymptotic optimality, meaning its performance converges to the theoretical best as the number of users and servers increases, making it suitable for large-scale IoT deployments.
  • Computational Efficiency: Unlike complex reinforcement learning models, the nested index can often be calculated using closed-form expressions, resulting in much lower computational overhead.

Conclusion

This research provides a robust, scalable framework for managing data freshness in MEC. By unifying preemptive and non-preemptive scheduling under a single nested index policy, it offers a practical solution for diverse IoT ecosystems. Future work may explore incorporating energy constraints and collaborative scheduling between edge servers to further optimize performance in dynamic environments.

Summary updated

Abstract

Mobile Edge Computing (MEC) leverages computational heterogeneity between mobile devices and edge nodes to enable real-time applications requiring high information freshness. The Age-of-Information (AoI) metric serves as a crucial evaluator of information timeliness in such systems. Addressing AoI minimization in multi-user MEC environments presents significant challenges due to stochastic computing times. In this paper, we consider multiple users offloading tasks to heterogeneous edge servers in an MEC system, focusing on preemptive and non-preemptive task scheduling mechanisms. The problem is first reformulated as a Restless Multi-Arm Bandit (RMAB) problem, with a multi-layer Markov Decision Process (MDP) framework established to characterize AoI dynamics in the MEC system. Based on the multi-layer MDP, we propose a nested index framework and design a nested index policy with provably asymptotic optimality. This establishes a theoretical framework adaptable to various scheduling mechanisms, achieving efficient optimization through state stratification and index design in both preemptive and non-preemptive modes. Finally, the closed-form of the nested index is derived, facilitating performance trade-offs between computational complexity and accuracy while ensuring the universal applicability of the nested index policy across both scheduling modes. The experimental results show that in non-preemptive scheduling, compared with the benchmark method, the optimality gap is reduced by 25.43%, while in preemptive scheduling, the gap has reduced by 61.84%. As the system scale increases, it asymptotically converges in two scheduling modes and especially provides near-optimal performance in non-preemptive structure.
BibTeX
@misc{yang2025minimizing,
  author = {Ning Yang and Yibo Liu and Shuo Chen and Meng Zhang and Haijun Zhang},
  title = {{Minimizing AoI in Mobile Edge Computing: Nested Index Policy with Preemptive and Non-preemptive Structure}},
  year = {2025},
  eprint = {2508.20564},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.20564},
}
Figure