Senior Member, IEEE Davide Dardari

Fellow, IEEE Marco Di Renzo

Intelligent Reflecting Surfaces: Sum-Rate Optimization Based on Statistical CSI

Keywords: Intelligent reflecting surfaces, statisticsl CSI, MU-MIMO, sum-rate

In this paper, we consider a multi-user multiple-input multiple-output (MIMO) system aided by multiple intelligent reflecting surfaces (IRSs) that are deployed to increase the coverage and, possibly, the rank of the channel. We propose an optimization algorithm to configure the IRSs, which is aimed at maximizing the network sum-rate by exploiting only the statistical characterization of the environment, such as the distribution of the locations of the users and the distribution of the multipath channels.

As a consequence, the proposed approach does not require the estimation of the instantaneous channel state information (CSI) for system optimization, thus significantly relaxing (or even avoiding) the need of frequently reconfiguring the IRSs, which constitutes one of the most critical issues in IRS-assisted systems. Numerical results confirm the validity of the proposed approach. It is shown, in particular, that IRS-assisted wireless systems that are optimized based on statistical CSI still provide large performance gains as compared to the baseline scenarios in which no IRSs are deployed.

I. INTRODUCTION

The path towards sixth generation (6G) wireless networks foresees the use of new frequency bands such as the terahertz (THz) spectrum, as well as the development of new transmission technologies in order to comply with the challenging requirements introduced by new mobile applications [START_REF] David | 6G vision and requirements: Is there any need for beyond 5G?[END_REF]- [START_REF] Rappaport | Wireless communications and applications above 100 GHz: Opportunities and challenges for 6G and beyond[END_REF]. Among several promising transmission technologies, one technology that has recently received a significant attention is the intelligent reflecting surface (IRS) [START_REF] Liaskos | A new wireless communication paradigm through software-controlled metasurfaces[END_REF]. An IRS can be broadly defined as a man-made thin surface, which can be realized by using Manuscript received Dec. [START_REF] Hu | Beyond massive MIMO: The potential of data transmission with large intelligent surfaces[END_REF]2020. A. Abrardo is the Univerity of Siena and CNIT, Italy (e-mail: abrardo@dii.unisi.it). D.

Dardari is with the University of Bologna and CNIT, Italy (e-mail: davide.dardari@unibo.it). M. Di Renzo is with CNRS and Paris-Saclay University, France (e-mail: marco.di-renzo@universite-paris-saclay.fr).

inexpensive antenna elements or metamaterials, whose properties provide great flexibility on how the electromagnetic (EM) waves that impinge upon the surface are reflected, refracted, focused, etc. [START_REF] Asadchy | Perfect control of reflection and refraction using spatially dispersive metasurfaces[END_REF]- [START_REF] Buriak | Metamaterials: Theory, classification and application strategies (review)[END_REF]. The most recent research activities on IRS are concerned with the design of nearly passive reconfigurable planar structures, i.e., surfaces, whose surface impedance can be appropriately configured according to specified communication needs [START_REF] Holloway | Reflection and transmission properties of a metafilm: with an application to a controllable surface composed of resonant particles[END_REF]- [START_REF] Dai | Reconfigurable intelligent surface-based wireless communication: Antenna design, prototyping and experimental results[END_REF]. These solutions are referred to as reconfigurable intelligent surfaces (RISs), and are capable of realizing multiple wave transformations (not only anomalous reflection, refraction, or focusing) [START_REF] Renzo | Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and road ahead[END_REF].

IRSs have several applications, and, in particular, they are useful for enhancing the coverage in severe non-line-of-sight (NLOS) channel conditions by acting as intelligent mirrors [START_REF] Di Renzo | Analytical modeling of the path-loss for reconfigurable intelligent surfaces -Anomalous mirror or scatterer ?[END_REF]. More in general, IRSs are viewed as a technology enabler for realizing the so-called smart radio environment, i.e., a wireless system in which the environment (e.g., the channel) becomes a variable that can be optimized in addition to the parameters of the communication devices [START_REF] Renzo | Smart radio environments empowered by reconfigurable AI meta-surfaces: an idea whose time has come[END_REF].

For instance, an IRS can be programmed to create "artificial" multipath in such a way that the channel rank, and so the channel capacity, in multiple-input multiple-output (MIMO)-aided systems is increased [START_REF] Özdogan | Intelligent reflecting surfaces: Physics, propagation, and pathloss modeling[END_REF], [START_REF] Dardari | Communicating with large intelligent surfaces: Fundamental limits and models[END_REF]. In the presence of multiple users, IRSs can be optimized to maximize the signal-to-interference-noise ratio (SINR) or the achievable rate (AR) [START_REF] Hu | Beyond massive MIMO: The potential of data transmission with large intelligent surfaces[END_REF].

One of the main design and implementation challenges of IRS-assisted communication systems is the need of estimating the channel state information (CSI) of the transmitter-IRS and IRSreceiver channels, and the need of appropriately configuring (virtually in real-time) the operation of the IRS via a feedback channel. As recently shown in [START_REF] Zappone | Overhead-aware design of reconfigurable intelligent surfaces in smart radio environments[END_REF], the overhead associated with the channel estimation and reporting phases through a feedback channel may offset the performance gains introduced by an IRS, if the number of individually reconfigurable elements is too large and/or an inefficient channel estimation algorithm is employed. Furthermore, due to the dynamic behavior of the wireless channel and the mobility of the users, an IRS needs to have the capability of re-configuring itself at a time-scale that depends on the coherence time of the environment (e.g., the channel), which may be difficult to realize in some highly dynamic environments [START_REF] Wu | Intelligent reflecting surface aided wireless communications: A tutorial[END_REF].

Motivated by these considerations, there is general a consensus that it is imperative to develop low-overhead IRS-assisted systems, which are designed and optimized without relying on the perfect knowledge of the CSI, while still providing performance gains with respect to legacy wireless networks in the absence of IRSs. The present paper tackles this open research issue, by proposing a joint offline and online optimization design for IRS-assisted communication systems. In the next two sub-sections, we first review the research works related to ours and then summarize the main contributions and novelty of the proposed approach.

A. State of the art

A comprehensive state of the art review on IRS-assisted systems can be found in [START_REF] Renzo | Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and road ahead[END_REF], [START_REF] Wu | Intelligent reflecting surface aided wireless communications: A tutorial[END_REF], [START_REF] Liu | Reconfigurable intelligent surfaces: Principles and opportunities[END_REF]. The present paper is focused on optimizing IRSs under the assumption that the perfect knowledge of the CSI is not available. In this section, therefore, we discuss only research works that are closely related to this main focus of the paper. Interested readers are referred to [START_REF] Renzo | Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and road ahead[END_REF]Sec. V-J], [21, Table III] and [14, Sec. V-G], [START_REF] Wu | Intelligent reflecting surface aided wireless communications: A tutorial[END_REF]Table V] for a detailed summary of the available research results on resource allocation and optimization, and channel estimation, respectively.

Based on the analysis of the state of the art (see, e.g., [21, Table III]), we evince that the vast majority of research works focused on optimizing the performance of IRS-assisted systems are based on the perfect knowledge of the CSI for all the available channels, as well as on the availability of appropriate feedback mechanisms to configure the operation of the IRSs based on the acquired CSI. This may make the channel estimation and signaling (feedback) overhead prohibitively high, especially in multi-user MIMO (MU-MIMO) systems [START_REF] Zappone | Overhead-aware design of reconfigurable intelligent surfaces in smart radio environments[END_REF]. More precisely, several channel estimation schemes have been proposed for different system configurations (single/multiple users, single/multiple antennas), as recently surveyed in [14, Sec. V-G]. The common denominator of most of the available schemes is to let the IRSs change the analog beamforming vectors during the channel estimation phase according to pre-designed reflection patterns that are exploited and appropriately optimized to facilitate and to make robust the channel estimation process. In spite of the relatively large number of research contributions available to date, the channel estimation in IRS-aided systems is still an open issue that is characterized by three major challenges: (i) the long training time, especially in MU-MIMO systems, which may not be tolerable in dynamic scenarios; (ii) the real-time reconfiguration of the reflection functionality of the IRS through a dedicated control channel with the base station (BS); and

(iii) the need of ad hoc channel estimation and signaling protocols that make the deployment of IRSs non-transparent to existing communication protocols. In order to tackle these open research issues, some authors have recently started researching on IRS-aided systems that do not necessarily rely upon the perfect knowledge of the CSI, e.g., [START_REF] Nadeem | Asymptotic max-min SINR analysis of reconfigurable intelligent surface assisted miso systems[END_REF], [START_REF] Zhao | Intelligent reflecting surface enhanced wireless network: Two-timescale beamforming optimization[END_REF], [START_REF] Nadeem | Opportunistic beamforming using an intelligent reflecting surface without instantaneous CSI[END_REF], [START_REF] Lin | Reconfigurable intelligent surfaces with reflection pattern modulation: Beamforming design and performance analysis[END_REF], [START_REF] Peng | Analysis and optimization for IRS-aided multi-pair communications relying on statistical csi[END_REF], [START_REF] Dardari | Using metaprisms for performance improvement in wireless communications[END_REF].

