CN109548031B - An unbalanced edge cloud network access and resource allocation method - Google Patents

Abstract

The invention discloses an unbalanced edge cloud network access and resource allocation method, which belongs to the field of mobile cloud computing and mobile edge computing. The invention adopts a cyclic method. In each round of resource allocation cycle, the multi-user multi-task basis is the smallest. The optimal task offloading path is independently selected by the delay-energy-consumption-cost weighted sum criterion, and finally the task with the global minimum delay-energy consumption-cost weighted sum obtains the current edge cloud server and wireless access base station resource allocation rights. The present invention can realize multi-user multi-task offloading decision and resource allocation in an unbalanced edge cloud network, and can significantly reduce the weighted sum of the total delay-energy consumption-cost of multi-user multi-task offloading.

Description

An unbalanced edge cloud network access and resource allocation method

technical field

The invention belongs to the field of mobile cloud computing and mobile edge computing, in particular to an unbalanced edge cloud network access and resource allocation method.

Background technique

At present, the mobile Internet and mobile application innovation still face three major contradictions, including: the sharp increase in the demand for computing-intensive applications of mobile devices but the limited computing power and battery capacity of the mobile device itself, the sharp increase in the demand for mobile cloud access but the limited access capabilities, the mobile network There are more and more technological innovations, but operators' network pipelines are serious and the average revenue of users is constantly decreasing. In order to solve the above contradictions, a new technology of Mobile Edge Computing (MEC, Mobile Edge Computing) has been proposed, and it has become one of the key network technologies of the fifth generation mobile communication. In essence, mobile edge computing technology can be seen as the extension or expansion of mobile cloud computing technology to the network edge. The concept of MEC was first proposed by the European Telecommunications Standards Institute (ETSI, European Telecommunications Standards Institute) in 2014. A new platform for capabilities". In this model, significant computing and storage resources are placed at the edge of the network, close to mobile devices or sensors. Therefore, mobile users can migrate computing-intensive tasks to the MEC server for execution, thereby significantly reducing the requirements for the computing power of the mobile device and reducing the energy consumption caused by the execution of the computing-intensive tasks on the mobile device. Second, by serving servers at the edge of the network, mobile users do not need to access the remote cloud, which can significantly reduce the cloud platform and backbone network load. In addition, mobile network operators can rent idle resources of mobile edge computing servers to third parties to obtain additional benefits.

Most of the existing researches on the migration decision and resource allocation of mobile edge cloud computing systems are based on balanced mobile cloud edge computing server deployment, that is, each wireless access point is configured with an independent non-shared edge cloud server. However, in the actual network, based on the uneven distribution of airspace services and deployment cost factors, operators generally choose an unbalanced mobile edge server deployment strategy, that is, multiple wireless access points access a few wireless access points through one-hop or multi-hop links. shared edge computing server. At present, there is little research on migration decision and resource allocation under such unbalanced mobile edge cloud server deployment; the existing system design goals of research on mobile edge cloud computing system migration decision and resource allocation are mainly delay, energy consumption or time. The delay-energy consumption weight sum does not consider the service (use) cost of the mobile edge cloud server.

In an unbalanced edge cloud network access and resource allocation method in the present invention, the service cost of the edge cloud server has multiple meanings, such as the delay from the wireless access point to the edge cloud server, the wireless access point and the edge cloud server The pricing of service agreements between the virtual network operator and the computing service provider for resource usage, etc.; the cost of such services is related to the associated wireless access point. In this case, the system migration decision and resource allocation design need to jointly consider the delay-energy-cost trade-off.

SUMMARY OF THE INVENTION

