Seamless Graph Task Scheduling over Dynamic Vehicular Clouds: A Hybrid Methodology for Integrating Pilot and Instantaneous Decisions
Preprint
Abstract
Vehicular clouds (VCs) play a crucial role in the Internet-of-Vehicles (IoV) ecosystem by securing essential computing resources for a wide range of tasks. This paPertackles the intricacies of resource provisioning in dynamic VCs for computation-intensive tasks, represented by undirected graphs for parallel processing over multiple vehicles. We model the dynamics of VCs by considering multiple factors, including varying communication quality among vehicles, fluctuating computing capabilities of vehicles, uncertain contact duration among vehicles, and dynamic data exchange costs between vehicles. Our primary goal is to obtain feasible assignments between task components and nearby vehicles, called templates, in a timely manner with minimized task completion time and data exchange overhead. To achieve this, we propose a hybrid graph task scheduling (P-HTS) methodology that combines offline and online decision-making modes. For the offline mode, we introduce an approach called risk-aware pilot isomorphic subgraph searching (RA-PilotISS), which predicts feasible solutions for task scheduling in advance based on historical information. Then, for the online mode, we propose time-efficient instantaneous isomorphic subgraph searching (TE-InstaISS), serving as a backup approach for quickly identifying new optimal scheduling template when the one identified by RA-PilotISS becomes invalid due to changing conditions. Through comprehensive experiments, we demonstrate the superiority of our proposed hybrid mechanism compared to state-of-the-art methods in terms of various evaluative metrics, e.g., time efficiency such as the delay caused by seeking for possible templates and task completion time, as well as cost function, upon considering different VC scales and graph task topologies.Keywords
All Related Versions
This publication has 41 references indexed in Scilit:
- A Trade-Off Task-Offloading Scheme in Multi-User Multi-Task Mobile Edge ComputingIEEE Access, 2022
- Task offloading method of edge computing in internet of vehicles based on deep reinforcement learningCluster Computing, 2022
- A Comprehensive Review of Computing Paradigms, Enabling Computation Offloading and Task Execution in Vehicular NetworksIEEE Access, 2022
- Task scheduling with precedence and placement constraints for resource utilization improvement in multi-user MEC environmentJournal of Systems Architecture, 2021
- Multi-Task Offloading over Vehicular Clouds under Graph-based Representation2020
- Dependency-Aware Task Scheduling in Vehicular Edge ComputingIEEE Internet of Things Journal, 2020
- Allocation of Computation-Intensive Graph Jobs Over Vehicular Clouds in IoVIEEE Internet of Things Journal, 2019
- SubISO: A Scalable and Novel Approach for Subgraph Isomorphism Search in Large Graph2019
- Mobile Edge Computing: A Survey on Architecture and Computation OffloadingIEEE Communications Surveys & Tutorials, 2017
- Vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication in a heterogeneous wireless network – Performance evaluationTransportation Research Part C: Emerging Technologies, 2016