王昊+李建中

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

關(guān)鍵詞： 混合無線網(wǎng)絡(luò)； 網(wǎng)絡(luò)選擇； 博弈論

中圖分類號(hào)： TP391.41

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 2095-2163（2016）06-0141-03

0引言

近年來，隨著人們對無線網(wǎng)絡(luò)連接需要的日益增加，適用于不同工作情況與使用環(huán)境的無線網(wǎng)絡(luò)接入技術(shù)得到了飛速的發(fā)展。這些技術(shù)的提升進(jìn)步滿足了人們隨時(shí)隨地能夠接入到無線網(wǎng)絡(luò)中的理想訴求。人們使用的無線網(wǎng)絡(luò)連接設(shè)備，如筆記本電腦、平板電腦、手機(jī)等，往往同時(shí)配備了多種滿足不同通信需求的無線網(wǎng)絡(luò)接入技術(shù)，如適用于近距離通信需要的Zigbee、Bluetooth，以及適用于中遠(yuǎn)距離通信需要的WiFi、WiMax、2G、LTE等。而且，同一地區(qū)被多種無線網(wǎng)絡(luò)覆蓋的情況也大大增加了，如辦公室、商場或者是家中，這些區(qū)域往往普遍配設(shè)有無限局域網(wǎng)絡(luò)與蜂窩網(wǎng)絡(luò)，而蜂窩網(wǎng)絡(luò)常常也是由多家移動(dòng)網(wǎng)絡(luò)服務(wù)商各自優(yōu)化后、且分別提供的，如中國移動(dòng)、中國聯(lián)通等，如此這般的多種無線網(wǎng)絡(luò)接入技術(shù)共存的情況被稱為混合無線網(wǎng)絡(luò)。綜上可知，在此背景環(huán)境中，人們所能選擇的無線網(wǎng)絡(luò)的數(shù)量也必然增加。根據(jù)使用環(huán)境的各異以及用戶需求的不同，人們在選擇移動(dòng)設(shè)備所要連接的無線網(wǎng)絡(luò)時(shí)將會(huì)綜合考慮多種因素，如網(wǎng)絡(luò)的穩(wěn)定性、網(wǎng)絡(luò)能提供的帶寬以及使用網(wǎng)絡(luò)需要付出的代價(jià)等。網(wǎng)絡(luò)選擇中的基本問題就是研究在多種無線網(wǎng)絡(luò)共存的情況下，人們（設(shè)備）如何根據(jù)自身的需要，選擇出最合適的無線網(wǎng)絡(luò)，以及在選擇過程中設(shè)備更換無線網(wǎng)絡(luò)的行為趨勢。為了分析解決混合無線網(wǎng)絡(luò)中不同無線接入技術(shù)的選擇問題，目前已提出了多種方法，如文獻(xiàn)[1-2]提出的最大化用戶效用的選擇方法，文獻(xiàn)[3-5]提出的基于多種屬性滿足的決策制定方法等等。博弈論作為一種數(shù)學(xué)工具，常常用于研究分析在人們根據(jù)自己的情況選擇出最有利的策略時(shí)，參與者的行為變化趨勢以及不同參與者之間相互影響的情況。在無線網(wǎng)絡(luò)的研究中，由于博弈論在分析無線網(wǎng)絡(luò)設(shè)備選擇不同通信策略時(shí)其所獲得的收益情況與各個(gè)設(shè)備行為特點(diǎn)上的優(yōu)勢，越來越多的工作利用博弈理論來解決混合無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)選擇問題[6-7]。本文總結(jié)了目前一些利用博弈理論來解決混合無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)選擇問題的文章，給出了博弈理論在解決這類問題時(shí)的一般方法。

[JP3][BT4]1博弈論的基本概念以及網(wǎng)絡(luò)選擇問題的博弈模型[JP]

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

