# An Incentive Mechanism for Computation Offloading in Satellite-Terrestrial Internet of Vehicles

Authors: Xingyu Zhang; Heyang Zhang; Sida Dai; Yang Liu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the development of satellite-terrestrial technology and the popularity of the Internet of Vehicles, how to improve the efficiency of mobile cloud computing (MCC) has become the next concern. However, the resource of cloudlets is not sufficient to perform large-scale computation tasks, or some applications designed to run on vehicles have more efficiency executed on vehicles than executed on cloudlets. Additionally, it is still challenging for platforms to motivate mobile vehicle owners to join in the process while the existing mechanisms cannot provide all the desired properties in cloudlet scenarios. To this end, we design a satellite-terrestrial IoV based on an incentive mechanism for computation offloading (IMCO) in mobile edge computing to motivate vehicle owners to perform computation offloading tasks so as to offload certain kinds of tasks to the mobile vehicles. By optimizing the MCC model, we integrate auction theory into the mechanism to ensure individual rationality, budget balance, system efficiency, and truthfulness for both sellers and buyers. Through rigorous theoretical analysis, we prove that our mechanism can achieve computational efficiency under the condition that all algorithm outputs be computed in polynomial time. Both theoretical derivations and numerical calculations prove that all the desired properties of the mechanism hold.


---

## Body

## 1. Introduction

Along with advances in computing and communications technology, the Internet of Vehicles (IoV), which is gradually replacing conventional Vehicle Ad-hoc Networks, is becoming popular worldwide and creating a promising vision for transport systems. According to a recent report by Allied Market Research, the global IoV market is expected to exceed200 billion by 2024. IoV is a distributed network [1] of huge commercial and research value that supports the use of data created by connected cars and vehicular ad-hoc networks (VANETs). Today, the design, implementation, and management of IoV technology rely heavily on modern cloud computing technologies, which play a central role in linking isolated vehicles into an organic network in which data are being processed primarily. However, considering limitations such as the size of the data and the stability of the channel, cloud computing struggles to process efficiently and could cause fatal latency [2]. According to a McKinsey & Company estimate, connected cars create up to 25 GB of data per hour. With such huge amounts of data, we need to consider new computing technologies [3]. Mobile edge computing is an emerging paradigm in IoT systems [4] that offloads data processing to the mobile which localizes data processing and enabling services to be functional [5] even if connectivity between the vehicle and cloud is absent. In addition, some applications which are suitable for running on vehicles have more efficiency executed on powerful mobile vehicles than executed on cloudlet.However, implementing mobile edge computing for computation offloading still faces several challenges [6]. First, requisitioning a viable and suitable mobile vehicle for computing takes up a user’s personal resources, and it is difficult to convince users to volunteer their mobile vehicles without rewards. Therefore, we need to design a flexible and reasonable incentive mechanism to encourage users to willingly provide their vehicles as computation resources [7]. Second, the complex physical environment in which cars travel [8], such as unstable signals and frequent congestion or crashes, places high demands on the stability and capacity of communications. Therefore, we design to adopt a satellite-terrestrial network [9] on IoV [8] to overcome the implementation difficulties. With seamless accessibility to overcome the coverage and distribution limitations of RSUs and BSs, it could provide macroscopic management to improve overall network efficiency and resource utilization at a low cost. Third, resource allocations [10] and computation offloading transactions require low time delay or there is no necessity to conduct it. Therefore, we design costumed algorithms during different stages which guarantee system and computation efficiency [11]. Lastly, the battery capacity is still a limitation of supporting energy consumption [12]. Luckily, with the popularity of fast charging technology [13], the charging efficiency of vehicles is greatly improved [14], since the development of low delay wireless charging technology [15] and the convenience of using wireless charging [16]. By using wireless charging technology [17], users can charge their mobile vehicles anytime and anywhere [18]. Therefore, with the development of fast charging technology and wireless charging technology, the problem of energy constraints can be relieved [19].In order to overcome the above challenges, we propose an incentive mechanism for computation offloading (IMCO) that maximizes the motivation of vehicle owners to perform computation offloading tasks while guaranteeing the system stability and the privacy of participants. More specifically, we first investigate the auction theory and integrate it into Mobile Cloud Computing (MCC) scenarios for computing offloads, where the problem of resource allocation was redesigned according to demand. Then, we propose the sealed-bid auction model which achieves consistent asks of mobile vehicles and variational offer of cloudlets as well as many desirable properties such as individual rationality, budget balance, truthfulness, and computational efficiency. To further illustrate the mechanism of IMCO, we design three algorithms for different phases within an auction and further use an example to demonstrate the process in detail. By rigorous theoretical analysis, our proposed mechanism is proved to achieve the four proposed desirable properties and close-to-optimal performance. Finally, we carry out extensive simulations of our proposed mechanism by testing the performance on a dataset generated by distribution functions by analyzing six indexes of different aspects.The main contributions of this paper are highlighted below.(1)
We propose an incentive mechanism for computation offloading (IMCO) based on satellite-terrestrial IoV. The feasibility and the advantages of our design are also discussed(2)
IMCO solves the problem that remote cloud server is not that sufficient to perform large scale computation tasks which will greatly encourage users to join in with computation offloading even further helps to shape a good user environment and provides the basis for widespread commercialization(3)
We apply the auction theory in economics to the scenarios in which computation tasks are offloaded to the vehicle owners. Since the existing auction algorithms cannot achieve all the properties when they are applied to computation offloading in MCC with cloudlets and vehicles as homogeneous items(4)
We theoretically prove that our proposed mechanism is more suitable for real-life scenarios as it achieves truthfulness. Extensive simulations verify that all previous proposed desirable properties are satisfiedThe rest of this paper is organized as follows. Section2 discusses the related work. Section 3 describes our system model and formulates problems. Section 4 designs the algorithm and the mechanism as well as carries out a theoretical analysis. Section 5 presents simulation and performance results of our proposed mechanism. Section 6 concludes the paper.


## 2. Related Work

In this part, the related work is divided into two groups: incentive mechanisms especially for mobile cloud computing and auction mechanisms used in economics.Mobile edge computing is an emerging paradigm in the current IoT system. Based on the concepts of cloud computing and mobile computing, MCC was built relying on wireless networks and focusing on the construction and interaction of physical devices and virtual resources. So, there are a number of studies and researches about different applications in MCC, such as online translation service with MCC and big data storage strategy for MCC. Nevertheless, there is little research about the incentive mechanism. In the scenario, the auction must deal with items with complementary and replacement relationships.As what we illustrated in Section1, even if the auction theory is well developed and applied, the existing auction algorithms are not suitable to apply in computation offloading from cloudlets to mobile vehicles. Because of incompletely satisfying the desirable properties, Vickrey auction [20] has the properties of individually rational, budget-balanced. However, it cannot deal with cheating behavior; therefore, it is susceptible to market manipulation. McAfee in [21] focuses on the auction of nonidentical items. In other words, buyers do not lean to auction commodities. When the auction begins, every buyer makes their offer only once and each seller asks for a price. After that, the auctioneer ranks the offers in a nonascending way and asks in a nondescending order to find out the minimum possible offer and maximal possible ask; then, determining the winners in buyers according to their bids. That is, their bids are larger than or equal to the maximum possible ask. And also determining the winning sellers relies on the same rule. Next, the auctioneer generates two prices: clearing price and clearing payment. Every buyer must submit the clearing price to the auctioneer. In the meantime, each seller gets rewards that are equal to clearing payment. Notwithstanding, McAfee cannot be applicable to the computation offloading scenario, since the mechanism aims at auction of homogeneous items. Even if it achieves all the desirable properties, in the scenario, each mobile vehicle will be rated differently from cloudlets rely on different factors, such as latency [6], quality of service, communication overhead, and computational capabilities.Considering the homogeneous commodities, TASC [22] includes two phases: winner determination phase and pricing phase. In the first stage, the auctioneer filtrates inapposite sellers and buyers to determine the first-stage winners. In the second stage, the auctioneer implements the McAfee mechanism to determine the clearing price and payment. Although the scenario of TASC is close to mobile cloud computing with cloudlets, there are still some defects by applying TASC in the cloudlet scenario. Because of the distinct feature of cloudlets, TASC cannot support truthfulness for buyers even if it can guarantee truthfulness for sellers and other properties.Our previous work proposes a computation offloading incentive mechanism [23]. Compared to [23], this paper discusses how to unload some types of applications to mobile vehicles by encouraging vehicle owners to perform computing unload tasks. By optimizing the MCC model, we integrate auction theory into the mechanism to ensure individual rationality, budget balance, system efficiency, and truthfulness for both sellers and buyers. IMCO maximizes the motivation of vehicle owners to perform computation offloading tasks. In addition, IMCO can assign more than one mobile vehicle for a single cloudlet in a temporary state.


