Joint 3-D Positioning and Power Allocation for UAV Relay Aided by Geographic Information

To distinguish different propagation scenarios, the key is to identify whether the communication link is blocked by buildings. For $M$ buildings, $M$ and $MK$ blocked regions are generated with respect to the BS and $K$ UEs, respectively. We index these blocked regions as $\mathcal{I}\triangleq\{1,...,M+MK\}$. In this paper, we assume that the shape of all the buildings is cube²²2For other types of building, we can always find a cube envelope which covers the building, and thus the proposed solution is workable.. We show that giving building and UE/BS locations, the blocked region can be formulated as a polyhedron.

On one hand, accurate state of NLoS components for BS-UAV/UAV-UE links is difficult to predict in practice, unless the UAV is deployed at a given fixed position and channel estimation is performed. On the other hand, the NLoS environment leads to dramatic deterioration of communication performance. Therefore, it is preferred to avoiding all blocked regions ($\mathcal{D}_{i},i\in\mathcal{I}$) to guarantee the overall performance. Let $\mathcal{D}=\{\mathbf{x}=(x_{\mathrm{V}},y_{\mathrm{V}},h_{\mathrm{V}})|x_{\mathrm{V}}\in[0,x_{\mathrm{D}}],y_{\mathrm{V}}\in[0,y_{\mathrm{D}}],h_{\mathrm{V}}\geq h_{\mathrm{min}}\}$ denote the whole considered region, then the position of the UAV relay should be restricted by

Under constraint (2), the LoS propagation environment is always guaranteed for the BS-UAV and UAV-UE links⁴⁴4We assume that all UEs are located at areas without buildings. Therefore, the feasible region for UAV positioning is nonempty as there always exists an unblocked region for sufficient high altitude of the UAV relay.. In this way, LoS channel models are adopted for UAV positioning design, while NLoS channels are not necessary in the design but required in the simulations. Since the UAV positioning should be optimized in a relatively large timescale, we mainly focus on the large-scale channel characteristics. The distance from the BS to the UAV relay is $\|\mathbf{x}-\mathbf{x}_{\mathrm{B}}\|$, and the distance from the UAV relay to UE $k$ is $\|\mathbf{x}-\mathbf{x}_{k}\|$. Then the channel gains of BS-UAV and UAV-UE links are respectively given by

where $\alpha_{1}$ is the path loss exponent, and $\beta_{1}$ is the channel gain at reference distance of $1$ m.

As a result, we obtain the communication capacities of the BS-UAV link and the UAV-UE link as follows:

where $W_{\mathrm{B}}$ and $W_{\mathrm{U}}$ denote the channel bandwidths of links from the BS to the UAV and from the UAV to UE $k$, respectively. $P_{\mathrm{B}}$ denotes the transmit power of BS, and $P_{k}$ is the transmit power of the UAV allocated to UE $k$. $N_{0}$ is the power spectral density of additive white Gaussian noise.

To ensure the fairness, we aim to maximize the minimum communication capacity among all the UEs by jointly optimizing the UAV positioning and the power allocation, subject to the blockage effect of buildings, and the backhaul constraint. The problem is formulated as

where $R$ denotes the minimum communication capacity among all the UEs. Constraint (2) confines that the UAV has to be deployed to avoid all the blocked regions for the BS-UAV and UAV-UE links. Constraint (7a) indicates that the minimum communication capacity does not exceed the communication capacity of each UAV-UE link. Constraint (7b) ensures that the BS-UAV backhaul link is capable to support all UEs with the minimum communication capacity. Constraints (7c), (7d), and (7e) indicate that the transmit powers are nonnegative and do not exceed a maximum value, where $P_{\mathrm{B}}^{\mathrm{tot}}$ and $P_{\mathrm{V}}^{\mathrm{tot}}$ are the maximum transmit powers of the BS and the UAV relay, respectively.

To make constraint (2) more tractable, we introduce auxiliary binary variable $l_{ij}$ and provide the following theorem.

According to Theorem 1, constraint (2) is equivalent to the following mixed integer linear constraints:

where $C$ is a sufficiently large constant.

By replacing constraint (2) with constraints (9)–(12), problem (7) is equivalent to

Due to the non-convexity of constraints (7a), (7b) and binary constraint (10), problem (13) is a non-convex and mixed-integer problem, which is difficult to obtain a globally optimal solution. Therefore, we propose to utilize Lagrangian relaxation [33]. First, binary constraint (10) can be equivalently replaced by

In this way, $l_{ij}$ becomes a continuous optimization variable between 0 and 1. By replacing constraint (10) with constraints (14) and (15), and then dualizing and penalizing constraint (15) into the objective function with Lagrangian multipliers $\lambda_{i}$ for $i\in\mathcal{I}$, we obtain a Lagrangian problem

Comparing Lagrangian problem (16) with original problem (13), we have the following Lemma.

To decrease the duality gap between Lagrangian problem (16) and original problem (13) and obtain a good feasible solution to original problem (13), we develop a two-loop optimization framework to adaptively determine the values of Lagrangian multipliers as well as the UAV positioning and power allocation.

For the $T$-th outer-loop, given Lagrangian multipliers $\{\lambda_{i}^{(T)}\}$, we develop an iterative algorithm to solve Lagrangian problem (16). For the $t$-th iteration of the inner-loop, given UAV’s position $\mathbf{x}^{(t)}$ and auxiliary variables $\{l_{ij}^{(t)}\}$, problem (16) is transformed to the following power allocation problem

where $\eta_{k}^{(t)}=\beta_{1}/(N_{0}W_{\mathrm{U}}\|\mathbf{x}^{(t)}-\mathbf{x}_{k}\|^{\alpha_{1}})$ and $\eta_{\mathrm{B}}^{(t)}=\beta_{1}/(N_{0}W_{\mathrm{B}}\|\mathbf{x}^{(t)}-\mathbf{x}_{\mathrm{B}}\|^{\alpha_{1}})$ are intermediate parameters for notational simplicity. The second term in the objective function is a constant which does not impact the optimality.

Problem (17) is a convex problem with respect to $P_{\mathrm{B}}$ and $\{P_{k}\}$ [37, 38]. To maximize the minimum communication capacity with minimal transmit powers, we provide the following theorem.

Hereto, we have obtained the optimal solution for the power allocation sub-problem.

Given the power allocation $\{P_{k}^{(t+1)}\}$ and $P_{\mathrm{B}}^{(t+1)}$, problem (16) is transformed to the following positioning problem

where $\zeta_{k}^{(t)}=\frac{P_{k}^{(t+1)}\beta_{1}}{N_{0}W_{\mathrm{U}}}$ and $\zeta_{\mathrm{B}}^{(t)}=\frac{P_{\mathrm{B}}^{(t+1)}\beta_{1}}{N_{0}W_{\mathrm{B}}}$ are intermediate parameters for notational simplicity. Problem (19) is not a concave/convex problem because of the non-concave objective function and the non-convex constraints in (19a) and (19b). In the following, we employ the SCA technique to obtain a sub-optimal solution.

Considering the objective function, for a given local point $l_{ij}^{(t)}$ in the $t$-th iteration, we have the following lower bound on $(l_{ij})^{2}$:

Considering constraints (19a) and (19b), note that function $r(z)=\log_{2}\left(1+1/z^{\alpha_{1}}\right)$ is convex with respect to $z$ for $z>0$, thus the right-hand-side (RHS) of constraint (19a) and the RHS of constraint (19b) are convex with respect to $\|\mathbf{x}-\mathbf{x}_{k}\|$ and $\|\mathbf{x}-\mathbf{x}_{\mathrm{B}}\|$, respectively. For a given local point $\mathbf{x}^{(t)}$ in the $t$-th iteration, the RHS of constraint (19a) is lower-bounded by its first-order Taylor expansion at $\|\mathbf{x}^{(t)}-\mathbf{x}_{k}\|$ as

with

The RHS of constraint (19b) is lower-bounded by its first-order Taylor expansion at $\|\mathbf{x}^{(t)}-\mathbf{x}_{\mathrm{B}}\|$ as

with

As a result, given local points $\mathbf{x}^{(t)}$ and $\{l_{ij}^{(t)}\}$ in the $t$-th iteration, problem (19) is relaxed as

It is easy to verify that problem (27) is a convex problem and can be readily solved by standard convex program solvers, such as CVXPY [38, 39]. The objective function of problem (27) is a lower bound on the objective function of problem (19). Constraints (27a) and (27b) have tighter forms compared to constraints (19a) and (19b). Hance, any feasible solution of problem (27) is also feasible for problem (19). Constraint (27c) is introduced to limit the update of $\mathbf{x}^{(t+1)}$ in a small neighborhood around the local point $\mathbf{x}^{(t)}$. $\rho^{(t)}$ is the radius of the spherical region and is gradually reduced during the iteration to ensure convergence. A feasible way to update $\rho^{(t)}$ is $\rho^{(t+1)}=\kappa_{1}\rho^{(t)}$, where $\kappa_{1}<1$ is the stepsize.

To decrease the duality gap between Lagrangian problem (16) and original problem (13), the Lagrangian multipliers need to be adjusted. This is actually a dual problem with respect to Lagrangian multipliers, which can be optimized by the gradient method [40]. For the $T$-th outer-loop, we have gotten the converged solution to Lagrangian problem (16) for given $\{\lambda_{i}^{(T)}\}$ by inner-loop iterations, denoted by $\bar{\mathbf{x}}^{(T)}$, $\{\bar{l}_{ij}^{(T)}\}$, $\bar{P}_{\rm{B}}^{(T)}$ and $\{\bar{P}_{{i}}^{(T)}\}$. Then the multiplier $\lambda_{i}$ is updated by using the following formula [33]:

where $\gamma^{(T)}$ is the stepsize formulated as

where $q_{\rm{U}}^{(T)}$ is the objective value of Lagrangian problem (16) at the $T$-th outer-loop, $q_{\rm{L}}^{(T)}$ is the objective value of original problem (13). The denominator is the sum square of the gradients. $\mu^{(T)}$ is an adaption parameter which is determined by setting $\mu^{(0)}=2$ and halving $\mu^{(T)}$ whenever $q_{\rm{U}}^{(T)}$ fails to decrease in the previous iteration. If the solution to Lagrangian problem (16) is not feasible for original problem (13), which means the BS-UAV link or UAV-UE link is blocked, $q_{\rm{L}}^{(T)}$ is estimated to be zero. Otherwise, $q_{\rm{L}}^{(T)}$ is set to be the corresponding communication capacity by substituting the solution into original problem (13).

It can be seen that (28) results an increase update direction for $\lambda_{i}$. In general, large $\lambda_{i}$ leads to small violation of constraint (15) [40]. However, it is not effective to initially set $\lambda_{i}$ to be a vary large value, since the objective will be dominated by the penalty term $-\sum_{i\in\mathcal{I}}\lambda_{i}\sum_{j\in\mathcal{J}_{i}}l_{ij}(1-l_{ij})$ and the minimum communication capacity $R$ will be diminished. In contrast, initializing $\lambda_{i}$ with a small value will provide enough degree of freedom for UAV positioning to obtain a good starting point. Then, by gradually increasing the value of $\lambda_{i}$ via (28), the upper bound given by Lagrangian problem (16) can be gradually strengthened. Ultimately, constraint (15) is satisfied, which means that the UAV is positioned in a region without any building blockage. In this way, the solution to Lagrangian problem (16) is also feasible for original problem (13), and the gap between the two problem is decreased to zero.

The overall solution of the algorithm is summarized in Algorithm 2. In Line 1, we invoke Algorithm 1 to calculate the blocked regions for the BS and $K$ UEs caused by $M$ buildings based on geographic information. Then, in Lines 3-14, we employ the Lagrangian relaxation framework and update the Lagrangian multipliers $\{\lambda_{i}\}$ in an iterative way. Lines 5-10 solve Lagrangian problem (16) with given $\{\lambda_{i}^{(T)}\}$, where the power allocation and UAV positioning are optimized in an alternate manner. The inner-loop terminates, when the increase of the objective value of problem (27) from one iteration to the next falls bellow a threshold $\epsilon_{\mathrm{t}}$ or the number of iterations exceeds the maximum value $L_{\mathrm{t,max}}$. The outer-loop terminates, when the difference between the objective value of problem (16) $q_{\rm{U}}^{(T)}$ and the objective value of problem (13) $q_{\rm{L}}^{(T)}$ falls bellow a threshold $\epsilon_{\mathrm{T}}$ or the number of iterations exceeds the maximum value $L_{\mathrm{T,max}}$.

In the proposed joint UAV positioning and power allocation algorithm, Line 1 in Algorithm 2 needs to calculate $(M+KM)$ blocked regions, which entails a computational complexity of $\mathcal{O}\left(KM\right)$. The main computational complexity of Lines 5-10 comes from solving positioning sub-problem (27), whose complexity is $\mathcal{O}\left((KM)^{3.5}\right)$ by using the interior point method [32]. Line 12 needs to estimate whether the solution of Lagrangian problem (16) is feasible for the original problem (7), i.e., whether the UAV’s position is out of all the $(M+KM)$ blocked regions, which entails a computational complexity of $\mathcal{O}\left(KM\right)$. As a result, the overall computational complexity of Algorithm 2 is $\mathcal{O}\left(L_{\mathrm{T,max}}L_{\mathrm{t,max}}\left(KM\right)^{3.5}\right).$

As we can see, the overall computational complexity comes from involving auxiliary variables $\{l_{ij}\}$ to tackle the $(M+KM)$ blocked regions, i.e., constraint (2). In practice, due to the hardware and power constraints, the coverage area of a single UAV relay is usually small. Thus, the number of blocked regions may not be very large. Even for a typical area of interest that may consist of a lager number of structures, the proposed solution can also be used by dividing the target area into multiple sub-regions and employing multiple UAV relays for coverage. With this implementation, the number of blocked regions is reduced. On the other hand, if a single UAV has to be utilized to cover a large area with many structures (although this rarely happens), we may use the following way to decrease the computational complexity. Constraint (2) can be rewritten in equivalent form as $\mathbf{x}\in\mathcal{D}\setminus\left(\bigcup_{i\in\mathcal{I}}\mathcal{D}_{i}\right)$. Note that if there exist a $j\in\mathcal{I}$ and a $k\in\mathcal{I}$ ($j\neq k$) such that $\mathcal{D}_{j}\subseteq\mathcal{D}_{k}$, then we have $\bigcup_{i\in\mathcal{I}}\mathcal{D}_{i}=\bigcup_{i\in\mathcal{I},i\neq j}\mathcal{D}_{i}$, which means that the $j$-th blocked region $\mathcal{D}_{j}$ is redundant and can be removed from $\bigcup_{i\in\mathcal{I}}\mathcal{D}_{i}$. Therefore, we can first search all the redundant sets through pairwise comparison and remove them from $\bigcup_{i\in\mathcal{I}}\mathcal{D}_{i}$. From a physical point of view, a UE is usually blocked by nearby buildings and the blockage of distant ones does not make sense. In this manner, the number of effective blocked regions may be smaller than $M+KM$, and the number of auxiliary variables $\{l_{ij}\}$ to be introduced is also decreased. Thus, the overall computational complexity can be reduced.

We consider a Manhattan-like dense urban area with size $500\times 500\text{ m}^{2}$, i.e., $x_{\mathrm{D}}=500$, $y_{\mathrm{D}}=500$. The center of each building follows $(100K_{x}-50,100K_{y}-50)$, with $K_{x}=1,...,5,K_{y}=1,...,5$. The length and width of each building are random variables which follow a uniform distribution in a range which is properly determined to reach the desired $20\%$ building density, i.e., the ratio of built-up land area to the total land area [43]. The heights of the buildings are random variables that follow a Rayleigh distribution with an average height of 23 meters, where the distribution function is interceptive between 3 meters to 50 meters. Thus, the minimum flight altitude of the UAV relay $h_{\mathrm{min}}$ is set to 50 meters. The coordinates of the BS antenna are set as $\mathbf{x}_{\mathrm{B}}=(0,0,25)$. In (9), a sufficiently large constant $C$ is set to

Auxiliary variable $l_{ij}$ is initialized as $l_{ij}^{(0)}=(|\mathcal{J}_{i}|-1)/|\mathcal{J}_{i}|,\forall j\in\mathcal{J}_{i},\forall i\in\mathcal{I}$. The position of UAV relay is initialized as $\mathbf{x}^{(0)}=(\frac{x_{\mathrm{D}}}{2},\frac{y_{\mathrm{D}}}{2},500)$. In this way, the initial values are a feasible solution to problem (27). Other adopted simulation parameter settings are summarized in Table I [43, 44], unless specified otherwise. The UEs are randomly generated in the areas without buildings, and each point in the simulation figures is the average performance over 500 UE distributions. If a simulation fails to converge under the default initial condition, it will be re-performed under the following new setup. First, an initial position where the UAV is outside the blocked regions is obtained by searching the lowest altitude with setting $(x_{\mathrm{V}},y_{\mathrm{V}})=(\frac{x_{\mathrm{D}}}{2},\frac{y_{\mathrm{D}}}{2})$. Then, the obtained values of binary variables $\{l_{ij}\}$ are fixed during optimization, and only $\mathbf{x}$, $P_{\mathrm{B}}$, and $\{P_{k}\}$ are optimized by adopting Algorithm 2.