基于快速移动节点的Ad hoc网络可信度模型及可信路由协议

冉崇善，车 育

(陕西科技大学 电气与信息工程学院， 陕西 西安 710021)



·信息科学·

基于快速移动节点的Ad hoc网络可信度模型及可信路由协议

冉崇善，车 育

(陕西科技大学 电气与信息工程学院， 陕西 西安 710021)

由于目前广泛应用的路由协议大都是假设网络中的节点是可以信任和相互协作的,对于安全的问题考虑不多,而网络中某些节点很容易被俘获而成为恶意节点,使得现有的路由协议变得十分脆弱，针对这一问题，提出了基于快速移动节点的可信度模型FATM,以及基于快速移动节点的可信路由协议FARP,通过网络中的快速移动节点辅助一般节点进行可信度的计算和更新,并在可信模型建立之后选择可信度较高的路由进行通信。最后采用OPNET对FATM模型进行了仿真,仿真结果表明基于快速移动节点的可信度模型的安全性更高,并且节省了一般节点的能量和空间开销,具有较好的网络适应性及可扩展性。

自组织网络;可信度模型;可信路由协议;快速移动节点

无线自组织网络[1]MANET(Mobile Ad hoc network)是由一系列具有无线通信能力的节点构成,不需要依赖现有固定通信设施,能够临时迅速展开使用的一种网络体系,网络中的节点既是主机,又具有路由功能,可以满足紧急情况下通信的需要[2]。与传统的网络需要基础的通信设施不同,自组织网络没有控制中心,也不依赖预设的基础设施,所有的结点处于平等的地位,可以快速构建起一个无线通信网络,而且任一结点的故障都不会影响整个网络的运行,所以自组织网络具有很强的抗毁性。由于无线信道本身的脆弱性,自组织网络容易遭到窃听、入侵、拒绝服务等攻击,而且相比传统的无线网络,自组织网络没有固定基础设施,这一弱点就更为突出[3]。

1 快速移动节点的可信度模型

自组织网络的特殊性使得传统的信任模型很难适应其网络环境,为了降低可信模型过程中的计算量和资源消耗,同时满足可信模型的快速建立和扩展能力,本节提出了基于快速移动节点的可信度模型FATM(Fast-moving nodes assisted trust model),并对其进行详细的分析。

1.1 FATM模型引入

本文依据“移动性有益”[4]这一观点来进行模型的设计,这一理论是由Grossglauser和David于2002年提出的。该观点认为如果能够有效利用自组织网络中节点的移动性,非但不会降低网络性能,反而会对网络产生有利的影响[5]。目前自组织网络的可信度模型大多没有充分考虑到节点的能耗问题,导致网络开销增大,且不能保证迭代的收敛性[6]，为了解决这些问题本文提出了基于快速移动节点的可信度模型FATM,该模型发挥了网络中少数快速移动节点的作用,对模型的建立、更新等起到了良好的辅助,同时也降低了一般节点的能量消耗,提高了网络性能。为方便表述,引入一般节点和快速移动节点概念。一般节点指那些在自组织网络中计算能力和节点能量较弱的节点,同时移动速度较低;快速移动节点指那些在自组织网络中移动速度较快,计算能力和节点能量充足的节点[7]。

1.2 FATM模型设计

在FATM模型中,一般节点和快速移动节点的任务有所区别。一般节点主要完成对邻居行为的监听,局部可信值的计算、储存,以及数据包的转发策略等。而快速移动节点主要负责全局可信值的收集、计算、更新等工作。

1.2.1 一般节点 FATM模型中的一般节点完成的工作主要是:监听邻居信息,计算、储存局部可信值,与快速移动节点进行信息交互。图1为一般节点的状态转移图。

图1 FATM模型的一般节点状态转移图Fig.1 FATM general node state transition diagram of the model

1) 监听邻居信息

每个一般节点在信任值的初始化完成后都将处于Idle状态,定时对邻居发送的数据包进行监听,判断邻居是否存在未转发数据包、或是恶意篡改的行为,通过Update状态来对邻居消息进行更新。监听邻居信息的报文结构如图2所示。

图2 邻居信息报文Fig.2 Neighbor information message

节点通过监听来判断邻居是否转发了自己的数据包,而由于邻居转发数据包的目的地址不是本节点,本节点的MAC层在收到数据包后会自动将包丢弃,因此需要对MAC协议进行修改。节点在发送给邻居数据包后,设置两个时间阈值t1和t2,t1为正常情况下邻居转发数据包的时间,t2为网络延迟非常大时邻居转发数据包的时间上限,t1

2) 与快速移动节点进行可信值交互

每个一般节点维护一张信任列表Trust[N],其中记录了对网络中其他节点的信任值(范围为0～1的实数),当一般节点检测到其周围存在快速移动节点时,其有限状态机进入FN状态,将自己监听到的局部信息发送给快速移动节点,同时从快速移动节点接受网络的全局信息。由于一般节点自身不进行全局可信值的计算,因此这样的交互过程,就使得一般节点以较小的计算量来获得全局性的节点可信值[9]。

1.2.2 快速移动节点FATM模型中的快速移动节点状态转移图如图3所示。

图3 FATM模型中快速移动节点的状态转移图Fig.3 Fast moving nodes in the FATM model of the state transition diagram

快速移动节点在网络的移动过程中,周期性地接受来自一般节点的邻居监视信息,收集一般节点报告信息构成全局性的信息,并将网络中节点的全局可信值及时更新到一般节点,使其能够了解最新的全局信息。由于在网络规模较大时,一般节点很难了解到与其相距较远节点的可信值,因此,快速移动节点在网络中的移动使其可以迅速将全局可信值发送到一般节点。而一般节点在接收到来自快速移动节点的全局可信信息时,通过下式来更新自己的信任列表Trust[N][10]

T=α*TD+(1-α)*TI，

(1)

式(1)中,TD表示节点对目标节点的直接信任值,TI表示节点接收来自快速移动节点的全局可信值。TI的计算由快速移动节点完成

(2)

式(2)中,TI(s,d)为节点s对d的推荐信任值,TD(s,i)为节点s对i的直接信任值,adj(s)为节点s的邻居。当TD为空,即节点不了解目标节点的信任值时,直接将目标节点的全局可信值TI作为对其的信任值。

1.2.3 模型分析FATM模型本质上属于混合式可信度模型,既通过节点的邻居监视机制来获取局部性的可信值,又使用在网络中快速移动的节点来将局部信息全局化。对一般节点的计算能力和能量要求较低,而且无须配备其他额外的功能。与其他可信度模型相比而言,FATM的一般节点在算法复杂度上与基于局部推荐的模型相当,而由于快速移动节点的作用,能够得到节点在全局性的可信值。因此,FATM模型的实用性更好。

2 快速移动节点的可信路由协议

在自组织网络中的节点相互之间建立了信任关系之后,节点在进行相互通信时对网络中的其他个体有了一个明确的认识,节点行为也不再漫无目的,而受到可信度模型的约束。节点对其他节点的信任值,就成为其在通信过程中路由选择的一个关键因素。为降低节点路由过程中的计算量及能量消耗,本节对DSDV路由协议进行了改进,提出了基于快速移动节点的可信路由协议FARP(Fast-movingnodesAssistedRoutingProtocol)。

2.1 FARP协议

节点在建立了可信模型之后,如何在发送数据时进行路由的选择就成为下一个问题。传统的安全路由协议是通过节点之间进行加密认证等身份信任的机制来保证通信的安全。而本文在FATM可信度模型的基础上,选择高可信度的路径进行数据的转发,将高可信度的邻居作为下一跳的转发节点,从根本上避开了网络中可信值较低的懒惰节点及恶意节点。

2.1.1 寻找最大可信路由的算法 在节点vi需要向目标节点vj发送数据包时,为了选择出可信值最高的通信路径,FARP协议对dijkstra算法[11]进行修改,dijkstra算法描述了节点如何选择到目标节点的最短路径,类似地,FARP协议需要节点选择出到目标节点可信值最大的路径。修改后的寻找可信值最大的路径算法过程如下:

1)定义集合S存放已经找到可信值最大路径的节点,集合T存放目前尚未找到可信值最大路径的节点,即满足T=V-S。将S初始化为空集。从vi出发到网络中其他节点vm最大可信初值为

D[m]=μ(vi,vm)，其中vm∈V。

2)选择vn,使得D[m]=max{D[m]|vm∈V-S}，则vn就是当前求得的一条从vi出发最大可信值的节点。令S=S∪{vn}。

3)修改从vi出发到集合V-S中任一节点vk的最大可信值。如果满足D[n]*μ(vn,vk)>D[k]，则修改D[k]为D[k]=D[n]*μ(vn,vk)。

4)重复步骤(2)和(3),直到集合S包含网络中所有节点,就可计算出节点vi到vj的最大可信值及最大可信路径。

2.1.2FARP协议的工作过程 根据上一节对寻找最大可信路由算法的介绍,可知其时间及空间复杂度都较大,且由于源节点并不知道邻居节点对其他节点的信任值,因此,一般节点无法对最大可信路由进行计算。针对这一问题,本节采用一般节点向FN询问的方法,具体工作过程如下:

1) 源节点在进行数据发送时,首先查询其周围是否存在快速移动节点。

2) 如果周围有快速移动节点,则向其发送可信路由的请求;如果没有,则转入步骤(5)。

3) 快速移动节点经过计算后,将最大可信路径发送给一般节点。

4) 一般节点根据最大可信路径,进行数据包的发送。转入步骤(7)。

5) 节点在一个设定的时间阈值t内继续探测周围是否有FN到来,如果出现FN,则转入步骤(2),否则转入步骤(6)。

6) 时间t内仍然没有快速移动节点出现,则节点在其路由中选择可信值最大的节点进行转发。

7) 节点发送数据包完成。

2.2 FARP协议的分析

在FARP协议中,一般节点进行数据发送时,需要向FN发出最大可信路由请求。而由于此时一般节点周围可能并不存在快速移动节点,因此一般节点的可信路由查询过程需要一定的时间,由于节点与FN相邻,固一般节点发送可信路由请求及接收快速移动节点的最大可信路由信息的时间相对较小。而FN较强的计算能力,使其计算最大路由的时间也相对较小。因此,节点周围出现FN的时间,占据了可信路由查询时间的主要部分。可以认为,节点在发送数据包时,一旦等到其周围出现FN,则可以立即得到经过FN计算的最大可信路由。

3 FATM与DSDV的仿真与分析

本节对FARP与传统的预先式路由协议DSDV的路由性能进行了仿真对比,研究了两种协议的分组投递率情况。仿真采用RWP作为节点的移动模型,默认的网络场景大小A*A为1000m*1000m,一般节点数N为100个,通信半径r为50m,最大移动速度v为5m/s,快速移动节点个数M为20个,通信半径R为100m,固定移动速度u为50m/s,恶意节点个数E占据一般节点的5%,仿真时间为600s。

路由协议的分组投递率为目的节点收到的数据包个数与源节点发送的数据包个数之比。这个参数反映了网络的吞吐量,表明了协议在不同网络环境下的可用性及有效性。

3.1 恶意节点数目不同时候的分组投递率

图4为网络中恶意节点数目变化时,FARP协议与DSDV协议的分组投递率。可以看出,在恶意节点数目增加时,DSDV协议的分组投递率有明显的下降,而FARP协议的分组投递率的下降相对较小。这是由于,DSDV协议仅维护一个下一跳邻居,而在恶意节点多的时候,其下一跳邻居是恶意节点的概率会增大,使节点的数据包不能得到发送,从而造成分组投递率的下降。而FARP协议的一般节点通过快速移动节点的辅助,能够主动选择最大可信路由进行通信,从而避开了恶意节点,使得分组投递率能够保持在相对较高的水平。

图4 恶意节点个数不同时的分组投递率Fig.4 The packet delivery rate of different malicious nodes

3.2 一般节点通信半径不同时候的分组投递率

