A Truthful Auction for Graph Job Allocation in Vehicular Cloud-assisted Networks
Zhibin Gao Minghui LiWang Seyyedali Hosseinalipour Huaiyu Dai Xianbin Wang
cs.DC cs.NI







A Truthful Auction for Graph Job Allocation in Vehicular Cloud-assisted Networks
    Zhibin Gao*, Minghui LiWang*, Member, IEEE, Seyyedali Hosseinalipour, Student Member, IEEE, Huaiyu Dai, Fellow, IEEE, Xianbin Wang, Fellow, IEEE


Zhibin Gao (gaozhibin@xmu.edu.cn) is with the school of Informatics, Xiamen University, Fujian, China. Minghui LiWang (corresponding author, mliwang@uwo.ca) and Xianbin Wang (xianbin.wang@uwo.ca) are with the department of Electrical and Computer Engineering, University of Western Ontario, Ontario, Canada. Seyyedali Hosseinalipour (shossei3@ncsu.edu) and Huaiyu Dai (hdai@ncsu.edu) are with the department of Electrical and Computer Engineering, North Carolina State University, NC, USA. *: These authors contributed equally to this work.






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.




Vehicular cloud-assisted networks, truthful auction, graph job allocation, subgraph isomorphism.

    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================







§ INTRODUCTION


With the rapid growth of connected devices in Internet of things (IoT) networks, especially smart cars, the Internet of vehicles (IoV) has become an emerging paradigm that offers safety, convenience, and entertainment for both drivers and passengers. Furthermore, technological advances in computing processors and sensing devices has offered innovative solutions for vehicular applications with resource hungry features. Such applications include face/behavior identification, simultaneous localization and mapping, autonomous driving, and advanced driver assistants, all of which require massive computational resources <cit.>. Notably, graph-based representation is utilized to characterize the non-negligible internal structures of such applications. In such scenarios, each application (the “application” is interchangeable with “job” or “graph job” throughout) is modeled as a graph, where the vertices (components) represent either data sources or data processing units, while the edges describe the dependency between the vertices <cit.>.

However, the limitation of a single smart vehicle caused by resource and capability constraints of on-board equipment, may hinder the fulfillment of graph job execution requirements. One approach is to process such applications on remote data centers or mobile edge computing (MEC) servers <cit.>. Nonetheless, the former may incur enormous costs due to bulk data transfer and latency, while the limited resource as well as signal coverage of MEC servers may cause unsatisfactory offloading performance. Thus, vehicular cloud computing (VCC) <cit.> has been proposed to provide flexible and effective computing services for the users (called job owners, JOs). In VCC platform, vehicles with surplus resources act as servers (called service providers, SPs) to form vehicular clouds (VCs) via vehicle-to-vehicle (V2V) communications, which enables the processing of jobs in parallel. We summarize two major challenges facing the allocation of graph jobs over VCs:

1) Obtaining the feasible mappings between the components of the jobs and the SPs while satisfying the heterogeneous computational demands of the components requires solving the subgraph isomorphism problem, which is known to be NP-complete.

2) Avoiding behaviors that sellers may misreport their bids while motivating the selfish SPs to lease their idle resources is a major challenge, since reporting untruthful bid may potentially lead to a higher profit for the SPs. 

Addressing the aforementioned challenges is the main motivation of this paper. We propose innovative policies for a marketplace considering resource reutilization. The proposed framework comprises three participants: sellers (service providers), buyers (service requestors), and the broker that manages the acution while offering the desired economical properties of truthfulness and individual rationality <cit.>. We investigate an auction mechanism for graph job allocation, where each JO has a job modeled as an undirected weighted graph of components (buyers) with different demands for execution time. A virtual machine (VM)-based <cit.> representation is utilized to quantize available resources of SPs. Also, the VC is abstracted to an undirected weighted graph consisting of VMs (sellers) that can be reutilized after release, where sellers can provide heterogeneous computational capabilities. To maximize the sum of the utility-of-service, an optimal and a sub-optimal algorithm together with the relevant payment rules are proposed to map each buyer to a feasible seller. The mapping ensures that the requirements of the graph job execution are met, and also provides truthfulness as well as individual rationality as two key desired market properties.



 §.§ Related work

There existing works devoted to studying the computation-intensive job allocation that can be roughly divided into two categories: a) allocation of bit stream-represented jobs without considering the inherent dependencies, such as <cit.>; and b) allocation of graph-represented jobs upon existence of inner dependencies among the components, which is also the main focus of this paper, such as <cit.>. Moreover, the environment in which the graph job allocation is studied can be divided into three types based on the dynamism of the network topology: static, semi-static, and dynamic. By assuming the static topologies for both the servers and the users, authors in <cit.> proposed a randomized job scheduling algorithm that stabilizes a system with job arrivals/departures and facilitates a smooth trade-off between the minimization of the average execution cost and the servers' queue length. 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 <cit.>, where solutions are obtained for data center networks considering various scales. A lyapunov optimization-based dynamic offloading approach is developed in <cit.> to satisfy the constraints on energy conservation and application execution time. The scheduling of parallel jobs composed of a set of independent tasks was studied in <cit.> by mainly considering energy consumption and job completion time. In <cit.>, a VC-based computation offloading mechanism was introduced which enabled tasks being executed in different vehicles to minimize the overall response time while enhancing the capacity of the edge clouds. 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. A randomized job allocation mechanism based on hierarchical tree decomposition was proposed in our previous work <cit.>, which efficiently solves the allocation problem considering the trade-off between the task completion time and data exchange cost among the SPs. In <cit.>, we investigated the multi-graph-task offloading problem while considering the potential competition among components caused by the concurrency of multiple tasks.




However, economical factors and incentive issues related to the graph job allocation haven't been fully addressed in the above-mentioned works. Auctions have been widely applied and regarded as a popular trading form for effective price discovery and resource sharing among the users. For the semi-static network environments (e.g., <cit.>), authors in <cit.> proposed two double auction schemes with dynamic pricing to determine the matched pairs between industrial-IoT mobile devices and edge servers. In <cit.>, a stochastic offloading approach in mobile cloud computing through online auction was presented while achieving desirable economic properties such as truthfulness and individual rationality. A truthful double auction mechanism was proposed in <cit.> to bridge users' task requirements and providers' resources in two-sided cloud markets. In <cit.>, the authors modeled the VM resource allocation problem among edge clouds and mobile users as an n-to-one weighted bipartite graph matching problem with 0-1 knapsack constraints, and then designed a greedy approximation algorithm to solve the problem. Authors in <cit.> focused on vehicular fog computing (VFC) environment based on smart parking, where a VFC-aware parking reservation auction was proposed to guide the on-the-move vehicles to the available parking places with less effort and exploite the computing services of the parked vehicles to assist the delay-sensitive tasks. In the dynamic environment, authors in <cit.> proposed different truthful auction models for homogeneous and heterogeneous task models (e.g., tasks with the same and different resource requirements). In <cit.>, a distributed auction model was investigated to facilitate the resource trading between the owner of the tasks and the mobile devices participating in task execution. However, the above mentioned auction-based works maily focused on the bit stream-represented jobs, and thus the inherent interdependencies among the components of the jobs has not been fully considered.



 §.§ Novelty and Contribution

In existing literature concerned with the semi-static or dynamic network environment, addressing the job allocation problem under graph-based representation while applying auction theory are rarely investigated. Moreover, the cocept of resource reutilization allowing the usage of a VM after its release is neglected in most of the above-mentioned works, which offers more options to buyers. 
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. The main contributions of this paper can be summarized as follows:



  * We establish a novel VC-assisted graph job allocation marketplace which enables multiple computation-intensive graph jobs to be mapped (offloaded) to the SPs, while considering the reutilization of resources. 


  * We propose an auction-based graph job allocation mechanism, where the components of jobs are acted as buyers with various demands. Sellers are defined by considering VM reutilization with heterogeneous capabilities. To achieve the maximum total utility-of-service of the buyers, we formulate the graph job allocation as an integer programming (IP) problem under limited opportunistic communications, which is NP-hard. Moreover, one of the constraints related to preserving the graph job structures requires addressing the subgraph isomorphism problem. We tailor a Vickrey–Clarke–Groves (VCG)-based payment rule to protect the benefits of the sellers, prevent misreporting behaviors, and achieve individual rationality.


  * To tackle the IP problem for obtaing a feasible mapping between the buyers and the sellers, we first develop an optimal algorithm to find the graph job allocation solution while guaranteeing truthfulness and individual rationality from different perspectives of the SPs, the VMs and the sellers. We show that this method suffers from a high computational complexity, which makes it ineffective when encountering a large number of jobs and SPs or upon having complicated job and network topology. 


  * To obtain a near optimal solution for the proposed IP problem in polynomial time, we propose a structure-preserved matching algorithm based on maximizing the utility-of-service-gain and its corresponding payment rule. We demonstrate that the low computational complexity of this method makes it a good fit for large and fast-changing IoV networks. Moreover, we prove that the proposed method enjoys desirable economic properties of truthfulness and individual rationality. 


  * Based on thorough numerical analysis and comparative evaluations, we demonstrate that the performance of the proposed low complexity structure-preserved matching algorithm can approach that of the optimal algorithm, while outperforming baseline methods considering various problem sizes.



