Computation efficiency optimization in UAV-enabled mobile edge computing system with multi-carrier non-orthogonal multiple access

In this paper, we study the issue of fair resource optimization for an unmanned aerial vehicle (UAV)-enabled mobile edge computing (MEC) system with multi-carrier non-orthogonal multiple access (MC-NOMA). A computation efficiency (CE) optimization problem based on the max-min fairness principle under the partial offloading mode is formulated by optimizing the subchannel assignment, the local CPU frequency, and the transmission power jointly. The formulated problem belongs to the non-convex mixed integer nonlinear programming (MINLP), that is NP-hard to find the global optimal solution. Therefore, we design a polynomial-time algorithm based on the big-M reformulation, the penalized sequential convex programming, and the general Dinkelbach’s method, which can choose an arbitrary point as the initial point and eventually converge to a feasible suboptimal solution. The proposed algorithm framework can be also applied to computation offloading only mode. Additionally, we derive the closed-form optimal solution under the local computing only mode. Simulation results validate the convergence performance of the proposed algorithm. Moreover, the proposed partial offloading mode with the CE maximization scheme outperforms that with the computation bits (CB) maximization scheme with respect to CE, and it can achieve higher CE than the benchmark computing modes. Furthermore, the proposed MC-NOMA scheme can attain better CE performance than the conventional OFDMA scheme.

In the past decade, the rapid growth of mobile communication business has promoted the great progress of wireless communication and network technologies, which gives birth to mobile cloud computing (MCC), i.e., allowing computing tasks to run remotely at cloud data centers [1]. However, the user equipment (UE) is usually far away from the cloud data center, which may result in a long time of data exchange between them. As a consequence, MCC is difficult to meet the computing service requirements of various real-time mobile applications [2]. Recently, Internet of Things (IoT) has been applied to many aspects, which can connect things via networks [3]. In contrast to the conventional MCC, mobile edge computing (MEC) has potential wide application ranges for IoT as a newly emerging technology [4]. The key idea of MEC is to decentralize computing servers at the wireless network edge closing to UEs so as to improve the computation capability of UEs and reduce the corresponding task delay and consumed energy greatly.

On the one hand, non-orthogonal multiple access (NOMA) is considered as a promising multiple access scheme in the future wireless communication systems [5]. The fundamental concept of NOMA is to serve more than one UE in one orthogonal resource block (ORB) by using superposition coding and multi-user detection technologies [6]. For instance, power-domain NOMA assigns different power levels to the UEs at the transmitter and exploiting successive interference cancelation (SIC) technology to decode overlapping signals at the receiver [7]. In [8], a NOMA-based resource allocation algorithm was designed for a cluster-based cognitive industrial IoT. This is very different from orthogonal multiple access (OMA) schemes, e.g., time division multiple access (TDMA), orthogonal frequency division multiple access (OFDMA), which service one UE at most in a time-domain ORB and a frequency-domain ORB, respectively.

However, the system complexity and decoding delay will become high if all users are multiplexed in one ORB. To this end, multi-carrier NOMA (MC-NOMA), i.e., the combination of NOMA and OFDMA, can be employed to meet the needs of massive connectivity and improve the transmission efficiency in MEC systems [9–12], where all users are divided into several NOMA groups and one NOMA group can occupy one ORB. In [9], a MEC-NOMA technique was proposed to minimize the consumed energy of MEC users, where the users can simultaneously upload their tasks via the uplink NOMA protocol. In [10], the total computation overhead minimization problem was investigated by coalition formation game theory in a MC-NOMA based MEC system. Moreover, [11] and [12] provided their separate theories and simulation results to the energy minimization in MC-NOMA based MEC systems, which show the application of MC-NOMA in MEC can improve the system performance greatly when compared to the OMA counterpart.

On the other hand, unmanned aerial vehicle (UAV) has attracted a great quantity of research interests in the wireless communication. The benefit of UAV as the aerial base station (BS) is great when compared with the traditional ground BS, such as flexible movement, high probability of line-of-sight (LoS) channel, and low cost and easy deployment. Therefore, MEC servers can be carried to UAV for the purpose of providing flexible computing services [13–18]. In [13], the Lyapunov optimization framework was invoked for minimizing the average weighted consumed energy of a UAV-MEC system. In [14], the resource optimization for maximizing computation rate was firstly studied in a wireless powered UAV-MEC system. In [15], user association and path planning were studied in a UAV-MEC system with energy restriction. In [16], a double deep Q-network based algorithm was developed to maximize the system reward of a UAV-MEC network. Moreover, [17] studied the sum-power optimization for a MEC system with several UAVs, which was addressed by solving the decomposed subproblems iteratively. Besides, [18] minimized the consumed energy of a UAV-MEC system, which can enable fairness among all the users.

It can be seen that the delay minimization, the energy consumption minimization, and the computation bits (CB) maximization are the main focus of resource allocation in MEC systems. However, with the rapid growth of communication business, the communication industry is becoming a major energy consumer. Against this background, it is critically important to consider green communication so as to improve the efficiency of resource utilization per joule. Particularly, it is suggested that future MEC pursue the maximization of computation efficiency (CE), i.e., the ratio of the total CB to the associated energy consumption [19–23]. In [19], the max-min CE optimization problem was studied in a MEC system powered by wireless energy. In contrast to [19, 20] maximized the weighted sum of CE in a MEC system. While TDMA is considered in both [19] and [20, 21] and [22] extended the CE maximization frameworks to MEC networks under NOMA and OFDMA, respectively. Furthermore, [23] aimed to maximize the CE of a multi-UAV based MEC system.

Motivated by the above discussions, we study the CE optimization problem in a UAV-MEC system with MC-NOMA, which is oriented towards computation-efficient massive connections and flexible deployment in the future MEC network.

The rest of this paper is organized as follows. The system model and problem formulation are presented in Section 2. The proposed CE optimization algorithm was detailed in Section 3. Two benchmark computing modes are discussed in Section 4. The relevant simulation results are provided in Section 5. Finally, the conclusion of this paper is made in Section 6.

In this paper, we focus on a computation-efficient UAV-enabled and MC-NOMA based MEC system, where a UAV is fitted with a MEC server to supply computing services for the ground UEs via the LoS connections. Besides, MC-NOMA is employed for the uplink transmissions between all the UEs and the UAV, in which all the UEs are divided into several user groups without repetition, and the UEs in the same group can adopt uplink NOMA to upload their tasks simultaneously to the UAV-MEC server in one ORB.

On this basis, we formulate the CE optimization problem based on the max-min fairness principle under the partial offloading mode by optimizing the subchannel assignment, the UE’s CPU frequency, and the transmission power jointly. Considering that the formulated problem belongs to the non-convex mixed-integer nonlinear programming (MINLP), we design a two-layer iterative algorithm based on the big-M reformulation, the penalized sequential convex programming (SCP), and the general Dinkelbach’s method to enjoy a polynomial-time complexity. The proposed algorithm can start from an arbitrary point and eventually converge to a feasible suboptimal solution. Moreover, the other two typical computing mode are discussed as benchmarks, including the local computing only mode and the computation offloading only mode. Specially, the closed-form best optimal solution is derived under the local computing only mode, while a suboptimal solution is obtained using the above algorithm under the computation offloading only mode.

Finally, simulation results confirm that the proposed algorithm achieves good convergence performance and is robust to random initial points. In addition, the proposed CE maximization framework has obvious computation-efficient advantages over the CB maximization framework under the partial offloading mode. Furthermore, the CE performance of the partial offloading mode is superior to the benchmarks computing modes. Moreover, the MC-NOMA scheme exhibits higher CE than the OFDMA scheme in the proposed UAV-MEC system.

As illustrated in Fig. 1, we focus on a UAV-MEC system where one rotary-wing UAV with an embedded MEC server provides computing services for K ground UEs denoted by the set \(k \in \mathcal {K} = \{1, 2, \ldots, K\}\), in which the UAV and all K UEs are each equipped with one single-antenna. We construct a three-demission (3D) Cartesian coordinate model, where the UAV and the kth UE are located at q_u=[X,Y,H] and \(\mathbf {q}_{k} = [x_{k}, y_{k}, 0], \forall k \in \mathcal {K}\), respectively. As a result, the distance between the UAV and the kth UE is given by \(d_{k} = \sqrt {(X - x_{k})^{2} + (Y - y_{k})^{2} + H^{2}}, \forall k \in \mathcal {K}\).

UAV-enabled MEC system model

Full size image

3.1 Communication model

In the proposed UAV-MEC system, the overall system bandwidth W is partitioned into N orthogonal subchannels denoted by the set \(n \in \mathcal {N} = \{1, 2, \ldots, N\}\) satisfying \({\sum \nolimits }_{n \in \mathcal {N}} {{W_{n}}} = W\), where W_n is the bandwidth of the nth subchannel. Besides, each subchannel is the frequency-flat block fading channel, i.e., the subchannel remains unchanged during one time block with duration T (T>0). We assume the UAV knows the perfect channel state information (CSI) of all subchannels as well as the computation information of all the UEs. Moreover, it is assumed that all subchannels are each dominated by LoS links since the altitude of the UAV is usually much higher than that of the UEs. Hence, by adopting the commonly used free-space path loss model [13–18], the channel power gain on the nth subchannel between the kth UE and the UAV can be modeled as

where μ₀ represents the channel power gain at the reference distance d₀=1 m.

