Future Internet-of-Things (IoT) applications will increasingly rely on the exchange of delay sensitive information for monitoring and control. Application domains such as autonomous vehicles, command and control systems, industrial control, virtual reality, and sensor networks, heavily rely upon the distribution of time-critical information. Age of Information (AoI) is a recently proposed performance metric that captures the freshness of the information from the perspective of the application. AoI measures the time that elapsed from the moment that the most recently received packet was generated to the present time.
The goal of this project is to extend the Age-of-Information framework to the wireless network setting. In particular, we propose to extend this theory from the simple and abstract queueing models to realistic wireless network models, taking into account the effects of wireless interference, transmission scheduling, and multi-hop routing. We will consider single-hop networks, such as LTE or WiFi; multi-hop networks such as sensor networks; and mobile ad-hoc networks.
Our goal is to understand the impact of network topology, node mobility, interference and channel reliability on AoI, and to develop network control mechanisms that minimize AoI under different wireless network settings. We propose to progressively extend the AoI framework to the wireless setting: Starting with simple single-hop networks and extending to mobile multi-hop networks. Our research agenda includes the following tasks:
- Single-Hop Wireless Networks: We propose to analyze AoI in single-hop wireless networks, and devise transmission scheduling schemes for minimizing AoI.
- Multi-Hop Networks: We propose to develop routing and scheduling schemes for minimizing AoI in multi-hop wireless networks.
- Mobile Wireless Networks: We propose to develop fundamental limits on AoI in mobile networks, and develop packet relaying schemes for minimizing AoI.
Participants:
Prof. Eytan Modiano, PI
Igor Kadota, graduate student
Vishrant Tripathi, graduate student
Rajat Talak, graduate student
Timothy Cardona, undergraduate student
Muhammad Shahir Rahman, undergraduate student
Results:
In [1] we consider a single-hop wireless network with a number of nodes transmitting time sensitive information to a Base Station and address the problem of minimizing the Expected Weighted Sum AoI of the network while simultaneously satisfying timely-throughput constraints from the nodes. We develop three low-complexity transmission scheduling policies that attempt to minimize AoI subject to minimum throughput requirements and evaluate their performance against the optimal policy. In particular, we develop a randomized policy, a Max-Weight policy and a Whittle’s Index policy, and show that they are guaranteed to be within a factor of two, four and eight, respectively, away from the minimum AoI possible. In contrast, simulation results show that Max-Weight outperforms the other policies, both in terms of AoI and throughput, in every network configuration simulated, and achieves near optimal performance.
In [2] we extend our work minimizing average and peak AoI in wireless networks under general interference constraints. When fresh information is always available for transmission, we show that a stationary scheduling policy is peak age optimal. We also prove that this policy achieves average age that is within a factor of two of the optimal average age. In the case where fresh information is not always available, and packet/information generation rate has to be controlled along with scheduling links for transmission, we prove an important separation principle: the optimal scheduling policy can be designed assuming fresh information, and independently, the packet generation rate control can be done by ignoring interference. Peak and average AoI for discrete time G/Ber/1 queue is analyzed for the first time,which may be of independent interest.
In [3] we develop distributed scheduling policies, in which a transmission is attempted over each link with a certain attempt probability. We obtain an interesting relation between the optimal attempt probability and the optimal AoI of the link, and its neighboring links. We then show that the optimal attempt probabilities can be computed by solving a convex optimization problem, which can be done distributively.
In [4], we developed transmission scheduling schemes for minimizing Age-of-Information in wireless networks with stochastic arrivals. In particular, we consider a wireless network with a base station serving multiple traffic streams to different destinations. Packets from each stream arrive to the base station according to a stochastic process and are enqueued in a separate (per stream) queue. The queueing discipline controls which packet within each queue is available for transmission. The base station decides, at every time t, which stream to serve to the corresponding destination. The goal of scheduling decisions is to keep the information at the destinations fresh. Information freshness is captured by the Age of Information (AoI) metric. We derive a lower bound on the AoI performance achievable by any given network. Then, we consider three common queueing disciplines and develop both an Optimal Stationary Randomized Policy and a Max-Weight Policy under each discipline. Our approach allows us to evaluate the combined impact of the queueing discipline and the scheduling policy on AoI. We evaluate the AoI performance both analytically and using simulations. Numerical results show that the performance of the Max-Weight Policy is close to the analytical lower bound.
In [5] we consider the problem of minimizing latency in a mobile network for information gathering and retrieval. In particular, we consider the problem of timely exchange of updates between a central station and a set of ground terminals V , via a mobile agent that traverses across the ground terminals along a mobility graph G = (V,E). We design the trajectory of the mobile agent to minimize peak and average age of information (AoI), two newly proposed metrics for measuring timeliness of information. We consider randomized trajectories, in which the mobile agent travels from terminal i to terminal j with probability Pi,j. For the information gathering problem, we show that a randomized trajectory is peak age optimal and factor-8H average age optimal, where H is the mixing time of the randomized trajectory on the mobility graph G. We also show that the average age minimization problem is NP-hard. For the information dissemination problem, we prove that the same randomized trajectory is factor-O(H) peak and average age optimal. Moreover, we propose an age-based trajectory, which utilizes information about current age at terminals, and show that it is factor-2 average age optimal in a symmetric setting.
In [6] we consider the problem of optimizing functions of age of information. We consider a setting where multiple active sources send real-time updates over a single-hop wireless broadcast network to a monitoring station. Our goal is to design a scheduling policy that minimizes the time-average of general non-decreasing cost functions of Age of Information. We use a Whittle index based approach to find low complexity scheduling policies that have good performance, for reliable as well as unreliable channels. We prove that for a system with two sources, having possibly different cost functions and reliable channels, the Whittle index policy is exactly optimal. For reliable channels, we also derive structural properties of an optimal policy, that suggest that the performance of the Whittle index policy may be close to optimal in general. These results might also be of independent interest in the study of restless multi-armed bandit problems with similar underlying structure. Finally, we provide simulationscomparing the Whittle index policy with optimal scheduling policies found using dynamic programming, which support our results.
Publications:
- Igor Kadota, Abhishek Sinha, Eytan Modiano, “Optimizing Age of Information in Wireless Networks with Throughput Constraints,” IEEE Infocom, Honolulu, HI, April 2018. (Best Paper Award)
- Rajat Talak, Sertac Karaman, Eytan Modiano,”Optimizing Information Freshness in Wireless Networks under General Interference Constraints,” ACM MobiHoc 2018, Los Angeles, CA, June 2018. (Best Paper Award)
- Rajat Talak, Sertac Karaman, Eytan Modiano, “Distributed Scheduling Algorithms for Optimizing Information Freshness in Wireless Networks,” IEEE SPAWC, Kalamata, Greece, 2018.
- Igor Kadota, Eytan Modiano, “Minimizing the Age of Information in Wireless Networks with Stochastic Arrivals,” ACM MobiHoc, Catania, Italy, July 2019.
- Vishrant Tripathi, Rajat Talak, Eytan Modiano, “Age Optimal Information Gathering and Dissemination on Graphs,” IEEE Infocom, Paris, April 2019.
- Vishrant Tripathi, Eytan Modiano, “A Whittle Index Approach to Minimizing Functions of Age of Information,” Allerton Conference on Communications, Control, and Computing, September, 2019.