The rest of this paper is organized as follows.  System model and design targets are introduced in Section 2. We formulate the IP problem and propose an adequate VCG-based payment rule in Section 3. This section also contains the proofs of the desired economical properties and the related optimal graph job allocation algorithm. In Section 4, a structure-preserved matching algorithm based on utility-of-service-gain maximization is proposed. The conomical properties are also proved to be true in the same section. The performance evaluation through comprehensive simulations is conducted in Section 5 before drawing the conclusion in Section 6.




§ SYSTEM MODEL AND DESIGN TARGETS


In the following, we mainly study the problem in one VC for tractable analysis,  since the proposed auction-based graph job allocation mechanism
is universal across all VCs. Consider a VC containsing |O| JOs and |S| SPs and several RSUs alongside the road. Note that the data size of resulting feedback of the job execution is much smaller than that of the application data <cit.>, alternatively, results can be transferred back to the JO via a multi-hop V2V routing path or uploaded to RSUs for future delivery in case the V2V connection is disrupted, and thus neglected in this paper. The framework of the proposed auction for VC-assisted graph job allocation is shown in Fig. 1(a), and the main notations are summarized in TABLE 1. 
The related models in this paper are introduced hereafter.




 §.§ Opportunistic contact model



A contact event between vehicles n and m occurs during τ∈ (τ_1, τ_2) when L_n (τ_1)-L_m(τ_1)>R,  L_n(τ)-L_m(τ) ≤ R and L_n (τ_2)-L_m(τ_2) >R, where L_n(τ) and L_m(τ) denote the respective locations, · represents the Euclidean distance, and R indicates the communication radius of the vehicles. Generally, the contact duration among the vehicles obeys an exponential distribution <cit.> with parameter λ_n, m; thus, the probability of the contact duration Δτ_n, m between two vehicles n and m being larger than T is given by prob(Δτ_n, m>T|λ_n, m)= e^-Tλ_n, m. Correspondingly, the larger the value of prob(Δτ_n, m>T|λ_n, m) is, the more insurance can be achieved to protect data interaction among the respective vehicles. 



 §.§ Modeling the buyers


Consider a set of JOs O, where each JO O_n∈O owns a graph job G^O_n=(V^O_n, E^O_n, W^O_n) that contains a set of components V^O_n ={b_n, x|n∈{1,2,…, | O| }, x∈{1,2,…, |V^O_n|}} where each component b_n,x is associated with a tolerable execution time t_n, x (seconds); and a set of edges E^O_n={e^O_n_xx'|x, x'∈{1,2,…, |V^O_n|}, x≠ x'} with associated weight W^O_n={ω^O_n_xx'|x, x'∈{1,2,…, |V^O_n|}, x≠ x'}. In this model, the edges represent data flows among the components and the weight ω^O_n_xx' of edge e^O_n_xx' indicates the requested connect duration for intermediate data exchange between components b_n, x and b_n, x', which is considered to be equal to or lower than the smaller tolerable execution time of the two. Also, the contact duration of the SPs that handle components b_n, x and b_n, x' should be ideally equal to or larger than ω^O_n_xx'. A job G^O_n represents how the computation is supposed to be splitted among components in V^O_n. In this paper, each component b_n, x∈V^O_n is seen as a buyer and mapped to an available seller in the related VC, by paying a certain commission for the computing service.




 §.§ Modeling the sellers


We use a VM-based presentation to describe the available resources of the SPs. In this case, each SP S_m∈S has a collection of VMs VM_m={v_m,1, …, v_m,|VM_m|} that are fully connected (namely, can communicate continuously with each other), where v_m,y denotes the y th VM on S_m. Moreover, v_m,y can provide the computational capability of c_m,y (seconds) that is the execution time of processing one component of a graph job. The VM reutilization factor enables each VM v_m,y to serve more than one buyer after every c_m,y (seconds); namely, to cover multiple buyers, v_m,y can process a buyer after the completion of the previous buyers. Thus, each VM v_m, y is modeled as a collection of virtual sellers s^v_m,y={s_m,y,r|r∈{1,2,…,  r_m,y}}, where s_m, y, r refers to the r^th virtual seller derived from VM  v_m,y, that can provide the computational capability c_m,y,r=r× c_m,y for processing one buyer. Notably, the value of r_m,y× c_m,y should be equal to or less than the maximum demand among buyers. For notational simplicity, we use “seller” as the substitution of “virtual seller” for indicating each s_m,y,r.

Fig. 1(b) shows a scenario of a graph job with three components (3 buyers), and a VC containing three SPs (SP1 has 2 VMs/5 sellers, SP2 has 1 VM/2 sellers, SP3 has 1 VM/4 sellers). Notably, the maximum tolerable execution time among buyers is 3 seconds. Take VM v_1,2 (the second VM on the first SP) which provides c_1,2=0.8 seconds for processing one component as an example. Considering VM reutilization (r_1,2=3), v_1,2 can be divided into three sellers s_1,2,1, s_1,2,2, s_1,2,3 with computational capabilities of c_1,2,1=1×0.8=0.8 seconds, c_1,2,2=2× 0.8=1.6 seconds and c_1,2,3=3×0.8=2.4 seconds, respectively. Fig. 1(b) also depicts several feasible solutions of mapping the buyers to the sellers. For instance, in Solution 1, buyers b_1,1, b_1,2, and b_1,3 are mapped to sellers s_1,2,1, s_2,1,1, and s_2,1,2, respectively.




 §.§ Modeling the VC


In a VC, we assume that each JO can communicate with at least one SP via one-hop V2V communication. It is assumed that the JOs are under pressure from insufficient local resources so that they prefer to integrate resources from the SPs in the related VC; thus, we do not consider the VMs on the JOs as available resources. Consequently, a VC is represented as graph G^s =(V^s, E^s, W^s) containing a set of sellers V^s={s_m, y, r|S_m∈S, v_m,y∈VM_m, s_m,y,r∈s^v_m, y}; edge set E^s={ e^m, y, r_m',y',r'|s_m,y,r, s_m',y',r'∈V^s, s_m,y,r≠ s_m',y',r'}, where each edge e^m,y,r_m',y',r'indicates that seller s_m,y,r can communicate with s_m',y',r'; and weight set W^s={λ^m, y, r_m', y', r'|s_m,y,r, s_m',y',r'∈V^s, s_m,y,r≠ s_m',y',r'} related to edges. Notably, sellers of the same SP are fully connected which brings λ^m, y, r_m', y', r'=0 when m=m'; otherwise, λ^m, y, r_m', y', r'=λ_m, m', which refers to the exponential distribution parameter of the contact duration between the vehicles.





 §.§ The broker


A broker acts as an intermediate agent or auctioneer who hosts and directs auction processes. In this paper, the edge computing server can conduct auctions as a broker <cit.>.




 §.§ The economic model



In our proposed auction-based framework for graph job allocation, each seller s_m, y, r has a bid p_m, y, r which denotes the reported price for processing one component and offers a computational capability c_m, y, r. Also, it has a true valuation q_m, y, r [The “true price” and “true valuation” are utilized interchangeably for the rest of this paper.] that is unknown to the broker, the buyers, and the other SPs. 
The true price q_m,y,r of seller s_m,y,r is defined as a monotone decreasing function of c_m,y,r as (1), 

    q_m, y, r=𝒰^S (c_m, y, r).

𝒰^S denotes a monotone decreasing function, where a lower execution time c_m,y,r leads to a higher price owing to a more powerful computational capability that s_m,y,r can provide. To prevent misreporting behavior where p_m, y, r≠ q_m, y, r, the mechanism proposed in this paper enjoys truthfulness that incentivizes sellers to provide the bidding information as the true valuation (i.e., p_m, y, r=q_m, y, r) by ensuring no additional benefits and possible risks brought by misreporting. 

