博弈論方法在混合無線網絡中網絡選擇問題研究中的應用

王昊+李建中

摘要：隨著無線網絡技術的日益發展以及人們對無線互聯的需求，各種適用于不同工作環境的無線網絡技術往往共同應用于人們的日常活動區域中。為了提高網絡的利用率與最大化自身收益，用戶往往會在不同的無線網絡中切換，選擇最合適網絡的進行連接。這種情況下，一個無線網絡用戶的行為變化會對其他用戶的網絡環境帶來嚴重的影響。博弈論在分析研究這類情況具有很大的優勢。本文簡單介紹了博弈論的基本概念，并總結了當前采用博弈論的方法研究解決混合無線網絡中網絡選擇問題的代表的工作。

關鍵詞： 混合無線網絡； 網絡選擇； 博弈論

中圖分類號： 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.