## 3. System Model and Problem Formulation

In our system architecture shown in Figure1, there are three main parts: the satellite-terrestrial networks (STNs), the vehicles, and the cloudlets. STNs are the integration of satellite networks and terrestrial networks [24], consisting of one or more satellite systems and land-based stations, which efficiently disseminate information through wireless channels [25]. In the architecture, computational tasks on cloudlets can be offloaded to vehicles within coverage [26], while vehicles are simultaneously free to choose to perform computational tasks from all cloudlets covered by their current locations via STNs.Figure 1
The system architecture of satellite-terrestrial IoV.There are lots of vehicles around one cloudlet, the performance of some vehicles may be too weak to carry out computation-intensive tasks. To lift efficiency, the cloudlet can use auction mechanisms to offload computation tasks to other high-performance vehicles so as to reduce the communication overhead and improve efficiency [27]. Each vehicle will be rated differently from cloudlets based on different factors, such as latency, quality of service, communication overhead, and computational capabilities [28]. On the other side, vehicle owners can be rewarded for providing computation resources and compensated for communication costs [29]. As in most real cases in the auction market, both the buyers and the sellers can get benefits from the transactions, that is, car owners can get paid to be incentivized to share its resource [30]. When the computation offloading is applied in the mobile edge computing, every cloudlet bids when it needs extra computational performance, and it submits the offers to the auctioneer [31]. Then, the asks of vehicles are also submitted. The auctioneer, also known as a control center, will allocate m vehicles among n cloudlets according to the outcome of IMCO, consequently reducing the communication overhead and the latency so that the services will be affordable.


### 3.1. Resource Allocation for Mobile Vehicles

As the structure shown in Figure1, there are lots of mobile vehicles around one cloudlet, and some performance of vehicles may be too weak to carry out some computation-incentive applications. The cloudlet can provide service to running applications for those vehicles. However, some tasks rely on particular hardware such as DSP, ISP, and NPU. The virtual machines may solve the problem by hardware virtualization. But the efficiency of virtualization is very low due to the structure of vehicles. The integration level of vehicles is much higher than cloudlet, so there are some applications using heterogeneous computing combining the advantages of CPU, GPU, NPU, ISP, and DSP. And lots of hardware are designed to process specific tasks. Hence, using virtualization is not a suitable solution. One cloudlet may serve several low-end mobile vehicles at one time; to lift efficiency, cloudlet can use auction mechanism to offload computation tasks to other high-performance mobile vehicles. The close range of high-performance mobile vehicles can be exploited to reduce the communication overhead and improve efficiency. Each mobile vehicle will be rated differently from cloudlets rely on different factors, such as latency, quality of service, communication overhead, and computational capabilities. Some cloudlet may need more powerful computation capabilities to achieve computation-intensive tasks, and others may prefer a low communication latency to respond to their clients more quickly.On the other side, vehicle owners can be rewarded for providing computation resource and compensated for communication cost. As most real cases in the auction market, both the buyers and sellers can get benefits from the trading, that is, vehicle owners can get paid such as bitcoins to be incentivized to share its resource, and the tasks which are offloaded to the mobile vehicles should be done in given times. Especially, cloudlet must pay no less than the cost of the vehicle owner providing such computation resource.In an area, the more computation offloading tasks, the higher the resource utilization of the mobile vehicles. In order to maximize the use of resources, the auctioneer should accurately allocate the mapping mobile vehicles’ resources to the assigned tasks from cloudlets. Mobile vehicles only care about the cost of renting their resources. And the cloudlets’ offers are adjustable. The performance of mobile vehicles varies from field to field and according to the auction model will be calculated to determine the right winning bidder.


### 3.2. Auction Model

The computation offloading is applied in the MCC scenario which is illustrated in Figure1. Every cloudlet bids when they need extra computational performance, and they submit their offers to the auctioneer. Then, the asks of mobile vehicles are also submitted. The auctioneer also known as the control center will allocate m mobile vehicles among n cloudlet according to IMCO, consequently reducing the communication overhead and the latency so that the services will be affordable.To achieve truthfulness, the sealed-bid auction model is necessary. That is to say, each cloudlet (mobile vehicle) can upload its bid (ask) secretly to the auctioneer so that everyone’s information including buyers’ bids and sellers’ asks is invisible to others. As Table1 depicted:
(i)
For each cloudletci∈C, C = {c1,c2,⋯,cn}. Bi = {Bi1,Bi2,⋯,Bim} is defined as bid vector, where Bij is the bid for mobile vehicle mj∈M, M = {m1, m2,⋯, mm}. The matrix of bids including all the bid vectors of all cloudlets is denoted by B = {B1;B2; ⋯;Bm}.(ii)
For each mobile vehiclemj∈M, its ask vector is defined as A = {A1,A2,⋯,Am}, where Aj is the ask of mobile vehicles mj∈MTable 1
Notions.
SymbolDefinitionciCloudletcijCloudlets with positive evaluation toward mobile vehiclesnTotal number of cloudletsmTotal number of mobile vehiclesmjMobile vehicleCSet of cloudletsC+Cloudlets with positive evaluationMSet of mobile vehiclesCcSet of winning cloudlets candidatesMcSet of winning mobile vehicles candidatesCbfSet of winning cloudlets before filteringMbfSet of winning mobile vehicles before filteringCwSet of winning cloudletsMwSet of winning mobile vehiclesℂNonincreasing order ofC+MNondecreasing order of mobile vehiclesσ′A function that maps fromMbf to CbfσA function that maps fromMw to CwBijCloudletci biding on mobile vehicle mjBiCloudletci’s bid vectorBBid matrix ofCAjAsk of mobile vehiclesmjAAsk vector ofMA−jAsk vector of all sellers not includingmjVijValuation ofmj rated by ciViValuation vector ofciCostjCost ofmj performing computation offloading tasksPicPrice that is charged tociPjmReward price paid tomjPijcPrice that is charged toci for mjPijmReward price paid tomj with allocated ciUicUtility ofciUjmUtility ofmjUijcUtility ofci with allocated mjUijmUtility ofmj with allocated ciPwcThe set of clearing price that is charged toCwPwmThe set of clearing rewards toMwAs you can see, the asks of mobile vehicles are consistent no matter which cloudlets are since the mobile vehicles only care about how much payment for renting their resources.On the contrary, the offer of cloudlets is variational respecting different mobile vehicles due to the weights of different tasks are distinct, and the performance of different mobile vehicles of different fields is different.The auctioneer will calculate to determine the winning mobile vehiclesCc∈C and winning cloudlets Mw∈M, also define a mapping σ between Cc and Mw, the price Pic is charged from winning cloudlets Mw∈M∈M, and the reward Pjm to Cc∈C. In particular, Pijc is denoted as the price charged to cloudlet ci from mobile vehicle mj, and Pijm is defined as payment rewarded to mobile vehicle mj from cloudlet ci.We are also concerned about the utilities of cloudlets and mobile vehicles in the mechanism. There are two factors that affect the utilities. The first one is the evaluation of cloudlets toward the services provided by mobile vehicles, and the next one is the cost of providing such computation resources. So, we definedVij as the valuation toward mobile vehicle mj rated by ci. Vi = (Vi1,Vi2,⋯,Vim). Hence, we can have the utility of ci and mj as below.
(1)Uci=Vij−Pic,ifci∈Cw,0.otherwise,(2)Umj=Pjm−Costj,ifmj∈Mw,0.otherwise.As what (1) and (2) expressed, the utility Uci>0 only when cloudlet ci is allocated to a mobile vehicle mj. The higher Uci is, the more satisfying the cloudlet will be. On the other side, the utility Umj illustrates the profit the mobile vehicles received, since it is equals to the remainder of the received reward over its cost.


