网络寻路阶段的合作激励机制探讨

《网络寻路阶段的合作激励机制探讨》由会员分享，可在线阅读，更多相关《网络寻路阶段的合作激励机制探讨（9页珍藏版）》请在装配图网上搜索。

1、Ad hoc 网络寻路阶段的合作激励机制研究黄蕾，刘立祥(中国科学院软件研究所综合信息系统技术国家级重点实验室，北京，100080)摘要： 如何激励属于不同利益最大化实体的自私节点合作是当前 Ad hoc 网络研究中的一个热点问题。 现有的自私节点检测和激励机制主要针对数据传输阶段，不能适应寻路阶段的特点。本文基于邻居节点中 继和生成的路由请求包之间的统计关系，提出了一种适用于按需路由协议寻路阶段的自私行为检测和惩罚 机制，并利用博弈论工具将其建模为噪声环境下的重复囚徒困境博弈， 对算法激励合作的有效性进行分析。 理论分析和仿真结果显示，本算法能够有效地惩罚寻路中的自私行为，促进节点合作。关键

2、词： Ad hoc 网络，路由，自私检测，合作激励，博弈论Study on cooperation stimulation mechanism in route discovery of ad hoc networksHuang Lei, Liu Lixiang(National Key Laboratory of Integrated Information SystemTechnology,Institute of Software, Chinese Academy of Sciences, Beijing , 100080)Abstract : How to stimulate self

3、ish nodes which belong to different utility -maximizing entities to cooperate is a hot topic in adhoc network research community . Current mechanisms proposed sofar focus mainly on detecting selfish behavior and stimulating cooperation in data forwarding stage. They are not applicable in route disco

4、very stage. Based on statistics relationship of route request packets relayed and generated by a neighbor node, this paper proposed an algorithm to detect and punish the selfishness in route discovery stage for on-demand routing protocols . The algorithm was modeled with the tool of game theory as t

5、he repeated prisoner dilemma in noisy environment, and its effectiveness to stimulate cooperation was analyzed with the model . Theoretic analysis and simulation results showed that our scheme could punish the selfishness in route discovery effectively and thus stimulate nodes to cooperate.Keyword :

6、 Ad hoc network , routing , selfishness detection, cooperation stimulation , game theory1 引言Ad hoc 网络由一组移动或固定的无线节点组成， 信息交流等网络关键任务的实现需要各节点之间的相 互协作，这种合作性也是现有诸多路由协议设计的一个基本假设前提。但是当节点属于不同实体时，其合 作性缺乏内在的保证，理性节点更倾向于采取能够使得自身利益最大化的行动，而不是完全遵从协议。由 于无线传输需要耗费大量的能量，因此理性的自私节点会尽量避免为其他节点中继数据，从而导致网络性 能下降，合作用户利益受损。Ad h

7、oc 网络中自私节点的激励机制是当前的一个研究热点， 提出的解决方案可分为三种类型1：基于信用的方法 (credit-based method)，基于声誉的方法 (reputati on- based method),和博弈论方法 (game theory method)。基于信用的方法一般建立在虚拟货币机制的基础上，通过精心设计的支付方式，使得节点只有 在合作的时候才能使自己的利益最大化 2-4。这种方法的缺陷在于作为其基础的虚拟货币管理系统，或者需要抗篡改硬件的支持 2，或者需要集中的支付服务 4 ，尚未有令人满意的解决方案； 基于声誉的方法记 录节点的过往行为，综合直接观察结果和第三方信

8、息形成对节点合作性的判断，对不合作的自私节点以拒 绝服务的方式进行惩罚，从而达到促进合作的目的5-8。目前声誉系统采用基于 Watchdog8的隐式响应或基于 ACK 的显式响应作为监测的主要方式， 19-10 等文献指出现有监测机制的不准确性是声誉系统应用 的主要障碍；博弈激励机制大多建立在针锋相对（TFT） ”策略及其变种的基础上，目前提出的方案多是各节点根据自己数据传输的成功率来调整为网络中其它节点中继分组的概率11-一三 。这类文献重在纳什均衡的证明，使用了较强的假设条件，距离实际应用尚有一段距离。上述文献提出的激励机制大多是针对数据传输阶段节点的自私行为而设计的，一个基本假设是节点在