In [START_REF] Nadeem | Asymptotic max-min SINR analysis of reconfigurable intelligent surface assisted miso systems[END_REF], the authors formulate an optimization problem for determining the optimal linear precoder, the power allocation matrix at the transmitter, and the phase shifts matrix at the IRS that maximize the minimum SINR of the system. The authors develop a deterministic approximation for the parameters of the optimal linear precoder by using tools from random matrix theory. Based on the obtained deterministic approximations, an algorithm based on the projected gradient ascent method is proposed to solve the non-convex optimization problem for determining the phases that maximize the minimum SINR of the users. The developed algorithm requires the knowledge of only the large-scale channel statistics, including the slowly varying spatial correlation matrices, which can be estimated using the knowledge of only the mean angles and angular spreads, and the channel attenuation coefficients, which change slowly with time. A multiple-input single-output (MISO) downlink multiuser communication system is considered in [START_REF] Zhao | Intelligent reflecting surface enhanced wireless network: Two-timescale beamforming optimization[END_REF], in which the phase shifts of a single IRS and the transmit beamforming/precoding vector at the access point are optimized by relaying on a two-timescale beamforming optimization algorithm. More precisely, the phase shifts applied by the IRS are optimized based on the statistical CSI of all the links, and the transmit beamforming/precoding vectors at the access point are designed by relying on the instantaneous CSI of the effective channels, given the optimized configuration of the IRS.

The authors show that the proposed approach can reduce the channel training overhead and the complexity of the analog beamforming design over existing schemes that need the knowledge of the instantaneous CSI of all the available channels. It is shown that, even though the phase shifts are optimized by using statistical CSI, a significant performance gain in terms of sumrate can be obtained, as compared with systems in the absence of an IRS. The authors of [START_REF] Nadeem | Opportunistic beamforming using an intelligent reflecting surface without instantaneous CSI[END_REF] study an IRS-assisted single-input single-output (SISO) broadcast channel, in which the IRS elements introduce random or deterministic phase rotations without requiring instantaneous CSI.

The average sum-rate capacity of the considered system is achieved by opportunistic scheduling the user with the largest signal-to-noise ratio (SNR). Also, the authors show that the average sum-rate under the proposed scheme in a slow-fading environment is capable of approaching the performance of coherent beamforming as the number of users increases. In [START_REF] Lin | Reconfigurable intelligent surfaces with reflection pattern modulation: Beamforming design and performance analysis[END_REF], the authors propose an IRS-enhanced MISO system with reflection pattern modulation, where the IRS can configure its reflection state for enhancing the received signal power via analog beamforming and simultaneously conveying its own information via reflection modulation. The authors formulate an optimization problem to maximize the average received signal power by jointly optimizing the digital beamforming at the access point and the analog beamforming at the IRS by assuming that the state information at the IRS is statistically known by the access point, and that the CSI is affected by channel estimation errors. A sub-optimal algorithm for solving the resulting optimization problem based on the alternating optimization method is proposed as well. The authors of [START_REF] Peng | Analysis and optimization for IRS-aided multi-pair communications relying on statistical csi[END_REF] investigate an IRS-aided multi-pair communication system, in which multi-pair users exchange information via an IRS. The authors derive an approximated expression of the achievable rate by assuming that only the knowledge of the statistical CSI is available. In [START_REF] Dardari | Using metaprisms for performance improvement in wireless communications[END_REF], finally, the estimation of the local CSI and the need for a dedicated control channel are avoided by exploiting the frequency selectivity of the IRSs. It is shown that, if the IRSs are appropriately designed, different reflection properties can be obtained in an orthogonal frequency division multiplexing (OFDM) context by suitably changing the sub-carriers allocated to each user. The effectiveness of the method is validated in the far-field and near-field regimes.

B. Contribution of the paper

In the present paper, we consider a multi-IRS MU-MIMO system and we optimize the reconfigurable elements of the IRSs and the beamforming vectors at the BS and user equipments (UEs) so as to maximize the system sum-rate. The main novelty of the proposed approach lies in not requiring the instantaneous CSI for optimizing the IRSs, thus relaxing the need for their (real time) configuration. As far as the optimization of the IRSs is concerned, in fact, the proposed approach relies only on the statistical characterization of the environment, such as the distribution of the users' locations and the channel statistics. To this end, a two-phase optimization process is introduced, which encompasses an offline phase (long-term and sporadic) and an online (shortterm and more frequent) phase. During the offline phase, the IRSs are optimized. During the online phase, the BS and the UEs are optimized. The main advantage of the proposed approach is that the statistical CSI can be either known a priori (e.g., one may know that some UEs are confined within a certain area) or can be learned occasionally during the operation of the system.

In the former case, the IRSs need to be optimized once forever during the offline optimization phase, and no dedicated control channel is needed during the communication phase. In the latter case, the IRSs need to be optimized sporadically based on the distribution of the users' locations and the fading channels. In this case, the configuration of the IRS is not kept fixed forever but it is updated at a low rate and requires a low estimation and feedback overhead. As far as the online phase is concerned, on the other hand, the IRS is always kept fixed and is not part of the optimization process. During the online phase, the IRS is viewed as a smart scatterer that generates controlled multipath based on the statistical distribution of the channels and the users' locations. Hence, the IRS is implicitly embedded in the channel, and only the BS and the UEs need to be optimized by using conventional CSI acquisition and beamforming methods [START_REF] Abrardo | Distributed digital and hybrid beamforming schemes with MMSE-SIC receivers for the MIMO interference channel[END_REF].

To substantiate the proposed approach, numerical results are illustrated for analyzing the coverage and channel rank improvement of the system sum-rate as a function of the statistical distribution of the users' locations, as well as the number of UEs and IRS. Monte Carlo simulations show that, even in the presence of moderate a priori knowledge about the scenario, the proposed approach leads to a significant performance improvement when the line-of-sight (LOS) is not available. Moreover, the numerical results indicate that increasing the number of IRSs deployed in the environment, while keeping constant the total surface area, increases the effective rank of the channel and reduces the interference at the UEs. These results make the proposed approach an appealing solution to facilitate the deployment of IRSs in wireless systems.

C. Comparison with the state of the art

Compared with the related research works discussed in Section I-B [START_REF] Nadeem | Asymptotic max-min SINR analysis of reconfigurable intelligent surface assisted miso systems[END_REF]- [START_REF] Dardari | Using metaprisms for performance improvement in wireless communications[END_REF], the most closely related paper to ours is [START_REF] Zhao | Intelligent reflecting surface enhanced wireless network: Two-timescale beamforming optimization[END_REF]. Therein, an IRS-assisted MISO system is considered, in which the beamforming optimization problem is split into a short-term and a long-term optimization phases.

In the first phase, the IRS analog beamforming vector is assumed to be fixed and a conventional weighted minimum mean square error (WMMSE) algorithm is utilized to compute the BS digital beamforming vector with the goal of maximizing the system sum-rate. In the second phase, the IRS analog beamforming vector is optimized with the goal of maximizing the rate averaged with respect to the small-scale fading statistics. These latter statistics, together with the LOS channel coefficients, are estimated during a preceding transmission phase in which the IRS is in sensing mode and pilots and/or data symbols transmitted in the uplink and downlink are exploited for channel estimation. The optimization is performed by leveraging the close relationship between the rate and the SNR in MISO systems, and by exploiting such a relationship to derive the gradient of each user rate with respect to the IRS analog beamforming vector.

In the present paper, on the other hand, we consider a general multi-IRS and MU-MIMO communication system, in which the digital beamforming vectors at the BSs and UEs and the analog beamforming vectors at the IRSs are optimized with the goal of maximizing the average sum-rate. In addition, rather than considering a long-term optimization problem, we consider an offline-based approach in which only mild a priori knowledge on the network scenario is available. More specifically, we assume the a priori knowledge of only the statistical distribution of the users' locations in a given service area. This allows us to get rid of estimating the exact LOS channel coefficients. Accordingly, the IRSs can be assumed to be nearly-passive and do not need to be equipped with any ad hoc circuits (or sensors) for estimating the CSI.

As far as the calculation of the average sum-rate is concerned, similar to [START_REF] Zhao | Intelligent reflecting surface enhanced wireless network: Two-timescale beamforming optimization[END_REF], we resort to a Monte Carlo generation method for the channels. However, we include the generation of the users' locations as well. By capitalizing on the proposed approach, in the extreme case in which the network is static as a function of the users' locations and channel statistics, the IRSs need to be optimized only once during the offline phase. In this case, the IRSs act as passive repeaters.

As far as the optimization algorithm is concerned, we provide new contributions for the online and offline optimization phases. As for the online phase, we introduce a generalized version of the WMMSE algorithm for application to MU-MIMO systems. As for the offline phase, owing to the more involved expression of the per-user rate of MIMO systems with respect to MISO systems, we further generalize the WMMSE method for optimizing the analog beamforming vectors of the IRSs. It is worth noting that the WMMSE algorithm was recently used for optimizing IRSs [START_REF] Pan | Intelligent reflecting surface aided MIMO broadcasting for simultaneous wireless information and power transfer[END_REF]. Therein, however, the optimization is performed for a given instance of the channel (the instantaneous CSI is needed) and a single IRS is considered.

Finally, we emphasize that the terms offline and online optimization were recently used in [START_REF] Najafi | Physics-based Modeling and Scalable Optimization of Large Intelligent Reflecting Surfaces[END_REF].

Therein, however, the problem formulation and proposed approach are fundamentally different compared with ours. In [START_REF] Najafi | Physics-based Modeling and Scalable Optimization of Large Intelligent Reflecting Surfaces[END_REF], for example, during the online optimization phase, all the effective end-to-end channels between the transmitter and the user via each tile of the IRSs are needed. This does not apply to the proposed algorithm, since the individual knowledge of these channels is not necessary. Similar to [START_REF] Najafi | Physics-based Modeling and Scalable Optimization of Large Intelligent Reflecting Surfaces[END_REF], however, our proposed approach can be applied to IRSs that are made of multiple tiles, which is useful for reducing the optimization complexity.

D. Organization of the paper

This paper is structured as follows. In Section, II the channel and IRS physical models are introduced. In Section III, the offline and online IRS optimization problems are described and tackled. Numerical results referred to a typical indoor scenario are described in Section IV.

Finally, concluding remarks are given in Section V.

II. DIRECT AND IRS-ASSISTED CHANNEL MODELS

We consider the downlink of a wireless system in which one BS equipped with antennas serves UEs that comprise antennas each. In this network scenario, IRSs are deployed in some predefined locations for assisting the communication between the BS and the UEs. Each IRS comprises nearly-passive reconfigurable scattering elements. In this setting, each IRS can be conveniently partitioned into smaller tiles in order to reduce the design complexity (e.g., see [START_REF] Najafi | Physics-based Modeling and Scalable Optimization of Large Intelligent Reflecting Surfaces[END_REF]). In this case, the number of equivalent IRSs is = × , each comprising = / scattering elements. In the following, for ease of notation, we employ the notation and regardless of whether the IRSs are partitioned in tiles or not.

The objective of this section is to introduce the BS-UE and BS-IRS-UE channel models. For ease of writing, we formulate the channel models for a single UE.

A. Channel model for the direct link (BS-UE channel)

We consider a non-stationary narrow-band clustered channel model, typically used for application to millimeter wave (mmWave) communications [START_REF] Wu | A non-stationary wideband channel model for massive MIMO communication systems[END_REF], which accounts for the near-field and far-field effects of the EM propagation in the presence of large antenna arrays. We denote by 0 the center frequency of the EM signal and by the corresponding wavelength. The channel is composed of a LOS component and a NLOS component that comprises a number of clustered paths, each corresponding to a macro-level scattering path. In particular, we assume that the center of each cluster c of multipath is located on an ellipse whose foci coincide with the antennas of the BS and UE. For simplicity, we assume that c are all located on the same ellipse. By denoting with t and r the center of the antenna arrays of the BS and UE, respectively, we have, by definition of ellipse, ct + cr = |t -r| / , ∀ , being the ellipse eccentricity.

Each cluster consists of a number of paths, and each path is represented by a point, which is denoted by p , that is randomly placed within a maximum (small) distance from the center of the cluster c . Accordingly, all the paths of a given cluster reach the receiver within a limited angular spread, in agreement with typical mmWave channels. In mathematical terms, the channel complex gain can be formulated as

ℎ = (LOS) exp - 2 |t -r | + (NLOS) =1 =1 exp -2 t -p + r -p (1)
where t denotes the position of the th antenna-element of the BS, r denotes the position of the th antenna-element of the UE, (LOS) = √ T R 4 |t -r | denotes the path-loss gain of the LOS, T denotes the antenna-element gain at the BS, R denotes the antenna-element gain at the UE, denotes the number of clusters, denotes the number of paths of each cluster, ∼ CN (0, 1) denotes the random complex fading coefficient of the th path of the th cluster, and (NLOS) denotes the path-loss gain of the channel in NLOS. According to [START_REF]5G channel model for bands up to 100 GHz[END_REF], we have (NLOS) (dB) = -PL 0 -10 log 10 , where PL 0 denotes the path-loss (in dB) at the reference distance of one meter, denotes the distance between the center of the antenna-array of the BS (t) and the center of the antenna-array of the UE (r), and denotes the path-loss exponent.

In particular, we consider the ABG channel model for the indoor office (IO) and the shopping mall (SM) NLOS scenairos at 28 GHz [START_REF]5G channel model for bands up to 100 GHz[END_REF]. The main difference between the two scenarios is given by the path-loss exponents, which are equal to 3.83 and 3.21 for the IO and SM cases, respectively. Finally, the binary variable allows us to model whether the LOS is present ( = 1) or is obstructed ( = 0).

B. Reflection model for the IRS

We consider an IRS that comprises small unit cells (scattering elements), which are spaced /2 apart and whose area is c . We consider a locally-plane (with respect to the size of each unit cell) 1 incident wave, whose angle of incidence with respect to the IRS is

Θ inc = ( inc , inc ),
with inc ∈ [0, 2 ) and inc ∈ [0, ) denoting the azimuth and elevation angles, respectively.

The local reflection coefficient of the th unit cell towards the generic direction of scattering Θ = ( , ) is modeled as

(Θ inc , Θ) = (Θ inc ) (Θ) c (2)
where (Θ) denotes the normalized power radiation pattern of each unit cell, which accounts for the possible non-isotropic behavior of each scattering element. As a first approximation, we assume that (Θ) is frequency-independent within the bandwidth of interest. Also, c denotes the boresight gain of the unit cell, and = exp( ) denotes the load reflection coefficient, with = | | and being the amplitude and the phase shift introduced by the th unit cell, respectively. 2 For analytical convenience, we collect the load reflection coefficients = exp(

) in the vector b = [ 1 , 2 , . . . , ].
It is worth mentioning that, especially for large 1 The wave is assumed to be plane with respect to the area c , but it is spherical with respect to the size of the IRS. 2 Depending on the specific implementation, the load reflection coefficient may have a different physical meaning [START_REF] Gradoni | End-to-end mutual coupling aware communication model for reconfigurable intelligent surfaces: An electromagnetic-compliant approach based on mutual impedances[END_REF].

IRSs, the angle of incidence Θ inc can be different for each unit cell. Without loss of generality, the boresight gain is defined as c = c 4 / 2 . In addition, a quite general model for (Θ) is

(Θ) =        cos ( ) ∈ [0, /2] , ∈ [0, 2 ] 0 otherwise (3)
which is compliant with the models used in, e.g., [START_REF] Özdogan | Intelligent reflecting surfaces: Physics, propagation, and pathloss modeling[END_REF], [START_REF] Ellingson | Path Loss in Reconfigurable Intelligent Surface-Enabled Channels[END_REF], [START_REF] Tang | Wireless communications with reconfigurable intelligent surface: Path loss modeling and experimental measurement[END_REF] for different values of the parameter , and with the model recently derived in [START_REF] Najafi | Physics-based Modeling and Scalable Optimization of Large Intelligent Reflecting Surfaces[END_REF], which originates from the radar crosssection of small reflecting tiles. In the numerical results, without loss of generality, the following parameters are considered: = 0.57, c = 2 4 [START_REF] Dardari | Using metaprisms for performance improvement in wireless communications[END_REF], [START_REF] Ellingson | Path Loss in Reconfigurable Intelligent Surface-Enabled Channels[END_REF].

C. Channel model for the indirect link (BS-IRS-UE channel)

In IRS-assisted communications, the near-field effects cannot be ignored if the size of the IRS is large and the transmission distances are short [START_REF] Danufane | On the path-loss of reconfigurable intelligent surfaces: An approach based on Green's theorem applied to vector fields[END_REF]. In this case, the plane wave approximation is not fulfilled anymore, and spherical waves need to be considered. Thus, the channel is nonstationary along the IRS. This implies that the angles of incidence and scattering are not sufficient to characterize the global response of the IRS, and the different transmission distances between the unit cells of the IRS and the antennas of the BS and UEs need to be taken into account.

In general, the IRSs are strategically deployed in order to ensure that they are in LOS with the BS and the UEs. In addition, they are more useful when the BS and the UEs are in NLOS [START_REF] Perovic | Achievable rate optimization for mimo systems with reconfigurable intelligent surfaces[END_REF].

Therefore, these assumptions are considered in the present paper and in the numerical results.

In addition, second-order reflections between the IRS and the cluster of scatterers are ignored because they are expected not to contribute significantly due to the large path-loss experienced.

According to the IRS model in (2), the (complex) channel gain between the th transmit antenna of the BS and the th unit cell of the IRS can be written as