In view of the above-mentioned defects of the prior art, the technical problem to be solved by the present invention is to provide an unbalanced edge cloud network access and resource allocation method, and the mechanism is a cyclic method. User multitasking independently selects the optimal task offloading path according to the weighted sum of minimum delay-energy consumption-cost criterion, and finally the task with the weighted sum of global minimum delay-energy consumption-cost obtains the current resource allocation of edge cloud servers and wireless access base stations right, and its final task offloading path is the wireless access base station and edge cloud server on the path to obtain the weighted sum of the minimum delay-energy consumption-cost. The above steps are repeated until the edge cloud server or wireless access base station resources are used up or all user tasks are unloaded. The method can realize multi-user and multi-task offloading decision and resource allocation in unbalanced edge cloud network. The method is a polynomial complexity method, and can significantly reduce the total delay-energy-consumption-cost weighted sum of multi-user and multi-task offloading.

To achieve the above object, the present invention provides an unbalanced edge cloud network access and resource allocation method, comprising the following steps:

S1. Define the following data;

define user set

Define user i uninstall task collection

define uninstall task set non-empty user set

Define the computing resource requirement ri _{,j of user i to unload task j} ;

Define a set of radio access base stations

Define the current number of accessible users Q _{m of the wireless access base station m} ;

Define a collection of edge cloud servers

Define the currently available computing resources R _{n of the edge cloud server n} ;

Define the time delay and energy consumption of user i offloading task j through wireless access base station m offloading transmission as t _i,j,m and e _i,j,m respectively;

Define the cost of wireless access base station m connecting edge cloud server n as cm _,n ;

The above data are defined in no particular order;

以及

如果条件

或

或

之一成立，则跳转到S8，否则跳转到S3；S2. Calculation

as well as

if condition

or

or

If one of them is established, jump to S8, otherwise jump to S3;

及卸载任务

依次执行S3-1到S3-5；S3, for any user

and uninstall tasks

Execute S3-1 to S3-5 in sequence;

和可接入边缘云服务器集合

分别为

和

S3-1: For the unloading task j of user i, construct a set of accessible wireless access base stations

and a collection of accessible edge cloud servers

respectively

and

的成本矩阵

S3-2: For the unloading task j of user i, the construction size is

cost matrix of

及该边缘云服务器索引

S3-3: For the unloading task j of the user i and the cost matrix C ^i,j , calculate the minimum cost of the accessible edge cloud server corresponding to each accessible wireless access base station m

and the edge cloud server index

卸载计算任务的总时延-能耗-成本权重和

其中α_i，β_i和γ_i分别为时延、能耗与成本权重因子，；S3-4: For the unloading task j of the user i, calculate the access to the edge cloud server through the wireless access base station m and the minimum cost.

The total delay-energy-cost weight sum of offloading computing tasks

where α _i , β _i and γ _i are the delay, energy consumption and cost weighting factors, respectively;

和最优可接入边缘云服务器

S3-5: For the unloading task j of user i, calculate its optimal accessible wireless access base station

and optimal access to edge cloud servers

中具有最小时延-能耗-成本的任务

并记录用户i的局部最优决策信息

包括用户i具有最小卸载时延-能耗-成本加权和的任务索引j^*，该任务的计算资源需求

该任务卸载路径上的无线接入基站索引

和边缘云服务器索引

以及该用户任务卸载的时延-能耗-成本加权和值

S4. For user i, calculate its uninstall task set

tasks with minimal latency-energy-cost in

And record the local optimal decision information of user i

Including the task index j ^* of the user i with the minimum offload delay-energy-cost weighted sum, the computing resource requirements of the task

The index of the radio access base station on the offload path of the task

and edge cloud server index

and the delay-energy-cost weighted sum of task offloading for this user

及卸载任务

都被遍历一次，则跳转到S6，否则跳转到S3；S5. If all users

and uninstall tasks

are all traversed once, then jump to S6, otherwise jump to S3;

及其任务j^*获得本次任务卸载的无线接入基站和边缘云服务器分配权利，即用户i^*的任务j^*通过无线接入基站

和边缘云服务器

