CN111045827A - Time-validity task scheduling method based on resource sharing in cloud and fog environment - Google Patents

Abstract

The invention relates to a task scheduling method based on the time validity of resource sharing in a cloud and fog environment. A contract-based resource sharing mechanism is established through a sealed bidding bilateral auction under a specific time slice, and resources are allocated according to the resource sharing mechanism, which specifically includes the following steps : Step S1: The fog cluster participates in the resource auction with a rented resource price and a rented resource price; Step S2: Determine the optimal bidding strategy according to the resources of other fog clusters and the rented-in and rented prices; Step S3: According to the optimal bidding The strategy participates in the auction, and establishes a contract with the corresponding fog cluster according to the auction result to form a resource sharing mechanism; Step S4: Select the key fog node under the resource sharing mechanism; Step S5: The fog key node completes the fog function through the spectral clustering method Domain division, task scheduling between different fog functional domains. Compared with the prior art, the present invention has the advantages of making full use of fog layer resources, reducing cloud workload, and reducing task response time.

Description

Time-effective task scheduling method based on resource sharing in cloud and fog environment

technical field

The invention relates to the field of computer edge computing, in particular to a time-effective task scheduling method based on resource sharing in a cloud and fog environment.

Background technique

Edge computing (fog computing) is generated with the rapid development and wide application of the Internet of Everything, the continuous expansion of data scale and the increasing demand for data processing and computing. Edge computing makes everything smarter and supports the construction of a robust edge application ecosystem. Edge computing is a supplement and extension to cloud computing, providing a better computing platform for mobile computing, Internet of Things, etc. Edge computing requires the powerful computing power of cloud computing centers and the support of massive storage. Cloud computing also requires edge devices to process massive data and private data in edge computing, so as to meet real-time, privacy protection and energy reduction requirements.

Based on the characteristics that cloud computing is farther away from users, and fog/edge computing is closer to users, many existing technologies are about how to migrate the application requests of the IoT layer to the fog or cloud for execution, so as to minimize application tasks. The time is either to minimize the energy consumption of the application request during execution, or to consider the optimization of the two indicators at the same time. There are also some technologies about the impact of the user's mobility (switching of geographic locations) on the completion of application requests. For example, if the user requests to download video resources, if the user is constantly moving, it will have a great impact on the performance of video downloads. However, the current technologies are all for the scheduling of fog resources in a certain area/scope, and do not consider the sharing of fog resources in different areas (the fog resources of a cell or city can be called a fog cluster). Although fog computing can ensure faster task response time with the advantages of physical distance and closer network distance, its resources are relatively limited. Therefore, how to make full use of the resources of the fog layer while reducing the response time of the task is a key issue.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a time-effective task scheduling method based on resource sharing in cloud and fog environment in order to overcome the defects of insufficient utilization of fog layer resources and long task response time in the prior art.

The object of the present invention can be realized through the following technical solutions:

A task scheduling method based on the time validity of resource sharing in a cloud and fog environment, establishes a contract-based resource sharing mechanism between fog clusters through a sealed bidding bilateral auction in a specific time slice, and performs function-based resource sharing according to the resource sharing mechanism. Resource allocation for domain construction, including the following steps:

Step S1: The fog cluster participates in the fog cluster resource auction at a rented resource price and a rented resource price according to its own local resources;

Step S2: the fog cluster determines the optimal bidding strategy according to the resources of other fog clusters and the rented resource price and the rented resource price;

Step S3: the fog cluster participates in the auction according to the optimal bidding strategy, and establishes a contract with other corresponding fog clusters according to the auction result to form the resource sharing mechanism;

Step S4: under the resource sharing mechanism formed in step S3, select key fog nodes;

Step S5: The fog key nodes dynamically and periodically cluster the remaining fog nodes through the spectral clustering method to complete the division of fog functional domains, and perform task scheduling among different fog functional domains.

具体为：The benefits obtained by the fog cluster by performing tasks on the resources leased in the contract when the local resources are insufficient

Specifically:

为合约的最终租进资源价格，τ为时间片，k为资源类型，i为雾簇，ρi为使用单位资源的价格，λ_i(τ)为时间片τ中雾簇i的工作负载，C_i(τ)为雾簇i在时间片τ中的资源量，V_k为雾簇i在时间片τ中所包含的k类型资源量。Among them, Res is a function of estimating its corresponding resource usage according to the load,

