离散相移约束下的智能反射面最优波束赋形方法

Yaowen Zhang, Kaiming Shen, Shuyi Ren, Xin Li, Xin Chen, Zhi-Quan Luo

关键词：智能反射面，离散波束赋形算法, 线性时间复杂度，全局最优, 近似比.

1.背景介绍

智能反射面（IRS）由大规模无源反射阵列构成，其中每块反射单元引入一条反射信道，并通过操纵该信道的相移参数来实现对信号传播环境的优化性重构，从而改善无线通信质量。在现实中由于IRS的制造工艺所限，相移参数往往要从一个离散集合中选取，例如{0, pi/2, pi, 3*pi/2}。这会导致相移参数的寻优，也就是波束赋形优化，成为一个离散问题，而离散问题通常具有高难度，甚至是NP困难。在现有文献中，为了解决离散相移约束下的IRS波束赋形问题，人们常使用的优化方法包括穷举搜索法，分支定界法，以及最近点投影算法（CPP）。穷举搜索法和分支定界法具有指数时间复杂度而无法适用于大规模场景。CPP的主要思路则是先把离散优化问题松弛成一个连续优化问题，进而将连续解投影到离散集，但它本质上是一种启发式算法，其性能无法从理论上获得保障。

本文创新地提出了线性时间复杂度的IRS离散波束赋形算法来最大化接收端的信噪比（SNR）。当离散约束为二元集时，即相移选项为{0, pi}，我们从理论上证明了该算法可以达到全局最优；而对于一般K>2元集离散约束，所提算法可以确保达到全局最优的75%以上。

2.问题描述

我们考虑IRS辅助下的点对点通信场景。IRS包含个反射单元。我们用hn来表示第n个反射单元所引入的反射信道，用h0来表示发射端与接收端之间的直射信道，其中每个信道都可以表示成极坐标形式：

对于第n个反射单元，我们用θn变量来表示它的相移值，所有相移值组成波束赋形向量θ=(θ1,...,θn)。此外，每个相移值θn被局限在如下离散集合

其中的间隔长度ω定义为

我们考虑“信噪比增益”，也就是有IRS辅助的SNR与无IRS辅助的原始SNR0之间的比值：

我们的目标是通过优化波束赋形向量来实现信噪比增益的最大化：

特色与难点：在现有文献中，以上离散波束赋形问题被普遍认为需要指数时间复杂度才能获得全局最优，但这里我们指出一个重要发现：在二元约束情况下该离散问题仅需线性时间复杂度即能找到全局最优！另外在一般K元约束下，我们可以确保达到全局最优的75%以上。

3.二元离散约束下的波束赋形算法

首先，我们做如下变量替换

进而将原问题（8）转换成一个二次优化问题：

这时注意到矩阵C的秩不超过2，换言之矩阵C的秩或为1或为2。以下分类讨论：

1)当矩阵C的秩为1时，所有的反射信道hn均与直射信道h0在复平面上正向或反向对齐，这时仅需选取相移值使得所有信道正向对齐即可达到全局最优。

2)当矩阵C的秩为2时，我们先把每个复数信道参数表示成一个二维实数向量：

然后使用Cauchy-Schwartz不等式将原问题（8）转换为

接下来的关键步骤是注意到新目标函数g(y)具有分段式线性结构，我们所提算法的大致思想是通过分段搜索在线性时间内找到全局最优解。更多技术细节可参考论文的Section III。

4.K元离散约束下的波束赋形算法

现在考虑一般性K元约束问题。我们首先在直射信道h0附近划分四个同尺寸的扇形，每个扇形的角弧度为ω/2。可以证明，最近点投影算法（CPP）的本质是让每个反射信道尽可能地靠近直射信道，因此CPP算法将导致所有反射信道最后都落在最接近直射信道的两个扇形区域，如下图中的阴影部分，即扇区S2与S3。

CPP算法是一种启发式方法，其最优性无法保障。在论文中第4页的Example 1，我们甚至给出了一个极端例子使得CPP算法的性能无限接近于0。问题出在我们根本没有必要把所有反射信道局限于距离h0最近的两个扇区。换个思路，我们同样可以假设所有反射信道都落在h0上方的两个扇区S1与S2，抑或都落在下方的两个扇区S3与S4。将以上两种扇形组合方案加上CPP的扇形组合方案，我们总共可以得到三组波束赋形解，如下图所示： 

