博弈论方法在混合无线网络中网络选择问题研究中的应用

王昊+李建中

摘要：随着无线网络技术的日益发展以及人们对无线互联的需求，各种适用于不同工作环境的无线网络技术往往共同应用于人們的日常活动区域中。为了提高网络的利用率与最大化自身收益，用户往往会在不同的无线网络中切换，选择最合适网络的进行连接。这种情况下，一个无线网络用户的行为变化会对其他用户的网络环境带来严重的影响。博弈论在分析研究这类情况具有很大的优势。本文简单介绍了博弈论的基本概念，并总结了当前采用博弈论的方法研究解决混合无线网络中网络选择问题的代表的工作。

关键词： 混合无线网络； 网络选择； 博弈论

中图分类号： TP391.41

文献标志码： A

文章编号： 2095-2163（2016）06-0141-03

0引言

近年来，随着人们对无线网络连接需要的日益增加，适用于不同工作情况与使用环境的无线网络接入技术得到了飞速的发展。这些技术的提升进步满足了人们随时随地能够接入到无线网络中的理想诉求。人们使用的无线网络连接设备，如笔记本电脑、平板电脑、手机等，往往同时配备了多种满足不同通信需求的无线网络接入技术，如适用于近距离通信需要的Zigbee、Bluetooth，以及适用于中远距离通信需要的WiFi、WiMax、2G、LTE等。而且，同一地区被多种无线网络覆盖的情况也大大增加了，如办公室、商场或者是家中，这些区域往往普遍配设有无限局域网络与蜂窝网络，而蜂窝网络常常也是由多家移动网络服务商各自优化后、且分别提供的，如中国移动、中国联通等，如此这般的多种无线网络接入技术共存的情况被称为混合无线网络。综上可知，在此背景环境中，人们所能选择的无线网络的数量也必然增加。根据使用环境的各异以及用户需求的不同，人们在选择移动设备所要连接的无线网络时将会综合考虑多种因素，如网络的稳定性、网络能提供的带宽以及使用网络需要付出的代价等。网络选择中的基本问题就是研究在多种无线网络共存的情况下，人们（设备）如何根据自身的需要，选择出最合适的无线网络，以及在选择过程中设备更换无线网络的行为趋势。为了分析解决混合无线网络中不同无线接入技术的选择问题，目前已提出了多种方法，如文献[1-2]提出的最大化用户效用的选择方法，文献[3-5]提出的基于多种属性满足的决策制定方法等等。博弈论作为一种数学工具，常常用于研究分析在人们根据自己的情况选择出最有利的策略时，参与者的行为变化趋势以及不同参与者之间相互影响的情况。在无线网络的研究中，由于博弈论在分析无线网络设备选择不同通信策略时其所获得的收益情况与各个设备行为特点上的优势，越来越多的工作利用博弈理论来解决混合无线网络中的网络选择问题[6-7]。本文总结了目前一些利用博弈理论来解决混合无线网络中的网络选择问题的文章，给出了博弈理论在解决这类问题时的一般方法。

[JP3][BT4]1博弈论的基本概念以及网络选择问题的博弈模型[JP]

[BT5]1.1博弈论的基本元素

在博弈理论中，博弈是由博弈的参与者、参与者所能选择的策略的集合、每个参与者选择某种策略时所获得的收益而构成的优选进化过程，过程中包含着3个基本元素，现对其进行如下定义描述。

1）参与者。博弈中能够选择自身策略的单位，可以是某一个体、也可以是某一群体，其目标是通过选择某种策略以使自己收益最大化，当目标为削减成本时为最小化。

2）策略集。策略集中包含了参与者能够选择的所有策略，每轮博弈时参与者将在其中选择一个以指导自己的行为。

3）收益。参与者选择某个策略时所能获得的效用，该效用由参与者选择的策略与其他参与者选择的策略共同决定。

[BT5]1.2博弈结果描述方法

具体地，针对存在多个参与者的博弈描述中，每个参与者将根据收益的大小采取不同的策略，同时某个参与者采取的策略也将影响到其他参与者的收益。当博弈重复进行的时候，各参与者是否可以最终达到某一平衡状态，即参与者是否可以找到一种最合适的策略，使得博弈终止。博弈是否能够终止，以及何时达到终止是博弈论中的重要研究部分。下面将调引最常用的描述博弈终止的状态定义，即纳什均衡状态。

纳什均衡状态用于描述这样一种情况，即在一个博弈中，所有的参与者都选择好自己的策略后，如果任意一个参与者都不能在其他参与者保持所选策略也不变的前提下，通过改变自身采取的策略使得自己的收益增大。这时，就可说系统达到了纳什平衡状态。