The gross utility g^n,x_m,y,r of buyer b_n, x is defined as the time saved by enjoying the computing service of seller s_m,y,r, defined as (2).

    g^n,x_m,y,r=t_n, x-c_m, y, r

The gross utility that each seller offers to buyers is non-identical, where the larger value of g^n, x_m, y, r represents that buyer b_n, x can save more time on execution. 

Based on (1) and (2), the utility-of-service (UoS) of each buyer b_n, x is defined as the utility each buyer can get after paying for the computing service, which can be calculated as α_ng^n,x_m,y,r-p_m,y,r, where α_n denotes the sensitivity factor between price and execution time of O_n. The VM reutilization can effectively handle various buyers with different preferences related to various prices and execution times the the sellers can provide. Thus, a buyer with a lower sensitivity on execution time can wait for the release of an applicable VM by enjoying a discounted price. 




 §.§ Design targets


In this paper, truthfulness and individual rationality are considered as key design targets <cit.>, which are formally defined below.


Definition 1 (Truthfulness):
An auction is truthful if every seller keeps his bid equal to his true valuation. Sellers in a truthful auction marketplace are not willing to take any risks that may have bad effects on their utilities.

Definition 2 (Individual rationality):
An auction is individually rational if all the bidders are guaranteed to receive non-negative utilities. 

Our proposed framework includes the following main steps (see Fig. 1(a)): first, the buyers publish their demands (e.g., the tolerable execution time) and the sellers provide their bids. Then, applicable allocation solutions can be determined by the broker and transfered to all the participants. Note that any feasible allocation should consider the structural characteristics of the jobs and the VC. Aiming to maximize the total UoS of buyers while protecting the sellers' benefits, each buyer is matched to a seller under the constraints of opportunistic communications and available resources.




§ PROBLEM FORMULATION AND THE OPTIMAL ALGORITHM


This section first presents the problem formulation, and the corresponding payment rule. Then, an optimal algorithm is proposed for distributing graph jobs over VCs.




 §.§ Problem formulation

Let the binary indicator κ^n,x_m,y,r represents the assignment of buyer b_n,x to seller s_m,y,r, where κ^n,x_m,y,r=1 when buyer b_n,x is mapped to s_m,y,r, and κ^n,x_m,y,r=0, otherwise. For notational simplicity, let 𝒦=[κ^n, x_m, y, r]_s_m,y,r∈V^s, 1≤ n≤|O|,1≤ x≤|V^o_n| denote the corresponding binary matrix. Given the bidding matrix of sellers ℬ=[p_m,y,r]_s_m,y,r∈V^s and the demand matrix of buyers 𝒟=[t_n,x]_1≤ n≤|O|,1≤ x≤|V^o_n|, we fomulate the graph job allocation as an integer programming problem P given in (4), aiming to maximize the total UoS of buyers ℱ(𝒦) shown in (3). 






    ℱ(𝒦)=∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1(α_n g^n,x_m,y,r-p_m,y,r)κ^n,x_m,y,r3






    P: 𝒦^*=max_𝒦ℱ(𝒦)4

s.t.

    κ^n, x_m, y, r≜ 0, if S_m∉ℛ_o_n or   t_n, x<c_m, y,r or (α_ng^n, x_m, y, r-p_m, y, r)≤ 0, C1
        e^-λ_mm'×ω^O_n_xx'≥ε , ∀ e^O_n_xx'∈E^o_n,  if  m≠ m'  and  κ^n, x_m, y, r·κ^n, x'_m', y', r'=1, C2
       ∑^|S|_m=1∑^|VM_m|_y=1∑^r_m,y_r=1κ^n, x_m, y, r=1, ∀ b_n, x,1≤ n≤ | O|,1≤ x≤ | V^o_n|, C3
       ∑^|O|_n=1∑^|V^o_n|_x=1κ^n, x_m, y, r≤ 1, ∀ s_m, y, r,1≤ m≤ | S|,1≤ y≤ | VM_m|,1≤ r≤r_m,y,C4



Notation S_m∈ℛ_O_n indicates that S_m is located within the communication range of O_n. In problem P, constraint (C1) ensures one-hop V2V job allocation from JOs to SPs where buyer b_n, x is mapped to a seller that meets the requirement on the tolerable execution time t_n, x and positive UoS, and thus guarantees the successful execution of components. Constraint (C2) represents a probabilistic constraint which ensures that if two connected buyers b_n, x and b_n, x' are assigned to two sellers belonging to two different SPs S_m and S_m', the probability of the contact duration between S_m and S_m' being larger than ω^o_n_xx' must be greater than the threshold ε∈ (0,1]. Also, 
(C2) relies on addressing the subgraph isomorphism problem, to preserve the graph job structures during auction. Constraint (C3) and (C4) guarantee the one-to-one mapping between the buyers and the sellers. Concretely, they guarantee that each buyer can only be mapped to one seller, and each seller can process no more than one buyer.





 §.§ The VCG-based payment rule


Having the above defined IP problem, we use a VCG-based <cit.> payment rule given in (5), 
where the payment of a winning seller s_i, j, k depends on the damage it causes to other participants, which is calculated as the difference between the optimal value of the objective function with and without seller s_i, j, k.

    𝒫_i, j, k    =ℱ (𝒦^*)-ℱ_V^s\{s_i, j, k}(Θ^*)
           +p_i, j, k×κ^n, x *_i, j, k, 5


where ℱ(𝒦^*) denotes the maximum value of function (3). Also, ℱ_V^s\{s_i, j, k}(Θ^*) indicates the maximum value of (3) without the participation of seller s_i, j, k, where the relevant optimal solution is represented by Θ^*=[θ^n, x *_m, y, r]_s_m,y,r≠ s_i,j,k.




 §.§ Analysis of truthfulness and individual rationality


Proposition 1 (Truthfulness):
Given the payment rule in (5), every seller s_i, j, k∈V^s in the proposed auction is willing to have the bid equal to his true valuation (p_i, j, k=q_i, j, k).

Under a given bidding matrix of other sellers in the related VC, consider two cases for seller s_i, j, k as follows,

Case 1: s_i, j, k has his bid p_i, j, k equal to the true valuation q_i, j, k (p_i, j, k=q_i, j, k), and the corresponding utility u_i, j, k is calculated as below based on the payment rule shown in (5),


    u_i, j, k    =𝒫_i, j, k-q_i, j, k×κ^n, x *_i, j, k
        =ℱ (𝒦^*)-ℱ_V^s\{s_i, j, k} (Θ^*).6



Case 2: s_i, j, k misreports his bid denoted as p'_i, j, k (p'_i, j, k≠ q_i, j, k), and the corresponding net utility is calculated in (7), in which 𝒦^*'=[κ^n, x *'_m, y, r]_s_m,y,r∈V^s, 1 ≤ n ≤ |O|, 1 ≤ X ≤ |V^O_n| denotes the graph job allocation solution when  s_i, j, k misreports his bid, and κ^n, x *'_i, j, k indicates the relevant assignment of s_i, j, k.

    u'_i, j, k    =𝒫'_i, j, k-q_i, j, k×κ^n, x *'_i, j, k
        =ℱ (𝒦^*')-ℱ_V^s\{s_i, j, k} (Θ^*)
           +p'_i, j, k×κ^n, x *'_i, j, k-q_i, j, k×κ^n, x *'_i, j, k7


The difference between the utilities of the above mentioned two cases is calculated in (8).

    u_i, j, k-u'_i, j, k    =ℱ (𝒦^*)-ℱ (𝒦^*')
           -p'_i, j, k×κ^n, x *'_i, j, k+q_i, j, k×κ^n, x *'_i, j, k.8

According to (3), we have 

    ℱ (𝒦^*)    =∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1
          (α_ng^n, x_m, y, r-p_m, y, r)×κ^n, x *_m, y, r,9

