We study how to schedule data sources in a wireless time-sensitive information system with multiple heterogeneous and unreliable channels to minimize the total expected Age-of-Information (AoI). Although one could formulate this problem as a discrete-time Markov Decision Process (MDP), such an approach suffers from the curse of dimensionality and lack of insights. For single-channel systems, prior studies have developed lower-complexity solutions based on the Whittle index. However, Whittle index has not been studied for systems with multiple heterogeneous channels, mainly because indexability is not well defined when there are multiple dual cost values, one for each channel. To overcome this difficulty, we introduce new notions of partial indexability and partial index, which are defined with respect to one channel’s cost, given all other channels’ costs. We then combine the ideas of partial indices and max-weight matching to develop a Sum Weighted Index Matching (SWIM) policy, which iteratively updates the dual costs and partial indices. The proposed policy is shown to be asymptotically optimal in minimizing the total expected AoI, under a technical condition on a global attractor property. We also propose an interpolation-based algorithm to quickly compute (approximate) partial indices in real time. Extensive performance simulations demonstrate that the proposed policy offers significant gains over conventional approaches by achieving a near-optimal AoI. Further, the notion of partial index is of independent interest and could be useful for other problems with multiple heterogeneous resources.

We study a scheduling problem for a base-station transmitting status information to multiple user-equipments (UE) with the goal of minimizing the total expected Age-of-Information (AoI). Such a problem can be formulated as a Restless Multi-Armed Bandit (RMAB) problem and solved asymptotically-optimally by a low-complexity Whittle index policy, if each UE’s sub-problem is Whittle indexable. However, proving Whittle indexability can be highly non-trivial, especially when the value function cannot be derived in closed-form. In particular, this is the case for the AoI minimization problem with stochastic arrivals and unreliable channels, whose Whittle indexability remains an open problem. To overcome this difficulty, we develop a sufficient condition for Whittle indexability based on the notion of active time (AT). Even though the AT condition shares considerable similarity to the Partial Conservation Law (PCL) condition, it is much easier to understand and verify. We then apply our AT condition to the stochastic-arrival unreliable-channel AoI minimization problem and, for the first time in the literature, prove its Whittle indexability. Our proof uses a novel coupling approach to verify the AT condition, which may also be of independent interest to other large-scale RMAB problems.

Motivated by an Age-of-Information (AoI) minimization problem for systems with both fast (but unreliable) and slow (but more reliable) channels, in this paper we are interested in MDPs (Markov Decision Processes) where multiple agents compete for multiple heterogeneous channels. Such an MDP is known to suffer the curse-of-dimensionality when the number of sources is large. Recently, a partial index approach, which generalizes the Whittle index for single-channel systems, has been proposed to decompose such a large-scale MDP into smaller sub-problems, if each sub-problem satisfies the partial indexability and the precise division property. Unfortunately, verifying partial indexability and the precise division property is highly non-trivial. This paper provides a new Active-Time (AT) condition, which ensures the precise-division property (which then implies the partial indexability). Our new AT condition generalizes the AT condition for Whittle indexability in a non-trivial manner, and is much easier to verify for systems with heterogeneous channels. We then apply our AT condition to the fast-slow-channel setting, and establish its partial indexability for the first time in the literature. Our analysis reveals new semi-threshold structures of the optimal policy, and uses a new coupling approach to analyze the corresponding AT condition, which could also be of independent interest. Numerical simulations are provided to verify our theoretical results and to demonstrate the close-to-optimal performance of the partial index policy.