一种非合作博弈下的无线网络接入选择方法

赵 婧,李兴华,薛飞洁,马建峰

(西安电子科技大学计算机学院,陕西西安 710071)

一种非合作博弈下的无线网络接入选择方法

赵 婧,李兴华,薛飞洁,马建峰

(西安电子科技大学计算机学院,陕西西安 710071)

针对如何根据用户的需求在无线网络中选择接入网络的问题,依据不同接入网络之间的非合作关系以及接入网络与用户之间的非合作关系,建立了非合作博弈下的基于支付函数的模型.该模型根据多属性决策理论,运用灰色关联分析法对不同网络的性能参数进行归一化处理,将得到的灰色关联等级作为支付函数进行比较,选出较优秀的网络.通过求解用户与较优秀网络间的纳什均衡,得到用户的接入网络选择.实验结果表明,该方法能够根据用户的需求有效地选择合适的接入网络.

非合作博弈;纳什均衡;灰色关联分析法;无线网络;选择方法

随着人类社会与经济的迅猛发展,无线通信系统为用户提供各种各样的服务,而用户的业务需求也越来越多.为了使用户的业务需求得到满足,用户所接受的服务不再是只由单一的运营商提供,而是可以按照自己的意愿从多个运营商和无线接入网络中选择适合自己业务需求的,能够以适当的付出得到满意服务质量的网络进行接入.因此,无线接入网络的选择问题受到越来越多的关注[1-3].

文献[4]将垂直切换时的网络选择方法分为:基于决议函数的策略,以用户为中心的策略,多属性决策策略,基于模糊逻辑和神经网络的策略以及环境感知策略.文献[5]分为4种网络选择算法:基于接收信号强度的算法,基于带宽的算法,基于花费函数的算法以及基于结合的算法(即模糊逻辑和神经网络算法).文献[6]在无线网络的选择中使用了基于效用函数的模糊逼近理想解排序法.为了使一个移动终端能够以最佳的方法接入到网络,需要考虑服务质量以及能量消耗.运用模糊化的方法解决一些属性值为不可度量或者不能统一度量的指标,然后按照永久最佳接入准则[7]选择接入网络.文献[8]主要以最大化系统容纳的呼叫次数、最小化切换发生频率以及达到网络服务质量为目标进行无线网络的选择.计算效用函数以及用户偏好值,选两者线性结合后所得数值最大的网络为最佳接入网络.在选择网络时考虑了移动终端的移动性,相比于迭代逼近理想解排序法,该方法能达到更好的服务质量满意度,容纳更多的呼叫次数,网络切换发生频率降低了30%.文献[9]主要从定价策略角度讨论无线网络的选择问题,在无线网络中,价格可以作为一种资源分配、允许控制以及网络选择的机制.价格应用于无线网络选择中有3种不同的方法:基于拍卖[10],基于最优化[11]以及基于需求/供应的策略.在计算语音/视频服务时,使用了S曲线函数[12]的变体对无弹性的服务用户满意度建模.文献[13]为了防止网络拥塞和性能降低,使用进化博弈的方法在无线网络中动态选择较佳网络.

不同的网络运营商为用户提供不同的网络,通过网络资费从用户处获取利润,所以当网络运营商的用户数量增加时,其获取的利润也会增多.在这种情况下,不同的网络运营商之间会建立一个非合作博弈.同时网络运营商和用户之间也属于竞争关系,因为这两者之间也存在利益冲突.在无线网络接入选择过程中,用户希望以最少的支付获得最优的网络服务.而网络运营商则希望使用最少的网络资源完成用户的业务需求,这样可以在消耗一定网络资源时,最大限度地增加网络可容纳的用户数量.所以网络运营商和用户之间也形成了竞争关系,也会建立一个非合作博弈.根据以上的问题背景分析,笔者在非合作博弈情况下进行了无线网络接入选择方法的研究,提出了非合作博弈下的基于支付函数的模型以及非合作博弈下的纳什均衡求解方法.

1 非合作博弈及其纳什均衡

传统上将博弈论分为合作博弈和非合作博弈,合作博弈是指参与人之间能达成一个具有约束力的协议;反之,如果参与人之间不可能达成一个具有约束力的协议则称为非合作博弈.然而,“非合作”不是说每个参与人总是拒绝和其他参与人合作,而是在非合作博弈中参与人只是根据 “可察觉的自我利益”来决策[14].

博弈论的理论研究主要集中在非合作博弈,除此之外,非合作博弈在经济领域的应用方面也取得了巨大成功.因此,非合作博弈的研究是博弈论研究的主流.文中根据分析问题的背景,也选择了基于非合作博弈的理论对无线网络接入选择方法的问题进行研究.

博弈论研究的目的就是寻找博弈问题的解,即给定一个博弈问题,分析或预测什么样的博弈结果将会出现.探寻博弈问题的解,必须明确两点,一是参与人完全理性,二是参与人都了解博弈问题的结构.参与人理性是指参与人在博弈中具有推理、决策能力,并通过选择策略使自己在博弈中的得益或支付最大化.

非合作博弈问题主要是通过求解纳什均衡来解决的.随着所研究问题复杂程度的增加,研究者又在纳什均衡的基础上提出了更加复杂和精炼的解的概念.

在博弈G={S1,S2,…,Sn;u1,…,un}中,如果由各个博弈方的各个策略组成的某个策略组合(s1*,…,)中,任一博弈方i的策略,都是对其余博弈方策略的组合的最佳策略,也即

简单来讲,如果有参与人没有选择最佳策略集合中的策略,那么纳什均衡就不能达到,这将致使某些参与人得不到优于纳什均衡时的收益.所以按照纳什均衡中的最佳策略集合选择策略,能达到一个相对较好的稳定状态.达到纳什均衡也是每个理性参与人的最终目的.

2 方案模型

2.1 非合作博弈下的基于支付函数的模型

支付函数对于博弈的进行、纳什均衡的计算极为重要.在现阶段关于基于博弈论的无线网络接入选择的研究中,支付函数都简化表述,如文献[16]把时延和抖动视为支付函数.但对于复杂的无线网络环境,这种简化的支付函数表述形式不足以体现全面性.例如,有些用户的业务对信号强度以及带宽都有严格要求,但如果支付函数中只包括信号强度或者只包括带宽,在这两种情况下进行的无线网络的接入选择,都会影响用户的网络服务质量.因此,需要改变这种支付函数是由单一指标或者两种指标简化表述的情况.

文中引入了一种新的更为全面的支付函数的表述形式,为此提出了多属性决策理论的概念.多属性决策是把多种性能参数进行综合评价,得出一个数值作为支付函数.对于选择接入网络的用户,支付高的网络,比较适合接入.多属性决策理论的方法一般是在属性权重归一化后的量化属性评价的基础上,利用决策方法的效用函数

产生综合评价指标,再根据U(Ai)值所体现的决策方案的优劣做出决策[17].其中,M表示备选决策方案的集合,N表示每个备选决策方案的多个属性集合.Xij表示转化为效益型属性并进行归一化后的属性评价值.文中采用灰色关联分析法[18]对系统性能进行动态分析,选出优秀的备选网络,再求解纳什均衡,由用户选择备选网络接入.

灰色关联分析的步骤如下:

(1)选择评估影响因子和测量参数.在选择接入的无线网络时,可以将网络的资费、信号强度、时延、丢包率等作为评估因子.

(2)选择加权因子.在评估因子确定之后,为每一个评估因子确定其相应的加权值,加权值为常数.

(3)建立评估矩阵.评估矩阵的每一列为不同的评估因子,每行为相应网络的评估因子的数值.

(4)测量数据的合理化.根据每个评估因子的属性范围对测量所得数据进行合理化处理.

(5)为每个评估因子确定灰色关联系数.

(6)确定每个备选网络的关联等级.

当存在多个用户终端对备选网络进行选择时,用户终端的接入选择会相互影响.例如,当网络达到一定负载量时,接入用户的增加可能会对网络的服务质量产生恶劣的影响,在选择接入网络时,这种情况也需要纳入考虑范围之内.在对支付函数精确表示的同时,也要注意到计算支付函数的复杂度和计算时间,不能过于影响到网络的接入选择.

2.2 非合作博弈下的纳什均衡求解

在参与人为用户和网络运营商的非合作博弈中,网络运营商的策略空间为{允许接入,拒绝接入};用户的策略空间为{要求接入,拒绝接入}.因此,策略组合为(网络,用户)={(允许接入,要求接入),(允许接入,拒绝接入),(拒绝接入,要求接入),(拒绝接入,拒绝接入)}.对应的支付函数值分别为(U′11,U″11),(U′12, U″12),(U′21,U″21),(U′22,U″22).