and 


    ℱ (𝒦^*')=∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1 α_ng^n, x_m, y, r×κ^n, x *'_m, y, r
    
       -∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1 p_m, y, r×κ^n, x *'_m, y, r
    
       -p'_i, j, k×κ^n, x *'_i, j, k+q_i, j, k×κ^n, x *'_i, j, k.10

Correspondingly, (8) can be calculated as (11).





    u_i, j, k-u'_i, j, k=∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1(α_ng^n, x_m, y, r-p_m, y, r)×κ^n, x *_m, y, r-∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1α_ng^n, x_m, y, r×κ^n, x *'_m, y, r+ 
       ∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1p_m, y, r×κ^n, x *'_m, y, r+p'_i, j, k×κ^n, x *'_i, j, k-q_i, j, k×κ^n, x *'_i, j, k- p'_i, j, k×κ^n, x *'_i, j, k+q_i, j, k×κ^n, x *'_i, j, k
       =∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1(α_ng^n, x_m, y, r-p_m, y, r)×κ^n, x *_m, y, r- ∑^|S|_m=1∑^|O|_n=1∑^|VM_m|_y=1∑^|V^o_n|_x=1∑^r_m,y_r=1(α_ng^n, x_m,y,r-p_m,y,r)×κ^n, x *'_m, y, r.11




Apparently in (11), solution κ^n, x *'_m, y, r is included in the solution space of the graph job allocation problem. Owing to that κ^n, x *_m, y, r represents the optimal solution which is always equal to or better than other solutions, we have u_i, j, k-u'_i, j, k≥ 0 and sellers do not obtain better utilities by misreporting in the auction. In other words, sellers will always report their true valuations.



The optimal algorithm for the auction-based graph job allocation
InputInputOutputOutput
graph jobs G^O_n={V^O_n, E^O_n, W^O_n}, VC graph G^s={V^s, E^s, W^s}, ℬ, 𝒟

the optimal solution 𝒦^*, the related payments 𝒫_i, j, k of the winning sellers

// Stage 1: The buyer-seller pair selection procedure

Initialization: B^*←{V^O_1∪V^O_2…∪V^O_|O|}, MatchT← [], 𝒦^*← [], b← length (B^*), s← length (V^s),

B^buyer←{B^buyer_i| i∈{1, 2, …, b!}, | B^buyer_i|=b}; % each sequence B^buyer_i denotes a permutation of the elements in B^*

S^*←{S^seller_j| j∈{1, 2, …, 𝒞(s,b)}, | S^seller_j|=b, S^seller_j⊆V^s}, % each sequence S^seller_j denotes a permutation of b elements in V^s 

i=1 to b!
j=1 to 𝒞(s, b)
a buyer in B^buyer_i can be mapped to a seller in S^seller_j while meeting constraints (C1) and (C2)

𝒦_ij←{B^buyer_i, S^seller_j}, MatchT←MatchT∪𝒦_ij,

𝒦_ij← [],

𝒦^*← the solution with maximum value of (3) in MatchT, % the optimal matching between the buyers and sellers

// Stage 2: Payment calculation for winning sellers

s_i, j, k∈V^s and κ^n, x_i, j, k=1 
calculate 𝒫_i, j, k according to the payment rule (5),

end algorithm


Proposition 2 (Individual rationality of the sellers):
Given the payment rule in (5), every seller s_i, j, k∈V^s in the proposed auction are individual rational, in other words, sellers will not be in worse positions after participation.

Given that the auction is truthful and the payment rule defined in (5), the utility of a winning seller s_i, j, k is calculated as (6), where κ^n, x *_m, y, r and θ^n, x *_m, y, r indicate the optimal allocation of cases with and without s_i, j, k. For notational simplicity, V^s'≜V^s\{s_i, j, k} denotes the sellers set without s_i, j, k, we consider the following two cases:

Case 1: ℱ (𝒦^*)≥ℱ_V^s'(Θ^*). According to (5), the utility u_i, j, k of seller s_i, j, k is greater than or equal to zero. Consequently, s_i, j, k will get non-negative benefit after participation.

Case 2: ℱ (𝒦^*)< ℱ_V^s'(Θ^*). Given that V^s'⊆V^s, the solution space over set V^s' is a subset of that over V^s, and thus the value of ℱ (𝒦^*) is always equal to or larger than ℱ_V^s'(Θ^*). Consequently, Case 2 will never happen.

In conclusion, all sellers in the auction have the property of individual rationality.


Proposition 3 (Individual rationality of VMs):
All VMs are willing to take part in the proposed auction scheme.

A VM is divided into multiple sellers with different capabilities owing to the resource reutilization factor considered in this paper. According to (6), the utility of a VM v_i, j participates in the auction is thus calculated as:


    u_i, j    =∑^r_i,j_k=1𝒫_i, j, k-∑^r_i,j_k=1q_i, j, k×κ^n, x *_i, j, k
       =ℱ (𝒦^*)×∑^r_i,j_k=1κ^n, x *_i, j, k-∑^r_i,j_k=1ℱ_V^s\{s_i, j, k} (Θ^*)
       +∑^r_i,j_k=1p_i, j, k×κ^n, x *_i, j, k -∑^r_i,j_k=1q_i, j, k×κ^n, x *_i, j, k12


Given that all the sellers are truthful, we have:

    u_i, j=ℱ (𝒦^*)×∑^r_i,j_k=1κ^n, x *_i, j, k-∑^r_i,j_k=1ℱ_V^s\{s_i, j, k} (Θ^*).13


Notably, when VM v_i, j does not take part in the auction, all sellers s_i, j, k∈s^v_i, j will accordingly exit the auction, which brings ℱ_V^s\{s_i, j, k} (Θ^*)≜ℱ_V^s\s^v_i, j (Θ^**). V^s\s^v_i, j denotes the set of sellers when VM v_i, j does not take part in the auction (all sellers of VM v_i, j are excluded) and Θ^**=[θ^n,x **_m,y,r]_v_m,y≠ v_i,j is the corresponding optimal solution. Thus, (13) can be rewrote as:


    u_i, j=(ℱ (𝒦^*)-ℱ_V^s\ s^v_i, j (Θ^**))×∑^r_i,j_k=1κ^n, x *_i, j, k.14


Since 𝒦^* stands for the optimal solution over set V^s, we have ℱ (𝒦^*)≥ℱ_V^s\s^v_i, j (Θ^**) which brings u_i, j≥ 0. Thus, all the VMs are willing to participate in the proposed auction scheme. 



Proposition 4 (Individual rationality of  SPs):
All SPs are willing to take part in the proposed auction.



The utility u_i of SP S_i can be calculated as:

    u_i    =∑^|VM_i|_j=1u_i, j. 15


According to Proposition 3, we have u_i≥ 0. Thus, all SPs in this auction are individual rational.






 §.§ The optimal graph job allocation



Our proposed optimal algorithm that matches each buyer to a feasible seller, proceeds in two stages, the pseudo-code of which is given in Algorithm 1. In stage 1, the best graph job allocation solution is obtained by exhaustive search and comparisons of the values of (3). Then, in stage 2, the payment of each winning seller is calculated according to (5), which guarantees the truthfulness. Specifically in Algorithm 1, lines 2-4 stands for the initialization procedure; in lines 5-10 we search for the possible mapping set MatchT, wherein each mapping 𝒦_ij denotes the assignments from the buyer set to a feasible seller set; line 11 selects the best mapping with the maximum value of the total UoS of buyers given by (3); lines 13-14 in stage 2 we calculate the payments for the winning sellers.

Algorithm 1 solves the NP-hard problem given in (4). Moreover, the constraint (C2) of (4) relies on addressing the subgraph isomorphism problem, which is also challenging to be solved <cit.>. Specially, obtaining the optimal solution requires computation complexity of 𝒪(b!×𝒞(s, b)), where b=∑^|O|_n=1|V^O_n| and s=|V^s| denotes the total number of buyers and sellers in the related VC, respectively. Symbol “!” is used as the factorial notation and 𝒞(s, b) stands for the s-choose-b operation. Due to that jobs are modeled as undirected graphs where components (buyers) do not have a particular execution sequence. Moreover, the calculation of the payments of the winning sellers leads to the computational complexity of 𝒪(b×b!×𝒞(s, b)). Thus, a broker can hardly obtain the solution for larger-scale and real-life networks with the inreasing number of buyers and sellers. In consequence, a structure-preserved matching algorithm is proposed in the next section to solve the problem in polynomial time complexity, while achieving the maximization of the utility-of-service-gain (UoSG).




§ THE STRUCTURE-PRESERVED MATCHING ALGORITHM BASED ON UOSG MAXIMIZATION



































































We propose a structure-preserved matching algorithm based on UoSG maximization (hereafter, we also use “MaxUoSG” for notational simplicity) as an efficient way to solve the graph job allocation problem in VC-assisted networks. Specifically, UoSG is defined as the profit a VC can obtain after matching one pair of buyer and seller. We later demonstrate that our proposed method enjoys truthfulness and individual rationality properties. 




 §.§ The proposed structure-preserved matching based on UoSG maximization


For notational simplicity, we define v^n,x_m,y,r≜(α_ng^n, x_m, y, r-p_m, y, r). We also define the preference lists from the perspectives of both buyers and the broker to identify the buyer-seller pairs that may bring more gains to the total UoS of the buyers.
Notably, if seller s_m,y,r is out of the communication coverage of buyer b_n, x or it makes the value of (α_ng^n, x_m, y, r-p_m, y, r) less than zero, it will not be included in both buyer's and broker's preference lists so as to prevent non-positive UoS. For b_n, x∈V^O_n, the preference list L_n,x is defined as (16) sorted by the value of v^n, x_m, y, r in a non-ascending order.


    L_n,x   : (1, b_n, x, s_m, y, r, v^n, x_m, y, r)≻_b_n, x…
       ≻_b_n, x(|ℛ_b_n, x|+1,b_n, x, s_b_n, x, v_b_n, x),16


where |ℛ_b_n, x| denotes a number that meets 0<|ℛ_b_n,x|≤ |ℛ_b_n,x|. Each item in the above list is represented by a tetrad that contains index in the list, a buyer, a seller and the corresponding v^n, x_m, y, r, symbol ≻_b_n,x represents the preference relation, where the seller on the left-side of “≻_b_n,x” can bring more benefit to buyer b_n, x as compared to all the sellers on the right-side. To ensure the property of truthfulness, a virtual seller s_b_n, x is added to the end of the list L_n,x as a critical indicator with the critical UoS v_b_n, x≜(α_ng^n, x_i, j, k-p_i, j, k) 
be slightly lower than the values of all UoS in the list. The relevant proofs of economical properties will be given in Section 4.3.

The broker's preference list given by (17) is regarded as a union set of all L_n,x excluding the virtual sellers, sorted by non-ascending order of the value of v^n, x_m, y, r, where the mapping between a buyer and a seller on the left-side of “≻_broker” can bring higher benefit to the buyers as compared to those on the right-side. An example of preference lists of buyers and the broker is shown in Fig. 2.


    L_Bro   : (1,b_n, x, s_m, y, r, v^n, x_m, y, r) ≻_broker 
       (2,b_n', x', s_m', y', r', v^n', x'_m', y', r')≻_broker⋯17



The proposed MaxUoSG contains the job allocation stage and the payment decision stage. The preference list L_Bro will be mainly referred to in the former stage aiming to maximize the total UoS. Notably, this might sacrifice some buyers' benefits. For instance, (1, b_n, x, s_i, j, k, v^n, x_i, j, k) and (1, b_n', x', s_i, j, k, v^n', x'_i, j, k) located at the top of L_n,x and L_n',x' respectively; however, the broker is inclined to match b_n, x to s_i, j, k since (α_ng^n, x_i, j, k-p_i, j, k)>(α_n'g^n', x'_i, j, k-p_i, j, k). Then, lists of the buyers L_n,x are used to calculate the payments for winning sellers.







 §.§ The related payment rule



