基于重复博弈的P2P网络节点行为策略模型＊

王春枝 陈 莉 陈宏伟 周 可

（武汉理工大学计算机学院1） 武汉 430070） （湖北工业大学计算机学院2） 武汉 430068）

0 引 言

P2P（peer－to－peer）即对等计算或对等网络，可以简单地理解成通过计算机之间的直接交换来共享计算机资源和服务.P2P应用发展到了引人关注的程度，信任和安全问题也越来越值得关注.大多数节点对整个网络的贡献很少，只有少数节点支撑整个网络资源，这种模式和传统的C／S模式没有多大区别，网络中的用户相互间缺乏信任，资源没有得到充分使用.例如：在Napster，Gnutella［1］中，有66%的节点对整个系统没有任何贡献，10%的节点提供了87%的文件资源，20%的节点提供了98%的共享文件.这说明P2P网络中存在大量的自私节点，容易出现以下问题：（1）搭便车（free－riding）问题［2］；（2）“公共物品的悲哀”（the tragedy of the commons）问题［3］；（3）不可靠服务和欺诈问题.所以提高网络节点之间的信任和安全是非常必要的，这样才能体现P2P网络的优势，最大化地利用资源优势.

基于重复博弈［4－5］的P2P网络节点行为策略模型的研究为设计更有效地激励机制奠定了理论基础.本文针对这些问题，深入分析节点类型的行为特征和重复博弈的特征，提出了一种基于重复博弈的P2P网络节点行为策略模型，利用重复博弈的贴现率来分析博弈双方采取何种策略才能使自己获得最大收益，最后通过仿真实验验证了该博弈模型的可行性.

1 重复博弈

定义 设G是一个基本博弈，重复进行T次，T可以是有限的，也可以是无限的.这样的博弈称为重复博弈，并记为G（T）.G称为G（T）的一个原博弈，每次博弈称为一个阶段博弈.当T是有限时称为有限重复博弈，当T是无限时，称为无限重复博弈.

在重复博弈G（T）中，在t阶段局中人选取行动记为sit，sit∈Sit，则第t期行动组合记为st＝（s1t，s2t，…，snt），则第i个局中人在T期的总收益为

重复博弈中，局中人可根据先前双方的博弈行为，决定自己下一阶段要采取的策略.在博弈论上被称为依存策略，依存策略又可看作为触发策略（trigger strategies），2个有名的触发策略：冷酷策略（grim strategy）和礼尚往来策略（tit for tat strategy）［6］.

2 P2P节点策略模型

根据网络中节点的推荐信任值［7］，即：一些曾经和服务节点有过交互经验的节点所给出的信任评价；还有我们自身对服务节点的信任，即自身和服务节点有过的历史交互经验所给出的评价.把P2P网络中的节点分为：善意节点G（good node）和恶意节点B（bad node），各类型节点都有各自的行为策略集合.

2.1 善意节点策略模型

P2P网络中善意节点的策略集合包括合作策略C（cooperation）和不合作策略N（non－cooperation），策略集S＝｛合作，不合作｝，记作｛C，N｝.合作策略是指其对所有邻节点的服务请求或转发请求都予以回应；不合作策略是指其不参与网络中的响应，也就是所谓的退出网络.表1显示的是2个善意节点博弈的收益矩阵，其中α为2节点合作的收益，β为2节点合作时的支付.

表1 节点G间博弈的收益矩阵

若只进行一次博弈，有惟一的纳什均衡点（合作，合作），其收益即均衡结果为（α－β，α－β）.若进行重复博弈，假设节点1先选择“合作”行为，但当对方采取的是“不合作”行为后，节点1立即在下一期也选择“不合作”行为，并永不改变.节点2也可以选择和节点1同样的策略.在此基础上，分析节点是否愿意单独违背自己的策略.

若节点1不改变自己的策略行为，则它的总收益，由式（1）得

当节点1在第t期改变策略时，节点2具有前期信息反馈，则在t＋1期，节点2也改变策略选择“不合作”策略.节点1也能觉察节点2的选择，因此在t＋1期，节点1也会选择“不合作”策略.这样节点1的总收益为

比较式（2）和（3）的大小.π1＞π′1，与下面表达式等价

因为δt－1＞0即当α＞β时，节点1不愿单独改变自己的策略；同样节点2也不愿意单独改变自己的策略.在P2P网络中，α＞β是一个网络能够维持的一个默认前提，所以当网络中的节点都是善意节点时，节点之间选择“合作”行为是一个均衡点.

2.2 恶意节点策略模型

P2P网络中恶意节点的策略集合包括攻击策略，共谋策略和搭便车策略.这里把恶意节点间博弈的策略也归纳为合作策略C和不合作策略N.其中，合作策略C包括恶意节点的共谋策略；不合作策略N包括搭便车策略.在P2P文件共享网络中，攻击策略是指恶意节点响应善意节点的服务请求并发送伪造文件或者病毒；共谋行为指的是当收到转发请求时，恶意节点将请求转发给其他恶意节点响应，还包括恶意节点间相互转发对方恶意节点所需的文件；搭便车行为指恶意节点只向周围节点发送服务请求来获取服务，而对所有的服务请求和转发请求都不予理睬.表2列出的是两个恶意节点博弈的收益矩阵，其中i代表两节点合作的收益，j代表两节点合作时的支付，这里考虑i＞j.

