A computing allocation strategy for Internet of things’ resources based on edge computing

Network model

The edge computing load balancing problem first considers the computing load balancing problem in the data analysis application scenario of IoT devices in the large-scale cloud edge collaborative network. The large-scale cloud edge collaborative network architecture scenario is shown in Figure 1. The main research content is that the huge amount of data generated by underlying IoT devices is transmitted and processed by wireless and wired networks, and finally converged to the cloud data center for big data analysis and processing. Large-scale intelligent networks, such as smart homes and smart cities, need to analyze the data collected by IoT device nodes to complete corresponding intelligent processing. The centralized processing solution of traditional cloud data center cannot meet the existing big data processing needs. The massive amount of data generated by the huge amount of IoT devices poses a huge challenge to the transmission capacity of backhaul link and the processing capacity of core network. Thus, on one hand, it is necessary to take advantage of the nearby services of edge nodes to meet the low-latency requirements of IoT applications. On the other hand, collaboration between edge nodes and cloud data centers is needed to cope with the arrival of intensive data, disperse the pressure of data processing, which can ensure the normal operation of network.

OPEN IN VIEWER

Figure 1.

Large-scale edge cloud collaborative network architecture.

Figure 1 shows the system model of problem being studied. The system can be a three-tier architecture (i.e. including three types of nodes), from the bottom to top: IoT devices, edge nodes, and cloud data centers. The underlying IoT devices will generate a large number of tasks that require big data analysis and processing, which are transmitted to the corresponding edge server nodes via wireless links, and then converge upward to the uppermost cloud data center node for centralized big data analysis and processing. The edge server nodes in the middle—such as base stations, WI-FI access points, switches, routers, and gateways—are connected by wires to form an edge cloud. Edge noders have abundant computing resources. When transmitting the data generated by underlying IoT devices, it can use its own computing resources to preprocess the data, and transmit the preprocessing results to the cloud data center. In the process of data processing and transmission, multiple edge nodes can process and transmit data in a collaborative manner.

The set of cloud data centers and edge nodes in the network is N = { 0 , 1 , . . . , N } , where 0 represents the cloud data centers, and 1 to N represent the edge nodes. The set of IoT devices is M = { 0 , 1 , . . . , M } , and the set of IoT devices connected to edge server i is M i . The system runs according to the time sequence, and the unit time sequence length is denoted as T .

Calculation model

Based on the definition of network model in the previous section, suppose i represents the user terminal i , where i ∈ { 0 , 1 , . . . , N } . j represents the edge node j , where j ∈ { 0 , 1 , . . . , N } . When j = 0 , specifically refers to the user terminal itself. Each user can migrate a computing task to a designated edge node, and the edge node can allocate bandwidth and computing resources for migration tasks. On the basis of sharing bandwidth and computing resources, this article assumes that each task is an independent execution unit, without considering the relevance of tasks. When multiple users have tasks that need to be calculated, first determine the maximum allowable delay of tasks and the time for local calculation. If the local calculation time is greater than the maximum allowable delay. A task migration request will be sent, and the task data size D i that needs to be calculated will be sent to the edge node. The edge node synchronizes the user’s information in edge cloud and generates a task table as follows

F ij = { x ij , λ ij , β ij , D i , T i tol }

(1)

where x ij indicates whether the computing task is executed locally or is being migrated; λ ij indicates the percentage of bandwidth allocated by edge node j to user i . β ij represents the percentage of computing resources allocated by edge node j to user i , and T i tol represents the maximum allowable delay of user terminal i .

The edge node updates and maintains the above-mentioned task table synchronously under edge cloud. This synchronization only needs to update the table information after each edge node makes a task migration decision, and broadcast it to all edge nodes under the same edge cloud. Therefore, the total task set F can be obtained from the table generated by all tasks

F = { F ij | i ∈ { 1 , 2 , … , N } , j ∈ { 1 , 2 , … , M } }

(2)

The total task set F will be formed at all edge nodes in edge cloud. Based on the total task set F , this article can get the migration decision of all tasks, and then calculate the corresponding processing cost of each task.

