一个新颖的异构无线网络接入选择算法

崔 扬，徐玉滨，许荣庆，沙学军

(哈尔滨工业大学通信技术研究所，150080哈尔滨，cuiyang_0305@163.com)

目前在无线接入领域中出现了大量使用不同无线接入技术和不同覆盖面积的无线接入网络.因此未来的无线通信网必将是异构的[1－2].为了在任何时间、任何地点都能够获得无缝的最佳服务，终端需要不断地在不同的无线接入网之间进行接入选择和垂直切换，因此异构网络的接入选择算法至关重要.文献[3－5]提出了基于门限的接入选择算法.文献[6－8]提出了基于智能处理的接入选择算法.这些算法在不同程度上都提高了用户的QoS满意度，同时允许系统容纳更多的用户.通过对上述文献研究可以发现，首先上述算法在接入选择中均没有考虑到网络的资源分配方式这一因素，其次这些算法着眼点都是对接入选择算法的改进、考虑因素的增多或是某几项性能指标的提升，都缺少对终端用户接入选择行为的合理解释.对每个网络来说所有用户共享资源，每个用户实际获得速率除了取决于接收信号的质量和RAT的特性外，还取决于网络为其分配资源的多少有关，因此有必要考虑网络的资源分配方式.另外，从系统角度出发，整个异构无线网络以最大化网络吞吐量为目标控制各个终端用户接入到相应的网络中;但这样往往使得部分用户由于获得较低的数据速率而无法得到更好的服务质量，以至于常常无法适用于实际系统.对于所有的用户终端来说，其目的都是想在现有的条件下选择1个能为其提供最高数据速率的网络进行接入，由于无线资源的有限性，这种行为也就导致了用户之间对于资源的获取是相互竞争的.对于1个终端来说，其他终端的接入选择结果将会影响自身最终的选择，所以有必要对异构无线网络中的接入选择问题引入新的研究方法和理论，值得庆幸的是，非合作博弈理论可以为该研究提供坚实的理论基础.非合作博弈论近些年被应用于解决无线网络资源管理的问题中[9－11].文献[12]和文献[13]分别利用进化博弈和非合作博弈解决异构无线接入选择问题，但都没有考虑到用户的信道条件和资源的分配方式，因此无法应用于实际网络中.本文提出了1个基于非合作博弈的接入选择算法:首先依据用户实际的接收信号质量、RAT特性以及网络的资源分配方式求出用户接入网络的实际速率，然后以最大化自身数据速率为目标建立基于非合作博弈理论的接入选择模型，并利用纳什均衡预测接入选择结果.

1 系统模型和实际接入数据速率

1.1 系统建模

本文选取3种具有代表性的无线接入网络来构成异构无线接入环境，如图1所示.其中WMAN选用的是基于IEEE 802.16且具有单载波接口的WiMAX[14]，蜂窝网采用的是 3GPP 的 HSDPA[15]，局域网采用的是基于IEEE 802.11的WLAN[16].为简化分析，本文选取了如图1下半部分所示的特例，其中这三种无线接入网络的基站中心相互重叠，该结构稍加改动就可以扩展为图1中上半部分的形式.将终端所处的位置按照可接入的网络数量进行划分，大致分为3个服务区.在区域1中，只有WMAN的网络覆盖，所以位于该区的用户只能接入WMAN中.而在区域2中的用户，由于其同时位于WMAN和蜂窝网的覆盖区，用户可以选择接入到这两个网络中任意1个.依据相同的道理，位于服务区3的用户可以接入WMAN、蜂窝网和WLAN这3种网络.其中位于这3个服务区的用户数分别为N1、N2和N3.从节省能量的角度考虑，规定所有终端在任意时刻只能接入到1个网络中.为了方便起见，WMAN、HSDPA和WLAN这3种网络分别简记为WM、CE和WLAN.

图1 异构网络的组成

1.2 实际接入数据速率

对于接入选择来说，首先要对终端所选择的无线接入链路的性能进行定量评估.而决定1个终端接入链路的性能主要有以下3个因素:

1)接收信号的质量.它可以用信干比(SINR)来进行描述，其物理意义是，发射功率减去传播衰落后与接收端的噪声和其他信号的干扰之和相比.其中传播的衰落是由3部分组成的，第一部分是与传播距离成指数关系的路径损耗，第二部分是与地形有关的阴影衰落，前两个为大尺度衰落，第三部分是由于信号多径传输所造成的小尺度衰落.这三种衰落相互叠加构成了整个信号的衰减.

2)RAT的特性，例如信道带宽和频谱效率.对于使用多个接入链接的终端来说，每条接入链路的信干比SSINR都可以独立计算.在获得接收信号的SSINR后，要想获得每个接入链路的实际速率，还需要知道每个RAT的特性，例如信道带宽和频谱效率.文献[17]基于对信息论中的香农定理的修改提出了RAT性能的一般描述.这个描述提供了对实际RAT特点的简单近似，为研究异构网络的资源管理带来了便利.于是任意1个RAT的容量均可由下式描述:

其中:B为载波的带宽;SSINR为信干比，其具体值与用户位于各个RAT小区中的位置有关;ΔSSINR为衰落因子，其实际值大约为10 dB左右;εmax为最大的频谱效率，它由每个RAT具体使用的最高调制与编码技术方案有关.因此利用式(1)可以对无线接入技术的近似容量做一般性的建模.

3)资源分配方式和负载状态.式(1)描述了系统中单一用户完全占有所有资源获得的信道性能，即峰值速率.但实际系统中用户不止1个，用户之间需要共享资源.用户实际获得的资源大小往往和资源的分配方式及当前负载状态有关，而目前的所有文献中均没有考虑到这一因素.因此当负载一定时，资源的分配方式将决定用户接入网络后的实际速率.为了说明这一问题，本文将考虑两种典型的资源分配方式:集中式和分布式.对于集中式，每个用户实际得到的数据速率为Ri(M)=CiG/N. (2)其中G为调度增益，它与具体每个网络所使用的调度算法有关.例如当网络使用公平比例算法时，调度增益与所有用户的链路质量分布有关;当使用的是Roubin调度算法时，该值为1.N为当前在该系统中的用户数，Ci是用户i的峰值速率.目前的2G/3G以及未来的LTE系统均采用集中式的资源分配.假设接入网络使用Roubin调度算法进行资源分配，那么式(2)则变成

而对于分布式，例如基于IEEE 802.11的WLAN，其一般使用的媒体接入协议(MAC)是基于冲突避免的多载波感知协议(CSMA/CA).于是用户接入到WLAN网络中的实际速率为[18]

2 基于非合作博弈论的接入选择建模

在异构无线网络中，整个网络是由多个不同的无线接入网以及终端用户组成的.这些终端用户相互竞争资源，在这种情况下1个全局优化的解可能对于所有的实体来说并不是其想要的.例如使整个网络的吞吐最大的解，不一定是使每个终端用户都能满意的解，因为为了使整个网络的资源最大化，可能将更多的资源分配给信道条件最好的用户，这使一些信道条件差的用户无法得到服务或提供的服务无法满足要求.为了解决上述问题，本文引入非合作博弈论来研究异构网络中的接入选择问题.在异构网络中的每个终端用户都会选择1个为其提供最高数据速率的网络进行接入，因而所有终端都是理性的.

在非合作博弈中，博弈理论的基本概念包括参与者、策略、行动、收益、信息、结果和均衡[19].其中参与者、策略和收益是非合作博弈不可缺少的3个要素.参与者指的是博弈中的决策主体，其目的是选择使自己收益最大化的策略;策略指参与者依据给定的信息的行动规则，它规定了参与者何时选择何种行动;收益指的是参与者在某一策略组合下所能获得的好处，该值通常由1个效用函数表示，效用函数值越大，其收益也就越大.

由于区域1中的用户只能接入到WM网络中，因此本文只将区域2和区域3中的用户作为博弈中的参与者.参与者i的策略pij(pi∈Pi)，指的是选择哪种网络接入，Pi为参与者i所有策略的集合，即所有可以选择的接入网络的集合.例如pi=wm，表示这个用户选择WM进行接入.用户之间由于地理位置不同，所以每个用户可以选择接入的网络数量不同，位于区域2和区域3中的用户策略集合分别为

其中:U为1个拟凹的效用函数;X表示一次博弈的策略组合;Ri为用户i在策略组合X下获得实际速率.本文引入纳什均衡来预测各个用户终端以自我收益最大化为目的的接入选择结果.纳什均衡是非合作博弈的一种状态，对于有N个参与者的博弈，在给定其他人策略的条件下，每个参与者选择自己的最优策略从而使自己利益最大化.所有参与者的策略构成1个策略组合.纳什均衡指的是由所有参与者的最优策略组成的策略组合，即在纳什均衡的情况下，没有任何参与者可以通过改变策略来提高自身的收益.其具体定义如下[19]:

其中X*为N个参与者的最优策略，X*pi表示只有参与者i改变策略组合X*中自己的策略.

3 求解纳什均衡

纳什均衡的定义本身并没有说明怎样求解纳什均衡，它只是用来检验某个策略组合是否是纳什均衡.因此在建立博弈模型后，需要借助其它的优化算法来求解.当博弈中的参与者数量很少，而且每个参与者的策略数量有限时，可以通过穷举法或剔除劣策略法来找到纳什均衡.但当用户数较多以及策略空间较大时，就无法通过这些方法得到纳什均衡，如本文中当区域2和区域3中的用户数达到5和10时，整个策略空间大小为1 889 568.因此需要借助于智能优化算法来进行求解.

粒子群优化算法是一种基于群智能的进化计算技术，由 Eberhart和 Kennedy[20]提出.与蚂蚁算法相比，粒子群算法对初始化参数的设置不敏感，且具有较好的收敛性;与遗传算法相比，在相同性能要求下，有较快的收敛速度和较好的收敛性能.基本的粒子群算法是应用于连续优化问题的，但许多实际的工程问题都被描述为组合优化问题，于是Kenedy和Eberhart[21]提出了一种基于二进制离散粒子群算法，随后Yang和Wang[22]受到物理学的启示提出了离散量子粒子群优化算法.由于在所建立的博弈模型中，某些参与者的可选择策略多于2种，例如区域3中的用户可以选择接入的网络数量达到了3种，因此本文选择使用离散量子粒子群算法进行求解.

在离散量子粒子群算法中，定义量子粒子群向量及其离散粒子向量分别为

其中α和β为量子粒子Q的控制参数，且满足α+β=1和0＜α，β＜1;α越大，Q越靠近其理想值;Zglobalbest(t)为到目前t代为止，在整个粒子群中使得适应度函数值最小的离散粒子，其为全局最优粒子;Zk

localbest(t)为到目前t代为止，第k个粒子使得适应度函数值最小的离散粒子，其为局部最优点;ω、c1和c2表示下一代Q的产生依赖于自己、局部最优和全局最优的程度，满足如下关系:

为了能够利用离散量子粒子群算法求解接入选择模型的纳什均衡，需要将模型中的策略以离散量子粒子群中二进制数的方式来表示，具体如下:位于区域2中的用户能够选择WM和CE中的任意1个网络进行接入，而位于区域3中的用户可以选择WM、CE和WL中的任意1个网络进行接入，因此对这两个区域中用户的策略分别用1个两位和三位的二进制数表示，其中二进制数中的每一位对应1个网络的选择情况.区域2中用户的二进制数从高比特位到低比特位分别对应WM和CE;区域3中用户的二进制数从高位到低位分别对应WM、CE和WL.如果对应位上的比特数为1，则表示接入该网络;为0则表示不接入该网络.因此如－果位于区域2中的用户策略pi=wm，那么它对应的两位二进制数为(1 0)，同理当区域3中用户的策略为pi=ce时，它对应的二进制数就为(0 1 0).于是将区域2和区域3中所有用户策略二进制数依次连接就组成了1个大小为1×(N2×2+N3×3)的二进制向量.这样就将策略组合X与离散粒子Zk建立起了对应关系，于是对于纳什均衡策略的寻找就可以转化为寻找使某一适应度函数最小的离散粒子.

根据纳什均衡的定义建立离散量子粒子群算法的适应度函数，其定义如下:如果X为有效策略，

如果X为无效策略，

其中

通过式(6)产生的离散粒子向量可使一些用户策略的二进制向量中出现所有比特位均为0或为1的比特位数量超过1个的情况.这就意味着这些用户要么不接入任何网络，要么同时接入的网络数量超过1个，这与系统的假设模型不符.于是这样的离散粒子对应的策略组合X是无效的.为了避免结果为无效的策略组合，当出现这样的无效离散粒子向量时，其对应的适应度函数值将变为常数L，这个常数L的值远远大于所有有效策略组合的适应度函数值.由于离散粒子趋向于使适应度值为最小的方向变化，这样可以确保离散量粒子不会向无效向量趋近，进而避免结果为无效策略组合.根据纳什均衡的定义及性质就可以知道，当且仅当策略X为纳什均衡解X*时，适应度函数取最小值0.

离散量子粒子群算法的工作流程如下:

1)随机初始化Q(t)和Z(t)，将Z(t)作为所有用户的初始网络选择结果，同时将设定为Z(t).

2)根据式(7)和(8)建立的适应度函数评估Z(t)，将适应度函数最小的 Z(t)存储为

3)While(不出现终止条件)

t=t+1，利用式(3)～(6)更新Q(t)和Z(t);利用式(7)和(8)评估Z(t)，然后分别与进行比较，并更新

判断终止条件，即Zglobalbest(t)的适应度函数值是否为零.

End

4)输出选择结果.

4 仿真与性能评估

假设选取的WMAN小区半径为1 km，最大发生功率为80 W，带宽为20 Hz，其峰值速率为10 Mb/s;蜂窝网的小区半径分别为866 m.最大发射功率分别为20 W，峰值速率为14.4 Mb/s，具体的用户链路峰值速率可以通过式(1)求出.WLAN网络小区半径为60 m，发射功率为1 W，带宽为22 MHz.对于WMAN和CE使用的是城市无线传播模型，其路径损耗指数和阴影衰落分别为为3.52和8 dB.WL路径损耗为每米减少0.3 dB，同时带有3 dB的标准阴影衰落.用户随机分布在每个区域内.选取的效用函数为U(x)=a·x，其中a=1.离散量子粒子群算法中的参数为

表1为在区域1、区域2、区域3中用户数分别为0、5、10的情况下(由于区域1中所选择的用户数大小与搜索空间大小无关，因此为了方便，取为0)，分别利用遗传算法和离散量子粒子群算法运行5次求解纳什均衡.从表1中可以清楚地看出，遗传算法的平均迭代次数为284.8次，而离散量子粒子群的平均迭代次数为201.6，同时在图2中列举了其中的一次两种算法的收敛状态，从图中也能清晰地看出离散量子粒子群算法的收敛所需的迭代次数较少.因此离散量子粒子群算法具有更高的收敛速率.

表1 DQPS算法与遗传算法迭代次数比较

图2 算法收敛性比较

图3为区域1中用户数变化对区域2和区域3用户接入选择的影响.其中区域2的用户数为5，区域3中的用户数为10.从图2中可以清楚看出随着区域1的用户数由0增加到30时，区域2和区域3中的用户选择WM进行接入的数量分别由2和1均变为0，在区域2和区域3中选择CE网络的用户数分别由3增加到5和由6增加到7.这主要是由于区域1中的用户只能选择WM进行接入，所以随着其数量增多，WM在区域2和区域3中的可用资源将逐渐降低，如果位于这两个区域的用户选择WM进行接入，将会相对于选择其它负载较低的网络进行接入获得的数据速率要低.因此区域2和区域3中的用户将会选择接入负载较低的CE和WL.

图3 N1变化对于整个网络选择结果的影响

图4为描述当区域2中的用户数增多时，区域2和区域3选择各个接入网络的数量的变化.其中区域1和区域3中的用户数分别为1和10，区域2中的用户数由2增加到5.从图3中可以看出当区域2中接入CE网络的用户数由1增加到4，这是由于在区域2中更多的用户能够从CE网络中获得更高的数据速率.当区域2中选择CE网络的用户数量由1到4逐渐增多，由于资源的有限性，进而导致区域3中选择CE网络的用户数由7降到6，因而在区域3中选择WL网络的用户数将增多，数量由2增加到了3.

图4 N2变化对于整个网络选择结果的影响

图5所示为区域1和区域2用户数固定不变，区域3中用户数逐渐增加时，区域2和区域3中选择这3种接入网络的用户数量.其中当区域1和区域2的用户数分别为1和5时，区域3的用户由2增加到8.从图4中可以清楚看出，随着区域3中的用户数量逐渐增加，此区域中的用户选择CE接入的数量逐渐增加，由0增加到5个，由于资源的有限性，区域2中选择CE接入网的用户数逐渐降低，由4变为3个;同时区域3中选择WM的用户也由0增加到1个.从上面的分析可以看出，本文提出的基于非合作博弈的接入选择算法可以适应网络的动态变化，同时也能够合理地解释用户终端自我优化的竞争行为.

图5 N3变化对于整个网络选择结果的影响

5 结论

本文对由 WiMAX、WCDMA的 HSDPA及WLAN三种无线接入网络组成的异构网络的接入选择问题进行研究，提出了基于非合作博弈理论的接入选择算法.引入非合作博弈理论描述终端自我优化的接入选择行为，利用纳什均衡预测用户的最终选择结果.纳什均衡的定义本身并没有说明怎样求解纳什均衡，它只是用来检验某个策略组合是否是纳什均衡.因此，本文利用离散量子粒子群算法来求解纳什均衡并与遗传算法进行比较，结果显示离散量子粒子群算法具有更快的收敛速度.最后利用仿真验证了基于非合作理论的接入选择算法能够适应网络的动态变化，同时获得的接入选择结果也能够合理地解释用户终端之间自我优化的竞争行为.

[1]杨震.专题:异构网络的协同与融合[J].中兴通讯技术，2008，3:1－2.

[2]BUHLER J，WUNDER G.An optimization framework for heterogeneous access management[C]//Wireless Communications and Networking Conference.Budapest:[s.n.]，2009:1 －6.

[3]LEE S，GOLMIE N.Power-efficient interface selection scheme using paging of WWAN for WLAN in heterogenous wireless networks[C]//In Proceeding of ICC’2006.Stanbul，Turkey:[s.n.]，2006，4:1742 －174.

[4]MOLINARO A I A，CAMPOLO C，AMADEO M.An access network selection algorithm dynamically adapted to user needs and preferences[C]//In Proceeding of IEEE PIMRC＇2006.Helsinki，Finland:[s.n.]，2006:1－5.

[5]PEREZ-ROMERO J，SALLENT O，AGUSTI R N，etal.Radio access technology selection enabled by IEEE P1900.4[C]//Mobile and Wireless Communications Summit，16th IST.Piscataway:IEEE，2007:1－5.

[6]ADAMOPOULO E，DEMESTICHAS K，KOUTSORODI A.Intelligent access network selection in heterogeneous networks simulation results[C]//Wireless Communication Systems 2nd International Symposium on.Siena:[s.n.]，2005:279 －283.

[7]STEVENS-NAVARRO E，LIN Y，WONG V W S.An MDP-based vertical handoff decision algorithm for heterogeneous wireless networks[J].IEEE Transactions on Vehicular Technology，2007，57(2):1243－1254.

[8]BARI F，LEUNG V C M.Automated network selection in a heterogeneous wireless network environment[J].IEEE Network，2007，21(1):34－40.

[9]LIN H，CHATTERJEE M，DAS S K，et al.ARC:an integrated admission and rate control framework for competitive wireless CDMA data networks using noncooperative games[J].IEEE Trans Mobile Comput，2005，4(3):243－258.

[10]KASTRINOGIANNIS T，PAPAVASSILIOU S.Game theoretic distributed uplink power control for CDMA networks with real-time services[J].Computer Communications，2009，32(1):376 －385.

[11]ALTMAN E，KHERANI A A，MICHIARDI P，et al.Non-cooperative forwarding in Ad-Hoc networks[J].Lecture Notes in Computer Science，2005，3462(1):569－578.

[12]NASERIAN M，TEPE K.Game theoretic approach in routing protocol for wireless ad hoc networks[J].Ad Hoc Networks，2009，7(3):569－578.

[13]NIYATO D，HOSSAIN E.Dynamics of network selection in heterogeneous wireless networks:an evolutionary game approach[J].IEEE Transaction on vehicular technology，2009，58(4):2008－2017.

[14]NIYATO D，HOSSAIN E.Noncooperative game-theoretic framework for radio resource management in 4G heterogeneous wireless access network[J].IEEE Trans on mobile computing，2008，7(3):332－345.

[15]IEEEE.IEEE 802.16 Standard-Local and Metropolitan Area Networks-Part 16[S].Piscatway:IEEE Std.，2003:35－47.

[16]HOLMA H，TOSKALA A.HSDPA/HSUP for UMTS:high speed radio access for mobile communications[M].Chichester:John Wiley and Sons Ltd，2006:15－19.

[17]IEEE.IEEE Std 802.11a-1999(R2003):Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications:High－speed Physical Layer in the 5 GHz Band[S].Piscataway:IEEEE，2003:23 －31.

[18]MOHR W.Spectrum demand for systems beyond IMT－2000 based on data rate estimates[J].Wireless Communications and Mobile Computing，2003，3(7):817 －835.

[19]HEUSSE M，ROUSSEAU F，SABBATEL G B.Performance anomaly of 802.11b[C]//Processing of Annual Joint Conference of the IEEE Computer and Communications Societies.Infocom:[s.n.]，2003，2:836 －843.

[20]KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proc IEEE Int Conf on Neural Networks.Perth:[s.n.]，1995:1942 －1948.

[21]KENNEDY J，EBERHART R.A discrete binary version of the particle swarm algorithm[C]//Proc IEEE Int Conf on Systems， Man， and Cybernetics. Orlando:[s.n.]，1997:4104 －4108.

[22]YANG Shuyuan，WANG Min，JIAO Licheng.A quantum particle swarm optimization.Evolutionary Computation [C]//CEC2004.Congress on.Pairs:[s.n.]，2004，1:320－324.