is the final rented resource price of the contract, τ is the time slice, k is the resource type, i is the fog cluster, ρi is the price of the unit resource used, λ _i (τ) is the workload of the fog cluster i in the time slice τ, C _i (τ) is the resource amount of the fog cluster i in the time slice τ, and V _k is the k-type resource amount included in the time slice τ of the fog cluster i.

具体为：The benefits obtained by the fog cluster by allocating part of the load to resources on other fog clusters when the running cost of local resources is greater

Specifically:

表示雾簇i中运行和管理类型为k的资源的开销。in,

represents the cost of running and managing a resource of type k in fog cluster i.

The rent-in optimal bidding strategy of the fog cluster is as follows:

为租进最优竞价策略。in,

It is the optimal bidding strategy for renting in.

具体为：When the fog cluster has surplus local resources, the income obtained by leasing resources to other fog clusters

Specifically:

为合约的最终租出资源价格。in,

is the final leased resource price of the contract.

具体为：The optimal bidding strategy for the rental of the fog cluster

Specifically:

where Null represents an empty bid, M _i (τ) is a list of fog nodes, and D _k represents a resource of type k.

The information of the contract includes fog clusters of rented resources, fog clusters of rented resources, rental price, rental price, corresponding time slice, and a list of fog nodes covered in the contract.

The process of selecting key fog nodes includes calculating the intermediate centrality, computing performance, and communication delay to the terminal node of the Internet of Things of each fog node in the fog cluster, performing non-dominant sorting according to the calculation results, and selecting the fog nodes. key node.

The calculation formula of the intermediate centrality is specifically:

Among them, g(n) represents the intermediate centrality of vertex n, σ _sd represents the total number of shortest paths from vertex s to vertex d, σ _sd (n) represents the shortest path from vertex s to vertex d passing through vertex n number of paths.

The grouping criteria of the spectral clustering method are based on the available computing and memory resources of the available fog devices.

Compared with the prior art, the present invention has the following beneficial effects:

1. By establishing a contract-based resource sharing mechanism between fog clusters, the present invention performs fog functional domain division and resource allocation under the condition of fog cluster resource sharing, realizes effective task scheduling, makes full use of fog layer resources, and makes more The tasks can be executed on the fog end, reducing the pressure on the core network between users and the cloud, reducing the workload of the cloud, and reducing the response time of tasks.

2. The present invention uses the centrality method to select the key nodes of the fog. The higher the centrality value of a vertex usually means, the vertex can reach other vertices with the shortest possible delay, and it also means that the vertex is in many shortest routes. On the path, improve the efficiency and accuracy of selecting key fog nodes.

3. The present invention uses the spectral clustering method when dividing the fog function domain, and uses the graph similarity to find the similarity between different data points, which is suitable for traversing the network graph in the fog environment.

Description of drawings

Fig. 1 is the schematic flow chart of the present invention;

2 is a schematic diagram of the fog end contract auction mechanism of the present invention;

FIG. 3 is a schematic diagram of resource sharing of cloud and fog environment according to the present invention

4 is a schematic flowchart of a fog cluster resource sharing mechanism of the present invention;

5 is a schematic flowchart of selecting a key fog node according to the present invention;

FIG. 6 is a schematic flowchart of the division of fog function domains according to the present invention.

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments. This embodiment is implemented on the premise of the technical solution of the present invention, and provides a detailed implementation manner and a specific operation process, but the protection scope of the present invention is not limited to the following embodiments.

As shown in Figure 1, a task scheduling method based on the time validity of resource sharing in the cloud environment, establishes a contract-based resource sharing mechanism between fog clusters through a sealed bidding bilateral auction in a specific time slice, and according to the resource sharing Mechanism for resource allocation based on functional domain construction, which includes the following steps:

Step S1: The fog cluster participates in the fog cluster resource auction at a rented resource price and a rented resource price according to its own local resources;

Step S2: The fog cluster determines the optimal bidding strategy according to the resources of other fog clusters and the rented-in resource price and the rented-out resource price;

Step S3: The fog cluster participates in the auction according to the optimal bidding strategy, and establishes a contract with other corresponding fog clusters according to the auction result to form a resource sharing mechanism;

Step S4: under the resource sharing mechanism formed in step S3, select key fog nodes;

Step S5: The key fog nodes dynamically and periodically cluster the remaining fog nodes through the spectral clustering method to complete the division of fog functional domains, and perform task scheduling among different fog functional domains.

