Inter-server Computation Offloading and Resource Allocation in Multi-drone Aided Space-Air-Ground Integrated IoT Networks

I. INTRODUCTION

During the past years, it is widely acknowledged that Internet of things (IoT) networks are experiencing an explosive growth in regard to both the number of participated equipment and the supported services [1]. By integrating smart sensing and wireless technologies, IoT can seamlessly combine various heterogeneous networks to construct powerful systems in diverse applied fields such as intelligent transportation, smart agriculture, wisdom health care, and smart logistics [2]. As is well known, most applications in IoT are computation intensive and require high-performance computations to accomplish. However, constrained by the physical size, the batterypowered IoT devices usually have limited computing capacity and cannot provide sustainable computation resource [3]. The contradiction between resource-restricted IoT devices and resource-hungry applications reveals an unparalleled challenge for the evolution and deployment of on-going and future IoT networks. How to introduce new computing architecture into IoT ecosystem to efficiently process applications and reduce energy consumption, so as to extend the battery life of IoT devices, is of great importance and deserves further exploring.

Having sufficient computation resources and storage capacity, cloud computing is able to dramatically reduce the computation latency and the energy consumption of IoT devices. Nevertheless, due to the long transmission latency caused by the long distance from terminal user to the cloud center, it cannot satisfy the requirements of time sensitive applications [4]. To address this challenge, mobile edge computing (MEC) [5] has been proposed as a key paradigm toward the fifth generation mobile communication (5G) [6], which deploys computation resource on MEC servers (MECSs) at the network edge, e.g., base stations (BSs), small cells, and wireless access points, to provide flexible and efficient computing services to the mobile users. Unlike traditional cloud computing, MEC can significantly reduce the accomplishing time and improve the communication reliability by offloading the tasks of mobile users to the adjacent MECSs. However, limited by the network coverage and capacity, only depending ground 5G systems cannot fulfill the increasing traffic and computation requirements of diverse IoT applications, especially in remote and rural areas, where IoT devices could be also widely deployed to conduct special services with high computing demands, such as high-definition sound or video information processing [7]. Due to the absence of ground network infrastructure, the typical cloud and edge computing are unable to be applied in such cases [8]. IoT must leverage new network architectures to widen the communication coverage and enhance the computation capacity for the large number of connected devices and provided services.

Interconnecting satellites, aerial platforms, and ground IoT devices (GIDs), the space-air-ground integrated IoT (SAGIoT) network can provide seamless connectivity and enhanced capacity to diverse practical IoT applications [9]. In particular, the multiple drones, aka unmanned aerial vehicles (UAVs), aided SAG-IoT holds great promise for bringing lots of benefits in terms of high flexibility, high throughput, and high reliability [10]. On one hand, drones can not only act as aerial BSs to offer wireless access services to GIDs, but also play the role of transfers to forward the data traffic originated from GIDs to the satellites [11]. On the other hand, when installed with MECSs, drones are able to serve as the aerial edge servers to provide low latency and high efficiency computing functionality for GIDs.

In recent years, the multi-drone involved MEC in SAGIoT systems have attracted lots of attentions, and a great deal of novel offloading schemes have been designed to optimize either processing latency [12], or energy consumption [13], or resource allocation for both communication and computation [14]. These research works, although presenting precious viewpoints for the offloading decision optimization and resource allocation in such networks, have one common limitation: all of them based on the assumption that the MECSs installed on drones can execute all types of applications to cope with various types of computation tasks offloaded by GIDs. As a matter of fact, impeded by the high cost of hardware deployment and maintenance, the computing and storage capacities of MECSs on drones cannot be as abundant as infinite. Accordingly, it is unpractical for one MECS to host all cartilaginous applications to compute unnumberable tasks. How to leverage the available limitation of application types deployed on MECSs to investigate effective cooperative computation offloading schemes among multiple MECSs on drones, deserves further exploration. Furthermore, offloading computation tasks to the MECSs in SAG-IoT can effectively alleviate the problem of resource constraints and reduce energy consumption of GIDs. Meanwhile, additional communication latency overhead will be inevitably required the tasks are transmitted through the wireless links. Therefore, task offloading in SAG-IoT must comprehensively consider the computation overhead in terms of both energy consumption and processing latency. To the best of our knowledge, we are the first to discuss the collaborative task offloading within multi-server for multi-task in the multi-drone enabled MEC. Motivated by this, we present this paper to study the problem of inter-server computation offloading and resource allocation in multi-drone aided SAG-IoT networks by introducing hybrid computing models of local, edge and remote cloud, to minimize the overall computation overhead of all GIDs. In particular, the main contributions of this paper are summarized as follows.

Given the multi-drone aided space-air-ground integrated IoT network architecture, we mainly focus on the collaborative computation offloading of multi-server for multitask by comprehensively leveraging local computing, edge computing, and remote cloud computing models.

We present a novel joint optimization problem of interserver task offloading and bandwidth allocation as well as drone deployment, and formulate it as a constrained optimization problem with the objective of minimizing the overall computation overhead of GIDs.

By alternately adopting heuristic greedy method and successive convex approximation (SCA) technique, an iterative algorithm is exploited as our solution to the proposed problem while integrally considering the computation resource schedule within multiple servers and the communication resource allocation among different channels.

