基于TOPSIS的匹配博弈网络选择算法

于秀兰，曾　成

(重庆邮电大学 重庆市移动通信市级重点实验室，400065 重庆 )



基于TOPSIS的匹配博弈网络选择算法

于秀兰，曾成

(重庆邮电大学 重庆市移动通信市级重点实验室，400065 重庆 )

摘要：针对无线通信中网络资源利用率的重要性，提出一种基于逼近理想解排序法(technique for order preference by similarity to ideal solution，TOPSIS)的匹配博弈论异构网络选择算法，联合考虑用户端的网络选择和网络端的用户选择，分析用户和网络的时延、传输速率、丢包率，运用匹配博弈的原理选择出双方满意度最高的网络选择方案。仿真结果表明，在多用户同时存在的情况下，给出TOPSIS的匹配博弈论异构网络选择算法具有较低的阻塞率和较高的满意度。

关键词：异构网络；逼近理想解排序法(TOPSIS)；多用户；匹配博弈

0引言

随着无线通信的快速发展以及802.11ad，Femtocell，WiMAX等新型无线接入技术的广泛使用，下一代无线网络必将是多种网络同时存在的无线异构网络，不同的网络接入技术在接入速率、工作频率、覆盖范围、接入方式和应用场景等方面都各不相同。用户在不同的情况下对网络的需求不同，同时用户需要根据不同的需求选择最优的网络，没有一种网络始终符合用户的需求。移动通信系统是一个异构的网络体系，需要协调各种无线网络，使得多个用户同时达到需要的时延、抖动、传输速率、丢包率等要求。因此，多用户的网络选择方案，已成为无线移动通信研究的热点课题。

目前，对异构网络选择的研究已取得一些成果。以用户为中心的网络选择算法主要考虑用户的满意度，通过对网络参数进行分析运算，选择使用户满意度最高的网络进行接入。文献[1]提出了一种新颖的网络选择算法。该算法的提出是基于文献[2]的层次分析法(analytic hierarchy process， AHP)和文献[3]的灰色关联分析法(grey relational analysis，GRA)。AHP算法用于计算每个网络的权重大小，但其对于网络参数权重的确定具有较强的主观性，网络权重分配不够合理。GRA算法对各样本采用平权处理，客观性较差，不符合网络选择的实际情况。文献[4] 提出一种AHP与破产博弈论的联合算法，该联合算法估计潜在贡献率，选择贡献率最大的网络，但算法复杂度较高，会造成过多的网络判决延迟。文献[5]提出一种在长期演进 (long term evolution，LTE)和无线局域网 (wireless local area networks，WLAN)系统中的自组织网络选择算法。该算法采用WLAN接收信号强度阀值来控制接入选择，由于仅从接收信号的强度来进行网络选择，考虑因素单一，造成网络选择的片面性。文献[6] 基于估计信号的信号干扰噪声比(signal to interference plus noise ratio，SINR)的网络选择策略，在异构网络中考虑所有用户的QoS需求，但仅从用户的QoS考虑网络的选择，忽略了网络端的影响。文献[7]提出一种基于蜂群演化的网络选择方案，同时利用灰度值分析方法、博弈论方法、遗传算法考虑网络选择的其他问题，使得算法复杂度较高，无法应用于实际环境。

以上研究主要针对单用户在异构网络中的选网，没有考虑多个用户同时进行网络选择的情况。同时，仅从用户端考虑用户对网络的偏好或仅考虑网络端对用户的偏好，这都是单向选择算法，以最大化自己的效用函数为目标。针对目前网络选择存在的不足，本文提出一种基于逼近理想解排序法(technique for order preference by similarity to ideal solution，TOPSIS)的匹配博弈算法，从用户和网络的角度出发，综合考虑多种参数指标，同时考虑两者的偏好，运用匹配博弈，达到用户和网络的双赢。

1用户端的网络偏好

逼近最优解排序法是多属性决策算法，考虑网络的多个参数，根据计算目标对象与理想解的相对接近程度来选择最优的网络。TOPSIS的理想解分为正理想解和负理想解。采用欧式距离计算每个目标方案与理想方案的距离。TOPSIS算法的最优目标方案距离正理想解比较近，同时距离负理想解比较远[8-10]。

1.1AHP法参数权重的确定

文献[11]介绍了常见的网络参数权重的计算方法。本文采用AHP计算网络参数的权重值。AHP应用于难于定量分析的问题，将问题中难以处理的部分划分为相对简单的问题加以处理。

1.2相对接近程度计算

