Delivering Perishable Information and Cargos: Delay-Constrained Communication and Transportation

Nowadays, provisioning delay-constrained services becomes more and more important in communication and transportation systems. However, most existing communication and transportation systems are best-effort and do not provide any delay guarantee. To address such an issue, in this thesis, we study two important yet different delay-constrained problems: (i) how to maximize the system performance in terms of network utility of a wireless communication system where every packet has a hard delivery delay constraint? and (ii) how to minimize the fuel consumption of a heavy-duty truck delivering cargos in a highway transportation system where the truck has a hard delivery delay constraint?;The first problem is important in multimedia communication systems, cyber-physical systems (CPSs), and Internet-of-Things (IoT) systems with real-time applications over wireless networks. The second problem is important for truck operators who aim at both saving fuel cost and ensuring timely delivery. These two problems share a common perishable feature that the considered entity (the packet/information or the truck/cargos) is required to reach the destination on/before a given hard deadline. We remark that the delay-unconstrained counterparts of these two problems (i.e., without the perishable feature) were well studied and understood while their approaches cannot be applied to our delay-constrained problems as shown later in the thesis.;For the first problem, recently, Hou and Kumar provided a novel idle-time-based framework to solve it for a special frame-synchronized traffic pattern. However, the problem remains largely open for general traffic patterns. To tackle this problem, we have two critical issues: one is how to characterize the timely capacity region, and the other is how to maximize the network utility (i.e., achieve the timely capacity region). In this thesis, we propose a general framework to address these two critical issues with general traffic patterns in a single-hop downlink access-point wireless network. We first show that the timely wireless ow problem is fundamentally an infinite-horizon Markov Decision Process (MDP). Then we apply two simplification methods to prove that the timely capacity region is a convex polygon specified by a finite number of linear constraints. This allows us for the first time to characterize the timely capacity region of wireless flows with general traffic patterns, addressing the first critical issue. To address the second critical issue, we further design three scheduling policies to maximize network utility and/or support feasible timely throughput vectors for general traffic patterns. The first policy achieves the optimal network utility and supports any feasible timely throughput vector but suffers from the curse of dimensionality. The second and third policies are heuristic that are inspired by our MDP framework and are of much lower complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.;For the second problem, we minimize the fuel consumption of the heavy-duty truck by exploring the full design space of both route planning and speed planning. We remark that this new and practically important problem is a generalization of the classical Restricted Shortest Path (RSP) problem. We first show that the problem is NP-complete and then design a fully polynomial time approximation scheme (FPTAS) to solve it. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time for large-scale national highway systems. Leveraging insights from studying the dual problem, we design a heuristic with much lower complexity, which can be applied to large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. Numerical experiments using real-world truck data over the actual U.S. highway network show that our proposed solutions reduce the fuel consumption by up to 17%, as compared to the shortest/fastest path algorithm adapted from common practice.;Overall, in the communication and transportation systems, we observe that both the problem structure and the problem-solving methodology of delay-constrained problems are completely different from those of the well-understood delay-unconstrained ones. This thesis serves as a first step towards studying delay-constrained communication and transportation systems and calls for further investigation participation.