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

_基于博弈论的不同网络资源管理方法的比较阿 伦 （内蒙古化工职业学院 内蒙古 呼和浩特 010010）摘 要：基于博弈论思想的网络资源管理方法可提高网络资源分配的公平性，本文分析了不同网络资源管理方法对网络上各个用户的影响，并针对网络资源均衡分配的问题，提出了基于博弈论思想的资源优化分配算法，分析了Nash均衡方法与strategyproofriess方法的各自特点，及其在网络资源管理不同方面的应用，最终可使网络上各个用户的利益最大化。关键词：网络资源、合作博弈、非合作博弈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) 将每个网络资源按照其计算执行能力降序排列(12n) (2) 计算 (3) While ( cn) do n 0 n n - 1 (4) for i = 1 , n do i i - c 依据上述算法实现过程, 可计算出以的代价换取网络计算资源,或网络资源对各个网络用户的资源分配方案。 通过分析可以从两个方面看出：一是采用纯策略不推荐 , 整个系统是无用的, 不符合要求,二是现实的系统中, 即使大多数的网络用户使用信息不对称策略不推荐 , 总归还有些用户之间存在信息交换,即不论最后的收益如何,总是有网络用户在共享之间的信息。采用如上的混合策略达到的纳什均衡比采用纯策略所达到的纳什均衡更加稳定, 网络资源可以根据信誉值的变化进行策略调整和反应。使每个用户的利益最大化。4、strategyproofriess博弈方法 基于不对称信息的博弈是Internet的一个重要特点。对于网络中各用户所得利益与付出贡献问题的研究主要足基于代价均担的思想，也就是基于代价分担机制。代价-分担机制通过函数x1(u)和1(u)来定义。对给定的代价分担机制，定义，是所有用户的集合，R(u)是根据给出的利益值u所选择出的能够接受传输的用户集合。类似地，W(u)=NW(R(u)是根据u向量计算出的最终整体利益值。对于代价分担机制，必须有u，i和Vi，即选择用户i一定会比选择其他用户获得的利润更高。除此之外，代价一分担模型还要满足以下基本规则： 非正式迁移(no-positive transfers，简称NPT)：xi(u) 0。避免向入不敷出的用户传输数据，即只有恰当付出的用户才能得到服务。 随意加入(voluntary participation，简称VP)：wi(u)0。用户可以自由选择不接受数据，也不需要付出。这样会使自身的利益值为0，网络不能强迫用户使利益值小于0。 消费者主权(customer sovereignty，简称CS)：时任意u，如果vi值足够大则 iuivi=1，分担机制不能随意地将任何用户排除在外，网络必须确保给出高付出用户能够得到的利益。此外，为了避免用户间的恶意竞争，保证整个网络的利益最大化，还需要以下两个额外的约束条件： 预算平衡(budget_balance)：ipxiu=c(T(R(u)，T(R(u)是根据u确定的最终组播树，即用户获得的收益正好可以支付传输所带来的代价 有效性(efficiecy)：对所有的RP，有NW(R(u)NW(R)。即最终的接收者集台能够使得网络的整体利益最大化NW(R)称为一个有效集。现在的strategyproofriess代价一分担机制中，还没有任何一种能够同时满足以上两个要求。从本质上分析，有只边际成本MC(marginal cost) 机制能够同时满足NPT，VP和有效性的要求。5、ICPISPUSER模型 因为代价分担机制中信息的不对称性，所以在网络的实际使用中更多的是应用在ICP、ISP、USER等不同种类网络用户同时存在的网络中。在这种网络中ISP和用户都有可能为取得更多的利益而进行欺骗，它们都是不可信任的。代价分担机制的模型中ICP-USR模型与ICP-ISP模型因为具有一定的局限性所以不加以讨论，下面只对ICP-ISP-USR模型进行分析。 模型可以如下描述：一棵建立好的组播树T(r)，r是提供服务的lCP，它通过ISP的集I=ISP1，ISP，ISPm来向网络上的用户集U=USR1, USR2, USRm传输组播数据。每个用户USR会先对所要得到服务的价值进行评估，得到评价值Ui，据此给出一个可以支付给ICP的竞价值Bi。那么，如果它能够得到服务，则获得的收益为WUi=Ui-Bi。ISPj在向用户传输组播数据的过程中，需要付出一定的代价Cj，它所期望从ICP获得的利益为Pj，那么它可以获得的收益为WIj=Pj-Cj。所以，ISP和用户都希望能够获得最大的收益WIj和WUi它们可能会通过通告较高的Cj或者较低的Bi来达到目的。 在图中，用户USR3可以获得的收益为5-3=2，用户USR4的收益为4-2=2。ISP2则期望在向USR3和USR4转发过程中得到的利益为6-3=3。由于ISP和USR追求自身利益的最大化，所以使得以ISP2为根的子树的总收益为-1为了惩罚它们这种过分的自私行为，它们将不能够获得到期望的利益。所以，为了实现Internet的健康可持续发展和良好的经济环境，我们必颁采取措施来约束这种过分的欺骗行为。 在整个博弈过程中存在着两类参与者ISP和用户，它们无法得到彼此的真实信息，所以，ICPISPUSER模型是一个多人不对称静态博弈。博弈G可以形式化地描述为 G=其中， N=I,U= ISP1，ISP，ISPm , USR1, USR2, USRm ,|N|=n+m。 i=0，if i is a ISP1，if i is a UserAi a1,a2,an是参与者i可能采取的策略集。在这里，如果i为ISP，则Ai为Pi；而若i为用户，则Ai为Bi。Wi=w1，w2,，wn为参与者i采取相应的策略或可能得到的利益集合。ICP-ISP-USER 模型实例 在ICPUSER模型中提到的对撒谎者的惩罚机制同样适用于ICPISPUSER模型。用户对网络的付出的越低，越不可能获得更多的网络服务，ISP要求USER付出的越高，也越不可能得到支付这样的惩罚机制能够使参与者在欺骗之前对成功的概率进行估计，判断欺骗是否真的能够得到更好的利益值。这样，可以利用奉身的利益机制来抑制欺骗行为的发生。 在我们的惩罚机制中，可以将参与者的利益函数Wi定义为 (1)当iN，如果i=0，Ai定义为Ci，Ci+1， ，Ci +x，那么，对应的利益函数Wi定义为： wtWi，wt=aiAn(i)pi=(Ci+t)An(i)0jch()Uj+C其中，0是ISP的收益参数，是一个定值。An(i) 是从i到r的路径上所有经过的ISP的集合，即An(i)中的元素为ISPi的祖先，则ISPi采取策略aiAi产生的利益为其通告的价格(Ci+t)与可能获得该值的概率之积。如果他的祖先也撒谎，那么这个概率值也会降低。 (2)当iN如果i=1，Ai定义为Ui，Ui+1，Ui+y，那么，对应的利益函数Wi定义为： wiWi，wt=aipui=(Ui+t)it其中，i是用户的收益参数，(it0，1。用户给出的Ui值越高，它能够获得服务的概率越大。 在非合作博弈中，参与者都会认为其他参与者是不友好的，即其他参与者选择的策略会对自己不利，那么，在它选择策略的时候也会假设其他人会撒谎，这样，它选择撒谎的概率也会大为降低。 在ICPISPUSER模型中6、结论在Internet中由于涉及到ICP、ISP、USER的关系复杂，所以ICPISPUSER模型复杂度较高。ICP和ISP以及用户之间都存在着利益冲突，所以是一个复杂博弈我们基于博弈论对其进行建模，为了对欺骗行为进行惩罚，定义了各个参与者的利益函数在欺骗的情况下取最小值。但对于这种在网络中各用户地位、信息不平等的情况下只能使用strategyproofriess博弈的管理方法，使得网络中的各个参与者只要保证自己诚实的情况下可以获得最大的利益。在Internet中还有只涉及到USER之间关系的情况（如P2P），在这样网络中各用户地位、信息是平等的，所以可以使用均衡博弈（Nash方法）的管理方法。这样的网络中每个用户都会使用唯一的一个方法，使得在多用户博弈中不管其他人的使用何种方法，都会使自己的利益最大化。参考文献：1 Richard T B ,Lee Sam C M ,Liu John C S ,et al. An incen2tive mechanism for P2P network C/ / 24th International Conference on Distributed Computing Systems. Tokyo ,2004 :5162523.2 Sun Qixiang , Garcia - Molina H. SL IC: a selfish link -based incentive mechanism for unstructured peer - to - peernetworks C/ / The 24th International Conference on Dis2tributed Computing Systems.Tokyo ,2004 :506 - 515.3 Yang B ,Garcia - Molina H. Micropayments for peer - to -peer systems C/ / Proceedings of the 10th ACM Confer2 ence on computer andCommunications Security. Washing2 ton ,2003 :300 -