完成任务卸载；S6. Use the delay-energy-consumption-cost weighted sum minimum criterion to select the user

Its task j ^* obtains the assignment rights of the wireless access base station and edge cloud server for this task offload, that is, the task j ^* of user i ^* accesses the base station through wireless

and edge cloud servers

Complete the task uninstall;

可用计算资源

更新无线接入基站

可接入用户数

更新用户i^*卸载任务集

后跳转到S2；S7, update edge cloud server

available computing resources

Update radio access base station

Accessible users

update user i ^* uninstall task set

Then jump to S2;

S8, the method ends.

Preferably, the weighting factor in step S3-4 satisfies α _i +β _i +γ _i =1, α _i ,β _i ,γ _i ∈[0,1].

The beneficial effects of the present invention are:

The invention can quickly obtain multi-user multi-task offloading paths and resource allocation of wireless access base stations and edge cloud servers;

The invention minimizes the weighted sum of delay-energy consumption-cost of multi-user multi-task offloading;

The present invention is not only applicable to an unbalanced edge cloud network, but also to a balanced edge cloud network;

The invention has fast convergence speed, low complexity and easy implementation.

Description of drawings

Fig. 1 is the scene diagram of the performance example of the present invention;

Figure 2 is a total delay-energy-cost weighted and comparison diagram;

Detailed ways

Below in conjunction with embodiment, the present invention is further described:

刻画；其中，

表示该用户Si任务计算资源需求量，

和

分别表示用户Si接入B1、B2和B3的时延-能耗加权代价。例如，对于用户S1与(2,3,2,5)，卸载计算任务的计算资源需求为2个单位，接入B1、B2和B3的时延-能耗加权代价分别为3、2和5。任意无线网络接入点Bj(j＝1,..,3)由一个二元组

刻画，分别表示无线网络接入点Bj接入边缘云服务器C1和C2的成本。例如，对于无线网络接入基站B1与(2,3)，其使用边缘云服务器C1和C2的单位成本分别是2和3。对于边缘云服务器Ck(k＝1,2)，由(z^k)刻画，表示Ck的可用计算资源数量。例如，对于边缘云服务器C1与(4)，其有4个单位的计算资源。显然，对于不同的用户Si，选择不同的任务卸载路径将承担不同的卸载成本并消耗对应的计算资源，如S2-B1-C2，即用户S2选择通过无线接入基站B1接入边缘云服务器C2，则其时延-能耗-成本和为8，消耗计算资源2个单位。可以看出，用户卸载路径选择受多个因素影响，包括无线接入基站接入时延-能耗、无线接入基站-边缘云服务器间连接成本、边缘云服务器计算资源以及其他用户卸载策略等。从系统全局角度来看，用户卸载路径是能耗-时延-成本的折中考虑。针对图1所示网络拓扑模型，一种非平衡边缘云网络接入与资源分配方法，它包含以下步骤：The network in FIG. 1 includes four mobile users (or tasks, applications) S1, S2, S3 and S4, three wireless network access base stations B1, B2 and B3, and two edge cloud servers C1 and C2. An arbitrary user Si (i=1,...,4) computes an offload task by a quaternion

engraving; in which,

Represents the computing resource demand of the user Si task,

and

respectively represent the delay-energy consumption weighted cost of user Si accessing B1, B2 and B3. For example, for users S1 and (2,3,2,5), the computing resource requirement for offloading computing tasks is 2 units, and the delay-energy consumption weighted costs for accessing B1, B2, and B3 are 3, 2, and 5, respectively. . Any wireless network access point Bj (j=1,..,3) consists of a two-tuple