= T c (Θ ) 4 exp - 2 (4)
where and Θ denote the distance between the th transmit antenna of the BS and the th unit cell of the IRS, and the angle from which the th transmit antenna is viewed by the IRS, respectively. Similarly, the (complex) channel gain between the th unit cell of the IRS and the th receive antenna can be written as

= R c (Θ ) 4 exp - 2 (5)
where and Θ denote the distance between the th receive antenna and the th unit cell of the IRS, and the angle from which the th receive antenna is viewed by the IRS, respectively.

It is important to note that, differently from (1), the NLOS component of the channel is not present in ( 4) and ( 5), since it is related to the second-and higher-order reflections, which are typically negligible, as mentioned in previous text, and are hence ignored in this paper.

For generality, we consider IRSs that are designed obeying a local constraint (LC) and a global constraint (GC) design criteria [START_REF] Asadchy | Perfect control of reflection and refraction using spatially dispersive metasurfaces[END_REF]. In the first case, we assume ≤ 1 ∀ , i.e., each unit cell of the IRS scatters an amount of power that is smaller than or equal to the impinging power. In the second case, we assume 2 ≤ , i.e., the IRS as a whole scatters an amount of power that is smaller than or equal to the total impinging power. Also, we assume that the IRSs are non-lossy and that the phase shifts applied by the unit cells belong to a finite set, i.e.,

∈ S = 1, 2 , 4 , . . . , 2( -1)
, where = 2 is the number of quantization levels.

III. IRS OPTIMIZATION BASED ON STATISTICAL CSI

In this section, we formulate the problem statement and introduce the proposed (offline and online) optimization algorithms for sum-rate maximization.

A. Problem formulation

Let s = (1), (2), . . . , ( ) be the complex vector comprising the symbols3 transmitted by the BS to the th UE (also referred to as the th stream) and V ∈ C × be the corresponding precoding matrix. The transmitted vector can be formulated as

x = V s ∈ C ×1 . (6)
The information symbols are assumed to be zero-mean and independent, identically distributed (i.i.d.) random variables (RVs), i.e., E s s = I and E s s = 0 for ≠ .

The signal received at the th IRS can be formulated as

r , = S x ∈ C ×1 (7)
where S ∈ C × is the channel matrix between the BS and the th IRS, whose elements are modeled according to (4). The signal reflected by the IRS is

r ′ , = B r , ∈ C ×1 (8)
where B = diag (b ) ∈ C × is the diagonal matrix whose elements are the load reflection coefficients b ∈ C ×1 introduced in Section II-B.

The signal received at the th UE can be expressed as

z , , = T , r ′ , = T , B S x = H , (b ) x ∈ C ×1 (9)
where T , ∈ C × is the channel matrix between the th IRS and the th receiver, whose elements are modeled according to [START_REF] Liaskos | A new wireless communication paradigm through software-controlled metasurfaces[END_REF], and H , (b ) = T , B S .

In addition, the direct signal emitted by the BS and received by the th UE is

w , = H x ∈ C ×1 ( 10
)
where H is the channel matrix between the BS and the th UE.

Thus, considering only the th stream and the th IRS, the received signal at the th UE is

y , , = z , , + w , + n = H + H , (b ) x + n ∈ C ×1 (11)
where n ∈ C ×1 denotes the additive white Gaussian noise with distribution CN 0, 2 I .

Let

H (B) = H + =1 H , (
y = =1 =1 z , , + w , + n = H (B) x + H (B) =1 ≠ x + n ∈ C ×1 . ( 12
)
Based on the MIMO interference channel in [START_REF] Turpin | Reconfigurable and tunable metamaterials: A review of the theory and applications[END_REF], the AR of the th UE is [START_REF] Shi | An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel[END_REF] (V, B) = log det

I + V H (B) J-1 H (B)V (13)
where

J = =1, ≠ H (B)V V H (B) + 2 I is the interference-plus-noise covariance matrix and V = V 1 , V 2 , . . . , V
is the set of precoding matrices of all the UEs.

In the next two sections, we introduce the proposed approach for optimizing the digital beamforming vectors of the BS and the UEs (which occurs during the online phase), as well as the analog beamforming vectors of the IRSs (which occurs during the offline phase). The online phase is subsequent to the offline phase, but it is introduced first for ease of description.

B. BS and UEs beamforming optimization -Online phase

During the online phase, the analog beamforming vectors B of the IRSs are kept constant and are set equal to those computed during the offline phase described next. Hence, for notational simplicity, the dependence on B of the rate in [START_REF] Dai | Reconfigurable intelligent surface-based wireless communication: Antenna design, prototyping and experimental results[END_REF] and the channel matrices is omitted in this section. This implies that the impact of the IRSs is incorporated into the channels in a transparent manner and the IRSs operate as smart scatterers. Therefore, the system boils down to a classical MIMO broadcast channel, which can be optimized by relaying on well established methods and protocols for estimating the CSI of the BS-UE links. This case study has been investigated extensively and is, therefore, briefly discussed in this section. In particular, we propose to utilize the iterative WMMSE algorithm for optimizing the digital beamforming vectors of the BS and the UEs [START_REF] Shi | An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel[END_REF]. The WMMSE algorithm is chosen since it provides the basis for optimizing the analog beamforming vectors of the IRSs, which is described in the next section. In preparation for the next section, the main features of the WMMSE algorithm are briefly summarized.

In the online phase, the sum-rate maximization problem can be formulated as

max V =1 (V) (14)
subject to tr V V ≤ , = 1, 2, . . . , (14.a)

where is the power budget of the th UE and α = [ 1 , 2 , . . . , ] is a set of weights chosen to guarantee a given degree of fairness among the UEs, e.g., by assigning higher weights to UEs with weaker channels. The readers are referred to [START_REF] Wang | Convexity of weighted sum rate maximization in noma systems[END_REF] for further information on α.

The WMMSE algorithm exploits the close relationship between the SINR and the mean square error (MSE), in order to find a locally optimal solution to the sum-rate problem in ( 14) [START_REF] Shi | An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel[END_REF]. To elaborate, let us introduce the MSE matrix E (V, G ), for = 1, 2, . . . , , as

E (V, G ) = E (s -s ) (s -s ) ∈ C × (15)
where s = G y and G is the linear decoding matrix of the th UE.

Problem ( 14) can be reformulated as the following weighted MSE minimization problem

min V,W,G =1 tr [W E (V, G )] -log det (W ) subject to tr V V ≤ , = 1, 2, . . . , (16)
where W 0 is the matrix of weights for the MSE of th UE, and W = W 1 , W 2 , . . . , W and G = G 1 , G 2 , . . . , G are the sets of all weight and receive filter matrices, respectively.

The equivalence between problem ( 14) and ( 16) follows by recalling the relation between the

MMSE covariance Ê (V) = min G E (V, G )
and the rate , i.e., = log det Ê-1 (V) and by the fact that the optimal solution of ( 16) is W = Ê-1 (V). Further details can be found in [START_REF] Shi | An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel[END_REF].

Problem ( 16) is non-convex. If all the optimization variables are fixed except one, however, it is a convex optimization problem in the remaining variables. Accordingly, the weighted MSE minimization problem in ( 16) can be solved by using an iterative block coordinate descent (BCD) algorithm [START_REF] Bertsekas | Nonlinear programming[END_REF]. To elaborate, let us denote by G ( +1) , W ( +1) and V ( +1) the optimization variables after the ( + 1)th iteration. Then, the receive filter matrix is [START_REF] Shi | An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel[END_REF]

G ( +1) = J ( ) -1 H V ( ) (17)
where

J ( ) = =1 H V ( ) V ( ) H + 2 I , the weight matrix W ( +1) is W ( +1) = E ( +1) -1 (18)
and the precoding filter at the BS V , +1 is

V ( +1) = K ( +1) + I -1 H G ( +1) W ( +1) (19)
where

K ( +1) = =1 H G ( +1) W ( +1) G (
+1) H and the Lagrange multiplier involved in the optimization problem is chosen so that the power constraint in [START_REF] Renzo | Smart radio environments empowered by reconfigurable AI meta-surfaces: an idea whose time has come[END_REF] for the th UE is fulfilled.

C. IRS beamforming optimization -Offline phase

The offline phase encompasses the optimization of the IRSs. In contrast to the online phase that relies on instantaneous CSI, the offline phase relies only on channel long-term statistics, e.g., the distribution of the locations of the UEs in the given area. Therefore, it is executed only sporadically. In the extreme case that the IRSs operate as repeaters, it is executed only once.

The objective of the offline phase is to optimize the analog beamforming vectors of the IRSs, B, that maximize the (statistical) average weighted sum-rate of the system. In particular, the average is computed with respect to all random phenomena that determine the channel matrices.

To elaborate, let us denote by Ω the set of random vectors that determine the channel status, including the locations of the UEs, the position of the antennas, the distribution of the clusters of multipath for each link, and the complex channel gains. Accordingly, the total channel matrices depend on and can be formulated as H ( , B). Denoting by Ω ( ) the joint probability density function of Ω, the optimization problem for computing B can be formulated as

max B E max V ( ) (B, V ( )) = max B ∫ ∈Ω max V ( ) =1 (V ( ) , B) Ω ( ) (20)
subject to where the dependence of V with respect to is made explicit in order to emphasize that V depends on . By direct inspection, we observe that GC in (20.b.1) is a convex constraint and LC in (20.b.2) is a non-convex constraint. Therefore, the LC setup is more difficult to study.

tr V ( ) V ( ) ≤ , ∀ , = 1, 2, . . . , (20.
In this section, therefore, we restrict the analysis to the GC setup. After solving the GC case study, a (suboptimal but low complexity) solution for the LC case study can be obtained by recalling that a local element-wise projection onto the unit circle of the solution obtained for the GC setup corresponds to the minimum distance projection on the feasibility set of the LC setup [START_REF] Abrardo | Distributed digital and hybrid beamforming schemes with MMSE-SIC receivers for the MIMO interference channel[END_REF], [START_REF] Gauch | Subspace estimation and decomposition for large millimeter-wave MIMO systems[END_REF]. Therefore, we solve the optimization problem in [START_REF] Zappone | Overhead-aware design of reconfigurable intelligent surfaces in smart radio environments[END_REF] under the GC constraint and we then obtain the solution under the LC constraint by applying an element-wise scaling to the solution of the GC setup. The performance offered by this approach is analyzed in the numerical results.

Even though the GC constraint is convex, problem ( 20) is non-convex and is, therefore, difficult to solve. To this end, the sum-rate maximization problem in [START_REF] Zappone | Overhead-aware design of reconfigurable intelligent surfaces in smart radio environments[END_REF] can be reformulated as a weighted MSE minimization problem. In particular, we have

min B ∫ ∈Ω min V ( ),W ( ),G( ) =1 tr [W ( ) E (V ( ) , B, G ( ))] -log det (W ( )) Ω ( ) (21)
subject to tr V ( ) V ( ) ≤ , ∀ , = 1, 2, . . . , (22)
tr b b ≤ 1, = 1, 2, . . . , , (23)
where E (V ( ) , B ( ) , G ( )) is the × MSE matrix defined in [START_REF] Di Renzo | Analytical modeling of the path-loss for reconfigurable intelligent surfaces -Anomalous mirror or scatterer ?[END_REF].

From the statistical properties of the information vectors s , we can elaborate [START_REF] Di Renzo | Analytical modeling of the path-loss for reconfigurable intelligent surfaces -Anomalous mirror or scatterer ?[END_REF] as

E (V ( ) , B, G ( )) = I + G ( ) H ( , B) V ( ) G ( ) H ( , B) V ( ) -G ( ) H ( , B) V ( ) -G ( ) H ( , B) V ( ) + =1 ≠ G ( ) H ( , B) V ( ) G H ( , B) V ( ) + 2 G ( ) G ( ) ∈ C × (24)
The optimization problem in ( 21) is constituted by an inner and an outer optimization subproblems. To tackle both sub-problems, we employ an iterative BCD algorithm. More precisely, let us denote by B ( ) , G ( ) ( ), W ( ) ( ) and V ( ) ( ) the optimization variables after the th iteration. As far as the inner optimization sub-problem is concerned, the set of variables B is fixed as a function of . Thus, the inner optimization sub-problem in ( 21) is formally the same as the optimization problem solved during the online phase. This implies that the single-step updates G ( +1) ( ), W ( +1) ( ) and V ( +1) ( ) can be computed from ( 17), [START_REF] Dardari | Communicating with large intelligent surfaces: Fundamental limits and models[END_REF], and [START_REF] Hu | Beyond massive MIMO: The potential of data transmission with large intelligent surfaces[END_REF].

As far as the outer optimization sub-problem in ( 21) is concerned, on the other hand, the solution is not straightforward. More precisely, the outer optimization sub-problem in [START_REF] Wu | Intelligent reflecting surface aided wireless communications: A tutorial[END_REF] encompasses the computation of the optimal set of variables B while all the other optimization variables are kept fixed. Next, we introduce an iterative algorithm to solve this problem. For ease of notation, we drop the index of the iterations and use the notation G ( ), W ( ), V ( ).

To start with, we elaborate the expression of the MSE in [START_REF] Zhao | Intelligent reflecting surface enhanced wireless network: Two-timescale beamforming optimization[END_REF]. By recalling that H ( , B) =

H ( ) + =1 H , ( , b ), we obtain E (V ( ), B, G ( )) = =1 G ( ) =1 H , ( , b ) V ( ) G ( ) =1 H , ( , b ) V ( ) + 2ℜ       =1 G ( ) =1 H , ( , b ) V ( ) V ( ) H ( ) G ( )       -2ℜ G ( ) =1 H , ( , b ) V ( ) + Υ ∈ C × (25)
where 2ℜ (A) = A + A , Υ is a constant, and ℜ( ) denotes the real part of .

Let us consider the WMMSE minimization with respect to the load reflection coefficient, b , of the th IRS. To this end, we introduce the shorthand notation

A , ( ) = G ( ) T , ( ) ∈ C × C , ( ) = S ( ) V ( ) ∈ C × D , , ( ) = S ( ) V ( ) H G ( ) ∈ C × F , , ( ) = S ( ) V ( ) G ( ) =1 ≠ H , ( , b ) V ( ) ∈ C × . ( 26
)
From ( 9), ( 25) and ( 26), we can derive the contribution of b to the MSE as follows

E ( ) (V ( ) , B, G ( )) = =1 A , ( ) B C , ( ) A , ( ) B C , ( ) + 2ℜ       =1 A , ( ) B D , , ( )       + 2ℜ       =1 A , ( ) B F , , ( )       -2ℜ A , ( ) B C , ( ) ∈ C × . ( 27
)
For ease of writing, we introduce the compact indexing notation Z { : , : } , which yields the submatrix extracted from the th to the th rows and from the th to the th columns of Z.

Furthermore, let us consider the mapping

Q (Q 1 , Q 2 ) between the matrices Q 1 ∈ C × and Q 2 ∈ C × and the matrices Q ∈ C × and ∈ C × defined as Q { ,( -1) +1: } (Q 1 , Q 2 ) = Q { ,:} 1 ⊙ Q {:, } 2 for = 1, 2, . . . , , = 1, 2, . . . , {( -1) +1: , } = b for = 1, 2, . . . , (28)
where () denotes the transpose operation and ⊙ denotes the Hadamard (element-wise) product.

From [START_REF] Dardari | Using metaprisms for performance improvement in wireless communications[END_REF], we obtain the identity

Q 1 B Q 2 = Q (Q 1 , Q 2 ) (29)
from which ( 27) can be reformulated as

E ( ) (V ( ) , B, G ( )) = =1 Q A , ( ) , C , ( ) Q A , ( ) , C , ( ) + 2ℜ       =1 Q A , ( ) , D , , ( )       + 2ℜ       =1 Q A , ( ) , F , , ( )       -2ℜ Q A , ( ) , C , ( ) ∈ C × . (30)
From mathematical convenience, we introduce the notation

M ( ) = =1 W ( ) =1 Q A , ( ) , C , ( ) Q A , ( ) , C , ( ) ∈ C × Ũ ( ) = =1 W ( ) =1 Q A , ( ) , C , ( ) -Q A , ( ) , D , , ( ) + Q A , ( ) , F , , ( ) ∈ C × (31)
with M ( ) ∈ C × and u ( ) ∈ C ×1 defined as

M ( ) = =1 M ( ) {( -1) +1: ,( -1) +1: } for = 1, 2, . . . , u ( ) = =1 Ũ ( ) {( -1) +1: , } for = 1, 2, . . . , . (32)
Based on these definitions, a closed-form expression for the gradient of the WMMSE in [START_REF] Wu | Intelligent reflecting surface aided wireless communications: A tutorial[END_REF] with respect to b is

∇ b       ∫ ∈Ω =1 tr (W ( ) E (V ( ) , B, G ( ))) Ω ( )       = 2 ∫ ∈Ω M ( ) Ω ( ) b -2 ∫ ∈Ω u ( ) Ω ( ) . (33)
Therefore, the analog beamforming vectors of the IRSs at the ( +1)th iteration, b ( +1) , can be formulated in analytical form. More precisely, let M( ) and ū( ) denote the statistical expectation, with respect to the random variables , of M ( ) ( ) and u ( ) ( ) evaluated at the th iteration

M( ) = ∫ ∈Ω M ( ) ( ) Ω ( ) (34)
ū( ) = ∫ ∈Ω u ( ) ( ) Ω ( ) .
proposed algorithm is guaranteed to converge to a stationary point of ( 21). An important property about the convergence of Algorithm 1 is stated in the following theorem.

Theorem 1 Any stationary point of ( 21) is also a stationary point of [START_REF] Zappone | Overhead-aware design of reconfigurable intelligent surfaces in smart radio environments[END_REF].

Proof: Let B, V ( ), Ŵ ( ), and Ĝ ( ) denote the optimization variables of Algorithm 1 at convergence. Since the WMMSE is guaranteed to converge to a stationary point of ( 21), the unconstrained variable set G ( )

fulfills the MMSE conditions E V ( ) , B, Ĝ ( ) = Ê V ( ) , B and Ŵ ( ) = Ê-1 V ( ) , B . Let us define Θ 1 (B, V ( ) , G ( ) , W ( )) = ∫ ∈Ω =1 tr [W ( ) E (V ( ) , B, G ( ))] -log det (W ( )) Ω ( ) (36)
Θ 2 (B, V ( )) = - ∫ ∈Ω =1 (V ( ) , B) Ω ( ) . (37)
Since the optimization problems in ( 21) and ( 20) have the same constraints in terms of the optimization variables B and V ( ), Theorem 1 can be proved by showing that Θ 1 and Θ 2 have the same gradient, computed with respect to B and V ( ), in correspondence of the convergence points B, V ( ), Ŵ ( ), Ĝ ( ). In detail, with the aid of some notable results on the differentiation of complex-valued matrices, the following gradients are obtained [START_REF] Perovic | Achievable rate optimization for mimo systems with reconfigurable intelligent surfaces[END_REF] and ( 36) we obtain

∇ b tr Ŵ ( ) Ê V ( ) , B = Ŵ ( ) ∇ b Ê V ( ) , B (38)
∇ b det Ê V ( ) , B = det Ê V ( ) , B Ê V ( ) , B -1 • ∇ b Ê V ( ) , B . Since V ( ) , B = -log det Ê V ( ) , B , from
∇ b Θ 1 B, V ( ) , Ĝ ( ) , Ŵ ( ) = ∫ ∈Ω =1 Ŵ ∇ b Ê V ( ) , B Ω ( ) ∇ b Θ 2 B, V ( ) = ∫ ∈Ω =1 Ê V ( ) , B -1 ∇ b Ê V ( ) , B Ω ( ) . (39)
Since

Ŵ ( ) = Ê-1 V ( ) , B , we have ∇ b Θ 1 = ∇ b Θ 2 .
By using a similar procedure, it is possible to prove the equality

∇ V Θ 1 = ∇ V Θ 2 .
This concludes the proof.

IV. NUMERICAL RESULTS AND DISCUSSION

In this section, we illustrate some numerical results in order to analyze the performance of the proposed optimization algorithm, and, in particular, to assess the impact of not using instantaneous CSI for optimizing the IRSs.

A. Simulation scenario

We consider an indoor environment with dimensions 30 m × 30 m along the -axis andaxis, respectively, as depicted in antennas along the -axis, while the 4 antennas of the UEs are arranged horizontally along the -axis. The antenna-element gains at the BS and at the UE are set to 3 dB. The variance 2 of the additive zero-mean Gaussian noise and the maximum power budget (assumed the same for all UEs), are set equal to -97 dBm and 0 dBm, respectively.

B. IRS deployment

The IRSs are placed on the walls around the UEs. The size of each IRS is 0.428/ √ m × 0.214/ √ m. This ensures that, regardless of the number of IRSs, the total area covered by the IRSs is 0.428 m × 0.214 m, for a fair comparison. The inter-distance between the scattering elements of the IRS is /2, where = 0.011 m corresponds to a carrier frequency of 28 GHz. Accordingly, the total number of scattering elements that is available in the considered environment is = 3200. To ensure an affordable computational complexity for Algorithm 1, each IRS is partitioned into = 64 tiles each comprising = 50 scattering elements. As a matter of fact, the complexity of the offline optimization algorithm is mainly determined by the computation of b ( +1) in [START_REF] Ellingson | Path Loss in Reconfigurable Intelligent Surface-Enabled Channels[END_REF], which requires the inversion of a × matrix whose complexity is ( 3 ). As a function of , on the other hand, the complexity of Algorithm 1 increases only linearly. As for the power constraints of the IRSs, both GC and LC case studies are considered.

C. Channel model

As for the wireless channel, we assume an NLOS channel model for the direct path, i.e., = 0

in [START_REF] David | 6G vision and requirements: Is there any need for beyond 5G?[END_REF]. This represents the most interesting network scenario for using the IRSs. If a strong LOS path is available, in fact, the impact and contribution of the IRSs are usually less significant if the transmission distances are large and the IRSs have a small size [START_REF] Perovic | Achievable rate optimization for mimo systems with reconfigurable intelligent surfaces[END_REF]. As for the NLOS contribution to the channel, we consider = 5 and = 10. More specifically, the centers of the clusters are positioned on an ellipse as discussed in Section II-A with an eccentricity = 0.5, and the scatterers associated to each cluster are randomly distributed around the clusters' centers such that the angle spread of the signals received by the UEs is 15 • . These values are in agreement with typical NLOS multipath models for mmWave communications, e.g., see [START_REF] Buzzi | Energy efficiency and asymptotic performance evaluation of beamforming structures in doubly massive MIMO mmWave systems[END_REF].

D. IRS optimization

In order to assess the effectiveness of the proposed joint online-offline optimization algorithm, we compare the sum-rate of two network setups: (i) the IRSs are optimized according to Algorithm 1 (denoted by OPT) and (ii) the IRSs act as non-controllable scatterers (denoted by NON-OPT). In this latter case, the unit cells of the IRSs operate as diffusive radiating elements whose reflection coefficient has unit amplitude and whose phases are independently and uniformly distributed in [0, 2 ]. Also, the weights α in ( 14) are set equal to 1.

As for the statistics of the locations of the UEs, we consider three scenarios that are denoted by , -1m, and -0m. In the scenario, the UEs are deployed uniformly at random within a given service area. This corresponds to the scenario with the minimal a priory information about the locations of the UEs, and, therefore, the analog beamforming vectors of the IRSs are optimized by averaging over a probability density function Ω ( ) that accounts for the largest uncertainty. In the -1m scenario, the locations of the UEs are assumed to be known with an uncertainty of 0.5 m around the actual location of each UE. In other words, the UEs are distributed within a disk of diameter 1 m that is centered at their actual locations. In the -0m scenario, the locations of the UEs are assumed to be perfectly known. This case study corresponds to the scenario in which the maximal a priori CSI is necessary and the IRSs need to be reconfigured more often based on the UEs' locations. It is worth recalling that the IRS-assisted links are determined only by the positions of the UEs. Therefore, the scenario corresponds to the full CSI setup for optimizing the analog beamforming vectors of the IRSs.

The simulation results are obtained by averaging the sum-rate over 10,000 network realizations and by setting = 1, 000 in Algorithm 1. Average rate per user (bpcu)

LC N b -N IRS = 1 LC N b -N IRS = 2 GC -N IRS = 1 GC -N IRS = 2 LC -N IRS = 1 LC -N IRS = 2
Fig. 2: Performance of the OPT scheme for the LC, GC, and LC ∞ constraints as a function of ( = 1, 2 and = 1).

E. Local vs. global power constraint and phase quantization noise

In Fig. 2, we investigate the impact of the phase quantization noise on the sum-rate, by assuming a single UE scenario ( = 1), the OPT setup, and the IO channel model. The constraints LC , GC, and LC ∞ are considered, where the latter constraint is referred to the case study with no phase quantization noise. We observe that the LC constraint provides, in the considered case study, similar performance as the GC constraint, even if the number of quantization bits is low. For example, the performance difference is less than 2% if = 3.

Similar results are obtained for all considered network scenarios. For simplicity, therefore, only the curves that correspond to the GC constraint are reported in the following figures.

F. Sum-rate optimization

In Fig. 3 that the average rate per user decreases with the increase of the number of UEs. This can be attributed to a stronger interference in the presence of multiple UEs. As far as the impact of the number of IRSs is concerned, we observe that, in general, the average rate per user increases with even if the total surface area covered by the IRSs is kept unchanged, i.e., deploying a larger number but smaller in size IRSs yields better performance. This is attributed to the fact that an higher number of IRSs located in different positions allow to increase the multipath, and, hence, the rank of the channel matrices as shown in subsequent results.

Slightly different results are, on the other hand, obtained in the SM channel model, as illustrated in Fig. 3-(right). In this case, in fact, the contribution of the NLOS multipath undergoes a smaller path-loss, and, therefore, fewer IRSs may be needed for achieving good performance.

In Fig. 4, we show the average rate per user that is achievable in the -0m and scenarios by assuming the IO channel model. By comparing Fig. 3 with Fig. 4, we observe, as expected, that the -0m setup outperforms the -1m setup, but at the cost of reconfiguring the IRSs more frequently. Likewise, the scenario offers the worse performance but with the main advantage of reducing the rate at which the IRSs need to be reconfigured. Nevertheless, it is interesting to note that the OPT case still outperforms the NON-OPT case even if the locations of the UEs are known with a quite large uncertainty.

G. Rank of the IRS-assisted channel

In Fig. 5, we analyze the effective rank of the IRS-assisted channel, by assuming where are the singular values of the channel matrix in [START_REF] Turpin | Reconfigurable and tunable metamaterials: A review of the theory and applications[END_REF]. The parameter provides one with information on how well conditioned the IRS-assisted channel is. In other words, the larger is, the larger the capacity and the number of information streams that can be transmitted simultaneously are. In particular, = 1 indicates that a singular value is predominant, and, thus, the rank of the channel is, in practice, one. If, on the other hand, all singular values are almost the same, the channel capacity is maximized. In the considered system setup, ≤ 4, since four antennas are available at the UEs. The results in Fig. 5 show that increasing the number of IRSs increases the effective rank of the channel and, thus, the system sum-rate. The effective rank is larger in the SM channel model because of the more favorable propagation conditions.

H. Analysis of the equivalent array factors of the IRSs

In order to get engineering insights on how the IRSs shape the wireless channel for increasing the sum-rate, Figs. 6 and 7 report the array factor of the BS and the equivalent array factor of the IRSs for some given locations of the UEs. More precisely, the equivalent array factor of an IRS, corresponding to some given locations of the UEs, is obtained by considering an equivalent antenna array virtually located at the IRS and whose array factor is obtained from the Finally, Fig. 7 shows the equivalent array factors in the scenario. In this case, in particular, the IRSs are optimized with the only a priori information that the UEs can be located anywhere in the grey shadowed area (uncertainty region). The figure reports the results that correspond to the system setup = 4 and = 4 for a generic realization of the positions of the UEs. In this case, we observe that the IRSs are optimized in order to diffuse the reflected signals towards

V. CONCLUSION

In this paper, we have introduced an optimization algorithm in order to maximize the network sum-rate of a MU-MIMO system in the presence of multiple IRSs. The proposed algorithm consists of an offline phase and an online phase. During the offline phase, the IRSs are configured based on an optimization procedure that relies exclusively on the statistical characterization of the environment, such as the distribution of the users' locations and the channel statistics. In this phase, in particular, instantaneous CSI is not necessary. During the online phase, on the other hand, only the beamforming vectors at the BS and at the users are optimized, whereas the configuration of the IRSs is kept unchanged. The main advantage of the proposed approach lies in not requiring the estimation of the instantaneous CSI for optimizing the IRSs, thus significantly reducing the overhead associated with the optimization of IRS-assisted wireless systems. The obtained numerical results confirm the validity of the proposed approach. Notably, IRS-assisted wireless systems that are optimized based solely on long-term CSI still provide large performance gains as compared to wireless systems in the absence of IRSs.

  b ) denote the total channel between the BS and the th UE, where B = {b 1 , b 2 , . . . , b } is the set of vectors containing the reflection coefficients of the IRSs (analog beamforming vectors). The signal received at the th UE in the presence of concurrent transmitted streams and IRSs is

a) tr b b ≤ 1 , = 1 , 2 ,

 112 . . . , (GC case) (20.b.1) or ∈ S , = 1, 2, . . . , = 1, . . . , (LC case) (20.b.2)