图5为一般节点通信半径不同时DSDV与FARP的分组投递率。由图4可见,随着一般节点通信半径的增加,DSDV和FARP协议的分组投递率都有不同程度的增加。这是由于一般节点通信半径越大,其能够发送和接受数据包的距离越远。而FARP协议中一般节点通信半径的增加,还使其与FN进行可信值交互的范围增大,能够从FN获得最大可信路由的几率也增加,因此FARP协议的分组投递率更高。

图5 一般节点通信半径不同时的分组投递率Fig.5 The packet delivery rate of different general node communication radius

4 结 语

本文对基于快速移动节点的可信度模型FATM以及基于快速移动节点的可信路由协议FARP进行了分析,并采用OPNET进行计算机仿真实验,将本文提出的可信路由协议与DSDV协议进行了仿真对比。仿真结果表明,基于快速移动节点的信任模型和路由协议具有更高的安全性,并且能够节省节点的能量消耗和空间开销。

[1] BROWN K, VAIDYA H. Location-aided routing (LAR) in mobile Ad hoc networks[C]∥Dallas:Proceeding 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom′98), 1998:66-75.

[2] BUCHEGGER S, MOLVA R. Nodes bearing grudges:Towards routing security,fairness,and robustness in mobile ad hoe networks[C]∥Los Angeles:10th Euromicro Workshop on Parallel,Distributed and Network-based Processing, 2002.

[3] PAPADIMITRATOS P, HAAS Z. Secure routing for mobile Ad hoc networks[C]∥San Antonio:Proceedings of the SCS communication Networks and Distributed Systems Modeling and Simulation Conference, 2002: 27-31.

[4] GROSSGLAUSER M, HALL D. Mobility increases the capacity of ad hoc wireless networks[J]. IEEE/ACM Transactions on Networking, August 2002, 10(4):477-486.

[5] LEINER M, ROBERT R, SASTRY R. Goals and challenges of the DARPA gloMo program[J]. IEEE Personal Communications, 1996,3(6):34-43.

[6] 宋雪吕,陆建德.基于组群的P2P系统中的信誉机制[J].微机发展,2005,15(11):11-13.

[7] SERGIO M, GIULI J. Mitigating routing misbehavior in mobile Ad hoc networks[C]∥Boston:Proceedings of 6th International Conference on Mobile Computing and Networking (MobiCom), 2000: 145-149.

[8] DAVID L. Transmission range control in multihop packet radio networks. communications[J]. IEEE Transactions on Communications, Jan 1986, 34(1):38-44.

[9] KEVIN L.E-learning markets and providers.some issues and prospects[J].Education Training,2001,43(4):233-239.

[10] LEBRON H. Transmission range control in multihop packet radio networks. communications[J]. IEEE Transactions on Communications, 1996, 34(1):38-44.

[11] BASAGNI S. A distance routing effect algorithm for mobility [C]∥Dallas: Proceeding 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom′98), 1998:76-84.

(编 辑曹大刚)

Research on fasting-moving node assisted trust model and routing protocol in mobile Ad hoc networks

RAN Chong-shan, CHE Yu

(College of Electric & Information Engineering, Shaanxi University of Science & Technology, Xi′an 710021， China)

Current widely used routing protocols mostly assume the nodes in the network are cooperative and trustful, however, some nodes can easily be captured and become malicious node, making the routing protocols become weak, to design a secure routing protocol has become a serious problem. To solve this problem, This paper presents the reliability of FATM model based on fast moving nodes, and FARP based on trusted routing protocol, calculating and updating aided general node credibility by fast moving nodes in the network, and choosing high reliability communication routing after trusted model. Finally, OPNET is used in the simulation of the FATM model, the simulation results show that the security of the trust model based on fast moving nodes and trusted routing is higher, and saves energy and space than that on general nodes, and has better network adaptability and scalability.

Ad hoc; trust model; trust protocol; fast-moving nodes

2014-04-11

国家自然科学基金青年科学基金资助项目(61202019)

冉崇善，男，陕西富平人，陕西科技大学教授，从事分布式系统与计算机网络、智能信息处理等研究。

TP319

：ADOI：10.16152/j.cnki.xdxbzr.2015-02-008