Extensive simulation experiments have been conducted to verify the efficiencies of our proposed schemes. Numerical results show that for various number of GIDs and drones as well as application types, the proposed iterative scheme can not only implement the best computation offloading decision, but also obtain the optimal spectrum allocation and drone position deployment, so as to achieve the minimum overall computation overhead.

The rest of this paper is organized as follows. Section II reviews the related works in recent years. In Section III, we first introduces the system model, and then the joint optimization problem of inter-server task offloading and resource allocation is formulated. Section IV describes the detailed iterative algorithm for the problem. We present extensive numerical results in Section V, and finally conclude the whole paper in Section VI.

II. RELATED WORK

Up to now, there have been many research works on the drone-enabled MEC systems in which the resource allocation schemes have been also proposed, including both single drone and multiple drones. For instance, with the constraints of energy-harvesting causal and the drone’s velocity, Zhou et al. in [15] aimed to maximize the computation rate in a droneenabled MEC wireless powered system through the joint optimization of processing unit frequency, user offloading latency and transmit power. Also in a drone-aided computing scenario, the authors in [16] proposed an alternative optimization scheme to minimize the total computation energy consumption by jointly optimizing offloading decisions, bit allocation and drone trajectory. While in [14], an optimization problem for minimizing the energy consumption of both communication and computation as well as drone’s flight was proposed in the drone assisted MEC system by integrally considering the power allocation, drone trajectory design, and bits allocation. Considering the limited battery of IoT devices and the energy budget in a drone enhanced edge, Guo et al. in [17] proposed a coordinate descent based approach to reduce the overall energy consumption for task processing.

In the multi-drone aided MEC networks, Zhang et al. in [18] presented a Dinkelbach-based iterative optimization algorithm to maximize the computation efficiency by taking into account computation bits, energy consumption, user association, power and spectrum resources, and drone trajectory scheduling. In [19], Guo et al. proposed a coded distributed computing framework for task offloading from multi-drone to ground MECSs to save transmission and flying energy consumption of drones and reduce computing latency by designing cost optimal trajectory and code parameter schedule algorithms. To cope with the problem of offloading heavy tasks of drones and to achieve the optimal trade-off among energy consumption, latency, and computation overhead, the authors in [20] presented a non-cooperative game theory based strategy in the drones assisted MEC system. To maximize the number of served IoT devices in the multi-drone enabled MEC network, Zhan et al. [21] presented a joint optimization scheme by adopting SCA method to alternatively optimizing computation offloading decisions, drone trajectory, and resource allocation. The authors in [22] presented a two-layer optimization strategy to minimize the total energy consumption in the multi-drone enabled MEC system consisting of large-scale IoT users by jointly optimizing the drone deployment and task scheduling. The authors designed a differential evolution algorithm and a greedy algorithm to solve the problem. In a multi-drone assisted SAG-IoT network, Cheng et al. [7] proposed a joint approach of computing resource allocation and task scheduling for MECs, and then devised a learning based method to optimize the offloading decisions with the objective of minimizing the computation cost.

Generally speaking, the existing works on drone-aided IoTMEC systems have introduced many novel methods for computation offloading and resource allocation. However, most of them mainly leveraged the edge servers deployed on drones to provide computing functionality for GIDs while ignored the sufficient computation resources in the remote cloud center (RCC). More importantly, the available studies presumed that the MECSs on drones were deployed all kinds of applications so that they had the capability of processing various types of computation tasks requested by GIDs. Subjected to the power limitation of drones and the architecture constraint of MEC, it is infeasible for MECSs on drones to be deployed as huge computation resources as cloud center. Each MECS can host finite kinds of applications to compute the offloaded tasks. Accordingly, task offloading in multi-drone assisted IoT systems must utilize the available resource deployed on MECSs and consider the collaboration among multiple servers. Although Yao et al. in [23] considered that workload could be served across multiple geographically distributed data centers, and proposed a stochastic optimization based approach to minimize the power consumption without reducing the amount of workload served, Sun et al. [24] designed two double auction mechanisms to improve the system efficiency while jointly considering incentives and cross-server resource allocation in blockchain-driven MEC, they mainly focused on the inter-server computation within fiber-connected data centers or MEC servers, while taking no consideration of the variable wireless communication links. Toward this end, we present this paper to elaborate the inter-server computation offloading and resource allocation problem for the computation overhead minimization in the multi-drone aided IoT network while collaboratively adopting local, edge, and RCC computing models.

III. SYSTEM MODEL AND PROBLEM FORMULATION

In this paper, we mainly consider a multi-task computation offloading scenario in the multi-drone aided SAG-IoT network, as shown in Fig. 1. [TeX:] $$M \operatorname{GIDs} \mathcal{M} \triangleq\{1,2, \ldots, M\}$$ are randomly deployed in a remote area covered by a low earth orbit (LEO) satellite to conduct certain tasks. In the air network, 𝑈 drones [TeX:] $$\mathcal{U} \triangleq\{1,2, \ldots, U\}$$ are hovering above this area within

