Yanfei He* and Zhenhua Tang*
Strategy for Task Offloading of Multi-user and Multi-server Based on Cost Optimization in Mobile Edge Computing Environment
Abstract: With the development of mobile edge computing, how to utilize the computing power of edge computing to effectively and efficiently offload data and to compute offloading is of great research value. This paper studies the computation offloading problem of multi-user and multi-server in mobile edge computing. Firstly, in order to minimize system energy consumption, the problem is modeled by considering the joint optimization of the offloading strategy and the wireless and computing resource allocation in a multi-user and multi-server scenario. Additionally, this paper explores the computation offloading scheme to optimize the overall cost. As the centralized optimization method is an NP problem, the game method is used to achieve effective computation offloading in a distributed manner. The decision problem of distributed computation offloading between the mobile equipment is modeled as a multi-user computation offloading game. There is a Nash equilibrium in this game, and it can be achieved by a limited number of iterations. Then, we propose a distributed computation offloading algorithm, which first calculates offloading weights, and then distributedly iterates by the time slot to update the computation offloading decision. Finally, the algorithm is verified by simulation experiments. Simulation results show that our proposed algorithm can achieve the balance by a limited number of iterations. At the same time, the algorithm outperforms several other advanced computation offloading algorithms in terms of the number of users and overall overheads for beneficial decision-making.
Keywords: Cost Optimization , Distributed Computing , Game Theory , Mobile Edge Computing , Multi MEC Servers , Nash Equilibrium , Task Offloading
1. Introduction
The technology of smartphones, tablet computers and other mobile terminal equipment has promoted the emergence of high transmission and processing rate for many services and applications, bringing severe challenges to network service providers. Although smartphones’ and other products’ CPU, battery capacity, software and hardware are constantly upgraded, they are still limited by the physical design, and cannot process applications requiring large-scale computing in a short time. This poses a challenge and yet offers an opportunity to stimulate the cloud computing technology; thus allowing terminal users to access and use cloud computing [1-3]. In mobile cloud computing (MCC), the mobile device (MD) can gain access to the remote centralized cloud computing and storage resources by using the core network and the Internet of mobile operators. MCC can directly and effectively improve the data storage capacity of users. At the same time, by offloading the computing tasks of applications to the cloud for processing, the computing load is reduced and the energy consumption is saved, conducive to extending the battery life of user terminal equipment [4]. Moreover, sufficient computing resources can provide the premise for the design, use and promotion of complex applications.
However, due to the long transmission distance between the MCC central cloud and users, available wireless channels are limited, which causes great pressure on the wireless transmission and the backhaul load of mobile network. In addition, due to the overload of the service center, the computing task queuing will increase the delay cost and the service cost. Therefore, performance requirements of the delaysensitive application cannot be met, and the quality of experience (QoE) cannot be guaranteed, resulting in huge profit loss to service providers.
In recent years, the number of wireless terminal devices is further increasing, and the demand for computing and terminal devices’ data is expected to witness an exponential growth in the next few years. The growth mainly comes from new applications, which need low latency and low energy services with intensive computing or a large amount of data, for instance, tactile interactive services that require responses within millisecond delay, Internet of Things (IOT), machine type communications (MTC), large-scale online games, virtual reality, augmented reality, etc. To avoid the high latency, it is worth considering to locate the cloud service near the user; thus, the mobile edge computing (MEC).
In MEC [5,6], the intermediate computing resources are introduced between the MD and the core cloud data center, which will address the problem of insufficient computing power for terminal devices [7,8]. These edge computing resources can be used to minimize the execution delay of computing tasks within the coverage, and provide enough computing resources for data processing through task unloading [9,10]. Thus, in the context of MEC, it is very important to propose an effective strategy for data offloading and computing offloading.
The innovations of the proposed strategy are summarized as follows:
1) Our proposed strategy point outs the problems and deficiencies in the existing research. Furthermore, the task execution time cost model and task execution energy consumption model are defined in a complex MEC network scenario.
2) In the proposed strategy, the offloading weights are calculated, and the offloading decision is iteratively as well as distributedly updated. Thus, the decision-making of mobile equipment users can be done within local iterations, and the real-time computing requirement for all users can be met at the same time.
2. Related Research
Research on MEC mainly focuses on offloading strategies and the optimization of network resource allocation in different network scenarios. In the network scenario of the multi-user and the single MEC server, Mao et al. [11] proposed a joint optimization strategy, which can optimize the computation delay and equipment energy consumption at the same time. Wang et al. [12] further realized the joint optimization of wireless and computing resources based on the binary offloading strategy in the single MEC server environment. The authors [13] solved the energy-efficient problem in the environment of the multi-user and the multi-MEC server. They divided the user-generated tasks into multiple sub-tasks and offloaded them in order to execute multiple computing nodes around.
Although some studies have paid attention to the problem of computing resource allocation in MEC systems, many early optimization methods and strategies have focused on the optimization of fixed computing resource allocation, and currently more is based on the new resource optimization technology DVFS for adjusting the CPU operating frequency [14]. Thinh et al. [15] studied a system scenario where a mobile equipment can offload computing tasks to multiple intervening nodes and can adjust its own CPU frequency, and proposed a joint optimization framework of offloading strategy and frequency adjustment. In the multi-user MEC environment, Zhang and Liu [16] proposed an offloading decision algorithm using the game theory, effectively minimizing the equipment’s total energy consumption within the computing delay constraints. In order to reduce the energy consumption of the mobile equipment and to ensure users’ task delay requirements, a task offloading decision algorithm based on the game theory was proposed. Tanzil et al. [17] minimized the execution delay of all tasks by allocating the computing resources of multiple MEC servers. Specifically, a service cluster was formed by cooperation. If the server performs a task for connecting other servers, it will offer this server a monetary reward. The server will first try to fulfil the task with the smallest communication delay. Only when the server is unable to process the task, will the task be transferred to other nearby servers for processing. In the scenario of a single mobile equipment with multiple access nodes, the task offloading strategy and mobile equipment frequency adjustment are jointly optimized by [18], which minimizes the total task execution delay and the total energy consumption.
However, many current studies on MEC ignore the characteristics of different tasks in a multi-user and multi-task environment, only a few works have noted this. Mao et al. [19] proposed a wireless resource management strategy for multi-user MEC system. Their strategy can minimize the weighted total energy consumption of the long-period wireless equipment. Huang et al. [20] discussed a multi-user oriented MEC task offloading algorithm using the deep Q-learning.
In summary, as a new network architecture paradigm, MEC helps to satisfy the growing demand for computing services and to achieve the collaborative optimization of network resources. It can reduce the system overheads and the task execution delay, and improve users’ quality of service (QoS). In addition, the delay minimization, the energy minimization and the trade-off delay energy are generally considered. For the participants, they are divided into the single-user oriented and the multi-user oriented. However, further research is still needed to explore how to efficiently perform computation offloading based on the trade-off between the delay and the energy according to the characteristics of different tasks in a multiuser and multi-task scenario.
In order to address the above problems, this paper focuses on the optimization of offloading strategies, aimed at reducing the overall system overheads in complex MEC network scenarios, and studies how to formulate a reasonable computation offloading strategy to offload mobile nodes’ own computing tasks to the edge server. We comprehensively consider various factors, for example, energy consumption, delay, cost, resource usage, contribution or profit of different types of tasks, and reduce the overall overheads of computation offloading. Furthermore, multi-users can efficiently offload computing in the game model. Therefore, in the environment of the multi-user and the multi-server MEC, this paper proposes a new task offloading algorithm considering the cost optimization.
3. Materials and Method
3.1 System Model
The overall system model based on the multi-user and the multi MEC server (MECs) is shown in Fig. 1. K MECs are represented as [TeX:] $$\boldsymbol{K}=\{1,2, \ldots, K\}.$$ The carrier of uplink communication is expressed as [TeX:] $$N= \{1,2, \ldots, N\},$$ and the bandwidth of each subcarrier is [TeX:] $$B_{N}.$$ Multiple mobile terminals are represented as [TeX:] $$I=\{1,2, \ldots, I\},$$ Each mobile terminal has a task request. [TeX:] $$A\left(D_{i}, \tau_{i}, X_{i}\right)$$ represents the task attribute; [TeX:] $$D_{i}$$ is the storage space occupied by the input data of the i-th task (unit: bit), [TeX:] $$\tau_{i}$$ is the calculation delay (unit: second), and [TeX:] $$X_{i}$$ is the computing power required to execute the i-th task.
[TeX:] $$f_{i, \text { loc }}$$ is used to represent the local CPU dominant frequency of the i-th mobile terminal. The maximum data transmission power of all mobile terminals is equal to [TeX:] $$P^{m} . f_{k, s e r}$$ is used to represent the CPU dominant frequency of the k-th MECs. [TeX:] $$\boldsymbol{W}=\left\{w_{i, n, k} \mid w_{i, n, k} \in\{0,1\}, i \in I, n \in N, k \in K\right\}$$ is used to represent the MECs allocation of subcarriers. Only when [TeX:] $$w_{i, n, k}=1,$$ the i-th mobile terminal can complete the task calculation on the k-th MECs with the help of subcarrier n. [TeX:] $$\boldsymbol{P}=\left\{P_{i, n, k} \mid P_{i, n, k} \in\left[0, P^{m}\right], i \in I, n \in N, k \in\right.K\}$$ is used to represent the power allocation of the subcarriers, and [TeX:] $$P_{i, n, k}$$ is the wireless data transmission power of the subcarriers between the i-th mobile terminal and the k-th MECs. [TeX:] $$\boldsymbol{G}=\left\{g_{i, n, k}, i \in I, n \in N, k \in\right.K\}$$ is used to represent all subcarrier channel gain sets, and [TeX:] $$g_{i, n, k}$$ represents the channel gain of subcarrier n between the i-th end user and the MECs. The noise of the proposed system obeys a Gaussian distribution [TeX:] $$\delta^{2}$$ with an expected value of 0.
3.2 Time Cost Model for Task Execution
Suppose that the total CPU cycles for completing the task is expressed as [TeX:] $$D_{i} X_{i}.$$ Since the task has been divided into two execution modes (local and offload), the time overheads are also divided into two situations for specific discussion [21,22]:
Time overhead of local execution
The local execution time cost depends on users' own computing power [TeX:] $$f_{i, l o c},$$ the local execution time cost can thus be expressed as
Time overhead of remote offload execution
When users offload tasks, the task needs to be transferred to the MEC server, and then to be processed by the CPU in servers. Thus, for offloading tasks, the execution time cost is divided into two parts: transmission and calculation:
(1) Time overhead of transmission process: Based on the OFDMA’s wireless transmission mechanism, due to the strict subcarrier allocation, the interference between users is ignored. The data transmission rate at which user [TeX:] $$\underline{i}$$ offloads the task to MEC server k can be expressed as:
(2)
[TeX:] $$R_{i, k}=B_{N} \sum_{n=1}^{N} w_{i, n, k} \log 2\left(1+\frac{P_{i, n, k} g_{i, n, k}}{\delta^{2}}\right)$$Consider that the data volume of computing tasks generated by users is relatively small, and the channel remains unchanged during the process of offloading tasks to MEC server. Therefore, the time overhead for user i to transfer tasks to MEC server is:
(2) Time overhead of calculation process: After receiving tasks offloaded by users, the MEC server will always allocate computing resources to execute tasks until the task is finally completed. In other words, only one computing task is executed at a time, and CPU resources will not be preempted by other tasks during the task execution. As only the idle MEC server will be used for the task scheduling and the execution, the queuing delay during the task offloading and the execution would not be considered. The time cost of executing task i in the MEC server depends on tasks’ computational complexity and the CPU frequency, and can be expressed as
In sum, the total time cost of executing task in the MEC server is
(5)
[TeX:] $$T_{i, k}^{r}=T_{i, k}^{t}+T_{i, k}^{c}=\frac{D_{i}}{R_{i, k}}+\frac{D_{i} X_{i}}{f_{k, s e r}}$$3.3 Energy Consumption Model for Task Execution
As the time-overhead model above, the energy consumption model is also separately discussed based on the mode of task execution.
Energy consumption of task local execution
Given the CPU frequency of tasks, the energy consumption of CPU per cycle can be expressed as [TeX:] $$k_{0} f_{i, l o c}^{2}, \text { where } k_{0}$$ is a constant related to the user equipment CPU. Thus, the energy consumption of task i executed locally can be expressed as
Energy consumption of task offloading remote execution
When the task is offloaded to MEC server for execution, it also includes the energy consumption of two processes. One is the transmission energy consumption of offloading tasks from the user to MEC server, and the second is the execution energy consumption of the tasks in MEC server. Since the output result is often much smaller than the input data after the task is executed, we ignore the downlink transmission energy consumption when calculation results from MEC server are returned to the user. The transmission energy offloaded from task i to MEC server k can be expressed as
Similar to the local execution of tasks, the calculated energy consumption of task i offloaded to MEC server k can be expressed as
where [TeX:] $$k_{1}$$ is a constant related to the k CPU of MEC server. In summary, the total energy consumption performed by i offloading to MEC server k can be expressed as
(9)
[TeX:] $$E_{i, k}^{r}=E_{i, k}^{t}+E_{i, k}^{c}=\sum_{n=1}^{N} w_{i n, k} p_{i, n, k} \frac{D_{i}}{R_{i, k}}+k_{1} f_{k, s e r}^{2} D_{i} X_{i}$$3.4 Task Offloading Weight Model based on Shapley Value
In actual applications, there is a trade-off between energy consumption and offloading delay. It is difficult to assign different tasks with varied task offloading weights through a unified definition. Thus, in this study, the offloading weight is calculated by the offloading weight model based on the Shapley value, and the offloading weight is calculated fairly with the rewards of different tasks. Shapley value is the solution concept in the cooperative game theory. As a fair standard, it is often used to distribute profits among multiple participants [23,24]. For each cooperative game, the unique distribution scheme generated by the alliance of all participants can be obtained by the calculation of Shapley value [25].
Suppose there are i participants in the complete set [TeX:] $$I=\left\{x_{1}, x_{2}, \ldots, x_{i}\right\},$$ and a subset [TeX:] $$S \subseteq I$$ formed by any number of people. [TeX:] $$v(S)$$ represents the value generated by the cooperation of elements included in subset. Function v is a characteristic function. Then the final value [TeX:] $$\psi_{n}(I, v)$$ is Shapley value.
Shapley value guarantees the fairness of distribution and has the following four characteristics:
1) Effectiveness: All values are allocated, namely [TeX:] $$\sum_{n \in I} \psi_{n}(I, v)-v(I).$$
2) Symmetry: If the positions of [TeX:] $$x_{n} \text { and } x_{m}$$ are equivalent (i.e., they can be substituted for each other), the benefits of the two should be the same, namely [TeX:] $$\psi_{n}(I, v)=\psi_{m}(I, v).$$
3) Pseudo-contribution: The income of non-contributors is 0.
4) Additivity: If the same batch of people completes two tasks, the benefits distribution of two tasks should be consistent with the results of separate distribution, i.e., [TeX:] $$\left(v_{1}+v_{2}\right)(s)=v_{1}(S)+v_{2}(S).$$
With proof, Shapley value is the only solution that satisfies the above four conditions [7,26]. Calculated by the following formula:
(10)
[TeX:] $$\psi_{n}(I, v)=\frac{1}{I !} \sum_{S \subseteq I\{n\}}|S| !(|I|-|S|-1)[v(S \cup n)-v(S)]$$Shapley value is in fact the average value of marginal contribution. For offloading computation, by measuring the profit generated by the contribution of tasks, offloading decisions can be more fairly and effectively made.
In the calculation model, [TeX:] $$\lambda_{i}^{t} \text { and } \lambda_{i}^{e}$$ are the tasks’ weights for calculating delay and energy consumption respectively, and they satisfy [TeX:] $$\lambda_{i}^{t}+\lambda_{i}^{e}=1.$$ For mobile node i, its multiple tasks can calculate Shapley value of multiple tasks by the rewards generated. The total profit [TeX:] $$v(I) \text { is } 1 . \text { Let } \lambda_{i}^{t}=\psi_{n}(I, v),$$ then [TeX:] $$\mid \lambda_{n}^{e}=1-\lambda_{i}^{t}.$$ With this kind of weight calculation method, the task with larger contribution has a greater weight on the delay, and is dominant in the offloading.
4. Game-based Computation Offloading Strategy
By the computation offloading model obtained above, the task offloading strategy in the multi-user and multi-task scenario is solved; thereby, turning the problem into a multi-user game problem and offering a computation offloading strategy.
4.1 Multi-user Game Model
4.1.1 Problem of beneficial computation offloading
The lower the data transmission rate i, the greater the energy consumption of wireless access and the longer the transmission time. In this case, the mobile equipment i prefers local computing tasks to avoid high energy consumption and high latency caused by data offloading. The following is a beneficial computation offloading.
Definition 1.When the offloading decision is fixed, compared with local computing, if the computing cost does not increase by using the edge server, the decision to choose mobile equipment i to offload to edge servers [TeX:] $$\left(\text { i.e., } a_{i}>0\right)$$ is beneficial [TeX:] $$\text { (i.e., } \left.K_{i}^{c}(a) \leq K_{i}^{m}\right) .$$
Based on beneficial computation offloading, a centralized problem-optimization algorithm is firstly designed according to the overall performance indicators of the mobile equipment. The problem can be modeled as follows:
(11)
[TeX:] $$\begin{aligned} \max \sum_{i \in N} L_{\left\{a_{i}>0\right\}} \\ \text { s.t. } K_{i}^{c}(a) \leq K_{i}^{m}, \forall a_{i}>0, i \in N \\ {i} \in\{0,1, \ldots, M\}, \forall i \in N \end{aligned}$$where [TeX:] $$L_{a_{i}>0}$$ is the indicator function. If [TeX:] $$a_{i}>0,$$ then [TeX:] $$L_{a_{i}>0}=1,$$ otherwise [TeX:] $$L_{a_{i}>0}=0.$$
However, the problem of finding the maximum number of the beneficial computation offloading equipment is an NP problem. This can be proved by being converted to the maximum cardinality binning problem. Given N objects, the size of object n is [TeX:] $$p_{n}.$$ M boxes are given at the same time, with the same capacity C. The problem is that loading objects into boxes generates the largest number of objects and does not exceed the capacity limit of boxes. The problem can be expressed as:
(12)
[TeX:] $$\begin{aligned} \max \sum_{n=1}^{N} \sum_{m=1}^{M} x_{n, m} \\ \text { s.t. } \sum_{n=1}^{N} p_{n} x_{n, m} \leq C, \forall m \in M, \\ \sum_{m=1}^{M} x_{n, m} \leq 1, \forall n \in N, \\ {n, m} \in\{0,1\}, \forall n \in N, m \in M \end{aligned}$$The above mentioned maximum cardinality binning problem has proved to be an NP problem. If the mobile equipment is considered as the object of the maximum cardinal packing problem and the channel is the box from the maximum cardinal packing problem, the weight of objects can be expressed as [TeX:] $$w_{n}=q_{i} g_{i, s}.$$ The capacity of the box can be expressed as the information rate of the channel. If mobile equipment i selects channel m, it can be assumed that the object i is packed in box m. The beneficial task offloading status can thus be expressed as the capacity limit of boxes. Therefore, the centralized optimization algorithm is also an NP problem.
4.1.2 Game model
Let [TeX:] $$a_{-i}=\left(a_{1}, \ldots, a_{i-1}, a_{i+1}, \ldots, a_{i}\right)$$ be the set of unloading decisions for all the equipment except equipment i. The equipment i will make its own unloading decisions according to [TeX:] $$a_{-i}.$$ Choose local calculation (i) or offloading calculation by wireless channel [TeX:] $$\left(a_{i}>0\right),$$ and minimize its overall overheads by the following formula:
(13)
[TeX:] $$\min _{a_{i} \in A_{i}\{0,1,,, M\}} Z_{i}\left(a_{1}, a_{i-1}\right), \forall i \in \boldsymbol{N}$$where [TeX:] $$Z_{i}\left(a_{1}, a_{i-1}\right)$$ is the overall cost of equipment i:
(14)
[TeX:] $$Z_{i}\left(a_{1}, a_{i-1}\right)=\left\{\begin{array}{ll} K_{i}^{m}, a_{i}=-1 \\ K_{i}^{s}(a), a_{i} \geq 0 \end{array}\right.$$Next, the above problem can be established as a game model with multi-users. [TeX:] $$\Phi=\left(\mathrm{N},\left\{A_{i}\right\}_{i \in N},\left\{Z_{i}\right\}_{i \in N}\right),$$ where N is the set of mobile equipment participating in the game, [TeX:] $$A_{i}$$ is the collection of participants’ strategies, and the total cost function [TeX:] $$Z_{i}\left(a_{1}, a_{i-1}\right)$$ is the cost function minimized by participant i. [TeX:] $$\Phi$$ is a game with multi-user attributes. Next, Nash equilibrium will be introduced in the game [27,28].
Definition 2. Strategy set [TeX:] $$a^{*}=\left(a_{1}^{*}, \ldots, a_{N}^{*}\right)$$ is a multi-user computing Nash equilibrium for offloading games. If there are no users in equilibrium [TeX:] $$a^{*}$$ , they can unilaterally change their strategy to further reduce their overall cost, namely:
(15)
[TeX:] $$Z_{i}\left(a_{i}^{*}, a_{-i}^{*}\right) \leq Z_{i}\left(a_{i}, a_{-i}^{*}\right), \forall a_{i} \in A_{i}, i \in N$$According to the Nash equilibrium concept, for a game with multi-user attributes, if equipment i is both in Nash equilibrium [TeX:] $$a_{i}^{*}$$ and chooses a cloud computing method [TeX:] $$\text { (i.e., } a_{i}>0 \text { ), }$$ an effective computation offloading strategy is necessary for equipment i [29].
4.2 Computation Offloading Algorithm
This algorithm enables the mobile equipment to realize mutually satisfactory computation offloading decisions before computing tasks are performed, achieving the Nash equilibrium after finite iterations by using the multi-user game model.
The clock signal of the wireless base station is used to synchronize the whole system, and the unloading decision is used to update the slot structure. Each time slot T consists of two steps:
(1) Receiving interference: if the i terminal device unloads to the edge server in the current time slot, it will send the pilot signal to the wireless base station S on its selected channel [TeX:] $$a_{i}(t).$$ Then, the wireless base station can measure the total received power [TeX:] $$\left.\rho_{m}\left(a_{i}(t)\right) \sum_{n \in \mathbf{m}: a_{n}(t)}=m q_{n} g_{n, s}\right).$$ and respond with the power information to the i-th mobile user. Thus, the i-th end user mobile device i can obtain the received interference of all users on all channels:
(16)
[TeX:] $$\mu_{n}\left(m, a_{-i}(t)\right)=\left\{\begin{array}{cc} \rho_{m}\left(a_{i}(t)\right)-q_{n} g_{n, s}, a_{i}(t)=m \\ \rho_{m} a_{i}(t), a_{i}(t) \neq m \end{array}\right.$$The interference of the current channel () is equal to the power received by equipment i minus its own power, and the interference of other channels are equal to the power received by equipment i.
(2) Offloading updating: As the Nash equilibrium can be achieved by finite iterations, the mobile equipment is allowed to make decision updates for iteration. Based on interference [TeX:] $$\left\{\rho_{m}\left(a_{i}(t), m \in M\right)\right\}$$ measured on different channels, the set of equipment i with the best response update is firstly calculated as:
(17)
[TeX:] $$\Delta_{i}(t) \triangleq\left\{\tilde{a}: \tilde{a}=\arg \min _{a_{i} \in A} Z_{i}\left(a, a_{-i}(t)\right), Z_{i}\left(\tilde{a}, a_{-i}(t)\right){i}\left(a_{i}(t), a_{-i}(t)\right)\right\}$$If [TeX:] $$\Delta_{i}(t) \neq \emptyset$$ means that the i terminal user can improve the decision, the i terminal user will send a decision update request to the wireless base station. If [TeX:] $$a_{i}(t)=0,$$ it means that the i-th end user continues to maintain the original unloading decision, i.e., [TeX:] $$a_{i}(t+1)=a_{i}(t).$$ The wireless base station randomly selects one of all the terminal users who send the update request, and sends the update permission to the terminal. The terminal will update the decision to [TeX:] $$a_{i}(t+1) \in \Delta_{i}(t)$$ in the next time slot. All the terminals that have not received the update permission shall maintain the original decision.
5. Simulation Results and Analysis
5.1 Simulation Scenarios and Parameter Settings
This section uses MATLAB simulation software to verify the performance of the algorithm proposed in this section, and compares it with algorithms proposed in reference [19] and reference [20]. The experiment is conducted on Win10 operating system with 8 G memory and Intel Core i7-8750H CPU @ 2.21 GHz. All simulation results are averaged over 500 independent simulations.
The system scenario is set in such a way that mobile users and MEC servers are randomly distributed in a circular area with a radius of 100 meters. The largescale channel fading model is [TeX:] $$P L=d_{i, k}^{-\theta},$$ where [TeX:] $$d_{i, k}$$ is the straight line distance between user i and MEC server k. The number of users is set to 30, and the number of MEC servers is set to 10. The Rayleigh fading is used as a small scale channel fading model. The constants [TeX:] $$k_{0} \text { and } k_{1}$$ for the local CPU and the MEC server CPU are set to [TeX:] $$k_{0}=1 \times 10^{-24}$$ [30] and [TeX:] $$k_{1}=1 \times 10^{-26}$$ [31], respectively. In addition, other simulation parameters can be found in Table 1 unless otherwise specified.
5.2 Simulation Results
By identifying the Nash equilibrium state, the convergence of the proposed algorithm is analyzed, as shown in Fig. 2. As can be seen from this figure, with the increase in the number of iterations, the energy consumption shows a linear decreasing trend. At the number of 30 iterations, the proposed algorithm can achieve the Nash equilibrium. In other words, it can converge after a finite number of iterations.
Table 1.
| MEC system parameters | Value |
|---|---|
| Subcarrier width | [TeX:] $$B_{N}=15 \mathrm{kHz}$$ |
| Background noise | [TeX:] $$\delta^{2}=-75 \mathrm{dBm}$$ |
| Maximum transmission power | [TeX:] $$P^{m}=600 \mathrm{~mW}$$ |
| Input data size | [TeX:] $$D_{i}=1000 \mathrm{bits}$$ |
| Task computational complexity | [TeX:] $$X_{i} \in[1000,1200] \text { cycles/bits }$$ |
| Task execution delay constraints | [TeX:] $$\tau_{i} \in[9,10] \mathrm{ms}$$ |
| User CPU frequency | [TeX:] $$f_{i, l o c} \in[0.6,0.7] \mathrm{GHz}$$ |
| MEC server frequency | [TeX:] $$f_{k, s e r} \in[1.1,1.2] \mathrm{GHz}$$ |
Fig. 3 evaluates the task execution cost, and compares our proposed algorithm with the algorithms in [19] and [20] under different conditions of noise power (background noises are -75, -80, -85, and -90 dBm, respectively); the relationship between task execution overheads and different amounts of task input data is illustrated.
Fig. 3 shows that the task execution cost of our proposed strategy and the algorithms proposed in [19] and [20] all increase with the amount of task input data. As the increase in the amount of input data increases task execution delay and increases task execution energy consumption, this in turn will increase the task execution overheads. Furthermore, the task execution cost of the proposed algorithm is better than the task execution cost of algorithms proposed in [19] and [20]. The reason is that the algorithms proposed in [19] and [20] aim to optimize the task execution delay, which may lead to higher task execution energy consumption and increase the task execution overheads. The algorithm proposed in this paper models the distributed computation offloading decision between the mobile equipment as a multiuser computation offloading game, achieving a balance between the user diversity and the MEC server diversity.
Fig. 4 demonstrates the relationship between task execution overheads and the computing power of MEC servers, and shows the comparison among the algorithms proposed in [19] and [20]. It can be seen from this figure that the task execution cost of our proposed algorithm as well as of [19] and [20] all decrease with the increase of the computing power for MEC servers. The reason is that increasing the computing power of MEC servers can improve the task execution performance and reduce task execution overheads. By comparing the curves obtained by the three algorithms, it is evident that our proposed algorithm is superior to the algorithms proposed in [19] and [20].
Fig. 3.
Fig. 5 compares the relationship between the algorithm task execution cost and the number of requested users of our proposed algorithm and the two proposed in [19] and [20]. As can be seen from this figure, as the number of requested users increases, the task execution overheads increase. Compared with other algorithms, the proposed algorithm has the lowest task execution cost. The reason is that the proposed algorithm offloads mobile node's own computing tasks to edge servers. It comprehensively considers several factors, for example, energy consumption, delay, cost, resource usage, contribution or profit of different types of tasks, and reduces the overall overheads of computation offloading. This allows multiusers to efficiently perform the computational offloading under the game model. The performance gap of each algorithm increases as the number of requested users increases. The reason is that when the number of requested users increases, the resource competition at MEC servers will cause the system performance to decrease.
The algorithm designed in this paper first calculates the unloading weight, and then the distributed time slot is iterated to update the unloading decision. In summary, our proposed algorithm can effectively increase the number of useful decision-making users, and can achieve the balance by a limited number of iterations. Under the Nash equilibrium, the final decision strategy shows self-stability. The user has no incentive to unilaterally change decisions, serving as a relatively stable final offloading decision plan for this period of time. At the same time, the proposed algorithm is superior to several other offloading algorithms in terms of the number of users and overall overheads for beneficial decision-making.
6. Conclusion
This paper discusses offloading strategies in a multi-user and multi-server scenario. In a resourceconstrained system, we propose a multi-user and multi-server MEC task offloading algorithm based on cost optimization. The algorithm is verified by simulation experiments, and simulation results show that our proposed algorithm has a good offloading performance. In terms of the number of users and overall overheads for beneficial decision-making, the algorithm is superior to several other computation offloading algorithms. Notwithstanding, there are still a few problems that need further discussion and optimization. This paper assesses the task offloading weight by calculating the reward of tasks. The weight is mainly used to investigate the decision of mobile equipment to calculate locally or offload to edge servers. There is hardly any study of the impact of offloading weight in the case of performing service migration when the edge server has insufficient computing power. Therefore, it is suggested that future work can address the issue of service migration, and discuss the impact of offloading weight during service migration.
References
- 1 Y. S. Jeong, J. H. Park, "Security, privacy, and efficiency of sustainable computing for future smart cities," Journal of Information Processing Systems, vol. 16, no. 1, pp. 1-5, 2020.custom:[[[-]]]
- 2 W. Liu, L. Zhang, Z. Zhang, C. Gu, C. Wang, M. O'neill, F. Lombardi, "XOR-based low-cost recon-figurable PUFs for IoT security," ACM Transactions on Embedded Computing Systems (TECS), vol. 18, no. 3, pp. 1-21, 2019.custom:[[[-]]]
- 3 V. Kumar, G. Sakya, C. Shankar, "WSN and IoT based smart city model using the MQTT protocol," Journal of Discrete Mathematical Sciences and Cryptography, vol. 22, no. 8, pp. 1423-1434, 2019.custom:[[[-]]]
- 4 W. Shi, X. Zhang, Y. Wang, Q. Zhang, "Edge computing: state-of-the-art and future directions," Journal of Computer Research and Development, vol. 56, no. 1, pp. 69-89, 2019.custom:[[[-]]]
- 5 E. Kim, S. Kim, "An efficient software defined data transmission scheme based on mobile edge computing for the massive IoT environment," KSII Transactions on Internet Information Systems, vol. 12, no. 2, pp. 974-987, 2018.doi:[[[10.3837/tiis.2018.02.027]]]
- 6 T. Quack, M. Bosinger, F. J. Heßeler, D. Abel, "Infrastructure-based digital maps for connected autonomous vehicles," at-Automatisierungstechnik, vol. 66, no. 2, pp. 183-191, 2018.doi:[[[10.1515/auto-2017-0100]]]
- 7 M. C. Filippou, D. Sabella, V. Riccobene, "Flexible MEC service consumption through edge host zoning in 5G networks," in Proceedings of 2019 IEEE Wireless Communications and Networking Conference Workshop (WCNCW), Marrakech, Morocco, 2019;pp. 1-6. custom:[[[-]]]
- 8 K. Kanai, K. Imagane, J. Katto, "Overview of multimedia mobile edge computing," ITE Transactions on Media Technology and Applications, vol. 6, no. 1, pp. 46-52, 2018.custom:[[[-]]]
- 9 M. Li, F. R. Y u, P. Si, Y. Zhang, "Green machine-to-machine communications with mobile edge computing and wireless network virtualization," IEEE Communications Magazine, vol. 56, no. 5, pp. 148-154, 2018.doi:[[[10.1109/MCOM.2018.1601005]]]
- 10 Q. Fan, N. Ansari, "Application aware workload allocation for edge computing-based IoT," IEEE Internet of Things Journal, vol. 5, no. 3, pp. 2146-2153, 2018.doi:[[[10.1109/JIOT.2018.2826006]]]
- 11 Y. Mao, J. Zhang, K. B. Letaief, "Joint task offloading scheduling and transmit power allocation for mobile-edge computing systems," in Proceedings of 2017 IEEE Wireless Communications and Networking Conference (WCNC), San Francisco, CA, 2017;pp. 1-6. custom:[[[-]]]
- 12 C. Wang, F. R. Y u, C. Liang, Q. Chen, L. Tang, "Joint computation offloading and interference management in wireless cellular networks with mobile edge computing," IEEE Transactions on V ehicular Technology, vol. 66, no. 8, pp. 7432-7445, 2017.doi:[[[10.1109/TVT.2017.2672701]]]
- 13 A. De La Oliva, X. C. Perez, A. Azcorra, A. Di Giglio, F. Cavaliere, D. Tiegelbekkers, et al., "Xhaul: toward an integrated fronthaul/backhaul architecture in 5G networks," IEEE Wireless Communications, vol. 22, no. 5, pp. 32-40, 2015.doi:[[[10.1109/MWC.2015.7306535]]]
- 14 J. Liu, Q. Zhang, "Offloading schemes in mobile edge computing for ultra-reliable low latency communications," IEEE Access, vol. 6, pp. 12825-12837, 2018.doi:[[[10.1109/ACCESS.2018.2800032]]]
- 15 Q. D. Thinh, J. Tang, D. La Quang, T. Q. Quek, "Adaptive computation scaling and task offloading in mobile edge computing," in Proceedings of 2017 IEEE Wireless Communications and Networking Conference (WCNC), San Francisco, CA, 2017;pp. 1-6. custom:[[[-]]]
- 16 G. Zhang, X. Liu, "Tasks split and offloading scheduling decision in mobile edge computing with limited resources," Computer Applications and Software, vol. 36, no. 10, pp. 268-278, 2019.custom:[[[-]]]
- 17 S. S. Tanzil, O. N. Gharehshiran, V. Krishnamurthy, "Femto-cloud formation: a coalitional game-theoretic approach," in Proceedings of 2015 IEEE Global Communications Conference (GLOBECOM), San Diego, CA, 2015;pp. 1-6. custom:[[[-]]]
- 18 T. Q. Dinh, J. Tang, Q. D. La, T. Q. Quek, "Offloading in mobile edge computing: task allocation and computational frequency scaling," IEEE Transactions on Communications, vol. 65, no. 8, pp. 3571-3584, 2017.doi:[[[10.1109/TCOMM.2017.2699660]]]
- 19 Y. Mao, J. Zhang, S. H. Song, K. B. Letaief, "Stochastic joint radio and computational resource management for multi-user mobile-edge computing systems," IEEE Transactions on Wireless Communi-cations, vol. 16, no. 9, pp. 5994-6009, 2017.doi:[[[10.1109/TWC.2017.2717986]]]
- 20 L. Huang, X. Feng, C. Zhang, L. Qian, Y. Wu, "Deep reinforcement learning-based joint task offloading and bandwidth allocation for multi-user mobile edge computing," Digital Communications and Networks, vol. 5, no. 1, pp. 10-17, 2019.custom:[[[-]]]
- 21 Y. Wei, Z. Zhang, F. R. Y u, Z. Han, "Joint user scheduling and content caching strategy for mobile edge networks using deep reinforcement learning," in Proceedings of 2018 IEEE International Conference on Communications Workshops (ICC Workshops), Kansas City, MO, 2018;pp. 1-6. custom:[[[-]]]
- 22 B. Bi, Y. J. Zhang, "Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading," IEEE Transactions on Wireless Communications, vol. 17, no. 6, pp. 4177-4190, 2018.doi:[[[10.1109/TWC.2018.2821664]]]
- 23 I. Dragan, "Egalitarian allocations and the inverse problem for the Shapley value," American Journal of Operations Research, vol. 8, no. 6, 2018.custom:[[[-]]]
- 24 W. Y ang, J. Liu, X. Liu, "Existence of fuzzy Zhou bargaining sets in TU fuzzy games," International Journal of Fuzzy System Applications (IJFSA), vol. 7, no. 1, pp. 46-55, 2018.doi:[[[10.4018/IJFSA.2018010104]]]
- 25 S. Sasikala, S. A. alias Balamurugan, S. Geetha, "n efficient feature selection paradigm using PCA-CFS-Shapley values ensemble applied to small medical data sets," in Proceedings of 2013 4th International Conference on Computing, Communications and Networking Technologies (ICCCNT), Tiruchengode, India, 2013;pp. 1-5. custom:[[[-]]]
- 26 M. Gusev, S. Dustdar, "Going back to the roots: the evolution of edge computing, an iot per-spective," IEEE Internet Computing, vol. 22, no. 2, pp. 5-15, 2018.custom:[[[-]]]
- 27 J. Xu, Z. K. Yang, W. Y uan, "Heterogeneous channel assignment of multi-radio multi-channel wireless networks: a game theoretic approach," Journal of Chinese Computer Systems, vol. 33, no. 5, pp. 1053-1056, 2012.custom:[[[-]]]
- 28 Z. Huo, X. Li, S. Jin, Z. Wang, "Nash equilibrium of an energy saving strategy with dual rate transmission in wireless regional area network," Wireless Communications and Mobile Computing, vol. 2017, no. 9053862, 2017.doi:[[[10.1155//9053862]]]
- 29 Y. Yang, Y. Li, W. Zhang, F. Qin, P. Zhu, C. X. Wang, "Generative-adversarial-network-based wireless channel modeling: challenges and opportunities," IEEE Communications Magazine, vol. 57, no. 3, pp. 22-27, 2019.custom:[[[-]]]
- 30 K. De V ogeleer, G. Memmi, P. Jouvelot, F. Coelho, "The energy/frequency convexity rule: modeling and experimental validation on mobile devices," in Parallel Processing and Applied Mathematics. HeidelbergGermany: Springer, pp. 793-803, 2013.custom:[[[-]]]
- 31 F. Wang, J. Xu, X. Wang, S. Cui, "Joint offloading and computing optimization in wireless powered mobile-edge computing systems," IEEE Transactions on Wireless Communications, vol. 17, no. 3, pp. 1784-1797, 2018.doi:[[[10.1109/TWC.2017.2785305]]]