Energy-efficient allocation for multiple tasks in mobile edge computing

Mobile edge computing (MEC) allows a mobile device to offload tasks to the nearby server for remote execution to enhance the performance of user equipment. A major challenge of MEC is to design an efficient algorithm for task allocation. In contrast to previous work on MEC, which mainly focuses on single-task allocation for a mobile device with only one task to be completed, this paper considers a mobile device with multiple tasks or an application with multiple tasks. This assumption does not hold in real settings because a mobile device may have multiple tasks waiting to execute. We address the problem of task allocation with minimum total energy consumption considering multi-task settings in MEC, in which a mobile device has one or more tasks. We consider the binary computation offloading mode and formulate multi-task allocation as an integer programming problem that is strongly NP-hard. We propose an approximation algorithm and show it is a polynomial-time approximation scheme that saves the maximum energy. Therefore, our proposed algorithm achieves a tradeoff between optimality loss and time complexity. We analyze the performance of the proposed algorithm by performing extensive experiments. The results of the experiments demonstrate that our proposed approximation algorithm is capable of finding near-optimal solutions, and achieves a good balance of speed and quality.

With the rapid development of the smartphone and the Internet of Things, mobile applications such as facial recognition, natural language processing, mobile social media, vehicular systems, and interactive gaming require extensive computing power and abundant energy. However, mobile devices generally have limited computing power and battery life, and cannot meet the demands of such tasks. Cloud computing, such as Amazon Web Services and Microsoft Azure, has many hardware resources, but usually cannot provide latency-sensitive quality of service at scale. Sitting at the edge of the internet, the edge cloud can provide service with lower latency than cloud computing and more powerful hardware than mobile devices, thereby enhancing the user experience [1, 2]. Mobile devices can reduce their computing time by offloading tasks to nearby servers for processing at the network edge[3]. Mobile edge computing (MEC) solves the problem of running resource-intensive applications with the limited capability of mobile devices [4]. However, unlike cloud computing, with its abundant hardware resources, the MEC server with limited resources sometimes cannot satisfy the requirements of all mobile devices. In this study, we consider task allocation in MEC and minimize the total energy consumption, which is the sum of the local energy consumption and the remote energy consumption.

Research on MEC has focused on one mobile device with one task. This assumption may not fit well for MEC in a realistic environment, for two reasons. First, a mobile device may have multiple tasks waiting to execute at the same time, such as interactive gaming and speech communication, where the first is resource-intensive and the second is latency-sensitive. Second, a mobile application always has the main task and other small tasks. For example, a user identification application may include a facial recognition task and some processing tasks. Therefore, it is necessary to consider multi-task allocation in MEC. Unfortunately, no algorithms have been designed to consider this problem in the existing literature. Motivated by this scenario, we consider in this paper the multi-task allocation setting. We assume a mobile device can offload at most one task for remote execution, such as a resource-hungry task, while other tasks execute locally to meet latency and reduce energy consumption. It is to ensure fairness so that each mobile device has the opportunity to upload one resource-hungry task for remote execution. By considering multi-task allocation, the remote resources of an MEC server and local resources of mobile devices can be utilized effectively to execute more tasks and significantly reduce total energy consumption.

We consider the binary computation offloading mode, in which a task cannot be partitioned, and is either locally executed or completely offloaded to the MEC server [5]. Some tasks can execute successfully as a whole locally or on an MEC server, and some cannot be divided into smaller units. If some mobile devices transmit data at the same time, this operation may cause wireless interference with each other, thereby increasing transmission delay and energy loss. Hence, we consider limited frequency subchannels, i.e., only a certain number of mobile devices are allowed to transmit data at the same time to improve transmission efficiency and save energy consumption. In addition, a latency-intensive task must be finished before its deadline, so we also consider the deadline constraints. However, the multi-task allocation problem cannot be modeled by any knapsack problem. Unfortunately, there are no existing algorithms to consider binary computation offloading mode, limited frequency subchannels, and deadline constraints. Thus, existing algorithms cannot be directly applied to the multi-task allocation problem. The multi-task allocation problem without deadline constraints can be considered as a multiple-choice knapsack problem with cardinality constraints. It is the integer programming problem that is strongly NP-hard, and there is no fully polynomial time approximation scheme (FPTAS) for solving it, unless \(P=NP\) [6]. Obtaining the optimal allocation is computationally difficult; hence, designing an efficient algorithm to solve the multi-task allocation problem is of major interest.

In this paper, we address the problem of multi-task allocation in mobile edge computing (MAMEC). We believe this is the first study to design a PTAS algorithm for multi-task allocation in MEC. The key contributions of this paper are summarized as follows.