### 3.3. Desired Properties

As what we have depicted, the auction model has several inputs:C, M, B, and A. Correspondingly, the auctioneer adopts an auction mechanism to calculate a series of results: Cw, Mw, and σ. A well-designed auction mechanism must have the properties as follows.
(i)
Individual rationality:(3)Pic≤Bij,∀ci∈Cw,(4)Pjm≥Aj,∀ci∈Cw,∀mj∈Mw.The formula shown in (3) means that the winning cloudlet is charged less than or equal to its offer. The formula in (4) shows that the winning vehicle is paid more or equal to its ask.
(ii)
Budget balance:(5)∑ci∈CwPic≥∑mj∈MwPjm.The formula above shows that the total rewards that the auctioneer gives to all winning vehicles are more or equal to the sum of prices that all winning buyers submit to the auctioneer.(iii)
Truthfulness. An auction algorithm is said to be truthful if and only if(6)Uicci′,B−i≥Uicci,B−i,(7)Ujmmj′,A−j≥Ujmmj′,A−j.B−i means that the bid vector without the cloudlet ci and A−j means that the ask vector of all sellers not including mj. Such that a cloudlet cannot improve its utility by faking a bid different from the true valuation of a vehicle and no vehicle can fake the ask different from its cost. Uic achieves its maximum only if
(8)Bi=Vi,∀ci∈C.TheUjm achieves its maximum only if
(9)Aj=Cj,∀mj∈M.(iv)
Computational Efficiency. The outputs of the auction mechanism, i.e., Cw, Mw, σ, Pwc, and Pwm should be calculated in a polynomial time concerning n and mAs what we have depicted, the auction model has those input:C, M, B, and A. Correspondingly, the auctioneer adopts auction algorithms to calculate a series of result: Cw, Mw, σ, and (referring to Table 1). A well-designed auction mechanism must have the properties as follows.


### 3.4. Technical Challenges

As the what we argue in Section2, the existing auction algorithms cannot achieve all the properties when they are applied to computation offloading in MCC with cloudlets and mobile vehicles as homogeneous items. The example shown below illustrates that TASC auction mechanism in [22] cannot support truthfulness for buyers despite the support of the other desirable properties.Table2 shows a matrix of bid in which the value of different mobile vehicles rated by different cloudlets are different. And Table 3 shows the ask vector of mobile vehicles which has the same value of the cost of providing computation resources. To illustrate the lacking truthfulness of TASC applied in this scenario, supposing that the auctioneer uses an algorithm to maximize the overall QoS. The TASC mechanism has two stages: the first step is to determine the winner and the next one is to determine the price. The mapping of winning cloudlet candidates and winning mobile vehicle candidates is shown in Figure 2.Table 2
Bid matrix.
m1m2m3m4m5m6m7c107001050c20122008c30006900c410000006c56098000Table 3
Ask vector of mobile vehicles.
Mobile vehiclem1m2m3m4m5m6m7Ask2395147Figure 2
The bidirectional mapping graph of winning mobile vehicles and cloudlets.In the second stage, we get the result of final winning cloudlet:c1 and c4, the winning mobile vehicles: m1 and m5, the Pwc=8 and Pwm=6. It is clear to see that the utility of c3 is 0 according to equation (1).If cloudletc3 cheats the auctioneer by submitting bid dishonestly. That is, c3 increases its offer B35 by adding a variable Δ which is larger than 1, since 9+Δ>10, the new result of winner mapping is shown in Figure 3. The winning cloudlets are changed to c4 and c3 which is still the same value as in Figure 2. The utility of c3 is changed to 9−8=1. Hence, c3 can improve its utility by faking its bid. It means that TASC auction mechanism is not suitable to the scenario that we are interested in. In Section 4, we propose a truthful double auction mechanism called IMCO, which can achieve all the desirable properties illustrated in Section 1.Figure 3
Different results of bidirectional mapping graph of winning mobile vehicles and cloudlets.


## 3.1. Resource Allocation for Mobile Vehicles

As the structure shown in Figure1, there are lots of mobile vehicles around one cloudlet, and some performance of vehicles may be too weak to carry out some computation-incentive applications. The cloudlet can provide service to running applications for those vehicles. However, some tasks rely on particular hardware such as DSP, ISP, and NPU. The virtual machines may solve the problem by hardware virtualization. But the efficiency of virtualization is very low due to the structure of vehicles. The integration level of vehicles is much higher than cloudlet, so there are some applications using heterogeneous computing combining the advantages of CPU, GPU, NPU, ISP, and DSP. And lots of hardware are designed to process specific tasks. Hence, using virtualization is not a suitable solution. One cloudlet may serve several low-end mobile vehicles at one time; to lift efficiency, cloudlet can use auction mechanism to offload computation tasks to other high-performance mobile vehicles. The close range of high-performance mobile vehicles can be exploited to reduce the communication overhead and improve efficiency. Each mobile vehicle will be rated differently from cloudlets rely on different factors, such as latency, quality of service, communication overhead, and computational capabilities. Some cloudlet may need more powerful computation capabilities to achieve computation-intensive tasks, and others may prefer a low communication latency to respond to their clients more quickly.On the other side, vehicle owners can be rewarded for providing computation resource and compensated for communication cost. As most real cases in the auction market, both the buyers and sellers can get benefits from the trading, that is, vehicle owners can get paid such as bitcoins to be incentivized to share its resource, and the tasks which are offloaded to the mobile vehicles should be done in given times. Especially, cloudlet must pay no less than the cost of the vehicle owner providing such computation resource.In an area, the more computation offloading tasks, the higher the resource utilization of the mobile vehicles. In order to maximize the use of resources, the auctioneer should accurately allocate the mapping mobile vehicles’ resources to the assigned tasks from cloudlets. Mobile vehicles only care about the cost of renting their resources. And the cloudlets’ offers are adjustable. The performance of mobile vehicles varies from field to field and according to the auction model will be calculated to determine the right winning bidder.


## 3.2. Auction Model

