With the advent of electric vehicles (EVs) and the proliferation of vehicle technologies like drive-by-wire and autonomous driving, advanced communication protocols to connect vehicles and the infrastructure have been proposed. However, practical large-scale deployments have been hindered due to caveats such as hardware, and infrastructure demands — including the security of vehicles, given their ubiquitous nature and direct correlation to human safety. As part of this thesis, we look at deploying a practical solution to adopt a secure large-scale vehicle-to-everything (V2X) communication architecture. Then, we also try to analyze and detect vulnerabilities in vehicle-to-grid communication for electric vehicles. In the first work, we analyze, build a proof of concept and evaluate the use of commercial off-the-shelf (COTS) smartphones as secure cellular-vehicle-to-everything (CV2X) radios. Here, we study the various possible network topologies considering the long-term evolution (LTE) technology with necessary latency requirements considering security and the associated overhead. We further simulate the proposed method by considering real-world scalability for practical deployment. In the second work, we analyze the ISO15118 standard for EV-to-electric grid communication involving high levels of energy exchange. We develop a grammatical fuzzing architecture to assess and evaluate the implementation of the standard on a road-deployed vehicle to detect security vulnerabilities and shortcomings. / Master of Science / The technology around vehicles and the transportation infrastructure has immensely advanced in the last few decades. Today we have advanced technologies like driver assistance, automated driving, and access to multimedia within our vehicles. And deploying such technologies has only been possible due to advancements in the electronics embedded in the vehicles and surrounding infrastructure. Opportunely, we can further improve the technologies to include numerous safety features by connecting vehicles and infrastructure via communication networks. However, this poses immense challenges regarding the scaling of communication infrastructure for the timely exchange of data and its security. But, given the proliferation of cellular technology, the ubiquitous nature of smartphones, and their capabilities, we propose and evaluate the idea of using commercial off-the-shelf (COTS) smartphones to connect vehicles and the infrastructure to exchange data securely. The first work of this thesis details the analysis and evaluation of the system and the network for a secure COTS-based cellular-vehicle-to-everything architecture, including a proof of concept hardware implementation and additional simulations. Additionally, in light of climate policies and cleaner transportation alternatives, we are moving from gasoline-based internal combustion engines to electric vehicles, requiring the transfer of extended amounts of electric energy from the electric grid to the batteries in the vehicles. In light of the same, ISO 15118 standard was developed to reduce repetitive efforts and standardize the communication and exchange of this energy. But as with any new technology, especially involving communication, new attack vectors for malicious entities open up. Therefore, we study this new standard and develop a novel fuzzing architecture to test the implementation of the standard on deployed real-world vehicles for security vulnerabilities and robustness. Again, as this is a nascent technology and standard, a fuzzing approach would accelerate the detection of edge cases and threats before these are exploited to cause harm to human life and property.