我们之所以仅考虑以上三种扇形组合方案，是为了在兼顾最优性的同时把搜索范围控制在线性规模以内。最后，我们比较上述三组解，选出最优者作为最终解，即新提出的APX算法。在理论分析方面，我们通过一系列精巧的上下界放缩，在原文第6页证明了APX算法能达到全局最优的以下常数近似比（approximation ratio）：

下图展示了当取不同值时各个算法所达到的常数近似比。可见新算法APX远比其它常规算法（包括最近点投影算法CPP，半正定松弛算法SDR）更接近全局最优。

还值得一提的是，我们已将APX算法推广至多用户场景，这部分内容在原文第7页进行了讨论。

5.仿真结果

我们的仿真实验假设信道为瑞利信道，采用on-off方法来估计信道。除了最近点投影算法CPP，半正定松弛算法SDR，以及新提出的APX算法，我们还考虑以下现有算法用来比较：

 

• 图5展示了当K=2,N=200时不同算法的信噪比增益CDF曲线，可以看出APX与其他算法相比有明显优势，特别是在SNR Boost较低的区域。

• 图9展示了当信道估计的噪声为-50dBm时，不同算法的SNR Boost CDF曲线。可以看出APX要显著好于其他算法。

• 图15 比较了不同算法的运行时间。可以看出APX与CPP算法的时间远远少于SDR方法和GNN的方法。这里GNN的训练时间没有计入在内，其训练通常需要若干个小时。

• 图16展示了四个用户情况下不同算法的信噪比增益CDF曲线。APX算法优于其他算法。

6.总结

在实际中我们往往需要在离散相移约束下来优化IRS波束赋形。尽管现有文献普遍认为该离散问题具有指数时间复杂度，我们发现在二元约束下仅需线性时间就能获取全局最优解。而对于一般元约束情况，我们提出了名为APX的新算法，并证明了它具备接近1的常数近似比，更进一步将其推广到了多用户场景。无论是理论分析还是仿真结果，我们都展示了新算法APX远优于现有算法，它特别适用于信道估计误差较大或者信噪比偏低的应用场景。

论文引用：

Y.Zhang, K. Shen, S. Ren, X. Li, X. Chen and Z.-Q Luo, “Configuring intelligent reflecting surface with performance guarantees: Optimal beamforming”, IEEE Journal of Selected Topics in Signal Processing, 2022.

论文链接：

https://kaimingshen.github.io/doc/OptimalBeamforming.pdf

点击文末左下角“阅读原文“或点击下方小程序可以直接查看原文：

Configuring Intelligent Reflecting Surface with Performance Guarantees: Optimal Beamforming

代码链接

https://kaimingshen.github.io/doc/IRS.zip

【学校简介】

香港中文大学（深圳）是一所经国家教育部批准创办的中外合作大学，学校沿用香港中文大学的办学机制和学术水准，同香港校区同属一个品牌，深圳校区学生毕业将颁发香港中文大学学位。大学已从全球范围内吸引了众多杰出的学者及研究人员，包括多位诺贝尔奖获得者和各国院士。

学校主页：https://www.cuhk.edu.cn

【深圳市大数据研究院】

深圳市大数据研究院，是在深圳市委、市政府的支持下于2016年3月组建成立的市属二类事业单位，其前身是香港中文大学（深圳）副校长罗智泉教授领衔的大数据信息处理及应用孔雀团队。2019年研究院正式授牌成为深圳市基础研究机构之一，是香港中文大学（深圳）的附属机构。

研究院以数学为基础，以大数据为驱动，以重大应用为导向，聚焦大数据基础理论与核心算法、大数据通用软件与技术、大数据驱动的智能应用技术三大方向进行理论研究和技术攻关，打造世界级的大数据研究机构和协同研发平台，服务于国家大数据发展战略，推动整合深圳市、粤港澳大湾区大数据科研和产业。

研究院主页：http://www.sribd.cn