Maximizing Network Connectivity for UAV Communications via Reconfigurable Intelligent Surfaces

We consider a RIS-assisted UAV network with a set of UAVs, one RIS, and multiple UEs that represent ground users, sensors, etc. An example of the considered network is shown in Fig. 1. The sets of UAVs and UEs are denoted as $\mathcal{A}=\{1,2,\ldots,A\}$ and $\mathcal{U}=\{1,2,\ldots,U\}$, respectively, where $A$ is the cardinality of the set $\mathcal{A}$. All UEs and UAVs are quipped with single antennas. The $A$ UAVs fly and hover over assigned locations at a fixed flying altitude and connect $U$ UEs with the fusion center. The locations of the UAVs, UEs, and the RIS are assumed to be fixed. We assume that all channels follow a quasi-static flat-fading model and thus remain constant over one time slot. The RIS is installed with a certain altitude $z_{R}$. Let $(x_{R},y_{R})$ be the 2D location of the RIS, $(x_{a},y_{a},z_{a})$ be the 3D location of the $a$-th UAV, and $(x_{u},y_{u})$ be the 2D location of the $u$-th UE, respectively. The distances between the $u$-th UE and the RIS and between the RIS and the $a$-th UAV are denoted by $d^{\text{UR}}_{u}$ and $d^{\text{RA}}_{a}$, respectively.

Due to their altitude, UAVs can have good connectivity to UEs. However, UEs may occasionally experience deep fade. To overcome this problem and further improve network connectivity, we propose to utilize a RIS to impose link redundancy to the RIS-assisted UAV network. As such, the network becomes more resilient against node failures by providing path diversity and alternative connectivity options between UEs and UAVs. The RIS is equipped with a controller and $M_{r}\times M_{c}$ passive reflecting units (PRUs) to form a uniform passive array (UPA). Each column of the UPA has $M_{r}$ PRUs with an equal spacing of $d_{c}$ meters (m) and each row of the UPA consists of $M_{c}$ PRUs with an equal spacing of $d_{r}$ m. These PRUs can add indirect links between UEs and UAVs with adjustable phase shifts. The phase-shift matrix of the RIS is modeled as the diagonal matrix $\mathbf{\Theta}=diag(e^{j\theta_{1}},\ldots,e^{j\theta_{2}},\ldots,e^{j\theta_{M}})$, where $\theta_{m}\in[0,2\pi)$, for $m=\{1,\ldots,M\}$ and $M=M_{r}\times M_{c}$.

The successful communications between the UEs and the RIS are measured using the distance threshold $D_{o}$, i.e., the $u$-th UE is connected to the RIS with distance $d^{(R)}_{u}$ if $d^{(R)}_{u}\leq D_{o}$. The communications between the UEs and UAVs/RIS are assumed to occur over different time slots (i.e., time multiplexing access) to avoid interference among the scheduled UEs. Therefore, we assume that only one UE is transmitting in each time slot to reduce interference. Considering the interference among the different scheduled UEs to the RIS and the UAVs is left for future work.

Since this paper focuses on the network connectivity from data link-layer viewpoint, we abstract the physical layer factors and consider a model that relies only on the distance between the nodes. Therefore, we model only the large scale fading and ignore the small scale fading. To quantify the UEs transmission to the UAVs and the RIS, we use the signal-to-noise ratio (SNR). For the $u$-th UE, SNR is defined as follows [8]

where $d_{u,a}$ is the distance between the $u$-th UE and the $a$-th UAV, $p$ is the transmit power of the $u$-th UE, which is maintained fixed for all the UEs, $N_{0}$ is the additive white Gaussian noise (AWGN) variance, and $\alpha$ is the path loss exponent that depends on the transmission environment.

UAVs hover at high altitudes, thus we reasonably assume that they maintain LoS channel between each other. The path loss between the $a$-th and the $a^{\prime}$-th UAVs can be expressed as

where $d_{a,a^{\prime}}$ is the distance between the $a$-th UAV and the $a^{\prime}$-th UAV, $f_{c}$ is the carrier frequency, and $c$ is light speed. The SNR in dB between the $a$-th UAV and the $a^{\prime}$-th UAV is $\gamma^{(A)}_{a,a^{\prime}}=10\log P-\Gamma_{a,a^{\prime}}-10\log N_{0}$, where $P$ is the transmit power of the $a$-th UAV, which is maintained fixed for all the UAVs. Note that the SNR of the $u$-th UE determines whether it has a successful connection to the corresponding UAV $a$. In other words, the $a$-th UAV is assumed to be within the transmission range of the $u$-th UE if $\gamma^{(U)}_{u,a}\geq\gamma^{\text{UE}}_{0}$, where $\gamma^{\text{UE}}_{0}$ is the minimum SNR threshold for the communication links between the UEs and the UAVs. Similarly, we assume that UAV $a$ and UAV $a^{\prime}$ have a successful connection provided that $\gamma^{(A)}_{a,a^{\prime}}\geq\gamma^{\text{UAV}}_{0}$, where $\gamma^{\text{UAV}}_{0}$ is the minimum SNR threshold for the communication links between the UAVs.

Since the RIS is deployed in the higher altitude, the signal propagation of UE-to-RIS link is adopted to be a simple yet reasonably accurate LoS channel model [11]. The LoS channel vector between the $u$-th UE and the RIS is given by [11]

where $d_{u}^{\text{UR}}$ is the distance between the $u$-th UE and the RIS, $\beta_{0}$ denotes the path loss at the reference distance $d_{\text{ref}}=1$ m, and $\tilde{\mathbf{h}}^{\text{UR}}_{u}$ represents the array response component which can be denoted by

where $\phi_{u}^{\text{UR}},\varphi_{u}^{\text{UR}}$, and $\psi_{u}^{\text{UR}}$ are related to the sine and cosine terms of the vertical and horizontal angles-of-arrival (AoAs) at the RIS [11], and given by $\phi_{u}^{\text{UR}}=\frac{y_{u}-y_{R}}{\sqrt{(x_{u}-x_{R})^{2}+(y_{u}-y_{R})^{2}}}$, $\varphi_{u}^{\text{UR}}=\frac{x_{R}-x_{u}}{\sqrt{(x_{u}-x_{R})^{2}+(y_{u}-y_{R})^{2}}}$, $\psi_{u}^{\text{UR}}=\frac{-z_{R}}{d^{\text{UR}}_{u}}$, $\lambda$ is the wavelength, and $T$ denotes transpose. On the other hand, the RIS and UAVs are deployed in the higher altitudes, thus the reflected signal propagation of the RIS-to-UAV link typically occurs in clear airspace where the obstruction or reflection effects diminish. The LoS channel vector between the RIS and the $a$-th UAV is given by

where $d_{a}^{\text{RA}}$ is the distance between the RIS and the $a$-th UAV, and $\tilde{\mathbf{h}}^{\text{RA}}_{a}$ represents the array response component which can be denoted by

where $\phi_{a}^{\text{RA}},\varphi_{a}^{\text{RA}}$, and $\psi_{a}^{\text{RA}}$ are related to the sine and cosine terms of the vertical and horizontal angles-of-departure (AoDs) from the RIS to the $a$-th UAV [11], and respectively given by $\phi_{a}^{\text{RA}}=\frac{y_{R}-y_{a}}{\sqrt{(x_{R}-x_{a})^{2}+(y_{R}-y_{a})^{2}}}$, $\varphi_{a}^{\text{RA}}=\frac{x_{R}-x_{a}}{\sqrt{(x_{R}-x_{a})^{2}+(y_{R}-y_{a})^{2}}}$, and $\psi_{a}^{\text{RA}}=~{}\frac{z_{R}-z_{a}}{d^{\text{RA}}_{a}}$.

Given the aforementioned channel models, the concatenated channel for the UE-RIS-UAV link between the $u$-th UE and the $a$-th UAV through the RIS is given by $h^{\text{URA}}_{u,a}=(\mathbf{h}^{\text{RA}}_{a}\mathbf{)}^{H}\mathbf{\Theta}\mathbf{h}^{\text{UR}}_{u}$ [11]. Accordingly, the SNR of the reflected link between the $u$-th UE and the $a$-th UAV through the RIS can be written as $\gamma^{(R)}_{u,a}=\frac{p|h^{\text{URA}}_{u,a}|^{2}}{N_{0}}$ [12]. For successful connection between UE $u$ and UAV $a$ via RIS $r$, $\gamma^{(R,r)}_{u,a}\geq\gamma^{\text{RIS}}_{0}$, where $\gamma^{(RIS)}_{0}$ is the minimum SNR threshold for the communication links between the UEs and the UAVs via the RISs.

