论文部分内容阅读
近年来,随着计算机网络技术的不断进步,以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不是激励兼容的,进一步阐述了服务分配规范对合作机制的影响。