As shown in Figure 2 and Figure 3, the system model of the contract-based fog cluster resource sharing in the cloud environment contains three logical layers. The first logical layer is the cloud layer, which is mainly responsible for global resource scheduling and intelligent decision-making. It acts as a third-party auctioneer when establishing a resource sharing mechanism, and is also responsible for the selection of key fog nodes within each fog cluster, and also performs part of the process. User request; the second logical layer is the fog end layer, which contains different fog cluster resources corresponding to several different areas. Each fog cluster is composed of multiple interconnected fog nodes. The resources in the fog cluster are mainly responsible for intelligent perception. , intelligent computing, data analysis, real-time control, process optimization and the construction of different functional domains, resources will be shared between fog clusters to achieve full utilization of resources and minimize task response time. It will accept and process task requests sent from the underlying terminal devices. There may be multiple key fog nodes in each fog cluster. The cloud layer and the fog layer need to carry out data collaboration, business management collaboration, intelligent collaboration and application management collaboration to achieve performance optimization; the bottom layer is the terminal device layer, and the terminal devices at this layer will send data to the upper fog end layer or cloud layer. The task handles requests and accepts device control information sent from the fog end layer or cloud layer.

As shown in Figure 4, the specific workflow of the contract-based resource sharing mechanism between fog clusters includes the input resource type k, time slice t, the number of fog clusters n, and the purchase price B ^q (t) of each fog cluster for type k resources and selling price S ^q (t), output the buyer set Bs and seller set Ss of resource type k and the corresponding rental price pr. Under a certain time slice, the contract establishment process for a resource of type k includes sorting the buying price B ^q (t) and the selling price S ^q (t) in descending and ascending order, respectively, to obtain arrays B and S, and perform Initialize to obtain B(0) and S(0) and the counter v of the array. If S(0)<B(0), traverse the arrays B and S to find the closest rental price and rental price to calculate the rent, otherwise directly Calculate the rent, rent m=[B(v+1)+S(v+1)]/2; if the rent m is not greater than B(v) and not less than S(v), the bid will be the fog cluster of the corresponding price Become a seller and a buyer, and establish a contract with a rent of m, otherwise the fog cluster that bids for the corresponding price will become a seller and a buyer, and establish a contract with a rent of S(v). The above four steps are continuously iterated when the time slice is from 1 to T, and are used to determine the auction result of each type k resource.

和卖价

进行竞标，第三方则会在特定的时间片下考虑所有的类型k资源的买价B^k(b₁,b₂,...,b_N)和卖价S^k(s₁,s₂,...,s_N)，决定最后的定价、买家和卖家。拍卖的结果记为

和

若x_bi＝1，表示bi是类型k资源的一个买家，若x_sj＝1，表示sj是类型k资源的一个卖家。商品拍卖的最终买价和卖价确定为

和

后，合约就会在最终的买家和卖家之间建立。In the resource sharing mechanism, each fog cluster will buy a price according to its own bidding strategy

and selling price

For bidding, the third party will consider the bid price B ^k (b ₁ ,b ₂ ,...,b _N ) and the ask price S ^k (s ₁ ,s ₂ , ...,s _N ), determine the final pricing, buyers and sellers. The result of the auction is recorded as

and

If x _bi =1, it means that bi is a buyer of type k resources, and if x _sj =1, it means that sj is a seller of type k resources. The final bid and ask prices of the commodity auction are determined as

and

After that, the contract is established between the ultimate buyer and seller.

具体为：The benefits obtained by the fog cluster by performing tasks on the resources leased in the contract when the local resources are insufficient

Specifically:

为合约的最终租进资源价格，τ为时间片，k为资源类型，i为雾簇，ρi为使用单位资源的价格，λ_i(τ)为时间片τ中雾簇i的工作负载，C_i(τ)为雾簇i在时间片τ中的资源量，V_k为雾簇i在时间片τ中所包含的k类型资源量。Among them, Res is a function of estimating its corresponding resource usage according to the load,

is the final rented resource price of the contract, τ is the time slice, k is the resource type, i is the fog cluster, ρi is the price of the unit resource used, λ _i (τ) is the workload of the fog cluster i in the time slice τ, C _i (τ) is the resource amount of the fog cluster i in the time slice τ, and V _k is the k-type resource amount included in the time slice τ of the fog cluster i.

具体为：The benefits of distributing part of the load to resources on other fog clusters when the running cost of local resources is greater for fog clusters

