CN114706631B - Unloading decision method and system in mobile edge calculation based on deep Q learning - Google Patents

Abstract

An unloading decision method and system in mobile edge calculation based on deep Q learning belongs to the technical field of unloading decision of mobile equipment in a mobile edge calculation system. The invention solves the problems of large time delay and high energy consumption generated in the unloading decision process in the existing mobile edge computing system. The invention applies a deep reinforcement learning algorithm to the unloading decision problem in the mobile edge calculation, and designs the corresponding system state, action and reward equation according to the task scheduling models such as a local calculation queue, a task transmission queue, an edge server queue and the like established in the system. By comparing the average time delay and energy consumption of the method with those of other algorithms, the unloading decision method disclosed by the invention can be used for greatly reducing the time delay and energy consumption generated in the unloading decision process in the mobile edge computing system. The method can be applied to the unloading decision of the mobile equipment in the mobile edge computing system.

Description

Method and system for offloading decision-making in mobile edge computing based on deep Q-learning

technical field

The invention belongs to the technical field of offloading decision-making of mobile devices in a mobile edge computing system, and in particular relates to a method and system for offloading decision-making in mobile edge computing based on deep Q-learning.

Background technique

With the rapid development of 5G and IoT technologies, people have stepped into a new world where everything is connected. In recent years, the number of mobile devices with networking capabilities, such as smart phones, smart home appliances, and smart wearable devices, has grown exponentially. The ability to transmit and calculate data imposes even more stringent requirements. How to find an effective way to solve the needs of IoT devices for data transmission and data computing is an urgent problem to be solved, and mobile edge computing has become an effective solution.

Although the existing mobile edge computing methods have achieved certain achievements, the delay in the offloading decision-making process in the existing mobile edge computing system is still large, and the energy consumption is still high. It is necessary to propose an unloading decision-making method to reduce the delay and energy consumption of the unloading decision-making process.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the problems of large time delay and high energy consumption in the offloading decision-making process in the existing mobile edge computing system, and propose a method and system for offloading decision-making in mobile edge computing based on deep Q-learning.

The technical scheme that the present invention takes to solve the above-mentioned technical problems is:

Based on one aspect of the present invention, a method for unloading decision-making in mobile edge computing based on deep Q learning, the method specifically includes the following steps:

Step 1. Build a reinforcement learning model

Construct the system state, system action and reward function in the Markov decision process according to the task characteristics;

Step 2, Neural Network Construction

Construct a neural network including an input layer, an LSTM layer, a first FC layer, a second FC layer, and an output layer. The input layer is used to pass the system state information to the LSTM layer and the first FC layer, and the output of the LSTM layer is used as the first FC layer. An input to the FC layer;

Then the output of the first FC layer is used as the input of the second FC layer, and the output of the second FC layer is used as the input of the output layer.

Further, the construction mode of the system state is:

Denote the task size of mobile device m at the beginning of the current time slot as λ _m (t), if there is a new task k (t) in mobile device m at the beginning of the current time slot, then λ _m (t)=k(t) , otherwise λ _m (t)=0;

将当前时隙开始时移动设备m的自身任务在任务传输队列中需要等待的时隙数表示为

将移动设备m在边缘节点n处的队列长度表示为

Construct the local computing queue, task transmission queue and edge node computing queue, and express the number of time slots that the mobile device m's own task needs to wait in the local computing queue at the beginning of the current time slot as

The number of timeslots that the mobile device m's own task needs to wait in the task transmission queue at the beginning of the current timeslot is expressed as

Denote the queue length of mobile device m at edge node n as

Construct a matrix M(t) representing the load level of each edge server in T time slots before the current time slot, where the dimension of M(t) is T×N, where N is the number of edge servers;

Then the system state s _m (t) observed by the mobile device m at the current time slot is:

Further, the system action is expressed as a(t)={0, 1, 2, ..., N}, where 0 represents local computing, k=1, 2, ..., N, k represents the serial number.

Further, the construction method of the reward function is:

为：The number of slots the task waits for if it is decided to compute locally

for:

表示在时隙t′产生的任务在本地执行完成后的时刻；in,

Represents the moment after the local execution of the task generated in the time slot t' is completed;

为：energy required for task-local computation

for:

Among them, ε _m represents the energy consumption coefficient of the CPU when the mobile device m calculates locally, that is, the energy consumed by the local CPU to calculate one cycle, and d _m represents the calculation amount of the task currently generated by the mobile device m, that is, the current task needs to be executed. The number of CPU computing cycles;

和

那么移动用户m在卸载决策过程中的奖励函数为：Set the preference coefficients of mobile user m for delay and energy consumption as

and

Then the reward function of mobile user m in the uninstallation decision process is:

与任务在本地执行过程中产生的时延之和，E为移动用户m产生的总能耗，即

Among them, R is the value of the reward function, T is the total delay generated by the mobile user m in the local calculation, that is, T is equal to the number of time slots waiting for the task to queue up.

The sum of the delay generated by the task in the local execution process, E is the total energy consumption generated by the mobile user m, namely

Further, the construction method of the reward function is:

来计算，即任务等待的时隙数为

If the task is decided to be edge computing, the number of time slots that the task waits for is determined by the moment after the execution of the edge server n is completed.

To calculate, that is, the number of time slots the task waits for is

为：The energy required in task edge computing includes two parts: task uploading and task execution. The power of the mobile device when the task is uploaded is expressed as p _up , and the power of the mobile device when the task is executed is expressed as p _e , then for the mobile device m, energy required

for:

Among them, t _n,up represents the time consumed by the mobile device m to upload the task to the edge server n, and t _{n, e} represents the time consumed by the mobile device m to execute the task in the edge server n.

At this point, the user's reward function in the uninstallation decision process is:

任务上传到边缘服务器n产生的时延t_n,up以及任务在边缘服务器n执行产生的时延t_n,e的和，E是边缘计算产生的总能耗，即

Among them, R is the reward function value, T is the total delay caused by task queuing

The sum of the delay t _n,up generated by the task uploading to the edge server n and the delay t _n,e generated by the task execution on the edge server n, E is the total energy consumption generated by edge computing, namely

Further, the construction method of the reward function is:

If the maximum delay time allowed by the task has been reached before the task execution is completed, the task is discarded, and the reward function value R at this time is set as a fixed penalty value P.

Further, the LSTM layer is used to predict the temporal correlation of the load level of the edge server according to the matrix M(t).

Further, the first FC layer and the second FC layer are used to learn the mapping from the system state to the system action reward function value, and both the first FC layer and the second FC layer include a group of neurons with rectified linear units.

Furthermore, the output layer is used to output the reward function value corresponding to the currently selected action in the current system state.

Based on another aspect of the present invention, an offloading decision-making system in mobile edge computing based on deep Q-learning is provided, the system is used to execute a decision-making method for offloading in mobile edge computing based on deep Q-learning.

The beneficial effects of the present invention are:

The invention applies the deep reinforcement learning algorithm to the unloading decision problem in the mobile edge computing, and designs the corresponding system state, action and reward equation according to the task scheduling models established in the system, such as the local computing queue, the task transmission queue, and the edge server queue. By comparing the average delay and energy consumption of the method of the present invention and other algorithms, it can be concluded that the offloading decision method of the present invention greatly reduces the delay and energy consumption of the offloading decision process in the mobile edge computing system.

Description of drawings

Fig. 1 is the neural network structure diagram that the present invention builds;

Fig. 2 is the reward function value of the inventive method with the number of iterations convergence curve diagram;

3 is a graph showing the average reward value of the method of the present invention and other three baseline algorithms changing with the number of users;

FIG. 4 is a graph showing the variation of the average delay with the number of users of the method of the present invention and the other three baseline algorithms.

Detailed ways

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 1. In this embodiment, a computing offloading strategy based on deep reinforcement learning is proposed for the network scenario of multiple mobile devices and multiple servers in the MEC system. Each mobile user is regarded as an agent, and tasks need to be queued due to the order of arrival in the process of unloading tasks. The present invention constructs three queues including a local computing queue, a task transmission queue, and an edge node computing queue. task scheduling model. Then, the calculation models of delay and energy consumption cost under two types of task execution modes are established respectively, and the target design method is to minimize the system cost, so that the minimum system delay and energy consumption can be generated in several consecutive time slots.

Step 1. Build a reinforcement learning model:

This step provides a detailed description of the specific implementation of the present invention using DQN to perform task offloading decision. It mainly includes the definition of system state, action, and reward equation in Markov decision-making process.

1. Markov decision process construction