• A multi-task allocation environment is introduced, where each mobile device with one or more tasks can offload at most one resource-intensive task to an MEC server for remote execution. This goes beyond the bulk of the current research, which primarily addresses the problem of one task per mobile device.

• We model the problem of multi-task allocation in an accurate mathematical model. By considering the binary computation offloading mode and limited frequency subchannels, the MAMEC problem is an integer programming problem that is strongly NP-hard. In the absence of computationally tractable optimal algorithms to solve this problem, we design an efficient allocation algorithm to obtain the near-optimal solutions, whose key property is to consider mobile devices with one or more tasks, which is the case in a real MEC setting. We show our proposed approximation algorithm is a polynomial time approximation scheme (PTAS), which is by far the strongest approximation result that can be achieved for this problem, unless \(P=NP\).

• Extensive experiments investigate the performance of our proposed approximation algorithm compared to the optimal solutions. The results show that our proposed algorithm can find near-optimal solutions and achieve a good balance of speed and quality.

Related Work

Early research mainly focused on a single device or single user. Cheng et al. [7] considered the code offloading problem and proposed a heuristic algorithm based on the Genetic Algorithm. Zhang et al. [8] considered the collaborative task execution problem and proposed the algorithms to obtain the optimal and approximation solutions. Munoz et al. [9] presented a general framework to optimize communication and computational resources usage. Zhang et al. [10] proposed the particle swarm optimization algorithm to schedule the tasks. However, only a single mobile device was taken into consideration in the above works.

Recently, researchers investigated task allocation among multiple devices [11,12,13]. Some works focused on equilibrium [14, 15]. Pu et al. [16] formulated an online task offloading problem and proposed a framework based on network-assisted device-to-device collaboration. Some works considered the Nash equilibrium [17, 18]. Chen et al. [17] proposed a decentralized computation offloading mechanism. Chen et al. [18] proposed a game-theoretic approach for task offloading. Liu et al. [19] proposed a multi-resource allocation approach. Lyu et al. [20] proposed asymptotically optimal offloading schedules based on Lyapunov optimization techniques. Lyu et al. [21] considered the task admission and resource allocation problem. Wang et al. [22] considered an MEC server with a base station and proposed a joint optimization allocation problem. Chen et al. [23] designed software defined task offloading for the task offloading problem. Chen et al. [24] considered the joint task scheduling and energy management problem in heterogeneous MEC. Wang et al. [25] considered the real-time online resource allocation problem. Zhang et al. [26] formulated the computing resource management as profit maximization problems. Park et al. [27] considered the multi-type users with different computation task sizes and provided the framework for MEC-enabled heterogeneous networks. Liu et al. [28] considered task allocation with many-to-one mapping in crowd sensing systems. However, some of the above works did not consider limited frequency subchannels, nor multi-task allocation.

Researchers approached the problem of multiple users or multiple tasks [29,30,31]. Elgendy et al. [32] considered the security layer in the MEC and proposed the linearization and binary relaxation approaches. Chen et al. [33] considered the MEC system consisting of multiple mobile devices and one server. Huang et al. [34] considered the network’s quality of service and proposed the algorithm based on a linear programming relaxation. Chen et al. [35] considered a renewable mobile edge cloud system and proposed centralized and distributed greedy scheduling algorithms. However, they did not consider limited frequency subchannels or deadline constraints. Our work is different from all previous works. In this paper, we consider multi-task allocation with binary computation offloading mode and limited frequency subchannels and design an approximation algorithm to solve the MAMEC problem. Table 1 summarizes the differences between the existing works.

Organization

The remainder of this paper is organized as follows. Section 2 describes the system model. Section 3 introduces our approximation algorithm and characterizes its properties. Section 4 evaluates the performance of the algorithm. Section 5 summarizes the results.

System Model

The MEC system consists of an access point (AP) and the MEC server, where the AP and the MEC server are connected using high-throughput optical fiber. Hence, the transmission delay between them can be ignored [37]. We assume that the mobile devices associated with the AP by non-orthogonal multiple access (NOMA) protocol. NOMA enables all the mobile devices to simultaneously offload their tasks so that offloading throughput can be improved. We assume the MEC system can support up to K mobile devices to transmit data at the same time. We assume each mobile device can offload at most one task to increase wireless access efficiency. We consider a set of collocated mobile devices, \({\mathcal {N}}=\{1,...,N\}\), where mobile device \(i\in {\mathcal {N}}\) has some latency- or computing-intensive tasks to be completed. Let \({\mathcal {T}}_i\) be the set of tasks of mobile device \(i\in {\mathcal {N}}\). Note that one mobile device can have one or more tasks (\(\vert {\mathcal {T}}_i \vert \ge 1\)). We assume task \(t_{ij}\in {\mathcal {T}}_i\) needs to be completed before deadline \(runtime_{ij}^{req}\).