For notational simplicity, let s_i, j, k be the first seller located behind s_i, j, k in list L_n,x. We define the payment of a winning seller s_i, j, k as 

    𝒫^#_i, j, k= (α_ng^n, x_i, j, k-(α_ng^n, x_i, j, k-p_i, j, k))×κ^n, x #_i, j, k,18

where g^n, x_i, j, k=t_n, x-c_i, j, k denotes the benefit of buyer b_n, x from enjoying the computing service of seller s_i, j, k. Symbol c_i,j,k and p_i, j, k represents the execution time and the bid of s_i, j, k, respectively. In (18), κ^n, x #_i, j, k indicates the obtained solution via the proposed MaxUoSG algorithm. 


The structure-preserved matching algorithm based on UoSG maximization
InputInputOutputOutput
graph jobs G^O_n={V^O_n, E^O_n, W^O_n}, VC graph G^s={V^s, E^s, W^s}, ℬ, 
𝒟, L_n,x, L_Bro

the sub-optimal solution 𝒦^sub, the related payments 𝒫^#_i, j, k of the winning sellers

// Stage 1: The buyer-seller pair selection procedure

Initialization: B^*←{V^O_1∪V^O_2…∪V^O_|O|}, S^*←V^s, b← length (B^*), s← length (S^*), L← length (L_Bro),

𝒦^sub← [], MatchT← [], indTry← 0, indMatch ← 1,

MatchT← the first item in L_Bro, % add the first item of LBro to MatchT

the index of the last item in MatchT≤L and indTry ≤L

indTry=(indMacth+1) to L
the buyer-seller pair of index indTry in L_Bro is not in MatchT

MTemp← the item with index indTry in L_Bro,

 TempB← the buyer in MTemp, % save the relevant buyer 

 TempS← the seller in MTemp, % save the relevant seller

match TempB to TempS can meet constraints (C1) and (C2), and prevent the interdependency with buyers and sellers in MatchT 

MatchT←MTemp∪MatchT, % add the new buyer-seller pair to MatchT

indMatch ← the index of the last item in MatchT, % update indMatch





the number of buyers in MatchT==b
go to stage 2, % if all the buyers are successfully mapped to the sellers, go to stage 2 (line 26)
the number of buyers in MatchT< b and indMatch < L and indTry==L
the number of buyers in MatchT==1
indMatch ← the index of the first item in MatchT+1, % restart the matching procedure from the second item in L_Bro 

the first item in MatchT← the item with indMatch in L_Bro,

the last item in MatchT←[], % delete the last successful matching pair in MatchT and keep searching from the next item of which in L_Bro



the number of buyers in MatchT< b and indMatch==L and indTry==Lgo to line 28,


𝒦^sub← all buyer-seller pairs in MatchT, % a feasible matching between the buyers and the sellers

// Stage 2: Payment calculation for winning sellers

s_i, j, k∈V^s and κ^n, x_i, j, k=1 
calculate 𝒫^#_i, j, k according to the payment rule in (18),


end algorithm



The pseudo-code of the proposed MaxUoSG algorithm is given in Algorithm 2. The notation MatchT stands for the match table that stores all the successfully matched buyer-seller pairs, and 𝒦^sub denotes the final graph job allocation solution. In stage 1 (lines 1-24), a mapping between the buyers and the winning sellers are obtained according to L_Bro, while taking into account the graph job structures. In stage 2 (lines 25-27), the payment of each winning seller is calculated based on the buyer's preference list. More precisely, lines 2-4 correspond to the initialization procedure. Lines 5-13 search for feasible buyer-seller pairs from the top of list L_Bro, while meeting the structure-preservation and one-to-one matching constraints. For the former constraint, the structure of each graph job has to be preserved, while the later constraint requires that the buyers and sellers that are in current MatchT should be ignored during the matching procedure. Lines 14-15 stand for the successful matching where all the buyers are mapped to the feasible sellers. Lines 16-19 correspond to the case in which no feasible buyer-seller pairs can be chosen after the first item of L_Bro, restart the matching procedure from the second item in list L_Bro. In lines 20-21, we delete the last successful matching pair in MatchT and keep searching from the next item located behind the deleted item in L_Bro, if the matching procedure is blocked by an infeasible buyer-seller pair (e.g, a buyer-seller pair that cannot meet the structure-preservation constraint). Lines 22-23 correspond to the failure of matching. In stage 2, lines 26-27 calculate the payment for every winning seller according to the proposed payment rule shown in (18). 

The proposed algorithm enables low computation complexity when solving the auction-based graph job allocation problem. For buyers' preference list generations, bubble sort is applied that brings a computation complexity of 𝒪(|ℛ_b_n,x|^2) for each buyer. As for L_Bro, merge sort algorithm is utilized with computation complexity of 𝒪(L× log (L)), where L=|L_Bro| denotes the number of items in L_Bro. The proposed structure-preserved matching provides the best computation complexity performance of 𝒪(b) and the worst case complexity of 𝒪 ((L-b)×b).




 §.§ Analysis of truthfulness and individual rationality



Proposition 5 (Truthfulness):
The proposed MaxUoSG algorithm makes each seller, i.e., s_i, j, k∈V^s set its bid equal to the true valuation, i.e., p_i, j, k=q_i, j, k.


Due to the structure-preservation factor, any changes to the broker's preference list may have a great impact on the final matching solution. Therefore, two cases are considered: Case 1) the misreporting behavior of a seller causes no change to the orders of items in L_Bro; and Case 2) the misreporting behavior of a seller causes changes to the orders of items in L_Bro. The utility u_i, j, k of a winning seller s_i, j, k when p_i, j, k=q_i, j, k, is given by:

    u_i, j, k=𝒫^#_i, j, k-q_i, j, k×κ^n, x #_i, j, k19


