Novel data partitioning and scheduling schemes for dynamic federated vehicular cloud

Abstract

In the last decade, many Intelligent Transport Systems (ITS) applications, that rely on the Internet cloud infrastructure have been deployed to provide services to clients in vehicular environments. However, the Internet cloud suffers from high latency in service access and intermittent Internet disconnection in vehicular environments. In response to these challenges, researchers have proposed the use of other distributed computing technologies such as mobile cloud computing, edge computing, and vehicular cloud computing which may rely on Wireless Local Area Networks (WLAN) or Ad-hoc networks for communication to provide computing resources and services in vehicular environments. Vehicular cloud computing, an emerging distributed computing paradigm that provides cloud services using the resources embedded in vehicles and Road Side Units (RSUs), is arguably the best alternative to other distributed computing systems because of its advantages. The provision of vehicular cloud services leads to efficient utilization of the abundant resources in embedded vehicles and therefore embraces green technology in vehicular environments. Considering that modern vehicles and RSUs have been designed with communication capabilities through the use of the Vehicular Ad-hoc Network (VANET), vehicular cloud computing may not require additional communication hardware infrastructure installation along roads and at parking lots before its deployment. Furthermore, access to vehicular cloud services may involve a relatively lower latency and fewer intermittent disconnections due to the close proximity of vehicular cloud resources to clients and the use of VANET which may provide better connections among vehicular resources and clients than the connection to Internet cloud in vehicular environments. As with all emerging technologies of which vehicular cloud is not an exception, some challenges need to be addressed before its full real-world deployment. The challenges of vehicular cloud computing are mainly caused by the unique characteristics of vehicular resources and the limited communication bandwidth of VANET. In vehicular environments, i.e., on roads and parking lots, vehicles are not permanently stationed but mobile, making the resources embedded in vehicles highly mobile. Also, the resources of vehicles that are organized to provide cloud services belong to different people (distributed ownership). The high mobility and distributed ownership of resources imply that vehicular resources may exit the provisioned vehicular cloud abruptly by either withdrawal of resources by the resource owner or intermittent network disconnection caused by the high mobility of vehicles. Therefore distributed ownership of resources and high mobility of vehicles cause vehicular resources to be volatile, making their availability and reliability unpredictable. The capacity constraint of the communication bandwidth of VANET, which serves as a communication backbone of vehicular cloud, implies that the transmission of data-intensive and bandwidth-intensive applications in vehicular environments is a challenge in vehicular cloud computing. Considering that the distributed ownership of resources, limited communication bandwidth, and high mobility of vehicles lead to low availability and low reliability of resources in vehicular cloud computing, they adversely affect almost all resource management operations, such as virtual machine migration. Therefore, the main focus of this dissertation is to propose novel solutions to address the challenges of vehicular cloud and ameliorate the adverse effects of the identified characteristics of vehicular cloud computing. As an introduction, the background of vehicular cloud computing and a detailed survey of resource management operations in vehicular cloud are presented using a three-phase taxonomy of resource management techniques proposed in this dissertation. Based on the review of vehicular cloud computing concepts, a novel distributed vehicular computing paradigm, Vehicular Volunteer Computing (VVC), is proposed in this dissertation. VVC is a volunteer computing platform where vehicle owners may donate their idle processing units towards the execution of scientific and other projects that are beneficial to a community, such as the "Compute The Cure" cancer project. The concept of a Dynamic Federated Vehicular Cloud (DFVC) is introduced in this dissertation to overcome the challenge of limited resource capacity and volatility of resources in vehicular cloud. The DFVC entails the organization of resources from different vehicles moving on the road to provide a specific vehicular cloud service such as Computation-as-a-Service (CaaS). Although the resources are collated from different vehicles in the formation of DFVC, they are organized as a single logical unit for the provision of services. The formation of a DFVC involves forming resource-based clusters, i.e., grouping vehicles with similar resource and mobility characteristics as a single unit and selecting a leader, known as a cluster head, to manage the resources in a cluster of vehicles. By considering the structure of resource-based clusters formed in a Region of Interest (RoI), two different DFVC schemes are proposed in this dissertation: the Cluster-Based Vehicular Cloud (CBVC) and the Platoon-Based Vehicular Cloud (PBVC). In the CBVC, vehicles (owners) with a high reputation and idle resources on an RoI on the road are organized into clusters without adhering to the condition that all cluster members use the same lane and maintain a fixed gap between vehicles. The PBVC, on the other hand, is a variant of the cluster-based vehicular cloud that requires strict adherence to a constant gap, i.e., the distance between all vehicles and the use of the same lane throughout the entire period of the provision of cloud services. In other words, the PBVC is a convoy with a constant gap between all vehicles whose resources are organized to offer specific cloud services. In order to address the challenge of limited computation capacity of resources and constraint communication bandwidth, a large divisible data load to be processed by the DFVC is partitioned and distributed to the individual vehicular nodes using efficient Data partitioning and Scheduling (DPS) schemes. One of the central themes of this dissertation is, therefore, to design and implement novel DPS schemes that consider the characteristics of vehicular resources of the DFVC and the communication channel of VANET: the communication backbone for DFVC. By considering the computation capacity of resources, data transmission bandwidth capacity, and communication delay experienced in data transmission in VANET, efficient DPS schemes proposed in this dissertation are designed through mathematical models developed using timing and data flow diagrams. The DPS schemes for the CBVC, and PBVC are modeled differently because of their unique characteristics and operations. The proposed DPS scheme for the CBVC was modeled with the consideration that the cluster head determines the data chunk for each vehicle using derived closed form mathematical equations and then distributes the data chunks directly as a single hop to the respective vehicles in the CVBC to process. After processing, the vehicles then transmit the processed data chunks directly to the cluster head. The DPS scheme for the CBVC is implemented as part of a unified data, resource, and channel management framework, which is referred to as the UniDRM in this dissertation. Considering different criteria or objectives for data partitioning and scheduling, three distinct DPS schemes, time-aware, cost-aware, and reliability-aware, are also proposed in this dissertation. For the PBVC, the data partitioning is carried out by the lead node, i.e., the first node of the platoon, using derived closed form equations. The determined data chunks of the platoon members are then distributed either directly (single hop) or through multi-hop transmission. The closed form equations were derived considering data flow and timing diagrams designed based on how vehicles in platoons exchange information with their neighbor nodes, which is referred to as platoon Information Flow Topologies (IFT). In this dissertation, existing platoon IFTs: the Bi-Directional (BD), Bi-Directional Lead (BDL), and the All- to- All IFT (A2A) are modified to derive mathematical models for six different DPS schemes, namely, the Bi-Directional-Recursive (BD-R), Bi-Directional Interlaced (BD-I), Bi-Directional Lead-Recursive (BDL-R), Bi-Directional Lead-Interlaced (BDL-I), Bi-Directional Lead Aggregate-Recursive (BDLA-R), and Bi-Directional Lead Aggregate-Interlaced (BDLA-I). Through realistic simulations developed via the use of the simulation platforms Omnet++, Sumo, Veins, and Plexe, a detailed performance analysis of the proposed DPS schemes were carried out. By developing the different DPS schemes for the PBVC, one of the long-standing challenges of divisible data partitioning and scheduling in the literature: the modeling and derivation of closed form equations for determining the percentage of data chunks and the processing time of the linearly arranged network of connected heterogeneous processors, is addressed. According to the literature, there are no closed form equations for the heterogeneous linear network of connected processors because of the complicated combinatorial terms that appear in expressions for individual data partitions while solving the recursive equations. However, using algebraic manipulations, closed form equations have been derived and modeled in this dissertation. In all, this dissertation presents novel solutions to key challenges of vehicular cloud computing, including the limited available capacity of resources in vehicles and the bandwidth constraint of the vehicular communications channel.