Optimizing Information Freshness in Wireless Networks

Age of Information (AoI) is a performance metric that can be used to measure the freshness of information. Since its inception, it has captured the attention of the research community and is now an area of active research. By its definition, AoI measures the elapsed time period between the present time and the generation time of the information. AoI is fundamentally different from traditional metrics such as delay or latency as the latter only considers the transit time for a packet to traverse the network. Among the state-of-the-art in the literature, we identify two limitations that deserve further investigation. First, many existing efforts on AoI have been limited to information-theoretic exploration by considering extremely simple models and unrealistic assumptions, which are far from real-world communication systems. Second, among most existing work on scheduling algorithms to optimize AoI, there is a lack of research on guaranteeing AoI deadlines. The goal of this dissertation is to address these two limitations in the state-of-the-art. First, we design schedulers to minimize AoI under more practical settings, including varying sampling periods, varying sample sizes, cellular transmission models, dynamic channel conditions, etc. Second, we design schedulers to guarantee hard or soft AoI deadlines for each information source. More important, inspired by our results from guaranteeing AoI deadlines, we develop a general design framework that can be applied to construct high-performance schedulers for AoI-related problems. This dissertation is organized into three parts. In the first part, we study two problems on AoI minimization under general settings. (i) We consider general and heterogeneous sampling behaviors among source nodes, varying sample size, and a cellular-based transmission model. We develop a near-optimal low-complexity scheduler---code-named Juventas---to minimize AoI. (ii) We study the AoI minimization problem under a 5G network with dynamic channels. To meet the stringent real-time requirement for 5G, we develop a GPU-based near-optimal algorithm---code-named Kronos---and implement it on commercial off-the-shelf (COTS) GPUs. In the second part, we investigate three problems on guaranteeing AoI deadlines. (i) We study the problem to guarantee a hard AoI deadline for information from each source. We present a novel low-complexity procedure, called Fictitious Polynomial Mapping (FPM), and prove that FPM can find a feasible scheduler for any hard deadline vector when the system load is under ln 2. (ii) For soft AoI deadlines, i.e., occasional violations can be tolerated, we present a novel procedure called Unstable Tolerant Scheduler (UTS). UTS hinges upon the notions of Almost Uniform Schedulers (AUSs) and step-down rate vectors. We show that UTS has strong performance guarantees under different settings. (iii) We investigate a 5G scheduling problem to minimize the proportion of time when the AoI exceeds a soft deadline. We derive a property called uniform fairness and use it as a guideline to develop a 5G scheduler---Aequitas. To meet the real-time requirement in 5G, we implement Aequitas on a COTS GPU. In the third part, we present Eywa---a general design framework that can be applied to construct high-performance schedulers for AoI-related optimization and decision problems. The design of Eywa is inspired by the notions of AUS schedulers and step-down rate vectors when we develop UTS in the second part. To validate the efficacy of the proposed Eywa framework, we apply it to solve a number of problems, such as minimizing the sum of AoIs, minimizing bandwidth requirement under AoI constraints, and determining the existence of feasible schedulers to satisfy AoI constraints. We find that for each problem, Eywa can either offer a stronger performance guarantee than the state-of-the-art algorithms, or provide new/general results that are not available in the literature. Doctor of Philosophy Age of Information (AoI) is a performance metric that can be used to measure the freshness of information. It measures the elapsed time period between the present time and the generation time of the information. Through a literature review, we have identified two limitations: (i) many existing efforts on AoI have employed extremely simple models and unrealistic assumptions, and (ii) most existing work focuses on optimizing AoI, while overlooking AoI deadline requirements in some applications. The goal of this dissertation is to address these two limitations. For the first limitation, we study the problem to minimize the average AoI in general and practical settings, such as dynamic channels and 5G NR networks. For the second limitation, we design schedulers to guarantee hard or soft AoI deadlines for information from each source. Finally, we develop a general design framework that can be applied to construct high-performance schedulers for AoI-related problems.