A Truthful Auction for Graph Job Allocation in Vehicular Cloud-assisted Networks
Abstract : Vehicular cloud computing has emerged as a promising solution to fulfill users’ demands on processing computation-intensive applications in modern driving environments. Such applications are commonly represented by graphs consisting of components and edges. However, encouraging vehicles to share resources poses significant challenges owing to users’ selfishness. In this paper, an auction-based graph job allocation problem is studied in vehicular cloud-assisted networks considering resource reutilization. Our goal is to map each buyer (component) to a feasible seller (virtual machine) while maximizing the buyers’ utility-of-service, which concerns the execution time and commission cost.First, we formulate the auction-based graph job allocation as an integer programming (IP) problem. Then, a Vickrey-Clarke-Groves based payment rule is proposed which satisfies the desired economical properties, truthfulness and individual rationality. We face two challenges: 1) the above-mentioned IP problem is NP-hard; 2) one constraint associated with the IP problem poses addressing the subgraph isomorphism problem. Thus, obtaining the optimal solution is practically infeasible in large-scale networks. Motivated by which, we develop a structure-preserved matching algorithm by maximizing the utility-of-service-gain, and the corresponding payment rule which offers economical properties and low computation complexity. Extensive simulations demonstrate that the proposed algorithm outperforms the benchmark methods considering various problem sizes.
? In this case, our BRMA algorithm is compared with the random strategy selection method due to the lack of an existing algorithm for the problem.
? Note that in this case, load parameters and prices of the DCs are unknown prior to the graph job assignment; hence the abovedefined greedy algorithms can not be applied to this setting.
? In simulations, we use the term “incurred power” referring to the difference between the power consumption of the GDCN after the graph jobs are assigned as compared to that before the assignment.
? The graph job allocation problem in dynamic network environments have rarely been studied.
? In such networks, the mobility of servers and users as well as interdependency of the components pose major challenges to the design of applicable allocation methods. We were among the few working on addressing such challenges.
? In, we investigated the multi-graph-task offloading problem while considering the potential competition among components caused by the concurrency of multiple tasks.
? To the best of our knowledge, this paper is among the first which proposes a truthful auction model for the graph job allocation problem over VCs while considering resource reutilization.
• In , a resource allocation scheme is proposed resulting in efficient utilization of the resources while increasing the revenue of the mobile cloud service providers.
• One of the pioneer works addressing resource allocation in GDCNs considering the power consumption state of the DCs is , where a distributed algorithm, called DGLB, is proposed for real-time geographical load balancing.
• The proposed system models do not capture the power consumption of the utilized DCs.
• This is despite the fact that in GDCNs, the execution cost is mainly determined by the real-time power consumption of the DCs
? Based on thorough numerical analysis and comparative evaluations, we demonstrate that the performance of the proposed low complexity structurepreserved matching algorithm can approach that of the optimal algorithm, while outperforming baseline methods considering various problem sizes.
? In semi-static environment where the topologies of either the computing servers or the service requestors are fixed, a novel framework for energy-efficient graph job allocation in geo-distributed cloud networks was introduced in , where solutions are obtained for data center networks considering various scales.
|