TDRA: A Truthful Dynamic Reverse Auction for DAG Task Scheduling Over Vehicular Clouds
Zhang Liu, Yifeng Zhao, Seyyedali Hosseinalipour, Zhibin Gao, Lianfen Huang, Huaiyu Dai
Abstract
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.