a height range of [TeX:] $$\left[h_{\min }, h_{\max }\right],$$ and each drone is installed an MECS to provide enhanced computing service to the GIDs. In the following, both drone and MECS are collectively called ‘drone’ for easy presentation. All drones have the capability to communicate with both GIDs and other drones as well as satellites by adopting decode-and-forward (DF) scheme [25] and full-duplex technology, while each GID must leverage drone as relay to connect with the satellite. There are total 𝐾 types of computation tasks [TeX:] $$\mathcal{K} \triangleq\{1,2, \ldots, K\}$$ requested by all GIDs, and each GID [TeX:] $$m \in \mathcal{M} \text { has } K_{m}$$ types of task to execute, denoted by [TeX:] $$\mathcal{K}_{m} \triangleq\left\{k_{m, 1}, k_{m, 2}, \ldots, k_{m, K_{m}}\right\}, \text { where } \mathcal{K}_{m} \subset \mathcal{K},K_{m}<K. $$ For GID 𝑚’s type-𝑛 computation task, i.e., [TeX:] $$k_{m, n},$$ it can generally be defined as [TeX:] $$k_{m, n} \triangleq\left(s_{m, n}, c_{m, n}, \tau_{m, n}^{m a x}\right),$$ where [TeX:] $$s_{m, n}$$ denotes the input data size of [TeX:] $$k_{m, n}, c_{m, n}$$ is the requisite CPU cycles to compute [TeX:] $$k_{m, n}, \text { and } \tau_{m, n}^{\max }$$ is the maximum tolerated latency to accomplish [TeX:] $$k_{m, n}.$$

[TeX:] $$\mathcal{J} \triangleq\{1,2, \ldots, K\}$$ deployed on all drones, and each drone [TeX:] $$u \in \mathcal{U}$$ can host at most [TeX:] $$K_{u}$$ types of APPs [TeX:] $$\mathcal{J}_{u} \triangleq \left\{j_{u, 1}, j_{u, 2}, \ldots, j_{u, K_{u}}\right\}, \mathcal{J}_{u} \subset \mathcal{J}, K_{u}<K.$$ That is, one drone is unable to process all types of computation tasks, if drone 𝑢 does not host the corresponding APPs, the tasks must be transferred to other drones through the multi-hop wireless airto- air links for processing, or be transmitted to the RCC via the satellite backhaul link, thus the inter-server computation offloading among multi-drone is caused.

A. Communication Model

As depicted in Fig. 1, there exist three kinds of communication links in the system: 1) G2A link (GID-to-drone), 2) A2A link (drone-to-drone), and 3) A2S link (drone-to-satellite). For simplicity, we consider these communication links to be clear line of sight (LoS) links and neglect the impact of shadowing and small scale fading. Therefore, we can set the value of path loss exponent, [TeX:] $$\alpha=2.$$ In addition, orthogonal frequency division multi-plexing (OFDM) transmission is adopted to avoid co-channel interference among different G2A, A2A, and A2S links caused by the strong LOS channels in the integrated system. Let [TeX:] $$\mathcal{B}^{G 2 A}=\left\{\omega_{m, u}^{G 2 A} \geq 0, m \in \mathcal{M}, u \in \mathcal{U}\right\}, \mathcal{B}^{A 2 A}= \left\{\omega_{u, v}^{A 2 A} \geq 0, u, v \in \mathcal{U}, u \neq v\right\}, \text { and } \mathcal{B}^{A 2 S}=\left\{\omega_{u}^{A 2 S}, u \in \mathcal{U}\right\}$$ denote the allocated bandwidth on the G2A links from GIDs to drones, the A2A links between two drones, and the A2S links from drones to the satellite, respectively, the bandwidth allocation matrix can be represented as

The overall allocated bandwidth is

It is assume that both the GIDs and drones do not change their positions during the data delivery process. Let [TeX:] $$p_{m}^{G}$$ and [TeX:] $$\omega_{m, u}^{G 2 A}$$ denote the transmit power of GID 𝑚 and the allocated bandwidth to the G2A link from GID 𝑚 to drone 𝑢, respectively, the uplink data rate can be expressed as

where [TeX:] $$\sigma_{A}^{2}$$ is the additive white Gaussian noise (AWGN) at the drone receiver, [TeX:] $$g_{m, u}^{G 2 A}$$ is the channel gain of the G2A link from GID 𝑚 to drone 𝑢,

in which [TeX:] $$g_{0}$$ denotes the channel power gain at the reference distance [TeX:] $$d_{0}=1 \mathrm{~m}, \mathbf{q}_{m}^{G}=\left(x_{m}^{G}, y_{m}^{G}, 0\right) \text { and } \mathbf{q}_{u}^{A}=\left(x_{u}^{A}, y_{u}^{A}, z_{u}\right)$$ are the positions of GID 𝑚 and drone 𝑢 in the 3-D Cartesian coordinate system, respectively

Similarly, let [TeX:] $$p_{u}^{A} \text { and } g_{u, v}^{A 2 A}$$ represent the transmit power of drone 𝑢 and the channel gain of the A2A wireless link, respectively, the achievable data rate from drone 𝑢 to drone 𝑣 is

where [TeX:] $$g_{u, v}^{A 2 A}=g_{0} /\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{v}^{A}\right\|^{2}.$$ Furthermore, in order to avoid collision, the communication security distances among 𝑈 drones must be guaranteed, i.e.,

where [TeX:] $$d_{\min }$$ is the minimum security distance.

Using [TeX:] $$H_{S} \text { and } \sigma_{S}^{2}$$ to separately denote the orbit height and the AWGN of the satellite, the uplink data rate of the A2S link can be given as

