CN103218737B - A kind of based on multi dimensional resource pricing method in the mobile cloud computing environment of two day market - Google Patents

Abstract

The invention discloses a kind of based on multi dimensional resource pricing method in the mobile cloud computing environment of two day market, the method operates in mobile cloud computing environment, relate to two groups of participants of mobile cloud computing environment, one group is the Cloudlet having resource, another group is the VM of request resource, VM is regarded as the buyer in two day market economic model, regard Cloudlet as the seller, both sides complete the configuration of resource by price interaction mechanism, the unloading completed on application request VM to Cloudlet performs, and saves the energy consumption of mobile device.Price interaction mechanism in the method is based on two day market game and combination punishes that pricing mechanism and balanced effectiveness discount design, the multi dimensional resource of mobile subscriber's application request reasonably can be distributed on multiple Cloudlet and dispatch, thus maximize the system benefit of mobile cloud.

Description

A Multidimensional Resource Pricing Method in Mobile Cloud Computing Environment Based on Two-sided Market

technical field

The invention relates to the field of mobile cloud computing environment and game theory, in particular to a multi-dimensional resource pricing method in a mobile cloud computing environment based on a bilateral market.

Background technique

With the vigorous development of the mobile Internet, cloud computing services based on mobile terminals such as mobile phones have emerged. Mobile Cloud Computing (MCC, Mobile Cloud Computing) refers to the delivery and use of an IT resource or (information) service that obtains the required infrastructure, platform, software (or application), etc. through the mobile network in an on-demand and easily expandable manner. model. Mobile cloud computing is the combination of mobile Internet industry and cloud computing technology, and it is a hot new business development direction in the IT industry. It not only means a technology or a combination of a series of technologies, it adheres to the core concept of "on-demand service", especially in today's increasingly convenient and popular smart terminal environment, it has made outstanding contributions to the IT field and people's lives contribute. It has the characteristics of breaking through the limitations of terminal hardware, convenient data access, intelligent load balancing, reducing management costs, and on-demand services to reduce costs. Due to the limited energy of mobile devices, in order to prolong the use time of mobile devices, research on energy saving methods for mobile devices is the key to ensure the rapid development of mobile cloud computing services.

At present, there are many companies around the world that have successfully operated mobile cloud computing instances. For example, Apple released the online cloud storage service "iCloud" for mobile phones. This solution allows iPhone or iPad to handle emails, notepad items, photos, etc. as easily as a PC. Everything the user does will be automatically updated to the iPad, iPhone, etc. Apple terminal device. As a pioneer of cloud computing, Google launched new applications based on mobile terminals and cloud computing at the end of 2010, including integrated mobile search, voice search, fixed-point search, Google mobile map, and Google Street View on Android. Microsoft and RIM have also successively launched application service solutions for many users, both of which are mobile Internet applications with cloud computing characteristics.

In the Chinese market, more and more Chinese companies are also joining the competition of mobile cloud computing. China Mobile and the Chinese Academy of Sciences launched the "Dayun Project", China Telecom released the "Ningyun Project"; and mobile phone manufacturer Yulong Coolpad also launched the "Cool Cloud Project", becoming the first mobile cloud computing service platform in China. The era of mobile cloud computing is coming.

Cloud computing includes the following levels of services: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). Among them, IaaS deploys services on a resource pool constructed of a large number of servers, storage devices, and network devices, enabling various business systems to obtain the required resources for operation. Since there are multiple applications deployed in the same cloud computing environment, and the applications come with time, there will often be peaks and low peaks. Therefore, especially in peak periods, it is necessary to reasonably schedule resources to meet the actual needs of the applications. At the same time, it can achieve the purpose of rationally allocating resources and saving energy consumption of terminal equipment.

Resource allocation is an important part of cloud computing, and its efficiency directly affects the working performance of cloud computing environment. The resources in the cloud computing resource pool include CPU, memory (Memory), storage space (Storage), bandwidth (Bandwidth), and I/O access rate. Assuming that the mobile cloud system consists of m Cloudlets to form a resource pool, the resource set of Cloudlet _j is R _j ={B,CPU,S}, which in turn represent bandwidth, CPU, and storage resources, n VMs want to obtain resources, and the resource characteristics of VM _i The set is r _i ={B,CPU,S}. After a Cloudlet has allocated resources, its resource vector needs to be corrected. Because Cloudlet has limited resources, how to allocate Cloudlet resources and complete the matching of VM to Cloudlet, so as to maximize the utilization efficiency of Cloudlet resources, has become a key issue in the mobile cloud computing platform.

