基于博弈论的不网络资源管理方法的比较.doc

基于博弈论的不同网络资源 管理方法的比较 阿 伦 （内蒙古化工职业学院 内蒙古 呼和浩特 010010） 摘 要：基于博弈论思想的网络资源管理方法可，本文，，可使网络上各个用户的利益最大化。 1、引言 将博弈论(Games Theory)应用于解决计算机网络中存在的问题具有很长的历史。从利用激励机制进行协议设计到分析现有资源分配的设计机制中用户自私性对结果的影响，以及为了应付用户自私性而采用的基于机制的设计方法对网络设计进行的修改等。在其他人工智能领域以及基于市场机制的计算领域中，博弈论也有重要的应用。 博弈论研究的核心问题一直以来都是动机问题。大量文献研究表明即使参与者是自私的，但为了达到全局期望利益的目的，在资源分配过程中的设计机制和实现方式的主要方法是运用Nash均衡(或其他考虑非合作的方法)理论(假设所有自私用户的行为将产生自私一致性均衡)，所有的参与者都无法在偏离整体均衡值的时候取得最优解。Nash问题一般采用基于均衡的资源预留方法来产生期望的结果。 与Nash均衡方法相对应的是Strategyproofness方法，它无论其他参与者的行为是撒谎的还是诚实的，是愚蠢的还是聪明的，都会保证任何参与者在自身诚实的情况下取得最优值及自身利益最大化。所以Strategyproofness方法在基于不对称信息网络博弈方面比Nash方法更具吸引力。 2、Nash均衡方法 　 在网络资源的分配模型中有M个网络用户竞争有限的计算资源,而且网络用户价格或付出相对较高, 使用的资源比例相对较多,每个用户需要向资源提交一个出价,并获得资源份额,由于资源分配遵循基于出价的正比例共享原则,份额x (b)和出价b满足下面的关系： （1） 式中, 表示所有用户的出价之和. 因此,第i个用户所获得的k类资源份额 () 就等于该用户出价与所有用户出价总和之比. 令为第i个网络用户为了完成类型k任务而选择的资源能力. Bk为网络资源从用户集合AM中接收总的用户出价, 并且。则第i个网络用户分到的资源数量为 （2） 合作网络中博弈的定义 定义1 　一个合作博弈由以下组成: (1) M个参与者； (2) 一个非空、紧致的凸集合 ,是M个参与者的博弈策略； (3) 每个参与者i ( i = 1 ,2 ,…, M) , 其效用函数fi (x)是从X到R的函数,可以取其最大值或者最小值； (4) 对于每个参与者i ( i = 1 ,2 ,…, M) , 如果效用函数是以最小值作为最佳效用，即f i 最小值表示,则矢量u0=（,,…，）称为合作参与者的初始点。 定理1、合作网格博弈,有且仅有一个bargaining点,并且该bargaining解是式（10）的最优解。 （3） 约束条件为 （i=1,…,n) （4） （5） （i=1,…,n) （6） 定理2、一合作博弈的bargaining解,也可通过式（7）最优解求得 （7） 约束条件为 （i=1,…,n) （8） （9） （i=1,…,n) （10） 3、Nash均衡的算法设计 针对网络合作博弈问题的求解, 设计了一种基于合作博弈的网络资源分配均衡算法. 算法描述如下： (1) 将每个网络资源按照其计算执行能力降序排列(μ1≥μ2≥…≥μn) (2) 计算 (3) While ( cμn) do ①βn ←0 ② n ← n - 1 ③ (4) for i = 1 ,…, n do βi ←μi - c 依据上述算法实现过程, 可计算出以λ的代价换取网络计算资源,或 通过分析可以从两个方面看出：一