假设判决矩阵为Y，表示为

(1)

(1)式中：行表示网络；列表示网络的参数指标。

1)判决矩阵标准化。由于各判决指标的单位不同、量纲不同、数量级不同，需要对所有判决指标进行标准化处理。判决矩阵标准化为

(2)

(2)式中：i表示网络，i=1,2,…,m；j表示网络的参数指标，j=1,2,…,n。得到标准化矩阵Z=(zij)m×n。

2)建立加权标准化矩阵。

(3)

(3)式中，uj是由上述AHP法求得的网络参数的权重值。

3)确定正理想解和负理想解。

(4)

(5)

(4)—(5)式中:vij为加权标准化矩阵V中的元素；J为效益型参考集合；J′为成本型参数集合。

4)计算距离。每个方案距离正负理想方案的距离为

(6)

(7)

5)计算与理想解的相对接近程度。

(8)

然后依据Ci大小进行排序。则用户i的网络排序U(N)i表示为

(9)

(9)式中：netm表示第m个网络。

2网络端的用户偏好

用户的流失率与网络的偏好直接相关，用户i是否接入网络，直接影响着网络的偏好。而用户的流失率又与数据速率、时延、丢包率、带宽、价格相关。

2.1用户满意度计算

用户的满意度与网络提供给用户的速率、时延、丢包率、带宽、价格直接相关。定义用户的满意度函数为

(10)

根据文献[12]，速率、时延、丢包率的评估函数定义为

(11)

(12)

(13)

(14)

(14)式中：x，μ为2个函数变量。

ζj定义为

(15)

(15)式中：ρj表示网络j的负载强度；ρ0表示网络j的最小负载门限。

根据Sigmoid函数，定义网络j的带宽及价格的评估函数分别为(16)式和(18)式。

(16)

(17)

(18)

(19)

(20)

(21)

(22)

2.2网络端的效用函数

网络端的效用函数为网络接入用户带来的收益减去网络不接入用户带来的损失，定义为

(23)

(23)式中：Pi,j表示用户i接入网络j给网络带来的收益；Si,j表示用户i不接入网络j给网络带来的损失。

用户流失率定义为

(24)

网络的损失效用Si,j定义为

(25)

(25)式中，Li,j表示用户i离开网络j时网络的损失。

根据不同用户的M大小，排列出网络j对用户的偏好排序N(U)j表示为

(26)

(26)式中：usern表示第n个用户。

3匹配博弈网络选择

匹配博弈是合作博弈的一种，由Gale和Shapley于1962年在一篇关于大学生就业和婚姻匹配的问题中提出[13]。1984年Roth对其进行了重要发展。匹配博弈的参与者被分为2个集合，网络集合和用户集合，其中网络集合包括femtocell，802.11ad，Wimax，LTE等一些网络组成的异构网络系统，用户集合是运行会话类、流类、互动类、背景类[14]的一系列业务的用户。这是2个完全不相交的集合，用户和网络根据自身的情况进行相互选择。假设在一次博弈中每个用户只能接入一个网络，一个网络可以接入多个用户。

3.1匹配博弈算法

假设网络集合为

Net={net1,net2,…,netm}

(27)

用户集为

User={user1,user2,…,usern}

(28)

匹配博弈采用多对一匹配博弈，即在第1次匹配博弈中，所有用户同时进行匹配博弈。每一轮匹配过程中，排在网络排序U(N)和用户排序N(U)前面的参与人最先完成匹配，没有匹配的用户会在多次匹配之后完成匹配[15]。匹配博弈的具体步骤如下。

1)第1次匹配。假设已完成匹配的用户不在用户集合中。用户端中的每一个用户根据自己的网络优先级排序U(N)，选择优先级最高的网络。网络端需要设定匹配窗口的大小，即网络端一次匹配中考虑多少个用户。如果网络端用户位于匹配窗口内，则匹配成功。

2)匹配窗口的平移。如果网络j是用户i中优先级最高的网络，网络j的用户优先级窗口中如果有用户i，则匹配完成。若用户i与网络j匹配不成功，即网络窗口中无用户i。第1次匹配结束后，需要对匹配窗口进行平移。网络j的窗口删除网络j第1次匹配中匹配成功用户及其他网络经过第1次匹配成功的用户，加入优先级排序中未参加匹配的用户。

3)第2次匹配。网络j仍是用户i中优先级最高的网络，网络j的匹配窗口已经发生了平移。如果用户i在平移后的匹配窗口中，则匹配完成。第2次匹配可进行多次。

4)用户匹配失败。用户i在第1次匹配和第2次匹配中都未完成匹配，则用户i选择优先级逐渐次之的网络。重复以上过程，直到所有用户匹配完成。

3.2匹配博弈算法的稳定性

匹配博弈始终存在稳定的博弈。完成匹配后的网络和用户都能获得最高的收益，因此，整个算法满足博弈的稳定性。

用户端的最优匹配网络指用户经过第k次匹配后所能接入的满意度最高的网络；网络端的最优匹配用户指经过第k次匹配后，网络所能接入的满意度最高的w个用户。

在整个匹配算法结束后，网络j最终和d个用户完成了匹配。对于用户i在第k次匹配后，用户i已经与其满意度最高的网络完成了匹配，满意度比网络j高的网络已经被用户i在k次匹配之前从用户端的网络排序中删除；对于网络j在第k次匹配后，网络j已经与窗口中参与匹配的用户i完成了匹配，因此，第k次匹配后窗口中的用户集满意度低于匹配删除的用户集，整个匹配博弈的结果是稳定的，即不存在一个更优的网络匹配来破坏原来的匹配结果。

4仿真结果与分析

本文的仿真场景如图1所示，多个用户同时处于femtocell，Wimax，802.11ad，LTE的覆盖区域内。根据3GPP将业务类型分为4类(会话类、流类、互动类、背景类)，用户的业务类型包含了全部的4种类型。仿真中的无线网络参数值如表1所示。

图1　多用户网络选择模型Fig.1　Multi-user network selection model

候选网络时延/ms抖动/ms速率/(Mbit·s-1)丢包率/%femtocell10—252—5500.001802.11ad8—201—8800.002Wimax35—502—7150.003LTE60—1003—10300.004

不同窗口大小满意度情况如图2所示。从图2可以看出，随着用户数的增加，用户端的平均满意度下降，网络端的平均满意度缓慢上升后趋于平稳。当窗口大小大于或等于用户数时，用户的平均满意度最大且不变，此时的匹配选择相当于用户端采用TOPSIS算法选择，用户选择性能最好的网络，此时用户的平均满意度最高，但是用户间无法相互通信，所有用户都同时接入性能最好的网络，必将造成最优网络拥塞。匹配窗口越大，要达到的匹配博弈的要求需要的用户数越多，且此时用户的满意度开始下降，表示通过匹配博弈，用户的平均满意度下降，部分用户选择了满意度较小的网络，与仅考虑用户端TOPSIS算法比较，避免了网络拥塞。窗口数越小对用户端和网络端的满意度影响越明显，窗口过大时，基于博弈论文的网络选择等同于用户端的网络选择算法。用户满意度与网络满意度的交点表示最佳匹配点，用户数为70时，网络的最佳窗口大小为10。

图2　不同窗口大小满意度情况Fig.2　Satisfaction with different window size

博弈次数随窗口大小的变化情况如图3所示。从图3可以看出，随着用户数目的增加，博弈的匹配次数增加。相同用户数的情况下，博弈的次数随窗口大小的减小而增加。

图3　博弈次数随窗口大小的变化Fig.3　Number of game along with the change of window size

由于不同用户的参数不同，网络的参数不同，造成用户对网络的优先级偏好，网络对用户的优先级偏好不同，所以博弈的次数也会造成不同。

5结束语

本文提出了一种适用于多用户的基于TOPSIS的匹配博弈，不同于已有文献仅考虑用户端或网络端进行网络选择的算法，该匹配博弈算法同时考虑用户对网络的偏好及网络对用户的偏好，运用匹配博弈找到博弈的均衡点，即是最优的网络选择。仿真结果表明，基于TOPSIS的匹配博弈网络选择算法，不但满足用户和网络的满意度而且有利于提升网络的利用率，降低网络的拥塞率。

参考文献：

[1]SASAKI M,YAMAGUCHI A,IMAGAKI Y,et al. Novel Communication System Selection applying the AHP Algorithm in Heteogeneous Wireless Networks[C]//Springer. Proceedings of The First International Conference on Wireless Communications and Applications.Sanya:Springer Berlin Heidelberg Press,2011:241-249.

[2]SONG Q, JAMALIPOUR A. Network selection in an integrated wireless LAN and UMTS environment using mathematical modeling and computing techniques [J].IEEE Wireless Communications,2005, 12(3):42-48.

