CN107708135B - Resource allocation method suitable for mobile edge computing scene - Google Patents

Abstract

The invention relates to a resource allocation method suitable for mobile edge computing scenarios. The method realizes optimal task caching and upload and download time allocation and low-complexity suboptimal task cache and upload and download time allocation based on task caching and transmission optimization mechanisms. When the calculation result of the task to be executed by the mobile device has been cached by the base station, the mobile device downloads the calculation result of the task from the base station; otherwise, the mobile device uploads the task to the base station for calculation, and then downloads the calculation result of the task from the base station, When multiple mobile devices upload the same task to the base station, the base station selects the mobile device with the best channel for uploading. When multiple mobile devices download the calculation result of the same task, the base station sends the calculation result of the task once by multicast. And make the mobile device with the worst channel just successfully receive the calculation result. Compared with the prior art, the present invention jointly optimizes the cache and upload and download time, and has the advantages of energy saving and the like.

Description

A resource allocation method suitable for mobile edge computing scenarios

technical field

The present invention relates to the field of mobile edge computing of wireless communication technology, in particular to a resource allocation method suitable for mobile edge computing scenarios.

Background technique

In the future, many computing-intensive and latency-sensitive tasks need to be run on mobile devices, these tasks have huge computational load and need to be completed in a short time, such as virtual reality, augmented reality, real-time online games, real-time monitoring, Navigation and Ultra High Definition (UHD) video streaming and more. However, due to the limited resources of the mobile device, the task cannot be completed in a short period of time, and the power of the mobile device is limited. Excessive energy consumption shortens the standby time of the mobile device. Mobile edge computing is a key technology for future computing-intensive and latency-sensitive tasks. Mobile edge computing, also known as "fog computing", moves the resources possessed by the cloud to the edge of the wireless network (such as base stations and wireless access points) closer to the user, where "cloud" refers to data centers, IP backbone networks and cellular cores A network that provides resources, such as a network. Mobile edge computing enables mobile users to obtain IT and cloud computing services at the edge of the radio access network, which can reduce service latency and improve user experience quality.

In the mobile edge computing system, when the task requests issued by users are highly concentrated in the space domain and repeated asynchronously or synchronously in the time domain, the calculation results are stored closer to the users (such as base stations) for future repetitions With this, the computational load and latency of mobile devices can be greatly reduced. Al-Shuwaili and O. Simeone in the article "Optimal resource allocation for mobile edge computing-based augmentedreality applications" propose a resource allocation scheme that allows users to share computing results and minimizes offloading under latency and power constraints The total mobile energy consumption generated. However, this article only focuses on one computational task and does not consider caching the computational results for future reuse. T.X.Tran, P.Pandey, A.Hajisami and D.Pompili proposed collaborative multi-bitrate video caching and processing in multi-user mobile edge computing systems in the article "Collaborative multi-bitrate video caching and processing in mobile-edge computing networks" processing, thereby minimizing the backhaul load, but does not account for the energy consumption of task execution and download of computational results. Therefore, considering multiple task requests and jointly optimizing cache and upload and download time to design an energy-efficient cache-assisted mobile edge computing system is a problem that needs further research.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a resource allocation method suitable for mobile edge computing scenarios in order to overcome the above-mentioned defects of the prior art, and to jointly optimize communication, cache and computing resources in a mobile edge system requested by multiple tasks to achieve the purpose of energy saving , an energy-efficient cache-assisted mobile edge computing system can be designed.

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

A resource allocation method suitable for mobile edge computing scenarios, the method realizes resource allocation of optimal task cache and upload and download time or resource allocation of low-complexity suboptimal task cache and upload and download time based on task cache and transmission optimization mechanism;

The task caching and transmission optimization mechanisms are:

When the calculation result of the task to be executed by the mobile device has been cached by the base station, the mobile device downloads the calculation result of the task from the base station, and when the calculation result of the task to be executed by the mobile device is not cached by the base station, the mobile device uploads the task Go to the base station for calculation, and then download the calculation result of the task from the base station. When multiple mobile devices upload the same task to the base station, the base station selects the mobile device with the best channel to upload, and when multiple mobile devices download the calculation result of the same task When the result is obtained, the base station sends the calculation result of the task once in a multicast mode, and makes the mobile device with the worst channel just successfully receive the calculation result.

The resource allocation based on task caching and transmission optimization mechanism to achieve optimal task caching and upload and download time is as follows:

The problem of minimizing the average total energy consumption of the system under the guarantee of delay is constructed, and the optimal allocation scheme is obtained by solving the problem.

The resource allocation of the optimal task cache and upload and download time specifically includes the following steps:

A1) The problem of minimizing the average total energy consumption of the system under the guarantee of construction delay:

E(c,T_u(X,H),T_d(X,H),X,H)为系统总能量消耗，

c_n表示任务n的计算结果在基站的缓存情况，c_n＝1表示任务n的计算结果在基站被缓存，c_n＝0表示表示任务n的计算结果未被基站缓存，

表示系统中任务的集合，X表示随机的系统任务状态，H表示随机的系统信道状态，T_u(X,H)和T_d(X,H)分别代表系统状态(X,H)下的各任务上传时间向量T_u和各任务下载时间向量T_d，L_d,n为任务n计算结果的大小，L_d,n>0，C为基站缓存容量，t_u,n为任务n的上传时间，t_d,n为任务n的下载时间，T为上传下载的总时间限制；in,

E(c, _Tu (X, H), T _d (X, H), X, H) is the total energy consumption of the system,

c _n indicates that the calculation result of task n is cached in the base station, c _n =1 indicates that the calculation result of task n is cached in the base station, c _n =0 indicates that the calculation result of task n is not cached by the base station,

Represents the set of tasks in the system, X represents the random system task state, H represents the random system channel state, and T _u (X, H) and T _d (X, H) represent the system state (X, H) respectively. Task upload time vector Tu and each task download time vector T _d , L _d,n is the size of the calculation result of task n, L _d,n > 0, C is the base station cache capacity, t _{u ,n} is the upload time of task n , t _{d, n} is the download time of task n, T is the total time limit of upload and download;

A2) Construct the Lagrangian relaxation problem:

Among them, L(c, T _u , T _d , λ) is the Lagrangian function of the problem of minimizing the average total energy consumption of the system under the guarantee of delay, and λ is the Lagrangian factor;

A3) Construct the dual problem of minimizing the average total energy consumption of the system under the guarantee of delay:

A4) Iteratively solve the dual problem to obtain the optimal allocation scheme.

In step A1), the total energy consumption of the system is defined as:

Among them, E _u,n (t _u,n ,X,H) represents the transmission energy loss of the mobile device uploading task n to the base station with the upload time t _u,n when the system state is (X,H), E _{e ,n} (X) represents the energy consumption of performing task n at the base station and obtaining its calculation result, E _d,n (t _d,n ,X,H) represents the transmission required by the base station to send the calculation result at the download time t _d,n energy.

The E _u,n (t _u,n ,X,H) is defined as

B为带宽，n₀为高斯白噪声的方差。Among them, _Hu,n is the maximum value of the channel power between all mobile devices with task n to be executed and the base station, _Lu,n refers to the size of the input of task n, _Lu,n >0, _Kn (X) is The total number of mobile devices with task n to be executed, the function g( ) is defined as:

B is the bandwidth, and n ₀ is the variance of white Gaussian noise.

The E _d,n (t _d,n ,X,H) is defined as

B为带宽，n₀为高斯白噪声的方差。Wherein, H _dn is the minimum value of the channel power between all mobile devices with task n to be performed and the base station, K _n (X) is the total number of mobile devices with task n to be performed, and the function g( ) is defined as:

B is the bandwidth, and n ₀ is the variance of white Gaussian noise.

The E _e,n (X) is defined as

Among them, F _b is the base station frequency, μ is a constant factor determined by the switch capacitor of the server, L _e,n is the workload of task n, that is, the number of CPU cycles required to execute task n, and K _n (X) is the number of CPU cycles required to execute task n. The total number of mobile devices executing task n.

Step A4) is specifically:

A401) Initialize loop number t=1 and Lagrangian multiplier

A402) Solve the Lagrangian relaxation problem under λ _t :

First, by solving the following knapsack problem, the optimal caching scheme under λ _t is obtained

where e _1,n (X,H,λ) is defined by:

e _1,n (X,H,λ)=p(X,H)(E _u,n (f(X,H,L _u,n ,H _u,n ,λ),X,H)+E _{e ,n} (X))+λf(X,H,L _u,n ,H _u,n ,λ)

Among them, p(X,H) represents the probability of the system state (X,H) appearing, and f(X,H,L _u,n ,H _u,n ,λ) is defined by the following formula:

where W( ) is the Lambertian function, K _n (X) is the total number of mobile devices with task n to be performed, B is the bandwidth, and n ₀ is the variance of white Gaussian noise;

和最优下载时间方案

Second, calculate the optimal upload time scheme under λ _t according to the following formula

and optimal download time scheme

A403) Calculate the subgradient of g(λ _t ):

Update λ _t+1 (X,H)=max{λ _t (X,H)+α _t s(X,H,λ _t ),0}, where α _t =(1+m)/(t+m ), m is a non-negative constant;

作为最优分配方案，终止，若否，更新迭代次数t＝t+1，进入步骤A402)。A404) Determine whether s(X, H, λ _t )<ε is satisfied, and ε is the set threshold, if so, output the current

As the optimal allocation scheme, terminate, if not, update the number of iterations t=t+1, and go to step A402).

Resource allocation based on task caching and transmission optimization mechanism to achieve low-complexity sub-optimal task caching and upload and download time is as follows:

Assuming that the base station does not cache the results of all tasks to be executed, the optimal solution of upload and download time allocation is obtained and then the task cache allocation is re-optimized. After obtaining an approximate task cache scheme, the upload and download time allocation scheme is re-optimized according to the approximate task cache scheme.

The resource allocation of the low-complexity suboptimal task cache and upload and download time includes the following steps:

下构建如下时间分配问题：B1) Assuming the base station buffer capacity C=0, in each system state

The following time allocation problem is constructed as follows:

表示系统中任务的集合，T为上传下载的总时间限制；Among them, En (0,t _u,n ,t _{d,n ,} X,H) represents the system energy consumption for task n, t _u,n is the upload time for uploading task n to the base station, and t _d,n is The download time for the base station to send the calculation result of task n, X represents the random system task state, H represents the random system channel state,

Represents the set of tasks in the system, T is the total time limit for uploading and downloading;

的拉格朗日因子

B2) Solving the time allocation problem, according to the following two formulas, the dichotomy method is used to satisfy

Lagrangian factor

where f(X,H,L _u,n ,H _u,n ,λ) is defined by the following formula:

where p(X,H) represents the probability of the system state (X,H) occurring, W( ) is the Lambertian function, Kn(X) is the total number of mobile devices with task _n to be performed, B is the bandwidth, n ₀ is the variance of white Gaussian noise;

和

Then determine the optimal solution of upload and download time allocation

and

B3) Reconsider the base station cache, even if C≠0, use the greedy algorithm to obtain an approximate task cache solution, that is, to solve the approximate solution of the following knapsack problem

Among them, cn indicates that the calculation result of task _{n is cached in the base station, c n =} 1 indicates that the calculation result of task n is cached in the base station, c _n =0 indicates that the calculation result of task n is not cached by the base station, L _{d, n} is the size of the calculation result of task n, L _d,n >0, e _1,n (X,H,λ) is defined by the following formula:

e _1,n (X,H,λ)=p(X,H)(E _u,n (f(X,H,L _u,n ,H _u,n ,λ),X,H)+E _{e ,n} (X))+λf(X,H,L _u,n ,H _u,n ,λ);

下、近似任务缓存方案

下的最优上传下载时间分配方案

和

B4) Based on the approximate task caching scheme, each system state is obtained using the following formula

Next, approximate task caching scheme

The optimal upload and download time allocation scheme under

and

Compared with the prior art, the present invention jointly optimizes communication, cache and computing resources in a mobile edge system requested by multiple tasks to achieve the purpose of energy saving, and has the following beneficial effects:

1. The upload and download mechanism can achieve the effect of energy saving. For any task, when multiple mobile devices need to upload the task to the base station for calculation, only one mobile device needs to upload the task to the base station to avoid repeated transmission. The base station selects the mobile device with the best channel (that is, the maximum channel power) to Upload to maximize the energy saving effect. When multiple mobile devices download the calculation results of the task, the base station sends the calculation results of the task once in a multicast mode, so that all mobile devices requesting the task can receive the calculation results successfully, avoiding repeated transmission, and achieving the effect of energy saving.

2. Under the condition that the system computing capacity allows, the optimal task cache and upload and download time allocation scheme can achieve optimal performance.

3. In the case of limited computing power of the system, the low-complexity sub-optimal task cache and upload and download time allocation scheme can obtain a better scheme with low complexity.

