论文标题
安排有多个来源的信息时代最小化信息的年龄
Scheduling to Minimize Age of Information with Multiple Sources
论文作者
论文摘要
我们考虑使用单个服务器的G/g/1排队系统，其中更新从不同的来源到达，可能会有不同的更新之间的发电间时间分布。该服务器最多可以随时发送/服务，具有属于不同来源的更新的可能不同的传输/服务时间。任何来源的信息年龄（AOI）是该来源连续更新的离发时间之间的时间差的函数。每个完全/部分传输的更新都会产生固定的（能源）成本，调度程序的目标是最大程度地减少所有来源信息时代的线性组合和总能源成本。我们提出了一种简单的非首选随机调度算法，该算法随机标记从源到达的更新，以便具有固定概率的传输条件，否则将其丢弃。每当服务器变得免费时，它都会选择一个随机传输的源，并使用另一个固定的概率随机传输，并开始传输所选源的最近标记的更新。通过求解凸面程序，选择了两个概率。拟议算法的竞争比（反向脱机最佳算法）被证明是3加方差之比的最大值和源间源间分布的平均值的最大值。对于几种常见的分布，例如指数，统一和瑞利，竞争比率最多为4。对于先发制化的政策，考虑了G/M/1系统，并且表明非抢先政策具有竞争比率（与先发制的离线最佳算法相对于最多5的优先级离线算法），最大程度地分配了该差异的最大比率和均值的时间分配时间。
We consider a G/G/1 queueing system with a single server, where updates arrive from different sources stochastically with possibly different update inter-generation time distributions. The server can transmit/serve at most one update at any time, with potentially different transmission/service times for updates belonging to distinct sources. The age of information (AoI) of any source is a function of the time difference between the departure time of successive updates of that source. Each fully/partially transmitted update incurs a fixed (energy) cost, and the goal of the scheduler is to minimize the linear combination of the sum of the age of information across all sources and the total energy cost. We propose a simple non-preemptive randomized scheduling algorithm that randomly marks arriving updates from a source to be eligible for transmission with a fixed probability and discards them otherwise. Every time the server becomes free, it chooses a source for transmission randomly with another fixed probability and begins to transmit the most recently marked update of the chosen source. Both the respective probabilities are chosen by solving a convex program. The competitive ratio of the proposed algorithm (against a non-preemptive offline optimal algorithm) is shown to be 3 plus the maximum of the ratio of the variance and the mean of the inter-arrival time distribution of sources. For several common distributions such as exponential, uniform and Rayleigh, the competitive ratio is at most 4. For preemptive policies, a G/M/1 system is considered and a non-preemptive policy is shown to have competitive ratio (against a preemptive offline optimal algorithm) at most 5 plus the maximum of the ratio of the variance and the mean of the inter-arrival time distribution of sources.