Particularly, one time block with duration T is composed of the following three stages. In the first stage, MC-NOMA is invoked for the uplink transmissions between the UEs and the UAV, i.e., each orthogonal subchannel can accommodate multiple users by employing NOMA. Specially, all the UEs are divided into different groups to upload their tasks simultaneously to the UAV-MEC server, where different groups access different subchannels and the UEs in the same group occupy one subchannel via NOMA. In the second stage, the UAV exploits SIC technique to decode the uploaded tasks from the UEs and the UAV-MEC server computes the decoded tasks. Finally, the UAV transmits the task results computed by the UAV-MEC sever to all the UEs in the third stage. Besides, each UE can perform its local computing throughout the entire time block duration T. Similar to [19–23], we only consider the first stage due to the strong computational capability of the UAV-MEC sever as well as the small data size of the computed results.

3.2 Local computing

For the local computing at the UEs, the total CB \(L_{k}^{\text {loc}}\) and total energy consumption \(E_{k}^{\text {loc}}\) of the kth UE during the entire time block T can be, respectively, expressed as [19–23]

where C_k denotes the CPU cycles of computing 1-bit of input task of the kth UE, f_k (cycles/second) is the CPU frequency at the kth UE, and γ_k is the CPU capacitance coefficient of the kth UE.

3.3 Computation offloading

To enable parallel execution, the proposed UAV-MEC system adopts the partial computation offloading mode, where the task of each UE can be divided into two parts, i.e., one part computed locally at the UE and another part uploaded to the UAV-MEC sever.

Let ρ_k,n denote the subchannel assignment indicator, \(\forall k \in \mathcal {K}, n \in \mathcal {N}\). Specially, ρ_k,n=1 if the kth UE is assigned to the nth subchannel, otherwise ρ_k,n=0. According to the uplink NOMA protocol, the received signal at the UAV on the nth subchannel can be expressed as

where s_k,n represents the transmitted signal of the kth UE over the nth subchannel satisfying \(\mathbb {E}\{ |s_{k, n}|^{2} \} = 1\), p_k,n is the corresponding transmission power, and z_n stands for the additive white Gaussian noise (AWGN) at the nth subchannel, i.e., \(z_{n} \sim \mathcal {CN}\left ({0, n_{0} W_{n}} \right)\), in which n₀ denotes the single-sided power spectral density of AWGN.

On each subchannel, the SIC decoding order of the uplink NOMA is always from the strong UE to the weak UE so as to avoid consuming significant transmission power for compensating the path loss [24]. Then, the uplink offloading rate of the kth UE on the nth subchannel is given by

where \({S_{k,n}} = \left \{ {\mathcal {K}|{g_{i,n}} < {g_{k,n}}, i \ne k} \right \}\) denotes the set of the UEs in the set \(\mathcal {K}\) whose channel power gain are worse than that of the kth UE.

Therefore, the number of offloaded bits of the kth UE on the nth subchannel can be calculated as

and the corresponding consumed energy is

where ξ is the amplifier coefficient at the UE, and p_c is the fixed circuit power consumption for the computation offloading process at the UE.

According to [19] and [20], the CE of the kth user can be quantified as

3.4 Problem formulation

With the purpose of guaranteeing fairness for all the UEs, the subcarrier assignment {ρ_k,n}, the local CPU frequency {f_k,n}, and the transmission power {p_k,n}, \(\forall {k\in \mathcal {K}}, n\in \mathcal {N}\), are jointly optimized to maximize the minimum CE among all the UEs. Therefore, the CE optimization problem based on the max-min fairness principle can be formulated as

where \(R_{k}^{\min }\) in the constraint \(\mathcal {C}_{1}\) is the minimum CB per second required by the kth UE, \(P_{k}^{\max }\) in the constraint \(\mathcal {C}_{2}\) denotes the maximum power consumption of the kth UE, \(f_{k}^{\max }\) in the constraint \(\mathcal {C}_{3}\) denotes the maximum CPU frequency of the kth UE, the constraint \(\mathcal {C}_{4}\) indicates that the nth subchannel can support at most M_n UEs, and the constraints \(\mathcal {C}_{5}\) and \(\mathcal {C}_{6}\) ensure that one UE can occupy at most one subchannel.

It is clearly that the problem in (8) belongs to the non-convex MINLP, that is NP-hard to find the global optimal solution in general. In this section, we design a polynomial-time iterative algorithm based on the big-M reformulation, the penalized SCP, and the generalized Dinkelbach’s method to obtain a feasible suboptimal solution of (8).

4.1 Big-M reformulation

Due to the product term ρ_k,np_k,n in (8), it is not easy to design an efficient algorithm for solving (8). Fortunately, we can use the big-M reformulation to decompose the product terms [25]. With the help of big-M reformulation, we first introduce auxiliary variables \({\tilde p_{k,n}} = {\rho _{k,n}}{p_{k,n}}, \forall k \in \mathcal {K}, n \in \mathcal {N}\). Then, all the product terms ρ_k,np_k,n in (8) will be replaced with \({\tilde p_{k,n}}\), which yields

