CN112099932A - Optimal pricing method and system for soft-hard deadline task offloading in edge computing - Google Patents

Abstract

The invention discloses an optimal pricing method and system for task offloading with soft-hard deadlines in edge computing. The method includes the following steps: designing an edge-cloud computing system model, and dividing tasks in the system into high priority and low priority Task; establish a queue model, and establish a queue model for edge servers and cloud servers respectively; the queue model for edge servers is established as M|M|1 queue, and the queue model for cloud servers is established as M|M|∞ queue; and calculate the hard cutoff Response time of deadline tasks and soft deadline tasks in edge server and cloud server; calculate the cost of edge server and cloud server respectively; calculate the benefit of edge server and cloud server separately; use Wardrop to model the cost of the system; use Nash Equilibrium models system returns; assesses the efficiency of pricing strategies. The present invention can find a pricing strategy that balances cost minimization and benefit maximization.

Description

Optimal pricing method and system for task offloading with soft-hard deadlines in edge computing

technical field

The invention relates to an optimal pricing method and system for unloading soft-hard deadline tasks in edge computing, and belongs to the technical field of edge computing.

Background technique

Edge computing originated in the field of media, and refers to the use of an open platform that integrates network, computing, storage, and application core capabilities on the side close to the source of objects or data to provide the most recent services nearby. By extending computing and storage resources to resource-constrained end users, edge computing greatly eliminates the transmission latency bottleneck between end users and remote cloud data centers. However, compared with resource-rich cloud servers, edge servers are greatly limited in terms of computing and resource storage. Therefore, task processing and computing allocation of resources have always been challenging problems in edge computing systems.

In edge computing, according to the timeliness constraints, delay-sensitive tasks can be divided into hard deadline tasks and soft deadline tasks. In general-purpose computing environments, many schedulers have been proposed one after another. These schedulers evolve based on the number of tasks that miss their deadlines under various time and resource constraints. By taking the similarity and timely characteristics of tasks, how to schedule these tasks in limited computing resources is an interesting research topic in edge computing.

A scheduling strategy is designed in Reference 1, that is, by choosing the locations that are most suitable for tasks with hard and soft deadlines. But their hard deadline tasks require very tight deadlines to execute in embedded systems. The remaining computing resources of edge nodes are used to perform tasks with soft deadlines, causing these tasks to suffer maximum delays beyond their deadlines. While Reference 1 lays a solid foundation for deadline-based task offloading, there is little interaction between edge and cloud. Furthermore, they do not consider computational cost.

Reference 2 discusses the decentralized resource allocation of tasks according to the requirements of tasks and the computational model of the network, and their main purpose is to reduce the overhead of the system. Reference 3 studies from the perspective of pricing models and resource allocation in microeconomic theory, aiming to optimize the limited resources of terminal device tasks in edge computing within a limited budget.

To maximize the social welfare of the network, Reference 4 proposes a platform in a sharing economy based business model that can be used to manage network resources in real time. The platform maximizes profits without relying on any user decisions about where to place and process tasks.

To sum up, the current literature mainly designs pricing models, and designs optimal pricing mechanisms for specific network scenarios. These pricing models do not explicitly consider deadlines, especially hard deadline and soft deadline tasks in edge computing. Therefore, it is necessary to solve the following technical needs of the existing technology: how to set prices for different deadline tasks, and maximize edge cloud revenue by utilizing its own computing and transmission capabilities.

References are as follows:

[1] N. Auluck, A. Azim, and K. Fizza, “Improving the schedulability of real-time tasks using fog computing,” IEEE Transactions on ServicesComputing, pp. 1–14, Sept. 2019.

[2] Q. He, G. Cui, X. Zhang, F. Chen, S. Deng, H. Jin, Y. Li, and Y. Yang, “A game-theoretical approach for user allocation in edge computing environment, ”IEEETrans.Parallel Distrib.Syst.,vol.31,no.3,pp.515–529,Mar.2020.

[3] J. Liu, S. Guo, K. Liu, and L. Feng, “Resource provision and allocation based on microeconomic theory in mobile edge computing,” IEEE Trans. Serv. Comput., pp. 1–14, June 2020,

[4] M.Siew, D.W.H.Cai, L.Li, and T.Q.S.Quek, “Dynamic pricing for resource-quota sharing in multi-access edge computing,” IEEETrans.Netw.Sci.Eng., pp.1–13, June 2020 .

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to overcome the defects of the prior art, and to provide an optimal pricing method and system for offloading soft-hard deadline tasks in edge computing, so that the edge-cloud computing system can find an equilibrium cost minimization and Profit-maximizing pricing strategies.

The present invention specifically adopts the following technical solutions: an optimal pricing method for task offloading with soft-hard deadlines in edge computing, comprising the following steps:

Step SS1: Design an edge-cloud computing system model, and divide tasks in the system into high-priority and low-priority tasks;

Step SS2: Establish a queue model, and establish a queue model for the edge server and the cloud server respectively; the queue model established for the edge server is M|M|1 queue, and the queue model for the cloud server is established as the M|M|∞ queue; The response time of deadline tasks and soft deadline tasks in edge servers and cloud servers;

Step SS3: Calculate the cost of the edge server and the cloud server respectively;

Step SS4: Calculate the revenue of the edge server and the cloud server respectively;

Step SS5: Use Wardrop to model the cost of the system;

Step SS6: Use Nash equilibrium to model system revenue;

Step SS7: Evaluate the efficiency of the pricing strategy.

As a preferred embodiment, the division of tasks in the system in step SS1 is based on the time limit of the task; high priority tasks usually require hard deadlines, while low priority tasks require soft deadlines, so the task It is also divided into hard deadline tasks and soft deadline tasks; assuming λ is the amount of tasks arriving:

λ= ^λH + ^λS

Among them, λ ^H is the number of hard deadline tasks, and λ ^S is the number of soft deadline tasks.

As a preferred embodiment, the step SS2 specifically includes:

和云服务器中硬截止期任务的数量

同理，软截止期任务的数量包含边缘服务器中软截止期任务的数量

和云服务器中软截止期任务的数量

则有：The number of hard deadline tasks contains the number of hard deadline tasks in the edge server

and the number of hard deadline tasks in the cloud server

Similarly, the number of soft deadline tasks includes the number of soft deadline tasks in the edge server

and the number of soft deadline tasks in the cloud server

Then there are:

The response times of the hard deadline tasks on the edge server and the cloud server are:

The response times of the soft deadline tasks on the edge server and the cloud server are:

Among them, μ _E and μ _C are respectively the service rate, that is, the number of tasks completed by the server in unit time.

As a preferred embodiment, the step SS3 specifically includes:

The cost of hard deadline tasks in edge servers is:

The soft deadline task cost in the edge server is:

where α is a parameter, which is used to balance the relationship between delay and cost, that is, the longer the task processing time, the higher the total cost; _PE is the cost of each task on the edge server;

The costs of hard deadline tasks and soft deadline tasks in the cloud server are as follows:

where d _t is the average transmission delay of transferring a single task from the edge server to the cloud server, and PC is the cost of each task on the cloud server _.

As a preferred embodiment, the step SS4 specifically includes:

The benefits of edge servers are:

The benefits of cloud servers are:

为边缘服务器中硬截止期任务的数量，

为云服务器中硬截止期任务的数量；

为边缘服务器中软截止期任务的数量，

为云服务器中软截止期任务的数量。

is the number of hard deadline tasks in the edge server,

is the number of hard deadline tasks in the cloud server;

is the number of soft deadline tasks in the edge server,

is the number of soft deadline tasks in the cloud server.

As a preferred embodiment, the step SS5 specifically includes:

The total cost of tasks with soft and hard deadlines in equilibrium is equal, namely:

The proportion of soft deadline tasks to total tasks plays an important role in the total computing cost of cloud servers and edge servers, so it is written as follows:

where φ is the offset of the deadline.

As a preferred embodiment, the step SS6 specifically includes:

和

分别为边缘服务器和云服务器的纳什价格，其中

定义如下：definition

and

are the Nash prices of edge servers and cloud servers, respectively, where

Defined as follows:

定义如下：Similarly,

Defined as follows:

γ＝2(λ-2μ_E)²，

in

γ=2(λ-2μ _E ) ² ,

As a preferred embodiment, the step SS7 specifically includes:

In order to evaluate the efficiency of the pricing strategy, the price-of-anarcy strategy POA is introduced; the social welfare function S is defined,

where x and y are hard deadline and weight deadline tasks, respectively;

To minimize the social welfare function S, the above formula can be rewritten as follows:

where T ^* is the total delay experienced in the network in the equilibrium state.

As a preferred embodiment, the step SS7 further includes: POA is calculated according to T ^* and S _min : POA=T ⁸ /S _min .

The present invention also proposes an optimal pricing system for task offloading with soft-hard deadlines in edge computing, including:

The task division module is used to perform: design the edge-cloud computing system model, and divide the tasks in the system into high-priority and low-priority tasks;

The queue model generation module is used to execute: establish a queue model, and establish a queue model for the edge server and cloud server respectively; the queue model established for the edge server is M|M|1 queue, and the queue model established for the cloud server is M|M| ∞ queue; and calculate the response time of hard deadline tasks and soft deadline tasks in edge servers and cloud servers;

The server cost calculation module is used to perform: calculate the cost of the edge server and the cloud server separately;

The server revenue calculation module is used to perform: separately calculate the revenue of the edge server and the cloud server;

System cost modeling module to perform: use Wardrop to model the cost of the system;

System benefit modeling module to perform: Modeling system benefits using Nash equilibrium;

Efficiency Evaluation Module for Execution: Evaluate the efficiency of pricing strategies.

Beneficial effects achieved by the present invention: The present invention proposes an optimal pricing method for task offloading with soft-hard deadlines in edge computing. Determine the equilibrium price of edge servers and cloud servers by designing a pricing model, first build an edge-cloud server system, divide tasks with soft and hard deadlines, and then build edge server and cloud server queue models to determine the response time of soft and hard deadlines, Next, the cost and benefit functions of edge servers and cloud servers are designed. Finally, the Nash equilibrium and Wardrop equilibrium are used to model the cost and benefit of the system, so that the system can find a pricing strategy that balances cost minimization and revenue maximization.

Description of drawings

1 is a schematic diagram of an edge-cloud computing system model of the present invention;

2 is a schematic diagram of a hard deadline task and a soft deadline task of the present invention;

FIG. 3 is a schematic diagram of the soft and hard deadline tasks of the present invention being processed locally in the edge server or offloaded to the cloud server for processing.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings. The following examples are only used to illustrate the technical solutions of the present invention more clearly, and cannot be used to limit the protection scope of the present invention.

Embodiment 1: As shown in FIG. 1 , FIG. 2 and FIG. 3 , an optimal pricing method for task offloading with hard-soft deadlines of edge computing of the present invention includes the following seven steps.

1) Design the edge-cloud computing system model, as shown in Figure 1, and divide the tasks in the system into high-priority and low-priority tasks.

Assuming that the edge-cloud server system of the present invention is a time slot system, it can be divided into high-priority tasks and low-priority tasks according to task priorities. It can also be divided into hard deadline tasks and soft deadline tasks according to different time requirements of tasks. Among them, high-priority tasks correspond to hard deadline tasks, which are used to ensure the correct operation of the system. Soft deadline tasks can tolerate longer delays than hard deadline tasks. As shown in Figure 2, the soft deadline task has an extra bias in latency than the hard deadline task. Suppose λ is the amount of tasks reached by the system, which consists of the amount of hard deadline tasks and the amount of soft deadline tasks:

λ= ^λH + ^λS

Among them, λ ^H is the number of hard deadline tasks, and λ ^S is the number of soft deadline tasks.

2) Establish a queue model, respectively establish a queue model for the edge server and the cloud server, and calculate the response time of the hard and soft deadline tasks in the edge server and the cloud server respectively.

和云服务器中硬截止期任务的数量组成

同理，软截止期任务的数量由边缘服务器中软截止期任务的数量

和云服务器中软截止期任务的数量组成

Without loss of generality, the present invention models edge servers as M|M|1 queues, and establishes queue models for cloud servers as M|M|∞ queues. Define μ _E and μ _C as the service rate, that is, the number of tasks completed by the server per unit time. The number of hard deadline tasks is determined by the number of hard deadline tasks in the edge server

and the number of hard deadline tasks in the cloud server

Similarly, the number of soft deadline tasks is determined by the number of soft deadline tasks in the edge server.

and the number of soft deadline tasks in the cloud server

和

The response times of the hard deadline tasks on the edge server and the cloud server are respectively

and

和

The response times of soft deadline tasks on edge server and cloud server are respectively

and

3) Calculate the cost of edge server and cloud server separately:

3.1 Soft and Hard Deadline Task Costs in Edge Servers

In order to better balance the relationship between delay and cost, the present invention introduces a parameter α, that is, the longer the task processing time, the higher the total cost.

The total cost of a hard deadline task is calculated as follows:

where _PE is the cost required by the edge server to process a task.

The total cost of a soft deadline task is calculated as follows:

3.2 Task costs of soft and hard deadlines in cloud servers

The total cost of a hard deadline task is calculated as follows:

The total cost of a soft deadline task is calculated as follows:

where d _t is the average transmission delay of transferring a single task from the edge server to the cloud server, and PC is the cost of each task on the cloud server _.

4) Benefits of edge servers and cloud servers:

The edge server revenue _UE is defined as follows:

Cloud server revenue U _C is defined as follows:

5) Use Wardrop balance to model the total cost of the system:

The total cost of tasks with soft and hard deadlines in the Wardrop equilibrium is equal i.e.

The proportion of soft deadline tasks to total tasks plays an important role in the total computing cost of cloud servers and edge servers, so it can be written as follows:

where φ is the offset of the deadline.

6) Use Nash Equilibrium to model the overall return of the system:

和

分别为边缘服务器和云服务器的纳什价格，其中

定义如下Nash equilibrium is used to model the total benefit of the system, and strive to get the maximum benefit for the system. we define

and

are the Nash prices of edge servers and cloud servers, respectively, where

Defined as follows

γ＝2(λ-2μ_E)²,

和

同理，

定义如下：in

γ=2(λ-2μ _E ) ² ,

and

Similarly,

Defined as follows:

7) Evaluate the efficiency of the pricing strategy:

In order to better evaluate the efficiency of the pricing strategy, the present invention introduces the price-of-anarcy (POA) strategy. The social welfare function S is defined,

where x and y are hard deadline and soft deadline tasks, respectively.

In order to minimize the social welfare function S, the above formula is rewritten as follows:

Further, the total delay experienced in the network in the equilibrium state is defined as follows:

Finally, the POA policy can be calculated from T ^* and _Smin : POA=T ^* / _Smin .

Embodiment 2: The present invention also proposes an optimal pricing system for task offloading with soft-hard deadlines in edge computing, including:

The task division module is used to perform: design the edge-cloud computing system model, and divide the tasks in the system into high-priority and low-priority tasks;

The queue model generation module is used to execute: establish a queue model, and establish a queue model for the edge server and cloud server respectively; the queue model established for the edge server is M|M|1 queue, and the queue model established for the cloud server is M|M| ∞ queue; and calculate the response time of hard deadline tasks and soft deadline tasks in edge servers and cloud servers;

The server cost calculation module is used to perform: calculate the cost of the edge server and the cloud server separately;

The server revenue calculation module is used to perform: separately calculate the revenue of the edge server and the cloud server;

System cost modeling module to perform: use Wardrop to model the cost of the system;

System benefit modeling module to perform: Modeling system benefits using Nash equilibrium;

Efficiency Evaluation Module for Execution: Evaluate the efficiency of pricing strategies.

As will be appreciated by those skilled in the art, the embodiments of the present application may be provided as a method, a system, or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the present application. It will be understood that each process and/or block in the flowchart illustrations and/or block diagrams, and combinations of processes and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to the processor of a general purpose computer, special purpose computer, embedded processor or other programmable data processing device to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing device produce Means for implementing the functions specified in a flow or flow of a flowchart and/or a block or blocks of a block diagram. These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions The apparatus implements the functions specified in the flow or flow of the flowcharts and/or the block or blocks of the block diagrams. These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in the flow or blocks of the flowcharts and/or the block or blocks of the block diagrams.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention and not to limit them. Although the present invention has been described in detail with reference to the above embodiments, those of ordinary skill in the art should understand that: the present invention can still be Modifications or equivalent replacements are made to the specific embodiments of the present invention, and any modifications or equivalent replacements that do not depart from the spirit and scope of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (10)

1. The optimal pricing method for soft-hard deadline task offloading in edge computing is characterized by comprising the following steps of:

step SS 1: designing an edge-cloud computing system, wherein the edge-cloud computing system comprises an edge server and a cloud server, and tasks entering the system are divided into high-priority tasks and low-priority tasks according to cut-off;

step SS 2: establishing a queue model, and respectively establishing the queue model for the edge server and the cloud server; the method comprises the following steps that a queue model is established for an edge server to be an M | M |1 queue, a queue model is established for a cloud server to be an M | M | ∞ queue, 1 represents that only 1 server exists, and infinity represents that an infinite server exists; calculating the response time of the hard deadline task and the soft deadline task in the edge server and the cloud server;

step SS 3: respectively calculating the cost of the edge server and the cost of the cloud server;

step SS 4: respectively calculating the profits of the edge server and the cloud server;

step SS 5: modeling the cost of the system using Wardrop;

step SS 6: modeling the system revenue by adopting Nash balance;

step SS 7: the efficiency of the pricing strategy is evaluated.

2. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 1, wherein the division of tasks in the system in step SS1 is based on time deadline of task; high priority tasks typically require a hard deadline and low priority tasks require a soft deadline, so the tasks are also divided into hard and soft deadline tasks; let λ be the amount of tasks reached:

λ＝λ^H+λ^S

wherein λ is^HFor the number of hard deadline tasks, λ^SIs the number of soft deadline tasks.

3. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 2, wherein the step SS2 specifically comprises:

the number of hard deadline tasks includes the number of hard deadline tasks in the edge server

And the number of hard deadline tasks in the cloud server

Similarly, the number of soft deadline tasks includes the number of soft deadline tasks in the edge server

And the number of soft deadline tasks in the cloud server

Then there are:

the response time of the hard deadline task on the edge server and the cloud server is respectively as follows:

the response time of the soft deadline task on the edge server and the cloud server is respectively as follows:

wherein, mu_EAnd mu_CThe normalized service rates of the edge server and the cloud server are respectively, that is, the number of tasks completed by the edge server and the cloud server in unit time.

4. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 3, wherein said step SS3 specifically comprises:

the cost of hard deadline tasks in edge servers is:

the soft deadline task cost in the edge server is:

where α is a parameter used to balance the relationship between delay and cost, i.e., the longer the task processing time, the higher the total cost; p_ECost for a single task on an edge server;

the costs of hard deadline tasks and soft deadline tasks in a cloud server are as follows:

wherein d is_tAverage transmission delay for transferring a single task from an edge server to a cloud server, P_CThe cost of a single task on the cloud server.

5. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 4, wherein the step SS4 specifically comprises:

the edge server gains are:

the yield of the cloud server is as follows:

for the number of hard deadline tasks in the edge server,

the number of hard deadline tasks in the cloud server;

for the number of soft deadline tasks in the edge server,

the number of soft deadline tasks in the cloud server.

6. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 5, wherein the step SS5 specifically comprises:

the total cost of the soft and hard deadline tasks in the balance is equal, namely:

the role played by the proportion of the total tasks in the cloud server and edge server computing the total cost based on the soft deadline tasks is therefore written as follows:

wherein,

representing the cost of the soft deadline task at the edge server,

representing the cost of the soft deadline task at the cloud server, alpha > 0 is a parameter for balancing the relation between the delay and the cost, and lambda_SDenotes the number of soft deadline tasks to arrive at the system, λ denotes the total number of tasks to arrive at the system, is the sum of the number of soft deadline tasks and the number of hard deadline tasks, μ_CRepresents the service rate, mu, of the cloud server_ERepresents the service rate of the edge server and phi is the offset of the expiration date.

7. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 6, wherein said step SS6 specifically comprises:

definition of

And

nash prices for edge servers and cloud servers, respectively, wherein

The definition is as follows:

in the same way, the method for preparing the composite material,

the definition is as follows:

wherein

γ＝2(λ-2μ_E)²，

The meaning of k.

8. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 7, wherein the step SS7 specifically comprises:

in order to evaluate the efficiency of the pricing strategy, a price-of-annular strategy POA is introduced; a social welfare function S is defined,

wherein x and y are hard deadline and right deadline tasks, respectively;

minimizing the social welfare function S, the above formula is rewritten as follows:

wherein, T^*The meaning of d is the total delay experienced in the network in equilibrium.

9. The optimal pricing method for soft-hard deadline task offloading in edge computing according to claim 8, wherein the step SS7 further comprises: POA according to T^*And S_minAnd (3) calculating: POA ═ T^*/S_min。

10. An optimal pricing system for soft-hard deadline task offloading in edge computing, comprising:

a task partitioning module to perform: designing an edge-cloud computing system model, and dividing tasks in the system into high-priority tasks and low-priority tasks;

a queue model generation module to perform: establishing a queue model, and respectively establishing the queue model for the edge server and the cloud server; the method comprises the following steps of establishing a queue model for an edge server as an M | M |1 queue, and establishing a queue model for a cloud server as an M | M | ∞ queue; calculating response time of the hard deadline task and the soft deadline task in the edge server and the cloud server;

a server cost calculation module to perform: respectively calculating the cost of the edge server and the cost of the cloud server;

a server revenue calculation module to perform: respectively calculating the profits of the edge server and the cloud server;

a system cost modeling module to perform: modeling the cost of the system using Wardrop;

a system revenue modeling module to perform: modeling the system revenue by adopting Nash balance;

an efficiency evaluation module to perform: the efficiency of the pricing strategy is evaluated.

Images