首先,将备选网络利用灰色关联分析法进行排序选择,选择出较优秀的网络.然后,这些网络与用户进行博弈,博弈表述的形式如表1所示.网络运营商的支付函数值由用户接入网络后带来的利润表示,用户的支付函数值则由灰色关联分析法所得的网络关联等级表示.文中使用划线法求解该博弈的纳什均衡.用户按照备选网络的排序依次与备选网络进行博弈,直至纳什均衡的解为策略组合(允许接入,要求接入).

表1 参与人为用户与网络的博弈模型

作为理性参与人的用户和网络,都会选择在博弈中使自己的支付能够最大化.在两者重复博弈的过程中,当用户和网络选择的策略符合最佳策略集合时,便可以达到纳什均衡.

3 方案分析

3.1 实验数据获取

为了获取实验数据,移动终端选择的手机型号为小米1S,操作系统为安卓系统.使用不同运营商的手机卡接入网络,通过实验获取相关数据.网络资费按照当前价格行情查得,对于备选网络A、B和C,50元人民币可购买的流量值分别为500 MB、600 MB、800 MB,若价格单位选为元/MB,则计算可得备选网络A、B和C的价格分别为0.1元/MB、0.083元/MB、0.063元/MB.在移动终端上安装移动终端模拟器,这款软件可以访问安卓系统内置的Linux操作系统的命令行.在终端模拟器里运行Linux命令“ping—c 50 www.xidian. edu.cn”,即可获得实验50次的情况下网络的时延及丢包率.

在测试网络的传输速度时,选用了网速测试软件.该软件是一款实时测试手机网速的工具,包括上行、下载,网络的传输速度=上行速度+下载速度.实验数据为测试10次计算所得的平均值.为了防止地理位置以及手机配置对网络的接入产生影响,进而可能影响实验结果,所有实验数据均在同一地点,使用相同移动终端测试所得.

3.2 非合作博弈下的数据分析

按照灰色关联分析法对3个不同网络运营商提供的网络进行性能分析,对备选网络进行排序,操作步骤如下.

(1)选择评估影响因子和测量参数.本次处理中选择价格、时延、传输速度、丢包率作为影响判决的评估因子.评估因子及其量化准则如表2所示.

表2 无线网络的评估因子和测量参数

(2)选择加权因子.在确定不同的无线网络的评估因子之后,为每一个评估因子确定其相应的加权值,加权值为常数.在本次处理中,假定有3个用户,不同用户对不同无线网络评估因子的加权值如表3所示.

表3 用户对评估因子的加权值

(3)建立评估矩阵.评估矩阵的每一列为不同的无线网络评估因子,每行为对应网络的评估因子的数值.备选网络的不同参数的数值通过3.1节所述办法测得,如表4所示.

表4 对应各评估属性的测量值

(4)测量数据的合理化.根据每个评估因子的属性范围对测量所得数据进行合理化处理.当用户希望无线网络的某项参数期望值越大越好时,如传输速度最大化,则该项参数的期望值可表示为Xij=(Xij-(Xij)min)((Xij)max-(Xij)min);当用户希望无线网络的某项参数期望值越小越好时,如价格、时延、丢包率最小化,则该项参数的期望值可表示为Xij=((Xij)max-Xij)((Xij)max-(Xij)min),其中,Xij表示表中第i行、第j列的数值.表5中的理想标准序列是根据每个评估因子的期望值得到的.

表5 理想标准序列

表6 关于各运营网络的灰色关联系数表

(6)确定每个备选网络的关联等级.通过使用不同用户对于不同备选网络的每个评估因子的加权值,计算每个备选网络的关联等级Γ,即

其中,βk表示每个评估因子的加权值.将表5中的关联系数代入式(3),得到灰色关联系数.

对于用户1,Γ01=0.5397,Γ02=0.7195,Γ03=0.8500.由于Γ03＞Γ02＞Γ01,因此,备选网络排序为C—B—A.

对于用户2,Γ01=0.5543,Γ02=0.6645,Γ03=0.9000.由于Γ03＞Γ02＞Γ01,因此,备选网络排序为C—B—A.

