Thesis (Ph.D.)--Boston University / PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you. / This dissertation is dedicated to optimization of Stochastic Hybrid Systems (SHS). The concentration is on both online optimization of these systems and extending the known optimal policies in Discrete-Event Systems (DES) to a broader context of SHS. A SHS involves both continuous and discrete dynamics and is suitable for modeling almost any physical system of interest. The first part of this dissertation focuses on applications of SHS and, particularly, a subclass known as Stochastic Flow Models (SFM) used in fluid scheduling. To this end, a classic problem for optimally allocating a resource to multiple competing user queues is considered in the DES context and placed in the framework of SFMs. Infinitesimal Perturbation Analysis (IPA) is used to calculate the gradient estimates for the average holding cost of this system with respect to resource allocation parameters. The monotonicity property of these estimates allows us to prove the optimality of a well-known rule called the "c - mu-rule" under non-idling policies. Furthermore, nonlinear cost functions are considered, yielding simple distribution-free cost sensitivity estimates. Next, we take the first step in using IPA for optimally calculating timeout thresholds in SHS. A Transmission Control Protocol (TCP) communication link is used to examine the effectiveness of SHS and IPA in calculating derivative estimates of a goodput objective with respect to a timeout parameter. The analysis is also extended to the case of multinode communications. Our results reveal a great potential in using IPA to control delay thresholds and motivate more investigations in future. Finally, we propose a general framework for analysis and on-line optimization of SHS which facilitates the use of IPA. In doing so, we modify the previous structure of a Stochastic Hybrid Automaton (SHA) and show that every transition is associated with an explicit event which is defined through a "guard function." This enables us to uniformly treat all events observed on the sample path of the SHS. As a result, a unifying matrix notation for IPA equations is developed which eliminates the need for the case-by-case analysis of event classes as usually done in prior works involving IPA for SHS. / 2999-01-01

<p>Various engineering systems have become rapidly automated and intelligent as sensing, communication, and computing technologies have been increasingly advanced. The dynamical behaviors of such systems have also become complicated as they need to meet requirements on performance and safety in various operating conditions. Due to the heterogeneity in its behaviors for different operating modes, it is not appropriate to use a single dynamical model to describe its dynamics, which motivates the development of the stochastic hybrid system (SHS). The SHS is defined as a dynamical system which contains interacting time-evolving continuous state and event-driven discrete state (also called a mode) with uncertainties. Due to its flexibility and effectiveness, the SHS has been widely used for modeling complex engineering systems in many applications such as air traffic control, sensor networks, biological systems, and etc.</p><p>One of the key research areas related to the SHS is the inference or estimation of the states of the SHS, which is also known as the hybrid state estimation. This task is very challenging because both the continuous and discrete states need to be inferred from noisy measurements generated from mixed time-evolving and event-driven behavior of the SHS. This becomes even more difficult when the dynamical behavior or measurement contains nonlinearity, which is the case in many engineering systems that can be modeled as the SHS.</p><p>This research aims to 1) propose a stochastic nonlinear hybrid system model and develop novel nonlinear hybrid state estimation algorithms that can deal with the aforementioned challenges, and 2) apply them to safety-critical applications in air traffic control systems such as aircraft tracking and estimated time of arrival prediction, and unmanned aircraft system traffic management.</p>

<p>We consider stochastic hybrid systems that stem from evolution equations with right-hand sides that stochastically switch between a given set of right-hand sides. To begin our study, we consider a linear ordinary differential equation whose right-hand side stochastically switches between a collection of different matrices. Despite its apparent simplicity, we prove that this system can exhibit surprising behavior.</p><p>Next, we construct mathematical machinery for analyzing general stochastic hybrid systems. This machinery combines techniques from various fields of mathematics to prove convergence to a steady state distribution and to analyze its structure.</p><p>Finally, we apply the tools from our general framework to partial differential equations with randomly switching boundary conditions. There, we see that these tools yield explicit formulae for statistics of the process and make seemingly intractable problems amenable to analysis.</p> / Dissertation

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.

