基于生态网络的P2P环境信任博弈进化模型

24 2007，43(23) ComputerEn∥neeringandApplications计算机工程与应用 基于生态网络的P2P环境信任博弈进化模型 刘凤鸣1．丁永生1，2 LIUFeng-min91，DINGYong-shen91，2 1．东华大学信息科学与技术学院。上海201620 2．东华大学数字化纺织服装技术教育部工程研究中心．上海201620 1．CollegeofInformationSciencesandTechnology，DonghuaUniversity，Shanghai201620，China ’- 2．EngineeringResearchCenterofDigitizedTextile＆FashionTechnology，MinistryofEducation，DonghuaUniversity，Shanghai 201620，China E—mail：ysding@dhu．edu．on LIUFeng-ming，DINGYong-sheng．EvolutionarymodeloftrustgamebasedonecologicalnetworkinP2Pnetworks。 ComputerEngineeringandApplications，2007，43(23)：24--27． Abstract：Thetrustmechanismcandetectandpunishthemaliciousnodes，andpromotehonestandcooperativeinteractionsin theP2Pnetworks．Inthispaper，wepresentatrustgamemodelbasedontheevolutionarymechanismofecologicalnetwork，and applythereplicatordynamicsmechanismtoanalyzetheevolutionarytrendoftrustrelationshipsamongnodes．P2Pnetworksusing thismodelhavegoodperformanceandstability． Keywords：P2Pnetworks；trustgame；evolutionarygame；ecologicalnetwork；replieatordynamicsmechanism；evolutionarystablestrategy 摘要：P2P网络中信任机制能够很好地检测和惩罚恶意节点，激励节点之间合作。提出了一种基于生态网络协同进化机理的信 任博弈模型，应用复制动态机制分析了节点之间信任关系的长期演化趋势，从理论与实践上说明了在P2P网络中应用此信任模型 具有良好的演化稳定性及性能的整体最优性。 关键词：P2P网络；信任博弈；进化博弈；生态网络；复制动态机制；进化稳定策略 文章编号：1002—8331(2007)23—0024—04文献标识码：A 中图分类号：TP393 1 引言 信任作为网络安全中的一个重要概念。是指网络节点之间 关系的集合。这种关系的建立与节点的历史行为有关[I】。但在 P2P网络中。没有中心控制服务器和可信第三方，信任的建立 尤为困难，因为用来评价信任的信息或证据有着非完整性、不 确定性等特点。又由于其天生的开放性、匿名性、自治性等，如 Napster、GnuteUa。导致有66％的节点对整个系统没有任何贡 献．10％的节点提供了87％的文件资源．20％的节点提供了 98％的共享文件f2】。这充分说明存在着大量的自私节点(Free Rider)．这样节点的存在严重影响了整体网络的性能，破坏了 网络系统的稳定性。因此，建立适当的机制，促进节点间的信任 合作，激励诚信、惩罚失信是很有必要的。 目前。P2P网络中信任机制的研究，如EigneTrustt月、Eigen- Rept4]、PeerTrust[!q等信任模型。试图通过收集节点的全部声誉信 息(即历史行为)计算节点的全局信任度。这种理想的模式实施 起来是很困难的，一是需要全局节点的配合，这本身又是信任 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：二是计算量与网络通信开销大。因此其可行性和必要性 有待进一步研究。基于局部信息计算的信任模型，如Chord[叼、 P—Gridr0等，对于自治节点的来去自由又显得“证据不足”。因 此，信任的定量研究有待进一步探索。信任是社会生活的基本 事实，是一种预期，是相信他人未来的可能行动的赌博嘲，信任 的这种不确定性和不可控性也使得上述计算模型过于“简单”。 L．Muitg}、MaryL．Ri硝on[101等从博弈论角度对信任问题进行了研 究。但更侧重于社会学与经济学方面的探讨。 信任是一种赌博，也就是博弈。经典博弈论是基于一种“完 全理性”的假设。要求行为主体应具有完善的判断和预测能力， 并且始终追求其自身利益的最大化。而Alchian认为{111，在真实 基金项目：国家自然科学基金重点项目(theKeyProjectoftheNationalNaturalScienceFoundationofChinaunderGrantNo．60534020)；国家自 然科学基金(theNationalNaturalScienceFoundationofChinaunderGrantNo．60474037)；教育部新世纪优秀人才支持计划(Program forNewCenturyExcellentTalentsinUniversityfromMinistryofEducationofChinaunderGrantNo．NCET_．04．415)：教育部科技创新 工程重大项目培育资金项目；上海市国际科技合作基金项目(theCultivationFundoftheKeyscientificandTechnicalInnovation ProjectfromMinistryofEducationofChina，InternationalScienceCooperationFoundationofShanghaiunderGrantNo．061307041)；教 育部高等学校博士学科点专项科研基金(SpecializedResearchFundfortheDoctoralProgramofHigherEducationfromMinistryofE． dueationofChinaunderGrantNo．20060255006)。 作者简介：刘凤鸣(1969一)，男，博士研究生，从事网络智能和信息安全等研究；丁永生(1967一)，男，博士，教授，博士生导师．从事智能系统、网络智 能、DNA计算、人工免疫系统、生物网络结构、生物信息学、数字化纺织服装、智能决策与分析等研究。 万方数据 刘凤鸣，丁永生：基于生态网络的P2P环境信任博弈进化模型 世界中，将来是不完全信息(IncompleteInformation)和不确定 预见(UncertainForesight)的，所以约束条件下求最优的完全理 性并不普遍。他原创性地提出了基于生物学进化论“自然选择” 思想 教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿 的 制度 关于办公室下班关闭电源制度矿山事故隐患举报和奖励制度制度下载人事管理制度doc盘点制度下载 演化模型。在该模型中，人通过模仿、试错(Imita- tiveandTrial—and—ErrorBehavior)适应不断变化的环境。并生 存下来。而“复制动态”(ReplieatorDynamics)机制在此基础上 假设博弈方为有限理性的，通过模仿、试错等手段，决定其行为 策略。并通过反复博弈和进化稳定策略实现动态策略调整及其 演化稳定性。MaynardSmith给出了进化稳定策略(Evolution． arilyStableStrategy，缩写为ESS)的概念旧，他指出，如果生物 种群所有个体使用某一策略后。种群中不可能出现使用其它策 略的稳定的群体．那么所有个体使用的这一策略称为进化稳定 的。网络安全的研究目的就是为了保证网络的稳定性和有效 性，传统的安全策略难以适应P2P网络的安全需求。信任是社 会重要的稳定因子．也将是保证未来网络安全的重要思想方 法，进化博弈与稳定策略为研究网络的信任提供了思路。 P2P网络比其它任何网络更能反映出社会网络的各种特 征【131。由此。基于生物学进化论“自然选择”思想，对于P2P网络 信任安全的研究。需要更多地从社会学、经济学和生态学的研 究中借鉴理论基础。而社会网络、生物网络中有许多重要的原 理和机理。如神经网络协同、免疫网络抵御等。可以用来研究网 络节点间的协作进化现象。因此。本文借鉴了社会生态学的生 物进化机理，运用进行博弈论的思想，充分考虑个体间利益关 系与系统网络可能出现的冲突。在保证个体利益的情况下。为 尽可能提高网络系统的整体生态进化，使系统能够长期稳定运 作．提出了基于生态网络的信任博弈进化模型。并在具有服务 突现和进化能力的生物网络仿真平台[14,151上进行了仿真实验。 实验结果验证了模型的可行性和可操作性．并能够实现网络生 态的稳定进化和性能优化。 2 P2P社会生态网络 生态学是研究生物和人与环境之间的相互关系。研究自然 生态系统和人类生态系统的结构和功能的一门学科。生态学的 基本原理既可以应用于生物。也可以应用于人类所从事的各项 生产活动。从社会生态学角度讲，网络的超速发展，将会导致网 络内部各种因素之间以及网络与其它相关社会环境之间出现 一系列问题。所有影响网络发展的其它社会系统构成了网络发 展的生态环境，当用联系发展的眼光分析网络与网络生态环境 之间相互作用、相互影响时．便形成了网络生态。网络与网络生 态环境构成网络生态系统【161。 P2P网络在复杂多样、层次交叠、动态多变环境中，进行信 息、数据、服务之间的交互、转移、生灭，形成了网络系统的动 态、连续、不确定的系统状态。然而长期的、不同形式与过程的 演化发展的结果，使整个系统趋向更高级的有序化发展，自组 织形成一个动态、有机的整体，整个系统通过各节点的交互和 协作解决问题。 假设lP2P网络系统是社会生态网络．其模型可用有向图 PSEnet(p—口))(8> m 要讨论该信任博弈的进化稳定策略。应先找出动态复制方 程的稳定解。 令Fix)=0。可解得三个解： 石l=0 露2—1 茗毒旦二苎 r—d+p—s (9) (10) (11) 上述三个解都有可能是进化稳定策略，但根据微分方程的 “稳定性原理”可知：稳定状态处的函数的导数必须小于0，即 矿(算‘)s、r>d且卜d>p-s，并可得如图2所 示的复制动态方程局部相位图。由此，在网络生态进化中引入 以下机制．就可使信任策略成为网络信任博弈的唯一进化稳定 策略： i1)使s变小或P变大，使p哪增大，即建立相应的惩罚机 制．并加大惩罚力度，使选择不信任策略将是一种风险很大收 益很小的行为。 (2)使r变大或d变小，使r_d增大，即提高选择信任策略 的收益，鼓励和促进信任策略的选择，降低失信的机会收益，使 信任成为一种自动约束机制。 (3)使r—d远大于p-s，这样劫趋向0，初始状态选择信任 策略的概率大于选择不信任策略的概率。 dx 一 山 0 ‘ ／；＼ ＼夕 。1 i x1-旦：! r—d+n—s 图2 网络初始的复制动态微分方程局部相位图 虽说髫l=O在最初状态也是一个稳定解，但随着博弈次数 的增加，网络生态的进化，托逐步退化为石。，此时P(*1．0)>0， x2=l就成为唯一的一个进化稳定策略幽=0就不再是一个稳定 策略。这样系统的性能和稳定性就能得到很好的保证。最终复 制动态方程的局部相位图就会如图3所示。 dx —— m 0 ／／—＼＼．． 1 j 图3 网络进化后的复制动态微分方程局部相位图 因此。只要在网络最初状态同时满足以上三点，信任就会 成为了生态网络进化的唯一稳定策略。 4仿真分析 通过以上分析。将P2P网络假定为社会生态系统，在单种 群的生态系统中，每个节点为一个个的生物个体，它们之间为 生存进行着竞争与合作，选择的策略为信任与不信任。由此，本 文在基于多Agent的生物网络仿真平台上实现了单种群个体 间的信任博弈进化模型．并进行了仿真实验。实验中的博弈参 与方即生态节点为智能Agent，它们的生存能量值为重复博弈 过程中的收益值(19一91。当一个Agent的能量值小于某个阈值(在 实验中设定为O)时，Agent退出生态网络，即为死去。实验中设 置了l000个Agent，进行随机策略选择配对博弈，假定x=0．8， 博弈重复进行了100次，图4和5显示了博弈过程中个体数量 的变化情况。 图4是r=10、s=-4、d=6、p=一l的网络系统进化的速度和稳 定性。图5是r=10、s=一3、d--4、p=一2的网络系统进化的速度和 稳定性．从图中可以看出参数的调整对于系统进化的影响。随 着博弈次数的不断增加，选择不信任策略的Agent在进化博 弈过程中出现了分化，小部分在过程中因能量值小于O而退 出。大部分通过模仿、学习及时调整策略，适应网络生态环 境而存活下来，最后网络生态进化趋于稳定，呈现出优化的 信任网络。 万方数据 刘凤呜，丁永生：基于生态网络的P2P环境信任博弈进化模型 27 图 Agent数量 图5两种策略的Agent的信任博弈进化 5结语 本文借用生态进化机理。将P2P网络假定为社会生态网 络，运用进化博弈和复制动态机制分析了其演化趋向，并进行 单种群即网络单服务的仿真。可以看出．要使网络稳定进化，服 务性能优化，成为一个可信的网络环境．可以通过调整博弈交 互策略的收益值，建立相应的激励和惩罚机制，使节点之间达 到有效合作进化的目的。最终信任策略成为网络稳定进化、安 全服务的有力保障。 本文通过简化信任博弈模型讨论了网络信任安全的有效 性和可行性。在将来的研究工作中，将进一步讨论多种群(多服 务)多策略随机配对进行信任博弈的可行性和可操作性，为网 络的服务优化和整体网络的稳定性提供可参考模型，完善网络 安全的信任机制．为P2P网络的进一步稳定进化和优化服务提 供更为有力的保证。(收稿日期：2007年4月) 参考文献： 【1】BarasJ S，JiangTao．Cooperation。trustandgamesinwirelc6snet— works[C]／／ProoeedingsofSymposiumonSystems，ControlandNet- works，inHonorofVaraiyaP，June2005． 【2】SaroiuS，GummodiPK，GrlbbleS。Ameasurementstudyofpeer- to—peerfilesharingsystems[C]／／MutlimediaComputingandNet- working(MMCN02)，SanJose，CA，2002． 【3】KamvarSD，SchlosserMT，MolinaHG．Theeigentrnstalgorithm forreputationmanagementinP2Pnetworks【C]／／www’03：Pro- ceedingsoftheTwelfthInternationalConferenceonWoddWide Web．【S．1．】：ACMPress，2003：640．65L f4】KamvarSD，SchlosserMT，MolinaHG．EigenRep：reputation managementinP2Pnetworks[C]／／ProccedingsoftheTwelfthIn— ternationalWorldWideWebConference．Budapest：ACMPress。 2003：123-134． (5lXiongL，LiuLAreputation-basedtrustmodelforpeer-to—peer E-commercecommunities[C]／／lEEEConfonE-Commerce(CEC’03)， NewportBeach，California，USA，2003． 【6】StoicsI，MorrisR，Kal曙erD，eta1．Chord：asealablepeer—to-peer lookupserviceforIntemetapplications[C]／／ProeoftheACMSIC．- COMM2001，SanDiego，2001． 【7】AbererK．P-Grid：aself-organizingacce98structureforP2Pinfor- mationsystems[C]／／SixthInternationalConferenceonCooperative InformationSystems，2001． 【8】SztompkaP．Trust：asociologicaltheory[M]．【S．1．】：CambridgeUni， versityPress，1999． 【91MuiL．Computationalmodelsoftrustandreputation：agents。evolu， tionarygRmes，andsocialnetworks[D]．MassachusettsInstituteof Technology，December2002． f10]RigdonML，McCabeKA，SmithVL．Sustainingcooperation·in trustgames[J]．TheEconomicJournal。2007，117(522)：991-1007． 【1l】AlchianA．Uncertainty，evolution，andtheeconomictheory们．‰ JournalofPoliticalEconomy，1995，58(3)：211-221． 【121SmithJ M．Evolutionandthetheoryofgfllnes．Cambridge，1982． U3】ClarkD．Face-to-facewithpeer-to—peernetworking[J]．IEEECorn- puter，2001，34(I)：18-21． 【l4】丁永生，任立红．一种基于免疫突现计算的生物网络结构的设计们． 控制与决策．2003，18(2)：185—189． 【15】任立红，丁永生．一种新颖的基于生态网络计算的网络仿真平台叨． 系统仿真学报，2002，14(11)：1497—1499． 【16】皋磊．基于生态网络的下一代Internet资源动态服务的研究【D】．东 华大学．2005． 【17】MyersonRB．Gametheory：analysisofconflict[M]．Cambridge，Mas- sachusetts：HarvardUniversityPress，1991． 【l8】张向锋，任立红，皋磊，等．生态网络仿真平台的能量服务管理明． 计算机工程与应用，2003，39(31)：145—148． 【19】皋磊。任立红，张向锋，等．基于市场经济的生态网络能量管理服务叨． 系统仿真学报，2004，16(1)：14． (上接20页) 否可以将概率删除和概率克隆量子计算机与纠缠态结合起来 考虑(因为真正的量子计算机里一定存在着量子纠缠态)，也是 一个相当有意义的研究课题。而且是要真正实现量子计算机必 须解决的首要问题。(收稿日期：2007年4月) 参考文献： 【1】WoottersWK，ZurekWH．Asinglequantumcannotbecloned[J]． Nature，1982(299)：802—803． [21FengY，ZhangSY，YingMS．Probabilisticcloninganddeletingof quantumstates[J]．PhysRevA，2002(65)． [3】PatiAK．Quantumsuperpositionofmultipleclonesandthenovel cloningmachine[J】．PhysRevLett，1999(83)：2849—2852． 【4】PatiAK，BraunsteinSL．Impossibilityofdeletinganunknown quantumstate[J]．Nature，2000(404)：164-165． 【5】FengYuan，ZhangSheng—yll，SunXiao-ping．Universaland original—preservingquantumcopyingisimpossible叨．PhysLeftA， 2002：97． 【6】NielsenMA，ChuangI L．Quantumcomputationandquantum information毋1]．Cambridge：CambridgeUniversityPress，2000：354-365。 【7】DuanLM，GuoGC．Prababilisticcloningandidentificationof linearlyindependentstate4J]．PhysRevLettA，1998(22)：4999--5002， 【8】BennettC H，BrassardG，CrepeanC．Teleportinganunknown quantumstateviadtIalclassicalandEPRchannels[J]．PhysRev Lett，1993(70)：1895—1899． 【9】BennettCH，WiesnerSJ．Communicationviaone-andtwo-particle operatorsonEinstein—Podolsky—Rosenstates田．PhysBevLett。1992 (20)：2881—2884． ≥裂 万方数据 基于生态网络的P2P环境信任博弈进化模型 作者： 刘凤鸣， 丁永生， LIU Feng-ming， DING Yong-sheng 作者单位： 刘凤鸣,LIU Feng-ming(东华大学,信息科学与技术学院,上海,201620)， 丁永生,DING Yong-sheng(东华大学,信息科学与技术学院,上海,201620;东华大学,数字化纺织服装技术教 育部工程研究中心,上海,201620) 刊名： 计算机工程与应用 英文刊名： COMPUTER ENGINEERING AND APPLICATIONS 年，卷(期)： 2007,43(23) 被引用次数： 2次 参考文献(19条) 1.Mui L Computational models of trust and reputation:agents,evolutionary games,and social networks 2002 2.丁永生;任立红 一种基于免疫突现计算的生物网络结构的设计[期刊 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 ]-控制与决策 2003(02) 3.Clark D Face-to-face with peer-to-peer networking 2001(01) 4.Smith J M Evolution and the theory of games 1982 5.Alchian A Uncertainty,evolution,and the economic theory[外文期刊] 1995(03) 6.Rigdon M L;McCabe K A;Smith V L Sustaining cooperation-in trust games[外文期刊] 2007(522) 7.Baras J S;Jiang Tao Cooperation,trust and games in wireless networks 2005 8.Sztompka P Trust:a sociological theory 1999 9.Aberer K P-Grid:a self-organizing access structure for P2P information systems 2001 10.Stoica I;Morris R;Karger D Chord:a scalable peer-to-peer lookup service for Internet applications 2001 11.Xiong L;Liu L A reputation-based trust model for peer-to-peer E-commerce communities 2003 12.Kamvar S D;Schlosser M T;Molina H G EigenRep:reputation management in P2P networks 2003 13.Kamvar S D;Schlosser M T;Molina H G The eigentrust algorithm for reputation management in P2P networks 2003 14.Saroiu S;Gummadi P K;Gribble S A measurement study of peer-to-peer file sharing systems[外文会议] 2002 15.皋磊;任立红;张向锋 基于市场经济的生态网络能量管理服务[期刊论文]-系统仿真学报 2004(01) 16.张向锋;任立红;皋磊 生态网络仿真平台的能量服务管理[期刊论文]-计算机工程与应用 2003(31) 17.Myerson R B Game theory:analysis of conflict 1991 18.皋磊 基于生态网络的下一代Internet资源动态服务的研究 2005 19.任立红;丁永生 一种新颖的基于生态网络计算的网络仿真平台[期刊论文]-系统仿真学报 2002(11) 本文读者也读过(10条) 1. 舒尹卓 从信任博弈的角度探讨信任行为及其神经机制[期刊论文]-商业经济2010(17) 2. 谭克虎.姚影 经理人的职业道德问题--基于信任博弈的分析[期刊论文]-经济问题2005(11) 3. 杨国涛.Yang Guotao 信任博弈与订单农业的运行风险防范[期刊论文]-农业科学研究2005,26(3) 4. 陈姣.马君.CHEN Jiao.MA Jun 信任的博弈论分析[期刊论文]-华东经济管理2005,19(4) 5. 邵红李 网格环境下由经济驱动的任务调度策略研究[学位论文]2008 6. 史砚湄.陈东勇.SHI Yan-mei.CHEN Dong-yong 可信赢得、信任给与和信任博弈[期刊论文]-湖北经济学院学报 2008,6(3) 7. 关朝辉.郭荷清.高伟.Guan Chaohui.Guo Heqing.Gao Wei 基于群决策的多Agent资源管理模型[期刊论文]-计算 机应用与软件2009,26(1) 8. 张维迎 信任博弈:叛将与叛军[期刊论文]-三联竞争力2006,50(4) 9. 王慧.付超.赵彬.WANG Hui.FU Chao.ZHAO Bin 网格环境下基于经济模型的开放式决策支持系统资源管理[期刊 论文]-合肥工业大学学报（自然科学版）2008,31(6) 10. 徐武.吴克捷.周卫东.杨印根.XU Wu.WU Ke-jie.ZHOU Wei-dong.YANG Yin-gen 一种基于策略的可扩展网格资 源管理机制[期刊论文]-计算机应用研究2007,24(7) 引证文献(2条) 1.李彦景.范通让.赵永斌 网络生态性研究及证明[期刊论文]-计算机应用研究 2011(9) 2.李征 防范电子商务信用骗取的种群共存模型[期刊论文]-计算机工程与应用 2010(3) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjgcyyy200723008.aspx