The computation offloading is applied in the MCC scenario which is illustrated in Figure1. Every cloudlet bids when they need extra computational performance, and they submit their offers to the auctioneer. Then, the asks of mobile vehicles are also submitted. The auctioneer also known as the control center will allocate m mobile vehicles among n cloudlet according to IMCO, consequently reducing the communication overhead and the latency so that the services will be affordable.To achieve truthfulness, the sealed-bid auction model is necessary. That is to say, each cloudlet (mobile vehicle) can upload its bid (ask) secretly to the auctioneer so that everyone’s information including buyers’ bids and sellers’ asks is invisible to others. As Table1 depicted:
(i)
For each cloudletci∈C, C = {c1,c2,⋯,cn}. Bi = {Bi1,Bi2,⋯,Bim} is defined as bid vector, where Bij is the bid for mobile vehicle mj∈M, M = {m1, m2,⋯, mm}. The matrix of bids including all the bid vectors of all cloudlets is denoted by B = {B1;B2; ⋯;Bm}.(ii)
For each mobile vehiclemj∈M, its ask vector is defined as A = {A1,A2,⋯,Am}, where Aj is the ask of mobile vehicles mj∈MTable 1
Notions.
SymbolDefinitionciCloudletcijCloudlets with positive evaluation toward mobile vehiclesnTotal number of cloudletsmTotal number of mobile vehiclesmjMobile vehicleCSet of cloudletsC+Cloudlets with positive evaluationMSet of mobile vehiclesCcSet of winning cloudlets candidatesMcSet of winning mobile vehicles candidatesCbfSet of winning cloudlets before filteringMbfSet of winning mobile vehicles before filteringCwSet of winning cloudletsMwSet of winning mobile vehiclesℂNonincreasing order ofC+MNondecreasing order of mobile vehiclesσ′A function that maps fromMbf to CbfσA function that maps fromMw to CwBijCloudletci biding on mobile vehicle mjBiCloudletci’s bid vectorBBid matrix ofCAjAsk of mobile vehiclesmjAAsk vector ofMA−jAsk vector of all sellers not includingmjVijValuation ofmj rated by ciViValuation vector ofciCostjCost ofmj performing computation offloading tasksPicPrice that is charged tociPjmReward price paid tomjPijcPrice that is charged toci for mjPijmReward price paid tomj with allocated ciUicUtility ofciUjmUtility ofmjUijcUtility ofci with allocated mjUijmUtility ofmj with allocated ciPwcThe set of clearing price that is charged toCwPwmThe set of clearing rewards toMwAs you can see, the asks of mobile vehicles are consistent no matter which cloudlets are since the mobile vehicles only care about how much payment for renting their resources.On the contrary, the offer of cloudlets is variational respecting different mobile vehicles due to the weights of different tasks are distinct, and the performance of different mobile vehicles of different fields is different.The auctioneer will calculate to determine the winning mobile vehiclesCc∈C and winning cloudlets Mw∈M, also define a mapping σ between Cc and Mw, the price Pic is charged from winning cloudlets Mw∈M∈M, and the reward Pjm to Cc∈C. In particular, Pijc is denoted as the price charged to cloudlet ci from mobile vehicle mj, and Pijm is defined as payment rewarded to mobile vehicle mj from cloudlet ci.We are also concerned about the utilities of cloudlets and mobile vehicles in the mechanism. There are two factors that affect the utilities. The first one is the evaluation of cloudlets toward the services provided by mobile vehicles, and the next one is the cost of providing such computation resources. So, we definedVij as the valuation toward mobile vehicle mj rated by ci. Vi = (Vi1,Vi2,⋯,Vim). Hence, we can have the utility of ci and mj as below.
(1)Uci=Vij−Pic,ifci∈Cw,0.otherwise,(2)Umj=Pjm−Costj,ifmj∈Mw,0.otherwise.As what (1) and (2) expressed, the utility Uci>0 only when cloudlet ci is allocated to a mobile vehicle mj. The higher Uci is, the more satisfying the cloudlet will be. On the other side, the utility Umj illustrates the profit the mobile vehicles received, since it is equals to the remainder of the received reward over its cost.


## 3.3. Desired Properties

As what we have depicted, the auction model has several inputs:C, M, B, and A. Correspondingly, the auctioneer adopts an auction mechanism to calculate a series of results: Cw, Mw, and σ. A well-designed auction mechanism must have the properties as follows.
(i)
Individual rationality:(3)Pic≤Bij,∀ci∈Cw,(4)Pjm≥Aj,∀ci∈Cw,∀mj∈Mw.The formula shown in (3) means that the winning cloudlet is charged less than or equal to its offer. The formula in (4) shows that the winning vehicle is paid more or equal to its ask.
(ii)
Budget balance:(5)∑ci∈CwPic≥∑mj∈MwPjm.The formula above shows that the total rewards that the auctioneer gives to all winning vehicles are more or equal to the sum of prices that all winning buyers submit to the auctioneer.(iii)
Truthfulness. An auction algorithm is said to be truthful if and only if(6)Uicci′,B−i≥Uicci,B−i,(7)Ujmmj′,A−j≥Ujmmj′,A−j.B−i means that the bid vector without the cloudlet ci and A−j means that the ask vector of all sellers not including mj. Such that a cloudlet cannot improve its utility by faking a bid different from the true valuation of a vehicle and no vehicle can fake the ask different from its cost. Uic achieves its maximum only if
(8)Bi=Vi,∀ci∈C.TheUjm achieves its maximum only if
(9)Aj=Cj,∀mj∈M.(iv)
Computational Efficiency. The outputs of the auction mechanism, i.e., Cw, Mw, σ, Pwc, and Pwm should be calculated in a polynomial time concerning n and mAs what we have depicted, the auction model has those input:C, M, B, and A. Correspondingly, the auctioneer adopts auction algorithms to calculate a series of result: Cw, Mw, σ, and (referring to Table 1). A well-designed auction mechanism must have the properties as follows.


## 3.4. Technical Challenges

As the what we argue in Section2, the existing auction algorithms cannot achieve all the properties when they are applied to computation offloading in MCC with cloudlets and mobile vehicles as homogeneous items. The example shown below illustrates that TASC auction mechanism in [22] cannot support truthfulness for buyers despite the support of the other desirable properties.Table2 shows a matrix of bid in which the value of different mobile vehicles rated by different cloudlets are different. And Table 3 shows the ask vector of mobile vehicles which has the same value of the cost of providing computation resources. To illustrate the lacking truthfulness of TASC applied in this scenario, supposing that the auctioneer uses an algorithm to maximize the overall QoS. The TASC mechanism has two stages: the first step is to determine the winner and the next one is to determine the price. The mapping of winning cloudlet candidates and winning mobile vehicle candidates is shown in Figure 2.Table 2
Bid matrix.
m1m2m3m4m5m6m7c107001050c20122008c30006900c410000006c56098000Table 3
Ask vector of mobile vehicles.
Mobile vehiclem1m2m3m4m5m6m7Ask2395147Figure 2
The bidirectional mapping graph of winning mobile vehicles and cloudlets.In the second stage, we get the result of final winning cloudlet:c1 and c4, the winning mobile vehicles: m1 and m5, the Pwc=8 and Pwm=6. It is clear to see that the utility of c3 is 0 according to equation (1).If cloudletc3 cheats the auctioneer by submitting bid dishonestly. That is, c3 increases its offer B35 by adding a variable Δ which is larger than 1, since 9+Δ>10, the new result of winner mapping is shown in Figure 3. The winning cloudlets are changed to c4 and c3 which is still the same value as in Figure 2. The utility of c3 is changed to 9−8=1. Hence, c3 can improve its utility by faking its bid. It means that TASC auction mechanism is not suitable to the scenario that we are interested in. In Section 4, we propose a truthful double auction mechanism called IMCO, which can achieve all the desirable properties illustrated in Section 1.Figure 3
Different results of bidirectional mapping graph of winning mobile vehicles and cloudlets.


## 4. Mechanism Design

