對行動裝置來說，為了提升服務品質，確保接收訊息的即時性是至關重要的。訊息的即時性通常透過資訊年齡評估。本論文考慮了一個不斷向其終端裝置傳送更新訊息的無線基地站，目標是設計訊息傳輸排程演算法，以最小化所有終端裝置的總體資訊年齡。以往的研究表明，當基地站需要傳送所有訊息時，所有線上演算法都有不好的表現。然而，在許多的應用當中，一旦生成新的訊息後，舊的訊息就可以被丟棄。這種策略被稱為封包管理。我們證明了循環排程在封包管理下對於最小化資訊年齡是O(1)-競爭的。我們還推廣了循環排程，並考慮了更一般的公平排程演算法。最後，我們證明了一些自然但可能不公平的排程演算法有很差的競爭比。

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. Finally, we show that some natural but potentially unfair scheduling algorithms have poor competitive ratios.

[1] S. Kaul, R. Yates, and M. Gruteser,“Real-time status: How often should one update?,”in 2012 Proceedings IEEE INFOCOM, pp. 2731–2735, IEEE, 2012.
[2] M. Moltafet, M. Leinonen, and M. Codreanu, “On the age of information in multisource queueing models,”IEEE Transactions on Communications, vol. 68, no. 8, pp. 5003–5017, 2020.
[3] N. Pappas, J. Gunnarsson, L. Kratz, M. Kountouris, and V. Angelakis, “Age of information of multiple sources with queue management,”in 2015 IEEE international conference on communications (ICC), pp. 5935–5940, IEEE, 2015.
[4] R. D. Yates and S. K. Kaul,“The age of information: Real-time status updating by multiple sources,”IEEE Transactions on Information Theory, vol. 65, no. 3, pp. 1807–1827, 2018.
[5] S. Farazi, A. G. Klein, and D. R. Brown,“Average age of information in multisource self-preemptive status update systems with packet delivery errors,”in 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 396–400, IEEE, 2019.
[6] E. Najm and E. Telatar,“Status updates in a multi-stream m/g/1/1 preemptive queue,”in IEEE Infocom 2018-Ieee Conference On Computer Communications Workshops (Infocom Wkshps), pp. 124–129, IEEE, 2018.
[7] Y. Sun and B. Cyr,“Sampling for data freshness optimization: Non-linear age functions,”Journal of Communications and Networks, vol. 21, no. 3, pp. 204–219, 2019.
[8] A. M. Bedewy, Y. Sun, S. Kompella, and N. B. Shroff,“Age-optimal sampling and transmission scheduling in multi-source systems,”in Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 121–130, 2019.
[9] A. M. Bedewy, Y. Sun, S. Kompella, and N. B. Shroff,“Optimal sampling and scheduling for timely status updates in multi-source networks,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 4019–4034, 2021.
[10] Y.-P. Hsu, E. Modiano, and L. Duan,“Age of information: Design and analysis of optimal scheduling algorithms,”in 2017 IEEE International Symposium on Information Theory (ISIT), pp. 561–565, IEEE, 2017.
[11] I. Kadota, E. Uysal-Biyikoglu, R. Singh, and E. Modiano,“Minimizing the age of information in broadcast wireless networks,”in 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 844–851, IEEE, 2016.
[12] I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano,“Scheduling policies for minimizing age of information in broadcast wireless networks,”IEEE/ACM Transactions on Networking, vol. 26, no. 6, pp. 2637–2650, 2018.
[13] J. Sun, Z. Jiang, B. Krishnamachari, S. Zhou, and Z. Niu,“Closed-form whittle’s index-enabled random access for timely status update,”IEEE Transactions on Communications, vol. 68, no. 3, pp. 1538–1551, 2019.
[14] Z. Jiang, B. Krishnamachari, X. Zheng, S. Zhou, and Z. Niu,“Timely status update in wireless uplinks: Analytical solutions with asymptotic optimality,”IEEE Internet of Things Journal, vol. 6, no. 2, pp. 3885–3898, 2019.
[15] B. Han, Y. Zhu, Z. Jiang, M. Sun, and H. D. Schotten,“Fairness for freshness: Optimal age of information based ofdma scheduling with minimal knowledge,”IEEE Transactions on Wireless Communications, vol. 20, no. 12, pp. 7903–7919, 2021.
[16] T.-W. Kuo,“Minimum age of information tdma scheduling: Approximation algorithms and hardness results,”IEEE Transactions on Information Theory, vol. 66, no. 12, pp. 7652–7671, 2020.
[17] Q. He, D. Yuan, and A. Ephremides,“Optimal link scheduling for age minimization in wireless systems,”IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 5381–5394, 2017.
[18] T.-W. Kuo,“Competitive analyses of online minimum age of information transmission scheduling,”in IEEE INFOCOM 2022-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1–8, IEEE, 2022.
[19] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus,“Age of information: An introduction and survey,”IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1183–1210, 2021.