Optimal Link Scheduling for Age Minimization in Wireless Systems
- 30 August 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 64 (7), 5381-5394
- https://doi.org/10.1109/tit.2017.2746751
Abstract
Information age is a recently introduced metric to represent the freshness of information in communication systems. We investigate age minimization in a wireless network and propose a novel approach of optimizing the scheduling strategy to deliver all messages as fresh as possible. Specifically, we consider a set of links that share a common channel. The transmitter at each link contains a given number of packets with time stamps from an information source that generated them. We address the link transmission scheduling problem with the objective of minimizing the overall age. This minimum age scheduling problem (MASP) is different from minimizing the time or the delay for delivering the packets in question. We model the MASP mathematically and prove it is NP-hard in general. We also identify tractable cases as well as optimality conditions. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age descent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall age is significantly reduced in comparison to other scheduling strategies.Keywords
Funding Information
- EC Marie Curie Actions Projects MESH-WISE (324515)
- Career LTE (329313)
- Division of Computing and Communication Foundations (CCF-0728966, CCF-1420651)
- Office of Naval Research Global (N000141410107)
This publication has 25 references indexed in Scilit:
- Minimum-Time Link Scheduling for Emptying Wireless Systems: Solution Characterization and Algorithmic FrameworkIEEE Transactions on Information Theory, 2013
- An Investigation on the Nature of Wireless SchedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game TheoryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Complexity in geometric SINRPublished by Association for Computing Machinery (ACM) ,2007
- On the complexity of scheduling in wireless networksPublished by Association for Computing Machinery (ACM) ,2006
- A column generation method for spatial TDMA scheduling in ad hoc networksAd Hoc Networks, 2003
- Resource optimization of spatial TDMA in ad hoc radio networks: a column generation approachPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric GraphsJournal of Algorithms, 1998
- Spatial TDMA: A Collision-Free Multihop Channel Access ProtocolIEEE Transactions on Communications, 1985
- Some complexity results about packet radio networks (Corresp.)IEEE Transactions on Information Theory, 1984