1

Deployment and Trajectory Optimization of
UAVs: A Quantization Theory Approach

arXiv:1708.08832v5 [] 16 Mar 2018

Erdem Koyuncu, Maryam Shabanighazikelayeh, and Hulya Seferoglu

Abstract
Optimal deployment and movement of multiple unmanned aerial vehicles (UAVs) is studied. The
considered scenario consists of several ground terminals (GTs) communicating with the UAVs using
variable transmission power and fixed data rate. First, the static case of a fixed geographical GT density
is analyzed. Using high resolution quantization theory, the corresponding best achievable performance
(measured in terms of the average GT transmission power) is determined in the asymptotic regime of
a large number of UAVs. Next, the dynamic case where the GT density is allowed to vary periodically
through time is considered. For one-dimensional networks, an accurate formula for the total amount
of UAV movement that guarantees the best time-averaged performance is determined. In general, the
tradeoff between the total UAV movement and the achievable performance is obtained through a
Lagrangian approach. A corresponding trajectory optimization algorithm is introduced and shown to
guarantee a convergent Lagrangian. Numerical simulations confirm the analytical findings. Extensions
to variable-rate fixed-power systems are also discussed.

Index Terms
Unmanned aerial vehicles (UAVs), node placement, trajectory optimization, quantization theory.

I. I NTRODUCTION
Unmanned aerial vehicles (UAVs) can be effectively utilized in a variety of wireless communication scenarios. Example applications include providing coverage to geographical areas lacking
The authors are with the Department of Electrical and Computer Engineering, University of Illinois at Chicago. Emails:
{ekoyuncu, mshaba7, hulya}@uic.edu
This work will be presented in part at the IEEE Wireless Communications and Networking Conference in April 2018 [1].

2

a wireless infrastructure, relaying to overcome terrain obstacles such as mountains, improving
cell edge performance by creating femtocells, among many others [2]–[4].
One of the most distinguishing features of UAV networks is the opportunity of very fast dynamic adaptation to the ever-changing environment through relocation. Environmental variations
in this context may include ground terminal (GT) location/density variations, UAV node failures,
etc. Although the ability of relocation potentially offers significant performance gains, including
improved coverage and rate for GTs, it also comes with many theoretical and practical challenges.
Even in a static scenario where the locations or the density of GTs are known and fixed,
finding the optimal UAV locations is a non-convex optimization problem whose dimensionality
grows with the number of UAVs [2]. Dynamic scenarios further involve optimization of UAV
trajectories, thus leading to much more complicated infinite-dimensional optimization problems.
Several approaches to resolve the challenges of UAV deployment/relocation have been proposed. In the case of static deployment, [5]–[7] consider the optimal placement of UAVs to
maximize coverage and propose several algorithms. These works assume that a UAV can cover
a GT provided that they are separated no more than a certain distance. In [8], the authors
consider instead the average throughput as the objective function, and incorporate possible hover
time constraints of UAVs into the problem formulation. Static placement of UAVs as relays for
offloading cellular traffic [9], or generic multihop communication [10] have also been studied.
Random deployments of UAVs are analyzed in [11] using tools from stochastic geometry.
There are also numerous works on dynamic deployment of UAVs. One well-studied scenario
is to view UAVs as mobile access points serving GTs. For such a use case, algorithms for UAV
coverage under variable coverage radii and possible UAV losses are proposed in [12]. For one
UAV and one GT, [13] optimizes the UAV trajectory to achieve high throughput with low UAV
energy consumption. A genetic algorithm for UAV trajectory optimization has been proposed
in [14] with the specific goal of restoring network service after natural disasters. In [15], the
authors optimize the trajectory of a single UAV serving multiple mobile GTs via space-division
multiple access. A Kalman filter predicts the future GT locations, which, in turn, determine the
UAV trajectory. Given several sensors on a one-dimensional space and one UAV, [16] determines

3

the time-varying UAV speed that minimizes the data collection time. A related problem is to
optimize the UAV trajectories subject to speed constraints [17], [18]. In [19], the authors consider
a UAV multicasting network-coded information to several GTs and the corresponding trajectory
optimization problem. An algorithm to minimize the energy consumption of moving the UAVs
from one deployment to another can be found in [20].
Several other works have considered the dynamic deployment problem in the context of UAVs
serving as communication relays. In particular, for a single source-destination pair and one UAV,
[21] develops a mobile UAV relaying method. The goal is throughput maximization via jointly
optimizing UAV trajectory and temporal power allocation. The utilization of UAVs as relays
between GTs and a central base station has been studied in [22], and a joint heading and
adaptive handoff algorithm is proposed. In [23], [24], the authors design trajectory optimization
algorithms for amplify-and-forward UAVs. For the case of one UAV and a circular trajectory, [25]
optimizes the speed and load factor of the UAV for maximum energy efficiency. UAVs can also
offer computation offloading opportunities in the context of edge computing. A corresponding
trajectory optimization problem has been studied in [26] for the special case of a single UAV.
Despite many recent studies on UAV deployment and trajectory optimization, some of which
have been described above, there are many fundamental open problems that are yet to be
resolved. In particular, for static networks, there is no general analytical framework that can
provide the optimal UAV positions for a given number of UAVs and spatial user density.
Also, for the dynamic scenario, an analytical characterization of achievable performance gains
are largely missing, and most of the above work relies on numerical methods for optimizing
UAV trajectories and determining the resulting performance. Moreover, some of these trajectory
optimization algorithms, including [13], [15], [21], [24]–[26], work only for one UAV, or one
dimension [16]. Some, including [17]–[20], [22], [23], only consider UAV speed or instantaneous
movement/energy limitations, and thus, do not incorporate a constraint on the long-term cost
of mobility. Some other algorithms rely on methods such as simulated annealing [9] or genetic
algorithms [14], and do not offer convergence guarantees or local optimality.
Quantization theory of data compression and source coding [27] has proved to be a very

4

successful analytical tool in addressing many existing problems that involve geographical deployment of agents [28]; examples applications of the theory include the deployment of antenna
arrays [29], sensors [30], or general heterogeneous nodes [31]. The main contribution of this
paper is to show that many of the aforementioned open problems on UAV networks can as
well be formulated and ultimately resolved using a quantization theory approach. Our setup
consists of a density of GTs that are served by an arbitrary number of UAVs. Each GT employs
variable-power fixed-rate transmission to ensure outage-free reception at its closest UAV. In the
static case, our goal is to find the optimal UAV deployment that minimizes the average GT
transmission power, while in the dynamic case, we wish to minimize the time-averaged power
consumption subject to the total distance traveled by the UAVs. The specific main contributions
of this paper are then summarized as follows:
•

In the static case, and a uniform distribution of GTs on a line segment on the ground,
we determine the optimal deployment of UAVs and the resulting average GT power consumption. For a general one or two dimensional area on the ground and an arbitrary GT
distribution, we determine the optimal deployment and the corresponding performance in
the asymptotic regime of a large number of UAVs.

•

In the dynamic case, for any dimension and any time-varying GT densities, we analytically
characterize the optimal UAV deployments and the corresponding GT power consumptions
in the two extremal cases of no UAV movement and unlimited UAV movement. In the
special case of one dimension, our approach leads to an analytical formula for the total
UAV movement that guarantees the lowest possible average GT power consumption.

•

In order to address the case of moderate UAV movements, we introduce a trajectory
optimization algorithm that relies on time discretization, and alternating optimization over
each discretized time instance. The algorithm is a descent over the Lagrangian combination
of GT power consumption and UAV movement. Optimization at each time instance is carried
out through a generalization of Lloyd algorithm [32], [33] in vector quantization. Certain
sub-optimization problems that arise in this context are solved in closed form.

5

Our algorithmic approach is thus more aligned with the Voronoi-based coverage control
algorithms that were originally envisioned for mobile sensor networks [34]–[36]. These existing
studies, however, do not consider total movement constraints and are thus not applicable.
Part of this work will be presented in a conference [1]. Compared to [1], most aspects of
the trajectory optimization algorithm and the solutions to the accompanying sub-optimization
problems are new. The current paper also provides more connections to the existing literature
and more detailed numerical simulation results.
The rest of this paper is organized as follows: In Section II, we introduce the system model. We
analyze static deployment of UAVs in Section III. We analyze the extremal cases of the dynamic
deployment scenario in Section IV. In Section V, we introduce our trajectory optimization
algorithm to address moderate movement constraints. We provide numerical simulation results
in Section VI. Finally, in Section VII, we draw our main conclusions and discuss extensions to
variable-rate transmission. Some of the technical proofs are provided in the appendices.
II. S YSTEM M ODEL
We consider a network of several GTs at zero elevation and several UAVs at a fixed elevation
h > 0. Mathematically, we assume that the GTs are located on Rd , where d ∈ {1, 2}. While
typically one is interested in the case d = 2, i.e. when the GTs are in general positions on the
ground, the case d = 1 is also relevant: The GTs may be constrained to lie on a line on the
ground, e.g. as cars on a straight highway.
We distinguish between what we refer to as the static and the dynamic deployment scenarios.
In static deployment, we assume that the GTs are located on Rd according to a certain fixed
R
(time-invariant) density function f , where Rd f (q)dq = 1. In the more complicated dynamic
deployment scenario, we will allow the user density to vary over time.

A. Static Deployment
In order to formally describe the static deployment scenario, let x1 , . . . , xn ∈ Rd denote the
UAVs’ (projected) locations on the GT space. The squared Euclidean distance between a GT at

6

q and the ith UAV at xi is then given by kxi − qk2 + h2 . Fig. 1 provides an illustration for the
special case of n = d = 2.

Fig. 1: A network of two UAVs serving a GT.

We first consider fixed-rate variable-power transmission at GTs. The case of fixed-power
variable-rate transmission will be discussed later. Suppose that a GT at location q wishes to
communicate with rate ρ bits/s/Hz, and transmits with power P J/s. From now on, we omit the
units of all quantities for brevity. Due to the aerial nature of the communication system, we
assume that there is line of sight between the GTs and the UAVs, and the effects of multipath
fading is negligible. In such a scenario, the received signal power at a UAV at xi is given by
r

(kxi − qk2 + h2 )− 2 P , where r is the path loss exponent. Reliable communication between the
GT and the UAV is possible provided that the capacity of the (Gaussian) channel between the
r

GT and the UAV is at least ρ, or, mathematically if log2 (1 + (kxi − qk2 + h2 )− 2 P ) ≥ ρ. The
minimum transmission power of a GT at q that guarantees reliable data reception at a UAV at
xi is then

2ρ −1
(kxi
P

r

− qk2 + h2 ) 2 . The minimum transmission power that guarantees successful

data reception at at least one of the UAVs is therefore mini

2ρ −1
(kxi
P

r

− qk2 + h2 ) 2 . Averaging

out the user density, and setting ρ = P = 1 without loss of generality, the average transmission
power of GTs given UAV locations x , [x1 · · · xn ] and GT density f is
Z
r
P (x, f ) ,
min(kxi − qk2 + h2 ) 2 f (q)dq.
Rd

i

(1)

7

The static deployment problem is then to find the optimal UAV locations that minimize the
average GT power consumption. In other words, we wish to determine P ? (f ) , minx P (x, f ),
and the optimal deployments x? that achieve P (x? , f ) = P ? (f ).
B. Dynamic Deployment
In practice, the GT density may vary over time. For example, in daily urban communications,
the GT density over highways will be higher during rush hours, when compared to nighttime. In
order to model such scenarios, we let ft denote the GT density function at time t. We assume ft
is periodic over a time interval of length T , i.e. ft (q) = ft+T (q), ∀t, ∀q. For example, one may
set T = 24 hours for the urban communication scenario. We also assume that ft (q) is continuous
in both t and q. Thus, the GT density does not experience abrupt changes over space or time.
Let xi,t denote the location of UAV i at time t, and xt = [xt,1 · · · xt,n ] denote the vector of
UAV locations at time t. The power consumption of GTs at time t is P (xt , ft ). The average
power consumption over time can be expressed as
Z
1 T
Q,
P (xt , ft )dt.
T 0

(2)

We have omitted to indicate the dependency of Q on {(xt , ft ) : t ∈ [0, T ]} for brevity. The
time-averaged distance traversed by the ith UAV can be calculated to be the line integral
v
Z Tu
d
2
uX
1
∂xt,i,j
t
Mi ,
dt,
T 0
∂t
j=1

(3)

where xt,i,j represents the jth component of xt,i . In this case, the goal is to find the optimal
UAV trajectories that minimize the average GT power consumption Q subject to a constraint
Pn
i=1 Mi ≤ M on the total UAV movement, where M ≥ 0 is given.
III. O PTIMIZATION OF A S TATIC D EPLOYMENT
We begin with the simpler scenario of a static deployment and its optimization. Namely, we
study the minimization of (1) with respect to UAV locations x. We begin by considering the
degenerate case h = 0, in which case we can imagine that the network consists of unmanned
ground vehicles (UGVs) instead of UAVs. The analysis of such a UGV scenario will be very
useful for our analysis of the UAV case h > 0.

8

A. The UGV Case h = 0
For h = 0, the cost function in (1) becomes
Z
P (x, f ) =
min kxi − qkr f (q)dq, h = 0.
Rd

(4)

i

This expression is the well-known average rth power distortion of a quantizer whose reproduction
points are x1 , . . . , xn for a given source density f . Finding the exact minimizers of (4) and the
corresponding minimum distortions is possible only for a few special cases. In particular, if
f (q) = 1(q ∈ [0, 1]) is the one-dimensional uniform density, then the optimal reproduction points
1
are given by the uniform quantizer codebook xu = [ 2n

3
2n

···

2n−1
]
2n

with P (xu , f ) =

1
.
(1+r)(2n)r

For a general uniform density, we have the following result of Bennett [37] and Zador [38].
R
R
d+r
Given A ⊂ Rd , let m(A) , A kqkr dq/( A dq) d denote the normalized rth moment of A.
r

r

Proposition 1. Let f (q) = 1(q ∈ [0, 1]d ), h = 0. As n → ∞, we have P ? (f ) = κrd n− d +o(n− d ),
where κrd depends only on r and d. In particular, κr1 =

2−r
1+r

and κr2 are the normalized moments

of the origin-centered interval and the origin-centered regular hexagon, respectively.
This implies in particular that for two dimensions and a uniform distribution, the best arrangement of quantization points is asymptotically the regular hexagonal lattice.
Making the transition from uniform to non-uniform f can be accomplished using the idea of
point density functions. In detail, one assumes the existence of a function λ(q) such that the
R
cube [q, q + dq] of volume dq contains nλ(q)dq reproduction points with Rd λ(q)dq = 1. Since
f should be approximately uniform on [q, q +dq], the conditional average distortion on [q, q +dq]
r

r

is κrd (nλ(q))− d + o(n− d ) by Proposition 1. Averaging out the density, we obtain the formula
Z
r
r
− dr
e
f (q)λ− d (q)dq + o(n− d ).
(5)
P (λ) , κrd n
Rd

for the average distortion given λ. Using reverse Hölder’s inequality, we have
r
Pe(λ) ≥ κrd n− d kf k

where kf kα , (

R
Rd

r

d
d+r

+ o(n− d ),

(6)

1

(f (q))α dq) α is the α-norm of the density f . In (6), equality holds if
d

λ(q) = f d+r (q)/

d

R
Rd

f d+r (q 0 )dq 0 , ∀q

(7)

9

r

Therefore, the minimum distortion κrd n− d kf k

r

d
d+r

+ o(n− d ) is achieved by the point density

function in (7).

B. The UAV Case h > 0
We now consider the case h > 0. We begin with the simple case of a uniform one-dimensional
distribution. The proof of the following proposition can be found in Appendix A.
Proposition 2. Let f (q) = 1(q ∈ [0, 1]). A minimizer of (1) is the uniform quantizer codebook
xu . The corresponding minimum average power is
Z 1
2n
r
(u2 + h2 ) 2 du.
P (xu , f ) = 2n

(8)

0

For a general d and f , we observe that if x1 , . . . , xn is an optimal deployment, the set of
points q with the property that mini kq − xi k → 0 as n → ∞ has probability one.1 This amounts
to the intuitive observation that every GT should be allocated a closer UAV as the number of
available UAVs grows to infinity. As a result, we may use the Taylor series expansion


min kxi − qk2 + h2

 r2

i



= hr + 21 rhr−2 min kxi − qk2 + o min kxi − qk2
i

i

so that, substituting to (1), we have
Z
Z
r
r−2
2
1
P (x, f ) = h + 2 rh
min kxi − qk f (q)dq +
Rd

i



o min kxi − qk2 f (q)dq.
i

Rd

(9)

(10)

Using (6) and (7), we can then obtain the following theorem.
Theorem 1. As n → ∞, we have



?
P (f ) =

 hr +

r

κrd n− d kf k

r

d
d+r

rhr−2 κ2d − d2
n kf k d
2
d+2

+ o(n− d ), h = 0,
2

The optimal point density function is given by
 d
R
d
 f d+r (q)/ d f d+r
(q 0 )dq 0 , h = 0,
R
λ? (q; f ) ,
R
d
d
 f d+2
(q)/ Rd f d+2 (q 0 )dq 0 , h > 0.
1

(11)

+ o(n− d ), h > 0.

(12)

Otherwise, there is a constant a > 0 such that with some positive probability  > 0, one has mini kq − xi k > a infinitely

often. This implies P ? (f ) > a infinitely often, contradicting Proposition 1.

10

This provides a complete asymptotic characterization of the achievable GT power consumption
and the corresponding optimal UAV configuration.
IV. O PTIMIZATION OF A DYNAMIC D EPLOYMENT: E XTREMAL C ASES
We now consider the dynamic scenario, where the GT density varies periodically over time.
As discussed in Section II-B, the goal in this case is to minimize the time-averaged power
P
consumption Q in (2), subject to the constraint ni=1 Mi ≤ M on the total movement of UAVs.
Here, Mi denotes the total movement of the ith UAV, and has been defined in (3). Given M ≥ 0,
P
we use the notation Q? (M ) to denote the minimum of (2) subject to ni=1 Mi ≤ M . In this
section in particular, we consider the two extremal cases M = 0 and M → ∞. The remaining
moderate cases will be discussed in Section V.
A. No UAV movement: M = 0
The case M = 0 corresponds to a scenario where we do not allow any UAV movement.
Equivalently, the UAV locations are fixed over time as xt = x0 , ∀t for a collection x0 = [x01 · · · x0n ]
of UAV locations to be optimized. By (1) and (2), we have
Z Z
1 T
?
0
2
2 r2
Q (0) = min
min
(kx
−
qk
+
h
) ft (q)dqdt.
(13)
i
x0 T 0
Rd i
RT
R
Now, let f (q) , T1 0 ft (q)dt be the “time-averaged density.” Note that Rd f (q)dq = 1 so that
f is a valid density function. According to (1) and (13), we have Q? (0) = minx0 P (x0 , f ), and
optimizing over x0 leads to the following.
Proposition 3. We have Q? (0) = P ? (f ).
Note that Theorem 1 can be applied to provide an asymptotically tight expression for P ? (f )
(and thus Q? (0)).
Example 1. Let us consider a one-dimensional network d = 1, a period of length T = 2 with
path loss exponent r = 2. For a simpler exposition, we further consider an UGV network where
h = 0. Let the time-varying GT density be given by
ft (q) = (1 + 3|t|)(q − 2 + 2|t|)3|t| , q ∈ [2 − 2|t|, 3 − 2|t|], t ∈ [−1, 1].

(14)

11

This defines shifted power-law densities. For example for t = −1, we obtain the density f1 (q) =
4q 3 , q ∈ [0, 1], and for t = 0, we obtain f0 (q) = 1, q ∈ [2, 3]. The time-averaged density f
as well as its 13 -norm kf k 1 ≈ 6.08 can be found by numerical integration. By Proposition 3
3

and Theorem 1, it follows that Q? (0) ≈

6.08 −2
n
12

= 0.507n−2 . The optimal point (UAV) density

function is given by λ? (q, f ), as defined in (12).

B. Unlimited UAV movement: M → ∞
We now allow an unlimited amount of UAV movement so as to obtain the minimum possible
time-averaged GT power consumption. For this purpose, at each time t, we use the UAV locations
that provide the minimum “instantaneous” GT power consumption. This results in the timeaveraged power
1
Q (∞) =
T
?

Z

T

P ? (ft )dt.

(15)

0

We recall that Theorem 1 provides an asymptotic expression for the integrand P ? (ft ). This can
be substituted to (15) for an asymptotically tight characterization of Q? (∞).
We now argue that (15) is, in fact, achievable with a finite amount of total movement as well.
In other words, there is a constant M > 0 such that Q? (M ) = Q? (∞) for every M ≥ M .
The idea is to observe that the GT density ft at time t is not “vastly different” than the GT
density ft+dt at time t + dt. This stems from our practical assumption in Section II-B that the
spatiotemporal density ft (q) is continuous in both space and time. As a result, we expect the
optimal location for each UAV to be a well-behaved continuous function of time, resulting in a
finite amount of total UAV movement.
We utilize high-resolution quantization theory to estimate M . The key is to recover the location
of each UAV at any given point t in time through the optimal quantizer point density function
at time t. Namely, let x?t , [x?t,1 · · · x?t,n ] denote the optimal UAV locations at time t for density
ft . We first consider the case of one dimension d = 1. Without loss of generality, suppose
x?t,1 ≤ · · · ≤ x?t,n . Given x ∈ [0, 1], let Λ?inv (x; ft ) be the unique real number that satisfies
Z Λ?inv (x;ft )
λ? (q; ft )dq = x,
(16)
0

12

where λ? (q; ft ) is the optimal point density function for ft , as defined in (12) of Theorem 1.
Ru
Note that Λ?inv (x; ft ) is the inverse of the cumulative distribution function u → 0 λ? (q; ft )dq.
Our idea is to approximate the optimal UAV locations via


2i − 1
?
?
et,i , Λinv
xt,i ' x
; ft , i = 1, . . . , n.
2n

(17)

Note that if U is a random variable that is uniformly distributed on [0, 1], then, according to
the inverse transform sampling method, the random variable Λ?inv (U ; ft ) is distributed according
to the density function λ? (q, ft ). The transformation in (17) can thus be considered to be a
“deterministic version” of inverse transform sampling, where the uniform random variable U is
replaced with the uniform quantizer with reproduction points

2i−1
,
2n

i = 1, . . . , n. The resulting

estimates x
et,1 , . . . , x
et,n are consistent with the density function λ? (q; ft ) in the sense that for
every q and  > 0, the fraction n1 |{i : x
et,i ∈ (q, q + )}| of UAVs that are located on (q, q + )
converges to λ? (q; ft ) as n → ∞.
Substituting (17) to (3), we obtain the following result.
Theorem 2. Let d = 1. As n → ∞, the minimum possible average power consumption of
RT
Q? (∞) = T1 0 P ? (ft ) is achievable with a total movement of

Z
;
f
1 T ∂Λ?inv 2i−1
t
2n
Mi ,
dt
(18)
T 0
∂t
P
for the ith UAV. Correspondingly, M = ni=1 M i .
Example 2. We continue the setup in Example 1. We have
!3
Z
Z 3−2|t|
|t|
kft k 1 = (1 + 3|t|)
(q − 2 + 2|t|) dq
= (1 + 3|t|)
3

2−2|t|

0

1
|t|

q dq

3
=

1 + 3|t|
. (19)
(1 + |t|)3

This yields
1
Q (∞) =
2
?

Z

1

1


1
kft k 1 dt + o
3
n2
−1
 
 
Z 1
1
1 + 3|t|
1
1
1
=
dt + o
=
+o
.
2
3
2
2
24n −1 (1 + |t|)
n
16n
n2

1
P (ft )dt =
24n2
−1
?

Z



(20)
(21)

13

The first three equalities follow from (15), (11), and (19), respectively. In order to estimate M ,
we use the formula (12) to first calculate λ? (q, ft ) = (1 + |t|)(q − 2 + 2|t|)|t| . In the light of (16),
we then solve for θ in the integral equality
Z θ
(1 + |t|)(q − 2 + 2|t|)|t| dq = x

(22)

0

to obtain the inverse cumulative distribution function
1

Λ?inv (x, ft ) = θ = 2 − 2|t| + x 1+|t| , x ∈ [0, 1], t ∈ [−1, 1].

(23)

According to (17), we can then obtain



 1
2i − 1
2i − 1 1+|t|
?
x
et,i = Λinv
; ft = 2 − 2|t| +
, i = 1, . . . , n.
2n
2n

(24)

Note that, for a fixed index i, the function t 7→ x
et,i is symmetric around the origin and decreases
on [0, 1]. Theorem 2 combined with the fundamental theorem of calculus then yields

1
Z
1 1 ∂e
2i − 1 2
xt,i
2i − 1
Mi =
.
dt = x
e0,i − x
e1,i = 2 +
−
2 −1 ∂t
2n
2n
Thus, the power consumption of Q? (∞) is achievable with a total UAV movement of

1 !
n
n
X
X
2i − 1
2i − 1 2
M=
M i = 2n +
−
,
2n
2n
i=1
i=1

(25)

(26)

and the optimal UAV trajectories are given by x
et,i in (24). Note that, as n → ∞, we have
Z 1
√
M
11
→2+
(x − x)dx = .
(27)
n
6
0
Therefore, for a per-UAV movement of

11
,
6

a GT power consumption of roughly

1
16n2

is achievable.

On the other hand, Example 1 shows that without any UAV movement, a GT power consumption
of roughly

0.507
n2

is achievable. For the particular scenario in Examples 1 and 2, allowing mobility

of access points thus potentially yields an 8-fold reduction in the GT power consumption.
The arguments that we have used to obtain Theorem 2 are not immediately applicable to
the case of two dimensions. The main difficulty is to find a simple analogue of (17) that can
faithfully extract the optimal UAV locations from the optimal UAV density functions. We leave a
resolution of this problem as future work. Nevertheless, M and Q? (M ) can still be numerically
approximated for two dimensional densities as we show in Section VI.

14

V. O PTIMIZATION OF A DYNAMIC D EPLOYMENT: M ODERATE D ISTANCES
We recall that our goal in the dynamic deployment scenario is to find the minimum average
GT power consumption Q? (M ) subject to the total movement constraint M on the UAVs. In the
previous section, we have analytically characterized the achievable performance in the extremal
cases of no UAV movement M = 0 and unlimited UAV movement M = ∞. In particular,
we have shown that there exists a sufficient amount of total movement M such that Q? (M ) =
Q? (∞). We now consider the achievable performance between the two extremal cases. In other
words, we consider the moderate distances regime 0 < M < M .
A precise analytical characterization of the achievable performance appears to be very challenging for the case 0 < M < M . We thus mainly follow a numerical approach. Specifically,
we introduce a Lagrangian-based descent algorithm for trajectory optimization. We first present
the general strategy and outline of the algorithm.

A. Outline of an Algorithm for Trajectory Optimization
Our general strategy for trajectory optimization is to follow the classical Lagrangian approach
of constrained optimization. Namely, we combine the power consumption (objective) function
P
Q in (2) and the movement (constraint) function ni=1 Mi through the Lagrangian
v


Z T
n uX
n
d
2
X
X
u
1
∂xt,i,j 
t
P (xt , ft ) + `
dt.
(28)
Q+`
Mi =
T 0
∂t
i=1
i=1
j=1
Minimizing the Lagrangian for different values of the Lagrange multiplier ` > 0 enables travel
over the (M, Q? (M )) tradeoff curve: For example, a small ` does not penalize the total amount
of movement as much as a larger ` does. It thus results in a lower power consumption compared
to the case of a larger `, albeit at the expense of more movement. The formulation in (28) thus
resembles the Lagrangian formulation of the entropy-constrained quantizer design problem [39].
Minimizing (28) requires optimization over the uncountably infinitely many variables xt,i , t ∈
[0, T ], i ∈ {1, . . . , n}, and is thus infeasible. The first step towards a feasible optimization is

15

:k∈
to discretize the continuous time interval [0, T ] to the set of discrete time instances { kT
K
{0, . . . , K − 1}}, where K ≥ 2 is a natural number. This results in the discrete-time Lagrangian
K−1
K−1 n
1 X
` XX
ˆ
L,
kyk,i − yk−1,i k,
P (yk , fk ) +
K k=0
K k=0 i=1

where the discrete time k corresponds to the continuous time

kT
,
K

(29)

and the optimization is over

yk , x kT = [yk,i · · · yk,n ] with density fˆk , f kT . Also, for a simple notation, we have omitted
K

K

to indicate that all k-dependent indices are evaluated modulo K. For example, for k = 0, the
discrete time index k − 1 = −1 is the same as the discrete time index −1 mod K = K − 1.
It can be shown that, under some technical conditions on xt,i , i = 1, . . . , n and ft , such as
continuity in t, the discrete time Lagrangian converges to the continuous time Lagrangian as the
number of time steps K grows to infinity. We thus expect the minimizers of (29) and (28) to
coincide asymptotically as K → ∞. Still, the direct minimization of (29) is a dnK dimensional
optimization problem. In order to further reduce the dimensionality, we define
n
n
1
` X
` X
ˆ
Lk , P (yk , fk ) +
kyk,i − yk−1,i k +
kyk,i − yk+1,i k, k = 1, . . . , K,
K
K i=1
K i=1

(30)

and note that L depends on yk only through Lk . The quantity Lk can be considered to be the
Lagrangian cost at time instance k. Our algorithm is then to perform alternating optimization
over the discrete time instances. In detail, we begin with an initial (for example, random) guess
on the trajectories y0 , . . . , yK−1 . For the infinite sequence of time indices k = 0, 1, . . . , K −
1, 0, 1, . . . , K − 1, . . . , we minimize Lk over yk , while keeping all yi , i 6= k fixed (The specific
manner in which we perform the minimization will be discussed later on). Since each step
minimizes Lk over yk for some k ∈ {0, . . . , K − 1}, and the dependence of L on yk is only
through Lk , the process guarantees a non-increasing L. It follows that the algorithm converges in
a cost function sense. In fact, in our numerical experiments, we have observed that the algorithm
also provides convergent trajectories as well. A formal proof of this observation will remain as
an interesting direction for future research.
The pseudocode of our trajectory optimization algorithm is as shown in Algorithm 1. We call
one pass over all discrete time instances as one epoch of optimization. The algorithm terminates

16

Algorithm 1 Trajectory Optimization
1:

Initialize y0 , . . . , yK−1 . Set maxEpochs.

2:

for epochs = 1 to maxEpochs do

3:
4:

Update the UAV deployments as yk ← arg minyk Lk , k = 0, . . . , K − 1.
end for

after a certain number of epochs that is to be chosen depending on the input parameters. Different
termination criteria (such as the convergence of trajectories or the cost L) can also be considered.
Obviously, due to the non-convex non-linear nature of the trajectory optimization problem, the
resulting trajectory may not necessarily be the globally-optimal solution.

B. Minimizing the Lagrangian Cost at a Given Time Instance
We now seek a computationally-efficient solution for the dn-dimensional optimization problem
of minimizing the Lagrangian cost Lk in (30). In other words, we study the optimization problems
in Line 3 of Algorithm 1. We follow the same decomposition strategy as in Section V-A. This
will lead us to a variant of the Lloyd algorithm of vector quantization [32], [33]. First, for the
term P (yk , fˆk ) in (30), we recall from (1) that
Z
r
ˆ
P (yk , fk ) =
min(kyk,i − qk2 + h2 ) 2 fˆk (q)dq
=

Rd i
n
XZ
i=1

r
(kyk,i − qk2 + h2 ) 2 fˆk (q)dq,

(31)
(32)

Vk,i

where Vk,i , {q : kyk,i − qk ≤ kyk,j − qk, ∀j ∈ {1, . . . , n}} is the Voronoi cell of the ith UAV
at time k. Given that the Voronoi cells Vk,i , i = 1, . . . , n are kept fixed, it follows that for any
given UAV index i ∈ {1, . . . , n}, the expression (30) depends on yk,i only through the quantity
Z
r
`
`
1
(kyk,i − qk2 + h2 ) 2 fˆk (q)dq + kyk,i − yk−1,i k + kyk,i − yk+1,i k.
Lk,i ,
(33)
K Vk,i
K
K
The quantity Lk,i can be interpreted as the Lagrangian cost of UAV i at discrete time instance
k. In general, given that Vk,i , i = 1, . . . , n are kept fixed, Lk,i is a convex function of yk,i and

17

thus be effectively minimized using any convex optimization method, or gradient descent. For
reference, the gradient of Lk,i with respect to yk,i can be calculated to be
Z
r
∂Lk,i
r
=
(kyk,i − qk2 + h2 ) 2 −1 (yk,i − q)fˆk (q)dq+
∂yk,i
K Vk,i
` yk,i − yk+1,i
` yk,i − yk−1,i
+
. (34)
K kyk,i − yk−1,i k K kyk,i − yk+1,i k
As we shall soon discuss, further simplifications or even closed-form solutions to the problem of
minimizing Lk,i are available in certain special cases. Regardless, once each Lk,i , i = 1, . . . , n are
minimized (while keeping Vk,i , i = 1, . . . , n fixed), the new Voronoi regions Vk,i , i = 1, . . . , n
will be calculated according to the new yk,i , i = 1, . . . , n. Algorithm 2 summarizes this process of
minimizing Lk . The algorithm proceeds in an iterative manner until a certain maximum number
of iterations is reached. Since each optimization we have described results in a non-increasing
Lk , Algorithm 2 converges in a cost function sense.
Algorithm 2 Minimizing Lk
1:

Initialize UAV locations yk = [yk,1 · · · yk,n ]. Set maxIterations.

2:

for iterations = 1 to maxIterations do

3:

Calculate the Voronoi regions Vk,i , i = 1, . . . , n.

4:

Update the UAV locations as yk,i ← arg minyk,i Lk,i , i = 1, . . . , n.

5:

end for

C. Minimizing the Lagrangian Cost of a UAV at a Given Time Instance
We now consider the minimization of Lk,i for a given UAV index k and time instance i. This
problem appears in Line 4 of Algorithm 2. As we have mentioned in Section V-B, in general,
Lk,i in (33) can be minimized using gradient descent. Here, we point out that the minimization
becomes considerably simpler for the special case r = 2 of the path loss exponent. In fact, we
will also provide a closed-form solution for r = 2 and one-dimensional networks d = 1.

Z

Let us first note that for any set A and vector x, we have
Z

2
kx − qk f (q)dq =
kxk2 − 2xT q + kqk2 f (q)dq

A

A

(35)

18

= kxk

2

Z


f (q)dq − 2x

A

Z
=

Z



Z

qf (q)dq +
A


f (q)dq

A

T

kqk2 f (q)dq

(36)

A

R
R
2 Z
qf
(q)dq
k
qf (q)dqk2
2
A
A
R
R
. (37)
x−
+ kqk f (q)dq−
f (q)dq
f (q)dq
A
A
A

Note that the last two terms do not depend on x. When r = 2, we use the identity in (37) to
rewrite the integral in (33). Then, by removing the terms that do not depend on yk,i , it follows
that the minimization of (33) over yk,i is equivalent to minimizing
φ(x) , kx − uk + kx − vk + ckx − wk2
over all x, where the constant vectors u, v, w, and the scalar c are given by
R
Z
q fˆk (q)dq
1
Vk,i
u , yk−1,i ,
v , yk+1,i ,
w, R
,
c,
fˆk (q)dq.
ˆk (q)dq
` Vk,i
f
Vk,i

(38)

(39)

Therefore, when we wish to minimize (33) (by using gradient descent for example), we can
avoid integration over the generally complicated region Vk,i by instead considering the equivalent
problem of minimizing (38). Let us further note that the domain/search space of minimization of
(38) is the entire Rd . We can also greatly reduce the size of this search space. For this purpose,
we need the following lemma, whose proof can be found in Appendix B.
Lemma 1. Let T ⊂ Rd be a triangle with vertices u, v, w, including its boundary and interior.
For any x ∈ Rd , there exists y ∈ T such that ky − ak ≤ kx − ak for every vertex a of T .
We now have the following proposition.
Proposition 4. A minimizer x? of (38) lies on the triangle T with vertices u, v, w.
Proof. Suppose x? ∈
/ T . By Lemma 1, we can find y ∈ T such that ky − ak ≤ kx? − ak for
every vertex a of T . It follows that y is also a minimizer of (38).
Therefore, without loss of optimality, we may minimize (38) over all x of the form x =
w + αx0 + βx00 , where α, β ≥ 0, α + β ≤ 1, and x0 = u − w, x00 = v − w are triangle edge
vectors. Hence, the minimization of (38), which should take place over the entire Rd , can be
transformed to a convex optimization over the (two-dimensional) triangle α, β ≥ 0, α + β ≤ 1.

19

In the special case of one dimension, a minimizer of (38) can be found in closed form. This
is shown by the following proposition, whose proof can be found in Appendix C.
Proposition 5. Let d = 1, and x? = arg minx∈Rd φ(x). For a simpler notation, we define the
intermediate variables
0



0

u , min{u, v},

v , max{u, v},

α , min

u+v 1
w−
,
2
c


.

(40)

We have

x? =








w, w ∈ [u0 , v 0 ],

max {v 0 , w − α} , w > v 0 ,




 min {u0 , w + α} , w < u0 .

(41)

As a result, for d = 1 and r = 2, the entire trajectory optimization algorithm can be
implemented with very low computational complexity.
VI. N UMERICAL R ESULTS
In this section, we provide numerical simulations that verify our analytical results. We first
consider the scenario in Examples 1 and 2. For reader’s convenience, we recall that given n UAVs
and no UAV movement, our analysis suggests that the best possible GT power consumption in
this scenario is given by
6.08 1
Q (0) ≈
+o
12 n2
?



1
n2



0.507
+o
=
n2



1
n2


.

(42)

On the other hand, with an unlimited UAV movement, the best GT power consumption is
 
1
1
?
Q (∞) =
+o
.
(43)
2
16n
n2
In fact, the performance in (43) is achievable with a per-UAV movement of

1 !
n
M
11
1 X 2i − 1
2i − 1 2
=2+
−
→
as n → ∞.
n
n i=1
2n
2n
6

(44)

For the same scenario, in Fig. 2, we show the simulated tradeoff between the per-UAV movement and GT power consumption for different number of UAVs. The horizontal axis represents
the distance traveled per UAV, and the vertical axis represents the GT power consumption in

20

logarithmic scale. Each marked data point is obtained using the algorithm in Section V with a
time discretization of K = 20 and different values of the Lagrange multiplier `. The continuoustime trajectory is reconstructed from the discrete-time trajectory using linear interpolation.
1 UAV
2 UAVs
4 UAVs
8 UAVs
16 UAVs
32 UAVs

GT power consumption

100

10-1

10-2

10-3

10-4
0

0.25

0.5

0.75

1

1.25

1.5

1.75

2

Distance traveled per UAV

Fig. 2: GT power consumptions for different per-UAV movements in a one-dimensional network.

We can observe that, doubling the number of UAVs roughly quarters the average GT power
consumption for the same amount of distance traveled per UAV. The O( n12 ) decay of the analytical
formulae in (42) and (43) justify this observation for the two special cases of zero and unlimited
UAV movement, respectively. The same decay rate can be observed if one instead considers a
total movement constraint instead of a per-UAV movement constraint.
In Fig. 3, we show the average GT power consumption for different number of UAVs and the
extremal scenarios of zero and unlimited UAV movements. The logarithmically-scaled horizontal
and the vertical axes represent the number of UAVs and the GT power consumptions, respectively.
Note that, the simulation curves for zero and unlimited UAV movements respectively correspond
to the vertical coordinates of the leftmost and the rightmost data points in Fig. 2. We can observe
that the analytical results in (42) and (43) match almost perfectly with the simulations. Due to
its asymptotic nature, the analysis is more accurate when the number of UAVs is large.
In Fig. 4, we show the per-UAV traveled distances for the scenario of unlimited UAV move-

21

100

No UAV movement, simulation
No UAV movement, analysis
Unlimited UAV movement, simulation
Unlimited UAV movement, analysis

GT power consumption

10-1

10-2

10-3

10-4
1

2

4

8

16

32

Number of UAVs

Fig. 3: GT power consumptions in extremal cases for a one-dimensional network.

Distance traveled per UAV

1.85

1.8

1.75

Simulation
Analysis
1.7
1

2

4

8

16

32

Number of UAVs

Fig. 4: Distance per UAV for different number of UAVs with unlimited movement.

ment. The simulation curve corresponds to the horizontal coordinates of rightmost data points
in Fig. 2, and the analysis curve corresponds to the formula (44). Noting that the values
in the vertical axis of the figure are already very close, we can conclude that the analysis
matches simulation very well. Example 2 also provides the optimal trajectories for the unlimited
movement scenario in (24). In Fig. 5, we compare these analytical trajectories with the trajectories

22

that are obtained numerically for the special case of 8 UAVs. The horizontal and the vertical axes
represent the time, and the UAV locations respectively. Each curve represents the trajectory of
one UAV. We have normalized both the analytical and the simulation trajectories by subtracting
the time-varying drift 2 − 2|t| of the density function. We can observe that, for any UAV index,
the analysis matches the simulation very well.
1
0.9

Normalized UAV location

0.8
0.7
0.6
0.5
0.4
0.3
0.2
Simulation
Analysis

0.1
0
-1

-0.5

0

0.5

1

Time

Fig. 5: Trajectories of 8 UAVs in a one-dimensional network.
As an example of two-dimensional (d = 2) dynamic deployment, let ft be the density function
of the random variable (3 + 2 sin 2πt)N + 10[sin 2πt cos 2πt], where N is a Gaussian random
vector with identity covariance matrix. Hence, ft is Gaussian at any t and its mean and variance
varies periodically over time with T = 1. We consider a path loss exponent of r = 3, and UAV
height h = 10. The normalized second moment of the origin-centered hexagon can be calculated
to be κ22 =

5√
.
18 3

By Theorems 1 and 2, the asymptotic GT power consumptions are then
25 kf k 21
Q (0) = 1000 + √
+o
6 3 n
?

 
1
,
n

(45)

 
1
+o
,
n

(46)

and
25
Q? (∞) = 1000 + √
6 3

R1
0

kft k 1 dt
2

n

23

for the cases of zero and unlimited UAV movement, respectively. In (45), the half-norm kf k 1
2

can be calculated through numerical integration to be roughly 908.16. For the case of unlimited
R1
movement in (46), after some calculus, we can obtain 0 kft k 1 dt = 88π in closed form.
2

As the asymptotic expressions (45) and (46) also show, the choice of parameters r = 3
and h = 10 imply that the GT power consumption is at least hr = 1000 regardless of the
constraints on the total UAV movement. For a clear illustration of results, we thus normalize the
GT transmission power by subtracting 1000 from the true GT transmission power.
In Fig. 6, we show the tradeoff between the per-UAV movement and the normalized GT power
consumption for different number of UAVs. Unlike the case of the one-dimensional network
shown earlier, for a fixed per-UAV movement, doubling the number of UAVs roughly only halves
(instead of quartering) the normalized GT power consumption. The asymptotic expression in (45)
formally verifies this observation for the special case of zero movement.
1 UAV
2 UAVs
4 UAVs
8 UAVs
16 UAVs
32 UAVs

Normalized GT power consumption

3000

1000

400
200
100
60
40
20
0

10

20

30

40

50

60

65

Distance traveled per UAV

Fig. 6: GT power consumptions for different per-UAV movements in a two-dimensional network.

In Fig. 7, we show the average GT power consumption for different number of UAVs in
the zero and unlimited UAV movement scenarios. We can observe that the analytical results
in (45) and (46) match very well with the simulations. Even though the analysis will provide
an asymptotically tight approximation on the simulation results, the amount of mismatch for a

24

moderate number of UAVs is more pronounced compared to the case of the one-dimensional
network. The reason is the lesser amount of UAVs per dimension. One encounters the same

Normalized GT power consumption

phenomenon in the performance analysis of general vector quantizers.

103

102

No UAV movement, simulation
No UAV movement, analysis
Unlimited UAV movement, simulation
Unlimited UAV movement, analysis
101

1

2

4

8

16

32

Number of UAVs

Fig. 7: GT power consumptions in extremal cases for a two-dimensional network.

15

15

15

10

10

10

5

5

5

0

0

0

-5

-5

-5

-10

-10

-10

-15
-15

-10

-5

0

5

10

(a) No UAV movement

15

-15
20 -15

-10

-5

0

5

10

15

(b) Moderate UAV movement

-15
20 -15

-10

-5

0

5

10

15

20

(c) Unlimited UAV movement

Fig. 8: Sample trajectories with 4 UAVs.

Finally, in Fig. 8, we show the optimized UAV trajectories for the three different scenarios of
zero, moderate, and unlimited UAV movements. The moderate movement scenario is designed

25

with a Lagrange multiplier of ` =

3
,
2

and achieves the data point with a per-UAV traveled

distance of approximately 21 in Fig. 7. The t = 0 positions of each trajectory are marked with
a circle. Each point on the trajectory corresponds to one discrete time instance that is optimized
via the trajectory optimization algorithm. All UAVs travel “clockwise.”
VII. C ONCLUSIONS AND E XTENSIONS
We have studied the optimal deployment and relocation of UAV networks. We have first
considered the case of variable ground terminal (GT) transmission power with fixed data rate. For
static networks without any GT density variations, we have found the asymptotically optimal UAV
locations that minimize the average GT power consumption. We have also provided analytical
and numerical methods for dynamic UAV deployment where the GT density varies over time.
In particular, we have found the asymptotically optimal UAV trajectories for one-dimensional
networks and an unlimited UAV movement. We have also introduced a trajectory optimization
algorithm for finding good trajectories for moderate UAV movement constraints.
Last but not least, let us also discuss the case of variable-rate fixed-power systems. In this case,
each GT transmits with a fixed power P , resulting in the achievable average rate (in nats/sec/Hz)


