自组织P2P网络中合作问题及其激励机制研究

摘要

近年来，随着计算机网络技术的不断进步，以P2P网络、Ad hoc网络为代表的一类新型网络迅速发展起来。这些网络往往由理性的自治节点通过自组织方式相互连接而成，故可统称自组织网络。在这类网络中，节点常为了谋求自身利益的最大化而采用自私的行动策略，易于引起个人利益与系统的整体利益的冲突，若不加以引导，节点的自私性将引起网络资源的浪费，降低系统的可用性。事实上，这种自私行为已经导致了大量的P2P网络的消亡。因此，随着自组织网络的进一步发展，旨在克服网络自私行为的研究工作正受到越来越多的关注。本文正是切合当前的网络应用的实际需要，研究自组织网络的合作机制，特别是面向大规模自组织网络的分布式合作机制。
　　 自组织网络普遍具有动态性强、无中心节点、规模庞大等特点，在集中式合作机制中，中心节点易成为性能的瓶颈和安全的隐患，分布式合作机制是当前研究的重点。但是这种分布式的组织方式也增加了路由、信息存储、服务分配等方面机制设计的复杂性；同时，由于分布式合作机制的执行只能由自私节点本身承担，因此该机制执行本身也存在激励问题。本论文针对以上问题，以提高自组织网络可用性为目标，探讨并实现了多种有效的、实用的分布式合作机制。
　　 (1)针对应用层P2P网络，提出了基于一般等价物的服务交换合作机制。这种合作机制的一个难点问题是如何采用分布方式对作为一般等价物的货币进行有效的管理。对此，本论文提出一种二值货币--不可转让的债务关系及相应的支付协议。由于邻居节点间存在重复交互，节点能自发的维护货币及支付的有效性，从而形成分布式货币管理机构。理论分析表明，在基于债务的交换机制下用户的服务策略存在Nash均衡；而进一步的实验表明，存在激励有效的Nash均衡，用户贡献值与获得的利益成正比关系。
　　 节点间的债务关系集合构成了债务网络。论文讨论了服务节点到请求节点债务链路的构造问题，即债务网络的路由问题。由于常规路由算法不能适应债务网络极强的动态性，因此在DHT网络中，拟采用贪婪路由降低动态网络的路由表维护开销，降低货币管理开销。同时论文也给出了非结构化网络中基于洪泛的债务链路构造算法。
　　 (2)基于债务的货币也可应用于Ad hoc网络--网络层的对等网络。债务网络M-DRN的路由问题是合作机制的关键问题。债务网络作为Ad hoc网络之上的一种覆盖网络，Ad hoc网络路由算法对债务机制的性能有很大影响。论文提出了基于最优路径的地理路由算法PGA，并通过实验证明，路径构造时引入恢复机制可以显著提高该算法的报文投递成功率。同时，该路由算法具有的路由无环性使得无状态路由成为可能，显著降低了路由协议的设计复杂度与维护开销。以PGA路由算法为基础，论文提出了适用于M-DRN的路由算法，并采用多路探测来补偿路径失效造成的路由成功率的降低。
　　 在上述工作基础上，论文针对Ad hoc网络中的文件共享应用设计了基于债务的合作机制。Ad hoc网络中的文件转发路径仅由本网节点组成，文件共享和文件转发都存在合作需求。由于两者具有不同的执行代价，在合作机制中仅采用二值货币无法满足支付的粒度。论文提出了连续型债务SimDebt，并通过在M-DRN中构造可行路径并分配费用，实现了对文件服务节点和中继节点的有效激励。
　　 (3)论文还对基于声誉的分布式合作机制的有效性进行了理论研究，并针对二阶搭便车问题提出了基于连续型二阶声誉的合作机制。提出了一种可行的服务分配规范PSL，通过对两两匹配、非两两匹配的不同博弈模型的分析和仿真实验，说明了结合该声誉和PSL规范能够有效的激励用户的合作。
　　 同时，论文还通过引入占优于Disc及NonDisc的中间策略RPFS，证明了比例分配规范RSL不是激励兼容的，进一步阐述了服务分配规范对合作机制的影响。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.1.1 对等计算的概念及应用

1.1.2 自组织对等网络的定义

1.1.3 应用需求

1.2 问题定义

1.2.1 对等网络节点类型

1.2.2 自组织P2P网络特性

1.2.3 合作问题及合作机制的定义

1.2.4 自私用户行为模型

1.3 研究目标及研究内容

1.4 论文组织结构

第二章 自组织P2P网络合作激励机制研究现状

2.1 合作问题的理论研究

2.1.1 基于重复博弈的合作进化

2.1.2 基于间接互惠的合作理论

2.2 合作理论在P2P网络中的应用

2.2.1 基于多人重复随机博弈的合作激励机制

2.2.2 基于交换及经济手段的合作激励机制

2.2.3 基于声誉的合作激励机制

第三章 应用层P2P网络中基于债务关系的文件共享机制

3.1 应用层P2P网络体系结构

3.1.1 分散无结构P2P网络

3.1.2 结构化P2P网络(DHT网络)

3.2 基于结构化债务关系网络的文件交换机制

3.2.1 债务关系网络DRN的基本概念

3.2.2 结构化债务关系网络的设计

3.2.3 文件交换机制的激励兼容性

3.2.4 威胁模型

3.3 无结构债务关系网络

3.3.1 债务网络的构建

3.3.2 债务网络中基于有限泛洪的资源搜索与债务更新

3.4 仿真及分析

3.4.1 仿真环境

3.4.2 实验结果

3.5 进一步工作

第四章 自组织Adhoc网络中基于债务网络的文件交换

4.1 基于SimDebt的文件交换方案SDE

4.1.1 债务关系SimDebt及债务网络M-DRN

4.1.2 文件交换方案SDE

4.1.3 激励机制的有效性分析

4.2 M-DRN网络的路由算法

4.2.1 Ad hoc网络的地理路由

4.2.2 PGA路由算法在M-DRN网络中的拓展

4.3 模拟及性能分析

4.4 本章小结

第五章 基于二阶声誉的P2P网络合作机制

5.1 声誉机制的博弈模型及一阶声誉的理论分析

5.1.1 二阶搭便车问题的引入

5.1.2 基于声誉的分布式激励机制的演化博弈模型

5.1.3 一阶声誉博弈模型的定量分析

5.2 基于连续型二阶声誉的合作机制

5.2.1 连续型二阶声誉

5.2.2 两类服务分配规范

5.2.3 比例分配规范RSL下合作机制的有效性分析

5.2.4 PSL服务规范下合作机制的有效性分析

5.3 结论

第六章 结束语

6.1 论文总结

6.2 进一步的研究工作

参考文献

致谢

作者攻读博士学位期间发表或录用的学术论文