4. In the steps of solving the optimal task cache and uploading and downloading time allocation scheme, solve the Lagrangian relaxation problem, and update the Lagrangian multiplier cyclically according to the sub-gradient of its optimal solution to ensure the optimal scheme. sex.

5. When solving the low-complexity sub-optimal task cache and upload and download time allocation scheme, first set the base station cache space to zero, and then reconsider the base station cache after obtaining the intermediate variables, which greatly reduces the complexity of the problem.

Description of drawings

1 is a schematic diagram of a system model of the present invention;

Figure 2 is a schematic diagram of the calculation flow of the optimal task cache and upload and download time allocation scheme;

FIG. 3 is a schematic diagram of the calculation flow of the low-complexity suboptimal task cache and upload and download time allocation scheme.

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.

The present invention provides a resource allocation method suitable for mobile edge computing scenarios. The method realizes resource allocation of optimal task cache and upload and download time or low-complexity suboptimal task cache and upload and download time based on task cache and transmission optimization mechanism. Resource allocation.

The proposed task caching and transmission optimization mechanism is specifically: when the calculation result of the task to be executed by the mobile device has been cached by the base station, the mobile device downloads the calculation result of the task from the base station, when the calculation result of the task to be executed by the mobile device is When it is not cached by the base station, the mobile device uploads the task to the base station for calculation, and then downloads the calculation result of the task from the base station; wherein, when multiple mobile devices upload the same task to the base station, the base station selects the mobile device with the best channel. Upload, when multiple mobile devices download the calculation result of the same task, the base station sends the calculation result of the task once by multicast, and makes the mobile device with the worst channel just successfully receive the calculation result.

There are 1 base station, 5 mobile devices and 4 tasks in the system model shown in Figure 1. The base station stores the calculation results of task 1 and task 2. There are two channel states in the system: excellent channel and poor channel. Specifically, both mobile device 1 and mobile device 2 are to perform task 1, and both have the same channel. The base station has stored the calculation result of task 1. The base station calculates the transmission rate according to the channels of mobile devices 1 and 2, and uses this transmission rate The rate directly sends the calculation result of task 1 to mobile device 1 and mobile device 2 by multicast; only mobile device 3 is to execute task 2, and the base station has stored the calculation result of task 2, so the base station directly sends the calculation result of task 2 The result is sent to mobile device 3 by unicast; both mobile device 4 and mobile device 5 are to execute task 4. Since the base station does not store the calculation result of task 4, it is necessary to select a mobile device to upload task 4 to the base station, and the mobile device 4 has the best channel, so the mobile device 4 uploads the task 4 to the base station, and then the base station calculates the task 4. Since the mobile device 5 has the worst channel, the base station calculates the transmission rate according to the channel of the mobile device 5, at this rate The calculation result of task 4 is sent to mobile device 4 and mobile device 5 in a multicast manner to ensure that both mobile device 4 and mobile device 5 can receive it successfully.

1. Resource allocation based on task caching and transmission optimization mechanism to achieve optimal task caching and upload and download time. Specifically, the problem of minimizing the average total energy consumption of the system under the guarantee of delay is constructed, and the optimal allocation scheme is obtained by solving it, as shown in Figure 2. shown, including the following steps:

A1) The problem of minimizing the average total energy consumption of the system under the guarantee of construction delay:

E(c,T_u(X,H),T_d(X,H),X,H)为系统总能量消耗，

c_n表示任务n的计算结果在基站的缓存情况，c_n＝1表示任务n的计算结果在基站被缓存，c_n＝0表示任务n的计算结果未被基站缓存，

表示系统中任务的集合，X表示随机的系统任务状态，H表示随机的系统信道状态，T_u(X,H)和T_d(X,H)分别代表系统状态(X,H)下的各任务上传时间向量T_u和各任务下载时间向量T_d，L_d,n为任务n计算结果的大小，L_d,n>0，C为基站缓存容量，t_u,n为任务_n的上传时间，t_d,n为任务n的下载时间，T为上传下载的总时间限制。in,

E(c, _Tu (X, H), T _d (X, H), X, H) is the total energy consumption of the system,

c _n indicates that the calculation result of task n is cached in the base station, c _n =1 indicates that the calculation result of task n is cached in the base station, c _n =0 indicates that the calculation result of task n is not cached by the base station,

Represents the set of tasks in the system, X represents the random system task state, H represents the random system channel state, and T _u (X, H) and T _d (X, H) represent the system state (X, H) respectively. Task upload time vector Tu and each task download time vector T _d , L _d,n is the size of the calculation result of task n, L _d,n > 0, C is the base station cache capacity, t _{u ,n} is the upload time of task _n , t _d,n is the download time of task n, and T is the total time limit for uploading and downloading.

The total energy consumption of the system is defined as:

Among them, E _u,n (t _u,n ,X,H) represents the transmission energy loss of the mobile device uploading task n to the base station with the upload time t _u,n when the system state is (X,H), E _{e ,n} (X) represents the energy consumption of performing task n at the base station and obtaining its calculation result, E _d,n (t _d,n ,X,H) represents the transmission required by the base station to send the calculation result at the download time t _d,n energy, specifically:

E _u,n (t _u,n ,X,H) is defined as

B为带宽，n₀为高斯白噪声的方差。Among them, _Hu,n is the maximum value of the channel power between all mobile devices with task n to be executed and the base station, _Lu,n refers to the size of the input of task n, _Lu,n >0, _Kn (X) is The total number of mobile devices with task n to be executed, the function g( ) is defined as:

B is the bandwidth, and n ₀ is the variance of white Gaussian noise.

E _d,n (t _d,n ,X,H) is defined as

B为带宽，n₀为高斯白噪声的方差。Wherein, H _dn is the minimum value of the channel power between all mobile devices with task n to be performed and the base station, K _n (X) is the total number of mobile devices with task n to be performed, and the function g( ) is defined as:

B is the bandwidth, and n ₀ is the variance of white Gaussian noise.

E _e,n (X) is defined as

Among them, F _b is the base station frequency, μ is a constant factor determined by the switch capacitor of the server, L _e,n is the workload of task n, that is, the number of CPU cycles required to execute task n, and K _n (X) is the number of CPU cycles required to execute task n. The total number of mobile devices executing task n.

A2) Construct the Lagrangian relaxation problem:

Among them, L(c, T _u , T _d , λ) is the Lagrangian function of the problem of minimizing the average total energy consumption of the system under the guarantee of delay, and λ is the Lagrangian factor.

A3) Construct the dual problem of minimizing the average total energy consumption of the system under the guarantee of delay:

A4) Iteratively solve the dual problem, obtain the optimal allocation scheme, initialize the number of loops t=1 and the Lagrange multiplier

A5) Solve the Lagrangian relaxation problem under λ _t :

First, by solving the following knapsack problem, the optimal caching scheme under λ _t is obtained

where e _1,n (X,H,λ) is defined by:

e _1,n (X,H,λ)=p(X,H)(E _u,n (f(X,H,L _u,n ,H _u,n ,λ),X,H)+E _{e ,n} (X))+λf(X,H,L _u,n ,H _u,n ,λ)

Among them, p(X,H) represents the probability of the system state (X,H) appearing, and f(X,H,L _u,n ,H _u,n ,λ) is defined by the following formula:

where W( ) is the Lambertian function, K _n (X) is the total number of mobile devices with task n to be performed, B is the bandwidth, and n ₀ is the variance of white Gaussian noise;

和最优下载时间方案

Second, calculate the optimal upload time scheme under λ _t according to the following formula

and optimal download time scheme

A6) Calculate the subgradient of g(λ _t ):

Update λ _t+1 (X,H)=max{λ _t (X,H)+α _t s(X,H,λ _t ),0}, where α _t =(1+m)/(t+m ), m is a non-negative constant.

和

作为最优分配方案，终止，若否，更新迭代次数t＝t+1，进入步骤A5)。A7) Judging whether s(X, H, λ _t )<ε is satisfied, ε is the set threshold, if so, output the current

and

As the optimal allocation scheme, terminate, if not, update the number of iterations t=t+1, and go to step A5).

2. Realization of low-complexity sub-optimal task caching and resource allocation of upload and download time based on task caching and transmission optimization mechanism Specifically, assuming that the base station does not cache the results of all tasks to be executed, the optimal solution for upload and download time allocation is obtained and then re-optimized Task cache allocation, after obtaining an approximate task cache scheme, re-optimize the upload and download time allocation scheme according to the approximate task cache scheme, as shown in Figure 3, including the following steps:

下构建如下时间分配问题：B1) Assuming the base station buffer capacity C=0, in each system state

The following time allocation problem is constructed as follows:

的拉格朗日因子

B2) Solving the time allocation problem, according to the following two formulas, the dichotomy method is used to satisfy