We model the considered RIS-assisted UAV network as an undirected graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\{v_{1},v_{2},\cdots,v_{V}\}$ is the set of nodes (i.e., UAVs and UEs) in the network, $\mathcal{E}=\{e_{1},e_{2},\cdots,e_{E}\}$ is the set of all edges. $V=|\mathcal{U}\cup\mathcal{A}|=|\mathcal{V}|$ and $|\mathcal{E}|=E$ are the numbers of vertices and edges in the graph, respectively. The graph $\mathcal{G}$ implies that all the links in the network are bidirectional, i.e., a node $v$ is able to reach node $v^{\prime}$, and vice versa. The edge between any two nodes is created based on a typical SNR threshold.

For an edge $e_{k}$, $1\leq k\leq E$, that connects two nodes $\{v_{n},v_{m}\}\in\mathcal{V}$, let $\mathbf{a}_{k}$ be a vector, where the $n$-th and $m$-th elements in $\mathbf{a}_{k}$ are given by $a_{k,n}=1$ and $a_{k,m}=-1$, respectively, and zero otherwise. The incidence matrix $\mathbf{A}\in\mathbf{R}^{V\times E}$ of a graph $\mathcal{G}$ is the matrix with the $k$-th column given by $\mathbf{a}_{k}$. Hence, in undirected graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, the Laplacian matrix $\mathbf{L}$ is an $V$ by $V$ matrix, which is defined as follows [9]:

where the entries of $\mathbf{L}$ are given as follows:

where $n,m\in\{1,2,\ldots,V\}$ are the indices of the nodes, and $D_{v_{n}}$ is the degree of node $v_{n}$, which represents the number of all its neighboring nodes.

In network connectivity, algebraic connectivity, also called the Fiedler metric or the second smallest eigenvalue [7], measures how well a graph $\mathcal{G}$ that has the associated Laplacian matrix $\mathbf{L}$ is connected. From its name, this metric is usually denoted as $\lambda_{2}(\mathbf{L})$. The motivation of $\lambda_{2}(\mathbf{L})$ to be used as a network connectivity metric comes from the following two main reasons [7]. First, $\lambda_{2}(\mathbf{L})>0$ if and only if $\mathcal{G}$ is connected, i.e., $\mathcal{G}$ is only one connected graph. It is worth mentioning that when $\lambda_{2}(\mathbf{L})=0$, the graph is disconnected in which at least one of its vertices is unreachable from any other vertices in the graph. Second, $\lambda_{2}(\mathbf{L})$ is monotone increasing in the edge set, i.e., if $\mathcal{G}_{1}=(V,E_{1})$ and $\mathcal{G}_{2}=(V,E_{2})$ and $E_{1}\subseteq E_{2}$, then $\lambda_{2}(\mathbf{L}_{2})\geq\lambda_{2}(\mathbf{L}_{1})$. This implies that $\lambda_{2}(\mathbf{L})$ qualitatively represents the connectivity of a graph in the sense that the larger $\lambda_{2}(\mathbf{L})$ is, the more connected the graph will be. To this end, since $\lambda_{2}(\mathbf{L})$ is a good measure of how connected the graph is, the more edges that exist between the UEs and the UAVs, the longer the network can live without being disconnected due to node failures. Thus, the network becomes more resilient. Based on that, we consider $\lambda_{2}(\mathbf{L})$ as a quantitative measure of the network resiliency in this paper, similar to [9, 13].

To optimally solve (7), we consider a linear search scheme that computes $\lambda_{2}(\mathbf{L}^{\prime})$ for each possible UAV node $a\in\mathcal{A}_{0}$, and then calculate the corresponding phase shift of the RIS to that UAV node. In particular, the corresponding phase shift at PRU of the RIS to the $a$-th UAV is calculated as follows [11]