Les besoins grandissants de prévisions robustes pour des systèmes complexes conduisent à introduire des modèles mathématiques considérant un nombre croissant de paramètres. Au temps s'ajoutent l'espace, l'aléa, les échelles de dynamiques, donnant lieu à des modèles stochastiques multi-échelles avec dépendance spatiale (modèles spatiaux). Cependant, l'explosion du temps de simulation de tels modèles complique leur utilisation. Leur analyse difficile a néanmoins permis, pour les modèles à une échelle, de développer des outils puissants: loi des grands nombres (LGN), théorème central limite (TCL), ..., puis d'en dériver des modèles simplifiés et algorithmes accélérés. Dans le processus de dérivation, des modèles et algorithmes dits hybrides ont vu le jour dans le cas multi-échelle, mais sans analyse rigoureuse préalable, soulevant ainsi la question d'approximation hybride dont la consistance constitue l'une des motivations principales de cette thèse.En 2012, Crudu, Debussche, Muller et Radulescu établissent des critères d'approximation hybride pour des modèles homogènes en espace de réseaux de régulation de gènes. Le but de cette thèse est de compléter leur travail et le généraliser à un cadre spatial.Nous avons développé et simplifié différents modèles, tous des processus de Markov de sauts pures à temps continu. La démarche met en avant, d'une part, des conditions d'approximations déterministes par des solutions d'équations d'évolution (type réaction-advection-diffusion), et, d'autre part, des conditions d'approximations hybrides par des processus stochastiques hybrides. Dans le cadre des réseaux de réactions biochimiques, un TCL est établi. Il correspond à une approximation hybride d'un modèle homogène simplifié à deux échelles de temps (suivant Crudu et al.). Puis, une LGN est obtenue pour un modèle spatial à deux échelles de temps. Ensuite, une approximation hybride est établie pour un modèle spatial à deux échelles de dynamique en temps et en espace. Enfin, des comportements asymptotiques en grandes populations et en temps long sont présentés pour un modèle d'épidémie de choléra, via une LGN suivie d'une borne supérieure pour les sous-ensembles compacts, dans le cadre d'un principe de grande déviation (PGD) correspondant.À l'avenir, il serait intéressant, entre autres, de varier la géométrie spatiale, de généraliser le TCL, de compléter les estimations du PGD, et d'explorer des systèmes complexes issus d'autres domaines. / The growing needs of precise predictions for complex systems lead to introducing stronger mathematical models, taking into account an increasing number of parameters added to time: space, stochasticity, scales of dynamics. Combining these parameters gives rise to spatial --or spatially inhomogeneous-- multiscale stochastic models. However, such models are difficult to study and their simulation is extremely time consuming, making their use not easy. Still, their analysis has allowed one to develop powerful tools for one scale models, among which are the law of large numbers (LLN) and the central limit theorem (CLT), and, afterward, to derive simpler models and accelrated algorithms. In that deduction process, the so-called hybrid models and algorithms have arisen in the multiscale case, but without any prior rigorous analysis. The question of hybrid approximation then shows up, and its consistency is a particularly important motivation of this PhD thesis.In 2012, criteria for hybrid approximations of some homogeneous regulation gene network models were established by Crudu, Debussche, Muller and Radulescu. The aim of this PhD thesis is to complete their work and generalize it afterward to a spatial framework.We have developed and simplified different models. They all are time continuous pure jump Markov processes. The approach points out the conditions allowing on the the one hand deterministic approximations by solutions of evolution equations of type reaction-advection-diffusion, and, on the other hand, hybrid approximations by hybrid stochastic processes. In the field of biochemical reaction networks, we establish a CLT. It corresponds to a hybrid approximation of a simplified homogeneous model (due to Crudu et al.). Then a LLN is obtained for a spatial model with two time scales. Afterward, a hybrid approximation is established, for a two time-space scales spatial model. Finally, the asymptotic behaviour in large population and long time are respectively presented for a model of cholera epidemic, through a LLN followed by the upper bound for compact sets, in the context of a corresponding large deviation principle (LDP).Interesting future works would be, among others, to study other spatial geometries, to generalize the CLT, to complete the LDP estimates, and to study complex systems from other fields.