As we illustrated in the background, truthful Vickrey auction [20] cannot guarantee truthfulness and other properties at the same time. However, the McAfee auction mechanism cannot be directly used in MCC with cloudlets and mobile vehicles as heterogeneous items. TASC auction mechanism is extending the McAfee mechanism in [22]. Unlike the McAfee auction, TASC is a heterogeneous auction mechanism. While TASC cannot achieve truthfulness to the scene as the example we present in the technical challenges. The result shows that TASC cannot counter market manipulation of untruthful cloudlets in stage 1.To solve this problem, we propose IMCO. In IMCO, we change the order of the general stage. The auctioneer firstly selects the winning candidates both the cloudlets and the mobile vehicles referring to some rules. And then, each mobile vehicle that is the winning candidate will be allocated to one winning cloudlet candidate. And thePwc and Pwm will be determined as well. In addition, IMCO can assign more than one mobile vehicle for a single cloudlet in a temporary state; in the last stage, the winner redundant mobile vehicles will be eliminated to ensure the efficiency of the mechanism.In the next part of this paper, we illustrate the mechanism of IMCO minutely. Then, we give an example to present the IMCO more clearly. The properties of IMCO will be discussed in the following chapter.Algorithm 1: Winner candidates determination phase.
Input:C,M,B,A;Output:Cc,Mc,Bpαqα,Ajβ;1:Cc⟵∅, Mc⟵∅;2: CreateC+ which is consist of bidders whose bid is greater than zero in accordance to B, i.e., C+ = {cpq: Bpq>0,cp∈C};3: Sort all cloudlets inC+ to a non-ascending sequence ℂ = (cp1q1,cp2q2,⋯,cp1γqγ)in which Bp1q1≥Bp2q2≥⋯≥Bpγqγ;4: Sort all mobile vehicles inM into a non-descending order M = (mj1,mj1,⋯,mjm) such that Aj1≤Aj2≤⋯≤Ajm;5: Find the median askAjβ of M, where β = 1+m/2;6: Find the minimizedα, so that Bpα+1qα+1<Ajβ and Bpαqα≥Ajβ;7:Cc⟵ the first α cloudlets in ℂ;8:Forcpq∈Ccdo9:IfAq>Ajβthen10:Cc⟵Cc\ {cpq};11:Else12:Ifmq∉Mc13:Mc⟵Mc∪ {mq};14:End if15:End if16:End for17:Return (Cc,Mc,Bpαqα,Ajβ);Algorithm 2: Assignment and pricing phase.
Input:Cc, Mc, Bpαqα, Ajβ, B;Output:Cbf, Mbf, σ′, Pbfm, Pbfc;1:Cbf⟵∅, Mbf⟵Mc,Pbfm⟵∅,Pbfc⟵∅;2:Formj∈Mbfdo3:Pjm = Ajβ, Pbfm⟵Pbfm∪ {Pjm};4:Cj = {cij:cij∈Cc};5:IfCj=1then6:Cbf⟵Cbf∪ {cij}, σ′j=i7:Pbfc=Bpαqα, Pbfc⟵Pbfc∪ {Pijc}8:Else9:  SortCj into a non-ascending list Cj such that10:Bij1≥Bij2≥⋯≥Bpαqα11:If the first k (k≥2) bids in Cj are equal then12:   Randomly choose one buyer from the firstk13:   Buyers inCj;14:Else15:   Select the1st buyer of Cj whose bid is the16:   Highest;17:End if18:Cbf⟵Cbf∪ {cij}, σ′j=i;19:Pbfc=Bij2, Pbfc⟵Pbfc∪ {Pijc};20:End if21:End for22:Return (Cbf,Mbf,σ′,Pbfm,Pbfc);Algorithm 3: Winner elimination phase.
Input:Cbf, Mbf, σ′, Pbfm, Pbfc;Output:Cw, Mw, σ, Pwm, Pwc;1:Cw⟵Cbf, Mw⟵Mbf,σ⟵σ′,Pwm⟵Pbfm,Pwc⟵Pbfc;2:For any two cloudlets cσa,a,cσb,b∈Cw & a≠bdo3:Ifσa=σbthen4:Uσjjc = Bσjj−Pσj,jc, j=a,b5:IfUσa,ac = Uσb,bcthen6:j′ = select from a,b randomly;7:Else8:j′ = min(Uσa,ac,Uσb,bc);9:End if10:Cw⟵Cw\ {cσj′,j′}, Mw⟵Mw\ {sj′};11:Pwc⟵Pwc\ {Pσj′,j′c}, Pwm⟵Pwm\Pj′m,12:σj′=∅;13:End if14:End for15:Return (Cw,Mw,σ,Pwm,Pwc);


### 4.1. Details of IMCO

The IMCO consists of three phases: winner candidates determination phase, assignment and pricing phase, and winner elimination phase to achieve the preceding desirable properties.To be specific, Algorithm1 is used to filter some unqualified cloudlets and mobile vehicles so as to select winner candidates. To begin with, Algorithm 1 creates C+ from the original cloudlet set C which consists of bidders whose bid is greater than zero in accordance to B. That is to say, a cloudlet can appear several times in regard to the mobile vehicles for which the cloudlet’s offer is larger than zero. Next, the C+ is sorted to C in which the bids are sorted in a nonascending sequence. Also, mobile vehicles are sorted in a nondescending list according to ask A, denoted by M. Particularly, the Ajβ is the median ask of mobile vehicles in M, where β=1+m/2, is to find the minimize value α, so that Bpα+1qα+1<Ajβ and Bpαqα≥Ajβ. The Ajβ and Bpαqα are two standards to identify the winning candidates. For example, if cpq is a winning cloudlet candidate in Cc, it should satisfy Aq<Ajβ and Bpαqα≥Ajβ. The mobile vehicle mα is said to be winning candidate if and only if and at least one cloudlet from ℂ has a bid for mα. The β can be other value no necessary the median value. The value of β directly affect the number of Mc so to affect the number of Cc.In the next stage, to protect the system from biding and asking untruthfully, we closely combine assigning and pricing. The procedure is shown above in Algorithm2. First, the control center assigns the winning cloudlet candidates for winning mobile vehicle candidates. There are three situations needed to be discussed. The first situation is that there is only one cloudlet biding for one mobile vehicle, so the cloudlet is added to the Cbf waiting for processing Algorithm 2 and charged Bpαqα. The second situation is that there are two or above cloudlets scrambling for one mobile vehicle, the auctioneer would choose the cloudlet with the highest bid from the cloudlet candidates and add it to Cbf. The last situation is when there are two or more cloudlets that offer the highest bids, the control center will randomly choose one cloudlet among the cloudlets with the highest bid and add to Bpαqα. Different from the first situation, the cloudlet is charged for the 2nd highest bid. To make it easier to understand, supposing that the clearing price Bpαqα is 6 and two highest bids are Baj=Bbj=12, and the next bid in nonascending order is Bcj=10, then, caj and cbj have a 50-50 chance of becoming member of Cbf. And the winner will be charged 10 to avoid untruthfully biding since the 2nd highest bid is 10.In the final phase, if one cloudlet inCbf who wins at least two mobile vehicles in Mbf, the auctioneer relies on the efficiency of utilization to decide only one mobile vehicle for a cloudlet. For example, if ciθ and ciϑ are both in the Cbf, in other words, ci as a cloudlet wins 2 mobile vehicles, mθ and mϑ in Mbf. The auctioneer would choose one cloudlet according to whose utility is higher. Just as we illustrated above, if there are at least 2 utilities equal, the auctioneer will select only one mobile vehicle stochastically, when algorithm 3 is finished, there should be a one-to-one mapping relationship between the mobile vehicle in Mw and cloudlet in Cw since the redundant mobile vehicles can join another auction.The idea that cloudlet offloads one task to multiple mobile vehicles seems an excellent way to raise the efficiency of cloudlets, but it may be too ideal to adopt. The major tasks offloaded to mobile vehicles are applications run on mobile vehicles, and the applications may not design for running parallelly or running on heterogeneous hardware.


### 4.2. A Walk through Example

