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.

In recent years, the remarkable development in ubiquitous communication networks and smart portable devices spawned a wide variety of real-time applications that require timely information updates (e.g., autonomous vehicular systems, industrial automation systems, and live streaming services). These real-time applications all have one thing in common: they desire their knowledge of the information source to be as fresh as possible. In order to measure the freshness of information, a new metric, called the Age-of-Information (AoI) is proposed. AoI is defined as the time elapsed since the generation time of the freshest delivered update. This metric is influenced by both the inter-arrival time and the delay of the updates. As a result of these dependencies, the AoI metric exhibits distinct characteristics compared to traditional delay and throughput metrics. In this dissertation, our goal is to optimize AoI under various real-time network applications. Firstly, we investigate a fundamental problem of how exactly various scheduling policies impact AoI performance. Though there is a large body of work studying the AoI performance under different scheduling policies, the use of the update-size information and its combinations with other information (such as arrival-time information and service preemption) to reduce AoI has still not been explored yet. Secondly, as a recently introduced measure of freshness, the relationship between AoI and other performance metrics remains largely ambiguous. We analyze the tradeoffs between AoI and additional performance metrics, including service performance and update cost, within real-world applications. This dissertation is organized into three parts. In the first part, we realize that scheduling policies leveraging the update-size information can substantially reduce the delay, one of the key components of AoI. However, it remains largely unknown how exactly scheduling policies (especially those making use of update-size information) impact the AoI performance. To this end, we conduct a systematic and comparative study to investigate the impact of scheduling policies on the AoI performance in single-server queues and provide useful guidelines for the design of AoI-efficient scheduling policies. In the second part, we analyze the tradeoffs between AoI and other performance metrics in real-world systems. Specifically, we focus on the following two important tradeoffs. (i) The tradeoff between service performance and AoI that arises in the data-driven real-time applications (e.g., Google Maps and stock trading applications). In these applications, the computing resource is often shared for processing both updates from information sources and queries from end users. Hence there is a natural tradeoff between service performance (e.g., response time to queries) and AoI (i.e., the freshness of data in response to user queries). To address this tradeoff, we begin by introducing a simple single-server two-queue model that captures the coupled scheduling between updates and queries. Subsequently, we design threshold-based scheduling policies to prioritize either updates or queries. Finally, we conduct a rigorous analysis of the performance of these threshold-based scheduling policies. (ii) The tradeoff between update cost and AoI that appear in the crowdsensing-based applications (e.g., Google Waze and GasBuddy). On the one hand, users are not satisfied if the responses to their requests are stale; on the other side, there is a cost for the applications to update their information regarding certain points of interest since they typically need to make monetary payments to incentivize users. To capture this tradeoff, we first formulate an optimization problem with the objective of minimizing the sum of the staleness cost (which is a function of the AoI) and the update cost, then we obtain a closed-form optimal threshold-based policy by reformulating the problem as a Markov decision process (MDP). In the third part, we study the minimization of data freshness and transmission costs (e.g., energy cost) under an (arbitrary) time-varying wireless channel without and with machine learning (ML) advice. We consider a discrete-time system where a resource-constrained source transmits time-sensitive data to a destination over a time-varying wireless channel. Each transmission incurs a fixed cost, while not transmitting results in a staleness cost measured by the AoI. The source needs to balance the tradeoff between these transmission and staleness costs. To tackle this challenge, we develop a robust online algorithm aimed at minimizing the sum of transmission and staleness costs, ensuring a worst-case performance guarantee. While online algorithms are robust, they tend to be overly conservative and may perform poorly on average in typical scenarios. In contrast, ML algorithms, which leverage historical data and prediction models, generally perform well on average but lack worst-case performance guarantees. To harness the advantages of both approaches, we design a learning-augmented online algorithm that achieves two key properties: (i) consistency: closely approximating the optimal offline algorithm when the ML prediction is accurate and trusted; (ii) robustness: providing a worst-case performance guarantee even when ML predictions are inaccurate. / Doctor of Philosophy / In recent years, the rapid growth of communication networks and smart devices has spurred the emergence of real-time applications like autonomous vehicles and industrial automation systems. These applications share a common need for timely information. The freshness of information can be measured using a new metric called Age-of-Information (AoI). This dissertation aims to optimize AoI across various real-time network applications, organized into three parts. In the first part, we explore how scheduling policies (particularly those considering update size) impact the AoI performance. Through a systematic and comparative study in single-server queues, we provide useful guidelines for the design of AoI-efficient scheduling policies. The second part explores the tradeoff between update cost and AoI in crowdsensing applications like Google Waze and GasBuddy, where users demand fresh responses to their requests; however, updating information incurs update costs for applications. We aim to minimize the sum of staleness cost (a function of AoI) and update cost. By reformulating the problem as a Markov decision process (MDP), we design a simple threshold-based policy and prove its optimality. In the third part, we study the minimization of data freshness and transmission costs (e.g., energy cost) under a time-varying wireless channel. We first develop a robust online algorithm that achieves a competitive ratio of 3, ensuring a worst-case performance guarantee. Furthermore, when advice is available, e.g., predictions from machine learning (ML) models, we design a learning-augmented online algorithm that exhibits two desired properties: (i) consistency: closely approximating the optimal offline algorithm when the ML prediction is accurate and trusted; (ii) robustness: guaranteeing worst-case performance even with inaccurate ML prediction. While this dissertation marks a significant advancement in AoI research, numerous open problems remain. For instance, our learning-augmented online algorithm treats ML predictions as external inputs. Exploring the co-design and training of ML and online algorithms to improve performance could yield interesting insights. Additionally, while AoI typically assesses update importance based solely on timestamps, the content of updates also holds significance. Incorporating considerations of both age and semantics of information is imperative in future research.