9、 路由发现阶段采取合作策略，而只在数据传输阶段自私丢包 5811 一三 ，显然这个假设不尽合理。对 于 Ad hoc 网络中通常采用的按需路由来说，节点在寻路阶段的自私行为可以使它免于后续的数据中继任 务， “合法 ”的节省更多的能量，因此节点倾向于在寻路阶段采用自私策略，我们必须考虑相应的检测和合 作激励机制。寻路阶段的自私行为可以分为两大类型：主动篡改路由控制包。当自私节点接收到RREQ （路由请求）、RREP （路由响应）等控制包时，它改变其中一些关键域如 AODV中的跳数、DSR中的中间节点列表， 从而使自己避免出现在源和 目的均为其他节点的路径上，逃避中继任务。这类自私行为的应对方式

10、已经被广泛研究714。被动丢弃。自私节点丢弃所接收到路由控制包，避免成为中继节点。两种类型的路由控制包中， RREP的性质与数据包类似，可采用Watchdog机制检测自私丢弃行为。但是RREQ包为广播包，而且它的传输是有条件的， 存在大量合法丢包， 因此 Watchdog 机制不能有效检测被动丢弃 RREQ 包的自私行为。目前尚未有应对这类自私行为的有效方式。本文主要研究 RREQ丢弃的检测、惩罚和激励机制，因此后续章节所提及的自私行为将主要指RREQ的被动丢弃。虽然 RREQ 的有条件传输和邻居集的不确定性使得基于单个包检测的Watchdog 机制失效，但是，由于每一个RREQ都会被接收到的

11、节点再次广播直到该节点拥有到目的节点的路径或者TTL超时，因此从统计角度来看，合作节点中继的RREQ与返回的RREP之和应该远大于自身所生成的RREQ数。这一点可作为检测被动丢弃的基础。本文提出一种被动丢弃行为的检测和激励机制，基本思想是节点监测过去一段时 间内的邻居中继和生成的 RREQ 数量，如果两者比率超过一定门限，则认为邻居是合作节点，否则认为邻 居是自私节点。节点以一定的概率丢弃来自自私节点的包，作为对自私行为的惩罚，从而激励合作。由于 Ad hoc网络中节点移动模型、业务模型、通信模型等均不相同，包括Watchdog在内的各种检测算法都不可避免的存在一定的误判率，我们的算法也不能例

12、外。我们建立简化的博弈模型对算法进行分析，研究误 判率对合作激励的有效范围的影响。分析结果表明，即使存在一定的误判率，本文算法也能够激励节点达 成合作。最后我们通过仿真对算法进行验证，仿真结果表明本文算法能够对自私节点进行有效的惩罚，从 而激励合作。2 节点寻路阶段自私行为的检测和惩罚算法2.1 基本思想本算法的出发点来自于这样一个观察：由于RREQ的广播本质，对于业务量较均匀的网络来说，从统计上来看，合作节点自身所生成 RREQ数应小于其中继的 RREQ数和响应的RREP数之和。在Ad hoc按需 路由中，节点接收到 RREQ后是否继续广播与 RREQ的内容以及本地路由表有关。例如，如果节点

13、曾经接 收过该RREQ，那么这个包将被丢弃； 如果节点具有到目的地的路径， 这个包也不再前传， 而是生成RREP 返回源节点。因此，一个节点自私与否无法逐包来判断。但是，对按需路由协议来说，当节点有数据要发 送且没有可用路由的时候，必须首先通过RREQ/RREP来建立数据传输路径。这里的 RREQ既可以是节点自己生成的，也可以是中继其他节点的。由于Ad hoc按需路由协议中的寻路都是通过广播实现的，因此节点中继的RREQ数与响应的RREP数之和应大于它自身生成的 RREQ数。后续章节中我们将只考虑相应的 RREQ数量，这是因为除了节点数极少的网络外，RREQ的数量将远大于 RREP。我们通过仿

