Scheduling observers and agents over a shared medium with hard delivery deadlines
Creators: name: Al Jurdi, Rebal
Publisher: name: The University of Texas at Austin
Year: 2019
Subjects: Ultra-reliability
Low-latency
Infrastructure wireless networks
Hard deadlines
Sensor scheduling
Sensor
Selection
Branch-and-bound
Dynamic programming
IoT
5G
URLLC
mMTC
Sensor selection

description: Applications that require ultra low latency and high reliability--such as intelligent transportation, telemedicine, and industrial automation--often involve a significant element of control and decision making. In particular, such systems involve three logical components: observers (e.g. sensors) measuring the state of an environment or dynamical system, a centralized executive (e.g. controller) deciding on the state, and agents (e.g. actuators) that implement the executive's decisions. The executive harvests the observers' measurements and decides on the short-term trajectory of the system by instructing its agents to take appropriate actions. All observation packets (typically uplink) and action packets (typically downlink) must be delivered by hard deadlines to ensure the proper functioning of the controlled system. This is very challenging in a wireless system due to inherent uncertainties in wireless channels due to phenomena such as fading and unpredictable interference, and for this reason applications with hard deadlines historically have typically used wired communication connections. This dissertation studies three main aspects involving communication systems with hard deadlines. First, we develop a probabilistic framework to study the outage of a controlled system. We model a communication method that uses periodic transmission frames, link adaptation, and controlled channel access. We obtain simple, closed-form expressions and upper and lower bounds on the probability of outage due to packet decoding errors and deadline violations. We perform detailed system-level simulations to identify design guidelines such as the optimal amount of training time, as well as benchmarking the proposed system design versus non-cooperative cellular, cooperative fixed-rate, and cooperative relaying systems. Second, we develop a novel framework that abstracts the context around different control and decision processes by using a common mathematical model to formulate and solve the observer selection problem (OSP). The executive solves this problem to select a feasible, schedulable sequence of observations that maximize its knowledge about the state of the system. To solve this constrained selection problem, we devise a branch-and-bound algorithm that efficiently prunes the search space. This work is fundamentally different from existing work on real-time communications in that communication reliability is not conveyed by packet loss or error rate, but rather by the extent of the executive's knowledge about the state of the system it controls. Third, we derive conditions that reduce the OSP constraint to 1) a sum (sum-of-weights) constraint and 2) an extremal (max-weight) constraint. We prove an optimal substructure of OSP which shows that if an observation sequence is optimal, then all of its subsequences are suboptimal. We propose a dynamic programming algorithm to optimally solve OSP with a sum constraint, and a reverse linear search to solve OSP with an extremal constraint