The problem of minimizing the Age of Information has been extensively studied in real-time monitoring applications. In this paper, we consider a scheduling problem in which a central monitor decides, at each time slot, whether to schedule a Markovian source to receive new status updates, with the goal of minimizing the Mean Age of Incorrect Information (MAoII). When the source parameters are known, we show that the optimal solution is a threshold-based policy and propose a low-complexity algorithm to determine this optimal threshold. When the source parameters are unknown, the main challenge lies in balancing exploration and exploitation. Specifically, the scheduler must estimate the unknown parameters (exploration) while simultaneously minimizing the MAoII (exploitation). In our model, the monitor can only explore a source by scheduling it. Using a naive greedy approach risks prematurely stopping exploration if, at a given time, the estimated parameters suggest that the optimal action is never to schedule the source. To address this, we develop a novel learning algorithm that overcomes this issue and prove that its regret, compared to a genie-aided solution, grows logarithmically with the time horizon. Finally, we present numerical results to demonstrate the performance of our proposed policy against baseline approaches.

This paper proposes a dual-aspect semantic metric in the context of a cyber-physical system and investigates a scheduling problem where a sensor and a controller communicate over an unreliable channel. In this setting, the sensor observes the state of a source at each time, and according to a scheduling policy should determine whether to transmit a compressed sampled state, transmit the uncompressed sampled state, or remain idle. Upon receiving the transmitted information, the controller executes a control action aimed at stabilizing the system, such that the effectiveness of stabilization depends on the quality of the received sensory information. Our primary objective is to derive an optimal scheduling policy that optimizes system performance subject to resource constraints, when the performance is measured by a dual-aspect metric penalizing both the frequency of transitioning to undesirable states and the continuous duration of remaining in those states. We formulate this problem as a Markov decision process, and prove that the optimal solution is a multi-threshold scheduling policy.

This paper investigates denial-of-service attacks on status updates in a binary networked control system. The physical system is abstracted as a Markovian source with two states: stable and unstable. The source sends status updates over an unreliable wireless channel to a remote controller in the presence of a malicious agent. Upon receiving a new status update, the controller sends back a control signal to stabilize the source if it is in the unstable state. The vulnerability of this system is measured by theage of physical instability—the duration the system remains in the unstable state. Our objective is to design jamming policies for the malicious agent that maximize this measure subject to energy constraints. We first present our results in a single-source scenario, and then extend them to a multi-source scenario. More specifically, we explore: (i) the optimal jamming policy that makes a balance between the system performance degradation and the adversary energy expenditure in a single-source scenario; and (ii) the optimal jamming policy that maximizes the aggregate system performance degradation by selectively jamming a subset of target channels in a multi-source scenario.

In this paper, we investigate denial-of-service attacks against status updating. The target system is modeled by a Markov chain along with an unreliable wireless channel, and the performance of status updating in this system is measured based on two metrics: age of information and age of incorrect information. Our objective is to devise optimal jamming policies that strike a balance between the system's performance deterioration and the adversary's energy expenditure. We model the optimal problem as a Markov decision process, and derive the optimal jamming policy. We prove rigorously that the optimal jamming policy is a threshold policy under both metrics. In addition, we provide a low-complexity algorithm for fining the optimal threshold value of the jamming policy. Our numerical results show that the networked system with the age-of-incorrect-information metric is less sensitive to jamming attacks than with the age-of-information metric.

To accommodate low latency and computation-intensive services, such as the Internet-of-Things (IoT), 5G networks are expected to have cloud and edge computing capabilities. To this end, we consider a generic network setup where devices, performing analytics-related tasks, can partially process a task and offload its remainder to base stations, which can then reroute it to cloud and/or to edge servers. To account for the potentially unpredictable traffic demands and edge network dynamics, we formulate the resource allocation as an online convex optimization problem with service violation constraints and allow limited communication between neighboring nodes. To address the problem, we propose an online distributed (across the nodes) primal-dual algorithm and prove that it achieves sublinear regret and violation; in fact, the achieved bound is of the same order as the best known centralized alternative. Our results are further supported using the publicly available Milano dataset.

The age of Information (AoI) has been introduced to capture the notion of freshness in real-time monitoring applications. However, this metric falls short in many scenarios, especially when quantifying the mismatch between the current and the estimated states. To circumvent this issue, in this paper, we adopt the age of incorrect information metric (AoII) that considers the quantified mismatch between the source and the knowledge at the destination while tracking the impact of freshness. We consider for that a problem where a central entity pulls the information from remote sources that evolve according to a Markovian Process. It selects at each time slot which sources should send their updates. As the scheduler does not know the actual state of the remote sources, it estimates at each time the value of AoII based on the Markovian sources' parameters. Its goal is to keep the time average of the AoII function as small as possible. For that purpose, we develop a scheduling scheme based on Whittle's index policy. To that extent, we use the Lagrangian Relaxation Approach and establish that the dual problem has an optimal threshold policy. Building on that, we compute the expressions of Whittle's indices. Finally, we provide some numerical results to highlight the performance of our derived policy compared to the classical AoI metric.

