异构网络选择的一种新博弈模型

徐 鹏,方旭明,向 征,陈美荣

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