在博弈理論中，博弈是由博弈的參與者、參與者所能選擇的策略的集合、每個(gè)參與者選擇某種策略時(shí)所獲得的收益而構(gòu)成的優(yōu)選進(jìn)化過程，過程中包含著3個(gè)基本元素，現(xiàn)對其進(jìn)行如下定義描述。

1）參與者。博弈中能夠選擇自身策略的單位，可以是某一個(gè)體、也可以是某一群體，其目標(biāo)是通過選擇某種策略以使自己收益最大化，當(dāng)目標(biāo)為削減成本時(shí)為最小化。

2）策略集。策略集中包含了參與者能夠選擇的所有策略，每輪博弈時(shí)參與者將在其中選擇一個(gè)以指導(dǎo)自己的行為。

3）收益。參與者選擇某個(gè)策略時(shí)所能獲得的效用，該效用由參與者選擇的策略與其他參與者選擇的策略共同決定。

[BT5]1.2博弈結(jié)果描述方法

具體地，針對存在多個(gè)參與者的博弈描述中，每個(gè)參與者將根據(jù)收益的大小采取不同的策略，同時(shí)某個(gè)參與者采取的策略也將影響到其他參與者的收益。當(dāng)博弈重復(fù)進(jìn)行的時(shí)候，各參與者是否可以最終達(dá)到某一平衡狀態(tài)，即參與者是否可以找到一種最合適的策略，使得博弈終止。博弈是否能夠終止，以及何時(shí)達(dá)到終止是博弈論中的重要研究部分。下面將調(diào)引最常用的描述博弈終止的狀態(tài)定義，即納什均衡狀態(tài)。

納什均衡狀態(tài)用于描述這樣一種情況，即在一個(gè)博弈中，所有的參與者都選擇好自己的策略后，如果任意一個(gè)參與者都不能在其他參與者保持所選策略也不變的前提下，通過改變自身采取的策略使得自己的收益增大。這時(shí)，就可說系統(tǒng)達(dá)到了納什平衡狀態(tài)。

如果博弈的參與者用集合N={1，2，…，n}來表示，參與者可以選擇的策略用集合S來表示，參與者i所選擇的策略用si來表示si∈S，那么s*={s1*，s2*，…，sn*}為納什均衡，當(dāng)且僅當(dāng)對任意的i∈N，存在：

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

其中，s*-i表示除了參與者i以外其他參與者所選擇的策略，ui（）為參與者的收益計(jì)算函數(shù)。并不是所有的博弈均存在納什均衡；同時(shí)，有的博弈可能存在多個(gè)納什均衡。

[BT5]1.3網(wǎng)絡(luò)選擇問題的博弈模型

網(wǎng)絡(luò)選擇問題存在3種博弈情況。對于每種博弈情況，現(xiàn)做出分析概述如下。

1）用戶與用戶之間的博弈。這種情況下，博弈的參與者均為需要使用無線網(wǎng)絡(luò)的用戶，多個(gè)無線網(wǎng)絡(luò)用戶將分享若干個(gè)無線網(wǎng)絡(luò)接入服務(wù)，每個(gè)用戶所能選擇的無線網(wǎng)絡(luò)接入點(diǎn)就是用戶所能采取的策略。用戶通過選擇不同的無線網(wǎng)絡(luò)接入點(diǎn)來最大化自己的收益或者最小化自己使用無線網(wǎng)絡(luò)服務(wù)所需支付的代價(jià)。

2）無線網(wǎng)絡(luò)服務(wù)商之間的博弈。這種情況下，博弈的參與者為能夠向用戶提供無線網(wǎng)絡(luò)服務(wù)的各個(gè)網(wǎng)絡(luò)服務(wù)商。各個(gè)無線網(wǎng)絡(luò)服務(wù)商通過采取不同的自費(fèi)策略來吸引更多的用戶選用自己的無線網(wǎng)絡(luò)服務(wù)，從而達(dá)成最大化自己收益的目的。

3）無線網(wǎng)絡(luò)服務(wù)商與用戶之間的博弈。參與者分別為無線網(wǎng)絡(luò)服務(wù)商與用戶。服務(wù)商通過選擇不同服務(wù)資費(fèi)標(biāo)準(zhǔn)與服務(wù)對象來最大化自己的收益，而用戶則通過選擇不同的服務(wù)商來最大化自己可能獲得的網(wǎng)絡(luò)效用。

[BT4]2博弈論在網(wǎng)絡(luò)選擇問題上的主要研究情況

[BT5]2.1用戶與用戶之間的博弈

文獻(xiàn)[8]將網(wǎng)絡(luò)選擇問題描述為各個(gè)自利用戶之間的非合作博弈，并使用擁塞博弈模型來研究用戶的行為情況。在該博弈中，用戶可以在多個(gè)可用的無線網(wǎng)絡(luò)的不同頻段中選擇其中之一進(jìn)行連接，在選擇某個(gè)網(wǎng)絡(luò)后，該用戶將會(huì)造成一定程度的網(wǎng)絡(luò)擁塞，同時(shí)用戶需要為其造成的擁塞支付費(fèi)用，而費(fèi)用的高低將由網(wǎng)絡(luò)當(dāng)前的擁塞程度決定。作者形式化地給出了網(wǎng)絡(luò)擁塞程度的描述以及用戶所需支付的費(fèi)用。實(shí)現(xiàn)過程是將該用戶的網(wǎng)絡(luò)選擇情況用一組布爾值來設(shè)定其表示，如表示用戶u是否選擇了a網(wǎng)絡(luò)的布爾值bua。當(dāng)用戶u選擇了網(wǎng)絡(luò)a時(shí)，bua=1，如果沒有選擇網(wǎng)絡(luò)a，bua=0。此后，研究利用整數(shù)規(guī)劃的方法求解了該博弈的納什均衡策略。

文獻(xiàn)[9]利用演化博弈模型來研究用戶的網(wǎng)絡(luò)選擇問題。演化博弈在傳統(tǒng)的博弈理論中加入了種群的概念，種群用于表示一組相同類型的用戶，種群中的用戶可以改變自己的策略以使種群的總體收益增加，或者使種群中其他用戶改變自己的行為，以達(dá)到收益均衡的目的。該項(xiàng)研究利用了演化博弈中的復(fù)制動(dòng)態(tài)來研究一群同類用戶的行為變化情況。復(fù)制動(dòng)態(tài)用來表示種群中選擇不同策略的用戶的比例的變化情況，數(shù)學(xué)上是利用常微分方程來構(gòu)建表示， 其對應(yīng)公式為：

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

其中，xi表示種群中采用策略i的個(gè)體占種群全體的比例，xi=ni/N，ni為選擇i策略的用戶的數(shù)量，N表示種群中用戶的總數(shù)量。fi（t）表示參與者選擇策略i所獲得的收益，（t）表示該種群中所有參與者獲得的平均收益。

文獻(xiàn)[10]描述了裝備有多種無線網(wǎng)絡(luò)通信技術(shù)的設(shè)備，在不同網(wǎng)絡(luò)之間切換服務(wù)，以達(dá)到自身獲得的網(wǎng)絡(luò)吞吐量最大的目的。文章給出了2類不同的無線網(wǎng)絡(luò)技術(shù)的帶寬分配模型，全面分析在了每種無線網(wǎng)絡(luò)技術(shù)下用戶的行為變化情況，給出了用戶最大化自身收益的算法，并證明了在同種無線通信技術(shù)內(nèi)部切換無線網(wǎng)絡(luò)基站的情況下，系統(tǒng)存在納什均衡，即用戶在經(jīng)歷有限的基站選擇變化后，所有用戶均將達(dá)到穩(wěn)定狀態(tài)，而無需繼續(xù)改變自身的選擇。

[BT5]2.2無線網(wǎng)絡(luò)服務(wù)商之間的博弈

文獻(xiàn)[11]提出了一個(gè)由4部分組成的用于分配管理無線傳輸資源系統(tǒng)框架，其中包括網(wǎng)絡(luò)層分配、容量預(yù)留機(jī)制、用戶接入控制以及連接層分配。作者將帶寬分配問題描述為不同接入網(wǎng)絡(luò)之間的博弈，同時(shí)在系統(tǒng)達(dá)到納什均衡時(shí)，網(wǎng)絡(luò)總效益最大。

文獻(xiàn)[12]將2個(gè)獨(dú)立的無線局域網(wǎng)之間的接入控制問題描述為多階段的非合作博弈問題。該博弈中的參與者為2個(gè)無線局域網(wǎng)，而策略集則為用戶發(fā)出的網(wǎng)絡(luò)接入請求。博弈的結(jié)果給出了2個(gè)網(wǎng)絡(luò)最大化自身收益時(shí)，網(wǎng)絡(luò)接入請求在2個(gè)無線網(wǎng)絡(luò)中的分布情況，

文獻(xiàn)[13]描述了在多個(gè)無線網(wǎng)絡(luò)共存的環(huán)境中，存在一個(gè)移動(dòng)著的用戶。為了保證負(fù)載平衡以及減少用戶在各個(gè)網(wǎng)絡(luò)的交接，作者提出了一合作博弈的方法。參與者為區(qū)域中各個(gè)可以被用戶連接的無線網(wǎng)絡(luò)，其策略集為用戶使用每個(gè)網(wǎng)絡(luò)的優(yōu)先級(jí)。每個(gè)候選網(wǎng)絡(luò)的收益為當(dāng)前網(wǎng)絡(luò)負(fù)載、預(yù)定負(fù)載界限與網(wǎng)絡(luò)懲罰權(quán)重的函數(shù)。博弈的目標(biāo)是使每個(gè)候選網(wǎng)絡(luò)的收益值最大。

2.3無線網(wǎng)絡(luò)服務(wù)商與用戶之間的博弈

文獻(xiàn)[14]利用將無線網(wǎng)絡(luò)服務(wù)商與用戶之間的競爭描述為雙方博弈的方式，提出了一種防止擁塞的控制機(jī)制。作者提出框架包括2個(gè)博弈，其中一個(gè)為接入控制博弈，另一個(gè)為負(fù)載控制博弈。接入控制博弈利用了經(jīng)典的囚徒困境模型，參與者為各種用戶-服務(wù)商對。每一種服務(wù)請求代表了每個(gè)參與者具有2個(gè)策略選擇的博弈。服務(wù)商可以接受或者拒絕服務(wù)請求，而用戶可以選擇繼續(xù)接受服務(wù)或者停止接受當(dāng)前服務(wù)商的服務(wù)。作者討論了該博弈的純策略納什均衡的存在情況。在負(fù)載控制博弈中，用戶在不停止傳輸?shù)那闆r下選擇是否離開當(dāng)前服務(wù)商，而服務(wù)商也可以選擇是否終止提供服務(wù)。文章表明當(dāng)服務(wù)商同時(shí)運(yùn)用2種策略時(shí)，得到的收益將會(huì)達(dá)至最大。

[BT4]3結(jié)束語

本文總結(jié)了當(dāng)前利用博弈理論分析解決混合無線網(wǎng)絡(luò)中網(wǎng)絡(luò)選擇問題的一些代表性工作。值得注意的是，在利用博弈論解決該問題時(shí)，不能僅停留在判斷是否存在納什均衡的層面上，還需對如何達(dá)到納什均衡進(jìn)行研究。博弈論分析了混合無線網(wǎng)絡(luò)中的參與者在為了最大化收益時(shí)的行為情況，為提出更加有效的網(wǎng)絡(luò)選擇方案作出了有益、且實(shí)用的貢獻(xiàn)。

參考文獻(xiàn)：

[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.