We first consider a task computed locally. Let \(b_{ij}\) be the required number of CPU cycles to accomplish task \(t_{ij}\). The information of \(b_{ij}\) can be obtained by applying program profiler [38]. Let \(f_{i}^l\) be the local computational capability of mobile device \(i\in {\mathcal {N}}\) in cycles per second, and \(runtime_{ij}^l\) the time consumed to locally process task \(t_{ij}\),

where \(d_{ij}^l\) is the number of local CPU cycles assigned to task \(t_{ij}\) in each second. Note that \(d_{ij}^l\) is unknown and is decided by the allocation algorithm. For example, we assume a task \(t_{ij}\) needs 100 CPU cycles to meet the deadline. If the algorithm allocates \(d_{ij}^l=200\) CPU cycles to task \(t_{ij}\), it can finish in a shorter time. However, if the algorithm allocates \(d_{ij}^l=50\), it cannot finish by the deadline.

The energy consumption of each CPU cycle can be denoted by \(\kappa (f_i^l)^2\), where \(\kappa\) is the energy coefficient [17]. Let \(E_{ij}^l\) be the energy consumption of task \(t_{ij}\) locally calculated [39],

where \(\kappa =10^{-28}\) [22].

Second, we consider remote computing. Let \(h_i\) be the channel gain between the AP and mobile device i (\(\forall i\in {\mathcal {N}}\)). We assume that the mobile device will not move too much while uploading tasks. Hence, \(h_i\) is a constant [36]. The uplink data rate of mobile device i (\(\forall i\in {\mathcal {N}}\)) can be given by [30]

where B is the channel bandwidth, \(\rho _i\) is the transmission power of the mobile device, and \(\amalg\) is the indicator function which takes the value 1 if its argument is correct and takes the zero value, otherwise.

Let \(runtime_{ij}^{tra}\) be the transmission duration of task \(t_{ij}\), as given by

where \(size_{ij}\) is the data size of task \(t_{ij}\). The remote processing duration \(runtime_{ij}^{pro}\) can be defined as:

where \(d_{ij}^r\) is the number of remote CPU cycles assigned to task \(t_{ij}\) in each second. Since the data size of the result is generally small compared to the raw data [17, 22], we neglect the downlink transmission delay. Hence, the total time duration on MEC server can be defined as:

If task \(t_{ij}\) is offloaded to the MEC server for remote execution, the energy consumption is only calculated for transmission energy consumption. Then, the transmission energy consumption of a mobile device to send \(size_{ij}\) bits to the MEC server can be defined as:

Without loss of generality, we assume \(b_{ij}>0\), \(size_{ij}>0\) and \(f^l_{i}>0\), \(\forall i\in {\mathcal {N}}, j\in {\mathcal {T}}_i\). The symbols used in this paper are summarized in Table 2.

Mathematical Formulation

The integer programming formulation of the MAMEC problem (called IP-MAMEC) can be formulated as follows:

The decision variable is defined as \(x_{ij}=1\) if task \(t_{ij}\) is processed on the MEC server, and 0 if it is processed locally. The objective (1) is to minimize total energy consumption. Constraints (2) guarantee that the time duration does not exceed the deadline. Constraints (3) guarantee that the allocation capacity does not exceed the available capacity for each mobile device. Constraints (4) guarantee that the allocation capacity does not exceed the available capacity for the MEC server. Constraints (5) guarantee that at most K mobile devices can be served by the AP. Constraints (6) guarantee that at most one task from each mobile device can be offered to the MEC server. Constraints (7) guarantee that the obtained computational resources are nonnegative. Constraints (8) represent the integrality requirements for the decision variable.

High-level view of MAMEC of four mobile devices

Full size image

Figure 1 shows how multi-task allocation works in the MAMEC problem. In this scenario, we consider four mobile devices with multiple tasks. For example, mobile devices 1, 2, 3, and 4 have two tasks, three tasks, one task, and two tasks, respectively. We assume that the AP serves at most three mobile devices simultaneously by the NOMA protocol. To reduce energy consumption, tasks \(t_{11}\), \(t_{22}\), and \(t_{42}\) are offloaded to the MEC server, and tasks \(t_{12}\), \(t_{21}\), \(t_{23}\), \(t_{31}\), and \(t_{41}\) execute on mobile devices.

In this section, we introduce our allocation algorithm for the MAMEC problem, called PTAS-MAMEC. The PTAS-MAMEC algorithm is summarized in Algorithm 1. The algorithm is run periodically by the MEC server. PTAS-MAMEC has three phases: collecting task requests, resource allocation, and offloading decision. In the collecting task requests phase, it collects the task requests from mobile devices (line 2). Then, it initializes the total energy consumption V and the allocation vector \(\mathbf {X}\) (line 3).

