PREPRINT VERSION

1

Local Map-assisted Positioning for
Flying Wireless Relays

arXiv:1801.03595v1 [cs.IT] 11 Jan 2018

Junting Chen, Member, IEEE, and David Gesbert, Fellow, IEEE

Abstract—This paper considers the exploitation of unmanned
aerial vehicles (UAVs) in wireless networking, with which
communication-enabled robots operate as flying wireless relays
to provide connectivity or a capacity boost to a ground user. We
focus on the particular problem of (automatic) UAV positioning,
which greatly affects the end-to-end throughput performance.
While existing methods rely on propagation distance minimization and statistical models for the presence or absence of a lineof-sight (LOS), we propose an approach capable of leveraging
local topological information so as to offer better performance
guarantees. The proposed method allows to strike a trade-off
between minimizing distance path loss and discovering (near)
LOS opportunities at locations away from the base station (BS)user axis. Furthermore, the algorithm is shown to find the
global optimal UAV position, although it only requires a local
exploration of a signal strength map and the length of search
trajectory is only linear to the geographical scale. Hence, it lends
itself to online implementation. Significant throughput gains are
found when compared to other positioning approaches based on
LOS statistical models.

I. I NTRODUCTION
The demand for high data rate and low latency wireless
service has dramatically increased in recent years. To address
the challenge, future wireless communication technologies
strive to bring the network infrastructure closer to the user
and provide higher bandwidth, e.g., through the deployment of
small cells and the application of millimeter-wave. However,
a known fundamental challenge is shadowing at the user-side
that blocks the signal. Recently, substantial research attention
has been brought on the exploitation of UAVs as flying relays
with flexible positioning so as to relay the signal from the air
for the BS and the user [1]–[7].
However, it is often difficult to find the optimal UAV
position for relaying because the shadowing that obstructs
the UAV-to-user signal depends on the complex, and usually
irregular, urban topology (e.g., buildings and vegetation). Even
in the case of relaying to a single user, the resulting optimal
UAV position may not simply locate on the BS-user axis.
A. Related Works
One essential issue for positioning the UAV is to predict
the air-to-ground channel, since a precise UAV-user channel
This work was supported by the ERC under the European Union Horizon
2020 research and innovation program (Agreement no. 670896).
J. Chen was with the Department of Communication Systems, EURECOM,
France. He is now with the Ming Hsieh Department of Electrical Engineering,
University of Southern California, Los Angeles, CA 90089, USA (email:
juntingc@usc.edu). D. Gesbert is with the Department of Communication
Systems, EURECOM, France (email: gesbert@eurecom.fr).

knowledge is usually not available before the UAV is sent
to a target position. As a way to circumvent this problem,
some prior works simply assumed LOS propagation from
the UAV to the ground user, and hence the channel gain is
merely an explicit continuous function of the UAV position.
Using the LOS model, [8]–[11] focused on UAV navigation
problems, and [12] studied the multiple-input multiple-output
(MIMO) channel to jointly optimize the UAV position and the
orientation of a uniform linear antenna array (ULA) mounted
at the UAV for the best spatial channel to multiple users.
However, LOS models overestimate the channel gain in urban
scenarios, especially in low altitude UAV applications, because
there the air-to-ground signal is likely blocked by obstacles
surrounding the user, and such a user-side shadowing effect
significantly dominates the relay performance.
To capture the shadowing effect, the works [13]–[17] studied a stochastic LOS model, which computes an empirical
LOS probability as a function of the elevation angle from
the user to the UAV. Such a model captures the practical
experience that the larger the elevation angle, the higher
chance to see LOS propagation from the air to the ground.
With that, the works [13]–[17], for instance, optimized the
UAV position to maximize the UAV signal coverage and
minimize the UAV power consumption. However, macroscopic
LOS statistics fails to capture the fine-grained propagation
pattern due to the urban topology, and hence those approaches
[13]–[17] can only be suboptimal.
B. Challenges and Contributions
In reality, the obstacle distribution depends on a specific
user location and is not homogeneous with respect to (w.r.t.)
another user location. As a result, the air-to-ground channel
gain depends on not only the UAV-user distance, but also
the local terrain. In a scenario such as a UAV flying over a
building that originally shadowed a user, a slight change of the
UAV position may result in a significant change in the air-toground channel gain (for example, when the UAV just leaves
the shadow). Ideally, optimal UAV positioning may require a
fully detailed air-to-ground propagation database, but such a
brute-force strategy results in an overwhelming complexity.
The goal of this paper is to adapt the UAV relay system to
the geographically fine-grained propagation environment, by
developing a low complexity trajectory for the UAV to explore
for the optimal relay position from the air. Specifically, two
fundamental challenges are to be addressed:
• How to model a fine-grained air-to-ground propagation channel? We need a model that not only captures

PREPRINT VERSION

•

2

the user-side non-parametric shadowing information but
also facilitates low complexity algorithm for optimal UAV
positioning.
How to plan an efficient search trajectory for the
optimal UAV position? It is not feasible to explore the
entire target area for the optimal UAV position due to the
practical constraint on the UAV flight time. Therefore, it
is critical to plan for an intelligent UAV trajectory with
a limited path length for the search.

In this paper, we propose a nested segmented air-to-ground
propagation model, which captures two important propagation
properties that are previously observed and leveraged in prior
works [18] and [13], respectively: First, the UAV location
space can be partitioned into propagation segments depending
on the degree of obstruction of the UAV-user link, such as pure
LOS, lightly obstructed LOS, and non-line-of-sight (NLOS)
conditions [18]. Second, as the UAV moves away from the
ground user, the UAV-user link tends to experience gradually worsening shadowing, e.g., from pure LOS to strongly
obstructed NLOS [13]. We establish a mathematical model
for the nested segmented propagation property and show that
such a model can be leveraged for globally optimal UAV
positioning without the need of a global radio map exploration.
While this idea was partially exploited in our preliminary work
[19], the work [19] focused only on the simplest case of two
propagation segments.
To summarize, the key contributions are made as follows:
•

•

•

We propose a nested segmented propagation model for
the air-to-ground channel and develop an algorithm
framework to search for the optimal position for UAV
relaying.
We establish theoretical results to prove that the proposed
algorithm finds the global optimal UAV position in a relay
system for a BS and a user, while the length of the search
trajectory is only linear to the BS-user distance; a global
exploration is not needed.
We perform numerical experiments to evaluate the endto-end throughput and compare with existing approaches
based on stochastic LOS models and an intuitive baseline
that limits the search to the BS-user axis. Throughput
gains of up to 300% are found based on Monte Carlo
analysis for an urban Manhattan-like environment.

The rest of the paper is organized as follows. Section II
establishes the nested segmented air-to-ground propagation
model. Section III develops the search algorithm from the
two propagation segment case to the case of arbitrary number
of segments. Section IV establishes theoretical results on
the global optimality. Numerical results are demonstrated in
Section V, and conclusions are given in Section VI.
II. S YSTEM M ODEL
Consider a cellular network in a dense urban environment,
where the direct BS-to-user transmission is obstructed by
obstacles such as buildings or trees. A UAV flies with a fixed
altitude HD in the air to relay the signal between the BS and
the user. Denote x ∈ R2 as the position of the UAV to be

optimized, and x̃ = (x, Hd ) ∈ R3 as the corresponding UAV
position in 3D space.
We consider that the altitudes Hb of the BS and Hd of
the UAV are large enough such that there is always LOS
propagation between the BS and the UAV. We define the
channel as the deterministic power gain averaged over small
scale fading. The BS-UAV channel is modeled as
gb (x) = β0 db (x)−α0

(1)
p
kx − xb k2 + (Hd − Hb )2 is the distance
where db (x) =
from the UAV at (x, Hd ) to the BS at (xb , Hb ), and the
constants α0 > 1 and β0 > 0 are the classical path loss
exponent and offset parameters.
A. Nested Segmented Air-to-ground Propagation Model
We consider a nested segmented propagation structure to
model the various degrees of shadowing for the air-to-ground
channel. Specifically, let D ⊆ R2 be the domain of all
possible UAV positions x at constant altitude Hd . Consider a
partition of D into K disjoint segments according to the actual
propagation environment around user position x̃u ∈ R3 , i.e.,
D = D1 (x̃u ) ∪ D2 (x̃u ) ∪ · · · ∪ DK (x̃u ), where Dk ∩ Dj = ∅,
for k 6= j, and Dk (x̃u ) denotes the region of UAV locations
for which the UAV maintains a degree-k of LOS obstruction.
The notion of degree is further detailed below through the
UAV-user channel:
gu (x) =

K
X

k=1

βk du (x)−αk I{x ∈ Dk }

(2)

p
kx − xu k2 + (Hd − Hu )2 is the distance
where du (x) =
from the UAV located at (x, Hd ) to the user at x̃u = (xu , Hu ),
αk > 1, βk > 0, and I{A} is an indicator function taking
value 1 if condition A is satisfied, and 0 otherwise. In addition,
the partition {Dk , k = 1, 2, . . . , K} is assumed to satisfy
the following two conditions: (i) the propagation segment Dk
exhibits a higher degree of LOS obstruction than Dk−1 , i.e.,
βk du (x)−αk < βk−1 du (x)−αk−1

(3)

for k = 2, 3, . . . , K and any UAV position x, and (ii) the
propagation segments Dk are nested along any directions from
the user, i.e., for any x ∈ Dk and 0 ≤ ρ ≤ 1,
xu + ρ(x − xu ) ∈ Dj ,

for some j ≤ k.

(4)

In other words, when the UAV moves straight towards the user,
the UAV-user channel tends to become always less obstructed
[20].
The nested segmented propagation model (2)–(4) is motivated by the following two observations from typical real-life
situations. First, it is a generalization of the classical path loss
model (1) to the case of multiple NLOS levels [18], e.g., from
light obstruction forms (wood walls) to severe ones (multiple
walls). Second, when the UAV moves straight towards the user,
it has a higher chance to see less obstructed propagation to the
user (as there are fewer obstacles between the UAV and the

PREPRINT VERSION
PREPRINT
PREPRINT

33
3

centered
where
every
user
experiences
in
similar
centered at
at U
U ,, where
where every
every user
user experiences
experiences in
in aaa similar
similar
shadowing
environment.
shadowing environment.
environment.
C.
Application
Examples
C. Application
Application Examples
Examples
C.

(a) Horizontal view
view
(a)
(a) Horizontal
Horizontal view

(b)
(b) Nested
Nested segmented
segmented model
model
Figure
Figure 1.
1. A
A geometric
geometric interpretation
interpretation of
of the
the nested
nested segmented
segmented model
model from
from
Figure 1. A geometric
interpretation
of the nested segmented model from (a)
(a)
(a) horizontal
horizontal view
view and
and (b)
(b) top
top view.
view.
horizontal view and (b) top view.
11
user
also
user as
as the
the UAV
UAV moves
moves closer).
observation was
closer).1 Such
Such an
an observation
observation
was also
exploited
exploited in
in the
the stochastic
stochastic LOS
[13]–[17]. A
LOS model
model [13]–[17].
[13]–[17].
A geometric
geometric
interpretation
interpretation is
is illustrated
illustrated in
in Fig.
Fig. 1.
1.
In
and
In this
this paper,
paper, we
we assume
assume that
that the
the number
number of
of segments
segments K
K and
the
the parameters
parameters α
αkk and
and ββkk are
are known
known or
or previously
previously estimated
estimated
[21],
[21], [22].
[22]. However,
However, the
the global
global knowledge
knowledge of
of the
the propagation
propagation
segments
segments D
Dkk is
is not
not available,
available, and
and the
the UAV
UAV needs
needs to
to plan
plan aa
trajectory
trajectory to
to determine
determine I{x
I{x ∈
∈D
Dkk}} in
in (2)
(2) along
along its
its flight
flight path.
path.

B.
B. Optimal
Optimal UAV
UAV Positioning
Positioning
Consider
Consider aa cost
cost function
function ff(g
(guu,, ggbb)) of
of the
the UAV-user channel
channel gain
gain
gain gguu and
and the
the BS-UAV
BS-UAV channel
gain ggbb.. Assume
Assume that f (x, y)
decreasing function
is
is aa continuous
continuous and
and decreasing
function in
in x and y, respecand ∂f
tively,
tively, i.e.,
i.e., ∂f
∂f(x,
(x, y)/∂x
y)/∂x and
∂f(x,
(x, y)/∂y
y)/∂y are
are negative for all
derivatives exist.
x,
x, yy >
> 00 wherever
wherever the
the derivatives
exist. Before
Before considering
concrete
concrete examples,
examples, aa generic
generic UAV
UAV positioning
positioning problem can
can
be
be formulated
formulated as
as follows
follows
P :::
P
P

minimize
ff (g
minimize
minimize
(guuu(x),
(x), ggbbb(x)).
(x)).
x∈R222
x∈R
x∈R

The difficult
difficult in
in solving
solving P
P
is
twofold:
First, the
the function
function
The
The
difficult
in
solving
P is
is twofold:
twofold: First,
(x)
is
segmented
according
to
the
urban
topology.
Secondly,
ggguuu(x)
is
segmented
according
to
the
urban
topology.
Secondly,
(x) is segmented according to the urban topology.
(guu(x),
(x), gb(x))
(x)) may
may not
not be
be
convex
in
the
variable x.
x. The
fff(g
The
(g
may
not
be convex
convex in
in the
the variable
u (x), ggbb(x))
goal
of
this
paper
is
to
develop
efficient
algorithms
to
find
the
goal
of
this
paper
is
to
develop
efficient
algorithms
to
find
the
goal of this paper is to develop efficient algorithms
globally
optimal
solution
to
P.
globally
optimal
solution
to
P.
globally optimal solution to P.
Note that
that although
although the
the formulation
formulation
P
considers aa relay
relay
Note
Note
that
although
the
formulation P
P considers
system
for
a
single
user
U
,
in
practice,
the
UAV
relay
can
system
for
a
single
user
U
,
in
practice,
the
UAV
relay
can
system for a single user U , in practice, the
actually
provide
service
to
multiple
users
in
a
local
area
actually
provide
service
to
multiple
users
in
a
local
area
actually provide service to multiple users
1 We also note that there are some rare cases of exceptions. For example,
11We
note
there
are
rare
of
For
example,
We also
alsowith
notea that
that
therelocated
are some
some
rare cases
cases
of exceptions.
exceptions.
Formay
example,
a building
big hole
between
the UAV
and the user
break
aa building
with
building
with aa big
big hole
hole located
located between
between the
the UAV
UAV and
and the
the user
user may
may break
break
this
assumption.
this
this assumption.
assumption.

The
transmission
from
the
BS
to
the
UAV
modeled
as
The√
transmission from
from the
the BS
BS to
to the
the UAV
UAV isis
is modeled
modeled as
as
The
√transmission
√
P
g
a
s
+
n
,
and
that
from
the
UAV
to
the
user
y
=
b
b
b
r
r
P
g
a
s
+
n
,
and
that
from
the
UAV
to
the
user
is
y
=
yrr = Pbbgbbabbs +√
nrr, and that from the UAV to the user isis
√
√
modeled
as
y
=
P
g
a
s
+
n
,
where
n
,
n
∼
CN
(0,
1)
u
u
u
u
r
u
r
u
modeled
as
y
=
P
g
a
s
+
n
,
where
n
,
n
∼
CN
(0,
1)
modeled as yuu = Puuguuauusrr + nuu, where nrr, nuu ∼ CN (0, 1)
are
the
receive
noise
at
the
UAV
relay
and
the
user,
respecare the
the receive
receive noise
noise at
at the
the UAV
UAV relay
relay and
and the
the user,
user, respecrespecare
tively,
s,
s
∼
N
(0,
1)
are
the
transmit
signals
from
the
BS
and
r
tively,
s,
s
∼
N
(0,
1)
are
the
transmit
signals
from
the
BS
and
tively, s, srr ∼ N (0, 1) are the transmit signals from the BS and
the
UAV
relay,
respectively.
The
variables
a
and
a
model
the
b
u
the
UAV
relay,
respectively.
The
variables
a
and
a
model
the
the UAV relay, respectively. The variables abb and auu model the
small
scale
fading
on
the
BS-UAV
link
and
the
UAV-user
link,
small scale fading on the BS-UAV link and the UAV-user
link,2
respectively. For
For Rayleigh
Rayleigh fading
fading channels,
channels, |a
|abb||222 and
and |a
|auu||22
respectively.
b
u
are assumed
assumed to
to follow
follow exponential
exponential distribution
distribution with
with parameter
parameter
are
(normalized as)
as) λλ =
= 1.
1.
(normalized
There
are
a
variety
of relay
relay strategies
strategies in
in the
the literature.
literature. To
To
There are a variety of
motivate
problem
P,
we
illustrate
two
examples,
respectively,
motivate problem P, we illustrate two examples, respectively,
on outage
outage probability
probability minimization
minimization for
for amplify-and-forward
amplify-and-forward
on
relaying
and
capacity
maximization
for
decode-and-forward
relaying and capacity maximization for decode-and-forward
relaying.
relaying.
1) Amplify-and-Forward:
Amplify-and-Forward: In
In amplify-and-forward
amplify-and-forward relayrelay1)
ing,
the
UAV
relays
the
information
by
transmitting
=
ing,p
ssrrr =
!the UAV relays the information by transmitting
!
22 + 1, where the scaling factor p P g |a |22
2+1
y
/
P
g
|a
|
2
r
b
b
r
b
b
r
yrr/ Pbbgbb|arr| + 1, where the scaling factor Pbbgbb|arr| + 1
is to
to normalize
normalize the
the transmission
transmission power
power at
at the
the UAV
UAV to
to be
be PPuuu.. ItIt
is
was
shown
in
[23],
[24]
that
the
capacity
of
the
relay
channel
was shown in [23], [24] that
" the capacity of the relay
#channel
2, Pu gu |au |22
2) , where
111 log2 1 + q(Pb gb |ar |22
is
given
by
C
=
AF
AF = 222 log22 1 + q(Pbbgbb|arr| , Puuguu|auu| ) , where
is given by CAF
q(x, y)
y) ,
! xy/(x
xy/(x +
+ yy +
+ 1)
1) and
and the
the parameter
parameter 12121 isis to
to capture
capture
q(x,
2
the
fact
that
the
information
requires
two
time
slots
to
reach
the fact that the information requires two time slots to reach
the
user.
The
outage
probability
with
respect
to
a
target
data
the user. The outage probability with respect to a target data
222
rate
R
was
shown
to
be
[24,
Lemma
1]
rate R was shown to be [24, Lemma 1]
%
$ 11
2R
11  (22R
2R − 1)22
2
P{C
<
R}
≈
+
AF
AF
P{CAF < R} ≈ Pb gb + Pu gu (2 −
1)
Pbbgbb Puuguu

under high
high SNR,
SNR, i.e.,
i.e., P
Pbggb,, P
Puggu 
≫ 1.
1.
under
b b
u u
To minimize the outage probability of the relay channel, the
To minimize the outage probability of the relay channel, the
desired UAV
UAV position
position can
can be
be determined
determined as
as the
the solution
solution to
to the
the
desired
following
problem:
following problem:
P1 :
P1 :

minimize
f (g (x), g (x))
minimize
f (guu(x), gbb(x))
x∈R22
x∈R2
1
1
1
1
:=
+
. (5)
:= Pu gu (x) + Pb gb (x). (5)
Pu gu (x) Pb gb (x)

2) Decode-and-Forward: In decode-and-forward relaying,
Decode-and-Forward:
In decode-and-forward
relaying,
the2)UAV
fully decodes the message
ŝ from the receive
signal
the
UAV
fully
decodes
the
message
ŝ
from
the
receive
signal
yrr, and transmits sr = ŝ to the user. The maximum capacity
of
yr , and transmits sr = ŝ to the user. The maximum capacity of
such a decode-and-forward relay system can be shown to be
such a decode-and-forward
relay2 system can be shown
11
2 to be
CDF
DF = 122 min{log2 (1 + Pb gb |ab |2 ), log2 (1 + Pu gu |au |2 )} [24],
CDF
= 2 min{log2 (1 + Pb gb |ab | ), log2 (1 + Pu gu |au | )} [24],
[25]. Using Jensen’s inequality E{C(x)} ≤ C(E{x}) on a
[25]. Using Jensen’s inequality E{C(x)} ≤ C(E{x}) on a
concave function C(x), an upper bound of the ergodic capacity
concave function C(x),
1 an upper bound of the ergodic capacity
E{CDF
DF} is given by 12 min{log2 (1 + Pb gb ), log2 (1 + Pu gu )}.
E{CDF
} is given by 2 min{log2 (1 + Pb gb ), log2 (1 + Pu gu )}.
The desired UAV position can be determined by maximizing
The desired UAV position can be determined by maximizing
such a capacity bound. Equivalently, the problem can be
2 The original problem in [24] considered a diversity scheme that combines
22The original problem in [24] considered a diversity scheme that combines
the signal from the relay and the signal from the BS. Such a strategy also
the
signal from the relay and the signal from the BS. Such a strategy also
the
leads to problem P1 under high signal-to-noise ratio (SNR).
leads
leads to problem P1 under high signal-to-noise ratio (SNR).

PREPRINT
PREPRINT
PREPRINT VERSION
PREPRINT

400

800

600 600

45

BS
35

User

User User
25

400 400

15
200

BS

35

35

15

25

15

200 200
5

0

45

45

25

4 4

Building height [m]

600

BS

Latitude [m]

800

Latitude [m]

Latitude [m]

800

1000

Building height [m]

1000

Building height [m]

1000

4

0

0
0
0
200
0

200
800
400 200 400
600 400 600

1000 8001000
600 800

[m] [m]
LongitudeLongitude
[m] Longitude

(a) (a)
Urban
topology
(a)
Urban
topology
(a) Urban
topology
Urban
topology

5

5

1000

(b) Power
Power
map map
(b)
(b) Power
mapmap
(b)
Power

(c)
Capacity
map
(c)
map
(c) Capacity
Capacity
map
(c)
Capacity
map

Figure
2.map
(a)
A amap
aurban
denseurban
urbanarea,
area,where
where
the rectangles
rectangles
denote
the
with
colors
representing
their
heights.
(b)
power
mapmap
2. A
A of
map
of of
aofdense
the
denote
thebuilding
building
with
colors
representing
heights.
(b)
The
received
power
mappower m
FigureFigure
2.Figure
(a)
dense
area,
where
the where
rectangles
denote
the denote
building
colors
representing
theirtheir
heights.
(b)The
Thereceived
received
power
2.(a)
(a)
A every
map
a position.
dense
urban
area,
the rectangles
thewith
building
with
colors representing
their
heights.
(b) The
received
corresponding
to
UAV
The
end-to-end
capacity
map.
corresponding
to every
UAV
position.
(c)(c)
The
end-to-end
capacity
map.
corresponding
to every
UAV
position.
The
end-to-end
capacity
map.
corresponding
to every
UAV (c)
position.
(c) The end-to-end
capacity map.

such a capacity bound. Equivalently, the problem can be

there exists a direction δ, such that for a sufficiently small

formulated
as follows:
formulated
as follows:
formulated
as follows:
follows:
 > 0, the new UAV position x + δ decreases the distances
formulated
as
to both the user and the BS, and at the same time, x+δ ∈ Dk .
: minimize
minimize
(g
gbg(x))
u (x),
P2 :P2
f (guf(x),
g(g
(x))
P2
minimize
ff(g
ub(x),
b (x))
2
P2
: :x∈R2x∈R
minimize
g
(x))
From the nested segmented model (2) and also the UAV-BS
u (x),
b
x∈R2
x∈R2
! !n " "
# #
channel model (1), smaller distances du and db imply larger
!
:=:=max
−−log
(x)
max
log
1+
P(x)
b gb (x)
:= max
− log
1 2+ 1P
g"bP
, ,, # channel gains g and g . Due to the monotonicity property of
b+
:= max 2 − 2log
1
+
P
g
(x)
,
u
b
$b #bo$
" 2
"
#
the
cost
function
f
(g
,
g
$
u
b ), larger channel gains yield a smaller
−
log
1
+
P
g
(x)
.
− log
2 1 +"Puu u (x)
− log
. . #
2 1 2+ Pu gu (x)
− log2 1 + Pu gu(6)
(x) cost
. value, which implies that x is not the optimal solution.
(6) (6)Figure
By
contradiction,
theaofpolar
proposition
is therefore
confirmed.
Figure
3.
Illustration
a polar
representation
of the
UAV
position
3.
Illustration
of
representation
of the
UAV
position
x. x.
(6)
A
numerical
example
is
given
in
Fig.
2,
where
Fig.
22 (b)
Figure 3. Illustration of a polar representation of the UAV position x.
A
numerical
example
is
given
in
Fig.
2,
where
Fig.
(b)
A numerical
example
is given
in Fig.
where Fig.
2 (b)
simulates
the received
power
of the2,
UAV-user
signal
w.r.t. 2 (b)Proposition 1 suggests an intuitive algorithm that searches
A
numerical
example
is
given
in
Fig.
2,
where
Fig.
simulates
the
received
power
of
the
UAV-user
signal
w.r.t.
simulatesevery
the received
power
of athesegmented
UAV-userpropagation
signal w.r.t.
UAV position
under
model along the propagation segment boundaries for the optimal
small>ϵ 0,
> the
0,However,
the
UAV
position
x
+
decreases
the
simulates
the under
received
power
of propagation
the propagation
UAV-user
signal
UAV
position
undersegmented
a segmented
model w.r.t.
newnew
UAV
position
x+
ϵδ ϵδ
decreases
UAVϵ position.
such an
algorithm
could
be
costly to the
everyevery
UAV
model
withposition
K = 2. Fig.
2 (c)a shows
the corresponding
relay
channelsmall
distances
to
user
and
the
and
at
time,
small
ϵboth
>
0,user
the
new
position
xsame
+same
ϵδtime,
decreases
t
K
2.from
2shows
(c)
the
UAV
position
under
a corresponding
segmented
propagation
implement,
since
thethe
segment
boundary
may
have
complex
distances
to both
the
and
theUAV
BS,BS,
and
at
theathe
the
BSshows
to
thecorresponding
user
via the UAV.
Itrelay
ischannel
notchannel
trivialmodel
with with
Kevery
=capacity
2. =
Fig.
2Fig.
(c)
the
relay
x
+
ϵδ
∈
D
.
From
the
nested
segmented
model
(2)
and
also
distances
to
both
the
user
and
the
BS,
and
at
the
same
tim
capacity
from
the
BS
to
the
user
via
the
UAV.
It
is
not
trivial
k
with
K
=
2.
Fig.
2
(c)
shows
the
corresponding
relay
channel
shape,
in athe
unacceptably
long trajectory
(which
couldalso
findthe
theBS
optimal
position
thetrivial
irregularx +
ϵδ ∈resulting
Dk . From
nested segmented
model
(2) and
capacity to
from
to theUAV
user relay
via the
UAV.due
It istonot
theunbounded
UAV-BS
channel
model
(1),
smaller
distances
du and(2)dband al
to capacity
find
the from
optimal
UAV
relay
position
due UAV.
to theItirregular
x
+
ϵδ
∈
D
.
From
the
nested
segmented
model
be
even
in
a
bounded
two-dimensional
search
area)
the
BS
to
the
user
via
the
is
not
trivial
k
propagation
pattern.
the
UAV-BS
channel
model
(1),
smaller
distances
d
to find the optimal UAV relay position due to the irregular
u and db
imply
larger
channel
gains
g
and
g
.
Due
to
the
monotonicity
for the
UAV
as demonstrated
inumodel
Fig.
propagation
b(1), smaller distances du and
the
UAV-BS
channel
to find
thepattern.
optimal UAV relay position due to the irregular
imply
larger
channel
gains
gu and
gb .2.Due
to the monotonicity
propagation
pattern.
property
of
the
cost
function
f
(g
, gb ), this
larger
channel
In
what
comes
below,
we
circumvent
problem
by gains
III.
A
LGORITHM
D
ESIGNS
u
imply
larger
channel
gains
g
gb . Due
to the
monotonic
propagation pattern.
property of the cost function f (gu , gbu),and
larger
channel
gains
developing
an
efficient
algorithm
that
has
a
limited
trajectory
yield
a
smaller
cost
value,
which
implies
that
x
is
not
the gai
In this section,
we
first
derive
some
useful
insights
on
the
propertycost
of the
costwhich
function
f (guthat
, gb ),x larger
III. A LGORITHM D ESIGNS
yield a smaller
value,
implies
is not channel
the
III. positions
A LGORITHM
D ESIGNS
It solution.
turns out that
the proposed algorithm
does notisneed
optimal
By
contradiction,
the
proposition
therefore
optimal UAV
via a polar
representation which better length.
yield a By
smaller
cost value,
implies that x is not t
solution.
contradiction,
the which
proposition
In this section, we
derive some D
useful
insights on theoptimal
III.first
A LGORITHM
ESIGNS
follow
the entirety
of the propagation
boundaries.is therefore
segmented
propagation
model. on
Based
In thisexploits
section,thewenested
first derive
some
useful insights
the on toconfirmed.
optimal
solution.
By
contradiction,
the
proposition is therefo
confirmed.
optimal
UAV
positions
viafirst
a polar
representation
which
better
that,
we
develop
algorithm
for useful
the
optimal
UAVon the Proposition 1 suggests an intuitive algorithm that searches
In this
section,
we
some
insights
optimal UAV
positions
viathe
a search
polar derive
representation
which
better
confirmed.
exploits
the under
nestedtwosegmented
propagation
model.toBased
on Proposition
1 suggests an intuitive algorithm that searches
position
segment
case,
andrepresentation
then
extend
propagation segment boundaries for the optimal
UAVsegmented
positions
via
a polar
which
B.along
Polarthe
Representation
exploitsoptimal
the
nested
propagation
model.
Basedthe
oncasebetter
Proposition
suggestsboundaries
an intuitive
that search
that,ofwe
develop
the search
algorithm for the optimal UAValong the propagation 1segment
foralgorithm
the optimal
arbitrary
of
segments.
UAV
position.
However,
such an algorithm
could
be costly
to
exploits
thethenumber
nested
segmented
propagation
model.
Based on
that, position
we
develop
search
algorithm
for
the
optimal
UAV
To
exploit
the
nested
segmented
propagation
model,
we
along However,
the propagation
segment boundaries
for to
the optim
under two segment case, and then extend to the caseUAV position.
such an algorithm
couldhave
be costly
implement,
since
the
segment
boundary
may
a
complex
that,
wetwo
develop
thecase,
search
fortothe
UAV
position
under
segment
andalgorithm
then extend
theoptimal
case
transform the problem into one expressed over a polar coof arbitrary
number
of segments.
position.
However,
such an
algorithm
could be costly
implement,
since
the segment
boundary
may
have a complex
A. Properties
of the
Optimal UAV Position
shape,UAV
resulting
ordinate
system. in a unacceptably long trajectory (which could
position
underoftwo
segment case, and then extend to the case
of arbitrary
number
segments.
resulting
in ax unacceptably
long
trajectory
(which
could
implement,
since
theground
segment
boundary
mayfrom
have
a compl
We first study
someofgeneric
properties of the solution to P.shape,
beLet
unbounded
bounded
two-dimensional
area)
ρ = kx −even
beathe
projected distancesearch
u k in
of arbitrary
number
segments.
be
unbounded
even
in
a
bounded
two-dimensional
search
area)
shape,
resulting
in
a
unacceptably
long
trajectory
(which
cou
As
an
intuitive
yet
naive
approach,
the
optimal
UAV
position
A. Properties of the Optimal UAV Position
the
(xu ,as
Hudemonstrated
) to the UAV at
foruser
the at
UAV
in (x,
Fig.H2.
d ). Let θ ∈ (−π, π)
A. Properties
of the
Optimal on
UAV
UAV
as
demonstrated
in
Fig.
2.
x could
be searched
thePosition
BS-user axis so as to simplyforbethethe
be
unbounded
even
in
a
bounded
two-dimensional
search
are
deviation
anglebelow,
from the
direction
to the by
In what
comes
we user-to-BS
circumvent
this problem
We first study some generic properties of the solution to P.
minimize
the
total
propagation
distance.
However
the
area
A.
Properties
of
the
Optimal
UAV
Position
In
what
below,
we circumvent
this
for comes
thean
UAV
asasdemonstrated
inhas
Fig.
2.problem
user-to-UAV
direction
illustrated
in
3.
utrajectory
= by
We first
study
someyet
generic
properties
of the
solution
to P.
developing
efficient
algorithm
thatFig.
a Denote
limited
Asoffan
intuitive
naivemay
approach,
the
optimal
UAV
xb −xu
the
BS-user
axis
provide
opportunities
to position
operatedeveloping
as
the
normalized
user-to-BS
direction.
(u
,
u
)
,
an
efficient
algorithm
that
has
a
limited
trajectory
1
2
In
what
comes
below,
we
circumvent
this
problem
Asxancould
intuitive
yet
naive
approach,
the
optimal
UAV
position
kxb −xout
We first
study
some generic
properties
of
solution
length. It turns
that the proposed algorithm does not need
uk
be searched
the BS-user
axis while
so the
as moderately
to simplyto P.
in a better
UAV-useronpropagation
segment
2
The
UAV
position
x
∈
R
can
be
equivalently
expressed
by
length.
It
turns
out
that
the
proposed
algorithm
does
not
need
developing
an efficient
algorithm that
has a limited trajecto
x could
be an
searched
onyet
thenaive
BS-user
axis the
soHowever
as to simply
to follow
the entirety
of the propagation
boundaries.
As
intuitive
approach,
optimal
UAV
position
minimize
the
totaldistances.
propagation
distance.
the area
increasing
the
While
the complexity
of searching
(ρ,
θ) as
to
follow
the
entirety
of
the
propagation
boundaries.
minimize
the
total
propagation
distance.
However
the
area
length.
It
turns
out
that
the
proposed
algorithm
does not ne
could
be searched
the BS-user
axis
to simply
offx the
the
BS-user
axisis may
provide
opportunities
toasoperate
complete
area
in on
principle
prohibitive,
the so
result
below
x(ρ,
θ)
=
x
+
ρM(θ)u
(7)
u
off the
BS-user
axis
may
provide
opportunities
to
operate
in minimize
ashows
bettera UAV-user
propagation
while
moderately
the totalefficient
propagation
distance.
the area to follow the entirety of the propagation boundaries.
relatively
way ofsegment
reducing
theHowever
search
space.
B. Polar Representation
in a increasing
better
UAV-user
propagation
segment
while
moderately
the distances.
While
the complexity
of
searching
offProposition
the
BS-user
axis
may
provide
opportunities
to
operate

B. where
Polar Representation 
1. The optimal solution x∗ to P is either on the
cos
θ − sin θpropagation model, we
increasing
the
distances.
While
the complexity
of
searching
To exploit the
nested
segmented
theincomplete
area
is
in
principle
prohibitive,
the
result
below
a
better
UAV-user
propagation
segment
while
moderately
M(θ)
=
(8)
BS-user axis, or on the boundary between two propagation To exploit
B. Polar
Representation
sin θonecos
θ
the problem
nested
segmented
propagation
model,
wecothe complete
area
is
in
principle
prohibitive,
the
result
below
transform
the
into
expressed
over
a
polar
shows
a
relatively
efficient
way
of
reducing
the
search
space.
increasing
the
distances.
While
the
complexity
of
searching
segments.
transform
the
problem
into
one
expressed
over
a
polar
coordinate
system.
shows the
a relatively
efficient
of reducing
the searchthe
space. below
is a rotation
To matrix,
exploitandthe nested segmented propagation model, w
∗
complete
area
isway
in
principle
prohibitive,
Proposition
1. The
optimal
to P isis strictly
eitherresult
on
theordinate
Proof. Suppose
there
is a solution
solution x
x which
inside
system.
Let
ρ
=
∥x
xu ∥problem
be the ground
projected
 distance from
transform−the
into one
Texpressed over a polar c
shows
a The
relatively
efficient
way
of
reducing
Proposition
1.axis,
solution
xis∗ between
to P
either
onsearch
the
BS-user
oroptimal
on the
boundary
two the
propagation
a propagation
segment
Dk and
off
the isBS-user
axis.
Thenspace.
θ =(x
sign(z
uto
−the
z1ground
uUAV
zH
u/ρ
2)be
1 the
2 ) · arccos
Let
=
∥x
−
x
∥
projected
distance
fromπ)
the ρuser
at
,
H
at
(x,
).
Let
θ ∈ (9)
(−π,
u
u
u
d
ordinate system.
BS-user
axis,
or
on
the
boundary
between
two
segments.
∗ propagation
thethe
usertheat deviation
(x
,
H
)
to
the
UAV
at
(x,
H
).
Let
θ
∈
(−π,
π)the fro
Proposition 1. The optimal solution x to P is either on
be
angle
from
the
user-to-BS
direction
u ∥x − x ∥ be the ground
d
Letu ρ =
projected to
distance
u
segments.
be
the
deviation
angle
from
the
user-to-BS
direction
to
the
in Fig. 3. Denote u =
BS-user
or on
the isboundary
twois propagation
Proof: axis,
Suppose
there
a solutionbetween
x which
strictly user-to-UAV
the userxdirection
at (x , Hasu ) illustrated
to the UAV
at (x, Hd ). Let θ ∈ (−π,
b −xu u
asas illustrated
in Fig.user-to-BS
3. Denotedirection.
u =
(u1 , u2 ) !direction
the normalized
segments.
Proof:
theresegment
is a solution
strictlyaxis.user-to-UAV
inside
aSuppose
propagation
Dk and xis which
off the is
BS-user

PREPRINT VERSION

PREPRINT

5

Figure 3. Illustration of a polar representation of the UAV position x.

in which z = (z1 , z2 ) , x − xu , sign(x) = 1 if x > 0, and
sign(x) = −1, otherwise.
We now define an alternative expression for the cost function f (gu (x), gb (x)).
Definition 1 (Fictitious Segment Cost Function). For
x(ρ, θ) ∈ Dk , k = 1, 2, . . . , K, the cost function
f (gu (x), gb (x)) can be written as
f (gu (x), gb (x)) = Fk (ρ, θ)
where
and


Fk (ρ, θ) , f gu(k) (x(ρ, θ)), gb (x(ρ, θ))
gu(k) (x) , βk du (x)−αk

Figure 4.
4. An
Figure
An example
example of
of UAV
UAV search
search trajectory
trajectory under
under two
two propagation
propagation
segment case.
case. Th
Th dashed
dashed lines
lines represent
segment
represent the
the contours
contours of
of the
the cost
cost function.
function.

(10)
(11)

is the UAV-user channel in the kth segment from the channel
model (2).
Note that, due to the nested segmented propagation property
(2), Fk+1 (ρ, θ) > Fk (ρ, θ) for k = 1, 2, . . . , K − 1.
C. Search Trajectory Design for K = 2
We first discuss the two segment case for an easy elaboration
of the design concept. Here, D1 corresponds to the LOS
segment and D2 corresponds to the NLOS segment.
An example search trajectory in the polar coordinate system
is visualized in Fig. 4 for easy illustration, where the black
curve represents the search trajectory and the dashed gray
curves represent the contours of the cost function F1 (ρ, θ).
Note that f (gu (x), gb (x)) = F1 (ρ, θ) when x(ρ, θ) ∈ D1
in the LOS region (unshaded area), and f (gu (x), gb (x)) =
F2 (ρ, θ) when x(ρ, θ) ∈ D2 in the NLOS region (shaded area).
The UAV search trajectory in the two propagation segment
case can be described as follows.
1) Search on the BS-user Axis: Let the UAV start from
the BS. It first moves towards the user until it finds two
critical positions (if they exist) x0k = x(ρ0k , 0), k = 1, 2, which
correspond to the points achieving the minimum cost over the
BS-user axis in the LOS region and NLOS region, respectively.
Specifically, the parameters ρ0k are the solutions that minimize
Fk (ρ, 0) subject to x(ρ, 0) ∈ Dk , for k = 1, 2, in the two
segment case.
For example, when the UAV is initially in the NLOS region,
it can move up to the LOS-NLOS boundary; with that, it can
solve for ρ01 and ρ02 to obtain the critical points x01 and x02 . On
the other hand, when the UAV is initially in the LOS region, it
can compute the critical position x01 in the LOS region, while
x02 does not exist.

on the Right Branch: Starting from the critical
(ρ,2)
θ) Search
as
position x01 , the UAV
first
toρM(θ)u
x(ρ01 , δ/ρ01 ), i.e., a position
x(ρ,
θ) moves
= xu +
(7)
0
just on the right of x1 in Fig. 4, where δ is some step size. It
where
! the following two
" phases, and at
then proceeds according to
cos θ − sin θ
the same time, keeps
track
M(θ)
= of the minimum cost value, denoted
(8)
sin θ cos θ
as Fmin , and the corresponding position, denoted as x̂, along
is
rotationtrajectory:
matrix, and
thea search
#
$ from the
• If the UAV is in the LOS region, it moves
away
θ = sign(z2 u1 − z1 u2 ) · arccos zT u/ρ
(9)
user. Specifically, it moves from x(ρ, θ) to x(ρ + δ, θ).
in •which
= (z1is
, z2in) !
− xu , region,
sign(x) it=moves
1 if x along
> 0, and
If thez UAV
thexNLOS
the
sign(x)
= −1,ofotherwise.
contour
F1 (ρ, θ). Specifically, the contour F1 (ρ, θ) =
3 an alternative expression for the cost funcWeCnow
define
satisfies
tion f (gu (x), gb (x)).
∂F1 (ρ, θ)
∂F1 (ρ, θ)
dρ +
dθ = 0.
Definition 1 (Fictitious
Segment
∂ρ
∂θ Cost Function). For
x(ρ, θ) ∈ Dk , k = 1, 2, . . . , K, the cost function
It can be shown that (Lemma 4 in Appendix C),
f (gu (x), gb (x)) can be written as
∂F1 (ρ, θ)/∂θ 6= 0 for θ 6= 0. As a result from (7), we
have
f (gu (x), gb (x)) = Fk (ρ, θ)

−1 ∂F
1
where dx = M(θ)udρ + ρ d M(θ)u − ∂F1
dρ.
dθ
∂θ
∂ρ
# (k)
$
Fk (ρ, θ) ! f gu (x(ρ, θ)), gb (x(ρ, θ))
(10)
Thus, the UAV updates its position from x to x + ∆x,
and where
k
 gu(k) (x) ! βk du (x)−α
 ∂F −1 ∂F (11)
d
1
1
∆x = γ M(θ)u + ρ M(θ)u −
is the UAV-user channel in the
channel
dθkth segment from
∂θ the ∂ρ
model (2).
in which, γ > 0 is chosen such that k∆xk = δ. The
Note
that, dueγto>the0 nested
propagation
property
constraint
is to segmented
guarantee that
the UAV
keeps
(2), Fmoving
> Ffrom
k=
1, 2,
. . .4).
, K − 1.
k+1 (ρ, θ)
k (ρ, θ)
away
thefor
user
(see
Fig.

The search at this branch is completed whenever the UAV
C.
Search
Trajectory
for K
= 2 ∂F1 (ρ, θ)/∂ρ ≥ 0 or
reaches
a point
x(ρ, θ)Design
such that
either
ρ≥
cos discuss
θ, where
, segment
kxb − xucase
k. The
justification
of the
WeLfirst
theLtwo
for an
easy elaboration
twothe
stopping
willHere,
become
in SectiontoIV-A.
of
designcriteria
concept.
D1clear
corresponds
the LOS
segment and D2 corresponds to the NLOS segment.
3 For mathematical completeness, the partial derivative is defined as
search trajectory in the polar coordinate system
∂f An
(x0 ,yexample
0)
= limt↑0 1t [f (x0 + t, y0 ) − f (x0 , y0 )] throughout this paper.
∂x
is visualized
in Fig. 4 for easy illustration, where the black

curve rep
curves re
Note tha
in the LO
F2 (ρ, θ) w
The UAV
case can
1) Sea
the BS.
critical po
correspon
BS-user a
Specifica
Fk (ρ, 0)
segment
For exa
it can mo
solve for
the other
can comp
x02 does n
2) Sea
position x
just on th
then proc
the same
as Fmin ,
the searc
•
•

If th
user
If th
cont
C sa

It c
∂F1
have

dx

Thu
whe

∆

in w
cons
mov

The sear
reaches a
ρ ≥ L co
two stopp
3 For

ma

∂f (x0 ,y0 )
∂x

PREPRINT VERSION

6

Algorithm 1 Search Trajectory for Optimal UAV Position
Choose a step size δ > 0.
1) Search on the BS-user axis: Find the critical points
ρ0k , k = 1, 2, . . . , K, defined in (14). Initialize Fmin =
F1 (ρ01 , 0) and x̂ = x(ρ01 , 0), where x(ρ, θ) is defined in
(7). Initialize k = 1.
2) Search on the right branch: Set x ← x(ρ0k , δ/ρ0k ).
3) For each iterate x, compute ρ = kx − xu k and θ from
(9).
a) Search
in the virtual LOS region: If x ∈
Sk
D
,
j=1 j update
x ← x(ρ + δ, θ)

(12)

When Fk (ρ + δ, θ) < Fmin , then update the record
Fmin ← Fk (ρ + δ, θ) and x̂ ← x(ρ + δ, θ).
b) S
Search in the virtual NLOS region: If x ∈
/
k
j=1 Dj , update x ← x + ∆x, where

 ∂F −1 ∂F 
d
k
k
∆x = γ M(θ)u + ρ M(θ)u −
dθ
∂θ
∂ρ
(13)
where γ > 0 is chosen such that k∆xk = δ.
Repeat this step until either (i) ρ ≥ L cos θ or (ii)
∂Fk (ρ, θ)/∂ρ ≥ 0.
4) Search on the left branch: Set x ← x(ρ0k , −δ/ρ0k ).
Repeat Step 3).
5) Let k ← k + 1. Repeat from Step 2) until k > K − 1.
6) If FK (ρ0K , 0) < Fmin , then Fmin ← FK (ρ0K , 0) and
x̂ ← x(ρ0K , 0).
3) Search on the Left Branch: Starting from the critical
position x01 , the UAV moves to x(ρ01 , −δ/ρ01 ), i.e., a position
just on the left of x01 in Fig. 4. It repeats the same process as
in Section III-C2 until it meets the stopping criteria. When the
search is completed, the minimum cost is found at Fmin with
corresponding position recorded as x̂. Note that the optimal
position x̂, for example, point A in Fig. 4, is not necessarily
where the search terminates, because the cost f at x(ρ, θ)
may equal to F1 (ρ, θ) or F2 (ρ, θ) depending on whether x is
in LOS or NLOS.
We will show in Section IV-A that the above procedure
finds the globally optimal UAV position at x̂ under some mild
conditions on the cost function f .
D. Search Trajectory Design for Arbitrary K
In the case of more than two propagation segments, one
can generate K − 1 search trajectories following a similar
procedure in Section III-C, where each trajectory is computed
by partitioning the whole area into two virtual propagation
regions: virtual LOS region and virtual NLOS region. Specifically, for the kth search trajectory, the virtual LOS region is
definedSby grouping the first k propagation segments together
k
D̃k , j=1 Dj , and correspondingly, the virtual NLOS region
SK
is defined as D̃kc , D\D̃k = j=k+1 Dj . The whole algorithm
can be summarized as follows.

•

Search on BS-user axis: Let the UAV start from the BS. It
first moves towards the user until it finds the K−1 critical
positions x0k = x(ρ0k , 0), k = 1, K − 1, each of which
corresponds to a point achieving the minimum cost over
the BS-user axis in a virtual LOS region. Specifically, the
parameters ρ0k are the solutions to
minimize Fk (ρ, 0)

(14)

ρ≥0

subject to x(ρ, 0) ∈

k
[

j=1

Dj

(15)

for k = 1, 2, . . . , K − 1. In addition, ρ0K is defined as the
solution that minimizes (14) subject to x(ρ, 0) ∈ DK .
Similarly, it is sufficient for the UAV to move up to the
boundary of the LOS region (propagation segment D1 ).
With that, it can infer all the propagation segments over
the BS-user axis from the nested segmented propagation
property (3)–(4), and solve (14) for ρ0k , k = 1, 2, . . . , K.
• Search over K −1 virtual LOS/NLOS partition scenarios:
In the kth search, k = 1, 2, . . . , K − 1, the UAV follows
a similar procedure as that in Sections III-C2 and III-C3
for virtual LOS region D̃k and virtual NLOS region D̃kc .
• Integration: During the whole search, the UAV keeps
track of the minimum achievable cost Fmin and the
corresponding position x̂. When the algorithm terminates,
x̂ gives the desired UAV position.
The entire search algorithm is summarized in Algorithm 1.
IV. G LOBAL O PTIMALITY AND L INEAR S EARCH L ENGTH
To study the optimality of Algorithm 1, we focus on cost
functions f that satisfy either one of the following conditions.
Condition 1. Assume that the cost function f (x, y) in P
satisfies
∂f (x, y)
∂ 2 f (x, y)
∂f (x, y)
∂ 2 f (x, y)
+2
≥
0,
and
y
+2
≥0
x
2
2
∂x
∂x
∂y
∂y
(16)
for every x, y > 0.
It can be easily verified that the outage probability minimization problem P1 satisfies Condition 1. Note that Condition 1 does not require f (x, y) to be convex.
Condition 2. Assume that the cost function f (x, y) in P can
be written as max{f1 (x), f2 (y)}, where f1 (x) and f2 (y) are
decreasing functions.
It is also clear that the rate maximization problem P2
satisfies Condition 2.
In addition, we focus on continuous-time algorithm trajectory x(t), which can be obtained from Algorithm 1 using infinitesimal step size δ = O(dt) at each infinitesimal time slot dt. Specifically, the search trajectory x(t)
in Algorithm 1 can be described by piece-wise continuous
dynamic systems, where one replaces δ by κdt in (12)
and γ by κγ̄dt in (13), in which κ is a parameter that
specifies the moving speed of the UAV. Accordingly, the
continuous-time processes of the minimum cost Fmin (t) and

PREPRINT VERSION

7

the position track record x̂(t) are given by Fmin (t) =
minimize0≤τ ≤t f (gu (x(τ ), gb (x(τ )) and x̂(t) = x(τ̂ ), respectively, where τ̂ = arg min0≤τ ≤t f (gu (x(τ ), gb (x(τ )).
A. Global Optimality

Proof. Please refer to Appendix B.

We first present the main optimality result as follows.
Theorem 1 (Global Optimality). Suppose that the cost function f in P satisfies either Condition 1 or Condition 2. Then,
x̂(t) in Algorithm 1 converges to the globally optimal solution
to P and Fmin (t) converges to the minimum cost value.
Theorem 1 establishes a powerful result that, the globally
optimal UAV position is attainable, even though the terrain
topology could be arbitrarily complex. As a practical implication, the result suggests that, even when the propagation
gaps between buildings are small (leading to many “spines”
in the irregular propagation segments as shown in Fig. 2(c)),
one can always choose a small enough step size δ < δ̄()
in Algorithm 1, such that the algorithm search trajectory will
visit the neighborhood of the globally optimal UAV position
with probability 1 − , close to 1.
Note that the globally optimality result does not require
convexity or first order continuity of the objective function.
The optimality result can be derived using the polar coordinate system. From the definition of the kth fictitious segment
cost function Fk (ρ, θ) in (10), problem P can be equivalently
written as
P0 :

minimize

ρ≥0,−π≤θ≤π

Proposition 3 (Partial Optimality). Suppose that the cost
function f in P satisfies either Condition 1 or Condition 2.
Then, Fk (ρ, θ) admits a unique local minimizer ρ∗k (θ) over
ρ ≥ 0 for every fixed θ, where |θ| < π/2.

F (ρ, θ) ,

K
X

k=1

Fk (ρ, θ)I{(ρ, θ) ∈ Pk }


where Pk , (ρ, θ) : x(ρ, θ) ∈ Dk is the kth propagation
segment in the polar coordinate system. The optimal solution
x? to P can be obtained as x? = x(ρ? , θ? ), in which (ρ? , θ? )
is the optimal solution to P 0 .
The following intermediate results provide some intuitions
to understand the optimality result in Theorem 1.
Proposition 2 (Bounded Search Region). The optimal solution
x? to P can be obtained as x(ρ? , θ? ), where (ρ? , θ? ) ∈ P
and
n
πo
π
(17)
P = (ρ, θ) : 0 ≤ ρ ≤ L cos θ, − ≤ θ ≤
2
2

in which, L , kxb −xu k is the ground projected distance from
the BS to the user.
Proof. Please refer to Appendix A.

Proposition 2 justifies the first stopping criterion ρ ≥ L cos θ
in Step 3) of Algorithm 1. An intuitive explanation is that when
the UAV moves outside the region P in (17), one can always
find a position in P that has a equal (or smaller) distances,
respectively, to the BS and to the user in the same (or less
obstructed) propagation segment Dk , leading to an equal (or
lower) cost to achieve. Therefore, the optimal UAV position
is contained in P.
The following proposition justifies the second stopping
criterion ∂Fk (ρ, θ)/∂ρ ≥ 0.

Due to the fact that Fk (ρ, θ) has a unique local minimum for
every θ, condition ∂Fk (ρ, θ)/∂ρ ≥ 0 implies that ρ ≥ ρ∗k (θ).
On the other hand, Step 3) of Algorithm 1 always increases
ρ (to be formally justified in Lemma 10 in Appendix E).
Therefore, it suffices to stop the search when the condition
∂Fk (ρ, θ)/∂ρ ≥ 0 is met.
Leveraging the important results in Propositions 2 and 3,
the proof of Theorem 1 is derived in Appendix C under the
two segment case, K = 2. The result is then generalized to
the case of arbitrary number of segments K ≥ 2 in Appendix
D.
B. Maximum Length of the Algorithm Trajectory
Here, we derive the worst-case trajectory length of Algorithm 1.
Theorem 2 (Maximum Trajectory Length). The length of
the search trajectory from Algorithm 1 is upper bounded by
(2.4K − 1.4)L.
Proof. Please refer to Appendix E.

Theorem 2 suggests that the algorithm must terminate in
a finite number of steps given a positive step size δ > 0.
Surprisingly, the bound is linear in L and does not depend on
the shapes of the propagation segments Dk . As a benchmark, if
one searches the optimal UAV position following the segment
boundaries (a property from Proposition 1), the worst-case
length of search will scale as O(L2 ), depending on the shapes
of the boundaries (see, for example, Fig. 2(c)).

V. N UMERICAL R ESULTS
Consider a dense urban area with buildings ranging from
5–45 meter height as illustrated in Fig. 2 (a). The user is
represented by a red circle and the BS locates at the top
right corner denoted by a blue triangle. The height of the
BS is 45 meters, and the UAV moves at 50 meter above the
ground. As a result, there is always LOS propagation between
the UAV and the BS. Consider two propagation scenarios
depending on whether there is LOS propagation between the
UAV and the user. Correspondingly, the parameters of the
UAV-BS channel (1) are chosen as (α0 , log10 β0 ) = (2.2, −4)
and the parameters of the UAV-user channel (2) are chosen as
(α1 , log10 β1 , α2 , log10 β2 ) = (2.2, −4, 3.6, −2.4) according
to some proper scenarios chosen from the WINNER II channel
measurement report [26].
We evaluate the UAV positioning algorithm for the endto-end capacity maximization problem P2. The transmission
powers are chosen as Pb = 30 dBm from the BS and Pd =
36 dBm from the UAV, and the noise power is −80 dBm.
The corresponding power map and end-to-end capacity map

PREPRINT

8

PREPRINT
PREPRINT

PREPRINT VERSION

8

BS

1000 1000

BS BS
UAV

800

UAVUAV

800

Latitude [m]

Latitude [m]
Latitude [m]

800

User

600

600

600

User

User

Average
end-to-end
throughput
(bps/Hz)
Average
end-to-end
throughput
(bps/Hz)
Average end-to-end throughput (bps/Hz)

8

1000

8
6

6

600

800

Longitude [m] 800
600
800
600

2.78

5.28
5.28
3.78 4.72
4.72

0.01

0

20th percentile
0.01

0 0.01

20th percentile
20th percentile

5.44

5.62

5.62
5.62
5.44
5.44

3.78
3.78

3.51
3.51

2.78
2.78
2.31
2.31

2

1000

1.22
1.22
1.22

Mean

Top 20th percentile

Mean
Mean
(a)

Top 20th percentile
Top 20th percentile

(a) (a)

1000
1000

Longitude [m]
Figure 5. Search path (greed lines)
towards [m]
the optimal UAV position (purple
Longitude
diamond). The curves in other colors represent the contours of the end-to-end
Figure
5. Search
Searchpath
path(greed
(greedlines)
lines)towards
towards theoptimal
optimalUAV
UAV
position
(purple
Figure
position
(purple
capacity
(the5. constant
objective value
in (6) inthe
P2).
The
curves
inother
othercolors
colorsrepresent
represent
thecontours
contours
end-to-end
Figurediamond).
5. SearchThe
path
(greed
lines)
towards
the optimal
UAV position
(purple
diamond).
curves
in
the
ofofthethe
end-to-end
capacity
(the
constant
objective
valueinin(6)
(6)
P2). of the end-to-end
diamond).
The (the
curves
in other
colorsvalue
represent
the
capacity
constant
objective
inincontours
P2).
capacity (the constant objective value in (6) in P2).

5.28

3.51

4

2

2

7.51
7.51
7.51
7.51

4.72

2.31

0
400
400
400
400
400
400

6

4

4

7.51 7.51

Direct BS-User link
Probabilistic Alg
Simple Search
Direct
BS-User
Proposed
Direct
BS-User
linklink
Probabilistic
Probabilistic
AlgAlg
Simple
Search
Simple Search
Proposed
Proposed

8

88

(a)

1
1

1
0.8
0.8

0.8
0.6

CDF CDF
CDF

Due to the complex environment, finding the optimal UAV
for every
UAV
position
are illustrated
inis Fig.
(b)
and (c).
position
for
end-to-end
capacity
highly
non-trivial
0.6
Due
to maximum
the
complex
environment,
finding
the2 optimal
UAV
Due
toincomplex
the
complex
environment,
finding
optimal
UAV
0.6
Due
to the
environment,
theisthehighly
optimal
UAV
as shown
Fig.
2 (c).
position
for
maximum
end-to-endfinding
capacity
non-trivial
0.4
position
forinmaximum
end-to-end
capacity
is highly
non-trivial
position
for maximum
capacity
is highly
non-trivial
as
shown
Fig. 2end-to-end
(c).
0.4
as shown
in Fig.
2 (c).
asA.shown
in Fig.
2 (c).
Demonstration
of the UAV Search Path
0.4
Direct BS-User link
0.2
Probabilistic Alg
Demonstration
of the
theUAV
UAV
Search
Path path for the opA.Fig.
Demonstration
Search
Path
InA.
5 the green of
curves
show
the search
DirectSearch
BS-User link
Simple
0.2
Probabilistic Alg
A.timal
Demonstration
of
the
UAV
Search
Path
Proposed
In
Fig.
5
the
green
curves
show
the
search
path
for
the
opUAV
position
in
solving
maximum
end-to-end
capacity
In Fig. 5 the green curves show the search path for the opDirect
BS-User
Simple
Searchlink
Exhaustive
0.2
Probabilistic
Proposed Alg
UAV
position
in solving
solving
maximum
end-to-end
capacity
problem
two
curve
branches
correspond
to the
UAV
In timal
Fig. P2.
5UAV
the The
green
curves
show
the
search
path for
the
optimal
position
in
maximum
end-to-end
capacity
0
Simple
Search
Exhaustive
0
12
4
2
6
8 Proposed10
problem
P2. 2)
The
two
curve
branches
correspond
tothe
theUAV
UAV
searches
Step
Step
4)
in Algorithm
1, respectively.
problem
P2.
The
two
curve
branches
correspond
tocapacity
timal
UAVinposition
inand
solving
maximum
end-to-end
0
Exhaustive
10
0
12
4
2 End-to-end
6
8
capacity
(bps/Hz)
searches
in
Step
2)
and
Step
4)
in
Algorithm
1,
respectively.
in
Step
2)curve
and
Step
4) inthe
Algorithm
Thesearches
other
curves
in
Fig.
5 represent
contour 1,
oftorespectively.
equal
endproblem
P2.
The
two
branches
correspond
the UAV
0
End-to-end
capacity
(bps/Hz)
10
0
12
4
2
6
8
The
other
curves
in
Fig.
5
represent
the
contour
of
equal
end(b)
other
curves
inoptimal
Fig.
represent
the contour
of equal
to-end capacity.
UAV
position
is
at endthe
(b)
searches
in
Step
2)The
and
Step5 4)
in Algorithm
1, found
respectively.
(b)
to-end
capacity.
The5optimal
optimal
UAV
positionisofisfound
foundat
atthethe
End-to-end capacity
(bps/Hz)
capacity.
The
UAV
purple
diamond.
The
other
curves
in Fig.
represent
the position
contour
equal
endFigure
Comparisonofofthe
theaverage
averageend-to-end
end-to-end
throughput
over
different
Figure 6.
6. Comparison
throughput
over
different
purple
diamond.
diamond.
(b)
to-end capacity. The optimal UAV position is found at the schemes.
schemes.
Figure 6. Comparison of the average end-to-end throughput over different

schemes.
purple
diamond. Performance
B. Throughput
Figure 6. Comparison of the average end-to-end throughput over different
B. Throughput
B.
Throughput Performance
Performance
schemes.
We We
nownow
evaluate
thethe
throughput
performance
The optimal UAV position is then obtained by solving
evaluate
throughput
performancewith
withthe
theUAV
UAV
The
optimal
position
is then
obtained by solving
We
now
evaluate
the
throughput
performance
with
the
UAV
B.relay.
Throughput
Performance
Consider
thatthat
a single
user
P2
based
on UAV
the
function
gu (x)
(18).
relay.
Consider
a single
userlocates
locatesrandomly
randomlyand
and uniuniThe
optimal
UAV
position
is in
then
obtained by solving
relay.
Consider
that
a
single
user
locates
randomly
and
uniP2
based
on
the
function
g
(x)
in
(18).
formly
on evaluate
the
streets
in in
Fig.
transmission
• Simple Search: Obtain the uoptimal UAV position by
Weformly
now
thedepicted
throughput
performance
with
the UAV
on the
streets
depicted
Fig.2 2(a).
(a).The
The
transmission
P2 based
on the
function
u (x) in (18).
formly
the streets
depicted
in dBm
Fig. 2 (a).both
The transmission
• The
Simple
Search:
theisgoptimal
UAV
position
by
optimal
position
then
obtained
by solving
searching
onlyUAV
on Obtain
the
BS-user
axis (i.e.,
to implement
powers
are on
chosen
=
Puser
33
BS
and
bP
dP=
powers
are
chosen
as
33 dBmfor
for boththe
the
BSuniand
relay.
Consider
thatasa P
single
locates
randomly
and
b =
d =
• Simple Search: Obtain the optimal UAV position by
powers
are
chosen
as
P
=
P
=
33
dBm
for
both
the
BS
and
searching
only
on
the
BS-user
axis
(i.e.,
to
implement
b
d
P2
based
on
the
function
g
(x)
in
(18).
only
Step
1)
of
Algorithm
1).
u
the UAV,
and
the the
throughput
asasthe
theon
UAV,
throughput
isFig.
evaluated
theabsolute
absolutevalue
value
formly
the and
streets
depictedisinevaluated
2 (a).
The
transmission
searching
only
on the BS-user
axis (i.e., to implement
the
UAV,
and
the throughput
isplaces
evaluated
as the
absolute
value •• Simple
only
Step
1)Search:
of Algorithm
1). optimal
Search:
Obtain
the
UAVsearch
position
Exhaustive
We perform
exhaustive
over by
of (6).
The
proposed
places
the
UAV
to
the
position
of are
(6).
The
proposed
scheme
the
UAV
to
the
position
powers
chosen
as Pscheme
=
P
=
33
dBm
for
both
the
BS
and
b
d
only
Step
1)
of
Algorithm
1).
of
(6).
The
proposed
scheme
places
the
UAV
to
the
position
•
Exhaustive
Search:
We
perform
exhaustive
search
over
the
entire
search
region
on
equally-spaced
grids
with
searching
only on the BS-user axis (i.e., to implement
obtained
from
Algorithm
under
stepsize
size
=5 5meters.
meters.
We
obtained
from
Algorithm
1 under
step
δ δ=absolute
We
the
UAV,
and
the
throughput
is11evaluated
as
the
value
• Exhaustive Search: We perform exhaustive search over
obtained
from
Algorithm
under
step
size
δ
=
5
meters.
We
the
entire
search
region
on
equally-spaced
grids
with
δ
=
5
meter
spacing.
The
grid
point
that
maximizes
the
only
1) of
Algorithm
also
consider
following
baselines
UAV
positioning:
consider
the the
following
baselines
forfor
UAV
ofalso
(6).
The
proposed
places
the
UAV
topositioning:
the
position
theStep
entire
search
region 1).
on equally-spaced grids with
also
consider
the scheme
following
baselines
for obtain
UAV
positioning:
δobjective
= 5 meter
spacing.
Theperform
point
that maximizes
the
in P2
is chosen
asgrid
the UAV
position.
Note
that
•
Exhaustive
Search:
We
exhaustive
search
over
•
Probabilistic
Algorithm
[16]:
First,
an
empirical
• Probabilistic
Algorithm
[16]:
empirical
obtained
from Algorithm
1 under
stepFirst,
sizeobtain
δ = 5 an
meters.
We
δ = 5 meter spacing.
The grid point
that maximizes
the
such
a
scheme
is
prohibited
in
practice
and
hence
it
is
• LOS
Probabilistic
Algorithm
[16]:
First,
obtain
an
empirical
objective
P2 is region
chosen on
as the
UAV position.grids
Note with
that
distribution
fLOS
P{LOS
, ϕ}
function
the
entireinsearch
equally-spaced
LOS distribution
fLOS
(ϕ)(ϕ)= =P{LOS
, ϕ}
asasa afunction
objective
in
P2
is
chosen
as
the
UAV
position.
Note
that
also consider
the
following
baselines
for
UAV
positioning:
for
benchmarking
LOS
distribution
fLOSϕ
(ϕ)from
= P{LOS
, ϕ}
as aUAV,
function
scheme
is only.
prohibited
practice
hence itthe
is
of
the
elevation
angle
userto
tothe
the
by
δsuch
=such
5ameter
spacing.
The gridinin
point
thatand
maximizes
of the
elevation
angle
ϕ[16]:
fromFirst,
thetheuser
UAV, by
a scheme
is prohibited
practice
and hence it
is
• Probabilistic
Algorithm
obtain
an
empirical
of the elevation
angle ϕ dropping
from the10,000
user tousers
the UAV,
by The objective
for benchmarking
only.
performance
on
direct
BS-user
transmission
(without
UAV
uniformly
and
randomly
on
the
in P2 is chosen
as the UAV position. Note that
uniformly
and
randomly
dropping
10,000
users
on
the
for
benchmarking
only.
LOSstreets
distribution
= dropping
P{LOSpicking
, ϕ}
asUAV
ausers
function
uniformly
and2fLOS
randomly
10,000
on the relaying)
the segmented
channel
model
in Fig.
(a) (ϕ)
and randomly
locations
such isa evaluated
scheme
isusing
prohibited
practice
and
hence(2)
it is
performance
on direct
BS-user in
transmission
(without
UAV
in Fig. 2 angle
(a) andϕrandomly
picking
UAV
locations
ofstreets
the
elevation
from
the
user
to
the
UAV,
by The
performance
on
direct
BS-user
transmission
(without
UAV
streets the
in Fig.
2 (a)
andSecond,
randomly
picking
locations
byThe
replacing
d
(x)
by
the
BS-user
distance
and
replacing
within
target
area.
given
each UAV
user position
u
for
benchmarking
only.
relaying)
is
evaluated
using
the
segmented
channel
model
(2)
within theand
target
area. Second,
given
each users
user position
uniformly
randomly
10,000
onposition
the
relaying)
usingofthe
channel
model (2)
within
the target
area.dropping
Second,
each
I{x
∈ Dk } is
byevaluated
the indicator
thesegmented
BS-user link
propagation
x
channel
at UAVgiven
location
x isuser
computed
u , the UAV-user
bybyreplacing
bybythe
distance
xu , x
the, the
UAV-user
at UAV
location
x isx computed
performance
on
direct
BS-user
transmission
(without
UAV
streets
Fig.
2 (a)channel
and
randomly
picking
UAV
locations
replacingdud(x)
theBS-user
BS-user
distanceand
andreplacing
replacing
segment.
UAV-user
channel
at UAV
location
is computedThe
asuin
[13],
[16]
u (x)
I{x
∈
D
}
by
the
indicator
of
the
BS-user
link
as
[13],
[16]
k
relaying)
using
theofsegmented
channel
model
within
target
area. Second, given
I{x
D
} by thetheindicator
the BS-user
linkpropagation
propagation
Fig. ∈6 is
compares
average
end-to-end
throughput
over (2)
as the
[13],
[16]
−α1each user position
kevaluated
gu (x) = fLOS (ϕ)β1 kx − xu k
segment.
1
replacing
the cell
BS-user
distance
and replacing
xu , the
UAV-user
channel
at−UAV
computed by
10,000
users indFig.
(a). The
edge users
are recognized
as
segment.
location
u (x)2 by
gu (x)
= f=
x−u ∥x−α
−α1 x is−α
LOS
1 ∥x ∥x
2
gu (x)
f(ϕ)β
(ϕ)β
∥
+
1
−
f
(ϕ)
β
kx
−
x
k
.
(18)
LOS
1
u
LOS
2
u
Fig.
6
compares
the
average
end-to-end
throughput
! !
" "
those
within
the
20th
percentile
of
the
throughput
under
direct
I{x
∈
D
}
by
the
indicator
of
the
BS-user
link
propagation
as [13], [16]
k
Fig. 6 compares the average end-to-end throughputover
over
−α2
−α
.
(18)
+ +
1 −1f−
(ϕ)
β
∥x
−
x
∥
2
LOS
2
u
10,000
users
in in
Fig.
2 (a).
The
cell
.
(18)segment.
fLOS (ϕ) β2 ∥x − xu ∥
10,000
users
Fig.
2 (a).
The
celledge
edgeusers
usersare
arerecognized
recognizedasas
−α1
gu (x) = fLOS (ϕ)β1 ∥x − xu ∥
Fig. 6 compares the average end-to-end throughput over
!
"
(18) 10,000 users in Fig. 2 (a). The cell edge users are recognized as
+ 1 − fLOS (ϕ) β2 ∥x − xu ∥−α2 .

PREPRINT VERSION

9

BS-user transmission, and the cell center users are recognized
as those in the top 20th percentile.4 First, the proposed scheme
performs as well as the exhaustive search scheme as seen from
the two overlapping cumulative distribution function (CDF)
curves, which verify our theoretical results on optimality.
Second, across all the three user categories, the proposed
scheme with the optimal UAV placement achieves the highest
throughput. In particular, it realizes more than 300% throughput gain on average over direct BS-user transmission, and
achieves 50% gain for cell edge users over an probabilistic
approach.
VI. C ONCLUSION
This paper designed algorithms to search for the optimal
UAV position for establishing the best wireless relay link
between a BS and a user in a dense urban area. Global
topological information, such as the location and the volume
of the buildings, was not required. The desired UAV position,
constrained at a fixed height above the ground, was defined
as the minima of a general cost function. A nested segmented
propagation model was proposed to model the propagation
from the UAV to the ground user that is probably blocked by
obstacles. A search algorithm was developed and shown to
find the global optimal UAV position. In addition, the length
of the search trajectory is upper bounded by a linear function
of the BS-user distance. Significant throughput gains are found
when compared to other UAV positioning approaches or direct
BS-user transmissions.
A PPENDIX A
P ROOF OF P ROPOSITION 2
We establish the following lemma, which implies that
a smaller cost value can be achieved in a less obstructed
propagation segment.
Lemma 1 (Less Obstructed Segmented is Preferred). Given
ρ and θ, the following holds
Fk (ρ, θ) < Fk+1 (ρ, θ)

(19)

for k = 1, 2, . . . , K − 1.

Proof. From the nested segmented propagation property (3)
(k)
– (4) and the definition of gu (x) in (11), we have
(k)
(k+1)
(x(ρ, θ)) for all x(ρ, θ). Since f (gu , gb )
gu (x(ρ, θ)) > gu
is a decreasing function in gu , we have the inequality (19) from
the definition of Fk (ρ, θ) in (10).
The result of Proposition 2 can be proven by contradiction
as follows.
First, suppose that solution x(ρ0 , θ0 ) satisfies π2 < |θ0 | < π.
Then, we must have F1 (ρ0 , θ0 ) ≤ F (ρ0 , θ0 ) by Lemma 1 as
Pk are mutually exclusive. Since there is LOS propagation
when the UAV is on top of the outdoor user, i.e., (0, 0) ∈ P1 ,
we have F (0, 0) = F1 (0, 0) < F1 (ρ0 , θ0 ) ≤ F (ρ0 , θ0 ), where,
by moving from (0, 0) to (ρ0 , θ0 ), the UAV position (ρ0 , θ0 )
has longer distances to both the user and the BS. Thus, by
4 We

found from our experiment that around 22% users have LOS propagation on the BS-user link.

contradiction, x(ρ0 , θ0 ) cannot be the optimal solution to P,
i.e., we must have |θ0 | ≤ π2 .
Second, suppose that the optimal solution x(ρ0 , θ0 ) satisfies
0
ρ > L cos θ0 . Consider a different solution x(ρ00 , θ0 ), where
ρ00 = L cos θ0 − (ρ0 − L cos θ0 ). From geometry, one can easily
show that the UAV-BS distance db (x(ρ0 , θ0 )) = db (x(ρ00 , θ0 ))
and the UAV-user distance du (x(ρ00 , θ0 )) < du (x(ρ0 , θ0 )).
Suppose that (ρ0 , θ0 ) ∈ Pk and (ρ00 , θ0 ) ∈ Pj . From the nested
segmented property (3) – (4), we must have j ≤ k. From
Lemma 1, we have
F (ρ00 , θ0 ) = Fj (ρ00 , θ0 ) < Fk (ρ00 , θ0 ) < Fk (ρ0 , θ0 ) = F (ρ0 , θ0 )
which contradicts to the hypothesis that (ρ0 , θ0 ) minimizes
the objective function F (ρ, θ). This confirms that the optimal
solution must satisfies 0 ≤ ρ ≤ L cos θ.
A PPENDIX B
P ROOF OF P ROPOSITION 3
A. Proof under Condition I
We first analyze the property of the composite function
f ((gu ◦ du )(z), (gb ◦ db )(z)).

Lemma 2. Let gi (di ) = βi di−αi , i = 1, 2, and α > 1. Let
di (z), i = 1, 2, be convex functions in z. Suppose that f (x, y)
satisfies Condition 1. Then, the composite function f ((g1 ◦
d1 )(z), (g2 ◦ d2 )(z)) is strictly convex in z.
Proof. Since ∂f /∂x < 0 and ∂f /∂y < 0, the first order
partial derivative of f (g1 ◦ d1 , g2 ◦ d2 ) is given by
∂f ∂gi
∂f
∂f
i −1
=
=
(−αi βi )d−α
>0
i
∂di
∂gi ∂di
∂gi
for i = 1, 2, and the second order partial derivative is given
by
∂2f
∂ 2 f ∂gi
∂f ∂ −αi −1
=
(−αi βi )di−αi −1 + (−αi βi )
d
∂d2i
∂gi2 ∂di
∂gi ∂di i

αi + 1 ∂f 
∂2f
= αi2 βi di−αi −2 βi di−αi 2 +
∂gi
αi ∂gi
 ∂2f

∂f
> αi2 βi di−αi −2 gi 2 + 2
∂gi
∂gi
≥0
for i = 1, 2, where the first inequality is due to the fact that
∂f
αi > 1 and ∂g
< 0.
i
Define an operator ∇ , [ ∂z∂ 1 ∂z∂ 2 . . . ∂z∂m ]T , where zi is
∂f
the ith entry of a vector variable z. From ∇f = ∂d
∇d1 +
1
∂f
∇d
,
the
Hessian
matrix
of
f
is
given
by
2
∂d2
∇2 f =

∂2f
∂f 2
∇d1 ∇dT1 +
∇ d1
∂d21
∂d1
∂2f
∂f 2
+ 2 ∇d2 ∇dT2 +
∇ d2  0
∂d2
∂d2

since ∇2 di (z)  0 due to the convexity of di (z). Therefore,
f is strictly convex in z (as di (z) are strictly convex).

PREPRINT VERSION

10

From the polar representation of the UAV-user and UAV-BS
distances
p
db (x(ρ, θ)) = ρ2 + L2 − 2ρL cos θ + (Hd − Hb )2 (20)
p
du (x(ρ, θ)) = ρ2 + (Hd − Hu )2
(21)

one can show that db (x(ρ, θ)) and du (x(ρ, θ)) are strictly
convex in ρ.
Then, using Lemma 2 and the definition of Fk (ρ, θ) in (10),
we can conclude that Fk (ρ, θ) is strictly convex in ρ, and
therefore, Fk (ρ, θ) admits a unique local minima ρ∗k (θ) in the
bounded interval ρ ∈ [0, L cos θ].

exists t∗ ≤ T3 , such that ρ(t∗ ) = ρ∗ and θ(t∗ ) = θ∗ , where
(ρ∗ , θ∗ ) is the optimal solution to the following problem
minmize

ρ≥0,(ρ,θ)∈P1+

where P1+ = {(ρ, θ) : 0 ≤ θ ≤

Consider Fk (ρ, θ) =
From (20) – (21), to increase ρ, we must have du increase
and db decrease, and as a result, f1 decreases and f2
increases monotonically in ρ ∈ [0, L cos θ]. Therefore, these
exists a unique local minimizer ρ∗k (θ) in the closed interval
[0, L cos θ].
A PPENDIX C
P ROOF OF T HEOREM 1 UNDER K = 2 C ASE
From the bounded search region result established in Appendix A (see Proposition 2), we can focus on − π2 < θ < π2 .
As a result, the algorithm trajectory x(t) can be written
as (ρ(t), θ(t)) via the inverse of the mapping x(ρ(t), θ(t))
from (7). In addition, defining the process (ρ̂(t), θ̂(t)) from
x̂(t), the convergence of the process x̂(t) corresponds to the
convergence of (ρ̂(t), θ̂(t)). With these notations, we will work
on the polar coordinate system for the optimality proof.
We first focus on the subproblem

π
2 , (ρ, θ)

∈ P1 }.

Using Lemma 3, the record Fmin (T3 ) satisfies
Fmin (T3 ) ≤ minimize F1 (ρ, θ).
ρ≥0,(ρ,θ)∈P1+

(27)

Finally, similar arguments from Lemma 3 can apply to Step
4) which yields
Fmin (T4 ) ≤ minimize F1 (ρ, θ)

B. Proof under Condition II
(k)
max{f1 (gu (x(ρ, θ)), f2 (gb (x(ρ, θ))}.

(26)

F1 (ρ, θ)

ρ≥0,(ρ,θ)∈P1−

(28)

where P1− = {(ρ, θ) : − π2 ≤ θ ≤ 0, (ρ, θ) ∈ P1 } and T4 > T3
is the time when the algorithm completes Step 4).
Since Fmin (t) is a non-increasing process, to summarize
from (25), (27), and (28), Fmin (T ) gives the minimum value
over subset P2 , P1+ , and P1− , and hence achieves the minimum
value of P 0 , i.e., the minimum value of P. As a result,
(ρ̂(t), θ̂(t)) converges to the optimal solution to P 0 before
the entire algorithm terminates at t = T , which implies that
x̂(t) converges to the optimal solution to P.
The remaining part of this section is to prove Lemma 3.
A. General Strategy to Prove Lemma 3

Fmin (T ) ≤ minimize F (ρ, 0)

(22)

= minimize F (ρ, 0)

(23)

≤ minimize F2 (ρ, 0)

(24)

Before developing the technical details, the structure of the
proof is sketched as follows.
• We first show that the algorithm trajectory (ρ(t), θ(t)) in
the loop of Step 3) can only stop at θ(T ) ≥ θ∗ , where
T is a finite stopping time (Lemma 7). Therefore, as the
algorithm trajectory from Step 3) is continuous, we must
have θ(t) = θ∗ for some t ≤ T .
∗
• We then argue that when the trajectory reaches θ(t) = θ
for some t ≤ T , it must hold that (ρ(t), θ(t)) ∈ P1+ and
ρ(t) ≤ ρ∗ (Lemma 8).
• As a result, by Step 3a) in Algorithm 1, (ρ(t), θ(t)) must
then reaches (ρ∗ , θ∗ ) by increasing ρ(t) until ρ(t) = ρ∗ .
Therefore, the minimum objective value Fmin ← F1 (ρ∗ , θ∗ ) as
well as the optimal solution (ρ∗ , θ∗ ) to the subproblem (26) are
discovered and recorded in processes Fmin (t) and (ρ(t), θ(t)).

≤ minimize

(25)

B. Preliminary Results

0
P+
:

minimize

ρ≥0,0≤θ≤ π
2

F (ρ, θ)

which corresponds to the search on the right branch illustrated
in Fig. 4.
0
To show the optimality in P+
, we note that when the
algorithm terminates at t = T , Fmin (T ) satisfy
0≤ρ≤L
ρ≥0
ρ≥0

ρ≥0,(ρ,θ)∈P2

F2 (ρ, θ)

where inequality (22) is due to Step 1) and 6) in Algorithm 1
and the fact that Fmin (t) is a non-increasing process. Equality
(23) is due Proposition 2, inequality (24) is due to Lemma 1
in Appendix A, and inequality (25) is from Lemma 4 to be
developed later.
We then state the following lemma, for which the proof will
be established later.
Lemma 3 (Local optimality). Suppose that the cost function
f in P satisfies either condition I or condition II. Then,
the continuous trajectory (ρ(t), θ(t)) passes through (ρ∗ , θ∗ )
before it completes Step 3) in Algorithm 1 at t = T3 , i.e., there

We need the following preliminary results to develop Lemmas 7 and 8.
First, the following property reduces the search space.
Lemma 4. It holds that ∂Fk (ρ, θ)/∂|θ| > 0 for all k and
θ 6= 0. In addition, for any θ0 ≥ 0, the following property
holds
min Fk (ρ, θ0 )
ρ≥0

≤

min

min

j≥k ρ≥0,θ 0 <θ≤ π
2

Fj (ρ, θ)

for 1 ≤ k ≤ K. Similarly, for any θ0 < 0,
min Fk (ρ, θ0 )
ρ≥0

≤

min

min

0
j≥k ρ≥0,− π
2 ≤θ<θ

Fj (ρ, θ)

(29)

(30)

PREPRINT VERSION

11

∂
Proof. We first note that ∂|θ|
Fk (ρ, θ) > 0 for all k =
1, 2, . . . , K, because increasing |θ| will increase the UAVBS distance db while the UAV-user distance du = ρ is not
affected, and hence gb (x(ρ, θ)) is decreased. As the cost
function f (x, y) is increasing with x and y, respectively, due to
conditions I or II, the cost Fk (ρ, θ) increases as |θ| increases.

Consider that θ0 ≥ 0. For every 0 ≤ ρ ≤ L, θ ≥ θ0 , and
j ≥ k, we must have
Fk (ρ, θ0 ) ≤ Fj (ρ, θ0 ) ≤ Fj (ρ, θ).

As a result, minρ≥0 Fk (ρ, θ0 ) ≤ minρ≥0 Fj (ρ, θ) for every
θ > θ0 . Hence the result (29) is confirmed.
The case of (30) can be shown in a similar way.
As a key property of Algorithm 1, the following lemma
shows that every cost F1 (ρ(t), θ(t)) along the algorithm
trajectory (ρ(t), θ(t)) is achievable as it were in the LOS
region. Specifically, even when the actual cost F (ρ(t), θ(t)) =
F2 (ρ(t), θ(t)) > F1 (ρ(t), θ(t)), there exists a 0 ≤ τ < t, such
that F (ρ(τ ), θ(τ )) = F1 (ρ(t), θ(t)).
Lemma 5. For every point on the algorithm trajectory
(ρ(t), θ(t)), 0 ≤ t ≤ T , there exists 0 ≤ τ ≤ t, such that
(ρ(τ ), θ(τ )) ∈ P1 and
F (ρ(τ ), θ(τ )) = F1 (ρ(τ ), θ(τ )) = F1 (ρ(t), θ(t)).
Proof. If (ρ(t), θ(t)) ∈ P1 , we have F (ρ(t), θ(t)) =
F1 (ρ(t), θ(t)) and τ = t. If (ρ(t), θ(t)) ∈ P2 , then the
algorithm is in the loop of Step 3b), where it follows the
trajectory on the contour F1 (ρ(t), θ(t)) = C. To trace backward, there must be a 0 ≤ τ < t, such that F1 (ρ(τ ), θ(τ )) =
F1 (ρ(t), θ(t)) and (ρ(τ ), θ(τ )) ∈ P1 . Note that the initial
point (ρ01 , 0) from Step 1) is in the LOS region P1 from the
definition (7).
Finally, the following property show that ∂F1 (ρ, θ(t))/∂ρ ≤
0 until the algorithm terminates.
Lemma 6. Let ρ∗1 (θ) minimize F1 (ρ, θ) over all ρ ≥ 0 with
θ fixed. Then, the algorithm trajectory (ρ(t), θ(t)) satisfies
ρ(t) ≤ ρ∗1 (θ(t)) and ∂F1 (ρ(t), θ(t))/∂ρ ≤ 0 for all t before
the iteration completes Step 3). Moreover, ∂F1 (ρ, θ(t))/∂ρ ≤
0 for all 0 ≤ ρ ≤ ρ(t). The same result holds for the search
trajectory in Step 4).
Proof. First, from the definition of
in (14) and the nested
segmented propagation property (3) – (4), we have ρ01 ≤ ρ∗1 (0).
This is because, we have x(ρ01 , 0) ∈ D1 from (14), and hence,
all the points (ρ, 0), 0 ≤ ρ ≤ ρ01 , are in the LOS region.
As a result, if ρ01 > ρ∗1 (0), then (ρ∗1 (0), 0) is also in the LOS
region (satisfying the constraint (15)), which implies that ρ∗1 (0)
minimizes (14), yielding a contradiction. Therefore, from Step
1), we have the initial point (ρ(0), θ(0)) satisfying θ(0) = 0
and ρ(0) = ρ01 ≤ ρ∗1 (0) = ρ∗1 (θ(0)).
Second, as the local minimizer ρ∗1 (θ) is unique from Proposition 3, we must have ∂F1 (ρ, θ)/∂ρ < 0 for ρ < ρ∗1 (θ)
and ∂F1 (ρ, θ)/∂ρ > 0 for ρ > ρ∗1 (θ). (Note that there is no
saddle point either, due to the strict convexity under Condition
1 and monotonicity of f1 and f2 under Condition 2.) Once
ρ01

∂F1 (ρ(t), θ(t))/∂ρ ≥ 0, Step 3) is completed. As a result, it
holds that ρ(t) ≤ ρ∗1 (θ(t)).
C. Proof of Lemma 3
We now prove the following results.
Lemma 7. The algorithm trajectory in Step 3) (ρ(t), θ(t)) can
only stop at θ(T3 ) = θ0 ≥ θ∗ where (ρ∗ , θ∗ ) is the optimal
solution to (26).
Proof. The result can be proven by contradiction. Suppose
that Step 3) stops at (ρ(T3 ), θ(T3 )) where ρ(T3 ) = ρ0 and
θ(T3 ) = θ0 < θ∗ . As Step 3) is completed, either one of the
stopping criteria should have been triggered.
First, suppose that the condition ∂F1 (ρ0 , θ0 )/∂ρ ≥ 0 was
triggered. From Lemma 5, there exists τ ≤ T3 , such that
F1 (ρ(τ ), θ(τ )) = F1 (ρ0 , θ0 ) and (ρ(τ ), θ(τ )) ∈ P1+ . From
Lemma 6 and Proposition 3, (ρ0 , θ0 ) minimizes F1 (ρ, θ0 ) over
ρ ≥ 0. As a result,
F1 (ρ(τ ), θ(τ )) = F1 (ρ0 , θ0 )

= minimize F1 (ρ, θ0 )
ρ≥0

Fj (ρ, θ)
≤ min minimize
π
0

(31)

F1 (ρ, θ)
≤ minimize
π
0

(32)

j≥1 ρ≥0,θ <θ≤ 2

ρ≥0,θ <θ≤ 2

≤

minimize

+
ρ≥0,θ 0 <θ≤ π
2 ,(ρ,θ)∈P1

F1 (ρ, θ)

= F1 (ρ∗ , θ∗ )
where inequality (31) is from Lemma 4, inequality (32) is
from Lemma 1, and the last equality is by the hypothesis that
θ∗ > θ0 . However, this violates the assumption that (ρ∗ , θ∗ ) is
the solution to (26), whereas, (ρ(τ ), θ(τ )) ∈ P1+ yields a lower
cost. By contradiction, the stopping criterion ∂F1 (ρ0 , θ0 )/∂ρ ≥
0 is not satisfied.
Second, suppose that the condition ρ(T3 ) = ρ0 ≥ L cos θ0 is
triggered. From Proposition 2 and the hypothesis that θ(T3 ) =
θ0 < θ∗ , we have
ρ0 ≥ L cos θ0 > L cos θ∗ ≥ ρ∗ .
From Lemma 6, ρ∗1 (θ0 ) > ρ0 and ∂F1 (ρ, θ0 )/∂ρ < 0 for ρ0 ≥
ρ ≥ ρ∗ . As a result,
F1 (ρ0 , θ0 ) < F1 (ρ∗ , θ0 ) < F1 (ρ∗ , θ∗ )

(33)

where the second inequality is from Lemma 4.
From Lemma 5, there exists τ ≤ T3 , such that
(ρ(τ ), θ(τ )) ∈ P1+ and F1 (ρ(τ ), θ(τ )) = F1 (ρ0 , θ0 ) <
F1 (ρ∗ , θ∗ ), which contradicts to the hypothesis that (ρ∗ , θ∗ )
is the solution to (26). Therefore, the stopping criterion
ρ(T3 ) = ρ0 ≥ L cos θ0 is not satisfied either.
To conclude, since neither of the stopping criteria is triggered, by contradiction, the algorithm can only stop at θ(T3 ) ≥
θ∗ .
Note that the trajectory from Step 3) is continuous. Suppose
that the trajectory reaches θ∗ at time t1 , i.e., θ(t1 ) = θ∗ and
θ(t) ≤ θ∗ for all t ≤ t1 . It holds that (ρ(t1 ), θ(t1 )) ∈ P1+ as
stated in the following lemma.

PREPRINT VERSION

12

Lemma 8. The algorithm trajectory satisfies (ρ(t1 ), θ(t1 )) ∈
P1+ , where t1 ≥ 0 satisfies θ(t1 ) = θ∗ and θ(t) ≤ θ∗ for
t < t1 .
Proof. We note that ρ(t1 ) ≤ ρ∗ . This is because if
ρ(t1 ) > ρ∗ , we must have F1 (ρ(t1 ), θ∗ ) < F1 (ρ∗ , θ∗ ),
since ∂F1 (ρ, θ∗ )/∂ρ < 0 for all ρ(t1 ) > ρ > ρ∗ as from
Lemma 6. As a result of Lemma 5, there exists τ ≤ t1 ,
such that F1 (ρ(τ ), θ(τ )) = F1 (ρ(t1 ), θ∗ ) < F1 (ρ∗ , θ∗ ) and
(ρ(τ ), θ(τ )) ∈ P1+ , which contradicts to the assumption that
(ρ∗ , θ∗ ) is the solution to (26).
As (ρ∗ , θ∗ ) ∈ P1+ , from the nested segmented propagation
property (3) – (4), we can conclude that (ρ(t1 ), θ(t1 )) ∈ P1+ .
Since (ρ(t1 ), θ(t1 )) ∈ P1+ , ρ(t) will increase to ρ∗ following Step 3a) in Algorithm 1. This completes the proof that the
algorithm trajectory passes through (ρ(t2 ), θ(t2 )) = (ρ∗ , θ∗ )
at time t2 , where t1 ≤ t2 ≤ T3 .
A PPENDIX D
P ROOF OF T HEOREM 1 UNDER A G ENERAL N UMBER OF K
A. The Main Proof
We first establish the following result.
Lemma 9 (Local Optimality after k Loops). After the kth loop
of Steps 2) – 4) in Algorithm 1 is completed at time t = Tk ,
the following holds,
Fmin (Tk ) ≤ minimize

θ≥0,(ρ,θ)∈Pk

Fk (ρ, θ)

(34)

for all k = 1, 2, . . . , K − 1. Moreover, (34) holds for k = K
when the entire algorithm terminates.
Theorem 1 is a direct result from Lemma 9, since (34) holds
for k = 1, 2, . . . , K and Fmin (t) is non-increasing, which
implies that Fmin (TK ) is the global minimum value of P 0
and (ρ̂(TK ), θ̂(TK )) is the globally optimal solution to P 0 .
B. Proof of Lemma 9
For the kth search trajectory from Steps 2) – 4) in Algorithm
1 in the case K > 2, the iteration is equivalent to that in the
two segment case, K = 2. Specifically, the virtual propagation
segment partition (D̃k , D̃kc ) in the kth outer loop for the case
K > 2 corresponds to the LOS-NLOS partition (D1 , D2 ) for
the K = 2 case. Moreover, the function Fk in the kth outer
loop in for the case K > 2 corresponds to the function F1
for the K = 2 case. Hence, using Lemma 3, Steps 2) – 4)
equivalently solve
Pk0 :
Sk

minimize
ek
θ≥0,(ρ,θ)∈P

Fk (ρ, θ)

(35)

where P̃k , j=1 Pj .
Denote the optimal solution to Pk0 as (ρ̂(k) , θ̂(k) ). The
remaining part of the proof proceeds using induction.
First of all, we know that for k = 1, inequality (34) is true
e1 = P1 .
due to Lemma 3, since P
Second, suppose that inequality (34) is true for i =
1, 2, . . . , k − 1, where 1 < k ≤ K − 1. The argument can
be divided into two cases:

1) If (ρ̂(k) , θ̂(k) ) ∈ Pk , then (34) is true because Pk ⊆ P̃k .
2) If (ρ̂(k) , θ̂(k)
/ Pk , then it holds that (ρ̂(k) , θ̂(k) ) ∈
S) ∈
e
Pk \Pk = i<k Pi . Without loss of generality (w.l.o.g.),
assume that (ρ̂(k) , θ̂(k) ) ∈ Pj for some j ≤ k − 1. We
thus have
minimize

Fk (ρ, θ)

ek
θ≥0,(ρ,θ)∈P

= Fk (ρ̂(k) , θ̂(k) )
≥ Fj (ρ̂

(k)

, θ̂

(k)

≥ minimize

ej
θ≥0,(ρ,θ)∈P

(36)
(37)

)
Fj (ρ, θ)

≥ Fmin (Tj )

≥ Fmin (Tk )

(38)
(39)
(40)

where inequality (37) is from Lemma 1 in Appendix
A, inequality (38) is due to assumption (ρ̂(k) , θ̂(k) ) ∈
Pj ⊆ P̃j , and inequality (40) is due to Tj ≤ Tk for
j < k and Fmin (t) is a non-increasing process. This
shows that inequality (34) is also true for k.
Therefore, by induction, inequality (34) is true for all k =
1, 2, . . . , K − 1.
Finally, the last step in Algorithm 1 yields
Fmin ≤ FK (ρ∗K (0), 0)

≤ minimizeπ FK (ρ, θ)
ρ≥0,0<θ≤ 2

(41)

≤ minimize FK (ρ, θ)
θ≥0,(ρ,θ)∈PK

where inequality (41) is from Lemma 4.
As a result from the above three paragraphs, (34) holds for
all k = 1, 2, . . . , K.
A PPENDIX E
P ROOF OF T HEOREM 2
An important property of Algorithm 1 is that the segment
of search trajectory in Step 3) does not “turn back”, and so
does that in Step 4).
Lemma 10 (Monotonicity). Step 3) in Algorithm 1 strictly
and monotonically increases ρ(t), and it also monotonically
increases |θ(t)|. Similar property holds in Step 4).

Proof. In Step 3a), ρ(t) strictly and monotonically increases,
while θ(t) keeps unchanged. In Step 3b), we have (omitting
the higher order term)
ρ + ∆ρ = kx + ∆x − xu k
p
= kx − xu k2 + 2(x − xu )T ∆x + k∆xk2


1
= ρ 1 + 2 (x − xu )T ∆x + o(kxk)
ρ

and since (x − xu )/ρ = M(θ)u from (7), we have
∆ρ = uT M(θ)T ∆x

= uT M(θ)T M(θ)uγ
+ γρuT M(θ)T

 ∂F −1 ∂F
d
k
k
M(θ)u −
dθ
∂θ
∂ρ

PREPRINT VERSION
PREPRINT

Figure 7.
7. Search
Figure
Search region
region and
and search
search trajectory,
trajectory, where
where point
point aa denotes
denotes user,
user,
point cc denotes
denotes the
the BS,
BS, and
and point
point dd denotes
denotes UAV
UAV at
point
at the
the boundary
boundary of
of the
the
search area.
area.
search

which
equals Step
to γ, 3b)
being
strictly
positive.
Therefore,
Step
3)
In addition,
moves
on the
contour
of Fk (ρ, θ)
= C,
strictly
increases
ρ(t).
whose dynamics is give by
In addition, Step 3b) moves on the contour of Fk (ρ, θ) = C,
∂Fkis(ρ,
θ) by ∂Fk (ρ, θ)
whose dynamics
give
dρ +
dθ = 0
∂ρ
∂θ
∂Fk (ρ, θ)
∂Fk (ρ, θ)
dρ +
dθ = 0 to Lemma 6
in which ∂Fk (ρ(t),
0 according
∂ρθ(t))/∂ρ ≤ ∂θ
(with a straight-forward generalization from F1 to Fk ) and
in which ∂F (ρ(t), θ(t))/∂ρ ≤ 0 according to Lemma 6
∂Fk (ρ, θ)/∂|θ|k > 0 according to Lemma 4. As a result, Step
(with a straight-forward generalization from F1 to Fk ) and
3b) monotonically increases |θ(t)|.
∂Fk (ρ, θ)/∂|θ| > 0 according to Lemma 4. As a result, Step
We now show that the boundary of the search region P
3b) monotonically increases |θ(t)|.
in (17) for the θ > 0 branch is given by a semi-circle as
illustrated
Fig. that
7 (the
semi-circle).
To seeregion
this, we
We nowinshow
the blue
boundary
of the search
P
first
noteforthat
boundary
for θby>a 0semi-circle
is given by
in (17)
thethe
θ >
0 branchofisPgiven
as
(ρ
cos θ, ρ sin
= Lsemi-circle).
cos θ and 0To≤see
θ this,
≤ π/2.
illustrated
in θ),
Fig.where
7 (theρ blue
we
first note that
boundary
ad =the
L cos
θ, ac = of
L, P for θ > 0 is given by
Therefore,
(ρ cos θ, ρ sin!
θ), where
ρ = 2L cos θ and 0 ≤ θ 2≤ π/2.
2
dc =
Therefore,
ad =(L
L cos
cos θ,θ −
acL)
= L,+ (L cos θ sin θ − 0)
p
2
2
2
which yields
+ (dc)
= 2(ac)
, and
point
2 θ − L)
dc = (ad)
(L cos
+ (L
cos θhence
sin θ −
0)2 d is on
the semi-circle with the diameter given by line segment ac.
2
2
= (ac)in
, and
hence10,
point
is on
which
(ad)2 + (dc)
Fromyields
the monotone
property
Lemma
the dsearch
the
semi-circle
with
the
diameter
given
by
line
segment
trajectory is a convex curve starting from point a at the ac.
user
theat the
monotone
property
in Lemma
andFrom
ending
semi-circle,
e.g., point
d. Note10,
thatthe
the search
length
˘convex
trajectory
is aad
of
any curve
is lesscurve
than starting from point a at the user
and ending at the semi-circle, e.g.,
point d. Note that the length
L cos2 θ + L cos θ sin θ
˘+
of any curve ab
ad
is bd
less=than
2
where the maximum
value
≤ θθsin<θ π/2 can be
ab + bd =
L cosover
θ +0L cos
numerically evaluated to be roughly 1.2L.
where
the maximum
< π/2axis
canwith
be
Algorithm
1 consists value
of the over
search0 on≤theθ BS-user
numerically
evaluated
to K
be−roughly
maximum
length
L, and
1 loops1.2L.
for the off-BS-user axis
Algorithm
1 consists
of the
search
the BS-user
searches,
where
each loop
consists
ofon
searches
on theaxis
leftwith
and
maximum
length
L, with
and K
− 1 loopslength
for the1.2L.
off-BS-user
axis
right
branches
each
maximum
As a result,
searches,
where of
each
consists
of searches
on bounded
the left and
the
total length
theloop
search
trajectory
is upper
by
right branches
(2.4K
− 1.4)L.each with maximum length 1.2L. As a result,
the total length of the search trajectory is upper bounded by
(2.4K − 1.4)L.
R EFERENCES

[1] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with
R EFERENCES
unmanned aerial vehicles: opportunities and challenges,” IEEE Commun.
Mag.,
vol.
54,
no.
5,
pp.
2016. “Wireless communications with
[1] Y. Zeng, R. Zhang, and36–42,
T. J. Lim,
[2] M.
Mozaffari,
W.vehicles:
Saad, M.opportunities
Bennis, andand
M. challenges,”
Debbah, “Unmanned
aerial
unmanned
aerial
IEEE Commun.
vehicle
with54,underlaid
Mag., vol.
no. 5, pp.device-to-device
36–42, 2016. communications: Performance
tradeoffs,” IEEE
Trans.
Commun.,
vol. 15,
no. 6, pp. 3949–
[2] and
M. Mozaffari,
W. Saad,
M. Wireless
Bennis, and
M. Debbah,
“Unmanned
aerial
3963,
vehicle2016.
with underlaid device-to-device communications: Performance
[3] Z.
P. Xia,IEEE
and X.-G.
“Enabling
UAV vol.
cellular
with6,millimeterandXiao,
tradeoffs,”
Trans.Xia,
Wireless
Commun.,
15, no.
pp. 3949–
wave
Potentials and approaches,” IEEE Commun. Mag.,
3963,communication:
2016.
54, no.
5, pp.
[3] vol.
Z. Xiao,
P. Xia,
and66–73,
X.-G. 2016.
Xia, “Enabling UAV cellular with millimeter[4] B.
Vancommunication:
Der Bergh, A. Chiumento,
andapproaches,”
S. Pollin, “LTE
inCommun.
the sky: trading
wave
Potentials and
IEEE
Mag.,
off
benefits
with
interference costs for aerial nodes,” IEEE
vol.propagation
54, no. 5, pp.
66–73,
2016.
Commun. Mag., vol. 54, no. 5, pp. 44–50, 2016.

13
13

[4]
Der Bergh,
and S.assisted
Pollin, “LTE
in the sky:networks
trading
[5] B.
A. Van
Merwaday
andA.I. Chiumento,
Guvenc, “UAV
heterogeneous
off
benefits
with interference
costs for
aerial Commun.
nodes,” IEEE
for propagation
public safety
communications,”
in Proc.
Wireless
and
Commun.
Mag.,
vol.
54, no. 5, 2015,
pp. 44–50,
2016.
Networking
Conf.
Workshops,
pp. 329–334.
[5]
Merwaday
and I.T. Guvenc,
“UAVand
assisted
networks
[6] A.
D.-T.
Ho, P. Sujit,
A. Johansen,
J. B. heterogeneous
De Sousa, “Performance
for
public safety
communications,”
Proc. swarm
Wirelessoptimization
Commun. and
evaluation
of cooperative
relay and in
particle
path
Networking
2015,
pp.network,”
329–334. in Proc. IEEE Globeplanning forConf.
UAVWorkshops,
and wireless
sensor
[6] D.-T.
Ho, P. Sujit,2013,
T. A.pp.
Johansen,
and J. B. De Sousa, “Performance
com Workshops,
1403–1408.
cooperative
relay
particle
swarm optimization
path
[7] evaluation
V. Sharma,ofM.
Bennis, and
R. and
Kumar,
“UAV-assisted
heterogeneous
planning
andenhancement,”
wireless sensorIEEE
network,”
in Proc.
Globenetworks for
for UAV
capacity
Commun.
Lett., IEEE
vol. 20,
no. 6,
com
Workshops, 2016.
2013, pp. 1403–1408.
pp. 1207–1210,
[7]
“UAV-assistedofheterogeneous
[8] V.
O. Sharma,
Jian, Z. M.
Yi, Bennis,
L. Min,and
andR. L.Kumar,
Jia, “Optimization
beamforming
networks
capacity
Commun.
vol. 20,Chinese
no. 6,
and path for
planning
forenhancement,”
UAV-assistedIEEE
wireless
relay Lett.,
networks,”
pp.
1207–1210,
2016. vol. 27, no. 2, pp. 313–320, 2014.
Journal
of Aeronautics,
[8]
Jian,Y.Z.
L. Min,
Jia, “Optimization
of beamforming
[9] O.
Y. Jin,
D. Yi,
Zhang,
and B.and
K. L.
Chalise,
“Joint optimization
of relay poand
path
for UAV-assisted
wireless
relay networks,”
Chinese
sition
andplanning
power allocation
in cooperative
broadcast
wireless networks,”
Journal
of
Aeronautics,
vol.
27,
no.
2,
pp.
313–320,
2014.
in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, 2012,
[9] Y.
Y. D. Zhang, and B. K. Chalise, “Joint optimization of relay popp.Jin,
2493–2496.
sition
and
power
broadcast wirelessmaneuvering
networks,”
[10] D. H. Choi,
B. H.allocation
Jung, andinD.cooperative
K. Sung, “Low-complexity
in
Proc. IEEE
Int. Conf. Acoustics,
Speech,
and Signal
Processing,
2012,
control
of a UAV-based
relay without
location
information
of mobile
pp.
2493–2496.
ground
nodes,” in Proc. IEEE Symposium on Computers and Commun.,
[10] D.
H. Choi,
B. H. Jung, and D. K. Sung, “Low-complexity maneuvering
2014,
pp. 1–6.
control of a UAV-based relay without location information of mobile
[11] A. Chamseddine, G. Charland-Arcand, O. Akhrif, S. Gagné, F. Gagnon,
ground nodes,” in Proc. IEEE Symposium on Computers and Commun.,
and D. Couillard, “Optimal position seeking for unmanned aerial vehicle
2014, pp. 1–6.
communication relay using only signal strength and angle of arrival,” in
[11] A. Chamseddine, G. Charland-Arcand, O. Akhrif, S. Gagné, F. Gagnon,
IEEE Conf. on Decision and Control, Dec 2014, pp. 976–981.
and D. Couillard, “Optimal position seeking for unmanned aerial vehicle
[12] F. Jiang and A. L. Swindlehurst, “Optimization of UAV heading for the
communication relay using only signal strength and angle of arrival,” in
ground-to-air uplink,” IEEE J. Sel. Areas Commun., vol. 30, no. 5, pp.
IEEE Conf. on Decision and Control, Dec 2014, pp. 976–981.
993–1005, 2012.
[12] F. Jiang and A. L. Swindlehurst, “Optimization of UAV heading for the
[13] A. Al-Hourani, S. Kandeepan, and A. Jamalipour, “Modeling air-toground-to-air uplink,” IEEE J. Sel. Areas Commun., vol. 30, no. 5, pp.
ground path loss for low altitude platforms in urban environments,” in
993–1005, 2012.
Proc. IEEE Global Telecomm. Conf., 2014, pp. 2898–2904.
[13] A. Al-Hourani, S. Kandeepan, and A. Jamalipour, “Modeling air-to[14] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Drone small cells
ground path loss for low altitude platforms in urban environments,” in
in the clouds: Design, deployment and performance analysis,” in Proc.
Proc. IEEE Global Telecomm. Conf., 2014, pp. 2898–2904.
IEEE
Global Telecomm.
Conf.,
2015,
[14] M.
Mozaffari,
W. Saad, M.
Bennis,
andpp.
M.1–6.
Debbah, “Drone small cells
[15] in
A.the
Hourani,
Sithamparanathan,
S. Lardner,
“Optimal
LAP
clouds: K.
Design,
deployment andand
performance
analysis,”
in Proc.
altitude
for
maximum
coverage,”
IEEE
Commun.
Lett., no. 99, pp. 1–4,
IEEE Global Telecomm. Conf., 2015, pp. 1–6.
2014.
[15] A.
Hourani, K. Sithamparanathan, and S. Lardner, “Optimal LAP
[16] altitude
M. Mozaffari,
W. Saad,
M. Bennis,
andCommun.
M. Debbah,
transport
for maximum
coverage,”
IEEE
Lett.,“Optimal
no. 99, pp.
1–4,
theory
2014. for power-efficient deployment of unmanned aerial vehicles,” in
Proc.
IEEE
Int.
Conf.
Commun.,
Kuala
Lumpur,
Malaysia,
May
2016,
[16] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Optimal transport
pp. 1–6.
theory
for power-efficient deployment of unmanned aerial vehicles,” in
[17] Proc.
——, IEEE
“Efficient
deployment
of multiple
unmanned
aerial vehicles
for
Int. Conf.
Commun.,
Kuala Lumpur,
Malaysia,
May 2016,
optimal
pp. 1–6. wireless coverage,” IEEE Commun. Lett., vol. 20, no. 8, 2016.
[18] ——,
Q. Feng,
J. McGeehan,
E. K.ofTameh,
andunmanned
A. R. Nix,aerial
“Pathvehicles
loss models
[17]
“Efficient
deployment
multiple
for
for air-to-ground
radio channels
urban environments,”
IEEE
optimal
wireless coverage,”
IEEEinCommun.
Lett., vol. 20,inno.Proc.
8, 2016.
Semiannual
Veh. Technol.
Conf.,
vol. and
6, 2006,
[18] Q.
Feng, J. McGeehan,
E. K.
Tameh,
A. R.pp.
Nix,2901–2905.
“Path loss models
[19] for
J. Chen
and D. Gesbert,
“Joint user
grouping
and beamforming
low
air-to-ground
radio channels
in urban
environments,”
in Proc.for
IEEE
complexity massive
MIMO
systems,”
IEEEpp.
Int.2901–2905.
Workshop on Signal
Semiannual
Veh. Technol.
Conf.,
vol. 6,in2006,
Process.
Advances
in Wireless
Edinburg,
UK, May 2016,
pp.
[19] J.
Chen and
D. Gesbert,
“Joint Commun.,
user grouping
and beamforming
for low
1–6.
complexity
massive MIMO systems,” in IEEE Int. Workshop on Signal
[20] Process.
T. Bai and
R. W. Heath,
“Coverage
and rate
analysisUK,
for millimeter-wave
Advances
in Wireless
Commun.,
Edinburg,
May 2016, pp.
cellular networks,” IEEE Trans. Wireless Commun., vol. 14, no. 2, pp.
1–6.
1100–1114,
[20] T.
Bai and R.2015.
W. Heath, “Coverage and rate analysis for millimeter-wave
[21] cellular
J. Chen,networks,”
U. Yatnalli,
andTrans.
D. Gesbert,
“Learning
radio
for2,UAVIEEE
Wireless
Commun.,
vol.maps
14, no.
pp.
aided wireless
networks: A segmented regression approach,” in Proc.
1100–1114,
2015.
IEEE
Int.U.Conf.
Commun.,
France,
May 2017.
[21] J.
Chen,
Yatnalli,
and D.Paris,
Gesbert,
“Learning
radio maps for UAV[22] aided
J. Chen,
O. Esrafilian,
D. Gesbert,
and U.regression
Mitra, “Efficient
algorithms
for
wireless
networks:
A segmented
approach,”
in Proc.
air-to-ground
channel
reconstruction
in UAV-aided
IEEE
Int. Conf.
Commun.,
Paris, France,
May 2017.communications,” in
Proc.
IEEE
Global Telecomm.
Conf.,
Dec.
2017,
Wi-UAV
workshop.
[22] J.
Chen,
O. Esrafilian,
D. Gesbert,
and U.
Mitra,
“Efficient
algorithms
for
[23] air-to-ground
R. U. Nabar, H.
Bolcskei,
and F. W. Kneubuhler,
“Fading
relay channels:
channel
reconstruction
in UAV-aided
communications,”
in
Performance
limits Telecomm.
and space-time
design,”
IEEE workshop.
J. Sel. Areas
Proc.
IEEE Global
Conf.,signal
Dec. 2017,
Wi-UAV
Commun.,
no. 6,and
pp. F.1099–1109,
2004.“Fading relay channels:
[23] R.
U. Nabar,vol.
H. 22,
Bolcskei,
W. Kneubuhler,
[24] Performance
J. N. Laneman,
D. and
N. Tse,
and G. signal
W. Wornell,
“Cooperative
limits
space-time
design,”
IEEE J. Sel.diversity
Areas
in wirelessvol.
networks:
Efficient
protocols 2004.
and outage behavior,” IEEE
Commun.,
22, no. 6,
pp. 1099–1109,
Trans.
Inf. Theory,
vol.Tse,
50, and
no. 12,
pp. Wornell,
3062–3080,
2004.
[24] J.
N. Laneman,
D. N.
G. W.
“Cooperative
diversity
[25] in
T. wireless
Wang, A.
Cano, G.
B. Giannakis,
J. N. Laneman,
networks:
Efficient
protocols and
and outage
behavior,” “HighIEEE
performance
cooperative
with decode-and-forward
reTrans.
Inf. Theory,
vol. 50, demodulation
no. 12, pp. 3062–3080,
2004.
lays,”
IEEEA.Trans.
vol. 55, no.and
7, pp.
1427–1438,
[25] T.
Wang,
Cano,Commun.,
G. B. Giannakis,
J. N.
Laneman,2007.
“High[26] performance
“Winner II interim
channeldemodulation
models,” Tech.with
Rep.decode-and-forward
IST-4-027756 WINNER
cooperative
reII D1.1.2
Sept.
2007. vol. 55, no. 7, pp. 1427–1438, 2007.
lays,”
IEEEv1.2,
Trans.
Commun.,
[26] “Winner II interim channel models,” Tech. Rep. IST-4-027756 WINNER
II D1.1.2 v1.2, Sept. 2007.

