基于信誉值的ad hoc网络节点自私类型检测

谭冕 戴昊峰 张晖 宋波

摘要：在ad hoc网络中，节点间的合作是一个重要的问题，不相邻节点的信息传递只能依靠中间节点的转发来完成，若中间节点存在自私行为则会较大地影响网络的性能。节点自私类型有不同，对网络功能造成的影响也各不一样，有些自私节点在一定数量上对网络整体性能影响不大，可以容忍；而有些自私节点则必须得采取强硬的惩戒措施，将其驱逐出网络或降低它的信誉值并公布。该文采用基于信誉值的算法检测出ad hoc网络中的问题节点，并对其进行类型定义，仿真查看其对网络性能的影响，方便下一步根据不同自私节点进行机制设计。

关键词： ad hoc网络；信誉值；节点自私类型

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）28-6622-05

随着军事技术的不断发展，新型武器、作战手段和作战理论等不断涌现。如何将众多武器设备之间相连和与指挥机构相连，以及对战场信息是否能够准确、有效地进行交流，是未来战争输赢的关键因素。因此，战场情景下的组网技术研究成为各国军队研究与发展的重点。无线ad hoc网络正是在这种趋势下产生的。Ad hoc网络是分布式的，没有中心控制节点，因此节点与它覆盖范围外的节点想要完成通信，就必须通过中继节点的转发来实现[1]。节点在网络有可能充当三种身份：源节点、中继节点和目的节点。在ad hoc网络中每个正常节点的能量、存储空间、处理能力、传输带宽都是有限的，假设它们都是理性的，在考虑转发任务的时候，尤其是当有单个节点的损耗和整个网络能耗的冲突时，就会产生一定的自私性，所以参与路由服务，同时会根据自己能量的損耗来决定是否参加中继转发任务[2]。人们还发现在ad hoc网络中还有恶意节点的存在，和其它善于伪装成正常节点来参与路由的节点，这些都对ad hoc网络造成一定威胁，因为它们会降低网络吞吐量，增加丢包率等，严重的时候甚至会导致整个ad hoc网络的崩溃[3]。

1 Ad hoc网络节点自私行为研究

由于ad hoc网络的合作需要通过节点来完成，故而网络性能的好坏很大程度取决于节点的行为，而通常节点可分为两种，一种是正常节点：具有较好的合作性，愿意无私地转发数据；另一种是存在问题的不正常节点，它往往会对网络性能造成一定的负面影响。

在本文中，存在问题的节点由于其具体自私行为不同，为方便表述，所以将问题节点分为恶意节点和两种自私节点。恶意节点：通过路由，传递虚假的信息给目的节点。自私节点：第一类为只参加路由服务，但是却从来不参加数据的转发，以此尽可能的提高节点生存时间。第二类为受到自身的能量限制，所以会根据具体的能量消耗情况考虑是否参加网络活动。

文献[4]提出一种基于退避窗口问题的解决方法。在此种方法中，接受节点用CTS或ACK帧通过界定退避值，发送给源节点。同时，这种方法具有可扩展性，可以用于ad hoc网络检测节点是否存在自私行为，并进行数据分析。这种方法主要是将实际退避值、连续退避值等数据与某个门限值比较，以判断节点是否更改退避窗口大小而取得高效益。

文献[5]提出一种通过诊断机制和惩罚机制，并且以更改MAC协议，且在帧内增加BOV数据，以此来判断节点是否存在自私行为，并解决移动自组网中MAC层存在的节点自私行为问题。

在基于信誉的机制中，当节点能够正确地转发数据包的时候，信誉值增加，如果节点信誉值比设定的门限值低时，就认为该节点为自私节点。文献[3]就提出了Watchdog和Pathrater模型，Watchdog的作用主要用于检测节点是否存在不良行为。Watchdog通过侦听下一条节点是否将数据包转发出去，以此确定行为异常的节点，并提供给Pathrater。而Pathrater则在选择路径的时候尽可能地规避那些异常节点，从而找到较好的路径。虽然它并没有惩戒异常节点，但在一定程度也减轻了网络负担。在之后的信誉机制设计中，普遍采用了该算法的思路。

文献[6]提出一种估算网络发生碰撞的平均概率的检测方法，并计算出帧经过几次重传到最后的发送成功，此算法较上述算法更加复杂；而且在具体的ad hoc网络中的捕获效应普遍存在，故它的实际应用性并不高。

文献[7]CONFIDANT机制是按需路由协议的扩展，其目的是为了检测并孤立那些有不良行为的问题节点，通过这样来达到节点间的合作。此机制下每个节点都拥有四个模块：检测器、信任管理、声誉系统及路径管理。这四个模块共同完成路由信息的提供和处理。