14、真来验证这个观察。仿真建立在 NS2 的平台上。在 1000m*1000m 的区域内分别随机抛洒30和10个节点，节点位置服从均匀分布。每个节点从剩余节点中随机选择其目的地，每一源-目的对建立一个CBR流，包长度为512字节，两包之间间隔为 1s。采用Random Way Point的随机移动模型。这种模 型中，节点随机移动到某一位置后停顿一段时间再开始新的移动。设节点的移动速度在 1m/s到10m/s之间均匀分布，停顿时间在 10s和50s之间均匀分布。传输模型为TwoRayGround，节点通信半径约为 250m。采用DSR作为路由协议。仿真持续 1000秒。在每个节点的路由 age nt

15、中设置一张表，记录过去200秒内收到的邻居自己生成的RREQ( REQs )和中继的RREQ ( REQr)的数量以及两者的比值手REQr/REQs。为了排除初始阶段不稳定性的影响，我们的统计范围为 REQs1的那些记录。30和10节点场景下E的分布如图1所示。可以看出，两个场景中氏1的记录所占百分比都非常小，10节点场景中约为6% , 30节点场景中约为1%。随着节点数的增加，峰值0 D&CO?所对应的E值也随之增大。图130节点和10节点场景中上述仿真结果证明了我们的观察在均匀业务下是成立的。但是在业务极其不均匀的情况下我们的观察 也可能不成立。例如某一高速移动的节点有大量的数据要发送，在

16、此期间其他所有节点不需要寻路， 这时，该节点的E将小于1。可以看出这种情况的发生概率是比较小的。小概率的误判对合作激励机制的影响我 们将在第3节讨论。2.2 自私检测和惩罚算法用NB来表示邻居节点，用 NB.REQr表示该节点中继的 RREQ数，NB.REQs表示该节点生成的 RREQ 数。为了减少误判，同时提高算法的灵敏度，我们设置两类门限：Thi和Tha、Ths。Thi是初始门限。考虑一个刚刚加入网络的邻居，节点对它的观察是 NB.REQs=NB.REQr=0,不能判定该邻居是否自私，这时它的寻路包应该得到中继。只有在有明确的证据表明该邻居为自私时，才对其进行惩罚。因此当NB.REQsW

17、Thi时，我们认为该邻居处于初始化阶段，不对它进行惩罚。Tha和Ths代表了节点性质的判断门限。当E值小于Tha时，认为节点是自私的，按照概率Thp丢弃来自该节点的路由包作为惩罚。当E值小于Ths时，认为节点是极度自私的，以更严厉的丢弃数据包的方式对节点进行惩罚。这两个门限值的选择与网络拓扑、业 务模型等密切相关，其关系留待下一步工作讨论。检测和惩罚算法如下表所示：On RecvReques( Packet RREQ)OnRecvData (Packet DATA)/* Reverse Route Handling */* Punishment for Selfish Node*/DSrc=R