Fig. 1 :

 1 Fig. 1: Layout of the considered indoor scenario (aerial view) for = 4 UEs and

Fig. 1 .

 1 The UEs are equipped with = 4 vertically polarized antennas and are deployed randomly on the left-half of the room, i.e., in an area of 15 m × 30 m, at a height of 1 m. The BS is equipped with = 16 vertically polarized antennas and is placed on the opposite side of the room at the position (15, 30) m and at a height of 2 m. The 16 antennas of the BS are arranged on theplane with 8 antennas along the -axis and 2

4 Fig. 3 :

 43 Fig. 3: Comparison between the OPT and NON-OPT schemes. (left) -1m setup and IO channel model; (right) -1m setup and SM channel model.

Fig. 4 :

 4 Fig. 4: Comparison between the OPT and NON-OPT schemes. (left) -1m vs.

= 1 and

 1 the OPT configuration of the IRSs in the three scenarios , -1m, -0m. Given the channel matrix in (12), we compute = | |/max | | as a function of the number of IRSs,

Fig. 5 := 1 . 2 (

 512 Fig. 5: Average effective rank ( ) of the IRS-assisted channel as a function of

Fig. 6 :

 6 Fig. 6: BS and IRS equivalent array factors. (left)

Fig. 7 : 4 .

 74 Fig. 7: BS and IRS equivalent array factors for

We assume that the number of symbols is equal to the number of receive antennas.

We eventually obtain

where the Lagrange multipliers is chosen so that the GC constraint in [START_REF] Wu | Intelligent reflecting surface aided wireless communications: A tutorial[END_REF] is fulfilled.

The proposed approach requires the analytical expression of the probability density function

If Ω ( ) is available in closed-form, then the integrals in (34) can be computed numerically. In general, however, Ω ( ) is seldom available in closed-form because of the large number of optimization variables involved. In this latter case, the typical approach used to overcome this issue lies in using Monte Carlo methods based on a repeated random sampling of all the optimization variables. The proposed algorithm is summarized in Algorithm 1, where { }, for = 1, . . . , , denote the random samples of the Monte Carlo method.

Algorithm 1: Proposed algorithm for (offline) sum-rate maximization Initialize:

Generate an initial precoding matrix V (0) and IRS analog beamforming vectors b (1) , = 1, . . . , , that fulfill the power constraint;

Set an arbitrarily small value ;

Generate the Monte Carlo samples , ∀ = 1, 2, . . . , , from Ω ( ) while Δ > do for = 1, . . . , do for = 1, . . . , do

Compute G ( ) ( ), W ( ) ( ) and V ( ) ( ) according to [START_REF] Özdogan | Intelligent reflecting surfaces: Physics, propagation, and pathloss modeling[END_REF], ( 18) and ( 19);

Compute M ( ) ( ) and u ( ) ( ) according to [START_REF] Wu | A non-stationary wideband channel model for massive MIMO communication systems[END_REF];

Compute b ( +1) according to [START_REF] Ellingson | Path Loss in Reconfigurable Intelligent Surface-Enabled Channels[END_REF].

D. Convergence of the proposed offline optimization algorithm

The proposed offline optimization algorithm minimizes the average weighted MSE. In particular, all the optimization variables are updated simultaneously. From [START_REF] Solodov | On the convergence of constrained parallel variable distribution algorithm[END_REF], it follows that the


Pierre Fraigniaud
email: pierre.fraigniaud@liafa.jussieu.fr

George Giakkoupis
email: george.giakkoupis@liafa.jussieu.fr

Influence d'une distribution des degr és en loi de puissance sur la navigabilit é des petits mondes † ‡

Keywords:

Cette note résume nos travaux sur le routage décentralisé dans les petits mondes, et plus spécifiquement dans ceux qui combinent un plongement spatial avec une grande variabilité des degrés. Plus précisément, nous considérons une variante du modèle des treillis augmentés dû à J. Kleinberg (STOC 2000) pour laquelle le nombre de contacts lointains par sommet suit une loi de puissance. Ce modèle est motivé par des observations concordantes qu'un grand nombre de réseaux ont une telle distribution de degré. Pour ces réseaux, l'exposant α de la loi de puissance est généralement entre 2 et 3. Nous prouvons que, dans notre modèle, et pour cet intervalle de valeurs 2 < α < 3, l'espérance du nombre d'étapes du routage glouton de n'importe quelle source à n'importe quelle destination est au plus O(log α-1 n). Cette borne est exacte au sens fort. En effet, nous montrons également que l'espérance du nombre d'étapes du routage glouton entre une source et une destination choisies aléatoirement uniformément est au moins Ω(log α-1 n). Pour α < 2 ou α ≥ 3, nous montrons également que le routage glouton s'exécute en Θ(log 2 n) étapes en espérance. Et, pour α = 2, Θ(log 1+ε n) étapes sont nécessaires en espérance, où 1/3 ≤ ε ≤ 1/2. A notre connaissance, ces résultats sont les premiers permettant de quantifier l'influence d'une distribution des degrés en loi de puissance sur la navigabilité des petits mondes. De surcroît, nous montrons que cette influence est significative. En particulier, lorsque l'exposant de la loi approche 2 par excès, l'espérance du nombre d'étapes du routage glouton dans un treillis augmenté dont les degrés suivent une oi de puissance approche la racine carrée du nombre d'étapes du routage glouton dans un treillis augmenté dont les degrés sont fixés, même lorsque les deux graphes possèdent un degré moyen identique.

1 Navigability of small worlds It has been observed that many "real-world" networks, such as social, information, technological, and biological networks, exhibit the small-world property ; i.e., they are locally clustered, and (yet) short paths exist between almost all pairs of nodes (see [START_REF] Newman | The structure and function of complex networks[END_REF] and the references therein). It is also well-established that many small-world networks (e.g., the network of acquaintances between individuals) are easy to navigate, provided that the nodes are able to estimate the distances to other nodes with respect to some underlying metric (e.g., geography, professions, etc.) [START_REF] Dodds | An experimental study of search in global social networks[END_REF][START_REF] Milgram | The small world problem[END_REF]. Navigability refers to the ability of nodes to route messages efficiently in a decentralized manner, using local information only. The most prominent example of such a routing scheme is greedy routing : a node handling a message destined to some target node forwards the message to its neighbor that is closer to the target, according to the underlying metric. The first formal analysis of greedy routing in a plausible model of small worlds was presented in [START_REF] Kleinberg | The small-world phenomenon : An algorithm perspective[END_REF]. The model studied there was the augmented lattice : Consider the n-node d-dimensional lattice that wraps around, where d ≥ 1. A node has links to its 2d lattice-neighbors, and also to k ≥ 1 other nodes, its longrange contacts. Each of the long-range contacts of a node u is chosen using an independent random trial following the d-harmonic distribution : the probability that node v is chosen in a given trial is

p u,v ∝ 1/(dist(u, v)) d , (1.1)
where dist(u, v) is the lattice-distance between u and v. In [START_REF] Kleinberg | The small-world phenomenon : An algorithm perspective[END_REF] it was shown that, in this model, greedy routing requires O( 1 k log 2 n) expected number of steps, for any source-target pair. (This complexity was later shown to be tight [START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF].) It was also shown that any decentralized routing algorithm performs poorly if the d-dimensional lattice is augmented using the h-harmonic distribution, for any h = d. Specifically, Ω(n γ ) expected steps are required, for some γ > 0 that depends on h and d.

Despite its simplicity, the augmented-lattice model seems to capture successfully the small-world and navigability properties of real-world networks. Note that in the d-dimensional lattice the d-harmonic distribution is equivalent to the "natural" distribution p u,v ∝ 1/|B u (dist(u, v))|, where B u (r) is the ball centered at u of radius r ; this latter distribution was used in [START_REF] Duchon | Could any graph be turned into a small-world[END_REF][START_REF] Slivkins | Distance estimation and object location via rings of neighbors[END_REF] to extend the results of [START_REF] Kleinberg | The small-world phenomenon : An algorithm perspective[END_REF] to graphs of bounded ball growth, and to graphs of bounded doubling dimension. Also, the d-harmonic distribution is equivalent in the lattice to the rank-based distribution p u,v ∝ 1/r u (v), where r u (v) is the rank of v when nodes are sorted in increasing distance from node u ; this latter distribution was used in [START_REF] Kumar | Navigating low-dimensional and hierarchical population networks[END_REF] to extend the results of [START_REF] Kleinberg | The small-world phenomenon : An algorithm perspective[END_REF] to non-uniform population densities. In fact, it was experimentally demonstrated that two-thirds of friendships are geographically distributed this way : the probability of befriending a particular person is inversely proportional to the number of people closer to you [LNNK + 05]. Finally, it was recently shown that the d-harmonic distribution of the long-range links might as well be an inherent byproduct of node mobility [START_REF] Chaintreau | Networks become navigable as nodes move and forget[END_REF]. Therefore, there is now a consensus that the augmented-lattice model is an appropriate framework for analyzing small-world navigability.

Power-law degree distribution

The augmented-lattice model, however, fails to capture another commonly observed property of realworld networks, the heavy-tailed degree distribution. Such a distribution is well approximated by a power law

ÈÖ[deg(u) = k] ∝ 1/k α , (2.1)
where α is a real, typically between 2 and 3 [START_REF] Newman | The structure and function of complex networks[END_REF]. Nevertheless, it is straightforward to reconcile the augmented-lattice model with a power-law distribution for the node degrees, simply by drawing the number of long-range links added to each node independently at random from a power-law distribution [START_REF] Kleinberg | Complex networks and decentralized search algorithms[END_REF]. It is reasonable to expect that this modification would reduce the lengths of shortest paths between nodes, since the (few) high-degree nodes should provide short-cuts between most nodes. This is typically the case in networks with power-law degree sequences [START_REF] Chung | The average distance in a random graph with given expected degrees[END_REF]. However, it is unclear how decentralized routing could benefit from the existence of these high-degree nodes [START_REF] Kleinberg | Complex networks and decentralized search algorithms[END_REF].

Utilizing the heavy-tailed degree distribution in the design of decentralized routing algorithms was suggested in [ALPH01, FGL05, KYHJ02, SBR04]. In all these works, the routing algorithms only have access to information about the degrees of neighboring nodes, not to any embedding of the graph. Although some performance improvements are observed compared to routing algorithms oblivious to the node degrees, the expected number of steps remains polynomial in the network size. Also, [START_REF] Simsek | Decentralized search in networks using homophily and degree disparity[END_REF] proposed a heuristic decentralized algorithm for routing in a variance of the augmented lattice where nodes have widely varying degrees. This heuristic assumes that nodes have access both to the locations of theirs neighbors, and to their degrees. Simulations showed that this algorithm performs better than decentralized algorithms using only one of these two sources of information. However, no formal analysis was provided.

Our framework

We consider the following variance of the augmented-lattice model. As in the original model, the longrange links are drawn independently at random according the harmonic distribution with exponent equal to the dimensionality of the lattice (cf. Eq. 1.1). Unlike the original model, however, the number of long-range contacts each node has is not fixed, but it is drawn independently at random from the power-law distribution with exponent α ≥ 0 (cf. Eq. 2.1). This distribution is scaled so that its expectation is constant and each node has at least one long-range contact. We then remove the orientation of each of the long-range links to get a non-directed network. We study the performance of greedy routing in this network.

Our results

In this section, we ignore O(log log n) multiplicative factors in the statement of the asymptotic bounds. We prove that, for 2 < α < 3, which is the case for most real-world networks, the expected number of steps of greedy routing from any source to any target is O(log α-1 n) steps. Thus, for this range of values for α, the effect of the power-law degree distribution is significant. In particular, when α approaches 2, the expected number of steps of greedy routing in the augmented lattice with power-law degrees approaches the square-root of the expected number of steps of greedy routing in the augmented lattice with fixed degrees, although both networks have the same average degree. For both α < 2 and α ≥ 3, we show that the expected number of steps of greedy routing from any source to any target is O(log 2 n) steps, which is the same order of magnitude as the performance of greedy routing in the augmented lattice with fixed degrees. For the critical value α = 2, we prove that the expected number of steps of greedy routing from any source to any target is O(log 3/2 n) steps.

All these upper bounds are tight (but, perhaps, for α = 2). For α > 2, the upper bounds are even tight in a strong sense. Indeed, we prove that the expected number of steps of greedy routing for a uniformly-random pair of source-target nodes is Ω(log α-1 n) steps if 2 < α < 3, and Ω(log 2 n) steps if α ≥ 3. For α < 2, we prove that there exists a source-target pair for which greedy routing requires Ω(log 2 n) expected steps. For α = 2, we show that the expected number of steps for a uniformly-random source-target pair is Ω(log 4/3 n).

We formally prove the above results for the case of the 1-dimensional lattice, i.e., the ring. Nevertheless, none of the arguments we use is specifically tied to the ring, and the exact same results can be easily shown for d-dimensional lattices, for constant values of d. Note that unlike the results in [START_REF] Kleinberg | The small-world phenomenon : An algorithm perspective[END_REF], where the critical value of the exponent depends on the dimensionality d of the lattice, our results do not depend on d.

To the best of our knowledge, these results are the first to formally quantify the effect of the power-law degree distribution on the navigability of small worlds.

The following picture emerges from our analysis. For α ≥ 3, almost all nodes are of small degree, and the nodes of higher degree are too few to contribute significantly. Hence greedy routing performs essentially the same as when the degrees are fixed. For 2 < α < 3, there are still very few nodes of high degree. However, nodes of degree roughly log n are relatively abundant, and there are more and more such nodes as α approaches 2. It is the contribution of these nodes that reduces the routing time from log 2 n to log α-1 n.

The case α = 2 is special. All "degree scales" are present, and each is equally likely to contribute. On the one hand, this results in greater routing speed than in the case 2 < α < 3 when the current node is far from the target, since there are many high-degree nodes between the current node and the target in the lattice. On the other hand, the balance in the degree scales means that as we get closer to the target the number of high-degree nodes available decreases faster than when 2 < α < 3 ; and when we get at distance sub-polynomial from the target (essentially at distance less than e √ ln n ), greedy routing performs the same as when the degrees are fixed.

Finally, for α < 2, there are very many nodes of high degree, and the role of the cut-off point k max of the power law becomes critical. We assumed that k max ∼ n γ , for some 0 < γ ≤ 1. In this setting, only the contribution of nodes with degree close to k max is significant. However, when the current node is at distance less than k max from the target, it is very likely that greedy routing will not find a node of such degree, and from that distance it starts performing the same as when the degrees are fixed. Note that for α < 2, nodes that are further away from the target may, in expectation, require fewer steps to reach that target than nodes closer to the target, which is not the case when α > 2.

FIGURE 1 :

 1 FIGURE 1: Summary of the results.

† Both authors are supported by the ANR project ALADDIN, and by the INRIA project GANG. ‡ The full version of this paper will appear in Proc. 28th ACM Symp. on Principles of Distributed Computing (PODC 2009).