Design of Centralized Scheduling Policies for Minimizing Average Age of Incorrect Information in Multi-Hop Wireless Networks With Interference

This paper designs and evaluates novel centralized sampling and scheduling policies for minimizing the average age of incorrect information (AoII) for a multi-hop network with interference constraints. The average AoII (AAoII) is a goal-oriented information freshness metric that is relevant for remote estimation. The paper considers a network model in which source nodes monitor and sample processes of interest. The samples are packetized and transmitted to a central node over the multi-hop network, with concurrent transmissions constrained by interference. The central node remotely estimates the source processes from the received packets. The objective of the paper is the design of centralized sampling and scheduling policies, implemented at the central node, for minimizing the AAoII across sources. The policies decide the source sampling times and link transmissions to forward the packetized samples. For practical implementability, the policies utilize only the information available at the central node from the received packets, such as timestamps, and static knowledge of the network topology, interference constraints, and source-process models. In contrast, prior work on scheduling for optimizing information freshness in multi-hop networks has considered metrics such as age of information (AoI), but not AAoII, and has also assumed the availability of real-time information at all nodes for centralized policies. A direct formulation of the policy design problem leads to an intractable partially observable Markov decision process, since the central node does not have real-time information of all nodes. However, we develop restless multi-armed bandit (RMAB) formulations of the multi-hop scheduling problem by considering genie policies that have access to such information. The proposed policies are derived from Whittle index policies for these RMABs. The paper also presents a novel analytical derivation of the Whittle indices. The AAoII performance of the proposed policies for different network topologies and interference constraints is studied using simulations and compared with AAoII of genie policies (which serve as baselines) and heuristic policies (such as randomized and AoI-based policies), demonstrating their utility.