Local execution

When the local calculation time is less than the maximum allowable delay of user i , the task is executed by local calculation. The local execution delay of task i is only related to the processing power of local CPU. Thus, the local calculation delay of task i is

T ij l = ( 1 − x ij ) D i β ij f i l

(3)

where β ij represents the percentage of CPU allocated to task i by local users; f i l represents the computing power of local users. Therefore, the energy consumption during local calculation of task i is

E ij l = p i l T ij l

(4)

where p i l represents the calculated power of local user i .

Combined with the local calculation delay formula and corresponding energy consumption formula, the total cost of local calculation can be expressed as

C ij l = α T ij l + ( 1 − α ) E ij l

(5)

where α and 1 − α respectively represent the weight of time and energy cost of task i , α ∈ [ 0 , 1 ] . Since each user’s task weight may be different, different tasks should be assigned different weights according to task types. When the task is a delay-sensitive task, increase the value of weight α appropriately. When the task is energy-sensitive, reduce the value of weight α appropriately. The specific initialization value can be selected according to a large number of experiments.

Migration execution

When the local calculation time of user task i is greater than its maximum allowable delay, user i chooses to execute tasks through calculation migration, that is, when x ij = 1 or j ≥ 1 . The entire migration process can be divided into five steps. First, if the task of user i needs to be migrated, a data migration request is sent to edge cloud. Second, the edge node obtains the optimal migration decision according to the request and sends it to user i . Subsequently, user i uploads the data to be processed to designated edge node j by the wireless access network or cellular mobile network, and edge node j allocates corresponding bandwidth to it. After that, edge node j allocates corresponding computing resources to process user i tasks. Finally, edge node j returns the execution result of tasks to user i .

Because each user migrates to a different edge node with different uplink and downlink rates, suppose the uplink rate of task i to be migrated to edge node j is as follows

V ij up = λ ij B j log ( P i up | H i | N 0 Γ ( g up ) d ( i , j ) ξ )

(6)

where B j represents the bandwidth of edge node j ; P i up represents the transmission power of data uploaded by user i . H i represents the channel gain of user i in the wireless channel; N 0 represents the noise power of channel. g up represents the target bit error rate, and Γ ( g up ) represents the signal-to-noise ratio margin introduced to meet the uplink target bit error rate. d ( i , j ) represents the distance between user i and edge node j ; ξ represents the loss index of transmission channel path.

Assuming that the downlink and uplink have the same channel environment and noise, the downlink rate can be expressed as

V ij do = λ ij B j log ( P i do | H i | N 0 Γ ( g do ) d ( i , j ) ξ )

(7)

According to the above steps, the transmission delay of user i uploading computing tasks to edge node j in migration calculation can be expressed as

T ij t u = x ij D i V ij up

(8)

According to the transmission delay, the corresponding transmission energy consumption can be obtained

E ij t u = p i up T ij t u

(9)

where p i up is the uplink transmission power of user i in unit time.

When the data are transmitted to edge node, CPU resources allocated to the task by edge node are used for calculation, and the calculation time of tasks for user i on edge node j can be obtained as

T ij e = x i j ( D i β ij f j e )

(10)

where f j e represents the computing power of edge node j , and β ij represents the percentage of computing resources allocated by edge node j to user i .

When edge node j completes the task of user i , it returns the calculation result to user i , where the transmission delay for edge node j to send the result to user i is

T ij t d = x i j ( D ij o V ij do )

(11)

where D ij o is the size of data returned by edge node j to calculation results.

Based on the transmission delay of edge node j sending the result to user i , this article can obtain the corresponding receiving energy consumption of user i

E ij t d = p ij do T ij t d

(12)

where p ij do is the downlink transmission power of user i in unit time.

Combining equations (8), (10), and (11), we can get the total delay of execution process of user task i migration to edge node j as

T ij total = T ij t u + T ij e + T ij t d

(13)

Therefore, it can be obtained that in the process of user task i migration to edge node j , the local waiting energy consumption of user i is