where [TeX:] $$g_{u}^{A 2 S}=g_{0} /\left(H_{S}-h_{u}\right)^{2} \approx g_{0} /\left(H_{S}\right)^{2}$$ is the channel gain of the A2S link, [TeX:] $$G_{t x} \text { and } G_{r x}$$ are respectively the antenna gains of the drone and satellite. In general, we assume that each drone has an omni-directional antenna array element, as a result of which, [TeX:] $$G_{1 x}=1$$ is satisfied [26].

B. Computing Model

In general, there are three computing models for each computation task to select: 1) Local computing, using GID’s CPU for computing, 2) edge computing, processing at the edge servers deployed on the drones, and 3) cloud computing, offloading to the RRC for computing. Each GID 𝑚 can select one of the three models to process its type-𝑛 task. In particular, we use [TeX:] $$\lambda_{m, n} \in\{-1,0,1\}$$ to denote task [TeX:] $$k_{m, n} \text { 's }$$ computing model selection, where [TeX:] $$\lambda_{m, n}=-1$$ represents that GID 𝑚 wants to process type-𝑛 task via its own CPU, [TeX:] $$\lambda_{m, n}=0$$ means that task [TeX:] $$k_{m, n}$$ will be offloaded to the MECSs and be processed there, and [TeX:] $$\lambda_{m, n}=1$$ states that GID 𝑚 decides to compute its task [TeX:] $$k_{m, n}$$ on the RCC.

1) Local Computing: When [TeX:] $$\lambda_{m, n}=-1,$$ i.e., GID 𝑚 decides to process the type-𝑛 task by using its own CPU, the processing latency [TeX:] $$t_{m, n}^{l}$$ and the consumed energy [TeX:] $$E_{m, n}^{l}$$ can be separately calculated as

where [TeX:] $$f_{m}^{l},$$ is the computational capability of GID 𝑚 (in CPU cycles per second), and [TeX:] $$K_{M 1}$$ is a coefficient related to the GID 𝑚’s CPU hardware architecture [27].

The computation overhead of [TeX:] $$k_{m, n}$$ is a function of the processing latency and energy consumption, in the local computing model, it can be defined as

where [TeX:] $$\beta_{m, n}^{t} \in[0,1] \text { and } \beta_{m, n}^{e} \in[0,1]$$ are respectively the weighted coefficients of the computing latency and energy consumption for task [TeX:] $$k_{m, n}, \beta_{m, n}^{t}+\beta_{m, n}^{e}=1$$

2) Edge Computing: When [TeX:] $$\lambda_{m, n}=0, \operatorname{task} k_{m, n}$$ will be offloaded to the MECSs for processing. In this model, GID 𝑚 first upload [TeX:] $$k_{m, n}$$ to the connected drone 𝑢 via the G2A wireless link. Then [TeX:] $$k_{m, n}$$ will be accomplished there if drone 𝑢 hosts the corresponding APP, otherwise the task must be forwarded to other drones on which the required APP is deployed. Note that the time cost for sending back computed results from drones to GIDs is neglected in this paper since the data size of processed results is much smaller than that of input data for most IoT applications. On this condition, the accomplishing latency to accomplish task [TeX:] $$k_{m, n}$$ mainly includes two parts, i.e., the transmission latency for uploading and forwarding [TeX:] $$k_{m, n}$$ from GID 𝑚 to the target drone which hosts the corresponding APP, and the computing time at the drone.

If task [TeX:] $$k_{m, n}$$ can be directly computed at drone 𝑢, GID 𝑚 will transmit the task to this drone with the data rate of [TeX:] $$r_{m, 2}^{G},$$ and the transmission latency can be easily calculate as [TeX:] $$t_{m, n}^{e, t r}= s_{m, n} / r_{m, u}^{G 2 A}.$$ If drone 𝑢 does not hosts the corresponding APP to process task [TeX:] $$k_{m, n},$$ it must forward [TeX:] $$k_{m, n}$$ to the other drone 𝑤 on which the required APP is deployed via the multi-hop A2A links. Suppose that a drone can directly forward its data to at most one of other ones. Let [TeX:] $$\mathcal{H}_{u, w}=\left\{h_{i}|1 \leq i \leq| \mathcal{H}_{u, w} \mid\right\}$$ denote the ordered set of drones on the routing path from drone 𝑢 to 𝑤, obviously, [TeX:] $$h_{1}=u, h_{\mid \mathcal{H}_{u, w}} \mid=w, \text { where }\left|\mathcal{H}_{u, w}\right|$$ is the cardinality of set [TeX:] $$\mathcal{H}_{u, w}.$$ According to the DF protocol, the transmission rate for forwarding the task [TeX:] $$k_{m, n}$$ from drone 𝑢 to 𝑤 can be calculated as

Thus, the data delivery rate for task [TeX:] $$k_{m, n}$$ from GID 𝑚 to drone 𝑤 is expressed as

and the delivery latency is

The time cost for computing [TeX:] $$k_{m, n}$$ can be expressed as

where [TeX:] $$f_{u}^{e} \text { and } f_{w}^{e}$$ denote the computing ability of the drones 𝑢 and 𝑤, respectively, [TeX:] $$\rho_{m, n}^{u}$$ is a binary variable, [TeX:] $$\rho_{m, n}^{u}=1$$ represents that task [TeX:] $$k_{m, n}$$ can be computed at drone [TeX:] $$u, \rho_{m, n}^{u}=0$$ otherwise.

