Introduction
The development of 5G networks has fostered the advancement of numerous applications including augmented reality, autonomous driving, and remote operation systems. IoT devices are becoming an integral part of various industries to facilitate latency-sensitive automated services by continuously monitoring environments, performing advanced computations, and making critical decisions. IoT devices can fall short of the needed capabilities and, thus, do regularly rely on offloading computations to remote servers [1], [2]. Multi-access edge computing (MEC) has emerged as a promising alternative solution to cloud computing to process latency-sensitive computational requests closer to resource-constrained IoT devices in order to avoid long distance transmissions that consume time and energy [3]. In addition to the direct benefits experienced by the devices, MEC saves the backhaul infrastructure and the core network from significant traffic load especially in dense network scenarios [4].
IoT networks are typically prone to dynamic changes and continuous shifts in device density, positions, and types of requested services. Hence, MEC solutions in such environments have to adapt their resources and capabilities to meet the changing demands. In this work, we propose a dynamic MEC system to serve a given IoT network running latency-sensitive services. The proposed MEC system is provisioned by cloudlets (or edge servers) mounted on Unmanned Aerial Vehicles (UAVs) that hover close to the IoT devices to process their generated workload within target latency requirements. As opposed to wireless fixed cloudlets, UAV-mounted cloudlets yield an efficient and relatively low cost solution that can be flexibly deployed in dynamic environments, especially in ultra-dense networks or remote hard-to-reach areas. Owing to their high agility and mobility, UAVs present themselves as an effective and prompt means in enabling various communication and computing services for a wide range of industry verticals [5], [6]. They allow edge servers to fly closer to IoT devices establishing better line of sight (LoS) links leading to higher transmission rate and consequently reduced energy consumption. Moreover, additional UAVs can be deployed if needed in response to a high surge in traffic demand.
The problem of deploying UAV-mounted cloudlets to support latency-sensitive services in IoT networks is inherently composed of multiple subproblems: 1) planning the network of UAV-mounted cloudlets to determine the optimized number and 3D positions of the UAVs needed to serve the given demand; 2) associating IoT devices to the deployed UAVs, where each UAV may either provide edge computing capability or serve as a relay node to other UAVs that provide edge computing capability; 3) distributing the generated IoT workload among the deployed UAV-mounted cloudlets. In this work, we formulate this joint problem as a mixed integer program (MIP) with the key objective of minimizing the number of deployed UAVs while serving all IoT workload within its required deadline. After demonstrating that the problem is NP-hard, we propose an efficient solution based on the meta-heuristic ions motion optimization algorithm [7]. We demonstrate the effectiveness of the proposed solution using extensive simulations with comparisons to the optimal solution as a function of various system parameters.
The rest of this paper is organized as follows. In Section II, we cover the related literature and highlight the main contributions of this work. Section III details the system model and its key components. In Section IV, we formulate the considered problem as a mixed integer program. Section V describes the proposed scalable and efficient solution based on the ions motion algorithm. Section VI presents performance results for various scenarios. Finally, conclusions are drawn in Section VII.
Related Literature
A. Mobile Edge Computing
Mobile edge computing has been shown to be an effective solution to deal with the downsides of the power and computational constraints in IoT devices [8], [9]. To this end, a wide range of research questions need to be addressed for each possible network scenario depending on the performance objectives and implementation constraints.
For example, in [10] the authors studied the problem of latency-aware workload offloading in edge computing. They suggested an architecture based on software defined networks, and formulated the problem with the goal of minimizing the response time of the end users. They proved that this problem is NP-hard by a reduction from the known partition problem. They suggested a heuristic algorithm to solve the formulated problem based on a greedy strategy. Another work in [11] addressed the joint optimization problem of resource allocation and user requests’ offloading in mobile edge computing networks. In addition, they formulated the problem to minimize the utilized power by the IoT devices and proposed an efficient heuristic algorithm to solve the optimization problem based on an iterative approach. The authors in [12] studied the planning of an edge cloud network in mobile access networks. They focused on the placement of access points and cloudlets, together with the assignment of users to cloudlets. They considered two design cases, the first being a static state network and the second being a dynamic state network with varying service and load level due to user mobility. Authors performed extensive simulations using real 4G cellular datasets to evaluate the tradeoffs resulting from the two design cases. In [13], an end-to-end hybrid cloudlet placement architecture over passive optical networks was proposed. The authors formulated the problem of cost-optimized cloudlet placement as a mixed-integer non-linear programming problem while achieving delay requirements suitable for tactile services. The authors applied their model to urban, suburban and rural scenarios and presented a comparative performance study among the various scenarios in terms of deployment cost, workload assignment, computational resources and energy increase. On the other hand, the authors in [14] introduced an MEC-enabled fiber-wireless (FiWi) access network architecture where computation and storage-centric cloudlets provide reliable cloud services at the edge. A unified cloudlet-aware resource management scheme was proposed where the system is designed in two time division multiple access layers to enhance the network performance and the offloaded traffic is scheduled outside the FiWi transmission slots. To thoroughly study the effectiveness of the proposed solution, a comprehensive analytical framework is developed that is based on different metrics including packet delay, response time, energy efficiency, and battery life.
Other works focused on virtualizing the services and network functions available within an IoT environment. For example, the authors in [15] focused on distributing IoT based applications on edge servers. Specifically, they assigned a unique group of applications to each edge server and defined specific stringent latency requirements for each application. Moreover, they associated each IoT device with multiple edge servers to minimize the total response time. Another work in [16] performed an extensive study to evaluate the performance gains while using mobile edge computing in different scenarios and environments. They specifically considered a game application and studied the effect of device association and server positions on the effectiveness of the deployed solutions. The findings highlighted that the response time greatly depends on the positions of the edge servers and the task assignments between end users and edge servers.
B. UAV-Aided IoT Networks
Recently, UAVs have been playing an important role in facilitating the deployment of IoT services. In [17], the authors utilized UAVs for data collection in dense wireless networks where sensors aggregate their data using compressive data gathering and forward it to designated cluster heads. A UAV then visits all cluster heads along an efficient trajectory towards a remote sink node that processes the data. In [18], the authors deployed UAVs in 3D space to harvest data from IoT devices. They formulated the problem while minimizing the total power and associating different IoT devices to various UAVs. Similarly, in [19] the path of multiple UAVs was optimized to collect data generated by IoT devices efficiently. Initially, they deployed the UAVs within a static network consisting of fixed IoT devices. This step consisted of grouping devices together and associating each group to a single static UAV. Then, they considered the scenario of mobile UAVs where they optimized the path of multiple UAVs to collect IoT data while minimizing the energy consumed.
The research literature related to deploying UAV-mounted cloudlets is relatively limited. Some recent work has tackled the problems associated with using and deploying UAV-mounted cloudlets. For example, in [20], the authors suggested using UAVs as computing cloudlets where they focused on optimizing the allocated bit rates. They carefully designed the path of a single UAV equipped with high computing capabilities while optimizing both uplink and downlink resource allocation. In [21], UAVs were used to support the edge network and act as caching devices. The authors suggested and described a new architecture that can enable effective use of UAVs for both caching and edge computing purposes. The authors in [22] proposed a space-air-ground integrated network that provides edge computing services for different computation-intensive applications. They presented an edge-computing architecture where UAVs provide close edge computing services and satellites provide access to remote cloud computing servers. They first formulated the IoT tasks offloading problem and proposed a reinforcement learning solution. Then, they studied the resource allocation problem on edge servers, by formulating it as a mixed integer program and proposing an efficient heuristic algorithm.
On the other hand, the authors in [23] studied the joint problem of UAV-based computation offloading and trajectory design. Due to its non-convex nature, the authors reformulated the problem to solve it using sequential convex optimization techniques. In [24], a multiple UAV-enabled MEC network was studied. With a fixed number of UAVs, a ground user might offload its computational tasks to the UAV or decide to compute locally. Given the number of computational tasks, the position of the ground users, and the number of available UAVs, the authors studied the sum power minimization problem with latency and coverage constraints. They jointly optimized user associations, power control, computation capacity allocation, and location planning. In order to solve the non-convex problem, the authors proposed an iterative algorithm that gradually solves the three subproblems in an efficient manner.
C. Novel Contributions
Most of the existing literature on UAV-mounted cloudlets considers either a single UAV or a fixed number of UAVs to serve a set of devices with special focus on UAV path optimization and energy consumption reduction. In contrast to the related work, this paper presents a novel UAV-enabled edge computing solution for IoT networks by jointly optimizing the number of deployed UAVs, their positions in 3D space, the device-to-UAV associations, and the computation offloading decisions. In particular, we study the optimal 3D deployment of UAV-mounted cloudlets to support latency-sensitive IoT applications while considering a set of constraints related to the computational tasks, available resources, and quality of service targets. The proposed system model enables the efficient utilization of resources while benefiting from the UAVs’ unique properties such as flexibility and enhanced line-of-sight connectivity, where each deployed UAV can serve either as an edge computing node or as a relay to other nearby UAVs that are equipped with edge computing capabilities. In order to generate solutions for large scale IoT network scenarios, we also propose an effective meta-heuristic algorithm and demonstrate its low complexity and close-to-optimal performance.
System Model
We consider an area where
Every IoT device is expected to generate computational tasks, whereby requests of multiple devices are delivered to a designated UAV-mounted cloudlet for processing within target latency limits. Due to the low transmission power, some IoT devices may not be able to reach their respective UAV-mounted cloudlets; therefore, additional UAVs may be deployed to serve only as relay nodes without being equipped with edge computing capabilities. Consequently, based on the expected demand, a swarm of UAVs are deployed in 3D space as a fully meshed network. Selected UAVs are equipped with cloudlet resources while others serve as relay nodes to connect IoT devices to their cloudlets. The system model also supports cases where a given UAV can serve as a cloudlet for a set of IoT devices and as as a relay for other devices. In this work, we aim at placing the minimum number of UAVs in 3D space to handle all computational workload generated by the IoT devices in the network. Each IoT device is associated to one of the nearby UAVs denoted as home UAV that may either relay the tasks to another UAV for computation or compute the tasks locally. The UAV responsible for computing an offloaded task is denoted as the cloudlet UAV.
Figure 1 presents a sample network with six IoT devices offloading tasks to three UAV-mounted cloudlets. The device, first, associates with a nearby UAV to act as its home UAV and uploads its computation workload. Afterwards, the home UAV may compute the tasks locally and deliver the results to the respective IoT device upon completion or offload to another UAV that can handle the requests. If offloaded to another UAV, the latter computes the task and sends the result back to the home UAV to deliver it to the requesting IoT device. For example in Fig. 1 the IoT device in yellow is connected to one UAV but the offloaded task is computed by another UAV. The IoT device in blue is, however, served by a close UAV that acts as both its home as well as cloudlet UAV.
Sample network scenario with multiple IoT devices offloading computational tasks to a set of deployed UAV-mounted cloudlets.
A. Air-to-Ground Communication Channel
Accurate channel characterization is essential for the design of efficient UAV communication systems. A lot of work has been done to model air-to-ground channels between UAVs and end devices [25]. In this work, we consider the channel path loss model from [26] since it captures several relevant characteristics and is given as follows:\begin{align*} \mathrm {PL}_{D}=&20\log \left ({\frac {4\pi f_{c}}{c}}\right) + 20\log \left ({\sqrt {h^{2}+r^{2}}}\right) \\&\qquad \qquad \quad + p_{\mathrm {LoS}}\eta _{\mathrm {LoS}} + \left ({1 - p_{\mathrm {LoS}}}\right)\eta _{\mathrm {NLoS}},\qquad \quad \tag{1}\end{align*}
\begin{equation*} p_{\mathrm {LoS}}= \frac {1}{1+\mu \cdot \exp \left ({-\beta \left ({\arctan \left ({\frac {h}{r}}\right)-\mu }\right)}\right)}, \tag{2}\end{equation*}
B. IoT Computation Tasks
We consider that each IoT device
C. UAV Computing Resources
Each UAV
D. Computation Tasks: Total Delay
In case IoT device \begin{equation*} t_{\mathrm {total},i} = t_{\mathrm {up},ij} + 2*t_{\mathrm {U2U},jk} + t_{\mathrm {process},ik}, \tag{3}\end{equation*}
\begin{equation*} R_{ij} = \frac {B_{j}}{A_{j}}\log (1+\mathrm {SNR}_{ij}), \tag{4}\end{equation*}
\begin{equation*} t_{\mathrm {process},ik} = \frac {1}{\frac {f_{k}}{L}-\sum _{n } \lambda _{n}}, \tag{5}\end{equation*}
Problem Formulation
We mathematically formulate our problem in this section to determine the minimum number of UAVs in addition to optimal positions in 3D space to serve all IoT computation requests before their latency limits. An IoT device establishes network association with only one home UAV and its requested tasks are processed by one cloudlet UAV. The IoT device could either have the same UAV acting as both home UAV and cloudlet UAV or have two distinct UAVs with the respective roles. The need for two distinct UAVs arises whenever an IoT device is in the coverage range of a UAV with inadequate computation capacity to process its tasks. As a result, the device establishes network connectivity with the closer UAV that in turn relays the device’s tasks to another more capable UAV to act as the cloudlet UAV. This kind of relaying happens as long as the latency target is not violated. The formulated optimization problem determines the number of UAVs to be deployed, the position of each deployed UAV, the association of IoT devices to UAVs, and the role of each UAV with respect to each IoT device whether serving as a home UAV or a cloudlet UAV. The solution of the formulated problem ensures that the delay constraint of all devices is being satisfied.
To formulate the problem, we introduce a decision variable \begin{equation*} d_{j}= \begin{cases} 1, & \text {if UAV} ~j~ \text {is deployed}~\\ 0, & \text {otherwise} \end{cases}\tag{6}\end{equation*}
Since each IoT device may use up to two UAVs, a home UAV that connects the device to the UAV network and a cloudlet UAV that acts as an edge server and processes the computation tasks, we make use of two binary decision variables, \begin{equation*} a_{ij}= \begin{cases} 1, & \text {if IoT device} ~i~ \text {is associated with UAV}~j~\\ 0, & \text {otherwise} \end{cases}\tag{7}\end{equation*}
The other decision variable \begin{equation*} b_{ij}= \begin{cases} 1, & \text {if tasks of IoT device} \\ &\text {$i$are processed by UAV $j$} \\ 0, & \text {otherwise} \end{cases}\tag{8}\end{equation*}
\begin{equation*} P_{ij} \geq a_{ij} \sigma ^{2} \Gamma,\tag{9}\end{equation*}
According to the above, the problem is formulated as a mixed integer program as follows:\begin{align*}&\text {minimize } ~ \sum _{j = 1}^{D} d_{j} \tag{10}\\&\text {subject to } ~ a_{ij} \leq d_{j} \quad \forall i \in [1,U]\quad \forall j \in [1,D]\tag{11}\\&\hphantom {\text {subject to } ~} b_{ij} \leq d_{j} \quad \forall i \in [1,U] \quad \forall j \in [1,D]\tag{12}\\&\hphantom {\text {subject to } ~} \sum _{j = 1}^{D} a_{ij} = 1 \quad \forall i \in [1,U]\tag{13}\\&\hphantom {\text {subject to } ~} \sum _{j = 1}^{D} b_{ij} = 1 \quad \forall i \in [1,U]\tag{14}\\&\hphantom {\text {subject to } ~} P_{ij} \geq a_{ij} \sigma ^{2} \Gamma \quad \forall i \in [1,U] \quad \forall j \in [1,D]\tag{15}\\&\hphantom {\text {subject to } ~} \sum _{j = 1}^{D}{ \big (a_{ij}t_{\mathrm {up},ij} + \frac {b_{ij}}{\frac {f_{j}}{L}-\sum _{n = 1}^{U} b_{nj}\lambda _{n}}} \\&\hphantom {\text {subject to } ~} +\overline {a}_{ij}b_{ij}\sum _{k = 1}^{D}{a_{ik}t_{\mathrm {U2U},jk} } \big )\leq T_{i} \quad \forall i \in [1,U]\qquad \tag{16}\\&\hphantom {\text {subject to } ~} \frac {f_{j}}{L} - \sum _{i = 1}^{U} b_{ij}\lambda _{i} \geq 0 \quad \forall j \in [1,D]\tag{17}\\&\hphantom {\text {subject to } ~} \sum _{i = 1}^{U} a_{ij} \leq K_{D} \quad \forall j \in [1,D]\tag{18}\\&\hphantom {\text {subject to } ~} \sum _{j = 1}^{D}\sum _{k = 1}^{D} {\sqrt {(x_{j}-x_{k})^{2}+(y_{j}-y_{k})^{2}+(z_{j}-z_{k})^{2}}} \\&\hphantom {\text {subject to } ~} \geq \theta \quad \forall i,j \in [1,D]\tag{19}\end{align*}
The formulated problem attempts to optimize the deployment of UAVs while meeting different constraints related to the computation tasks, time limits, computational resources available, and power constraints. The objective function in (10) minimizes the number of deployed UAVs.
The first constraint in (11) ensures that an IoT device
The constraint in (17) ensures a stable queuing system at the cloudlet UAV where the arrival rate of computing requests does not exceed the service rate of the UAV. Constraint (18) makes sure that each home UAV does not exceed its user capacity
A. Complexity Analysis
We show that the formulated problem is NP-hard by dividing it into two sub-problems. The first sub-problem is the UAV deployment and the second sub-problem is the device-to-UAV association and IoT task assignment. The first sub-problem can be reduced to the capacitated facility location problem that is well known to be NP-hard [31]. This problem considers a number of facilities that have to be deployed in order to serve a number of customers. In our problem, the UAVs can be the facilities and the IoT devices the customers. The second sub-problem can be reduced to the assignment problem that is also well known to be NP-hard [32]. This problem requires the distribution of specific objects to different bins. In our problem, the IoT devices and their tasks can be the objects and the home UAVs and the cloudlet UAVs the bins. Hence, it is very hard to obtain an optimal solution to our problem especially for large-scale IoT network scenarios. Thus, we propose a scalable solution approach based on a meta-heuristic optimization as described in the next section.
Proposed Algorithm Based on Ions Motion Optimization
Even though this work does not address real-time network operation that requires prompt reaction to any traffic demand deviation, the high complexity of the problem and the difficulty of obtaining an optimal solution in a reasonable time raise the need for a more efficient solution. The complexity of the problem is further increased with a growing number of IoT devices lending the optimal solution unattainable. In this section, an efficient meta-heuristic algorithm is proposed to provide an optimized solution for large-scale networks in reasonable time. The proposed algorithm can thus be applied in response to any considerable change in traffic demand including IoT task generation rate, task latency targets, devices’ positions, and number of devices.
The proposed meta-heuristic algorithm is based on ions motion optimization that iteratively searches for an efficient solution that encompasses the number and positions of UAVs in addition to the device associations and computation task allocations. Ions motion optimization (IMO) was first suggested in [7] and is derived from the natural behavior of ions within different environments. It is a population based meta-heuristic where candidate solutions are represented as anions and cations. Anions are ions assigned negative charges and cations are ions assigned positive charges. Half of the population is considered as anions and the other half is considered as cations. When all these ions exist in the same environment, they form an electrically charged field where unlike ions attract and likewise ions repel. So, in an electrically charged environment, anions move towards cations and cations move towards anions. However, the behaviour of these ions and particles depend on the states of matters in which these particles are formed.
We customize the IMO approach to provide a scalable and efficient solution to our formulated optimization problem. To the best of our knowledge, this is the first work to apply IMO to solve an emerging problem in wireless network design. In the proposed algorithm, we consider two states according to [7], a liquid state where ions have greater freedom of motion followed by a solid state where ions are constrained to small-scale vibrations in their positions. In addition to these two states, the execution of the algorithm starts with an initialization phase and ends with a termination phase as described in the next subsection.
The main motivation behind selecting this solution approach is its fast convergence, ability to try to avoid local optima, and relatively small number of parameters that need be tuned compared to other meta-heuristic algorithms. In [7], authors showed that ion motion optimization provides better conversion behavior as compared to other meta-heuristics including genetic algorithms and particle swarm optimization. The algorithm’s fast convergence can be attributed to the liquid state where ions are attracted to the best anion and cation so promising search spaces are explored. Also, the algorithm avoids local optima due to the solid state where ions are forced to exit from the local optimum due to the repulsion forces applied. The balance between exploration and exploitation impacts the positioning of different UAVs and their roles and contributes to the fast conversion.
A. IMO Initialization Phase
Considering the three variables
The population is initialized as follows:\begin{align*} \mathrm {AI}_{sv}=&\mathrm {Min}_{v} + (\mathrm {Max}_{v} - \mathrm {Min}_{v}) r_{1} \tag{20}\\ \mathrm {CI}_{sv}=&\mathrm {Min}_{v} + (\mathrm {Max}_{v} - \mathrm {Min}_{v}) r_{2}\tag{21}\end{align*}
\begin{equation*} \sum _{j = 1}^{D} d_{j} +\sum _{j = 1}^{D} q_{j} + \sum _{i = 1}^{U} k_{i},\tag{22}\end{equation*}
\begin{equation*} a_{ij}= \left \lfloor{ \mathrm {AI}_{sv} }\right \rfloor \bmod 2. \tag{23}\end{equation*}
B. IMO Liquid Phase
In the liquid phase, ions are attracted to better ions of opposite charges. Cations will move towards the best anions and anions will move towards the best cations. Repulsion forces are neglected in this phase in order to explore the full search space. This behavior is represented on the sample schematic shown in Figure 2 left.
The figure on the left shows the behaviour of ions in the liquid phase (more freedom to move in the search space) and the one on the right shows the behavior in the solid phase (local vibration with limited freedom to move).
We consider the distance as the key factor affecting the force between opposite ions; thus, the force \begin{equation*} \mathrm {FA}_{sv}= \frac {1}{1+e^{\frac {-0.1}{\mathrm {DA}_{sv}}}}, \tag{24}\end{equation*}
After calculating the forces applied on each ion, the position of each anion is updated according to (25) and similarly the position of each cation is updated.\begin{equation*} \mathrm {AI}_{sv}= \mathrm {AI}_{sv}+\mathrm {FA}_{sv}(\mathrm {BestC}_{v} - \mathrm {AI}_{sv}). \tag{25}\end{equation*}
C. IMO Solid Phase
After the ions converge to an optimized solution causing them to enter the solid phase, anions and cations are trapped and have very limited freedom of motion as illustrated in the right of Figure 2. This convergence, however, might have led to a local optimum and thus requires an external force to crack the solid structure causing ions to move away from each other in random directions. This mechanism of exiting from a local optimum is described in Algorithm 1 where
Algorithm 1 IMO Solid Phase Implementation Based on [7]
procedure Solid–Phase
if (
if (random() ≥ 0.5) then
else
end if
if (random() ≥ 0.5) then
else
end if
if (random() ≤ 0.05) then
Randomly re-intialize all AIs and CIs
end if
end if
end procedure
D. IMO Termination Phase
The algorithm keeps on iterating between the solid and liquid states until the maximum number of iterations is reached and, thus, the best feasible candidate solution is returned. Depending on the nature of the problem formulation and the number of iterations, the outcome can coverage to the global optimum or can lead to the best achieved local optimum.
Simulation Results and Performance Analysis
In this section, we evaluate the proposed meta-heuristic solution approach for the problem formulated in Section IV. We generate extensive simulation results to demonstrate its effectiveness in terms of complexity and performance with respect to the optimal solution. We present results as a function of various system parameters and for multiple IoT use cases with different latency requirements. We note that the formulated optimization problem is solved using the mixed integer linear programming solver of MATLAB’s optimization toolbox after being linearized as detailed earlier; the IMO algorithm is implemented using JAVA programming language.
We consider a 200 m
Average number of UAVs required to serve the IoT devices for the optimal solution compared to the proposed meta-heuristic algorithm, as a function of the total number of IoT devices.
Execution time of the optimal solution versus the meta-heuristic approach as a function of the number of IoT devices.
Next, we deploy different applications on the IoT devices and consider various industry verticals. Table 2 presents the deadline ranges of the considered industry verticals and the maximum latency limit that we applied in our simulations.
In Fig. 5, we plot the average number of deployed UAVs as a function of the number of IoT devices available in the network with
Average number of UAVs required to serve the IoT devices based on the proposed meta-heuristic approach as a function of the total number of IoT devices for different industry verticals.
In Fig. 6, we study the average number of UAVs deployed for different verticals and according to different request rates; the computation task request rate
Average number of UAVs required to serve IoT devices in different industry verticals as a function of the rate of computation task requests.
To further study the effects of time deadlines and response times, we plot in Fig. 7 the average number of UAVs deployed to serve 200 users with
Average number of UAVs and achieved time delay as a function of the time deadline for the Tactile Internet use case.
Conclusion
In this work, we leveraged the flexibility, enhanced line of sight connectivity, and low cost of UAVs to deploy them as mobile edge computing cloudlets to serve resource-constrained IoT devices. Specifically, we addressed the joint problem of 3D deployment of UAV-mounted cloudlets, IoT device to UAV association, and IoT device to UAV-mounted cloudlet computation task offloading with focus on latency sensitive services. We formulated the problem as a mixed integer program, demonstrated that it is NP-hard, and proposed a low complexity efficient algorithm based on ions motion meta-heuristic optimization. Results are presented and analyzed as a function of a wide range of parameters and quality of service constraints. We demonstrated the effectiveness of the proposed algorithm in terms of achieving close-to-optimal performance with notably low complexity, making it especially attractive for large IoT network scenarios.
AppendixLinearization of Problem Constraints
Linearization of Problem Constraints
In this appendix, we describe the linearization of (15) and (16) using methods from [34].
The optimization problem constraint (15) can be linearized as follows.
\begin{align*} \dfrac {1}{P_{i,j}}\leq&a_{i,j} \dfrac {1}{\sigma ^{2} \Gamma } \\[2pt] \dfrac {1}{P_{i,j}}=&\dfrac {d^{2}}{\kappa P_{T}} \\[2pt] d^{2}=&(x_{d}-x_{u})^{2}+ (y_{d}-y_{u})^{2} = x_{d}^{2} + x_{u}^{2} - 2x_{d}x_{u} \\[2pt]&+\, y_{d}^{2} + y_{u}^{2} - 2y_{d}y_{u}\end{align*} View Source\begin{align*} \dfrac {1}{P_{i,j}}\leq&a_{i,j} \dfrac {1}{\sigma ^{2} \Gamma } \\[2pt] \dfrac {1}{P_{i,j}}=&\dfrac {d^{2}}{\kappa P_{T}} \\[2pt] d^{2}=&(x_{d}-x_{u})^{2}+ (y_{d}-y_{u})^{2} = x_{d}^{2} + x_{u}^{2} - 2x_{d}x_{u} \\[2pt]&+\, y_{d}^{2} + y_{u}^{2} - 2y_{d}y_{u}\end{align*}
, and similarlyx_{d}^{2} , can be linearized using piecewise linear approximation as per [34]. To do so, considery_{d}^{2} is limited betweenx_{d} as a lower bound andX_{2} as an upper bound; thusX_{1} . The piecewise linear approximation ofX_{2} \leq x_{d}\leq X_{1} can then be written as:x_{d}^{2} No other constraints are needed on\begin{align*} \lambda _{1}(X_{2})^{2} + \lambda _{2}\left({X_{1}\dfrac {1}{3}}\right)^{2} + \lambda _{3}\left({X_{1}\dfrac {2}{3}}\right)^{2} + \lambda _{4}(X_{1})^{2}=&x_{d}^{2} \\[2pt] \lambda _{1}(X_{2}) + \lambda _{2}\left({X_{1}\dfrac {1}{3}}\right) + \lambda _{3}\left({X_{1}\dfrac {2}{3}}\right) + \lambda _{4}(X_{1})=&x_{d} \\[2pt] \lambda _{1}+ \lambda _{2} + \lambda _{3} + \lambda _{4}=&1\end{align*} View Source\begin{align*} \lambda _{1}(X_{2})^{2} + \lambda _{2}\left({X_{1}\dfrac {1}{3}}\right)^{2} + \lambda _{3}\left({X_{1}\dfrac {2}{3}}\right)^{2} + \lambda _{4}(X_{1})^{2}=&x_{d}^{2} \\[2pt] \lambda _{1}(X_{2}) + \lambda _{2}\left({X_{1}\dfrac {1}{3}}\right) + \lambda _{3}\left({X_{1}\dfrac {2}{3}}\right) + \lambda _{4}(X_{1})=&x_{d} \\[2pt] \lambda _{1}+ \lambda _{2} + \lambda _{3} + \lambda _{4}=&1\end{align*}
since\lambda is convex.x^{2} The component
of the problem constraint represented in (16) can be linearized as follows. We first consider\overline {a}_{ij}b_{ij}\sum _{k = 1}^{D}{a_{ik}t_{U2U,jk}} , being a product of two binary variables, and replace it with another binary variable\overline {a}_{ij}b_{ij} conditioned by the following constraints to force it to take the value ofz_{ij}\in \{0,1\} .\overline {a}_{ij}b_{ij} Next, the component\begin{align*} z_{ij}\leq&\overline {a}_{ij} \\[2pt] z_{ij}\leq&b_{ij}\\[2pt] z_{ij}\geq&\overline {a}_{ij}+ b_{ij} -1\end{align*} View Source\begin{align*} z_{ij}\leq&\overline {a}_{ij} \\[2pt] z_{ij}\leq&b_{ij}\\[2pt] z_{ij}\geq&\overline {a}_{ij}+ b_{ij} -1\end{align*}
becomes\overline {a}_{ij}b_{ij}\sum _{k = 1}^{D}{a_{ik}t_{U2U,jk}} ; this involves product of two binary variables as above since both ofz_{ij}\sum _{k = 1}^{D}{a_{ik}t_{U2U,jk}} andz_{ij} are binary whilea_{ik} is a given parameter. We replacet_{U2U,jk} by a new variablez_{ij}\sum _{k = 1}^{D}{a_{ik}t_{U2U,jk}} and consider the maximum value of alls_{ij} ast_{U2U,jk}, \forall j,\forall k . The following constraints are then added to forceT_{U2U,jk} to take the value ofs_{ij} :z_{ij}\sum _{k = 1}^{D}{a_{ik}t_{U2U,jk}} \begin{align*} s_{ij}\leq&T_{U2U,jk}z_{ij}\\[2pt] s_{ij}\leq&\sum \nolimits _{k = 1}^{D}{a_{ik}t_{U2U,jk}}\\[2pt] s_{ij}\geq&\sum \nolimits _{k = 1}^{D}{a_{ik}t_{U2U,jk}} -T_{U2U,jk}(1-z_{ij})\\[2pt] s_{ij}\geq&0\end{align*} View Source\begin{align*} s_{ij}\leq&T_{U2U,jk}z_{ij}\\[2pt] s_{ij}\leq&\sum \nolimits _{k = 1}^{D}{a_{ik}t_{U2U,jk}}\\[2pt] s_{ij}\geq&\sum \nolimits _{k = 1}^{D}{a_{ik}t_{U2U,jk}} -T_{U2U,jk}(1-z_{ij})\\[2pt] s_{ij}\geq&0\end{align*}
The component
of the problem constraint represented in (16) represents a product of a binary variable\frac {b_{ij}}{\mu _{j}-\sum _{n = 1}^{U} b_{nj}\lambda _{n}} and a continuous variableb_{ij} . The latter product is denoted bym_{j} = \frac {1}{\mu _{j}-\sum _{n = 1}^{U} b_{nj}\lambda _{n}} .h_{ij} = b_{ij}m_{j} We can linearize
using the following constraints, whereb_{ij}m_{j} is an upper bound onM_{j} .m_{j} Then, we deal with\begin{align*} h_{ij}\leq&M_{j} b_{ij} \\ h_{ij}\leq&m_{j} \\ h_{ij}\geq&m_{j} - M_{j}(1-b_{ij}) \\ h_{ij}\geq&0\end{align*} View Source\begin{align*} h_{ij}\leq&M_{j} b_{ij} \\ h_{ij}\leq&m_{j} \\ h_{ij}\geq&m_{j} - M_{j}(1-b_{ij}) \\ h_{ij}\geq&0\end{align*}
. It becomesm_{j} = \frac {1}{\mu _{j}-\sum _{n = 1}^{U} b_{nj}\lambda _{n}} = 1. The componentm_{j}\mu _{j} - m_{j}\sum _{n = 1}^{U} b_{nj}\lambda _{n} comprises a product of continuous and binary variables and can also be linearized as above.m_{j}\sum _{n = 1}^{U}\,\,b_{nj}\lambda _{n}