學術產出-Theses
Article View/Open
Publication Export
-
題名 封包管理下的公平排程: 資訊年齡的競爭分析
Fair Scheduling Under Packet Management: Competitive Analysis of Age of Information作者 簡辰叡
Jien, Chen-Rui貢獻者 郭桐惟
簡辰叡
Jien, Chen-Rui關鍵詞 資訊年齡
循環排程
競爭分析
Age of information
Round Robin
Competitive analysis日期 2023 上傳時間 1-Sep-2023 15:25:04 (UTC+8) 摘要 對行動裝置來說，為了提升服務品質，確保接收訊息的即時性是至關重要的。訊息的即時性通常透過資訊年齡評估。本論文考慮了一個不斷向其終端裝置傳送更新訊息的無線基地站，目標是設計訊息傳輸排程演算法，以最小化所有終端裝置的總體資訊年齡。以往的研究表明，當基地站需要傳送所有訊息時，所有線上演算法都有不好的表現。然而，在許多的應用當中，一旦生成新的訊息後，舊的訊息就可以被丟棄。這種策略被稱為封包管理。我們證明了循環排程在封包管理下對於最小化資訊年齡是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. 描述 碩士
國立政治大學
資訊科學系
110753149資料來源 http://thesis.lib.nccu.edu.tw/record/#G0110753149 資料類型 thesis dc.contributor.advisor 郭桐惟 zh_TW dc.contributor.author (Authors) 簡辰叡 zh_TW dc.contributor.author (Authors) Jien, Chen-Rui en_US dc.creator (作者) 簡辰叡 zh_TW dc.creator (作者) Jien, Chen-Rui en_US dc.date (日期) 2023 en_US dc.date.accessioned 1-Sep-2023 15:25:04 (UTC+8) - dc.date.available 1-Sep-2023 15:25:04 (UTC+8) - dc.date.issued (上傳時間) 1-Sep-2023 15:25:04 (UTC+8) - dc.identifier (Other Identifiers) G0110753149 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/147035 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 110753149 zh_TW dc.description.abstract (摘要) 對行動裝置來說，為了提升服務品質，確保接收訊息的即時性是至關重要的。訊息的即時性通常透過資訊年齡評估。本論文考慮了一個不斷向其終端裝置傳送更新訊息的無線基地站，目標是設計訊息傳輸排程演算法，以最小化所有終端裝置的總體資訊年齡。以往的研究表明，當基地站需要傳送所有訊息時，所有線上演算法都有不好的表現。然而，在許多的應用當中，一旦生成新的訊息後，舊的訊息就可以被丟棄。這種策略被稱為封包管理。我們證明了循環排程在封包管理下對於最小化資訊年齡是O(1)-競爭的。我們還推廣了循環排程，並考慮了更一般的公平排程演算法。最後，我們證明了一些自然但可能不公平的排程演算法有很差的競爭比。 zh_TW dc.description.abstract (摘要) 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. en_US dc.description.tableofcontents 1 Introduction 11.1 Necessity of Packet Management 31.2 Fair Scheduling Algorithms 41.3 Our Results 42 Definition and System Model 63 Fair Scheduling Algorithms 93.1 Definition of RR 93.2 Definition of Fair Scheduling Algorithms 113.3 Discussion on Some Unfair Algorithms 113.3.1 Proof of Theorem 2 124 Analysis of Fair Scheduling Algorithms 164.1 Objective Function Transformation: From AoI to Pseudo AoI 164.2 Lower Bounds of A(OPT) 214.3 Partition of [t^arr_i + 1, t^dep_i] 234.4 Proof of Eq (∗) 264.5 Proof of Lemma 15 274.5.1 Proof of Claim 18 305 Experimental Result 345.1 Experimental Setting 345.2 Experimental result 355.2.1 Impact of the Number of Long-Lived Terminals 365.2.2 Impact of Short-Lived Terminals’ Inter-Arrival Time 375.2.3 Impact of Capacity 376 Concluding Remarks 39Reference 40 zh_TW dc.format.extent 702494 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0110753149 en_US dc.subject (關鍵詞) 資訊年齡 zh_TW dc.subject (關鍵詞) 循環排程 zh_TW dc.subject (關鍵詞) 競爭分析 zh_TW dc.subject (關鍵詞) Age of information en_US dc.subject (關鍵詞) Round Robin en_US dc.subject (關鍵詞) Competitive analysis en_US dc.title (題名) 封包管理下的公平排程: 資訊年齡的競爭分析 zh_TW dc.title (題名) Fair Scheduling Under Packet Management: Competitive Analysis of Age of Information en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [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. zh_TW