Depicted, respectively represent the cost of wireless network access point Bj accessing edge cloud servers C1 and C2. For example, for wireless network access base stations B1 and (2, 3), the unit costs of using edge cloud servers C1 and C2 are 2 and 3, respectively. For the edge cloud server Ck (k=1, 2), it is characterized by (z ^k ), which represents the amount of available computing resources of Ck. For example, for edge cloud server C1 and (4), it has 4 units of computing resources. Obviously, for different users Si, choosing different task offloading paths will bear different offloading costs and consume corresponding computing resources, such as S2-B1-C2, that is, user S2 chooses to access edge cloud server C2 through wireless access base station B1 , then the sum of delay-energy-cost-cost is 8, consuming 2 units of computing resources. It can be seen that the selection of user offloading paths is affected by many factors, including wireless access base station access delay-energy consumption, connection cost between wireless access base stations and edge cloud servers, edge cloud server computing resources, and other user offloading strategies, etc. . From the global perspective of the system, the user offloading path is a compromise between energy consumption, delay and cost. For the network topology model shown in Figure 1, an unbalanced edge cloud network access and resource allocation method includes the following steps:

The method is suitable for unbalanced edge cloud networks and also for balanced edge cloud networks, that is, multiple wireless access base stations share edge cloud servers with fewer access numbers than wireless access base stations through backhaul links. Multiple users in the network have multiple computing-intensive tasks that need to be offloaded to edge cloud servers to complete computing, and multiple tasks of each user have different computing resource requirements. On the one hand, users will pay a certain fee (cost) to offload their tasks to the edge cloud server for computing, and this cost depends on the selected wireless access base station. On the other hand, users also face different delay overhead and energy consumption. All edge cloud servers in the network have limited computing resources, and each wireless access base station has an independent limit on the maximum number of users that can be accessed. Users choose wireless access base stations and edge cloud servers based on the delay-energy-consumption-cost criteria to complete Computing task offloading; the design criterion for system access and resource allocation is to minimize the total delay-energy-cost sum of the system;

There is a virtual decision center (VDC) in the network, which is responsible for collecting the information of all users, wireless access base stations and edge cloud servers. Delay and energy consumption, the cost of wireless access base stations accessing edge cloud servers, the number of users that can be accessed by wireless access base stations, and the computing resources of edge cloud servers;

An unbalanced edge cloud network access and resource allocation method, the allocation process includes the following steps:

S1. Define the following data;

define user set

Define user i uninstall task collection

define uninstall task set non-empty user set

Define the computing resource requirement ri _{,j of user i to unload task j} ;

Define a set of radio access base stations

Define the current number of accessible users Q _{m of the wireless access base station m} ;

Define a collection of edge cloud servers

Define the currently available computing resources R _{n of the edge cloud server n} ;

Define the time delay and energy consumption of user i offloading task j through wireless access base station m offloading transmission as t _i,j,m and e _i,j,m respectively;

Define the cost of wireless access base station m connecting edge cloud server n as cm _,n ;

The above data are defined in no particular order;

以及

如果条件

或

或

之一成立，则跳转到S8，否则跳转到S3；S2. Calculated by VDC

as well as

if condition

or

or

If one of them is established, jump to S8, otherwise jump to S3;

及卸载任务

依次执行S3-1到S3-5；S3, for any user

and uninstall tasks

Execute S3-1 to S3-5 in sequence;

和可接入边缘云服务器集合

分别为

和

S3-1: For the unloading task j of user i, construct a set of accessible wireless access base stations

and a collection of accessible edge cloud servers

respectively

and

的成本矩阵

S3-2: For the unloading task j of user i, the construction size is

cost matrix of

及该边缘云服务器索引

S3-3: For the unloading task j of the user i and the cost matrix C ^i,j , calculate the minimum cost of the accessible edge cloud server corresponding to each accessible wireless access base station m

and the edge cloud server index

卸载计算任务的总时延-能耗-成本权重和

其中α_i，β_i和γ_i分别为时延、能耗与成本权重因子，其中权重因子满足α_i+β_i+γ_i＝1,α_i,β_i,γ_i∈[0,1]；S3-4: For the unloading task j of the user i, calculate the access to the edge cloud server through the wireless access base station m and the minimum cost.