表2 节点B间博弈的收益矩阵

若只进行一次博弈，有惟一的纳什均衡点（合作，合作），其收益即均衡结果为（i－j，i－j）.若进行重复博弈，假设节点3选择的策略是：先选择“合作”行为，但当对方采取的是“不合作”行为后，节点3立即在下一期也选择“不合作”行为，并永不改变.节点4也可以选择和节点3同样的策略.这种情况下，来分析节点是否愿意单独违背自己的策略.

若节点3不改变自己的策略行为，则它的总收益，由式（1）得

当节点3在第t期改变策略时，节点4具有前期信息反馈，则在t＋1期，节点4也改变策略选择“不合作”策略.节点3也能觉察节点4的选择，因此在t＋1期，节点3也会选择“不合作”策略.这样节点3的总收益为

综述之，根据节点的推荐信任值来大致分析节点的类型，当善意节点自身周围的善意节点越多时，调整收支参数：α越大、β越小（α＞β），网络中的节点更倾向于采取合作策略，那么P2P网络就可以得到健康有序的发展，更加体现它对等网的优势；当恶意节点自身周围的恶意节点越多时，调整收支参数：i越小，j越大（i＞j），这时网络中的恶意节点就更倾向于搭便车行为，这可以有效地减少P2P网络中病毒和恶意软件的传播，减少共谋策略.这样做可以控制不良情况的发生，从而找到合适方法发展健康的P2P网络.

3 仿真结果分析

运用博弈分析软件gambit来进行试验仿真.设定两个博弈参与者参加博弈，根据节点的收益、支出的参数变化来调整节点的策略.结合上面文章中提到的参数变化分析验证模型的有效性，利用具有典型代表性的参数来验证分析.

分析善意节点之间的博弈，不妨先设α＝4，β＝3，再把收益调整为α＝9，β＝1.由图1和图2可知，图中上面一条曲线代表着两个参与者都选择合作策略，在α越大、β越小时，即收益调整后（图2）所示，网络中的节点更倾向于采取合作策略，而且愿意一直采取合作策略，从而保证了P2P网络的健康发展.

图1 善意节点博弈收益调整前变化

图2 善意节点博弈收益调整后变化

图3 恶意节点博弈收益调整前变化

图4 恶意节点博弈收益调整后变化

分析恶意节点之间的博弈，不妨先设i＝9，j＝1，再把收益调整为i＝4，j＝3.由图3和图4可知，图中上面一条曲线代表着两个参与者都选择不合作策略，即搭便车行为.在i越小，j越大（i＞j）时，网络中的恶意节点就更倾向于搭便车行为，这可以有效地减少P2P网络中病毒和恶意软件的传播，减少共谋策略.

4 结 论

本文针对P2P网络中节点的类型不同和所采取的行为策略不同，进行了分类讨论，分析了在何种情况下采取相应的策略能获得较大的收益，并且结合重复博弈中的贴现率来讨论在P2P网络中节点之间的交互行为的短期和长期收益，以及节点策略调整的约束性条件.本文还用博弈论仿真工具gambit验证了该模型.在今后的研究工作中，还需要深入研究P2P网络中的节点类型未知情况下，节点所采取的策略组合博弈模型.

［1］Saroiu S，Gummadi K P，Gribble S D.Measuring and analyzing the characteristics of napster and gnutella hosts［J］.Multimedia Systems，2003，9（2）：170－184.

［2］Feldman M，Papadimitriou C，Chuang J.Free－riding and whitewashing in peer－to－peer systems［J］.IEEE Journal on Selected Areas in Communications，2006，24（5）：1010－1019.

［3］Tang Yangbin，Wang Huaimin，Dou Wen.Trust based incentive in P2Pnetwork［C］／／IEEE International Conference on E－Commerce Technology for Dynamic E－Business，2004：302－305.

［4］Feldman M，Lai K，Stoica L.Robust incentive techniques for peer－to－peer networks［C］／／The 5th ACM conference on Electronic commerce，2004，4：102－111.

［5］Xue Kaiping，Wang Qi，Hong Peilin.A conceptual incentive mechanism of P2Pfile sharing systems based on game theory［J］.Network and Parallel Computing Workshops，2007：77－82.

［6］Martin Nowak，Karl Sigmund.The evolution of stochastic strategies in the Prisoner＇s Dilemma［J］.Acta Applicandae Mathematicae，1990，20（3）：247－265.

［7］Sun Y L，Wei Yu，Zhu Han.Information theoretic framework of trust modeling and evaluation for ad hoc networks［J］.IEEE Journal，2006，24（2）：305－317.