Minimizing Age of Information and Its Peak: Finding Cyclic Schedules With Deletion Search

We study the scheduling problem for a multi-source single-server generate-at-will (GAW) status update system with sources having heterogeneous service times and weights, for which the goal is to minimize the system age of information (AoI), or system peak AoI (PAoI), by employing scheduling algorithms with low runtime complexity. Here, system AoI/PAoI refers to weighted sum of the average AoI/PAoI values of information sources. In particular, we focus on open-loop cyclic schedulers with O(1) runtime complexity, where status updates are scheduled according to a fixed finite transmission pattern whose construction is the main scope of this paper. We first develop an analytical method to obtain the exact average AoI/PAoI of the sources when a transmission pattern is given. Subsequently, we derive the optimum transmission pattern for system AoI in closed form, for the specific case of two sources. For general number of sources, a novel method is proposed based on a deletion search (DS) based algorithm which constructs a pattern whose system PAoI can be brought arbitrarily close to the minimum system PAoI that is attainable using open-loop scheduling. Using another outcome of the same DS-based algorithm, a heuristic scheduler is proposed for system AoI minimization, which is shown to outperform various existing age-agnostic schedulers in the literature, including the insertion search (IS) based algorithm, in the majority of the examples we studied.