学位论文 > 优秀研究生学位论文题录展示

P2P网络中基于博弈算法的优化技术研究

作　者: 左方
导　师: 张卫
学　校: 华东师范大学
专　业: 计算机应用技术
关键词: P2P网络算法博弈论网络优化合作行为促进机制自私路由避免副本分配网络带宽资源分配
分类号: TP393.02
类　型: 博士论文
年　份: 2013年
下　载: 119次
引　用: 0次
阅　读: 论文下载

内容摘要

大规模P2P网络已经是一种较为成熟的网络应用模式,它采用节点分散化以及节点角色地位平等的交互机制,使得网络中每一个节点都可以访问、享用各自的资源,如计算能力、网络带宽、存储空间、内容等。如今该网络技术的应用范围遍及文件分发、分布式存储、实时多媒体数据传输和计算机支持的协同工作等诸多方面。然而目前大多数P2P应用都建立在用户愿意提供共享资源的假设之上,这一假设忽视了节点出于自身利益考虑不按既定协议行事的情形。相关研究发现,自私性是P2P节点不可忽视的本性,节点的自私行为会导致P2P网络应用出现严重的问题,诸如节点不合作行为、节点间资源分配不公和节点自私路由行为导致的路由热点等等。而这些问题都会对P2P网络本身的运行质量与服务质量带来危害。为了解决这些问题,越来越多的科研人员进入了这个研究领域。本文在这样的背景下,结合当前P2P网络应用的实际情况,围绕着P2P网络中存在的上述问题,将P2P网络优化算法与算法博弈论相结合,对节点不合作现象、自私路由、节点间文件副本分配和节点间带宽分配,进行了深入系统的研究。本文研究成果可概括如下：(1)提出P2P网络节点间合作促进机制(简称IMNC, Incentive Mechanism for Node’s Cooperation in P2P networks)。IMNC针对节点在多重策略空间下的自私行为方式,促进节点合作,提高节点服务率和节点之间的合作程度。IMNC包括P2P节点策略动态演化博弈模型(PEGMNS)和基于PEGMNS模型的IMNC算法。针对大量异构节点的网络环境下,节点相互间的不信任或者为了某种利益产生先合作而后彼此背叛并拒绝合作等行为这些问题,论文设计了P2P节点策略动态演化博弈模型(PEGMNS),即把P2P网络当作一个渐进演化系统,强调其动态性和宏观性。模型研究对象是整个网络的节点群体在离散空间和连续时间下,有限理性的个体节点如何随着时间的推移在不断的重复博弈过程中通过自适应地学习或模仿他人策略,优化自身收益值。模型揭示了节点在空间扩散后的分布结构以及节点之间的网络博弈行为、节点加入或离开、节点异质性对整个系统变化态势的影响。同时通过理论分析,指出P2P节点之间的合作局面能够成为纳什均衡,即P2P节点采用合作策略是能够进入系统稳定态。论文在PEGMNS基础上提出了IMNC算法,即P2P演化策略选择算法。IMNC算法利用随机学习的方式诱导节点选择延迟相对较轻的路径进行流量交互,使整个网络中的流量尽可能达到纳什均衡的状态通过与其他算法(Powertrust和Native系统)的仿真试验结果比较,IMNC在节点服务率和系统中可用副本数量这两个方面上,IMNC明显优于Powertrust模型和Native系统。同时在IMNC作用下,节点之间合作明显加强,合作局面成为系统的稳定态。(2)提出P2P自私路由行为避免机制(简称MASR, a Mechanism for Avoiding Selfish Routing in P2P networks)。 MASR以P2P自私路由问题为解决目标,包含基于动态演化博弈的路由选择模型(EGMPR),以及此模型上的P2P自私路由避免算法。P2P网络中的个体往往在发起P2P session时以自己的利益为主,例如考虑到如何是自己的路由最短,或端到端的时延最小,而不顾及其他节点的路由状况,这在算法博弈论中称为自私路由问题。这样的自私的路由行为会造成局部路由热点拥塞以及路由秩序混乱等问题发的发生。针对这个问题本文研究了在路径延迟约束条件下的P2P网络内部的路由规律,并采用EGMPR来刻画节点路由的规律。通过理论分析指出,EGMPR存在具有帕累托最优的纳什均衡,在该均衡状态下节点路由平均时延最小,且节点没有动机擅自改变路由,路由抖动最小。基于EGMPR的理论分析,提出了具有节点自适应学习性质的自私路由避免算法,即MASR算法。在该算法下节点通过获取由他人提供的路由延迟时间信息,并通过不断地比较这些信息,逐渐做出合理的路由策略选择即模仿他人路由路径,从而达到规避拥塞的目的。通过仿真实验结果显示,MASR能够从路径延迟时间、链路占用率以及下载完成时间等方面,明显地提高网络的服务质量。(3)提出基于交易拍卖机制的P2P副本分配机制(简称SPRPM, Strategy-proof P2P Replica Placement Mechanism),解决P2P副本资源分布不合理,副本不均衡等问题。该问题核心着眼点就是研究不完全信息(节点彼此不完全知道对方的处理能力、带宽、服务质量等真实状态)与参与约束(保证节点在参与SPRPM下的收益至少不比参与前的收益差)这两者一起作用的情况下,解决P2P网络中节点间文件副本资源的分配问题。具体而言,我们将整个系统中对于文件副本资源的争夺看作一场非合作的不完全信息博弈,通过设计一场拍卖过程来解决谁获得副本。在拍卖过程中,利用算法博弈论中的VCG机制计算出一定量的虚拟货币,作为激励措施去诱导节点提供真实报价(报价高低与节点自身处理能力强弱相关)。然后根据报价确定获胜者,将文件优先分配给能力强的那些节点,由他们再进行处理或分发,这样带有优先性的资源分配规则可以使得节点间的资源分配更加有效。从具体实验结果来看,SPRPM不仅能确保拍卖的真实性,而且能够提高副本配置效率,同时也能够使得网络服务质量得到提升。(4)提出基于VCG拍卖形式的P2P带宽分配优化机制(简称VPBA,VCG-based P2P Bandwidth Allocation Mechanism),合理分配节点的P2P带宽资源,解决P2P带宽资源分布不合理,热点拥塞等问题。解决该问题的着眼点在于不完全信息条件下,(节点彼此不完全知道对方的处理能力、带宽、服务质量等真实状态),通过设计合理的带宽分配机制,使得带宽能够按照用户的真实需求进行分配,同时保证所有用户的社会收益最优。本文采用基于VCG拍卖形式的单维竞价信息带宽拍卖机制VPBA,通过激励用户说真话,合理分配带宽,达到所有用户收益最优的目的,以此解决P2P网络中节点间资源分配的效率问题。从具体实验结果来看,VPBA能够有效分配节点之间的带宽,较为有效地提高了网络通信能力与服务质量。