The total delay-energy-cost weight sum of offloading computing tasks

where α _i , β _i and γ _i are the weighting factors of delay, energy consumption and cost, respectively, and the weighting factors satisfy α _i +β _i +γ _i =1,α _i ,β _i ,γ _i ∈[0,1] ;

和最优可接入边缘云服务器

S3-5: For the unloading task j of user i, calculate its optimal accessible wireless access base station

and optimal access to edge cloud servers

中具有最小时延-能耗-成本的任务

并记录用户i的局部最优决策信息

包括用户i具有最小卸载时延-能耗-成本加权和的任务索引j^*，该任务的计算资源需求

该任务卸载路径上的无线接入基站索引

和边缘云服务器索引

以及该用户任务卸载的时延-能耗-成本加权和值

S4. For user i, calculate its uninstall task set

tasks with minimal latency-energy-cost in

And record the local optimal decision information of user i

Including the task index j ^* of the user i with the minimum offload delay-energy-cost weighted sum, the computing resource requirements of the task

The index of the radio access base station on the offload path of the task

and edge cloud server index

and the delay-energy-cost weighted sum of task offloading for this user

及卸载任务

都被遍历一次，则跳转到S6，否则跳转到S3；S5. If all users

and uninstall tasks

are all traversed once, then jump to S6, otherwise jump to S3;

及其任务j^*获得本次任务卸载的无线接入基站和边缘云服务器分配权利，即用户i^*的任务j^*通过无线接入基站

和边缘云服务器

完成任务卸载；S6, VDC uses the delay-energy-cost weighted sum minimum criterion to select the user

Its task j ^* obtains the assignment rights of the wireless access base station and edge cloud server for this task offload, that is, the task j ^* of user i ^* accesses the base station through wireless

and edge cloud servers

Complete the task uninstall;

的可用计算资源

和用户i^*卸载任务j^*的计算资源需求

In this cycle, determine the edge cloud server at this time

of available computing resources

and computing resource requirements of user i ^* offloading task j ^*

的可接入用户数

In this cycle, determine the wireless access base station at this time

number of accessible users

In this cycle, determine the uninstall task set of user i ^* at this time

可用计算资源

更新无线接入基站

可接入用户数

更新用户i^*卸载任务集

后跳转到S2；S7, update edge cloud server

available computing resources

Update radio access base station

Accessible users

update user i ^* uninstall task set

Then jump to S2;

的可用计算资源为步骤S6中的边缘云服务器

的可用计算资源减去用户i^*卸载任务j^*的计算资源需求；In this cycle, the updated edge cloud server in step S7

The available computing resources are the edge cloud server in step S6

of available computing resources minus the computing resource requirements of user i ^* offloading task j ^* ;

可接入用户数为步骤S6中的无线接入基站

可接入用户数自身减1；In this cycle, the wireless access base station is updated in step S7

The number of accessible users is the wireless access base station in step S6

The number of accessible users is reduced by 1;

In this cycle, the user i* uninstall task set after updating in step S7 is the set obtained by removing the task j ^* from the user i ^* uninstall task set in step S6;

S8, the method ends.

The performance of the method proposed in the present invention is compared with the random pairing method; the basic idea of the random pairing method is: each user task randomly selects the wireless access base station and the edge cloud server. The simulation setting conditions are: in the scenario of Figure 1, the average number of tasks per user changes as the horizontal axis, where the amount of computing resources ri _,j ∈ [2,6] for each task, the delay of each task migration t _i,j,m ∈[2,10], the energy consumption of each task migration e _i,j,m ∈[2,10], the cost of each base station accessing different servers c _m,n ∈[5, 6], the number of accessible tasks of the base station is Q _m ∈ [5, 7], the available resources of the edge server are R _n ∈ [30, 40], in addition, α=0.2, β=0.3, γ=0.5.