Flooding can severely disrupt transportation systems. When safety measures are limited to road closures, vehicles affected by the flooding have an origin, destination, or path segment that is closed or soon-to-be flooded during the trip's duration. This thesis introduces a framework to provide routing assistance and trip cancellation recommendations to affected vehicles. The framework relies on the connected vehicle environment for real-time link performance measures and flood data and evaluates the trip of the vehicle to determine whether it is affected by the flood or not. If the vehicle is affected and can still leave its origin, the framework generates the corresponding routing assistance in the form of hyperpath(s) or set of alternative paths. On the other hand, a vehicle with a closed origin receives a warning to wait at origin, while a vehicle with an affected destination is assigned to a new safe one. This framework is tested on two transportation networks. The evaluation of the framework's scalability to different network sizes and the sensitivity of the results to various flood characteristics, policy-related variables and other dependencies are performed using simulated vehicle data and hypothetical flood scenarios. The computation times depends on the network size and flood depth but have generally an average of 1.47 seconds for the largest tested network and deepest tested flood. The framework has the potential to alleviate the impacts and inconveniences associated with flooding. / Master of Science / Flooding is a natural hazard that occurs with heavy rainfalls and high tides. In extreme situations, a flood in an area results in the evacuation of its occupant. Yet, in many cases, a flood is less severe and may only result in roads closures without necessitating evacuation. During these situations, and as transportation engineers, our ultimate goal is to maintain efficient and safe traffic operations. This thesis introduces a framework that focuses on providing routing assistance to affected vehicles and sending warnings to unaffected ones. It relies on the future connected vehicle environment which enables the communication between a traffic management center and equipped vehicles. The traffic management center collects and processes the information about the link performance measures and the weather and flood forecasts and sends them to the connected vehicles. Each vehicle has an in-vehicle navigation system in which the proposed framework is embedded. The framework, depending on the vehicle’s origin, destination, path and departure time and based on the flood’s characteristics, determines whether the vehicle is affected or not. If the vehicle is unaffected, it will receive a warning with the areas to avoid in case of any deviation and it can resume its trip as intended. If affected, the vehicle will either receive a warning to stay at its origin or routing guidance in the form of hyperpath or a set of alternative paths. The proposed framework has been evaluated on two transportation networks modeled in VISSIM based on the city of Virginia Beach, VA. Using simulated vehicle data and generated flood scenarios, several tests were executed to evaluate the scalability of the framework to different transportation networks along with the sensitivity of the results to variation in flood characteristics, policy-dependent variables and other dependencies. Concentrated, more intense and deeper floods resulted in a higher impact on the system. Yet, the analysis of the output is highly dependent on the location of the origin and destination of the vehicles with respect to the flooded roads. Thus, a lot of the output explanation are specific. Computation time increased with the increase in network size and in the flood depth. Nevertheless, it is still small and reasonable and further increase in both parameters (network size and flood depth) can be tested in future along with multiple techniques that minimize the computation time. This framework addresses the flooding hazard which road users are experiencing more and more nowadays. This hazard brings risks and inconveniences to our daily life. Thus, the development of this framework is of great interest to our society as it is a promising tool that has the potential to offer benefits, in terms of safety and mobility, to roads users exposed to a flood hazard. Its first implementation shows that it is a timely application with a potential to perform even better with future improvements.

With connected and autonomous vehicles, no optimal standard or framework currently exists, outlining the right level of information sharing for cooperative autonomous driving. Cooperative Perception is proposed among vehicles, where every vehicle is transformed into a moving sensor platform that is capable of sharing information collected using its on-board sensors. This helps extend the line of sight and field of view of autonomous vehicles, which otherwise suffer from blind spots and occlusions. This increase in situational awareness promotes safe driving over a short range and improves traffic flow efficiency over a long range. This thesis proposes a methodology for cooperative perception for autonomous vehicles over a short range. The problem of cooperative perception is broken down into sub-tasks of cooperative relative localization and map merging. Cooperative relative localization is achieved using visual and inertial sensors, where a computer-vision based camera relative pose estimation technique, augmented with position information, is used to provide a pose-fix that is subsequently updated by dead reckoning using an inertial sensor. Prior to map merging, a technique for object localization using a monocular camera is proposed that is based on the Inverse Perspective Mapping technique. A mobile multi-robot testbed was developed to emulate autonomous vehicles and the proposed method was implemented on the testbed to detect pedestrians and also to respond to the perceived hazard. Potential traffic scenarios where cooperative perception could prove crucial were tested and the results are presented in this thesis. / MS / Perception in Autonomous Vehicles is limited to the field of view of the vehicles’ onboard sensors and the environment may not be fully perceivable due to the presence of blind spots and occlusions. To overcome this limitation, Vehicle-to-Vehicle wireless communication could be leveraged to exchange locally sensed information among vehicles within the vicinity. Vehicles may share information about their own position, heading and velocity or go one step further and share information about their surroundings as well. This latter form of cooperative perception extends each vehicle’s field of view and line of sight, and helps increase situational awareness. The result is an increase in safety over a short range whereas communication over a long range could help improve traffic flow efficiency. This thesis proposes one such technique for cooperative perception over a short range. The system uses visual and inertial sensors to perform cooperative localization between two vehicles sharing a common field of view, which allows one vehicle to locate the other vehicle in its frame of reference. Subsequently, information about objects in the surroundings of one vehicle, localized using a visual sensor is relayed to the other vehicle through communication. A mobile multi-robot testbed was developed to emulate autonomous vehicles and to experimentally evaluate the proposed method through a series of driving scenario test cases in which cooperative perception could be effective and crucial to the safety and comfort of driving.

