2023/09/21 by Gongpu Chen, Soung Chang Liew · 5 citations
Computer Science · Medicine · #Age of Information Optimization #Distributed Sensor Networks and Detection Algorithms #Cardiovascular Function and Risk Factors
paper · doi:10.1109/tit.2023.3315459
This paper focuses on the information freshness of finite-state Markov sources, using the uncertainty of information (UoI) as the performance metric. Measured by Shannon’s entropy, UoI can capture not only the transition dynamics of the Markov source but also the different evolutions of information quality caused by the different values of the last observation. We consider an information update system with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">M </tex-math></inline-formula> finite-state Markov sources transmitting information to a remote monitor via <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">m </tex-math></inline-formula> communication channels ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">1≤ m < M </tex-math></inline-formula> ). At each time, only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">m </tex-math></inline-formula> Markov sources can be selected to transmit their latest information to the remote monitor. Our goal is to explore the optimal scheduling policy to minimize the sum-UoI of the Markov sources. The problem is formulated as a restless multi-armed bandit (RMAB). We relax the RMAB and then decouple the relaxed problem into <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">M </tex-math></inline-formula> single bandit problems. Importantly, analyzing the single bandit problem provides useful properties with which the relaxed problem reduces to maximizing a concave and piecewise linear function, allowing us to develop a gradient method to solve the relaxed problem and obtain its optimal policy. By rounding up the optimal policy for the relaxed problem, we obtain an index policy for the original RMAB problem. Notably, the proposed index policy is universal in the sense that it applies to general RMABs with bounded cost functions. Moreover, we show that our policy is asymptotically optimal as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">m </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">M </tex-math></inline-formula> tend to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">∞ </tex-math></inline-formula> with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">m/M </tex-math></inline-formula> fixed. In non-asymptotic cases, numerical results demonstrate that our index policy is near-optimal and performs as well as the celebrated Whittle index policy in the problems that are Whittle-indexable. Unlike the Whittle index policy, our index policy does not require “indexability”; the indices can be computed regardless of indexability in the Whittle’s sense. Thus, our index policy is a promising alternative method for the class of RMABs of concern: it can be used when the Whittle index policy is not viable and it performs as well as the Whittle index policy even when the Whittle index policy is viable.