Specifically:

表示雾簇i中运行和管理类型为k的资源的开销。in,

represents the cost of running and managing a resource of type k in fog cluster i.

The rent-in optimal bidding strategy of fog cluster is as follows:

为租进最优竞价策略。in,

It is the optimal bidding strategy for renting in.

具体为：When the fog cluster has surplus local resources, the income obtained by renting resources to other fog clusters

Specifically:

为合约的最终租出资源价格。in,

is the final leased resource price of the contract.

具体为：Optimal Bidding Strategy for Leasing in Fog Cluster

Specifically:

where Null represents an empty bid, M _i (τ) is a list of fog nodes, and D _k represents a resource of type k.

The information of the contract includes fog clusters of rented resources, fog clusters of rented resources, rental price, rental price, corresponding time slice, and a list of fog nodes covered in the contract. After the contract is established, each fog cluster updates the list of fog nodes covered by itself, that is, removes the fog nodes rented out in the auction and adds the rented fog nodes.

When selecting key fog nodes, the centrality method in graph theory is used to evaluate the centrality of fog computing nodes in each fog cluster. In the research field of graph theory, betweenness centrality is used to measure the centrality of a node in a graph, mainly about the number of shortest paths passing through the node. There is at least one shortest path between each pair of vertices in a connected unweighted graph, so that the number of edges traversed by the route can be minimized. Correspondingly, for a weighted graph, the betweenness centrality uses the sum of the weights on the edges to find the shortest path. A higher centrality value of a vertex usually means that the vertex can reach other vertices with the shortest possible delay, and also means that the vertex is on the path of many shortest routes. After the betweenness centrality evaluation is completed, the fog nodes are sorted non-dominantly based on NSGA-II, and the fog key nodes are selected according to the results considering the betweenness centrality, computing performance, and communication delay to the terminal node of each fog node.

The formula for calculating betweenness centrality is as follows:

Among them, g(n) represents the intermediate centrality of vertex n, σ _sd represents the total number of shortest paths from vertex s to vertex d, σ _sd (n) represents the shortest path from vertex s to vertex d passing through vertex n number of paths.

As shown in Figure 5, the specific process of selecting key fog nodes includes inputting the fog node set P={fn ₁ ,fn ₂ ,...,fn _n }, the CPU and storage M and other resource information on the fog nodes, and the connection between the fog nodes. Topology Gr, and then traverse and calculate the median centrality value of all fog nodes in the fog node set. Based on NSGA-II, the fog nodes are sorted non-dominantly. At the same time, the computing performance of each fog node and the communication delay to the terminal node are considered. The fog key node is output, and the fog key node set {fn _x } of the current fog cluster is output, where x is some value between 1 and n.

There will be one or more key fog nodes in each fog cluster, and each key fog node will dynamically and periodically cluster the remaining fog nodes, that is, divide the functional domain, and divide the fog device nodes into different classes. Used for the needs of different types of applications, such as compute or memory or network intensive applications. In order to effectively construct the functional domain in the fog cluster, the spectral clustering method in the unsupervised clustering technology is adopted. Spectral clustering methods are suitable for finding similarities between different data points by using the concept of graph similarity, and are suitable for traversal of network graphs in foggy environments. Commonly used similarity measures in spectral clustering are based on Euclidean distance and Gaussian kernel. After dimensionality reduction, spectral clustering uses simple clustering methods such as k-means to group data points. The clustering process is carried out in a continuous adaptive manner, mainly to respond to changes in the environment in time, such as the removal or addition of fog equipment in the fog cluster.

As shown in Figure 6, the specific process of fog functional domain division includes the following steps:

Step S501: Input the number N of nodes in the fog cluster, the computing capability C corresponding to each fog node and resources such as storage M, the type of kNN for neighbor classification, the Gaussian function G used, and the update step size s;

Step S502: Calculate the similarity between the fog nodes according to the resource information of the fog nodes, and obtain a degree matrix D and a similarity matrix W related to the fog nodes;

Step S503: Calculate the Laplacian matrix L=D-W according to the degree matrix D and the similarity matrix W, and standardize L;

Step S504: Calculate the eigenvectors of the first k minimum eigenvalues in L, form the k eigenvectors into an m*k-dimensional matrix, and convert them into a matrix Q according to standardization;

Step S505: take each row of m rows in the matrix Q as a k-dimensional sample, and perform k-means clustering;

Step S506: Output the sets S1,..., _Sk of each type of fog nodes in the current fog cluster.

The clustering process needs to group logically similar fog devices, so the key fog nodes in each fog cluster will perform an effective clustering method, such as spectral clustering, considering the available computing and memory of the available fog devices resources, etc. If the purpose of a fog control node is to create a computationally optimized functional domain, the corresponding spectral clustering will identify all similar fog devices that have sufficient processing resources. Each key fog node creates its own functional domain class, and a fog node with sufficient resources can belong to multiple functional domain classes.

In addition, it should be noted that the names of the specific embodiments described in this specification may be different, and the above content described in this specification is only an example to illustrate the structure of the present invention. All minor changes or simple changes made according to the structure, features and principles of the present invention are included in the protection scope of the present invention. Those skilled in the art to which the present invention pertains can make various modifications or additions to the specific examples described or adopt similar methods, as long as they do not deviate from the structure of the present invention or go beyond the scope defined by the claims, all It belongs to the protection scope of the present invention.

Claims (10)

1. A task scheduling method based on the time validity of resource sharing in a cloud and fog environment is characterized in that, a contract-based resource sharing mechanism between fog clusters is established by means of a sealed bidding bilateral auction under a specific time slice, and according to the described method; The resource sharing mechanism performs resource allocation based on functional domains, which specifically includes the following steps: Step S1: The fog cluster participates in the fog cluster resource auction at a rented resource price and a rented resource price according to its own local resources; Step S2: the fog cluster determines the optimal bidding strategy according to the resources of other fog clusters and the rented resource price and the rented resource price; Step S3: the fog cluster participates in the auction according to the optimal bidding strategy, and establishes a contract with other corresponding fog clusters according to the auction result to form the resource sharing mechanism; Step S4: under the resource sharing mechanism formed in step S3, select key fog nodes; Step S5: The fog key nodes dynamically and periodically cluster the remaining fog nodes through the spectral clustering method to complete the division of fog functional domains, and perform task scheduling among different fog functional domains. 2. The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 1, is characterized in that, when the local resources are insufficient in the fog cluster, by using the resources leased in the contract. Earnings from performing tasks

Specifically:

Among them, Res is a function of estimating its corresponding resource usage according to the load,

is the final rented resource price of the contract, τ is the time slice, k is the resource type, i is the fog cluster, ρ _i is the price of the unit resource used, λ _i (τ) is the workload of the fog cluster i in the time slice τ, C _i (τ) is the resource amount of the fog cluster i in the time slice τ, and V _k is the k-type resource amount included in the time slice τ of the fog cluster i. 3. The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 2, wherein the fog cluster allocates part of the load to other resources when the running cost of the local resources is larger. The benefits of resources on the fog cluster

Specifically:

in,

represents the cost of running and managing a resource of type k in fog cluster i. 4. The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 3, wherein the optimal bidding strategy for renting in the fog cluster is specifically:

in,

It is the optimal bidding strategy for renting in. 5. The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 1, wherein the fog cluster rents resources obtained from other fog clusters when there are surplus local resources. income

Specifically:

in,

is the final leased resource price of the contract. 6. The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 5, wherein the optimal bidding strategy for renting out the fog cluster

Specifically:

where Null represents an empty bid, M _i (τ) is a list of fog nodes, and D _k represents a resource of type k. 7. The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 1, wherein the information of the contract comprises fog clusters of rented resources, fog clusters of rented resources, rental Price, rent-in price, corresponding time slice, list of fog nodes covered in the contract. 8 . The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 1 , wherein the process of selecting key fog nodes comprises calculating the value of each fog node in the fog cluster. 9 . Betweenness centrality, computing performance, and communication delay to the terminal node of the Internet of Things, non-dominant sorting is performed according to the calculation result, and the key fog node is selected. 9. The task scheduling method based on the time validity of resource sharing in a cloud environment according to claim 8, wherein the calculation formula of the intermediate centrality is specifically:

Among them, g(n) represents the intermediate centrality of vertex n, σ _sd represents the total number of shortest paths from vertex s to vertex d, σ _sd (n) represents the shortest path from vertex s to vertex d passing through vertex n number of paths. 10 . The task scheduling method based on the time validity of resource sharing in a cloud and fog environment according to claim 1 , wherein the grouping criteria of the spectral clustering method are based on available computing and memory resources of available fog devices. 11 .

Images