本文参考了Watchdog模型，采用AODV路由协议，通过侦听邻居节点的行为，并基于信誉值来检测出问题节点，用“自私节点发送率”与信誉值共同判断出其类型。最后仿真并查看各种类型的问题节点在“丢包率”、“网络吞吐量”的数据上的表现，得出一些适用的结论。

2 系统模型

图1为检测并分类当前ad hoc网络存在的各种问题节点时生成的场景图既模型图。假设一个ad hoc网络中，共存在100个节点，这100个节点随机生成正常节点，自私节点类型一，自私节点类型二，恶意节点若干，记录下各类节点的数目。图2、图3、图4是在当前网络共存在100个节点，分别为恶意节点数为4、第一类自私节点数为6、第二类自私节点数为10的系统模型图，也就是在实验过程中，随着各种类型的问题节点数目的变化，系统都会生成相应的模型既场景图，可以看出这些问题节点是随机生成并分布在当前ad hoc网络。在当前图1的场景图中，随机选定一个节点作为源节点，当中继节点为正常节点的时候，它会无条件的转发该数据包；当中继节点是恶意节点的时候，它会接受这个数据包，但是会篡改其目的节点的位置，再将其发送出去；当中继节点是自私节点类型一的时候，它会接受这个数据包，但是会直接将其丢弃，以此来节约有限的能量，尽可能地提高自己的生存时间；当中继节点是自私类型二的时候，它会根据当前剩余的能量来判断是否转发数据，如果当前的能量大于门阀值，就会转发该数据包，如果当前的能量小于门阀值，它就会丢弃这个数据包。根据上面各种节点不同的表现，每当该节点没有转发这个数据包，其信誉值就会在基础值上面递减，一旦信誉值在0值以下，就可以判断其为问题节点。然后再根据各自类型的问题节点在具体行为上的不同，可以得到它们的自私节点发送率，再判断出是哪种类型的问题节点。

3 自私類型检测算法

算法共分两个部分：一部分是要验证类型检测是否正确，一部分是要知道丢包率、网络吞吐量与各类问题在节点数目上的关系。

算法的检测部分：随机选定一个源节点a，探测并得到它的邻居节点数目（节点的初始信誉值都为1） 。然后，源节点传递RREQ（路由请求）数据。若源节点的某一相邻节点c无转发，则c的信誉值相对于源节点a（-1） 。一个周期后，a再次发送RREQ数据，c仍无转发，则认为c的信誉值过低，判定c为问题节点。遍历所有节点后，但凡是信誉值小于0的，都为问题节点。此时，以问题节点为目标节点，进行“自私节点发送率”的检测，结合信誉值进行比较，就能得出问题节点的具体类型，并对其计数。最后，得到各种类型节点的数值，与之前记录的节点数值对比，是否相同，若相同则算法的检测部分得证。算法的另一部分是通过仿真查看各种不同数目的问题节点在检测数据上的表现，并不断变换各个类型问题节点的实际存在数目，并生成当前的场景图。

以下是本文中关于“丢包率”，“网络吞吐量”和“自私节点发送率”的定义。

节点通过对相邻节点的信誉值的评定，可以得知是否存在问题节点。而当节点存在自私行为的时候，会对网络造成不良影响，而恶意节点则相对于其它节点，表现的只为降低网络性能的相关数据，比如降低周围节点的吞吐量，提升丢包率等行为。算法中的多次检测，也让算法具有一定的容错率[8]。

图5为算法检测部分的流程图，对所有节点而言，其判决如下：当信誉值不小于0的时候，为正常节点；当信誉值小于0且自私节点发送率等于1的时候，为恶意节点；当信誉值小于0且自私节点发送率等于0，为第一类自私节点；当信誉值小于0且自私节点发送率大于0小于1，为第二类自私节点，最后统计各类问题节点的数量。

图6为算法统计部分的流程图，它简单的描述了算法，通过一个判决框比较数据量。假设当前测试数据tt为0，算法随机产生起始节点和目的节点，并记录下成功传输的数据和丢失的数据，不断更新。直到TT在数值上小于tt，这时再统计“丢包率”、“网络吞吐量”，查看各种问题节点在不同数量下对网络性能的影响。

4 仿真分析

基于信誉值的ad hoc网络节点自私类型检测算法是在ad hoc网络中，以AODV路由协议[9]为基础的matlab程序。在已知各种类型节点数目的前提下，再用信誉值和自私节点发送率这两个数据来检测出问题节点，并进行具体分类。第二部分的仿真主要是从丢包率和网络吞吐量这两个数据来测试三种不同的问题节点对当前ad hoc网络性能的影响。