where

Afterwards, we add the following constraints into (8):

Moreover, we can rewrite the binary constraint \(\mathcal {C}_{6}\) in its equivalent continuous form as follows:

Therefore, we can reformulate (8) as the following equivalent problem:

where \(\Theta = \left \{ {{\rho _{k,n}},{p_{k,n}},{{\tilde p}_{k,n}},{f_{k,n}},\forall k \in \mathcal {K},n \in \mathcal {N}} \right \}\).

The big-M reformulation linearizes the term ρ_k,np_k,n, such that ρ_k,n is separated from p_k,n, which helps to design an efficient CE optimization algorithm. Moreover, if the constraints \(\mathcal {C}_{6a}\), \(\mathcal {C}_{6b}\), and \(\mathcal {C}_{7} \sim \mathcal {C}_{10}\), are satisfied, then \({\tilde {\mathcal {C}}}_{1}\) is equivalent to \(\mathcal {C}_{1}\), and \({\tilde {\mathcal {C}}}_{2}\) is also equivalent to \(\mathcal {C}_{2}\). Hereto, the original MINLP problem in (8) has been equivalently transformed into a more tractable form in (13). However, the transformed problem in (13) still belongs to the non-convex max-min fractional programming (MMFP), which can not be addressed directly. To this end, we combine fractional programming theory with sequential convex programming (SCP) [26, 27].

4.2 Sequential convex programming

In particular, the core idea of SCP is to convert a non-convex optimization problem into a series of convex optimization problems and solve them iteratively, where the non-convex terms in each iteration will be substituted by appropriate inner convex terms [28].

We note that \({{\tilde R}_{k,n}}\) in (13) can be expressed as the subtraction of two concave functions \({{\tilde R}_{k,n,1}}\) and \({{\tilde R}_{k,n,2}}\), i.e.,

At the tth iteration (t≥1) of SCP, we can obtain an upper bound \(\tilde R_{k,n,2}^{\left (t \right)}\) of \({{\tilde R}_{k,n,2}} \) by using its first-order Taylor expansion, which is expressed as

where \({\tilde p_{i,n}^{\left ({t - 1} \right)}}\) is the value of \({{{\tilde p}_{i,n}}}\) at the (t−1)th iteration of SCP. Similarly, we can obtain a lower upper \({\tilde \rho }_{k,n}^{\left ({t} \right)}\) of \(\rho _{k,n}^{2}\) by using its first-order Taylor expansion, which is expressed as

where \({\rho _{k,n}^{\left ({t - 1} \right)}}\) is the value of ρ_k,n at the (t−1)th iteration of SCP. Furthermore, since the function \(\min \{\cdot \}\) is increasing, we can obtain a lower bound \(\tilde \eta _{k}^{\left (t \right)}\) of \({\tilde \eta }_{k}\) at the tth iteration of SCP, i.e.,

As a result, a convex approximation of (13) at the tth iteration of SCP can be cast as

4.3 Generalized Dinkelbach’s method

It can be observed that all the constraints in (18) are convex, i.e., the feasible region of (18) is a convex set. In addition, for each \({\tilde {\eta }}_{k}\), \(\forall k \in \mathcal {K}\), its numerator is non-negative and concave, meanwhile its denominator is positive and convex. Therefore, the problem in (18) belongs to the convex MMFP, which can be efficiently addressed by the generalized Dinkelbach’s method [26].

Let λ^∗ and Θ^∗ denote the optimal objective and the optimal solution of (18), respectively, then

Moreover, Θ^∗ is the optimal solution of (18) if and only if the following condition is satisfied: [26]

Based on (20), we can transform (18) into its associated subtractive form as

where (21) is the problem to be solved at the qth iteration (q≥1) of the generalized Dinkelbach’s method, and \(\lambda ^{\left (q - 1 \right)}\) is the corresponding iterative parameter at the (q−1) iteration. At the qth iteration, we compute the optimal solution \(\Theta ^{\left (q \right)}\) of (21) for the fixed \(\lambda ^{\left ({q - 1} \right)}\), then we update \(\lambda ^{\left (q \right)}\) by using the obtained \(\Theta ^{\left (q \right)}\), i.e.,

By solving (21) iteratively and setting a very small iteration tolerance ε>0, ε-optimal solution \(\Theta ^{*} = \Theta ^{\left (q \right)}\) of (18) is achieved if the following condition holds: [26]

Since the objective function in (18) is not smooth, we introduce a new auxiliary variable given as

Accordingly, the equivalent form of (18) can be expressed as:

Based on the above analysis, a two-layer iterative algorithm consisting of the outer iterative procedure based on the SCP and the inner iterative procedure based on the generalized Dinkelbach’s method can be employed to obtain a feasible suboptimal solution of (13). Nevertheless, the above algorithm requires a feasible point of (13) as the initial point. If the above algorithm starts from a feasible point, then all the generated points will be feasible; otherwise, it may fail at the first iteration due to the infeasibility [28]. However, finding a feasible point in the non-convex feasible region of (13) is very hard. To avoid this, we will integrate the penalized SCP [29] with the framework of the above algorithm, which can start from an arbitrary point.