In this section, we use an example to demonstrate the process of IMCO by using cloudlets’ bid in Table2 and mobile vehicles’ ask in Table 3.The first stage is to determine the winner candidates.(i)
Create the setC+ from Table 2C+=c12,c15,c16,c22,c23,c24,c27,c34,c35,c41,c47,c51,c53,c54(ii)
Sequencing the cloudlets inC+ in a nonincreasing order to get ℂ=c15,c41,c35,c53,c27,c54,c12,c34,c47,c51,c16,c23,c24,c22(iii)
Sorting the mobile vehicles inM in a nondecreasing sequence to obtain M=m5,m1,m2,m6,m4,m3,m7(iv)
Drawing the mapping relationship graphic between cloudlets inℂ and mobile vehicles in M in Figure 4(v)
Calculating the two standards:Bpαqα=B16=5 and Ajβ=A6=4(vi)
Determining the winner cloudlet and mobile vehicle candidates:Figure 4
Mapping relationship graphic betweenCc and Mc.Cc=c15,c41,c35,c53,c27,c54,c12,c34,c47,c51,c16;Mc=m5,m1,m2(vii)
Drawing the mapping relationship graphic between cloudlets inCc and mobile vehicles in Mc in Figure 4(viii)
According to Algorithm2, we can obtainCbf=c15,c41,c12; Mbf=m5,m1,m2;so we can seeσ′5=1,σ′1=4,σ′2=1(ix)
Computing the price of cloudlets and determining the clearing price:Pbfc=P15c=B35=9,P41c=B51=6,P12c=Bpαqα=5(x)
Determining the payment paid to winning mobile vehicles:Pbfm = {P5m=P1m=P2m=Ajβ=4}
(xi)
Drawing the mapping relationship graphic between cloudlets inCbf and mobile vehicles in Mbf in Figure 5Figure 5
Mapping relationship graphic betweenCbf and Mbf.However, there still has some mobile vehicles server one cloudlet at the same time; auctioneer needs to filter the redundant vehicles.So, auctioneer executes the elimination algorithm depending on the utilities of cloudlet according to different mobile vehicles.(i)
Calculating the utilities of cloudletc1 according to mobile vehicle m5 and m2:U15c=B15−P15c=10−9=1,U12c=B12−P12c=7−5=2.
(ii)
It is clear to see thatU12c>U15c, so mobile vehicle m5 is filtered to achieve higher utility of cloudlet c1 with m2. The winning cloudlet is Cw=c1,c4(iii)
Determining the winning mobile vehicles:Mw=m5,m1Pwc=P1c=5,P4c=6, Pwm=4, σ1=4,σ2=1.Remember what we illustrate about the TASC mechanism which fails to satisfy the truthfulness. The IMCO overcomes the shortcomings of TASC. As what you can see below.IfC3 increases its offer B35 from 9 to 9+δ to cheat auctioneer. (δ>1). Then, Figure 6 shows the situation when assignment and pricing phase finish. In consequence, the utility of C3 is 9−10 = -1 which is lower than 0. So, it will be filtered in the next stage. To win the auction, C3 should bid truthfully.Figure 6
Mapping relationship graphic betweenCc and Mc with untruthful biding.


## 4.1. Details of IMCO

The IMCO consists of three phases: winner candidates determination phase, assignment and pricing phase, and winner elimination phase to achieve the preceding desirable properties.To be specific, Algorithm1 is used to filter some unqualified cloudlets and mobile vehicles so as to select winner candidates. To begin with, Algorithm 1 creates C+ from the original cloudlet set C which consists of bidders whose bid is greater than zero in accordance to B. That is to say, a cloudlet can appear several times in regard to the mobile vehicles for which the cloudlet’s offer is larger than zero. Next, the C+ is sorted to C in which the bids are sorted in a nonascending sequence. Also, mobile vehicles are sorted in a nondescending list according to ask A, denoted by M. Particularly, the Ajβ is the median ask of mobile vehicles in M, where β=1+m/2, is to find the minimize value α, so that Bpα+1qα+1<Ajβ and Bpαqα≥Ajβ. The Ajβ and Bpαqα are two standards to identify the winning candidates. For example, if cpq is a winning cloudlet candidate in Cc, it should satisfy Aq<Ajβ and Bpαqα≥Ajβ. The mobile vehicle mα is said to be winning candidate if and only if and at least one cloudlet from ℂ has a bid for mα. The β can be other value no necessary the median value. The value of β directly affect the number of Mc so to affect the number of Cc.In the next stage, to protect the system from biding and asking untruthfully, we closely combine assigning and pricing. The procedure is shown above in Algorithm2. First, the control center assigns the winning cloudlet candidates for winning mobile vehicle candidates. There are three situations needed to be discussed. The first situation is that there is only one cloudlet biding for one mobile vehicle, so the cloudlet is added to the Cbf waiting for processing Algorithm 2 and charged Bpαqα. The second situation is that there are two or above cloudlets scrambling for one mobile vehicle, the auctioneer would choose the cloudlet with the highest bid from the cloudlet candidates and add it to Cbf. The last situation is when there are two or more cloudlets that offer the highest bids, the control center will randomly choose one cloudlet among the cloudlets with the highest bid and add to Bpαqα. Different from the first situation, the cloudlet is charged for the 2nd highest bid. To make it easier to understand, supposing that the clearing price Bpαqα is 6 and two highest bids are Baj=Bbj=12, and the next bid in nonascending order is Bcj=10, then, caj and cbj have a 50-50 chance of becoming member of Cbf. And the winner will be charged 10 to avoid untruthfully biding since the 2nd highest bid is 10.In the final phase, if one cloudlet inCbf who wins at least two mobile vehicles in Mbf, the auctioneer relies on the efficiency of utilization to decide only one mobile vehicle for a cloudlet. For example, if ciθ and ciϑ are both in the Cbf, in other words, ci as a cloudlet wins 2 mobile vehicles, mθ and mϑ in Mbf. The auctioneer would choose one cloudlet according to whose utility is higher. Just as we illustrated above, if there are at least 2 utilities equal, the auctioneer will select only one mobile vehicle stochastically, when algorithm 3 is finished, there should be a one-to-one mapping relationship between the mobile vehicle in Mw and cloudlet in Cw since the redundant mobile vehicles can join another auction.The idea that cloudlet offloads one task to multiple mobile vehicles seems an excellent way to raise the efficiency of cloudlets, but it may be too ideal to adopt. The major tasks offloaded to mobile vehicles are applications run on mobile vehicles, and the applications may not design for running parallelly or running on heterogeneous hardware.


## 4.2. A Walk through Example

In this section, we use an example to demonstrate the process of IMCO by using cloudlets’ bid in Table2 and mobile vehicles’ ask in Table 3.The first stage is to determine the winner candidates.(i)
Create the setC+ from Table 2C+=c12,c15,c16,c22,c23,c24,c27,c34,c35,c41,c47,c51,c53,c54(ii)
Sequencing the cloudlets inC+ in a nonincreasing order to get ℂ=c15,c41,c35,c53,c27,c54,c12,c34,c47,c51,c16,c23,c24,c22(iii)
Sorting the mobile vehicles inM in a nondecreasing sequence to obtain M=m5,m1,m2,m6,m4,m3,m7(iv)
Drawing the mapping relationship graphic between cloudlets inℂ and mobile vehicles in M in Figure 4(v)
Calculating the two standards:Bpαqα=B16=5 and Ajβ=A6=4(vi)
Determining the winner cloudlet and mobile vehicle candidates:Figure 4
Mapping relationship graphic betweenCc and Mc.Cc=c15,c41,c35,c53,c27,c54,c12,c34,c47,c51,c16;Mc=m5,m1,m2(vii)
Drawing the mapping relationship graphic between cloudlets inCc and mobile vehicles in Mc in Figure 4(viii)
According to Algorithm2, we can obtainCbf=c15,c41,c12; Mbf=m5,m1,m2;so we can seeσ′5=1,σ′1=4,σ′2=1(ix)
Computing the price of cloudlets and determining the clearing price:Pbfc=P15c=B35=9,P41c=B51=6,P12c=Bpαqα=5(x)
Determining the payment paid to winning mobile vehicles:Pbfm = {P5m=P1m=P2m=Ajβ=4}
(xi)
Drawing the mapping relationship graphic between cloudlets inCbf and mobile vehicles in Mbf in Figure 5Figure 5
Mapping relationship graphic betweenCbf and Mbf.However, there still has some mobile vehicles server one cloudlet at the same time; auctioneer needs to filter the redundant vehicles.So, auctioneer executes the elimination algorithm depending on the utilities of cloudlet according to different mobile vehicles.(i)
Calculating the utilities of cloudletc1 according to mobile vehicle m5 and m2:U15c=B15−P15c=10−9=1,U12c=B12−P12c=7−5=2.
(ii)
It is clear to see thatU12c>U15c, so mobile vehicle m5 is filtered to achieve higher utility of cloudlet c1 with m2. The winning cloudlet is Cw=c1,c4(iii)
Determining the winning mobile vehicles:Mw=m5,m1Pwc=P1c=5,P4c=6, Pwm=4, σ1=4,σ2=1.Remember what we illustrate about the TASC mechanism which fails to satisfy the truthfulness. The IMCO overcomes the shortcomings of TASC. As what you can see below.IfC3 increases its offer B35 from 9 to 9+δ to cheat auctioneer. (δ>1). Then, Figure 6 shows the situation when assignment and pricing phase finish. In consequence, the utility of C3 is 9−10 = -1 which is lower than 0. So, it will be filtered in the next stage. To win the auction, C3 should bid truthfully.Figure 6
Mapping relationship graphic betweenCc and Mc with untruthful biding.