In this case, the accomplishing latency [TeX:] $$t_{m, n}^{e}$$ and the energy consumption of GID 𝑚, [TeX:] $$E_{m, n}^{e},$$ can be respectively given as

and

The computation overhead of [TeX:] $$k_{m, n}$$ in the edge computing model is calculated as

3) Cloud Computing: As for the case of offloading decision [TeX:] $$\lambda_{m, n}=1,$$ GID 𝑚 will transmit its computation task [TeX:] $$k_{m, n}$$ to the RCC through the satellite links, and then the RCC server will process the task. It is noticeable that RCC servers are always deployed rich computation resource, thus, only the transmission latency and propagation latency from GID 𝑚 to the RRC are taken into account and the computing latency of [TeX:] $$k_{m, n}$$ in this model can be neglected. Also based on DF protocol, the uplink data rate of [TeX:] $$k_{m, n}$$ from GID 𝑚 to the satellite using drone 𝑢 as relay can be expressed as

Then the transmission latency can be obtained as [TeX:] $$t_{m, n}^{c, t r}= s_{m, n} / r_{m, n}^{c},$$ and the propagation latency is [TeX:] $$t_{m, n}^{c, p r}=2 H_{s} / c, c=3 \times 10^{8}$$ m/s is the velocity of electromagnetic wave in vacuum. Then, when being computed in RRC, the processing latency [TeX:] $$t_{m, n}^{c} \text { of } k_{m, n}$$ and the energy consumption of GID 𝑚, [TeX:] $$E_{m, n}^{c},$$ can be separately calculated as [TeX:] $$t_{m, n}^{c}=t_{m, n}^{c, t r}+t_{m, n}^{c, p r}$$ and [TeX:] $$E_{m, n}^{c}=p_{m} t_{m, n}^{C, t r}.$$ The computation overhead of [TeX:] $$k_{m, n}$$ in the cloud computing model is given as

C. Problem Formulation

According to the system models and assumptions discussed above, the main objective of this paper is to obtain the minimum computational overhead of all GIDs by jointly optimizing the task’s computation offloading decision, spectrum allocation, and drone position deployment, while satisfying the maximum tolerated processing latency of all tasks and the given total available bandwidth [TeX:] $$\Omega.$$ For notational convenience, we define [TeX:] $$\mathcal{S}=\left\{\lambda_{m, n}\right\}, Q=\left\{\mathbf{q}_{u}^{A}\right\}, \text { and } \mathcal{P}=\{\mathcal{S}, \mathcal{B}, Q\},$$ the constrained computational overhead minimizing problem can be mathematically formulated as follows.

where

and

[TeX:] $$I_{\{\cdot\}}$$ is an indicator function, [TeX:] $$I_{\{\cdot\}}=1 \text { if }\{\cdot\}$$ holds, otherwise[TeX:] $$I_{\{\cdot\}}=0.$$

In problem P1, the constraint 𝐶1 ensures that the accomplishing latency of each task must meet the requirement of its maximum tolerated processing time. 𝐶2 denotes that the totally allocated bandwidth in the system cannot exceed the available spectrum, and 𝐶3 means the allocated bandwidth cannot be negative. 𝐶4 is the flow conservation constraint [28] in the multi-hop relay wireless networks, which declares the total outgoing flows of each drone should be less than or equal to its sum of incoming ones. While the constraint 𝐶5 states that each task can be computed at most on one drone. 𝐶6 and 𝐶7 guarantee the communication security distance among drones. 𝐶8 represents that each task [TeX:] $$k_{m, n}$$ can select any but only one computing model from the three offloading choices. It is easy to prove that problem P1 is NP-hard [29] and it cannot be solved in polynomial time.

IV. JOINT OPTIMIZATION OF INTER-SERVER TASK OFFLOADING AND ROURCE ALLOCATION

The objective function of problem P1 is multivariate with respect to variables [TeX:] $$\mathrm{s} \mathcal{S}, \mathcal{B}, \text { and } Q.$$ Constraints 𝐶1, 𝐶4, 𝐶6 and the objective function are all non-convex. What’s more, P1 is also a mixed integer programming problem due to the variables [TeX:] $$\lambda_{m, n} \text { and } \rho_{m, n}^{u}.$$ Therefore, P1 is a non-convex mixed integer programming optimization problem, which is difficult to solve. To efficiently handle problem P1, we decompose it into three subproblems by alternately optimizing the offloading decision [TeX:] $$\mathcal{S},$$ bandwidth allocation [TeX:] $$\mathcal{B},$$ and drone deployment Q. And then the minimum computational overhead and the optimal solution to P1 are obtained through an iterative method.

A. Computation Offloading Optimization

Given bandwidth allocation [TeX:] $$\mathcal{B}$$ and drone deployment Q, problem P1 can be formulated as

