Adhoc网络寻路阶段的合作激励机制研究黄蕾，刘立祥（中国科学院软件研究所综合信息系统技术国家级重点实验室，北京，100080）摘要：如何激励属于不同利益最大化实体的自私节点合作是当前Adhoc网络研究中的一个热点问题。现有的自私节点检测和激励机制主要针对数据传输阶段，不能适应寻路阶段的特点。本文基于邻居节点中继和生成的路由请求包之间的统计关系，提出了一种适用于按需路由协议寻路阶段的自私行为检测和惩罚机制，并利用博弈论工具将其建模为噪声环境下的重复囚徒困境博弈，对算法激励合作的有效性进行分析。理论分析和仿真结果显示，本算法能够有效地惩罚寻路中的自私行为，促进节点合作。关键词：Adhoc网络，路由，自私检测，合作激励，博弈论StudyoncooperationstimulationmechanisminroutediscoveryofadhocnetworksHuangLei,LiuLixiang(NationalKeyLaboratoryofIntegratedInformationSystemTechnology,InstituteofSoftware,ChineseAcademyofSciences,Beijing,100080)Abstract:Howtostimulateselfishnodeswhichbelongtodifferentutility-maximizingentitiestocooperateisahottopicinadhocnetworkresearchcommunity.Currentmechanismsproposedsofarfocusmainlyondetectingselfishbehaviorandstimulatingcooperationindataforwardingstage.Theyarenotapplicableinroutediscoverystage.Basedonstatisticsrelationshipofrouterequestpacketsrelayedandgeneratedbyaneighbornode,thispaperproposedanalgorithmtodetectandpunishtheselfishnessinroutediscoverystageforon-demandroutingprotocols.Thealgorithmwasmodeledwiththetoolofgametheoryastherepeatedprisonerdilemmainnoisyenvironment,anditseffectivenesstostimulatecooperationwasanalyzedwiththemodel.Theoreticanalysisandsimulationresultsshowedthatourschemecouldpunishtheselfishnessinroutediscoveryeffectivelyandthusstimulatenodestocooperate.Keyword:Adhocnetwork,routing,selfishnessdetection,cooperationstimulation,gametheory1引言Adhoc网络由一组移动或固定的无线节点组成，信息交流等网络关键任务的实现需要各节点之间的相互协作，这种合作性也是现有诸多路由协议设计的一个基本假设前提。但是当节点属于不同实体时，其合作性缺乏内在的保证，理性节点更倾向于采取能够使得自身利益最大化的行动，而不是完全遵从协议。由于无线传输需要耗费大量的能量，因此理性的自私节点会尽量避免为其他节点中继数据，从而导致网络性能下降，合作用户利益受损。Adhoc网络中自私节点的激励机制是当前的一个研究热点，提出的解决方案可分为三种类型[1]：基于信用的方法（credit-basedmethod），基于声誉的方法（reputation-basedmethod），和博弈论方法（gametheorymethod）。基于信用的方法一般建立在虚拟货币机制的基础上，通过精心设计的支付方式，使得节点只有在合作的时候才能使自己的利益最大化[2-4]。这种方法的缺陷在于作为其基础的虚拟货币管理系统，或者需要抗篡改硬件的支持[2]，或者需要集中的支付服务[4]，尚未有令人满意的解决方案；基于声誉的方法记录节点的过往行为，综合直接观察结果和第三方信息形成对节点合作性的判断，对不合作的自私节点以拒绝服务的方式进行惩罚，从而达到促进合作的目的[5-8]。目前声誉系统采用基于Watchdog[8]的隐式响应或基于ACK的显式响应作为监测的主要方式，[1][9-10]等文献指出现有监测机制的不准确性是声誉系统应用的主要障碍；博弈激励机制大多建立在“针锋相对（TFT）”策略及其变种的基础上，目前提出的方案多是各节点根据自己数据传输的成功率来调整为网络中其它节点中继分组的概率[11-13]。这类文献重在纳什均衡的证明，使用了较强的假设条件，距离实际应用尚有一段距离。上述文献提出的激励机制大多是针对数据传输阶段节点的自私行为而设计的，一个基本假设是节点在路由发现阶段采取合作策略，而只在数据传输阶段自私丢包[5][8][11][13]，显然这个假设不尽合理。对于Adhoc网络中通常采用的按需路由来说，节点在寻路阶段的自私行为可以使它免于后续的...