## 5. Theoretical Analysis

In this chapter, we analyze the IMCO that we designed with the attributes that we are interested in, including computational efficiency, individual rationality, budget balance, and truthfulness. If and if only those properties are achieved, the auction mechanism can be applied to the scenario.Theorem 1.
IMCO is computational efficiency.Proof.
In Algorithm1, there are not more than n×m cloudlet customers in the filtered set of cloudlets with positive valuation C+. Merge-sort sorts the cloudlets from C+ into C using Onmlognm times and sorting the mobile vehicles in M using Omlogm time. Then when auctioneer sorts the cloudlets into Cc, the number of cloudlets in Cc is n×1+m/2. The remain part of the algorithm, the following for loops, takes O1+m/2×1+n times. Thus, the time complexity of Algorithm 1 is Onm2+nmlogn.
In Algorithm2, there exist not more than 1+m/2 cloudlet customers in Cc and mobile vehicles in Mc. To find out the subset of CcCj, the auctioneer needs to take Onm time, since auctioneer has already sort the cloudlets in nonincreasing order, so the auctioneer can save some time without sorting again. There are no more than n mobile vehicles, so calculate the winning mobile vehicles only takes On time. The following loops take O1+m/2=On2m2.
In Algorithm2, there exist no more than 1+m/2 cloudlets in Cbf and mobile vehicles in Mbf, since Cbf=Mbf. The loop has a time complexity of OCbf×Cbf−1/2=Om2.
All in all, since the algorithms in IMCO is sequential execution, so the time complexity of IMCO mechanism isOnm2+nmlogn. It means that, IMCO is computational efficiency.Theorem 2.
IMCO is individually rational.Proof.
Each winning mobile vehiclemj∈Mw, the price offered to mobile vehicles mj is Pwj which is larger than the ask of mj on the basis of IMCO. Therefore, mobile vehicles accommodate the demand of desirable property.
In Algorithm2, for every cloudlet cij∈Cbf, there are two different situations needed to be discussed.
In the former situation, there is only one cloudletcij selects one mobile vehicle mj. According to Algorithm 2, the price that cloudlet ci needed to submit to auctioneer is the clearing price Bpαqα which is less than or equal to the price Bij.
In the last case, there are more than one cloudlet competing for one mobile vehicle. Supposing that cloudletci wins the auction; in other words, it has the highest bid valued Bij. Referring to Algorithm 2, the cij is charged the 2nd highest bid in Cj. It is easy to see that Pijc is no more than Bij.
As what we illustrated above, both the cloudlets and mobile vehicles meet the desirable property. In the next stage, auctioneer filters some redundant mobile vehicles and according to the utility of cloudlet. Algorithm3 will not affect the Pijm and Pijc, so it can still has the desirable property.Theorem 3.
IMCO is budget-balanced.Proof.
After the auctioneer filters all redundant mobile vehicles, only oneci∈Cw mapped to one mj∈Mw. According to the mapping relationship σj=i, it is easy to see that
(10)Pic≥Bpαqα≥Ajβ=Pjm.
That is(11)∑ci∈CwPic−∑mj∈MwPjm≥0.Lemma 4.
IMCO is truthful for mobile vehicles.Referring to Algorithm2, all the winning mobile vehicles are rewarded Ajβ. According to the utility formula (2) of mobile vehicles:
(12)Ujm=Pjm−Costj.Since the cost is regarded as constant and the reward is also constant, the utility of winning mobile vehicles can be improved, in the contrary, if the ask is higher than its cost in some degree (higher thanAjβ), the utility will decrease to 0.Lemma 5.
IMCO is truthful for cloudlets.According to Algorithm2, cloudlet cannot fake biding higher than the actual value of mobile vehicle to compete the mobile vehicle, because the price charging to winning cloudlets is variable. So, the utility of faking cloudlet is below zero. From formula (1), it is easy to obtain
(13)Uic=Vij−Pic<0.Since there are competition in the auction, the winning cloudlet cannot improve its utility by increasing its bid, because the price charged to it depends on the second-highest biding.Theorem 6.
IMCO is truthful.Proof.
According to the above lemma, we can get that IMCO is truthful for both mobile vehicles and cloudlets, that is to say, IMCO is truthful.


## 6. Performance Evaluation

In this part, we use the dataset to analyze the IMCO to find out whether it satisfies the desirable properties that are proved in the section above. Also, we validate the effectiveness of the proposed approach. Because there has no statistics about the cost of mobile vehicles and the demands of cloudlets. So we use the built-in uniform distribution function to generate the bids of cloudlet and ask of mobile vehicles in the scope from 0 to 1. That is the conclusions hold true no matter what dataset is used.


### 6.1. The Influence of Parameterβ

First, we randomly generate100 cloudlets and 100 mobile vehicles, which means there are 10000 bids in the auction. The number of winning cloudlet candidates and winning mobile vehicle candidates is closely related to the value of β. We found out that the largest number of winning cloudlet candidates appears when β is closed to the 1+m/2. So, we are interested in successful trades. Figure 7 shows the relationship between the number of successful trades and different β.Figure 7
The relationship between the number of successful trades and differentβ.From what we observe from Figure7 when the β is small, the threshold Bpαqα is small enough. However, the number of sellers is too small, so it limited the total number of cloudlet buyers. When the β is large, the threshold Bpαqα is so large that there are few cloudlet buyers who meet the conditions. And the β value is closely related to different values of n and m.


### 6.2. Computational Efficiency

We randomly generate different numbers of cloudlets and vehicles to test the running time. The computation time is shown in Table4.Table 4
Computation time.
n=100m50100150200250300Time(s)0.1600.4560.7421.0341.3251.617


### 6.3. Individual Rationality

To verify this property, we present both the winning cloudlets’ bids and the prices, which are shown in Figure8. In addition, Figure 9 shows the asks and the payments of winning vehicles. We can see that the bids are always no less than the price charged to cloudlets, and the rewards to vehicles are no less than the asks of vehicles. So, IMCO meets individual rationality. In other words, both the cloudlets and the vehicles can achieve positive utilities. The auctioneer can stimulate vehicles to carry out computation offloading tasks by paying them no less than their asks while the cloudlets can make use of the computation resources of the vehicles.Figure 8
The relationship between the bids and prices of winning cloudlets.Figure 9
The relationship between the asks and payments of winning mobile vehicles.As what we observe from the figures, the bids are always no less than the price charged to cloudlets, and the payment rewards to mobile vehicles are no less than the asks of mobile vehicles. So, the IMCO meets the individual rationality. In other words, both the cloudlets and mobile vehicles can achieve positive utilities, and it is a win-win game. The auctioneer can stimulate mobile vehicles to carry out computation offloading tasks by paying them no less than their asks, and the cloudlets can make use of the computation resources of mobile vehicles.


### 6.4. Budget Balance

IMCO is only of budget balance when the total fund that the cloudlets submit to the auctioneer is larger than or equal to the payments which are rewarded to the winning vehicles. We set the number of total cloudlets to100 consistently. By changing the number of vehicles from 50 to 150, we obtain the total prices and payments. The result is shown in Figure 10 showing each time the total number of vehicles increases by 10. It is clear that the total prices are always larger than the total payments.Figure 10
The relationship between the prices and payments of IMCO.As the result shows, the total prices are always larger than the total payments.


### 6.5. Truthfulness