18、oute-SOURCE-of(DATA);/* Observation */if(DSrc.REQ_sTh_i)now=Scheduler:i nsta nee ().clock ();ratio = DSrc.REQ_r/ DSrc.REQ_sNb= Lasthop-of(RREQ);if(ratio Th_s& Ran dom:u niform(0,1) Th_i)ratio = RSrc.REQ_r/ RSrcREQ_s if(ratioTh_a& Random :uniform(0,1) Ui( D，*)(3)*为C或者D。我们对a, 3,等参数取不同的值，以观察策略促成合作的有效范围

19、。誉与各参数之间的关系如图2所示。图2合作范围与e, p的关系从图2中我们可以观察不同参数对合作范围的影响：S*随着a, 3的比率的增大而降低，其原因是数据成功传输所获得的收益越大，节点就越倾向于 合作。S*随着p的增加而降低，其原因可解释为惩罚越严厉，节点偏离既有策略所获得的收益越小，节 点越倾向于合作S*随着e的增加而增加，当8=0.5时，不论其他参数为何值，节点均不能达成相互合作。其原因是，误判率越大，节点所获得的对手的信息越少，就越倾向于采用安全的自私策略以保证自身利 益的最大化。可以看出，当较小，P较大时，不等式(3)对于大部分3值均成立，系统达到合作的均衡状态。这 说明本算法可有效

20、实现合作激励的功能。4仿真验证我们仍采用2节中的30节点仿真场景对算法进行仿真验证。算法参数选择为Thi=1 , Tha=4, Ths=1和Thp=1。节点的初始能量为5，发送和接收能量配置分别为0.1和0.025，仿真时间设为2000秒。首先我们考察不同自私节点数时算法的表现。设置三种场景，基线场景：所有节点均合作；场景自私节点丢弃 RREQ包，但是没有启用本文算法；场景2:自私节点丢弃 RREQ，但是合作节点启用了本文算法。各场景分别设 3、6、9、12、一五个节点为自私节点。对比自私节点和合作节点在不同场景下的 吞吐量，如下图所示：首札V7点平氏石社量图3不同场景下吞吐量与自私节点数目关

21、系首先观察自私节点吞吐量的变化规律。对比基线场景和场景1的吞吐量变化，可以看出，节点自私丢弃RREQ，逃避中继任务，节省了能量，从而使得自己的吞吐量上升。场景2本文算法启用之后，对自私节点进行有效检测和惩罚，使得自私节点吞吐量大幅度下降，低于其合作状态，因此理性的自私节点将倾 向采用合作策略，从而实现对自私节点的激励。合作节点的吞吐量变化规律与此相反。自私节点丢弃RREQ包使得合作节点需要花费更多的能量中继包，导致自己的吞吐量下降。算法启用后，合作节点不再中继自私节点的包，从而可以节省能量用于中继 合法包。自私节点数目越多，节省的能量越多，吞吐量提高的幅度就越明显。下面我们考虑本文算法对选择性

22、丢包的应对能力。设自私节点数目为 6,即20%的节点自私丢包，丢包概率分别为50%、60%直到100%。两种类型的节点在不同场景下的平均吞吐量如表2所示：表2 :不同场景下不同类型节点的平均吞吐量自私节点 丢包概率场景1:不采用本文算法场景2:采用本文算法合作节点 平均吞吐量（包）自私节点 平均吞吐量（包）合作节点 平均吞吐量（包）自私节点 平均吞吐量（包）100%342.625388.833383.708257.590%350.917330.833374.125294.66780%344.5321.833362.1673 一八70%343.75314.667362.333333.16760%

23、348.167325360.042339.550%344.3753 一五.333363.25348.50 （合作状态）354.708316.667360348.833从上表可以看出，在合作状态，本文算法并不会给网络性能带来负面影响。在场景1本文算法没有启用的时候，自私节点只有在丢包率较高（80% ）时，吞吐量才能得到显著的增加。场景2中合作节点启用本文算法之后，丢包率越大，遭受的惩罚力度越大，自私节点的吞吐量越小。当丢包率大于80%时，其吞吐量远小于合作状态的348.833，因此本文算法激活后，理性节点将选择合作而不是自私丢包，从而实现对自私节点的激励。5相关工作8是Ad hoc网络自私行为检

24、测和激励领域的开创性文献。8关注的是数据传输阶段的自私丢包问题，并提出了后续文献中广泛应用的Watchdog检测方案。Watchdog建立在DSR的基础上，并设定节点工作在混杂侦听模式下。节点发包之后，侦听下一跳节点的通信。如果在设定时间内，没有听到该包被继续传 送到路径上的下一节点，那么认为下一跳节点自私丢包。当节点检测到其下一跳自私丢包的比率超过一定 门限时，它将通知源节点。源节点中的 Pathrater 部件在选择路径时，避开丢包的自私节点。从 Watchdog 的机理中可以看出它并不适合于寻路阶段 RREQ 的丢包检测； 首先， RREQ 是广播包， 链 路层不提供应答，因此节点不能确

25、定此时邻居域内哪些节点接收到RREQ，哪些没有。不能确定需要监测的节点，也就无法对节点是否中继RREQ包做出判断。其次，由于一个RREQ可能被多个节点广播，因此为了降低寻路开销，节点对同一个RREQ只作一次响应，后续收到的重复 RREQ将被丢弃，因此存在大量合法丢包。这两个方面使得 Watchdog 无法用于寻路阶段自私丢包的检测。19 提出了一种基于ACK的自私丢包检测方式2ACK，其核心思想是传输路径上的节点接收到数据包后返回ACK给两跳前的节点，从而可以对中间节点的传输行为进行判定。2ACK方法也建立在DSR的基础上。寻路过程忠节点邻居集未知、存在合法丢包的特点同样使得2ACK不能正常发

26、挥作用：尽管节点收到下两跳的 ACK 时能够确定下一跳节点是合作的；但是没有收到 ACK 时，却不能判定下一跳自私丢包。 因此这种方式也不能用于寻路过程中。20 提出一种基于虚拟支付的紧凑激励机制来促使节点在寻路阶段合作。收到RREQ 后再次广播的节点可以得到小额的支付，对最终构成源目的路径的节点则可以获得大额支付。参与路由越多的节点获得的 支付越多，从而使节点愿意合作。但是 20中只是简单的描述了这种思想，对于支付如何实现、支付的数 量等细节问题均缺乏进一步的说明。6 结论对于采用按需路由的Ad hoc网络来说，自私节点丢弃寻路包从而合法逃避为其他节点中继数据的责任是节约自己能量的最好方式。

27、由于路由控制包的有条件中继模式和邻居的不确定性，这类自私方式很难通 过传统的 Watchdog或基于ACK的方式来检测。本文基于寻路包的统计特性，提出了一种被动丢弃寻路包 的行为检测和惩罚算法，使得自私节点的收益大幅度下降。本文建立博弈模型对算法的有效性进行分析， 结果表明即使存在一定的误判率，我们的算法仍能够促使节点达成合作。仿真结果同样也证明了我们的算 法能够有效惩罚自私节点，从而激励节点合作。参考文献1 .Yoo Y., Agrawal D. P., Why does it pay to be selfish in a MANET? IEEE Wireless Communication

28、s, 2006, 一三 (6): 87-972 .Buttyan L., Hubaux J.-P., Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, 2003, 8(5): 579-5923 .Wang W., EideNBenz S., Wang Y., Li X.-Y ., OURS: Optimal unicast routing systems in non-cooperative wireless networks, Proceed

29、ing of the AnnualInternational Conference on Mobile Computing and Networking(MOBICOM),Los Angeles: ACM Press,2006, 402-4 一三4 .Zhong S., Chen J., Yang R., Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks, Proceedings of INFOCOM, San Francisco:IEEE Press, 2003, 1987-19975

30、.Buchegger S., Boudec J.-Y. L., Performance analysis of the CONFIDANT protocol cooperation of nodes fairness in dynamic ad hoc networks, Source:Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Lausanne: ACM Press, 2002, 226-2366 .Buchegger S., Boudec J.

31、-Y. L., Self-policing mobile ad hoc networks by reputation systems, IEEE Communications Magazine ， 2005, 43(7):101-1077 .He Q., Wu D., Khosl P., A secure incentive architecture for ad-hoc networks, Wireless Communications and Mobile Computing, 2006, 6(3):333-3468 .Marti S., Giuli T.J., Lai K. Baker

32、M., Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the Annual International Conference onMobile Computing and Networking(MOBICOM), Boston: ACM Press, 2000,255-2659 .Huang E., Crowcroft J., Wassell I., Rethinking incentives for mobile ad hoc networks, Proceedings of the ACM

33、SIGCOMM 2004 Workshops, Portland:ACM Press, 2004, 191-19610 . Carruthers R., Nikolaidis I., Certain limitations of reputation -based schemes in mobile environments, Proceedings of the Eighth ACM Symposium onModeling, Analysis and Simulation of Wireless and Mobile Systems, Montreal: ACM Press, 2005,

34、2-1111 . Srinivasan V., Nuggehalli P., Chiasserini C. F., Rao R. R., Cooperation in wireless ad hoc networks, Proceedings of INFOCOM, San Francisco: IEEEPress, 2003, 808-81712 . Milan F., Jaramillo J. J., Srikant R., Achieving cooperation in multihop wireless networks of selfish nodes, Proceedings o

35、f ACM workshop on Gametheory for communications and networks, Pisa: ACM Press, 200613 . Felegyhazi M., Buttyan L., Nash equilibrium of packet forwarding strategies in wireless ad hoc networks, IEEE Transactions on Mobile Computing,2006, 5(5):463-47514 . Zapata M.-G., Asokan N. , Securing ad hoc rout

36、ing protocols, Proceedings of the 3rd Workshop on Wireless Security, New York: ACM Press, 2002, 1-1015 . Newsome J., Shi E., Song D., Perrig A., The Sybil attack in sensor networks: analysis and defenses, Proceedings of International Symposium onInformation Processing in Sensor Networks(IPSN), New Y

37、ork: ACM Press, 2004, 259-26816 . Li R.-D., Li J., Liu P., Chen H.-H., On-demand public-key management for mobile Ad hoc networks, Wireless Communications and Mobile Computing,2006, 6(3): 295-30617 . Urpi A., Bonuccelli M., Giordano S., Modeling cooperation in mobile ad hoc networks: a formal descri

38、ption of selfishness, Proceedings of Modeling andOptimization in Mobile, Ad hoc and Wireless Networks, Sophia-Antipolis: IEEE Press, 200318 . Myerson R. B., Game Theory, Analysis of Conflict, Chinese Economy Press, 200119 . Liu K., Deng J., Varshney P. K., Balakrishnan K., An acknowledgment-based ap

39、proach for the detection of routing misbehavior in MANETs, IEEETransactions on Mobile Computing, 2007, 6(5): 488-50120 . Zhu H.-F, Bao F., Li T.-Y., Compact stimulation mechanism for routing discovery protocols in civilian ad hoc networks, Proceeding of IFIP InternationalFederation for Information P

40、rocessing, 2005, LNCS 3677: 200-209黄蕾，女，1972年生，博士研究生， 高工，研究方向包括 ad hoc网络合 作激励，卫星网络拥塞控制等Hua ng Lei, born in 1972, Ph.D. can didate ， senior engin eer. Her research in terests in clude cooperati on stimulation in ad hoc networks, con gestio n con trol in satellite n etwork, etc.刘立祥，男，1973年生，博士，副研究员，研究

41、方 向包括ad hoc网络、卫星网络路由协议、新型网络 体系结构、网络控制等Liu Lixiang, born in 1973, Ph.D. ，associate researcher. His research in terests in clude ad hoc n etwork, routi ng protocol in satelliten etwork,novel n etworkarchitecture,n etwork con trol, etc.Backgro undMobile ad-hoc n etworks are basically peer to peer multi

42、-hop wireless n etworks. Key n etwork ing tasks must becarried out on the base of mutual cooperati on among these no des. If these no des bel ong to differe nt profit-maximiz ingentities, for example, in a commercial scenario, cooperation assumption doesn t hold. To save the resources sen ergy, a se

43、lfish node may refuse to relay the packets for others.How to stimulate selfish no des to cooperate became a hot spot in ad hoc n etwork research commu nity rece ntly.Curre nt studies proposed a lot of schemes to detect selfish dropp ing in data forward ing stage, such as watchdog or2ACK. But it is e

44、asy to escape the detecti on of these schemes by just sile nt dropp ing con trol packets in route discovery stage. Because of the un certa inty in route discovery, it is hard to detect such kind of selfish ness. This paper proposed a detecti on mecha nism for sile nt dropp ing in route discovery bas

45、ed on the statistics of route con trol packet. Authors proved the effective ness of the proposed algorithm to stimulate cooperati on with the tools of game theory and by simulatio n.This research is partially supported by the adva need research foun dati on of Chin ese Academy of Scie nces un der grant 9140A 一五 0301.第一作者联系方式：x 一三 621230920Email: huangleiffxyahooxx100080通信地址：北京中关村南四街四号软件所通用软件实验室