Competitive Algorithms for Minimizing the Maximum Age-of-Information

2020/05/12 by Rajarshi Bhattacharjee, Abhishek Sinha, Bhattacharjee, Rajarshi +1 · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Performance (cs.PF) #cs.IT #cs.PF #math.IT

paper · pdf · doi:10.48550/arxiv.2005.05873

Submitted to the workshop Mathematical performance Modeling and Analysis (MAMA) 2020

arxiv created 2020/05/12 · arxiv updated 2020/05/13

Abstract

In this short paper, we consider the problem of designing a near-optimal competitive scheduling policy for N mobile users, to maximize the freshness of available information uniformly across all users. Prompted by the unreliability and non-stationarity of the emerging 5G-mmWave channels for high-speed users, we forego of any statistical assumptions of the wireless channels and user-mobility. Instead, we allow the channel states and the mobility patterns to be dictated by an omniscient adversary. It is not difficult to see that no competitive scheduling policy can exist for the corresponding throughput-maximization problem in this adversarial model. Surprisingly, we show that there exists a simple online distributed scheduling policy with a finite competitive ratio for maximizing the freshness of information in this adversarial model. Moreover, we also prove that the proposed policy is competitively optimal up to an O(ln N) factor.

Cited by

• Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning

Related

• Optimizing Age-of-Information in Adversarial and Stochastic Environments
• Fundamental Limits of Age-of-Information in Stationary and Non-stationary Environments
• Optimizing Age-of-Information in Adversarial Environments with Channel State Information
• Distributed Scheduling Algorithms for Optimizing Information Freshness in Wireless Networks
• Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks