TDRA: A Truthful Dynamic Reverse Auction for DAG Task Scheduling Over Vehicular Clouds

Vehicular Clouds (VCs) have attracted tremendous attention for offering commendable computing services to vehicles with computation-intensive tasks. Such tasks are often represented as Directed Acyclic Graphs (DAGs) consisting of several interdependent subtasks and directed edges. Processing of DAG...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on vehicular technology 2024-03, Vol.73 (3), p.4337-4351
Main Authors: Liu, Zhang, Zhao, Yifeng, Hosseinalipour, Seyyedali, Gao, Zhibin, Huang, Lianfen, Dai, Huaiyu
Format: Article
Language:English
Subjects:
Cloud computing
Computational modeling
directed acyclic graph (DAG)
Dynamic scheduling
dynamic task scheduling
Economic analysis
Enumeration
Graph theory
Graphical representations
Optimization
Polynomials
Pricing
Processor scheduling
Provisioning
Resource management
reverse auctions
Task analysis
Task scheduling
Vehicle dynamics
Vehicles
Vehicular cloud (VC) computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Vehicular Clouds (VCs) have attracted tremendous attention for offering commendable computing services to vehicles with computation-intensive tasks. Such tasks are often represented as Directed Acyclic Graphs (DAGs) consisting of several interdependent subtasks and directed edges. Processing of DAG tasks often needs pooling the computation resources of vehicles. However, the selfishness of vehicles prevents them from sharing their resources. To this end, we propose a Truthful Dynamic Reverse Auction (TDRA) mechanism to motivate vehicles to participate in service provisioning. To realize TDRA, we first propose an enumeration-based allocation strategy to optimally allocate subtasks among vehicles and obtain a Vickrey-Clarke-Groves (VCG)-based pricing strategy that can ensure the economic properties of individual rationality and truthfulness. Then, to deal with the high computational complexity of obtaining the optimal solution, we develop a near-optimal Dynamic Bilateral Ranking (DBR) allocation strategy to allocate subtasks within polynomial time and design a critical value-based pricing strategy that can also guarantee the two above-mentioned economic properties. Through simulating real-world movement traces of vehicles, we demonstrate that DBR outperforms the existing benchmarks, and verify our theoretical analysis on the economic properties of our developed pricing strategy.
ISSN:0018-9545
1939-9359
DOI:10.1109/TVT.2023.3329141