对于用户3,Γ01=0.5439,Γ02=0.7922,Γ03=0.7500.由于Γ02＞Γ03＞Γ01,因此,备选网络排序为B—C—A.

观察以上计算结果,虽然用户1和用户2对于不同评估因子的加权值不同,但所得备选网络排序相同.而对于用户1和用户3或用户2和用户3,用户对不同评估因子的加权值不同,备选网络排序也不同.当然,如果不同用户对不同评估因子的加权值相同,则备选网络排序也必然相同.因此,无法根据加权因子的数值直接判断备选网络的排序,而必须计算出备选网络的关联等级,才能对备选网络进行排序.

3.3 方案比较

文献[6]在服务质量的比较时,选用了带宽和时延作为比较参数.该方法考虑了连接网络的能量消耗,比如在移动终端电量较低的情况下,可以综合网络的服务质量以及能量消耗情况选择更适合的网络.但是服务质量仅仅以带宽和时延作为比较参数,忽略资费以及丢包率等其他属性,会造成网络服务质量判断不全面.文献[9]按照服务类型确定效用函数,服务类型主要包括语音/视频服务以及数据服务,最终达到用户和无线网络提供商的双赢.不同网络提供商对网络的定价不同.这种方法针对不同的网络服务,给出了不同的效用函数,更具有针对性,使结果更为精确.但是服务质量仅以带宽作为比较参数,会对选择结果造成不良影响.文献[13]考虑了不同用户为争夺有限带宽而存在竞争,以此形成一个动态的进化博弈,并提出种群进化以及强制学习两个算法.强化学习算法不同于其他方案,需要用户花费时间通过交流了解不同网络的性能以及价格来制定一个训练集,然后再把训练集中的信息应用于网络选择.

文中在非合作博弈下的基于支付函数的模型中,使用多属性决策方法对网络进行排序,然后再由用户和网络通过博弈进行选择接入.相对于其他以单一性能作为参数的选择方法,文中方法能更全面地对网络进行评价.除此之外,文中方法的另一优点是考虑了用户需求,根据用户的需求为不同备选网络的评估因子设定加权值,这种方法设计可以根据用户的业务需求更合理有效地选择出用户所需网络.

表7中,展示了文中的方案与文献[6,9,13]中方案的对比,Y表示方案采用或考虑到该项,N表示方案没有采用或没有考虑到该项.

表7 方案间的对比

4 结束语

基于博弈论研究了无线网络接入选择方法的问题.在非合作博弈下,建立了基于支付函数的模型.使用了灰色关联分析法,以网络的多种性能为评估因子,对网络进行了全方面的评估,最终由用户选择优秀的网络进行接入.相比其他已有方案,多属性决策的灰色关联分析法对网络进行的评估更为全面和准确.

博弈论解决网络选择问题[19-20]能充分考虑通信实体之间的相互影响,具有更高的选择可靠性,但对于纳什均衡求解的研究仍需要长时间的努力,特别是对于计算的复杂度、纳什均衡的存在性、满意度等,这也是下一步工作的研究重点.

[1]Argento A,Cesana M,Gatti N,et al.A Game Theoretical Study of Access Point Association in Wireless Mesh Network [J].Computer Communications,2012,35(5):541-553.

[2]Haria M,Milano P,Matto C,et al.Network Selection and Resource Allocation Games for Wireless Access Networks [J].Mobile Computing,2012,12(12):2427-2440.

[3]Kaleem F,Mehbodniya A,Islam A,et al.Dynamic Target Wireless Network Selection Technique Using Fuzzy Linguistic Variables[J].China Communications,2013,10(1):1-16.

[4]Kassar M,Kervella B,Pujolle G.An Overview of Vertical Handover Decision Strategies in Heterogeneous Wireless Networks[J].Computer Communications,2008,31(10):2607-2620.

[5]Yan Xiaohuan,Sekercioglu Y,Narayanan S.A Survey of Vertical Handover Decision Algorithms in Fourth Generation Heterogeneous Wireless Networks[J].Computer Networks,2010,54(11):1848-1863.

[6]Chamodrakas I,Martakos D.A Utility-based Fuzzy TOPSIS Method for Energy Efficient Network Selection in Heterogeneous Wireless Networks[J].Applied Soft Computing,2012,12(7):1929-1938.

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