A virtual seller s'_i, j, k is considered owning the same properties with seller s_i, j, k, except for the untruthful bid p'_i, j, k≠ q_i, j, k, which denotes the case where seller s_i, j, k misreports in the auction. The utility of s'_i, j, k is given by:

    u'_i, j, k=𝒫^#'_i, j, k-q_i, j, k×κ^n, x #'_i, j, k,20

where κ^n, x #'_i, j, k is the graph job allocation solution via the proposed algorithm when s_i, j, k misreports its bid. Based on the aforementioned utilities, the proof of truthfulness is presented based on the above mentioned two cases. For Case 1, consider the following conditions:

Case 1.1 (p'_i, j, k<q_i, j, k). If s'_i, j, k wins the auction, the utility can be calculated as:

    u'_i, j, k=(α_ng^n, x_i, j, k'- (α_ng^n, x '_i, j, k-p'_i, j, k)-q_i, j, k)×κ^n, x #'_i, j, k,21

where g^n, x '_i, j, k and g^n, x '_i, j, k denote the buyer b_n, x's benefit obtained from virtual seller s'_i, j, k and the first seller located after s'_i, j, k in list L_n,x, respectively. Similarly, if s_i, j, k wins the auction, we get the utility:

    u_i, j, k= (α_ng^n, x_i, j, k- (α_ng^n, x_i, j, k-p_i, j, k)-q_i, j, k)×κ^n, x #_i, j, k,22

When p'_i, j, k<q_i, j, k, s'_i, j, k  is always located before s_i, j, k in each buyer's preference list, which lead to (α_ng^n, x '_i, j, k-p'_i, j, k)≥(α_ng^n, x_i, j, k-p_i, j, k) and u_i, j, k≥ u'_i, j, k. Consequently, s'_i, j, k will never be mapped to b_n, x owing to the same properties with s_i, j, k except for the bid. Thus, bidding truthfully will always lead to more utility.

Case 1.2 (p'_i, j, k>q_i, j, k). It is obvious that s_i, j, k will be located before s'_i, j, k in each buyer's preference list.

Case 1.2.1: s_i, j, k and s'_i, j, k are located adjacently with each other in list L_n,x. Here, we have u'_i, j, k=u_i, j, k since s'_i, j, k is the only critical indicator. Thus, s_i, j, k does not have to misreport his bid in the auction.

Case 1.2.2: There is a seller s_i, j, k located between s_i, j, k and s'_i, j, k in list L_n,x. Here, if s'_i, j, k wins the auction, s_i, j, k will also win the auction. Due to the one-to-one mapping rule between buyers and sellers in the proposed auction, we have u'_i, j, k=0.



To meet the requirement of structure-preservation, a seller who misreports bid faces the following risks in Case 2. 

Risk 2.1: the structure-preservation constraint may bring a seller s'_i, j, k with failure in this auction even when p'_i, j, k>q_i, j, k, which leads to u'_i, j, k=0.

Risk 2.2: the structure-preservation constraint leads to an equal utility for an untruthful seller s'_i,j,k, i.e., u'_i, j, k=u_i, j, k, when (α_ng^n, x '_i, j, k-p'_i, j, k)= (α_ng^n, x_i, j, k-p_i, j, k).

Risk 2.3: the structure-preservation constraint leads to an non-positive utility for an untruthful seller s'_i,j,k, if α_ng^n, x '_i, j, k-(α_ng^n, x '_i, j, k-p'_i, j, k)<0, which leads to u'_i, j, k<0.

Notably, misreporting behavior may bring an untruthful seller a higher utility in Case 2 (examples are detailed in simulation). However, a seller has no idea how to adjust its bid to aviod the above mentioned risks while insuring a higher utility, owing to the non-transparent information in the proposed marketplace (e.g., the opportunistic V2V communication duration among different SPs, and the required weights 
ω^O_n_xx' among buyers of each graph job). 

Consequently, in Case 2, being truthful stands for a risk-free option for each seller. In general, the proposed MaxUoSG algorithm offers truthfulness in this auction marketplace.






Proposition 6 (Individual rationality of the sellers):
All the sellers in the proposed auction scheme are individual rational via the proposed MaxUoSG algorithm.


Given that seller s_i, j, k bids truthfully and s_i, j, k is the seller located behind s_i, j, k in the preference list of b_n, x, we have:

    α_ng^n, x_i, j, k-p_i, j, k≥α_ng^n, x_i, j, k-p_i, j, k,23

which leads to

    α_ng^n, x_i, j, k-α_ng^n, x_i, j, k+p_i, j, k≥ p_i, j, k24


Combining (22) with (24), we have u_i, j, k≥ 0. Thus, all the sellers in the proposed auction scheme have the property of individual rationality.



Proposition 7 (Individual rationality of VMs and SPs):
All SPs and VMs are willing to take part in the proposed auction scheme via the proposed MaxUoSG algorithm.

For each VM v_i, j∈VM_i and SP S_i∈S, we calculate the utility of which as u_i, j=∑^r_i,j_k=1u_i, j, k, and u_i=∑^|VM_i|_j=1u_i, j, respectively. According to Proposition 6, we have u_i, j≥ 0 and u_i≥ 0. In conclusion, all SPs and VMs are willing to participate in the proposed auction scheme.






§ NUMERICAL RESULTS AND PERFORMANCE EVALUATION






This section presents numerical results, illustrating the validity of the proposed algorithms. In the following, the performance of the optimal algorithm (“Opt”) and the structure-preserved matching algorithm based on UoSG maximization (“MaxUoSG”) comparing with the baseline methods, are analyzed in detail. Moreover, various problem sizes are investigated with different numbers of buyers and sellers. Baseline methods and the related procedures considered in the simulation are given below:






1) Execution time preferred mechanism (ETPM): Randomly select a buyer and match it to the seller with the current lowest execution time, while satisfying constraints (C1) and (C2), until all the buyers are mapped to the sellers successfully.

2) Low price preferred mechanism (LPM): Randomly select a buyer and match it to the seller with the current lowest price, while satisfying constraints (C1) and (C2), until all the buyers are mapped to the sellers successfully.

3) Random matching mechanism (RMM): Randomly select a buyer and randomly match it to an available seller, while satisfying constraints (C1) and (C2), until all the buyers are mapped to the sellers successfully.




 §.§ Simulation setup

Graph job structures considered in the simulation are depicted in Fig. 3. A monotone decreasing function formed by 𝒰^S (c_m, y, r)=β_2-β_1c_m, y, r is applied to determine the true valuation q_m, y, r of each seller, where β_1 and β_2 are positive constants (β_1∈ [0.7,0.9], β_2∈ [0.9,1]) which enables a higher true valuation of a more powerful seller. The simulation parameters are randomly obtained from the following intervals: ε∈ [0.9,0.95], α_n∈ [1,1.5], c_m, y∈ [0.2,0.3], t_n, x∈ [0.6,0.7], ω^o_n_xx'∈ [0.1,0.7], and λ_mm'∈ [0.05,0.06] for small problem sizes with a couple of JOs and SPs and λ _mm'∈ [0.01,0.02] for large problem sizes with more participants.




 §.§ Running time performance


The running time performance comparison between the optimal algorithm and the proposed MaxUoSG is shown in Fig. 4, for various numbers of SPs/sellers and different job types depicted in Fig. 3. Notably, 10-based logarithm representation is applied since the gap between the running time of the two algorithms becomes too large as the graph job and VC structures become more complicated (e.g., by increasing the number of buyers and sellers). Compared with the proposed MaxUoSG, Fig. 4 indicates that as the number of buyers and sellers in a VC grows, the running time of obtaining the optimal solutions rises sharply, while that of the proposed MaxUoSG remains at a certain order of magnitude of 10^-2 seconds, which makes the optimal algorithm unsuitable for fast-changing and large-scale networks. Moreover, different topological complexity of VC configurations (e.g., existence of more sellers and edges in VC graph) may also lead to a dramatic change in the running time. Specifically, obtaining the optimal solution takes more than 2× 10^4 seconds upon allocating a job with type 4 and four SPs (37 sellers), as shown in Fig. 4.




 §.§ The obtained UoS in various problem sizes