4.4 Penalized sequential convex programming

To ensure that a sequence of feasible solutions can be generated, the abovementioned SCP needs a feasible initial point. Generally, an infeasible initial point misleads intermediate solutions obtained by the iterative process, which often causes an incorrect local solution. However, it is usually NP hard to find a feasible initial point for non-convex problems, e.g., the CE optimization problem in (13). To avoid the above initialization requirement, it is a good choice to adopt the penalized SCP. Specially, auxiliary variables are introduced to relax all non-convex inequality constraints, and penalty parameters are added into the objective function, so that we can randomly generate the initial point and then feasible solutions can be gradually obtained with the increasing of iterations.

It can be found that only the constraints \({\tilde {\mathcal {C}}}_{1}\) and \({\mathcal {C}}_{6b}\) are non-convex in (13). To this end, we relax the constraint \({\tilde {\mathcal {C}}}_{1}\) via slack variables s_1,k\((s_{1, k} \geq 0, \forall k \in \mathcal {K})\) and the constraint \({\mathcal {C}}_{6b}\) via a slack variable s₂ (s₂≥0). Then, the constraints \({\bar {\mathcal {C}}}_{1}\) and \({\tilde {\mathcal {C}}}_{6b}\) in (25) are, respectively, reformulated as

In order to minimize the violations of non-convex constraints, we subtract the sum of the slack variables from the objection function of (25). Therefore, (25) can be reformulated as

where (27) is the problem to be solved at the tth iteration of the penalized SCP, and \(\tau ^{\left (t - 1 \right)}\) is the corresponding penalty factor at the (t−1)th iteration and is updated for the next iteration by using the following equation:

Here, \(\tau _{\max }\) denotes the upper bound of \(\tau ^{\left (t \right)}\) so as to avoid numerical problems if \(\tau ^{\left (t \right)}\) is too large and provide convergence if a feasible region is not found, and μ is the predefined increasing factor [29]. Moreover, existing optimization tools, like YALMIP [30], CVX [31], CVXQUAD [32], can be used to solve the convex problem in (27).

In summary, we propose a CE optimization algorithm based on the big-M reformulation, the penalized SCP, and the generalized Dinkelbach’s method, which is presented in Algorithm 1.

Theorem 1

Algorithm 1 can converge to a local optimal solution of (13).

Proof

See Appendix A. □

Remark 1

The stopping criterion of Algorithm 1 includes two parts, while one is that the objective value of (13) is nearly unchanged, and the other is that the sum of slack variables is very small, which indicates that the solution obtained by Algorithm 1 is a feasible solution of (13).

4.5 Computational complexity analysis

In Algorithm 1, the computational complexity is mainly determined by solving problem (27) L₁L₂ times, where L₁ and L₂ denote the required iterations of the inner loop and outer loop, respectively. In addition, (27) is solved by using standard optimization tools based on the interior-point method whose complexity is \(\mathcal {O}\left ((4 K N + N + 2)^{3.5}\log (1/\varepsilon)\right)\), where \(\mathcal {O}\left (\cdot \right)\) denotes the big-O notation and ε represents the solution accuracy [33]. Thus, the proposed Algorithm 1 has an acceptable polynomial time computational complexity, i.e., \(\mathcal {O}\left (L_{1} L_{2} (4 K N + N + 2)^{3.5}\log (1/\varepsilon)\right)\).

In this section, we discuss the other two computing modes as benchmarks, namely the local computing only mode and the computation offloading only mode. The local computing only mode requires that all the UEs only perform their local computing but never offload their tasks to the UAV-MEC server, while the computation offloading only mode requires that all the UEs only offload their tasks to the UAV-MEC sever but never perform their local computing.

5.1 Local computing only mode

Under the local computing only mode, the CE of the kth UE can be expressed as

The corresponding CE optimization problem is formulated as

In (30), we find that the optimization variables \(\{f_{k},k\in \mathcal {K}\}\) are decoupled. Moreover, the objective function consists of the “min” function and K independent CE expressions, i.e., \(\{\eta _{L,k},k\in \mathcal {K}\}\). Without loss of optimality, we can maximize each CE expression η_L,k to maximize the objective function of (30). Thus, (30) can be decomposed into K sub-problems, in which the kth sub-problem is given by

By setting the first order derivative of η_L,k to be zero, i.e.,

the zero point of ∂η_L,k/∂f_k can be calculated as

The numerator of ∂η_L,k/∂f_k is a concave and monotone decreasing function with respect to f_k≥0, while the denominator of ∂η_L,k/∂f_k is positive for f_k≥0. Thus, the closed-form optimal solution of (31) can be derived as