E ij w = p i w T ij total

(14)

where p i w is the power of devices for user i in the waiting state.

Combining equations (9), (12), and (14), it can be obtained that the total energy consumption of user side in the process of migrating task i to edge node j is

E ij total = E ij t u + E ij t d + E ij w

(15)

Finally, combined with the total delay and total energy consumption during the execution of task migration for user i to edge node j , namely, equations (13) and (15), the total cost of migration process can be obtained as

C ij total = α T ij total + ( 1 − α ) E ij total

(16)

where α and 1 − α respectively represent the weight of time and energy cost of edge node processing tasks and α ∈ [ 0 , 1 ] . Similar to the above, since each edge node processing task weight may be different, the specific initialization value of weight can be selected according to a large number of experiments.

Optimization problem description

Latency and energy consumption are the two core indicators for measuring network performance. The optimization objectives of this article are mainly focused on the completion time and energy consumption of all tasks at user level. The specific optimization goal is to minimize the weighted sum of task execution delay and energy consumption of all users, that is, the total cost C . The way is to realize through joint optimization of migration decision, bandwidth allocation, and computing resource allocation, in which tasks can be executed locally or migrated. The specific optimization problem is constructed as follows

min C = min ∑ j = 0 M ∑ i = 1 N z ij [ ( 1 − x ij ) C ij l + x ij C ij total ]

(17)

s.t.

( 1 − x ij ) T ij l + x ij T ij total ≤ T i tol

(17a)

∑ i N z ij λ ij ≤ 1 , ∀ j ∈ { 0 , 1 , … , M }

(17b)

∑ i N z ij β ij ≤ 1 , ∀ j ∈ { 0 , 1 , … , M }

(17c)

z ij ∈ { 0 , 1 }

(17d)

In the above optimization problem, the objective function (17) is to minimize the sum of weights for completion time of all tasks and the energy consumption of user side, expressed by the total cost C. Constraint (17a) indicates that neither the delay caused by local computing nor the delay caused by migration computing can be greater than the maximum delay that the user can tolerate for task execution. Constraint (17b) indicates that the sum of bandwidth proportions allocated by node j to each task must be less than or equal to 1, that is, the sum of bandwidth occupied by all user tasks migrated to edge node is less than or equal to the maximum bandwidth of edge node. The same is true for bandwidth allocation for local users. Similarly, constraint (17c) indicates that the sum of CPU proportions of all tasks migrated to edge nodes (or executed locally) is less than or equal to 1. Constraint (17d) represents the value constraint of variable z ij , when z ij = 0 indicates that task i did not select node j for calculation. When z ij = 1 represents task i , node j is selected to perform the calculation.

Reinforcement learning

Reinforcement learning is an important branch of machine learning. In this branch, the agent learns how to get the maximum reward through interaction with environment. Unlike supervised learning, reinforcement learning cannot learn from samples provided by experienced external supervisors. On the contrary, it must learn from its own experience, even though it faces greater uncertainty in environment. The definition of reinforcement learning is not to describe learning methods, but to describe learning problems. Besides, method suitable for solving this problem can be considered as a reinforcement learning method. A reinforcement learning problem generally includes the following elements:

Reinforcement learning problem can usually be described as the optimal control of Markov Decision Process (MDP), but it is not necessary to know the state space, transition probability, and reward function. Thus, reinforcement learning is very effective in dealing with complex problems in the real world. An MDP consists of a finite number of states, actions, and rewards, which can be expressed as

x 0 , a 0 , r 1 , x 1 , a 1 , r 2 , x 2 , a 2 , r 3 , … , x n − 1 , a n − 1 , r n

(18)

where x j represents the state, a j represents the action, and r j + 1 represents the reward after action is taken. When the state reaches the preset end state x n , an MDP ends.

Reinforcement learning has two outstanding features: trial and error search and delayed reward. Trial and error search means a trade-off between exploration and exploitation. Agents prefer to use effective actions they have tried in the past to generate rewards. But it must also explore new and better actions that may generate higher returns in the future. The agent must try a variety of actions, and gradually favor those that get the most rewards. Another feature of reinforcement learning is that the agent must not only consider the immediate reward, but also the long-term accumulated reward, that is, the value function.