We argue that the computational complexity of the proposed solution of this case is affordable since it needs to compute only $|\mathcal{A}_{0}|$ Laplacian matrices. The steps of the proposed method are summarized in Algorithm 1.

The exhaustive search scheme to solve (8) for multiple UEs can be done by computing $\lambda_{2}(\mathbf{L}^{\prime})$ for a total of $U\sum_{u=1}^{U}|\mathcal{A}^{u}_{0}|$ Laplacian matrices, which requires huge amount of computation for large $U$. For graph $\mathcal{G}^{\prime}(\mathcal{V},\mathcal{E}^{\prime})$, the time complexity of the exhaustive search is high for large network settings. It runs in $\mathcal{O}(4E^{\prime}V^{3}/3)$ to compute $\lambda_{2}(\mathbf{L}^{\prime})$ [14]. To overcome such computational intractability, we instead propose an efficient method to solve (8), which finds the feasible UE-RIS-UAV association to maximize $\lambda_{2}(\mathbf{L}^{\prime})$ using SDP solvers [15].

We add a link connecting the $u$-th UE to the $a$-th UAV through the RIS if both $x_{u}$ and $y^{u}_{a}$ in (8) are $1$. Let $\mathbf{z}$ be a vector representing the UE-RIS-UAV candidate associations, in which case $x_{u}=1$ and $y^{u}_{a}=1$, $\forall u\in\mathcal{U},a\in\mathcal{A}$. Therefor, the problem in (8) can be seen as having a set of $|\mathbf{z}|$ UE-RIS-UAV candidate associations, and we want to select the optimum UE-RIS-UAV association among these $|\mathbf{z}|$ associations. This optimization problem can be formulated as

where $\mathbf{1}\in\mathbf{R}^{|\mathbf{z}|}$ is the all-ones vector and

where $\mathbf{a}_{l}$ is the incidence vector resulting from adding link $l$ to the original graph $\mathcal{G}$ and $\mathbf{L}$ is the Laplacian matrix of the original graph $\mathcal{G}$. Clearly, the dimension of $\mathbf{L}$ and $\mathbf{L}^{\prime}(\mathbf{z})$ is $V\times V$.

The optimization vector in (12) is the vector $\mathbf{z}$. The $l$-th element of $\mathbf{z}$, denoted by $z_{l}$, is either $1$ or $0$, which corresponds to whether this UE-RIS-UAV association should be chosen or not, respectively. The combinatorial optimization problem in (12) is NP-hard problem with high complexity. Therefore, we relax the constraint on the entries of $\mathbf{z}$ and allow them to take any value in the interval $[0,1]$. Specifically, we relax the Boolean constraint $\mathbf{z}\in\{0,1\}^{|\mathbf{z}|}$ to be a linear constraint $\mathbf{z}\in[0,1]^{|\mathbf{z}|}$, then we can represent the problem (12) as

We emphasize that the optimal solution of the relaxed problem in (14) is an upper bound for the optimal solution of the original problem (12) since it has a larger feasible set. In [10], it was shown that $\lambda_{2}(\mathbf{L}^{\prime}(\mathbf{z}))$ in (14) is the point-wise infimum of a family of linear functions of $\mathbf{z}$, which is a concave function in $\mathbf{z}$. In addition, the relaxed constraints are linear in $\mathbf{z}$. Therefore, the optimization problem in (14) is a convex optimization problem [10], and it is equivalent to the following SDP optimization problem [16]

where $\mathbf{I}\in\mathbf{R}^{V\times V}$ is the identity matrix and $\mathbf{F}\preceq\mathbf{L}$ denotes that $\mathbf{L}-\mathbf{F}$ is a positive semi-definite matrix.

By solving the SDP optimization problem in (15) efficiently using any SDP standard solver such as the CVX software package [15], the optimization variable $\mathbf{z}$ is obtained. Since the entries of the output vector $\mathbf{z}$ are continuous, we consider to round the maximum entry to $1$ while others are rounded to zero. For the given association vector $\mathbf{z}$, we optimize the phase shift of the RIS as in (11) to direct the signal of the selected UE to the associated UAV.