Fair Scheduling Under Packet Management: Competitive Analysis of Age of Information

被引：0

作者：

Jien, Chen-Rui ^{[1
]}

Kuo, Tung-Wei ^{[1
]}

机构：

[1] Natl Chengchi Univ, Dept Comp Sci, Taipei, Taiwan

来源：

ALGORITHMICS OF WIRELESS NETWORKS, ALGOWIN 2023 | 2023年 / 14061卷

关键词：

Age of information; Round Robin; Competitive analysis;

D O I：

10.1007/978-3-031-48882-5_9

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Maintaining up-to-date information is essential for enhancing the quality of service in mobile devices. The freshness of a mobile device is typically evaluated using the Age of Information (AoI) metric. This study considers a system where a Base Station (BS) transmits update messages to its terminals, and the goal is to design message transmission scheduling algorithms that minimize the overall AoI across all terminals. Previous studies have demonstrated that online algorithms perform poorly when the BS is required to send every message. However, in many applications, once a new message is generated, older ones can be discarded. This policy is called packet management. We prove that Round Robin (RR) is O(1)-competitive under packet management. We also generalize RR and consider a broader class of fair scheduling algorithms.

引用

页码：117 / 132

页数：16

共 19 条

[1] Optimal Sampling and Scheduling for Timely Status Updates in Multi-Source Networks [J].