论文标题
在任意数据包大小的任意到达模型下，在任意到达模型下的信息年龄最小化
Minimizing Age of Information under Arbitrary Arrival Model with Arbitrary Packet Size
论文作者
论文摘要
我们考虑一个单一的源用途对，其中信息更新在任意时间瞬间到达源。对于每个更新，其大小，即完全传输到目的地所需的服务时间也是任意的。在任何时候，信息的年龄（AOI）等于当前时间和最新更新（源）的到达时间（源）的到达时间（已完全传输到目的地）。 AOI量化了目的地更新（信息）的陈旧性。目的是找到一项因果计划策略，以最大程度地减少AOI的时间平均时间，在这种情况下，任何时间可能的决定是）是否在获得新更新后是否在传输后进行更新，ii）如果没有更新正在传输，则选择要传输的更新（在可用更新中）。 在本文中，我们提出了一种称为srpt $^+$的因果策略，i）i）如果新更新的尺寸较小，则在传输中抢占更新，而ii）如果没有更新正在传输，则开始传输AOI减少的更新，该更新在完全传输后（如果将来不会在将来抢占），则最大的尺寸为最大尺寸。我们使用称为竞争比率的度量标准来表征SRPT $^+$的性能，即因果政策的平均AOI和最佳离线政策的平均AOI（预先知道整个输入），在所有可能的投入方面最大化。我们表明，SRPT $^+$的竞争比率最多为$ 4 $。此外，我们提出了一个更简单的策略，称为srpt $^l $，i）i）如果新更新的尺寸较小，则在传输中抢占更新，ii）如果没有更新正在传输，则开始在最新到达时间的情况下传输更新。我们表明，SRPT $^l $的竞争比率最多为$ 29 $。
We consider a single source-destination pair, where information updates arrive at the source at arbitrary time instants. For each update, its size, i.e. the service time required for complete transmission to the destination, is also arbitrary. At any time, age of information (AoI) is equal to the difference between the current time, and the arrival time of the latest update (at the source) that has been completely transmitted (to the destination). AoI quantifies the staleness of the update (information) at the destination. The goal is to find a causal scheduling policy that minimizes the time average of AoI, where the possible decisions at any time are i) whether to preempt the update under transmission upon arrival of a new update, and ii) if no update is under transmission, then choose which update to transmit (among the available updates). In this paper, we propose a causal policy called SRPT$^+$ that at each time, i) preempts the update under transmission if a new update arrives with a smaller size, and ii) if no update is under transmission, then begins to transmit the update for which the ratio of the reduction in AoI upon complete transmission (if not preempted in future) and the remaining size, is maximum. We characterize the performance of SRPT$^+$ using the metric called the competitive ratio, i.e. the ratio of the average AoI of causal policy and the average AoI of an optimal offline policy (that knows the entire input in advance), maximized over all possible inputs. We show that the competitive ratio of SRPT$^+$ is at most $4$. Further, we propose a simpler policy called SRPT$^L$, that i) preempts the update under transmission if a new update arrives with a smaller size, and ii) if no update is under transmission, then begins to transmit the update with the latest arrival time. We show that the competitive ratio of SRPT$^L$ is at most $29$.
