異構網絡選擇的一種新博弈模型

徐 鵬,方旭明,向 征,陳美榮

（1.西南交通大學信息編碼與傳輸省重點實驗室,成都610031;2.成都高等紡織專科學校電子信息與電氣工程系,成都 611731）

異構網絡選擇的一種新博弈模型

徐 鵬1,方旭明1,向 征1,陳美榮2

（1.西南交通大學信息編碼與傳輸省重點實驗室,成都610031;2.成都高等紡織專科學校電子信息與電氣工程系,成都 611731）

目前對于異構網絡選擇問題的研究大多沒有充分考慮用戶和網絡的相互選擇,為此提出一種新的異構網絡選擇博弈模型,通過用戶與網絡相互選擇得到該博弈的穩定匹配。算法性能分析與仿真驗證表明,該模型相對于用戶決策模型提高了網絡滿意度,相對于網絡決策模型提高了用戶滿意度,即最終用戶與網絡得到了雙贏。

異構網絡選擇;匹配博弈;滿意度;穩定匹配

1 引 言

近年來無線移動通信技術的快速發展與部署,使得移動通信接入網絡呈現出多樣化與異構的特征,包括GSM（G lobal System for Mobile Communications）、UMTS（Universal Mobile Telecommunications System）、WLANs（Wireless Local Area Networks）、WiMAX（Worldwide Interoperability for Microwave Access）、衛星網絡和藍牙網絡等[1]。各種異構接入網絡適用于不同的場合以及提供側重不同的服務,在不同的限制條件下用戶和網絡如何進行有效和適合的相互選擇變得越來越重要。

以用戶為中心的網絡選擇問題主要是指用戶將依賴智能網絡選擇判決策略進行最優選擇,該問題通常是通過考慮用戶的滿意度或者價格,然后根據不同的目標對定義不同的選擇標準來解決的[2]。文獻[1]提出了一種以用戶為中心的動態選擇機制,主要使用了用戶自定義的策略和一些包括物理層、鏈路層和應用層的跨層信息。文獻[3]提出了由用戶應用來確定網絡選擇同時考慮網絡的特征和費用。文獻[4]通過引入層次分析法（Analytic Hierarchy Processing,AHP）和灰度關聯法（Grey Relational Analysis,GRA）來對備選網絡進行排序,進而進行選擇。文獻[5]提出基于效用函數的選擇機制,這里效用函數定義與相應用戶的服務請求有關。以網絡為中心的網絡選擇問題主要是指網絡在考慮了網絡收益和保證其它用戶不受影響的情況下,選擇適合的客戶[2]。文獻[6]提出了一種以網絡為中心的選擇機制,目的是最優分配終端用戶以最大化頻譜效率。文獻[7]提出了將網絡選擇建模為博弈過程,網絡為博弈方對用戶進行分配,但是有些沖突不可避免。在此基礎上文獻[8]引入網絡效率和容量解決了可能的沖突問題。上述文獻的不足在于都是只從一個角度考慮網絡選擇問題,在進行選擇的時候要么忽略了網絡要么忽略了用戶,從而可能降低系統的性能或收益。同時許多經濟學模型可以很好地解決無線網絡中的資源分配與網絡選擇等問題,定價機制和博弈論等工具被廣泛地應用于解決沖突和相互作用的問題。文獻[9]引入了基于定價機制的經濟學模型來解決資源分配問題。文獻[10-12]聯合考慮了用戶和網絡,并建立非合作博弈模型來解決網絡選擇與資源分配問題,不足的是將用戶與網絡選擇分成兩個階段先用戶后網絡或者先網絡后用戶,并非真正意義上的雙向同時選擇。

基于上述原因,本文提出了一個新的異構網絡選擇博弈模型,該模型同時考慮用戶與網絡的選擇策略,并通過博弈使用戶與網絡進行相互選擇進而達到穩定匹配。新模型可以實現真正的雙向同時選擇,提升用戶與網絡的滿意度及系統整體的性能。

2 一種新的博弈模型

匹配問題最早由Gale和Shapley于1962年提出,并由Roth于1984年進行了重要的發展。之后關于匹配問題的研究大致沿著兩個方向進行:第一,設計并分析中央匹配機制;第二,研究不存在中央匹配機制時,雙方參與人通過搜尋達成匹配的過程。Roth發現了實際中使用匹配原則恰好符合博弈論的預測結果,從此匹配博弈逐漸成為研究各種匹配問題的主要方法。一般來講,匹配博弈存在兩個重要的假設:第一,參與人雙方從博弈開始就分別屬于兩個互不相交的集合,且位置不能互換;第二,只有經過雙方一致同意后才能形成匹配[13-14]。

異構網絡場景包含多個接入網絡（Radio Access Networks,RANs）,每個接入網絡都能為用戶提供接入服務。用戶可以接入任何單一的網絡但不限制于特定的網絡。這樣用戶和網絡形成互不相交的集合,用戶和網絡之間在一定的限制條件下進行相互選擇。同時用戶和網絡由于都有各自的需求及目標,每個策略或動作都被認為是理性的。設定某個時刻在異構網絡的多重覆蓋區域,存在多個用戶包括新用戶和切換過來的用戶,為了簡化分析過程假定每個用戶每次只能接入單一網絡,每個網絡每次也只能接入單一用戶,那么網絡選擇過程就可以建模為一對一匹配博弈。

假設兩個有限集合Net={n1,n2,…,np}和Usr={u1,u2,…,un}分別表示多重覆蓋區域的網絡集和用戶集。異構網絡選擇可以用圖1表示,其中網絡集Net={RAN-1,RAN-2,RAN-3,RAN-4}包含4個接入網絡,用戶集包括那些至少被兩個接入網絡覆蓋的用戶,圖中指至少被兩種不同灰度覆蓋的用戶。每個網絡（用戶）都對用戶（網絡）有各自的偏好選擇,且該偏好是理性的。這是因為參與人對其面臨的不同選擇總是可以做出比較和判斷,所以該偏好是完備的。又因為參與人的選擇是前后一致的,所以該偏好是可傳遞的。滿足了完備性和可傳遞性,就可以認為偏好是理性的[13,15]。表1為定義匹配博弈所涉及的符號。

圖1 網絡與用戶場景Fig.1 The scene of networks and users

表1 符號定義Table 1 The definition of signs

3 系統分析與建模

對于處于多重覆蓋區域的用戶和網絡存在多種情況,為了便于分析,這里只考慮所有用戶處于同樣的覆蓋區域,即這些用戶的網絡可選擇集是相同的。圖1中的虛線所選范圍即為研究目標區域。對于用戶來說,根據自身狀態、QoS需求、價格以及帶寬需求等選擇一個最優網絡,同樣地對于網絡來說,也需要根據自身狀態選擇最適合的客戶。

用戶主要受到幾個因素的影響,包括當前的移動性（v）、業務服務質量（q）、可以承受的費用（p）和所需帶寬（bw）,用向量u表示。其中業務服務等級包括時延α、抖動 β和丟包率γ3個變量。類似地,網絡受到影響的因素包括可以提供的速度支持v,提供的服務質q、服務的費用p和當前可用帶寬bwa,用向量n表示。

圖2 AHP計算權重Fig.2 Computing weights with AHP

對于各權重值的計算,采用文獻[16-17]中的AHP（Analytic Hierarchy Process）算法,分層方法如圖2所示。對于用戶和網絡都按此分層方法計算其權重值。AHP算法中首先考慮影響目標的因素個數n,通過兩兩比較各因素的相對權重,可以得到一個矩陣A=（aij）n×n,通過權重計算公式（18）可以得到各因素的權重wi,其中i,j={1,2,…,n}。

用滿意度作為該模型的效用,就構成了一個匹配模型G,即G:（Usr,Net,P,P）。其中用P（Su（j）,Sn（i））表示用戶和網絡的效用,其中j∈{1,2,…,p},i∈{1,2,…,n},P（μ）表示u、n的相互選擇的效用,用uij表示用戶選擇網絡j的效用,用nij表示網絡j選擇用戶i的效用,則效用矩陣P可以表示為

4 博弈模型的算法實現

對于得到的Su（j）,j∈{1,2,…,p}和Sn（i）,i∈{1,2,…,n}分別進行一個降序排列得到 Su（j）和Sn（i）,排在最前面的表示用戶和網絡最可能的選擇。算法描述如下:

（1）每個用戶首先選擇其滿意度向量 Su（j）中排在第一位的網絡,發送請求;

（2）每個網絡根據其Sn（i）中用戶的排序,對比步驟1的請求用戶,選擇排在比較靠前位置的用戶,拒絕其它請求;

（3）根據步驟2的結果,被拒絕的用戶繼續根據Su（j）中的排序向未被拒絕網絡中排在第一位的網絡發送請求;

（4）每個網絡根據Sn（i）排序,對比步驟3中請求用戶和步驟1中接受的用戶,選擇排序最靠前的用戶,拒絕其它用戶。

（5）重復步驟3和4,直到所有用戶都有網絡接入。

根據上述步驟可以得到每個用戶與網絡的對應匹配,對于該匹配博弈是否一定存在穩定匹配,由Gale和Shap ley在1962年給予了肯定的回答并證明了存在性。Gale又于1985年證明了穩定匹配也就是匹配博弈的均衡點。Roth和VandeVate、K lasus和Klijn分別于1990年和2007年給出了通過參與人的獨立決策,最終能夠收斂于穩定匹配的結論。即對于網絡選擇的匹配博弈模型,穩定匹配是一定存在的[14-15]。

5 數值分析結果

本文的仿真場景對文獻[4,18]進行了擴展,如圖4所示,覆蓋區域由 1個WiMAX、1個UMTS和 4個WLAN網絡組成,當用戶從其它區域切換到虛線覆蓋區域或處于虛線覆蓋區域發起新呼叫時,網絡選擇算法觸發。假設多重覆蓋區域的用戶有3種類型的服務需求,包括會話型、流媒體型和背景型業務,其對應的權重和滿意度采用第三部分介紹的計算方法。同樣地采用上節描述的網絡權重和滿意度的計算方法。在某時刻,用戶的業務需求和網絡狀態分別如表2和表3所示,權重計算如表4～7所示。假設n個用戶按業務類型等比例均勻分布在多重覆蓋區域,運動狀態分布為80%處于靜止或步行（v<6 km/h）,20%處于車載（v=80 km/h）狀態。

圖3 仿真場景Fig.3 Simulation scenario

表2 業務類型參數Table 2 The parameters of traffics

表3 網絡狀態參數Table 3 The parameters of networks

首先計算用戶的各權重值,n=4,用表4表示第一層權重計算過程,用表5表示對應不同業務類型時QoS權重計算,這里業務類型包括會話型、流媒體和背景型3種業務。

表4 第一層權重計算Table 4 Computing the first tier weights for users

表5 不同類型業務權重計算Table 5 Computing the weights of different traffic types

類似地,可以得到網絡的第一層權重,如表6所示。第二層權重需要區分具體網絡,這里考慮3種網絡類型WiMAX、UMTS和WLAN,其權重如表7所示。

表6 網絡第一層權重計算Table 6 Computing the first tier weights for networks

表7 WLAN權重計算Table 7 Computing the weights of WLAN

圖4（a）、（b）分別給出了不同業務類型的低速用戶選擇網絡與網絡選擇用戶的滿意度及排序,根據上節算法描述,對于3種類型用戶其最后符合匹配博弈的穩定匹配是 μ（uvoice）=UMTS,μ（ustream）=WiMAX,μ（ubackground）=WLAN2。類似地 ,從圖 5可以得到高速用戶的穩定匹配選擇為 μ（uvoice）=UMTS,μ（ustream）=W iMAX,μ（ubackground）=WLAN1。

圖4 低速用戶和網絡對應的滿意度Fig.4 The corresponding satisfaction degree of users and networks with low velocity

圖5 高速用戶和網絡的滿意度Fig.5 The corresponding satisfaction degree of users and networks with high velocity

為了體現匹配博弈算法的優越性,將算法與兩種常見的算法進行比較,一種是由用戶決策即用戶選擇滿意度最大的網絡接入,另外一種是由網絡決策即網絡選擇滿意度最大的用戶,其結果如圖6和圖7所示。在圖6（a）中可以得到匹配算法的用戶滿意度低于由用戶決策的算法,但是高于由網絡決策的算法。這是由于在用戶決策算法中忽略了網絡方的選擇過程,當然這可以增加用戶的服務體驗,但是完全犧牲了網絡方的利益。對于網絡決策算法由于不考慮用戶的選擇,最大化了網絡的滿意度如圖6（b）所示,同樣的不足在于降低了用戶的服務體驗,可能導致用戶選擇其它網絡。而匹配博弈算法綜合考慮用戶和網絡的選擇過程,在上述兩種算法中找到了一個平衡,即相對于用戶決策算法取得了較高的網絡滿意度,相對于網絡決策算法取得了較高的用戶滿意度,從而在某種意義上得到用戶與網絡的雙贏。

在圖6中我們看到了匹配博弈算法在低速用戶網絡選擇過程中的性能。對于高速用戶基于同樣的理由,可以類似地得到算法的性能如圖7所示。需要注意的是,與圖6區別在于網絡支持移動性的差別。

圖6 低速用戶和網絡的平均滿意度Fig.6 The average satisfaction degree of users and networks with low velocity

圖7 高速用戶和網絡的平均滿意度Fig.7 The average satisfaction degree of users and networkswith high velocity

6 結 語

本文提出了一種適用于異構網絡選擇的新博弈模型,不同于已有文獻從用戶或網絡任一方面進行判決,該模型基于不同準則分析了用戶與網絡相互選擇的匹配博弈過程,并找到了博弈的均衡點。仿真驗證表明可以使得用戶與網絡在選擇過程中得到了雙贏。另外,因為同時兼顧了用戶與運營商,該模型具有一定的實用前景,尤其是在單網絡資源匱乏又同時存在多個可選網絡時,可以提高資源的利用率和均衡負載。

[1] CAI Xue-jun,CHEN Ling,Sofia Rute,et al.Dynam ic and User-Centric Network Selection in Heterogeneous Networks[C]//Proceedings of IEEE International Conference on Performance,Computing,and Communications.New Orleans,Louisiana,USA:IEEE,2007:538-544.

[2] Pei X,Jiang T,Qu D,et al.Radio-Resource Management and Access-Control Mechanism Based on a Novel Economic Model in Heterogeneous Wireless Networks[J].IEEE Transactions on Vehicular T echnology,2010,59（6）:3047-3056.

[3] Noonan J,Perry P,Murphy J.Client controlled network selection[C]//Proceedings of the Fifth IEE International Conference on 3G Mobile Communication Technologies.Savoy-Place,London,UK:IEE,2004:543-547.

[4] Song Q,Jamalipour A.Network selection in an integrated wireless LAN and UMTS environment using mathematical modeling and computing techniques[J].IEEEWireless Communications,2005,12（3）:42-48.

[5] Chen Y,Yang N,Chang C.A Utility Function-based Access SelectionMethod for HeterogeneousWCDMA andWLAN Networks[C]//Proceedings of IEEE Conference on Personal,Indoor andMobile Radio Communications.LosAlam itos:IEEE,2007:1-5.

[6] Jia H,Zhang Z,Cheng P,et al.Study on network selection for next-generation heterogeneouswireless networks[C]//Proceedings of IEEE 17th International Symposium on Personal,Indoor and Mobile Radio Communications.Helsinki,Finland:IEEE,2006:1-5.

[7] Antoniou Josephina,PitsillidesAndreas.4G Converged Environment:Modeling Network Selection as a Game[C]//Proceedings of the 16th IST Mobile and Wireless Communications Summit.Budapest,Hungary:IEEE,2007:1-5.

[8] Charilas D,M arkaki O,Tragos E.A theoretical scheme for applying game theory and network selection mechanism s in access admission control[C]//Proceedings of the 3rd International Symposium on Wireless Pervasive Computing.Santorini,Greece:IEEE,2008:303-307.

[9] Alkhaw lani,Mohammed M,Hussein,et al.Intelligent radio network selection for next generation networks[C]//Proceedings of the 7th International Conference on Informatics and Systems.Cairo,Egyp t:IEEE,2010:1-7.

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

[11] Pervaiz H,Bigham J.Game Theoretical Formulation of Network Selection in Competing Wireless Networks:An Analytic Hierarchy Process Model[C]//Proceedings of the third International Conference on Next Generation Mobile App lications,Services and Technologies.Cardiff,UK:IEEE,2009:292-297.

[12] Cesana Matteo,Malanchini Ilaria,Capone Antonio.Modelling network selection and resource allocation in wireless access networkswith non-cooperative games[C]//Proceedings of the 5th IEEE International Conference onMobile Ad Hoc and Sensor Systems.Atlanta,USA:IEEE,2008:404-409.

[13] Alvin E Roth,Marilda A Oliveira Sotomayor.Two-sided matching:a study in game-theoretic modeling and analysis[M].London:Cambridge University Press,1992.

[14] Gabrielle Demange,Myrna Wooders.Group formation in economics:networks,clubs,and coalitions[M].London:Cambridge University Press,2005:11-49.

[15] 董保民,王運通,郭桂霞.合作博弈論[M].北京:中國市場出版社,2008.DONG Bao-min,WANG Yun-tong,GUO Gui-xia.Cooperative Game Theory[M].Beijing:China Market Press,2008.（in Chinese）

[16] Frederic P Miller,Agnes F Vandome,John McBrewster.Analytic Hierarchy Process[M].Beau Bassin:VDM Publishing House Ltd.,2009.

[17] Phillips-W ren G,Jain L C,Nakamatsu K,et al.Advances in Intelligent Decision Technologies[M].Heidelberg:Springer,2010.

[18] 袁堯,張玉成,董雯霞,等.基于二分圖匹配的多業務流網絡選擇機[J].軟件學報,2010,21（6）:1378-1390.YUAN Yao,ZHANG Yu-cheng,DONG Wen-xia,et al.Mu lti-Flow Network Fairness Selection Scheme Based on Weighted Bigraph Model[J].Journal of Software,2010,21（6）:1378-1390.（in Chinese）

A Novel Game M odel for Heterogeneous Network Selection

XU Peng1,FANG Xu-ming1,XIANG Zheng1,CHEN Mei-rong2
（1.Provincial Key Lab of Information Coding&Transmission,South west Jiaotong University,Chengdu 6 10031,China;2.Department of Electronic Information and Electrical Engineering,Chengdu Textile College,Chengdu 611731,China）

The issue of heterogeneous network selection is rarely concentrated on mutual selection between users and networks at present.A novel game model for heterogeneous network selection is proposed,and the stable matching of game is obtained through mutual selecting for both users and networks.The simulation results show that the proposed model improves the satisfaction degree of networks/users compared to the models based on user/network decision.Additionally,the proposed model makes the users and networks achieve a win-win situation.

heterogeneous network selection;matching game;satisfaction degree;stable matching

The National Natural Science Foundationof China（No.60772085）;Technology Research and Development Plan of the Ministry of Railways（2009X009-E）

TN929.5

A

10.3969/j.issn.1001-893x.2011.02.006

1001-893X（2011）02-0027-07

2010-11-11;

2010-12-28

國家自然科學基金資助項目（60772085）;鐵道部科技研究開發計劃重點課題（2009X009-E）

徐 鵬（1981-）,男,河南人,分別于2004年和2007年獲西南交通大學學士和碩士學位,現為博士研究生,主要研究方向為異構網絡與分層網絡無線資源管理;

XU Peng was born in Henan Province,in 1981.He

the B.S.degree and the M.S.degree from Southwest Jiaotong University in 2004 and 2007,respectively.He is currently working towarol the Ph.D.degree.His research interests include location technology,radio resourcemanagement of hybrid networks,wireless mesh network.

Email:pengxup@gmail.com

方旭明（1962-）,男,浙江人,教授、博士生導師,主要研究方向為無線移動通信網絡無線資源管理。

FANG Xu-ming was born in Zhejiang Province,in1962.He is now a professor and also the Ph.D.supervisor.His research interests include mobile ad hoc,wireless mesh and multi-hop relay networks,scheduling admission control,power control,and cognitive radio.