如果博弈的参与者用集合N={1，2，…，n}来表示，参与者可以选择的策略用集合S来表示，参与者i所选择的策略用si来表示si∈S，那么s*={s1*，s2*，…，sn*}为纳什均衡，当且仅当对任意的i∈N，存在：

[HT5SS]ui（s*i，s*-i）≥ui（s'i，s*-i）[JY]（1）

其中，s*-i表示除了参与者i以外其他参与者所选择的策略，ui（）为参与者的收益计算函数。并不是所有的博弈均存在纳什均衡；同时，有的博弈可能存在多个纳什均衡。

[BT5]1.3网络选择问题的博弈模型

网络选择问题存在3种博弈情况。对于每种博弈情况，现做出分析概述如下。

1）用户与用户之间的博弈。这种情况下，博弈的参与者均为需要使用无线网络的用户，多个无线网络用户将分享若干个无线网络接入服务，每个用户所能选择的无线网络接入点就是用户所能采取的策略。用户通过选择不同的无线网络接入点来最大化自己的收益或者最小化自己使用无线网络服务所需支付的代价。

2）无线网络服务商之间的博弈。这种情况下，博弈的参与者为能够向用户提供无线网络服务的各个网络服务商。各个无线网络服务商通过采取不同的自费策略来吸引更多的用户选用自己的无线网络服务，从而达成最大化自己收益的目的。

3）无线网络服务商与用户之间的博弈。参与者分别为无线网络服务商与用户。服务商通过选择不同服务资费标准与服务对象来最大化自己的收益，而用户则通过选择不同的服务商来最大化自己可能获得的网络效用。

[BT4]2博弈论在网络选择问题上的主要研究情况

[BT5]2.1用户与用户之间的博弈

文献[8]将网络选择问题描述为各个自利用户之间的非合作博弈，并使用拥塞博弈模型来研究用户的行为情况。在该博弈中，用户可以在多个可用的无线网络的不同频段中选择其中之一进行连接，在选择某个网络后，该用户将会造成一定程度的网络拥塞，同时用户需要为其造成的拥塞支付费用，而费用的高低将由网络当前的拥塞程度决定。作者形式化地给出了网络拥塞程度的描述以及用户所需支付的费用。实现过程是将该用户的网络选择情况用一组布尔值来设定其表示，如表示用户u是否选择了a网络的布尔值bua。当用户u选择了网络a时，bua=1，如果没有选择网络a，bua=0。此后，研究利用整数规划的方法求解了该博弈的纳什均衡策略。

文献[9]利用演化博弈模型来研究用户的网络选择问题。演化博弈在传统的博弈理论中加入了种群的概念，种群用于表示一组相同类型的用户，种群中的用户可以改变自己的策略以使种群的总体收益增加，或者使种群中其他用户改变自己的行为，以达到收益均衡的目的。該项研究利用了演化博弈中的复制动态来研究一群同类用户的行为变化情况。复制动态用来表示种群中选择不同策略的用户的比例的变化情况，数学上是利用常微分方程来构建表示， 其对应公式为：

[HT5SS]x·i（t）=xi[fi（t）-（t）][JY]（2）

其中，xi表示种群中采用策略i的个体占种群全体的比例，xi=ni/N，ni为选择i策略的用户的数量，N表示种群中用户的总数量。fi（t）表示参与者选择策略i所获得的收益，（t）表示该种群中所有参与者获得的平均收益。

文献[10]描述了装备有多种无线网络通信技术的设备，在不同网络之间切换服务，以达到自身获得的网络吞吐量最大的目的。文章给出了2类不同的无线网络技术的带宽分配模型，全面分析在了每种无线网络技术下用户的行为变化情况，给出了用户最大化自身收益的算法，并证明了在同种无线通信技术内部切换无线网络基站的情况下，系统存在纳什均衡，即用户在经历有限的基站选择变化后，所有用户均将达到稳定状态，而无需继续改变自身的选择。

[BT5]2.2无线网络服务商之间的博弈

文献[11]提出了一个由4部分组成的用于分配管理无线传输资源系统框架，其中包括网络层分配、容量预留机制、用户接入控制以及连接层分配。作者将带宽分配问题描述为不同接入网络之间的博弈，同时在系统达到纳什均衡时，网络总效益最大。

文献[12]将2个独立的无线局域网之间的接入控制问题描述为多阶段的非合作博弈问题。该博弈中的参与者为2个无线局域网，而策略集则为用户发出的网络接入请求。博弈的结果给出了2个网络最大化自身收益时，网络接入请求在2个无线网络中的分布情况，

文献[13]描述了在多个无线网络共存的环境中，存在一个移动着的用户。为了保证负载平衡以及减少用户在各个网络的交接，作者提出了一合作博弈的方法。参与者为区域中各个可以被用户连接的无线网络，其策略集为用户使用每个网络的优先级。每个候选网络的收益为当前网络负载、预定负载界限与网络惩罚权重的函数。博弈的目标是使每个候选网络的收益值最大。

