Information Freshness: Fundamental Limits and Optimization Methodologies
Open Access
- Author:
- Feng, Songtao
- Graduate Program:
- Electrical Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- June 16, 2022
- Committee Members:
- Constantino Lagoa, Major Field Member
Viveck Cadambe, Major Field Member
Jing Yang, Chair & Dissertation Advisor
Guodong Pang, Outside Unit & Field Member
Kultegin Aydin, Program Head/Chair - Keywords:
- Age of Information (AoI)
Scheduling
Wireless networks - Abstract:
- In recent years, the pervasive availability of network connectivity and the proliferation of sensing devices have fundamentally transformed the operation and control of cyber-physical systems (CPSs), where continuous data streams are generated by the sensors, transferred through different communication pipelines, delivered to central controllers, and eventually processed and analyzed, facilitating real-time status monitoring and decision-making. In such systems, the timeliness of information is of paramount importance: Stale measurements may lead to state estimations that significantly deviate from the current system state, resulting in incorrect control commands and deteriorating the stability and resilience of the system. Therefore, there is a compelling need to quantify and study the ``freshness'' of information, to measure the impact of information ``staleness'' on system performance, and to develop information gathering and processing techniques to ensure information freshness in real-time systems. In order to measure and ensure the freshness of the information available to the monitor, a metric called {\it Age of Information (AoI)} has been introduced and analyzed in various status updating systems. Specifically, at time $t$, the AoI in the system is defined as $t-U(t)$, where $U(t)$ is the time stamp of the latest received update at the destination. Since AoI depends on data generation as well as queueing and transmission, it is fundamentally different from traditional network performance metrics, such as throughput and delay. The goal of this dissertation is to characterize the AoI in various status monitoring systems under practical system level constraints, and to design efficient sampling, coding and scheduling techniques to improve information freshness and optimize AoI by leveraging a diverse corpus of tools from queueing theory, optimization theory, combinatorial analysis and information theory. We first provide an overview of the dissertation and a brief review of the related literature in Chapter~\ref{ch:intro}. In Chapter~\ref{ch:EH}, we focus on the AoI in energy harvesting (EH) sensor networks where the channel between the sensor and the destination is noisy. Our goal is to design an optimal online status updating policy to minimize the long-term average AoI at the destination, subject to the energy causality constraint. Depending on whether there exists updating feedback to the source, we consider two possible scenarios: no updating feedback and perfect updating feedback. For both cases, we propose Best-effort Uniform updating (BU) policy and Best-effort Uniform updating with Retransmission (BUR) policy and prove their optimality under a broad class of online policies. In order to analyze the performance of the proposed policies, we come up with a novel virtual policy based approach. Specifically, for both BU and BUR updating policies, we construct a sequence of virtual policies, which are strictly sub-optimal to their original counterparts, and eventually converge to them. Leveraging the virtual policies, we are able to decouple the effects of battery outage and updating errors in the performance analysis. We show that the long-term average AoI under virtual polices converges to the corresponding lower bound, which implies the optimality of the proposed policies. In Chapter~\ref{ch:MIMO}, we consider the MIMO broadcast setting where optimizing AoI through precoding and transmission scheduling is the focal point. Under the assumptions that the noise level is negligible in the channel and the instantaneous channel state information (CSI) is available to the transmitter at the beginning at each time slot, we propose novel coding and scheduling schemes under different setups that allow simultaneously transmissions of multiple users, and prove their optimalities. Our results indicate that the size of the updates plays a critical role in the design of the optimal updating schemes. In fact, when the update size is greater than one, wasting some transmission opportunities in order to deliver fresher updates may be better. The techniques developed to the show the optimality are novel and those techniques may be applicable for other AoI problems as well. The MIMO broadcast setting has been extensively studied for throughput optimization but existing study on AoI in broadcast channel rarely considers the impact of multiplexing gain on information freshness. This work bridges the gap between existing studies on MIMO broadcast channel and AoI. In Chapter~\ref{ch:rateless}, we study AoI optimization for an symbol erasure channel with rateless codes. We formulate the problem as a Markov Decision Process (MDP) and identify the monotonic threshold structure of the optimal policy. We then consider a more practical scenario where limited feedback is available during the transmission of an update. We propose a type of threshold policies to approximate the multi-threshold structure of the optimal policy and derive the explicit expression of the time-average AoI under the threshold policies. We then numerically search for the optimal policy through structured dynamic programming, and compare its AoI performance with a threshold policy and other baseline policies. Numerical results corroborate the structural properties of the optimal solution and indicates that the performance under the special type of threshold policy is very close to the optimal policy. In Chapter~\ref{ch:adaptcode}, we investigate the impact of coding on the AoI in a two-user broadcast symbol erasure channel with feedback. Assuming perfect feedback information at the source right after the transmission of each symbol, our objective is to design an adaptive coding scheme to achieve small AoI at both users. We propose a novel coding scheme to judiciously combine symbols from different updates together, and analyze the AoI at both users. Compared with a baseline greedy scheme, the proposed adaptive coding scheme improves the AoI at the weak user by orders of magnitude without compromising the AoI at the strong user. In Chapter~\ref{ch:detection}, we aim to establish the connection between AoI in network theory, information uncertainty in information theory, and detection delay in time series analysis. We consider a dynamic system whose state changes at discrete time points, and a state change will not be detected until an update generated after the change point is delivered to the destination for the first time. We introduce an information theoretic metric to measure the information freshness at the destination, and name it as generalized Age of Information (GAoI). We show that under any state-independent online updating policy, if the underlying state of the system evolves according to a stationary Markov chain, the GAoI is proportional to the AoI. Besides, the accumulative GAoI and AoI are proportional to the expected accumulative detection delay of all changes points over a period of time. Thus, any (G)AoI-optimal state-independent updating policy equivalently minimizes the corresponding expected change point detection delay, which validates the fundamental role of (G)AoI in real-time status monitoring. Besides, we also investigate a Bayesian change point detection scenario where the underlying state evolution is not stationary. Although AoI is no longer related to detection delay explicitly, we show that the accumulative GAoI is still an affine function of the expected detection delay, which indicates the versatility of GAoI in capturing information freshness in dynamic systems. Finally, we conclude the dissertation in Chapter~\ref{conclusion}, with a brief discussion of potential future directions.