The environmental impact of a transportation system is critical in the assessment of the transportation system performance. Eco-Cooperative Adaptive Cruise Control (Eco-CACC) systems attempt to minimize vehicle fuel consumption and emission levels by controlling vehicle speed and acceleration levels. The majority of previous research efforts developed and applied Eco-CACC systems on either freeway or signalized intersections independently on simple and small transportation networks without consideration of the interaction among these controls. This thesis extends the state-of-the-art in Eco-CACC evaluation by conducting a comprehensive evaluation on a complex network considering Eco-CACC control on both freeways and arterials individually and simultaneously. The goal of this study is to compare Eco-CACCs on arterial facilities (Eco-CACC-A), freeway facilities (Eco-CACC-F) and both facilities (Eco-CACC-F+A). The effects of Eco-CACC are evaluated considering various Measures of Effectiveness (MOEs), including: average vehicle delay, fuel consumption, and emission levels using simulated results from INTEGRATION, a microscopic traffic assignment and simulation software, considering different freeway speed limits, traffic demand levels and system market penetration rates. In total, 19 traffic scenarios for each of the four different cases (Eco-CACC-A, Eco-CACC-F and Eco-CACC-F+A plus a base no control case) were tested. In total 760 simulation runs were conducted (4 cases * 19 scenarios * 10 repetitions). T-tests and pairwise mean comparison (Tukey HSD) were conducted to identify any statistical differences between control cases and the base case from the simulation results. This thesis shows that arterial and freeway Eco-CACCs can work well together and their effects will be largely influenced by network characteristics. / Master of Science

Various methods are used to collect pavement surface conditions, varying from manual checks by employees to specialized equipment. However, traditional methods usually require expensive specialized equipment and are time-consuming and costly. This thesis examines the use of connected vehicles (CV) to collect pavement surface data estimated based on sensors mounted in the cars. This concept was first analyzed through a literature review, where CV technology was examined to measure roughness, friction, and pothole data. Data collection was performed by a specialized company, utilizing sensor data from standard manufactured cars. A sample of data from the Richmond district of Virginia, was used to compare the estimated values to the standard International Roughness Index (IRI) values used by VDOT. Data collected using both methods were matched using Matlab code to have a common linear referencing system. Subjective visual comparison showed that both data sets had similar trends, highlighting roads with rough sections. A quantitative analysis performed to compare the average results of the two methods on a sample of uniform sections, showed a high correlation. A technology assessment was also conducted to evaluate the maturity level of the CV, which was found to be at least a TRL 7. This suggests that CV technology can be a valuable addition to the traditional methods for collecting pavement surface data. / Master of Science / Traditional methods of assessing road conditions usually require expensive specialized equipment and can be time-consuming and expensive. This study explores a new approach, using connected vehicles to gather road data through car sensors. A review of existing research showed that connected vehicle technology could measure road surface characteristics such as roughness, friction, and potholes. Data collected from cars in Virginia's Richmond district was compared to standard road condition data from the Virginia Department of Transportation. Both methods showed similar results, with a high correlation value, indicating a strong match. The technology behind connected vehicles was assessed and found to be a potentially useful, cost-effective alternative to traditional road condition assessment methods.

This dissertation first conducts a study on raw-data level cooperative perception for enhancing the detection ability of self-driving systems for connected autonomous vehicles (CAVs). A LiDAR (Light Detection and Ranging sensor) point cloud-based 3D object detection method is deployed to enhance detection performance by expanding the effective sensing area, capturing critical information in multiple scenarios and improving detection accuracy. In addition, a point cloud feature based cooperative perception framework is proposed on edge computing system for CAVs. This dissertation also uses the features' intrinsically small size to achieve real-time edge computing, without running the risk of congesting the network. In order to distinguish small sized objects such as pedestrian and cyclist in 3D data, an end-to-end multi-sensor fusion model is developed to implement 3D object detection from multi-sensor data. Experiments show that by solving multiple perception on camera and LiDAR jointly, the detection model can leverage the advantages from high resolution image and physical world LiDAR mapping data, which leads the KITTI benchmark on 3D object detection. At last, an application of cooperative perception is deployed on edge to heal the live map for autonomous vehicles. Through 3D reconstruction and multi-sensor fusion detection, experiments on real-world dataset demonstrate that a high definition (HD) map on edge can afford well sensed local data for navigation to CAVs.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional. / Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.