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

开篇：润墨网以专业的文秘视角，为您筛选了一篇博弈论在网络拥塞控制中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：博弈论研究多个独立的决策者之间的冲突与合作，而网络拥塞控制中端用户行为典型的构成了一种非合作博弈。该文基于博弈论方法，将网络拥塞控制问题模型化为非合作博弈，通过一种有效的带宽使用定价与收费机制，使博弈的Nash均衡解达到全局最优，导致有效与公平的网络带宽分配。

关键词：博弈论；网络；拥塞控制；纳什均衡

中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)31-pppp-0c

Game Theoretical Application in the Network Congestion Control

ZHONG Bo-cheng

(College of Electronic & Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China)

Abstract: Game theory researches conflict and cooperation among independent decision-makers, while in the problem of network congestion control host users’ behaviores typically form a noncooperation game. In the paper, based on game theroy the problem of network congestion control was modeled a noncooperation game. With 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

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

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

本文基于博弈论方法提出了一种不依赖端系统用户合作的IP网络拥塞控制框架，将网络中的流量源模型化为网络博弈中的局中人，竞争共享网络带宽资源，通过一种有效的带宽使用定价与收费机制，使博弈的NASH均衡解达到全局最优，导致有效与公平的网络带宽分配。

1 问题原型

考虑N个用户共享一个带宽为C的通信链路，设用户i的发送速率为xi，其效用函数为ui(xi)是用户速率xi的函数，表示用户对使用资源（带宽）的满意度。对效用函数作如下假设，

假设1对各用户i，在xi≥上，效用函数ui(xi)是凹的，严格增的与连续的；在xi>0上ui(xi)是连续可微的；在xi=0点的右导数ui’(0)有界。

假设1中的凹性相应于Shenker[3]的弹性流，弹性流源是一种不需要固定速率服务且可按网络的拥塞状况调整其发送速率的流量源，如使用TCP的Internet流量源，ATM网中使用ABR服务的源等。

则IP网络速率控制问题可公式化为如下最优化问题，

该问题的目标函数是聚集效用，约束条件说明链路上总的用户速率不超过链路容量C。由于目标函数连续且可行域是紧的，因此存在最优解xi=(x1,...,xN)。如果函数ui(xi)严格凹，由于可行域是凸的，那么该最优化问题的解是唯一的。

一般来说，效用函数是用户的私有信息，网络不可能完全了解。因此可考虑用一个市场定价的方案来进行分布式的速率分配。各用户 为所需带宽向网络提交一个愿付价格（也称为出价）wi，假设wi≥0。给定出价向量w=(w1,...,wN)，链路管理者选择一个速率分配x=(x1,...,xN)。假设管理者没有价格歧视，公平对待所有用户，则各用户支付相同的单位带宽价格为λ>0，各用户按此价格计算可使用的带宽（即速率）xi=wi/λ，并支付带宽使用费用ηi=wi。进一步假设管理者总是分配所有链路容量C，则价格λ应满足，

上面的等式只有在∑iwi>0时成立，此时有，

这个机制在经济学术语中称为市场出清（market-clearing）过程，设定一个价格使供给等于需求。注意到当一个用户选择总支出为wi时，相当于对应于价格λ>0选择了一个需求函数D(λ,wi)=wi/λ。需求函数描述了用户在任意给定的价格λ>0上带宽的总需求。因此，链路管理者选择一个价格使得∑iD(λ,wi)=C，即聚集需求等于供应C。

由式（3）用户i对给定的D(λ,wi)获得一速率分配，并支付费用λD(λ,wi=wi)。

假设用户为定价的参与者，可建立了一种速率分配的非合作博弈模型。

2 非合作博弈模型

令w-i=(w1,...,wi-1,wi+1,...,ws)为除了i外的所有用户出价向量。则问题P1可用博弈论方法描述为，给定w-i，各用户i选择愿付费用wi，最大化自己的收益，

定义1（Nash均衡）设Ψi(wi,w-i)为当用户i采用出价wi，所有其他用户采用出价w-i时，用户i的收益。一个策略集w*是一个Nash均衡，如果对任意用户i，

对?wi∈Ωi成立，Ωi为用户的可行出价集。

Nash均衡是一个稳定的控制点，没有用户可通过背离该点的单独行为获得更大利益。下列定理表明上述博弈，存在唯一Nash均衡。

定理1 令假设1成立。在N>1时，由（5）定义的博弈存在唯一的Nash均衡w*≥0满足∑iwi>0。在这种情况下，向量x=(x1,...,xN)定义为，

是下列最优化问题的唯一最优解，

其中：

定理1表明单链路网络多用户非合作博弈的唯一Nash均衡可用最优问题P2刻画。但注意到，虽然博弈存在唯一Nash均衡，但该稳态解不是原问题P1的最优解。那么如何得到原问题P1的最优解呢？下面将讨论这个问题。

3 激励定价博弈模型

为了简化分析，我们考虑如下网络博弈模型，设各用户i向网络提交一个愿付费用（出价）wi，给定向量w=(w1,...,wN)，网络选择一速率分配x=(x1,...,xN) 与用户的出价成正比。假设网络总是分配链路的所有带宽，则每个用户得到的速率如下：

考虑到用户自私行为对网络拥塞的影响，构造一种反映这种影响的收费机制：

其中， zbc11.tif 。由于用户i的出价wi反映了用户对资源（带宽）的渴望程度，因此zbc12.tif 表明了总需求，对数函数是一个严格增函数，一个较大的log(?W)意味着更严峻的竞争。公式（9）的收费中?W-i表示所有其他用户的需求， zbc13.tif 表明用户i参与后竞争程度的增加。在这个收费机制中，ηi直观上可理解为估计由于用户i的竞争对其他用户造成的价值损失。这样博弈问题(5)可进一步描述为：给定w-i，各用户i选择愿付费用wi，最大化自己的收益，

对问题（10）存在如下定理：

定理2给定收费机制 (9)，IP网络速率控制的N人博弈问题(10)存在唯一Nash 均衡点w*，进一步有，在w*上的速率zbc15.tif ， 是最优化问题P1唯一解。

证明：首先证明N 人非合作博弈问题(10)存在唯一Nash 均衡点。对式(10)求一阶偏导数有，

由于ui 是严格凹函数， 因此，zbc17.tif 在wi上严格减, 所以Ji(wi,w-i)是wi的严格拟凹函数。对给定的w-i存在唯一的wi* 最大化Ψi(wi,w-i)。

其次，注意到当P1问题达到最大时，所有用户应具有相同的边界效用u'i，这是因为给定一个速率分配，如果一个用户 i 的边界效用高于另一个用户j，那么最优化问题P1（即社会福利）可以通过增加xi而减少xj得到进一步改善。由于在Nash 均衡点，边界效用zbc18.tif为确定值，所以在w*上的速率zbc19.tif， 是最优化问题P1唯一最优解，从而最大化社会福利。证毕。

4 结束语

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

参考文献：

[1] Basar T,Srikant R.Revenue-maximizing pricing and capacity expansion in a many-users regime[J].Proc.IEEE Infocom,New York,2002:1556-1563.

[2] Shen H X,Basar work Game with a Probabilistic Description of User Types[J].Proc.IEEE CDC 2004, Atlantis,Paradise Island, The Bahamas,2004:14-17.

[3] Shenker S.Making Greed Work in Networks:A Game-Theoretic Analysis of Switch Service Disciplines[J].Proc. IEEE SIGCOMM,1994:47-57.

收稿日期：2011-08-15