Age of Information: Design and Analysis of Optimal Scheduling Algorithms
Abstract: Age of information is a newly proposed metric that captures delay from an application layer perspective. The age measures the amount of time that elapsed from the moment the mostly recently received update was generated until the present time. In this paper, we study an age minimization p...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/112350 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826200995547316224 |
|---|---|
| author | Hsu, Yu-Pin Duan, Lingjie Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Hsu, Yu-Pin Duan, Lingjie Modiano, Eytan H |
| author_sort | Hsu, Yu-Pin |
| collection | MIT |
| description | Abstract:
Age of information is a newly proposed metric that captures delay from an application layer perspective. The age measures the amount of time that elapsed from the moment the mostly recently received update was generated until the present time. In this paper, we study an age minimization problem over a wireless broadcast network with many users, where only one user can be served at a time. We formulate a Markov decision process (MDP) to find dynamic transmission scheduling schemes, with the purpose of minimizing the long-run average age. While showing that an optimal scheduling algorithm for the MDP is a simple stationary switch-type, we propose a sequence of finite-state approximations for our infinite-state MDP and prove its convergence. We then propose both optimal off-line and online scheduling algorithms for the finite-approximate MDPs, depending on knowledge of time-varying arrivals. |
| first_indexed | 2024-09-23T11:45:00Z |
| format | Article |
| id | mit-1721.1/112350 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:45:00Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1123502022-10-01T05:43:46Z Age of Information: Design and Analysis of Optimal Scheduling Algorithms Hsu, Yu-Pin Duan, Lingjie Modiano, Eytan H Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Modiano, Eytan H Abstract: Age of information is a newly proposed metric that captures delay from an application layer perspective. The age measures the amount of time that elapsed from the moment the mostly recently received update was generated until the present time. In this paper, we study an age minimization problem over a wireless broadcast network with many users, where only one user can be served at a time. We formulate a Markov decision process (MDP) to find dynamic transmission scheduling schemes, with the purpose of minimizing the long-run average age. While showing that an optimal scheduling algorithm for the MDP is a simple stationary switch-type, we propose a sequence of finite-state approximations for our infinite-state MDP and prove its convergence. We then propose both optimal off-line and online scheduling algorithms for the finite-approximate MDPs, depending on knowledge of time-varying arrivals. National Science Foundation (U.S.) (award CNS-1701964) 2017-12-01T22:49:19Z 2017-12-01T22:49:19Z 2016-11 Article http://purl.org/eprint/type/ConferencePaper 978-1-5090-4096-4 http://hdl.handle.net/1721.1/112350 Hsu, Yu-Pin, Eytan Modiano, and Lingjie Duan. “Age of Information: Design and Analysis of Optimal Scheduling Algorithms.” 2017 IEEE International Symposium on Information Theory (ISIT) (June 2017). https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/ISIT.2017.8006590 2017 IEEE International Symposium on Information Theory (ISIT) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Prof. Modiano |
| spellingShingle | Hsu, Yu-Pin Duan, Lingjie Modiano, Eytan H Age of Information: Design and Analysis of Optimal Scheduling Algorithms |
| title | Age of Information: Design and Analysis of Optimal Scheduling Algorithms |
| title_full | Age of Information: Design and Analysis of Optimal Scheduling Algorithms |
| title_fullStr | Age of Information: Design and Analysis of Optimal Scheduling Algorithms |
| title_full_unstemmed | Age of Information: Design and Analysis of Optimal Scheduling Algorithms |
| title_short | Age of Information: Design and Analysis of Optimal Scheduling Algorithms |
| title_sort | age of information design and analysis of optimal scheduling algorithms |
| url | http://hdl.handle.net/1721.1/112350 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT hsuyupin ageofinformationdesignandanalysisofoptimalschedulingalgorithms AT duanlingjie ageofinformationdesignandanalysisofoptimalschedulingalgorithms AT modianoeytanh ageofinformationdesignandanalysisofoptimalschedulingalgorithms |