探索对等网副本散布问题纯策略纳什均衡

　　摘 要：
　　在对等网环境中为增强数据的可靠性与访问效率，需要将数据副本进行有效的散布。应用博弈论原理研究副本散布问题是一种有效的新方法。分析了当前使用博弈论方法研究所存在的问题，提出副本散布问题的基本博弈模型，首次证明了多对象且节点容量有限情况下纯策略纳什均衡的存在性，较以前的研究成果更具有实用价值，且是今后进一步研究的基础。
　　
　　关键词：对等网；副本散布；纯策略纳什均衡
　　
　　1 引言
　　
　　在对等网环境中，各节点保存数据对象的多份副本可提高数据的可靠性与访问效率。但副本数量过多会导致存储资源的极大浪费，而数量过少则无法显著提高数据的可靠性与访问效率。因此如何将数据对象副本有效的散布到各节点是目前对等网研究所面临的主要问题之一。
　　
　　人们已经对副本散布问题进行了许多研究，由于在对等网环境中，节点数量多，具有动态性且各自时钟无法完全同步，因此很难实现集中式算法，目前的算法大多是分布式的。Ko和Rubenstein提出了一种用于副本散布的自稳定的、分布式、异步且可扩展的协议[1]，将每个节点用一种颜色来标示，并不断改变节点的颜色使具有相同颜色的节点间距离最大化，他们通过理论与实验分析了其协议的收敛性。Chen，Katz和Kubiatowica提出了一个满足客户端Qos和服务器端容量限制条件下的动态副本散布算法[2]。Douceur和Wattenhofer在Farsite分布式文件系统上研究了为增强可靠性而交换副本的爬山算法[3]。与上述这些方法不同，Dennis和Kubiatowicz认为大规模的副本管理问题更适合用基于经济模型的方法来解决[4]，这方面的研究目前尚处于起步阶段。Byung-Gon Chun等通过使用非合作博弈的方法分析了副本散布问题[5]，并在其博弈模型下证明了纯策略纳什均衡的存在性，进而分析了纳什均衡局势的最优化程度，并通过模拟实验研究了其属性，但在其博弈模型中他们假定节点容量无限大，而在实际情况中这个条件是根本无法达到，从而导致其缺乏实用性。
　　
　　针对[5]中存在的问题，本文首次证明了副本散布博弈模型在多对象且节点容量有限的情况下纯策略纳什均衡的存在性，是对[5]研究的深化，使其更有实际价值，并且也为今后使用博弈论的方法进一步研究副本散布问题打下了基础。
　　
　　2 副本散布问题基本博弈模型
　　
　　在对等网环境中节点副本复制决策受其它节点决策的影响，决策时需要考虑其它节点的决策。通过量化节点对各数据对象的访问代价，并以此作为节点的效用。受程序控制的节点以最大化自身效用为目标，前后一致理性的做出决策。
　　
　　副本散布问题的非合作静态博弈模型用四元组表示。为有限非空节点集(CostSMNNnN=||，对节点，表示节点用于存储副本的共享存储空间容量。Ni∈+∈RiV)(iM为有限非空的数据对象集，对mM=||Mj∈，Njowner∈)(表示负责存储数据对象j的节点，称为j的宿主节点，+∈RjVM)(为数据对象大小。S为节点可选择的有限非空策略集，节点i的策略集为，纯策略SSiiSs∈为维向量，第mj维为1表示节点保存对象j的副本，为0表示不保存对象j的副本。中所有节点的策略组合集为N)，节点的访问代价函数为策略组合集到实数集的映射，其定义为：对节点，RSGCost→:iSGsg∈其中Σ。若节点i保存对象j 的副本，I ij 为1，否则为0。ij α为节点i首次复制对象j 的代价与对象维护代价两者之和与对象访问频率的乘积， 满足。节点l 保存对象j 副本且对节点访问代价最小。
　　
　　为对象从节点到节点l 的传输时间。与特定节点的对象维护代价，对象同步周期和节点间对象传输时间相关。为使对象维护代价与访问代价具有可比性，引入比例因子，对节点，取为节点i 到任意两个节点的d 与之差的比值，这个比值只与中对象传输时间的系数相关，对节点和对象j 来说是唯一的。ij β 表示节点i 从节点l 访问对象j 的代价，是数据传输代价与对象访问频率的乘积。dil wij博弈论的方法追求的是稳定的解，即纳什均衡解。纯策略纳什均衡是指这样一种局势：对任一节点，若给定其它节点的策略不变，该节点不会单方面改变自己的策略，否则不会使节点访问代价变小。形式化的描述为： 若为一个纯策略纳什均衡，则有。在节点个数与各节点策略均为有限的情况下，必定存在混合策略意义下的纳什均衡，但不一定存在纯策略意义下的纳什均衡。与强调整体最优的方法不同，博弈论方法强调的是个体节点的最优，纳什均衡解可能是全局最优的，也可能不是全局最优的。
　　
　　3 纯策略纳什均衡存在性证明
　　
　　对任一节点，给定其它节点的复制策略，总可以找到一种对象复制策略使该节点的对象访问代价最小。对节点i与对象j ij ij α ≥ β 时节点i选择通过其它节点访问对象j ，aij < βij时类似于0-1 背包问题根据ij α 、及决定是否保存对象VM( j) V (i)j 的副本。
　　
　　定理 1：在副本散布博弈模型中，若某复制策略为节点最优策略，那么当该节点访问某对象的代价变小时，该复制策略仍为节点的最优策略。
　　
　　证明：设节点最优复制策略为I ，其复制与通过距其最近的节点访问对象的代价分别为m α1,α 2 ,......,α 与m β1,β 2 ,......,β ， 则。访问代价变小时Σ=与j β 分别变为和，设访问代价变小的对象的集合为ObjM ，则若有，否则有， 。
　　
　　假如I 不再是最优策略，则必存在策略I 有由于I 为访问代价变小前的最优策略则有根据α 与β 的取值有将（3）加入（2）的两端有与（1）式矛盾，则假设错误，即I 仍为最优策略。
　　
　　□给出一种局势的构造算法：
　　
　　令和为两个节点集， V 中的节点只通过对象宿主节点访问对象， 中的节点既可通过对象宿主节点也可通过其它节点的共享存储区访问对象。
　　
　　步骤1：令集合V = N ，集合V '= Φ为空。
　　
　　步骤2：对所有的节点，选择复制策略，使最小。
　　
　　i∈Vsi Costi步骤3：从集合任取一节点i ，令其可通过集合中节点的共享存储区访问对象，节点重新选择复制策略使其在当前条件下访问代价最小，将节点从集合V 中删除，加入集合。'V步骤4：重复步骤3，直至集合V变为空。
　　
　　定理2：经上述构造算法生成的局势是一个纳什均衡局势。
　　
　　证明：每次在步骤3改变节点i的复制策略时不会影响集合V中其它节点复制策略的最优性，因此只需考虑集合中的节点。对节点，将其复制的对象集合记为，分两种情况： 'Vi)(iObjN(1) 对节点，对象，若节点导致'Vk∈)(iObjNj∈ikjα和kjβ变大，则不会改变节点复制策略的最优性，不变。kkCost(2) 对节点，对象，若节点导致'Vk∈)(iObjNj∈ikjα和kjβ减小，则根据定理1，不会改变节点复制策略的最优性，减小。
　　
　　经上述算法逐渐增加集合中元素的个数，最终必可生成一个纳什均衡局势。
　　
　　定理2说明，在副本散布问题基本博弈模型中，在多对象且节点容量有限的情况下存在纯策略的纳什均衡。
　　
　　4 结论与今后工作
　　
　　本文在多对象且节点容量有限的情况下证明了副本散布问题的博弈模型中纯策略纳什均衡存在性，是对节点无限容量情况更为实用的扩展。在此基础上可通过继续研究纳什均衡解的最优化性质，明确最优解的上下限，引入改进方法，提出真正实际可用的副本散布算法。