Mobile cloud computing is oriented to different applications, and different applications correspond to different service qualities, so the required resources are also different. In addition, since cloud computing provides services externally, the cost of resource consumption must be considered, which also makes cloud computing The resource scheduling problem is more complicated.

Contents of the invention

The technical problem to be solved by the present invention is to provide a multi-dimensional resource pricing method in a mobile cloud computing environment based on a two-sided market game to improve the resource utilization rate of resource pools and save energy consumption of mobile devices.

In order to solve the above-mentioned technical problems, the technical solution adopted by the present invention is: a multi-dimensional resource pricing method in a mobile cloud computing environment based on a two-sided market, including a mobile cloud computing system, and the mobile cloud computing system includes a mobile network resource storage system and a mobile terminal device communicating with the resource storage system, the resource storage system includes a plurality of autonomous cloud slice Cloudlets, each Cloudlet has multidimensional and different resources, and each Cloudlet selfishly maximizes its own benefits as The target selects the virtual machine bearing form VM requested by the mobile terminal application, the Cloudlet is the seller who owns resources in the two-sided market, and the VM is the buyer who purchases resources in the two-sided market, and it is characterized in that the pricing method adopts The pricing mechanism between VM and Cloudlet prompts VM to select a suitable Cloudlet, and prompts Cloudlet to select and determine the VM it accepts, so as to complete the matching between VM and cloudlet. The specific steps of this method are:

Step 1: The VM calculates its waiting time according to the arrival time of its request, that is, the waiting time t _i of VM _i = current time - the arrival time of VM _i request, and set the initial bid vector of the i-th VM to the j-th Cloudlet multi-dimensional resource as in Basic pricing for the unit resource that cloudlet _j provides services for VM _i , Cloudlet _j represents the jth Cloudlet, VM _i represents the i-th VM;

Step 2: Each VM _i calculates the utility of being served by different Cloudlet _j , and VM _i obtains the service utility value from Cloudlet _j Use the following function to calculate:

${\mathrm{<span\; class="notranslate">\; \&pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; ik</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&Center\; Dot;</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>$

Among them, f _j (t _i ) represents the penalty Cloudlet _j pays to VM _i due to service delay, f _j (t _i )=st _ij ·w _i ·t _i , st _ij represents the unit time delay Cloudlet _j to VM _i Pay penalty coefficient, w _i represents the priority of VM _i , t _i represents the waiting time of VM _i request, a _ik is the unit utility constant when VM _i obtains the k-th dimension request resource, Represents the Cloudlet multi-dimensional resource vector requested by VM _i , k refers to the kth dimension, d represents the dimension of Cloudlet multi-dimensional resources, g(t _i ) represents the utility lost by VM _i due to waiting for the response, g(t _i )=at _i · w _i ·t _i , at _i is a constant of unity gain at which VM _i loses utility;

Step 3: Mark the cloudlet whose VM utility is greater than 0 as the candidate cloudlet of the VM, and put it into the candidate cloudlet set. If the candidate cloudlet set is empty, the resource request of the VM will not be sent, and the application will be executed locally on the mobile terminal. The cloudlet collection is not empty, and the VM selects an optimal cloudlet from the available cloudlets according to the VM utility value. The resource request includes the price to be paid to the optimal Cloudlet;

Step 4: Cloudlet _j that receives the resource request of VM _i first confirms whether its remaining resources meet the request of VM _i , if not, then rejects the request of VM _i , if it does, Cloudlet _j calculates according to the utility function formula The utility of serving a group of VM sets, the utility function formula is as follows:

${\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; load</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; index</span>}}$

in,

${\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&CenterDot;</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&CenterDot;</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; index</span>}}<span\; class="notranslate">\; =</span>\frac{{<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; \&CenterDot;</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; (</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

p(t _i )=bt _i ·w _i ·t _i

Indicates the utility obtained by Cloudlet _j serving a group of VM sets S _j , S _j is the set of VMs that Cloudlet _j intends to serve, Indicates the utility discount generated by the unbalanced utilization of multi-dimensional resources when Cloudlet _j serves VM set S _j , p(t _i ) indicates the remuneration paid to Cloudlet _j in the two-sided market because Cloudlet _j serves VM _i , and bt _i is the unit incentive utility gain constant;

Step 5: Each Cloudlet _j in the mobile cloud computing system selects the VM subset S _j that provides services according to the Cloudlet utility value among all requesting VMs, and rejects other VMs. When the VM is selected by the Cloudlet, the corresponding mobile terminal The device offloads its corresponding application to the Cloudlet for execution;

Step 6: The VM whose resource request is rejected by the corresponding Cloudlet in Step 5 will initiate a resource request again. When the resource request is initiated again, the VM's bid for the Cloudlet that rejected it will be increased by a margin based on the price in Step 3 That is, if VM _i is rejected by Cloudlet _j , the price of VM _i to Cloudlet _j is updated as The bids for other Cloudlets maintain the price of step 3;

Step 7: Repeat steps 2 to 6 until no VM resource request message is sent out. At this time, the matching from VM to Cloudlet is completed, and all VMs that are successfully matched can obtain the multi-dimensional resources of Cloudlet, and uninstall the application of the corresponding mobile terminal device Execute on Cloudlet, and finally feed back the execution result to the mobile terminal device.

The present invention considers a mobile cloud computing system (MCCs) deployed in a local area network. The system is composed of a cloud resource pool composed of m Cloudlets with multi-dimensional resources and n VMs carrying end-user applications. The present invention regards the system as an economic model—two-sided market model, which is composed of two types of participants, the seller who owns the resource and the buyer who needs to pay to purchase the resource. Cloudlet in the present invention is a seller who owns resources, and VM is a buyer who purchases resources. The two parties complete the matching through the price interaction mechanism to realize price-based resource allocation.

Because in the mobile cloud computing system, timeliness is the key to evaluate the system efficiency, and the QoS of end users also has strong time sensitivity. Since the application of the end user arrives dynamically according to time, if the VM carrying an application is not scheduled in time, the VM will directly lead to the decline of the QoS experience of the application due to the long waiting time for the response, resulting in the loss of system customers; In addition, Cloudlet, the resource owner, will also pay corresponding penalties for not scheduling VMs in time, and the longer the waiting time of VMs, the more penalties need to be paid, which directly leads to the reduction of Cloudlet's revenue, which is beneficial to both buyers and sellers. bad decision.

The calculation of the effect function in Step 4 of the present invention embodies the adoption of a scheduling method based on response time. Because rewards can be obtained from the two-sided market platform, VMs with a long waiting time for Cloudlet services will receive greater benefits, so Cloudlet will choose VMs with a long waiting time for services. Figure 3 depicts the schematic diagram of application arrival. Under our pricing mechanism, VM ₂ will be scheduled to be executed on Cloudlet first. Although its priority is the lowest, its waiting time is much longer than that of VM ₁ and VM ₃ .

At the same time, when designing the utility function of Cloudlet, the concept of utility discount is introduced, mainly to make the multi-dimensional resources of Cloudlet be used in a balanced manner as much as possible, and to avoid the high utilization rate of resources in one dimension and the low utilization rate of the other dimension. phenomena to achieve optimal utilization of resources.

Utility discount in step 4 Design with the following functions:

${\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; index</span>}}<span\; class="notranslate">\; =</span>\frac{{<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; \&Center\; Dot;</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; (</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

The utility discount value is a real number between [0, 1], the larger the value, the The closer the three-dimensional value of is, the more balanced the three-dimensional resources are. Considering Cloudlet's utility function

${\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; load</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; index</span>}}$

To make the utility value of Cloudlet as large as possible, then The value of will be as large as possible, so that the resources allocated by Cloudlet three-dimensionally should be as balanced as possible. Therefore, utility discount helps resource allocation to achieve balance among different dimensions, and indirectly realizes the optimal utilization of resources.

Compared with the prior art, the beneficial effects of the present invention are: the present invention is based on a two-sided market game model, and implements scheduling by pricing the multi-dimensional resources of mobile cloud computing. Under the circumstances, formulate incentives for the execution strategy of the pricing mechanism, so that participants such as Cloudlet and terminal equipment under the mobile cloud computing can realize the optimal allocation of resources under the pricing scheduling strategy formulated by the system; in addition, the concept of utility discount is added to make Cloudlet Multi-dimensional resources can be distributed in a balanced manner, thereby utilizing the resources of the mobile cloud platform more effectively. The present invention can improve the resource utilization rate of the resource pool and save energy consumption of mobile devices; for the mobile cloud computing environment, the method has certain versatility , and is easy to implement, and has a very broad application prospect.

Description of drawings

FIG. 1 is a schematic diagram of a scene of a network model of the present invention;

Fig. 2 is the VM-Cloudlet bilateral market game model of the present invention;

Fig. 3 is a schematic diagram of the arrival of application requests over time according to an embodiment of the present invention;

Figure 4 is a schematic diagram of multi-dimensional resource allocation according to an embodiment of the present invention; 4(a) is an inefficient allocation scheme; Figure 4(b) is an efficient resource allocation scheme for 10 VMs by the system in one cycle;

Fig. 5 is the convergence result of the bilateral market pricing method according to an embodiment of the present invention; Fig. 5(a) is a schematic diagram of price convergence; Fig. 5(b) is a schematic diagram of utility convergence;

Figure 6 is a schematic diagram of the unilateral effect of the bilateral market due to the change of the size of the unilateral participant in an embodiment of the present invention; Figure 6(a) is a schematic diagram of the VM unilateral effect; Figure 6(b) is a schematic diagram of the Cloudlet unilateral effect;

Figure 7 is a schematic diagram of the resource utilization of the four methods; Figure 7 (a) is a schematic diagram of the average resource utilization of the four methods; Figure 7 (b) is a schematic diagram of the maximum dimension resource utilization of the four methods;

Figure 8 is a schematic diagram of the response time of a VM waiting to be scheduled; Figure 8(a) is a schematic diagram of the average response time; Figure 8(b) is a schematic diagram of the maximum response time;

Figure 9 is a schematic diagram of the system benefits of the four methods;

FIG. 10 is a schematic diagram of the total execution time of the four methods.

detailed description

The multi-dimensional resource pricing method in the mobile cloud computing environment based on the two-sided market of the present invention comprises the following steps:

Step 1: The VM calculates its waiting time according to the arrival time of its request, that is, the waiting time t _i of VM _i = current time - the arrival time of VM _i request, and set the initial bid vector of the i-th VM to the j-th Cloudlet multi-dimensional resource as in Basic pricing for the unit resource that cloudlet _j provides services for VM _i , cloudlet _j represents the jth Cloudlet, VM _i represents the ith VM;

Step 2: Each VM _i calculates the utility of being served by different Cloudlet _j , and VM _i obtains the service utility value from Cloudlet _j Use the following function to calculate:

${\mathrm{<span\; class="notranslate">\; \&pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; ik</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&Center\; Dot;</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>$

Among them, f _j (t _i ) represents the penalty Cloudlet _j pays to VM _i due to service delay, f _j (t _i )=st _ij ·w _i ·t _i , st _ij represents the unit time delay Cloudlet _j to VM _i Pay penalty coefficient, w _i represents the priority of VM _i , t _i represents the waiting time of VM _i request, a _ik is the unit utility constant when VM _i obtains the k-th dimension request resource, Represents the Cloudlet multi-dimensional resource vector requested by VM _i , k refers to the kth dimension, d represents the dimension of Cloudlet multi-dimensional resources, g(t _i ) represents the utility lost by VM _i due to waiting for the response, g(t _i )=at _i · w _i ·t _i , where at _i is a constant of unity gain at which VM _i loses utility;

Step 3: Mark the cloudlet whose VM utility is greater than 0 as the candidate cloudlet of the VM, and put it into the candidate cloudlet set. If the candidate cloudlet set is empty, the resource request of the VM will not be sent, and the application will be executed locally on the mobile terminal. The cloudlet set is not empty, the VM selects an optimal cloudlet from the available cloudlets according to the VM utility value, and the optimal cloudlet is the cloudlet that makes the VM produce the largest effect value, and sends a resource request to the optimal cloudlet, the The resource request includes the price to be paid to the optimal Cloudlet;

Step 4: Cloudlet _j that receives the resource request of VM _i first confirms whether its remaining resources meet the request of VM _i , if not, then rejects the request of VM _i , if it does, Cloudlet _j calculates according to the utility function formula The utility of serving a group of VM sets, the utility function formula is as follows:

${\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; load</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; index</span>}}$

in,

${\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&CenterDot;</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&Center\; Dot;</span>{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; index</span>}}<span\; class="notranslate">\; =</span>\frac{{<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; \&Center\; Dot;</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; (</span>\underset{{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\stackrel{<span\; class="notranslate">\; \&Right\; Arrow;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

p(t _i )=bt _i ·w _i ·t _i

Indicates the utility obtained by Cloudlet _j serving a group of VM sets S _j , S _j is the set of VMs that Cloudlet _j intends to serve, Indicates the utility discount generated by the unbalanced utilization of multi-dimensional resources when Cloudlet _j serves VM set S _j , p(t _i ) indicates the remuneration paid to Cloudlet _j in the two-sided market because Cloudlet _j serves VM _i , and bt _i is the unit incentive utility gain constant;

Step 5: Each Cloudlet _j in the mobile cloud computing system selects the VM subset S _j that provides services according to the Cloudlet utility value among all requesting VMs, and rejects other VMs. When the VM is selected by the Cloudlet, the corresponding mobile terminal The device offloads its corresponding application to the Cloudlet for execution;

Step 6: The VM whose resource request is rejected by the corresponding Cloudlet in Step 5 will initiate a resource request again. When the resource request is initiated again, the VM's bid for the Cloudlet that rejected it will be increased by a margin based on the price in Step 3 That is, if VM _i is rejected by Cloudlet _j , the price of VM _i to Cloudlet _j is updated as The bids for other Cloudlets maintain the price of step 3;

Step 7: Repeat steps 2 to 6 until no VM resource request message is sent out. At this point, the matching from VM to Cloudlet is completed, and all VMs that are successfully matched can obtain the multi-dimensional resources of Cloudlet, and uninstall the application of the corresponding mobile terminal device Execute on Cloudlet, and finally feed back the execution result to the mobile terminal device.

The present invention considers a mobile cloud computing system (MCCs) deployed in a local area network. The system consists of a cloud resource pool composed of m Cloudlets with multi-dimensional resources and n VMs carrying end-user applications. The system model diagram is shown in Figure 2 shown.

The calculation of the effect function in Step 4 of the present invention embodies the adoption of a scheduling method based on response time. Because rewards can be obtained from the two-sided market platform, VMs with a long waiting time for Cloudlet services will receive greater benefits, so Cloudlet will choose VMs with a long waiting time for services. Figure 3 depicts the schematic diagram of application arrival. Under our pricing mechanism, VM ₂ will be scheduled to be executed on Cloudlet first. Although its priority is the lowest, its waiting time is much longer than that of VM ₁ and VM ₃ . .

At the same time, when designing the utility function of Cloudlet, the concept of utility discount is introduced, mainly to make the multi-dimensional resources of Cloudlet be used in a balanced manner as much as possible, and to avoid the high utilization rate of one dimension and the low utilization rate of the other dimension. phenomena to achieve optimal utilization of resources.

Figure 4 is a schematic diagram of resource allocation with 3 Cloudlets and 10 VMs. As shown in Figure 4(a), it is an inefficient allocation scheme. Although the storage space of Cloudlet ₁ , the CPU of Cloudlet ₂ and the bandwidth utilization of Cloudlet ₃ are all high, the bandwidth of Cloudlet ₁ , the storage space of Cloudlet ₂ and the The storage space utilization rate of Cloudlet ₃ is only 40%, 70% and 60%, respectively, and the utilization rate of 3D resources is unbalanced. As a result, only 7 VMs can use the resources in the system, and the other 3 VMs must wait until the next execution cycle is scheduled. In contrast, after the design of utility discount is added, as shown in Figure 4(b), an efficient resource allocation scheme for 10 VMs in one cycle is given. The three-dimensional resources of the three Cloudlets are all used in a balanced manner and the The system can fully accommodate 10 VMs. Figure 4 shows that the design of utility discount can effectively improve the resource utilization rate of the system and balance the resource utilization rate among various dimensions.

The specific implementation of the present invention will be described below through simulation experiments, and the effectiveness of the present invention will be verified by comparison with other embodiments. The simulation experiment realized four different resource pricing and scheduling methods. The first method is a multi-dimensional resource allocation method based on a two-sided market with punishment and balance proposed by the present invention, which is denoted as MPTMG-PB. The second method is based on a two-sided market A resource allocation method with no penalty and no balance, denoted as MPTMG-NPNB. The main difference between the two approaches is whether penalty payments and utility discounts are used in the price adjustment process. The third and fourth methods use the fixed price mechanism. In these two methods, the VM pays a fixed price to Cloudlet to use its resources, and according to the arrival time of the application, the corresponding VM is scheduled to obtain the resources of Cloudlet and complete the application. Offload tasks for execution to the cloud. The difference is that the type of VM in the third method is fixed, and there are only a limited number of 8 types. Each type of VM has fixed resource requirements, and Cloudlet allocates resources for it according to the type of VM. The method is named LIMITED; In the fourth method, the type of VM is not fixed, and the required resources are variable, and Cloudlet only allocates the requested amount of resources to it. This method is called UNLIMITED. Under the same scenario and experimental settings, using Java programming to implement the above methods and conduct simulation experiments, we compared the average resource utilization, maximum dimension resource utilization, average response time, maximum response time, and system utility of these four different methods and execution time parameters.

In the setting of the simulation experiment, each Cloudlet has three-dimensional resources, bandwidth, CPU and storage space, and the total amount of three-dimensional resources is (10000, 10000, 10000). The application requests of mobile terminals obey the Poisson distribution and arrive dynamically at the arrival rate of λ. Each application request has its own resource requirements. Without loss of generality, we assume that the elastic range of resource requests in each dimension of the application is [ 1,600], and assume that the execution time of the application is randomly within the range of [1,5] cycles, and the values of parameters such as w _i , a _ik , st _ij , at _i , bt _i are randomly selected from [1,10] , [0.1,0.5], [0.01,0.05], [0.01,0.05], real numbers in the range of [0.01,0.05]. Base price of 3D resources for each Cloudlet are randomly generated within [0.05,0.1] respectively.

Figure 5 depicts the convergence behavior of the iterative process of the method of the present invention. As shown in Figure 5(a), the multidimensional price adjustment process of a VM in price interaction is described. Before starting the price interaction, each VM bids relatively low for Cloudlet resources. After being rejected by a Cloudlet, the VM will gradually increase the bid for the Cloudlet to ensure that the Cloudlet's resources can be obtained. The fluctuation of the price in the figure is caused by the change of the bid of the VM to different Cloudlets. Finally, the price of the VM stabilizes, indicating that the selection of mutual matching with the Cloudlet has been completed. As shown in Figure 5(b), which describes the convergent behavior of the total utility of all VMs, all Cloudlets, and the system during the interaction process, the utility will no longer change when all pairings are completed.

Figure 6 depicts a schematic diagram of the unilateral effect of a two-sided market due to changes in the size of unilateral participants. An important feature of the two-sided market is the existence of unilateral effects. Because of the heterogeneity of the participants, the number of participants on one side is fixed, and the number of participants on the other side increases or decreases, which will affect the outcome of the entire game. As shown in Figure 6(a), it describes the competition of buyers, and the number of sellers is fixed. For example, when the number of Cloudlets is fixed to 10, as the number of VMs arriving in each cycle increases, the competition of VMs for resources increases. An increase in the price paid to the Cloudlet leads to a decrease in the average utility of the VM, while an increase in the average utility received by the Cloudlet. Similarly, as shown in Figure 6(b), it describes the competition of sellers. When the number of buyers is fixed, for example, the number of fixed VMs is 150, gradually increase the number of sellers, and the number of cloudlets that can be selected by VMs increases, and the price also increases accordingly. The increase is slow, so the average utility of VM increases with the increase of the number of Cloudlets, but the average utility of Cloudlets decreases with the increase of its number.

Figure 7 depicts the resource usage of the four methods, including the average resource usage shown in Figure 7(a) and the resource usage of the largest dimension shown in Figure 7(b). Both the average resource utilization rate and the resource utilization rate of the largest dimension gradually increase with the increase of λ, and finally tend to be smooth. Compared with the other three methods, the method MPTMG-PB proposed by the present invention has the highest average resource utilization rate and is close to the resource utilization rate of the largest dimension, which proves that the design of utility discount in this method is very effective for improving resource utilization utility . In the LIMITED method, each application is matched to a type of VM, and usually the resources requested by this type of VM exceed the amount of resources actually required by the application, thus causing a waste of system resources.

Figure 8 depicts the response time of a VM waiting to be scheduled, including the average response time in Figure 8(a) and the maximum response time in Figure 8(b). The efficient resource allocation method can increase the number of concurrently executing VMs and reduce the response time of scheduled applications, thereby effectively saving the energy consumption of the mobile terminal. As shown in Figure 8(a), when λ=180, the average response time of the method MPTMG-PB proposed by the present invention is 20%, 50% and 70% lower than the other three methods MPTMG-NPNB, UNLIMITED and LIMITED, respectively %. The maximum response time in Fig. 8(b) directly reflects the service quality. It can be seen that the MPTMG-PB method is 30%, 40% and 90% lower than the MPTMG-NPNB, UNLIMITED and LIMITED methods, respectively. Longer response times will significantly reduce end-user satisfaction. The results in Fig. 8 show that the penalty design introduced due to the response time helps the mobile cloud computing system to attract more and more users into the market. By reducing the response time of VM scheduling, Cloudlet can reduce the additional overhead caused by delayed response to scheduling VMs and get rewards paid by the platform, thereby increasing its own revenue.

Figure 9 depicts the system gains for the four approaches. The system returns of the MPTMG-PB and MPTMG-NPNB methods are significantly higher than the two methods of the fixed price mechanism. When λ>110, the system returns of the MPTMG-PB method start to be nearly 20% higher than the MPTMG-NPNB method. Since the MPTMG-PB method can achieve higher resource utilization, Cloudlet can get more system benefits by selling more resources to VMs and VMs pay less.

Fig. 10 describes the total execution time of the four methods, the total execution time can help reduce the energy consumption of the mobile terminal in the mobile cloud computing system. Although application requests are only generated in the first 50 cycles, as λ increases, the system load gradually increases, so that system resources are insufficient to satisfy incoming application requests at the same time, and some application requests will wait to be scheduled, so that within 50 cycles The application request cannot be scheduled completely, and the response time will be superimposed. Therefore, the application requests generated in 50 cycles will be scheduled in the subsequent time. When λ=180, as shown in Figure 10, it takes 70 cycles for MPTMG-PB to schedule and execute all application requests, while MPTMG-NPNB, UNLIMITED, and LIMITED need 80, 100, and 130 cycles, respectively. The execution time required by the method used in the present invention is the shortest, which can effectively save the energy consumption of the terminal equipment.

Therefore, the simulation experiment results show that the mobile cloud computing multi-dimensional resource pricing method based on the two-sided market proposed by the present invention can effectively improve the resource utilization rate of the mobile cloud computing system, increase system revenue, and save energy consumption of terminal equipment.

Claims (2)

1. A multi-dimensional resource pricing method in a mobile cloud computing environment based on bilateral market comprises a mobile cloud computing system, the mobile cloud computing system comprises a resource storage system of a mobile network and a mobile terminal device in communication with the resource storage system, the resource storage system comprises a plurality of autonomous cloud disk cloudlets, each Cloudlet having a multidimensional different resource, each of said cloudlets is selfish to select the virtual machine bearer form VM requested by the mobile terminal application with the goal of maximizing its own revenue, the Cloudlet is a seller of the bilateral market that owns the resource, the VM is a buyer of the bilateral market that purchases the resource, wherein the pricing method causes the VM to select an appropriate Cloudlet and causes the Cloudlet to select and determine the VM it accommodates through a pricing mechanism between the VM and the Cloudlet, therefore, matching between the VM and the clouldlet is completed, and the method specifically comprises the following steps:

step 1: the VM calculates its latency based on its request arrival time, i.e., the VM_iWaiting time t of_iCurrent time-VM_iRequesting arrival time, setting the initial bid vector of the ith VM to the jth Cloudlet multi-dimensional resource to beWhereinIs a cloddlet_jAs a VM_iBasic pricing of unit resources, cloudlets, for providing services_jRepresents the jth Cloudlet, VM_iRepresents the ith VM;

step 2: each VM_iThe computation is differentiated by the Cloudlet_jUtility of service, VM_iSlave Cloudlet_jTo obtain the utility value of the serviceThe following function is used for calculation:

${\mathrm{\&pi;}}_i^t\left(j,{\stackrel{\&RightArrow;}{p}}_{ij}\right)=\underset{1\&le;k\&le;d}{\&Sigma;}{w}_i\&CenterDot;a_{ik}\&CenterDot;{\stackrel{\&RightArrow;}{v}}_i\&lsqb;k\&rsqb;-\underset{1\&le;k\&le;d}{\&Sigma;}{\stackrel{\&RightArrow;}{p}}_{ij}\&lsqb;k\&rsqb;\&CenterDot;{\stackrel{\&RightArrow;}{v}}_i\&lsqb;k\&rsqb;+f_j\left(t_i\right)-g\left(t_i\right)$

wherein f is_j(t_i) Indicating Cloudlet due to service delay_jFor VM_iPenalty of payment, f_j(t_i)＝st_ij·w_i·t_i，st_ijRepresenting a unit time delay Cloudlet_jFor VM_iPenalty factor for payment, w_iRepresenting a VM_iPriority of, t_iRepresenting a VM_iWaiting time of request, a_ikIs a VM_iA unit utility constant at the time of requesting the resource in the k-th dimension is obtained,representing a VM_iThe requested Cloudlet multidimensional resource vector, k refers to the kth dimension, d represents the dimension of the Cloudlet multidimensional resource, g (t)_i) Representing a VM_iLost utility because of waiting for a response, g (t)_i)＝at_i·w_i·t_iWherein at_iIs a VM_iA constant of the unit gain of spent;

a k-dimension initial bid vector for the ith VM for the jth Cloudlet multi-dimensional resource;is a cloddlet_jAs a VM_iBasic pricing of kth dimension unit resource of the service is provided;

and step 3: marking the Cloudlet with the VM utility larger than 0 as a candidate Cloudlet of the VM, putting the candidate Cloudlet into a candidate Cloudlet set, if the candidate Cloudlet set is empty, not sending a resource request of the VM, applying the resource request to a local execution of the mobile terminal, if the candidate Cloudlet set is not empty, selecting an optimal Cloudlet from optional cloudlets according to the VM utility value, wherein the optimal Cloudlet is the Cloudlet which enables the VM to generate the maximum effect value, and sending the resource request to the optimal Cloudlet, wherein the resource request comprises the price to be paid to the optimal Cloudlet;

and 4, step 4: receive VM_iResource request of_jFirstly, whether the residual resource quantity of the self meets the VM or not is confirmed_iIf not, rejecting the VM_iIf satisfied, the Cloudlet_jCalculating the utility brought by a group of VM sets according to a utility function formulaThe utility function formula is as follows:

$u_j^{t,load}(S_j,{\stackrel{\&RightArrow;}{p}}_j)=u_j^t(S_j,{\stackrel{\&RightArrow;}{p}}_j)\&CenterDot;f_{S_j,j}^{index}$

wherein,

$u_j^t\left(S_j,{\stackrel{\&RightArrow;}{p}}_j\right)=\underset{{\stackrel{\&RightArrow;}{v}}_i\&Element;S_j}{\&Sigma;}\left(\underset{1\&le;k\&le;d}{\&Sigma;}{\stackrel{\&RightArrow;}{p}}_{ij}\&lsqb;k\&rsqb;\&CenterDot;{\stackrel{\&RightArrow;}{v}}_i\&lsqb;k\&rsqb;-\underset{1\&le;k\&le;d}{\&Sigma;}{\stackrel{\&RightArrow;}{\mathrm{\&sigma;}}}_{ij}\&lsqb;k\&rsqb;\&CenterDot;{\stackrel{\&RightArrow;}{v}}_i\&lsqb;k\&rsqb;-f_j\left(t_i\right)+p\left(t_i\right)\right)$

$f_{S_j,j}^{index}=\frac{{\left(\underset{1\&le;k\&le;d}{\&Sigma;}\left(\underset{{\stackrel{\&RightArrow;}{v}}_i\&Element;S_j}{\&Sigma;}{\stackrel{\&RightArrow;}{v}}_i\&lsqb;k\&rsqb;\right)\right)}^2}{d\&CenterDot;\underset{1\&le;k\&le;d}{\&Sigma;}{\left(\underset{{\stackrel{\&RightArrow;}{v}}_i\&Element;S_j}{\&Sigma;}{\stackrel{\&RightArrow;}{v}}_i\&lsqb;k\&rsqb;\right)}^2}$

p(t_i)＝bt_i·w_i·t_i

represents a Cloudlet_jServing a set of VM sets S_jThe obtained effect, S_jIs a Cloudlet_jA set of VMs to be serviced,represents a Cloudlet_jService VM set S_jUtility discounts due to unbalanced utilization of multidimensional resources, p (t)_i) Representing bilateral market because of Cloudlet_jService VM_iPaying to Cloudlet_jReward of, bt_iIs a constant of the unit excitation utility gain;

and 5: each Cloudlet in a mobile cloud computing system_jSelecting a subset S of VMs to provide a service among all requesting VMs based on the Cloudlet utility value_jAnd refuse other VM, after VM is chosen by Cloudlet, correspondent mobile terminal device unload its correspondent application to the Cloudlet to carry out;

step 6: the VM rejected by the corresponding Cloudlet in the step 5 will re-initiate the resource request, and when the resource request is re-initiated, the VM will increase the bid of rejecting its Cloudlet by one margin based on the price in the step 3I.e. if the VM_iIs Cloudlet_jIf rejected, the VM_iFor Cloudlet_jIs updated toWhile bids for other cloudlets maintain the price of step 3;

and 7: and repeating the steps 2 to 6 until no VM resource request message is sent, at this time, matching from the VM to the Cloudlet is completed, all the VMs successfully matched can obtain the multidimensional resource of the Cloudlet, the application corresponding to the mobile terminal equipment is unloaded to the Cloudlet for execution, and finally the execution result is fed back to the mobile terminal equipment.

2. The bilateral market-based method for pricing multidimensional resources in a mobile cloud computing environment according to claim 1, wherein in the step 4, the utility discount is a real number in an interval range of [0,1 ].