一种基于非合作博弈的均衡路由方法
!""&年#月第’,卷!第’期
!
西安电子科技大学学报（自然科学版）!"#$%&’!"(!)*+*&%!#%*,-$.*/0
!
Q?D-!""&
R:;-’,!1:-’
一种基于非合作博弈的均衡路由方法
!
张惠娟+!!周利华+!翟鸿鸣’
!陕西西安!&上海!!+-西安电子科技大学计算机学院"+""&+#!-同济大学软件学院""""#!#上海!!$’-交通银行上海总行""""’’
摘要!针对路由器路径选择中的资源分配不均衡问题!提出了基于博弈论思想的解决方案-将./0#协议中的任意博路由过程看作是多个非合作参与者间的博弈问题!给出了以单个参与者在各条链路上的以该参与者的延迟时间为博弈效用的路由器路由博弈模型!求解了保证该博弈模速率分配为博弈策略"
型处于均衡状态时的1在此基础上!提出了保证多个参与者公平使用网络链路的均衡路由234均衡解-算法-仿真实验表明!该算法使得各个参与者在网络中延迟时间少!且对各个参与者是公平的!解决了路由器路径选择中资源的均衡性分配问题-关键词!资源分配#非合作博弈#均衡路由1234均衡#
中图分类号!"#5/’%’-"’!!文献标识码!6!!文章编号!+""+$!,""!""&"’$"’%7$",
!"#"$%&’()*+&"(,+-.&+,%/"0&’$)$%))&("+,2&3".&+-&)(14
’
!"#$%"&’(&*++!#!",-.’(/&*+#!"#0"1+(3’+)22
#
!#E#E#$!#+-894::;:KK##$##"5:DCGDC0-842D42C"""#!)4CD2’-*2DM:
%#5/0+("%+A92?3A:2@494:C9A:BA3AD@AF>>KO>O
2AB3-6K2=A=:FA;IC@42>;2AB3B2@AFC3@BCN?@C:D3@B2@A@DFFA;202C;CD2;;2@43C3KC0AD-54A>OOO2O2>&3B2@AFC3@BCN?@C:DI4C9492D233?BA@4A1234A?C;CNBC?=C33:;0AF-*23AF:D@4A1234;2ABP>O
J?C;CNBC?=#2N2;2D9AFB:?@A2BC@4=A@C9I4C942339?BA3@4ANA3@FA;2DF@4ABA3AD@AF-8C=?;2@C:DBA3?;@3CDFC92@A@42@@4C32BC@4=A@C992D3:;0A@4AN2;2D9AFBA3:?B9A>OFC3@BCN?@C:DCD@4AB:?@ABCDAP47
(+
路由器作为网络资源分配的核心部件#其路径选择算法是影响网络资源分配公平性和均衡性’的关键问
题-均衡路由算法是指路由器在进行路由选择时#其目标不再是单纯)最短路径最佳*#而是整个网络路径效用最佳#其本质是网络资源的均衡性分配问题#即网络路径带宽和服务器处理能力等网络资源的均衡性分配问
(!
题-目前#关于网络均衡路由算法的研究很多#如基于控制策略+神经网络+遗传算法’+移动2AD@和模拟退火K
方法等算法-博弈论是本世纪应用数学最重要理论成果之一#在网络资源分配研究中有广泛应用#基于博弈论思想以及博弈解的均衡性来解决网络资源分配的均衡性问题#是研究网络均衡路由算法的一种新思路-’(
是指博弈的任何参与者不能依靠单方面改变自身策略而期望获1234均衡’是博弈问题的一种重要解#
文献’(分别研究了1网络路由中非合作用户间博弈的1得更高效益-,!%234均衡的存在性#234均衡存在
性以及均衡解的惟一性#具有线性特性的效用函数路由博弈问题#在网络执行过程中建立非合作用户间的
笔者研究了路由器路径选择中的均衡性问题#提出了基于博弈论思想的解决方案#即1234均衡方法等问题-将.针对该博弈问题#建立了路由算法的/0#协议中的任意博路由问题看作是多个非合作参与者间的博弈-收稿日期!!""#$"#$!!
基金项目!国家重点基础研究发展计划!"项目!"%&’!""()*’!+%",作者简介!张惠娟!"#女#副教授#博士-+%&"$
第’期!!!!!!!!!!!!!!张惠娟等!一种基于非合作博弈的均衡路由方法
’%%
非合作博弈模型!求得了该博弈的1并在此基础上!提出了一种基于非合作博弈的均衡路由234均衡点!方法-
8!系统介绍
!"!!任务模型
其中4+到43是路由器!分别以速率!!!网络实际状况任务模型示意图见图+-!+到+的泊松分布形式向网络发送数据"其地址在路由器4+到43的路由表中用映射入口!
各个服5+到5+是特定任意播的服务器地址!
路分类在
中
)
!!$&+
则参与者)在网络中的总体延迟时间为
7)$!&9
’9+
&9";"5!&"5:$"$
’’)
’)
’
=’=
’9+
=9+
++3
$&!
每个参与者总是期望自身7)$且各个参与者都是自私的!不考虑其他参与者!&最小!!!根据博弈论可知!
的期望和动机-因此上述博弈问题的1在其他参与者策略确定的情况下!参与者)期望延234均衡求解变为’迟时间最小!即
=CD7)$!&!>
5)
$&’
根据网络路由实际模型可知!式$&受限条件是’’
%!5’9+!+!!!!!’#")
3
$&,$&($&#
=9++
"5!"5
’)
=’=
%!’9+!+!!!’!!$"
9+!>
’9+
9!算法设计
主要通过拉氏函数来求解式$&的最小值问题-文中给出了该博弈均衡解求解算法!称为1S’T*)算法-基于1S给出了完整网络路由均衡算法1S即基于非合作博弈的均衡路由算法-T*T*!)算法!
()+")))!)表示在其定义!!博弈均衡解"即"!将博弈模型中的路径处理能力按降序排列!+#"!#%#+"’"
)他参与者路由路径策略确定情况下!参与者)可以使用路由路径上的处理能力!其取值为"’9"’;
自然科学版",卷!!!!!!!!!!!!!!!!!!西安电子科技大学学报!!!!!!!!!!!!!!!第’,""
3
=9+!=%)
"
则在该博弈模型中对于参与者)的最优解为5=!=>)
)
"’;"""#5’9)
!!
$!)+
’
"!!"##"";!"""
)
’
)
$!)+’
?)?)
)
’9+’9+
"#&
$+!)#其中?#的最小取值!"(?))是满足不等式"")
>""##"";!"""
)
=
)
$!)+=
?)?)
=9+=9+
基于上述求解!针对图+任务模型给出了求解单个参与者)均衡点的方法%%%1ST*)算法-1ST*)算法&
)))"#将每条路径上用于处理参与者)处理能力降序排列&++#"!#’#+>"""#!@*
>""##"";!"""
)
’
)
$!)+’
++
’9+’9+
"#I’4C;A"@+"F:"##!+*+;+!@*!!
>""##"";!"""
)
’
)
$!)+’
$!)++
++
’9+’9+
"#’!,
$!))+
"$@!!""
基于1S构建了完整均衡路由算法%%%1ST*T*算法&)算法!
"#初始化&使得每个参与者在各条路径上的策略!’!为"!定义参数A!+555A表示算法得+!!!+#)9")))
到最优解需要执行的次数-"!#根据1ST*!#值>求得+9)算法计算参与者)的策略!并计算在该策略下的7)"A+A;
+B75#;7)并将+传递给下一个参与者-)"
"#重复执行第"#步!直到所有参与者的策略分配都计算完成-此刻!重新回到第一个参与者的策略计’!算-首先判定+取值是否满足误差需要!如果满足则结束算法!得到了各个参与者的策略分配-如果不满足需求!则重复执行"#!直到满足需求-!
因此根据该算法求得的策略分配是11ST*算法的核心是算法1ST*234均衡的-)!
:!仿真实验
$"!!实验设计
每个参与者到每个服务器之间都有特定路径!每条路’个目标服务器-!!假定该路由系统有’个参与者!
径的传输性能由该条路径上的链路带宽和服务器处理能力确定-&+至&’路由器到各个目标服务器之间的路径处理能力通常由链路带宽以及目标服务器处理能力确定-在这里用&该实验中!取$!$!$业&"UNC@3&"UNC@3&""UNC@3>’表示相应链路处理能力>+9,!9#’9+
’
务流分别以!!9+到!’速率发送到网络中!
"!
’9+
’
表示路由器业务总速率!取值从!$"UNC@3变化到
$!变化间隔为!$!其取值反映了整个网络系统负载程度-为分析问题方便!取!!""UNC@3"UNC@3>’!!+9"
’
其中系统负载程度通过参数>!>(!!!!!>!9"’9"#9
一般来说!"V$,"V认为是轻#为+"&来度量!
’
’9+
负载系统!"V$#"V是中度负载系统!"V以上是重负载系统-#为,#为#
(")
为了更好地比较1S实验中比较了该算法和典型的/T*算法的性能!8算法+-$"#!实验结果
实验+!比较1ST*与/8算法平均延迟时间-+
+
’’)
每个参与者延迟时间为7)"!#9
’9+
5#9""5:"
’9+
5’)
3
!参与者在网络中的延迟时间之和为
!’;’=""5=
=9+
3
79
)9+
#由此可计算出平均延迟时间-!""7!
)
实验!!比较1ST*与/8算法的公平性-该实验研究了输入速率!W+$!"UNC@3时每个参与者的执行时间分配公平性问题-从图!看出#在较低系统负载下#路由延迟时间均较低#算法1S在网T*延迟时间最小#/8算法较高-络处于中度负载情况下#延迟时间增加#尤其是网络处于重负载情况下#延迟时间增加很快-当输入速率大于网络处于拥挤状态#延迟时间将会大大增大
-网络处理能力后#