The Age of Incorrect Information for Multi-User Link Scheduling Over Fading Channels

This paper considers a timely scheduling problem where a base station (BS) disseminates status updates to multiple users via a wireless fading channel. The information freshness is captured by age of incorrect information (AoII) metric. The long-term behavior of average AoII is minimized under limited transmission power. Since only partial users can get the updates successfully at one time slot, our problem is formulated as a multi-action multi-armed bandit (MAB) problem. To find the optimal transmission policy, we first divide the original MAB into several sub-problems, obtaining the multi-threshold property of optimal policy and establishing indexability of each sub-problem. Based on that, we propose a novel marginal productivity index (MPI) for our problem, which is proved to be optimal. However, the exact value of our MPI is difficult to calculate due to the enormous iterations in the RVI algorithm. To tackle this, we propose a computational-efficiency algorithm to get indicies and apply a greed strategy to obtain final policy for each user. Compared with Whittle's Index and Max Weight policies under different scenarios, the simulation shows that the proposed policy based on MPIs can achieve significant performance improvement, especially when the network scale is large and transmission power separation interval is small.