Z
P
log 1 +
R(x, f ) ,
f (q)dq,
(47)
r
(mini kxi − qk2 + h2 ) 2
Rd
as the variable-rate analogue of (1). For a large number of UAVs, a Taylor expansion yields

 1
Z
Z


rP/h2
P
2
2
2
R(x, f ) = log 1+ r −
min
kx
−
qk
f
(q)dq+
o
min
kx
−qk
f (q)dq. (48)
i
i
i
h
P + hr Rd i
Rd
This final expression is in the same form as (10); the only differences are in the constants. All
of our asymptotic results thus extend to variable-rate systems in a straightforward manner.
ACKNOWLEDGEMENTS
The authors would like to thank Raheleh Khodabakhsh and Nitin Surya for their invaluable
feedback on an earlier version [1] of this paper.

26

A PPENDIX A
P ROOF OF P ROPOSITION 2
First, note that if g is monotonically increasing, A ⊂ R, and x ∈ R, we have
R
B

R
A

g(kx−qk)dq ≥

g(kqk)dq, where B is the origin-centered interval with the same measure as A. In particular,
r

for g(u) = (u2 + h2 ) 2 , we obtain
r

R
A

(kx − qk2 + h2 ) 2 dq ≥ h(µ(A)),

(49)

where
Z
h(ν) ,

1
ν
2

2

Z

r
2

2

1
ν
2

(u + h ) du = 2
− 21 ν

r

(u2 + h2 ) 2 du,

(50)

0

and µ(A) is the Lebesgue measure of A. By differentiation, it can be shown that h(ν) is a
concave function of ν. Now, let Vi , {q : kq − xi k ≤ kq − xj k, ∀j}, i = 1, . . . , n denote the
Voronoi cells that are generated by x1 , . . . , xn . We have
P (x, f ) =

n Z
X
i=1

r

(kxi − qk2 + h2 ) 2 dq ≥

Vi

n
X

h(µ(Vi ))

i=1

≥ nh

1
n

n
X
i=1

!
µ(Vi )

 
Z 1
2n
r
1
= nh
= 2n
(u2 + h2 ) 2 du. (51)
n
0

The first and the second inequalities follow from (49) and the concavity of h(·), respectively. It
can easily be verified that the last expression equals P (xu , f ). This concludes the proof.
A PPENDIX B
P ROOF OF L EMMA 1
Let “y  x” be the shorthand notation for conditions ky − uk ≤ kx − uk, ky − vk ≤ kx − vk,
and ky − wk ≤ kx − wk. If x ∈ T , we set y = x, and the proof is complete. Otherwise, let
x0 be the projection of x on the two-dimensional subspace that contains T . We have x0  x
by the Pythagorean inequality. If x0 ∈ T , the lemma then follows with y = x0 . Otherwise, by
1
appropriate translations of vectors u, v, w, x0 , we may assume that u = [ 00 ], v = [ v01 ], w = [ w
w2 ],

x01
and x0 = [ xx01
02 ], where v1 , x01 , x02 ≥ 0, w2 ≤ 0, and w1 ∈ R. Now, let x1 = [ 0 ]. The

geometry so far is illustrated in Fig. 9. It is easily verified that kx1 − uk ≤ kx0 − uk and

27

x0
u

x1

v
w

Fig. 9: The first case for the proof of Lemma 1.

◦
kx1 − vk ≤ kx0 − vk. Also, since the angle x\
0 x1 w is at least 90 , we have kx1 − wk ≤ kx0 − wk,

and therefore, x1  x0 . If x1 ∈ T , the lemma then holds for y = x1 . Otherwise, we consider
the following three cases: The first case w1 ≤ v1 is the same scenario as illustrated in Fig. 9.
In this case, we have v  x1 , and since v ∈ T obviously, the proof is complete with y = v.
The second case v1 ≤ w1 ≤ x01 is illustrated in Fig. 10. We let x2 = [ w01 ], and x3 to be the
projection of x2 on the edge vw. The relation x2  x1 obviously holds. The relation x3  x2

x0
u

v

x2

x3

x1

w
Fig. 10: The second case for the proof of Lemma 1.

follows from the same arguments that we have used to prove x1  x0 in Fig. 9. Since x3 ∈ T ,
the lemma follows with y = x3 . Finally, for the third case w1 ≥ x01 , let x4 to be the projection
of x1 on the edge vw. The proof of the relation x4  x1 similarly follows the proof of x1  x0
in Fig. 9. The lemma then holds for y = x4 . This concludes the proof.

28

A PPENDIX C
P ROOF OF P ROPOSITION 5
Let φ1 (x) = |x − u| + |x − v| and φ2 (x) = c|x − w|2 . Without loss of generality, let u ≤ v.
We have φ1 (x) ≥ v − u with equality if and only if x ∈ [u, v], and φ2 (x) ≥ 0 with equality if
and only if x = w. Therefore, φ(x) ≥ v − u with equality if and only if x = w and x ∈ [u, v],
or equivalently, if x = w and w ∈ [u, v]. This proves the first case in (41).
Suppose w > v. We first show that x? ∈ [v, w]. We have x? ∈ [u, w] by Lemma 1. Moreover,
for any x ∈ [u, v], we have φ(x) = v − u + c|x − w|2 ≥ v − u + c|v − w|2 with equality if and
only if x = v. Hence, x? ∈ [u, v] implies x? = v. Combining with x? ∈ [u, w] yields x? ∈ [v, w].
Now, let ξ(x) = |2x − u − v| + c|x − w|2 . We have ξ(x) ≤ φ(x) for all x ∈ R. Equality
holds if and only if x ≤ u or x ≥ v. Let y ? = arg minx∈R ξ(x) denote the global minimizer of
ξ. According to [40], we have
y ? = (w − α) ∈ [u, w].

(52)

If further y ? ∈ [v, w], we have
y ? = arg min ξ(x) = arg min φ(x)
x∈[v,w]

x∈[v,w]

= arg min φ(x) = x? .
x∈R

(53)
(54)

Otherwise, if y ? ≤ v, first note that ξ is increasing on [v, ∞) as ξ is convex. It follows that φ
is increasing on [v, ∞). Since x? ∈ [v, w] as already shown, φ attains its minimum at x? = v.
Hence, we have x? = max{v, y ? } = max {v 0 , w − α} in general, and this proves the second
case in (41). The final case in (41) follows from the same arguments.
R EFERENCES
[1] E. Koyuncu, R. Khodabakhsh, N. Surya, and H. Seferoglu, “Deployment and trajectory optimization for UAVs: A
quantization theory approach,” IEEE Wireless Commun. Networking Conf., Apr. 2018.
[2] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial vehicles: Opportunities and challenges,”
IEEE Commun. Mag., vol. 54, no. 5, pp. 36–42, May 2016.
[3] I. Bor-Yaliniz and H. Yanikomeroglu, “The new frontier in RAN heterogeneity: Multi-tier drone-cells,” IEEE Commun.
Mag., vol. 54, no. 11, pp. 48–55, Nov. 2016.

29

