邓 旭,朱立东
(电子科技大学 通信抗干扰技术国家级重点实验室,四川 成都611731)
随着无线通信技术的发展,人们对卫星提供高速率、低时延、大容量的多媒体业务提出了更高要求。对卫星通信系统而言,无线资源管理与分配的关注点在多用户分布和多业务分配不均的情况下,如何解决资源共享,如何提高卫星通信系统的资源利用率,如何使卫星通信系统拥有更好的性能成为人们亟待解决的问题[1]。传统资源分配技术已难以满足人们日益增长的多媒体业务服务质量需求,原因在于该技术在新呼叫阻塞率和切换呼叫失败率之间进行权衡考虑,一方面失败率的降低意味着另一方面失败率的提高。因此,针对多用户场景下卫星通信网络资源分配问题,提出匹配博弈新策略,力求满足多业务的服务质量要求。
有关信道分配资源算法的研究除了传统波束信道分配策略外,现有的算法研究有凸优化算法[2]、贪心算法[3]和基于博弈论的算法[4]。基于博弈论的算法运用比较广泛,其中包含非合作博弈和匹配博弈算法等。在解决资源分配问题方面,SONG L提出了非合作博弈算法,该算法虽然能有效解决资源分配问题,但是资源匹配单边不稳定[5],所以有关信道资源分配算法的研究,本文把重点放在以匹配为基础的双边稳定博弈算法。
匹配博弈的最初目的是为了解决市场因缺乏稳定而失灵的问题,通过匹配即市场间交换的本质,使双方经济效益达到最大化。匹配博弈根据匹配关系,可以将其分成一对一[6]、多对一[6-7]、多对多匹配[8]关系。2012年匹配理论的创立者Alvin E.Roth[9]凭借这一贡献获得诺贝尔经济学奖。随着匹配博弈理论的发展,该算法思想不再局限于经济学领域,越来越多的研究者将其运用到无线通信领域来解决无线资源分配问题。
ZHOU Z Y等人基于D2D通信资源分配问题,结合多对一的匹配博弈算法,采用迭代方法对频谱和功率进行联合分配,数值结果验证了该算法在各种仿真场景下的有效性和优越性[10]。ZHAO J将提高系统吞吐量作为研究对象,提出多对多匹配博弈用以解决D2D的资源分配算法,该算法表明在有限的迭代次数范围内可以收敛到双边交换稳定匹配,并加以证明该算法性能明显优于一对一匹配算法[11]。此外,姚天等人就如何实现用户与网络资源间有效匹配问题上充分考虑用户公平性,采用多对多和多对一双层匹配博弈加以求解,通过引入随机匹配和最优化匹配对比,验证该算法具有良好的收敛性、有效性和可行性[12]。时国维等人提出2层多对一匹配博弈算法,经研究结果表明该算法能使资源匹配变稳定,有效解决存储系统中的资源分配问题,并有效降低系统时延。为了进一步优化资源分配问题,提出了3层多对多的资源分配方案,经仿真结果表明,该算法能实现传输延迟最小化和社会效益最大化[13]。
多层资源分配网络结构如图1所示。假设存在I个MEO卫星,J个LEO卫星,P个基站数以及平均每个基站有Q个用户数。M={M1,M2,…,MI}表示I个MEO卫星集合,L={L1,L2,…,LJ}表示J个LEO卫星集合,B={B1,B2,…,BP}表示P个基站数集合。
匹配过程分为3个阶段:第1阶段为MEO卫星层与LEO卫星层之间星间链路的建立。LEO/MEO双层卫星网络系统可发挥LEO卫星传输时延短及损耗小等特点[14-15],简化LEO卫星结构以及降低其建设成本;同时在卫星网络中起到传输、转发和管理功能的MEO卫星结构简单,有利于简化路由设置,减少信息开销和信息交换时延等功能,通过将LEO/MEO卫星之间的优势互补可实现天基网发展的一种理想组网模式[16]。除了不同轨道间星间链路建立,还要在同轨道进行链路建立,通过建立好的星间链路实现卫星与卫星之间的信息数据交互。第2阶段为卫星与地面基站的星地链路建立。卫星与地面网络可以看作一个整体,它们通过星地激光链路相互连接,在此过程不仅可发挥卫星覆盖面积广、大容量通信等特点,还可发挥地面光通信速率快、可靠性高等特点,它们之间互为补充可增强整个网络的生存能力[17-18]。第3阶段为基站与用户之间的匹配问题。由于基站与基站之间的覆盖面积有重叠区域,而且每个基站覆盖的大小和用户分布都不均匀,为了简便该层匹配模型,将所有基站看成是一个大的资源池,所有用户对资源池里的资源块进行使用,在一定程度上可对其分配模型进行简化。
图1 网络匹配模型
在该系统模型构建下主要解决3个问题。第1个问题是不同轨道之间星间链路的建立;第2个问题是卫星与地面基站星地链路的建立;第3个问题是基站与用户之间的资源匹配。3层匹配之间相互联系,前面的匹配博弈结果将影响后边的匹配决策判断,匹配框架如图2所示。
图2 匹配框架
在星间链路中电波传播主要考虑自由空间传播的影响,由于不存在大气层等其他附加损耗的影响,相对应的自由空间传播损耗公式为:
LMEO-LEO=92.44+20lgd+20lgf,
(1)
式中,d为MEO卫星和LEO卫星之间的距离,单位km,f为卫星的工作频段,单位GHz,LMEO-LEO表示MEO卫星与LEO卫星之间的自由空间传播损耗。
由此得知MEO卫星与LEO卫星之间的信道增益可表示为:
GMEO-LEO=10-(LMEO-LEO/10)。
(2)
星地链路传播损耗除了自由空间传播损耗外,还存在其他附加损耗。对于自由空间损耗与式(1)类似,则星地链路传播损耗公式为:
LLEO-BS=92.44+20lgd+20lgf+Lrest,
(3)
式中,Lrest包括雨衰及大气层吸收等附加损耗。则星地链路间的信道增益为:
GLEO-BS=10-(LLEO-BS/10)。
(4)
对于基站与用户之间的链路连接问题,可将链路损耗视为服从高斯分布,其概率密度函数服从瑞利分布[9],则基站与用户之间的链路增益可表示为:
GBS-MS=βd-η|h|2,
(5)
式中,β为信道参数,d为用户与基站间的距离,η为路径衰落指数,而h遵循h~CN(0,1)的复高斯信道参数。
多对多匹配模型下每个MEO卫星能与多个LEO卫星建立链路连接,假设每个MEO卫星平均发射总功率为Q,则第i个MEO卫星在链路建立上平均分配其功率为:
(6)
同理,每个LEO卫星也可以与多个MEO卫星建立链路连接,则第j个LEO卫星在链路建立上平均分配功率可表示为:
(7)
结合式(6)和式(7),分别得到LEO卫星和MEO卫星接收到的信噪比γi,γji为:
(8)
(9)
式中,Gij为第i个MEO卫星到第j个LEO卫星的增益,Gji为第j个LEO卫星到第i个MEO卫星的增益。为了方便计算,假设Gij=Gji。此外,N0表示接收端的噪声功率,可表示为:
N0=-228+10lgT+10lgBMEO-LEO,
(10)
式中,BMEO-LEO为MEO卫星和LEO卫星之间的传输带宽,T为接收机的等效噪声温度。
结合式(8)和式(9),第i个MEO卫星和第j个LEO卫星的传输速率为:
ri=BMEO-LEOlb(1+γi),
(11)
rji=BMEO-LEOlb(1+γji)。
(12)
在匹配博弈中,为了评估参与对象博弈匹配中的整体满意度,需要在特定模型和特定应用下设计合理的效用函数来反映其满意程度,用U1表示MEO卫星层与LEO卫星层之间的系统总体效用值,通过MEO卫星与LEO卫星总的吞吐量对其进行描述。其相关定义如下:
(13)
此外,对于上述公式存在一些限定条件,相关定义如下:
xijγji≥xijγjimin∀i,j,
(14)
γi≥γimin∀i,
(15)
xij∈{0,1} ∀i,j∈{1,2,…,J},
(16)
(17)
(18)
式(14)和式(15)中,γjimin,γimin表明MEO卫星与LEO卫星所接收到的最小信噪比,且在接收过程中信噪比不能低于最小信噪比,否则星间链路建立失败;式(16)表明,xij只能取0或1;式(17)表明对于任意LEO卫星最多只能与pmax个MEO卫星进行链路连接,式(18)表明对于任意MEO卫星最多只能连接qmax个LEO卫星,若超过则选择偏好列表前qmax个卫星进行连接。第2层和第3层的效用值U2,U3求法与第1层求法类似,可求得3层匹配模型下的最优效用值为:
Uall=U1+U2+U3。
(19)
匹配博弈通常涉及到2个集合间的匹配关系问题,在所提匹配博弈中MEO卫星、LEO卫星、基站和用户被看作是参与匹配博弈的4种不同参与者,并假设四者之间相互独立。
在第1层匹配博弈中,MEO卫星和LEO卫星被看作是双方参与者,数据业务的传输需要在二者之间建立星间链路,每颗MEO卫星不仅能与多颗LEO卫星建立星间链路连接,而且每颗LEO卫星也能建立多条链路与MEO卫星连接,因此该匹配模型可看作是多对多匹配。
μ1是集合M∪L到集合2M∪L的映射,对于∀Mi∈M,Lj∈L有:
① |μ1(Mi)|={L1,L2,…,Lj},|μ1(Mi)|≤J,并且当μ1(Mi)∉L时,μ1(Mi)=Mi;
② |μ1(Lj)|={M1,M2,…,Mi},|μ(Lj)|≤I,并且当μ1(Lj)∉M时,μ1(Lj)=Lj;
③ 当且仅当μ1(Mi)=Lj时,μ(Lj)=Mi。
条件①表示Mi卫星可以和一个或多个LEO卫星进行链路连接,并规定Mi卫星最大链路连接不能超过LEO卫星总数,若μ1(Mi)=Mi则表示Mi卫星没有链路连接;同理条件②表示Lj卫星可以和一个或多个MEO卫星进行链路连接,Lj卫星最大连接数不大于MEO卫星总数,若μ1(Lj)=Lj,则Lj卫星没有链路连接;条件③表示当Mi卫星和Lj卫星的双向选择。
在第2层匹配博弈中,匹配双方参与者为LEO卫星和BS基站。与第1层匹配类似,该层匹配双方之间的偏好列表根据传输环境及空地间距等综合考虑。每颗LEO卫星可以与多个基站进行星地链路连接后传输业务数据,而每个基站转发数据信息到多颗卫星上,因此该层匹配也可视为多对多匹配模型,与第1层定义类似,这里不做重复介绍。
在第3层匹配博弈中,将所有基站中总信道资源视为一个资源池,用户对资源池中的资源块进行使用。每个用户可以和一个或多个资源块进行连接,但是一个资源块在同一时刻只能被一个用户使用,因此该匹配模型为多对一匹配。μ3是集合RB∪MU到集合2RB∪MU的映射,对于∀RBr∈RB,MUk∈MU,满足下列条件:
① |μ(RBr)|={MU1,MU2,…,MUk},|μ(RBr)|≤1,并且当μ(RBr)∉MU时,μ(RBr)=RBr;
② |μ(MUk)|={RB1,RB2,…RBr},|μ(MUk)|≤K,并且当μ(MUr)∉RB时,μ(MUk)=MUk;
③ 当且仅当μ(RBr)=MUk时,μ(MUk)=RBr。
条件①表示一个资源块最多只能被一个用户使用,若μ(RBr)∉MU则表示该资源块没有匹配对象;条件②表示一个用户可以和一个或多个资源块进行连接使用,并且规定一个用户最大使用资源块数不能超过总资源块数;条件③表明RBr,MUk之间的双向匹配。
根据MEO卫星与LEO卫星之间的多对多匹配关系建立相应的匹配博弈算法,如算法1所示。在开始阶段输入βj,βi偏好列表,并限定每颗MEO卫星的配额为QL,每颗LEO卫星的配额为QM。MEO卫星根据自己的偏好程度给LEO发送连接请求,然后LEO卫星根据自己的偏好列表选择前QM颗MEO卫星相连接并拒绝其他请求。如果此时MEO卫星还有多余的连接空间,则将继续留在Θ1中,否则将从Θ1中删除并计算当前的U1效用值。最后依次循环直到未匹配集合Θ1为空。第2层和第3层算法思想与第1层类似,这里不做重复介绍。
算法1 第1层多对多匹配算法
输入:MEO卫星的偏好列表βj,配额QL;LEO卫星的偏好列表βi,配额QM。
输出:稳定匹配μ1和效用值U1。
1:创建MEO卫星未匹配集合Θ1={M1,M2,…,Mi};
2:whileΘ1≠∅ do
3: for allMi∈Θ1do
4: 根据偏好列表βj向LEO卫星发送链路连接请求,并使xij=1;
5: 将βj中的最偏好元素移除;
6: end for
7: for allLj∈Ldo
8: if∑i=1xij>QM
9: 根据βi选择QM个最偏好的MEO卫星建立连接,拒绝其他请求;
10: 被拒绝的MEO卫星的xij=0;
11: else
12: 与当前的MEO卫星建立链路连接;
13: end if
14: end for
15: for allMi∈Θ1do
16: if∑j=1xij>QL
17: 将Θ1中的Mi移除
18: end if
19: end for
20:计算当前U1效用值;
21:end while
为了验证3层多对多匹配博弈算法的有效性,通过Matlab对其进行仿真,具体参数如表1所示。
表1 系统仿真参数
参数取值MEO高度/km10 355星间最大发射功率/W27星间链路ISL频段/GHz 30星间链路带宽/MHz 100星间链路接收发射天线总增益/dB68MEO最大复用数2LEO高度/km1 414LEO最大发射功率/W19.95LEO频段/GHz14.5星地链路带宽/MHz32星地链路接收发射天线总增益/dB19.5LEO最大复用数2星地链路附加损耗Lrest/dB2基站带宽/MHz10基站最大发送功率/dBm23基站最大复用数2小区半径/m500路径衰减指数α4路径衰减常数β0.02用户接收端噪声功率N0/dB-134用户最大复用数2最大迭代次数30地面接收发射天线总增益/dB17.5
图3表示LEO卫星个数为6、基站个数为10、平均每个基站用户数为20时系统总体效用值QoE随MEO卫星个数不同而变化的曲线;图4表示MEO卫星个数为3、基站个数为10、平均每个基站用户数为20时系统总体效用值QoE随LEO卫星个数不同而变化的曲线;图5表示MEO卫星个数为3、LEO卫星个数为6、平均每个基站用户数为20时系统总体效用值QoE随基站个数不同而变化的曲线。
由图3~图5可以看出,随着MEO卫星、LEO卫星或是基站个数的增加,系统的总体效用值都在逐步增加,这是因为个数的增多会使其他参与者获得更多的分集增益,并且有更多的机会成功参与到资源分配当中,从而提高系统总的吞吐量,与理论分析一致。随着迭代次数的增加,3条曲线呈不断上升的趋势,并最终趋于稳定,证明了匹配博弈的有效性及稳定性。
图3 QoE随MEO卫星个数变化
图4 QoE随LEO卫星个数变化
图5 QoE随基站个数变化
图6表示MEO卫星个数为4、基站个数为10、平均每个基站用户数为20时3种匹配博弈算法的系统总体效用值QoE随LEO卫星个数的变化曲线。图7表示MEO卫星个数为3、LEO卫星个数为4、平均每个基站用户数为20时3种匹配博弈算法系统总体效用值QoE随基站个数的变化曲线。图8表示MEO卫星个数为3、LEO卫星个数为4、基站个数为8时3种匹配博弈算法系统总体效用值QoE随用户个数的变化曲线。
图6 3种算法随LEO卫星个数变化
图8 3种算法随用户个数变化
由图6和图7可知,随着LEO卫星个数和基站个数的增多三者算法的QoE呈正相关,很好地验证了匹配博弈的有效性;从图8中可看出随着用户数量的增多三者算法的QoE在逐渐减少,当用户数目逐渐增多时,每个用户所获得的频谱资源不断减少。当用户数增长到一定程度后,由于资源是固定不变的,最终能匹配到的用户数有限,因此最终的QoE会逐渐趋于稳定。由图6~图8可以看出,多层多对多匹配博弈的QoE始终比其余2种高,这也很好地说明了多对多匹配博弈能更好地提高社会效益,使通信系统拥有更高的资源利用率。
针对多用户场景下的网络资源分配问题,不同于传统波束信道资源分配策略,本文提出一种新的资源分配策略——匹配博弈,在建立MEO卫星、LEO卫星、基站和用户四者之间多层多对多匹配博弈模型下,根据系统目标函数设计相应的匹配博弈算法,从效用函数的角度对其进行求解。通过引入多层多对一匹配和多层一对一匹配算法,从匹配博弈的稳定性、有效性和收敛性等性能指标入手,与多层多对多匹配博弈进行对比,仿真结果表明多层多对多匹配博弈策略能有效解决资源分配问题,并使卫星通信系统拥有更好的社会效益和更高的资源利用率。