Design of scheduling policies for minimizing age of incorrect information in multi-hop wireless networks

The problem of remote estimation over a multi-hop network with interference constraints is considered in this paper. Source nodes in the network sample physical processes of interest. The samples are packetized and transmitted to a single destination node over the network from every source node. The destination node remotely estimates the source processes from the received packets. The sampling times as well as link transmissions to forward the packetized samples are controlled by a centralized policy. The goal-oriented remote-estimation performance of policies is measured by Age of Incorrect Information (AoII). The objective in this paper is the design of centralized sampling and scheduling policies to minimize average AoII across sources. A direct formulation of this scheduling problem leads to a partially observable Markov decision process that is not tractable. However, tractable restless multi-armed bandit (RMAB) formulations of the scheduling problem are obtained. These formulations are obtained under the restriction that at most a single packet from each source is allowed in the network at a time and the scheduler has access to additional information. The paper discusses the indexability of the formulated RMABs and obtains a novel analytical derivation of the Whittle indices. The Whittle indices are used to obtain index policies. Centralized implementable multi-hop sampling and scheduling policies motivated by these index policies are then proposed. The average AoII performance of the proposed policies are evaluated in different scenarios using simulations and compared with benchmark policies. Extensions to networks with general interference models and lossy links are also explored.