图7为节点类型的检测结果，它表明当ad hoc网络的恶意节点、第一类型自私节点、第二类自私节点数目都为10且如图1所示分布，通过算法的检测部分，成功得到了三种类型问题节点各自正确的数量。

从图8可以看出，三大类型问题节点随着各自节点数目的增加，丢包率也是随之增加。第一类自私节点和第二类自私节点在丢包率上的整体变化趋势是类似的，第一类自私节点略高于第二类自私节点。两类节点在数量小于6的时候，它们的丢包率较小，说明网络并未受到较大影响，可以包容这些问题节点。而恶意节点则在丢包率上表现的较为突出，普遍高于前两者，说明存在直接丢弃数据包的可能性。图9中的三大类型问题节点随着各自节点数目的增加，网络吞吐量也随之递减，尤其是恶意节点，几乎不传输数据，此时问题节点存在比例较大，影响了当前网络的整体性能。在这三种问题节点中，恶意节点的吞吐量比其它自私节点小且丢包率也高，所以它是这三种类型节点中影响网络最大的问题节点。

5 结束语

在ad hoc网络中，网络的通信主要是依赖于节点之间的合作。由于各种资源的限制，节点往往是缺乏合作性的，为了尽可能地维护自己的利益，节点可能会采取各种各样的行为，比如拒绝转发数据、虚报节点信息等。在具体网络环境中，有很多种情况能够导致网络性能的降低，其威胁不仅来自于外部，更多的来自于内部的自私节点、恶意节点、叛变节点。由于节点自私行为的多样化，它们对网络性能的影响是不同的，应该区别对待，否则建立的惩戒机制就可能不是最有效的，因此对节点进行自私类型检测很有必要的。该文就是基于这种情况，参考了信誉值的算法，验证了三种自私类型节点的数目，并通过仿真查看其对网络性能的影响。因为网络中问题节点的多样化，下一步，将会完善算法，并提出一种基于博弈论的算法来惩戒问题节点，构建一个合理的机制，通过该机制让网络达到纳什均衡[10]，甚至于帕累托最优。

参考文献：

[1] 谭长庚，罗文燕，陈松乔，王建新.移动Ad hoc网络中节点合作性研究综述[J].计算机科学，2007，4：24-27，6.

[2] 陈真勇， 唐龙，唐泽圣，熊璋.以鲁棒性为目标的数字多水印研究[J].计算机学报，2006，29（11）.

[3] 黄莉.基于博弈论的无线网络节点行为研究[D].北京：北京交通大学，2011.

[4] Marti S， Giuli T， Lai K， and Baker M. Mitigating routing misbehavior in mobile Ad hoc networks[C].IEEE International Conference on Mobile Computing and Networking[M].NewYork：ACMPress，2000：255-265.

[5] Raya M， Aad I， Hubaux J， Fawal A. DOMINO： Detecting MAC Layer Greedy Behavior in IEEE 802.11 Hotspots[J]. IEEE TransactionsonMobileComputing，2006.5（12）：1-11.

[6] Gunasekaran R， Uthariaraj V， Yamini U， etc. A Distributed Mechanism for Handing of Adaptive/Intelligent Selfish Misbe- havior at MAC Layer in Mobile Ad Hoc Networks[J].Journal of Computer Science and Technology，2009，24（3）：1007-1017.

[7] Toledo A L， Wang X， Robust detection of selfish misbehavior in wireless networks [J]. IEEE J. Sel. Areas Commun， 2007， 6（25）： 1124-1134.

[8] Buchegger S，，Boudec J Y L.Performance analysis of the CONFIDANT protocol：Cooperation of nodes fairness in dynamic ad hoc networks. Proc of IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing（Mobi HOC），2002.

[9] LIU Chunfeng， SHU Yantai， LI Mingyuan， et al. Delay modeling and analysis of IEEE 802.11 DCF with selfish nodes[C]//Proceedings of the 4th International Conference on wireless Communications. Networking and Mobile Computing. Piscataway. NJ. USA：IEEE Press，2008：1-4.

[10] WANG Cui-rong， YANG Xiao-zong， GAO Yuan. Enhancement in Ad hoc on Demand Distance Vector （AODV） Routing Protocol Security[J]. Journal of DongHua University，2005，03：18-22.

[11] Srivastava V， Neel J O， MacKenzie A B， et al. Using game theory to analyze wireless ad hoc networks [J]. IEEE Communications Surveys and Tutorials， 2005， 7（1-4）： 46-56.