政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/147035
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113324/144300 (79%)
Visitors : 51111618      Online Users : 900
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/147035


    Title: 封包管理下的公平排程: 資訊年齡的競爭分析
    Fair Scheduling Under Packet Management: Competitive Analysis of Age of Information
    Authors: 簡辰叡
    Jien, Chen-Rui
    Contributors: 郭桐惟
    簡辰叡
    Jien, Chen-Rui
    Keywords: 資訊年齡
    循環排程
    競爭分析
    Age of information
    Round Robin
    Competitive analysis
    Date: 2023
    Issue Date: 2023-09-01 15:25:04 (UTC+8)
    Abstract: 對行動裝置來說，為了提升服務品質，確保接收訊息的即時性是至關重要的。訊息的即時性通常透過資訊年齡評估。本論文考慮了一個不斷向其終端裝置傳送更新訊息的無線基地站，目標是設計訊息傳輸排程演算法，以最小化所有終端裝置的總體資訊年齡。以往的研究表明，當基地站需要傳送所有訊息時，所有線上演算法都有不好的表現。然而，在許多的應用當中，一旦生成新的訊息後，舊的訊息就可以被丟棄。這種策略被稱為封包管理。我們證明了循環排程在封包管理下對於最小化資訊年齡是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.
    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.
    Description: 碩士
    國立政治大學
    資訊科學系
    110753149
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0110753149
    Data Type: thesis
    Appears in Collections:[Department of Computer Science ] Theses

    Files in This Item:

    File Description SizeFormat
    314901.pdf686KbAdobe PDF20View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback