基于演化博弈的多用户网络选择算法

唐 夲，李 乐，肖静薇，吴维农，冯文江

(1.国网重庆市电力公司信息通信分公司，重庆 400022；2.重庆大学通信工程学院，重庆 400044)

1 引言

无线通信技术的发展改变了人们的生活和工作方式，而通信需求的日益增长又促进了无线通信技术的进一步发展。不同于传统无线网络中通信体制的单调演进，新一代无线通信系统着重于多类网络异构网络融合。不同网络为用户提供差异化服务的同时，用户也能根据QoS(Quality of Service)选择不同的网络实现最佳接入[1]。从而提升网络频谱效率和服务质量。

典型的网络选择算法有博弈论法[2 - 4]、遗传算法[5,6]、人工神经网络法[7]、排队论法[8]、马尔科夫链法[9]等。但是，在热点区域，当密集分布的大量用户同时发起同种业务请求时，如果采取多属性决策进行网络选择，虽然可以实现单用户最优，但未顾及用户间竞争，且缺乏公平性，难以高效、合理利用不同网络资源。针对多用户的网络选择算法则大多利用博弈论，如用户间博弈[2,10]、用户与网络间博弈[3]和网络间博弈[11,12]等。文献[4]提出一种网络选择算法，将网络与用户间的关系抽象为非合作博弈，搜寻纳什均衡以最大化用户性价比；而在以用户为中心的网络选择中，需要同时满足用户的QoS需求和最大化网络效益，如文献[13]运用匹配博弈，提出一种异构网络选择算法，能同时兼顾用户和网络效益。

在异构多网共存和重叠覆盖区域，当多个用户同时请求同种业务时，用户间表现为一种非合作竞争关系。本文提出一种基于动态演化博弈的多用户网络选择算法，根据选择网络的用户数设计效益函数，给出了演化博弈的复制动态方程。与接收信号强度指示RSSI(Received Signal Strength Indication)算法[13]的对比仿真结果表明：该算法能快速达到演化均衡，用户平均收益高于RSSI算法，接入网络的用户分布更均匀，能合理利用网络资源。

2 演化博弈模型

如图1所示，WCDMA 蜂窝网、LTE蜂窝网和无线局域网(WLAN)重叠、交叉覆盖，构成异构多网共存环境。根据各用户位置、请求业务类型和传输速率，将用户划分为不同群体，即不同群体的用户具备不同属性。在图1中，两种业务的不同群体用户分别分布于网络覆盖区域1、2、3。

Figure 1 A network scenario图1 网络场景

将多用户选择网络过程抽象为一种演化博弈，以图1为例说明，其中：

参与者：在特定区域内请求特定业务类型的用户群体。区域2的参与者为竞争LTE和WLAN的用户群体；区域3的参与者为竞争WCDMA、LTE和WLAN的用户群体，而区域1只有WCDMA覆盖，用户无网络选择过程，不属于演化博弈参与者。在动态演化博弈中，参与者能在自我复制过程中变异和选择。

种群：在特定区域内请求同种业务的用户。区域2中请求接入LTE的用户构成一个种群，请求接入WCDMA的用户构成另一个种群；区域3中请求接入WCDMA、LTE和WLAN的用户也分别构成种群。

决策：用户可选择接入的网络。区域2有两张网络覆盖，决策集合为{WCDMA,LTE}，区域3有三张网络覆盖，决策集合为{WCDMA,LTE,WLAN}。

收益：用户选择网络能获得的效用。

3 网络选择算法

3.1 用户效用函数设计

针对特定业务类型，设计一个凸函数来衡量用户收益，表示如下：

(1)

3.2 演化博弈复制动态方程

(2)

在演化博弈中，种群a的复制动态方程为：

(3)

3.3 演化均衡稳定性

3.4 算法流程

在网络重叠覆盖区域部署一个控制中心，基于演化博弈的多用户网络选择算法如图2所示，算法流程描述如下。

具体步骤为：

Step1初始化各类参数，用户随机选择网络；

Step2控制中心执行演化博弈网络选择算法，根据当前用户的网络选择状态计算各用户收益和种群内用户平均收益，并将计算结果广播至各用户；

Step4重复执行Step 2和Step 3，直到达到演化均衡。

Figure 2 Flowchart of multi-user network selection algorithm based on evolutionary game图2 基于演化博弈的多用户网络选择算法流程

4 仿真及分析

图3所示为本文研究的网络场景中的用户分布情况图，WCDMA、LTE和WLAN分布于1.5 km×1.5 km区域，最外圆区域内WCDMA基站坐标为(550,530)，覆盖半径为600 m,网络带宽为7 Mbps,代价系数取0.02；正六边形区域内LTE基站坐标为(550,480)，覆盖半径为300 m,网络带宽为20 Mbps,代价系数取0.03；中心椭圆区域内WLAN接入点坐标为(550,400)，覆盖半径为150 m，网络带宽和价格系数分别为10 Mbps和0.01。两种不同业务请求的用户随机分布于整个区域内，业务1请求用户数为50，业务2请求用户数为30。

Figure 3 Distribution of networks and users图3 网络及用户分布仿真图

根据区域1、2、3内用户分布以及请求业务类型分成4个种群，区域3内请求业务1的用户为种群1，可选择接入WCDMA、LTE或WLAN；区域2内请求业务1的用户为种群2，可选择接入WCDMA或LTE；区域3内请求业务2的用户为种群3，可选择接入WCDMA、LTE或WLAN；区域2请求业务2的用户为种群4，可选择接入WCDMA或LTE。位于区域1内的用户无论请求何种业务只能选择接入WCDMA，因此区域1用户不构成种群。对网络中用户进行统计分析，各种群用户数分布依次为9、22、2、18。

Figure 4 Change rate of access user proportion of different groups图4 各种群接入用户比例变化率

Figure 5 Proportion of user selection network of different groups图5 各种群用户选择网络比例

根据演化博弈理论，当达到演化均衡时，种群内用户收益等于用户平均收益，用户选择不会再改变。下面从数值角度验证：以种群1为例，最终演化均衡时所有用户全部选择WLAN，根据式(2)计算此时用户收益为13.780 0，假设该用户背离演化均衡选择另一个网络，那么在其他用户不改变网络选择的情况下该用户收益为13.047 6，小于此前的收益，因此该用户不会做出该选择；假设另一个用户选择WCDMA，那么在其他用户不改变网络选择的情况下，用户收益为12.331 1，同样小于演化均衡时的收益，也不会选择与演化均衡不一致的结果。同理可证种群2、3、4的演化均衡均稳定。

当达到演化均衡时，各种群选择接入各网络的收益值如表2所示。

需要说明的是，本文未考虑用户离散性，鉴于演化博弈是一个连续的动态选择过程，在均衡时各用户收益均采用四舍五入方式近似取值，因此均衡时每个种群的收益并非完全相等，但这不影响演化均衡结果，满足演化均衡定义，该演化均衡仍是稳定的。

Table 1 User selection statistics of different groups

Table 2 Benefit statistics obtained by different groups

图6所示为用户平均收益随时间变化曲线。由图6可知，相比于RSSI算法[13]，本文算法用户平均收益更高。图7所示为不同业务在演化博弈和RSSI两种算法仿真下，最终选择接入各网络的用户数。由图7可知，采用本文算法，选择各网络的用户数比RSSI算法[13]更均衡，各网络资源利用更合理。

Figure 6 Average benefit of users图6 用户平均效益

Figure 7 Number of access users图7 接入用户数

5 结束语

本文研究了在用户密集区域且多个异构网络共存时，大量用户同时发起同种业务请求时如何高效进行网络选择，旨在满足用户QoS，均衡网络负载，提高频谱效率。提出了一种基于演化博弈的多用户网络选择算法，设计了一种随选择网络用户数变化的用户效用函数，并给出了演化博弈的复制动态方程。

与RSSI算法的对比仿真结果表明：本文算法能快速达到演化均衡，用户平均收益高于文献[13]提出的RSSI算法，接入异构网络的用户分布更均匀，网络资源能得到合理利用。

[1] Gustafsson E,Jonsson A.Always best connected[J].IEEE Wireless Communications,2003,10(1):49-55.

[2] Trestian R,Ormond O,Muntean G M.Game theory-based network selection:Solutions and challenges[J].IEEE Communications Surveys & Tutorials,2012,14(4):1212-1231.

[3] Maheswaran C P,Sulochana C H.Network selection mechanism for future generation networks using game theory model[C]∥Proc of International Conference on Computer Science and Information Technology,2014:405-413.

[4] Salih Y K,See O H,Ibrahim R W,et al.A novel noncooperative game competing model using generalized simple additive weighting method to perform network selection in heterogeneous wireless networks[J].International Journal of Communication Systems,2015,28(6):1112-1125.

[5] Gu C,Song M,Zhang Y,et al.Novel network selection mechanism using AHP and enhanced GA[C]∥Proc of the 7th Annual Communication Networks and Services Research Conference,2009:397-401.

[6] Tang Liang-rui,Li Wen-meng,Sheng Jie,et al.Chaos inheritance based access selection strategy on heterogeneous wireless network [J].Acta Electronica Sinica,2014,42(8):1564-1570.(in Chinese)

[7] Xing H Z,Mu D W,Ge X L,et al.An NN-based access network selection algorithm for heterogeneous networks[C]∥Proc of the 22nd Wireless and Optical Communications Conference (WOCC),2013:378-383.

[8] Sun Y,Liu C,Yang P,et al.A smart vertical handoff decision algorithm based on queuing theory[C]∥Proc of the 16th International Conference on Advanced Communication Technology (ICACT),2014:1217-1222.

[9] Du Z Y,Wu Q H,Yang P L.Dynamic user demand driven online network selection[J].IEEE Communications Letters,2014,18(3):419-422.

[10] Salih Y K,See O H,Ibrahim R W,et al.A user-centric game selection model based on user preferences for the selection of the best heterogeneous wireless network[J].Annals of Telecommunications-Annales Des Telecommunications,2015,70(5-6):239-248.

[11] Chen Q B,Zhou W G,Chai R,et al.Game-theoretic approach for pricing strategy and network selection in heterogeneous wireless networks[J].IET Communications,2011,5(5):676-682.

[12] El-Hajj A M,Dawy Z,Saad W.A stable matching game for joint uplink/downlink resource allocation in OFDMA wireless networks[C]∥Proc of IEEE International Conference on Communications (ICC),2012:5354-5359.

[13] Feng Ya-nan.The research of access selection strategy and algorithm on heterogeneous wireless network [D].Hangzhou:Zhejiang University,2014.(in Chinese)

附中文参考文献:

[6]唐良瑞,李文猛,盛洁,等.基于混沌遗传的异构无线网络接入选择策略[J].电子学报,2014,42(8):1564-1570.

[13]冯亚男.异构无线网络接入选择策略与算法的研究[D].杭州:浙江大学,2014.