全文目录

论文摘要  6-9
ABSTRACT  9-11
目录  11-13
插图索引  13-15
表格索引  15-16
1 绪论  16-31
  1.1 研究背景与意义  16-17
  1.2 P2P网络概述与相关优化技术  17-24
    1.2.1 P2P网络及其特点  17-19
    1.2.2 P2P网络中优化技术的研究现状  19-21
    1.2.3 运用算法博弈论的P2P网络研究  21-24
  1.3 研究内容与创新成果  24-29
    1.3.1 本文重点解决的问题  24-25
    1.3.2 研究内容  25-27
    1.3.3 创新成果  27-29
  1.4 文章组织结构  29-31
2 P2P网络节点间合作促进机制：IMNC  31-55
  2.1 引言  31-33
  2.2 相关研究进展  33-38
    2.2.1 基于信誉模型的促进合作机制研究进展  33-34
    2.2.2 基于博弈模型的促进合作方法的研究进展  34-38
  2.3 P2P节点策略动态演化博弈模型  38-42
    2.3.1 预备知识  38-39
    2.3.2 动态演化模型的建立  39-42
  2.4 模型演化动力学特性分析  42-46
  2.5 IMNC算法的提出与仿真实验分析  46-53
    2.5.1 算法描述  47
    2.5.2 仿真场景设置与实验性能测度标准  47-49
    2.5.3 结果分析  49-53
  2.6 小结  53-55
3 P2P网络中自私路由避免机制：MASR  55-75
  3.1 引言  55-56
  3.2 相关研究  56-60
    3.2.1 非博弈论研究方法  56-58
    3.2.2 博弈论的研究方法  58-60
  3.3 P2P路由演化博弈模型与其演化动力学特性  60-65
    3.3.1 路由演化模型  60-64
    3.3.2 复制动态方程到路由演化模型映射的建立  64-65
  3.4 模型稳定性分析  65-68
  3.5 MASR算法与实验仿真分析  68-74
    3.5.1 MASR算法描述  68-69
    3.5.2 实验场景与测度  69-70
    3.5.3 结果分析  70-74
  3.6 小结  74-75
4 防策略操控的P2P副本分配机制：SPRPM  75-98
  4.0 引言  75-76
  4.1 相关研究  76-79
  4.2 预备知识  79-83
    4.2.1 机制设计  80-81
    4.2.2 VCG机制  81-83
  4.3 网络模型与副本分配机制的优化目标  83-85
    4.3.1 P2P网络文件共享系统模型  83-84
    4.3.2 副本分配目标  84-85
  4.4 防策略操控的副本拍卖分配机制  85-89
    4.4.1 副本分配机制描述  85-88
    4.4.2 副本分配机制向拍卖过程的映射  88-89
  4.5 SPRPM算法与算法性能仿真分析  89-96
    4.5.1 SPRPM算法的提出  89-91
    4.5.2 算法特性分析  91
    4.5.3 SPRPM性能仿真结果分析  91-96
  4.6 小结  96-98
5 VCG拍卖形式的P2P网络带宽资源分配机制：VPBA  98-121
  5.1 引言  98-99
  5.2 相关工作进展  99-102
  5.3 网络模型与带宽分配优化目标  102-106
    5.3.1 网络模型  103-105
    5.3.2 优化目标  105-106
  5.4 基于VCG的带宽分配模型  106-109
    5.4.1 带宽分配机制  106-108
    5.4.2 模型性质分析  108-109
  5.5 算法设计与仿真结果分析  109-119
    5.5.1 算法的提出与算法特性分析  109-113
    5.5.2 仿真方法与场景  113-115
    5.5.3 仿真结果分析  115-119
  5.6 小结  119-121
6 总结和展望  121-124
  6.1 本文工作总结  121-122
  6.2 未来研究展望  122-124
参考文献  124-130
致谢  130-131
读博期间以第一作者发表的论文成果  131

P2P网络中基于博弈算法的优化技术研究

内容摘要

全文目录

相似论文