博弈论在网络拥塞控制中的应用

1、博弈论在网络拥塞控制中的应用ISSN 1009-3044 E-mail:凹:ufComputer Knowledge and Technology电脑知识与技术/ Vol.7, No.31, November 2011 Tel:+86-551-5690963 5690964 博弈论在网络拥塞控制中的应用钟伯成(上海工程技术大学电子电气学院，上海201620)摘要:博弈论研究多个独立的决策者之间的冲突与合作，而网络拥塞控制中端用户行为典型的构成了一种非合作博弈。该文基于博弈论方法，将网络拥塞控制问题模型化为非合作博弈，通过一种有效的带宽使用定价与收费机制，使博弈的Nash均衡解达到全局最优，导致

2、有效与公平的网络带宽分配。关键词:博弈论;网络;拥塞控制;纳什均衡中图分类号:TP393 文献标识码:A文章编号:1009-3044(2011)31-7744-03Game Theoretical Application in the Network Congestion Control ZHONG Bo-cheng (College ofElectronic & Electrica1 Engineering, Shanghai University ofEngineering Science, Shanghai 201620, China) Abstract: Game theorr

3、esearches conflict and cooperation among independent decision-makers, while in the problem of network conges?tion control host users behaviores typically form a noncooperation game. In the paper, based on game theroy the problem of network con?gestion control was modeled a noncooperation game. With

4、a effective mechanism of bandwidth pricing,the network congestion game can reach the global optimization Nash equilibrium, which can distribute the network bendwidth effectively and equally. Key words: game theory; network; congestion control; Nash equilibrium 曰前Intemet的网络拥塞控制机制提供一种端到端的速率控制，端系统(用户)根

5、据相应的网络信息判断网络当前的拥塞状况，并自觉地据此调整发向网络的流速以达到拥塞控制的目的。随着Intemet的发展，人们对网络流量控制进行了大量研究，使端到端的速率控制机制不断完善。但是迄今大部分的流量控制方案均建立在端用户自愿合作的基础上，严重依赖端用户的行为。随着In?temet从一个小的科研实验网络发展为大型商业网络，上述端用户自愿合作的假设不再成立。应用的多样性与商业化等各种因素自然地导致以追求个人利益最大化的不合作与竞争行为。这种行为可能造成网络带宽的不公平占用，甚至拥塞崩溃，从而严重影响Intemet的稳定性。因而有必要研究这种非合作行为对IP网络的影响，设计一种不依赖端用户合作

6、的速率控制方法，使网络按预定的目标运行博弈论为研究非合作行为下的速率控制提供了一个自然的框架飞网络中的端用户可看成速率控制博弈中的参与者，通过选择不同的策略(如速率等)进行博弈。参与者在对网络带宽的需求方面相互竞争，体现非合作性且不知道网络上其他端用户所采取策略的具体信息。在不合作速率控制方案中，各用户在其可行策略中选择最优化自己性能目标的策略。在一个网络博弈中，由于用户的性能不仅依赖于自己的策略，而且依赖其他用户的策略，因而这种操作模式导致一种动态行为。当用户实现其最优控制策略时，一个关键问题是网络能否收敛到一个均衡操作点，使得没有用户有意愿单独修改其速率控制策略，用博弈论的术语，这样的点即

7、为Nash均衡点飞本文基于博弈论方法提出了一种不依赖端系统用户合作的IP网络拥塞控制框架，将网络中的流量源模型化为网络博弈中的局中人，竞争共享网络带宽资源，通过一种有效的带宽使用定价与收费机制，使博弈的NASH均衡解达到全局最优，导致有效与公平的网络带宽分配。1问题原型考虑N个用户共享一个带宽为C的通信链路，设用户i的发送速率为矶，其效用函数为uJx，)是用户速率Z的函数，表示用户对使用资源(带宽)的满意度。对效用函数作如下假设，假设1对各用户，在X，;. 0上，效用函数uJx，)是凹的，严格增的与连续的;在xi>O上uJx，)是连续可微的;在EX, =0点的右导数u，(O)有界。31假

8、设1中的凹性相应于ShenkerI的弹性流，弹性流源是一种不需要固定速率服务且可按网络的拥塞状况调整其发送速率的流量源，如使用TCP的Intemet流量源，ATM网中使用ABR服务的源等。则IP网络速率控制问题可公式化为如下最优化问题，P只抨1川ma凡XC s川t.三x旦，运钊x,;.O, Vi=l, ,N 收稿日期:2011-08-15 本栏目责任编辑唐一东7744 协川人工.及规瓢技术l时挝纠b第7卷第31期(2011年11月)Computernowledge and Technology电脑知识与技术该问题的目标函数是聚集效用，约束条件说明链路上总的用户速率不超过链路容量C。由于目标函数

9、连续且可行域是紧的，因此存在最优解Xi=(X;，xN)。如果函数u.(xJ严格凹，由于可行域是凸的，那么该最优化问题的解是唯一的。一般来说，效用函数是用户的私有信息，网络不可能完全了解。因此可考虑用一个市场定价的方案来进行分布式的速率分配。各用户i为所需带宽向网络提交一个愿付价格(也称为出价)矶，假设矶O。给定出价向量w=(w;，WN)，链路管理者选择一个速率分配X:(x旷川。假设管理者没有价格歧视，公平对待所有用户，则各用户支付相同的单位带宽价格为>0，各用户按此价格计算可使用的带宽(即速率问=%，并支付带宽使用费用户品。进一步假设管理者总是分配所有链路容量C.则价格应满足，(2) 三

10、号=c上丽的等式只有在立即，>0时成立，此时有，立即a(3) =- 这个机制在经济学术语中称为市场出清(market-clearing)过程，设定一个价格使供给等于需求。注意到当一个用户选择总支出为矶时，相当于对应于价格>0选择了一个需求函数D(，时=时。需求函数描述了用户在任意给定的价格>0上带宽的总需求。因此，链路管理者选择一个价格使得L，D(矶由式(3)用户i对给定的D(矶)获得-速率分配，并支付费用D(矶)=矶。假设用户为定价的参与者，可建立了一种速率分配的非合作博弈模型。2非合作博弈模型令w_，=(甜俨o，Wi_1，Wi+l，.叮wJ为除了i外的所有用户出价向量。则

11、问题P，可用博弈论方法描述为，给定矶，各用户i选择愿付费用矶，最大化自己的收益，飞(w;wJ:叫;icl (4) I LWk I 定义1(Nash均衡)设1，(即i，W_J为当用户z采用出价矶，所有其他用户采用出价w_，时，用户i的收益。一个策略集即晴是一个Nash均衡，如果对任意用户! 飞1.(即;即:J二，1.(阳iW:)(5) 对Vw，Efl，成立.fl，为用户的可行出价集。Nash均衡是一个稳定的控制点，没有用户可通过背离该点的单独行为获得更大利益。下列定理表明上述博弈，存在唯一Nash均衡。定理1令假设I成立。在N>1时，由(5)定义的博弈存在唯一的Nash均衡旷注0满足立即，

12、>0。在这种情况下，向量x:(x旷;，x)定义为，Nw. Zz-Ztu了，i= 1(6) , J 是下列最优化问题的唯一最优解，P2:m缸L，?(xJ(7) s.t. L,x,<C x，o， i=l, ,N 其中a :(1-专忏)时u咐(x价.)创(f川:u，(y)句定理1表明单链路网络多用户非合作博弈的唯一Nash均衡可用最优问题P，刻画。但注意到，且然博弈存在唯一Nash均衡，但该稳态解不是原问题P，的最优解。那么如何得到原问题P，的最优解呢?下面将讨论这个问题。3激励定价博弈模型为了简化分析，我们考虑如下网络博弈模型，设各用户i向网络提交个愿付费用(出价)w, ，给定向量w=

13、(即;，、).网络选择一速率分配X:(x;内)与用户的出价成正比。假设网络总是分配链路的所有带宽，则每个用户得到的速率如下:x乏与-c(8) 考虑到用户自私行为对网络拥塞的影响，构造一种反映这种影响的收费机制:=们og(1+最)(9) 本栏目责任编辑:唐东人工锢能及调到接术抑制7745 Computer Knowledge and Technology电脑知识与技术第7卷第31期(2011年11月)其中，仇=Lk，.oiWk0由于用户z的出价w，反映了用户对资源(带宽)的渴望程度，因此访=立川表明了总需求，对数函数是一个严格增函数，一个较大的l呐意味着更严峻的竞争。公式(州收费中防表示所有其他

14、用户的需求，log(1 +兑)表明用户i参与后竞争程度的增加。在这个收费机制中，z直观上可理解为估计由于用户i的竞争对其他用户造成的价值损失。这样博弈问题(5)可进一步描述为:给定叭，各用户i选择愿付费用矶，最大化自己的收益，山町、l.(w;wJ= uJ一二-C)-W_, log(1 +云)(10) L川W对问题(10)存在如下定理:定理2给定收费机制(9)，IP网络速率控制的N人博弈问题(10)存在唯一Nash均衡点矿，进一步有，在即上的速率们手书，i =1 ，J是最优化问题P1唯一解。证明:首先证明N人非合作博弈问题(10)存在唯一Nash均衡点。对式(10)求一阶偏导数有，仇C访三川)?

15、C仰，几)=Ui一一一=一一lU -7一|, (工产，)L川(L,w,)l-i C) 由于U是严格凹函数，因此，普(w;wJ在wi上严格减，所以J，(w;wJ是w，的严格拟凹函数。对给定的甜-，存在唯一的叫最大化、1.(叭，wJ。其次，注意到当P1问题达到最大时，所有用户应具有相同的边界效用队，这是因为给定一个速率分配，如果一个用户i的边界效用高于另一个用户j，那么最优化问题P1(即社会福利)可以通过增加X，而减少抖得到进一步改善。由于在Nash均衡点，边界效w 用中(L，w;)jc为确定值，所以在町上的速如:=zr，z=1，J是最优化问题P1唯一最优解，从而最大化社会福利。证毕。4结束语本文

16、研究了在端系统自私地最大化自己利益情况下，如何有效实现网络拥塞控制问题。博弈论方法的关键是设计出这样的算法使个体用户的动机与行动转变成整个系统理想的结果。这个问题并不容易实现，其困难在于各个用户有基于其行动的个人偏好的私有信息，算法设计者的目的就是基于分布式信息将这些行动转化为理想的系统性能。基于博弈论方法，提出了一种网络拥寒控制框架，给出了拥塞控制的非合作博弈模型，通过一种定价机制能够驱使自私用户按网络设计目标操作，并达到最优网络拥塞控制。参考文献:1 Basar T,Srikant R.Revenue-maximizing pricing and capacity expansion in

17、 a many-users regimeJ.Proc.lEEE Infocom,New York,2oo2: 1556-1563. 2 Shen H X,Basar T.Network Game with a Probabilistic Description of User ypes1.Proc.IEEE CDC 2004, Atlantis,Paradise Island, The Bahamas,2oo4: 14-17. 3 Shenker S.Making Greed Work in Networks:A Game-Theoretic Analysis of Switch Servic

18、e DisciplinesJ.Proc. IEEE SIGCOMM,1994: 47-57. (上接第7743页)参考文献:1朱香卫，肖亮，吴慧中，等.数字图像水印性能评估指标的研究1.通信技术，2009(1):256-258.勾吴爱弟，崔英俊，刘赛君.数字水印技术及其应用综述J.天津工程师范学院学报，2007(1):12-16. 3赵翔，郝林.数字水印综述J.计算机工程与设计，26(11):1946-1950. 4朱香卫.静止图像鲁棒性数字水印算法与性能评估方法D.南京:南京理工大学，27.5 Petitcolas FAP, Anderson RJ.Evaluation of copyright marking systems1.Proc of IEEE Multimedia Sy