1 Introduction

With the enduring prosperity of wireless communication techniques, pervasive Wireless Wide Area Networks (WWANs), e.g., the LTE-A networks, the next generation networks (5G) and beyond, have triggered the dramatic shift in people lifestyle and bring plentiful benefits to contemporaries. With WWANs, users can easily access remote Internet resources and enjoy services via Base Stations (BSs) anytime and anywhere, e.g., online shopping on the way to work, watching live broadcast videos during heavy traffic jam, playing interactive games on a high-speed train, to name a few. An irresistible tendency is that the contemporaries are heavily relying on WWANs to fulfill their transmission and computation requirements. Unfortunately, such a lifestyle shift could suffer from severe service degradation under massive transmission and computation scenarios, where huge volumes of mobile traffic are generated and aggregated at the side of network edge, exerting significant pressure on cellular BSs. Even more seriously, users may not be served properly when the BSs are heavily jammed, or even some of them are damaged by natural disasters, e.g., earthquakes or hurricanes.

To address this issue, mobile offloading [2], including traffic offloading and computation offloading, is considered to be of great significance, of which one traditional scheme is that the overloaded networks offload partial tasks to small-cell networks, e.g., WiFi access points and femtocells. For example, Losifidis et al. [3] assumed that the cellular networks can competitively lease residential users as access points for data offloading, while Al-Kanj et al. [4] proposed that the mobile device holders can actively form device-to-device (D2D) networks to offload partial user traffic for the overloaded cellular networks. In addition, Wang et al. [5] proposed a novel architecture that reduced resource consumption and ensured the extensibility of trust evaluation mechanism. The above existing work can be of feasibility and practicality only when the cooperative partners are densely deployed. Unfortunately, such assumptions cannot always hold, especially when partial cellular networks in populated urban areas are severely jammed by overloaded user traffic requirements or damaged by natural disasters. On the other hand, in remote areas out scope of the BS transmission coverage, users’ demands can hardly be fulfilled without the direct connections between users and BS. Considering this fact, leveraging Unmanned Aerial Vehicles (UAVs) to assist traffic or computation offloading in cellular networks is proposed [6,7,8,9], in which the UAVs serve as moving cloudlets or relays to accommodate user demands thanks to the convenient mobility in 3-D spaces [10,11,12,13,14,15]. With this offloading paradigm, the UAV can not only provide a much lager transmission coverage during flight, but also maintain a reliable connection with the cellular networks. As such, the user requirements can be satisfied to a certain extent. The existing work can achieve a better performance when the user demands are homogeneous, i.e., all users require only the same one of services, namely, transmission offloading or computation offloading, rather than both of them.

In this paper, we consider a more complicated and practical scenario, where users are heterogeneous, and each user might have different offloading requirement. Different from the data and computation co-offloading in [16], we use the UAV as a moving cloudlet to provide concurrent serve and relay when the heterogeneous users are not covered by the cellular BS. It is a necessity that the UAV has to fulfill its offloading tasks before a hard deadline during flying to the destination, and new challenges to the UAV-assisted traffic and computation offloading (UOTO) problem are brought in three folds. Firstly, the resource competition in the UOTO problem, including bandwidth and energy, is unavoidable. In comparison to the existing offloading optimization [17, 18], non-linear couple between UAV’s transmit power and bandwidth allocation is incurred, which leads to the UOTO problem difficult to solve optimally. Secondly, different from the assumption of sufficient UAV computation capacity in existing work [19,20,21,22,23], the UAV usually contributes to the computation offloading task with a constrained on-board computation resource during serving as a moving cloudlet. In other words, the user computation tasks could be performed at the locality, the UAV, or the BS server. Therefore, the UAV has to make an instant decision when multiple user tasks come. In addition, the UAV’s trajectory has to be considered since it can affect the resource allocation manner including energy and computation resources. Compared with the existing work [24,25,26], we not only consider the power allocation and trajectory optimization, also consider the heterogeneousness of users need. The above three folds motivate us to optimize the UOTO problem by jointly considering the bandwidth allocation, partial offloading decision and UAV’s trajectory planning. The UOTO problem considered in this paper is more practical since most of users might require traffic offloading and computation offloading concurrently, rather than only one of them. The optimal solution not only relies on the competition in resource competition between traffic offloading and computation offloading but also on the UAV’s trajectory planning. In consideration of the fairness among users, the objective of the UOTO problem is to maximize the minimum user utility. In the formulated problem, there exists non-linear couples among variables and it is an NP-hard problem. To deal with it, we propose a three-stage alternative optimization (TSAO) algorithm to solve it. The main contributions of this paper are summarized as follows.

  • Considering the heterogeneous demands for mobile offloading, the UAV-assisted mobile offloading and trajectory optimization problem (UOTO) is formulated with the objective of maximizing minimum user utility. And it is a non-convex optimization problem.

  • We carefully investigate the structure of the UOTO problem, which is decomposed three sub-problems, namely, bandwidth resource allocation, partial offloading decision, and UAV trajectory optimization. The closed form of optimal solution for bandwidth resource allocation is obtained by its dual multipliers.

  • We develop a three-stage alternative optimization algorithm to solve it iteratively by leveraging the nonlinear fractional programming (NFP) and successive convex approximation (SCA) methods.

The rest of this work is as follows. Section II introduces the system model and presents the formulation of UOTO problem. In Section III, we analyze the property of the problem and propose a three-stage alternative optimization algorithm to solve it. Then, numerical results are given in Section IV. Finally, in Section V, the conclusions are drawn.

2 System model

Considering a mobile offloading scenario with a three-dimensional (3D) Euclidean coordinate, there are N heterogeneous users with fixed locations on the ground. The users might have traffic demand, computation demand, or both of them. In the scenario, although the cellular BS server can provide a more powerful transmission and computing capability, the users cannot connect to the cellular networks directly due to the existing obstacles blocking the transmission between the users and cellular BS, or the users are not in the coverage of the cellular BS. One UAV, equipped with on-board communication circuits and computing processors while constrained energy and computation resources, can provide transmission and computation services for the covered users during floating from one position to another. Assume that there is a LOS transmission condition between the UAV and BS, i.e., the UAV can serve as an aerial platform for the covered users and meanwhile maintain a reliable connection with the BS. The considered system is time slotted with a duration T, which is divided into M identical slots.

In the system model, three types of users, i.e., users with computation offloading demand, users with traffic offloading demand, and users with both offloading commands are considered. Different from our previous work [1], when the UAV faces some resource-hungry computation tasks, the UAV might transmit partial tasks to the BS server for the sake of saving resources. For the first user type, the UAV functions as a mobile cloudlet to provide computation services for this type of users. For the second user type, the UAV is employed as a relay to download the traffic from BS and then transmit to the kind of users. For the third user type, the UAV will perform traffic and computation offloading for users concurrently. The example of scenario is illustrated in Fig. 1.

Fig. 1
figure 1

A UAV-assisted wireless relay networks for mobile offloading scenario for heterogeneous users, where User 2, User 3 and User 5 require only traffic or computation offloading, while others have both demands. For the users with traffic demand, the UAV will request the relative contents from the BS and then transmit to the users. For the users with computation demand, the UAV and BS server will jointly process the tasks. UAV has a fixed initial and final location [27]

Full size image

The computation tasks of users are partitioned into two parts, one is completed by the UAV and the other is transmitted to the BS server to perform, which is also called partial computation offloading mode.

The notations used in this paper are summarized in Table 1. Denote the set of UEs as \(\mathcal {N}\) and \(\mathbf {L}_{i}=[x_{i}^{(\text {l})},y_{i}^{(\text {l})},z_{i}^{(\text {l})}]\) as the coordinate of user i (1 ≤ i ≤ N), which can be obtained by the built-in GPS and other sensors [28]. We assume that all the users stand on a flat ground (i.e., \(z_{i}^{(\text {l})}\) is a constant) and the UAV flies at a fixed height H, which is the minimum altitude that is appropriate to the terrain. The wireless communication channels between MDs and UAV are dominated by line-of-sight links. Denote qst and qend as UAV’s the initial location and destination location, respectively. Considering the energy consumption, the UAV’s flight speed has an upper limit, denoted by \(v_{\max \nolimits }\) [28]. According to the slotted system model, M can be sufficiently large, such that the slot duration to be sufficiently small. Therefore, the location of UAV within each slot can be approximately constant [23, 27]. Noted that there are M sets of variables, which means the variables with different slots are irrelevant. Denote q(t) = [x(c)(t),y(c)(t),H] as UAV’s location within slot t, where x(c)(t) and y(c)(t) represent the horizontal and vertical coordinates, respectively. The location of BS is denoted as S = [x(s),y(s),H(s)], where H(s) denotes the altitude of BS.

Table 1 Parameter definitions
Full size table

Assume the bandwidth of downlink and uplink are both B MHz. And time division multiple access (TDMA) scheme is used in downlink and uplink transmission, respectively. Let \(\alpha _{i}^{(\text {d} )}(t)\) and \(\alpha _{i}^{(\text {u})}(t)\) represent the percentage of downlink and uplink communication duration allocated for user i, respectively. Obviously, for the users who have upload demands, the sum of their allocated upload proportion cannot exceed 1. The users who have download demands are similar. The constraints are given as

$$ \sum\limits_{i=0}^{N}\alpha_{i}^{(\text{u})}(t)\theta_{i}^{(\text{u})}\leq 1, $$
(1)

and

$$ \sum\limits_{i=0}^{N}\alpha_{i}^{(\text{d})}(t)\theta_{i}^{(\text{d})}\leq 1, $$
(2)

where \(\theta _{i}^{(\text {d} )}\) and \(\theta _{i}^{(\text {u})}\) represent user i’s traffic and computation offloading demands, respectively. And user i has offloading demands if it equals to 1, otherwise not.

The distance between user i and UAV and the distance between BS and UAV within slot t are respectively expressed as

$$ d_{i}(t)=\sqrt{H^{2}+\parallel{\mathbf{q}(t)-\mathbf{l}(t)}\parallel^{2}}, $$
(3)
$$ d_{s}(t)=\sqrt{(H^{(s)})^{2}+\parallel{\mathbf{q}(t)-\mathbf{S}}\parallel^{2}}. $$
(4)

According to [27, 29], the time-varying communication channel between user i and UAV and the time-varying communication channel between BS and UAV follow the free-space path loss model

$$ h_{i}(t)=\delta d_{i}^{-2}(t), $$
(5)
$$ h_{s}(t)=\delta d_{s}^{-2}(t), $$
(6)

where δ denotes the communication channel gain at the reference distance equals to 1 m.

According to the standard information theory [30], user i’s transmission rate in uplink within slot t is express as

$$ R_{i}^{(\text{u})} (t)=\theta_{i}^{(\text{u})}B\log_{2}(1+\frac {P_{i}^{(\text{u})}(t)h_{i}(t)}{N_{0}}), $$
(7)

where \(p_{i}^{(\text {u})}(t)\) represents user i’s transmit power and N0 represents the gaussian noise. Therefore, the traffic volume that user i uploaded is given by

$$ D_{i}^{(\text{u})}(t) = \frac{T}{M}\alpha_{i}^{(\text{u})}(t)R_{i}^{(\text{u})}(t). $$
(8)

Similarly, user i’s transmission rate in downlink can be expressed as

$$ R_{i}^{(\text{d})}(t) = \alpha_{i}^{\text{(d)}}(t)\theta_{i}^{(\text{d})}B\log_{2}(1 + \frac{p_{i}^{(\text{d})}(t){h_{i}}(t)}{N_{0}}), $$
(9)

where \(p_{i}^{(\text {d})}(t)\) represents the transmit power that UAV allocates for user i. Therefore, traffic volume that user i downloaded within slot t is given by

$$ D_{i}^{(\text{d})}(t) = \frac{T}{M}\alpha_{i}^{(\text{d})}(t)R_{i}^{(\text{d})}(t). $$
(10)

Similarly, the transmit rate of UAV to BS within slot t is given by

$$ R_{i}^{(\text{s})} = B_{s}\log_{2}(1+\frac{p_{s}(t)h_{s}(t)}{N_{0}}). $$
(11)

Similar to [31, 32], the computing time of UAV and the downloading time of computation result are neglected, which is because UAV’s computing capability is significantly bigger than MDs’ and the returned traffic volume is relatively small. Then, the flight speed of UAV within slot t can be expressed as

$$ v(t) = \frac{\parallel \mathbf{q}(t)-\mathbf{q}(t-1)\parallel}{T/M}. $$
(12)

Because the flight speed of UAV is upper bounded to its maximum flight speed \(v_{\max \nolimits }\), one has

$$ v(t) \le {v_{\max} }. $$
(13)

Similarly, for UAV’s and users’ transmit power, one has

$$ p_{s} + \sum\limits_{i=1}^{N}\theta_{i}^{\text{(d)}}p_{i}^{(\text{d})}(t) \le p^{(\text{\text{uav}})}_{\max}, $$
(14)

and

$$ p_{i}^{(\text{u})}(t) \le p^{(\text{u})}_{i,\max}, $$
(15)

where \(p^{(\text {u})}_{i,\max \nolimits }\), \(p^{(\text {uav})}_{\max \nolimits }\) and ps represent the maximum transmit power of user i, UAV and the transmit power that UAV allocates for BS, respectively.

Due to users’ and UAV’s transmit power should be positive or equal to zero, one has

$$ p_{i}^{(\text{u})}(t) \ge 0, $$
(16)
$$ p_{s}(t) \ge 0, $$
(17)
$$ p_{i}^{(\text{d})}(t) \ge 0. $$
(18)

Besides, the sum of the transmission rates allocated by the UAV to all users is less than or equal to the bandwidth allocated by the UAV to the BS, one has

$$ \sum\limits_{i = 1}^{N} R_{i}^{(\text{d})}(t) \leq B_{s}\log_{2}(1+\frac{p^{\text{(b)}}h_{s}(t)}{N_{0}}), $$
(19)

where Bs and p(b) denote the bandwidth that the UAV allocates to the BS and the transmit power of BS, respectively.

Each user has a downlink capacity requirement

$$ R_{i}^{\text{(d)}}(t) \ge R_{i,\min}^{\text{(d)}}(t), $$
(20)

where \(R_{i,\min }^{\text {(d)}}(t)\) denotes the minimum downlink capacity requirement of user i.

According to [19, 33], the computation time of user i on the UAV within slot t is given by

$$ T_{i}^{(\text{uu})}(t) = \frac{ \eta_{i}(t) D_{i}^{\text{(u)}}(t)\gamma_{i}}{f_{i}^{(\text{c})}}, $$
(21)

where γi and \(f_{i}^{(\text {c})}\) represent the number of CPU cycles per input bit needed for computing and the CPU frequency allocated for user i, respectively. ηi(t) denotes the proportion of computation task that user i computed on the UAV within slot t.

The computation time of user i on the central cloud within slot t is expressed as

$$ T_{i}^{(\text{uc})}(t) = \frac{ (1-\eta_{i}(t)) D_{i}^{\text{(u)}}(t)\gamma_{i}}{f_{i}^{(\text{s})}}. $$
(22)

The time that UAV offload user i’s partial task to the BS within slot t is given by

$$ T_{i}^{(\text{us})}(t) = \frac{(1-\eta_{i}(t)) D_{i}^{\text{(u)}}(t)}{R_{i}^{\text{(s)}}}. $$
(23)

According to Eqs. 21-23, the computation delay of user i within slot t is expressed as

$$ T_{i}^{\text{(ucd)}}(t) = \max\{T_{i}^{(\text{uu})}(t),T_{i}^{(\text{us})}(t)+T_{i}^{(\text{uc})}(t)\}. $$
(24)

Therefore, the delay of user i within slot t is given by

$$ T_{i}^{\text{(ud)}}(t) = \alpha_{i}^{(\text{u})}\frac{T}{M} + T_{i}^{\text{(ucd)}}(t). $$
(25)

The objective is to maximize user utility [34, 35], which is indicated by the computation size minus the delay, and it is expressed as

$$ U_{i} = \sum\limits_{t=1}^{M} \left( \tau_{i}^{\text{(d)}} D_{i}^{\text{(u)}}(t) - \tau_{i}^{\text{(t)}}T_{i}^{\text{(ud)}}(t) \right), $$
(26)

where \(\tau _{i}^{\text {(d)}}\) and \(\tau _{i}^{\text {(t)}}\) denote the weights of computation size and delay of user i, respectively. It should be noted that \(0 \le \tau _{i}^{\text {(d)}}, \tau _{i}^{\text {(t)}} \le 1\). Users can set different values of \(\tau _{i}^{\text {(d)}}\) and \(\tau _{i}^{\text {(t)}}\) for their demands. For example, when a user is sensitive to the delay (e.g., online game), the user can set \(\tau _{i}^{\text {(t)}} = 1\) and \(\tau _{i}^{\text {(d)}} = 0\). When user concerns more about the computation size, the value of \(\tau _{i}^{\text {(d)}}\) can be assigned larger. In practice the proper weights can be calculated by the multi-attribute utility approach [36].

We take the Max-Min fairness scheme [37, 38] for users mobile offloading. We introduce a variable \(\xi = \min \limits _{i \in \mathcal {N}}U_{i} \) and add following constraint:

$$ U_{i} \ge \xi. $$
(27)

Then, the objective is to maximize ξ. Therefore, we can obtain the UOTO optimization problem as P0.

$$ \begin{array}{@{}rcl@{}} \mathbf{P0}&:&\max\limits_{{{\alpha^{(\text{u})},\alpha^{(\text{d})},\textbf{p}^{(\text{d})},{\textbf{q}}}}}\xi \end{array} $$
(28a)
$$ \begin{array}{@{}rcl@{}} &&s.t. \ (1),(2),(13)-(20) \text{\ and\ } (27) \end{array} $$
(28b)

In problem P0, the objective function represents user utility. Equations 1 and 2 denote the uplink and downlink bandwidth allocation constraints, respectively. And Eqs. 13-14 denote the constraint of UAV’s flight speed and transmit power. Equations 15-20 denote the download rate and transmit power constraints of users. Besides, Eq. 27 denotes the fairness constraint among users.

3 Problem analysis and algorithm design

Due to there exists nonlinear coupling in constraints (20) and (27), the problem P0 is therefore non-convex. At present, there are no effective solutions to obtain the optimal solution. Therefore, instead of resorting to expensive global optimization methods, we propose the TSAO algorithm to decouple the nonlinear coupling variables and solve them iteratively. In detail, we separate the variables into several subsets of non-overlapping variables and then get three sub-problems. For each sub-problem, we replace the non-convex function with suitable convex approximation by leveraging SCA and NFP [39,40,41,42].

Stage I: For the given trajectory and variables ηi(t), \(f_{i}^{\text {(c)}}\), p(s), we have following bandwidth allocation and power optimization problem P1 that related to users and UAV. However, due to the constraint (27) is non-convex, P1 is a non-convex problem.

Let \(\phi _{i}^{(\text {u})}(t) = \alpha _{i}^{(\text {u})}(t)p_{i}^{(\text {u})}(t)\), \(\phi _{i}^{(\text {d})}(t) = \alpha _{i}^{(\text {d})}(t)p_{i}^{(\text {d})}(t)\), \(D_{i}^{\text {(u)}}(t)\) is then transformed into \(D_{i}^{\text {(u1)}}(t)\), which is given by

$$ D_{i}^{\text{(u1)}}(t) = \frac{T}{M}\alpha_{i}^{(\text{u})}(t) \theta_{i}^{(\text{u})}B\log_{2}(1+\frac{\phi_{i}^{(\text{u})} (t)h_{i}(t)}{\alpha_{i}^{(\text{u})}(t) N_{0}}) $$
(29)

Besides, constraint (27) can be rewritten as

$$ \begin{array}{ll} &{\sum}_{t=1}^{M}(\tau_{i}^{\text{(d)}}D_{i}^{\text{(u1)}}(t) - \tau_{i}^{\text{(t)}}(\frac{T}{M} + \max\{\frac{\varphi \eta_{i}(t) D_{i}^{\text{(u1)}}(t)\gamma_{i}}{f_{i}^{(\text{c})}(t)}, \\ &\frac{ (1-\eta_{i}(t)) D_{i}^{\text{(u1)}}(t)}{B_{s}\log_{2}(1+ p_{s}(t)h_{s}(t)/ N_{0})}\})) \ge \xi \end{array} $$
(30)

Thereafter, we can identically transform (30) into following constraints:

$$ \sum\limits_{t=1}^{M}(\tau_{i}^{\text{(d)}}D_{i}^{\text{(u1)}}(t) - \tau_{i}^{\text{(t)}}(\frac{T}{M} + \frac{\varphi \eta_{i}(t) D_{i}^{\text{(u1)}}(t)\gamma_{i}}{f_{i}^{(\text{c})}(t)})) \ge \xi, $$
(31)
$$ \begin{array}{@{}rcl@{}} &&\sum\limits_{t=1}^{M}(\tau_{i}^{\text{(d)}}D_{i}^{\text{(u1)}}(t) - \tau_{i}^{\text{(t)}}(\frac{(1-\eta_{i}(t)) D_{i}^{\text{(u1)}}(t)}{B_{s}\log_{2}(1+ p_{s}(t)h_{s}(t)/N_{0})} \\ &&+ \frac{T}{M})) \ge \xi. \end{array} $$
(32)

Therefore, P0 is reformed as P1.

$$ \begin{array}{@{}rcl@{}} &&\mathbf{P1}:\max\limits_{\alpha_{i}^{(\text{u})}(t),\alpha_{i}^{(\text{d})}(t),p_{i}^{(\text{u})}(t),p_{i}^{(\text{d})}(t)}\xi \end{array} $$
(33a)
$$ \begin{array}{@{}rcl@{}} &&s.t. (1), (2), (14),(15),(16),(18),(31)\ \text{and} \ (32) \end{array} $$
(33b)

According to [43, 44], it can be proved that P1 is a convex optimization problem. We can tackle it by adopting the classic algorithm (e.g. Gradient descent) [45,46,47,48], and the optimal solutions of \(\alpha _{i,\text {opt}}^{(\text {u})}(t)\), \(\alpha _{i,\text {opt}}^{(\text {d})}(t)\), \(p_{i,\text {opt}}^{(\text {d})}(t)\), \( p_{i,\text {opt}}^{(\text {u})}(t)\) will be obtained. Moreover, we have the following Theorem 1.

Theorem 1

For a given trajectory, the closed-form of the optimal solution can be directlyobtained by the dual multipliers that associated with constraints in problemP1.

Proof

Let λ(uu),λ(ud), λ(v), λ(pdm), \(\lambda _{i}^{(\text {pum})}\), λ(sum), \(\lambda _{i}^{(\text {u})}, \lambda ^{(\text {ps})},\)\(\lambda _{i}^{(\text {pd})}, \lambda ^{(\text {r})}, \lambda _{i}^{(\text {rm})}, \lambda ^{(\text {e})}, \lambda _{i}^{(\text {f1})}, \lambda _{i}^{(\text {f2})}\) denote the dual multipliers w.r.t. constraints (13)-(20), (31) and (32). Thus, the general Lagrangian function of problem P1 can be expressed as (34) (see next page).

$$ \begin{array}{@{}rcl@{}} &&L=\xi + \sum\limits_{t=1}^{M}\lambda^{(\text{uu})}(t)\sum\limits_{i=0}^{N}(\theta_{i}^{(\text{u})}\alpha_{i}^{\text{(u)}}(t)-1)+\sum\limits_{i=0}^{N}\sum\limits_{t=1}^{M} (\lambda^{(\text{pd})}_{i}p^{\text{(d)}}_{i}(t))+\sum\limits_{i=0}^{N}\sum\limits_{t=0}^{M}(\lambda_{i}^{(\text{pum})}(t)(p_{i}^{\text{(u)}}(t)-p_{i,\max}^{\text{(u)}})) \\ &&+\sum\limits_{i=0}^{N}(\lambda^{(\text{sum})}(p_{s}-p^{(\text{u})}_{i,\max}))+\sum\limits_{t=1}^{M}\lambda^{(\text{ud})}(t)\sum\limits_{i=0}^{N}(\theta_{i}^{\text{(d)}} \alpha_{i}^{\text{(d)}}(t)-1) +\sum\limits_{t=1}^{M}(\lambda^{(\text{v})}(t)(v(t)-v_{\text{(max)}}))+\lambda^{(\text{ps})}p_{s}(t) \\ &&+\sum\limits_{t=1}^{M}(\lambda^{(\text{pdm})} (p_{s}(t) + \sum\limits_{i=1}^{N}p_{i}^{(\text{d})}(t)-p^{(\text{\text{d}})}_{\max}))+\sum\limits_{i=0}^{N}\sum\limits_{t=1}^{M}(\lambda^{(\text{u})}_{i}p^{(\text{u})}_{i}(t)) +\sum\limits_{i=0}^{N}\sum\limits_{t=1}^{M}(\lambda^{(\text{r})}(R_{i}^{(\text{d})}(t)-B_{s}\log_{2}(1+\frac{p^{\text{(b)}}h_{s}(t)}{N_{0}}))) \\ &&+\sum\limits_{i=0}^{N}\sum\limits_{t=1}^{M}(\lambda^{(\text{f1})}_{i}(\tau_{i}^{\text{(d)}}D_{i}^{'\text{(u)}}(t) - \tau_{i}^{\text{(t)}}(\frac{T}{M} + \frac{ \eta_{i}(t) D_{i}^{'\text{(u)}}(t)\gamma_{i}}{f_{i}^{(\text{c})}(t)})-\xi)) +\sum\limits_{i=0}^{N}\sum\limits_{t=1}^{M}(\lambda^{(\text{rm})}_{i}(R^{(\text{d})}_{i}(t)-R^{(\text{d})}_{i,min}(t))) \\ &&+\sum\limits_{i=0}^{N}\sum\limits_{t=1}^{M} (\lambda^{(\text{f2})}_{i}(\tau_{i}^{\text{(d)}}D_{i}^{'\text{(u)}}(t) - \tau_{i}^{\text{(t)}}(\frac{T}{M} + \frac{(1-\eta_{i}(t)) D_{i}^{'\text{(u)}}(t)}{B_{s}\log2(1+ p_{s}(t)h_{s}(t)/N_{0})})-\xi)). \end{array} $$
(34)

Therefore, the general Lagrangian dual function of problem P1 is given by

$$ \begin{array}{ll} &\kappa(\lambda^{(\text{uu})}, \lambda^{(\text{ud})}, \lambda^{(\text{v})}, \lambda^{(\text{pdm})}, \lambda_{i}^{(\text{pum})}, \lambda^{(\text{sum})}, \lambda_{i}^{(\text{u})},\\ &\lambda^{(\text{ps})},\lambda_{i}^{(\text{pd})}, \lambda^{(\text{r})}, \lambda_{i}^{(\text{rm})}, \lambda^{(\text{e})}, \lambda_{i}^{(\text{f1})}, \lambda_{i}^{(\text{f2})}) = \max L. \end{array} $$
(35)

Then, the solution of P1 can be obtained by solving its dual problem, which is expressed as

$$ \begin{array}{ll} \min &\kappa(\lambda^{(\text{uu})}, \lambda^{(\text{ud})}, \lambda^{(\text{v})}, \lambda^{(\text{pdm})}, \lambda_{i}^{(\text{pum})}, \lambda^{(\text{sum})}, \lambda_{i}^{(\text{u})},\\ &\lambda^{(\text{ps})},\lambda_{i}^{(\text{pd})}, \lambda^{(\text{r})}, \lambda_{i}^{(\text{rm})}, \lambda_{i}^{(\text{dm})}, \lambda^{(\text{e})}, \lambda_{i}^{(\text{f1})}, \lambda_{i}^{(\text{f2})}) \end{array} $$
(36)

It can be seen that the dual problem of P1 can be divided into N independent convex optimization problems. Thus, by getting the derivation of each sub-problem with respect to variables \(\alpha _{i}^{(\text {u})}(t), \alpha _{i}^{(\text {d})}(t), p_{i}^{(\text {u})}(t), p_{i}^{(\text {d})}(t)\), we can obtain the closed-form of the optimal solution. □

Stage II: After P1 is solved, the optimal values of \(p_{i,\text {opt}}^{(\text {d})}(t)\), \(p_{i,\text {opt}}^{(\text {u})}(t)\), \(\alpha _{i,\text {opt}}^{(\text {u})}(t)\), \(\alpha _{i,\text {opt}}^{(\text {d})}(t)\) under some given variables can be obtained. Then, the problem related to computation can be obtained as P2 for given variables \(\alpha _{i,\text {opt}}^{(\text {u})}(t)\), \(\alpha _{i,\text {opt}}^{(\text {d})}(t)\), \(p_{i,\text {opt}}^{(\text {d})}(t)\), \(p_{i,\text {opt}}^{(\text {u})}(t)\) and q(t). P2 aims at solving the proportion of partial offloading and power optimization related to UAV and BS, which is given as

$$ \begin{array}{@{}rcl@{}} \mathbf{P2}&:&\max\limits_{\eta_{i}(t), f_{i}^{\text{(c)}}(t), p_{s}(t)}\xi \end{array} $$
(37a)
$$ \begin{array}{@{}rcl@{}} &&s.t. \ (14), (17), (31) \ \text{and} \ (32) \end{array} $$
(37b)

Due to the fraction in Eq. 32, problem P2 is thus a nonlinear fraction optimization problem, which is hard to solve. We have following lemma by the reformulation of P2.

Lemma 1

problem P 2 can be transformed into an equivalent convex optimization.

Proof

By introducing some additional variables to replace the fraction expressions, we have the following equations:

$$ \mu_{i}^{\text{(c)}}(t) = \frac{\eta_{i}(t)}{f_{i}^{\text{(c)}}(t)}, $$
(38)
$$ \mu_{i}^{\text{(s)}}(t) = \frac{\eta_{i}(t)}{\log_{2}(1+p_{s}(t)h_{s}(t)/N_{0})}, $$
(39)
$$ \nu_{s}(t) = \frac{1}{\log_{2}(1+p_{s}(t)h_{s}(t)/N_{0})}. $$
(40)

Then, constraints (31) and (32) are transformed as follows:

$$ \begin{array}{ll} &{\sum}_{t=1}^{M}(\tau_{i}^{\text{(d)}}D_{i}^{'\text{(u)}}(t) - \tau_{i}^{\text{(t)}}(\frac{T}{M} + \varphi D_{i}^{'\text{(u)}}(t)\gamma_{i}\mu_{i}^{\text{(c)}}(t))) \ge \xi, \end{array} $$
(41)
$$ \begin{array}{ll} &{\sum}_{t=1}^{M}(\tau_{i}^{\text{(d)}}D_{i}^{'\text{(u)}}(t) - \tau_{i}^{\text{(t)}}(\frac{T}{M} + (\nu_{s}-\mu_{i}^{\text{(s)}}(t)) D_{i}^{'\text{(u)}}(t)B_{s} )) \\ & \ge \xi. \end{array} $$
(42)

Besides, in order to transform P2 into a convex optimization problem, two following constraints should be satisfied [49]:

$$ \mu_{i}^{\text{(c)}}(t) \le \frac{1}{f_{i}^{\text{(c)}}(t)}, $$
(43)
$$ \nu_{s}h_{s}(t) \log_{2}\left( 1+\frac{\mu_{i}^{\text{(s)}}(t)}{\nu_{s}h_{s}(t)N_{0}}\right) \le 1. $$
(44)

Therefore, we have following convex problem P3:

$$ \begin{array}{@{}rcl@{}} \mathbf{P3}&:&\max\limits_{\mu_{i}^{\text{(c)}}(t), \mu_{i}^{\text{(s)}}(t), \nu_{s}(t)}\xi \end{array} $$
(45a)
$$ \begin{array}{@{}rcl@{}} &&s.t. (14), (17), (41)-(44) \end{array} $$
(45b)

□

Therefore, problem P2 is transformed into the convex problem P3, which can be tackled by leveraging the classic optimization algorithm, and the corresponding optimal solutions can be then obtained.

Stage III: When P1 and P3 are solved, the optimal variables expect UAV’s trajectory are obtained. Then, UAV’s trajectory can be obtained by following optimization problem P4.

$$ \begin{array}{@{}rcl@{}} \mathbf{P}4&:&\max\limits_{\mathbf{q}(t)}\xi \end{array} $$
(46a)
$$ \begin{array}{@{}rcl@{}} &&s.t. \ (19), (13), (31) \ \text{and} \ (32) \end{array} $$
(46b)

Because (32) is non-convex, P4 is a non-convex problem. In Eq. 32, variables \(p_{i}^{(\text {u})}\) and q(t) are nonlinear coupled in the form of bilinear expression [50, 51]. We leverage the SCA method to tackle it, which decouples the variables and approximate it to a convex problem. Thereafter, by relaxing the non-convex expressions with Taylor formula, Theorem 2 can be obtained.

Theorem 2

For any given feasible UAV trajectoryq0(t),following inequalities can hold:

$$ \begin{array}{@{}rcl@{}} &&\log_{2}(1+\frac{\delta p_{i}^{(\text{u})}(t)}{N_{0}(H^{2}+\parallel \mathbf{q}(t)-\mathbf{l}(t)\parallel^{2})})\\ &&\geq R^{\text{(u)}}(t) = \log_{2}(1+\frac{\delta p_{i}^{(\text{u})}(t)}{N_{0}(H^{2}+\parallel \mathbf{q}_{0}(t)-\mathbf{l}(t)\parallel^{2})})- \\ &&(\frac{\log_{2}(e)p_{i}^{(\text{u})}(t)(\parallel\mathbf{q}(t)\parallel^{2}-\parallel\mathbf{q}_{0}(t)\parallel^{2})} {(N_{0}H^{2}+\delta p_{i}^{(\text{u})}(t)+N_{0}\parallel\mathbf{q_{0}}(t)\parallel^{2})(H^{2}+\parallel\mathbf{q_{0}}(t)\parallel^{2})}), \end{array} $$
(47)
$$ \begin{array}{@{}rcl@{}} &&\log_{2}(1+\frac{\delta p_{i}^{(\text{d})}(t)}{N_{0}(H^{2}+\parallel \mathbf{q}(t)-\mathbf{l}(t)\parallel^{2})})\\ &&\geq R^{\text{(d)}}(t) = \log_{2}(1+\frac{\delta p_{i}^{(\text{d})}(t)}{N_{0}(H^{2}+\parallel \mathbf{q}_{0}(t)-\mathbf{l}(t)\parallel^{2})})-\\ &&(\frac{\log_{2}(e)p_{i}^{(\text{d})}(t)(\parallel\mathbf{q}(t)\parallel^{2}-\parallel\mathbf{q}_{0}(t)\parallel^{2})} {(N_{0}H^{2} + \delta p_{i}^{(\text{d})}\!(t) + N_{0}\parallel\mathbf{q_{0}}(t)\parallel^{2})(H^{2}+\parallel\mathbf{q_{0}}(t)\parallel^{2})}), \end{array} $$
(48)
$$ \begin{array}{@{}rcl@{}} &&\log_{2}(1+\frac{\delta p_{r}}{N_{0}((H^{s})^{2}+\parallel \mathbf{q}(t)-\mathbf{s}(t)\parallel^{2})})\\ &&\geq R^{\text{(s)}}\!(t) = \log_{2}(1 + \frac{\delta p_{r}}{N_{0}((H^{\text{(s)}})^{2}+\parallel \mathbf{q}_{0}(t)-\mathbf{s}(t)\parallel^{2})})- \\ &&(\frac{\log_{2}(e)p_{r}(\parallel\mathbf{q}(t)\parallel^{2}-\parallel\mathbf{q}_{0}(t)\parallel^{2})} {(N_{0}(H^{\text{(s)}})^{2} + \delta p_{r} + N_{0}||\mathbf{q_{0}}(t)||^{2})((H^{\text{(s)}})^{2}+\!\parallel\!\mathbf{q_{0}}(t)\!\parallel^{2})}), \end{array} $$
(49)

where the equalities hold whenq(t) = q0(t).

Proof

Let δ(t) = ||q(t) −l(t)||2, and then \({\log _{2}}(1 + \frac {{p_{i}^{(\text {u})}(t)}}{{{N_{0}}({H^{2}} + ||{\textbf {q}}(t) - {\textbf {l}}(t)|{|^{2}})}})\) is converted into \({\log _{2}}\!(1 \!+ \!\frac {{p_{i}^{(\text {u})}\!(t)}}{{{N_{0}}\!({H^{2}} + \delta (t))}}\!)\). Let \(f(\delta (t)) = {\log _{2}}(1 + \frac {{p_{i}^{(\text {u})}(t)}}{{{N_{0}}({H^{2}} + \delta (t))}})\), in which δ(t) is the variable of function f(δ(t)). Therefore, f(δ(t)) is a convex function. According to Taylor expansion, the following inequality can be obtained.

$$ f(\delta(t))\ge f(\delta_{0}(t))- f(\delta_{0}(t))(\delta(t)-\delta_{0}(t)). $$
(50)

By substituting δ(t) = ||q(t) −l(t)||2 into (50), inequality (47) is obtained. Similarly, the inequality (48) and (49) are obtained. □

Therefore, the upload traffic size of user i within slot t is transformed into \(D_{i}^{{}^{\prime \prime }(\text {u})}(t)\), which is given by

$$ D_{i}^{{}^{\prime\prime}(\text{u})\!}(t) = \frac{T\theta_{i}\!^{(\text{u}\!)}B\alpha_{i}\!^{(\text{u})\!}(t)}{M}\log_{2}(1+\!\frac{\delta p_{i}^{(\text{u})\!}(t)/N_{0}\!}{(H^{2}\!+||{\mathbf{q}(t)\!-\mathbf{l}(t)\!}||^{2})}), $$
(51)
$$ \sum\limits_{t=1}^{M}(\tau_{i}^{\text{(d)}}D_{i}^{{}^{\prime\prime}\text{(u)}}(t)- \tau_{i}^{\text{(t)}}(\frac{T}{M}+\frac{\varphi \eta_{i}(t) D_{i}^{{}^{\prime\prime}\text{(u)}}(t)\gamma_{i}}{f_{i}^{(\text{c})}(t)})) \ge \xi, $$
(52)
$$ \begin{array}{@{}rcl@{}} &&\sum\limits_{t=1}^{M}\!(\tau_{i}^{\text{(d)}\!}D_{i}^{{}^{\prime\prime}\text{(u)}}\!(t) - \tau_{i}^{\text{(t)}}\!(\frac{(1-\eta_{i}(t)) D_{i}^{{}^{\prime\prime}\text{(u)}}(t)}{B_{s}\!\log_{2}\!(1\!+ \frac{p_{s} \delta}{N_{0} ((H^{(\text{s})})^{2}+\parallel{\mathbf{q}(t)-\mathbf{S}}\parallel^{2}))}} \end{array} $$
(53)
$$ \begin{array}{@{}rcl@{}} &&+ \frac{T}{M})) \ge \xi. \end{array} $$
(54)

Substituting (51), (52) and (53) into P5, we have problem P5.

$$ \begin{array}{@{}rcl@{}} \mathbf{P}5&:&\max\limits_{\mathbf{q}(t)}\xi \end{array} $$
(54a)
$$ \begin{array}{@{}rcl@{}} &&s.t. \ (19), (13), (52)\ \text{and\ } (53) \end{array} $$
(54b)

According to [19, 27, 52], it can be proven that problem P5 is convex. Thus, we can tackle it by leveraging classic algorithm (e.g., Gradient descent). Thereafter, substituting the optimal trajectory 6̱oldqopt(t) into problem P1. Then, solve P1, P3 and P5 iteratively until the growth of objective function is less than the threshold ρ1. The details are depicted in Algorithm 1.

figure i

The convergence of Algorithm 1 is discussed in [53]. Besides, the complexity of Algorithm 1 is composed of four aspects. The first is the computation of problem P1 by using CVX [54, 55]. The second is the computation of problem P3 by using CVX. Denote A1,B1 as the number of required iterations for the outer loop and inner loop in Algorithm 1, respectively. Thus, according to [56], the complexity of Algorithm 1 is \({\mathcal O}(A_{1}(2M^{3} + B_{1}M^{3}))\).

4 Numerical results

In this section, numerical results are provided to evaluate the performance of proposed scheme. The simulation settings are based on some existing work [27, 57]. There are N = 4 users and their positions are L1 = [0,0], L2 = [10,0], L3 = [0,10] and L4 = [10,10], respectively [43]. The location of BS is set as S = [70,70,0]. Besides, UAV’s initial position and destination position are set as qst = [0,0] and qst = [0,10], respectively. Assume users are static within each slot. Users’ traffic and computation offloading demands are set as a(d) = [1,1,1,0] and a(u) = [1,0,1,1], respectively. Besides, the duration time is set as T = 2s, which is decomposed into M = 50slots. UAV’s maximum flight speed is set as 20m/s. Both uplink and downlink bandwidths are set as 40MHz. \(p_{max}^{\text {(d)}}\) and \(p_{i,max}^{\text {(u)}}\) are set as 4W and 4W, respectively. \(\tau _{i}^{\text {(d)}}\) and \(\tau _{i}^{\text {(t)}}\) are set as 0.5 and 0.5, respectively. The remaining parameters used in the simulations, unless specified otherwise, are summarized in Table 2. The altitude of UAV is set as H = 10m, the channel power gain is set as δ = -50dB and the noise power is set as N0 = -174dBm/Hz. Besides, it is assumed the required CPU cycles per bit of user i is set as γi = 103 and the computing capacity that cloud allocated to user i is set as \(f_{i}^{\text {(c)}}\) = 1GHZ.

Table 2 Simulation parameters
Full size table

Figure 2 shows the dynamics of the minimum user utility during iteration. Similar to [27, 43, 58, 59], the iteration number in Fig. 2 is defined as the number that the three-stage has been looped. That is, we only calculate the number of outer loop in Algorithm 1, and the iterations of solving problem P1,P3 and P5 is not counted. It can be observed that the value of utility will decrease with the iteration. The transmit power of UAV larger, the minimum user utility larger, which is because the transmit rate between UAV and BS increases. More clearly, the transmit power larger, the more data can be processed on UAV and the less delay it takes. And the proposed partial offloading scheme outperforms the scheme that only computing on UAV. The reason is that the proposed partial offloading scheme can take use of BS for computing, which augments the computation capacity of UAV. However, the minimum user utility of proposed partial is less than that of total on UAV during iteration. It’s because that in the alternative process of solving the three-stage problem, the obtained value of some variables are not global optimal. Besides, the proposed algorithm only need several iterations to converge, which indicates it is computationally efficient and has a fast convergence rate.

Fig. 2
figure 2

The dynamics of the minumum user utility

Full size image

Figures 3 and 4 show the dynamics of users’ transmit power with different time slots under a given semicircle trajectory. It can be observed that user 1’s transmit power is gradually increasing, which is due to the distance between UAV and user 1 is gradually increasing. Due to the requirements of fairness among users, users will increase transmit power to keep communication rate steady when the distance increases. Besides, it can be observed that the trends of users’ transmit power is opposite to that of the distance between users and UAV. Since user 2 has no computation offloading demand, the transmit power of user 2 equals to zero. Additional, the transmit power of user 4 has an increasing trend after decreasing, which is due to the distance between user 4 and UAV decreases first and increases after slot 25. Thus, it can be inferred that users’ transmit power is related to the distance between UAV and users. In addition, it can be observed that the value of users’ average transmit power are close, and it will lead to the traffic size that users uploaded are close, which denotes the fairness among users.