At the beginning of each slot, each mobile device observes its state (information such as task size, queue length, etc.). If there is a new task to process, the mobile device chooses an appropriate offloading decision for that task, minimizing the long-term cost of its task computation. Applying deep reinforcement learning to the task offloading decision problem requires constructing a Markov decision process, in which the system state, action and reward equation need to be specifically defined.

2. System status settings

The first piece of information related to offloading decisions is the nature of the task itself. First consider the size of the task itself λ(t). At the beginning of each time slot, the mobile device m needs to first observe the size of its own task, denoted by λ(t). Among them, if there is a new task k(t) at the beginning of the current time slot, then λ(t)=k(t), otherwise λ(t)=0. Note that because the generation of the new task is also generated at the beginning of the time slot, there is no problem that the task generated in the time slot cannot calculate λ(t).

A task characteristic that also needs to be considered is the maximum acceptable latency of the task, which is also relevant for offloading decisions. Therefore, it is also considered to be added to the system state.

The execution time of tasks in the three queues is also related to the unloading decision. So it should also be added to the system state. Specifically include:

表示任务在本地计算队列中需要等待的时隙数；

Indicates the number of time slots that the task needs to wait in the local computing queue;

表示任务在传输队列中需要等待的时隙数；

Indicates the number of time slots that the task needs to wait in the transmission queue;

表示移动设备m在边缘节点n处的队列长度。

represents the queue length of mobile device m at edge node n.

Since the load level of each edge node, i.e. the number of active queues at the node, is constantly changing. The load level at the current moment has a strong correlation with the previous moment. Therefore, it is considered to construct an edge node load level matrix M(t) to reflect the load level of edge nodes in a period of time.

Specifically, the matrix M(t) is used to represent the load level of each edge node in the first T time slots (from time slot tT to time slot t-1) (that is, the number of active queues of this edge node, the maximum is mobile History of the number of devices M). It is a T×N-dimensional matrix, where T is the total number of time slots, and N is the number of edge nodes. For example, {M(t)} _(i,j) represents the number of active queues of edge node j at the t-T+i-1th time slot.

Based on the above description, the system state observed by the mobile device m at the current time slot can be defined as a vector of several dimensions, represented by s _m (t), that is

3. System action

The decision that each mobile device needs to make is first to decide whether to offload to an edge server or to execute locally, and then it needs to consider which edge server to offload to. Use 0 for local computing and k for the sequence number of the offloaded edge server. Assuming a total of M edge servers, the system action can be expressed as a(t)={0,1,2,...,M}.

4. Reward function

What affects the mobile device application experience the most is the delay and energy consumption caused by uninstallation. Therefore, the setting of the reward function of the present invention is also constructed around the time delay and energy consumption generated during the task unloading process.

The delay generated by the task is considered from both local computing and edge computing.

可以如下计算。If the task is decided to compute locally, the number of slots the task waits for

It can be calculated as follows.

来计算，即为

If the task is decided to be edge computing, the number of time slots the task waits for is determined by the moment after the execution of the edge node is completed.

to calculate, that is,

The energy consumption of tasks is also considered from both local computing and edge computing.

The energy required for task-local computation is

The energy consumption in task edge computing is mainly in two parts: task uploading and task execution. Assuming that the power of the mobile device is p _up when the task is uploaded, and the power of the mobile device is p _e when the task is executed, then for device i;

和

那么设置用户在卸载决策过程中的奖励函数为Set the preference coefficients of mobile user i for delay and energy consumption as

and

Then set the reward function of the user in the uninstall decision process as

On the other hand, if the task is discarded because it has reached the maximum delay time it can accept, then the reward function at this time is defined as a fixed penalty value P, that is

R=P (5)

Step 2. Neural network construction, as shown in Figure 1:

M(t)将被传递给FC层进行预测。1. Input layer: This layer is responsible for taking the state as input and passing it to the following layers. For mobile device m, the state information λ(t),

M(t) will be passed to the FC layer for prediction.

2. LSTM layer: The matrix M(t) represents the load level of each edge node in the first T time slots, and the load level of the edge node is time-dependent, that is, the load level of the edge node is time-dependent. So consider using LSTM layers to predict the temporal correlation of load levels.

3. FC layer: Two FC layers are responsible for learning the mapping of state to action Q value. Each FC layer contains a set of neurons with rectified linear units.