[8]Chang C J,Tsai T L,Chen Y H.Utility and Game-theory Based Network Selection Scheme in Heterogeneous Wireless Networks[C]//IEEE Wireless Communications and Networking Conference.New York:IEEE,2009:4918016.

[9]Sengupta S,Anand S,Chatterjee M,et al.Dynamic Pricing for Service Provisioning and Network Selection in Heterogeneous Networks[J].Physical Communication,2009,2(1-2):138-150.

[10]Sallent O,Perez-Romero J,Agusti R,et al.Resource Auctioning Mechanisms in Heterogeneous Wireless Access Networks[C]//IEEE Vehicular Technology Conference.Piscataway:IEEE,2006:52-56.

[11]Zhang Wenhui.Bearer Service Allocation and Pricing in Heterogeneous Wireless Networks[C]//IEEE International Conference on Communications.Piscataway:IEEE,2005:1367-1371.

[12]Wikipedia.Sigmoid Function[DB/OL].[2012-05-28].http://en.wikipedia.org/wiki/Sigmoid_function.

[13]Niyato D,Hossain E.Dynamics of Network Selection in Heterogeneous Wireless Networks:an Evolutionary Game Approach[C]//IEEE Vehicular Technology Conference.Piscataway:IEEE,2009:2008-2017.

[14]罗云峰.博弈论教程[M].北京:清华大学出版社,北京交通大学出版社,2007.

[15]李帮义,王玉燕.博弈论及其应用[M].北京:机械工业出版社,2010.

[16]Antoniou J,Pitsillides A.4G Gonverged Environment:Modeling Network Selection as a Game[C]//IEEE Mobile and Wireless Communications Summit.Piscataway:IEEE,2007:1-5.

[17]陈守学.异构网络中的网络选择方案研究[D].北京:北京邮电大学,2010.

[18]贺昕,李斌.异构无线网络切换技术[M].北京:北京邮电大学出版社,2008.

[19]宗汝,高新波,彭建华.临近空间平台自组织网络优化部署的博弈算法[J].西安电子科技大学学报,2013,40(5): 188-193.

Zong Ru,Gao Xinbo,Peng Jianhua.Deployment Optimization of the Self-organized Network on Near Space Platforms Based on the Game Theoretical Learning Algorithm[J].Journal of Xidian University,2013,40(5):188-193.

[20]刘英挺,李晨曦,张海林,等.WRAN多小区上行链路信道与功率的联合分配[J].西安电子科技大学学报,2012,39 (4):39-45.

Liu Yingting,Li Chenxi,Zhang Hailin,et al.Joint Channel and Power Allocation for the Uplink in Multi-cells of the WRAN[J].Journal of Xidian University,2012,39(4):39-45.

(编辑:齐淑娟)

Wireless network access selection method with the non-cooperative game

ZHAO Jing,LI Xinghua,XUE Feijie,MA Jianfeng
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

The coexistence of various wireless access networks has been widely recognized in the next generation network.As a different network access form,how the clients at the instance of their needs will select the access network has become a widespread concern.For this problem,according to the noncooperation between different access networks and the noncooperation relationship between the access network and the clients,a non-cooperative game model based on the payoff function is established.On the basis of the multi-attribute decision theory,the model uses the gray correlation analysis method to normalize the performance parameters of the network,chooses the grey relation grade as the payoff function,compares and selects excellent networks which the clients can access.By solving the Nash equilibrium between the clients and excellent networks,the clients can access the appropriate network. Experimental results demonstrate that the method can effectively select the appropriate network according to the needs of the clients.

non-cooperative game;Nash equilibrium;gray correlation analysis method;wireless network;selection methods

TP393

A

1001-2400(2014)05-0098-07

2013-07-10< class="emphasis_bold">网络出版时间:

时间:2014-01-12

国家自然科学基金资助项目(U1135002,61372075,61202389,61100230,61309016);中央高校基本科研业务费资助项目(K5051303004);国家密码发展基金资助项目(MMJJ201201004);地理信息国家重点实验室开放课题资助项目(SKLGIE2013-M-4-1)

赵 婧(1989-),女,西安电子科技大学硕士研究生,E-mail:zhaojing201534@gmail.com.

http://www.cnki.net/kcms/doi/10.3969/j.issn.1001-2400.2014.05.017.html

10.3969/j.issn.1001-2400.2014.05.017