As a result, the best optimal solution of (30) is given by

Theorem 2

The problem in (30) has many optimal solutions with the same objective value.

Proof

See Appendix B. □

Remark 2

Since (30) has many optimal solutions with the same objective value, “the best” means that the optimal solution in (35) can make the CEs of all the UEs as large as possible.

5.2 Computation offloading only mode

Under the computation offloading only mode, the CE of the kth UE can be expressed as

The corresponding CE optimization problem is formulated as

Since (37) is similar to (8), the framework of Algorithm 1 can be applied to solve (37). To avoid repetition, the detailed solution to (37) is omitted here.

In this section, we provide the relevant simulation results to first demonstrate the convergence of the proposed Algorithm 1 and then evaluate the performance of the proposed partial offloading scheme by using the local computing only scheme, the computation offloading only scheme, and the OFDMA scheme as benchmarks. In the simulations, we consider a UAV-MEC system as illustrated in Fig. 2, where K=8 UEs are randomly located in a squared area of size 1000 m ×1000 m, and the UAV is located at q_u=[0,0,100] [23]. To reduce the decoding complexity and time delay in one NOMA group, the maximum number of the UEs supported by each subchannel is considered as two, i.e., \(M_{n} = 2, \forall n \in \mathcal {N}\) [34]. Besides, the maximum power consumption of the kth UE is \(P_{k}^{\max } = P_{\max }, \forall k \in \mathcal {K}\), where \(P_{\max }\) is defined as the maximum local power consumption. For convenience, the normalized CE and CB are used as the performance indicators, and their units are, “Bits/Joule/Hz” and “Bits/Hz”, respectively. Except where otherwise stated, we present the remaining simulation parameters in Table 1, which are based on the typical settings in [21–23].

The locations of the UEs and the UAV in x-y axes

Full size image

Figure 3 plots the convergence curves of the iterative objective value \(\Gamma ^{\left (t \right)}\) and the sum of penalty values \(\pi _{1}^{\left (t \right)}\) for the proposed Algorithm 1 under the partial offloading mode, where the maximum local power is set as \(P_{\max } = 0.2\mathrm {W}\). As seen from Fig. 3, when the number of iterations increases, the sum of penalty values \(\pi _{1}^{\left (t \right)}\) decreases accordingly. Since \(\pi _{1}^{\left (t \right)}\) denotes the sum of violations of non-convex constraints, the generated solutions by Algorithm 1 tend to be feasible for (8). In fact, Algorithm 1 can be interpreted as an infeasible method for the original MINLP problem in (8). Specially, Algorithm 1 may generate a sequence of infeasible solutions if it starts from an infeasible point but can converge to a feasible suboptimal solution of (8) at last. Moreover, the proposed Algorithm 1 has a fast convergence rate because the iterative objective value \(\Gamma ^{\left (t \right)}\) needs only 5 iterations to be stable and converge to a ε-optimal solution for the specified precision ε. Furthermore, the average iterations of Algorithm 1’s inner loop and outer loop are 6.08 and 6.49, respectively. The above observations demonstrate the convergence property and the convergence efficiency of Algorithm 1.

Convergence of Algorithm 1 with respect to the iterative objective value and the sum of penalty values under the partial offloading mode

Full size image

Table 2 evaluates the impact of random initial points on the CE performance of Algorithm 1 under the partial offloading mode, where \(P_{\max } = 0.2\mathrm {W}\). The random initial points for Algorithm 1 are given by \( \rho _{k,n}^{\left (0\right)} = \) rand([0.5, 1]), \(p_{k,n}^{\left (0 \right)} = 0, f_{k,n}^{\left (0\right)} = 0, \forall k \in \mathcal {K}, n \in \mathcal {N}\), where rand([0.5, 1]) stands for a real random variable uniformly distributed in the range of [0.5, 1]. As shown in Table 2, with these random initial points, Algorithm 1 will eventually converge to one of the three different local optimal values, denoted by, η₁=10.455 bits/Joule/Hz with the probability 11%, η₂=11.487 bits/Joule/Hz with the probability 15%, and η₃=12.455 bits/Joule/Hz with the probability 74%, respectively. Moreover, the probability of converging to η₃ is 74% for one run time, which means that Algorithm 1 has a 98.4% probability of converging to the best local optimal values within 3 run times. In other words, Algorithm 1 is robust to different initial points due to the high probability of converging to the best local optimal values with very few run times.

