一種非合作博弈下的無線網絡接入選擇方法

趙 婧,李興華,薛飛潔,馬建峰

(西安電子科技大學計算機學院,陜西西安 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