This paper examines the average age minimization problem where only a fraction of the network users can transmit simultaneously over unreliable channels. Finding the optimal scheduling scheme, in this case, is known to be challenging. Accordingly, the Whittle’s index policy was proposed in the literature as a low-complexity heuristic to the problem. Although simple to implement, characterizing this policy’s performance is recognized to be a notoriously tricky task. In the sequel, we provide a new mathematical approach to establish its optimality in the many-users regime for specific network settings. Contrary to previous works in the literature that use restrictive mathematical assumptions, which can be challenging to verify, our novel approach is based on intricate techniques and it is free of any strong mathematical assumptions. These findings showcase that the Whittle’s index policy has analytically provable asymptotic optimality for the AoI minimization problem. Finally, we lay out numerical results that corroborate our theoretical findings and demonstrate the policy’s notable performance in the many-users regime.

The age of Incorrect Information (AoII) has been introduced to address the shortcomings of the standard Age of information metric (AoI) in real-time monitoring applications. In this paper, we consider the problem of monitoring the states of remote sources that evolve according to a Markovian Process. A central scheduler selects at each time slot which sources should send their updates in such a way to minimize the Mean Age of Incorrect Information (MAoII). The difficulty of the problem lies in the fact that the scheduler cannot know if the information at side of the monitor is correct or not before receiving the updates and it has then to estimate it. We show that the problem can be modeled as a partially Observable Markov Decision Process Problem framework. We develop a new scheduling scheme based on Whittles index policy. The scheduling decision is made by updating a belief value of the states of the sources, which is to the best of our knowledge has not been considered before in the Age of Information area. To that extent, we proceed by using the Lagrangian Relaxation Approach, and prove that the dual problem has an optimal threshold policy. Building on that, we show that the problem is indexable and compute the expressions of the Whittles indices. Finally, we provide some numerical results to highlight the performance of our derived policy compared to the classical AoI metric.

In this article, we consider the average age minimization problem where a central entity schedules M users among the N available users for transmission over unreliable channels. It is well-known that obtaining the optimal policy, in this case, is a difficult task. Accordingly, the Whittle's index policy has been suggested in earlier works as a heuristic for this problem. However, the analysis of its performance remained elusive. In the sequel, we overcome these difficulties and provide rigorous results on its asymptotic optimality in the many-users regime. Specifically, we first establish its optimality in the neighborhood of a specific system's state. Next, we extend our proof to the global case under a recurrence assumption, which we verify numerically. These findings showcase that the Whittle's index policy has analytically provable optimality in the many-users regime for the AoI minimization problem. Finally, numerical results that showcase its performance and corroborate our theoretical findings are presented.

In this paper, we consider the average age minimization problem where a central entity schedules M users among the N available users for transmission over unreliable channels. It is well-known that obtaining the optimal policy, in this case, is out of reach. Accordingly, the Whittle's index policy has been suggested in earlier works as a heuristic for this problem. However, the analysis of its performance remained elusive. In the sequel, we overcome these difficulties and provide rigorous results on its asymptotic optimality in the many-users regime. Specifically, we first establish its optimality in the neighborhood of a specific system's state. Next, we extend our proof to the global case under a recurrence assumption, which we verify numerically. These findings showcase that the Whittle's index policy has analytically provable optimality in the many-users regime for the AoI minimization problem. Finally, numerical results that showcase its performance and corroborate our theoretical findings are presented.

In this paper, we introduce a new performance metric in the framework of status updates that we will refer to as the Age of Incorrect Information (AoII). This new metric deals with the shortcomings of both the Age of Information (AoI) and the conventional error penalty functions as it neatly extends the notion of fresh updates to that of fresh “informative” updates. The word informative in this context refers to updates that bring new and correct information to the monitor side. After properly motivating the new metric, and with the aim of minimizing its average, we formulate a Markov Decision Process (MDP) in a transmitter-receiver pair scenario where packets are sent over an unreliable channel. We show that a simple “always update” policy minimizes the aforementioned average penalty along with the average age and prediction error. We then tackle the general, and more realistic case, where the transmitter cannot surpass a specific power budget. The problem is formulated as a Constrained Markov Decision Process (CMDP) for which we provide a Lagrangian approach to solve. After characterizing the optimal transmission policy of the Lagrangian problem, we provide a rigorous mathematical proof to showcase that a mixture of two Lagrange policies is optimal for the CMDP in question. Equipped with this, we provide a low complexity algorithm that finds the AoII-optimal operating point of the system in the constrained scenario. Lastly, simulation results are laid out to showcase the performance of the proposed policy and highlight the differences with the AoI framework.

In this paper, we consider a queueing system with multiple channels (or servers) and multiple classes of users. We aim at allocating the available channels among the users in such a way to minimize the expected total average queue length of the system. This known scheduling problem falls in the framework of Restless Bandit Problems (RBP) for which an optimal solution is known to be out of reach for the general case. The contributions of this paper are as follows. We rely on the Lagrangian relaxation method to characterize the Whittle index values and to develop an index-based heuristic for the original scheduling problem. The main difficulty lies in the fact that, for some queue states, deriving the Whittle's index requires introducing a new approach which consists in introducing a new expected discounted cost function and deriving the Whittle's index values with respect to the discount parameter β. We then deduce the Whittle's indices for the original problem (i.e. with total average queue length minimization) by taking the limit β → 1. The numerical results provided in this paper show that this policy performs very well and is very close to the optimal solution for high number of users.