1006大设计翻译版以激励策略研究与实现

ResearchandImplementationStrategyofIncentiveInternetP2PsharingAuthor:WANGZhao-P2Pnetworkapplicationtechnologyisahottechnology,isoneoftoday'shotresearchdirectionofInternettechnology.P2PtechnologyoriginatedintheInternet,it'sthecoreideaisthedirectexchangeofdatabetweenthenodesinthenetwork,withoutrelyingonothernodes.P2Pnodeestablishesavirtualconnectionbetweentheapplicationlayer,sothattheentiresystemofinterconnectionbetweenallthecomponentsofavirtualnetworknodelogiconanapplicationlayer.Withthecontinuousdevelopmentofwirelesscommunicationtechnologyandencodingtransmissiontechnology,theInternetbusinessistowardfaster,moreandmorecleardirectionspeedahead,includingmoreserviceswithahighamountofdata,thecharacteristicsofhighreal-timerequirements.Butterminalssuchasphones,ipad,etc.thereislimitedavailabilityortrafficflowproblemsexpensive,butwillbeappliedtoP2Psharing,willgreatlyreducetheflowofeachnodeinthenetwork,sothateachnetworknodewithlesscostaccessmoreresources.Withthecontinuousdevelopmentofwirelesscommunicationtechnologyandencodingtransmissiontechnology,theInternetbusinessistowardfaster,moreandmorecleardirectionspeedahead,includingmoreserviceswithahighamountofdata,thecharacteristicsofhighreal-timerequirements.Butterminalssuchasphones,ipad,etc.thereislimitedavailabilityortrafficflowproblemsexpensive,butwillbeappliedtoP2Psharing,willgreatlyreducetheflowofeachnodeinthenetwork,sothateachnetworknodewithlesscostaccessmoreresources.ButparticipationintheP2Pnetworknodesarevoluntaryprinciplesgenerallyassumedthatallparticipatingnodescanvoluntarilytaketheinitiativetosharealltheirownresources.izetheirowninterestsbutinfactmanyoftheparticipatingnodeswillinstinctively,alwayshotogetasmanyresourcesfromothernodes,butalmostnoothernodestoshareresources,suchselfishbehavioriscalledhitchhiking,rideitexistsnodevehiclebehavioriscalledriders(rider).Tosolvetheseproblems,westudyandimplementacommunityforallnetworkdiscoverysystemthatcanauthorizetheuseofallnetworkdatatodiscoverallnetworkusers'socialcircle.Contentsofthispaperincludethefollowingthreeaspects:First,thestudyP2Pnetworkarchitecture,P2PtechnologyoriginatedintheInternet,it'sthecoreideaisthedirectexchangeofdatabetweenthenodesinthenetwork,withoutrelyingonothernodes.P2Pnodeestablishesavirtualconnectionbetweentheapplicationlayer,sothattheentiresystemofinterconnectionbetweenallthecomponentsofavirtualnetworknodelogiconanapplicationlayer.Researchincentivemodelofgametheory,gametheoryexpoundedongametheoryconcepts,models,methodswereintroduced,andyzedbasedongametheoryhassomeincentivemodelofP2Pnetworks.Second,thepapercomparesthecurrenttitfortatalgorithm,designedatitfortatstrategytolerantalgorithms.BecauseofthemobilityoftheInternetandinstabilitywillalwayscausesomeshortnetworkdisruptionofnormalnode,iffollowedwillleadtothesetitfortatalgorithmshortnetworkdisruptionnodeisconsideredbadnodeornodescheatingpunished,andtolerancethetitfortatalgorithmallowsnetworknodesinashortinterruptionoccursinacertainroundthisnodedoesnotsendresourcestoothernodes,whilestillthereareothernodessendtheirresourcesuntilthisnodebacktonormal,butmorethanthislimitwhenthenumberofroundsseenascheatingnodethisnode,thuskickedoutfromP2Pnetworks,sothisgeneroustitfortatstrategyalgorithmcanbetterdistinguishcheatingnodes,butalsotoadapttomobilityandinstabilityoftheInternet.Third,titfortatstrategyBasedtolerantalgorithmsdesignedanexperimentalmodeltoverifythefeasibilityofthisalgorithm.BygeneratingasimulationtosimulatetheInternetdevicenodeandonesetofclusterheadnode,theothernodeshavejoinedtheP2Pnetwork,thetransmissionofinformationusingtheabovealgorithm,theprogramgeneratesthefinaltestpassstateinformationbetweennodeseachother,anddisyeverymessagedeliveredsuccessfullyornot,thefinalstatisticsoftheaveragepacketlossrate,throughmultipletestdatathusdemonstratethefeasibilityofthisalgorithm.Inaddition,thearticlealsotheeffectivenessandperformanceofthesystemiscarriedoutevaluation,summarizessomeoftheresultsobtainedandthelackofmethods,andfutureworkarediscussed.：Internet,P2Pnetworks,tolerancetitfortat 绪 研究背 国内外研究现 研究目标与内 课题来 的组织结 P2P网络中激励机制的相关研 P2P网络概 P2P网络的特 P2P网络的分 P2P网络的应 P2P网络中激励机制的相关研 基于效用函数的激励方 基于经济模型的激励方 基于博弈论的激励方 本章小 博弈论及基于博弈的激励机制研 博弈论的基本概 纳什均 博弈论的分 合作博弈与非合作博 静态博弈与动态博 完全信息博弈与不完全信息博 本章小 移动互联网P2P共享中基于宽容的针锋相对博弈的激励机制的设计与研 针锋相对算 宽容的针锋相对算 模型的分析与建 策略分 本章小 模拟实验及实验结果分 模拟实验系 实验系统功能需 平台环境和开发语 实验结果分 本章小 总结与展 工作总 工作展 致 参考文 P2P技术是目前网络应用的热点技术，也是互联网技术的热点研究方向之一。其他节点。P2P节点之间在应用层建立虚拟连接，从而使整个系统中的所有节点之间互我们把它称作覆盖网(overlay)[1]。根据覆盖网的结构,P2P系统划分为集中式拓扑(centralizedtopology)、分布式非结构化拓扑(decentralizedunstructuredtopology)和分布式结构化拓扑(decentralizedstructuredtopology)[2]。随着无线通信技术和编码传输技术的不断发展，移动互联网业务正向着更快、动终端如、ipad等存在着可用流量有限或流量昂贵等问题，而将P2P应用于共但P2P网络点的参与都是自愿的原则,通常假设所有参与节点都能自愿主动地共享自己所有的资源。但是事实上很多参与节点都会本能地最大化自已的利益,总是希望能尽可能多的从其他节点获取资源,却几乎不为其他节点共享资源,这种自私行为被称为搭便车存在搭便车行为的节点称为搭便车者(rider)3]70的网络参与节点几乎不向网络做出任何贡献,而是以一个搭便车者的免费使用网络中其他共享节点的可用资源50%的网络可用资源来自1%的共享节点[4][5]为一种非他性占有的公共物品,被大多数P2P节点无节制的使用,大量搭便车现象的存P2P系统资源的平衡,P2P共享中设计一种激励策略来促使P2P网络中的节点主动共享资源，建立一种公平的基于微支付的模型其基本思想是以虚拟货币的方式作为P2P网络中服务或的媒介，惠模型的基本思想是P2P网络中的服务提供节点再为其他节点提供服务后，能够得到某种直接；基于信誉的模型主要指在P2P网络中引入等级概念，即每个节点根据自己的服务和中，其他节点都根据请求节点的信誉值给予对应等级的回应。P2PP2PE.Adar[4]等人最早在研究中Gnula网络中多数节点没有共享文件或是共享了Gnula网络的初衷只是想从对等网络中获取其他节点的服务，而不愿意为对等网络做贡献，Gnula存在大量的搭便车用户，自身缺乏激励提出了一个分析框架去研究D.Hales现有的激励机制通常是通过应用程序的编码来实现，不能充分利用开放式系统的优势。他提出了节点拷贝高效用节点的和行为来提高自身的效用的SLAC机制。但作者同时也，SLAC要求节点之间进行效用的比较，在实际中并不华东师范大学计算机系的夏素贞在2004年提出一种基于网格的信息共享系统，该 PeerPeer系统同样存在与同类Peer系统相似的Nash均衡。华技大学计算机科学与技术学院的胡和平教授于2008年提出了一个基于承诺立公平的资源共享环以实现P2P网络公平资源共享。东南大学计算机网络和信息集成的博士于年2006提出了基于博弈理论励机制是能够适应结构化P2P网络的自组织管理模式及网络规模的可缩放性的。用户的流量。如，流量大于20G且共享率低于0.3者，流量大于100G享率低于0.8者，流量大于750G且共享率低于0.9者，流量大于1TB且共享率低于1者，将不能所需资料。未来花园还严厉打击各种形式的、互、ipad等存在着可用流量有限或流量昂贵等问题，而将P2P应用于共享，将会大大减少每个网络中移动节点的流量，使每个网络节点用更少的成本获得的资源。本课题的目标是，设计实现一种激励算法，使加入P2P网络中的各个移动互联第一，研究P2P网络架构，P2P技术于互联网，它的思想是网络中的节点之间直接进行数据交换,而不依赖于其他节点。P2P节点之间在应用层建立虚拟连接，从并分析了己有的基于博弈论的P2P网络激励模型。法则会导致这些短时间网络中断的节点被认为是坏节点或节点而受到惩从P2P 第一章绪论P2P危害，并阐述了激励机制对抑制-riding现象的重要作用。之后，本文介绍了三类激其是后期建模需要使用到的一些概念、模型、方法，并分析了己有的基于博弈论的P2P激励作用，达到减少-riding的现象，又让移动互联网点的不稳定性得以解决本文主要研究并设计一种基于移动互联网P2P共享激励机制的算法，并通过java模拟出各个移动互联网节点加入网络并通过此算法进行共享的过程，且统计出结果。本章将分别针对与本系统设计过程相关的技术展开介绍。P2P系统的诞生，P2P网络经历了一个高速的发展过程，P2P网络的出现改变了人们使用网络的方式，为网络的发展提供了新的思路。P2P网络中的实际上，P2P70年代网络产生以来就存P2PC/S架构中服务器的负载分散到节点中，因此，加入系统的节点越P2P网络的特点可表现为以下几个方面：P2P系统中各种服务是分散在各个节点之间进行的，相比其传统P2P网络均采用了不同的资源定位和路由选择模型，并应用于不同的领域，我们分别对三种类型的P2P网络进行介绍。P2PC/SC/S架构中，服务器中据索引，将拥有该资源的节点给请求节点，之后由请求节点直接拥有资源的节点，所需的资源。提供的查询和文件的。由于没有服务器，节点间信息的索引服务请求将通过网络一步步的执行，直到成功或超时。这种结构的典型代表是Gnula，它采用P2P模式避免了对中心服务器的依赖，也不需要利用广播的方式来进行资源发现，而是通过使用分布式哈希表（DistributedHashTable，DHT）来构建出使得DHT起来较为。P2P网络由于其高动态性及可扩展性，受到了广大互联网用户的青睐，的学者P2P2台计算特定的服务器或上。用户需要时，需要先从服务器或上对所需文件进行搜常高，当用户的量增大时，也要求服务器在这种情况下能提供有效的服务。同时，该模式的抗能力也不好，如果服务器或遭到，可能导致整个网络的瘫痪， la以及eMule等都是此应用的典型代表。Napster是用于音乐文件交换的P2P应用软件，该软件采用了集中式 器并不用于MP3文件，而是用户共享的MP3文件的索引。当用户需要某个音频文件时，将会首先连接到Napster索引服务器上进行检索，服务器将拥有该BitTorrent(BT)是一个具有高度可扩展性的P2P文件共享协议，文件在协议中被分成大小相等的分片，对文件感的节点能够通过连接一些当前正在给文件的节点来组成 名为.torrent的文件中，并将该文件放在web服务器上供其他节点，文件包括了文件名，文件大小，分片大小及服务器(tracker)的地址等信息。其中，服务器是BT网络和用户信息的者，其职责是该文件的用户并帮助用户互相发现对方，对一个文件的起着关键性的作用。Gnula与Napster的不同在于前者没有服务器而后者有，较Napster的混合式星型结构而言，Gnula是纯粹意义P2P网络，它是一种无结构、纯分布式的网络，在查询过程中，Napster是依靠其索引服务器，而Gnufa则完全依靠节点间的协作，采用泛洪的广播方式来传输网就对网络的带宽提出了。而P2P技术由于其资源的分散性，将带宽分配到网络中的各个节点上，因此，随着加入网络的节点数的增加，流的速度会不降反增。因此，P2P模式被认为很适合流的传输，以至于对P2P研究热点在很短时间内转移到由科技大学张欣研开发的Coolstreaming原型系统最早的P2P流直展和可靠性的网状多播协议应用在P2P中的系统。后期相继涌现了大批基于P2P的流,、点播系统，如UUsee、PPLive及PPstream等。的P2P搜索引擎搜索范围大，几分钟就可以搜遍数百万台PC。据各自的情况，再将任务分散到其他节点。SETI@homeP2P在对等计算方面最典型P2P技术对于协同工作也非常有用，传统的协同工作需要服务器的干预，信息!都需要通过服务器的转发，长此以往，对服务器造成了很大的压力，特别是传输语音或InternetP2P网络中仍然存在需要解问题就是搭便车问题，本文就是针对该问题设计相应的激励模型，以降低-riding现P2P网络提供资源的行为[7]，显然这与P2P网络“我为人人，人人为我”的设计理P2P网络中-riding现象的存在，意味着系统中有部分资源没有得到充分利用，P2P系统的。对系统造成以下影响：P2P网络中存在着一些热心节点，他们承担了网络中大部分的资源查询及等搭便车现象产生的根本原因是因为现有的P2P系统缺乏一种有效的对搭便车行为step1 step6； step6step7系统继续等待服务，如果有新的请求信息，转到step3；如果节点为其他节点提供了服务，则转入step6。eBay中使用的利用中心服务器对节点行为及数据交换进行监督的基于信誉的激励机制，由Figueiredo等人基于惩罚的激励机制也是这类算法的典型应网络点的搭便车行为突出时，将导致节点无法查询和资源，此时它将离开网络，使得P2P网络的数量急剧降低。是在一些约束条件下(如带宽、优先级等)获得尽可能好的资源来满足自己的需对动态性较强的P2P网络（如移动互联网，该方法在应用方面仍然存在缺陷。博弈论在分析社会群体和经济活动中和集体选择最优策略方面有着天然的优个简单的行为，而与同时的其他节点的选择策略相关，节点之间的可以用一个P2P网络的角度来分析一个节点的行为策略与其他节点策略之间的关系。本章首先对P2P网络的概念、特性及分类进行了简单的介绍，随后阐述了在P2P网络广泛的应用的同时，带来的-riding现象，对于-riding现象对系统的危害，普遍认为博弈论诞生于1944年由冯·诺依曼和斯坦恩共同合作编写的《博弈念，并将二人博弈推广到n人博弈，奠定了这一学科的和方法基础。到投资、消费、雇用关系分析、拍卖及竞标等多个方面。下面我们通过“困境”逐Tucker1950年定义的一个由两个参与人组成的博弈。该博弈都，将均被判一个月；如果双方都坦白，都会因被判10个月；如果有一个人坦白，而另一个人沉默，则坦白的一方将马上获释，而沉默的一方将1年。我们用支付矩阵表达此博弈如表格3-1困境支付矩阵表格3-1困境支付矩21别用于表示两个参与者的支付，其中第一个数字表示犯1的支付，第二个则表示1犯2同样是占有策略，因此，（坦白，坦白）就是困境博弈的占有策略均衡。究人们在利益相互影响的中如何选决策使自己的，即策略选择问题。自己的，即策略选择问题。困境是典型的非合作博弈，正如其中所表现的略。由此可见，非合作博弈更符合P2P网络点的行为。行动的一方对先行动一方所采取的策略并不知情。困境博弈就是典型的静态博弈，适合用不完全信息博弈来处理移动互联网P2P共享系统。网P2P共享的需求角度出发，设计了宽容的针锋相对算法。因为移动互联网P2P网络点的稳定性较差，为了使节点能够一定的网络其中T(x)x我们用ai(t表示节点i在第tA{CD表示每个节点的行为集合，其中CD代表转发，01，j表示第j个时隙节点的收益函数。)当出现一方出现故障的时隙起，另一方在n个时隙内选择无条件交换数据，这n个时隙称为阶段；时隙开始，在mn个时隙内采取针锋相对策略。这mn个时隙称为检验阶段；其中n点u在这段时间内的收益为n(n)F(x)i1n

1令nF(x)i1T(x)n1n

2 4-2成立的最大正对这个策略的解释是：在(u,v)这个节点对中，对于u这个节点，它可以节点在n时隙内的连续故障。也就是说节点uv之间数据传输的过程中，只要在n这个范围内进行至少1次的合作，那么对方节点的收益就会大于0n(n)T(x)nF(x)

3 4-2可知，当n的取值在一络故障后最多会有n2个回合本节点对会采取针锋相对策略。而且远大于T(x)。对节点来说，由于它了解诚实节点采取的策略，那么它每采取一次不合作行为，就要在此后在n个时隙内采取合作行为，才能使自己的。宽容的针锋相对策略中，如果节点对(u,v)中包含一个诚实节点u和一个节点v那么如果v在u的每个阶段内采取k次不合作行为，称该策略为策略k，而如果节点在诚实节点的每个阶段的前k个时隙都采取不合作行为，称该策略为连策略k引理4.1：策略1的最佳选择是节点在诚实节点阶段的第一个时隙采取不合作行为，而连续策略k是策略k的最大收益策略。vv在博弈开始时对这2n个时隙的期望 v(2n)T(x)i1F(x)i1F(x)t1 4v 考虑到0 v(2n)T(x)i1F(x)i1 5v 也就是t1时节点v的期望越大。所以前k个连续时隙不合作。证毕。4.2：宽容的针锋相对策略中，如果节点对(uv包含一个诚实节点u弊节点v，当n2时，采用连续策略k的节点在kn时期望。首先证明，在k1时，连续策略k的期望收益大于连续策略1连续策略1中，初始周期中v有一次不合作行为，那么此后n个时隙u会采取针锋相对策略，那么每经过2n个时隙重新回到起始状态，连续策略k在第一个周内的n个时隙内采取k次合作策略，那么此后的kn个时隙内u会采取针锋相对策略，所以连续策略k每n(k1)个时隙重新回到起始状态。比较两种策略在一个公倍2n(k1)时隙内的期望收益：连续策略1：2n(k 2n(k1(2nk2n)T F F(x)( ) 6 连续策略k2n(k 2n(k n(kk(2nk2n)

T(x)i1

F(x)i1F(x)(i1

in(k

7考虑到01，比 4-6 4-7可以得k(2nk2n1(2nk2n在n2然后证明，在nk1时，连续策略k优于连续策略k1。比较两种策略在一个公倍数nk(k1)时隙内的收益连续策略kk (nk2nkk

nk(k

T(x)i1

nk(k

nF(x)i1F(x)(i1

n(ki1...ink

nk2ink2

8连续策略kk(nk

nk)

nk(kT

i1

nk(kF

nF

n(k in(k

nk... i(k...

9k 比较可以得出， (nk2nk)(nk2nk)。所以，k越大，连续策略k 望收益越大，由于诚实节点的阶段为n个时隙，所以kn时，连续策略k期望在发生网络故障后在有限时间内达到稳定合作状态。并且由命题4可以看出，如果的初始成本与一个时隙内的最大收益T(x)相差太大，那么节点需要经过相当长大减少，从而达到减少了-riding现象的效果。从网络上的数据。可设置节点数量5-110001000次传输中的丢包率，如图5-2。5-25- 5-3 5-45-4可知，故障率越大，丢包率越高，而平均收益也会相应减小。当然在现实移动互联网P2P网络中各个节点的影响不会很大。率随节点数变化的曲线如图5-5 图5-5丢包率随节点数变化的曲由图5-5可知，当故障率与宽容系数不变时，宽容的针锋相对策略的发现作弊节点并能很好的降低节点的收益，在发现节点后，则会及时对节点进行P2P网络，从而达到减少-ridingP2P网络更加“有3个自变量与丢包率这个因变量之间的关系，并对其进行了分析，证明了宽容的针锋相对策略在移动互联网P2P网络中的可行性与有效性。P2P技术是目前网络应用的热点技术，也是互联网技术的热点研究方向之一。P2P技术于互联网，它的思想是网络中的节点之间直接进行数据交换，而不依赖于其他节点。P2P节点之间在应用层建立虚拟连接，从而使整个系统中的所有节点之随着无线通信技术和编码传输技术的不断发展，移动互联网业务正向着更快、、更清晰的方向高速前进，其中业务更具有高数据量、高实时要求的特点。但移动终端如、ipad等存在着可用流量有限或流量昂贵等问题，而将P2P应用于多的资源。但P2P网络点的参与都是自愿的原则，通常假设所有参与节点都能自愿主动被称为搭便车，存在搭便车行为的节点称为搭便车者(rider)。针对这些问题，本文第一，研究P2P网络架构，P2P技术于互联网，它的思想是网络中的节点之间直接进行数据交换，而不依赖于其他节点。P2P节点之间在应用层建立虚拟连接，析了己有的基于博弈论的P2P