A typical model for real-time status update systems consists of a transmitter node that generates real-time status updates about some physical process(es) of interest and sends them through a communication network to a destination node. Such a model can be used to analyze the performance of a plethora of emerging Internet of Things (IoT)-enabled real-time applications including healthcare, factory automation, autonomous vehicles, and smart homes, to name a few. The performance of these applications highly depends upon the freshness of the information status at the destination node about its monitored physical process(es). Because of that, the main design objective of such real-time status update systems is to ensure timely delivery of status updates from the transmitter node to the destination node. To measure the freshness of information at the destination node, the Age of Information (AoI) has been introduced as a performance metric that accounts for the generation time of each status update (which was ignored by conventional performance metrics, specifically throughput and delay). Since then, there have been two main research directions in the AoI research area. The first direction aimed to analyze/characterize AoI in different queueing-theoretic models/disciplines, and the second direction was focused on the optimization of AoI in different communication systems that deal with time-sensitive information. However, the prior queueing-theoretic analyses of AoI have mostly been limited to the characterization of the average AoI and the prior studies developing AoI/age-aware scheduling/transmission policies have mostly ignored the energy constraints at the transmitter node(s). Motivated by these limitations, this dissertation develops new queueing-theoretic methods that allow the characterization of the distribution of AoI in several classes of status updating systems as well as novel AoI-aware scheduling policies accounting for the energy constraints at the transmitter nodes (for several settings of communication networks) in the process of decision-making using tools from optimization theory and reinforcement learning. The first part of this dissertation develops a stochastic hybrid system (SHS)-based general framework to facilitate the analysis of characterizing the distribution of AoI in several classes of real-time status updating systems. First, we study a general setting of status updating systems, where a set of source nodes provide status updates about some physical process(es) to a set of monitors. For this setting, the continuous state of the system is formed by the AoI/age processes at different monitors, the discrete state of the system is modeled using a finite-state continuous-time Markov chain, and the coupled evolution of the continuous and discrete states of the system is described by a piecewise linear SHS with linear reset maps. Using the notion of tensors, we derive a system of linear equations for the characterization of the joint moment generating function (MGF) of an arbitrary set of age processes in the network. Afterwards, we study a general setting of gossip networks in which a source node forwards its measurements (in the form of status updates) about some observed physical process to a set of monitoring nodes according to independent Poisson processes. Furthermore, each monitoring node sends status updates about its information status (about the process observed by the source) to the other monitoring nodes according to independent Poisson processes. For this setup, we develop SHS-based methods that allow the characterization of higher-order marginal/joint moments of the age processes in the network. Finally, our SHS-based framework is applied to derive the stationary marginal and joint MGFs for several queueing disciplines and gossip network topologies, using which we derive closed-form expressions for marginal/joint high-order statistics of age processes, such as the variance of each age process and the correlation coefficients between all possible pairwise combinations of age processes. In the second part of this dissertation, our analysis is focused on understanding the distributional properties of AoI in status updating systems powered by energy harvesting (EH). In particular, we consider a multi-source status updating system in which an EH-powered transmitter node has multiple sources generating status updates about several physical processes. The status updates are then sent to a destination node where the freshness of each status update is measured in terms of AoI. The status updates of each source and harvested energy packets are assumed to arrive at the transmitter according to independent Poisson processes, and the service time of each status update is assumed to be exponentially distributed. For this setup, we derive closed-form expressions of MGF of AoI under several queueing disciplines at the transmitter, including non-preemptive and source-agnostic/source-aware preemptive in service strategies. The generality of our analysis is demonstrated by recovering several existing results as special cases. A key insight from our characterization of the distributional properties of AoI is that it is crucial to incorporate the higher moments of AoI in the implementation/optimization of status updating systems rather than just relying on its average (as has been mostly done in the existing literature on AoI). In the third and final part of this dissertation, we employ AoI as a performance metric for several settings of communication networks, and develop novel AoI-aware scheduling policies using tools from optimization theory and reinforcement learning. First, we investigate the role of an unmanned aerial vehicle (UAV) as a mobile relay to minimize the average peak AoI for a source-destination pair. For this setup, we formulate an optimization problem to jointly optimize the UAV's flight trajectory as well as energy and service time allocations for packet transmissions. This optimization problem is subject to the UAV's mobility constraints and the total available energy constraints at the source node and UAV. In order to solve this non-convex problem, we propose an efficient iterative algorithm and establish its convergence analytically. A key insight obtained from our results is that the optimal design of the UAV's flight trajectory achieves significant performance gains especially when the available energy at the source node and UAV is limited and/or when the size of the update packet is large. Afterwards, we study a generic system setup for an IoT network in which radio frequency (RF)-powered IoT devices are sensing different physical processes and need to transmit their sensed data to a destination node. For this generic system setup, we develop a novel reinforcement learning-based framework that characterizes the optimal sampling policy for IoT devices with the objective of minimizing the long-term weighted sum of average AoI values in the network. Our analytical results characterize the structural properties of the age-optimal policy, and demonstrate that it has a threshold-based structure with respect to the AoI values for different processes. They further demonstrate that the structures of the age-optimal and throughput-optimal policies are different. Finally, we analytically characterize the structural properties of the AoI-optimal joint sampling and updating policy for wireless powered communication networks while accounting for the costs of generating status updates in the process of decision-making. Our results demonstrate that the AoI-optimal joint sampling and updating policy has a threshold-based structure with respect to different system state variables. / Doctor of Philosophy / A typical model for real-time status update systems consists of a transmitter node that generates real-time status updates about some physical process(es) of interest and sends them through a communication network to a destination node. Such a model can be used to analyze the performance of a plethora of emerging Internet of Things (IoT)-enabled real-time applications including healthcare, factory automation, autonomous vehicles, and smart homes, to name a few. The performance of these applications highly depends upon the freshness of the information status at the destination node about its monitored physical process(es). Because of that, the main design objective of such real-time status update systems is to ensure timely delivery of status updates from the transmitter node to the destination node. To measure the freshness of information at the destination node, the Age of Information (AoI) has been introduced as a performance metric that accounts for the generation time of each status update (which was ignored by conventional performance metrics, specifically throughput and delay). Since then, there have been two main research directions in the AoI research area. The first direction aimed to analyze/characterize AoI in different queueing-theoretic models/disciplines, and the second direction was focused on the optimization of AoI in different communication systems that deal with time-sensitive information. However, the prior queueing-theoretic analyses of AoI have mostly been limited to the characterization of the average AoI and the prior studies developing AoI/age-aware scheduling/transmission policies have mostly ignored the energy constraints at the transmitter node(s). Motivated by these limitations, this dissertation first develops new queueing-theoretic methods that allow the characterization of the distribution of AoI in several classes of status updating systems. Afterwards, using tools from optimization theory and reinforcement learning, novel AoI-aware scheduling policies are developed while accounting for the energy constraints at the transmitter nodes for several settings of communication networks, including unmanned aerial vehicles (UAVs)-assisted and radio frequency (RF)-powered communication networks, in the process of decision-making. In the first part of this dissertation, a stochastic hybrid system (SHS)-based general framework is first developed to facilitate the analysis of characterizing the distribution of AoI in several classes of real-time status updating systems. Afterwards, this framework is applied to derive the stationary marginal and joint moment generating functions (MGFs) for several queueing disciplines and gossip network topologies, using which we derive closed-form expressions for marginal/joint high-order statistics of age processes, such as the variance of each age process and the correlation coefficients between all possible pairwise combinations of age processes. In the second part of this dissertation, our analysis is focused on understanding the distributional properties of AoI in status updating systems powered by energy harvesting (EH). In particular, we consider a multi-source status updating system in which an EH-powered transmitter node has multiple sources generating status updates about several physical processes. The status updates are then sent to a destination node where the freshness of each status update is measured in terms of AoI. For this setup, we derive closed-form expressions of MGF of AoI under several queueing disciplines at the transmitter. The generality of our analysis is demonstrated by recovering several existing results as special cases. A key insight from our characterization of the distributional properties of AoI is that it is crucial to incorporate the higher moments of AoI in the implementation/optimization of status updating systems rather than just relying on its average (as has been mostly done in the existing literature on AoI). In the third and final part of this dissertation, we employ AoI as a performance metric for several settings of communication networks, and develop novel AoI-aware scheduling policies using tools from optimization theory and reinforcement learning. First, we investigate the role of a UAV as a mobile relay to minimize the average peak AoI for a source-destination pair. For this setup, we formulate an optimization problem to jointly optimize the UAV's flight trajectory as well as energy and service time allocations for packet transmissions. This optimization problem is subject to the UAV's mobility constraints and the total available energy constraints at the source node and UAV. A key insight obtained from our results is that the optimal design of the UAV's flight trajectory achieves significant performance gains especially when the available energy at the source node and UAV is limited and/or when the size of the update packet is large. Afterwards, we study a generic system setup for an IoT network in which RF-powered IoT devices are sensing different physical processes and need to transmit their sensed data to a destination node. For this generic system setup, we develop a novel reinforcement learning-based framework that characterizes the optimal sampling policy for IoT devices with the objective of minimizing the long-term weighted sum of average AoI values in the network. Our analytical results characterize the structural properties of the age-optimal policy, and demonstrate that it has a threshold-based structure with respect to the AoI values for different processes. They further demonstrate that the structures of the age-optimal and throughput-optimal policies are different. Finally, we analytically characterize the structural properties of the AoI-optimal joint sampling and updating policy for wireless powered communication networks while accounting for the costs of generating status updates in the process of decision-making. Our results demonstrate that the AoI-optimal joint sampling and updating policy has a threshold-based structure with respect to different system state variables.

