{'fraction_non_alphanumeric': 0.045485124831813425, 'fraction_numerical': 0.013903423531170578, 'mean_word_length': 4.452822498471571, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computation Offloading in Heterogeneous Mobile Edge Computing with Energy Harvesting

Energy harvesting aided mobile edge computing (MEC) has gained much attention for its widespread application in the computation-intensive, latency-sensitive and energy-hungry scenario. In this paper, computation offloading from multi-MD to multi-MEC-s in heterogeneous MEC systems with energy harvesting is investigated from a game theoretic perspective. The objective is to minimize the average response time of an MD that consists of communication time, waiting time and processing time. M/G/1 queueing models are established for MDs and MEC-ss. The interference among MDs, the randomness in computation task generation, harvested energy arrival, wireless channel state, queueing at the MEC-s, and the power budget constraint of an MD are taken into consideration. A noncooperative computation offloading game is formulated. We give the definition and existence analysis of the Nash equilibrium (NE). Furthermore, we reconstruct the optimization problem of an MD. A 2-step decomposition is presented and performed. Thereby, we arrive at a one-dimensional search problem and a greatly shrunken sub-problem. We can obtain the optimal solution of the sub-problem by seeking the finite solutions of its Karush-Kuhn-Tucker (KKT) conditions. Thereafter, a distributive NE-orienting iterated best-response algorithm is designed. Simulations are carried out to illustrate the convergence performance and parameter effect.


INTRODUCTION
M OBILE edge computing (MEC) that provides cloud services within the vicinity of mobile device (MD) via the radio access network can effectively enhance the computing power of MD and reduce latency [1]- [3]. Computation offloading, which leverages powerful MEC servers to augment the computing capability of less powerful MDs, is a key computing paradigm used in MEC. In [4], computation offloading strategy optimization with multiple heterogeneous servers in MEC is investigated. Three multi-variable optimization problems are studied, and corresponding efficient numerical algorithms are proposed. In [5], the computation offloading problem is formulated as graph cut problem, and a solution based on spectral clustering computation is developed. In [6], a lightweight and efficient user level online offloading framework for MEC, is presented. Real experiments with Android systems and simulations using large-scale data from a cellular network provider are preformed to prove the efficiency of the proposed framework. In [7], the multi-user computation offloading problem for mobile-edge cloud computing is studied under a multi-channel wireless interference environment. A multi-user computation offloading game is formulated, and a distributed Nash equilibrium (NE) achieving computation offloading algorithm is designed.
To prolong the lifetime of the battery, energy harvesting technology being capable of converting the energy from the environment (e.g., solar, ambient radio-frequency (RF) signals) into electrical energy has been widely utilized in wireless communications [8] [9]. The energy management of the stored harvested energy at the battery plays a centric rule in energy harvested aided wireless networks. In [10], energy efficient resource allocation in a time division multiple access (TDMA) based wireless energy harvesting sensor network is studied. The closed form expression for the optimization problem is obtained, and thereafter solved by utilizing Karush-Kuhn-Tucker (KKT) conditions. In [11], hybrid energy harvesting communication systems are modeled based on their probabilistic natures. An integrated Markov energy model is designed. In [12], beamforming implementation in energy harvesting wireless networks is surveyed. Different beamforming approaches in each network topology are classified according to its design objective.
Over the past years, massive multi-player online game, virtual reality (VR), and artificial intelligence (AI)-based applications (e.g., augmented reality and face detection) have emerged on smart MDs. High computation capacity requirement, low latency, heavy energy consumption, and the stringent equipment-size constraint have brought great challenges on smart MDs, especially for the CPU and battery. Combing the virtues of the two aforementioned technologies, energy harvesting MEC could augment the MD to handle the computation-intensive, latency-sensitive and energy-hungry applications. In [13], a green MEC system with energy harvesting devices has been considered, and an effective Lyapunov optimization-based dynamic computa-tion offloading algorithm is developed. The proposed algorithm jointly decides the offloading decision, the CPU-cycle frequencies for mobile execution, and the transmit power for computation offloading. In [14], an efficient reinforcement learning-based resource management algorithm is designed for energy harvesting MEC. The proposed algorithm learns on-the-fly the optimal policy of dynamic workload offloading to the centralized cloud and edge server provisioning to minimize the long-term system cost (including both service delay and operational cost). In [15], the computation offloading process in energy harvesting MEC is modeled as a Markov decision process (MDP) with no prior statistic information. Thereafter, reinforcement learning algorithms are utilized to derive the optimal offloading policy. In [16], the multi-user multi-task computation offloading problem for green MEC is investigated. Lyaponuv optimization approach is utilized to determine the energy harvesting policy and the task offloading schedule. Centralized and distributed greedy maximal scheduling algorithms are proposed. In [17], the energy harvesting edge computing is investigated, and an effective and efficient MDP-based energy harvesting and data transmission scheduling strategy is designed. In [18], computation offloading is discussed in an edge-computing system consisting of energy harvesting MDs and a dispatcher. Online rewards-optimal auction is developed to maximize the long-term sum-of-rewards for processing offloaded tasks. In [19], computation efficiency maximization problems are investigated in wirelesspowered MEC networks. Partial and binary computation offloading modes for TDMA and non-orthogonal multiple access (NOMA) are respectively considered. In [20], deep reinforcement learning-based online offloading framework to maximize the weighted sum computation rate in wireless powered MEC networks with binary computation offloading is proposed. The proposed algorithm optimally adapts wireless resource allocations and task offloading decisions to the time-varying wireless channel conditions.
In this paper, we investigate the computation offloading in multiple heterogeneous MEC networks with energy harvesting. There are multiple MDs and multiple MEC serves (MEC-ss) from different MEC networks. Besides tackling locally, each energy harvesting aided MD could partially or fully offload its computation tasks to MEC-ss via wireless channels. There are interferences when MDs offload tasks to MEC-ss simultaneously over the shared wireless channel. Thereby the data transmission time is influenced for each MD. We settle M/G/1 queueing models for MDs and MECss. Tasks from different MDs wait in a queue at each MECs. Therefore the waiting time is affected for each other. That is to say, MDs' offloading strategies have impact on response time of each other. For each MD, the offloading should consider physical conditions: The computation task generation, the harvested energy arrival, the wireless channel state, the queueing time, and the power budget constraint. How to choose MEC-ss and how many should be offloaded becomes a challenging problem for each MD. First, a noncooperative game framework is established to describe the MDs' offloading. In the game, MDs are players and the action is a vector that corresponds to the offloading amount of tasks for each MEC-s (the value is 0 for these MEC-ss that are not selected for offloading) and for local process. There are constraints on actions to comply with physical conditions. The payoff is the average response time of computation offloading for each MD that includes the communication time, the computing time, and the waiting time. Next, the best-response iterated algorithm is designed for the proposed game. Although the optimization problem of each MD is intractable, it is decomposed into a 2-step structure: one dimensional search and a sub-problem. The sub-problem is NOT convex, but it can be solved through searching over the finite solutions of KKT conditions.
In conclusion, the contributions of the paper are in threefold. • We consider multiple heterogeneous energy harvesting MEC systems with multiple MDs and multiple MEC-ss. The randomness of computation task generation, harvested energy arrival, wireless channel state, queueing at the MEC-s, the power budget constraint, and the interference among MDs when offloading are taken into account.
• A game theoretic framework is developed. We formulated a noncooperative computation offloading game for MDs, an action vector is designed to denote the offloading amount for these chosen MEC-ss. In addition, the NE is defined and its existence is analyzed.
• The one-MD optimization problem is solved by a 2step decomposition and KKT conditions. Thereafter, a NE-orienting distributive iterated best-response algorithm is derived of the game. Numerical results demonstrate the convergence and parameter effect of the proposed algorithm.
The rest of the paper is structured as follows. The system model is presented in Section 2, and we formulate the noncooperative game. In Section 3, we carry out analysis on the optimization problem of one MD and the game. Next, the NE-orienting iterated algorithm is proposed in Section 4. We show simulations and numerical results in Section 5. Finally, Section 6 concludes the whole paper.

SYSTEM MODEL AND PROBLEM FORMULATION
As shown in Fig. 1, consider multiple heterogeneous MEC networks consisting of M MDs and N MEC-ss. The MD is denoted as MD 1, · · · , MD M . The MEC-s is denoted as MEC-s 1, · · · , MEC-s N . Formally, M = {0, · · · , M } is the MD set, and N = {1, · · · , N } represents the MECs set. Each MD is equipped with energy harvesting component that can extract energy from the environment (e.g., light, thermal, kinetic, magnetic field sources). Generally, the computation capability of the MEC-s surpasses that of the MD, thereby the MD prefers to offloading computation tasks to the MEC-s. An MD chooses an MEC-s for computation offloading in the light of some merits, e.g., the real-time vicinity, the wireless channel state, etc. Denote that MD i offloads computation tasks to MEC-s j with probability p i,j . Apparently, j∈N p i,j = 1. We suppose that the MDs share the same wireless frequency bandwith for computation offloading. Consider M/G/1 model for an MD, and assume that the computation tasks generate at MD i according to a Poisson process with arrival rate λ i . Furthermore, the stream of generated computation tasks is divided into the offloaded computation task sub-stream with rateλ i and local processing sub-stream with rateλ i , where λ i =λ i +λ i . The computation tasks offloaded from MD i to MEC-s j constitute a Poisson stream with arrival rateλ i,j = p i,jλi . For MEC-s j, the received computation tasks from MDs compose a Poisson stream with arrival rate π j = i∈Mλ i,j . M/G/1 queueing model is erected for each MEC-s. Denote the execution requirements (e.g., number of processor cycles to be executed) of computation tasks generated at MD i as independent and identically distributed (i.i.d.) random variable r i . Let f i and F j be the processor's computing speed (cycles per second, i.e., HZ) of MD i and MEC-s j, respectively. The amount of data to be communicated between MD i and MEC-s j is depicted as i.i.d. random variables A i,j . The data transmission rate between MD i and MEC-s j is R i,j . The time of locally processing at MD i is ri fi . The processing time of offloaded computation tasks from MD i to MEC-s j is ri Fj + Ai,j Ri,j , where ri Fj is the computing time and Ai,j Ri,j is the data transmission time. The processing time of computation tasks at MEC-s j can be characterized by random variable τ j with mean and second moment The average waiting time of computation tasks at MEC-s j can be given by [21] ω j = π jτ 2 where ζ j = π jτj is the utilization of MEC-s j. The average response time of offloaded computation tasks from MD i to MEC-s j can be expressed as The average response time of generated computation tasks on MD i is given by The channel coefficient between MD i and MEC-s j is h i,j , the channel bandwidth B, the transmission power from MD i to MEC-s j is P i,j . The data transmission rate is given by The power consumption can be expressed by where ξ i,j = N0+Ij |hi,j | 2 . The average energy consumption of data transmission from MD i to MEC-s j for a computation task offloading is P i,jĀ Ri,j . The average data transmission energy consumption for a computation task offloading at MD i can be written as Power consumption due to computation at MD i can be given by η i f 3 i , where η i is the computation energy efficiency [22]. The average computation power consumption at MD i can be described as where σ i =λ ir i fi is the processor utilization of MD i, P s is the power consumption when no computation is executed. The average power consumption of communication and computation at MD i can be expressed as Assume that the harvested energy arrival of MD i is i.i.d with rate E i . The greedy strategy of harvested energy usage, i.e., utilizing the available harvested energy preferentially, is optimal with high probability [9]. Therefore, the average extra power that is constrained can be written as P i − E i . MD i aims to minimize the average response time under the power constraint. Mathematically, where C i is the power constraint on MD i. MDs are selfinterested and compete each other to minimize its own average response time by adjusting the computation offloading strategy. Formally, the noncooperative game of MDs can be formulated as where Ω = M is the set of players, is the offloading strategy 1 of player i, and U i = T i is the payoff.

PROBLEM ANALYSIS
Optimization problem of an MD is analyzed in Section 3.1. To analyze and handle the formulated problem conveniently, we first reconstruct the objective function and the constraints. The corresponding KKT conditions are derived. However, it is very difficult to solve. Next, a 2-step decomposition strategy is built, and we further reexpress the optimization problem accordingly. The optimization can be decomposed into a one-dimension search together with a reduced subproblem. In Section 3.2, game analysis is performed. The definition and existence of mixed strategy NE are investigated.
l,j , and ν i,j = 1. In the paper, we focus on the computation allocation strategy. When the data transmission rate {R i,j } j=1,··· ,N is added in the strategy, it corresponds to the joint allocations of computation and resource.
The processor utilization constraint (11c) can be expressed as The power constraint (11d) can be written as α i,j ,β i,j , γ i,j , δ i,j , φ i,j , and ν i,j are constant with respect to {λ i,j } j=1,··· ,N , the objective and the constraints are rewritten as the functions of {λ i,j } j=1,··· ,N , explicitly and concisely. Thereafter, the KKT conditions can be obtained in Lemma 1.
Proof: Please see Appendix A.
In (P 2 ), we first fix the sum ofλ i,j , i.e., N l=1λ i,l = t i , in the constraint. Then, we vary the sum in feasible scope. t i can be viewed as an intermediate variable. Thereby, (P 2 ) can be tackled by a 2-step strategy. First, for a given t i ∈ [0, λ i ], solve the following shrunken problem, 2 i.e., (P 3 ).
2. The solution of (P 3 ) is investigated in Section 4.
Next, find the optimal t * i = inf

Game analysis
In the paper, we consider the computation tasks and the response time in average sense, i.e., depicted by the arriving rate and average response time, respectively. Therefore mixed strategy is appropriate for the game analysis. To begin with, the mixed strategy NE of the formulated noncooperative game G is described in Definition 1.
Let Π i be the set of probability measures over the pure strategy (action) set S i . σ i ∈ Π i is a mixed strategy of MD i, and σ −i denotes the set of mixed strategies of players except i.
Proof: According to the von Neumann-Morgenstern expected payoff theory, we have That is to say, only pure strategy deviations when determining whether a given profile is an NE. Hence, we have Property 1.
Regarding the existence, we have the following Lemma.

Lemma 3. G has at least one mixed strategy NE.
Proof: The action set S i is nonempty and compact, the payoff function T i is continuous. According to [23], the game has a mixed strategy NE.

ALGORITHM DESIGN
In this section, we turn our attention to solve the shrunken problem (P 3 ) at first. After that, we conceive an NEorienting algorithm.
(P 3 ) is a fractional programming problem, and is not convex in general. The KKT conditions can be derived in Lemma 4.

Algorithm 1: Optimal offloading algorithm for MD i given other MDs' offloading policies
Step 1: Step 3: k = k + 1, go to Step 2 until convergence.
Step 4: t * = a+b 2 . The optimal policy is the solution of (26) given t * .

Lemma 4.
For optimization problem (P 3 ), the KKT conditions can be described as where ǫ j , ̟ j , and ρ are multipliers, Compared with (21), (26) has been greatly reduced. The variables {λ i,1 , · · · ,λ i,N } have been decoupled. Each variable can be obtained independently by solving a quintic equation with constant coefficients. Generally, KKT conditions give necessary but NOT sufficient solutions. However, (26) has finite solutions. A quintic equation has five solutions, then we have at most 5 N combinations. By exhausting these combinations, we can get the optimal one. 3 We design Algorithm 1 to attain the best response of an MD when other MDs' offloading policies are fixed. Mathematically, Algorithm 1 is plotted to get the solutions of optimization problem (P 2 ). The proposed 2-stage strategy is utilized. In Algorithm 1, we depict a golden section search method for the one-dimensional search in handling is obtained by acquiring the solution of the KKT conditions (26). Finally, we get the optimal offloading policy and the average response time.
In Algorithm 2, each MD has a feasible initial offloading policy, S (0) i i∈M . In the k-th iteration, MD i derives its 3. The time efficiency is not high especially when N is large.
Step 2: For every i ∈ M, compute the offloading policy S optimal offloading policy, S (k+1) i , by applying Algorithm 1, under the circumstances that other MDs employ offloading policies in (k − 1)-th iterations, S (k) −i . All M MDs complete the renewals in the iteration. The execution of the iterative algorithm terminates when satisfying a stoping criterion. Denote the outcome of Algorithm 2 as S * i = (λ * i,1 , · · · ,λ * i,N ). We have the following mixed strategy NE solution. When a task arrives at MD i, it is locally processed with probability

NUMERICAL RESULTS
In this section, simulations are performed to verify and exhibit the effectiveness and efficiency of the proposed algorithm. We first explore the convergence performance, and then the average response time regarding parameters such as the computation capability of MEC-s, data transmission rate, and computation task generation rate are investigated, respectively.
In the simulations, we discuss the 2-MD and 2-MECs scenario. The parameters are listed in Table 1 unless specified otherwise. We consider Rayleigh fading environ-ment, the power gains of the wireless channel, {|h i,j | 2 } j=1,2 i=1,2 , are exponentially distributed with mean 0.3, 0.2, 0.25, 0.25, respectively. P i,j (i = 1, 2, j = 1, 2) can be computed according to (6). Observe that φ i,jλ i,j 2 ti +λ i,j δ i,j +λ i,j ti µ i,j + ν i,j − 1 = 0 should not reach for the optimal solutions. Otherwise, the objective function value is infinite. Therefore, the corresponding Lagrange multiplier ̟ j = 0. When (26) has no solutions, arbitrary allocation policy that satisfies (28) is adopted. Once (28) has on solutions, it means that the power budget is NOT sufficient for offloading t tasks under the setting rate. Fig. 2 demonstrates the convergence performance of the proposed algorithm. Two wireless channel configurations are given. From both figures, we can see that Algorithm 2 converges since 90-th iteration. In the figures, MD 2 has better average response time performance. It is because that MD 1 has higher computation task generation rate. Another observation is that the channel configuration has few influences on the convergence performance. This can be explained as follows: In the simulation settings, we have fixed transmission rate R i,j . The channel power gain |h i,j | 2 is related to the transmitting power of the mobile devices P i,j . P i,j is related to the constraint (11d). When (11d) is lose, the channel power gain |h i,j | 2 has no effect on the formulated problem. Therefore, the two wireless channel configurations in the figure have similar convergence performance. Fig. 3 plots the average response time with respect to the computation capability of MEC-s. F 1 , F 2 , and F 1 together with F 2 vary with the coefficient c in Fig. 3(a), Fig. 3(b), and Fig. 3(c), respectively. In Fig. 3(a) and Fig. 3(c), the average repones time decreases with the increment of c, harshly at first and smoothly later. This is because that with better computation capability of MEC-s 1 and MEC-s 2, the processing time and the waiting time at MEC-s become shorter (the data transmission time remains static) under some computation offloading strategy. Then the average response time diminishes. At the beginning, the processing time and the waiting time dominate in the average response (a) |h 1,1 | 2 = 0.1375, |h 1,2 | 2 = 0.4655, |h 2,1 | 2 = 0.3196, |h 2,2 | 2 = 0.1509.
(b) |h 1,1 | 2 = 0.0615, |h 1,2 | 2 = 0.0198, |h 2,1 | 2 = 0.5159, |h 2,2 | 2 = 0.0227. time, and the drop is apparent. With the decrement of the processing and waiting time, they are not dominant after a value of c. Then the decrement of the average response time becomes moderate. In Fig. 3(b), we can observe that the average response time increases in a short range (c = 0.4, 0.8, 1.2) at first and then decreases. The reasons are as follows. The offloading strategy alters for c = 0.4, 0.8, 1.2. Under different allocation strategies, the average response time have a short range increment (c = 0.4, 0.8, 1.2 for MD 1 and c = 0.4, 0.8 for MD 2). When the offloading strategy remains static, the average response time decreases with the increment of F 2 . For MD 1, the increment is harsh, and for MD 2, moderate. This shows that more computation tasks of MD 1 are offloaded to MEC-s 2. As for MD 2, more tasks are processed at MEC-s 1 than MEC-s 2. Fig. 4 draws the average response time regarding the data transmission rate. R 1,1 and R 2,2 alter with the coefficient c in Fig. 4(a) and Fig. 4(b), respectively. In Fig. 4(a), we can find that with the increment of R 1,1 , the response time of MD 1 lessens apparently in the commence and then moderately. Meanwhile, the average response time of MD 2 has an increment at first and remains constant then. The reasons are as follows. When R 1,1 increases, the data transmission time of MD 1 decreases. At the same time, the portion of the transmission time in the average response time (data transmission time plus processing time plus waiting time) becomes smaller. Then the decrement is drastic initially and moderate then. Regarding MD 2, the offloading policy changes at first, and the average response time increases. When the offloading policy remains static, R 1,1 has few effects on its average response time. In Fig.  4(b), the average response time of MD 2 decreases with the increment of R 2,2 for similar reasons as in Fig. 4(a). The difference is that there is a increment from c = 1 to c = 1.2 since the offloading policy alteration. The average response time of MD 1 decreases firstly since the offloading policy shift, and remains static as R 2,2 has few effects on its average performance under fixed offloading policy. Fig. 5 shows the average response time when the computation task generation rate modifies. From Fig. 5(a) and Fig. 5(b), we can see that when the computation task generation rate of MD 1 (2) increases, its average response time increases apparently. It is because the processing time, the waiting time, and the transmission time increase with the augment of task generate rate. For MD 2 (1), its average response time expands mildly at the beginning and modifies slightly then. This can be explained as follows. When MD 1 (2) has more tasks for offloading, the waiting time of MD 2 (1) increases under fixed offloading strategy. Thus the average response time of MD 2 (1) increases at first. When the average response time is larger than a value, MD 2 (1) changes its offloading policy to alleviate the influence, and the response time changes slightly.

CONCLUSION
In the paper, we discuss the computation offloading of multi-MD to multi-MEC-s over wireless interference channels in energy harvesting aided heterogeneous MEC networks. Considering the stochastic features of computation (c) F 1 = 20 * c, F 2 = 18 * c.  (b) λ 2 = 4 * c,r 2 = 1.1 * c,r 2 2 = 0.9 * c 2 ,Ā 2,1 = 1 * c, A 2,2 = 1 * c,Ā 2 2,1 = 0.5 * c 2 , andĀ 2 2,2 = 0.5 * c 2 . task generation, wireless channel, harvested energy, queueing time, the interference among MDs, the transmission power budget, and the average response time minimization aim of each MD, we establish a noncooperative computation offloading game framework. Via the problem reconstruction, the 2-step decomposition, and the solution of KKT conditions, the optimization of one MD is settled. Thereby, we present an iterated distributive NE-orienting algorithm. The convergence performance and effect of parameters are investigated in the simulations. Future topics include considering the transmission rate allocation together with computation offloading, the time efficiency improvement, etc.

APPENDIX A PROOF OF LEMMA 1
The KKT conditions of (P 1 ) are written as T i can be reexpressed as where H i,j is given by (31). Consequently, where ∂Hi,j ∂λ i,j is given by (33). The processor utilization constraint can be written as (34). Thus ∂(ζ j − 1) ∂λ i,j = 2 (φ i,j + δ i,j )λ i,j Then we arrive at (21), which completes the proof.