PhD Oral Exam - Ebrahim Sarkhouh, Computer Science

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

Autonomous driving (AD) is rising as an efficient solution to a wide range of transportation problems. With all the capabilities utilized (sensors, 5G communication technologies, computation units), intelligent vehicles can interact with the surroundings and cooperate in instantaneously maneuvering safely and effectively. Incorporating a central agent that supports this on-the-road interaction represents a critical enabling idea that will elevate the Cooperative Autonomous Driving (CAD) performance. Edge Computing (EC) recently attracted a considerable focus, specifically in vehicular networks, as it provides a reliable and online response to service demands arriving from vehicles. In the context of CAD, EC can reduce the usage of wireless communications, orchestrate the activities on the road and provide massive computation capabilities to the vehicles. In this dissertation, we investigate the potential of EC in the context of supporting autonomous driving and managing the radio and computation resources available. We propose adequate solutions for various problems that EC should continuously resolve as an essential component of a complete intelligent transportation system.

First, we examine the capability of EC by formulating the problem of scheduling vehicular computational tasks over the resources as an optimization problem and solve it via integer linear programming (ILP) and Lagrangian relaxation. We prove the complexity of the problem, and thus we develop a scalable solution that reaches near-optimal solutions and around 90% speedup compared with branch-and-cut.

Second, we propose a system model that harvests the computational resources available on the vehicles’ onboard units via a fog computing scheme. The system aims to jointly allocate the radio and computational resources to maximize the number of admitted tasks. We provide a formal definition of the problem as multi-stage scheduling and, due to its complexity, propose a Dantzing-Wolfe decomposition method to solve the problem. We compare the performance of the proposed method with CPLEX and show that the solution is only 20% far from the optimal solution while achieving 94% speedup.

Third, to accurately represent an autonomous driving scenario, we model the computational load as long-term processes that continuously receive data from multiple sources, process them together and inform multiple destinations with decisions that support cooperative autonomous driving applications. These processes essentially represent long-term on-the-road tasks such as changing lanes or platoon establishment. The objective is to minimize the age of the information continuously received in the destinations. The problem turned to be highly complex. We propose a novel Benders decomposition technique that divides the problem into several subproblems and one integer master problem. We developed a scalable solution for each of these problems and compared the overall method with the optimal solution. The method proposed showed high scalability and efficiency in terms of the objective and computation time.

We conclude with a discussion on the outcomes of this thesis and the directions we intend to take in our future work.