Seamless Graph Task Scheduling Over Dynamic Vehicular Clouds: A Hybrid Methodology for Integrating Pilot and Instantaneous Decisions

作     者：Guo, Bingshuo Liwang, Minghui Xia, Xiaoyu Li, Li Jiao, Zhenzhen Hosseinalipour, Seyyedali Wang, Xianbin 

作者机构：Tongji University Department of Control Science and Engineering Shanghai200092 China Xiamen University School of Informatics Xiamen361005 China Tongji University Shanghai Institute of Intelligent Science and Technology National Key Laboratory of Autonomous Intelligent Unmanned Systems Frontiers Science Center for Intelligent Autonomous Systems Shanghai200092 China RMIT University School of Computing Technologies MelbourneVIC3000 Australia China Academy of Information and Communications Technology iF-Labs Beijing Teleinfo Technology Company Ltd. Beijing100191 China University at Buffalo-SUNY Department of Electrical Engineering GetzvilleNY14068 United States Western University Department of Electrical and Computer Engineering LondonONN6A 3K7 Canada 

出 版 物：《IEEE Transactions on Services Computing》 (IEEE Trans. Serv. Comput.)

年 卷 期：2025年第18卷第3期

页      面：1753-1768页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 080204[工学-车辆工程] 0802[工学-机械工程] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China Shanghai Municipal Science and Technology Major Project Shanghai Pujiang Programme Aeronautical Science Foundation of China Chinese Academy of Engineering, Strategic Research and Consulting Program 

主　　题：Undirected graphs 

摘      要：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 inapplicable 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. © 2008-2012 IEEE.