《网络寻路阶段的合作激励机制探讨.doc》由会员分享，可在线阅读，更多相关《网络寻路阶段的合作激励机制探讨.doc（10页珍藏版）》请在金锄头文库上搜索。
1、Ad hoc网络寻路阶段的合作激励机制研究黄蕾，刘立祥（中国科学院软件研究所综合信息系统技术国家级重点实验室，北京，）摘要：如何激励属于不同利益最大化实体的自私节点合作是当前Ad hoc网络研究中的一个热点问题。现有的自私节点检测和激励机制主要针对数据传输阶段，不能适应寻路阶段的特点。本文基于邻居节点中继和生成的路由请求包之间的统计关系，提出了一种适用于按需路由协议寻路阶段的自私行为检测和惩罚机制，并利用博弈论工具将其建模为噪声环境下的重复囚徒困境博弈，对算法激励合作的有效性进行分析。理论分析和仿真结果显示，本算法能够有效地惩罚寻路中的自私行为，促进节点合作。关键词：Ad hoc网络，路由，自
2、私检测，合作激励，博弈论Study on cooperation stimulation mechanism in route discovery of ad hoc networksHuang Lei, Liu Lixiang(National Key Laboratory of Integrated Information System Technology, Institute of Software, Chinese Academy of Sciences, Beijing, )Abstract: How to stimulate selfish nodes which belong
3、to different utility-maximizing entities to cooperate is a hot topic in ad hoc network research community. Current mechanisms proposed so far focus mainly on detecting selfish behavior and stimulating cooperation in data forwarding stage. They are not applicable in route discovery stage. Based on st
4、atistics 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 the repeated prisoner dil
5、emma 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: Ad hoc network, routing,
6、selfishness detection, cooperation stimulation, game theory1 引言Ad hoc网络由一组移动或固定的无线节点组成，信息交流等网络关键任务的实现需要各节点之间的相互协作，这种合作性也是现有诸多路由协议设计的一个基本假设前提。但是当节点属于不同实体时，其合作性缺乏内在的保证，理性节点更倾向于采取能够使得自身利益最大化的行动，而不是完全遵从协议。由于无线传输需要耗费大量的能量，因此理性的自私节点会尽量避免为其他节点中继数据，从而导致网络性能下降，合作用户利益受损。Ad hoc网络中自私节点的激励机制是当前的一个研究热点，提出的解决方案可分为
7、三种类型1：基于信用的方法（credit-based method），基于声誉的方法（reputation-based method），和博弈论方法（game theory method）。基于信用的方法一般建立在虚拟货币机制的基础上，通过精心设计的支付方式，使得节点只有在合作的时候才能使自己的利益最大化2-4。这种方法的缺陷在于作为其基础的虚拟货币管理系统，或者需要抗篡改硬件的支持2，或者需要集中的支付服务4，尚未有令人满意的解决方案；基于声誉的方法记录节点的过往行为，综合直接观察结果和第三方信息形成对节点合作性的判断，对不合作的自私节点以拒绝服务的方式进行惩罚，从而达到促进合作的目的5-8
8、。目前声誉系统采用基于Watchdog8的隐式响应或基于ACK的显式响应作为监测的主要方式，19-10等文献指出现有监测机制的不准确性是声誉系统应用的主要障碍；博弈激励机制大多建立在 “针锋相对（TFT）”策略及其变种的基础上，目前提出的方案多是各节点根据自己数据传输的成功率来调整为网络中其它节点中继分组的概率11-13。这类文献重在纳什均衡的证明，使用了较强的假设条件，距离实际应用尚有一段距离。上述文献提出的激励机制大多是针对数据传输阶段节点的自私行为而设计的，一个基本假设是节点在路由发现阶段采取合作策略，而只在数据传输阶段自私丢包581113，显然这个假设不尽合理。对于Ad hoc网络中通
9、常采用的按需路由来说，节点在寻路阶段的自私行为可以使它免于后续的数据中继任务，“合法”的节省更多的能量，因此节点倾向于在寻路阶段采用自私策略，我们必须考虑相应的检测和合作激励机制。寻路阶段的自私行为可以分为两大类型：l 主动篡改路由控制包。当自私节点接收到RREQ（路由请求）、RREP（路由响应）等控制包时，它改变其中一些关键域如AODV中的跳数、DSR中的中间节点列表，从而使自己避免出现在源和目的均为其他节点的路径上，逃避中继任务。这类自私行为的应对方式已经被广泛研究714。l 被动丢弃。自私节点丢弃所接收到路由控制包，避免成为中继节点。两种类型的路由控制包中，RREP的性质与数据包类似，可
10、采用Watchdog机制检测自私丢弃行为。但是RREQ包为广播包，而且它的传输是有条件的，存在大量合法丢包，因此Watchdog机制不能有效检测被动丢弃RREQ包的自私行为。目前尚未有应对这类自私行为的有效方式。本文主要研究RREQ丢弃的检测、惩罚和激励机制，因此后续章节所提及的自私行为将主要指RREQ的被动丢弃。虽然RREQ的有条件传输和邻居集的不确定性使得基于单个包检测的Watchdog机制失效，但是，由于每一个RREQ都会被接收到的节点再次广播直到该节点拥有到目的节点的路径或者TTL超时，因此从统计角度来看，合作节点中继的RREQ与返回的RREP之和应该远大于自身所生成的RREQ数。这一
11、点可作为检测被动丢弃的基础。本文提出一种被动丢弃行为的检测和激励机制，基本思想是节点监测过去一段时间内的邻居中继和生成的RREQ数量，如果两者比率超过一定门限，则认为邻居是合作节点，否则认为邻居是自私节点。节点以一定的概率丢弃来自自私节点的包，作为对自私行为的惩罚，从而激励合作。由于Ad hoc网络中节点移动模型、业务模型、通信模型等均不相同，包括Watchdog在内的各种检测算法都不可避免的存在一定的误判率，我们的算法也不能例外。我们建立简化的博弈模型对算法进行分析，研究误判率对合作激励的有效范围的影响。分析结果表明，即使存在一定的误判率，本文算法也能够激励节点达成合作。最后我们通过仿真对算
12、法进行验证，仿真结果表明本文算法能够对自私节点进行有效的惩罚，从而激励合作。 2 节点寻路阶段自私行为的检测和惩罚算法2.1 基本思想本算法的出发点来自于这样一个观察：由于RREQ的广播本质，对于业务量较均匀的网络来说，从统计上来看，合作节点自身所生成RREQ数应小于其中继的RREQ数和响应的RREP数之和。在Ad hoc按需路由中，节点接收到RREQ后是否继续广播与RREQ的内容以及本地路由表有关。例如，如果节点曾经接收过该RREQ，那么这个包将被丢弃；如果节点具有到目的地的路径，这个包也不再前传，而是生成RREP返回源节点。因此，一个节点自私与否无法逐包来判断。但是，对按需路由协议来说，当
13、节点有数据要发送且没有可用路由的时候，必须首先通过RREQ/RREP来建立数据传输路径。这里的RREQ既可以是节点自己生成的，也可以是中继其他节点的。由于Ad hoc按需路由协议中的寻路都是通过广播实现的，因此节点中继的RREQ数与响应的RREP数之和应大于它自身生成的RREQ数。后续章节中我们将只考虑相应的RREQ数量，这是因为除了节点数极少的网络外，RREQ的数量将远大于RREP。我们通过仿真来验证这个观察。仿真建立在NS2的平台上。在1000m*1000m的区域内分别随机抛洒30和10 个节点，节点位置服从均匀分布。每个节点从剩余节点中随机选择其目的地，每一源-目的对建立一个CBR流，包
14、长度为512字节，两包之间间隔为1s。采用Random Way Point的随机移动模型。这种模型中，节点随机移动到某一位置后停顿一段时间再开始新的移动。设节点的移动速度在1m/s到10m/s之间均匀分布，停顿时间在10s和50s之间均匀分布。传输模型为TwoRayGround，节点通信半径约为250m。采用DSR作为路由协议。仿真持续1000秒。在每个节点的路由agent中设置一张表，记录过去200秒内收到的邻居自己生成的RREQ（REQs）和中继的RREQ（REQr）的数量以及两者的比值=REQr/REQs。为了排除初始阶段不稳定性的影响，我们的统计范围为REQs1的那些记录。30和10节
15、点场景下的分布如图1所示。可以看出，两个场景中1的记录所占百分比都非常小，10节点场景中约为6%，30节点场景中约为1%。随着节点数的增加，峰值所对应的值也随之增大。图1 30节点和10节点场景中的分布情况上述仿真结果证明了我们的观察在均匀业务下是成立的。但是在业务极其不均匀的情况下我们的观察也可能不成立。例如某一高速移动的节点有大量的数据要发送，在此期间其他所有节点不需要寻路，这时，该节点的将小于1。可以看出这种情况的发生概率是比较小的。小概率的误判对合作激励机制的影响我们将在第3节讨论。2.2 自私检测和惩罚算法用NB来表示邻居节点，用NB.REQr表示该节点中继的RREQ数，NB.REQ
16、s表示该节点生成的RREQ数。为了减少误判，同时提高算法的灵敏度，我们设置两类门限：Thi和Tha、Ths。Thi是初始门限。考虑一个刚刚加入网络的邻居，节点对它的观察是NB.REQs=NB.REQr=0，不能判定该邻居是否自私，这时它的寻路包应该得到中继。只有在有明确的证据表明该邻居为自私时，才对其进行惩罚。因此当NB.REQsThi时，我们认为该邻居处于初始化阶段，不对它进行惩罚。Tha和Ths代表了节点性质的判断门限。当值小于Tha时，认为节点是自私的，按照概率Thp丢弃来自该节点的路由包作为惩罚。当值小于Ths时，认为节点是极度自私的，以更严厉的丢弃数据包的方式对节点进行惩罚。这两个门限值的选择与网络拓扑、业务模型等密切相关，其关系留待下一步工作讨论。检测和惩罚算法如下表所示：OnRecvRequest(Packet RREQ)OnRecvD