2.3无线网络服务商与用户之间的博弈

文献[14]利用将无线网络服务商与用户之间的竞争描述为双方博弈的方式，提出了一种防止拥塞的控制机制。作者提出框架包括2个博弈，其中一个为接入控制博弈，另一个为负载控制博弈。接入控制博弈利用了经典的囚徒困境模型，参与者为各种用户-服务商对。每一种服务请求代表了每个参与者具有2个策略选择的博弈。服务商可以接受或者拒绝服务请求，而用户可以选择继续接受服务或者停止接受当前服务商的服务。作者讨论了该博弈的纯策略纳什均衡的存在情况。在负载控制博弈中，用户在不停止传输的情况下选择是否离开当前服务商，而服务商也可以选择是否终止提供服务。文章表明当服务商同时运用2种策略时，得到的收益将会达至最大。

[BT4]3结束语

本文总结了当前利用博弈理论分析解决混合无线网络中网络选择问题的一些代表性工作。值得注意的是，在利用博弈论解决该问题时，不能仅停留在判断是否存在纳什均衡的层面上，还需对如何达到纳什均衡进行研究。博弈论分析了混合无线网络中的参与者在为了最大化收益时的行为情况，为提出更加有效的网络选择方案作出了有益、且实用的贡献。

参考文献：

[1]

BARI F， LEUNG V. Use of nonmonotonic utility in multi-attribute network selection[C]//Processings of Wireless Telecommunications Symposium 2007. Pomona：IEEE， 2001：1–8.

[2] NGUYEN-VUONG Q T， GHAMRIDOUDANE Y， AGOULMINE N. On utility models for access network selection in wireless heterogeneous networks[C]//Processings of Network Operations and Management Symposium 2008. Salvador： IEEE， 2001：144-151.

[3] WANG L， BINET D. TRUST： a triggerbased automatic subjective weighting method for network selection[C]//Processings of Fifth Advanced International Conference On Telecommunications 2009. Venice：IEEE， 2009： 362-368.

[4] BAKMAZ B， BOJKOVIC Z， BAKMAZ M. Network selection algorithm for heterogeneous wireless environment[C]//Processings of IEEE 18th International Symposium on Personal， Indoor and Mobile Radio Communications 2007. Athens：IEEE， 2007： 1-4.

[5] BARI F， LEUNG V. Automated network selection in a heterogeneous wireless network environment[J]. Network， IEEE， 2007， 21（1）： 34-40.

[6] STEVENSNAVARRO E， WONG V W S. Comparison between vertical handoff decision algorithms for heterogeneous wireless networks[C]//Processings of Vehicular technology conference 2006. Melbourne：IEEE， 2006： 947-951.

[7] ZHANG W. Handover decision using fuzzy MADM in heterogeneous networks[C]//Processings of Wireless Communications and Networking Conference 2004. Atlanta：IEEE， 2004： 653-658.

[8] MALANCHINI I， CESANA M， GATTI N. Network selection and resource allocation games for wireless access networks[J]. IEEE Transactions on Mobile Computing， 2013， 12（12）： 2427-2440.

[9] NIYATO D， HOSSAIN E. Dynamics of network selection in heterogeneous wireless networks： an evolutionary game approach[J]. IEEE Transactions on Vehicular Technology， 2009， 58（4）：2008-2017.

[10]ARYAFAR E， KESHAVARZ-HADDAD A， WANG M， et al. RAT selection games in HetNets[C]//Proceedings of INFOCOM 2013. Turin：IEEE， 2013：998-1006.

[11]NIYATO D， HOSSAIN E. A noncooperative gametheoretic framework for radio resource management in 4G heterogeneous wireless access networks[J]. Mobile Computing， IEEE Transactions on， 2008， 7（3）：332-345.

[12]CHARILAS D E， MARKAKI O I， VLACHEAS P T. Admission control as a noncooperative multistage game between wireless networks[C]//Processings of Systems， International Conference on Signals and Image 2009. Chalkida：IEEE， 2009： 1-5.

[13]CHANG C J， TSAI T L， CHEN Y H. Utility and gametheory based network selection scheme in heterogeneous wireless networks[C]//Processings of Wireless Communications and Networking Conference 2009. Budapest：IEEE， 2009：1-5.

[14]CHARILAS D E， PANAGOPOULOS A D， VLACHEAS P， et al. Congestion avoidance control through noncooperative games between customers and service providers[C]//Mobile Lightweight Wireless Systems. Berlin Heidelberg： Springer ， 2009（13）： 53-62.