Obviously, P1.1 is an integer programming problem and can be solved by adopting the enumeration method, which has high computational complexity of [TeX:] $$O\left(3^{M K_{m}}\right)$$ and is not applicable to large scale problems. Notice that for the fixed bandwidth allocation and drone position deployment strategies, which computing model will be selected for each task depends on whether it can achieve the minimum overhead with the constraint of maximum processing latency. Based on this, we propose a heuristic greedy offloading optimization algorithm (HGOA) to solve problem P1.1. In HGOA, we first select the tasks of which the accomplishing latency meets their maximum tolerated processing time and record them into set [TeX:] $$\mathcal{K}^{s a t},$$ then assign the offloading decisions of the tasks in [TeX:] $$\mathcal{K}^{s a t}$$ according to their minimum computational overhead by comparing three computing models, respectively. The details of the proposed HGOA are elaborated in Algorithm 1.

In Algorithm 1, calculating [TeX:] $$t_{m, n}^{e} \text { and } \phi_{m, n}^{e}$$ means that task [TeX:] $$k_{m, n}$$ is chosen to be computed at the drone. As discussed in Section III-B, this task cannot be processed until the specific drone hosting the corresponding APP is searched. To obtained the minimum forwarding latency from drone 𝑢 to 𝑤, we proposed an open shortest path first (OSPF) routing strategy based APP searching method to obtain the maximum forwarding data rate [TeX:] $$r_{u, w}^{A 2 A},$$ which is summarized in Procedure 1.

B. Bandwidth Allocation Optimization

According to (21), when the computation offloading scheme is known, [TeX:] $$\phi_{m, n}^{l}$$ is a constant, and [TeX:] $$\phi_{m, n}$$ varies only with [TeX:] $$\phi_{m, n}^{e}$$ and [TeX:] $$\phi_{m, n}^{c}.$$ Therefore, for any given [TeX:] $$\mathcal{S},$$ problem P1 can be redefined as

Define [TeX:] $$X=\left\{x_{m, u}>0, \forall m \in \mathcal{M}, \forall u \in \mathcal{U}\right\}, \mathcal{Y}=\left\{y_{u, v}>\right.0, \forall u, v \in \mathcal{U}, u \neq v\}, \text { and } \mathcal{Z}=\left\{z_{u}>0, \forall u \in \mathcal{U}\right\}, \phi_{m, n}^{c} \text { and } \phi_{m, n}^{e}$$ can be separately expended as

and

Similarly, the expansion of constraint 𝐶1 can be expressed as

Thus, problem P1.2 is transformed into

From (3), (5), and (7), we can see that [TeX:] $$r_{m, n}^{G 2 A}, r_{U}^{A 2 A}, \text { and } r_{u}^{A 2 S}$$ are linear functions with respect to [TeX:] $$\omega_{m, u}^{G 2 A}, \omega_{u, v}^{A 2 A}, \text { and } \omega_{u}^{A 2 S},$$ respectively. Therefore, both the objective function and the constraints of problem P1.2′ are convex, and it can be solved in optimization solvers such as YALMIP toolbox [30].

C. Drone Deployment Optimization

Under given computation offloading scheme [TeX:] $$\mathcal{S}$$ and bandwidth allocation [TeX:] $$\mathcal{B},$$ the problem of drone deployment optimization can be transformed into

In problem P1.3, constraints 𝐶1, 𝐶4, and 𝐶6 as well as the objective function are non-convex due to that [TeX:] $$F_{m, u}^{G 2 A}, F_{u, v}^{A},$$ and [TeX:] $$\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{v}^{A}\right\|^{2}$$ are non-convex with respect to [TeX:] $$\mathbf{q}_{u}^{A}$$ and [TeX:] $$\mathbf{q}_{v}^{A}.$$ However, [TeX:] $$r_{m, u}^{G 2 A} \text { and } r_{u, v}^{A 2 A}$$ are respectively convex with respect to [TeX:] $$\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{m}^{G}\right\|^{2} \text { and }\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{v}^{A}\right\|^{2}, \text { while }\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{v}^{A}\right\|^{2}$$ is convex with regard to [TeX:] $$\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{V}^{A}\right\|.$$ It is known the first-order Taylor expansion of any convex function is its global lower bound at any point [31]. Therefore, we can adopt the SCA technique [32] to cope with the non-convexity of P1.3. Let [TeX:] $$\left(\mathbf{q}_{u}^{A}\right)^{i} \text { and }\left(\mathbf{q}_{v}^{A}\right)^{i}$$ denote the positions of drone 𝑢 and 𝑣 in the

𝑖-th iteration, respectively, by applying the first-order Taylor expansion of [TeX:] $$r_{m, u}^{G 2 A} \text { and } r_{u, v}^{A 2 A},$$ we have

and

Similarly, [TeX:] $$\left\|\mathbf{q}_{u}^{A}-\mathbf{q}_{v}^{A}\right\|^{2}$$ can be substituted with its convex lower bound at a given local point in each iteration, i.e.,

Also by introducing the auxiliary variables [TeX:] $$X \text { and } \mathcal{Y},$$ we replace [TeX:] $$r_{m, u}^{G 2 A} \text { and } r_{u, v}^{A 2 A} \text { with }\left(r_{m, u}^{G 2 A}\right)^{\prime} \text { and }\left(r_{u, v}^{A 2 A}\right)^{\prime}$$ in (26), (25) and (27) to obtain [TeX:] $$\left.\left(\phi_{m, n}^{e}\right)^{\prime \prime},\left(\phi_{m, n}^{c}\right)\right)^{\prime \prime}, \text { and }\left(t_{m, n}\right)^{\prime \prime},$$ respectively, problem P1.3 can be converted into

