Configuring Intelligent Reflecting Surface with Performance Guarantees: Optimal Beamforming

Intelligent reflecting surface (IRS) is an emerging 6G technology that uses a large array of low-cost electromagnetic “mirrors”, i.e., reflective elements, to orient the impinging radio waves toward the intended receiver, thereby boosting the spectral efficiency, energy efficiency, and reliability of wireless transmission [1, 2]. From a practical standpoint, the choice for the phase shift induced by each reflective element is normally restricted to a set of discrete values because of hardware constraints. Although IRS has been studied extensively in the literature to date, it remains a challenging task to optimally coordinate discrete phase shifts across reflective elements.

This work proposes efficient strategies for discrete beamforming for IRS in order to maximize the received signal-to-noise ratio (SNR) boost, the computational complexity of which is only linear in the number of reflective elements. For the binary phase beamforming with each phase shift confined to the set $\{0,\pi\}$, we show that the global optimal solution can be computed in linear time; for the general $K$-ary phase beamforming case with each phase shift confined to the set $\{\omega,2\omega,\ldots,K\omega\}$ where $\omega=2\pi/K$, we propose a linear time approximation algorithm that guarantees an SNR boost within a constant fraction $(1+\cos(\pi/K))/2$ of the global optimum, e.g., it can attain over $85\%$ of the optimal SNR boost for the quadrature beamforming with $K=4$.

Unlike the existing multi-antenna devices, IRS is a passive device that does not perform active signal transmitting. This passive trait of IRS has spurred considerable research interests over the past few years in adapting the traditional methods of active beamforming, covering a variety of system models ranging from point-to-point communication [3, 4, 5, 6] to downlink cellular network [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], uplink cellular network [20, 21], interference channel [22], and wiretap channel [23]. While the prior studies in this area mostly assume that the phase shift can be chosen arbitrarily for every reflective element, there is a growing trend toward practical beamforming that restricts the choice for phase shift to a set of discrete values [24, 25, 26, 27, 28, 29, 30, 31, 32, 33]. Two common objectives of IRS beamforing as adopted in the literature are to maximize the throughput [8, 3, 11, 10, 20, 18, 19, 15, 13, 23] and to minimize the power consumption under the quality-of-service (QoS) constraints [7, 12, 21, 17, 16], other works accounting for the generalized degree-of-freedom (GDoF) [22], energy efficiency [9], and outage probability [34].

Optimization is a key aspect of the IRS beamforming. In the realm of continuous IRS beamforming, two standard optimization tools—semidefinite relaxation (SDR) [35] and fractional programming (FP) [36, 37]—have been brought to the fore to address the nonvexity of the IRS beamforming problem. For instance, [7, 38, 14, 12, 20, 15, 19] suggest using SDR because of the quadratic programming form of the IRS beamforming problem, while [11, 23, 17, 34, 21, 5, 18, 23, 13] invoke FP to deal with the fractional function of the signal-to-interference-plus-noise ratio (SINR). Moreover, [22] develops a unified Riemannian conjugate gradient algorithm to enable interference alignment in an IRS-assisted system, [10, 16] cope with the nonconvex beamforming problem via successive convex approximation, [6] relies on the minorization-maximization (MM) to address the hardware impairments in the IRS beamforming problem, and [3, 19] suggest a decentralized beamforming scheme based on alternating direction method of multipliers (ADMM).

In comparison to the above continuous beamforming algorithms for IRS, the existing discrete beamforming algorithms lag somewhat in sophistication. Few attempts have been made for the discrete case to date. To achieve the global optimum, [32] uses the exhaustive search and [33] uses the branch-and-bound algorithm, neither of which is computationally scalable. The remaining works [24, 25, 26, 27, 28, 29, 30] typically relax the discrete constraint and then round the relaxed continuous solution to the closest point in the discrete constraint set, namely the closest point projection algorithm. However, this heuristic method can lead to arbitrarily bad performance as shown in this paper. We shall give a linear time beamforming algorithm with provable performance guarantees. The main contributions of the paper are two-fold:

Consider a pair of transmitter and receiver, along with an IRS that facilitates the data transmission between them. The IRS consists of $N$ passive reflective elements. Let $h_{n}\in\mathbb{C}$, $n=1,\ldots,N$, be the cascaded channel from the transmitter to the receiver that is induced by the $n$th reflective element; let $h_{0}\in\mathbb{C}$ be the superposition of all those channels from the transmitter to the receiver that are not related to the IRS, namely the background channel. Each channel can be rewritten in an exponential form as

with the magnitude $\beta_{n}\in(0,1)$ and the phase $\alpha_{n}\in[0,2\pi)$.

Denote the IRS beamformer as $\bm{\theta}=(\theta_{1},\ldots,\theta_{N})$, where each $\theta_{n}\in[0,2\pi)$ refers to the phase shift of the $n$th reflective element. The choice of each $\theta_{n}$ is restricted to the discrete set

with the distance parameter

Let $X\in\mathbb{C}$ be the transmit signal with the mean power $P$, i.e., $\mathbb{E}[|X|^{2}]=P$. The received signal $Y\in\mathbb{C}$ is given by

where an i.i.d. random variable $Z\sim\mathcal{CN}(0,\sigma^{2})$ models the additive thermal noise. The received SNR can be computed as

The baseline SNR without IRS is

The SNR boost is defined as

We seek the optimal $\bm{\theta}$ to maximize the SNR boost:

The above problem is difficult to tackle directly because of the discrete constraint on $\bm{\theta}$.

As $K\rightarrow\infty$, the discrete beamforming problem in (8) reduces to the continuous, in which case the SNR boost is maximized when every $h_{n}$ is perfectly aligned with $h_{0}$, so the optimal relaxed solution $\theta^{\infty}_{n}$ equals the phase difference between $h_{0}$ and $h_{n}$:

It is then tempting to believe that the problem becomes harder when $K$ decreases. But it turns out that the problem can be efficiently solved when $K=2$, as stated below.

Before proceeding to the proof of the above theorem, we first cast (8) to a quadratic programming form. By letting

we rewrite the problem in (8) as

where the matrix $\bm{C}=[C_{mn}]_{(N+1)\times(N+1)}$ is given by

It can be shown that $\mathrm{rank}(\bm{C})\leq 2$. We deal with the rank-one case and the rank-two case separately in the following.

This section considers the general $K$-ary phase beamforming in (8). We begin with a sectorization scheme in order to reduce the search space of the optimal beamformer. This new idea then yields a linear time approximation algorithm that guarantees performance within a constant fraction of the global optimum. It is further shown that the proposed algorithm has a tighter approximation ratio than the existing algorithms.

In this section we validate the performance of the proposed algorithms in simulations. The channel model follows the previous works [7, 29, 41]. The background channel $h_{0}$ is given by

where the transmitter-to-receiver pathloss $\mathsf{PL}_{0}$ (in dB) is computed as $\mathsf{PL}_{0}=32.6+36.7\log_{10}(d_{0})$, with $d_{0}$ in meters denoting the distance between the transmitter and the receiver, while the Rayleigh fading component $\zeta_{0}$ is drawn from the Gaussian distribution $\mathcal{CN}(0,1)$. The reflected channel $h_{n}$ is given by

where $\mathsf{PL}_{1}$ and $\mathsf{PL}_{2}$ are both based on the pathloss model $\mathsf{PL}_{0}=30+22\log_{10}(d)$, with $d$ in meters respectively denoting the transmitter-to-IRS distance and the IRS-to-receiver distance, while the Rayleigh fading component $\zeta_{n}$ is drawn from the Gaussian distribution $\mathcal{CN}(0,1)$ independently across $n=1,\ldots,N$. We use the following parameters unless otherwise stated. The transmit power level $P$ equals $30$ dBm. The background noise power level $\sigma^{2}$ equals $-90$ dBm. The locations of the transmitter, IRS, and receiver are denoted by the 3-dimensional coordinate vectors $(50,-200,20)$, $(-2,-1,0)$, and $(0,0,0)$ in meters, respectively. The number of reflective elements $N$ equals $200$. The channels are estimated via an ON-OFF strategy in [42].

Fig. 5 shows the cumulative distribution of the SNR boost for the binary phase beamforming case with $K=2$. When $N=100$, it can be seen that the proposed approximation algorithm “APX” outperforms the closest point projection algorithm “CPP”, especially in the low SNR boost regime. For instance, the 5th percentile SNR boost by APX is more than 2 dB higher than that by CPP. This performance gap remains when the number of reflective elements raises to 200. Moreover, we consider the quadrature beamforming case with $K=4$ in Fig. 6. Observe that APX and CPP now have similar performance. Thus, APX is more suited for the binary phase beamforming for IRS.

We further look into the low SNR boost regime by comparing the 1st percentile SNR boosts (i.e., the 1% lowest SNR boost across the random channel realizations) in Fig. 7. Different values of $N$ are considered here. The figure shows that APX outperforms CPP significantly in the low SNR boost regime when $K=2$. For instance, when $N=200$, APX improves upon CPP by about 5 dB. Observe that the gap between APX and CPP decreases with $N$. When $K$ is increased to $4$, the advantage of APX over CPP becomes marginal.

Fig. 8 shows how the reflected channel strength impacts the SNR boost. We put the IRS sequentially at the following 6 positions: $(-1,-1,0)$, $(-2,-1,0)$, $(-2.5,-1,0)$, $(-3,-1,0)$, $(-3.5,-1,0)$, $(-4,-1,0)$, so the reflected channel magnitude $\beta_{n}$ varies among these IRS locations, while the background channel magnitude $\beta_{0}$ is fixed. We evaluate the channel ratio $\beta_{0}/\beta_{n}$ for each IRS location. As shown in Fig. 8, the gap between APX and CPP in terms of the average SNR boost increases with $\beta_{0}/\beta_{n}$, in both the binary phase beamforming case and the quadrature beamforming case. Furthermore, Fig. 9 shows the low SNR boost performance with respect to the different values of $\beta_{0}/\beta_{n}$. The figure also suggests that the gap between APX and CPP becomes larger when $\beta_{0}/\beta_{n}$ is increased. Summarizing the above observations, we conclude that APX is more suited for the scenario where the reflected channels are relatively weak in comparison to the background channel.

The noise power $\sigma^{2}$ is fixed at $-90$ dBm in all the above simulations. We now raise $\sigma^{2}$ to $-50$ dBm and plot the resulting cumulative distributions of SNR boosts in Fig. 10. Due to more severe noise, the channel estimation becomes less accurate, and thus can spoil the IRS beamforming algorithms. Observe from Fig. 10 that APX is less affected by the increased noise as compared to CPP. Actually, APX is far superior to CPP when $\sigma^{2}=-50$ dBm, whereas the two algorithms are close when $\sigma^{2}=-90$ dBm. The tolerance to channel estimation error enables APX to perform much better than CPP in the presence of strong interference and background noise.

Despite the practical discrete phase value constraints for the IRS beamforming, this work shows that the optimal SNR boost can be reached by the proposed algorithm with a linear time complexity in the number of reflective elements, if the phase value is binary. For the general $K$-ary phase beamforming, we propose a linear time algorithm with a provable approximation accuracy, whereas the existing closest point projection algorithm can result in arbitrarily bad performance. Simulation results demonstrate the superior performance of the proposed approximation algorithm over the existing closest point projection algorithm in enhancing the received SNR, especially when channel estimation is error-prone because of interference and noise.