The comparisons of the sum of the UoS (the value of the objective function (3)) between the baseline methods, the optimal, and the MaxUoSG algorithms for various graph job types are shown in Fig. 5 for small problem size scenarios with a couple of buyers and sellers. Fig. 5(a), Fig. 5(b), Fig. 5(c) and Fig. 5(d) reveal that the proposed MaxUoSG exhibits the same or similar performance with the optimal algorithm, and outperforms the baseline methods RMM, ETPM and LPM upon allocating one graph job. Similarly, upon allocating two graph jobs, Fig. 5(e), Fig. 5(f), Fig. 5(g) and Fig. 5(h) demonstrate that the proposed MaxUoSG achieves better UoS than the baseline methods that is close to that of the optimal solutions. Notably, as an excessively long time is needed to obtain the optimal solutions with an increase in the number of buyers and sellers, performance evaluation of the optimal algorithm is ignored in Fig. 5(g) and Fig. 5(h).

For large problem sizes containing more buyers and sellers, the comparisons of the sum of the buyers' UoS between the baseline methods, the optimal and the MaxUoSG algorithms are shown in Fig. 6. Note that the performance evaluation of the optimal algorithm is not considered in Fig. 6 since the running time becomes prohibitively large when the number of participants in the marketplace grows. As can be seen from Fig. 6, the proposed MaxUoSG algorithm always results in a better value of the objective function (3) rather than that of RMM, ETPM and LPM, in various scenarios considering different numbers of buyers and sellers. For a better illustration, TABLE 2 is presented that describes the average performance improvement revealed in Fig. 5 and Fig. 6 upon utilizing the proposed MaxUoSG compared with the baseline methods in various problem sizes. 




 §.§ The desired economical properties


Simulations related to the economical properties of truthfulness and individual rationality for the proposed MaxUoSG algorithm considering different problem sizes are depicted in Fig. 7 and Fig. 8. Considering a small problem size case with one graph job type 1 and one type 2 (totally 7 buyers) and 3 SPs (totally 25 sellers), the comparison between the winning sellers’ payments and bids is depicted in Fig. 7(a). As can be seen from this figure, each winning seller will get a final payment no less than his bid, which is related to the individual rationality property. Fig. 7(b)-Fig. 7(h) exhibit both the untruthful and truthful bidding behaviors of each winning seller, where the value of x-axis is defined as the submitted bids and the red solid circles indicate the truthful prices and the related payments. Specifically, Fig. 7(b), Fig. 7(f) and Fig. 7(g) show that misreporting behavior in bidding will not lead to higher payments to the sellers, which encourages them to behave truthfully. Sellers 2, 3, 4 and 22 in Fig. 7(c), Fig. 7(d), Fig. 7(e) and Fig. 7(h) are facing with the risk of getting worse payments when misreporting in the auction. According to Case 2 in Proposition 5, misreporting behaviors may cause some changes to the preference lists of the buyers and the broker, which may result in a different buyer-seller pair selection owing to the structure preservation constraint. Thus, sellers 2, 3, 4 and 22 in these figures may get chances to obtain better payments when they are untruthful. However, non-transparent information in the marketplace makes sellers unconsciousness of arranging their bids to avoid potential risks. Thus, bidding truthfully stands for a risk-free behavior. Take Fig. 7(e) as an example, seller 4 will definitely get a worse payment when bidding lower than his true price 0.6. Also, seller 4 is insensible of how to raise his bid for getting a better payment before encountering the risk of non-payment after bidding larger than 0.648. As a conclusion, sellers observe the truthfulness property in our proposed framework.

Simulation results for large problem sizes considering 4 JOs (totally 19 buyers, including two graph job type 2, one type 3 and one type 4) and 5 SPs (totally 48 sellers) are presented in Fig. 8. Similar to Fig. 7(a), Fig. 8(a) shows that the payment of each winning seller stays no less than his bid, which makes all sellers individual rational. Subsequently, seven winning sellers as repesentatives are randomly chosen from 19 winning sellers to conduct payment evaluation under untruthful and truthful behaviors. Fig. 8(b), Fig. 8(c) and Fig. 8(d) indicate that the sellers do not get better payments when misreporting their bids. Moreover, Fig. 8(e), Fig. 8(f), Fig. 8(g) and Fig. 8(h) reveal the risks that the sellers may undergo when misreporting their bids in the marketplace. Consequently, sellers are motivated to bid truthfully in our proposed framework. 






§ CONCLUSION

This paper studies a novel truthful auction-based graph job allocation scheme for VC-assisted IoV, which is formulated as an IP problem. For small problem sizes with a couple of buyers and sellers, an optimal algorithm is introduced along with a VCG-based payment rule. For large problem sizes containing more participants and complicated job and VC structures, a low computation complexity structure-preserved matching algorithm based on UoSG maximization, and the corresponding payment role are proposed. The effectiveness of the proposed algorithms is revealed through comprehensive simulations.  Several potential future directions can be concerned such as considering the cooperation among the SPs, and designing new payment rules to avoid risks if possible.





§ ACKNOWLEDGEMENT


This work is supported in part by the National Natural Science Foundation of China (grant nos. 61971365, 61871339, 61901403), Digital Fujian Province Key Laboratory of IoT Communication, Architecture and Safety Technology (grant no. 2010499), the State Key Program of the National Natural Science Foundation of China (grant no. 61731012), the Major Research Plan of the National Natural Science Foundation of China (grant no. 91638204) and the US National Science Foundation (grant nos. ECCS-1444009, CNS-1824518).


99


1 G. Qiao, S. Leng, K. Zhang, and Y. He, “Collaborative task offloading in vehicular edge multi-access networks,” IEEE Commun. Mag., vol. 56, no. 8, pp. 48–54, 2018.

2 T. Mekki, I. Jabri, A. Rachedi, and M. B. Jemaa, “Vehicular cloud networks: challenges, architectures, and future directions,” Veh. Commun., vol. 9, pp. 268–280, 2017.

3 S. Hosseinalipour, A. Nayak, and H. Dai, “Power-aware allocation of graph jobs in geo-distributed cloud networks,” IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 4, pp. 749–765, 2019.

4 Z. Ning, P. Dong, X. Kong, and F. Xia, “A cooperative partial computation offloading scheme for mobile edge computing enabled internet of thing,” IEEE Internet Things J., vol. 6, no. 3, pp. 4804- 4814, 2018.

5 S. Bi, and Y. J. Zhang, “Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading,” IEEE Trans. Wireless Commun., vol. 17, no. 6, pp. 4177-4190, 2018.

6 S. Deng, Z. Xiang, J. T. Taheri, M. A. Khoshkholghi, J. Yin, A. Y. Zomaya, and S. Dustdar, “Optimal application deployment in resource constrained distributed edges,” IEEE Trans. Mobile Comput., DOI: 10.1109/TMC.2020.2970698, pp. 1-1, 2020.

7 X. Wang, X. Chen, and W. Wu, “Towards truthful auction mechanisms for task assignment in mobile device clouds,” IEEE Int. Conf. Comput. Commun. (INFOCOM), Atlanta, GA, USA, May. 2017, pp. 1-9.

8 Q. Wu, M. Zhou, Q. Zhu, and Y. Xia, “VCG auction-based dynamic pricing for multi-granularity service composition,” IEEE Trans. Autom. Sci. Eng., vol. 15, no. 2, pp. 796–805, 2018.

9 Z. Tao, Q. Xia, Z. Hao, C. Li, L. Ma, S. Yi, and Q. Li, “A survey of virtual machine management in edge computing,” Proc. IEEE, vol. 107, no. 8, pp: 1482–1499, 2019.

10 H. Guo, J. Liu, J. Zhang, W. Sun, and N. Kato, “Mobile-edge computation offloading for ultradense IoT networks,” IEEE Internet Things J., vol. 5, no. 6, pp. 4977-4988, 2018.

11 J. Du, L. Zhao, J. Feng, and X. Chu, “Computation offloading and resource allocation in mixed fog/cloud computing systems with min-max fairness guarantee,” IEEE Trans. Commun., vol. 66, no. 4, pp. 1594-1608, 2017.

12 J. Ren, G. Yu, Y. Cai, and Y. He, “Latency optimization for resource allocation in mobile-edge computation offloading,” IEEE Trans. Wireless Commun., vol. 17, no. 8, pp. 5506– 5519, 2018.

13 M. LiWang, S. Dai, Z. Gao, Y. Tang, and H. Dai, “A truthful reverse-auction mechanism for computation offloading in cloud-enabled vehicular network,” IEEE Internet Things J., vol. 6, no. 3, pp. 4214- 4227, 2018.

14 J. Ghaderi, S. Shakkottai, and R. Srikant, “Scheduling storms and streams in the cloud,” ACM Trans. Modeling and Performance Eval. of Comput. Syst., vol. 1, no. 4, pp. 1–14, 2016.