Generally speaking, depending on whether the environmental elements (i.e. state transition probability and reward function) are known, reinforcement learning can be divided into model-free reinforcement learning and model-based reinforcement learning. Model-free reinforcement learning has recently been successfully applied to deep neural networks. It can directly input the original state into the deep neural network to learn more difficult task strategies. In contrast, model-based reinforcement learning learns the system model with the help of supervised learning, and optimizes the strategy under this model. In recent years, model-based reinforcement learning elements have been incorporated into model-free deep reinforcement learning to increase the learning speed without losing advantages of model-free learning. Q-learning algorithm is one of the widely used model-free reinforcement learning algorithms. The Q-function is defined as the state-action value function, usually expressed as Q π ( x , a ) , that is, after action a is executed in state x , the value function of strategy n is continued to be executed. The most important part of Q-learning algorithm is the correct and effective method of estimating the value of Q-function. The Q-function can be implemented by a lookup table or a function approximator, and sometimes, it can be a non-linear approximator, such as a neural network, or a more complex deep neural network.Q-learning algorithm combined with deep neural network is deep Q-learning algorithm.

Dynamic offloading scheduling algorithm based on Q-learning

Under normal circumstances, due to the dynamic changes of network environment, conventional dynamic programming algorithms or model-based algorithms cannot effectively solve such optimization problems without prior knowledge of environment. Because the agent cannot predict the next state of environment before acting. Thus, this article uses this model-free reinforcement learning method to study the problem of offloading optimization.

Q-learning algorithm is a very classic model-free, offline strategy reinforcement learning algorithm. The core of Q-learning algorithm lies in Q-table. The rows and columns of Q-table are composed of states and actions, namely, the state set S and action set A . The value of each state-action group in Q-table is the action value function Q ( s t , a t ) , which is expressed as the expected value of long-term cumulative reward. The offloading scheduler calculates Q ( s t , a t ) and stores it in Q-table. According to the Bellman optimal equation, the update formula of Q ( s t , a t ) is

Q ( s t , a t ) = ( 1 − μ ) Q ( s t , a t ) + μ ( U ( s t , a t ) + γ max Q ( s t + 1 , a t + 1 ) )

(19)

where μ represents the learning rate, which is a constant that satisfies 0 < µ ≤ 1. Generally, the value of learning rate μ determines the speed of learning convergence. The larger the value of μ , the faster the convergence speed. But if the value is set too much, the algorithm will converge to the local optimal solution, so the value of μ needs to be set reasonably. γ represents the discount factor, and its value range is γ ∈ ( 0 , 1 ] . The smaller the value of γ , it means that the offloading scheduler mainly considers the current instantaneous reward. If the value of γ is larger, it means that the offloading scheduling also pays attention to future rewards.

In the process of learning and training of Q-learning algorithm, in order to prevent falling into the local optimal solution, ε-greedy strategy is used to learnQ-table. The ε-greedy strategy is a balance between exploration and utilization. Exploration is to randomly select actions, that is, randomly select an offloading strategy for task k among local computing, edge nodes and cloud servers. Exploring the effects of unknown actions is conducive to updating the action value function. The utilization is based on the action corresponding to greedy maximum Q-value of the current state. For ε-greedy strategy, every time an attempt is made to select an action, the probability of ε is used to randomly explore, that is, the action that maximizes action value function is selected with a probability of 1 − ε .

Since offloading optimization is considered in a dynamic network environment, it is necessary to determine which one or more tasks can be executed at the same time in the time slot t . Through the data dependency between tasks acquired in the initial stage and completed task set in the state s t of each time slot t , the task scheduling process in dynamic environment as shown in Figure 2 can be given.

OPEN IN VIEWER

Figure 2.

Task scheduling process in dynamic scenario.

Based on Figure 2, this article gives the specific steps of task scheduling in a dynamic environment: