网络路由基于对策论的资源分配策略

《网络路由基于对策论的资源分配策略》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第２Ａ期电子学报Ｖｏｌ．３８Ｎｏ．２Ａ２０１０年２月ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡＦｅｂ．２０１０网络路由基于对策论的资源分配策略董军，詹聪明，舒静（华东师范大学软件学院，上海２０００６２）摘要：对策论提供对独立参与者之间冲突进行建模的框架，可用以综合考虑路由选择和拥塞控制问题．经典的对策论不一定直接能应用于网络．本文在路由选择的多Ａｇｅｎｔ系统的基础上，给出具有“惩恶扬善”行为的基于对策论的路由资源分配策略．它奖励避免拥塞、惩罚行为不合要求的用户．在用户都是理性的前提下，系统能稳定在纳什均衡状态．关键词：对策论；路由选

2、择；拥塞控制；多Ａｇｅｎｔ系统；资源分配中图分类号：ＴＰ３９３０文献标识码：Ａ文章编号：０３７２２１１２（２０１０）２Ａ１４３０５ＲｏｕｔｉｎｇＲｅｓｏｕｒｃｅＤｉｓｔｒｉｂｕｔｉｏｎＳｔｒａｔｅｇｙＢａｓｅｄｏｎＧａｍｅＴｈｅｏｒｙＤＯＮＧＪｕｎ，ＺＨＡＮＣｏｎｇｍｉｎ，ＳＨＵＪｉｎｇ（ＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，ＥａｓｔＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０００６２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｇａｍｅｔｈｅｏｒｙｉｓａｌｔｅｒｎａｔｉｖｅｆｒａｍｅｗｏｒｋｔｏ

3、ｍｏｄｅｌｃｏｎｆｌｉｃｔｉｏｎｂｅｔｗｅｅｎｉｎｄｅｐｅｎｄｅｎｃｅｐｌａｙｅｒｓ，ｗｈｉｃｈｃａｎｂｅｕｓｅｄｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍ．Ｈｏｗｅｖｅｒ，ｃｌａｓｓｉｃｇａｍｅｔｈｅｏｒｙｃｏｕｌｄｎ’ｔｂｅａｐｐｌｉｅｄｔｏｎｅｔｗｏｒｋｄｉｒｅｃｔｌｙ．ＧａｍｅｔｈｅｏｒｙｂａｓｅｄｒｏｕｔｉｎｇａｐｐｒｏａｃｈＭＰＳ，ｗｈｉｃｈｃａｎ“ｅｎｃｏｕｒａｇｅｍｅｒｉｔａｎｄｐｕｎｉｓｈｅｖｉｌ”，ｉｓｐｒｅｓｅｎｔｅｄ．Ｉｔｒｅｗａｒｄｓｃｏｎｇｅｓｔｉｏｎａｖｏｉｄｉｎｇｕｓｅｒｓａｎｄｐｕｎｉｓｈｅｓｍｉｓｂｅｈａ

4、ｖｉｎｇｕｓｅｒｓ．ＡＮａｓｈＥｑｕｉｌｉｂｒｉｕｍｃｏｕｌｄｂｅｒｅａｃｈｅｄｗｈｅｎｐｌａｙｅｒｓａｒｅｒａｔｉｏｎａｌ．Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉａｇｅｎｔｓｓｙｓｔｅｍ；ｇａｍｅｔｈｅｏｒｙ；ｒｏｕｔｉｎｇ；ｃｏｎｇｅｓｔｉｏｎｃｏｎｔｒｏｌ；ｒｅｓｏｕｒｃｅｄｉｓｔｒｉｂｕｔｉｏｎ意度的效用函数．在“最大最小准则”基础上，１９５０年纳１引言什（ＪｏｈｎＦ．Ｎａｓｈ）介绍了一个对策中解的概念，即纳什平网络路由选择策略不仅要分配路径，还要在若干资衡：在其他参与者的策略已确定的情况下，没有参与者［１］源中分担负荷，与此相关的

5、是拥塞问题．拥塞控制有能通过改变其自身策略而增加效用．系统的性能只有通赖于路由选择，路由选择应该考虑拥塞控制．例如，我国过其提供给参与者的满意程度的和来评估．由于网络不长信网中的交换机曾出现因负荷在短时间（除夕晚）内总是处于均衡状态，就公平而言更好的原则是：只要参过重而崩溃的情况；分布式Ｗｅｂ服务系统被广泛应用与者能增加其效用，系统就被认为是公正的．［２］于提供有效的因特网服务，但现有的方式几乎没有考上世纪９０年代，从人工智能出发的对策论研究引虑对主机和服务器的处理过负荷的控制，这要求能够进起重视［４］，也有将对策论应用于网络资源分

6、配的工行负荷均衡和资源复制，以图响应时间恰好在允许范围作［５］．我们在分析已有方法不足的基础上，提出了以预内而预防过早丢弃服务请求．测为核心的路有选择的多Ａｇｅｎｔ系统方法［６～８］．随之而所以，宜从路由选择和拥塞控制相结合的角度，综来的问题是：若某结点同一时刻的业务（入呼或中继请合考虑路由选择和拥塞控制问题，以解决网络资源分配求）多于现有中继线数，就会出现资源冲突情况．本文将问题．这个问题一般化为多队列流竞争网络资源问题，可利用对策论提供对独立参与者（Ｐｌａｙｅｒ）之间资源冲突和对策论作进一步分析．［３］决策进行建模和分析的框架．

7、每个参与者的回报依赖２基于对策论的资源分配策略于其自身的行为和其他参与者的行为．其自身的行为依赖于三个参数：活动的策略空间或现有的策略；包含关在对策论中，通常假定用户和资源供应商独立优化于其他参与者信息的信息集合；确定从结果中获得的满各自的效用函数，从而使资源分配达到某一特定的对策收稿日期：２００８０３０３；修回日期：２００９１２３０基金项目：上海市优秀学科带头人计划（Ｎｏ．０７ＸＤ１４２０３）；国家重点基础研究发展规划（Ｎｏ．２００５ＣＢ３２１９０４）１４４电子学报２０１０年均衡解．对策论的关注点包括研究单个的局中人追求ｎ

8、（２）工作守恒性：ｉ，ｓ．ｔ．γｉ（ｔ）＜ｒｉ（ｔ）∑γｉ效益最大化行为的决策过程，系统在大量局中人的作ｉ＝１用下是否存在某种均衡或稳定解，以及局中人采取竞（ｔ）＝Ｃ；争与合作等不同策略对于系统均衡解的影响等问题．γｊ（ｔ）（３）