PTAS-MAMEC

Full size image

In the resource allocation phase, PTAS-MAMEC allocates the remote computational resources and selects tasks that must be offered for remote processing. To guarantee the deadline constraints and minimize energy consumption, PTAS-MAMEC sets \(d_{ij}^r\) and \(d_{ij}^l\), \(\forall i\in {\mathcal {N}}, j\in {{\mathcal {T}}_i}\) as the minimum requirements to meet task deadlines (lines 5-7). That is, task \(t_{ij}\) can be finished before the deadline when it obtains resources not less than \(d_{ij}^l\) or \(d_{ij}^r\) for local or remote execution, respectively. To make more tasks satisfy deadline constraints, it sorts the mobile devices in non-decreasing of order of \(d_{ij'}^l\), \(\forall i\in {\mathcal {N}}\), \(j'=argmax_{j\in {\mathcal {T}}_i}d_{ij}^l\) (line 8). Then, it considers each mobile device by turns. If the resources of a mobile device cannot meet all demands, then PTAS-MAMEC selects a task to offload to minimize energy consumption (lines 11-13), and updates the resources and the allocation vector (lines 14-18).

In the offloading decision phase, PTAS-MAMEC calls the PTAS-ALLOC algorithm to determine the allocation (lines 20-25). Idle resources may remain on the MEC server; these can be allocated to offloading tasks to hasten execution. PTAS-MAMEC allocates these resources equally to offloading tasks (lines 26-28). Finally, it returns the allocation result (line 29).

PTAS-ALLOC(\({\mathcal {N}}\),\(\mathbf {d}\),f,K,\(\epsilon\))

Full size image

PTAS-ALLOC: Allocation Algorithm of PTAS-MAMEC

We define “energy-saving” before describing the allocation algorithm. Let \(E_{ij}^s\) be energy-saving, where \(E_{ij}^s=E_{ij}^l-E_{ij}^r,\forall i\in {\mathcal {N}}, j\in {\mathcal {T}}_i\). Note that the required local or remote resources were known in the previous phase, so we only consider the offloading tasks that we choose. Then, we turn the minimum problem into a maximum problem, and the maximum energy-saving can be obtained by the following linear programming:

Our proposed PTAS allocation algorithm, called PTAS-ALLOC, is given in Algorithm 2. Our approximation technique is inspired by Caprara et al. [40] and Dobzinski et al. [41]. However, the former did not consider one user with multiple value settings, and the latter did not consider cardinality constraints. Then, we refer to the partial allocation idea [40] and the rounding idea [41] to design an approximation algorithm suitable for the MAMEC problem. Parameter \(\epsilon\) controls how close the solution determined by PTAS-ALLOC is to the optimal solution. PTAS-ALLOC has one output parameter, the allocation vector, \(\mathbf {X}\). PTAS-ALLOC has three phases: initialization, partial allocation, and approximation allocation.

The main idea is to find a partial allocation and then allocate through dynamic programming. In the initialization phase, PTAS-ALLOC defines parameter q, the number of tasks in the partial allocation (line 2). In partial allocation, if more tasks are considered, the quality of the obtained solution is better, but it takes more time. When q equals the total number of tasks, the algorithm searches all feasible allocations and obtains the optimal one, but the algorithm is computationally infeasible.

In the partial allocation phase, PTAS-ALLOC considers the subset \({\mathcal {Q}}\), where the number of \({\mathcal {Q}}\) is at most \(q-1\). PTAS-ALLOC iteratively considers the tasks of subset \({\mathcal {Q}}\) executed on the MEC server and other tasks executed locally, and confirms that these do not exceed the resource constraints (lines 6-9). Then, it finds the allocation that is the maximum energy-saving (lines 10-11). Note that PTAS-ALLOC searches all space in this progress; hence, it obtains the optimal solution for subset \({\mathcal {Q}}\), where the number of \({\mathcal {Q}}\) is at most \(q-1\).

In the approximation allocation phase, PTAS-ALLOC iterates over all subsets \({\mathcal {Q}}\) of q tasks (lines 13-34). Unlike the second phase, PTAS-ALLOC considers not just the tasks of the set \({\mathcal {Q}}\) but the other tasks. For each subset, if its tasks can execute remotely and this is a feasible partial allocation, then the remaining resources are divided into \((K-q)^2\) parts, each of size \(\hat{f}_{r}/(K-q)^2\). Then, PTAS-ALLOC rounds the number of required resources by the unallocated tasks, i.e., \(\hat{d}_{ij}^r=\lceil {d^r_{ij}(K-q)^2}/{\hat{f}^r}\rceil\) (lines 19-20), and uses the dynamic programming approach to obtain an allocation.

We now describe the dynamic programming approach to find an optimal allocation for the rounded required resources (lines 21-28). We consider the subproblem \(v_{i}(k,c)\), which includes the first i mobile devices with available subchannels k and the available capacity c in such a way that \(v_{i}(k,c)\) is the optimal value of the subproblem. The dynamic programming recurrence can be defined as:

The recurrence considers two cases, local execution and the selection of at most one task for remote execution. The value \(v_{i-1}(k,c)\) means all tasks of mobile device i execute locally, and the value \(max_{j\in {\mathcal {T}}_i}(v_{i-1}(k-1,c-\hat{d}_{ij}^r)+E^s_{ij})\) means selecting one task to offload. The value \(v_{i}(k,c)\) is the maximum between them, and then it is an optimal value. When the final value \(v_{N}(K-q,(K-q)^2)\) is found, PTAS-ALLOC saves the maximum allocation (lines 30-34). PTAS-ALLOC finds \({\mathbf {x}}\) by looking backward at \(v_{N}(K-q,(K-q)^2)\), as follows. If \(v_{i}(k,c)=v_{i-1}(k,c)\), then the tasks of mobile device i execute locally, and PTAS-ALLOC recursively works backward from \(v_{i-1}(k,c)\). Otherwise, PTAS-ALLOC finds task \(t_{ij}\) satisfying \(v_{i}(k,c)=v_{i-1}(k-1,c-\hat{d}_{ij}^r)+E^s_{ij}\), which means task \(t_{ij}\) is offloaded to the MEC server. Then, PTAS-ALLOC recursively works backward from \(v_{i-1}(k-1,c-\hat{d}_{ij}^r)\). Finally, PTAS-ALLOC returns the best allocation (line 35).

Properties

Theorem 1

The approximation of PTAS-ALLOC is \(1-\epsilon\).

Proof

Without loss of generality, let OPT be the optimal value, and V the value generated by PTAS-ALLOC. If no more than q tasks are offered to remotely process in the optimal solution, then V is optimal, where \(q=min\{\lceil 1/\epsilon \rceil -1,K\}\), because PTAS-ALLOC considers all subsets \({\mathcal {Q}}\) of at most \(q-1\) tasks in step 2 of PTAS-ALLOC.

Otherwise, let \(\{t_{i^*_1j^*_{i_1}},t_{i^*_2j^*_{i_2}},...,t_{i^*_qj^*_{i_q}},...\}\) be the set of tasks in an optimal solution ordered so that \(E_{i^*_1j^*_{i_1}}^s\ge E_{i^*_2j^*_{i_2}}^s\ge ...\ge E_{i^*_qj^*_{i_q}}^s\ge ...\). In one iteration of step 3 of PTAS-ALLOC, the algorithm considers sets \({\mathcal {Q}^*}=\{t_{i^*_1j^*_{i_1}},t_{i^*_2j^*_{i_2}},...,t_{i^*_qj^*_{i_q}}\}\) and \({\mathcal {S}^*}=\sum _{i\in {\mathcal {N}}}\cup {\mathcal {T}}_i\setminus {\mathcal {Q}^*}\). Let \(OPT_{S^*}\) be the optimal value for \({\mathcal {S}^*}\). Then

The remaining resources of the MEC server can be allocated to speed up execution. Without loss of generality, we assume that all its resources are allocated in the optimal allocation. Let \(l=\sum _{t_{i^*j^*}\in {{\mathcal {Q}^*}}}d^r_{i^*j^*}\). Let \(t_{i^*_kj^*_{i_k}}\notin {\mathcal {Q}^*}\) be the task that obtains the most resources. Then

Let \(V_{S^*}\) be the value generated by PTAS-ALLOC for \({\mathcal {S}^*}\). PTAS-ALLOC searches all subsets \({\mathcal {Q}}\) when \(|{\mathcal {Q}}|=q\), so it certainly searches the set \({\mathcal {Q}^*}\). We then have

For each task \(t_{ij}\in {\mathcal {S}^*}\), we round up \(d_{ij}^r\) to the nearest multiple of \(\frac{f^r-l}{(K-q)^2}\) in PTAS-ALLOC. The rounding procedure increases the number of required resources of unallocated tasks. The algorithm selects at most \(K-q\) tasks; hence, it adds at most \((K-q)\cdot \frac{f^r-l}{(K-q)^2}=\frac{f^r-l}{K-q}\) resources by rounding up.

This may lead to an infeasible allocation of required resources based on the new rounded sizes. According to (10), the resources obtained by task \(t_{i^*_kj^*_{i_k}}\) are more than the most that PTAS-ALLOC adds. To make the allocation feasible, we can remove task \(t_{i^*_kj^*_{i_k}}\) such that it satisfies capacity constraints while decreasing the objective function. Note that PTAS-ALLOC obtains the best solution by removing task \(t_{i^*_kj^*_{i_k}}\). Thus, we have

In the previous phase, the tasks were sorted in decreasing order of energy-saving, and we have

We also have:

where the first inequality follows from (11) and (14); and the third equation follows from (9).

Clearly, then,

where the first inequality follows from (12); the second inequality follows from (13); the third equation follows from (9); and the fourth inequality follows from (15).

Theorem 2

The time complexity of PTAS-ALLOC is \(O(T^{q}(K-q)^3)\), where T is the number of tasks.

Proof

The exhaustive search to find a partial allocation is based on the total number of allocations of q tasks which is \(\sum _{i=1}^q(_i^T)\le T^q\). The time complexity of the approximation allocation is \(O(T^{q}(K-q)^3)\). Therefore, the time complexity of PTAS-ALLOC is \(O(T^{q}(K-q)^3)\).◻

Definition 1

PTAS [36] A maximization problem has a PTAS if for every instance I and for every \(\epsilon\), it finds a solution V for I in time polynomial in the size of I that satisfies \(V(I)\ge (1-\epsilon )V^*(I)\), where \(V^*(I)\) it the optimal value of a solution for I.

Theorem 3

The PTAS-ALLOC algorithm is a PTAS.

Proof

The solution obtained by PTAS-ALLOC is in a \((1-\epsilon )\) neighborhood of the optimal (Theorem 1), and the time complexity of PTAS-ALLOC is polynomial in T (Theorem 2). Therefore, PTAS-ALLOC is PTAS.◻

Theorem 4

The time complexity of PTAS-MAMEC is \(O(T^{q}(K-q)^3)\), where T is the number of tasks.

Proof

PTAS-MAMEC needs \(O(T^2)\) to allocate resources in step 2. Then, PTAS-MAMEC calls PTAS-ALLOC to determine the allocation in step 3. Therefore, the time complexity of PTAS-MAMEC is \(O(T^{q}(K-q)^3)\).◻

In this section, we compare the PTAS-MAMEC algorithm to the All Request Admission Algorithm (ARAA) [21] and the optimal solution obtained by the B &B algorithm [42]. Note that the MEC system accepts all requests and randomly discards more than K tasks [21]. If solving an optimal solution that is not feasible, we ignore the constraints (2) in the optimal solution. The experimental platform environment uses \(C\#\) in Visual Studio 2013. All the simulations were run on a machine with Intel CPU i5 2.8 GHz and 16 GB memory.

PTAS-MAMEC versus B&B & ARAA: a Total energy consumption; b Execution time; c Average percentage of satisfied tasks (*B &B was not able to determine the allocation ranging from 23 to 25 mobile devices in feasible time, and thus, there are no bars in the plots for those cases)

Full size image

PTAS-MAMEC versus B&B & ARAA: a Average energy consumption per device; b Average runtime per task; c Computational resource utilization (*see note in Fig. 2)

Full size image

Experimental Setup

We assume that mobile devices are uniformly distributed in a cell with radius 250 m [21]. The transmission bandwidth B and transmitting power \(\rho\) of a mobile device are 20 MHz and 0.5 W [36], respectively. We assume the wireless channel gain of mobile device \(i\in {\mathcal {N}}\) is \(h_i=127+30*\log w_i\), where \(w_i\) is the distance between mobile device i and the AP [36]. We assume that the AP serves at most \(K=15\) mobile devices simultaneously, and the deadline of task \(runtime^{req}\), in seconds, is uniformly distributed over [1, 1.5] [21].

Each mobile device has a set of tasks to execute, with a maximum of three per device. The parameters used in the simulation are summarized in Table 3. We average over 1000 simulations to obtain data points and eliminate randomness.

Performance of Different Numbers of Mobile Devices

We compare the performance of PTAS-MAMEC, B &B and ARAA for different number of mobile devices, ranging from 15 to 25. For PTAS-MAMEC, the selected \(\epsilon\) values are 0.4, 0.5, corresponding to q equalling 2, 1, respectively. Note that parameter \(\epsilon\) depends only on the accuracy of the solution, not on the specific actual problem. Figure 2a shows the total energy consumption obtained by these algorithms. We can see that the total energy consumption obtained by PTAS-MAMEC is very close to the optimal solution. Note that PTAS-MAMEC with smaller \(\epsilon\) can find better solutions. This is because PTAS-MAMEC with smaller \(\epsilon\) will search more partial allocations to obtain better solutions. Then, PTAS-MAMEC with smaller \(\epsilon\) spends more time. The main idea of ARAA is to select some tasks at random; thus, it obtains the maximum total energy consumption. This gap is amazing given the fact that our proposed PTAS-MAMEC performs very well.

Figure 2b shows the execution times of the algorithms on a logarithmic scale. The ARAA algorithm randomly selects tasks, and then it is very fast and there are no bars in the plots for it. The results show that the execution time increases with the number of mobile devices. We observe that PTAS-MAMEC with \(\epsilon =0.5\) is the fastest, and it spends much less time than B &B. This is because the complexity of PTAS-MAMEC depends on the number of tasks, and the execution time of PTAS-MAMEC is polynomial in the number of tasks. According to the results of Fig. 2a and 2b, PTAS-MAMEC with \(\epsilon =0.5\) can obtain the near-optimal solutions very quickly; thus, it is beneficial for MEC to use this algorithm rather than PTAS-MAMEC with \(\epsilon =0.4\).

Figure 2c shows the average percentage of satisfied tasks. We see that this is less for B &B than for PTAS-MAMEC, because the objective of B &B is to find the minimum total energy consumption without considering deadlines. Obviously, almost all tasks satisfy deadlines when allocated by PTAS-MAMEC. This is can conclude that PTAS-MAMEC not only finds the near optimal solutions but also considers the deadline constraints.

PTAS-MAMEC versus B&B & ARAA (different deadline instances): a Total energy consumption; b Average percentage of satisfied tasks

Full size image

PTAS-MAMEC versus B&B & ARAA (different deadline instances): a Average percentage of offloading tasks; b Computational resource utilization

Full size image

Figure 3a shows the average energy consumption per device. The results show that the average energy consumption per device increases as the number of devices increases. We observe that B &B has the minimum energy consumption per device, which is consistent with obtaining minimum total energy consumption. Obviously, the average energy consumption per device obtained by B &B and PTAS-MAMEC are fairly similar. From this, we can conclude that PTAS-MAMEC can reduce energy consumption and save the battery power of mobile devices.

Figure 3b shows the average runtime per task. The results show that the average runtime per task increases as the number of mobile devices increases. Note that for PTAS-MAMEC, this is longer for \(\epsilon =0.4\) than for \(\epsilon =0.5\). This is because, to minimize total energy consumption, with \(\epsilon =0.4\), just enough resources are allocated to tasks to meet their deadlines.

Figure 3c shows the utilization of computational resources of mobile devices. ARAA obtains the highest resource utilization because it selects offloading tasks at random, without considering the demand. PTAS-MAMEC with \(\epsilon =0.5\) has higher utilization than PTAS-MAMEC with \(\epsilon =0.4\) and B &B, but they are very close. This can conclude that PTAS-MAMEC can better utilize resources.

Performance of Different Deadlines

We evaluate the performance of algorithms for different deadlines. The number of mobile devices is 20, and the deadline ranges from 0.8 s to 1.5 s. Figure 4a shows the total energy consumption obtained by the algorithms. The results show that the total energy consumption decreases as the deadline increases. The required resources decrease as the deadline increases. That is, tasks need more resources and consume more energy when the deadline is shorter. We observe that the total energy consumption obtained by PTAS-MAMEC is more than that of B &B when the deadline is less than 1.3 s, and PTAS-MAMEC obtains the near-optimal solutions in other cases. This is because PTAS-MAMEC tries to satisfy demands to increase energy consumption (see Fig. 4b), and B &B has the objective to minimize total energy consumption while ignoring the deadline constraints.

PTAS-MAMEC versus B&B & ARAA with different numbers of required tasks: a Total energy consumption; b Average percentage of satisfied tasks

Full size image

PTAS-MAMEC versus B&B & ARAA with different numbers of required tasks: a Average runtime per task; b Average energy consumption per device

Full size image

Figure 4b shows the average percentage of satisfied tasks. The results show that the number of satisfied tasks increases as the deadline increases. Note that the average percentage of satisfied tasks obtained by PTAS-MAMEC is greater than that of B &B and ARAA. All tasks execute successfully in PTAS-MAMEC when the deadline is more than 1.2 s, while the percentages of satisfied tasks obtained by B &B and ARAA are less than \(100\%\) when the deadline is 1.5 s. This is because PTAS-MAMEC can effectively increase the number of satisfied tasks.

Figure 5a shows the average percentage of offloading tasks. The result shows that the average percentage of offloading tasks increases as the deadline increases. Figure 5b shows the utilization of computational resources of mobile devices. The results show that the utilization of computational resources decreases as the deadline increases. This is because the loose deadline leads to fewer demands. From this experiment, we can observe that PTAS-MAMEC performs well in latency-sensitive environments.

Performance of Different Numbers of Required Tasks

We evaluate the performance of PTAS-MAMEC for different number of required tasks. We assume the maximum number of tasks of each mobile device ranges from 1 to 5, and the number of mobile devices is 20. Figure 6a shows the total energy consumption obtained by the algorithms. We observe that the gap between optimal and approximate solutions obtained by PTAS-MAMEC increases with the number of tasks. However, this gap is very small. This can conclude that PTAS-MAMEC performs very well.

PTAS-MAMEC versus B&B over time: a Total energy consumption; b Execution time; c Average energy consumption per device

Full size image

Figure 6b shows the average percentage of satisfied tasks. The results show the number of satisfied tasks decreases as the number of required tasks increases. We observe that the percentage of satisfied tasks obtained by PTAS-MAMEC is larger than that of B &B and ARAA. Note that PTAS-MAMEC can meet almost all tasks when the number of required tasks is less than 3, while B &B and ARAA cannot. According to Fig. 6a and 6b, we can see that PTAS-MAMEC not only obtains the near-optimal solutions but meets more demands.

Figure 7a shows the average runtime per task. Figure 7b shows the average energy consumption per device. The results show that the average runtime per task and the average energy consumption per device increase as the number of required tasks increases. We observe that the average runtime and energy consumption obtained by PTAS-MAMEC are very close to the optimal solutions. This can conclude that PTAS-MAMEC can efficiently use resources to save energy and serve more tasks. From this experiment, we can observe that PTAS-MAMEC performs well regardless of task properties.

Performance Over Time

We evaluate the performance of algorithms over a period of 24 hours. This simulation runs using between 15 and 22 mobile devices that dynamically arrive each hour. Figure 8a shows the total energy consumption by these algorithms. We observe that PTAS-MAMEC obtains the near-optimal solutions and the optimality gap is very small in all cases. Figure 8b shows the execution times of these algorithms. The results show that PTAS-MAMEC with \(\epsilon =0.5\) is fast, and B &B spends too much time on calculations. This can conclude that PTAS-MAMEC with \(\epsilon =0.5\) provides quality service in a shorter response time and can increase customer satisfaction. Figure 8c shows the average energy consumption per device. PTAS-MAMEC obtains near-optimal solutions, and we can conclude that it is effective at reducing energy consumption and improving mobile device performance.

From all of the above results, we can observe that PTAS-MAMEC not only finds the near-optimal solutions but also the execution time only depends on the number of tasks and the selected \(\epsilon\). In addition, PTAS-MAMEC performs very well in different environments. As a result, we can conclude that PTAS-MAMEC is a good candidate for deployment on the current MEC.

We address the problem of multi-task allocation in mobile edge computing Since the MAMEC problem is computationally difficult, we proposed an approximation algorithm using a dynamic programming approach. In addition, we analyzed the approximation ratio of our proposed algorithm and showed it is a polynomial time approximation scheme. Therefore, it achieves the tradeoff between optimality loss and time complexity. The objective of our proposed algorithm is to minimize total energy consumption on the premise that tasks can be completed before deadlines. Experimental results demonstrated that the proposed algorithm obtained the near-optimal solutions while meeting deadlines. Designing better algorithms is the focus of our next research.

The datasets used or analysed during the current study are available from the corresponding author on reasonable request.

MEC:

Mobile edge computing

PTAS:

Polynomial time approximation scheme

MAMEC:

Multi-task allocation in mobile edge computing

AP:

Access point

NOMA:

Non-orthogonal multiple access

The authors would like to thank all peer reviewers for their good comments.

This work was supported in part by the Chinese Natural Science Foundation under Grant 11361048, in part by the Yunnan Natural Science Foundation under Grant 2017FH001-014, in part by the Yunnan Science Foundation under Grant 2019J0613, and in part by the Qujing Normal University Science Foundation under Grant ZDKC2016002.

Authors and Affiliations

1. Institute of Applied Mathematics, Qujing Normal University, Qujing, China

   Jun Liu

2. School of Information Engineering, Qujing Normal University, Qujing, China

   Xi Liu

Contributions

Xi Liu and Jun Liu have written this paper and have done the research which supports it. Jun Liu helped with the revision and gave instructional suggestions regarding experiments and writing. All authors read and approved the final manuscript.

Authors’ information

Jun Liu received the B.E. degree in department of mathematics, from Yunnan University in 1993. He is currently a professor with the Department of CInstitute of Applied Mathematics of Qujing Normal University. His main research interests include cloud computing and distributed systems. Xi Liu received the Ph.D. degree in department of the School of Information Science & Engineering, from Yunnan University in 2018. He is currently with the Qujing Normal University. His main research interests include big data, cloud computing, mobile computing, and edge computing.

Corresponding author

Correspondence to Xi Liu.

Competing interests

The authors declare there is no conflicts of interest regarding the publication of this paper.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Reprints and permissions