where

Notably, problem P1.3′ is convex and can be solved by using YALMIP solver.

D. Overall Algorithm

Based on the block coordinate descent method [33], a joint optimization algorithm (JOA) is devised by alternately solving the three sub-problems P1.1, P1.2′, and P1.3′ in an iterative manner, which is described in Algorithm 2.

E. Computational Complexity Analysis

From the whole solving process of problem P1 described above, one can see that the proposed joint optimization scheme uses an iterative method to obtain the minimum computation offloading overhead of all GIDs. The computational complexity of the overall scheme is mainly determined by the resolution progress of the three sub-problems via the whileloop in Algorithm 2. The heuristic greedy computation offloading optimization scheme in Algorithm 1, which is used to solve P1.1, has the computational complexity of [TeX:] $$O\left(\left(M K_{m}\right)^{2}\right),M K_{m}$$ is the total number of the computation tasks. Problem P1.2′ and P1.3′ are solved by adopting a primal-dual interior point algorithm in YALMIP toolbox with complexity of [TeX:] $$O\left(\left(M K_{m}\right)^{3} \log \left(\zeta^{-1}\right)\right)$$ [18], where [TeX:] $$\zeta$$ is the accepted duality gap, i.e., the allowance error. Accordingly, if the maximum iteration numbers of Algorithm 2 is [TeX:] $$l_{\max },$$ the overall computation complexity for the proposed joint optimization algorithm can be calculated as [TeX:] $$O\left(l_{\max }\left(\left(M K_{m}\right)^{2}+\left(M K_{m}\right)^{3} \log \left(\zeta^{-1}\right)\right)\right).$$

V. NUMERICAL RESULTS

A. Parameter Settings

Without loss generality, we consider a remote [TeX:] $$3 \mathrm{~km} \times 3 \mathrm{~km}$$ square area in which 50 GIDs are randomly distributed. 10 drones are hovering at the height of 100 m ∼ 150 m above this area, the minimum distance between UAVs is set as 100 m. Each drone has the same computation capacity of 6 GHz, and the CPU frequency of each GID is 0.8 ∼ 1 GHz. There are total 10 types of computation tasks requested by all GIDs and each GID has two types of tasks to process. There are also 10

types of APPs deployed on all drones and each drone can host two types of APPs. The input data size of a task is set as 0.5 ∼ 1 MB, and the CPU cycles for computing it is assumed to be 0.1 ∼ 1 Gigacycles. The maximum tolerated accomplishing latency of each task is 0.1 ∼ 2 s, and the weighted coefficients [TeX:] $$\beta^{t} \text { and } \beta^{e}$$ are all set as 0.5. Furthermore, the transmit power of each GID and UAV are set as 0.1 W and 3 W, respectively. The LEO satellite’s orbit height is set as 500 km, and its receiving antenna gain is set to be 45 dBi. The G2A, A2A, and the A2S channels are all working at C-band and the totally allocatable bandwidth is 200 MHz, and the AWGN is assumed to be −110 dBm.

B. Simulation Results

Considering that our proposed joint optimization algorithm is an alternately iterative method, its convergence should be firstly analyzed. Fig. 2 presents the convergence behavior of the joint optimization scheme, i.e., JOA, with the growing

number of GIDs. Especially, Fig. 2(a) illustrates the convergence analysis of JOA with regard to the overall computation overhead, in which the numbers of GIDs 𝑀 are set as 10 and 30, respectively. Fig. 2(b) depicts the average iterations for the convergence of JOA with different number of GIDs and drones. As can be seen from these figures, given different number of GIDs and drones, JOA can always obtain the minimum computation overhead after a certain number of iteration, which verifies that our proposed joint optimization scheme has a fast and stable convergence.

Next, we evaluate the effectiveness of our proposed task offloading algorithm (HGOA) by comparing the computation overhead with other offloading schemes, i.e., an optimal enumeration algorithm (OEA) and a random algorithm (RNDA). Further, other two task offloading methods, CHGO and COOL, which were designed in [34] and [35], respectively, and collaboratively utilized three computation models, are also adopted in the simulation. In particular, CHGO is a central-

ized offloading method in which each task first selects the computing model that can achieve the minimum computation overhead, and then the GID reports its offloading decision to the RCC. One of the tasks makes its current optimal offloading decision after the RCC broadcasts all the wireless connections to the drones and GIDs. While COOl is a decentralized game theory based offloading mechanism, which regards each task as a player and it can probably choose an appropriate decision given the offloading decision of other tasks. Considering the high computational complexity of OEA, the number of GIDs varies from 5 to 10. Fig. 3 demonstrates the performance comparison among these five algorithms. Fig. 3(a) depicts the comparison results of the overall computation overhead. As can intuitively be seen from this figure, given the same number of GIDs, HGOA is able to obtain the minimum computation overhead very close to OEA, and it has better performance than both CHGO and COOL. Since CHGO must report each GID’s offloading decision to the RCC, which inevitably increases the processing latency, leading to higher computation overhead. Fig. 3(b) shows that our proposed offloading algorithm has a much shorter running time than that of OEA. Even compared to CHGO and COOL, HGOA still has a higher computational efficiency. It is verified from these two figures that HGOA can achieve a near-optimal computation overhead within a very short running time. Furthermore, although the random algorithm is the fastest offloading scheme, it obtains the worst performance of computation overhead.

