《Ad hoc网络寻路阶段的合作激励机制研究》由会员分享，可在线阅读，更多相关《Ad hoc网络寻路阶段的合作激励机制研究（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 System Technology, Institute of Software, Chinese Academy of Sciences, Beijing, 100080) Abstrac
3、t: How to stimulate selfish nodes which belong 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 a
4、pplicable in route discovery 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
5、tool of game theory as the 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
6、 to cooperate. Keyword: Ad hoc network, routing, selfishness detection, cooperation stimulation, game theory1引言引言Ad hoc 网络由一组移动或固定的无线节点组成，信息交流等网络关键任务的实现需要各节点之间的 相互协作，这种合作性也是现有诸多路由协议设计的一个基本假设前提。但是当节点属于不同实体时， 其合作性缺乏内在的保证，理性节点更倾向于采取能够使得自身利益最大化的行动，而不是完全遵从协 议。由于无线传输需要耗费大量的能量，因此理性的自私节点会尽量避免为其他节点中继数据，从而导 致
7、网络性能下降，合作用户利益受损。 Ad hoc 网络中自私节点的激励机制是当前的一个研究热点，提出的解决方案可分为三种类型1：基 于信用的方法（credit-based method） ，基于声誉的方法（reputation-based method） ，和博弈论方法（game theory method） 。基于信用的方法一般建立在虚拟货币机制的基础上，通过精心设计的支付方式，使得节 点只有在合作的时候才能使自己的利益最大化2-4。这种方法的缺陷在于作为其基础的虚拟货币管理系 统，或者需要抗篡改硬件的支持2，或者需要集中的支付服务4，尚未有令人满意的解决方案；基于声 誉的方法记录节点的过往行
8、为，综合直接观察结果和第三方信息形成对节点合作性的判断，对不合作的 自私节点以拒绝服务的方式进行惩罚，从而达到促进合作的目的5-8。目前声誉系统采用基于 Watchdog8的隐式响应或基于 ACK 的显式响应作为监测的主要方式，19-10等文献指出现有监测机制 的不准确性是声誉系统应用的主要障碍；博弈激励机制大多建立在 “针锋相对（TFT） ”策略及其变种的基 础上，目前提出的方案多是各节点根据自己数据传输的成功率来调整为网络中其它节点中继分组的概率 11-13。这类文献重在纳什均衡的证明，使用了较强的假设条件，距离实际应用尚有一段距离。 上述文献提出的激励机制大多是针对数据传输阶段节点的自私
9、行为而设计的，一个基本假设是节点在路由发现阶段采取合作策略，而只在数据传输阶段自私丢包581113，显然这个假设不尽合理。对 于 Ad hoc 网络中通常采用的按需路由来说，节点在寻路阶段的自私行为可以使它免于后续的数据中继任 务， “合法”的节省更多的能量，因此节点倾向于在寻路阶段采用自私策略，我们必须考虑相应的检测和合 作激励机制。寻路阶段的自私行为可以分为两大类型：主动篡改路由控制包。当自私节点接收到 RREQ（路由请求） 、RREP（路由响应）等控制包时， 它改变其中一些关键域如 AODV 中的跳数、DSR 中的中间节点列表，从而使自己避免出现在源 和目的均为其他节点的路径上，逃避中继
10、任务。这类自私行为的应对方式已经被广泛研究714。被动丢弃。自私节点丢弃所接收到路由控制包，避免成为中继节点。两种类型的路由控制包中， RREP 的性质与数据包类似，可采用 Watchdog 机制检测自私丢弃行为。但是 RREQ 包为广播包， 而且它的传输是有条件的，存在大量合法丢包，因此 Watchdog 机制不能有效检测被动丢弃 RREQ 包的自私行为。目前尚未有应对这类自私行为的有效方式。 本文主要研究 RREQ 丢弃的检测、惩罚和激励机制，因此后续章节所提及的自私行为将主要指 RREQ 的被动丢弃。 虽然 RREQ 的有条件传输和邻居集的不确定性使得基于单个包检测的 Watchdog
11、机制失效，但是，由 于每一个 RREQ 都会被接收到的节点再次广播直到该节点拥有到目的节点的路径或者 TTL 超时，因此从 统计角度来看，合作节点中继的 RREQ 与返回的 RREP 之和应该远大于自身所生成的 RREQ 数。这一点 可作为检测被动丢弃的基础。本文提出一种被动丢弃行为的检测和激励机制，基本思想是节点监测过去 一段时间内的邻居中继和生成的 RREQ 数量，如果两者比率超过一定门限，则认为邻居是合作节点，否 则认为邻居是自私节点。节点以一定的概率丢弃来自自私节点的包，作为对自私行为的惩罚，从而激励 合作。由于 Ad hoc 网络中节点移动模型、业务模型、通信模型等均不相同，包括 W
12、atchdog 在内的各种检 测算法都不可避免的存在一定的误判率，我们的算法也不能例外。我们建立简化的博弈模型对算法进行 分析，研究误判率对合作激励的有效范围的影响。分析结果表明，即使存在一定的误判率，本文算法也 能够激励节点达成合作。最后我们通过仿真对算法进行验证，仿真结果表明本文算法能够对自私节点进 行有效的惩罚，从而激励合作。 2节点寻路阶段自私行为的检测和惩罚算法节点寻路阶段自私行为的检测和惩罚算法2.1基本思想基本思想本算法的出发点来自于这样一个观察：由于 RREQ 的广播本质，对于业务量较均匀的网络来说，从 统计上来看，合作节点自身所生成 RREQ 数应小于其中继的 RREQ 数和
13、响应的 RREP 数之和。在 Ad hoc 按需路由中，节点接收到 RREQ 后是否继续广播与 RREQ 的内容以及本地路由表有关。例如，如果节点 曾经接收过该 RREQ，那么这个包将被丢弃；如果节点具有到目的地的路径，这个包也不再前传，而是生 成 RREP 返回源节点。因此，一个节点自私与否无法逐包来判断。但是，对按需路由协议来说，当节点 有数据要发送且没有可用路由的时候，必须首先通过 RREQ/RREP 来建立数据传输路径。这里的 RREQ 既 可以是节点自己生成的，也可以是中继其他节点的。由于 Ad hoc 按需路由协议中的寻路都是通过广播实 现的，因此节点中继的 RREQ 数与响应的
14、RREP 数之和应大于它自身生成的 RREQ 数。后续章节中我们 将只考虑相应的 RREQ 数量，这是因为除了节点数极少的网络外，RREQ 的数量将远大于 RREP。 我们通过仿真来验证这个观察。仿真建立在 NS2 的平台上。在 1000m*1000m 的区域内分别随机抛洒 30 和 10 个节点，节点位置服从均匀分布。每个节点从剩余节点中随机选择其目的地，每一源-目的对建 立一个 CBR 流，包长度为 512 字节，两包之间间隔为 1s。采用 Random Way Point 的随机移动模型。这种 模型中，节点随机移动到某一位置后停顿一段时间再开始新的移动。设节点的移动速度在 1m/s 到
15、10m/s 之间均匀分布，停顿时间在 10s 和 50s 之间均匀分布。传输模型为 TwoRayGround，节点通信半径约为 250m。采用 DSR 作为路由协议。仿真持续 1000 秒。 在每个节点的路由 agent 中设置一张表，记录过去 200 秒内收到的邻居自己生成的 RREQ（REQs）和中继的 RREQ（REQr）的数量以及两者的比值 =REQr/REQs。为了排除初始阶段不稳定性的影响，我们 的统计范围为 REQs1 的那些记录。30 和 10 节点场景下 的分布如图 1 所示。可以看出，两个场景中 Th_i)ratio= RSrc.REQ_r/ RSrc.REQ_sif(ra
16、tioTh_i)ratio= DSrc.REQ_r/ DSrc.REQ_sif(ratio Tha，该包得到正常处理，如果 Ui（D，*）(3) *为 C 或者 D。我们对 ，p 等参数取不同的值，以观察策略促成合作的有效范围。*与各参 数之间的关系如图 2 所示。图 2 合作范围与 ，p 的关系从图 2 中我们可以观察不同参数对合作范围的影响： *随着 ， 的比率的增大而降低，其原因是数据成功传输所获得的收益越大，节点就越倾向于 合作。 *随着 p 的增加而降低，其原因可解释为惩罚越严厉，节点偏离既有策略所获得的收益越小， 节点越倾向于合作 *随着 的增加而增加，当 =0.5 时，不论其他参数为何值，节点均不能达成相互合作。其原因 是，误判率越大，节点所获得的对手的信息越少，就越倾向于采用安全的自私策略以保证自身 利益的最大化。 可以看出，当 较小，p 较大时，不等式（3）对于大部分 值均成立，系统达到合作的均衡状态。 这说明本算法可有效实现合作