4. Output layer: The value of the output layer corresponds to the current state and adopts the Q value corresponding to the currently selected action. It is used to reflect the comprehensive cost brought by the current decision, that is, the equilibrium value of delay and energy consumption.

Example

This embodiment introduces the system architecture of the application of the present invention from three aspects: the network model, the task model, and the task scheduling model.

Step 1. Establishment of a network model: The scenario targeted by the present invention consists of the following two parts, several base stations equipped with edge servers, and several mobile devices that need to perform intensive computing tasks. Each base station is equipped with an edge server with high computing power. It is assumed that at the beginning of each time slot, each mobile device generates an intensive task that needs to be executed with a certain probability. The task is either executed locally or all offloaded to the edge server for execution, and the task is inseparable.

Consider a time period T={1, 2, 3, . For the N mobile devices in the cell, at the beginning of each time slot, the offloading decision variable α _i is used to indicate whether to offload the computing task to the edge server for execution and which server to offload it to, if it is selected to be offloaded to the kth In each edge server, the decision variable a _i =k, if you choose to execute the task locally, the decision variable a _i =0.

It is assumed that the tasks of the mobile device have the same priority. Each edge node has a CPU for processing tasks in the queue. At the beginning of each time slot, the task queues corresponding to several mobile devices at the edge node share the processing power of the CPU at the edge node n on average.

Step 2. Establishment of the task model: The task representation generated by the mobile device has two dimensions. One is the storage space size of the task. Here, the task size λ _m (t) is set to a random value between 3Mbit and 5Mbit, and the step size is 0.1 Mbit. The other is the maximum number of waiting slots that a task can accept, denoted by τ _m . When a task waits longer than τ _m , the task will be discarded in the system.

Step 3. Establishment of task scheduling model: Taking the edge server side as an example, since tasks arrive in sequence, at the beginning of the next time slot, the edge server may not have processed the tasks of the previous time slot, so the tasks will be queued . This part builds three queue models of local computing queue, task transmission queue, and edge node computing queue as task scheduling models.

Step 4. Algorithm performance evaluation and analysis:

Select a scenario to study the convergence of the algorithm, set the number of users to 120, the number of edge servers to 5, the algorithm iterates 1200 times, and plot the average reward value of the algorithm's reward function after 100 consecutive decisions. It can be seen from Figure 2 that the average reward value begins to converge when the number of iterations reaches about 500, and the average reward value gradually becomes stable in the subsequent iterations. This shows that the intelligent algorithm has learned a relatively stable unloading strategy in multiple trainings.

Select the other three baseline algorithms to compare with the DQN-based algorithm designed by the present invention, set the number of mobile users to change from 50 to 120, and the number of fixed edge servers to 5, as shown in Figure 3, and plot the average reward values of the four algorithms respectively Curves, in which the reward values used by the three baseline algorithms are all obtained by averaging 100 times.

It can be seen from the simulation curve that with the increase of the number of users, except for all local computing algorithms, the average reward values obtained by the other three algorithms all show a downward trend. This is because the number of edge servers set in this simulation is always 5, but the number of users is gradually increasing, so the server resources that users can share are gradually tight. For all local offloading algorithms, the average reward value is basically unchanged with the number of users. When the number of users is less than 90, the performance of all offloading algorithms is better than that of all local computing algorithms. This is because the server computing resources are relatively sufficient at this time, and As the number of users continues to increase, the performance of the full offload algorithm is worse than that of the full local computing algorithm.

As can be seen from the simulation curve in Figure 4, compared with the other three baseline algorithms, the DQN algorithm can always obtain lower task processing delays. Similar to the change trend of the reward value curve, when the number of users exceeds 90, the delay of the full offloading algorithm starts to exceed the delay of all local computing algorithms because the computing resources of the edge server are too tight.

The above calculation examples of the present invention are only to illustrate the calculation model and calculation process of the present invention in detail, but are not intended to limit the embodiments of the present invention. For those of ordinary skill in the art, on the basis of the above description, other different forms of changes or changes can also be made, and it is impossible to list all the implementations here. Obvious changes or modifications are still within the scope of the present invention.

Claims (3)

1. The unloading decision method in the moving edge calculation based on the deep Q learning is characterized by comprising the following steps:

step one, building a reinforcement learning model

Constructing a system state, a system action and a reward function in the Markov decision process according to the task characteristics;

the system state is constructed in the following manner:

denote the self task size of the mobile device m at the beginning of the current time slot t as λ _m (t), if there is a new task k (t) for the mobile device m when the current time slot t starts, λ _m (t) = k (t), otherwise λ _m (t)＝0，m＝1,2,…,M ₀ ，M ₀ Representing the total number of mobile devices;

constructing a local calculation queue, a task transmission queue and an edge node calculation queue, and representing the number of time slots of the self task of the mobile equipment m needing to wait in the local calculation queue when the current time slot t begins as the number of the time slots

The number of time slots that the task of the mobile device m needs to wait in the task transmission queue when the current time slot t begins is expressed as

Denote the queue length of mobile m at edge node n as

Constructing a matrix M (T) for representing the load level of each edge server in T time slots before the current time slot T, wherein the dimension of the M (T) is T multiplied by N, N is the number of the edge servers, and T is less than or equal to T ₀ ，T ₀ Representing the total time slot number;

the system state s observed by the mobile device m at the current time slot t _m (t) is:

the system action is represented as a (t) = {0,1,2, \8230;, N }, where 0 represents local computation, k =1,2, \8230; N, k represents the sequence number of the offloaded edge server;

the construction mode of the reward function is as follows:

if the task is decided to be calculated locally, the number of time slots for which the task waits

Comprises the following steps:

wherein,

indicating the time after the task generated at the time slot t' is executed locally;

energy required in the local calculation of a task

Comprises the following steps:

wherein epsilon _m Representing the CPU's coefficient of energy consumption during the local calculation of the mobile device m, i.e. the energy consumed by the local CPU for a cycle, d _m Representing the calculation amount of the currently generated task of the mobile device m, namely the number of CPU calculation cycles needed for executing the currently generated task;

setting preference coefficients of the mobile user m to time delay and energy consumption as

And

then the reward function for mobile user m in the offload decision process is:

wherein, R is the value of the reward function, T is the total time delay generated when the mobile user m is locally calculated, namely T is equal to the number of time slots of task queuing waiting

E is the total energy consumption generated by the mobile user m, i.e. the sum of the time delays generated during the local execution of the task

If the task is decided as the edge calculation, the time slot number of the task waiting is determined by the time after the execution of the edge server n is completed

Is calculated as the number of time slots the task waits

n＝1,2,…,n ₀ ，n ₀ Representing the total number of edge servers;

the energy required in task edge computing comprises two parts of task uploading and task execution, and the power of the mobile equipment when the task is uploaded is represented as p _up The power of the mobile device when a task is performed is denoted as p _e Then for mobile device m, the required energy

Comprises the following steps:

wherein, t _n,up Representing the time it takes for mobile device m to upload a task to edge server n, t _n,e Represents the time consumed by the mobile device m to perform a task in the edge server n;

at this time, the reward function of the user in the uninstalling decision process is:

wherein R is the value of the reward function, and T is the total time delay generated by task queuing

Time delay t generated by uploading task to edge server n _n,up And the time delay t generated by the execution of the task at the edge server n _n,e E is the total energy consumption resulting from the edge calculation, i.e.

If the maximum delay time allowed by the task is reached before the task is executed, the task is discarded, and the reward function value R at the moment is set as a fixed penalty value P;

step two, neural network construction

Constructing a neural network comprising an input layer, an LSTM layer, a first FC layer, a second FC layer and an output layer, wherein the input layer is used for transmitting system state information to the LSTM layer and the first FC layer and taking the output of the LSTM layer as the input of the first FC layer;

then taking the output of the first FC layer as the input of a second FC layer, and taking the output of the second FC layer as the input of an output layer;

the LSTM layer is used for predicting the time correlation of the load level of the edge server according to a matrix M (t);

the first FC layer and the second FC layer are used for learning the mapping of system states to system action reward function values, and each of the first FC layer and the second FC layer comprises a group of neurons with rectifying linear units.

2. The method for offloading decision making in moving edge computing based on deep Q learning of claim 1, wherein the output layer is configured to output the reward function value corresponding to the currently selected action adopted by the current system state.

3. The system for unloading decision in moving edge calculation based on deep Q learning is characterized in that the system is used for executing the method for unloading decision in moving edge calculation based on deep Q learning of claim 1 or claim 2.

Images