# A Survey on Model-based, Heuristic, and Machine Learning Optimization
Approaches in RIS-aided Wireless Networks
††thanks:  This work was supported in part by the Natural Sciences and
Engineering Research Council of Canada (NSERC) Canadian Collaborative Research
and Training Experience Program (CREATE) under Grant 497981; in part by the
Canada Research Chairs Program; in part by the U.S National Science Foundation
under Grants CNS-2128448 and ECCS-2335876; in part by the CHIST-ERA grant
under the project CHIST-ERA-20-SICT-005; in part by the Engineering and
Physical Sciences Research Council (EPSRC) under Project EP/W035588/1; and in
part by the PHC Alliance Franco-British Joint Research Programme under Grant
822326028. H. Zhou and M. Erol-Kantarci are with the School of Electrical
Engineering and Computer Science, University of Ottawa, Ottawa, ON K1N 6N5,
Canada. (emails:{hzhou098, melike.erolkantarci}@uottawa.ca). Yuanwei Liu is
with the School of Electronic Engineering and Computer Science, Queen Mary
University of London, London E1 4NS, U.K. (email:yuanwei.liu@qmul.ac.uk). H.
Vincent Poor is with the Department of Electrical and Computer Engineering,
Princeton University, Princeton, NJ 08544 USA (e-mail: poor@princeton.edu).

Hao Zhou, , Melike Erol-Kantarci, , Yuanwei Liu, ,
and H. Vincent Poor

###### Abstract

Reconfigurable intelligent surfaces (RISs) have received considerable
attention as a key enabler for envisioned 6G networks, for the purpose of
improving the network capacity, coverage, efficiency, and security with low
energy consumption and low hardware cost. However, integrating RISs into the
existing infrastructure greatly increases the network management complexity,
especially for controlling a significant number of RIS elements. To unleash
the full potential of RISs, efficient optimization approaches are of great
importance. This work provides a comprehensive survey on optimization
techniques for RIS-aided wireless communications, including model-based,
heuristic, and machine learning (ML) algorithms. In particular, we first
summarize the problem formulations in the literature with diverse objectives
and constraints, e.g., sum-rate maximization, power minimization, and
imperfect channel state information constraints. Then, we introduce model-
based algorithms that have been used in the literature, such as alternating
optimization, the majorization-minimization method, and successive convex
approximation. Next, heuristic optimization is discussed, which applies
heuristic rules for obtaining low-complexity solutions. Moreover, we present
state-of-the-art ML algorithms and applications towards RISs, i.e., supervised
and unsupervised learning, reinforcement learning, federated learning, graph
learning, transfer learning, and hierarchical learning-based approaches.
Model-based, heuristic, and ML approaches are compared in terms of stability,
robustness, optimality and so on, providing a systematic understanding of
these techniques. Finally, we highlight RIS-aided applications towards 6G
networks and identify future challenges.

###### Index Terms:

Reconfigurable intelligent surfaces, optimization, model-based methods,
heuristics, machine learning.

Figure 1: Organization and key topics covered in this work.

##  I Introduction

While 5G has entered the commercialization phase, the research community has
started the exploration of future 6G networks. Compared with previous
generations, 6G networks are expected to present more stringent performance
requirements, i.e., terabits per second (Tbps) data rates for virtual reality,
and more than $10^{7}/km^{2}$ connection densities with significantly lower
latencies than 5G networks [1]. One of the main obstacles to wireless network
evolution is the uncontrollable radio environment with reflections,
diffractions, and scattering. Recently, reconfigurable intelligent surfaces
(RISs) have emerged as promising techniques to enhance wireless signal
propagation [2]. In particular, the core feature of RISs is to manipulate the
signal propagation path by intelligently configuring numerous small elements.
Each RIS element can independently tune the phase of the incident signal,
creating a smart radio environment[3]. RISs not only are technically
attractive but also require low energy consumption and hardware cost, making
it promising to enhance the spectral efficiency for real-world deployments.
Given these advantages, RISs can be combined with other emerging techniques,
including multiple-input multiple-output (MIMO), millimeter-wave (mmWave)
communications, unmanned aerial vehicle (UAV) networks, non-orthogonal
multiple access (NOMA), vehicle-to-everything (V2X) networks, and so on[4, 5].
Many existing studies and implementations have demonstrated RIS’s capability
of improving network capacity, coverage, energy efficiency, and security.

Despite their potential, integrating RISs into wireless networks will
significantly increase the complexity of network management [6]. For example,
each RIS element requires independent phase-shift configurations, leading to
large solutions spaces for optimization algorithms. The RIS configuration is
more complicated when other control variables are jointly involved, such as
beamforming, spectrum allocation, NOMA decoding order, or UAV trajectory
design. Therefore, advanced optimization techniques are of paramount
importance to handle such complexity and take full advantage of RISs.
Motivated by the importance of optimization techniques, this work provides a
comprehensive overview of optimization techniques of RIS-aided wireless
communications, including model-based, heuristic, and machine learning (ML)
approaches. There are several surveys devoted to the theory, design, analyses,
and applications of RISs [7, 8, 9, 10, 11, 12]. However, this work is
different from existing surveys and tutorials by systematically summarizing
and analyzing the optimization techniques for RIS-aided wireless networks,
providing detailed comparisons, as well as including more state-of-the-art ML
techniques. Specifically, as shown in Fig. 1, we focus on the following
aspects:

TABLE I: Comparison of this work with existing surveys

Ref. | RIS control and optimization-related contributions1
---|---
| Model-based approaches | Heuristic algorithms | Machine learning-based methods
|  AO |  MM |  SCA |  BCD |  SDR |  SOCP |  FP |  BnB |  CCP |  Meta-heuristic |  Greedy method |  Matching theory |  Supervised learning |  Unsupervised learning |  Reinforcement learning |  Federated learning |  Graph learning |  Transfer learning |  Hierarchical learning |  Meta- learning
[7] |  ✓ |  ✓ |  ✓ |  ✓ |  |  |  |  |  |  |  |  |  ✓ |  |  |  |  |  |  |
[8] |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  |  |  |  |  |  |  |  ✓ |  |  ✓ |  |  |  |  |
[9] |  ✓ |  ✓ |  |  |  ✓ |  |  |  |  |  |  |  |  |  |  ✓ |  |  |  |  |
[10] |  ✓ |  ✓ |  ✓ |  |  ✓ |  ✓ |  |  |  |  |  |  |  |  |  ✓ |  |  |  |  |
[11] |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  |  ✓ |  |  ✓ |  ✓ |  |  |  |  |  ✓ |  |  |  |  |
[12] |  ✓ |  |  |  |  ✓ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
[13] |  |  |  |  |  |  |  |  |  |  |  |  |  ✓ |  ✓ |  ✓ |  ✓ |  |  |  |
[14] |  ✓ |  |  ✓ |  |  ✓ |  |  |  ✓ |  |  |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  |  |  |
[15] |  ✓ |  ✓ |  ✓ |  |  |  |  |  |  |  |  |  ✓ |  ✓ |  |  |  |  |  |  |
This work |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓ |  ✓

  * 1

There are many surveys and tutorials on RISs recently, but Table I focuses on
studies that include control and optimization sections.

1) Problem formulations: We first introduce the fundamental theories of RIS
technology, and then provide an overview of the problem formulations for
optimizing RIS-aided wireless networks, including maximization of sum-
rate/capacity, energy efficiency, user fairness, and secrecy rate, and
minimization of power consumption. In addition, we consider discrete RIS phase
shifts and resource management problems that include integer control
variables, and imperfect channel state information (CSI) with different error
model constraints.

2) Model-based methods: In this work, model-based methods refer to algorithms
that rely on specific optimization models with full knowledge of the defined
problem111Note that some machine learning algorithms are also model-based, but
here we use “model-based” to best describe the common features of a type of
optimization algorithms.. Model-based algorithms usually have demanding
requirements for the properties and forms of problem formulations, e.g.,
convexity, continuity, and differentiability. We include the following model-
based algorithms for optimizing RIS-aided wireless networks: alternating
optimization (AO), the majorization-minimization (MM) method, successive
convex optimization (SCA), block coordinate descent (BCD), semidefinite
relaxation (SDR), second-order cone programming (SOCP), fractional programming
(FP) and branch-and-bound (BnB).

3) Heuristic algorithms: These algorithms apply heuristic rules for problem-
solving. They provide more efficient alternatives to conventional model-based
methods by sacrificing optimality and accuracy for low complexity and fast
solutions. Heuristic algorithms can be used to solve NP-hard problems or serve
as baselines and supplements for other algorithms. In this survey, we review
the convex-concave procedure (CCP) algorithm, meta-heuristic algorithms,
greedy algorithms, and matching theory for optimizing RIS-aided wireless
networks.

4) ML algorithms: ML algorithms are recognized as promising solutions for
wireless network optimization[16]. ML techniques do not need full knowledge of
the defined problem, and they learn from data or interact with environments to
find hidden patterns. We present state-of-the-art ML techniques for optimizing
RIS-aided wireless networks, including supervised and unsupervised learning,
reinforcement learning (RL), federated learning (FL), graph learning, transfer
learning, hierarchical learning, and meta-learning. We provide in-depth
analyses for algorithm features and applications towards RISs, i.e., the
dataset acquisition of neural networks for RIS phase-shift optimization, and
loss function definitions of unsupervised neural networks for data rate
maximization. In addition, we compare model-based, heuristic, and ML
approaches in terms of optimality, robustness, stability, and so on.

5) Applications and challenges towards 6G networks: We give an overview of
RIS-assisted applications towards envisioned 6G networks, including NOMA,
simultaneous wireless information and power transfer (SWIPT), mmWave and THz
communications, nonterrestrial networks (NTNs), V2X communications, and
integrated sensing and communication (ISAC). Moreover, we identify research
challenges for the control and optimization of RISs.

In summary, the main contribution of this work is that we systematically
survey the optimization techniques for RIS-aided wireless networks, ranging
from problem formulations to the features and applications of various
approaches. Our work aims to be a roadmap for researchers to optimize RIS-
aided wireless networks. The rest of this work is organized as follows.
Section II reviews related work, while Section III presents the problem
formulations. Section IV, V and VI introduce model-based, heuristic, and ML
optimization approaches, respectively, and we compare these three approaches
in Section VII. Section VIII includes RIS-aided applications towards 6G
networks and identifies future challenges. Finally, Section IX concludes this
survey.

##  II Related Surveys

There are many research directions relating to RISs, including channel
modelling and estimation, signal processing, performance analysis, passive
beamforming, and hardware designs. This work focuses on optimization
techniques due to their paramount importance, and Table I compares this work
with existing surveys in terms of control and optimization-related
contributions.

Table I shows that most existing works focus on model-based approaches,
including AO, MM, SCA, and SDR. The main reason is that these techniques have
been widely applied, e.g., using AO to decouple joint active and passive
beamforming, and applying MM and SCA to approximate non-convex objectives.
Then, heuristic algorithms are usually considered as low-complexity
alternatives and supplements. For example, greedy algorithms are used for
element-by-element RIS phase-shift control, and matching theory is applied for
resource allocation. However, despite their importance, heuristic approaches
are omitted in many existing surveys. Meanwhile, ML algorithms have been
widely used for wireless network management, but existing surveys are limited
in supervised learning and RL. In addition, some newly emerging techniques,
such as graph learning and hierarchical learning, are not mentioned in
existing surveys.

More specifically, in many existing studies [7, 8, 9, 10], optimization
techniques are very briefly discussed by introducing the algorithm titles that
have been used in the literature, but the motivations and algorithm features
are not included. Alghamdi et al. overviewed optimization and performance
analysis techniques of RISs, but it is limited in analyzing problem
formulations [12]. In [13], Faisal and Choi specialized in ML approaches for
RIS-aided wireless networks, but model-based and heuristic approaches are not
included. Besides, some state-of-the-art ML techniques, including graph
learning and hierarchical learning, are not included in [13]. By contrast,
multiple model-based approaches are introduced in [11] for signal processing
of RISs, but many heuristic and ML techniques are not covered. Liu et al.
presented RIS beamforming, resource management and ML for RIS-aided wireless
networks, but only RL is presented in detail [14]. Supervised learning,
unsupervised learning, and FL are briefly discussed in [14], while newer
techniques, such as graph learning, transfer learning, and hierarchical
learning, are not covered. In [15], Zheng et al. surveyed the channel
estimation and practical RIS control under imperfect/statistical/hybrid CSI,
but some optimization techniques are not included.

This work is different from existing studies in the following aspects:

  * •

Control and optimization have been included in many surveys, but this work is
the first to systematically investigate optimization techniques of RIS-aided
wireless networks, ranging from problem formulations to steps, features,
advantages, and difficulties of nearly 20 techniques.

  * •

We present in-depth analyses to apply these optimization techniques to RISs.
For example, deep neural network (DNN) and deep reinforcement learning (DRL)
are included in many existing surveys, but some important questions are not
discussed, i.e., dataset acquisition for neural network training in RIS-aided
environments, and customizing the state, action, and reward function
definitions for RL-enabled RIS control. The answers to these questions are
critical to taking full advantage of RISs.

  * •

Finally, we present the most state-of-the-art ML techniques for optimizing
RIS-aided wireless networks, e.g., graph learning, transfer learning, and
hierarchical learning, which are not included in existing surveys, to the best
of our knowledge. These novel techniques may bring new research directions.

To summarize, this survey answers the following: what are the state-of-the-art
techniques for optimizing RIS-aided wireless networks, and how do they cover
different aspects with respect to each other?

##  III Background and Problem Formulations for Optimizing RIS-aided Wireless
Networks

This section first introduces the fundamentals of RIS technology, and then it
overviews the problem formulations of RIS-aided wireless networking solutions,
including maximization of sum-rate/capacity, energy efficiency, user fairness,
secrecy rate, and minimization of power consumption. For each objective, we
summarize related works in terms of scenarios, phase-shift resolutions,
channel settings, CSI, control variables, constraints, and algorithms.
Additionally, we investigate problem formulations with integer control
variables, such as discrete RIS phase shifts and resource allocation problems.
Finally, imperfect CSI scenarios are discussed within deterministic and
stochastic models.

Figure 2: Illustration of RIS operation and control principles.

###  III-A Fundamental Theories of RIS Technology

This subsection introduces the fundamentals of RIS technologies, including RIS
operation principles, RIS control, and RIS deployment. Note that there are a
few studies that have explicitly introduced the fundamental principles of
RISs[14, 2, 6], and so this subsection serves as a brief background in our
work. The reader is referred to those studies for further details.

####  III-A1 RIS Operation Principles

An RIS is a man-made two-dimensional reflecting surface, and the core feature
of RISs is that the electromagnetic response can be intelligently
reconfigured. Each RIS element can tune the phase of the incident signal,
enabling a customized signal propagation environment. There have been various
designs of RISs, which can be can be categorized in terms of power sources,
energy consumption, tuning features, etc[14]. For example, Fig. 2 shows an
example of a varactor-based RIS, which applies varactor diodes with tunable
biasing voltages to achieve desired phase shifts. By reflecting the incident
signal from the BS, the RIS provides an alternative transmission link.

####  III-A2 RIS Control

A smart RIS controller is usually deployed using a device such as field-
programmable gate array (FPGA). As shown in Fig. 2, the RIS phase shift
pattern is designed at the BS, and it will send control signals to the RIS
controller for phase-shift configuration. In this case, the BS will collect
the required information for decision-making. Specifically, CSI is one of the
most important pieces of information for RIS phase-shift design, since RIS
elements have to respond rapidly to channel dynamics. Meanwhile, other
information may also be required, which varies between different RIS phase-
shift design algorithms. For example, Huang et al. consider user positions as
input for phase-shift design, which means the user location should be
collected[17]. Additionally, the communication frequency between the BS and
RIS controller depends on the specific RIS design. For instance, the unit
elements of passive metasurfaces will remain static during normal operation,
and the controller has fewer communication demands with the BS[6]. By
contrast, for RISs with active tunability, the controller may require frequent
information sharing to make real-time responses to dynamic channel conditions.

####  III-A3 RIS Deployment

Due to the low hardware cost and low energy consumption, RISs can be easily
deployed on building walls and ceilings. These terrestrial RISs may be
deployed in a centralized manner as a single large surface, or as
decentralized surfaces that are closer to users. The centralized deployment
means that more users can be covered, while the decentralized deployment has
lower control complexity. In addition, RISs can also be placed on aerial
platforms. For instance, UAVs with RISs can provide full space reflections
with mobility and higher flexibility[18, 19].

To realize the benefits of deploying RISs in wireless networks, RISs should be
carefully configured, including locations, on/off status, amplitude, phase
shifts, etc. In particular, phase-shift design is the key to RIS operation,
which will directly affect network performance. Meanwhile, other network
decisions, such as transmit beamforming, user association and resource
allocation, should be jointly optimized. These joint optimization problems are
usually non-convex and highly non-linear, requiring various optimization
techniques for different scenarios, e.g., joint active and passive
beamforming, RIS-related resource allocation, physical layer security, etc. In
the following, we will introduce the problem formulations for optimizing RIS-
aided wireless networks.

TABLE II: Summary of RIS-aided sum-rate/capacity maximization works under
various constraints

Ref. |  Scenario1 |  Phase-shift resolution |  Channel settings |  CSI |  Control variables |  Constraints |  Algorithms
---|---|---|---|---|---|---|---
[20] |  MIMO-DL-MU irregular RISs |  Continuous |  Rayleigh fading |  Perfect |  BS beamforming matrix, RISs selection and phase shifts |  Total transmit power, RISs selection and phase constraints |  AO, Tabu search, extraction based cross-entropy methods
[21] |  MIMO-DL-MU Multicell |  Continuous |  Rayleigh and Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power and RISs phase constraints |  BCD, MM, Complex circle manifold
[22] |  MIMO-DL OFDM |  Continuous |  Rayleigh and Rician fading |  Perfect |  Transmit covariance matrix and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO
[23] |  MIMO-UP/DL |  Continuous/ Discrete |  Rayleigh fading |  Perfect |  Source precoders and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO
[24] |  MISO-DL-MU |  Discrete |  Correlated Rician fading |  Statistical/ Instantaneous |  BS beamforming matrix and RIS phase shifts |  Total transmit power and RISs phase constraints |  Penalty dual decomposition, Stochastic SCA
[25] |  MISO-DL-SU Cognitive Radio |  Continuous |  Rician fading |  Perfect/ Imperfect |  BS beamforming vectors and RIS phase shifts |  Interference level, total transmit power, and RISs phase constraints |  BCD, SDP, SOCP
[26] |  MISO-DL-MU |  Discrete |  Reflection-dominated |  Imperfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO, BnB, SDR
[27] |  MISO-DL-MU |  Continuous |  Rayleigh and Rician fading |  Perfect/ Imperfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power and RISs phase constraints |  FP, BCD, complex circle manifold
[28] |  SISO-UL-SU |  Discrete |  Rayleigh fading |  Estimated |  RIS phase shifts |  RISs phase constraint |  Successive refinement algorithm
[29] |  MISO-DL-MU NOMA |  Continuous/ Discrete |  Rayleigh and Rician fading |  Perfect |  BS beamforming vector, RIS phase shifts, and user decoding order |  Successive interference cancellation, total transmit power, and RISs phase constraints |  AO, SCA, sequential rank-one constraint relaxation
[30] |  MISO-UL-MU mmWave V2X |  Continuous |  Saleh-Valenzuela |  Imperfect |  Transmit power, multi-user detection matrix, and RIS phase shifts |  Target SINR, total transmit power, and RISs phase constraints |  AO, SCA, penalty CCP
[31] |  MIMO-DL-MU |  Continuous/ Discrete |  Rician fading |  Perfect |  RIS phase shifts |  RISs phase constraint |  Particle swarm optimization (PSO)
[32] |  MIMO-DL-MU |  Discrete |  Rayleigh and Rician fading |  Statistical |  RIS phase shifts |  RISs phase constraint |  Genetic algorithm
[33] |  Point to point communication |  Discrete |  Rician fading |  Imperfect |  RIS phase shifts |  RISs phase constraint |  Greedy algorithm
[34] |  Multi-cell NOMA |  Continuous |  Rayleigh and Rician fading |  Perfect |  User association, subchannel assignment, reflection matrix, power allocation, and decoding order. |  Target data rate, total transit power, association, decoding, and RISs phase constraints. |  Matching method, convex upper bound substitution, SCA, and SDR.
[35] |  V2X communications |  Continuous |  Rayleigh and Rician fading |  Large-scale and slowly varying |  Transmit power, multi-user detection matrix, spectrum sharing, and RIS phase shifts |  Maximum transmit power, RISs phase, QoS requirement, and spectrum sharing protocol |  BCD, SDR, CCP

  * 1

MISO: multiple input single output; DL/UL: downlink/uplink; SU/MU: single
user/ multiple users.

Figure 3: Downlink channel of RIS-aided multi-user systems.

###  III-B Sum-rate/Capacity Maximization

Fig. 3 shows a RIS-aided downlink transmission system, in which one base
station (BS) with $M$ antennas serves $K$ single-antenna users, and the RISs
have $N$ reflecting elements. The users can receive signals by direct
transmission link BS-user and indirect transmission link BS-RIS-user. The
signal-to-interference-plus-noise ratio (SINR) of user $k$ is:

$\gamma_{k}=\frac{|(\bm{h}^{R}_{k}\bm{\Theta}\bm{G}+\bm{h}^{D}_{k})p_{k}|^{2}}{\sum\limits_{j=1,j\neq
k}^{K}|(\bm{h}^{R}_{k}\bm{\Theta}\bm{G}+\bm{h}^{D}_{k})p_{j}|^{2}+N_{0}^{2}},$
(1)

where $p_{k}$ is the transmit power at the BS for active beamforming,
$\bm{G}\in\mathbb{C}^{N\times M}$ indicates the channel gain from BS antennas
to RIS elements, $h^{R}_{k}\in\mathbb{C}^{1\times N}$ indicates the channel
gain from RIS elements to user $k$, $h^{D}_{k}\in\mathbb{C}^{1\times M}$
indicates the channel gain from BS antennas to user $k$, and $N_{0}^{2}$ is
the noise power. The RISs reflect the signal to users via a phase-shift vector
$\theta_{n}=e^{j\phi_{n}}$ for passive beamforming, and we define a diagonal
matrix
$\bm{\Theta}=\text{diag}(\theta_{1},\theta_{2},...,\theta_{n},...,\theta_{N})\in\mathbb{C}^{N\times
N}$. Here RISs may have different operation modes to change the phase shifts,
which depend on their specific designs. For instance, RIS elements can be
reconfigured electrically, mechanically, or thermally based on their tuning
design, and a thorough survey can be found in [6]. However, note that RISs
cannot be completely passive due to their inherent property of being
configurable[14]. In addition, note that the BS in Fig. 3 can serve multiple
users simultaneously due to multi-antenna BS beamforming, and RIS elements are
used to reflect the incident signal and change the phases[36].

Sum-rate/channel capacity improvement is one of the most widely considered
advantages of RIS. Compared with the direct transmission BS-user, RISs provide
an indirect link that can be line-of-sight, leading to less path loss and
higher SINR. To maximize the weighted sum-rate

$\displaystyle\max\limits_{p,\bm{\Theta}}\qquad$
$\displaystyle\sum_{k=1}^{K}w_{k}\log(1+\gamma_{k})$ (2) s.t.
$\displaystyle\sum_{k=1}^{K}||p_{k}||^{2}\leq P_{max},$ (2a)
$\displaystyle|\theta_{n}|=1,n=1,2,...,N,$ (2b)

where $P_{max}$ is the maximum transmission power of BS, $w_{k}$ is the weight
of user $k$. Equation (2) aims to maximize the sum-rate of all $K$ users, and
equation (2a) is the transmission power constraint. Equation (2b) is the RISs
phase constraint which can be continuous or discrete.

Table II summarizes sum-rate/channel capacity maximization works in RIS-aided
wireless communications, including scenarios, phase-shift resolutions, channel
settings, CSI availability, control variables, constraints and algorithms.
This problem has been investigated in various scenarios, i.e., MIMO[20, 21,
22, 23], MISO[24, 25, 26, 27], SISO[28], NOMA[29], mmWave[30] and vehicle
communications[30]. These works mainly consider BS beamforming vectors and RIS
phase shifts as control variables, which are known as joint active and passive
beamforming, and the total transmit power and RIS phases are included as
constraints. However, the joint optimization problem is very challenging due
to network dynamics and the large number of RIS elements. The fractional terms
of SINR, logarithm introduced by Shannon theory, and non-convex constraint of
RIS phase shifts lead to significant complexity for the joint optimization.
Consequently, most existing studies decouple the control variables using
AO[20, 21, 22, 23, 26]. For example, a widely applied scheme is to first
optimize the BS beamforming vectors, then solve the RIS phase shifts sub-
problem iteratively. Finally, as one of the core control variables, the RIS
phase-shift control is supposed to be continuous in many studies. The first
reason is that discrete control variables lead to integer constraints that are
NP-hard; another reason is that the achieved results can be converted into the
nearest discrete values using the rounding method[37].

TABLE III: Summary of RIS-aided power minimization works under various
constraints

Ref. |  Scenario |  Phase-shift resolution |  Channel settings |  CSI |  Control variables |  Constraints |  Algorithms
---|---|---|---|---|---|---|---
[38] |  MISO-DL-MU |  Continuous |  Rician fading |  Perfect |  AP beamforming vector and RIS phase shifts |  SINR and RISs phase constraints |  AO, SDR, two-stage algorithm
[39] |  MISO-DL-MU |  Continuous/ Discrete |  Rician fading |  Perfect |  AP beamforming vector and RIS phase shifts |  SINR and RISs phase constraints |  Successive refinement algorithm, BnB
[40] |  MISO-DL-MU broadcast |  Continuous |  Rayleigh and Rician fading |  Imperfect |  BS precoding vector and RIS phase shifts |  SINR and RISs phase constraints |  AO, SDR
[41] |  MISO-DL-MU broadcast |  Continuous |  Rayleigh fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  SNR and RISs phase constraints |  SDR, SCA
[42] |  MISO-DL-MU broadband |  Continuous |  Rayleigh fading |  Imperfect |  BS precoder matrix and RIS phase shifts |  Target transmission rate, outage probability, and RISs phase constraints |  AO, SDR, penalty CCP
[43] |  SISO-DL-MU NOMA/OMA |  Discrete |  Rayleigh fading |  Perfect |  BS transmit power allocation and RIS phase shifts |  Target transmission rate and RISs phase constraints |  AO, linear approximation,
[44] |  MISO-DL-MU NOMA |  Continuous/ Discrete |  Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Target transmission rate and RISs phase constraints |  SOCP, ADMM
[45] |  MISO-DL-MU NOMA |  Continuous |  Rayleigh and Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Target transmission rate and RISs phase constraints |  AO, successive convex relaxations
[46] |  MISO-DL-MU NOMA |  Continuous |  Rayleigh distribution |  Perfect |  BS beamforming vectors and RIS phase shifts |  Target transmission rate and RISs phase constraints |  SDR, FP, SCA
[47] |  Full-duplex transmission |  Continuous |  Rayleigh fading |  Perfect |  Power allocation of signal sources and RIS phase shifts |  Target transmission rate and RISs phase constraints |  Lagrangian dual method, SDP
[48] |  MISO-DL-MU edge computing |  Continuous |  Rayleigh fading |  Perfect |  Offloading bits, transmission time, power allocation, and RIS phase shifts |  Computation ability, NOMA rate region, time constraint, offloading bits, and total transmit power |  AO, BCD
[49] |  MISO-DL-SU maritime communication |  Continuous |  Rician fading |  Estimated |  Mode selection, transmission power, BS beamforming vector, and RIS phase shifts |  Rate threshold, binary selection, maximum transmit power, and RISs phase constraints |  AO, exhaustive search, matching method, SDP

###  III-C Power Minimization

Power minimization is another widely investigated topic for RIS-aided wireless
communications. Transmission power reduction not only saves the power
consumption of wireless networks but also reduces the interference on adjacent
cells. Power minimization problems with QoS constraints can be described by

$\displaystyle\min\limits_{p,\bm{\Theta}}\qquad$
$\displaystyle\sum_{k=1}^{K}||p_{k}||^{2}$ (3) s.t.
$\displaystyle\gamma_{k}\geq\gamma_{min},k=1,2,...,K,$ (3a)
$\displaystyle|\theta_{n}|=1,n=1,2,...,N,$ (3b)

where $\gamma_{min}$ is the minimum SINR requirement of users. The objective
function is greatly simplified by minimizing power consumption
$\sum_{k=1}^{K}||p_{k}||^{2}$, and the quality of service (QoS) requirements
are balanced by SINR constraints as $\gamma_{k}\geq\gamma_{min}$. Here, the
SINR or date-rate requirements introduce fractional or logarithmic terms in
the constraints, which makes equation (3a) a challenging non-convex problem.

We summarize power minimization-related works in Table III. These studies aim
to minimize the transmit power of BSs with SINR or data rate constraints.
Similar to the sum-rate maximization problem, power minimization is also
investigated in diverse scenarios, including MISO[38, 39, 40, 41], SISO[43],
NOMA[44, 43, 45, 46] and full-duplex antennas [47]. Meanwhile, these studies
still assume continuous RIS phase shifts and perfect CSI to reduce the
optimization complexity[38, 41, 45, 46], and the main control variables are BS
beamforming vectors and RIS phase shifts. BnB and successive refinement
algorithm are applied in [39] for discrete optimization, and Zheng et al.
obtain the optimal RIS phase shifts first and then finds the nearest discrete
value [43]. In addition, imperfect CSI is investigated in [40, 42], in which
[40] applies penalty CCP to handle the CSI uncertainty, and S-procedure and
Bernstein-Type inequality are used in [42] to transform the QoS constraints
under CSI error. Perfect CSI is a common setting in many existing studies, but
such strong assumptions may be impractical in real-world applications. On the
one hand, more advanced channel estimation methods should be developed to
reduce the CSI estimation error[15]; on the other hand, robust optimization
algorithms are expected to handle the channel uncertainty.

TABLE IV: Summary of RIS-aided energy efficiency maximization works under
various constraints

Ref. |  Scenario |  Phase-shift resolution |  Channel settings |  CSI |  Control variables |  Constraints |  Algorithms
---|---|---|---|---|---|---|---
[50] |  MISO-DL-MU |  Continuous |  3GPP |  Perfect |  BS beamforming vectors and RIS phase shifts |  Target data rate, total transmit power, and RISs phase constraints |  AO, gradient descent, MM
[51] |  MISO-DL-MU multicast |  Continuous |  Rician fading |  Perfect/ Estimated |  BS covariance matrix and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO, FP
[52] |  SISO-MU D2D |  Discrete |  Rician fading |  Perfect |  D2D transmitter power and RIS phase shifts |  Target data rate, total transmit power, and RISs phase constraints |  AO, FP, Dinkelbach method
[53] |  MISO-DL-MU rate splitting |  Continuous |  Rayleigh fading |  Perfect |  BS beamforming vector, RIS phase shifts, and user message rate |  Common message decoding, target data rate, total transmit power, and RISs phase constraints |  AO, SCA
[54] |  MISO-DL-MU |  Continuous |  Rayleigh fading |  Perfect |  BS beamforming vector, RIS phase shifts and on/off |  Target data rate, total transmit power, RIS on/off status, and RISs phase constraints |  AO, SCA, greedy searching
[55] |  Cell-free MIMO-DL-MU |  Discrete |  Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO
[56] |  SISO-DL-MU NOMA |  Continuous |  Rician fading |  Perfect |  Subcarrier allocation, BS beamforming vector, and RIS phase shifts |  Subcarrier assignment, total transmit power, and RISs phase constraints |  AO, matching method, DC programming, and univariate search.

###  III-D Energy Efficiency Maximization

Energy efficiency is a critical metric for green 5G and 6G networks. Different
from power minimization problems, the objective of energy efficiency
maximization includes both transmission rate and energy consumption metrics,
which can better evaluate the power utilization efficiency. The main benefit
of RISs lies in the capability of reshaping the signal propagation path with
extremely low power consumption, making RISs a promising technique to improve
energy efficiency. To maximize energy efficiency, one can formulate

$\displaystyle\max\limits_{p,\bm{\Theta}}\qquad$
$\displaystyle\frac{\sum_{k=1}^{K}w_{k}\log(1+\gamma_{k})}{\sigma^{-1}\sum_{k=1}^{K}||p_{k}||^{2}+KP_{UE}+P_{BS}+NP_{R}(\varrho)}$
(4) s.t. $\displaystyle\sum_{k=1}^{K}||p_{k}||^{2}\leq P_{max},$ (4a)
$\displaystyle|\theta_{n}|=1,n=1,2,...,N,$ (4b)
$\displaystyle\gamma_{k}\geq\gamma_{min},k=1,2,...,K,$ (4c)

where $\sigma$ is the efficiency of the transmit power amplifier, $P_{UE}$ is
the hardware static power consumed by one user, $P_{BS}$ is the total hardware
static power consumption in BS, and $P_{R}(\kappa)$ is the power consumption
of one RIS reflecting element with resolution $\varrho$. To maximize energy
efficiency in equation (4), the numerator is to maximize the sum-rate, while
the denominator is to reduce power consumption. Constraint (4a) is the total
transmit power limit, (4b) is the RIS phase constraint, and (4c) is the QoS
requirement indicated by target SINR or data rate.

Problem (4) is more complicated than sum-rate maximization or power
minimization problems, since it includes both logarithm and fractional terms
in the objection function and constraints. Energy efficiency maximization-
related works are summarized in Table IV. Similar to former problem
formulations, BS beamforming vectors and RIS phase shifts are main control
variables, and constraints include target data rate, total transmit power, and
RIS phases[50, 51, 55]. To solve the energy efficiency maximization problem,
the key is to decouple the transmission rate and energy consumption items in
equation (4). Dinkelbach method is applied in [52], but these conventional
methods can not be directly applied to sum-ratio problems. Note that the power
consumption definition in equation (4) may change case by case, which depends
on the scenario of deploying RISs. For example, the total power consumption in
most studies include BS transmit power, RIS energy consumption and user device
power. By contrast, Zhou et al. investigate the energy efficiency with BS
sleep control, and the total BS power consumption becomes the denominator in
the objective of equation (4)[57].

TABLE V: Summary of RIS-aided fairness maximization works under various
constraints

Ref. |  Scenario |  Phase-shift resolution |  Channel setting |  CSI |  Control variables |  Constraints |  Algorithms
---|---|---|---|---|---|---|---
[58] |  MISO-DL-MU multicast |  Continuous /Discrete |  Rayleigh and Rician fading |  Perfect |  BS precoding matrix and RIS phase shifts |  Total transmit power and RISs phase constraints |  SOCP, MM
[37] |  SISO/MISO-DL-MU NOMA |  Continuous |  Rayleigh and Rician fading |  Perfect |  BS power allocation and RIS phase shifts |  Target SINR, channel strength, total transmit power, and RISs phase constraints |  BCD, SDR
[59] |  MISO-DL-MU |  Continuous |  Rayleigh fading |  Perfect |  RIS phase shifts |  RIS phase constraint |  Projected gradient ascent
[60] |  MISO-DL-MU |  Continuous |  Rayleigh and Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power and RISs phase constraints |  SOCP, SDR, SCA
[61] |  Cell-free MIMO-UL-MU |  Continuous |  Rician fading |  Estimated |  User transmit power and RIS phase shifts |  User transmit power and RISs phase constraints |  AO
[62] |  MIMO-DL-MU SWIPT |  Discrete |  Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power, target harvested energy, and RISs phase constraints |  AO, optimal BnB, reformulation-linearization
[63] |  Full-Duplex relay networks |  Continuous |  Rayleigh fading |  Perfect |  Transmit power and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO, SDR
[64] |  MIMO-DL-MU coordinated multi-point |  Continuous |  Rayleigh and Rician fading |  Perfect |  BS beamforming vectors and RIS phase shifts |  Total transmit power and RISs phase constraints |  SOCP, SDR, MM
[65] |  MIMO-UL |  Continuous /Discrete |  Rician fading |  Statistical |  RIS phase shifts |  RIS phase constraint |  Genetic algorithm.
[66] |  Point to point communications |  Continuous |  Rayleigh fading |  Estimated |  RIS phase shifts |  Target SINR and RISs phase constraints |  SDR, greedy-iterative method

###  III-E User Fairness Maximization

Former problem formulations usually consider the total or average network
performance as objectives, but the fairness among multiple users is equally
important. Such user fairness metrics can describe the experience of cell-edge
users, guaranteeing the worst-case network performance. User fairness
maximization aims to maximize the minimum SINR or data rate, indicating that
users can achieve target performance even in the worst case. For instance, the
max-min SINR problem can be defined by

$\displaystyle\max\limits_{p,\bm{\Theta}}\qquad$
$\displaystyle\min\limits_{k\in K}\\{\gamma_{k}\\}$ (5) s.t.
$\displaystyle\sum_{k=1}^{K}||p_{k}||^{2}\leq P_{max},$ (5a)
$\displaystyle|\theta_{n}|=1,n=1,2,...,N,$ (5b)
$\displaystyle\gamma_{k}\geq\gamma_{min},k=1,2,...,K,$ (5c)

where $\min\limits_{k\in K}\\{\gamma_{k}\\}$ is the minimum SINR among $K$
users. Maximizing the worst user experience will improve the fairness of the
whole network.

Table V summarizes existing works for fairness maximization problems in RIS-
aided wireless networks. Although various scenarios have been investigated,
the primary control variables are still BS beamforming vectors and RIS phase
shifts[58, 37, 60, 64], and the constraints focus on total transmit power and
RIS phases[58, 60, 63, 64]. The formulated problem (5) is more challenging
than conventional max-min fairness beamforming problems. RISs not only
introduce additional non-convex constraints but also makes the reflective
beamforming vector coupled with the transmit beamforming vectors in the SINR
term, thus making problem (5) highly nonlinear and non-convex[60]. Therefore,
instead of optimizing the complicated objective functions directly,
approximation-based algorithms are frequently applied. For example, MM and SCA
algorithms construct surrogate functions as the upper bound of original
objective functions, which are easier to be optimized than problem (5).
Additionally, the genetic algorithm (GA) and greedy-iterative method are used
in [65] and [66] for RIS phase-shift control, respectively. Compared with
model-based algorithms, these heuristic algorithms can obtain fast solutions
efficiently, but the optimality cannot be guaranteed.

###  III-F Secrecy Rate Maximization

Physical layer security is increasingly of interest for wireless
communications, and various techniques have been proposed to enhance physical
layer security, e.g., artificial noise-aided beamforming and cooperative
jamming. However, these approaches may lead to high hardware costs and power
consumption, and RISs provide a novel low-cost solution by manipulating the
signal propagation path.

Fig. 4 shows a RIS-aided downlink transmission system with one legitimate user
and one eavesdropper. The data rate of the legitimate user is:

$R_{L}=\log(1+\frac{|(\bm{h}_{L}\bm{\Theta}\bm{G}+\bm{h}_{d,L})p_{L}}{|}^{2}{N_{L,0}^{2}}),$
(6)

where $\bm{h}_{L}$ is the channel from RISs to the legitimate user,
$\bm{h}_{d,L}$ is the direct transmission channel from RISs to the legitimate
user, and $N_{L,0}$ is the Gaussian noise at the legitimate user.

Figure 4: The downlink channel model of RIS-aided secure transmission.

Similarly, the data rate of the eavesdropper is:

$R_{E}=\log(1+\frac{|(\bm{h}_{E}\bm{\Theta}\bm{G}+\bm{h}_{d,E})p_{L}}{|}^{2}{N_{E,0}^{2}}),$
(7)

where $\bm{h}_{E}$ is the channel from RISs to the eavesdropper,
$\bm{h}_{d,E}$ is the direct transmission channel from RISs to the
eavesdropper, and $N_{E,0}$ is the Gaussian noise at the eavesdropper.
Finally, to maximize the secrecy rate, we have

$\displaystyle\max\limits_{p,\bm{\Theta}}\qquad$ $\displaystyle R_{L}-R_{E}$
(8) s.t. $\displaystyle||p||^{2}\leq P_{max},$ (8a)
$\displaystyle|\theta_{n}|=1,n=1,2,...,N.$ (8b)

Table VI summarizes the RIS-aided secure transmissions-related studies. It
shows that most existing works apply continuous phase shifts with perfect CSI
sharing, and BS beamforming and RIS phase shifts are still the major control
variables. Most existing studies consider single-user cases[67, 68, 69, 70,
71, 72, 73], which significantly lower the optimization complexity without
considering interference between multiple legitimate users. Moreover, the
perfect CSI acquisition of legitimate users may be unrealistic in practice,
indicating a gap between theoretical studies and real-world applications.

On the other hand, RIS technique is also combined with conventional secure
transmission strategies, i.e., artificial noise, to achieve secure
transmissions[74, 69], and the simulations demonstrate that integrating RIS
with artificial noise can achieve a higher secure transmission rate. However,
these coupled control variables also increase the optimization complexity. The
main difficulties of solving problem (8) are the non-convex objective function
and RIS phase-shift constraints (8b). Subsequently, AO-based estimation
methods are widely applied as low-complexity solutions. For instance, the
original problem is decoupled into multiple sub-problems by optimizing one
control variable and holding other variables fixed, and then applying
approximation-based algorithms, e.g., SCA[74, 69, 72] and MM[75, 73], to solve
each sub-problem.

TABLE VI: Summary of RIS-aided secure transmission-related works under various
constraints

Ref. |  Scenario |  Phase-shift resolution |  Channel setting |  CSI |  Control variables |  Constraints |  Algorithms
---|---|---|---|---|---|---|---
[75] [76] |  MIMO wiretap channel |  Continuous |  Rayleigh fading |  Perfect/ Imperfect |  Transmit covariance matrix and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO, one-by-one optimization, bisection search, MM.
[67] |  MISO-DL-SU |  Continuous |  Rayleigh fading |  Estimated |  Transmit beamformer and RIS phase shifts |  Secure transmission rate and RISs phase constraints |  AO, SDR
[74] |  MISO-DL-MU SWIPT |  Continuous |  Rayleigh fading |  Perfect |  BS transmit beamforming and artificial noise covariance matrix, and RIS phase shifts. |  Harvested power, total transmit power, and RISs phase constraints |  AO, SDR, SCA
[68] |  MISO-DL-SU |  Continuous |  Rayleigh fading |  Perfect |  Transmit beamformer and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO
[69] |  MISO-DL-SU |  Continuous |  Rician fading |  Perfect |  AP transmit beamforming and artificial noise covariance matrix, and RIS phase shifts. |  Total transmit power, RISs phase, and secrecy rate constraints |  AO, penalty-based approach, SCA, SDR
[70] |  MISO-DL-SU |  Continuous |  Rician fading |  Perfect/ Imperfect |  BS transmit beamforming vector and RIS phase shifts |  Secrecy capacity requirement and RISs phase constraints |  SDR, projected gradient algorithm
[71] |  MISO-DL-SU |  Continuous |  Correlated Rician fading |  Perfect |  AP transmit beamforming vector and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO
[72] |  SISO-DL-SU |  Continuous |  Rician fading |  Perfect |  RIS phase shifts |  RISs phase constraint |  AO, SDR, SCA
[73] |  MISO-DL-SU |  Continuous |  Rayleigh fading |  Partial |  Transmit beamforming vector and RIS phase shift |  SNR and RISs phase constraints |  Oblique manifold algorithm, MM
[77] |  MISO-DL-MU |  Continuous/ Discrete |  Rician fading |  Perfect |  BS transmit beamformer, and RIS phase shifts |  Total transmit power and RISs phase constraints |  AO based path-following algorithm, heuristic algorithm
[78] |  MISO-DL-MU |  Continuous |  Rician fading |  Perfect |  BS transmit beamforming and RIS phase shifts |  Total transmit power, RIS phase, and energy conservation constraints |  AO, CCP, one dimension search

###  III-G Optimization with Integer Constraints: Discrete RIS Phase Shifts
and Resource Allocation Problems

Previous sections show that many existing studies assume continuous RIS phase
shifts for simplicity, but practical RISs usually have limited phase-shift
resolutions, indicating discrete phase shifts for the incident signal.
However, such realistic settings will lead to discrete control variables along
with mixed integer nonlinear programming (MINLP) problems, considerably
increasing the difficulty of optimization. In addition, RIS element on/off
control, resource allocation, and association problems will also involve
integer control variables.

Compared with former problem formulations, the main difference is that
discrete control variables lead to integer constraints. For instance, discrete
RIS phase shifts include a constraint
$\theta_{n}\in\\{0,\frac{2\pi}{2^{\varrho}},...,(2^{\varrho}-1)\frac{2\pi}{2^{\varrho}},2\pi\\}$,
where $\varrho$ is the RIS phase-shift resolution. RIS elements on/off,
subchannel allocation, and user association problems will involve binary
constraints as $\chi\in\\{0,1\\}$, where $\chi$ is the binary decision
variable. We summarize three approaches to formulate optimization problems
with integer control variables:

  * •

Relaxation method: This method is to relax the discrete RIS phase shifts
$\theta_{n}\in\\{0,\frac{2\pi}{2^{\varrho}},...,(2^{\varrho}-1)\frac{2\pi}{2^{\varrho}},2\pi\\}$
into continuous phase shifts with $0\leq\theta_{n}<2\pi$. Similarly, the
binary control variables in resource allocation and association problems with
$\chi\in\\{0,1\\}$ are converted into $0\leq\chi\leq 1$. Such linear
programming relaxation can transform NP-hard problems into related problems
that may be solvable in polynomial time. In addition, the relaxation method
may introduce penalties in the objective function by allowing violating
constraints such as Lagrangian relaxation. Then, the reformulated problem
formulations are solved by using algorithms such as SCA or MM. These methods
will be included in Section IV.

  * •

Quantization approach: The quantization method is mainly used to simplify the
RIS phase-shift control. It considers continuous RIS phase shifts when solving
the problem, and then the achieved optimal RIS phase shifts are quantized into
the closest discrete values as
$\theta_{n}\in\\{0,\frac{2\pi}{2^{\varrho}},...,(2^{\varrho}-1)\frac{2\pi}{2^{\varrho}},2\pi\\}$.
For example, the authors in [37] maximize the received signal strength by
using BCD and SDR, and the achieved continuous RIS phase shifts are easily
converted into the nearest discrete values. Compared with the relaxation
method, the quantization approach has much lower complexity with few
reformulations. However, the solution quality may be considerably degraded
when quantizing the continuous values into discrete solutions. For example,
the quantization approach may have difficulty handling binary decision
problems since all continuous solutions between 0 and 1 can only be quantized
into values 0 or 1. In this case, the relaxation method is more appropriate
for binary decision-making.

  * •

Heuristic and ML techniques: Heuristic and ML techniques also provide
attractive solutions for MINLP problems. Discrete control variables are
directly optimized without relaxation and transformation, which will be
introduced in Section V and VI.

TABLE VII: Summary of discrete control variables for optimizing RIS-aided
wireless networks

Discrete control variables |  Main features |  Solution algorithms
---|---|---
Discrete RIS phase shifts |  Discrete phase shift indicates that the phase of each RIS element can only be selected from multiple fixed values. It is more practical than continuous phase changing, but increases the optimization complexity as MINLP problems. |  Relaxation method, quantization method[37], BnB[26], heuristic and ML algorithms[65, 79].
RIS on/off decision |  RIS on/off decision is to decide the on/off status of each RIS element, which can better save energy consumption and improve energy efficiency. |  Greedy algorithms [54], dual method.
Association decisions |  User-RIS-BS associations are key control variables for optimizing multi-cell and multi-RIS network performance. In addition, these association decisions can apply to RIS-UAV systems for the user-UAV association. |  Matching theory is the most widely used method for solving association and resource allocation problems [80, 81]. Meta-heuristic and ML algorithms also present promising solutions.
Resource allocation decision |  Resource allocation is a key decision for optimizing RIS-aided wireless network performance, which will directly decide the user experience. |
D2D-user pairing in RIS-aided D2D networks |  RIS provides a promising opportunity for the interference control of D2D communications, and the pairing of celluar users and D2D links is important to reuse the subchannels allocated to users. |  Hungarian algorithm[82], heuristic pairing[83].
Task offloading in RIS-aided MEC |  RIS could change the channel condition for MEC services to increase channel efficiency, and task offloading decision is one of the core decisions for MEC services. |  BCD and SCA [84], DRL[85].

TABLE VIII: Summary of different CSI error models for optimizing RIS-aided
wireless networks

CSI error model |  Main features |  Solution algorithms
---|---|---
Deterministic model |  Deterministic model defines an upper bound of the CSI error. Most existing studies convert the optimization problem into max-min formulations to guarantee the worst-case performance, i.e., secrecy rate maximization [86], weighted sum-rate maximization [87]. |  AO, SDR, SCA[87], penalty CCP, MM[75] [76].
Stochastic model |  Stochastic model indicates that CSI error follows certain distributions without a predefined upper bound. Therefore, an outage probability constraint is applied to guarantee network performance, i.e., power minimization and secrecy rate maximization with SINR and secrecy rate outage probability constraints[88, 89]. |  SCA[88], DDPG[89]

In summary, the quantization approach has the lowest complexity by
transforming continuous RIS phase shifts into the nearest discrete values, but
such brute-force transformation may degrade the network performance. The
relaxation method converts discrete control variables into continuous
optimization problems. It may guarantee optimality but require case-by-case
analyses and complicated design. By contrast, heuristic and ML techniques can
better handle discrete optimization problems by using heuristic rules and ML
algorithms. For instance, discrete RIS phase shifts are defined as actions in
[79], and then the DRL agent interacts with the wireless environment directly
to maximize the long-term benefit.

Table VII overviews integer control variables that are involved in the
optimization of RIS-aided wireless networks, including discrete RIS phase
shifts, RIS on/off control, resource allocation and association, D2D-user
pairing for RIS-D2D communications, and task offloading decisions for RIS-
aided MEC. Table VII shows that handling these integer control variables is
critical to optimize network performance, and heuristic and ML algorithms are
regarded as appealing approaches to solve these NP-hard problems.

###  III-H Optimization Constraints for Imperfect CSI

CSI availability is critical for properly optimizing RIS-aided wireless
networks. Note that there are many advanced channel estimation methods to
provide accurate CSI[15], and then most existing studies assume perfect CSI as
shown from Table II to VI. However, obtaining perfect and instant CSI is
impractical due to limited feedback overhead, noise, and interference. As
shown in Table VIII, the CSI estimation error can be described by
deterministic or stochastic models.

  * •

Deterministic model: The deterministic model indicates an upper bound of the
CSI error as $||e_{Ch}||\leq e_{Ch,max}$, where $e_{Ch}$ is the estimation
error and $\leq e_{Ch,max}$ is the upper bound. Then $||e_{Ch}||\leq
e_{Ch,max}$ will be included in the problem formulations shown from Section
III-B to III-F. In addition, problem formulations with the deterministic error
model will become a max-min problem to guarantee the worst-case performance,
which is similar to Section III-E.

  * •

Statistical model: On the other hand, the statistical model considers the CSI
error as a random variable with specific distributions such as complex
Gaussian distribution. Without CSI error bound, an extra constraint is
required to guarantee the network performance $Pr(\gamma\geq\gamma_{min})\geq
Pr_{min}$, where $\gamma_{min}$ is the minimum SINR requirement, and
$Pr_{min}$ is the minimum probability requirement that the SINR is higher than
the target value. $Pr(\gamma\geq\gamma_{min})\geq Pr_{min}$ is a probabilistic
constraint because there is no upper limit on the CSI error, and a large error
will unavoidably lead to system outages.

Finally, note that there are many algorithms that can be used to optimize
problems with imperfect CSI constraints, including AO, SCA, SDR, and DRL,
which will be introduced in the following sections.

###  III-I Discussions and Analyses

Sections III-B to III-H have investigated various problem formulations for
RIS-aided networks, and then this subsection aims to analyze the common
features of these formulations. Especially, identifying the main challenges of
solving these problems can motivate us to find more efficient solutions.

1) Non-convex Objectives and Constraints: One common feature of RIS-related
optimization problems is that the objectives and constraints are usually non-
convex and highly non-linear. For instance, fractional terms are frequently
involved with SINR, and the logarithm is usually included due to Shannon’s
formula. These fractional and logarithmic terms lead to non-convex terms in
objectives and constraints. Thus dedicated transformation and relaxation are
needed to reformulate the problem for convexity, which requires case-by-case
analyses for each problem formulated.

2) Highly Coupled Control Variables: RIS passive beamforming is often combined
with other techniques, e.g., BS active beamforming, NOMA, and UAVs. This
results in highly coupled control variables, e.g., RIS phase-shift design,
user decoding order in NOMA, BS transmit power control, UAV trajectory design,
and so on. For instance, in RIS-UAV systems, when changing the UAV altitude,
the RIS phase shifts must be simultaneously optimized to maintain the network
performance. Compared with optimizing RIS phase shifts solely, such
correlation between network functions and control variables is much more
complicated. The ideal solution is to jointly optimize all variables
simultaneously, but this can be extremely difficult due to the interactions
between these techniques.

3) Large Solution Spaces: RIS-related optimization problems usually involve a
large solution space due to the considerable number of RIS elements.
Meanwhile, the integration with other techniques also contributes to the size
of the solution space. For instance, compared with RIS passive beamforming,
joint active and passive beamforming problems are more complicated by
including BS beamforming vectors, leading to a much larger solution space.
Such large solution spaces indicate extra difficulty when exploring the
optimal solution, e.g., large datasets and action spaces for deploying ML
algorithms.

4) Integer Control Variables: As introduced in Section III-G, integer control
variables are frequently involved in optimizing RIS-aided networks, e.g.,
resource allocation and user-RIS-BS association. These integer control
variables will result in NP-hard problems, which cannot be efficiently solved
in polynomial time. In addition, optimization problems become more complicated
when both integer and continuous control variables are included, such as joint
RIS phase-shift design and elements on/off control.

Finally, given the above features, it is critical to investigate efficient
optimization algorithms to handle these challenges and realize the full
potential of RIS-aided networks. In the following sections, we will introduce
model-based, heuristic, and ML optimization approaches.

##  IV Model-based Optimization Algorithms for RIS-aided Wireless Networks

This section introduces model-based algorithms and applications for optimizing
RIS-aided wireless networks, including AO, MM, SCA, BCD, SDR, SOCP, FP, and
BnB. In addition, we summarize the features, advantages, drawbacks,
difficulties, and applications of these techniques.

###  IV-A Alternating Optimization

AO has been widely applied for RIS-related control and optimizations. The main
reason is the high complexity of joint optimization problems that include
multiple control variables such as the BS beamforming matrix and RIS phase
shifts. For instance, the joint active and passive beamforming is usually
decoupled into an active BS beamforming sub-problem and passive RIS
beamforming sub-problem, and then each sub-problem is alternatively optimized.
In particular, for an optimization problem with $I$ control variables
$\vec{x}=(x_{1},x_{2},...,x_{i},...,x_{I})$ and $x_{i}\in X_{i}$, to minimize
objective function $f(\vec{x})$, AO method is summarized by

  * •

Step 1: Initializing the control variables by setting
$\vec{x^{0}}=(x^{0}_{1},x^{0}_{2},...,x^{0}_{i},...,x^{0}_{I})$. Defining
control variable number $i=1$, iteration number $l=1$, maximum iteration
number $L$, and termination threshold $\delta$.

  * •

Step 2: In the $l^{th}$ iteration, for control variable $x^{l}_{i}$,
optimizing $f(\vec{x})$ by finding $x_{i}$ that satisfies

$x^{l}_{i}\leftarrow\operatorname*{arg\,min}\limits_{x_{i}\in
X_{i}}f(\underbrace{x^{l}_{1},x^{l}_{2},...,x^{l}_{i-1}}_{\textbf{done}}\underbrace{,x_{i},}_{\textbf{current}}\underbrace{x^{l-1}_{i+1},...,x^{l-1}_{I}}_{\textbf{todo}}),$
(9)

while holding all the other control variables
$(x^{l}_{1},x^{l}_{2},...,x^{l}_{i-1},x^{l-1}_{i+1},...,x^{l-1}_{I})$
constant.

  * •

Step 3: $i=i+1$ and repeating from Step 2 until $i\leq I$.

  * •

Step 4: If $f(\vec{x_{l}})-f(\vec{x_{l-1}})\leq\delta$, stopping all
iterations and $\vec{x_{l}}$ is the optimal solution; if not, moving to step
5.

  * •

Step 5: If $l\leq L$, then $l=l+1$, and setting control variable number $i=1$
and repeat from Step 2; if not, outputting $\vec{x_{L}}$ as the optimal
solution.

In equation (9), AO simplifies joint optimization problems by optimizing
single control variables alternatively while holding other variables
unchanged[90]. Each iteration is time-efficient by optimizing one individual
variable, which is easily implemented. In addition, it does not require step
size parameter tuning and extra storage vectors. AO provides an iterative
optimization scheme, but it still relies on other techniques to solve each
sub-problem. Also, having each variable monotonically decrease at each
iteration does not guarantee the algorithm will converge to a global minimum,
and moreover, the convergence may slow down near an optimum point[90].

The RIS is often combined with other techniques for joint optimization, such
as joint active and passive beamforming, RIS-related resource allocation, RIS-
NOMA, and RIS-MEC, leading to coupled control variables and large solution
spaces. AO is particularly useful in solving such joint optimization problems.
For example, the RIS-MEC system can be decoupled into RIS phase-shift control
sub-problem and task offloading sub-problem, and these two sub-problems will
be iteratively optimized to reduce the overall complexity. Joint active and
passive beamforming is another example that has been widely investigated,
which applies AO to generate BS active beamforming and RIS passive beamforming
sub-problems[38, 39].

###  IV-B Block Coordinate Descent

Coordinate descent is a very useful method to solve large-scale optimization
problems, and BCD is considered a generalized version to improve computation
efficiency. Compared with AO, each block in the BCD algorithm may include
several control variables, enabling dynamic block generation, selection and
updating. Therefore, BCD method is more suitable than AO for optimizing a
large number of control variables simultaneously, which has been widely
applied to RIS-related optimization problems.

BCD method sequentially minimizes the objective function $F(\vec{x})$ in each
block $x_{i}$ while the other blocks are held fixed. Specifically, it
minimizes
$x^{l}_{i}\leftarrow\operatorname*{arg\,min}\limits_{x_{i}\in\mathscr{X_{i}}}(f(x_{i})+f_{i}(x_{i}))$
while holding other blocks $x_{1},x_{2},...,x_{i-1},x_{i+1},...x_{I}$ fixed.
However, it is worth noting that each block consists of multiple control
variables, and the block selection and updating method will affect the BCD
performance. An ideal block selection method is expected to maximize the
improvement by choosing the blocks that decrease $F(\vec{x})$ by the largest
amount[91]. On the other hand, there are many alternatives for the block
updating method such as block proximal updating

$x^{l}_{i}\leftarrow\operatorname*{arg\,min}\limits_{x_{i}\in\mathscr{X_{i}}}(f(x_{i})+f_{i}(x_{i})+\frac{L_{i}^{l-1}}{2}\|x_{i}-x^{l-1}_{i}\|^{2}),$
(10)

where $L_{i}^{l-1}>0$. Equation (10) is more stable than conventional BCD by
including $\frac{L_{i}^{l-1}}{2}\|x_{i}-x^{l-1}_{i}\|^{2}$. The BCD algorithm
is easily deployed with low memory requirements and iteration costs, allowing
parallel or distributed implementations. But the block selection may affect
the algorithm performance, and block updating is difficult in some cases.

Similar to AO, BCD is considered as an iteration-based scheme to reduce
problem-solving complexity. BCD has been applied to sum-rate maximization [21,
25, 27], user fairness maximization [37], and power minimization [48]. As an
example, a two-block BCD is used to maximize the sum-rate in [27], in which
the first block is for BS active beamforming and the second is for RIS passive
beamforming, then these blocks are iteratively optimized.

Figure 5: MM method for RIS-related optimizations.

###  IV-C Majorization-Minimization Method

MM is an iterative optimization method that has been applied for RIS control
and optimizations. Consider an optimization problem $\min\limits_{x}f(x)$ and
$x\in\mathscr{X}$, where $f(x)$ is a continuous objective function and
$\mathscr{X}$ is a convex closed set. In RIS-related control problems, the
$f(x)$ is usually complicated to solve directly due to fractional and
logarithmic terms. As shown in Fig. 5, the main idea of the MM algorithm is to
construct a surrogate function $g(x)$ that can locally approximate the
objective function $f(x)$, e.g., power minimization or sum-rate maximization.
$g(x)$ is considered an upper bound of $f(x)$, which is easier to be
optimized. Therefore, optimizing $g(x)$ can either improve the objective
function value or leave it unchanged with $g(x)\geq f(x)$[92].

Constructing a surrogate function $g(x)$ is the first step of applying the MM
algorithm, since $g(x)$ will be optimized directly instead of the original
objective $f(x)$. The $g(x)$ construction rules include:
A1): $g(x^{l-1}|x^{l-1})=f(x)$; A2): $g(x|x^{l-1})\geq f(x)$;
A3):
$g^{\prime}(x|x^{l-1};d)|_{x=x^{l-1}}=f^{\prime}(x^{l-1};d)|_{x=x^{l-1}}$;
A4): $g(x|x^{l-1})$ is continuous in $x$ and $x^{l-1}$,
where $x^{l-1}$ is the produced point at iteration $l-1$. $g(x|x^{l-1})$ is an
approximation function of $f(x)$ at the iteration $l$, and ”$|$” in
$g(x|x^{l-1})$ means that the point $x^{l-1}$ is already on this function. $d$
indicates the distance from a point $x$ to a set $\mathscr{X}$ and
$d=\inf\limits_{x^{\prime}\in\mathscr{X}}||(x-x^{\prime})||$.
$f^{\prime}(x;d)$ is the directional derivative of $f(x)$ in direction $d$.
Assumptions (A1) and (A2) indicate that $g(x|x^{l-1})$ is a tight upper bound
of the original objective $f(x)$. It guarantees that optimizing $g(x|x^{l-1})$
can meanwhile find an improved objective value for $f(x)$. Note that surrogate
function may be defined in various ways, e.g. Jensen’s inequality, Convexity
inequality, Cauchy–Schwarz inequality. Then, the surrogate function
$g(x|x^{l-1})$ is iteratively minimized and updated by
$x^{l}\leftarrow\operatorname*{arg\,min}\limits_{x\in\mathscr{X}}g(x|x^{l-1})$
until convergence.

As an estimation-based method, MM is considered a low-complexity solution for
many RIS-related optimizations, including sum-rate maximization[21], fairness
maximization[64, 58], secure transmission[73] and so on. For example, the
joint active and passive beamforming problem is decoupled into BS transmit
power control and RIS phase-shift optimization in both [21] and [64]. Then,
the RIS phase-shift optimization problem is first converted into a non-convex
quadratically constrained quadratic program (QCQP) problem222A QCQP problem
example is given by equation (12) in Section IV-E, which is frequently
formulated in wireless networks., and a MM algorithm is applied to obtain
locally optimal solutions by $\min_{\theta}g(\theta|\theta^{l})$ with
constraint $|\theta_{n}|=1$. After that, the optimal phase shift $\theta$ in
current iteration $l$ is obtained as $\hat{\theta}^{l}$, and then $l=l+1$ and
$\hat{\theta}^{l}$ becomes a new $\theta^{l}$ in
$\min\limits_{\theta}g(\theta|\theta^{l})$.

The MM applies surrogate functions to avoid the complexity of optimizing the
non-convex objective function directly, transforming non-differentiable
problems into smooth optimizations. The MM method requires that the surrogate
function $g(x)$ must be a global upper bound for $f(x)$, which is a
fundamental assumption for using MM. However, defining such a tight upper
bound can be impractical in some cases, which may prevent the application of
the MM method.

###  IV-D Successive Convex Approximation

Figure 6:  Using SCA algorithm for RIS-related optimization.

Similar to the MM algorithm, SCA applies a surrogate function $g(x)$ to
approximate the original objective function $f(x)$, which is shown in Fig. 6.
However, the $g(x)$ in the SCA algorithm does not have to be a tight upper
bound for $f(x)$, reducing the complexity of the surrogate function design
[93]. Therefore, SCA is more flexible and easier to be implemented for RIS-
related optimization problems.

The SCA method first constructs a surrogate function $g(x)$, and the
assumptions are similar to the MM algorithm:
A1): $g(x|x^{l-1})$ is continuous in $\mathscr{X}$;
A2): $g(x^{l-1}|x^{l-1})=f(x)$;
A3): $g(x)$ is differentiable with
$\nabla_{x}g(x|x^{l-1})|_{x=x^{l-1}}=\nabla_{x}f(x)|_{x=x^{l-1}}$.
SCA relaxes the upper bound condition for the surrogate function, but
$g(x|x^{l-1})$ must be strongly convex in $\mathscr{X}$. Then, solving the
constructed surrogate problem
$\mathbf{\hat{x}}(x^{l})\leftarrow\operatorname*{arg\,min}\limits_{x\in\mathscr{X}}g(x|x^{l-1})$,
and smoothing the next point by

$x^{l}=x^{l-1}+\beta^{l-1}(\mathbf{\hat{x}}(x^{l})-x^{l-1}),$ (11)

where $\beta^{l-1}$ is the step size for value updating. Finally, $g(x)$
construction and solving are repeated until meeting the convergence criteria.
In SCA, the surrogate function $g(x)$ does not have to be a tight upper bound
for $f(x)$. Therefore, the step size in each iteration requires dedicated
designs to guarantee an accurate approximation. The factor $\beta^{l-1}$ is
used to control the $x^{l}$ updating step size. Meanwhile, the MM algorithm
updates the whole control variable $x$ at each iteration, but SCA can be
naturally implemented in a distributed manner when the constraints are
separable.

Compared with MM, SCA is more frequently applied in RIS-related optimizations
due to the relaxed upper bound, e.g., sum-rate maximization in [24, 30, 29]
and power minimization in [41, 46]. Defining a surrogate function is the key
to using the SCA method, which depends on specific objective functions and
constraints in RIS-related applications. For instance, the non-convex BS
transmit power constraint in [41] is replaced by a first-order Taylor
approximation to apply the SCA algorithm. By contrast, Pan et al. in [11]
claim that the unit modulus constraint of the RIS phase shift $|\theta_{n}|=1$
can be relaxed as a series of convex constraints, e.g., $1\leq 2{\rm
Re}\\{\theta^{*}_{n}\theta_{n}^{l}\\}-|\theta_{n}^{l}|^{2}$, where ${\rm
Re}\\{\cdot\\}$ denotes the real part of a complex argument and $\theta^{*}$
is the conjugate of $\theta$.

###  IV-E Semidefinite Relaxation

Many RIS-related signal processing problems can be described by QCQP
formulations, and SDR is an efficient solution to solve QCQP problems[94]. The
QCQP problem is defined by

$\displaystyle\min\limits_{x\in\mathscr{X}}$ $\displaystyle x^{T}Cx$ (12) s.t.
$\displaystyle x^{T}D_{i}x\geq b_{i},i=1,2,3,,,n,$

where the ”$\geq$” in the constraint can also be replaced by ”$\leq$”. Note
that $x^{T}Cx$ produces an $1\times 1$ matrix, and therefore
$x^{T}Cx=Cx^{T}x=Tr(Cx^{T}x)$. Similarly,
$x^{T}D_{i}x=D_{i}x^{T}x=Tr(D_{i}x^{T}x)$ is achieved. By introducing
$X=xx^{T}$, then

$\displaystyle\min\limits_{x\in\mathscr{X}}$ $\displaystyle Tr(CX)$ (13) s.t.
$\displaystyle Tr(DX_{i})\geq b_{i},i=1,2,3,,,I,$ $\displaystyle X\succeq 0,$
$\displaystyle rank(X)=1,$

where $Tr$ indicates the trace operation, and $X\succeq 0$ indicates that $X$
is positive semidefinite with $X=xx^{T}$. Then, the non-convex constraint
$rank(X)=1$ is relaxed and achieve

$\displaystyle\min\limits_{x\in\mathscr{X}}$ $\displaystyle Tr(CX)$ (14) s.t.
$\displaystyle Tr(DX_{i})\geq b_{i},i=1,2,3,,,I,$ $\displaystyle X\succeq 0.$

Equation (14) is an SDR of (13), which can be efficiently solved by
semidefinite programming (SDP)[95]. SDR has been very generally applied to
RIS-related optimization problems, since the $rank(x)=1$ is frequently
formulated for phase control. Specifically, the RIS phase shift constraint
$|\theta_{n}|=1$ is non-convex with $\theta\theta^{T}=1$. Then we can define
$\mathcal{V}=\theta\theta^{T}$ with $\mathcal{V}\succeq 1$ and
$rank(\mathcal{V})=1$, which can be then transformed and relaxed as shown by
equations (13) and (14).

However, the main obstacle to applying SDR is to transform a globally optimal
solution $\hat{\mathcal{V}}$ into a feasible solution $\hat{\theta}$. An ideal
solution is that $\hat{\mathcal{V}}$ is rank-one, and then $\hat{\theta}$ is
easily obtained by solving $\hat{\mathcal{V}}=\hat{\theta}\hat{\theta}^{T}$.
Otherwise, if $rank(\hat{\theta})>1$, a rank-one approximation may be used to
obtain a sub-optimal solution $\widetilde{\theta}$. There are multiple methods
to find a feasible $\widetilde{\theta}$ from $\hat{\mathcal{V}}$, leading to
various solution qualities. For instance, Mu et al. propose a penalty-based
method to relax the rank-one constraint, finding a sub-optimal solution by
introducing penalties if $rank(\hat{x})>1$ [4]. SDR has been used for sum-rate
maximization [26, 96, 34], power minimization [40, 41, 42, 46], fairness
maximization [37, 60, 63, 64], and secure transmission [67, 74, 69, 70, 72].

Figure 7: An example of a second-order cone in 3D space.

###  IV-F Second-order Cone Programming

SOCP is another method that is used to efficiently solve optimization problems
in wireless networks, especially for QCQP and fractional problems. Fig. 7
presents a second-order cone example in 3D space. SOCP is a generalization of
linear and quadratic programming that allows for affine combinations of
variables to be constrained inside a second-order cone

$\displaystyle\min\limits_{x\in\mathscr{X}}$ $\displaystyle C^{T}x$ (15) s.t.
$\displaystyle||A_{i}x+b_{i}||\leq c_{i}^{T}x+d_{i},i=1,2,3,,,I,$

where $A\in\mathbb{R}^{n_{i}\times n}$, $b_{i}\in\mathbb{R}^{n_{i}}$,
$c_{i}\in\mathbb{R}^{n}$, and $d_{i}\in\mathbb{R}$. The $x$ in equation (15)
may be RIS phase shifts, BS beamforming vectors, and so on, which depends on
specific application scenarios. Consider the inverse image of the unit second-
order cone with an affine mapping

$||A_{i}x+b_{i}||\leq
c_{i}^{T}x+d_{i}\leftrightarrow\left[\begin{array}[]{c}A_{i}\\\ c_{i}^{T}\\\
\end{array}\right]x+\left[\begin{array}[]{c}b_{i}\\\ d_{i}\\\
\end{array}\right]\in\mathscr{C}_{n_{i}+1}.$ (16)

Therefore, SOCP is a convex optimization problem with a convex objective
function and convex constraints. Equation (16) indicates the core properties
of SOCP problems, and hence many problems are converted into SOCPs and solved
efficiently[97].

For instance, sum and fractional problems are frequently defined in RIS-
related problems to maximize the sum-rate or total throughput regarding the
SINR

$\displaystyle\min\limits_{x\in\mathscr{X}}$
$\displaystyle\sum_{i=1}^{I}\frac{||C_{i}^{T}+D_{i}||^{2}}{A_{i}^{T}x+B_{i}}$
(17) s.t. $\displaystyle A_{i}^{T}x+B_{i}\geq 0,i=1,2,3,,,I,$

which is converted into a SOCP by

$\displaystyle\min\limits_{x\in\mathscr{X}}$
$\displaystyle\sum_{i=1}^{I}t_{i}$ (18) s.t.
$\displaystyle(C_{i}^{T}+D_{i})^{T}(C_{i}^{T}+D_{i})\leq
t_{i}(A_{i}^{T}x+B_{i}),$ $\displaystyle A_{i}^{T}x+B_{i}>0,i=1,2,3,,,I.$

SOCP can be efficiently solved by the interior point method. Meanwhile, SOCP
is less general than SDP since equation (15) may be transformed into an SDP
problem. However, the complexity of solving SOCP is $O(n^{2}\sum_{i}{n_{i}})$,
while the complexity for SDP is $O(n^{2}\sum_{i}{n_{i}}^{2})$[98]. Such
complexity difference is crucial for large-dimension problems.

Finally, to apply SOCP for RIS-aided optimizations, the first step is to
utilize AO or BCD scheme to decouple the control variables into multiple sub-
problems, e.g., BS precoding matrix and RIS passive beamforming[58, 44, 64],
coordinated transmit beamforming and RIS passive beamforming[60]. For example,
the max-min data rate problem in [64] is decoupled into SOCP-based BS
beamforming and SDR-based RIS phase-shift control, and the data rate
maximization problem in [25] is converted into a SOCP-based BS active
beamforming and SDR-based RIS passive beamforming.

###  IV-G Fractional Programming

FP refers to optimization problems involving ratios or fractional terms. FP is
particularly useful for wireless network optimizations due to the fractional
terms in communication systems, especially for SINR and energy efficiency[99].

Consider a single-ratio FP problem to maximize the SINR of single UE by
$\max\limits_{x\in\mathscr{X}}{f(x)}/{g(x)}$, where $f(x)$ is the signal
strength and $g(x)$ is the interference and noise. There are many classic
methods to solve FP problems, such as Charnes-Cooper transform and
Dinkelbach’s transform[100]. Dinkelbach’s method reformulates the problem into
$\max\limits_{x\in\mathscr{X},y\in\mathbb{R}}f(x)-yg(x)$, where $y$ is the
auxiliary variable that is updated iteratively
$y^{(l+1)}={f(x)^{l}}/{g(x)^{l}}$, and $l$ is the iteration number. Then,
alternatively updating $y$ and $x$ will lead to a converged solution with non-
decreasing $y^{l}$. However, instead of the single-ratio problem, sum-ratio FP
problems are more frequently involved in wireless networks, i.e., maximizing
sum-rate or total channel capacity as $\max\limits_{x\in\mathscr{X}}\
\sum_{i=1}^{I}f_{i}(x)/g_{i}(x)$.

However, classic methods can not be directly generalized to sum-ratio cases,
since maximizing single ratios cannot guarantee the convergence and
maximization for sum-ratio cases. An equivalent transform proposed by [101] is

$\max\limits_{x\in\mathscr{X},y\in\mathbb{R}}\quad 2yf(x)^{0.5}-y^{2}g(x),$
(19)

which can be readily converted into sum-ratio problems. In addition, equation
(19) is further generalized to sum-ratio problems as

$\max\limits_{x\in\mathscr{X},y\in\mathbb{R}}\quad\sum_{i=1}^{I}F_{i}(2y_{i}C_{i}(x)^{0.5}-y_{i}^{2}D_{i}(x)),$
(20)

where $F_{i}$ is a non-decreasing function. Equation (20) is particularly
useful given the frequently used term $\sum log(1+SINR)$ in wireless
communications.

The FP method can significantly lower the problem-solving complexity by
eliminating fractional items. This transformation is very useful for RIS-
related optimization problems, especially considering that RIS phase shifts
will affect the received signal strength and interference simultaneously. In
addition, the FP method can be particularly useful for RIS-related max-min
fairness problems, which are usually formulated as
$\max\limits_{x\in\mathscr{X}}\ \min\limits_{1\leq i\leq I}\
{f_{i}(x)}/{g_{i}(x)}$, where $x$ indicates the control variables, e.g., RIS
phase shifts and BS transmit power. $f_{i}(x)$ can be the signal strength of
user $i$, and $g_{i}(x)$ indicates the interference and noise. Then the max-
min fairness problems can be reformulated as

$\displaystyle\max\limits_{x\in\mathscr{X},y,z\in\mathbb{R}}$
$\displaystyle\quad z$ (21) s.t. $\displaystyle
2y_{i}f_{i}(x)^{0.5}-y_{i}^{2}g_{i}(x)\geq z;i=1,2,3,,,I.$

where $z$ is an intermediate objective function that is included in the
constraint. A detailed proof of obtaining equation (21) can be found in [101].

The FP method significantly reduces the optimization complexity by decoupling
the fractional terms. Therefore, it has been widely used in wireless network
optimizations, including power control, beamforming, energy efficiency, and so
on[27, 52]. However, note that FP is usually used for transformation, and then
the reformulated problems still need to be solved by other techniques. A
widely considered method is first to apply FP to eliminate the fractional
terms in objective functions, e.g., throughput and power consumption for
energy efficiency maximization, received signal strength and interference for
SINR maximization. And then, AO is used to separate the coupled control
variables, e.g., RIS phase-shift design and BS transmit power control, and
optimize each sub-problem iteratively.

Figure 8: Using BnB for RIS control with discrete phase shifts. TABLE IX:
Summary of model-based optimization algorithms for RIS-aided wireless networks

Methods |  Main features |  Advantage |  Drawbacks |  Difficulties |  Application scenarios
---|---|---|---|---|---
AO |  Decoupling the joint optimization into multiple sub-problems, and alternatively optimizing each sub-problem. |  The problem-solving complexity is greatly reduced. Each sub-problem may be easier to solve. |  Iterative optimization may lead to sub-optimal results; the convergence must be proved. |  The complexity is high when each sub-problem is still complicated. |  AO is the most widely applied optimization scheme for RIS-aided networks. It decouples the joint optimization into multiple sub-problems and then optimizes them iteratively [50].
BCD |  The control variables are divided into multiple blocks. Minimizing one block in each iteration and keeping other blocks fixed. |  Cheap iteration costs; low memory requirements; potential for parallel implementation |  Block selection may affect the BCD performance, and block updating is difficult in some cases. |  Block selection and updating methods are complicated. |  BCD employs alternating schemes to reduce joint optimization complexity, e.g., sum-rate maximization [21] and power minimization[48], and one block in BCD may include multiple control variables.
MM |  Iteratively constructing and optimizing an upper bound surrogate function that can locally approximate objective functions. |  Avoiding the complexity of optimizing non-convex objective functions directly. |  The surrogate function must be a strict tight upper bound for objective functions, which is hard to achieve in practice. |  The surrogate function must follow the shape of objective functions and meanwhile be easy to optimize. |  The MM applies surrogate functions as low-complexity solutions for many RIS-aided optimizations, i.e., sum-rate maximization[21], fairness maximization[64, 58], secure transmission[73].
SCA |  Constructing and optimizing surrogate functions iteratively to estimate the objective function. |  Low computational complexity; the tight upper bound is not required for the surrogate function; naturally implemented in a distributed manner. |  The step size selection is critical for an accurate approximation. |  Surrogate function and step size selection. |  SCA relaxes the tight upper bound constraint on surrogate function design. Such an estimation-based approach is easier to be implemented in RIS-related optimization, e.g., sum-rate maximization [24, 30] and power minimization[41, 46].
SDR |  SDR is used to solve QCQP problems by relaxing the rank constraint. Then the reformulated problem is efficiently solved by SDP. |  Given the objective problem, SDR is easily implemented without extra parameters or settings. |  Approximation is required if the relaxed solution is not rank one. |  The reformulated problem is complicated if the achieved solution is not rank one. |  SDR is particularly useful to solve $rank(x)=1$ constraints, such as RIS phase-shift constraint $|\theta_{n}|=1$ [26] [96, 38].
SOCP |  SOCP utilizes the property of the second-order cone, and many problems are reformulated into SOCP, which is much easier to be solved. |  SOCP can be efficiently solved by many existing algorithms. It has a lower complexity $O(n^{2}\sum_{i}{n_{i}})$ than SDR. |  Problem reformulation into SOCP is complicated. |  The main difficulty lies in how to reformulate the original problem into SOCP. |  SOCP can be very useful if the RIS-related problems can be easily formulated as a second-order cone, which has been used for power minimization [44] and user fairness [58, 60, 64].
FP |  FP refers to optimization problems that involve fractional terms, which is very useful for wireless communications considering the form of SINR and energy efficiency. |  FP is easily implemented without extra parameters or problem formulation requirements. |  The reformulated problems generally require iterative optimization to approximate the solution of original FP problems. |  Compared with single-ratio problems, wireless networks are more related to sum-ratio problems, which are more complicated to solve. |  FP is particularly useful when decoupling the fractional terms in RIS-related problems, e.g., SINR and energy efficiency. It is widely applied for optimizing RIS-aided networks [27, 46, 50].
BnB |  BnB is mainly designed for combinational optimization problems. It applies a tree to enumerate all possible subsets and sub-problems. |  Lower complexity than direct optimizations. The solution quality is controlled by customized search, branching, and pruning rules. |  The algorithm is slow when constantly searching or branching in the worst case. |  The algorithm performance relies on the searching and pruning method, which is hard to select in some cases. |  Different from aforementioned technique, BnB is mainly applied for discrete and combinational optimization problems, i.e., RIS on/off and discrete phase shift[62, 39, 26].

###  IV-H Branch-and-Bound

BnB is a classic scheme for combinatorial and discrete optimization
problems[102]. To minimize $f(x)$ with $x\in\mathscr{X}$, BnB applies a tree
scheme to enumerate all possible subsets $X_{i}\subseteq\mathscr{X}$, and each
subset $X_{i}$ indicates a sub-problem $f_{i}(x)$. Solving sub-problems
$f_{i}(x)$ will generate and prune branches based on the estimated lower and
upper bounds.

A BnB algorithm consists of three basic operations: branching, bounding, and
pruning. Considering a non-linear integer programming problem, and the BnB
scheme is summarized as Fig. 8, including the search method, branching
strategies, and pruning rules. In particular, the search method indicates the
order of sub-problem exploration in the tree, e.g., which RIS phase-shift
combination is first explored. The branching strategy specifies how to
generate new sub-problems from the solution space, e.g., how to generate a new
set of phase-shift designs. Finally, pruning rules can prevent exploring
specific regions of the tree, which will eliminate sub-optimal RIS phase-shift
solutions. BnB produces a series of sub-problems $f_{i}(x)$ that are
equivalent to the original $f(x)$, which is much more efficient than brute-
force enumeration. It provides an alternative solution for challenging
problems that cannot be solved directly. An important advantage is that the
quality of the solution is controlled by customized searching, branching, and
pruning rules.

BnB is mainly applied for RIS control with discrete phase shift, including
sum-rate maximization [26], power minimization [39], and max-min SINR [62].
The main reason is that the problem formulations are usually MINLP problems,
which are NP-hard and intractable. As shown in Fig. 8, the MINLP is converted
into an 0-1 integer linear programming using the special ordered set of type 1
(SOS1) transformation [39] and reformulation-linearization [62]. BnB
performance is very dependent on search and pruning rules, and defining these
rules can be difficult in some cases. In addition, the algorithm may converge
slowly when constantly searching and branching for new solutions, which may be
caused by the considerable number of RIS elements.

###  IV-I Discussions and Numerical Results

Table IX summarizes model-based algorithms for RIS-aided wireless networks,
including main features, advantages, disadvantages, difficulties, and
application scenarios.

Firstly, considering the high complexity of RIS-related optimization, AO is
regarded as the primary scheme to decouple the joint optimization problem into
several sub-problems. Then, each sub-problem is alternatively solved by using
different algorithms, e.g., SCA, SDR, and BnB. Compared with AO, the BCD
algorithm applies a similar iterative optimization scheme, but one block may
include multiple control variables. When there are a large number of control
variables, the BCD algorithm can be more efficient, e.g., coupled optimization
problem with a considerable number of control variables.

MM and SCA are two estimation-based algorithms that avoid the complexity of
direct optimizations. However, the MM algorithm requires a tight upper bound
when designing the surrogate function. Such requirements can be impractical in
some cases, especially considering non-convex and highly non-linear RIS phase-
shift design problems. By contrast, the SCA method relaxes the upper bound
requirement for surrogate functions, which is more flexible and easier for
design and implementation. However, without the upper bound constraint, the
updating step size in SCA may affect the solution quality, which should be
carefully selected. MM and SCA are usually considered low-complexity solutions
for RIS-aided wireless network optimizations.

SDR and FP are usually combined with other techniques for optimizations. In
particular, SDR is mainly used to relax the RIS phase constraints, while FP
can decouple the numerator and denominator for SINR and energy efficiency
terms. These two techniques reformulate the original problems into low-
complexity or even convex forms, then other techniques can be applied.
Meanwhile, SOCP takes advantage of the property of the second-order cone,
which is efficiently solved by many existing methods. But the main difficulty
is how to transform the problem with logarithm and fractional terms into a
second-order cone. BnB is mainly designed for combinational and discrete
optimization problems, e.g., RIS control with discrete phase shifts and
elements on/off.

(a) Average throughput comparison under various peak traffic loads. AOFP:
combining AO and the FP algorithm; surrogate method: using a surrogate
function to approximate the objective function in a black-box manner.

(b) Convergence performance of AOFP under various numbers of RIS elements.

Figure 9: Simulation results by combining AO and FP to maximize the channel
throughput. We consider a MISO system with one BS and multiple UEs, and the
daily traffic load pattern is shown in 9(a). Detailed simulation parameters
and algorithms can be found in [103].

Finally, it is worth noting that these algorithms are not independent, and
multiple algorithms are usually combined for transformation and optimizations.
The main objective of Table IX is to analyze the feasibility of these problems
for various RIS-related optimizations, and the most efficient solution for
specific scenarios requires case-by-case analyses. For instance, Fig. 9 shows
an example of combining AO and FP for RIS phase-shift control in an MISO
system with multiple UEs. Specifically, it applies FP to decouple the received
signal strength with interference and noise, and then uses AO to optimize
multiple control variables alternatively[103]. Fig. 9(a) presents the average
throughput under various peak traffic loads, which involves a daily traffic
load pattern as shown by the blue shade in Fig. 9(a). Meanwhile, we consider
surrogate optimization as a baseline, which applies surrogate functions to
approximate the objective function in a black-box manner. When the peak
traffic load is light, one can observe that AOFP and surrogate function have
comparable performance, which means that the channel capacity can already
satisfy the traffic demand. However, when peak traffic load increases, AOFP
attains higher throughput than baselines, which demonstrates that RIS control
and deployment strategy should consider dynamic UE traffic demand.
Additionally, Fig. 9(b) presents the convergence performance of AOFP, in which
the objective function is improved with increasing iterations and finally
converges. This reveals the basic features of AO, which is to guarantee the
objective function will be improved iteration-by-iteration, and such a scheme
has been widely used in RIS-related optimization studies.

##  V Heuristic Algorithms for RIS-aided Wireless Networks

As presented in Section IV, model-based algorithms have specific requirements
for problem formulations, especially for convexity and continuity. Meanwhile,
the large number of RIS elements, dynamic channel conditions, and various CSI
levels further contribute to the overall complexity. Therefore,
transformations and relaxations are required to convert the original problem
into specific forms. Moreover, these transformations are usually problem-
specific, requiring case-by-case analyses and dedicated design.

By contrast, heuristic algorithms have fewer requirements for objective
functions and constraints, which will significantly reduce the complexity.
Compared with model-based methods, heuristic algorithms are usually considered
low-complexity solutions. In the following, we will introduce four heuristic
algorithms, including CCP, meta-heuristic algorithms, greedy algorithms, and
matching-based algorithms.

###  V-A Convex-concave Procedure

The CCP algorithm uses the local heuristic to solve difference of convex (DC)
problems, which is considered a low-complexity solution for complicated
wireless network optimization333The main reason that CCP is considered a
heuristic algorithm is that it applies a simple heuristic rule for
optimization, which is iteratively finding two points with the same tangent
vectors[104]. Hence, CCP fits well with our defined classifications of
heuristic algorithms..

DC problems are frequently formulated in many fields, representing many
scenarios that cannot be solved in polynomial time. The DC problem is defined
as

$\displaystyle\max\limits_{x\in\mathscr{X}}$ $\displaystyle\quad
f_{0}(x)-g_{0}(x)$ (22) s.t. $\displaystyle f_{i}(x)-g_{i}(x)\leq 0;\
i=1,2,3,,,I,$

where $f(x)$ and $g(x)$ are both convex. DC problems are usually non-convex
unless $g_{i}(x)$ are affine, which is generally hard to solve.

As shown in Fig. 10, the core idea of CCP is to find $x^{l+1}$ in the $l+1$
iteration that satisfies $\nabla_{x}f(x^{l+1})=\nabla_{x}g(x^{l})$, indicating
a point on $f(x)$ that has the same tangent with $g(x^{l})$[105]. The CCP
algorithm will first form

$\overline{g}_{i}(x|x^{l})=g_{i}(x^{l})+\nabla_{x}g(x)(x-x^{l}),\
i=0,1,2,3,,,I.$ (23)

Then it solves the following problem to get $x^{l+1}$

$\displaystyle\max\limits_{x\in\mathscr{X}}$ $\displaystyle\quad
f_{0}(x)-\overline{g}_{0}(x|x^{l})$ (24) s.t. $\displaystyle
f_{i}(x)-\overline{g}_{i}(x|x^{l})\leq 0;\ i=1,2,3,,,I.$

Equation (24) is equivalent to $\nabla_{x}f(x^{l+1})=\nabla_{x}g(x^{l})$ by
deriving the objective function, and equations (23) and (24) are iteratively
repeated until reaching the stop criteria. CCP algorithm does not require a
dedicated step size design, and the main reason is that the estimator
$f_{0}(x)-\overline{g}_{0}(x|x^{l})$ is global. It retains all the information
from the convex component $f(x)$ and only linearizes the concave portion
$g(x)$.

Figure 10: Convex concave procedure for RIS-related optimization.

Moreover, there are multiple extensions of the CCP algorithm. For instance,
the penalty CCP includes a penalty term for violations, which removes the
requirements for feasible initial points. The RIS phase shift optimization
problem is reformulated as [11]

$\displaystyle\max\limits_{\theta,\tau>0}$ $\displaystyle\quad
f(\theta)-\tau^{l}\sum_{i=1}^{2I}v_{i}$ (25) s.t.
$\displaystyle{g}(\theta)\geq D,$
$\displaystyle|\theta_{i}^{l}|^{2}-2Re\\{\theta^{*}_{i}\theta_{i}^{l}\\}\leq
v_{i}-1,$ $\displaystyle|\theta_{i}|^{2}\leq 1+v_{i+I},\ i=1,2,3,,,I,$

where $\tau^{l}\sum_{i=1}^{2I}v_{i}$ is the penalty term, $v_{i}$ are slack
variables, and $\tau^{l}$ is a coefficient that will decline in each iteration
for convergence. After some transformations, problem (25) can be solved by
using the CVX toolbox, and the detailed procedure is included in [11].

CCP has been applied in [42, 30, 35, 78, 106] for controlling RIS phase
shifts. In these works, the joint optimization problem is first decoupled into
multiple sub-problems using BCD or AO, then penalty CCP is used to solve the
RIS phase shifts sub-problem. The main motivation is the high complexity of
solving non-convex RIS control problems. For example, the sum-rate
maximization problem in [35] is converted into three sub-problems: joint
optimization of the transmit power and spectrum sharing, SDR-based multi-user
detection, and CCP-based RIS phase shifts. However, note that CCP is a
heuristic algorithm that will find a locally optimum solution, and the initial
point $x^{0}$ may affect the final output. In particular, there may exist
multiple locally optimal solutions, and CCP can easily get stuck in a sub-
optimal one.

###  V-B Meta-heuristic Algorithms

One of the main difficulties of controlling RISs is the large number of RIS
elements, leading to huge solution spaces. Therefore, it is hard to achieve
exact solutions by finding a closed-form expression, and hence model-based
approximation algorithms such as SCA and MM are applied. However, these
methods have stringent requirements for objectives and constraints, especially
for convexity, continuity, and differentiability. By contrast, meta-heuristic
algorithms can search significantly large solution spaces with few or no
additional requirements on problem forms [107]. It usually contains
intelligent policies to guide the heuristic exploration, producing high-
quality solutions efficiently. Meta-heuristic algorithms have been extensively
developed, e.g., genetic algorithm (GA), particle swarm algorithm (PSO), ant
colony optimization, simulated annealing, and tabu search [108].

Fig. 11 shows the steps of using population-based meta-heuristic algorithms
for RIS phase-shift design. The first step is to initialize the algorithm
parameters such as population numbers and crossover rate in a genetic
algorithm. Then, the algorithm will produce initial individuals, which
indicates various RIS phase-shift designs. The objective function is converted
into a fitness function, e.g., the sum-rate or energy efficiency. After that,
the algorithm will constantly search for better solutions using heuristic
rules iteratively, such as evolution strategy in a genetic algorithm, and
particle movement for PSO. Finally, the heuristic exploration will stop if the
fitness function values converge or reach maximum iteration numbers.

Compared with model-based methods, the main advantage is that meta-heuristic
algorithms can easily adapt to both continuous and discrete RIS phase shifts
without relaxation and transformation. PSO and GA are used for RIS phase
shifts in [31] and [65] to maximize the data rate. Statistical CSI is
investigated in [32] to obtain a closed-form expression of the uplink ergodic
data rate, then GA is deployed for phase control to maximize the data rate. In
addition, Tabu search is applied to irregular RIS to decide the element design
in [20].

The simulations in [31, 65, 32, 20] show that meta-heuristic algorithms can
significantly reduce the optimization complexity, especially for MINLP
problems. However, it may be trapped in local optima, and the algorithm
performance relies on the parameter settings. For example, the phase shifts of
hundreds of RIS elements require a large number of populations in GA, leading
to high exploration costs. By contrast, reducing the population numbers may
lower the probability of finding optimal solutions.

Figure 11: Population-based meta-heuristic algorithms for RIS phase-shift
control.

###  V-C Greedy Algorithms

Most former algorithms are designed to find global optima of the objective
function. However, many problems are NP-hard and non-convex, and the solutions
are usually problem-specific with a series of transformations. To this end,
greedy algorithms are proposed as low-complexity alternatives. In particular,
greedy algorithms refer to the problem-solving heuristic that makes locally
optimal decisions at each stage regardless of global optima[109]. Consider an
minimization problem $\min f(\vec{x})$, and the control variables $\vec{x}$
include $\vec{x}=\\{x_{1},x_{2},...,x_{i},...,X_{I}\\}$. At each stage, the
greedy algorithm will optimize only one control variable $x_{i}$ by
$\hat{x_{i}}=\operatorname*{arg\,min}_{x_{i}\in X_{i}}f(\vec{x})$, while
holding the rest of variables unchanged. Then it moves to the next stage until
$i=I$.

RIS elements’ on/off control is a non-convex problem with discrete
constraints. It may be solved by relaxing the integer constraint
$\chi\in\\{0,1\\}$ into $0\leq\chi\leq 1$, but the reformulated problem can
still be complicated. A low-complexity solution is a greedy element-by-element
control. Specifically, it evaluates the on/off decision of one RIS element at
each stage by observing the changes in objective functions. If the performance
is improved by achieving a higher sum-rate and lower power consumption, then
the on/off status will be updated[54]. Similarly, as shown in Fig. 12, this
greedy scheme can also be applied to control RIS phase shifts, indicating that
one element is optimized at a time by observing the improvement of objective
functions, e.g., achieving higher data rate or energy efficiency. Then, the
next RIS element is optimized sequentially[33, 66, 110].

In addition, greedy algorithms are used to relax the constraints. For example,
the RIS phase shift is allowed to violate the stringent constraints in [111],
then the achieved objective values are compared with the theoretical optimal
results to find a feasible solution. Greedy schemes may be combined with AO to
handle problems with multiple sub-objectives. For instance, a greedy scheme is
applied in [112] to maximize the served users by controlling RIS phase shifts,
then it schedules the users to minimize the age of information. The main
advantage of the greedy algorithm is the low complexity by decoupling the
joint optimization into multiple stages. However, instead of global optima, it
can only achieve local optima. The simple greedy policy means that there is no
guarantee for the algorithm’s performance, which may lead to poor output in
some cases.

Figure 12: Greedy method for RIS phase shift control.

###  V-D Matching Theory-based Methods

The matching theory is useful for optimizing resource allocation problems,
i.e., subcarrier assignment, user-BS and user-RIS association, and mode
selection. These problems are formulated as MINLPs, and a possible solution is
to relax the zero-one constraints and reformulate the problem. A linear conic
relaxation method is proposed in [113] for the user-RIS association, but it
further requires SDP to solve the relaxed formulation, leading to high
computational complexity. In addition, the problem becomes even more
complicated when RIS on/off control and phase shifts are involved.
Consequently, the primary motivation for applying matching theory is to
achieve low-complexity solutions efficiently.

Consider the most widely applied many-to-one matching problem with two finite
and disjoint sets of players $\mathcal{U}$ and $\mathcal{B}$. $\mathcal{U}$
represents users, and $\mathcal{B}$ may be BS, RIS or subchannels.

######  Definition 1.

The considered many-to-one matching problem is defined by
(a) Matching relationship function $f:=\mathcal{U}\times\mathcal{B}$ with
$u\in\mathcal{U}$ and $b\in\mathcal{B}$, e.g., the many-to-one association
relationship between multiple users and one BS;
(b) $|f(u)|=1$ with $\forall u\in\mathcal{U}$, indicating that one $u$ can
only be matched with at most one $b$ in many-to-one matching problem, e.g.,
one user can be associated with at most one BS.
(c) $|f^{-1}(b)|\geq K$ with $\forall b\in\mathcal{B}$, which means that $b$
has a capacity limit for the connection with $u$. For example, one BS has a
maximum service capability for users.
(d) $b=f(u)$ $\leftrightarrow$ $u=f^{-1}(b)$. This means the matching is
bidirectional and mutual.

To describe the exchange operation between different matching, the swap
matching is considered

######  Definition 2.

Given $u\in f^{-1}(b)$ and $u^{\prime}\in f^{-1}(b^{\prime})$ with
$u,u^{\prime}\in\mathcal{U}$ and $b,b^{\prime}\in\mathcal{B}$, the swap
matching is defined by
$f_{u,b,u^{\prime},b^{\prime}}=\\{f\backslash\\{(u,b)(u^{\prime},b^{\prime})\\}\\}\cup\\{(u,b^{\prime})(u^{\prime},b)\\}$.

Swap matching allows $u$ and $u^{\prime}$ to exchange their matched $b$ and
$b^{\prime}$, while other players remain unchanged. For instance, two users
can exchange their associated BSs without changing other association pairs.

######  Definition 3.

$u$ and $u^{\prime}$ become a swap blocking pair if and only if
(a) For all players in $\\{u,b,u^{\prime},b^{\prime}\\}$,
$F(f_{u,b,u^{\prime},b^{\prime}})\geq F(f)$, where $F$ is the utility function
of players. This means that the utility functions of all involved players will
not decrease.
(b) At least one player in $\\{u,b,u^{\prime},b^{\prime}\\}$ has
$F(f_{u,b,u^{\prime},b^{\prime}})>$ $F(f)$, indicating that at least one
player’s utility is improved, e.g., at least one user achieves higher channel
capacity or data rate by switching pairs.

Definition 3 shows that the overall utility can be improved by finding swap
matching pairs. Then the stable matching is defined by

######  Definition 4.

The matching relationship between two sets $\mathcal{U}$ and $\mathcal{B}$ is
two-sided exchange-stable if there is no swap blocking pairs. This means that
the overall utility such as channel capacity or sum-rate cannot be improved by
switching user-BS associations.

TABLE X: Summary of heuristic algorithms for RIS-aided wireless networks

Methods |  Main features |  Advantage |  Drawbacks |  Difficulties |  Application scenarios
---|---|---|---|---|---
CCP |  CCP aims to obtain local optima of DC problems by iteratively finding points with the same tangent values. |  CCP algorithm does not require a dedicated step size design, and it retains all of the information from the convex component and only linearizes the concave portion. |  The selection of initial points may affect the final results, and hence it requires an initialization method. |  The problem has to be reformulated into the DC form; initial points may need to be selected several times due to local optima. |  Penalty CPP is used for imperfect CSI in [42], and statistical CSI in [30]. Other applications include non-convex RIS control problems in [35, 78, 106].
Meta-heuristic algorithms |  Meta-heuristic algorithms apply intelligent policies to guide the heuristic exploration iteratively, producing high-quality solutions efficiently. |  Meta-heuristic algorithms can search huge solution spaces with few or no additional assumptions. |  It can be trapped in local optima, and these algorithms require many iterations. The algorithm performance is sensitive to parameter selections. |  Selecting the best parameters is complicated in meta-heuristic algorithms. For instance, crossover probability in GA and inertia weight in PSO may decide the algorithm performance. |  Meta-heuristic algorithms are mainly deployed for RIS phase-shift control, including GA for rate maximization in [65], PSO for phase-shift optimization in [31, 32], tabu search for irregular RIS in [20].
Greedy algorithms |  Instead of global optima, greedy algorithms make locally optimal decisions at each stage of solving the problem. |  Greedy algorithms can greatly reduce the complexity by decoupling the original problem into multiple stages. |  It may present poor global performance, since the local optima in one stage may lead to bad results for the next stage. |  Finding the trade-off between low complexity and good algorithm performance is critical to using the greedy heuristic. |  Greedy algorithms are used for RIS phase control in [33, 66, 110] and on/off control in [54] as low-complexity solutions, providing low-complexity alternative solutions for NP-hard problems.
Matching theory-based method |  Matching-based method is designed to solve matching or association problems with two sides of players. |  Compared with direct optimization methods, matching-based methods have lower complexity for large-scale problems. |  Matching-based method may require exhaustive searches to find matching pairs. |  Defining the utility function for two sides of players with peer effects is difficult. |  Matching theory is mainly applied to resource allocation and association problems in RIS-aided networks, e.g., channel assignment and user-BS-RIS association[80, 81].

Figure 13: Matching theory applications in RIS-aided wireless networks.

