Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing

Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge... This paper studies a single-user Mobile Edge Computing (MEC) system where mobile device (MD) includes an application consisting of multiple computation components or tasks with dependencies. MD can offload part of each computation-intensive latency-sensitive task to the AP integrated with MEC server. In order to accomplish the application faultlessly, we calculate out the optimal task offloading strategy in a time-division manner for a predetermined execution order under the constraints of limited computation and communication resources. The problem is formulated as an optimization problem that can minimize the energy consumption of mobile device while satisfying the constraints of computation tasks and mobile device resources. The optimization problem is equivalently transformed into solving a nonlinear equation with a linear inequality constraint by leveraging the Lagrange Multiplier method. And the proposed dual Bi-Section Search algorithm Bi-JOTD can efficiently solve the nonlinear equation. In the outer Bi-Section Search, the proposed algorithm searches for the optimal Lagrangian multiplier variable between the lower and upper boundaries. The inner Bi-Section Search achieves the Lagrangian multiplier vector corresponding to a given variable receiving from the outer layer. Numerical results demonstrate that the proposed algorithm has significant performance improvement than other baselines. The novel scheme not only reduces the difficulty of problem solving, but also obtains less energy consumption and better performance. Keywords: Mobile edge computing, computation offloading, task dependency, optimization problem, convex optimization This work was supported in part by National Key R&D Plan of China under Grant No. 2017YFA0604500, in part by the Jilin Industrial Innovation Special Fund Project under Grant No. 2017C028-4, and in part by the Jilin Province Science and Technology Development Plan Project under Grant No. 20190201180JC. http://doi.org/10.3837/tiis.2020.06.006 ISSN : 1976-7277 KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2423 1. Introduction With generations of mobile devices launched by mobile device providers, users focus on implementing more complex application on their MDs. More and more emerging applications (i.e. online game, augmented reality, video optimization/acceleration, real-time monitoring, face recognition) are being integrated to form more powerful mobile application[1,2]. Those powerful mobile applications consist of multiple computation tasks with dependencies. In order to accomplish every computation task, the computation and communication resources of MD will be heavily occupied. However, MD's finite battery life and limited computation capacity pose significant challenges on accommodating the resource demand of those applications[3]. Fortunately, offloading computation tasks partly to Mobile Cloud Computing (MCC)[4] provides a promising technique to the elastic scaling of the capability of MDs. However, driven by the vision of 5G communications, the inherent limitation of MCC, i.e. the long transmission distance from MD to MCC, will lead to exceedingly long latency for mobile applications[5]. Moreover, there still exists many urgent issues to solve, such as increasing demand for high bandwidth, decreasing the energy consumption, and high quality of experience. Mobile Edge Computing (MEC)[6] can address those limitation by offloading computation tasks to the near-user MEC server instead of the remote cloud center.[7] indicated that MEC would play an significant role in 5G, the next generation mobile network. MEC[8,9] is regraded as a brilliant solution to overcome these difficulties. By combining with partial computation offloading, the computation task can be divided into two parts, which are executed locally and on the MEC server. [10] deeply studied the computation offloading scheme with the two protocols TDMA and OFDMA in a multiuser Mobile Edge Computing Offloading system by joint optimization the offloading ration, computation and communication resources, and formulated the two computation offloading problem as a convex optimization problem and a mixed-integer problem, respectively. Chen et al.[11] studied a multiuser computational offloading problem in a MEC system under the constraints of communication and computation resources, and designed a distributed computation algorithm which could obtain the Nash equilibrium by using the game theoretic. Chen et al.[12] proposed a decentralized computation offloading algorithm which could achieve a Nash equilibrium in a multiple mobile devices MCC system. [13] proposed a computation offloading framework in a multiple wireless access points MEC system by optimizing the chosen edge server, the CPU frequency and computation and communication resources to trade off the energy consumption and execution time of mobile device including multiple independent tasks. [14,15] all carried out reaserch for the purpose of maximizing the computation rate, but the backgrounds of the proposed problem and the strategies and measures show were different. [14] jointly optimized the transmission power at the access point, the task computation mode(local computing or computation offloading) and time allocation to tasks, and derived the optimal solution by using the convex optimization techniques. In order to prolong the standy time of MD, wireless powered transfer(WPT) and MEC had been integrated together. [15] jointly optimized the computation mode selection(local computing or edge computing), the time allocated to wireless power transfer(WPT) and task offloading in a WPT-assisted multi-MD MEC system. And a joint optimization algorithm based on ADMM decomposition technique was proposed to tackle this problem. In [16], the proposed dynamic computation offloading algorithm achieved the multi-objective optimization by jointly optimizing the computation offloading ratio, the CPU 2424 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing frequency allocated to local execution, and the transmission power for computation offloading under the MEC system with an energy harvesting technique. In the following paper[17], MDs not only could offload their jobs to the MEC server, but also could request computation resource from others MD in the same MEC system. Meanwhile, all the MDs obtained energy from the AP by using WPT technique. [17] aimed at minimizing the whole AP's energy transmitted under the constraints of communication and computation resources, the deadline and the power transmission. [18,19] also gived a study on computation offloading. Although these papers are all about independent task with MD as shown previously, there is no dependency relationship among tasks. As the application becomes increasingly complex, multiple tasks, functions or applications are incorporated into an integrated application. Thus, an in-depth study of offloading computation tasks with dependencies is worthwhile. Coarse-granularity based task offloading policy is used to provide a optimal solution for tasks with dependencies. [20] proposed a collaborative task computation algorithm to prolong the standby time of mobile devices for the application model in the linear topology. [21] provided a comprehensive computation offloading algorithm for computationally intense applications with multiple subtasks to determine which subtasks should be computed in the MD or cloud. [22] aimed to trade-off the energy consumption of MD and latency for application by finding the optimal assignments of tasks executed on local or remote devices. [23] achieved the trade-offs between the energy cost and latency by optimizing the power allocation and the offloading decisions for an application modeled as directed acyclic graph(DAG). [24,25] also could obtain an overall solution by designing a joint scheduling offloading policy for the application with sequential task dependencies. [26] divided the application into a non-offloadable task and multi-offloadable tasks, and a low complexity sub-optimal algorithm was proposed to decide which offloadable task should be transmitted to MEC server. For an application including multiple subtasks depended on each other, [27] proposed a heuristic algorithm based on particle swarm optimizer (PSO) to solve the 0-1 programming problem, where 0 represented local computing and 1 represented edge computing. Though these studies improve the performance of mobile device by using computation offloading, most of those researches focus on the optimal scheduling order. Meanwhile, the transmission power and the CPU frequency allocated to tasks are fixed. Therefore, we make a study on the computation offloading in the mobile application which includes multiple computational intensive dependent tasks for a single MD MEC system, and propose an algorithm that minimizes the energy cost and improves performance by jointly optimizing the offloading ratio, CPU frequency, the transmission power and the transmission time. [28] compared the performance of offloading the dependent tasks from MD to a remote cloud center or an edge server and made the conclusion that offloading to an edge server is a promising technique in providing better performance than a remote cloud server. [29] took use of offloading strategy which migrated tasks in the task graph to the nearby wearable or mobile device through the available wireless communication interface such as Bluetooth or Wi-Fi. Experimental conclusions of [29] demonstrated that the scheduling policy could achieve the two objectives of extending battery lifetime and enhancing performance. At present, there are not many works related to task graph on MEC system, most of them are sub-task granularity and these works aim at different objective. As far as we know, there is no related work with the goal of minimizing energy consumption of MD by dividing the input data of all the subtasks on task graph bit by bit, which is able to guarantee the higher resource utilization and less energy consumption. Accordingly, this paper aims to minimize the energy consumption of task graph by jointly optimizing the resource allocation strategy. KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2425 In this paper, we study an single MD MEC system where MD executes a mobile application made up of multiple computation tasks. The objective of the paper is to minimize the energy consumption of MD with energy-saving resources allocation. In this paper, we model the complex mobile application consisting of multiple interdependent tasks as a DAG task-graph, and develop an energy-efficient computation offloading algorithm by joint optimization the communication and computation resources. Our main contributions are generalized as follows. Firstly, in term of system model, most the computation offloading algorithms do not take into account the computation results feedback, and partial computation offloading for tasks with dependencies is task granularity rather than dividing the input data bit by bit. Therefore, we propose a system model of partial computation offloading for a application consisting of multiple tasks with dependencies, which divides the computation data by bitwise and integrates results feedback. Secondly, in term of problem formulation, for tasks with dependencies, most studies are aimed at achieving the objective of saving energy or reducing latency by optimizing scheduling strategy with fixed transmission power and local computation capacity. However, this paper uses the DVFS technique optimize the CPU frequency, and achieves the optimal transmission power. The corresponding time slots for the local computing, uploading the offloading bits and computation results feedback are allocated with a time division mechanism. Therefore, the problem is formulated as an optimization problem that minimizes the MD’s energy consumption with the constraints of the delay, the computation and communication capacity. Finally, in term of the optimal solution, convex optimization techniques and the Lagrange Multiplier method are used to simplify the problem, and the original non-convex optimization problem is transformed into a univariate nonlinear equation, which accelerates the problem solving. Simulation results demonstrate that the proposed algorithm not only saves energy consumption, but also prolongs the standby time of MD. The rest of this paper is organized as follows. In Section II, we expounds the system model. The problem is formulated and the algorithm for the problem is proposed in Section III and its performance evaluation and simulation results are analysed and shown in Section IV. The conclusion is given in Section V. 2. System Model As shown in Fig. 1, we consider a basic two-node MEC system that consists of single MD and one AP node integrated with a MEC server. In order to reduce the impact of multiple wireless channel creation, frequent requests for the MEC server resources, etc. on task offloading, we conduct the study in the single MEC server scenatio. Both of the two nodes are equipped with one single antenna. This system provides the simplex mode. That is to say, the two processes, offloading input data or receiving computation results, can not be executed through the wireless channel at the same time. The MEC server not only provides the same execution environment but has more sufficient resources than the MD. Therefore, the MEC server can accomplish the computation tasks of application more efficient than the MD. The distance is defined as d between MD and AP, and the bandwidth is denoted as B . 2426 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing Fig. 1. A mobile-edge computing system with a mobile device and an AP 2.1 Computation Application Model We assume that the MD has an application that is composed of N computation-intensive tasks (See Fig. 1, with an example where N = 6 ). Each task can be offloaded to MEC server by using partial computation offloading technique. This application model can be described by using Directed Acyclic Graph(DAG) where the node v in the node set G = (,)   denotes a task in the application, the edge ( vv , ) represents the dependency from task to i j i v and the edge set of the DAG denotes the set of dependencies. represents the  Set j i in-degree set of task i . Task i can not start executing until tasks belonging to Set are completed.To describe the parametric context of each task, a two-tuple ( I ,η ) is defined, ii where iN = 1,..., . Accordingly, I is the size of task i input data which includes the existing data l and the computation results transmitted from tasks in Set . According to [10,17,19,20], i i we learn that there is a linear relationship between the computation result and the input data for the computation task. η is the ratio of the output data to the input data for task i . Task i may need the computation results from related tasks if Set is not null.As such, the total input data size I is ll + η while Set is non-null. If Set is an empty set, I is equal to l . We use i i ∑ ii i i i i k∈Set D , a N*N matrix, represent the task graph. In this paper, we focus on the scenarios where the MD has finite computing capability. In order to accomplish the application, offloading parts of the input data to the MEC server is necessary. We assume that all tasks of the application are executed in a predetermined scheduling policy which results from Breadth-First Traversal(BFT). For example, we can get the scheduling policy ( 1, 2, 3, 4, 5, 6 ) in Fig. 1. And then, we realize our objective which minimizes the energy consumption of the MD. Meanwhile, with the given scheduling strategy, we assume that both local computing and computation offloading of the current task begin simultaneously, which ensures that its dependent tasks have completed correctly. λ is the ratio of the offloading data to the input data for task i , so we can get the constraint of λ : 0≤λ ≤ 1,∀∈ iN {1,..., }. (C1) where λ = {λλ ,..., } denotes the offloading policy of the tasks graph. 1 N KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2427 2.2 Communication Model For each computational intensive task i∈ , its input bits I is split into two parts λ I ≥ 0 i ii and (1−≥ λ )I 0 bits, which denote the number of bits offloaded to the MEC server through ii AP and computed locally, respectively. MD receives the offloading computing results from the MEC server. We introduce the TDMA protocol into the system to avoid any interference among tasks. Because of MD and AP equipped with one antenna, the wireless channel can execute only one process during each time slot. As shown in Fig. 2, the protocol divides the ud whole time T into 2 N time slots, and each task contains two time slots ( tt , ). ii Fig. 2. The TDMA protocol for mutli-task computation offloading in an application 1) Computation Offloading from MD to the AP In the time slot, task offloads input bits to the AP with the transmission power t i λ I i ii t 2 . We define as the channel power gain between MD and AP. Next, the achievable P ≥ 0 h data rate(bits/sec) for uploading offloading input data from the MD to the AP is defined as t 2 Ph u i rB log (1+ ) (1) i 2 where N means the additive white Gaussian noise at the receiver of the AP. For simplifying the computation, we define a function gx ( ) (2−> 1), x 0 . According to (1), we can get t u t the expression of P with the variable r . That is to say, P (2− 1) . After we get the i i i λ I u u u t ii offloading bits λ I and the uploading time t , r can be represented as r = . So P ii i i i i can be re-defined as followed: I λ ii NI λ t Bt 0 i i Pg (2 1) ( ) (2) 2 u ht Based on the actual observation offered in [30], and the equation recommended by the EARTH project[31], we know that the uploading power includes the transmission power t c P and an extra constant circuit power P caused by converting from digital signal to analog i t u t signal, packaging, and so on. Moreover, P is linear with P . Therefore, we give the i i following definition: −= = = 2428 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing uc t P P+κ P (3) i t ti where κ denotes the linear growth and is a constant coefficient without unit. According to (3),the energy consumption of uploading data at MD in time slot t is expressed as I λ u uu t u i i E P t (( g )+κ P )t (4) i i i ti i 2) Downloading the Computation Results from the AP to the MD Considering that the MD needs to receive the computation results from AP, so the delay cannot be ignored. The computation results of task i are η I . And then, the achievable data ii rate for receiving computation results from the AP to the MD is expressed by Ph rB log (1+ ) (5) d 2 where P denotes the transmission power of the AP, which is a constant. Therefore, r is a F d constant. Meanwhile, we have known the amount of the computation results ηλ I . i ii Ultimately, combining (5), we can get the representation as follows: ηλ I i ii t = (6) According to [32,33], the MD power consumption P increases linearly with the download data rate r . So we give the formula of P as follows. d i dc PP+κ r (7) i d dd c c c where is similar to the previous definition . However, is affected by converting P P P d t d from analog signal to digital signal, unpackaging, and so on. κ represents the linearly increasing coefficient. And then, we get the equation of calculating the energy consumed by d d receiving the computation results from AP in the time slot t . By merging (6) and (7), E is i i expressed as the following equation. ηλ IP d dd c i ii d E = P t = (P+= κ r ) ( +κ )η I λ (8) i i i d dd d i i i rr dd 2.3 Computing Model 1) Local Computing: (1−λ )I input data of task i is executed on the mobile device(MD) within a duration t . ii i C denotes the number of CPU cycles required for computing 1-bit of input data at MD, and (1−λ )IC ii f is the CPU frequency allocated to task i , i.e. . In practical application, the f = i i CPU frequency of MD has a maximum value, denoted by f . So f is capped by f , i.e. max i max (1−λ )IC ii ≤ fi ,∀ (C2) max = = = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2429 Also, the computation latency constraint t for local computing of task i must be satisfied as follows: t ≥ 0. (9) Then, the whole local computation tasks must be accomplished before the deadline, i.e. tT ≤ (C3) ∑ i i=1 The energy consumption of task i for local computing is 33 3 (1−λ ) IC ll 3 i i E κκ ft ,∀i (10) i li i l l 2 () t where κ means the effective capacitance coefficient which has relation with the chip structure of MD. According to Fig. 2, for task i , the time that MD starts to transmit input data through wireless channel is simultaneous with starting local execution. Besides, according to (10), the l l bigger t is, the smaller E is. So we can infer that CPU is not in idle state between the end of i i the previous task and the beginning of the next task, which means that local execution lasts the whole time period t . Consequently, the wireless channel occupation time and local computation time should meet the following time constraint for task i . ud l t + t ≤ t ,. ∀i (11) ii i Replacing t with (6), we can rewrite the former time constraint as below. ηλ I ul i ii t + ≤ ti ,. ∀ (C4) ii 2) Edge-Computation: We assume that the network and computational resources of the MEC server are infinite. Owing to the sufficient computation capability of the MEC server, the delay of receiving offloading data, the time spending on accomplishing the offloaded computation task, and the delay of sending computation results are relatively small and negligible at the MEC server. Therefore,we assume that MD immediately receives computation result from the AP when the offloading data transmission is completed. Since the objective is to minimize the energy consumption of mobile device, the energy consumption of MEC server is negligible. 3. Problem Formulation and Optimal Solution In this section, we propose a feasible computation offloading scheme to the application modeled as task graph. In order to minimize the energy consumption of MD, the CPU frequency and the transmission power are optimized for local computing and computation offloading, respectively. The solution process of the optimal computation offloading scheme is shown below. 3.1 Problem Formulation Under the system model above mentioned, we give a trade-off model between the energy consumption of local computing and the energy cost of communication among the AP and the MD to obtain the total minimum energy consumption of the MD. Meanwhile, the trade-off = = 2430 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing model must satisfy the delay constraint, the limited computation and communication resources. From (4), (8) and (10), we can come to the conclusion that all the energy consumption of MD is impacted by local computing, computation offloading and receiving computation results. Learning from the former section, the local energy consumption is influenced by the locally executed bits (1−λ )I and its executed time t , and the energy consumed by communication i i i between the AP and the MD is impacted by the time spending on uploading the offloading bits u uu u ll l t and the offloading bits λ I . Then, Let λ = {λλ ,..., } , t = {tt ,..., } , t = {t ,..., t } , and i i i 1 N 1 N 1 N these three vectors determine how much energy the application will consume. Mathematically, the delay-constrained energy minimization optimization problem is formulated as ud l E : min EE ++ E ∑ ii i u l (,λ t ,t ) i=1 st . . C1, C 2, C3, C 4 ul C5 : tt , >∀ 0 i ii Now we substitute all related equations into problem E , and E is represented as follows. I ln 2λ ii c 3 N P ((1−λ )IC ) uc Bt 0 d ii E : min tP ( +κ (e −+ 1))+( κ )ηλ I +κ 1 ∑ i t t d i i l u l 22 l (,λ t ,t ) hr () t i=1 di st . . C1: 0≤≤ λ 1 ∀i (1−λ )IC ii C 2: ≤∀ f i l max (12) C3: tT ≤ i=1 ηλ I ul i i Ct 4: +≤ t ∀i ii ul C5 : tt , >∀ 0 i ii In Problem E , C1 denotes the constraint of the offloading ratio, C2 is the maximum CPU frequency constraint for each task of the application, and C3 is the deadline constraint. C4 guarantees that the time cost by local computing must be greater than or equal to the time taken by the data transmission and receiving computation results for task i . Note that E is non-convex in general because of the coupling of λ and t in C2. Therefore, we need convert i i E into a convex problem[34] with some measures, and then give the optimal solution. 3.2 Optimal Solution To E This subsection gives the optimal solution of E . To achieve this goal, firstly, we transform C2 into a convex constraint by multiplying both sides of inequality C2 with t . The constraint C2 is converted to C 2′ . (1−λ )IC− f t ≤∀ 0, i. ( C 2′ ) i i max i Then, E is reformulated as follows. 1 KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2431 I ln 2λ ii c 3 N P ((1−λ )IC ) uc 0 Bt d ii E : min tP ( +κ (e −+ 1))+( κ )ηλ I +κ 2 i t t 22 d i i l l u l (,λ t ,t ) hr () t i=1 di st . . C1,3 C , C 4,5 C (13) C 2 : (1−λ )IC− f t ≤ 0 ∀i i i max i (1−λ ) Meanwhile, the function is convex with respect to 01 << λ and t > 0 [35], and i i l 2 () t κ ((1−λ )IC ) l ii hence the equation in the objective function is jointly convex with respect to l 2 () t 01 << λ and 0<< tT . Moreover, the following lemma demonstrates the evidence that i i Problem E is a convex problem. Lemma 1 Problem E is a convex optimization problem. Proof: Because gx () is an exponential function and a convex function, its perspective I λ κ ((1−λ )IC ) u i i l ii function[13], tg () is still convex. Also, is jointly convex function[35]. u l 2 t () t i i Thus, the objective function which is the summation of a set of convex functions, holds the convexity. All constraints are the linear convex function. Consequently, we get the result of Lemma 1. Assume that Problem E is feasible, we use the Lagrange Multiplier method to simply the problem solving. We define α ≥ 0,βγ ≥≥ 0, 0 as the Lagrangian multipliers for C1, i ii C 2′ ,C4, respectively. µ is the Lagrange multiplier for C3. Therefore, the partial Lagrangian function of E is given by I ln 2λ ii c 3 κ N P ((1−λ )IC ) ul u c Bt t 0 d ii (λ , tt , ,α ,βγ , ,µ ) tP ( + (e −+ 1)) ( +κ )ηλ I +κ ∑ i t d i i l 22 l hr () t i=1 di NN N ηλ I lu l ii i + αλ ( − 1)+ β ((1−λ )IC− f t )+ γ (t + − t ) (14) ∑∑ i i i i i max i ∑ i i i ii 11 i 1 +− µ () tT ∑ i i=1 * ul ** Let λ ,, tt denote the optimal solution of E . The optimal solution always satisfies all { } ii i 2 constraints and has the minimum energy consumption of MD. By applying KKT conditions, the following necessary and sufficient conditions must be true. I ln 2λ i i c *2 3 3 κ NI ln 2 u* (P +− κ r )η I 3κ (1 λ ) I C η I ∂ t 0 i Bt d d d ii l i i ** * ii e + − +αβ− IC+γ 0 (a) i ii i * 2 l*2 ∂λ Bh r (t ) r i di d ** II ln 2⋅⋅ λλ ln 2 ii ii N uu ** nI ln 2⋅λ ∂ c 00 Bt⋅⋅ ii Bt * ii (b) = Pe +κ ( −− 1) κ e +γ = 0 tt t i u* 2 2* u ∂⋅ t h h Bt i i *3 3 3 2κ (1−λ ) IC ∂ l ii * ** (c) =− −β f −γ +µ = 0 i max i l* l*3 ∂tt ( ) i i ** αλ ( −= 1) 0,∀i (d) ii = = = == = 2432 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing ** l* β ((1−− λ )IC f t )= 0,∀i (e) i i i max i η I λ ** ul* ii i γ (t + − ti )=0,∀ (f) ii i ** l µ ( tT −= )0 (g) ∑ i i=1 * u* * According to (b), we can get Lemma 2 which describes the relations among λ ,, t γ . { } ii i * u* * Lemma 2 The optimal λ ,, t γ satisfies { } ii i *2 c λ B −1 () Ph +γ i t i (1+ Wi ( + ))∀ , (15) u* t I ln 2 e κ eN ii t 0 Wx () where Wx () defines the Lambert-W function, i.e. x= W () x e . I ln 2⋅λ ii * c *2 ( −1) u* I ln 2⋅λ −1 (P +γ )h Bt⋅ i i t i Proof: With the help of (b), we have ( − 1)e =+ . u* B⋅ t e κ eN it 0 Wx () According to the Lambert-W function, i.e. x= W () x e , which is the inverse function of * c *2 I ln 2⋅+ λ −1 (P γ )h i i t i f () x = xe .We can straightforwardly infer that ( −= 1) W ( + ), u* B⋅ t e κ eN it 0 which leads to the result in Lemma 2 with some simple operations. With some operations on (c), we can get the following expression. *3 3 3 2κ (1−λ ) IC * l ii ** * µ +β fi+∀ γ , . Therefore, we can get the result µ > 0 . Combining i max i l*3 (t ) l* with (g), the summation of is identically equal to , i.e. t T l* t = T (16) ∑ i i=1 which conforms to the monotonically decreasing property of the objective function respect to t . According to (a), (c), (d), we can get the following Lemma 3. In order to reduce the complexity of interpretation, we firstly define c 2 −1 () Ph +γ t i ϕγ ( )= 1+ W ( + ). (17) ii e κ eN t 0 ** l * Lemma 3 The optimal λ , t ,γ satisfies { } ii i κ N ln 2 ηγ η ϕγ () c t 0 i i i i i e + ++ () Pr κ d d d 1 * 2 1−λ Bh r r i dd = () (18) l* 23 t 3κ IC i li The ratio is influenced by the i-th task parameters of η , I and the lagrangian multiplier γ . { } ii i Proof: At first, according to (d), because not all the input data is transmitted to the MEC server, we obtain α = 0 . The result makes sure that the local energy cost is not the maximum. And then, to ensure (e) true, since the CPU frequency f allocated to task i always less than * * f , we obtain β = 0 . Plugging β = 0 into (c), and making some simple manipulations, max i i we obtain the following result. = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2433 *3 3 3 2κ (1−λ ) IC ** l ii µγ+∀ ,. i (19) l*3 (t ) * * At last, we substitute (17), αβ 0, 0 into (a). The Lemma 3 is inferred. ii (1−λ )IC ii We know f ≤ f . Meanwhile, plugging (18) into f , we obtain an i max i 1−λ * * inequality about γ . We introduce the function F () γ for replacing the ratio , i.e. i ii l* 1−λ * * F () γ = . Correspondingly, the range of γ can be described as Proposition 1. ii i l* * * Proposition 1 F () γ is a monotonically increasing function when γ > 0 . The one and only ii i * ( 0) * ( 0) γ > 0 satisfies Ff () γ = existed. The value is defined as γ , and γγ ≤ . i i i max i ii ϕγ () i i Proof: e is an increasing function with γ ≥ 0 because ϕγ () is an increasing i ii function with γ ≥ 0 . Meanwhile, γ is a linear function. Because F () γ is the square root i i ii of the sum of an increasing function, we infer that F () γ is an increasing function with γ ≥ 0 . ii i ( 0) γ →+∞ and F () γ →+∞ . So we can get the unique γ by using the Bi-Section Search i ii i method. The Proposition 1 is proved. * * *3 µγ + 2κ (F (γ )) . (20) i l ii Now, substituting (18) into (19), we get (20). Learning from (18), we acknowledge that µ is associated with γ , η , and the performance parameters of SD. Although the ratio of (18) i i changes over ηγ ,, I , the lagrangian multiplier µ is fixed. Meanwhile, µ is a scalar rather ii i * * than a vector. Therefore, the lagrangian multiplier γ should satisfy γ > 0 . In order to meet i i η I λ ul ** * ii i the condition (f), we get the result tt += because of γ > 0 . Accordingly, we obtain ii i l* Lemma 4 by using the above derivation results, which denotes that the local execution time t can be expressed as a function with a single variable lagrangian multiplierµ . l* Lemma 4 The optimal t can be expressed as l** t =Q () µ = , (21) i i 2 * −1* rr ln 2 (µψ − (µ )) dd i − + −1* 1 Iη η (I r ln 2+ BIηϕ (ψ (µ ))) ii i i d ii i i IC (2κ ) i l l * r r l Q ()µ is monotonically decreasing with µµ ≤ ≤µ . If QT (µ )> or Q () µ < T , λ , ∑ ∑ i i i l u l r l u t , and t do not exist. If TQ < () µ and QT (µ )< , λ , t , and t are unique. ∑ i ∑ i Proof: Firstly, µ =ψγ () is introduced to simplify the derivation and computation, i.e. ii 3 2 ψγ () γ + 2κ F () γ . ψγ () 1+ 6κ FF () γ () γ denotes its derivation. Learning from i i i l i i i i l i i i i Proposition 1, we can get ψγ ()> 1 because F () γ is a monotonically increasing function ii ii F () γ > 0 . Consequently, ψγ () is a monotonically increasing function with γ > 0 . Given ii ii i = = = = = 2434 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing the value of µ , we can get a unique γ , and vice versa. The inverse function of ψγ () is i ii ψγ ()−γ −1 ii i denoted as γψ = ()µ , and F () γ can be rewritten as F () γ = ( ) . As we all ii ii ii 2κ know, the derivative of the original function is equal to the inverse of the derivative of its −1 inverse function in calculus. Hence, 0<= (ψ )(µ ) < 1 , where µ =ψγ () . Learning i ii ψγ′( ) ii l* from Lemma 2 and Lemma 3, we can get the expression of t by solving the simultaneous −1 equation (22). We use ψ ()µ replace the Lagrangian multiplier γ in (23), and we can use a i i * * l* function Q () µ only associated with µ represent t , which is (21). i i  η I λ ul ** ii i tt += ii r (22) (15), (18) l* t = (23) i 2* rr ln 2 F (γ ) d d ii −+ Iη Iη (r ln 2+ Bηϕ (γ )) IC ii ii d i i i i −1 Secondly, based on the property of Lambert-W function ϕ > 0 , and 0( << ψ ) 1 , the i i derived function Q ()µ < 0 , and Q ()µ is µ 's rigid monotony decrease by degrees function. i i 2 −11 − −1 ′′ BI r ln 2ϕ (ψµ ( ))(ψµ ( )) 1 1− (ψ (µ )) i d i i i i + ⋅ −12 12 (I r ln 2+ BIηϕ (ψ (µ ))) i ii i −1 3 3 3IC (2κ ) (µψ − (µ )) i l i Q ()µ < 0 (24) i 1 21 − r r ln 2 (µψ − (µ )) di −− () + −1 1 Iη η (I r ln 2+ BIηϕ (ψ (µ ))) ii i i d ii i IC (2κ ) i l * * ( 0) Thirdly, we get the interval range of γ as 0≤γγ ≤ according to Proposition 1. And, (20) i ii indicates that µ is a monotonically increasing function with γ . We define ( 0) ( 0) ( 0) * µ = max{ψ (0)} and µ = min ψγ ( ) , and the numeric zone of µ is displayed as { } li r ii follows. ( 0) * ( 0) µ ≤µµ ≤ . (25) lr l* * Meanwhile, according to (21), t is monotonically decreasing with µ ≥ 0 . What’s more, l* l * (1) 0≤ t ≤ T . By solving tT = , we can get a unique value of µ , defined as µ . Let i i l l ( 0) (1) r ( 0) * µ = max µµ , and µµ = . The restriction of µ is rewritten as ( ) ll r l * r µµ ≤ ≤µ . (26) By using the well studied methods, i.e. Bi-Section Search, Newton Method, solve µ ψγ ( ),∀i , the numeric zone of γ ,∀i can be achieved with the given lower and upper ii i limits of µ . Ultimately, by judging the value of Q ()µ , i.e. t , we can determine whether problem ∑ i ∑ i * l * u * r l E exists the optimal solution λ , t , and t or not. If QT (µ )> or Q () µ < T , it 2 ∑ i ∑ i = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2435 l r does not exist the optimal solution. If TQ < () µ and QT (µ )< , the unique optimal ∑ i ∑ i solution can be achieved by solving (16). Lemma 4 is proved now. Accordingly, problem E , a multiple variables non-linear optimization problem with multi-constraint, is equivalently transferred to a non-linear equation with a linear inequality constraint. The nonlinear equation is expressed as follows: E : QT ()µ = 3 ∑ i (27) i=1 lr st ..µ ≤µµ ≤ l l Since t is a monotonic decreasing function respect to µ , t inherits the descending i ∑ i characteristic. Therefore, there exists a unique µ to E . Then, we propose our algorithm Bi-JOTD to calculate the optimal solution to E . The solution is the optimal offloading strategy for E , too. The proposed optimization method not only successfully avoids solving a nonlinear convex optimization problem with high dimensions and high orders, but also overwhelmingly decreases on the computational complexity and the computation time to acquire the optimal strategy. The following pseudo-code gives the accurate processes to solve the non-linear equation with a linear inequality constraint. Algorithm 1 calculates the approximate multiplierγ which satisfies (19) with given µ . Bi-JOTD computes the multiplier µ among the linear constraint. After Lagrangian * * multipliers γ and µ are achieved, we can use (15), (18), (21) obtain the final optimal * l * u * resource allocation strategy λ , t , and t . 2436 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing Through analyzing the proposed algorithm Bi-JOTD, the complexity of Bi-JOTD is associated with the iteration number of inner and outer Bi-Section Search algorithms. We define  and  as the complexity of inner and outer algorithms, respectively. inner outer Therefore, the complexity of Bi-JOTD algorithm is  () N  . Compared with the inner outer original Problem E , our proposed algorithm can greatly reduce the complexity. 4. Simulation Results In this section, the simulation results of the proposed computation offloading scheme through joint optimization time allocation and dependency tasks is presented. The scheme is named as Bi-JOTD in the simulation results. Based on [16,23,24], the simulation parameters are set as follows. We assume that the channel reciprocity holds for the downlink and uplink, and thus 222 2 −− 3 ζ hhh . The channel power gain is modeled as hd 10 Φ [24], where Φ stands for ud the short-term fading which obeys the Rayleigh fading. For distance d in meters with the , a 30dB average signal power attenuation is assumed for all the same path-loss exponentζ channels at reference of 1m. Moreover, the input data size and the ratio of the computation results follow the uniform distribution with I ∈[10,100]KB andη ∈[0.01, 0.1] , separately. i i The other detailed parameters are listed in Table 1. Table 1. Simulation Parameters Parameter Value 5 Mbps Bandwidth B Deadline T 1s c c −4 Circuit powers P and P 5.0 *10 W t d Distance between the MD and the MEC server d 100m Path-loss exponent ζ 1.7 −9 White Gaussian channel noise N 10 W MD’s maximum CPU frequency f 1.0GHz max The linear growth coefficient κ 1.0 −27 The effective capacitance coefficient −7 The power consumption of receiving per bit κ 2.86 *10 W bit The required number of CPU cycles per bit C 800 cycles bit Meanwhile, in order to comparison, the following five baselines[5,16,17,23,24,25,26], are displayed. 1) λ = 0.4 : The computation input data are divided into two parts for each task. The ratio λ = 0.4 of input data is accomplished in the MEC server, and the rest of input data is completed in MD. 2) Task: In the task-graph representing the mobile application, some tasks are offloaded to MEC server, and the rest of tasks execute on the mobile device. 3) λ = 0.8 : The offloading ratio of computation data transmitted to MEC server is set as λ = 0.8 . = = = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2437 4) Ave-JOTD: The offloading ratio λ is set as the average of suboptimal solution λ , i.e. i i λλ = . ii ∑ 5) PSO-JOTD: The suboptimal task offloading scheme is achieved by using particle swarm optimizer (PSO). 4.1 The Validation of the Optimal Solution In this subsection, we verify the correctness and superiority of the proposed algorithm. The energy consumption of the approximate solution is close to the cost of the exact solution in a tolerable accuracy range, which compares the simulation results of different block input data I () KB and the ratio η at the same deadline Ts = 1.0 in Fig. 3 and Fig. 4, respectively. Fig. 3. The energy consumption with different I versus T Fig. 4. The energy consumption with different η versus T 2438 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing By comparing with the energy consumption between the global search with the default step size of 0.001 among the fixed range of offloading ratio λ and the proposed optimization algorithm, the energy consumption of the proposed approximate solution is minimum. The simulation results of Fig. 3 and Fig. 4 provide the evidence that problem E is a convex optimization problem. Meanwhile, the process of solving E is correct. 4.2 The Simulation Results for Task Graph Fig. 5. The energy consumption with fixed and random versus I η T Fig. 6. The energy consumption with fixed η and random I versus T This subsection evaluates the energy consumption of the proposed Bi-JOTD algorithm and other five baselines, which spends on computing and communicating versus the deadline T . KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2439 Fig. 5 makes the comparison simulation of energy consumption with a vector (, I η ) , where ii I is fixed and η is random, and Fig. 6 gives a simulation with random I and fixed η . The i i i i proposed Bi-JOTD algorithm is obviously superior to the other baselines. Specifically, the energy consumption of the proposed algorithm is always less than other baselines, which further displays the advantages of offloading the computation tasks to the MEC server. The minimum energy cost has decreased trend with the increase of T . Therefore, Bi-JOTD algorithm has some advantages in solving multi-task application. Then, making a comparison test between Bi-JOTD and Ave-JOTD, we can see that the energy cost of Bi-JOTD is less than Ave-JOTD with the increase of T . It can be concluded that task's result feedback has a great influence on the ratio of offloading input data. Hence, we should comprehensively take task's feedback into account in the task graph to solve the objective of the formulated problem. Fig. 7. The succeeding assignment ratios with random and versus η I T Fig. 8. shows the relationship of the minimum energy consumption of MD, the input data I and the ratio of the computation results η 2440 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing The figure simulated in Fig. 7 is based on 300 times simulated testing, in which I , η are i i randomly selected on the basis of the above assumptions in every implementation, modeling the actual computation offloading scenario. We simulate the resource allocation, and the statistics of success ratios are brought in Fig. 7. The success ratios of all the schemes increase with T , as we excepted. Besides, the success ratio of Bi-JOTD grows faster than others. Bi-JOTD can achieve a high success ratio even with low latency T . Meanwhile, as time goes by, the success ratio of Bi-JOTD reaches and remains stable. Compared with other 100% baselines, our proposed algorithm has more advantages in a high success ratio. Fig. 8 shows the relationship of the minimum energy consumption of MD, the input data and the ratio of computation results. The energy consumption is achieved by using our proposed algorithm, and Ts = 1.5 . According to Fig. 8, while setting the value of η , the energy consumption increases significantly as the input data increases. When setting the value of the input data I , the energy consumption also shows an increasing trend with the increase of η , but the growth is not very obvious. In particular, the application cannot be accomplished while I = 100KB and η =0.1 . Integrated with the previous simulation results and the optimization processes, the proposed algorithm not only has a great advantage in energy consumption, but also has a good performance on the executability of the computation offloading strategy. Ultimately, combining all figures and the equivalence of problem E , E , and E , we can get the 1 2 3 conclusion that our proposed algorithm not only can obtain higher efficiency, less energy consumption and better performance, but also can be calculated more easily than others. 5. Conclusion This work studies a computation offloading scheme for an application including multiple computation components with dependencies under a single-user MEC system. MEC server assists MD in completing its computation-intensive latency-critical application. The application is modeled as a DAG task-graph. By jointly optimizing the offloading ratio, CPU frequency, transmission power and transmission time, the objective that minimizes the energy consumption of MD is achieved. The problem is formulated as a optimization problem. The nonlinear equation with a linear inequality is obtained by using the Lagrange Multiplier method and convex optimization techniques. A double Bi-Section Search algorithm is proposed to solve the transformed nonlinear equation. Simulation results reveal that the proposed strategy greatly reduces the energy consumption while compared with the used baselines. The proposed computation offloading scheme not only reduces the difficulty of problem solving, but also prolongs the MD’s standy time and achieves better performance. Meanwhile, we will extend our study of using partial computation offloading strategy to deal with the application including dependent tasks to the multiple mobile devices multiple MEC servers scenario. References [1] Z. Q. Jaber and M. I. Younis, “Design and implementation of real time face recognition system (rtfrs),” International Journal of Computer Applications, vol. 94, no. 12, pp. 15-22, 2014. Article (CrossRef Link) [2] J. Kephart and D. Chess, “The vision of autonomic computing,” Computer, vol. 36, no. 1, pp. 41–50, Jan. 2003. KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2441 [3] K. Kumar and Y. H. Lu, “Cloud computing for mobile users: Can offloading computation save energy?,” Computer, vol. 43, pp. 51–56, Apr. 2010. Article (CrossRef Link) [4] N. Vallina-Rodriguez and J. Crowcroft, “Energy management techniques in modern mobile handsets,” IEEE Communications Surveys & Tutorials, vol. 15, no. 1, pp. 179–198, First 2013. Article (CrossRef Link) [5] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” IEEE Communications Surveys & Tutorials, vol. 19, no. 4, pp. 2322–2358, 2017. Article (CrossRef Link) [6] M. Patel, B. Naughton, C. Chan, N. Sprecher, S. Abeta, A. Neal et al., “Mobile-edge computing introductory technical white paper,” ETSI, Sophia Antipolis, France, and MEC, London, U.K., Tech. Rep., pp. 1089–7801, 2014. [7] Y. Jararweh, A. Doulat, O. AlQudah, E. Ahmed, M. Al-Ayyoub, and E. Benkhelifa, “The future of mobile cloud computing: integrating cloudlets and mobile edge computing,” in Proc. of 23rd Int. Conf. Telecommun. (ICT). IEEE, pp. 1–5, 2016. Article (CrossRef Link) [8] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and its role in the internet of things,” in Proc. of 1st Edition MCC Workshop Mobile Cloud Comput. ACM, pp. 13–16, 2012. Article (CrossRef Link) [9] G. I. Klas, “Fog computing and mobile edge cloud gain momentum open fog consortium, etsi mec and cloudlets,” Google Scholar, 2015. [10] A. Al-Shuwaili and O. Simeone, “Energy-efficient resource allocation for mobile edge computing-based augmented reality applications,” IEEE Communication Letter, vol. 6, no. 3, pp. 398–401, 2017. Article (CrossRef Link) [11] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,” IEEE/ACM Transaction on Networking, vol. 24, no. 5, pp. 2795–2808, 2015. Article (CrossRef Link) [12] X. Chen, “Decentralized computation offloading game for mobile cloud computing,” IEEE Transaction on Parallel Distribution System, vol. 26, no. 4, pp. 974–983, 2014. Article (CrossRef Link) [13] T. Q. Dinh, J. Tang, Q. D. La, and T. Q. Quek, “Adaptive computation scaling and task offloading in mobile edge computing,” in Proc. of WCNC. IEEE, pp. 1–6, 2017. Article (CrossRef Link) [14] F. Wang, “Computation rate maximization for wireless powered mobile edge computing,” in Proc of 23rd Asia-Pacific Conf. Commun. (APCC). IEEE, pp. 1–6, 2017. Article (CrossRef Link) [15] S. Bi and Y. J. Zhang, “Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading,” IEEE Transaction Wireless Communication, vol. 17, no. 6, pp. 4177–4190, 2018. Article (CrossRef Link) [16] Y. Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading for mobile-edge computing with energy harvesting devices,” IEEE Journal on Selected Areas in Communication, vol. 34, no. 12, pp. 3590–3605, 2016. Article (CrossRef Link) [17] X. Hu, K.-K. Wong, and K. Yang, “Wireless powered cooperation-assisted mobile edge computing,” IEEE Transaction on Wireless Communication, vol. 17, no. 4, pp. 2375–2388, 2018. Article (CrossRef Link) [18] F. Wang, J. Xu, X. Wang, and S. Cui, “Joint offloading and computing optimization in wireless powered mobile-edge computing systems,” IEEE Transaction on Wireless Communication, vol. 17, no. 3, pp. 1784–1797, 2017. Article (CrossRef Link) [19] Y. Liu, S. Wang, and F. Yang, “Poster Abstract: A multi-user computation offloading algorithm based on game theory in mobile cloud computing,” in Proc. of IEEE/ACM Symp. Edge Comput. (SEC). IEEE, pp. 93–94, 2016. Article (CrossRef Link) [20] W. Zhang, Y. Wen, and D. O. Wu, “Collaborative task execution in mobile cloud computing under a stochastic wireless channel,” IEEE Transaction on Wireless Communication, vol. 14, no. 1, pp. 81–93, 2014. Article (CrossRef Link) [21] S. E. Mahmoodi, K. Subbalakshmi, and V. Sagar, “Cloud offloading for multi-radio enabled mobile devices,” in Proc. of IEEE Int. Conf. Commun. (ICC). IEEE, pp. 5473–5478, 2015. Article (CrossRef Link) 2442 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing [22] Y.-H. Kao, B. Krishnamachari, M.-R. Ra, and F. Bai, “Hermes: Latency optimal task assignment for resource-constrained mobile computing,” IEEE Transaction on Mobile Computing, vol. 16, no. 11, pp. 3056–3069, 2017. Article (CrossRef Link) [23] S. Khalili and O. Simeone, “Inter-layer per-mobile optimization of cloud mobile computing: a message-passing approach,” Transaction on Emerging Telecommunications Technology, vol. 27, no. 6, pp. 814–827, 2016. Article (CrossRef Link) [24] S. E. Mahmoodi, R. Uma, and K. Subbalakshmi, “Optimal joint scheduling and cloud offloading for mobile applications,” IEEE Transaction on Cloud Computing, 2016. Article (CrossRef Link) [25] P. Di Lorenzo, S. Barbarossa, and S. Sardellitti, “Joint optimization of radio resources and code partitioning in mobile edge computing,” arXiv preprint arXiv:1307.3835, 2013. [26] S. Cao, X. Tao, Y. Hou, and Q. Cui, “An energy-optimal offloading algorithm of mobile computing based on HetNets,” in Proc. of 2015 International Conference on Connected Vehicles and Expo (ICCVE), Shenzhen, China, pp. 254–258, 2015. Article (CrossRef Link) [27] J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Proc. of IEEE International conference on systems, man, and cybernetics. Computational cybernetics and simulation, Orlando, FL, USA, pp. 4104–4108, 1997. [28] A. Bhattcharya and P. De, “Computation offloading from mobile devices: Can edge devices perform better than the cloud?,” in Proc. of ARMS-CC. ACM, pp. 1–6, 2016. Article (CrossRef Link) [29] M. Safar, I. Ahmad, and A. Al-Yatama, “Energy-aware computation offloading in wearable computing,” in Proc. of Int. Conf. Comput. Appl. IEEE, pp. 266–278, 2017. Article (CrossRef Link) [30] A. R. Jensen, M. Lauridsen, P. Mogensen, T. B. Sørensen, and P. Jensen, “Lte ue power consumption model: For system level energy and performance optimization,” in Proc. of IEEE VTC Fall. IEEE, pp.1–5, 2012. Article (CrossRef Link) [31] G. Auer, O. Blume, V. Giannini, I. Godor, M. Imran, Y. Jading, E. Katranaras, M. Olsson, D. Sabella, P. Skillermark et al., “D2. 3: Energyefficiency analysis of the reference systems, areas of improvements andtarget breakdown,” Earth, vol. 20, no. 10, 2010. [32] S. Cui, A. J. Goldsmith, and A. Bahai, “Power estimation for Viterbi decoders,” Wireless Systems Lab, Stanford Univ., Stanford, CA, USA, Tech. Rep., 2003. [33] O. Munoz, A. Pascual-Iserte, and J. Vidal, “Optimization of radio and computational resources for energy efficiency in latency-constrained application offloading,” IEEE Transaction on Vehicular Technology, vol. 64, no. 10, pp.4738–4755, 2014. Article (CrossRef Link) [34] S. Boyd and L. Vandenberghe, “Convex optimization,” Cambridge university press, 2004. [35] X. Cao, F. Wang, J. Xu, R. Zhang, and S. Cui, “Joint computation and communication cooperation for mobile edge computing,” in Proc. of IEEE WiOpt. IEEE, pp. 1–6, 2018. Article (CrossRef Link) KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2443 Yang Li received the MS degrees from the College of Computer Science and Technology, Jilin University in 2014. Currently, he is PhD candidate at the College of Computer Science and Technology, Jilin University, China. His main research interests include mobile cloud computing, mobile edge computing, distributed computing. Gaochao Xu received the BS, MS, and PhD degrees from the College of Computer Science and Technology, Jilin University in 1988, 1991, and 1995, respectively. Currently, he is the professor and PhD supervisor at the College of Computer Science and Technology, Jilin University, China. His main research interests include distributed system, grid computing, cloud computing, Internet of things, information security, software testing, and software reliability assessment, etc. As a person in charge or a principal participant, he has finished more than 10 national, provincial, and ministerial level research projects of China. Jiaqi Ge received the B.S. and M.S. degree from the College of Computer Science and Technology, Jilin University, China, in 2018, where she is currently pursuing the Ph.D. degree. Her main research interests include mobile cloud computing, mobile edge computing, and the collaborative cloud and edge computing in the Internet of Things. Peng Liu received the M.S. degree from the College of Computer Science and Technology, Jilin University, China, in 2016, and received Ph.D. degree in 2019. Now he is a lecturer in College of Information and Computer Engineering, Northeast Forestry University, Harbin, China. His main research interests include mobile cloud computing, mobile edge computing, edge caching, and the Internet of Things. Xiaodong Fu received the M.Eng. degree from Jilin University in 2005. She is currently a Senior Engineer at the College of Computer Science and Technology, Jilin University, China. Her main research interests include distributed computation and software reliability analysis. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png KSII Transactions on Internet and Information Systems Unpaywall

Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing

KSII Transactions on Internet and Information SystemsJun 30, 2020

Loading next page...
 
/lp/unpaywall/energy-efficient-resource-allocation-for-application-including-dGsyHl9v9y

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Unpaywall
ISSN
1976-7277
DOI
10.3837/tiis.2020.06.006
Publisher site
See Article on Publisher Site

Abstract

This paper studies a single-user Mobile Edge Computing (MEC) system where mobile device (MD) includes an application consisting of multiple computation components or tasks with dependencies. MD can offload part of each computation-intensive latency-sensitive task to the AP integrated with MEC server. In order to accomplish the application faultlessly, we calculate out the optimal task offloading strategy in a time-division manner for a predetermined execution order under the constraints of limited computation and communication resources. The problem is formulated as an optimization problem that can minimize the energy consumption of mobile device while satisfying the constraints of computation tasks and mobile device resources. The optimization problem is equivalently transformed into solving a nonlinear equation with a linear inequality constraint by leveraging the Lagrange Multiplier method. And the proposed dual Bi-Section Search algorithm Bi-JOTD can efficiently solve the nonlinear equation. In the outer Bi-Section Search, the proposed algorithm searches for the optimal Lagrangian multiplier variable between the lower and upper boundaries. The inner Bi-Section Search achieves the Lagrangian multiplier vector corresponding to a given variable receiving from the outer layer. Numerical results demonstrate that the proposed algorithm has significant performance improvement than other baselines. The novel scheme not only reduces the difficulty of problem solving, but also obtains less energy consumption and better performance. Keywords: Mobile edge computing, computation offloading, task dependency, optimization problem, convex optimization This work was supported in part by National Key R&D Plan of China under Grant No. 2017YFA0604500, in part by the Jilin Industrial Innovation Special Fund Project under Grant No. 2017C028-4, and in part by the Jilin Province Science and Technology Development Plan Project under Grant No. 20190201180JC. http://doi.org/10.3837/tiis.2020.06.006 ISSN : 1976-7277 KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2423 1. Introduction With generations of mobile devices launched by mobile device providers, users focus on implementing more complex application on their MDs. More and more emerging applications (i.e. online game, augmented reality, video optimization/acceleration, real-time monitoring, face recognition) are being integrated to form more powerful mobile application[1,2]. Those powerful mobile applications consist of multiple computation tasks with dependencies. In order to accomplish every computation task, the computation and communication resources of MD will be heavily occupied. However, MD's finite battery life and limited computation capacity pose significant challenges on accommodating the resource demand of those applications[3]. Fortunately, offloading computation tasks partly to Mobile Cloud Computing (MCC)[4] provides a promising technique to the elastic scaling of the capability of MDs. However, driven by the vision of 5G communications, the inherent limitation of MCC, i.e. the long transmission distance from MD to MCC, will lead to exceedingly long latency for mobile applications[5]. Moreover, there still exists many urgent issues to solve, such as increasing demand for high bandwidth, decreasing the energy consumption, and high quality of experience. Mobile Edge Computing (MEC)[6] can address those limitation by offloading computation tasks to the near-user MEC server instead of the remote cloud center.[7] indicated that MEC would play an significant role in 5G, the next generation mobile network. MEC[8,9] is regraded as a brilliant solution to overcome these difficulties. By combining with partial computation offloading, the computation task can be divided into two parts, which are executed locally and on the MEC server. [10] deeply studied the computation offloading scheme with the two protocols TDMA and OFDMA in a multiuser Mobile Edge Computing Offloading system by joint optimization the offloading ration, computation and communication resources, and formulated the two computation offloading problem as a convex optimization problem and a mixed-integer problem, respectively. Chen et al.[11] studied a multiuser computational offloading problem in a MEC system under the constraints of communication and computation resources, and designed a distributed computation algorithm which could obtain the Nash equilibrium by using the game theoretic. Chen et al.[12] proposed a decentralized computation offloading algorithm which could achieve a Nash equilibrium in a multiple mobile devices MCC system. [13] proposed a computation offloading framework in a multiple wireless access points MEC system by optimizing the chosen edge server, the CPU frequency and computation and communication resources to trade off the energy consumption and execution time of mobile device including multiple independent tasks. [14,15] all carried out reaserch for the purpose of maximizing the computation rate, but the backgrounds of the proposed problem and the strategies and measures show were different. [14] jointly optimized the transmission power at the access point, the task computation mode(local computing or computation offloading) and time allocation to tasks, and derived the optimal solution by using the convex optimization techniques. In order to prolong the standy time of MD, wireless powered transfer(WPT) and MEC had been integrated together. [15] jointly optimized the computation mode selection(local computing or edge computing), the time allocated to wireless power transfer(WPT) and task offloading in a WPT-assisted multi-MD MEC system. And a joint optimization algorithm based on ADMM decomposition technique was proposed to tackle this problem. In [16], the proposed dynamic computation offloading algorithm achieved the multi-objective optimization by jointly optimizing the computation offloading ratio, the CPU 2424 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing frequency allocated to local execution, and the transmission power for computation offloading under the MEC system with an energy harvesting technique. In the following paper[17], MDs not only could offload their jobs to the MEC server, but also could request computation resource from others MD in the same MEC system. Meanwhile, all the MDs obtained energy from the AP by using WPT technique. [17] aimed at minimizing the whole AP's energy transmitted under the constraints of communication and computation resources, the deadline and the power transmission. [18,19] also gived a study on computation offloading. Although these papers are all about independent task with MD as shown previously, there is no dependency relationship among tasks. As the application becomes increasingly complex, multiple tasks, functions or applications are incorporated into an integrated application. Thus, an in-depth study of offloading computation tasks with dependencies is worthwhile. Coarse-granularity based task offloading policy is used to provide a optimal solution for tasks with dependencies. [20] proposed a collaborative task computation algorithm to prolong the standby time of mobile devices for the application model in the linear topology. [21] provided a comprehensive computation offloading algorithm for computationally intense applications with multiple subtasks to determine which subtasks should be computed in the MD or cloud. [22] aimed to trade-off the energy consumption of MD and latency for application by finding the optimal assignments of tasks executed on local or remote devices. [23] achieved the trade-offs between the energy cost and latency by optimizing the power allocation and the offloading decisions for an application modeled as directed acyclic graph(DAG). [24,25] also could obtain an overall solution by designing a joint scheduling offloading policy for the application with sequential task dependencies. [26] divided the application into a non-offloadable task and multi-offloadable tasks, and a low complexity sub-optimal algorithm was proposed to decide which offloadable task should be transmitted to MEC server. For an application including multiple subtasks depended on each other, [27] proposed a heuristic algorithm based on particle swarm optimizer (PSO) to solve the 0-1 programming problem, where 0 represented local computing and 1 represented edge computing. Though these studies improve the performance of mobile device by using computation offloading, most of those researches focus on the optimal scheduling order. Meanwhile, the transmission power and the CPU frequency allocated to tasks are fixed. Therefore, we make a study on the computation offloading in the mobile application which includes multiple computational intensive dependent tasks for a single MD MEC system, and propose an algorithm that minimizes the energy cost and improves performance by jointly optimizing the offloading ratio, CPU frequency, the transmission power and the transmission time. [28] compared the performance of offloading the dependent tasks from MD to a remote cloud center or an edge server and made the conclusion that offloading to an edge server is a promising technique in providing better performance than a remote cloud server. [29] took use of offloading strategy which migrated tasks in the task graph to the nearby wearable or mobile device through the available wireless communication interface such as Bluetooth or Wi-Fi. Experimental conclusions of [29] demonstrated that the scheduling policy could achieve the two objectives of extending battery lifetime and enhancing performance. At present, there are not many works related to task graph on MEC system, most of them are sub-task granularity and these works aim at different objective. As far as we know, there is no related work with the goal of minimizing energy consumption of MD by dividing the input data of all the subtasks on task graph bit by bit, which is able to guarantee the higher resource utilization and less energy consumption. Accordingly, this paper aims to minimize the energy consumption of task graph by jointly optimizing the resource allocation strategy. KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2425 In this paper, we study an single MD MEC system where MD executes a mobile application made up of multiple computation tasks. The objective of the paper is to minimize the energy consumption of MD with energy-saving resources allocation. In this paper, we model the complex mobile application consisting of multiple interdependent tasks as a DAG task-graph, and develop an energy-efficient computation offloading algorithm by joint optimization the communication and computation resources. Our main contributions are generalized as follows. Firstly, in term of system model, most the computation offloading algorithms do not take into account the computation results feedback, and partial computation offloading for tasks with dependencies is task granularity rather than dividing the input data bit by bit. Therefore, we propose a system model of partial computation offloading for a application consisting of multiple tasks with dependencies, which divides the computation data by bitwise and integrates results feedback. Secondly, in term of problem formulation, for tasks with dependencies, most studies are aimed at achieving the objective of saving energy or reducing latency by optimizing scheduling strategy with fixed transmission power and local computation capacity. However, this paper uses the DVFS technique optimize the CPU frequency, and achieves the optimal transmission power. The corresponding time slots for the local computing, uploading the offloading bits and computation results feedback are allocated with a time division mechanism. Therefore, the problem is formulated as an optimization problem that minimizes the MD’s energy consumption with the constraints of the delay, the computation and communication capacity. Finally, in term of the optimal solution, convex optimization techniques and the Lagrange Multiplier method are used to simplify the problem, and the original non-convex optimization problem is transformed into a univariate nonlinear equation, which accelerates the problem solving. Simulation results demonstrate that the proposed algorithm not only saves energy consumption, but also prolongs the standby time of MD. The rest of this paper is organized as follows. In Section II, we expounds the system model. The problem is formulated and the algorithm for the problem is proposed in Section III and its performance evaluation and simulation results are analysed and shown in Section IV. The conclusion is given in Section V. 2. System Model As shown in Fig. 1, we consider a basic two-node MEC system that consists of single MD and one AP node integrated with a MEC server. In order to reduce the impact of multiple wireless channel creation, frequent requests for the MEC server resources, etc. on task offloading, we conduct the study in the single MEC server scenatio. Both of the two nodes are equipped with one single antenna. This system provides the simplex mode. That is to say, the two processes, offloading input data or receiving computation results, can not be executed through the wireless channel at the same time. The MEC server not only provides the same execution environment but has more sufficient resources than the MD. Therefore, the MEC server can accomplish the computation tasks of application more efficient than the MD. The distance is defined as d between MD and AP, and the bandwidth is denoted as B . 2426 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing Fig. 1. A mobile-edge computing system with a mobile device and an AP 2.1 Computation Application Model We assume that the MD has an application that is composed of N computation-intensive tasks (See Fig. 1, with an example where N = 6 ). Each task can be offloaded to MEC server by using partial computation offloading technique. This application model can be described by using Directed Acyclic Graph(DAG) where the node v in the node set G = (,)   denotes a task in the application, the edge ( vv , ) represents the dependency from task to i j i v and the edge set of the DAG denotes the set of dependencies. represents the  Set j i in-degree set of task i . Task i can not start executing until tasks belonging to Set are completed.To describe the parametric context of each task, a two-tuple ( I ,η ) is defined, ii where iN = 1,..., . Accordingly, I is the size of task i input data which includes the existing data l and the computation results transmitted from tasks in Set . According to [10,17,19,20], i i we learn that there is a linear relationship between the computation result and the input data for the computation task. η is the ratio of the output data to the input data for task i . Task i may need the computation results from related tasks if Set is not null.As such, the total input data size I is ll + η while Set is non-null. If Set is an empty set, I is equal to l . We use i i ∑ ii i i i i k∈Set D , a N*N matrix, represent the task graph. In this paper, we focus on the scenarios where the MD has finite computing capability. In order to accomplish the application, offloading parts of the input data to the MEC server is necessary. We assume that all tasks of the application are executed in a predetermined scheduling policy which results from Breadth-First Traversal(BFT). For example, we can get the scheduling policy ( 1, 2, 3, 4, 5, 6 ) in Fig. 1. And then, we realize our objective which minimizes the energy consumption of the MD. Meanwhile, with the given scheduling strategy, we assume that both local computing and computation offloading of the current task begin simultaneously, which ensures that its dependent tasks have completed correctly. λ is the ratio of the offloading data to the input data for task i , so we can get the constraint of λ : 0≤λ ≤ 1,∀∈ iN {1,..., }. (C1) where λ = {λλ ,..., } denotes the offloading policy of the tasks graph. 1 N KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2427 2.2 Communication Model For each computational intensive task i∈ , its input bits I is split into two parts λ I ≥ 0 i ii and (1−≥ λ )I 0 bits, which denote the number of bits offloaded to the MEC server through ii AP and computed locally, respectively. MD receives the offloading computing results from the MEC server. We introduce the TDMA protocol into the system to avoid any interference among tasks. Because of MD and AP equipped with one antenna, the wireless channel can execute only one process during each time slot. As shown in Fig. 2, the protocol divides the ud whole time T into 2 N time slots, and each task contains two time slots ( tt , ). ii Fig. 2. The TDMA protocol for mutli-task computation offloading in an application 1) Computation Offloading from MD to the AP In the time slot, task offloads input bits to the AP with the transmission power t i λ I i ii t 2 . We define as the channel power gain between MD and AP. Next, the achievable P ≥ 0 h data rate(bits/sec) for uploading offloading input data from the MD to the AP is defined as t 2 Ph u i rB log (1+ ) (1) i 2 where N means the additive white Gaussian noise at the receiver of the AP. For simplifying the computation, we define a function gx ( ) (2−> 1), x 0 . According to (1), we can get t u t the expression of P with the variable r . That is to say, P (2− 1) . After we get the i i i λ I u u u t ii offloading bits λ I and the uploading time t , r can be represented as r = . So P ii i i i i can be re-defined as followed: I λ ii NI λ t Bt 0 i i Pg (2 1) ( ) (2) 2 u ht Based on the actual observation offered in [30], and the equation recommended by the EARTH project[31], we know that the uploading power includes the transmission power t c P and an extra constant circuit power P caused by converting from digital signal to analog i t u t signal, packaging, and so on. Moreover, P is linear with P . Therefore, we give the i i following definition: −= = = 2428 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing uc t P P+κ P (3) i t ti where κ denotes the linear growth and is a constant coefficient without unit. According to (3),the energy consumption of uploading data at MD in time slot t is expressed as I λ u uu t u i i E P t (( g )+κ P )t (4) i i i ti i 2) Downloading the Computation Results from the AP to the MD Considering that the MD needs to receive the computation results from AP, so the delay cannot be ignored. The computation results of task i are η I . And then, the achievable data ii rate for receiving computation results from the AP to the MD is expressed by Ph rB log (1+ ) (5) d 2 where P denotes the transmission power of the AP, which is a constant. Therefore, r is a F d constant. Meanwhile, we have known the amount of the computation results ηλ I . i ii Ultimately, combining (5), we can get the representation as follows: ηλ I i ii t = (6) According to [32,33], the MD power consumption P increases linearly with the download data rate r . So we give the formula of P as follows. d i dc PP+κ r (7) i d dd c c c where is similar to the previous definition . However, is affected by converting P P P d t d from analog signal to digital signal, unpackaging, and so on. κ represents the linearly increasing coefficient. And then, we get the equation of calculating the energy consumed by d d receiving the computation results from AP in the time slot t . By merging (6) and (7), E is i i expressed as the following equation. ηλ IP d dd c i ii d E = P t = (P+= κ r ) ( +κ )η I λ (8) i i i d dd d i i i rr dd 2.3 Computing Model 1) Local Computing: (1−λ )I input data of task i is executed on the mobile device(MD) within a duration t . ii i C denotes the number of CPU cycles required for computing 1-bit of input data at MD, and (1−λ )IC ii f is the CPU frequency allocated to task i , i.e. . In practical application, the f = i i CPU frequency of MD has a maximum value, denoted by f . So f is capped by f , i.e. max i max (1−λ )IC ii ≤ fi ,∀ (C2) max = = = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2429 Also, the computation latency constraint t for local computing of task i must be satisfied as follows: t ≥ 0. (9) Then, the whole local computation tasks must be accomplished before the deadline, i.e. tT ≤ (C3) ∑ i i=1 The energy consumption of task i for local computing is 33 3 (1−λ ) IC ll 3 i i E κκ ft ,∀i (10) i li i l l 2 () t where κ means the effective capacitance coefficient which has relation with the chip structure of MD. According to Fig. 2, for task i , the time that MD starts to transmit input data through wireless channel is simultaneous with starting local execution. Besides, according to (10), the l l bigger t is, the smaller E is. So we can infer that CPU is not in idle state between the end of i i the previous task and the beginning of the next task, which means that local execution lasts the whole time period t . Consequently, the wireless channel occupation time and local computation time should meet the following time constraint for task i . ud l t + t ≤ t ,. ∀i (11) ii i Replacing t with (6), we can rewrite the former time constraint as below. ηλ I ul i ii t + ≤ ti ,. ∀ (C4) ii 2) Edge-Computation: We assume that the network and computational resources of the MEC server are infinite. Owing to the sufficient computation capability of the MEC server, the delay of receiving offloading data, the time spending on accomplishing the offloaded computation task, and the delay of sending computation results are relatively small and negligible at the MEC server. Therefore,we assume that MD immediately receives computation result from the AP when the offloading data transmission is completed. Since the objective is to minimize the energy consumption of mobile device, the energy consumption of MEC server is negligible. 3. Problem Formulation and Optimal Solution In this section, we propose a feasible computation offloading scheme to the application modeled as task graph. In order to minimize the energy consumption of MD, the CPU frequency and the transmission power are optimized for local computing and computation offloading, respectively. The solution process of the optimal computation offloading scheme is shown below. 3.1 Problem Formulation Under the system model above mentioned, we give a trade-off model between the energy consumption of local computing and the energy cost of communication among the AP and the MD to obtain the total minimum energy consumption of the MD. Meanwhile, the trade-off = = 2430 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing model must satisfy the delay constraint, the limited computation and communication resources. From (4), (8) and (10), we can come to the conclusion that all the energy consumption of MD is impacted by local computing, computation offloading and receiving computation results. Learning from the former section, the local energy consumption is influenced by the locally executed bits (1−λ )I and its executed time t , and the energy consumed by communication i i i between the AP and the MD is impacted by the time spending on uploading the offloading bits u uu u ll l t and the offloading bits λ I . Then, Let λ = {λλ ,..., } , t = {tt ,..., } , t = {t ,..., t } , and i i i 1 N 1 N 1 N these three vectors determine how much energy the application will consume. Mathematically, the delay-constrained energy minimization optimization problem is formulated as ud l E : min EE ++ E ∑ ii i u l (,λ t ,t ) i=1 st . . C1, C 2, C3, C 4 ul C5 : tt , >∀ 0 i ii Now we substitute all related equations into problem E , and E is represented as follows. I ln 2λ ii c 3 N P ((1−λ )IC ) uc Bt 0 d ii E : min tP ( +κ (e −+ 1))+( κ )ηλ I +κ 1 ∑ i t t d i i l u l 22 l (,λ t ,t ) hr () t i=1 di st . . C1: 0≤≤ λ 1 ∀i (1−λ )IC ii C 2: ≤∀ f i l max (12) C3: tT ≤ i=1 ηλ I ul i i Ct 4: +≤ t ∀i ii ul C5 : tt , >∀ 0 i ii In Problem E , C1 denotes the constraint of the offloading ratio, C2 is the maximum CPU frequency constraint for each task of the application, and C3 is the deadline constraint. C4 guarantees that the time cost by local computing must be greater than or equal to the time taken by the data transmission and receiving computation results for task i . Note that E is non-convex in general because of the coupling of λ and t in C2. Therefore, we need convert i i E into a convex problem[34] with some measures, and then give the optimal solution. 3.2 Optimal Solution To E This subsection gives the optimal solution of E . To achieve this goal, firstly, we transform C2 into a convex constraint by multiplying both sides of inequality C2 with t . The constraint C2 is converted to C 2′ . (1−λ )IC− f t ≤∀ 0, i. ( C 2′ ) i i max i Then, E is reformulated as follows. 1 KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2431 I ln 2λ ii c 3 N P ((1−λ )IC ) uc 0 Bt d ii E : min tP ( +κ (e −+ 1))+( κ )ηλ I +κ 2 i t t 22 d i i l l u l (,λ t ,t ) hr () t i=1 di st . . C1,3 C , C 4,5 C (13) C 2 : (1−λ )IC− f t ≤ 0 ∀i i i max i (1−λ ) Meanwhile, the function is convex with respect to 01 << λ and t > 0 [35], and i i l 2 () t κ ((1−λ )IC ) l ii hence the equation in the objective function is jointly convex with respect to l 2 () t 01 << λ and 0<< tT . Moreover, the following lemma demonstrates the evidence that i i Problem E is a convex problem. Lemma 1 Problem E is a convex optimization problem. Proof: Because gx () is an exponential function and a convex function, its perspective I λ κ ((1−λ )IC ) u i i l ii function[13], tg () is still convex. Also, is jointly convex function[35]. u l 2 t () t i i Thus, the objective function which is the summation of a set of convex functions, holds the convexity. All constraints are the linear convex function. Consequently, we get the result of Lemma 1. Assume that Problem E is feasible, we use the Lagrange Multiplier method to simply the problem solving. We define α ≥ 0,βγ ≥≥ 0, 0 as the Lagrangian multipliers for C1, i ii C 2′ ,C4, respectively. µ is the Lagrange multiplier for C3. Therefore, the partial Lagrangian function of E is given by I ln 2λ ii c 3 κ N P ((1−λ )IC ) ul u c Bt t 0 d ii (λ , tt , ,α ,βγ , ,µ ) tP ( + (e −+ 1)) ( +κ )ηλ I +κ ∑ i t d i i l 22 l hr () t i=1 di NN N ηλ I lu l ii i + αλ ( − 1)+ β ((1−λ )IC− f t )+ γ (t + − t ) (14) ∑∑ i i i i i max i ∑ i i i ii 11 i 1 +− µ () tT ∑ i i=1 * ul ** Let λ ,, tt denote the optimal solution of E . The optimal solution always satisfies all { } ii i 2 constraints and has the minimum energy consumption of MD. By applying KKT conditions, the following necessary and sufficient conditions must be true. I ln 2λ i i c *2 3 3 κ NI ln 2 u* (P +− κ r )η I 3κ (1 λ ) I C η I ∂ t 0 i Bt d d d ii l i i ** * ii e + − +αβ− IC+γ 0 (a) i ii i * 2 l*2 ∂λ Bh r (t ) r i di d ** II ln 2⋅⋅ λλ ln 2 ii ii N uu ** nI ln 2⋅λ ∂ c 00 Bt⋅⋅ ii Bt * ii (b) = Pe +κ ( −− 1) κ e +γ = 0 tt t i u* 2 2* u ∂⋅ t h h Bt i i *3 3 3 2κ (1−λ ) IC ∂ l ii * ** (c) =− −β f −γ +µ = 0 i max i l* l*3 ∂tt ( ) i i ** αλ ( −= 1) 0,∀i (d) ii = = = == = 2432 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing ** l* β ((1−− λ )IC f t )= 0,∀i (e) i i i max i η I λ ** ul* ii i γ (t + − ti )=0,∀ (f) ii i ** l µ ( tT −= )0 (g) ∑ i i=1 * u* * According to (b), we can get Lemma 2 which describes the relations among λ ,, t γ . { } ii i * u* * Lemma 2 The optimal λ ,, t γ satisfies { } ii i *2 c λ B −1 () Ph +γ i t i (1+ Wi ( + ))∀ , (15) u* t I ln 2 e κ eN ii t 0 Wx () where Wx () defines the Lambert-W function, i.e. x= W () x e . I ln 2⋅λ ii * c *2 ( −1) u* I ln 2⋅λ −1 (P +γ )h Bt⋅ i i t i Proof: With the help of (b), we have ( − 1)e =+ . u* B⋅ t e κ eN it 0 Wx () According to the Lambert-W function, i.e. x= W () x e , which is the inverse function of * c *2 I ln 2⋅+ λ −1 (P γ )h i i t i f () x = xe .We can straightforwardly infer that ( −= 1) W ( + ), u* B⋅ t e κ eN it 0 which leads to the result in Lemma 2 with some simple operations. With some operations on (c), we can get the following expression. *3 3 3 2κ (1−λ ) IC * l ii ** * µ +β fi+∀ γ , . Therefore, we can get the result µ > 0 . Combining i max i l*3 (t ) l* with (g), the summation of is identically equal to , i.e. t T l* t = T (16) ∑ i i=1 which conforms to the monotonically decreasing property of the objective function respect to t . According to (a), (c), (d), we can get the following Lemma 3. In order to reduce the complexity of interpretation, we firstly define c 2 −1 () Ph +γ t i ϕγ ( )= 1+ W ( + ). (17) ii e κ eN t 0 ** l * Lemma 3 The optimal λ , t ,γ satisfies { } ii i κ N ln 2 ηγ η ϕγ () c t 0 i i i i i e + ++ () Pr κ d d d 1 * 2 1−λ Bh r r i dd = () (18) l* 23 t 3κ IC i li The ratio is influenced by the i-th task parameters of η , I and the lagrangian multiplier γ . { } ii i Proof: At first, according to (d), because not all the input data is transmitted to the MEC server, we obtain α = 0 . The result makes sure that the local energy cost is not the maximum. And then, to ensure (e) true, since the CPU frequency f allocated to task i always less than * * f , we obtain β = 0 . Plugging β = 0 into (c), and making some simple manipulations, max i i we obtain the following result. = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2433 *3 3 3 2κ (1−λ ) IC ** l ii µγ+∀ ,. i (19) l*3 (t ) * * At last, we substitute (17), αβ 0, 0 into (a). The Lemma 3 is inferred. ii (1−λ )IC ii We know f ≤ f . Meanwhile, plugging (18) into f , we obtain an i max i 1−λ * * inequality about γ . We introduce the function F () γ for replacing the ratio , i.e. i ii l* 1−λ * * F () γ = . Correspondingly, the range of γ can be described as Proposition 1. ii i l* * * Proposition 1 F () γ is a monotonically increasing function when γ > 0 . The one and only ii i * ( 0) * ( 0) γ > 0 satisfies Ff () γ = existed. The value is defined as γ , and γγ ≤ . i i i max i ii ϕγ () i i Proof: e is an increasing function with γ ≥ 0 because ϕγ () is an increasing i ii function with γ ≥ 0 . Meanwhile, γ is a linear function. Because F () γ is the square root i i ii of the sum of an increasing function, we infer that F () γ is an increasing function with γ ≥ 0 . ii i ( 0) γ →+∞ and F () γ →+∞ . So we can get the unique γ by using the Bi-Section Search i ii i method. The Proposition 1 is proved. * * *3 µγ + 2κ (F (γ )) . (20) i l ii Now, substituting (18) into (19), we get (20). Learning from (18), we acknowledge that µ is associated with γ , η , and the performance parameters of SD. Although the ratio of (18) i i changes over ηγ ,, I , the lagrangian multiplier µ is fixed. Meanwhile, µ is a scalar rather ii i * * than a vector. Therefore, the lagrangian multiplier γ should satisfy γ > 0 . In order to meet i i η I λ ul ** * ii i the condition (f), we get the result tt += because of γ > 0 . Accordingly, we obtain ii i l* Lemma 4 by using the above derivation results, which denotes that the local execution time t can be expressed as a function with a single variable lagrangian multiplierµ . l* Lemma 4 The optimal t can be expressed as l** t =Q () µ = , (21) i i 2 * −1* rr ln 2 (µψ − (µ )) dd i − + −1* 1 Iη η (I r ln 2+ BIηϕ (ψ (µ ))) ii i i d ii i i IC (2κ ) i l l * r r l Q ()µ is monotonically decreasing with µµ ≤ ≤µ . If QT (µ )> or Q () µ < T , λ , ∑ ∑ i i i l u l r l u t , and t do not exist. If TQ < () µ and QT (µ )< , λ , t , and t are unique. ∑ i ∑ i Proof: Firstly, µ =ψγ () is introduced to simplify the derivation and computation, i.e. ii 3 2 ψγ () γ + 2κ F () γ . ψγ () 1+ 6κ FF () γ () γ denotes its derivation. Learning from i i i l i i i i l i i i i Proposition 1, we can get ψγ ()> 1 because F () γ is a monotonically increasing function ii ii F () γ > 0 . Consequently, ψγ () is a monotonically increasing function with γ > 0 . Given ii ii i = = = = = 2434 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing the value of µ , we can get a unique γ , and vice versa. The inverse function of ψγ () is i ii ψγ ()−γ −1 ii i denoted as γψ = ()µ , and F () γ can be rewritten as F () γ = ( ) . As we all ii ii ii 2κ know, the derivative of the original function is equal to the inverse of the derivative of its −1 inverse function in calculus. Hence, 0<= (ψ )(µ ) < 1 , where µ =ψγ () . Learning i ii ψγ′( ) ii l* from Lemma 2 and Lemma 3, we can get the expression of t by solving the simultaneous −1 equation (22). We use ψ ()µ replace the Lagrangian multiplier γ in (23), and we can use a i i * * l* function Q () µ only associated with µ represent t , which is (21). i i  η I λ ul ** ii i tt += ii r (22) (15), (18) l* t = (23) i 2* rr ln 2 F (γ ) d d ii −+ Iη Iη (r ln 2+ Bηϕ (γ )) IC ii ii d i i i i −1 Secondly, based on the property of Lambert-W function ϕ > 0 , and 0( << ψ ) 1 , the i i derived function Q ()µ < 0 , and Q ()µ is µ 's rigid monotony decrease by degrees function. i i 2 −11 − −1 ′′ BI r ln 2ϕ (ψµ ( ))(ψµ ( )) 1 1− (ψ (µ )) i d i i i i + ⋅ −12 12 (I r ln 2+ BIηϕ (ψ (µ ))) i ii i −1 3 3 3IC (2κ ) (µψ − (µ )) i l i Q ()µ < 0 (24) i 1 21 − r r ln 2 (µψ − (µ )) di −− () + −1 1 Iη η (I r ln 2+ BIηϕ (ψ (µ ))) ii i i d ii i IC (2κ ) i l * * ( 0) Thirdly, we get the interval range of γ as 0≤γγ ≤ according to Proposition 1. And, (20) i ii indicates that µ is a monotonically increasing function with γ . We define ( 0) ( 0) ( 0) * µ = max{ψ (0)} and µ = min ψγ ( ) , and the numeric zone of µ is displayed as { } li r ii follows. ( 0) * ( 0) µ ≤µµ ≤ . (25) lr l* * Meanwhile, according to (21), t is monotonically decreasing with µ ≥ 0 . What’s more, l* l * (1) 0≤ t ≤ T . By solving tT = , we can get a unique value of µ , defined as µ . Let i i l l ( 0) (1) r ( 0) * µ = max µµ , and µµ = . The restriction of µ is rewritten as ( ) ll r l * r µµ ≤ ≤µ . (26) By using the well studied methods, i.e. Bi-Section Search, Newton Method, solve µ ψγ ( ),∀i , the numeric zone of γ ,∀i can be achieved with the given lower and upper ii i limits of µ . Ultimately, by judging the value of Q ()µ , i.e. t , we can determine whether problem ∑ i ∑ i * l * u * r l E exists the optimal solution λ , t , and t or not. If QT (µ )> or Q () µ < T , it 2 ∑ i ∑ i = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2435 l r does not exist the optimal solution. If TQ < () µ and QT (µ )< , the unique optimal ∑ i ∑ i solution can be achieved by solving (16). Lemma 4 is proved now. Accordingly, problem E , a multiple variables non-linear optimization problem with multi-constraint, is equivalently transferred to a non-linear equation with a linear inequality constraint. The nonlinear equation is expressed as follows: E : QT ()µ = 3 ∑ i (27) i=1 lr st ..µ ≤µµ ≤ l l Since t is a monotonic decreasing function respect to µ , t inherits the descending i ∑ i characteristic. Therefore, there exists a unique µ to E . Then, we propose our algorithm Bi-JOTD to calculate the optimal solution to E . The solution is the optimal offloading strategy for E , too. The proposed optimization method not only successfully avoids solving a nonlinear convex optimization problem with high dimensions and high orders, but also overwhelmingly decreases on the computational complexity and the computation time to acquire the optimal strategy. The following pseudo-code gives the accurate processes to solve the non-linear equation with a linear inequality constraint. Algorithm 1 calculates the approximate multiplierγ which satisfies (19) with given µ . Bi-JOTD computes the multiplier µ among the linear constraint. After Lagrangian * * multipliers γ and µ are achieved, we can use (15), (18), (21) obtain the final optimal * l * u * resource allocation strategy λ , t , and t . 2436 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing Through analyzing the proposed algorithm Bi-JOTD, the complexity of Bi-JOTD is associated with the iteration number of inner and outer Bi-Section Search algorithms. We define  and  as the complexity of inner and outer algorithms, respectively. inner outer Therefore, the complexity of Bi-JOTD algorithm is  () N  . Compared with the inner outer original Problem E , our proposed algorithm can greatly reduce the complexity. 4. Simulation Results In this section, the simulation results of the proposed computation offloading scheme through joint optimization time allocation and dependency tasks is presented. The scheme is named as Bi-JOTD in the simulation results. Based on [16,23,24], the simulation parameters are set as follows. We assume that the channel reciprocity holds for the downlink and uplink, and thus 222 2 −− 3 ζ hhh . The channel power gain is modeled as hd 10 Φ [24], where Φ stands for ud the short-term fading which obeys the Rayleigh fading. For distance d in meters with the , a 30dB average signal power attenuation is assumed for all the same path-loss exponentζ channels at reference of 1m. Moreover, the input data size and the ratio of the computation results follow the uniform distribution with I ∈[10,100]KB andη ∈[0.01, 0.1] , separately. i i The other detailed parameters are listed in Table 1. Table 1. Simulation Parameters Parameter Value 5 Mbps Bandwidth B Deadline T 1s c c −4 Circuit powers P and P 5.0 *10 W t d Distance between the MD and the MEC server d 100m Path-loss exponent ζ 1.7 −9 White Gaussian channel noise N 10 W MD’s maximum CPU frequency f 1.0GHz max The linear growth coefficient κ 1.0 −27 The effective capacitance coefficient −7 The power consumption of receiving per bit κ 2.86 *10 W bit The required number of CPU cycles per bit C 800 cycles bit Meanwhile, in order to comparison, the following five baselines[5,16,17,23,24,25,26], are displayed. 1) λ = 0.4 : The computation input data are divided into two parts for each task. The ratio λ = 0.4 of input data is accomplished in the MEC server, and the rest of input data is completed in MD. 2) Task: In the task-graph representing the mobile application, some tasks are offloaded to MEC server, and the rest of tasks execute on the mobile device. 3) λ = 0.8 : The offloading ratio of computation data transmitted to MEC server is set as λ = 0.8 . = = = KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2437 4) Ave-JOTD: The offloading ratio λ is set as the average of suboptimal solution λ , i.e. i i λλ = . ii ∑ 5) PSO-JOTD: The suboptimal task offloading scheme is achieved by using particle swarm optimizer (PSO). 4.1 The Validation of the Optimal Solution In this subsection, we verify the correctness and superiority of the proposed algorithm. The energy consumption of the approximate solution is close to the cost of the exact solution in a tolerable accuracy range, which compares the simulation results of different block input data I () KB and the ratio η at the same deadline Ts = 1.0 in Fig. 3 and Fig. 4, respectively. Fig. 3. The energy consumption with different I versus T Fig. 4. The energy consumption with different η versus T 2438 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing By comparing with the energy consumption between the global search with the default step size of 0.001 among the fixed range of offloading ratio λ and the proposed optimization algorithm, the energy consumption of the proposed approximate solution is minimum. The simulation results of Fig. 3 and Fig. 4 provide the evidence that problem E is a convex optimization problem. Meanwhile, the process of solving E is correct. 4.2 The Simulation Results for Task Graph Fig. 5. The energy consumption with fixed and random versus I η T Fig. 6. The energy consumption with fixed η and random I versus T This subsection evaluates the energy consumption of the proposed Bi-JOTD algorithm and other five baselines, which spends on computing and communicating versus the deadline T . KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2439 Fig. 5 makes the comparison simulation of energy consumption with a vector (, I η ) , where ii I is fixed and η is random, and Fig. 6 gives a simulation with random I and fixed η . The i i i i proposed Bi-JOTD algorithm is obviously superior to the other baselines. Specifically, the energy consumption of the proposed algorithm is always less than other baselines, which further displays the advantages of offloading the computation tasks to the MEC server. The minimum energy cost has decreased trend with the increase of T . Therefore, Bi-JOTD algorithm has some advantages in solving multi-task application. Then, making a comparison test between Bi-JOTD and Ave-JOTD, we can see that the energy cost of Bi-JOTD is less than Ave-JOTD with the increase of T . It can be concluded that task's result feedback has a great influence on the ratio of offloading input data. Hence, we should comprehensively take task's feedback into account in the task graph to solve the objective of the formulated problem. Fig. 7. The succeeding assignment ratios with random and versus η I T Fig. 8. shows the relationship of the minimum energy consumption of MD, the input data I and the ratio of the computation results η 2440 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing The figure simulated in Fig. 7 is based on 300 times simulated testing, in which I , η are i i randomly selected on the basis of the above assumptions in every implementation, modeling the actual computation offloading scenario. We simulate the resource allocation, and the statistics of success ratios are brought in Fig. 7. The success ratios of all the schemes increase with T , as we excepted. Besides, the success ratio of Bi-JOTD grows faster than others. Bi-JOTD can achieve a high success ratio even with low latency T . Meanwhile, as time goes by, the success ratio of Bi-JOTD reaches and remains stable. Compared with other 100% baselines, our proposed algorithm has more advantages in a high success ratio. Fig. 8 shows the relationship of the minimum energy consumption of MD, the input data and the ratio of computation results. The energy consumption is achieved by using our proposed algorithm, and Ts = 1.5 . According to Fig. 8, while setting the value of η , the energy consumption increases significantly as the input data increases. When setting the value of the input data I , the energy consumption also shows an increasing trend with the increase of η , but the growth is not very obvious. In particular, the application cannot be accomplished while I = 100KB and η =0.1 . Integrated with the previous simulation results and the optimization processes, the proposed algorithm not only has a great advantage in energy consumption, but also has a good performance on the executability of the computation offloading strategy. Ultimately, combining all figures and the equivalence of problem E , E , and E , we can get the 1 2 3 conclusion that our proposed algorithm not only can obtain higher efficiency, less energy consumption and better performance, but also can be calculated more easily than others. 5. Conclusion This work studies a computation offloading scheme for an application including multiple computation components with dependencies under a single-user MEC system. MEC server assists MD in completing its computation-intensive latency-critical application. The application is modeled as a DAG task-graph. By jointly optimizing the offloading ratio, CPU frequency, transmission power and transmission time, the objective that minimizes the energy consumption of MD is achieved. The problem is formulated as a optimization problem. The nonlinear equation with a linear inequality is obtained by using the Lagrange Multiplier method and convex optimization techniques. A double Bi-Section Search algorithm is proposed to solve the transformed nonlinear equation. Simulation results reveal that the proposed strategy greatly reduces the energy consumption while compared with the used baselines. The proposed computation offloading scheme not only reduces the difficulty of problem solving, but also prolongs the MD’s standy time and achieves better performance. Meanwhile, we will extend our study of using partial computation offloading strategy to deal with the application including dependent tasks to the multiple mobile devices multiple MEC servers scenario. References [1] Z. Q. Jaber and M. I. Younis, “Design and implementation of real time face recognition system (rtfrs),” International Journal of Computer Applications, vol. 94, no. 12, pp. 15-22, 2014. Article (CrossRef Link) [2] J. Kephart and D. Chess, “The vision of autonomic computing,” Computer, vol. 36, no. 1, pp. 41–50, Jan. 2003. KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2441 [3] K. Kumar and Y. H. Lu, “Cloud computing for mobile users: Can offloading computation save energy?,” Computer, vol. 43, pp. 51–56, Apr. 2010. Article (CrossRef Link) [4] N. Vallina-Rodriguez and J. Crowcroft, “Energy management techniques in modern mobile handsets,” IEEE Communications Surveys & Tutorials, vol. 15, no. 1, pp. 179–198, First 2013. Article (CrossRef Link) [5] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” IEEE Communications Surveys & Tutorials, vol. 19, no. 4, pp. 2322–2358, 2017. Article (CrossRef Link) [6] M. Patel, B. Naughton, C. Chan, N. Sprecher, S. Abeta, A. Neal et al., “Mobile-edge computing introductory technical white paper,” ETSI, Sophia Antipolis, France, and MEC, London, U.K., Tech. Rep., pp. 1089–7801, 2014. [7] Y. Jararweh, A. Doulat, O. AlQudah, E. Ahmed, M. Al-Ayyoub, and E. Benkhelifa, “The future of mobile cloud computing: integrating cloudlets and mobile edge computing,” in Proc. of 23rd Int. Conf. Telecommun. (ICT). IEEE, pp. 1–5, 2016. Article (CrossRef Link) [8] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and its role in the internet of things,” in Proc. of 1st Edition MCC Workshop Mobile Cloud Comput. ACM, pp. 13–16, 2012. Article (CrossRef Link) [9] G. I. Klas, “Fog computing and mobile edge cloud gain momentum open fog consortium, etsi mec and cloudlets,” Google Scholar, 2015. [10] A. Al-Shuwaili and O. Simeone, “Energy-efficient resource allocation for mobile edge computing-based augmented reality applications,” IEEE Communication Letter, vol. 6, no. 3, pp. 398–401, 2017. Article (CrossRef Link) [11] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,” IEEE/ACM Transaction on Networking, vol. 24, no. 5, pp. 2795–2808, 2015. Article (CrossRef Link) [12] X. Chen, “Decentralized computation offloading game for mobile cloud computing,” IEEE Transaction on Parallel Distribution System, vol. 26, no. 4, pp. 974–983, 2014. Article (CrossRef Link) [13] T. Q. Dinh, J. Tang, Q. D. La, and T. Q. Quek, “Adaptive computation scaling and task offloading in mobile edge computing,” in Proc. of WCNC. IEEE, pp. 1–6, 2017. Article (CrossRef Link) [14] F. Wang, “Computation rate maximization for wireless powered mobile edge computing,” in Proc of 23rd Asia-Pacific Conf. Commun. (APCC). IEEE, pp. 1–6, 2017. Article (CrossRef Link) [15] S. Bi and Y. J. Zhang, “Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading,” IEEE Transaction Wireless Communication, vol. 17, no. 6, pp. 4177–4190, 2018. Article (CrossRef Link) [16] Y. Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading for mobile-edge computing with energy harvesting devices,” IEEE Journal on Selected Areas in Communication, vol. 34, no. 12, pp. 3590–3605, 2016. Article (CrossRef Link) [17] X. Hu, K.-K. Wong, and K. Yang, “Wireless powered cooperation-assisted mobile edge computing,” IEEE Transaction on Wireless Communication, vol. 17, no. 4, pp. 2375–2388, 2018. Article (CrossRef Link) [18] F. Wang, J. Xu, X. Wang, and S. Cui, “Joint offloading and computing optimization in wireless powered mobile-edge computing systems,” IEEE Transaction on Wireless Communication, vol. 17, no. 3, pp. 1784–1797, 2017. Article (CrossRef Link) [19] Y. Liu, S. Wang, and F. Yang, “Poster Abstract: A multi-user computation offloading algorithm based on game theory in mobile cloud computing,” in Proc. of IEEE/ACM Symp. Edge Comput. (SEC). IEEE, pp. 93–94, 2016. Article (CrossRef Link) [20] W. Zhang, Y. Wen, and D. O. Wu, “Collaborative task execution in mobile cloud computing under a stochastic wireless channel,” IEEE Transaction on Wireless Communication, vol. 14, no. 1, pp. 81–93, 2014. Article (CrossRef Link) [21] S. E. Mahmoodi, K. Subbalakshmi, and V. Sagar, “Cloud offloading for multi-radio enabled mobile devices,” in Proc. of IEEE Int. Conf. Commun. (ICC). IEEE, pp. 5473–5478, 2015. Article (CrossRef Link) 2442 Li et al.: Energy-Efficient Resource Allocation for Application Including Dependent Tasks in Mobile Edge Computing [22] Y.-H. Kao, B. Krishnamachari, M.-R. Ra, and F. Bai, “Hermes: Latency optimal task assignment for resource-constrained mobile computing,” IEEE Transaction on Mobile Computing, vol. 16, no. 11, pp. 3056–3069, 2017. Article (CrossRef Link) [23] S. Khalili and O. Simeone, “Inter-layer per-mobile optimization of cloud mobile computing: a message-passing approach,” Transaction on Emerging Telecommunications Technology, vol. 27, no. 6, pp. 814–827, 2016. Article (CrossRef Link) [24] S. E. Mahmoodi, R. Uma, and K. Subbalakshmi, “Optimal joint scheduling and cloud offloading for mobile applications,” IEEE Transaction on Cloud Computing, 2016. Article (CrossRef Link) [25] P. Di Lorenzo, S. Barbarossa, and S. Sardellitti, “Joint optimization of radio resources and code partitioning in mobile edge computing,” arXiv preprint arXiv:1307.3835, 2013. [26] S. Cao, X. Tao, Y. Hou, and Q. Cui, “An energy-optimal offloading algorithm of mobile computing based on HetNets,” in Proc. of 2015 International Conference on Connected Vehicles and Expo (ICCVE), Shenzhen, China, pp. 254–258, 2015. Article (CrossRef Link) [27] J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Proc. of IEEE International conference on systems, man, and cybernetics. Computational cybernetics and simulation, Orlando, FL, USA, pp. 4104–4108, 1997. [28] A. Bhattcharya and P. De, “Computation offloading from mobile devices: Can edge devices perform better than the cloud?,” in Proc. of ARMS-CC. ACM, pp. 1–6, 2016. Article (CrossRef Link) [29] M. Safar, I. Ahmad, and A. Al-Yatama, “Energy-aware computation offloading in wearable computing,” in Proc. of Int. Conf. Comput. Appl. IEEE, pp. 266–278, 2017. Article (CrossRef Link) [30] A. R. Jensen, M. Lauridsen, P. Mogensen, T. B. Sørensen, and P. Jensen, “Lte ue power consumption model: For system level energy and performance optimization,” in Proc. of IEEE VTC Fall. IEEE, pp.1–5, 2012. Article (CrossRef Link) [31] G. Auer, O. Blume, V. Giannini, I. Godor, M. Imran, Y. Jading, E. Katranaras, M. Olsson, D. Sabella, P. Skillermark et al., “D2. 3: Energyefficiency analysis of the reference systems, areas of improvements andtarget breakdown,” Earth, vol. 20, no. 10, 2010. [32] S. Cui, A. J. Goldsmith, and A. Bahai, “Power estimation for Viterbi decoders,” Wireless Systems Lab, Stanford Univ., Stanford, CA, USA, Tech. Rep., 2003. [33] O. Munoz, A. Pascual-Iserte, and J. Vidal, “Optimization of radio and computational resources for energy efficiency in latency-constrained application offloading,” IEEE Transaction on Vehicular Technology, vol. 64, no. 10, pp.4738–4755, 2014. Article (CrossRef Link) [34] S. Boyd and L. Vandenberghe, “Convex optimization,” Cambridge university press, 2004. [35] X. Cao, F. Wang, J. Xu, R. Zhang, and S. Cui, “Joint computation and communication cooperation for mobile edge computing,” in Proc. of IEEE WiOpt. IEEE, pp. 1–6, 2018. Article (CrossRef Link) KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS VOL. 14, NO. 6, June 2020 2443 Yang Li received the MS degrees from the College of Computer Science and Technology, Jilin University in 2014. Currently, he is PhD candidate at the College of Computer Science and Technology, Jilin University, China. His main research interests include mobile cloud computing, mobile edge computing, distributed computing. Gaochao Xu received the BS, MS, and PhD degrees from the College of Computer Science and Technology, Jilin University in 1988, 1991, and 1995, respectively. Currently, he is the professor and PhD supervisor at the College of Computer Science and Technology, Jilin University, China. His main research interests include distributed system, grid computing, cloud computing, Internet of things, information security, software testing, and software reliability assessment, etc. As a person in charge or a principal participant, he has finished more than 10 national, provincial, and ministerial level research projects of China. Jiaqi Ge received the B.S. and M.S. degree from the College of Computer Science and Technology, Jilin University, China, in 2018, where she is currently pursuing the Ph.D. degree. Her main research interests include mobile cloud computing, mobile edge computing, and the collaborative cloud and edge computing in the Internet of Things. Peng Liu received the M.S. degree from the College of Computer Science and Technology, Jilin University, China, in 2016, and received Ph.D. degree in 2019. Now he is a lecturer in College of Information and Computer Engineering, Northeast Forestry University, Harbin, China. His main research interests include mobile cloud computing, mobile edge computing, edge caching, and the Internet of Things. Xiaodong Fu received the M.Eng. degree from Jilin University in 2005. She is currently a Senior Engineer at the College of Computer Science and Technology, Jilin University, China. Her main research interests include distributed computation and software reliability analysis.

Journal

KSII Transactions on Internet and Information SystemsUnpaywall

Published: Jun 30, 2020

There are no references for this article.