15 D. Huang, P. Wang, and D. Niyato, “A dynamic offloading algorithm for mobile computing,” IEEE Trans. Wireless Commun., vol. 11, no. 6, pp. 1991–1995, 2012.

16 L. Shi, Z. Zhang, and T. Robertazzi, “Energy-aware scheduling of embarrassingly parallel jobs and resource allocation in cloud,” IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 6, pp. 1607–1620, 2017.

17 F. Sun, F. Hou, N. Cheng, M. Wang, H. Zhou, L. Gui, and X. Shen, “Cooperative task scheduling for computation offloading in vehicular cloud,” IEEE Trans. Veh. Technol., vol. 67, no. 11, pp: 11049–11061, 2018.

18 M. LiWang, S. Hosseinalipour, Z. Gao, Y. Tang, L. Huang, and H. Di, “allocation of computation-intensive graph jobs over vehicular clouds in IoV,” IEEE Internet Things J., vol. 7, no. 1, pp. 311-324, 2019.

19 M. LiWang, Z. Gao, S. Hosseinalipour, and H. Dai, “Multi-Task Offloading over Vehicular Clouds under Graph-based Representation,” arXiv preprint arXiv:1912.06243, 2019.

20 W. Sun, J. Liu, Y. Yue, and H. Zhang, “Double auction-based resource allocation for mobile edge computing in industrial Internet of Things,” IEEE Trans. Industrial Informatics., vol. 14, no. 10, pp. 4692-4701, 2018.

21 C. Zhou, C. Tham, and M. Motani, “online auction for truthful stochastic offloading in mobile cloud computing,” IEEE Int. Conf. Global Commun. (GLOBECOM), Singapore, Dec. 2017, pp. 1-6.

22 L. Lu, J. Yu, Y. Zhu, and M. Li, “A double auction mechanism to bridge users' task requirements and providers' resources in two-sided cloud markets,” IEEE Trans. Parallel Distrib. Syst., vol. 29, no. 4, pp. 720-733, 2017.

23 G. Gao, M. Xiao, J. Wu, H. Huang, S. Wang, and G. Chen, “Auction-based vm allocation for deadline-sensitive tasks in distributed edge cloud,” IEEE Trans. Services Comput., DOI: 10.1109/TSC. 2019.2902549, pp. 1-1, 2019.

24 Y. Zhang, C. Y. Wang, H. Y. Wei, “Parking reservation auction for parked vehicle assistance in vehicular fog computing,” IEEE Trans. Veh. Technol., vol. 68, no. 4, pp. 3126-3139, 2019.

25 X. Wang, Y, Sui, J. Wang, C. Yuen, and, W. Wu, “A distributed truthful auction mechanism for task allocation in mobile cloud computing,” IEEE Trans. Services Comput., DOI: 10.1109/TSC. 2018.2818147, pp. 1-1, 2018.

26 X. Zhu, Y. Li, D. Jin, and J. Lu, “Contact-aware optimal resource allocation for mobile data offloading in opportunistic vehicular networks,” IEEE Trans. Veh. Technol., vol. 66, no. 8, pp. 7384–7399, 2017.

27 Y. Li, D. Jin, L. Zeng, and S. Chen, “Revealing patterns of opportunistic contact durations and intervals for large scale urban vehicular mobility,” IEEE Int. Conf. Commun. (ICC), Budapest, Hungary, Jun. 2013, pp. 1646–1650.

28 W. Vickrey, “Counter speculation, auctions, and competitive sealed tenders,” J. Finance, vol. 16, no. 1, pp. 8–37, 1961.

29 M. LiWang, Z. Gao, S. Hosseinalipour, H. Dai, and X. Wang, “Energy-aware allocation of graph jobs in vehicular cloud computing-enabled software-defined IoV,” arXiv preprint arXiv:2004.01953, 2020.













[
    < g r a p h i c s >
]Zhibin Gao
(gaozhibin@xmu.edu.cn) received his B.S. degree in Communication Engineering in 2003, M.S. degree in Radio Physics in 2006, and Ph.D. in Communication Engineering in 2011 from Xiamen University, where he is a senior engineer of communication engineering. His current research interests include wireless communication, mobile network resource management, and signal processing.


[
    < g r a p h i c s >
]Minghui LiWang
[M'19] (mliwang@uwo.ca) received her B.S. degree in Computer Science and Technology in 2013 and Ph. D degree in Information & Communication Engineering, Xiamen University, China in 2019. She is now a postdoc fellow in the Department of Electrical & Computer Engineering, University of Western Ontario, Ontario, Canada. She was a visiting scholar at NC State University, NC, USA during 2017 to 2018. Her research interests are wireless communication systems, mobile edge computing, resource optimization & management and Internet of Vehicles.



[
    < g r a p h i c s >
]Seyyedali Hosseinalipour[S’18]
(shossei3@ncsu.edu) received his B.S. degree in Electrical Engineering from Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran in 2015. He is pursuing a Ph.D. degree in the Department of Electrical and Computer Engineering at North Carolina State University, Raleigh, NC, USA. His research interests include analysis of wireless networks, resource allocation and load balancing for cloud networks, and resource allocation and task scheduling for vehicular ad-hoc networks.




[
    < g r a p h i c s >
]Huaiyu Dai
[F'17] (hdai@ncsu.edu) received the B. E. and M.S. degrees in Electrical Engineering from Tsinghua University, Beijing, China, in 1996 and 1998, respectively, and the Ph.D. degree in electrical engineering from Princeton University, Princeton, NJ in 2002. He was with Bell Labs, Lucent Technologies, Holmdel, NJ, in summer 2000, and with AT & T Labs-Research, Middletown, NJ, in summer 2001. He is currently a Professor of Electrical and Computer Engineering with NC State University, Raleigh. His research interests are in the general areas of communication systems and networks, advanced signal processing for digital communications, and communication theory and information theory. His current research focuses on networked information processing and crosslayer design in wireless networks, cognitive radio networks, network security, and associated information-theoretic and computation-theoretic analysis. He has served as an editor of IEEE Transactions on Communications, IEEE Transactions on Signal Processing, and IEEE Transactions on Wireless Communications. Currently he is an Area Editor in charge of wireless communications for IEEE Transactions on Communications. He co-edited two special issues of EURASIP journals on distributed signal processing techniques for wireless sensor networks, and on multiuser information theory and related applications, respectively. He co-chaired the Signal Processing for Communications Symposium of IEEE Globecom 2013, the Communications Theory Symposium of IEEE ICC 2014, and the Wireless Communications Symposium of IEEE Globecom 2014. He was a co-recipient of best paper awards at 2010 IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2010), 2016 IEEE INFOCOM BIGSECURITY Workshop, and 2017 IEEE International Conference on Communications (ICC 2017).


[
    < g r a p h i c s >
]Xianbin Wang[F'17] (xianbin.wang@uwo.ca) is a Professor and Tier 1 Canada Research Chair at Western University, Canada. He received his Ph.D. degree in electrical and computer engineering from National University of Singapore in 2001. Prior to joining Western, he was with Communications Research Centre Canada (CRC) as a Research Scientist/Senior Research Scientist between July 2002 and Dec. 2007. From Jan. 2001 to July 2002, he was a system designer at STMicroelectronics. His current research interests include 5G and beyond, Internet-of-Things, communications security, machine learning and intelligent communications. Dr. Wang has over 400 peer-reviewed journal and conference papers, in addition to 30 granted and pending patents and several standard contributions. Dr. Wang is a Fellow of Canadian Academy of Engineering, a Fellow of Engineering Institute of Canada, a Fellow of IEEE and an IEEE Distinguished Lecturer. He has received many awards and recognitions, including Canada Research Chair, CRC President’s Excellence Award, Canadian Federal Government Public Service Award, Ontario Early Researcher Award and six IEEE Best Paper Awards. He currently serves as an Editor/Associate Editor for IEEE Transactions on Communications, IEEE Transactions on Broadcasting, and IEEE Transactions on Vehicular Technology. He was also an Associate Editor for IEEE Transactions on Wireless Communications between 2007 and 2011, and IEEE Wireless Communications Letters between 2011 and 2016. He was involved in many IEEE conferences including GLOBECOM, ICC, VTC, PIMRC, WCNC and CWIT, in different roles such as symposium chair, tutorial instructor, track chair, session chair and TPC co-chair. Dr. Wang is currently serving as the Chair of ComSoc SPCE Technical Committee.