In Figs. 4 and 5, we compare the proposed partial offloading mode with the CE maximization scheme referred as “MaxCE” and the CB maximization scheme referred as “MaxCB” in terms of CB and CE with varying the maximum local power consumption \(P_{\max }\), respectively. In particular, the CB maximization scheme is to maximize the minimum CB among all the UEs, which is implemented by using the simplified Algorithm 1 without the inner loop, i.e., λ^(q)=0,∀q. From the above two figures, the “MaxCE” scheme has both CB and CE in common with the “MaxCB” scheme when \(P_{\max }\) is not so large, i.e., \(P_{\max } \leq P_{\max }^{\text {th}}\). Due to the limitation of \(P_{\max }\), the resource allocation strategies of the two schemes are identical when \(P_{\max }\) is small, which leads to the above result. In the case of small \(P_{\max }\), the CE and CB of the two schemes increase with \(P_{\max }\) since the CB increases faster than the power consumption. But on the other hand, when \(P_{\max } > P_{\max }^{\text {th}}\), although the “MaxCB” scheme has larger CB than the “MaxCE” scheme, the “MaxCE” scheme has obvious advantages on the CE compared with the "MaxCB" scheme from Fig. 5. This is because the "MaxCB" scheme maximizing the CB will consume more inefficient power to achieve higher CB but the “MaxCE” scheme will still adopt the solution maximizing the CE instead of consuming inefficient power when \(P_{\max } > P_{\max }^{\text {th}}\), i.e., the solution of the “MaxCE” scheme is not affected by the increase of \(P_{\max }\). Consequently, both CE and CB of the “MaxCE” scheme keep unchanged when \(P_{\max } > P_{\max }^{\text {th}}\).

Comparison of CBs under partial offloading mode with CE maximization and CB maximization

Full size image

Comparison of CEs under the partial offloading mode with the CE maximization scheme and the CB maximization scheme

Full size image

Figure 6 presents the CE versus the maximum local power consumption \(P_{\max }\) under different computing modes with the proposed CE maximization frameworks. From Fig. 6, it can be found that the partial offloading mode has a much higher CE performance than the other two computing mode, especially when compared to the local computing only mode. The reason is that the partial offloading scheme can offer the flexibility to adjust the resource allocation for the task offloading and the local computing. However, the local computing only scheme allows the UEs to perform their local computing only regardless of the channel conditions, and the computation offloading only mode completely uploads the tasks of the UEs to the UAV-MEC server even if the channel conditions are bad, so their CE performances are greatly compromised. Besides, the computation offloading only mode exhibits better CE performance than the local computing only mode since the former can yield better computation-efficient benefits than the latter when \(P_{\max }\) is not so small.

Comparison of CEs among different computing modes

Full size image

Figure 7 shows the max-min fairness with the proposed CE maximization framework under different computing modes, where the minimum CE, the average CE, and the best CE of all the UEs are compared, and the maximum local power is set as \(P_{\max } = 0.2\mathrm {W}\). With respect to the above three performance indicators, the proposed partial offloading mode has the best performances, while the local computing only mode has the worst performances. The reason for explaining this is similar to the simulation result in Fig. 6, which verifies the effectiveness of the proposed scheme in the max-min fairness.

Comparison of fairness among different computing modes

Full size image

Figure 8 illustrates the CE versus the maximum local power consumption \(P_{\max }\) in the partial offloading mode with the proposed MC-NOMA scheme and the OFDMA scheme. In the OFDMA scheme, each UE can access one subchannel at most and each subchannel can support one UE at most, which is implemented by letting the maximum number of the UEs supported by one subchannel to be one, i.e., \(M_{n} = 1, \forall n \in \mathcal {N}\). To ensure fair comparison, the number of subchannels in the OFDMA scheme is set as N=8, but the other simulation parameters are consistent with the proposed MC-NOMA scheme. It can be observed from Fig. 8 that the proposed MC-NOMA scheme is significantly greater than the OFDMA scheme on the CE performance. This is because NOMA can service more users than OFDMA at the same frequency-domain resource block, i.e., the multiplexing gain can be obtained when NOMA is applied.

Comparison of CEs under partial offloading mode with MC-NOMA and OFDMA

Full size image

In this paper, we have studied a max-min fairness based CE optimization problem in a UAV-MEC system with MC-NOMA, where the joint optimization of the subchannel assignment, the local CPU frequency, and the transmission power is considered. Since it is NP-hard to find the global optimal solution of the formulated non-convex MINLP problem, we design a polynomial-time algorithm to obtain a feasible suboptimal solution. In specify, the big-M reformulation is employed firstly to obtain the equivalent continuous form of the original problem. Next, by applying the penalized SCP and the general Dinkelbach’s method, a two-layer iterative algorithm is designed, which is able to start from an arbitrary initial point and finally converge to a feasible suboptimal solution. We also analyze the corresponding CE optimization problems in the benchmark computing modes. The relevant simulation results have demonstrated that the proposed Algorithm 1 enjoys a good convergence performance. Moreover, the proposed computation-efficient scheme is superior to the other benchmark schemes. Besides, when compared with the conventional OFDMA scheme, the proposed MC-NOMA scheme can get higher CE.

Proof of Theorem 1