FIG. 2 shows a comparison diagram of the total delay-energy-consumption-cost weighted sum of the method proposed in the present invention and the random pairing method; it is the average result of performing 1000 Monte Carlo simulations. When the average number of tasks is 6, it reaches the limit of the number of tasks that the system can access. Before that, as the number of tasks increases, the total cost increases because the number of tasks to be migrated increases; after that, as the number of tasks increases, The total cost is reduced because the system can only access limited tasks at this time, and tasks with lower access costs can be selected from more tasks. It can be seen that, compared with the random pairing method, the method proposed in the present invention can significantly reduce the weighted sum of total system delay-energy consumption-cost.

The preferred embodiments of the present invention have been described in detail above. It should be understood that those skilled in the art can make many modifications and changes according to the concept of the present invention without creative efforts. Therefore, all technical solutions that can be obtained by those skilled in the art through logical analysis, reasoning or limited experiments on the basis of the prior art according to the concept of the present invention shall fall within the protection scope determined by the claims.

Claims (2)

1. an unbalanced edge cloud network access and resource allocation method, is characterized in that comprising the following steps: S1. Define the following data; define user set

Define user i uninstall task collection

define uninstall task set non-empty user set

Define the computing resource requirement ri _{,j of user i to unload task j} ; Define a set of radio access base stations

Define the current number of accessible users Q _{m of the wireless access base station m} ; Define a collection of edge cloud servers

Define the currently available computing resources R _{n of the edge cloud server n} ; Define the time delay and energy consumption of user i offloading task j through wireless access base station m offloading transmission as t _i,j,m and e _i,j,m respectively; Define the cost of wireless access base station m connecting edge cloud server n as cm _,n ; The above data are defined in no particular order; S2. Calculation

as well as

if condition

or

or

If one of them is established, jump to S8, otherwise jump to S3; S3, for any user

and uninstall tasks

Execute S3-1 to S3-5 in sequence; S3-1: For the unloading task j of user i, construct a set of accessible wireless access base stations

and a collection of accessible edge cloud servers

respectively

and

S3-2: For the unloading task j of user i, the construction size is

cost matrix of

S3-3: For the unloading task j of the user i and the cost matrix C ^i,j , calculate the minimum cost of the accessible edge cloud server corresponding to each accessible wireless access base station m

and the edge cloud server index

S3-4: For the unloading task j of the user i, calculate the access to the edge cloud server through the wireless access base station m and the minimum cost.

The total delay-energy-cost weight sum of offloading computing tasks

where α _i , β _i and γ _i are the delay, energy consumption and cost weighting factors, respectively; S3-5: For the unloading task j of user i, calculate its optimal accessible wireless access base station

and optimal access to edge cloud servers

S4. For user i, calculate its uninstall task set

tasks with minimal latency-energy-cost in

And record the local optimal decision information of user i

Including the task index j ^* of the user i with the minimum offload delay-energy-cost weighted sum, the computing resource requirements of the task

The index of the radio access base station on the offload path of the task

and edge cloud server index

and the delay-energy-cost weighted sum of task offloading for this user

S5. If all users

and uninstall tasks

are all traversed once, then jump to S6, otherwise jump to S3; S6. Use the delay-energy-consumption-cost weighted sum minimum criterion to select the user

Its task j ^* obtains the assignment rights of the wireless access base station and edge cloud server for this task offload, that is, the task j ^* of user i ^* accesses the base station through wireless

and edge cloud servers

Complete the task uninstall; S7, update edge cloud server

available computing resources

Update radio access base station

Accessible users

update user i ^* uninstall task set

Then jump to S2; S8, the method ends. 2. a kind of unbalanced edge cloud network access and resource allocation method as described in claim 1, is characterized in that; described weight factor in step S3-4 satisfies α _i + β _i +γ _i =1, α _i , β _i , γ _i ∈ [0,1].

Images