论文标题
竞争性算法，以最大程度地减少最大信息年龄
Competitive Algorithms for Minimizing the Maximum Age-of-Information
论文作者
论文摘要
在这篇简短的论文中，我们考虑了为$ n $移动用户设计近乎最佳的竞争日程安排策略的问题，以最大程度地提高所有用户的可用信息的新鲜度。在高速用户的新兴5G-mmwave频道的不可靠性和非平稳性的提示下，我们放弃了无线通道和用户误差的任何统计假设。取而代之的是，我们允许渠道状态和移动性模式由无所不知的对手决定。并不难看到该对抗性模型中相应的吞吐量最大化问题不存在竞争性调度策略。令人惊讶的是，我们表明存在具有有限竞争比率的简单在线分布式调度策略，以最大程度地提高此对抗性模型中信息的新鲜感。此外，我们还证明了拟议的政策是竞争性的最佳选择，最高为$ o（\ ln n）$。
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.