Definition 4 is very useful in matching theory, since it provides locally
optimal criteria, and it is easily achieved by searching and eliminating all
the swap blocking pairs. Fig. 13 presents the applications of matching theory
in RIS-aided wireless networks, including D2D-user pairing, user-BS-RIS
association, channel assignment, etc. It shows that matching theory provides
an efficient solution for overcoming these NP-hard problems. For instance, a
RIS-aided maritime communication system is investigated in [49], in which
many-to-one matching was applied for the joint mode selection and power
control of BSs. In RIS-assisted NOMA system, many-to-one matching is used for
channel assignment [80, 81] and user clustering [56], while many-to-one and
many-to-many matching are jointly considered in [34] for the UE association
and channel assignment. Moreover, matching theory is applied in [114] for edge
computation offloading in RIS-aided networks, and a deferred acceptance
matching game is formulated in [115] for user association in mmWave networks
with RISs. The simulations in [49, 80, 81, 56, 34, 114, 115] demonstrate that
matching theory is a low-complexity solution for resource allocation and
association problems in RIS-aided communication systems. However, matching
theory relies on iterative searching to eliminate swap blocking pairs, and the
searching cost may increase exponentially with more players. In addition, the
wireless network players will affect each other, changing the overall
interference level. Such peer effects may increase the complexity of applying
matching theory.

(a) Sum-rate comparison under various numbers of RIS elements. The greedy
algorithm applies element-by-element RIS phase-shift control. It decides the
phase-shift of one element at each time by observing the improvement in sum-
rate, and then moves to the next element. The genetic algorithm considers
different phase shift designs as individuals, and uses evolutionary strategies
to find near-optimal solutions.

(b) Convergence performance of the genetic algorithm

Figure 14: Simulation results of greedy and genetic algorithms. We consider a
MISO system with one BS and multiple UEs, and detailed simulation parameters
and algorithms can be found in [116]

.

###  V-E Discussions and Numerical Results

Table X compares heuristic algorithms in terms of main features, advantages,
drawbacks, difficulties, and applications. Compared with model-based
algorithms, a common advantage of heuristic algorithms is their low
complexity.

RIS-related optimization problems may involve summation, logarithm, fractional
terms, and discrete constraints in problem formulations, which are non-convex
and highly non-linear. Applying model-based algorithms generally require a
series of transformation and relaxation to achieve a convex or a concave
reformulation, but this complexity is avoided in heuristic algorithms. For
instance, many problems are easily converted into DC forms, and the CCP
algorithm can be applied by iteratively finding two points with the same
tangent vectors. Compared with other estimation-based methods such as MM or
SCA, the CCP method has much lower complexity, since no extra surrogate
function is required. However, the initial point selection may affect the
solution quality of the CCP algorithm.

Greedy algorithms employ a simple greedy policy for decision-making. They aim
to maximize the current benefit, disregarding the effect on future stages.
Greedy algorithms can efficiently solve problems in near-linear time
complexity. However, greedy algorithms can only generate locally optimal
results, and the increasing number of control variables may lead to poor
performance.

By contrast, meta-heuristic algorithms apply more advanced heuristic rules for
iterative exploration, e.g., genetic algorithm, tabu search, and PSO. Similar
to greedy algorithms, meta-heuristic algorithms have no requirements for
problem formulations and constraints, and objective functions can be easily
converted into fitness functions. However, compared with greedy algorithms,
meta-heuristic algorithms can better guarantee the solution quality by using
heuristic rules for iterative optimization.

Different from previous approaches, matching theory specializes in solving
resource allocation and association problems. In matching-based methods, the
control variables are considered as matching operations, and the objective
function is improved by searching swap matching pairs. Therefore, when
handling these allocation problems, matching theory is more efficient than
other heuristic algorithms due to its dedicated design.

Note that heuristic algorithms may be combined with model-based algorithms.
For instance, the energy-efficiency maximization problem in [54] is decoupled
into the beamforming optimization, phase control, and RIS on/off optimization,
in which beamforming and phase control are solved by SCA, and RIS on/off is
optimized by the greedy algorithm. Other combinations can be found in [66] by
combining SDR with greedy heuristic, and in [34] by combining SCA and SDR with
matching methods.

Finally, Fig. 14(b) shows an example with greedy and genetic algorithms. In
particular, the greedy algorithm applies element-by-element RIS phase-shift
control. It decides the phase-shift of one element at each time by observing
the improvement in sum-rate, and then moves to the next element. Meanwhile,
genetic algorithm considers different phase shift combinations as individuals,
and uses evolutionary strategies to find near-optimal solutions. Fig. 14(a)
provides the sum-rate under various numbers of RIS elements. It shows that
heuristic algorithms can achieve satisfactory performance with a limited
number of RIS elements. However, when the number of RIS elements increases,
both greedy and genetic algorithms present sub-optimal results. In addition,
Fig. 14(b) illustrates the convergence performance of the genetic algorithm.
It shows that the average values of individuals increase with iterations, and
finally the optimal objective value converges. The main reason is that the
genetic algorithm applies evolutionary policies, which will select elite
individuals to produce new solutions, and therefore the solution quality is
constantly improved.

##  VI ML-enabled Optimization for RIS-aided Wireless Networks

ML has achieved great success in various fields, and this section investigates
ML applications for the control and optimization of RIS-aided wireless
networks, including supervised learning, unsupervised learning, RL, FL, graph
learning, transfer learning, hierarchical learning, and meta-learning.

A variety of algorithms have been developed to optimize RIS-aided wireless
networks. Early studies mainly considered model-based methods, and some
heuristic algorithms are deployed as low-complexity solutions. However, there
are several challenges for these conventional optimization techniques:

1) Highly dynamic wireless environment: Wireless networks are highly dynamic
due to frequently changing channel conditions, traffic demands, and user
conditions. These dynamics lead to great difficulty for conventional
optimization schemes. As an example, model-based methods need full knowledge
of the formulated problem, but some sensitive information, e.g., real-time
user locations, may be unknown in practice.

2) Evolving network architecture: The wireless network architecture is
constantly evolving from RAN to cloud RAN, virtual RAN, and Open RAN.
Consequently, these new architectures increase the complexity of network
management, and conventional algorithms may have difficulty modelling and
optimizing such complicated systems.

3) Diverse user requirements: Wireless network user types are not limited to
enhanced Mobile Broad Band, Ultra Reliable Low Latency Communications, and
massive Machine Type Communications. Some newly emerged applications, such as
virtual and augmented reality, have more stringent requirements on network
metrics, leading to a great burden for conventional optimization methods.

Given these challenges, ML-enabled control and optimization techniques have
become appealing approaches for wireless communications in general, as well as
for RIS-aided wireless networks. In the following, we will introduce the
fundamentals and applications of various ML techniques. It is worth noting
that ML algorithms can be applied to optimize RIS-aided networks in various
ways, e.g., controlling RIS elements directly or jointly optimizing the whole
RIS-aided network scenario. Here we focus on the application of using ML
algorithms to optimize RIS elements directly, e.g., supervised learning-based
sum-rate prediction, unsupervised learning-enabled RIS phase-shift
optimization, RL-enabled RIS phase-shift control, and so on.

TABLE XI: Summary of supervised learning for RIS-aided wireless networks

Ref. |  Scenario |  Phase-shift resolution |  Channel settings |  CSI |  Objectives |  Model |  Layer |  Data acquisition |  Input data |  Output data
---|---|---|---|---|---|---|---|---|---|---
[117] |  Point-to-point SISO |  Discrete |  DeepMIMO dataset |  Predicted |  Maximizing data rate |  CNN |  9 Conv2D layers |  Collected from fully active model |  Estimated partial channels |  Full channel information
|  |  |  |  |  |  FNN |  5 Layers |  Codebook |  CSI |  RIS phase shifts
[118] |  Rich-scattering Point-to-point |  Binary |  Generated by simulator |  Predicted |  Maximizing data rate |  DNN |  4 layers |  Obtained from simulators |  RIS phases |  Second-order moments of CSI.
[119] |  Point-to-point SISO |  Continuous |  Wideband geometric |  Partially |  Maximizing data rate |  DNN |  6 layers |  Exhaustive generation |  CSI |  Estimated data rate
[120] |  Point-to-point SISO |  Continuous |  Wideband geometric |  Perfect |  Maximizing data rate |  DNN |  5 layers |  Exhaustive search beamforming |  Pilot signals |  RIS phase shifts
[121] |  Point-to-point SISO |  Discrete |  Rician fading |  Perfect |  Maximizing data rate |  DNN |  5 layers |  Simulation generated |  Transmit power, and positions |  RIS phase shifts
[122] |  MISO-DL-SU |  Continuous |  Quasi-static flat-fading |  Estimated |  Maximize energy efficiency |  DNN |  5 layers; 6 layers |  Separately generated |  Pilot signal |  RIS phase shifts and BS beamforming vector
[17] |  MISO-DL-SU |  Continuous |  Rayleigh fading |  Perfect |  Maximizing data rate |  DNN |  5 layers |  Generated by estimation |  User positions |  RIS phase shifts
[123] |  SISO-UL-MU |  Continuous |  Quasi-static |  Perfect |  Maximizing SINR |  CNN |  5 layers |  Collected using by USRP2 testbed |  Incident RF signal |  Interfering user set
[124] |  MISO-DL-MU |  Continuous |  Rician fading |  Perfect |  Maximizing secrecy rate |  DNN |  6 layers |  Generated by AO algorithm |  Channel coefficients |  RIS phase shifts
[125] |  MISO-DL-MU MEC |  Continuous |  Rician fading |  Predicted |  Maximizing data rate |  DNN |  7 layers |  Generated by BCD algorithm |  CSI |  RIS phase shifts; offloading decision
|  |  |  |  |  |  DNN |  7 layers |  |  UE positions |

Figure 15: Supervised learning for RIS-aided wireless networks.

###  VI-A Supervised Learning-enabled Optimization

Supervised learning is designed to find the hidden relationships between
inputs and labeled outputs. Supervised learning algorithms adjust their
parameters to map the input to the expected output, and this relationship is
used for the prediction and classification of unseen data. Table XI summarizes
supervised learning-based control and optimization studies for RIS-aided
wireless networks. It shows that most studies consider partial CSI or pilot
signals as input to predict full CSI or RIS phase shifts, and then utilize the
prediction results to maximize the data rate. Meanwhile, there are various
approaches for neural network model selection, dataset acquisition, input and
output data definitions, etc. This subsection will discuss how to apply
supervised learning for optimizing RIS-aided wireless networks, including data
acquisition, neural network architecture, loss functions and algorithm
training.

####  VI-A1 Dataset Acquisition in RIS-aided Environments

A fine-grained dataset is the prerequisite for deploying supervised learning,
since it relies on the labeled output for validation. Table XI indicates that
the dataset is generated in various ways: simulators, exhaustive searches,
codebook, model-based optimization algorithms or live networks. For example,
the exhaustive searches mean trying different solutions and then collecting
the corresponding output to form labeled datasets[119][120]. By contrast, a
more efficient method is to reuse the data produced by AO[124] and BCD[125] as
model-based optimization algorithms.

In addition, the algorithm performance also depends on the dataset size,
ranging from 5000 [121] and 30000[120, 119] to 200000 [125] in several
studies. The simulation results in [120, 119] demonstrate that the achievable
data rate is significantly improved when the number of training samples
increases from 5000 to 30000. Note that the complex entry of the input data,
especially the channel coefficient, is usually split into real and imaginary
parts, increasing the dimension of the neural network input. Although there
are several ways to generate the data for supervised learning, most existing
datasets are simulation-based. Realistic datasets that are produced in real-
world RIS-aided environments are still very rare.

####  VI-A2 Loss Functions and Algorithm Training

Given the huge number of training samples, supervised learning models are
trained to produce the expected output. Suppose that the prediction output is
the RIS phase shifts [117, 120, 121], and the loss function is defined to
minimize the mean square error (MSE) of algorithm training

$Loss(\omega)=\frac{1}{N}\sum^{N}_{i=1}(\theta_{i}-\hat{\theta}_{i}(\omega))^{2},$
(26)

where $N$ is the total number of outputs, i.e., the number of RIS elements,
$\theta_{i}$ is the desired phase shift given by the dataset, $\omega$ is the
neural network weight, and $\hat{\theta}_{i}(w)$ indicates the RIS phase
shifts predicted by neural networks. The desired phase shift $\theta_{i}$ can
be obtained in various ways, such as exhaustive search or model-based
approaches[119, 124], which have been introduced in Section VI-A1. For
example, Song et al. apply AO to produce a dataset with desired targets for
DNN training[124], and Hu et al. apply BCD algorithm to generate target phase
shift to train DNN models[125]. Meanwhile, note that the dataset must be
divided into training and validation samples, since the objective of algorithm
training is to predict unseen data. For example, the authors in [124] include
10000 samples to predict the RIS phase shifts, of which 90% is used for
training and the remaining 10% for testing purposes.

####  VI-A3 Neural Network Architecture and Overfitting

Table XI shows that DNN is used in most studies to predict CSI or RIS phase
shifts, and the network architecture ranges from 4 to 9 layers. It is known
that more hidden layers may provide a better performance, but the
computational complexity and training time will increase. Hence, the network
architecture selection should consider the trade-off between performance and
training costs.

Overfitting is another important issue for neural network training. It means
that the algorithm fits exactly to the current training data, but cannot
achieve satisfactory prediction for unseen data, which should be carefully
prevented. One solution is to add a random dropout layer with probabilities,
ignoring the contribution of some neurons [125]. Multiple methods are provided
by [124] to suppress overfitting in predicting RIS phase shifts, including
larger datasets (CSI and RIS phase shift pairs), decreasing hidden layers, and
early stopping.

Fig. 15 summarizes how to apply supervised learning for RIS-aided wireless
networks. Firstly, the datasets can be produced by various methods, including
simulators, exhaustive searches, testbed, and model-based methods. The
collected dataset may include UE positions, data rates, and pilot signals
received at the transmitter and receiver, which mainly depends on the designed
prediction algorithms. Then, one specific model will be selected, i.e., FNN,
convolutional neural networks (CNNs), and recurrent neural networks (RNNs).
Note that each neural network model has unique features and advantages, e.g.,
RNNs are suitable for handling sequential data, and CNNs can better handle
spatial data. The selection of neural network models requires case-by-case
analyses of the dataset size, quality, and data-processing demands. The number
of nodes and hidden layers of neural networks should be carefully designed,
which will affect the network training time and accuracy. Finally, selected
models are trained and implemented, and the algorithm output includes RIS
phase shifts, achieved data rate, BS beamforming vectors and so on, which are
further used to optimize network performance. Supervised learning has been
widely used for wireless networks. However, note that it relies on high-
quality labeled datasets for model training, which may be inaccessible in
practice. In addition, the algorithm performance is sensitive to
hyperparameters, and the fine-tuning of parameters requires considerable
experience.

TABLE XII: Summary of unsupervised learning for RIS-aided wireless networks

Ref. |  Scenario |  Phase-shift resolution |  Channel settings |  CSI |  Objectives |  Model |  Layer |  Data generation |  Input data |  Output data
---|---|---|---|---|---|---|---|---|---|---