First, we prove the convergence of the algorithm based on the SCP and generalized Dinkelbach’s method to solve (13), namely Algorithm 2. Let \(\Theta _{(t)}^{*}\) and \({\tilde {\Gamma }}^{(t)}(\Theta _{(t)}^{*})\) respectively denote the optimal solution and the optimal objective value of (18) at the tth iteration of SCP; meanwhile, the corresponding objective value of (13) is given by \(\Gamma (\Theta _{(t)}^{*})\), then we have

At the tth iteration of SCP, we can find from (38) that (a) holds since \({\tilde {\Gamma }}^{(t)}(\Theta _{(t)}^{*})\) is a lower bound of \(\Gamma (\Theta _{(t)}^{*})\), (b) holds if (18) can be solved globally, which can be guaranteed by using the generalized Dinkelbach’s method, and (c) holds because \(\Theta _{(t-1)}^{*}\) is used as the local point of the first-order Taylor expansion based on (17). From (38), it can be seen that the objective value of (13) is non-decreasing. Since the objective value of (13) is upper bounded, Algorithm 2 can gradually converge to a local optimal solution of (13). Next, it is ready to prove the convergence of Algorithm 1. If the penalty factor τ is large enough and the sum of slack variables is very close to zero, then (27) can be rewritten as (25). Therefore, Algorithm 1 is equivalent to Algorithm 2, which indicates that Algorithm 1 will converge to a local optimal of (13). Please refer to [29] for more detail.

Proof of Theorem 2

Based on (35), we denote \(\eta _{L,k} \left (f_{L,k}^{*}\right)\) as the optimal CE of the kth UE. We further define \(\tilde {k}\) as the index of the UE whose optimal CE is smallest, i.e.,

According to (39), we have

where \({\mathcal K} \setminus \tilde k = \{ {k|k \in {\mathcal K},k \ne \tilde k} \}\). For each \(k \in \mathcal {K} \setminus \tilde {k}\), there exists at least one \(f_{k} \in \left [ f_{L,k}^{\text {LB}}, f_{L,k}^{\text {UB}} \right ]\), such that \(\eta _{L,k}\left (f_{L,k}^{*}\right) \geq \eta _{L,k}(f_{k}) \geq \eta _{L,\tilde {k}}\left (f_{L,\tilde {k}}^{*} \right)\). Note that the solution \(\left \{f_{k}, \forall k \in \mathcal {K} \setminus \tilde {k}, f_{L,\tilde {k}}^{*} \right \}\) has the same objective value of (30) as the optimal solution \(\left \{f_{L,k}^{\ast }, \forall k \in \mathcal {K} \right \}\) in (35). Therefore, (30) has many optimal solutions with the same objective value.

Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.

UAV:

Unmanned aerial vehicle

MCC:

Mobile cloud computing MEC: Mobile edge computing

OMA:

Orthogonal multiple access

TDMA:

Time division multiple access

OFDMA:

Orthogonal frequency division multiple access NOMA: Non-orthogonal multiple access

MC-NOMA:

Multi-carrier non-orthogonal multiple access

IoT:

Internet of Things

ORB:

Orthogonal resource block

SIC:

Successive interference cancelation

UE:

User equipment

BS:

Base station

LoS:

Line-of-sight

CB:

Computation bits

CE:

Computation efficiency

MINLP:

Mixed-integer nonlinear programming

SCP:

Sequential convex programming

CPU:

Central processing unit

3D:

Three-demission

CSI:

Channel state information

AWGN:

Additive white Gaussian noise

MMFP:

Max-min fractional programming

The authors thank the editor and anonymous reviewers for offering their valuable comments, which greatly improve the quality of this paper.

This work was supported in part by Open Research Fund of Nanjing University of Aeronautics and Astronautics (KFJJ20190409), National Natural Science Foundation of China (61971220) and Open Research Fund Key Laboratory of Wireless Sensor Network and Communication of Chinese Academy of Sciences (2017006), and Postgraduate Research and Practice Innovation Program of Jiangsu Province (KYCX19 _0191).

Authors and Affiliations

1. College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, 29 Jiangjun Ave., Nanjing, 210016, China

   Fangcheng Xu, Xiangbin Yu, Jiali Cai & Guangying Wang

2. Key Laboratory of Wireless Sensor Network and Communication, Shanghai Institute of Microsystem and Information Technology of Chinese Academy of Sciences, 865 Changning Road, Shanghai, 200050, China

   Xiangbin Yu

Contributions

FX, YX, JC, and GW conceived and designed the research and simulations. FX designed the main idea and algorithm and drafted the main manuscript of this work. YX gave crucial suggestions and reviewed and modified the drafted manuscript. JC helped to perform the simulation and analyse the result. GW helped to draft the manuscript. All authors reviewed and edited the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Xiangbin Yu.

Competing interests

The authors declare that they have no competing interests.

Publisher’s Note

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

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

Reprints and permissions