Lagrangian factor

和

Then determine the optimal solution of upload and download time allocation

and

B3) Reconsider the base station cache, even if C≠0, use the greedy algorithm to obtain an approximate task cache solution, that is, to solve the approximate solution of the following knapsack problem

下、近似任务缓存方案

下的最优上传下载时间分配方案

和

B4) Based on the approximate task caching scheme, each system state is obtained using the following formula

Next, approximate task caching scheme

The optimal upload and download time allocation scheme under

and

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 (6)

1. A resource allocation method suitable for a mobile edge computing scene is characterized in that the method realizes resource allocation of optimal task cache and uploading and downloading time or low-complexity suboptimal task cache and uploading and downloading time based on a task cache and transmission optimization mechanism;

the task caching and transmission optimizing mechanism comprises the following steps:

when the calculation result of the task to be executed by the mobile equipment is cached by the base station, the mobile equipment downloads the calculation result of the task from the base station, when the calculation result of the task to be executed by the mobile equipment is not cached by the base station, the mobile equipment uploads the task to the base station for calculation, and then downloads the calculation result of the task from the base station, wherein when a plurality of mobile equipment upload the same task to the base station, the base station selects the mobile equipment with the best channel to realize uploading, and when a plurality of mobile equipment download the calculation result of the same task, the base station sends the calculation result of the task once in a multicast mode, and enables the mobile equipment with the worst channel to receive the calculation result just successfully;

the resource allocation for realizing the optimal task caching and uploading and downloading time based on the task caching and transmission optimization mechanism specifically comprises the following steps: constructing a system average total energy consumption minimization problem under the time delay guarantee, and solving to obtain an optimal distribution scheme;

the resource allocation of the optimal task caching and uploading and downloading time comprises the following steps:

A1) the problem of minimizing the average total energy consumption of the system under the guarantee of the construction time delay is as follows:

wherein,

E(c,T_u(X,H),T_d(X, H), wherein X and H are total energy consumption of the system,

c_nrepresenting the buffer condition of the calculation result of the task n in the base station, c_n1 indicates that the calculation result of task n is buffered at the base station, c_n0 indicates that the calculation result of task n is not buffered by the base station,

representing a set of tasks in the system, X representing a random state of the system tasks, H representing a random state of the system channels, T_u(X, H) and T_d(X, H) respectively represents each task uploading time vector T under the system state (X, H)_uAnd each task download time vector T_d，L_d,nCalculate the size of the result, L, for task n_d,n>0, C is base station buffer capacity, t_u,nFor the upload time of task n, t_d,nThe time is the download time of the task n, and T is the total time limit of uploading and downloading;

A2) constructing the lagrangian relaxation problem:

wherein, L (c, T)_u,T_dLambda) is a Lagrange function of the system average total energy consumption minimization problem under the time delay guarantee, and lambda is a Lagrange factor;

A3) the dual problem of the problem of minimizing the average total energy consumption of the system under the guarantee of the construction time delay is as follows:

A4) iteratively solving the dual problem to obtain an optimal distribution scheme;

the resource allocation for realizing the low-complexity suboptimal task caching and uploading and downloading time based on the task caching and transmission optimization mechanism specifically comprises the following steps:

supposing that the base station does not cache the results of all the tasks to be executed, re-optimizing the task cache allocation after obtaining the optimal solution of the uploading and downloading time allocation, and re-optimizing the uploading and downloading time allocation scheme according to the approximate task cache scheme after obtaining an approximate task cache scheme;

the resource allocation of the low-complexity suboptimum task caching and uploading and downloading time comprises the following steps:

B1) assuming that the base station buffer capacity C is 0, in each system state

The following time allocation problem is constructed:

wherein E is_n(0,t_u,n,t_d,nX, H) represents the system energy consumption for task n, t_u,nUpload time, t, for uploading task n to base station_d,nThe download time for the base station to send the calculation result of task n, X represents the random system task state, H represents the random system channel state,

representing a set of tasks in the system, wherein T is the total time limit of uploading and downloading;

B2) solving the time distribution problem, and obtaining the time distribution problem by using a dichotomy according to the following two formulas

Lagrange's factor of

Wherein, f (X, H, L)_u,n,H_u,nλ), is defined by the following formula:

where p (X, H) represents the probability of occurrence of the system state (X, H), W (-) is a Lambert function, K_n(X) is the total number of mobile devices with task n to be performed, B is the bandwidth, n₀Is the variance of Gaussian white noise;