In order to evaluate our proposed joint optimization scheme, we provide some comparisons on the overall computation overhead of GIDs under diverse optimization schemes, including scheme only optimizing offloading decision, scheme only optimizing bandwidth allocation, scheme only optimizing drone deployment, scheme with no optimization, and our proposed one. Specially, in the non-optimized scheme, the random offloading decision, average bandwidth allocation, and random drone deployment are adopted. Fig. 4 demonstrates the

compared results as the number of GIDs varying from 10 to 100. It can be seen from the comparison shown in this figure, when the number of GIDs is small, the overall computation overhead obtained by the joint optimization scheme is near to the that by other schemes, while as the GID number increasing, the gap between them becomes larger. Fig. 4 also shows that the scheme with only drone deployment optimization is slightly better than the one with no optimization, which has the worst performance. This is due the fact that, optimizing drone position deployment can improve the channel gains of G2A and A2A links so as to enhance the data delivery rate and reduce the transmission latency, but such improvement is inferior than that of the offloading decision and bandwidth allocation optimization. Finally, our proposed joint optimization scheme is much more preferred to the other four schemes as the scale of GIDs becomes larger.

To further validate the performance of our proposed task offloading scheme, we compare the achieved overall computation overhead by adopting different offloading schemes, i.e., computing all tasks locally, offloading all tasks to the MECSs, and our proposed scheme. In addition, to show the advantage of introducing RCC computing, the scheme of joint optimization without RCC model, is added into the comparison. What’s more, we also introduce the scheme presented in [18] into the comparison, which jointly optimized offloading decision, resource allocation, and drone trajectory, but took no consideration for RCC model. Fig. 5 provides the comparison results among these five schemes. As seen from the figure, one can find that our proposed offloading scheme outperforms the other four ones. Moreover, when the number of GIDs is small, all tasks computing at the edge can produce less computation overhead than local computing thanks to the abundant computation resource on the MECSs. However, with the growth of GID number, the overhead of edge computing gradually exceeds that of local computing and increases extremely. Evidently, given the limited spectrum

resource, a large number of GIDs choosing edge computing will greatly decrease the data rate, leading to longer transmission latency and larger computation overhead. Furthermore, our proposed scheme can obtain better performance than the one without RCC computing, which corroborates the necessity of introducing RCC computing model in the SAG-IoT MEC networks. Fig. 5 also verifies that, even without RCC model, our proposed joint optimization scheme is slightly superior to the one in [18].

Notice that the computation overhead consists of processing latency and energy consumption for the accomplishment of tasks, and the weighted coefficients [TeX:] $$\beta^{t} \text { and } \beta^{e}$$ [TeX:] $$\beta^{t} \text { and } \beta^{e}$$ as different values to verify how these coefficients effect on the overall computation overhead. Fig. 6 demonstrates the simulation results when the number of GIDs increasing from 10 to 100. One can easily observed from this figure that, given the same number of GIDs, with [TeX:] $$\beta^{t}$$ increasing and [TeX:] $$\beta^{e}$$ decreasing, the overall computation overhead monotonously declines. Especially when [TeX:] $$\beta^{t}=1$$ and [TeX:] $$\beta^{e}=0,$$ the computation overhead will contain only processing latency. Therefore, the value settings of weighted coefficients should take into account the actual application scenarios of computation tasks. For instance, if the task is time sensitive, we should give priority to the processing latency and set [TeX:] $$\beta^{t}$$ as a larger value.

To identify how the computing resource of drones affects the overall computation overhead, we change the number of APPs deployed on each drone and compare the obtained results. In this group of simulations, the number of GIDs is set as 50, the types of tasks requested by each GID and the APPs hosted on each drone are all vary from 2 to 10 with the increment of 2. Fig. 7 presents the comparisons of the calculated overall computation overhead under different numbers of task and APP types. It can be easily observed that, when the number of APP types hosted on each drone, i.e., [TeX:] $$K_{u},$$ is fixed, the overall computation overhead increases following the growth of task

types requested by each GID, i.e.,[TeX:] $$K_{m}$.$ While for the same [TeX:] $$K_{m},$$ the overall overhead presents a monotone decreasing tendency with [TeX:] $$K_{u}$$ growing. The reason is that if one drone hosts all types of APPs, it will has the capability of process all types of tasks and the inter-server data forwarding is unnecessary, which can significantly reduce the task’s total accomplishing latency and the overall computation overhead

VI. CONCLUSIONS

This paper mainly investigated the problem of inter-server task offloading and bandwidth allocation for computation overhead minimization in the multi-drone aided SAG-IoT network. The issue was formally defined as a constrained optimization problem according to communication and computing models. To efficiently tackle this problem, we first decomposed it into three sub-problems, and then leveraged heuristic greedy algorithm and successive convex approximation method to solve them. Finally, an iteratively joint optimization scheme was proposed by alternately optimizing offloading decision, bandwidth allocation, and drone deployment. Various numbers of GIDs and different optimization schemes as well as diverse offloading models have been adopted to evaluate the performance of our proposed algorithms. Numerical results demonstrated that, to the joint optimization problem of inter-server offloading and resource allocation, our presented solutions could achieve the minimum overall computation overhead of all GIDs in the multi-drone assisted SAG-IoT systems.