一种基于间接互惠的计算网格合作激励机制研究*
2011-06-27张东戈白天松
杨 虎，张东戈，刘 浩，白天松
（解放军理工大学指挥自动化学院 南京210007）
1 引言
随着社会对网格计算认识的深入和需求的提升，网格计算[1]技术已成为当前的研究热点之一。计算网格中的资源组成比较复杂，包括地理上分布的各种计算资源、存储资源、数据资源以及其他特殊资源，由于分布的资源属于不同的个人或组织，因此只有资源拥有者享有对各自资源的最高管理权限，这就决定了网格中对资源的管理不可能采取集中控制的模式，只能依靠资源拥有者间自发地共享和协作，这种共享和协作可以看作是一种合作关系。
合作关系是社会生态系统中普遍存在的一种现象，围绕着合作问题，近十年来涌现出许多研究成果[2]。庆祝《Science》创刊 125 周年之际，《Science》公布了 125 个最具挑战性的科学问题，合作问题研究位列第16位[3]，到目前为止，合作研究依然是热点。
通常，网格资源能否得到有效的利用，取决于各资源拥有者之间能否进行稳定、有效的合作，资源拥有者间的合作效果，直接决定着计算网格的性能。因此，要想最大限度地发挥网格计算的潜力，就需要建立有效的合作激励机制，以促进资源拥有者之间达成良好的合作。国内外文献中，目前对计算网格激励的研究相对较少，主要有Barmouta 等[4，5]提出的基于货币的“网格银行”服务，Xiao 等[6，7]提出的基于价格的网格调度；Paraioannou等[8]提出的信誉、可信度等非货币激励；Buyya等[9，10]从经济学角度设计的网格资源分配机制；而从互惠合作演化的角度对计算网格中激励机制进行研究，尚未发现文献报道。网格中，拥有资源的组织或个人在不断的交互中会体现出经济行为特征，因此可以将资源拥有者抽象地看作是理性的个体，它们通过自主的观察、学习以及根据自身经验不断调整自身的合作策略。它们之间的合作，类似于社会和生物种群间发生的一种演化合作。借鉴合作博弈研究成果，通过有区分的奖励和惩罚，我们可以设计出一种面向计算网格合作需要的激励机制，以提升合作效果。
2 间接互惠合作
最新研究表明，人类社会中合作演化遵循五大规则[11]：亲缘选择（kin selection）、直接互惠（direct reciprocity）、间接互惠 （indirect reciprocity）、 网络互惠 （network reciprocity）、群组选择（group selection）[2]，其中，亲缘选择在最近已经完成了从理论到实证的研究[12]。由于网格中的资源随时都在发生动态变化，资源的来源和用途有很大的不确定性，资源拥有者很难锁定和拥有固定的合作伙伴，因此资源拥有者间不容易形成直接互惠合作。顺应这种实际，引入间接互惠机制，则更可能激励资源拥有者之间进行良好的合作。
间接互惠是指，助人者为受助者提供帮助，但是对这种恩惠的报答，不一定直接来自受助者，而是可能来自于被受助者帮助过的其他受助者[13]。在延续多期的间接互惠合作中，合作伙伴的选择，并非仅仅是在当期进行，为了能够在非当期的情况下选择到恰当的合作者，就需要一个传递伙伴信息的媒介，这个媒介就是“声誉”。由此，声誉的建立、更新、传播，在间接互惠机制中具有非常重要的作用[14]。
在现实社会中，愿意选择合作行为的人，也就是“合作者”，通常会得到好的声誉，并且这种声誉经常会被传播得很远。同时，声誉较好的人也会有好的回报，那就是更愿意与人合作的人，通常可以得到比他人更多的帮助。而“拒绝合作者”由于不肯与他人合作，因此其声誉会较低，其行为同样会被广为传播，“声誉较差者”得到他人帮助的机会也更少[15]。按照这样的原理，可以在计算网格中有针对性地建立声誉系统，通过对声誉的管理，来有效地激励资源拥有者更好地合作。
3 基于间接互惠的计算网格合作激励机制设计
由于在计算网格合作激励机制研究中，很多微观细节并不重要，因此我们围绕问题的核心，构建了一个简化的计算网格结构，如图1所示，涉及的资源也统一为一致性足够良好的抽象资源。图1中，资源拥有者表示可以向网格提供共享资源的个体，同时，由于资源拥有者本身，也可能向网格提出资源申请，因此其身份也有可能转变为网格用户；网格资源代理是网格的组织者，它具备用户需求管理、资源发现、资源调度、任务管理、结果返回等功能，此外，它还肩负着声誉管理的任务。资源拥有者一旦加入网格，首先将自己可供共享的资源在网格资源代理上进行注册，网格资源代理接到用户的计算申请后，根据资源调度规则，选择恰当的资源拥有者，给其分配相应的计算任务。资源拥有者在规定时间内，如果完成了分配给它的任务，就视为合作，否则，则视为拒绝合作。
引起拒绝合作的原因有可能是主观的，也有可能是由客观原因引起的，比如硬件故障。可以将主观的拒绝合作视为恶意拒绝合作，将客观原因引起的拒绝合作视为偶然拒绝合作。由于恶意拒绝和偶然拒绝在合作中扮演着不同的角色，会对未来的合作产生不同的影响，因此在激励机制中需要对“拒绝合作者”中的“恶意拒绝合作者”和“偶然拒绝合作者”进行区分，并对恶意拒绝合作者进行严厉的惩罚，从而增加合作的稳定性[16]。设定，网格资源代理依据资源拥有者的合作表现，对其声誉信息进行评价并进行传播。计算网格中的用户有可能是网格外部用户，也有可能是资源拥有者自己，即资源拥有者自己也可以向网格资源代理提出计算申请。在计算网格中，合作激励机制主要有两方面的作用：一是为了激励资源拥有者尽可能多地共享闲置资源；二是避免资源拥有者在被分配了任务后恶意拒绝合作。
在现实社会中，我们用历史来揭示未来，而声誉可以传递历史的信息，因此以一套声誉系统，来记录过去发生的事情，来预测和引导未来的行动。
3.1 三维声誉系统
三维声誉系统由资源拥有者的合作贡献值、合作诚信度和连续拒绝合作次数3部分组成。设计三维声誉系统，是用以记录资源拥有者对网格的贡献和合作情况的历史信息，同时对拒绝合作的类型进行区分。
用 Pi（1≤i≤N,N为网格资源代理者的总数）表示第 i个网格资源代理，用Sj（1≤j≤M,M为资源拥有者总数）表示第j个资源拥有者。当资源拥有者在网格资源代理处注册信息以后，网格资源代理对资源拥有者的声誉信息进行管理。假设资源拥有者Sj在网格资源代理Pi上注册了资源，用R
其中，Cj表示资源拥有者Sj对网格的合作贡献值。合作贡献值用于记录资源拥有者向计算网格提供的共享资源总量，资源拥有者的贡献值可以累积。每隔一定时间，网格资源代理依据资源拥有者的贡献值，向其支付相应的“报酬”，通常报酬可以是实际的货币优惠，也可以是虚拟的积分。Hj用来表示资源拥有者Sj的合作诚信度，用于记录资源拥有者历史上的合作信息。当资源拥有者向网格资源代理提出计算申请时，资源拥有者的身份转变为用户，此时依据合作诚信度对资源的使用进行区别收费，对诚信度越高的资源拥有者，收取的单位资源使用费越低。nj表示资源拥有者连续拒绝合作的次数，用于区分资源拥有者的拒绝合作为“恶意拒绝合作”还是“偶然拒绝合作”。同一资源拥有者可以在不同的网格资源代理上注册资源，但是由于历史上为不同网格资源代理提供的服务质量不同，因此其在不同的网格资源代理上的声誉信息可能不同，在移动计算中，这一情况更为明显。
新加入计算网格的资源拥有者，设其初始声誉值为(0,h0,0)，其中h0(h0>0)为合作诚信度初始值。新加入计算网格的资源拥有者如果选择合作，其合作诚信度会增加，如果拒绝合作那么合作诚信度会减少。当资源拥有者Sj的合作诚信度Hj减少为0时，就认为Sj已经成为恶意拒绝合作者。
假设经过一段时间以后，资源拥有者Sj在网格资源代理Pj上的声誉值为R
其中，α为报酬支付系数，资源拥有者Sj在网格资源代理Pi上对计算网格的贡献值越大，其得到的报酬就越多。Pi向Sj支付报酬后，将Sj的合作贡献值置0，但是声誉保持不变。
假设此时资源拥有者Sj向网格资源代理Pi提出网格计算申请，即资源拥有者Sj的身份转变为用户，网格资源代理Pi依据 Sj的合作诚信度Hj向Sj收取费用，Pi向Sj收取的每使用单位资源的费用标准记为price(Pi,Sj)，如式（3）：
其中，β为收费标准系数，Sj的合作诚信度越高，网格资源代理Pi向其收取的单位资源使用费越低。T为激励调节量，T值越小，合作诚信度较小的资源拥有者对合作诚信度变化引起的收费标准变化越敏感，即T值越小，声誉系统对合作诚信度较小的资源拥有者激励越大。不同时期可以选择不同的T值，比如在网格建立初期，资源拥有者的合作诚信度普遍较低，为了激励更多新加入的资源拥有者提供合作，加入合作者队伍，可以选择较小的T值。在具体工程设计上，也可以根据需要将T设定为一个可以变化的值。
3.2 声誉管理机制
网格资源代理负责对资源拥有者的声誉信息进行动态管理，声誉管理包括声誉评价和声誉传播。
3.2.1 声誉评价
当用户向网格资源代理提出计算申请后，网格资源代理根据资源调度规则，选择恰当的资源拥有者，向其分配任务，并规定应该完成任务的时限。规定时限过后，网格资源代理根据资源拥有者完成任务的情况，对其声誉值进行评价。具体算法如下。
（1）当资源拥有者Sj在规定时限内完成任务时，此时认为Sj选择了合作。网格资源代理Pj增加Sj的合作贡献值Cj和合作诚信度Hj，同时将连续拒绝合作次数置0，即
其中，m表示资源拥有者本次合作提供的共享计算资源量。需要指出的是，当资源拥有者共享的不是计算资源，而是其他类型的资源时，网格资源代理对资源量的计算必须综合考虑该种资源的稀缺程度。对于越是稀缺的资源，给予的评价值也就越高。
（2）当资源拥有者Sj在规定时限内未能完成任务时，此时认为Sj拒绝合作。网格资源代理Pi增加Sj的连续拒绝合作次数，同时依据其连续拒绝合作次数nj减少Sj的合作诚信度，即
如果Hj=0，则认为Sj的行为属于恶意拒绝合作。
这里以连续拒绝合作为考虑的关键点，是以宽容的“一报还一报”模型（tat-for-tit）[17]为基础，并进行了改进，将宽容设为一个变化值，以避免偶发失误而引发中断合作。而这种偶发失误，最常见的场合是硬件设备故障，用户反复重试的情形。
3.2.2 声誉传播
广泛的合作行为有利于确保计算网格的性能，资源拥有者的合作行为被认为是“好”的行为，应当被广为传播。同样，大量的恶意拒绝合作行为会导致计算网格的性能不能保证，一旦发现资源拥有者的恶意拒绝合作这一“坏”行为，也应当将其广为传播，以避免出现错误选择。
（1）如果Sj选择了合作，Pi向其他网格资源代理传播Sj的合作行为信息，信息的传播动力学方程如式（6）：
其中，λ为考虑声誉信息传播会衰减的情况下的传播动力衰减系数。合作诚信度越高的节点，声誉信息传播动力衰减越慢，传播得越远。当其他网格资源代理收到Sj的合作行为消息后，如果Sj在其上注册了资源，那么将Sj的合作诚信度加1，并按照动力学方程向其他网格资源代理传播这一信息，否则只对消息进行传播。
（2）如果Sj拒绝合作，此时区分资源拥有者是否为恶意拒绝合作。如果Hj=0，则认为Sj的行为属于恶意拒绝合作，此时Pi向其他网格资源代理传播Sj的恶意拒绝合作行为信息，传播的动力学方程如式（7）：
连续拒绝合作次数越高的节点，恶意拒绝合作行为信息将被传播得更远。当相邻网格资源代理收到Sj的恶意拒绝合作行为消息后，如果Sj在其上注册了资源，那么将Sj的合作诚信度减1，将连续拒绝合作次数加1，并按照动力学方程向其他网格资源代理传播这一信息，否则只对消息进行传播。
如果Sj为偶然决绝合作，那么他的这一拒绝合作行为信息将不被传播。
通过声誉传播，选择合作的资源拥有者在网格中将获得更好的合作诚信度评价，而选择恶意拒绝合作的资源拥有者在网格中将得到更差的合作诚信度评价。
4 激励机制有效性分析
如果将资源拥有者进行一次资源共享，或一次计算请求看作是一个生存期，假设资源拥有者可以进行独立的行为决策，于是其可以通过分析、模仿以及积累的历史经验选择自己的最优策略。由此计算网格就构成了一个演化博弈网络，于是可以采用演化博弈理论进行分析。
由式（2）可知，资源拥有者每共享单位资源得到的报酬为α，假设资源拥有者每共享单位资源的成本为c，记资源拥有者每共享单位资源的收益为ps，那么：
当资源拥有者的合作诚信度Hj>h0时，记资源拥有者申请单位资源时由合作诚信度产生的收益为pr，由式（3）可知：
由式（9）可以看出，资源拥有者的合作诚信度越高，其申请单位资源时的收益越大。同时为了激励合作，保证共享资源不会受到损失，可以在式（8）中令α>c。于是每个生存期内，资源拥有者合作的收益总会大于恶意拒绝合作的收益，同时恶意拒绝合作者的“坏”声誉还会被传播，致使其合作诚信度降低，因此选择合作是资源拥有者的优势策略，于是理性的资源拥有者总会选择合作。下面只对资源拥有者选择合作的情况进行分析。
由式（6）可知，合作诚信度传播的方程为
由于dHj>0时才能传播，且传播距离为整数，因此传播距离为：
假设每传播一次，计算网格中平均有θ个网格资源代理，更新资源拥有者的合作诚信度。于是资源拥有者每进行一次合作，计算网格中平均有个网格资源代理更新资源拥有者的合作诚信度。假设资源拥有者随机地选择网格资源代理进行资源共享和发布请求，即每个生存期向任何一个网格资源代理Pi共享和请求资源的概率为（N为网格资源代理者的总数）。于是资源拥有者选择合作后，在进行下一次资源共享和请求时，其合作诚信度的期望增量为：
记资源拥有者Sj的闲置资源总量为 Ssj，sj记为资源拥有者实际共享的资源量，对于理性的资源拥有者sj≤Ssj。假设资源拥有者向网格资源代理共享和申请单位资源的概率分别为ε和η，其中ε+η=1。那么，在每一生存期内，资源拥有者的期望收益为：
将式（8）、式（9）、式（12）代入式（13）得：
Ej(sj,Hj)=ε·[s·j(谆-c)]+
(sj,Hj)(sj∈(0,Ssj],Hj∈[h0,∝))构成了资源拥有者连续的策略空间。由式(14)可知：当Hj一定时，sj越大Ej(sj,Hj)越大；当 sj一定时，Hj越大 Ej(sj,Hj)越大；且当 sj=Ssj，Hj→∝时Ej(sj,Hj)取得最大值。由此可见，每一生存期内，资源拥有者的期望收益随着资源拥有者的实际共享资源量以及合作诚信度的增加而增加。
结论：在激励机制下，在每一生存期，资源拥有者的最佳策略是最大限度地共享闲置资源，同时通过不断合作提升自己的合作诚信度。
由结论可知，在激励机制下，计算网格中理性的资源拥有者，都会不断选择尽最大可能共享自己的闲置资源。
5 结束语
本文在一个简化的计算网格体系结构下，基于间接互惠构建了计算网格合作激励机制。为了能够简化研究，文中只提出了一个简易的结构关系框架，对声誉信息的存储以声誉信息的网络传播进行了理想化假设，更为复杂的现实细节没有加以考虑，在实际应用中需要设计相关的更为精细的模块和协议，考虑更为复杂的信息传播模型，特别是要借鉴博弈理论中“颤抖的手”均衡，考虑网络出现“颤抖”时的情况，由此来进一步分析系统稳定性。另外，本文利用合作博弈理论检验了激励机制的有效性，得出了在激励机制下，资源拥有者最大限度地共享闲置资源，并通过不断合作提升自己的合作诚信度是最佳策略，下一步还需要利用实验对激励机制的稳定性进行实证研究。
1 Foster I,Kesselman C.The grid:blueprint for new computing infrastructure.San Francisco:Morgan Kaufmann Publishers,1999
2 Nowak M A.Five rules for the evolution of cooperation.Science,2006(314):1560～1563
3 Elizabeth Pennisi.How did cooperative behavior evolve.Science,2005(309):93
4 BarmoutaA,BuyyaR.GridBank:agrid accountingservices architecture (GASA)fordistributed systems sharing and integration.In:Proceedings of the 17th Annual International Parallel and Distributed Processing Symposium.Nice,France:IEEE Computer Society,2003
5 Elmroth E,Gardfjall P,Mulmo O,et al.An OGSA-based bank service for grid accounting systems.Lecture Notes in Computer Science: Applied Parallel Computing. State-of-the-Art in Scientific Computing.Lyngby,Denmark:Springer Verlag,2004:1051～1060
6 Xiao Lijuan,Zhu Yanmin,NiL M,etal.GridIS:an incentive-based grid scheduling.In:Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium.Denver,Colorado,USA:IEEE Computer Society,2005
7 Zhu Yanmin,Han Jinsong,Liu Yunhao,et al.TruGrid:a self-sustaining trustworthy grid.In:Proceeding of the 25th IEEE InternationalConference on Distributed Computing Systems Workshops’2005,Columbus,Ohio,USA:IEEE Computer Society,2005
8 Paraioannou T G,Stamouris G D.An incentives’mechanism promoting truthful feedback in peer-to-peer systems.In:Proceedings of the 2005 IEEE International Symposium on Cluster Computing and the Grid.Cardiff,U K:IEEE Computer Society,2005
9 Buyya R,Abramson D,Gidd Y J.A case for economy grid architecture for service-oriented grid computing.In:Proceeding of the 10th IEEE Heterogeneous Computing.San Francisco,USA:IEEE Computer Society,2001
10 Wolski R,Plankj S,Bryan T,et al.Gcommerce:market formulations controlling resource allocation on the computational grid.In:Proceedings of the 15th IEEE International Parallel and Distributed Processing Symposium.San Francisco,USA:IEEE Computer Society,2001:46-53.
11 Ellickson R C.Order without law:how neighbors settle Disputes.Cambridge,Massachusetts:Harvard University Press,1991.
12 Markus Waibel,Dario Floreano,Laurent Keller.A quantitative test of hamilton’s rule for the evolution of altruism.PLOS Biology,2011(9):1～7
13 Alexander R D.The biology of moral systems.Aldine de Gruyter,New York,1987
14 Karthik Panchanathan,Robert Boyd.A tale of two defectors:the importance of standing for evolution of indirect reciprocity.Journal of Theoretical Biology,2003(224):115～126
15 Nowak M A,Sigmund K.Evolution of indirect reciprocity.Nature,2005(437):1 291～1 298
16 Brandt H,Sigmund K.The logic of reprobation:assessment and action rulesforindirectreciprocity.JournalofTheoretical Biology,2004(231):475～486
17 Axelrod R.The emergence ofcooperation among egoists.American Political Science Review,1981(75):306～318