further determining the optimal solution of uploading and downloading time distribution

And

B3) reconsidering base station caching, i.e. making C not equal to 0, and solving an approximate task caching scheme by using a greedy algorithm, i.e. solving an approximate solution of the following knapsack problem

Wherein, c_nRepresenting the buffer condition of the calculation result of the task n in the base station, c_n1 indicates that the calculation result of task n is buffered at the base station, c_n0 indicates that the calculation result of task n is not cached by the base station, L_d,nCalculate the size of the result, L, for task n_d,n>0，e_1,n(X, H, λ) is defined by the formula:

e_1,n(X,H,λ)＝p(X,H)(E_u,n(f(X,H,L_u,n,H_u,n,λ),X,H)+E_e,n(X))+λf(X,H,L_u,n,H_u,n,λ)；

B4) based on the approximate task caching scheme, each system state is obtained by using the following formula

Lower and approximate task caching scheme

Optimal uploading and downloading time distribution scheme

And

2. the resource allocation method for a moving edge computing scenario as claimed in claim 1, wherein in step a1), the total energy consumption of the system is defined as:

wherein E is_u,n(t_u,nX, H) indicates that the mobile device uploads time t when the system state is (X, H)_u,nTransmission energy loss for uploading task n to base station, E_e,n(X) represents the energy consumption for executing task n and obtaining the calculation result thereof at the base station, E_d,n(t_d,nX, H) denotes the base station download time t_d,nAnd transmitting transmission energy required by the calculation result.

3. The method of claim 2, wherein E is the resource allocation rule for a moving edge computing scenario_u,n(t_u,nX, H) is defined as

Wherein H_u,nFor the maximum value of the channel power between all mobile devices having task n to be performed and the base station, L_u,nRefers to the size of the task n input, L_u,n>0，K_n(X) is the total number of mobile devices with task n to perform, and the function g (-) is defined as:

b is the bandwidth, n₀Is the variance of gaussian white noise.

4. The method of claim 2, wherein E is the resource allocation rule for a moving edge computing scenario_d,n(t_d,nX, H) is defined as

Wherein H_d,nFor the minimum value of the channel power between all mobile devices having task n to be performed and the base station, K_n(X) is the total number of mobile devices with task n to perform, and the function g (-) is defined as:

b is the bandwidth, n₀Is the variance of gaussian white noise.

5. The method of claim 2, wherein E is the resource allocation rule for a moving edge computing scenario_e,n(X) is defined as

Wherein, F_bMu is a constant factor determined by the switched capacitance of the server, L, for the base station frequency_e,nFor the workload of task n, i.e. the number of CPU cycles required to execute task n, K_n(X) is the total number of mobile devices having task n to perform.

6. The resource allocation method applicable to the mobile edge computing scenario as claimed in claim 2, wherein step a4) is specifically:

A401) number of initialization cycles t 1 and lagrange multiplier

A402) Solving for λ_tThe following lagrangian relaxation problem:

first, by solving the following knapsack problem, λ is obtained_tOptimal caching scheme of

Wherein e is_1,n(X, H, λ) is defined by the formula:

e_1,n(X,H,λ)＝p(X,H)(E_u,n(f(X,H,L_u,n,H_u,n,λ),X,H)+E_e,n(X))+λf(X,H,L_u,n,H_u,n,λ)

wherein p (X, H) represents the probability of occurrence of the system state (X, H), and f (X, H, L)_u,n,H_u,nλ), is defined by the following formula:

wherein W (-) is a Lambert function, K_n(X) is the total number of mobile devices with task n to be performed, B is the bandwidth, n₀Is the variance of Gaussian white noise;

next, λ is calculated according to the following formula_tOptimal upload time scheme of

And optimal download time scheme

A403) Calculating g (lambda)_t) The secondary gradient of (a):

updating lambda_t+1(X,H)＝max{λ_t(X,H)+α_ts(X,H,λ_t) 0} where α is_t(1+ m)/(t + m), m being a non-negative constant;

A404) judging whether s (X, H, lambda) is satisfied_t) If epsilon is less than epsilon, epsilon is a set threshold value, if epsilon is less than epsilon, then output of the current time

And

as the optimal allocation scheme, the process is terminated, and if not, the number of update iterations t is t +1, and the process proceeds to step a 402).

Images