We focus on two different cloudlets and mobile vehicles groups which contain both winners and losers. Then, by changing their bids and asks from0 to 1, we obtain the changing trends of utilities. The result of those in the winning set is shown in Figure 11. Figure 11(a) shows that when the cloudlet offers a truthful bid of 0.42, it has a utility of 0.12. However, no matter how higher a bid the cloudlet selects, the utility still stays the same, unless it reduces the bid under the original price. Figure 11(b) shows that the utility of mobile vehicles cannot be improved by asking untruthfully. Offering asks lower than 0.25 cannot achieve higher utilities while the utilities are always positive. The result of those not in the winning set is shown in Figure 12. Figure 12(a) shows that the utility of the losing cloudlet is always no larger than 0 since it loses the auction. However, even if the losing cloudlet fakes its bid, it still cannot make the utility larger than 0. Figure 12(b) shows that the utility of a losing mobile vehicle can only be 0 or below 0. Overall, IMCO can achieve truthfulness for both cloudlets and mobile vehicles.Figure 11
The utilities of vehicles and cloudlets in the winning set.
(a)
Buyer(b)
SellerFigure 12
The utilities of vehicles and cloudlets not in the winning set.
(a)
Buyer(b)
SellerIn conclusion, IMCO can achieve truthfulness for both cloudlets and mobile vehicles. They cannot improve their utilities by lying.


### 6.6. System Efficiency

In Section5, we have proved that IMCO meets the desirable properties in theoretical, and Section 6 uses the numerical results shows the above properties. As what we address, the TASC auction mechanism cannot guarantee the property of truthfulness applied in the cloudlet scenario. In Figure 13, the system efficiency of IMCO and TASC is evaluated as the number of successful trades.Figure 13
System efficiency with uniformly distributed datasets.Figure14 shows the efficiency of TASC and IMCO according to a number of successful trades. The bids and asks are generated by the MATLAB built-in unified function which is used to generate uniformly distributed datasets. Some of the efficiency of IMCO is sacrificed to guarantee truthfulness. Thus, the total efficiency of IMCO still has an advantage over TASC since IMCO maintains more winning cloudlet candidates than TASC, and IMCO only filters a few winning cloudlets in the third stage. Hence, IMCO can achieve a reasonable efficiency with all the desirable properties.Figure 14
Percentage improvement of normalized system efficiency comparing to TASC with uniformly distributed datasets.


## 6.1. The Influence of Parameterβ

First, we randomly generate100 cloudlets and 100 mobile vehicles, which means there are 10000 bids in the auction. The number of winning cloudlet candidates and winning mobile vehicle candidates is closely related to the value of β. We found out that the largest number of winning cloudlet candidates appears when β is closed to the 1+m/2. So, we are interested in successful trades. Figure 7 shows the relationship between the number of successful trades and different β.Figure 7
The relationship between the number of successful trades and differentβ.From what we observe from Figure7 when the β is small, the threshold Bpαqα is small enough. However, the number of sellers is too small, so it limited the total number of cloudlet buyers. When the β is large, the threshold Bpαqα is so large that there are few cloudlet buyers who meet the conditions. And the β value is closely related to different values of n and m.


## 6.2. Computational Efficiency

We randomly generate different numbers of cloudlets and vehicles to test the running time. The computation time is shown in Table4.Table 4
Computation time.
n=100m50100150200250300Time(s)0.1600.4560.7421.0341.3251.617


## 6.3. Individual Rationality

To verify this property, we present both the winning cloudlets’ bids and the prices, which are shown in Figure8. In addition, Figure 9 shows the asks and the payments of winning vehicles. We can see that the bids are always no less than the price charged to cloudlets, and the rewards to vehicles are no less than the asks of vehicles. So, IMCO meets individual rationality. In other words, both the cloudlets and the vehicles can achieve positive utilities. The auctioneer can stimulate vehicles to carry out computation offloading tasks by paying them no less than their asks while the cloudlets can make use of the computation resources of the vehicles.Figure 8
The relationship between the bids and prices of winning cloudlets.Figure 9
The relationship between the asks and payments of winning mobile vehicles.As what we observe from the figures, the bids are always no less than the price charged to cloudlets, and the payment rewards to mobile vehicles are no less than the asks of mobile vehicles. So, the IMCO meets the individual rationality. In other words, both the cloudlets and mobile vehicles can achieve positive utilities, and it is a win-win game. The auctioneer can stimulate mobile vehicles to carry out computation offloading tasks by paying them no less than their asks, and the cloudlets can make use of the computation resources of mobile vehicles.


## 6.4. Budget Balance

IMCO is only of budget balance when the total fund that the cloudlets submit to the auctioneer is larger than or equal to the payments which are rewarded to the winning vehicles. We set the number of total cloudlets to100 consistently. By changing the number of vehicles from 50 to 150, we obtain the total prices and payments. The result is shown in Figure 10 showing each time the total number of vehicles increases by 10. It is clear that the total prices are always larger than the total payments.Figure 10
The relationship between the prices and payments of IMCO.As the result shows, the total prices are always larger than the total payments.


## 6.5. Truthfulness

We focus on two different cloudlets and mobile vehicles groups which contain both winners and losers. Then, by changing their bids and asks from0 to 1, we obtain the changing trends of utilities. The result of those in the winning set is shown in Figure 11. Figure 11(a) shows that when the cloudlet offers a truthful bid of 0.42, it has a utility of 0.12. However, no matter how higher a bid the cloudlet selects, the utility still stays the same, unless it reduces the bid under the original price. Figure 11(b) shows that the utility of mobile vehicles cannot be improved by asking untruthfully. Offering asks lower than 0.25 cannot achieve higher utilities while the utilities are always positive. The result of those not in the winning set is shown in Figure 12. Figure 12(a) shows that the utility of the losing cloudlet is always no larger than 0 since it loses the auction. However, even if the losing cloudlet fakes its bid, it still cannot make the utility larger than 0. Figure 12(b) shows that the utility of a losing mobile vehicle can only be 0 or below 0. Overall, IMCO can achieve truthfulness for both cloudlets and mobile vehicles.Figure 11
The utilities of vehicles and cloudlets in the winning set.
(a)
Buyer(b)
SellerFigure 12
The utilities of vehicles and cloudlets not in the winning set.
(a)
Buyer(b)
SellerIn conclusion, IMCO can achieve truthfulness for both cloudlets and mobile vehicles. They cannot improve their utilities by lying.


## 6.6. System Efficiency

In Section5, we have proved that IMCO meets the desirable properties in theoretical, and Section 6 uses the numerical results shows the above properties. As what we address, the TASC auction mechanism cannot guarantee the property of truthfulness applied in the cloudlet scenario. In Figure 13, the system efficiency of IMCO and TASC is evaluated as the number of successful trades.Figure 13
System efficiency with uniformly distributed datasets.Figure14 shows the efficiency of TASC and IMCO according to a number of successful trades. The bids and asks are generated by the MATLAB built-in unified function which is used to generate uniformly distributed datasets. Some of the efficiency of IMCO is sacrificed to guarantee truthfulness. Thus, the total efficiency of IMCO still has an advantage over TASC since IMCO maintains more winning cloudlet candidates than TASC, and IMCO only filters a few winning cloudlets in the third stage. Hence, IMCO can achieve a reasonable efficiency with all the desirable properties.Figure 14
Percentage improvement of normalized system efficiency comparing to TASC with uniformly distributed datasets.


## 7. Conclusion

In this paper, we concentrate on an emerging paradigm in the current IoT systems, in which computation is offloaded to vehicle owners. Because of the distance between mobile vehicles and cloudlets and the distinct computational capabilities of mobile vehicles, the mobile vehicles can be seen as heterogeneous sellers to cloudlets, so different cloudlets may evaluate each mobile vehicle due to different demands and give different valuations toward different vehicles. In order to make mobile vehicles offer the computation offloading servers to cloudlets, we have proposed the IMCO which deals with the resource exchanging between mobile vehicles and cloudlets. IMCO can meet the properties such as individual rationality, budget balance, system efficiency, and truthfulness for both cloudlets and mobile vehicles.There are some aspects that may be improved in future work, such as the system efficiency is not that satisfying even it is better than TASC as a whole since IMCO sacrifices some efficiency to maintain the truthfulness for both cloudlets and mobile vehicles. The other problem is that even if the time complexity of the mechanism is acceptable, the program in MATLAB could not be seen as of high-efficiency. So we could optimize the programs to execute faster as we expected in further study.



---

*Source: 1514437-2022-01-19.xml*