skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 10:00 PM to 12:00 PM ET on Tuesday, March 25 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Minimizing Age-of-Information in Heterogeneous Multi-Channel Systems: A New Partial-Index Approach
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. 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.  more » « less
Award ID(s):
1717493 1703014
PAR ID:
10300528
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
ACM MobiHoc 2021
Page Range / eLocation ID:
11 to 20
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, ACM)
    In this paper, we study a sampling and transmission scheduling problem for multi-source remote estimation, where a scheduler determines when to take samples from multiple continuous-time Gauss-Markov processes and send the samples over multiple channels to remote estimators. The sample transmission times are i.i.d. across samples and channels. The objective of the scheduler is to minimize the weighted sum of the time-average expected estimation errors of these Gauss-Markov sources. This problem is a continuous-time Restless Multi-armed Bandit (RMAB) problem with a continuous state space. We prove that the bandits are indexable and derive an exact expression of the Whittle index. To the extent of our knowledge, this is the first Whittle index policy for multi-source signal-aware remote estimation of Gauss-Markov processes. We further investigate signal-agnostic remote estimation and develop a Whittle index policy for multi-source Age of Information (AoI) minimization over parallel channels with i.i.d. random transmission times. Our results unite two theoretical frameworks for remote estimation and AoI minimization: threshold-based sampling and Whittle index-based scheduling. In the single-source, single-channel scenario, we demonstrate that the optimal solution to the sampling and scheduling problem can be equivalently expressed as both a threshold-based sampling strategy and a Whittle index-based scheduling policy. Notably, the Whittle index is equal to zero if and only if two conditions are satisfied: (i) the channel is idle, and (ii) the estimation error is precisely equal to the threshold in the threshold-based sampling strategy. Moreover, the methodology employed to derive threshold-based sampling strategies in the single-source, single-channel scenario plays a crucial role in establishing indexability and evaluating the Whittle index in the more intricate multi-source, multi-channel scenario. Our numerical results show that the proposed policy achieves high performance gain over the existing policies when some of the Gauss-Markov processes are highly unstable. 
    more » « less
  2. ; (, IEEE)
    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 MultiArmed Bandit (RMAB) problem and solved asymptoticallyoptimally 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 unreliablechannel 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. 
    more » « less
  3. ; ; (, IEEE International Conference on Communications)
    In this paper, we address the problem of channel allocation for femtocells that share the use of regular macrocell spectrum. The femto basestation (FBS) scheduling problem is formulated in the form of restless multiarmed bandit (RMAB) framework. Our goal is to choose the arms/channels that maximize the total expected discounted reward over infinite horizon while minimizing the induced interference due to channel sharing with macrocell. Without direct observation of true channel state, we use the available macrocell user feedback known as channel quality indicator (CQI). In general, the RMAB problem is P-SPACE hard. We propose a heuristic low complexity indexing policy referred as approximated Whittle index to rank available channels for FBS. Although finding a closed form channel ranking solution typically involve dynamic programming, we show that based on the partial channel information within CQI, there exists a closed form for the channel index. Moreover, we demonstrate the performance advantage of the proposed indexing policy over a myopic policy. 
    more » « less
  4. ; ; ; (, IEEE/ACM Transactions on Networking)
    We study the dynamic cache dimensioning problem, where the objective is to decide how much storage to place in the cache to minimize the total costs with respect to the storage and content delivery latency. We formulate this problem as a Markov decision process, which turns out to be a restless multi-armed bandit problem and is provably hard to solve. For given dimensioning decisions, it is possible to develop solutions based on the celebrated Whittle index policy. However, Whittle index policy has not been studied for dynamic cache dimensioning, mainly because cache dimensioning needs to be repeatedly solved and jointly optimized with content caching. To overcome this difficulty, we propose a low-complexity fluid Whittle index policy, which jointly determines dimensioning and content caching. We show that this policy is asymptotically optimal. We further develop a lightweight reinforcement learning augmented algorithm dubbed fW-UCB when the content request and delivery rates are unavailable. fW-UCB is shown to achieve a sub-linear regret as it fully exploits the structure of the near-optimal fluid Whittle index policy and hence can be easily implemented. Extensive simulations using real traces support our theoretical results. 
    more » « less
  5. ; ; ; (, IEEE International Conference on Computer Communications (IEEE INFOCOM))
    We study the dynamic cache dimensioning problem, where the objective is to decide how much storage to place in the cache to minimize the total costs with respect to the storage and content delivery latency. We formulate this problem as a Markov decision process, which turns out to be a restless multi-armed bandit problem and is provably hard to solve. For given dimensioning decisions, it is possible to develop solutions based on the celebrated Whittle index policy. However, Whittle index policy has not been studied for dynamic cache dimensioning, mainly because cache dimensioning needs to be repeatedly solved and jointly optimized with content caching. To overcome this difficulty, we propose a low-complexity fluid Whittle index policy, which jointly determines dimensioning and content caching. We show that this policy is asymptotically optimal. We further develop a lightweight reinforcement learning augmented algorithm dubbed fW-UCB when the content request and delivery rates are unavailable. fW-UCB is shown to achieve a sub-linear regret as it fully exploits the structure of the near-optimal fluid Whittle index policy and hence can be easily implemented. Extensive simulations using real traces support our theoretical results. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email