Similar to Figs. 3 and 4, 5 and 6 show UAV’s transmit power that allocated to each user with different time slots under a given semicirle trajectory. It can be seen that the result is similar to Figs. 3 and 4, which has been described and analyzed above. Moreover, to meet users’ minimum download rate requirement, the minimum transmit power that UAV allocates to users is still relatively high. It implies that the proposed scheme not only guarantees the computation offloading fairness, but also traffic offloading fairness among users.

Fig. 3
figure 3

a Users’ transmit power with different timeslots

Full size image
Fig. 4
figure 4

b Users’ transmit power with different timeslots

Full size image
Fig. 5
figure 5

a UAV’s transmit power to each user with different timeslots

Full size image
Fig. 6
figure 6

b UAV’s transmit power to each user with different timeslots

Full size image

The proportion of users’ upload duration within each slot is shown in Figs. 7 and 8. It can be seen that the dynamic changes trends in Figs. 7 and 8 are opposite to that in Figs. 3 and 4. That is, the transmit power of users smaller, the proportion of users upload time larger. And it denotes that more traffic of users will be uploaded when the transmit power in low state. In addition, it can be observed that the distance between UAV and users smaller, the upload time of users larger, which guarantees the high computation rate of users.

Fig. 7
figure 7

a Proportion of upload time about users within each slot

Full size image
Fig. 8
figure 8

b Proportion of upload time about users within each slot

Full size image

The proportion of users’ download duration within each slot is shown in Figs. 9 and 10. It can be observed that the dynamic changes trends in Figs. 9 and 10 are opposite to that in Figs. 5 and 6. The transmit power that UAV allocates to users smaller, the proportion of download duration larger, which is due to the minimum download rate requirements of users. That is, in order to satisfy the requirements, the download time of users will increase when in low transmit power range. From another aspect of view, UAV offloads more traffic for users in the low transmit power state, which guarantees UAV can assist more users.

Fig. 9
figure 9

a Proportion of download time about users during each slot

Full size image
Fig. 10
figure 10

b Proportion of download time about users during each slot

Full size image

Figure 11 shows the minimum user utility with different user’s and UAV’s maximum transmit power and offloading schemes [27, 43]. It can be observed that with the increasing of users’ maximum transmit power, the minimum user utility is also increasing. The reason is that the transmit power of users higher, the size of data uploaded larger, which is contribute to the user utility. However, the minimum user utility increasing gradually slowly, which is because the transmit rate between UAV and BS is limited. With the upload data increasing, UAV has no enough computation capacity, which leads to the increasing of delay. Therefore, the minimum user utility increases gradually slowly. In addition, it can be observed that minimum user utility under the schemes that only perform computation on UAV and local computation is relatively smaller than the proposed schemes, which indicates the efficiency of proposed algorithm.

Fig. 11
figure 11

The minimum user utility with different user’s maximum transmit power

Full size image

Figure 12 show the minimum user utility versus the maximum transmit power of users under several different UAV trajectories. As shown in Fig. 12, the minimum user utility achieved by using proposed scheme is larger than that of semi-circle trajectory mode and trajectory with a constant speed mode. The reason is that users who are far from UAV have low transmit rate, and it leads to the low computation rate and high delay. Besides, the result indicates that the optimization of the trajectory of the UAV can improve the minimum user utility. It also verifies that our proposed scheme outperforms the disjoint optimization scheme. Besides, the relation between the transmit power of users and minimum user utility is consistent with Fig. 11.

Fig. 12
figure 12

The minimum user utility under different UAV trajectories

Full size image

Figure 13 show the minimum user utility versus the number of users under different maximum transmit power of UAV. The maximum transmit power of UAV is set as \(p^{(\text {\text {uav}})}_{\max \nolimits }\) = 0.2W, \(p^{(\text {\text {uav}})}_{\max \nolimits }\) = 0.3W or \(p^{(\text {\text {uav}})}_{\max \nolimits }\) = 0.4W. As shown in Fig. 13, the minimum user utility increases with the number of users. The reason is that the number of users larger, the computation rate larger. However, the delay doesn’t increase too much, which is because the UAV offloading some tasks to the BS for computing. It indicates the proposed schemes is adaptive for the large number of users. Besides, it can be observed that the minimum use utility under \(p^{(\text {\text {uav}})}_{\max \nolimits }\) = 0.4W is larger than that of utility under \(p^{(\text {\text {uav}})}_{\max \nolimits }\) = 0.3W and \(p^{(\text {\text {uav}})}_{\max \nolimits }\) = 0.2W. It’s because the maximum transmit power of the UAV larger, the transmit rate between UAV and BS larger, which can reduce the delay and increase the computation rate.

Fig. 13
figure 13

The minimum user utility with different number of users

Full size image

As shown in Fig. 14, the utilities of users are almost equally. With the increasing of user transmit power, the results are similar. It indicates fairness among users.

In conclusion, we evaluate the performance of proposed scheme from several different aspects. First, Fig. 2 shows the proposed algorithm has a fast convergence rate. Then, Figs. 3-6 study the dynamics of users’ and UAV’s transmit power with different time slots, and Fig. 7-10 study the dynamics of download and upload duration allocation. The results show that the resources allocated to each user are almost equally, which demonstrates the fairness among users. Last, the minimum user utility with different parameters and other disjoint optimization schemes are studied in Figs. 11-14. The results show that the proposed scheme can achieve larger user utility under different parameters, which implies the proposed scheme has a better performance than other disjoint optimization schemes.

Fig. 14
figure 14

Users utilities with transmit power

Full size image

5 Conclusion

In this paper, we study the UOTO optimization problem. The minimum user utility is maximized under the partial offloading schemes. Since the problem is formulated as a non-convex problem, a three-stage alternative optimization algorithm based on SCA and Nonlinear fractional programming is proposed to jointly optimize the power allocation, bandwidth allocation, offloading decision and UAV trajectory. Simulation results show that the proposed schemes outperform other disjoint optimization schemes. Besides, it is shown that the convergence speed of proposed algorithm is fast.

For the future work, we are going to study the more general case where multiple UAVs assisted mobile offloading, and the collision avoidance among UAVs should be carefully investigated. Another research direction is to consider UAV flight with a variable altitude, which would be very interesting and challenging.