[4] M. Mozaffari, W. Saad, M. Bennis, Y.-H. Nam, and M. Debbah, “A tutorial on UAVs for wireless networks: Applications,
challenges, and open problems,” Mar. 2018. [Online] Available: https://arxiv.org/pdf/1803.00680.pdf
[5] R. I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Efficient 3-D placement of an aerial base station in next generation
cellular networks,” IEEE Intl. Conf. Commun., May 2016.
[6] E. Kalantari, H. Yanikomeroglu, and A. Yongacoglu, “On the number and 3D placement of drone base stations in wireless
cellular networks,” IEEE Veh. Tech. Conf., Sept. 2016.
[7] J. Lyu, Y. Zeng, R. Zhang, and T. J. Lim, “Placement optimization of UAV-mounted mobile base stations,” IEEE Commun.
Lett., vol. 21, no. 3, pp. 604–607, Mar. 2017.
[8] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Wireless communication using unmanned aerial vehicles (UAVs):
Optimal transport theory for hover time minimization,” IEEE Trans. Wireless Commun., vol. 16, no. 12, pp. 8052–8066,
Sept. 2017.
[9] S. Rohde, M. Putzke, and C. Wietfeld, “Ad hoc self-healing of OFDMA networks using UAV-based relays,” Ad Hoc Nets.,
vol. 11, no. 7, Sept. 2013.
[10] E.

Koyuncu,

“Power-efficient

deployment

of

UAVs

as

relays,”

Mar.

2018.

[Online]

Available:

https://arxiv.org/abs/1803.04315
[11] M. M. Azari, Y. Murillo, O. Amin, F. Rosas, M.-S. Alouini, and S. Pollin, “Coverage maximization for a poisson field of
drone cells,” IEEE Packet, Indoor and Mob. Radio Commun. Conf., Oct. 2017.
[12] J.-S. Marier, C.-A. Rabbath, and N. Léchevin, “Health-aware coverage control with application to a team of small UAVs,”
IEEE Trans. Control Sys. Tech., vol. 21, no. 5, pp. 1719–1730, Sept. 2013.
[13] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” IEEE Trans. Wireless Commun.,
vol. 16, no. 6, pp. 3747–3760, June 2017.
[14] K. Anazawa, P. Li, T. Miyazaki, and S. Guo, “Trajectory and data planning for mobile relay to enable efficient Internet
access after disasters,” IEEE Global Commun. Conf., Dec. 2015.
[15] F. Jiang and A. L. Swindlehurst, “Optimization of UAV heading for the ground-to-air uplink,” IEEE J. Select. Areas
Commun., vol. 30, no. 5, pp. 993–1005, June 2012.
[16] J. Gong, T.-H. Chang, C. Shen, and X. Chen, “Aviation time minimization of UAV for data collection over wireless sensor
networks,” ArXiV preprint, Jan. 2018. [Online] Available: https://arxiv.org/abs/1801.02799
[17] H. Wang, G. Ren, J. Chen, G. Ding, and Y. Yang, “Unmanned aerial vehicle-aided communications: Joint transmit power
and trajectory optimization,” to appear in IEEE Wireless Commun. Lett., Jan. 2018.
[18] L. Liu, S. Zhang, and R. Zhang, “CoMP in the sky: UAV placement and movement optimization for multi-user
communications,” Feb. 2018. [Online] Available: https://arxiv.org/pdf/1802.10371.pdf
[19] Y. Zeng, X. Xu, and R. Zhang, “Trajectory design for completion time minimization in UAV-enabled multicasting,” to
appear in IEEE Trans. Wireless Commun., Jan. 2018.
[20] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Mobile unmanned aerial vehicles (UAVs) for energy-efficient internet
of things communications,” IEEE Trans. Wireless Commun., vol. 16, no. 11, pp. 7574–7589, Nov. 2017.
[21] Y. Zeng, R. Zhang, and T. J. Lim, “Throughput maximization for UAV-enabled mobile relaying systems,” IEEE Trans.

30

Commun., vol. 64, no. 12, pp. 4983–4996, Dec. 2016.
[22] P. Zhan, K. Yu, and A. L. Swindlehurst, “Wireless relay communications with unmanned aerial vehicles: Performance and
optimization,” IEEE Trans. Aerospace Elect. Sys., vol. 47, no. 3, pp. 2068–2085, July 2011.
[23] D. S. Kalogerias and A. P. Petropulu, “Enhancing QoS in spatially controlled beamforming networks via distributed
stochastic programming,” IEEE Intl. Conf. Acoustics Speech Signal Process., Mar. 2017.
[24] S. Zhang, H. Zhang, Q. He, K. Bian, and L. Song, “Joint trajectory and power optimization for UAV relay networks,”
IEEE Commun. Lett., vol. 22, no. 1, pp. 161–164, Jan. 2018.
[25] D. H. Choi, S. H. Kim, and D. K. Sung, “Energy-efficient maneuvering and communication of a single UAV-based relay,”
IEEE Trans. Aerosp. Electron. Syst., vol. 50, no. 3, pp. 2320–2327, Jul. 2014.
[26] S. Jeong, O. Simeone, and J. Kang, “Mobile edge computing via a UAV-mounted cloudlet: Optimization of bit allocation
and path planning,” IEEE Trans. Veh. Tech., May. 2017 (to appear).
[27] R. M. Gray and D. L. Neuhoff, “Quantization,” IEEE Trans. Inf. Theory, vol. 44, no. 6, pp. 2325–2383, Oct. 1998.
[28] A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,
2nd ed., Wiley Series in Probability and Statistics. New York, NY: John Wiley & Sons, 2000.
[29] E. Koyuncu, “Performance gains of optimal antenna deployment in massive MIMO systems,” IEEE Trans. Wireless
Commun., Feb. 2018 (to appear).
[30] Y. Song, B. Wang, Z. Shi, K. R. Pattipati, and S. Gupta, “Distributed algorithms for energy-efficient even self-deployment
in mobile sensor networks,” IEEE Trans. Mobile Comput., vol. 13, no. 5, pp. 1035–1047, May 2014.
[31] E. Koyuncu and H. Jafarkhani, “On the minimum average distortion of quantizers with index-dependent distortion
measures,” IEEE Trans. Signal Process., vol. 65, no. 17, pp. 4655–4669, Sept. 2017.
[32] S. P. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, vol. 28, no. 2, pp. 129–137, Mar. 1982.
[33] Y. Linde, A. Buzo, and R. Gray, “An algorithm for vector quantizer design,” IEEE Trans. Commun., vol. 28, no. 1, pp.
84–95, Jan. 1980.
[34] J. Cortes, S. Martinez, T. Karatas, F. Bullo, “Coverage control for mobile sensor networks,” IEEE Trans. Robot. Automat.,
vol. 20, no. 2, pp. 243–255, Apr 2004.
[35] A. Gusrialdi, S. Hirche, T. Hatanaka, and. M. Fujita, “Voronoi based coverage control with anisotropic sensors,” American
Control Conf., June 2008.
[36] J. Guo and H. Jafarkhani, “Movement-efficient sensor deployment in wireless sensor networks,” IEEE Intl. Conf. Commun.,
May 2018.
[37] W. R. Bennett, “Spectra of quantized signals,” The Bell System Tech. J., vol. 27, no. 3, pp. 446–472, July 1948.
[38] P. L. Zador, “Asymptotic quantization error of continuous signals and the quantization dimension,” IEEE Trans. Inf. Theory,
vol. 28, no. 2, pp. 139–148, Mar. 1982.
[39] P. A. Chou, T. Lookabaough, and R. M. Gray, “Entropy-constrained vector quantization,” IEEE Trans. Acoustics, Speech
and Signal Process., vol. 37, no. 1, pp. 31–42, Jan. 1989.
[40] p.s. (https://math.stackexchange.com/users/17433/p-s), “min : sum of L2 norm and squared-L2 norm,” Mathematics Stack
Exchange, [Online] Available: https://math.stackexchange.com/q/931702 (version: 2014-09-15).