<p>It is predicted that there would be 41.6 billion IoT devices by 2025, which has kindled new interests on the timing coordination between sensors and controllers, i.e., how to use the waiting time to improve the performance. Sun et al. showed that a <i>controller</i> can strictly improve the data freshness, the so-called Age-of-Information (AoI), via careful scheduling designs. The optimal waiting policy for the <i>sensor</i> side was later characterized in the context of remote estimation. The first part of this work develops the jointly optimal sensor/controller waiting policy. It generalizes the above two important results in that not only do we consider joint sensor/controller designs, but we also assume random delay in both the forward and feedback directions. </p> <p> </p> <p>The second part of the work revisits and significantly strengthens the seminal results of Sun et al on the following fronts: (i) When designing the optimal offline schemes with full knowledge of the delay distributions, a new <i>fixed-point-based</i> method is proposed with <i>quadratic convergence rate</i>; (ii) When the distributional knowledge is unavailable, two new low-complexity online algorithms are proposed, which provably attain the optimal average AoI penalty; and (iii) the online schemes also admit a modular architecture, which allows the designer to <i>upgrade</i> certain components to handle additional practical challenges. Two such upgrades are proposed: (iii.1) the AoI penalty function incurred at the destination is unknown to the source node and must also be estimated on the fly, and (iii.2) the unknown delay distribution is Markovian instead of i.i.d. </p> <p> </p> <p>With the exponential growth of interconnected IoT devices and the increasing risk of excessive resource consumption in mind, the third part of this work derives an optimal joint cost-and-AoI minimization solution for multiple coexisting source-destination (S-D) pairs. The results admit a new <i>AoI-market-price</i>-based interpretation and are applicable to the setting of (i) general heterogeneous AoI penalty functions and Markov delay distributions for each S-D pair, and (ii) a general network cost function of aggregate throughput of all S-D pairs. </p> <p> </p> <p>In each part of this work, extensive simulation is used to demonstrate the superior performance of the proposed schemes. The discussion on analytical as well as numerical results sheds some light on designing practical network utility maximization protocols.</p>