[3]FU Jianqing, WU Jiyi, ZHANG Jianlin, et al. A Novel AHP and GRA Based Handover Decision Mechanism in Heterogeneous Wireless Networks[C]//Springer.Information Computing and Applications.Tangshan:Springer Berlin Heidelberg,2010:213-220.

[4]LIU Bin,TIAN Hui, WANG Bin,et al.AHP and Game Theory based Approach for Network Selection in Heterogeneous Wireless Networks [C]//IEEE.IEEE Consumer Communications and Networking Conference(CCNC).LasVegas, NV:IEEE,2014:501-506.

[5]WANG Y,DJAPIC R, BERGSTROM A,et al. Performance of WLAN RSS based SON for LTE/WLAN access network selection[C]//IEEE.IEEE Wireless Communications Systems(ISWCS).Barcelona: IEEE,2014:460-464.

[6]JABBAN A,NASSER Y, HELARD M. Performance Analysis of Heterogeneous Networks Based on SINR Selection Strategy[C]//IEEE. International Conference on Telecommunications(ICT).Casablanca:IEEE,2013:1-5.

[7]ZHANG Chengbo, WANG Xingwei . A Network Selection Scheme Based on Bee Colony Evolution [C]//IEEE.IEEE Computer Science and Network Technology (ICCSNT).Dalian:IEEE,2013: 650-654.

[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]ZHOU Shaoqi, CHANG Wenbing, ZHOU Shenghan,et al.The method of risk evaluation for equipment development based on triangular fuzzy number and TOPSIS [C]//IEEE.Proceedings of IEEE Control and Decision Conference (CCDC).Changsha:IEEE,2014:2272-2276.

[10] LIU Fang, ZHANG Weiguo. TOPSIS Based Consensus Model for Group Decision Making with Incomplete Interval Fuzzy Preference Relations [J]. IEEE Transactions on,2014, 44(8):1283-1294.

[11] MOHAMED L, LEGHRIS C, ABDELLAH A. A survey and comparison study on weighting algorithms for access network selection[C]// IEEE .Annual Conference on Wireless On-demand Network Systems and Services(WONS). Courmayeur:IEEE，2012：35-38.

[12] CHEN Yunghan, YANG Nuanyu, CHANG Chungju. A utility function based access selection method for heterogeneous WCDMA and WLAN network[C] //IEEE.IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications(PIMRC). Athens:IEEE, 2007:l-5.

[13] GALE D, SHAPLEY L S.College Admissions and the Stability of Marriage [J].The American Mathematical Monthly, 1962，2013,69(5):9-15.

[14] 3GPP.Technieal Specification TS23.107, V4.0.0，QoS, Concept and Architecture [S].[s.l.]: 3GPP Organization Partners, 2000.

[15] ZENG Yi, ZHANG Zufan. Joint transmit beamforming and power control in multi-user MIMO downlink using a game theoretic approach [J]. The Journal of China Universities of Posts and Telecommunications, 2007,14(2)：14-18.

DOI：10.3979/j.issn.1673-825X.2016.04.002

收稿日期：2015-06-15

修订日期：2016-02-29通讯作者：曾成448212556@qq.com

基金项目：国家自然科学基金(61440062)；国家863计划(2014AA01A705)

Foundation Items：The National Natural Science Foundation of China(61440062)；The National High Technology Research and Development Program of China(“863”Program)(2014AA01A705)

中图分类号：TN929.5

文献标志码：A

文章编号：1673-825X(2016)04-0451-05

作者简介：

于秀兰(1973-)，女，四川广安人，副教授，硕士，研究方向为无线通信。E-mail: yuxl@cqupt.edu.cn。

曾成(1989-)，男，四川眉山人，硕士研究生，研究方向为无线通信。E-mail:448212556@qq.com。

(编辑：王敏琦)

Matching game network selection algorithm based on TOPSIS

YU Xiulan， ZENG Cheng

(Chongqing Key Laboratory of Mobile Communication, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R.China)

Abstract:According to the importance of enhancing the network resources efficiency for wireless communication, this paper proposes a heterogeneous network selection algorithm based on technique for order preference by similarity to ideal solution (TOPSIS)matching game. We consider network selection at client and user selection at server and analyze delay, transmission rate, packet loss rate of the whole system. Based on the TOPSIS matching game, we select the most appropriate network selection program which meets the requirements of both clients and servers. The simulation shows that in the presence of multiple users at the same time, heterogeneous network selection algorithm based on TOPSIS matching game has lower blocking rate and achieve higher satisfaction.

Keywords：heterogeneous network; technique for order preference by similarity to ideal solution (TOPSIS); multiple users; matching game