#  Effectiveness of Reconfigurable Intelligent Surfaces to Enhance
Connectivity in UAV Networks

Mohammed S. Al-Abiad, Member, IEEE, Mohammad Javad-Kalbasi, Student Member,
IEEE, and Shahrokh Valaee, Fellow, IEEE Mohammed S. Al-Abiad, Mohammad Javad-
Kalbasi, and Shahrokh Valaee are with the Department of Electrical and
Computer Engineering, University of Toronto, Toronto, Canada, Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>A part of this paper [1] is accepted at the IEEE
Globecom’ 2023, Kuala Lumpur, Malaysia. This work was supported in part by
funding from the Innovation for Defence Excellence and Security (IDEaS)
program from the Department of National Defence (DND).

###### Abstract

Reconfigurable intelligent surfaces (RISs) are expected to make future 6G
networks more connected and resilient against node failures, due to their
ability to introduce controllable phase-shifts onto impinging electromagnetic
waves and impose link redundancy. Meanwhile, unmanned aerial vehicles (UAVs)
are prone to failure due to limited energy, random failures, or targeted
failures, which causes network disintegration that results in information
delivery loss. In this paper, we show that the integration between UAVs and
RISs for improving network connectivity is crucial. We utilize RISs to provide
path diversity and alternative connectivity options for information flow from
user equipments (UEs) to less critical UAVs by adding more links to the
network, thereby making the network more resilient and connected. To that end,
we first define the criticality of UAV nodes, which reflects the importance of
some nodes over other nodes. We then employ the algebraic connectivity metric,
which is adjusted by the reflected links of the RISs and their criticality
weights, to formulate the problem of maximizing the network connectivity. Such
problem is a computationally expensive combinatorial optimization. To tackle
this problem, we propose a relaxation method such that the discrete scheduling
constraint of the problem is relaxed and becomes continuous. Leveraging this,
we propose two efficient solutions, namely semi-definite programming (SDP)
optimization and perturbation heuristic, which both solve the problem in
polynomial time. For the perturbation heuristic, we derive the lower and upper
bounds of the algebraic connectivity obtained by adding new links to the
network. Finally, we corroborate the effectiveness of the proposed solutions
through extensive simulation experiments.

###### Index Terms:

Network connectivity, algebraic connectivity, RIS-assisted UAV communications,
graph theory, perturbation method.

##  I Introduction

###  I-A Motivation

In future 6G networks, there is a proliferation of connected nodes (i.e.,
smart devices, sensors, military vehicles) and services (i.e., augmented
reality, information flow, data collection) that need to be supported by
wireless networks [2, 3, 4]. Consequently, there is a pressing need for more
connected wireless networks that are resilient and robust against node and
link failures. To address this need, unmanned aerial vehicles (UAVs)
communication is shown to be a promising solution since they can be rapidly
deployed with adjustable mobility [5, 6]. One distinctive aspect of UAV-
assisted communications involves enhancing network connectivity through the
establishment of line-of-sight (LoS) connections with user equipment (UE) [7].

The prime concern of UAV communications is that UAVs111We use the terms nodes
and UAVs/UEs interchangeably in this paper. In addition, the terms links and
edges are used interchangeably since we usually use a graph to represent a
network. are prone to failure due to several reasons, such as limited energy,
hardware failure, or targeted failure in the case of battlefield surveillance
systems. Such UAV failures cause network disintegration, and consequently,
information flow from UEs to a fusion center through UAVs can be severely
impacted. Hence, it is crucial to always keep the network connected, which can
be addressed by adding more backhual links to the network [8]. Network
densification, by adding more UAVs or access points (APs), helps to improve
network connectivity but that will increase the hardware and energy
consumption drastically [9]. In addition, deploying a large number of UAVs or
APs can be challenging in densely populated urban areas due to site
constraints, limited space, and limited UAV battery. Instead, deploying
passive nodes in the network can achieve a more connected system with less
cost and lower energy consumption.

Recently, reconfigurable intelligent surfaces (RISs) have drawn significant
attention from both academia and industry, with the features of relatively
low-cost and the capability to extend coverage and reduce energy consumption.
Besides their other benefits in wireless networks, RISs offer two key
advantages for designing connected and resilient wireless networks as follows.
First, RISs can improve network connectivity by creating an indirect path
between a UE and a UAV when the LoS is not available, or to provide more
reliable links between the connected UEs and the UAVs [10, 11]. As a result,
path diversity and alternative connectivity options for information flow from
UEs to UAVs are provided. Second, RIS provides a high passive beamforming gain
via adjusting its reflection coefficients intelligently [12]. By tuning the
phase shifts of RIS, we can direct the signals of the UEs from critical UAVs
that are most likely to fail to less critical UAVs. Therefore, RIS can reflect
the signals of the UEs to the desired UAVs, which is one of the main
motivations of this work. As a result, RISs can be utilized to provide for
more connected and resilient networks that can effectively operate in the
presence of node failures. In this paper, we show that with the integration of
UAV communications and RISs, a small number of low-cost RISs can increase the
connectivity of the RIS-assisted UAV networks significantly.

Optimized network connectivity plays a crucial role in designing more
connected and resilient networks and extending network lifetime, which is
defined as the time until the network becomes disconnected [16, 17]. An
important metric that measures how well a graph network is connected is called
the algebraic connectivity, also called the Fiedler metric or the second
smallest eigenvalue222We use the terms algebraic connectivity and the Fiedler
value interchangeably in this paper since they both measure the network
connectivity of the graph Laplacian matrix. of the graph Laplacian matrix[18].
One important property of the algebraic connectivity is that the larger it is,
the more connected the graph will be. Such metric has been considered widely
in wireless sensor networks. Several studies, as will be detailed below,
consider routing solutions with the focus more on extending the battery
lifetime of sensor nodes, e.g., [16, 17, 19, 20, 21]. One trivial strategy to
optimize network connectivity is to add more links via adding more connected
nodes (i.e., APs, relays, or UAVs) [16]. However, despite significant
advancements in wireless sensor networks and UAV communications, the limited
battery of nodes, the consumed energy, and cost necessitate a simple and
efficient network design. Therefore, we introduce a cost-effective expansion
of the traditional UAV communications by deploying compact RIS passive nodes
that reflect the signals of the UEs to the desired UAVs. As a result, more
links are added to the network to optimize its algebraic connectivity
significantly.

###  I-B Related Work

In the recent literature, several works have studied the importance of RISs in
improving different metrices, such as positioning accuracy [9, 10], extending
the coverage of networks [11], boosting the communication capability [12, 13,
14, 15], etc. However, to the best of our knowledge, there is no work that
used RISs to maximize network connectivity. Therefore, we briefly review some
of the related works that addressed network connectivity maximization problem
in different wireless sensor networks and UAV communications, e.g., [16, 17,
19, 20, 21, 22, 23].

In spite of recent advances in wireless sensor networks, most of the existing
studies consider routing solutions with the focus more on extending the
battery lifetime of sensor nodes. These works define network connectivity as
the network lifetime, in which the first node or all the nodes of a sensor
network have failed [16, 19, 21]. In [16], the authors addressed the problem
of adding relays to maximize the connectivity of multi-hop wireless networks.
In [22], the authors maximized the algebraic connectivity by positioning the
UAV to maximize the connectivity of small-cells backhaul network. The paper
[24] proposed three different random relay deployment strategies, namely, the
connectivity-oriented, the lifetime-oriented, and the hybrid-oriented
strategies. However, there is no explicit optimization problem for maximizing
the network lifetime in that work. A mathematical approach to placing a few
flying UAVs over a wireless ad-hoc network in order to optimize the network
connectivity for better coverage was proposed in [25]. However, none of the
aforementioned works has ever explicitly considered the exploitation of RISs
to add more reflected links to improve network connectivity of UAV-assisted
networks. Different from the works [16, 17, 11, 19, 20, 21, 22, 23] that
focused on routing solutions, this paper focuses on designing a more connected
RIS-assisted UAV network. This network enables information flow from the UEs
to the UAVs and is resistant to UAV failure.

The network connectivity maximization problem can be solved either by (i)
relaxing the problem’s constraints using convex relaxation, and then
formulating the problem as a semi-definite programming (SDP) optimization
problem to be solved using CVX [1, 16, 22] or (ii) using exhaustive search.
However, the exhaustive search is computationally intractable for large
network sizes and the SDP optimization is sub-optimal. Therefore, there is a
need to find an efficient heuristic algorithm that can find a set of suitable
reflected links of the RISs that connect the UEs to the UAVs in polynomial
time, such that we maximize the connectivity of a RIS-assisted UAV network. As
one of the main contributions in this paper, we build on the reference [26] to
perturbate the eigenvalues of the original Laplacian matrix with rank-one
update matrix and propose a novel perturbation heuristic. This efficient
perturbation heuristic is based on calculating the values of the Fiedler
vector, which can be conveniently applied to large graphs with low
computational complexity.

###  I-C Contribution

In this paper, we investigate the integration between RISs and UAV-assisted
communication systems by studying nodes criticality and the algebraic
connectivity through SDP optimization and the Laplacian matrix perturbation,
so that we maximize the connectivity of the envisioned RIS-assisted UAV
network. The main contributions of this work are:

  * •

RIS-assisted UAV problem formulation: First, we propose to define the
criticality of UAV nodes, which reflects the importance of some nodes over
other nodes towards the network connectivity. By considering the nodes’
importance from the graph connectivity perspective, the node with higher
importance will be retained in the network, therefore the connectivity of the
remaining network is maintained as long as possible. We then employ the
algebraic connectivity metric, which is adjusted by the reflected links of the
RISs and their criticality weights, to formulate the problem of maximizing the
network connectivity. Such problem is shown to be a combinatorial optimization
problem. By embedding the nodes criticality in the links selections, we
propose two solutions to solve the proposed problem.

  * •

Convex relaxation and SDP formulation: To tackle this problem, we propose a
relaxation method such that the objective function of the relaxed problem
becomes continuous. Leveraging this, we propose to formulate the problem as a
SDP optimization problem that can be solved efficiently in polynomial time
using CVX.

  * •

Algebraic connectivity perturbation: We propose a low-complexity, yet
efficient, perturbation heuristic, which has less complexity compared to the
relaxation method. In this heuristic perturbation, one UE-RIS-UAV link is
added at a time by calculating only the eigenvector values corresponding to
the algebraic connectivity. We also derive the lower and upper bounds of the
algebraic connectivity obtained by adding new links to the network based on
this perturbation heuristic.

  * •

Performance evaluation: We evaluate the performance of the proposed schemes in
terms of network connectivity via extensive simulations. We verify that the
proposed schemes result in improved network connectivity as compared to the
existing solutions. In particular, the proposed perturbation heuristic has a
superior performance that is roughly the same as the optimal solution using
exhaustive search and close to the upper bound.

The rest of this paper is organized as follows. In Section II, we describe the
system model, network connectivity, and then define nodes criticality and
outline some of its important properties. In Section III, the network
connectivity maximization problem in a RIS-assisted UAV network is formulated.
In Section IV, the proposed solutions are explained, and the upper and lower
bounds on the algebraic connectivity of our proposed perturbation scheme are
analyzed in Section V. Extensive simulation results are presented in Section
VI, and the conclusion is given in Section VII.

Figure 1: A typical RIS-assisted UAV network with $2$ RISs, $2$ UEs, and $4$
UAVs.

##  II System Model and Network Connectivity

###  II-A System Model

Consider the sample RIS-assisted UAV system shown in Fig. 1. The system
consists of a set of UAVs, a set of RISs, and multiple UEs that represent
ground users, sensors, etc. The sets of UAVs, RISs, and UEs are denoted as
$\mathcal{A}=\\{1,2,\ldots,A\\}$, $\mathcal{R}=\\{1,2,\ldots,R\\}$, and
$\mathcal{U}=\\{1,2,\ldots,U\\}$, respectively. All UEs and UAVs are equipped
with single antennas. The $A$ UAVs fly and hover over assigned locations at a
fixed flying altitude and connect with $U$ UEs. The locations of the UAVs,
UEs, and RISs are assumed to be fixed. The RISs are installed with a certain
altitude $z_{r}$, $r\in\mathcal{R}$. Let $(x_{r},y_{r},z_{r})$ be the 3D
location of the $r$-th RIS, $(x_{a},y_{a},z_{a})$ the 3D location of the
$a$-th UAV, and $(x_{u},y_{u})$ the 2D location of the $u$-th UE,
respectively. The distances between the $u$-th UE and the $r$-th RIS and
between the $r$-th RIS and the $a$-th UAV are denoted by $R^{\text{UR}}_{u,r}$
and $R^{\text{RA}}_{r,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 set of RISs to impose
link redundancy to the network. As such, the network becomes more resilient
against node failures by providing path diversity and alternative connectivity
options between the UEs and the UAVs. Each RIS is equipped with a controller
and $M:=M_{b}\times M_{c}$ passive reflecting units (PRUs) to form a uniform
passive array (UPA). Each column of the UPA has $M_{b}$ 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_{b}$ m. Through appropriate adjustable phase
shifts, these PRUs can add indirect links between the UEs and the UAVs or
connect the blocked UEs to the desired UAVs. The phase-shift matrix of the
$r$-th RIS is modeled as the diagonal matrix
$\mathbf{\Theta}_{r}=diag(e^{j\theta_{1}^{r}},\ldots,e^{j\theta_{2}^{r}},\ldots,e^{j\theta_{M}^{r}})$,
where $\theta_{m}^{r}\in[0,2\pi)$, for $r\in\mathcal{R}$, and
$m\in\\{1,\ldots,M\\}$.

For the $u$-th UE, the reachable UAVs are denoted by a set $\mathcal{A}^{u}$.
Assuming that $|\mathcal{A}^{u}|\geq 1$ in general, some UEs are able to
access multiple UAVs simultaneously. Similarly, the reachable RISs for the
$u$-th UE are denoted by a set $\mathcal{R}_{u}$. The successful
communications between the UEs and RISs are measured using the distance
threshold $D_{o}$, i.e., the $u$-th UE can be connected to the $r$-th RIS with
distance $d_{u,r}$ if $d_{u,r}\leq D_{o}$. The communications between the UEs
and UAVs/RISs are assumed to occur over different time slots (i.e., time
multiplexing access) to avoid interference among the scheduled UEs. Therefore,
in each time slot, we assume that distinct UEs $u$ and $u^{\prime}$ are
allowed to transmit simultaneously if
$\mathcal{R}_{u}\cap\mathcal{R}_{u^{\prime}}=\emptyset$ to reduce
interference.

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

$\gamma^{(U)}_{u,a}=\frac{d_{u,a}^{-\alpha}p}{N_{0}},$ (1)

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, hence we reasonably assume that they maintain
LoS channel between each other [7]. The path loss between the $a$-th UAV and
$a^{\prime}$-th UAV can be expressed as

$\Gamma_{a,a^{\prime}}=20\log\bigg{(}\frac{4\pi
f_{c}d_{a,a^{\prime}}}{c}\bigg{)},$ (2)

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 the speed of
light. Consequently, the SNR between the $a$-th and the $a^{\prime}$-th UAVs
is

$\gamma^{(A)}_{a,a^{\prime}}=10\log P-\Gamma_{a,a^{\prime}}-10\log
N_{0},~{}~{}~{}~{}(dB)$ (3)

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^{(UAV)}_{0}$ is the minimum SNR threshold for the communication links
between the UAVs.

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

$\mathbf{h}^{\text{UR}}_{u,r}=\sqrt{\frac{\beta_{0}}{(d_{u,r}^{\text{UR}})^{2}}}\tilde{\mathbf{h}}^{\text{UR}}_{u,r},$
(4)

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

$\displaystyle\tilde{\mathbf{h}}^{\text{UR}}_{u,r}$
$\displaystyle\\!\\!=\\!\\!$ $\displaystyle{[1,e^{-j\frac{2\pi
d_{b}}{\lambda}\phi_{u,r}^{\text{UR}}\psi_{u,r}^{\text{UR}}},\ldots,e^{-j\frac{2\pi
d_{b}}{\lambda}(M_{b}-1)\phi_{u,r}^{\text{UR}}\psi_{u,r}^{\text{UR}}}]}^{T}$
$\displaystyle\otimes{[1,e^{-j\frac{2\pi
d_{c}}{\lambda}\varphi_{u,r}^{\text{UR}}\psi_{u,r}^{\text{UR}}},\ldots,e^{-j\frac{2\pi
d_{c}}{\lambda}(M_{c}-1)\varphi_{u,r}^{\text{UR}}\psi_{u,r}^{\text{UR}}}]}^{T},$

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

$\mathbf{h}^{RA}_{r,a}=\sqrt{\frac{\beta_{0}}{(d_{r,a}^{RA})^{2}}}\tilde{\mathbf{h}}^{RA}_{r,a},$
(5)

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

$\displaystyle\tilde{\mathbb{h}}^{\text{RA}}_{r,a}\\!\\!$
$\displaystyle=\\!\\!$ $\displaystyle{[1,e^{-j\frac{2\pi
d_{b}}{\lambda}\phi_{r,a}^{\text{RA}}\psi_{r,a}^{\text{RA}}},\ldots,e^{-j\frac{2\pi
d_{b}}{\lambda}(M_{b}-1)\phi_{r,a}^{\text{RA}}\psi_{r,a}^{\text{RA}}}]}^{T}$
$\displaystyle\otimes{[1,e^{-j\frac{2\pi
d_{c}}{\lambda}\varphi_{r,a}^{\text{RA}}\psi_{r,a}^{\text{RA}}},\ldots,e^{-j\frac{2\pi
d_{c}}{\lambda}(M_{c}-1)\varphi_{r,a}^{\text{RA}}\psi_{r,a}^{\text{RA}}}]}^{T},$

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

Based on the channel models described above, the concatenated channel for the
UE-RIS-UAV link between the $u$-th UE and the $a$-th UAV through the $r$-th
RIS is given by [12]

$\mathbf{h}^{\text{URA}}_{u,a}=(\mathbf{h}^{\text{RA}}_{r,a}\mathbf{)}^{H}\mathbf{\Theta}_{r}\mathbf{h}^{\text{UR}}_{u,r}.$
(6)

Accordingly, the SNR of the reflected link between the $u$-th UE and the
$a$-th UAV through the $r$-th RIS can be written as [27]

$\gamma^{(R,r)}_{u,a}=\frac{p\lVert\mathbf{h}^{\text{URA}}_{u,a}\rVert^{2}}{N_{0}}.$
(7)

In this paper, 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, and $\mathcal{E}=\\{e_{1},e_{2},\cdots,e_{E}\\}$ is
the set of all edges, where $V$ and $E$ are the cardinality of the sets
$\mathcal{V}$ and $\mathcal{E}$, respectively, i.e.,
$V=|\mathcal{U}\cup\mathcal{A}|=|\mathcal{V}|$ and $E=|\mathcal{E}|$. The edge
between any two nodes is created based on a typical previously mentioned SNR
threshold. The key notations are summarized in Table I.

TABLE I: Summary of the Main Notations and Definitions Variable |  Definition
---|---
$\mathcal{A},\mathcal{U}$, $\mathcal{R}$ |  Sets of $A$ UAVs, $U$ UEs, and $R$ RISs
$\mathcal{U}_{t}$ |  Set of transmitting UEs in time slot $t$
$R^{\text{UR}}_{u,r},R^{\text{UR}}_{r,a}$ |  Distances between UE $u$ (RIS $r$) and RIS $r$ (UAV $a$)
$\theta^{r}_{m}$ |  Phase-shift of element $m$ at RIS $r$
$d_{c},d_{b}$ |  Column and row spacing between RIS elements
$\mathbf{\Theta}_{r},M$ |  Phase-shift matrix of RIS $r$ and total number of RIS elements
$\mathcal{R}_{u},D_{0}$ |  Reachable RISs to UE $u$ and distance threshold
$\gamma^{(U)}_{u,a},\gamma^{(A)}_{a,a^{\prime}}$ |  SNRs of UE $u$ to UAV $a$ and UAV $a$ to UAV $a^{\prime}$
$\gamma^{\text{(UE)}},\gamma^{\text{(UAV)}}$ |  SNR thresholds for UE-UAV and UAV-UAV communications
$\mathbf{h}^{\text{UR}}_{u,r},\mathbf{h}^{\text{RA}}_{r,a}$ |  LoS channel vectors between UE $u$ (RIS $r$) and RIS $r$ (UAV $a$)
$\gamma^{(R,r)}_{u,a}$ |  SNR of the reflected link between UE $u$ and UAV $a$ through RIS $r$
$\mathcal{G},\mathcal{G}_{-n}$ |  Original graph and its sub-graph after removing node $n$ and all its edges
$\mathcal{V},\mathcal{E}$ |  Sets of vertices and edges of graph $\mathcal{G}$
$\mathbf{L},\mathbf{A}$ |  Laplacian and incidence matrices
$deg(v_{n})$ |  Degree of node $v_{n}$
$w_{l}$ |  Weight of link $l$ that connects UE $u$ and UAV $a$ through a RIS
$\lambda_{2}(\mathbf{L})$ |  Algebraic connectivity of the original Laplacian matrix $\mathbf{L}$
$\lambda_{2}(\mathbf{L}^{\prime})$ |  Algebraic connectivity of adjusted Laplacian matrix $\mathbf{L}^{\prime}$
$\mathcal{C}_{n}$ |  Criticality of node $n$
$X_{u,a},Y^{u}_{r,a}$ |  Two binary variables for UE-UAV and UE-RIS-UAV scheduling

###  II-B Network Connectivity

This subsection briefly discusses the definition of the Laplacian matrix
$\mathbf{L}$ representing a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, its
second smallest eigenvalue $\lambda_{2}(\mathbf{L})$, and the relationship
between $\lambda_{2}(\mathbf{L})$ and the connectivity of the associated graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$.

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}$ of a graph $\mathcal{G}$ is the matrix with the $k$-th column
given by $\mathbf{a}_{k}$. Furthermore, the weight of an edge $e_{k}$ that
connects two nodes $\\{v_{n},v_{m}\\}\in\mathcal{V}$, denoted by $w_{n,m}$ or
$w_{k}$, is a function of the criticality of the nodes, as will be discussed
in Section II-C. The weight vector $\mathbf{w}\in{[\mathbb{R}^{+}]}^{E}$ is
defined as $\mathbf{w}=[w_{1},w_{2},\ldots,w_{E}]$. Hence, in an undirected
graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, the Laplacian matrix
$\mathbf{L}$ is a $V$ by $V$ matrix, which is defined as follows [16]:

$\mathbf{L}=\mathbf{A}~{}diag(\mathbf{w})~{}\mathbf{A}^{T}=\sum^{E}_{k=1}w_{k}\mathbf{a}_{k}\mathbf{a}^{T}_{k},$
(8)

where the entries of $\mathbf{L}$ are given element-wise by

$L(n,m)=\begin{cases}deg(v_{n})&\text{if}~{}v_{n}=v_{m},\\\
-w_{n,m}&\text{if}~{}(v_{n},v_{m})\in\mathcal{E},\\\
0&\text{otherwise},\end{cases}$ (9)

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

As mentioned above, in network connectivity, algebraic connectivity measures
how well a graph $\mathcal{G}$ that has the associated Laplacian matrix
$\mathbf{L}$ is connected [18]. This metric is usually denoted as
$\lambda_{2}(\mathbf{L})$. The main motivation of $\lambda_{2}(\mathbf{L})$ as
a network connectivity metric comes from the following two main reasons [18].
First, $\lambda_{2}(\mathbf{L})>0$ if and only if $\mathcal{G}$ is connected,
i.e., $\mathcal{G}$ has only one component. It is worth mentioning that when
$\lambda_{2}(\mathbf{L})=0$, the graph is disconnected in which it has more
than one component. Second, $\lambda_{2}(\mathbf{L})$ is monotone increasing
in the edge set, i.e., if $\mathcal{G}_{1}=(\mathcal{V},\mathcal{E}_{1})$ is
associated with $\mathbf{L}_{1}$ and
$\mathcal{G}_{2}=(\mathcal{V},\mathcal{E}_{2})$ is associated with
$\mathbf{L}_{2}$ and $\mathcal{E}_{1}\subseteq\mathcal{E}_{2}$, then
$\lambda_{2}(\mathbf{L}_{1})\leq\lambda_{2}(\mathbf{L}_{2})$. 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 carefuly selected 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 and similar to [16, 23], this paper considers
$\lambda_{2}(\mathbf{L})$ as a quantitative measure of network connectivity,
which shows network resiliency against node failures. For simplicity, the
remaining of the paper uses node $n$ instead of node $v_{n}$.

###  II-C Nodes Criticality

Let $\mathcal{G}_{-n}$ be the remaining graph after removing UAV node $n$ and
all its adjacent edges to other nodes. Noticed that the most critical nodes in
$\mathcal{G}$ are those representing the UAVs since UAVs have many connections
to UEs and other UAVs, i.e., they represent the backhaul core of the network.
We propose to quantify the connectivity of the remaining graph based on the
Fiedler value. The connectivity of the remaining graph can be quantified by
$\lambda_{2}(\mathcal{G}_{-n})$ of the graph resulted from removing a typical
node $n$ and all its connected edges in $\mathcal{G}$. We define the nodes
criticality as follows.

######  Definition 1.

The criticality of node $n$, which reflects the severity of network
connectivity after removing that node and its connected edges to other nodes,
is defined as

$\mathcal{C}_{n}=\frac{1}{\lambda_{2}(\mathcal{G}_{-n})}.$ (10)

∎

Remark: Since the Laplacian matrix $\mathbf{L}$ is positive semi-definite
(expressed as $0\preceq\mathbf{L}$), we have $\mathcal{C}_{n}\geq 0$.

######  Theorem 1.

$\frac{1}{\lambda_{2}(\mathcal{G})-1}$ is a tight upper bound on
$\mathcal{C}_{n}$.

###### Proof.

Consider the graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ with the set of
vertices, $\mathcal{V}$, and the set of edges, $\mathcal{E}$. Let us define a
new graph $\mathcal{G}_{com}(\mathcal{V},\mathcal{E}_{com})$ by extending
$\mathcal{G}(\mathcal{V},\mathcal{E})$ with adding all missing edges from node
$n$, such that, $\mathcal{E}\subseteq\mathcal{E}_{com}$, and node $n$ is
connected to all other nodes in the graph. Then,
$\mathbf{L}(\mathcal{G}_{com})$ can be written as

$\mathbf{L}(\mathcal{G}_{com})=\begin{pmatrix}\mathbf{L}(\mathcal{G}_{-n})+\mathbf{I},&-\mathbf{1}\\\
-\mathbf{1}^{T},&V-1\end{pmatrix}.$ (11)

Let $\mathbf{v}$ be an eigenvector of $\mathbf{L}(\mathcal{G}_{-n})$ that is
corresponding to $\lambda_{2}(\mathbf{L}(\mathcal{G}_{-n}))$. From (11), we
show that $\lambda_{2}(\mathcal{G}_{-n})+1$ is an eigenvalue of
$\mathbf{L}(\mathcal{G}_{com})$ as follows:

$\displaystyle\mathbf{L}(\mathcal{G}_{com})\begin{pmatrix}\mathbf{v}\\\
0\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\mathbf{L}(\mathcal{G}_{-n})+\mathbf{I},&-\mathbf{1}\\\
-\mathbf{1}^{T},&V-1\end{pmatrix}\begin{pmatrix}\mathbf{v}\\\ 0\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\mathbf{L}(\mathcal{G}_{-n})\mathbf{v}+\mathbf{I}\mathbf{v}\\\
-\mathbf{1}^{T}\mathbf{v}\end{pmatrix}\stackrel{{\scriptstyle({\rm
a})}}{{=}}\begin{pmatrix}\lambda_{2}(\mathcal{G}_{-n})\mathbf{v}+\mathbf{v}\\\
0\end{pmatrix}$
$\displaystyle=\begin{pmatrix}(\lambda_{2}(\mathcal{G}_{-n})+1)\mathbf{v}\\\
0\end{pmatrix}=[\lambda_{2}(\mathcal{G}_{-n})+1]\begin{pmatrix}\mathbf{v}\\\
0\end{pmatrix},$

where (a) follows from the fact that $-\mathbf{1}^{T}\mathbf{v}=0$ for a
connected graph, and $\mathbf{I}\mathbf{v}=\mathbf{v}$. Thus,
$\lambda_{2}(\mathcal{G}_{-n})+1$ is an eigenvalue of
$\mathbf{L}(\mathcal{G}_{com})$ that is different from the zero eigenvalue,
i.e., $\lambda_{2}(\mathcal{G}_{-n})+1\neq\lambda_{1}(\mathcal{G}_{com})$ and
$\lambda_{2}(\mathcal{G}_{com})\leq\lambda_{2}(\mathcal{G}_{-n})+1$.
Therefore,

$\displaystyle\lambda_{2}(\mathcal{G}_{-n})\geq\lambda_{2}(\mathcal{G}_{com})-1.$
(12)

Finally, since $\mathcal{E}\subseteq\mathcal{E}_{com}$,
$\lambda_{2}(\mathcal{G})\leq\lambda_{2}(\mathcal{G}_{com})$, (12) can be
written as

$\displaystyle\lambda_{2}(\mathcal{G}_{-n})\geq\lambda_{2}(\mathcal{G})-1.$
(13)

This shows that removing node $n$ from $\mathcal{G}$ can at least reduce the
algebraic connectivity $\lambda_{2}(\mathcal{G})$ by $1$, which depends on the
number of edges that connect node $n$ to the remaining nodes in $\mathcal{G}$.
From (13) and (10), we have

$\displaystyle\mathcal{C}_{n}\leq\frac{1}{\lambda_{2}(\mathcal{G})-1}.$ (14)

Inequality (14) reasonably implies that if $\mathcal{G}$ is highly connected,
removing a node from it would not affect the network connectivity much since
all nodes have high criticality and more connected. Assuming that
$\mathcal{G}$ is a complete graph, $\lambda_{2}(\mathcal{G})=V$, and
accordingly, $\lambda_{2}(\mathcal{G}_{-n})=\lambda_{2}(\mathcal{G})-1=V-1$.
In this case, we have

$\mathcal{C}_{n}=\frac{1}{\lambda_{2}(\mathcal{G}_{-n})}=\frac{1}{V-1},$

Which shows the tightness of upper bound. We point out that
$\mathcal{C}_{n}\approx\frac{1}{V}$ for large complete graphs. ∎

Definition 1 implies that the high criticality of nodes that cause severe
reduction in the remaining algebraic network connectivity should be balanced.
In this case, no node in the graph can severely impact the network resiliency
if it has accidentally or intentionally failed. Intuitively to make the
network more connected, the RISs should be utilized properly since they have
less probability of failures as compared to UAVs due to their limited
batteries. In addition, RISs will add more links to the network, which will
maximize the network connectivity and reduce the criticalities of the nodes.
Consequently, the signals of the UEs can be redirected via the RISs to less
critical UAV nodes, which results in more balanced network. One can achieve
this balance by assigning weights to edges connecting UE nodes to UAV nodes,
and the selection of the UE-RIS-UAV combinations relatively rely on these
weights. Thus, we propose to design the weight of link $e_{k}$ that connects
nodes $n$ and $m$ as follows

$w_{n,m}=\frac{1}{\mathcal{C}_{n}+\mathcal{C}_{m}},$ (15)

where $\mathcal{C}_{n}$ and $\mathcal{C}_{m}$ are the criticalities of nodes
$n$ and $m$, respectively. The weight $w_{n,m}$ is high if the criticalities
of the nodes $n$ and $m$ are low, thus a link between them via a possible RIS
would be highly created. The high critical UAV nodes are less likely to have
new links from the UEs via the RISs since their failures may significantly
degrade the network connectivity. Therefore, by carefully adding new links to
less critical UAV nodes, one can balance the criticality of all the UAV nodes
in the network.

##  III Problem Formulation

The problem of maximizing the connectivity of RIS-assisted UAV networks can be
stated as follows. Given a RIS-assisted UAV network represented by a graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$, what are the optimum combinations
between the UEs and the UAVs via optimizing phase shifts of the RISs in order
to maximize $\lambda_{2}(\mathbf{L})$ of the resulting network while balancing
the criticality of the UAV nodes? Essentially, deploying the RISs in the
network may result in connecting multiple UEs to multiple UAVs, which were not
connected together. It may also result in adding new alternative options to
the UEs if their scheduled high critical UAV nodes have failed. By adjusting
their phase shifts, RISs can smartly beamform the signals of the UEs to the
desired, less critical UAVs to maximize the network connectivity and make the
network more resilient against node failures.

We consider that multiple UEs are allowed to transmit simultaneously if their
mutual transmission coverage to the RISs is empty. Therefore, we have the
following UE-RIS-UAV association constraints:

  * •

Multiple UEs are allowed to transmit as long as they do not have common RISs
in their coverage transmissions.

  * •

Each RIS is connected to only one UE.

  * •

Each RIS reflects the signal of the selected UE to only one UAV.

  * •

Each UAV is connected to one RIS only.

Let $\mathcal{A}^{u,r}_{0}$ be a set of reachable UAVs that have indirect
communication links from the $u$-th UE through the $r$-th RIS, i.e.,
$\mathcal{A}^{u,r}_{0}=\\{a\in\mathcal{A}\backslash\mathcal{A}^{u}\mid\gamma^{r}_{u,a}\geq\gamma^{\text{RIS}}_{0}\\}$,
where $\mathcal{A}^{u}$ is defined above as the set of UAVs that have direct
links to the $u$-th UE. We aim at providing alternative links to connect the
UEs to the suitable UAVs in the set $\mathcal{A}_{0}^{u,r}$, $\forall
u\in\mathcal{U},r\in\mathcal{R}$. As such, the UEs do not miss the
communications if their scheduled UAV have failed. Let $X_{u,r}$ be a binary
variable that is equal to $1$ if the $u$-th UE is connected to the $r$-th RIS,
and zero otherwise. Now, let $Y^{u}_{r,a}$ be a binary variable that is equal
to $1$ if the $r$-th RIS is connected to the $a$-th UAV when the $u$-th UE is
selected to transmit, and zero otherwise. Let $\mathcal{U}_{t}$ be the set of
the possible transmitting UEs, where $\mathcal{U}_{t}\subset\mathcal{U}$. This
set $\mathcal{U}_{t}$ consists of multiple UEs that have empty mutual
transmission coverage to the RISs, which can be defined as
$\mathcal{U}_{t}=\\{u\in\mathcal{U}\mid(u,u^{\prime})\in\mathcal{U}^{2},\mathcal{R}_{u}\cap\mathcal{R}_{u^{\prime}}=\emptyset\\}$.
Therefore, the considered optimization problem of maximizing the network
connectivity is formulated as follows:

$\displaystyle\max_{\begin{subarray}{c}X_{u,r},Y^{u}_{r,a},\theta^{r}_{m}\end{subarray}}\lambda_{2}(\mathbf{L}^{\prime})$
(16a) $\displaystyle{\rm subject~{}to\
}\sum\limits_{u\in\mathcal{U}_{t}}X_{u,r}=1,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
r\in\mathcal{R},$ (16b)
$\displaystyle~{}~{}~{}~{}~{}~{}\sum_{u\in\mathcal{U}_{t}}\sum_{a\in\mathcal{A}^{u,r}_{0}}Y^{u}_{r,a}\leq
1,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
r\in\mathcal{R},$ (16c)
$\displaystyle~{}~{}~{}~{}~{}~{}\theta^{r}_{m}\in[0,2\pi),~{}~{}~{}~{}~{}~{}~{}~{}\forall
r\in\mathcal{R},m=\\{1,\ldots,M\\},$ (16d)
$\displaystyle~{}~{}~{}~{}~{}~{}X_{u,r}\in\\{0,1\\},Y^{u}_{r,a}\in\\{0,1\\},~{}~{}~{}\forall
r\in\mathcal{R},a\in\mathcal{A}.$ (16e)

In (16), constraint (16b) implies that each RIS receives a signal from a
single UE in the set $\mathcal{U}_{t}$. Constraint (16c) assures that each RIS
reflects the signal of its associated UE to only one UAV. This also means that
at maximum $R$ paths from the selected UEs to the suitable UAVs through the
RISs. Constraint (16d) is for the RIS phase shift optimization.

Since the above optimization problem (16) is NP-hard, we first propose
heuristic solutions to find feasible UE-RIS-UAV associations. Afterwards, we
optimize the phase shift of the RISs elements to smartly direct the signals of
the UEs to the suitable UAV nodes.

##  IV Proposed Solutions

In this section, we reformulate the problem (16), and then develop two
heuristic solutions to maximize $\lambda_{2}(\mathbf{L}^{\prime})$. In Section
IV-A, we relax the problem in (17) to a convex optimization problem in order
to be formulated as an SDP problem. In Section IV-B, we propose a novel
perturbation heuristic that selects the maximum possible increase in
$\lambda_{2}(\mathbf{L}^{\prime})$ based on the weighted values of the
differences between the values of the Fiedler vector.

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

$\displaystyle\max_{\mathbf{z}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\lambda_{2}(\mathbf{L}^{\prime}(\mathbf{z}))$
(17) $\displaystyle{\rm subject~{}to\
}~{}~{}~{}~{}\mathbf{1}^{T}\mathbf{z}=R,$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathbf{z}\in\\{0,1\\}^{|\mathbf{z}|},$

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

$\mathbf{L}^{\prime}(\mathbf{z})=\mathbf{L}+\sum^{|\mathbf{z}|}_{l=1}z_{l}w_{l}\mathbf{a}_{l}\mathbf{a}^{T}_{l},$
(18)

where $\mathbf{a}_{l}$ is the incidence vector resulting from adding link $l$
to the original graph $\mathcal{G}$, $\mathbf{1}^{T}\mathbf{z}=R$ indicates
that the number of chosen RISs is $R$, $\mathbf{L}$ is the Laplacian matrix of
the original graph $\mathcal{G}$, and $w_{l}$ is the weight of a constructed
edge that connects a RIS with a UE and a UAV as given in (15). The $l$-th
element of $\mathbf{z}$, denoted by $z_{l}$, is either $1$ or $0$, which
corresponds to whether a RIS should be chosen or not, respectively. Clearly,
the dimension of $\mathbf{L}$ and $\mathbf{L}^{\prime}(\mathbf{z})$ is
$V\times V$. We notice that the effect of adding RISs appears only in the edge
set $\mathcal{E}$, and not in the node set $\mathcal{V}$. For ease of
illustration, (18) can be written as

$\mathbf{L}^{\prime}=\mathbf{L}+(\mathbf{z}\otimes\mathbf{I}_{|\mathbf{z}|})\Lambda,$
(19)

where
$\Lambda=\big{[}(\mathbf{A}_{1}diag(\mathbf{w}_{1})\mathbf{A}^{T}_{1})^{T},\ldots,(\mathbf{A}_{|\mathbf{z}|}diag(\mathbf{w}_{|\mathbf{z}|})\mathbf{A}^{T}_{|\mathbf{z}|})^{T}\big{]}^{T}$
and the block $(\mathbf{A}_{1}diag(\mathbf{w}_{1})\mathbf{A}^{T}_{1})^{T}$ is
a $V\times V$ matrix.

The problem in (17) is combinatorial, and can be solved exactly by exhaustive
search by computing $\lambda_{2}(\mathbf{L}^{\prime})$ for
${|\mathbf{z}|\choose R}$ Laplacian matrices. However, this is not practical
for large graphs that have large $|\mathbf{z}|$ and $R$. Instead, we are
interested in proposing efficient heuristics for solving the problem in (17).

###  IV-A Convex Relaxation

The proposed SDP solution for multiple RISs in this subsection is mainly
related to the preliminary work [1] but the authors considered a simple case
of one RIS without utilizing the criticality of the nodes.

The optimization vector in (17) 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.
Since (17) is NP-hard problem with high complexity, 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 (17) as

$\displaystyle\max_{\mathbf{z}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\lambda_{2}(\mathbf{L}^{\prime}(\mathbf{z}))$
(20) $\displaystyle{\rm subject~{}to\
}~{}~{}~{}~{}~{}~{}\mathbf{1}^{T}\mathbf{z}=R,$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}0\leq\mathbf{z}\leq
1.$

In [17], it was shown that $\lambda_{2}(\mathbf{L}^{\prime}(\mathbf{z}))$ in
(20) 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 (20) is a convex optimization problem [17], and is equivalent to
the following SDP optimization problem [28]

$\displaystyle\max_{\mathbf{z},q}q$ (21) $\displaystyle{\rm subject~{}to\
}q(\mathbf{I}-\frac{1}{|\mathbf{z}|}\mathbf{1}\mathbf{1}^{T})\preceq\mathbf{L}^{\prime}(\mathbf{z}),\mathbf{1}^{T}\mathbf{z}=R,0\leq\mathbf{z}\leq
1,$

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.

The solution to the SDP optimization problem in (21) is explained as follows.
First, we calculate the corresponding phase shifts of the RISs from each
feasible UE node to each feasible UAV node, such that we generate all the
possible schedules $\mathbf{z}$. In particular, the corresponding phase shift
at PRU of the $r$-th RIS to reflect the signal of the $u$-th UE to the $a$-th
UAV is calculated as follows [12]

$\theta^{r}_{m}=\pi\frac{f_{c}}{c}\big{\\{}d_{b}(m_{b}-1)\psi^{\text{RA}}_{r,a}\phi^{\text{RA}}_{r,a}+d_{c}(m_{c}-1)\psi^{\text{RA}}_{r,a}\varphi^{\text{RA}}_{r,a}\\\
+d_{b}(m_{b}-1)\psi^{\text{UR}}_{u,r}\phi^{\text{UR}}_{u,r}+d_{c}(m_{c}-1)\psi^{\text{UR}}_{u,r}\varphi^{\text{UR}}_{u,r}\big{\\}}.$
(22)

Second, we use off-the-shelf CVX software solver [29] to solve the SDP
optimization problem in (21) and obtain $\mathbf{z}$. The entries of the
output vector $\mathbf{z}$ resulting from the CVX solver are continuous, that
are between $0$ and $1$, and accordingly, we consider to round the maximum $R$
entries to $1$ while others are rounded to zero.

Note that if $n$ is an articulation node (i.e., the removal of that node
disconnects the network [16]), then $\lambda_{2}(\mathcal{G}_{-n})$
theoretically equals to zero. This might cause numerical problem when we
calculate the weight in the network connectivity. To avoid this problem, we
introduce a small threshold, $\epsilon$. If
$\lambda_{2}(\mathcal{G}_{-n})\leq\epsilon$, we set
$\lambda_{2}(\mathcal{G}_{-n})=\epsilon$. The steps of calculating the edge
weights are summarized in Algorithm 1.

Algorithm 1 Weight Calculation Based On Nodes Criticality

1:Input: Construct $\mathcal{G}(\mathcal{V},\mathcal{E})$ and set
$\epsilon=10^{-5}$

2:for For each edge $l$ that connects two nodes $u,a$ do

3: Form the Laplacian matrix $\mathbf{L}(\mathcal{G}_{-u})$ as (8) and find
the corresponding criticality value $\mathcal{C}_{u}$:

4: if $\lambda_{2}(\mathcal{G}_{-u})>\epsilon$ then
$\mathcal{C}_{u}=1/\lambda_{2}(\mathcal{G}_{-u})$

5: else $\mathcal{C}_{u}=1/\epsilon$

6: end if

7: Form the Laplacian matrix $\mathbf{L}(\mathcal{G}_{-a})$ as (8) and find
the corresponding criticality value $\mathcal{C}_{a}$:

8: if $\lambda_{2}(\mathcal{G}_{-a})>\epsilon$ then
$\mathcal{C}_{a}=1/\lambda_{2}(\mathcal{G}_{-a})$

9: else $\mathcal{C}_{a}=1/\epsilon$

10: end if

11: Calculate the weight of edge $l$ as (15).

12:end for

###  IV-B A Greedy Perturbation Heuristic

The SDP optimization has high complexity when $|\mathbf{z}|$ and $R$ are
large, which is the case of large networks. Instead, we propose an effective
greedy heuristic for solving (17) based on the values of the Fiedler vector,
which is denoted by $\mathbf{v}$. On the other hand, unlike the exhaustive
search that calculates $\lambda_{2}(\mathbf{L}^{\prime})$ for each possible
association of UE-RIS-UAV, the proposed perturbation heuristic adds the $R$
edges one at a time by calculating only the weighted values of the differences
between the values of the Fiedler vector. In the following proposition, we
prove the upper bound of $\lambda_{2}(\mathbf{L}^{\prime})$, and the proposed
perturbation heuristic will be described next.

######  Proposition 1.

$\lambda_{2}(\mathbf{L}^{\prime})$ is upper bounded by
$\lambda_{2}(\mathbf{L})+w_{l}(v_{u}-v_{a})^{2}$, where $v_{u}$ and $v_{a}$
are the corresponding values of the $u$-th and $a$-th indices of the Fiedler
vector $\mathbf{v}$ of $\lambda_{2}(\mathbf{L})$ and $w_{l}$ is the weight of
edge $l$ as given in (15).

###### Proof.

For simplicity, we use $V_{ua}=(v_{u}-v_{a})^{2}$. If $\mathbf{v}$ is an
eigenvector with unit norm corresponding to $\lambda_{2}(\mathbf{L})$, then
$\mathbf{v}\mathbf{v}^{T}$ is a supergradient of $\lambda_{2}(\mathbf{L})$
[30]. This means for any symmetric matrix $Y$ with size $V\times V$, we have

$\lambda_{2}(\mathbf{L}+Y)\leq\lambda_{2}(\mathbf{L})+\textbf{Tr}(Y\mathbf{v}\mathbf{v}^{T}).$
(23)

In one connected graph, $\lambda_{2}$ is isolated, where
$\lambda_{1}<\lambda_{2}<\lambda_{3}$, then $\lambda_{2}(\mathbf{L}^{\prime})$
is an analytic function of $\mathbf{L}^{\prime}$, and therefore of
$\mathbf{z}$. In this case the supergradient is the gradient [30], i.e.,

$\pdv{\lambda_{2}(\mathbf{L}^{\prime})}{z_{l}}=\mathbf{v}^{T}\pdv{\mathbf{L}^{\prime}(\mathbf{z})}{z_{l}}\mathbf{v},$
(24)

where $\mathbf{v}$ is the unique normalized eigenvector corresponding to
$\lambda_{2}(\mathbf{L}^{\prime})$. By taking the partial derivative of

$\mathbf{L}^{\prime}(\mathbf{z})=\mathbf{L}+\sum^{|\mathbf{z}|}_{l=1}z_{l}w_{l}\mathbf{a}_{l}\mathbf{a}^{T}_{l},$
(25)

we have

$\pdv{\mathbf{L}^{\prime}(\mathbf{z})}{z_{l}}=w_{l}\mathbf{a}_{l}\mathbf{a}_{l}^{T}.$
(26)

By substituting (26) in (24), we have

$\displaystyle\pdv{\lambda_{2}(\mathbf{L}^{\prime})}{z_{l}}=w_{l}\mathbf{v}^{T}\mathbf{a}_{l}\mathbf{a}_{l}^{T}\mathbf{v}=w_{l}V_{ua}.$
(27)

Therefore, the partial derivative of $\lambda_{2}(\mathbf{L}^{\prime})$ with
respect to $z_{l}$ is $w_{l}V_{ua}$, where $l$ is the added edge between UE
node $u$ and UAV node $a$. When $\lambda_{2}$ is isolated, $w_{l}V_{ua}$ gives
the first order approximation of the increase in
$\lambda_{2}(\mathbf{L}^{\prime})$, if edge $l$ is added to the graph.
Therefore, our step (2) of the greedy heuristic corresponds to adding an edge,
from among the remaining $R$ edge candidates, that gives the largest possible
increase in $\lambda_{2}(\mathbf{L}^{\prime})$, according to a first order
approximation. Therefore, we can say that if $\mathbf{v}\mathbf{v}^{T}$ is a
supergradient of $\lambda_{2}(\mathbf{L}^{\prime})$ and based on (23),
$\lambda_{2}(\mathbf{L}^{\prime})$ can be written as follows

$\displaystyle\lambda_{2}(\mathbf{L}^{\prime})$
$\displaystyle=\lambda_{2}(\mathbf{L}+w_{l}\mathbf{a}_{l}\mathbf{a}_{l}^{T})\leq\lambda_{2}(\mathbf{L})+\textbf{Tr}(w_{l}\mathbf{a}_{l}\mathbf{a}_{l}^{T}\mathbf{v}\mathbf{v}^{T})$
(28)
$\displaystyle\leq\lambda_{2}(\mathbf{L})+w_{l}\textbf{Tr}(\mathbf{a}_{l}\mathbf{a}_{l}^{T}\mathbf{v}\mathbf{v}^{T})\leq\lambda_{2}(\mathbf{L})+w_{l}V_{ua}.$

(28) completes the proof. ∎

Greedy Heuristic: Given Proposition 1, in each step of the proposed heuristic,
we choose an edge $l$ that connects UE $u$ and UAV $a$, which has the largest
value of $w_{l}V_{ua}$ that provides the maximum possible increase in
$\lambda_{2}(\mathbf{L}^{\prime})$. Starting from $\mathcal{G}$ and
$\mathbf{L}$, we add new edges one at a time as follows:

  * •

Calculate $\mathbf{v}$, a unit eigenvector corresponding to
$\lambda_{2}(\mathbf{L})$, where $\mathbf{L}$ is the current Laplacian matrix.

  * •

From the remaining candidate edges corresponding to the UE-RIS-UAV schedules,
add an edge $l$ connecting UE $u$ and UAV $a$ with the largest $w_{l}V_{ua}$.

  * •

Remove all the UE-RIS-UAV candidate links of the already selected UE, RIS,
UAV.

We stop the greedy heuristic when there is no feasible link to add. Since the
number of UEs/UAVs is larger than the number of RISs, this heuristic stops
when there is no more available RISs that have not been selected. The steps of
the greedy algorithm are given in Algorithm 2.

Algorithm 2 The Proposed Greedy Perturbation Heuristic

1:Input: UEs, UAVs, RISs, and network topology.

2:Initially set $\mathbf{L}^{\prime}\leftarrow\mathbf{L}$

3:for $i=1,2,\ldots,R$ do

4: Calculate $\mathbf{v}$ of the associated $\mathbf{L}^{\prime}$.

5: From the remaining candidate edges corresponding to the UE-RIS-UAV
schedules, add an edge $l$ connecting UE $u$ and UAV $a$ with largest
$w_{l}V_{ua}$, where $w_{l}$ is calculated as in Algorithm 1.

6: Calculate the corresponding phase shift at PRU of the selected $r$-th RIS
that reflects the signal of the $u$-th UE to the $a$-th UAV as in (22).

7: Based on the selected edge $l$, update $\mathbf{L}^{\prime}$.

8: Remove all the UE-RIS-UAV candidate links of the already selected UE, RIS,
UAV.

9:end for

10:Output: $\lambda_{2}(\mathbf{L}^{\prime})$.

##  V Perturbation Heuristic Analysis

In this section, we derive the upper and lower bounds of
$\lambda_{2}(\mathbf{L}^{\prime})$ based on the proposed perturbation
heuristic solution. Then, the computational complexity of the proposed
schemes, as compared to the exhaustive search, is analyzed in Section V-B.

###  V-A Lower and Upper Bounds Analysis

Given the proposed perturbation heuristic, Proposition 2 derives the lower and
upper bounds on the algebraic connectivity of a graph obtained by adding $R$
edges connecting UE nodes to UAV nodes to a single connected graph.

######  Proposition 2.

Let $\mathbf{L}$ be the Laplacian matrix of the original connected graph
$\mathcal{G}$. Suppose we add an edge $l$ that connects UE node $u$ to UAV
node $a$ through RIS $r$ to $\mathcal{G}$. Then, we have the following lower
and upper bounds, respectively, for
$\lambda_{2}(\mathbf{L}+w_{l}\mathbf{a}_{l}\mathbf{a}_{l}^{T})$:

$\displaystyle\lambda_{2}(\mathbf{L}+w_{l}\mathbf{a}_{l}\mathbf{a}_{l}^{T})\geq\lambda_{2}$
$\displaystyle+\frac{w_{l}V_{ua}+\delta+2w_{l}-\sqrt{5w_{l}V_{ua}-w_{l}\delta^{2}+4w_{l}^{2}+4w_{l}\delta}}{2},$
(29)
$\displaystyle\lambda_{2}(\mathbf{L}+w_{l}\mathbf{a}_{l}\mathbf{a}_{l}^{T})\leq\lambda_{2}+\frac{w_{l}V_{ua}}{1+w_{l}(2-V_{ua})/(\lambda_{n}-\lambda_{2})},$
(30)

where $\delta=\lambda_{3}-\lambda_{2}$.

###### Proof.

Let $\mathbf{L}=\mathbf{Q}\mathbf{D}\mathbf{Q}^{T}$ be the eigenvalue
decomposition of $\mathbf{L}$, where $\mathbf{D}$ is the diagonal matrix whose
diagonal elements are the corresponding eigenvalues, denoted by
$\lambda_{1},\lambda_{2},\ldots,\lambda_{V}$, and $\mathbf{Q}$ is an
orthogonal matrix whose columns are the real, orthonormal eigenvectors of
$\mathbf{L}$. Suppose that all entries in $\mathbf{D}$ are distinct (same
process applies if eigenvalues other than $\lambda_{2}$ are repeated [30]).
Note that $\mathbf{a}_{l}\mathbf{a}_{l}^{T}$ is a matrix of rank-one and
therefore our analysis follows the same steps used in [31] for eigenvalues
perturbation of a matrix with rank-one update. In particular, the standard
form in [31] is

$\displaystyle\underbrace{\mathbf{L}^{\prime}}_{\text{updated
matrix}}=\mathbf{Q}\underbrace{\mathbf{D}}_{\text{diagonal matrix with
$\lambda_{i}$
entries}}\mathbf{Q}^{T}+\rho\underbrace{\mathbf{a}_{l}\mathbf{a}_{l}^{T}}_{\text{rank-
one}},$ (31)

where $\rho>0$, which will be replaced by $w_{l}$. Recall that $w_{l}$ is a
non-negative value. Thus, we can write (31) as

$\displaystyle\mathbf{Q}\mathbf{L}^{\prime}\mathbf{Q}^{T}=\mathbf{D}+w_{l}(\mathbf{Q}\mathbf{a}_{l})(\mathbf{Q}\mathbf{a}_{l})^{T}.$
(32)

We denote the eigenvalues of $\mathbf{L}^{\prime}$ by
$\tilde{\lambda}_{1},\tilde{\lambda}_{2},\ldots,\tilde{\lambda}_{V}$. Since we
have one graph component, we assume
$\tilde{\lambda}_{i}\leq\tilde{\lambda}_{i+1}$, and similarly,
$\lambda_{i}\leq\lambda_{i+1}$. Note that the matrices $\mathbf{L}$ and
$\mathbf{L}^{\prime}$ both have eigenvalue $0$ with the corresponding
eigenvector $\mathbf{1}$, i.e., $\lambda_{1}$ and $\tilde{\lambda}_{1}$ are
zero. Thus, we are interested in the remaining $V-1$ eigenvalues of
$\mathbf{L}^{\prime}$, i.e., particularly $\tilde{\lambda}_{2}$. Therefore,
the eigenvalues of $\mathbf{L}^{\prime}$ are the same as those of
$\mathbf{D}+w_{l}\mathbf{u}\mathbf{u}^{T}$, where
$\mathbf{u}=\mathbf{Q}\mathbf{a}_{l}$. To find the eigenvalues of
$\mathbf{L}^{\prime}$, assume first that
$\mathbf{D}-\tilde{\lambda}\mathbf{I}$ is non-singular, we compute the
characteristic polynomial as follows:

$\displaystyle\text{det}(\mathbf{L}^{\prime}-\tilde{\lambda}\mathbf{I})$
$\displaystyle=\text{det}(\mathbf{D}+w_{l}\mathbf{u}\mathbf{u}^{T}-\tilde{\lambda}\mathbf{I})$
$\displaystyle=\text{det}((\mathbf{D}-\tilde{\lambda}\mathbf{I})(\mathbf{I}+w_{l}(\mathbf{D}-\tilde{\lambda}\mathbf{I})^{-1}\mathbf{u}\mathbf{u}^{T}))$
$\displaystyle=\text{det}(\mathbf{D}-\tilde{\lambda}\mathbf{I})\text{det}(\mathbf{I}+w_{l}(\mathbf{D}-\tilde{\lambda}\mathbf{I})^{-1}\mathbf{u}\mathbf{u}^{T}).$

Since $\mathbf{D}-\tilde{\lambda}\mathbf{I}$ is non-singular,
$\text{det}(\mathbf{I}+w_{l}(\mathbf{D}-\tilde{\lambda}\mathbf{I})^{-1}\mathbf{u}\mathbf{u}^{T})=0$
whenever $\tilde{\lambda}$ is an eigenvalue. Note that
$\mathbf{I}+w_{l}(\mathbf{D}-\tilde{\lambda}\mathbf{I})^{-1}\mathbf{u}\mathbf{u}^{T})$
is the identity plus rank-one matrix. The determinant of such matrix is as
follows333By definition, if $\mathbf{x}$ and $\mathbf{y}$ are vectors,
$\text{det}(\mathbf{I}+\mathbf{x}\mathbf{y}^{T})=1+\mathbf{y}^{T}\mathbf{x}$
[26].:

$\displaystyle\text{det}(\mathbf{I}+w_{l}(\mathbf{D}-\tilde{\lambda}\mathbf{I})^{-1}\mathbf{u}\mathbf{u}^{T})$
$\displaystyle=(1+w_{l}\mathbf{u}^{T}(\mathbf{D}-\tilde{\lambda}\mathbf{I})^{-1}\mathbf{u})$
$\displaystyle=\underbrace{\big{(}1+w_{l}\sum_{i=2}^{V}\frac{u_{i}^{2}}{\lambda_{i}-\tilde{\lambda}}\big{)}}_{\text{secular
equation}},$ (33)

where $u_{i}=\mathbf{Q}_{i}^{T}\mathbf{a}_{l}$. Thus,
$u_{1}=\mathbf{Q}_{1}^{T}\mathbf{a}_{l}=0$ since the values of the eigenvector
corresponding to $\lambda_{1}$ is the same and
$u_{2}=\mathbf{Q}_{2}^{T}\mathbf{a}_{l}=v_{u}-v_{a}$. Golub [31] showed that
in the above situation the eigenvalues of $\mathbf{L}^{\prime}$ are the zeros
of the secular equation, which is given as follows

$\displaystyle
f(\tilde{\lambda})=1+w_{l}\sum_{i=2}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}$
$\displaystyle
1+w_{l}\sum_{i=2}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}=0\to
w_{l}\sum_{i=2}^{V}\frac{u^{2}_{i}}{\tilde{\lambda}-\lambda_{i}}=1.$ (34)

Figure 2:
$f(\tilde{\lambda})=1+\frac{0.5}{2-\tilde{\lambda}}+\frac{0.5}{3-\tilde{\lambda}}+\frac{0.5}{4-\tilde{\lambda}}$
in the interval $(\lambda_{2},\lambda_{3})$ for $\lambda_{i}=i,u^{2}_{i}=0.5$,
$i=2,3,4$ and $w_{l}=1$.

Consider $u^{2}_{i}=0.5,\lambda_{i}=i,i=\\{2,3,4\\}$, $V=4$, and $w_{l}=1$,
the function
$f(\tilde{\lambda})=1+\sum_{i=2}^{4}\frac{0.5}{\lambda_{i}-\tilde{\lambda}}$
has the graph shown in Fig. 2 for the interval $(\lambda_{2},\lambda_{3})$.
Since
$f^{\prime}(\tilde{\lambda})=\sum_{i=2}^{4}\frac{u^{2}_{i}}{(\lambda_{i}-\tilde{\lambda})^{2}}>0$,
the function is strictly increasing in the interval
($\lambda_{i},\lambda_{i+1}$). Thus, the roots of $f(\tilde{\lambda})$ are
interlaced by the $\lambda_{i}$. Since $\mathbf{L}^{\prime}$ has more edges
than $\mathbf{L}$ and by eigenvalue interlacing, we have [31, 32]

$\displaystyle\lambda_{i}\leq\tilde{\lambda}_{i}\leq\lambda_{i+1},~{}~{}~{}~{}~{}~{}~{}~{}\forall
i=2,\ldots,V-1$

Let us consider $\tilde{\lambda}$ in the interval $(\lambda_{2},\lambda_{3})$.
For $\tilde{\lambda}$ in the interval $(\lambda_{2},\lambda_{3})$, from Fig.
2, if $f(\tilde{\lambda})\leq 0$, then
$\tilde{\lambda}\leq\tilde{\lambda}_{2}$. It is easy to see that
$f(\tilde{\lambda})\leq 0$ is equivalent to

$\displaystyle w_{l}\frac{u^{2}_{2}}{\tilde{\lambda}-\lambda_{2}}\geq
1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}.$ (35)

Thus, we conclude that (35) implies $\tilde{\lambda}\leq\tilde{\lambda}_{2}$.

Recall $\lVert
u\rVert=\lVert\mathbf{Q}^{T}\mathbf{a}_{l}\rVert=\lVert\mathbf{a}_{l}\rVert=2$,
$\sum_{i=3}^{V}u_{i}^{2}\leq 2$ [30]. From the right hand side of (35), we
have

$\displaystyle
1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}\overset{(a)}{\leq}1+\frac{w_{l}}{\lambda_{3}-\tilde{\lambda}}\sum_{i=3}^{V}u_{i}^{2}\overset{(b)}{\leq}1+w_{l}\frac{2}{\lambda_{3}-\tilde{\lambda}},$
(36)

where $(a)$ and $(b)$ follow from the facts that
$\lambda_{3}\leq\lambda_{4},\ldots,\leq\lambda_{n}$ and
$\sum_{i=3}^{V}u^{2}_{i}\leq 2$, respectively. From (36), if

$\displaystyle w_{l}\frac{u^{2}_{2}}{\tilde{\lambda}-\lambda_{2}}\geq
1+w_{l}\frac{2}{\lambda_{3}-\tilde{\lambda}},$ (37)

then $\tilde{\lambda}\leq\tilde{\lambda}_{2}$. We set
$\tilde{\lambda}-\lambda_{2}=\epsilon$ and $\lambda_{3}-\lambda_{2}=\delta$ in
(37). We aim to find $\epsilon>0$ (i.e., $\tilde{\lambda}>\lambda_{2}$) such
that

$w_{l}\frac{u^{2}_{2}}{\epsilon}\geq 1+w_{l}\frac{2}{\delta-\epsilon},$ (38)

By solving (38), we can verify that

$\displaystyle\epsilon=\frac{w_{l}u_{2}^{2}+\delta+2w_{l}-\sqrt{w_{l}(u_{2}^{2}-\delta^{2})+4w_{l}^{2}+4w_{l}(u_{2}^{2}+\delta)}}{2},$
(39)

satisfies (38). Thus, the lower bound is

$\displaystyle\tilde{\lambda}_{2}$
$\displaystyle\geq\lambda_{2}+\frac{w_{l}u_{2}^{2}+\delta+2w_{l}-\sqrt{5w_{l}u_{2}^{2}-w_{l}\delta^{2}+4w_{l}^{2}+4w_{l}\delta}}{2},$
(40)

where $u_{2}^{2}=V_{ua}$. This concludes that (40) gives the lower bound in
(2).

Now, we derive the upper bound of $\tilde{\lambda}_{2}$. A sharper upper bound
than (28) can be obtained using the secular equation. From (V-A), the
algebraic connectivity of $\mathbf{L}^{\prime}$ is the number
$\tilde{\lambda}_{2}\in(\lambda_{2},\lambda_{3})$ satisfying

$\displaystyle
w_{l}\frac{u^{2}_{2}}{\tilde{\lambda}-\lambda_{2}}+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\tilde{\lambda}-\lambda_{i}}=1$
$\displaystyle
w_{l}\frac{u^{2}_{2}}{\tilde{\lambda}-\lambda_{2}}=1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}$
$\displaystyle\frac{w_{l}}{\tilde{\lambda}-\lambda_{2}}=\frac{1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}}{u^{2}_{2}}$
$\displaystyle\tilde{\lambda}-\lambda_{2}=\frac{w_{l}u^{2}_{2}}{1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}}$
$\displaystyle\tilde{\lambda}=\lambda_{2}+\frac{w_{l}u^{2}_{2}}{1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}}}$

For the special case of $\tilde{\lambda}=\tilde{\lambda}_{2}$, we have

$\displaystyle\tilde{\lambda}_{2}=\lambda_{2}+\frac{w_{l}u^{2}_{2}}{1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\tilde{\lambda}_{2}}}.$

Thus, the upper bound of $\tilde{\lambda}_{2}$ is given as follows

$\displaystyle\tilde{\lambda}_{2}\overset{(a)}{\leq}\lambda_{2}+\frac{w_{l}u^{2}_{2}}{1+w_{l}\sum_{i=3}^{V}\frac{u^{2}_{i}}{\lambda_{i}-\lambda_{2}}}$
$\displaystyle\tilde{\lambda}_{2}\overset{(b)}{\leq}\lambda_{2}+\frac{w_{l}u^{2}_{2}}{1+w_{l}(\frac{1}{\lambda_{n}-\lambda_{2}}(\sum_{i=2}^{V}u^{2}_{i}-u^{2}_{2}))}$
(41)
$\displaystyle\tilde{\lambda}_{2}\overset{(c)}{\leq}\lambda_{2}+\frac{w_{l}V_{ua}}{1+w_{l}(2-V_{ua})/(\lambda_{n}-\lambda_{2})},$

where $(a)$, $(b)$, and $(c)$ come from $\lambda_{2}<\tilde{\lambda}_{2}$,
$\lambda_{n}\geq\lambda_{n-1},\ldots,\geq\lambda_{2}$,
$\sum_{i=2}^{V}u^{2}_{i}=2$, and $u_{2}^{2}=V_{ua}$, respectively. This
concludes that (V-A) gives the upper bound in (30). ∎

###  V-B Computational Complexity

The exhaustive search requires a computational complexity of calculating
$\lambda_{2}(\mathbf{L}^{\prime})$ for ${|\mathbf{z}|\choose R}$ Laplacian
matrices, in which each Laplacian matrix computation requires
$\mathcal{O}\big{(}4E^{\prime}V^{3}/3\big{)}$ [33]. Thus, exhaustive search
requires $\mathcal{O}\big{(}{|\mathbf{z}|\choose R}4E^{\prime}V^{3}/3\big{)}$
operations. On the other hand, the SDP optimization for the convex relaxation
runs in high computational complexity for large $|\mathbf{z}|$. The proposed
perturbation heuristic requires only an eigenvector value computation, as
opposed to the exhaustive search. In particular, for the first added link, it
computes the vector $\mathbf{v}$ of the current $\mathbf{L}$. Computing all
the eigenvectors of an $V\times V$ dense matrix costs approximately
$\mathcal{O}(4V^{3}/3)$ arithmetic operations [30]. Since we have at maximum
$R$ possible links to be added, the proposed perturbation solution runs in
$\mathcal{O}(4RV^{3}/3+4RE^{\prime}V^{3}/3)=\mathcal{O}(4RV^{3}/3(1+E^{\prime}))\approx\mathcal{O}(4RV^{3}E^{\prime}/3)$
arithmetic operations.

##  VI Numerical Results

We run MATLAB simulations to demonstrate the viability of the proposed
schemes, and their superiority to the existing solutions. The simulation
parameters of RISs configurations and UAV communications are consistent with
those used in [22] and [12], respectively. We consider a RIS-assisted UAV
system in an area of $150~{}m\times 150~{}m$, where the RISs have fixed
locations and the UEs and the UAVs are distributed randomly. The RISs are
located at an altitude of $20$ m, $M=100$, $d_{r}=5$ cm, $d_{c}=5$ cm,
$\beta_{0}=10^{-6}$, $N_{0}=-130$ dBm, the altitude of the UAVs is $50$ m,
$f_{c}=3\times 10^{9}$ Hz, $c=3\times 10^{8}$ m/s, $\alpha=4$, $p=1$ watt,
$P=5$ watt, $\gamma_{0}^{\text{(U)}}=85$ dB, and $\gamma_{0}^{\text{(A)}}=80$
dB. Unless specified otherwise, $A=10$, $U=15$, $\gamma^{\text{(RIS)}}_{0}=30$
dB, and $\epsilon=10^{-5}$.

The optimization problem in (16) is solved using the two proposed heuristics
in Section IV-A and Section IV-B, denoted by SDP and Proposed Perturbation,
which are inspired by [1], [30], respectively. For the sake of numerical
comparison, the problem in (16) is solved optimally via exhaustive search,
which searches over all the feasible possible links between the UEs and the
UAVs through the RISs, and then selects the maximum
$\lambda_{2}(\mathbf{L}^{\prime})$. In addition, we consider solving (16)
using the two benchmark schemes: original network without RISs deployment and
random link selection. Finally, we implement the upper and lower bounds, which
are computed from (30) and (2), respectively. Our performance measure is the
network connectivity, which we calculate using $500$ iterations at each chosen
value of UE, UAV, RIS, and SNR threshold of the RISs. In each iteration, we
change the locations of the UEs and the UAVs.

In Fig. 3, we plot the average network connectivity of the proposed and
benchmark schemes versus the number of UEs $U$. From Fig. 3, we can see that
the proposed SDP and perturbation outperform the original scheme in terms of
network connectivity. The results from the perturbation scheme are very close
to the actual optimal value obtained using exhaustive search. This is because
the perturbation scheme calculates the relative values of the Fiedler vector
and selects the largest value that offers the possible maximum increase in the
network connectivity, which is corresponding to the desired UE-RIS-UAV link.
For this reason, the performance of the perturbation heuristic is also close
to the upper bound. Due to controlling the phase shift of the RISs, the
proposed schemes judiciously establish new links that connect the UEs to the
desired UAVs such that the UEs do not miss the communications to the network
while improving network connectivity. Between these two proposed solutions,
the perturbation heuristic significantly outperforms SDP since the latter is
sub-optimal. The original scheme that is without RISs deployment has poor
performance. This interestingly shows that by adding a few number of low-cost
passive nodes, the average network connectivity of RIS-assisted UAV networks
is improved significantly. Notably, the values of
$\lambda_{2}(\mathbf{L}^{\prime})$ of all the schemes decreases as the number
of UEs increases, since adding more unconnected UEs may result in a sparse
graph with low network connectivity.

We observe from Fig. 3 that the performance of the proposed perturbation is
very close to that of the optimal scheme. For ease of illustration, we include
the optimal scheme in Fig. 3 only and omit it in the remaining figures.

Figure 3: The average network connectivity $\lambda_{2}(\mathbf{L}^{\prime})$
versus the number of UEs $U$ for $7$ UAVs and $3$ RISs.

In Fig. 4 and Fig. 5, we show the average network connectivity of the proposed
and benchmark schemes versus the number of UAVs $A$ in different setups, i.e.,
small and large network sizes. For a small number of UAVs in Fig. 4, the
proposed SDP and perturbation schemes offer a slight performance gain in terms
of network connectivity compared to the original scheme. This is because our
proposed schemes have a few options of UE-UAV links, where the RISs can direct
the signal of the UEs to a few number of UAVs. However, when the number of
UAVs increases, the proposed schemes smartly select effective UE-RIS-UAV links
that significantly maximize the network connectivity. It is noted that
$\lambda_{2}(\mathbf{L}^{\prime})$ of all schemes increases with the number of
UAVs since adding more connected nodes to the network increases the number of
new links, which increases the network connectivity. This also can be seen in
Fig. 5 in the case of a large number of UAV nodes.

We observe that the values of $\lambda_{2}(\mathbf{L}^{\prime})$ in Fig. 3 are
smaller than the values of $\lambda_{2}(\mathbf{L}^{\prime})$ in Fig. 4 and
Fig. 5 for all the UAV configurations. This is reasonable because adding more
connected nodes of UAVs, adds more links to the network, thus improves the
network connectivity than adding more unconnected nodes of UEs. The latter
makes the network less connected (i.e., more UE nodes and no links between
them).

Figure 4: The average network connectivity $\lambda_{2}(\mathbf{L}^{\prime})$
versus the number of UAVs $A$ for $10$ UEs and $3$ RISs.

Figure 5: The average network connectivity $\lambda_{2}(\mathbf{L}^{\prime})$
versus a large number of UAVs $A$ for $22$ UEs and $3$ RISs.

Figure 6: The average network connectivity $\lambda_{2}(\mathbf{L}^{\prime})$
versus the number of RISs $R$ for $15$ UEs and $10$ UAVs.

To show that adding a few passive nodes is indeed crucial to maximize the
network connectivity of UAV networks, Fig. 6 plots the average network
connectivity versus the number of RISs $R$. For plotting this figure, we
change the number of RISs and distribute them randomly and consider $15$ UEs
and $10$ UAVs. For a small number of RISs in Fig. 6, the performance of all
schemes increases significantly since there are many possible selections of
UEs and UAVs for each RIS, and therefore all the schemes select the best
schedule that maximizes the network connectivity. However, when the number of
RISs increases ($R>5$), there are no more good opportunities of selecting
links that connect the remaining UEs to the remaining UAVs. Thus, we notice a
slight performance increase in the network connectivity of all the schemes.
This also shows that adding the first few links is important to improve the
network connectivity of the network. Note that the original scheme works
irrespective of the RISs deployment, thus it has fixed performance when we
change the number of RISs.

To show the superior performance of the proposed perturbation as compared to
the random link addition, Fig. 7 studies the average network connectivity
versus the number of RISs $R$ for $15$ UEs and $10$ UAVs. For fair comparison,
the random scheme is simulated similar to the perturbation heuristic except
that the selection of a link $l$ is randomly, not based on the maximum value
of $w_{l}V_{ua}$. Thus, both schemes add the same number of links to the
network. As expected, random addition performs poorly compared to the
perturbation heuristic. However, the point to be highlighted here is that a
large increase in the average network connectivity can be obtained by adding a
new edges carefully as we propose in the perturbation heuristic.

Figure 7: The average network connectivity $\lambda_{2}(\mathbf{L}^{\prime})$
versus the number of RISs $R$ for $15$ UEs and $10$ UAVs. A comparison of the
perturbation heuristic with a random link addition.

In Fig. 8, we show the impact of the SNR threshold $\gamma_{0}^{\text{(RIS)}}$
on the network connectivity. For small SNR threshold, all the links between
the UEs and the UAVs through the RIS can satisfy this SNR threshold, thus many
alternative links between the potential UE and the UAVs to select to maximize
the network connectivity. On the other hand, for high RIS SNR threshold, a few
UE-RIS-UAV links can satisfy such high SNR threshold. Thus, the network
connectivity of all the schemes is degraded, and it becomes relatively close
to the original scheme, which does not get affected by changing
$\gamma_{0}^{\text{(RIS)}}$.

Figure 8: The average network connectivity $\lambda_{2}(\mathbf{L}^{\prime})$
versus SNR threshold $\gamma_{0}^{\text{(RIS)}}$ in dB for $12$ UEs, $8$ UAVs,
and $3$ RISs.

It is worth remarking that while the random scheme adds a random link to the
network, the original scheme does not add a link. The proposed solutions
balance between the aforementioned aspects by judiciously selecting an
effective link, between a UE and a UAV, that maximizes the network
connectivity. This utilizes the benefits of the cooperation between an
appropriate scheduling algorithm design and RISs phase shift configurations.
Compared to the optimal scheme, the proposed perturbation heuristic is near-
optimal, however our proposed SDP has a certain degradation in network
connectivity that comes as the achieved polynomial computational complexity as
compared to the high complexity of the optimal scheme.

##  VII Conclusion

In this paper, we studied the effectiveness of RISs in UAV communications in
order to maximize the network connectivity by adjusting the algebraic
connectivity using the reflected links of the RISs. We started by defining the
nodes criticality and formulating the proposed network connectivity
maximization problem. By embedding the nodes criticality in the link
selection, we proposed two efficient solutions to solve the proposed problem.
First, we proposed to relax the problem to a convex problem to be formulated
as an SDP optimization problem that can be solved efficiently in polynomial
time using CVX. Then, we proposed a low-complexity, yet efficient,
perturbation heuristic that adds one UE-RIS-UAV link at a time by calculating
only the weighted difference between the values of the Fiedler eigenvector. We
also derived the lower and upper bounds of the algebraic connectivity obtained
by adding new links to the network based on the perturbation heuristic.
Through numerical studies, we evaluated the performance of the proposed
schemes via extensive simulations. We verified that the proposed schemes
result in improved network connectivity as compared to the existing solutions.
In particular, the perturbation heuristic is near-optimal solution that shows
very close results in terms of network connectivity compared to the optimal
solution.

## References

  * [1] Mohammed S. Al-Abiad, Mohammad Javad-Kalbasi, and Shahrokh Valaee, “Maximizing network connectivity for UAV communications via reconfigurable intelligent surfaces”, Accepted for publication in _(Globecom’ 2023), Kuala Lumpur, Malaysia,_ Available at: https://arxiv.org/pdf/2308.04675.pdf
  * [2] L. Ericsson, “Ericsson mobility report june 2020,” Ericsson, vol. 36, no. 2, pp. 1-36, 2020.
  * [3] M. S. Elbamby, C. Perfecto, M. Bennis, and K. Doppler, “Toward low-latency and ultra-reliable virtual reality,” _IEEE Network,_ vol. 32, no. 2, pp. 78–84, 2018.
  * [4] M. S. Al-Abiad, M. Z. Hassan, and M. J. Hossain, “Task offloading optimization in NOMA-enabled dual-hop mobile edge computing system using conflict graph,” in _IEEE Trans. on Wireless Commun.,_ vol. 22, no. 2, pp. 761-777, Feb. 2023.
  * [5] L. Godage, “Global unmanned aerial vehicle market (UAV) industry analysis and forecast (2018-2026),” Mont. Ledger Boston, MA, USA, 2019.
  * [6] Mohammed S. Al-Abiad and M. J. Hossain, “Coordinated scheduling and decentralized federated learning using conflict clustering graphs in fog-assisted IoD networks,” _IEEE Trans. on Vehicular Tech._ vol. 72, no. 3, pp. 3455-3472, Mar. 2023.
  * [7] M. B. Ghorbel, D. Rodríguez-Duarte, H. Ghazzai, M. J. Hossain, and H. Menouar, “Joint position and travel path optimization for energy efficient wireless data gathering using unmanned aerial vehicles,” in _IEEE Trans. Veh. Technol.,_ vol. 68, no. 3, pp. 2165-2175, Mar. 2019.
  * [8] H. Dahrouj, A. Douik, F. Rayal, T. Y. Al-Naffouri, and M.-S. Alouini, “Cost-effective hybrid RF/FSO backhaul solution for next generation wireless systems,” in _IEEE Wireless Commun.,_ vol. 22, no. 5, pp. 98-104, Oct. 2015.
  * [9] M. Ammous and S. Valaee, “Cooperative positioning with the aid of reconfigurable intelligent surfaces and zero access points,” _2022 IEEE 96th Vehicular Tech. Conf. (VTC2022-Fall), London, United Kingdom,_ 2022, pp. 1-5.
  * [10] Mustafa Ammous, Hui Chen, Henk Wymeersch, and S. Valaee, “Zero access points 3D cooperative positioning via RIS and sidelink communications, _https://arxiv.org/pdf/2305.08287.pdf_ , May, 2023.
  * [11] M. Javad-Kalbasi and S. Valaee, “Re-configuration of UAV Relays in 6G Networks,” _(ICC Workshops), Montreal, QC, Canada,_ 2021, pp. 1-6.
  * [12] Z. Wei _et al.,_ “Sum-rate maximization for IRS-assisted UAV OFDMA communication systems,” in _IEEE Trans. on Wireless Commun.,_ vol. 20, no. 4, pp. 2530-2550, Apr. 2021.
  * [13] Q. -U. -A. Nadeem, H. Alwazani, A. Kammoun, A. Chaaban, M. Debbah, and M. -S. Alouini, “Intelligent reflecting surface-assisted multi-user MISO communication: Channel estimation and beamforming design,” in _IEEE Open Journal of the Commun. Society,_ vol. 1, pp. 661-680, 2020.
  * [14] M. Obeed and A. Chaaban, “Joint beamforming design for multiuser MISO downlink aided by a reconfigurable intelligent surface and a relay,” in _IEEE Trans. on Wireless Commun.,_ vol. 21, no. 10, pp. 8216-8229, Oct. 2022.
  * [15] Mohammad Javad-Kalbasi, Mohammed S. Al-Abiad, and Shahrokh Valaee, “Energy efficient communications in RIS-assisted UAV networks based on genetic algorithm”, Accepted for publication in _(Globecom’ 2023), Kuala Lumpur, Malaysia,_ Available at: https://arxiv.org/pdf/2308.08652.pdf
  * [16] C. Pandana and K. J. R. Liu, “Robust connectivity-aware energy-efficient routing for wireless sensor networks,” in _IEEE Trans. on Wireless Commun.,_ vol. 7, no. 10, pp. 3904-3916, Oct. 2008.
  * [17] A. S. Ibrahim, K. G. Seddik and K. J. R. Liu, “Connectivity-aware network maintenance and repair via relays deployment,” in _IEEE Trans. on Wireless Commun.,_ vol. 8, no. 1, pp. 356-366, Jan. 2009.
  * [18] M. Fiedler, “Algebraic connectivity of graphs,” _Czechoslovak Mathematical J.,_ vol. 23, pp. 298-305, 1973.
  * [19] Jae-Hwan Chang and L. Tassiulas, “Maximum lifetime routing in wireless sensor networks,” in _IEEE/ACM Trans. on Networking,_ vol. 12, no. 4, pp. 609-619, Aug. 2004.
  * [20] C.-K. Toh, “Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks,” in _IEEE Commun. Magazine,_ vol. 39, no. 6, pp. 138-147, Jun. 2001.
  * [21] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” _Proceedings of the 33rd Annual Hawaii Intern. Conf. on System Sciences,_ Maui, HI, USA, 2000, pp. 10 pp. vol. 2.
  * [22] M. A. Abdel-Malek, A. S. Ibrahim, and M. Mokhtar, “Optimum UAV positioning for better coverage-connectivity tradeoff,” _2017 IEEE 28th Annual Intern. Symposium on Personal, Indoor, and Mobile Radio Commun. (PIMRC),_ Montreal, QC, Canada, 2017, pp. 1-5.
  * [23] N. Li and J. C. Hou, “Improving connectivity of wireless ad hoc networks,” in _Proc. Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous’05),_ pp. 314-324, July 2005.
  * [24] K. Xu, H. Hassanein, and G. Takahara, “Relay node deployment strategies in heterogeneous wireless sensor networks: multiple-hop com- munication case,” in _Proc. IEEE Sensor and Ad Hoc Commun. Networks (SECON’ 05),_ pp. 575-585, Sept. 2005.
  * [25] Z. Han, A. L. Swindlehurst, and K. J. R. Liu, “Smart deploy- ment/movement of unmanned air vehicle to improve connectiv- ity in MANET,” in _Proc. IEEE Wireless Commun. Networking Conf.(WCNC’06),_ vol. 1, pp. 252-257, Apr. 2006.
  * [26] James W. Demmel, “Applied numerical linear algebra,” 1997.
  * [27] A. Albanese, P. Mursia, V. Sciancalepore and X. Costa-Pérez, “PAPIR: Practical RIS-aided localization via statistical user information,” _2021 IEEE 22nd Inter. Workshop on Signal Processing Advances in Wireless Commun. (SPAWC),_ Lucca, Italy, 2021, pp. 531-535.
  * [28] S. Boyd, “Convex optimization of graph laplacian eigenvalues,” in _Proc. International Congress of Mathematicians,_ vol. 3, pp. 1311-1319, 2006.
  * [29] SDPA-M package, [Online]. Available: http://grid.r.dendai.ac.jp/sdpa/
  * [30] A. Ghosh and S. Boyd, “Growing well-connected graphs,” _Proceedings of the 45th IEEE Conference on Decision and Control,_ San Diego, CA, USA, 2006, pp. 6605-6611.
  * [31] G. Golub, “Some modified matrix eigenvalue problems,” _SIAM Review,_ 15:318–334, 1973.
  * [32] J. H. Wilknson, “The algebraic eigenvalue problem,” _Clarendon Press,_ Oxford, 1965.
  * [33] G. H. Golub and C. F. Van Loan, “Matrix computations,” Math. Gazette, vol. 47, no. 5, pp. 392–396, 2013.

|  Mohammed S. Al-Abiad received the B.Eng. degree in computer and
communication engineering from Taiz University, Taiz, Yemen, in 2010, the
M.Sc. in electrical engineering from King Fahd University of Petroleum and
Minerals (KFUPM), Dhahran, Saudi Arabia, in 2017, the Ph.D. degree in
electrical engineering from the University of British Columbia, BC, Canada, in
2020. He is currently a Postdoctoral Research Fellow with the Edward S. Rogers
Sr. Department of Electrical and Computer Engineering, University of Toronto.
He was a Postdoctoral Research Fellow with the School of Engineering at the
University of British Columbia, Canada, from 2020 to 2022. He was the
recipient of the Natural Science and Engineering Research Council Postdoctoral
Fellowship (NSERC PDF) of Canada in 2023. His research interests include
optimization and resource allocation in wireless communications, federated
learning, mobile edge computing, and wireless networks connectivity using
RISs.
---|---
|  Mohammed Javad-Kalbasi received the M.Sc. degree in electrical and computer
engineering from the Isfahan University of Technology in 2014. He is currently
pursuing the Ph.D. degree with the University of Toronto. He is also a member
of the Fujitsu Co-Creation Research Laboratory, University of Toronto. His
main research interests include efficient Communications for the next
generation of networks, information theory, scheduling in communications
networks, and planning network migration.
---|---
|  Shahrokh Valaee is a Professor with the Edward S. Rogers Sr. Department of
Electrical and Computer Engineering, University of Toronto, and the holder of
Nortel Chair of Network Architectures and Services. He is the Founder and the
Director of the Wireless Innovation Research Laboratory (WIRLab) at the
University of Toronto. Professor Valaee was the TPC Co-Chair and the Local
Organization Chair of the IEEE Personal Mobile Indoor Radio Communication
(PIMRC) Symposium 2011. He was the TPC Co-Chair of ICT 2015, and PIMRC 2017,
and the Track Co- Chair of WCNC 2014, PIMRC 2020, VTC Fall 2020. He is the co-
chair of the organizing committee for PIMRC 2023. From December 2010 to
December 2012, he was the Associate Editor of the IEEE Signal Processing
Letters. From 2010 to 2015, he served as an Editor of IEEE Transactions on
Wireless Communications. Currently, he is an Editor of the Journal of Computer
and System Science and serves as a Distinguished Lecturer for IEEE
Communication Society. He was the co-recipient of the best paper award in the
IEEE Machine Learning for Signal Processing (MLSP) 2020 workshop. Professor
Valaee is a Fellow of the Engineering Institute of Canada, and a Fellow of
IEEE.
---|---