一种基于簇的移动Ad hoc路由算法

摘要：在大规模MANET中采用分簇的方法进行路由是解决网络可扩展性问题的一个有效方法，该文提出的CBRP算法在选取簇首节点时，引入了节点的带权ID，簇的分布更加均衡，改善了大规模MANET的路由计算效率。路由过程中使用数字签名，增强了CBRP路由的安全性。最后的仿真结果显示，与现有的协议相比，CBRP算法能提供更好的Qos性能，适合于结点较多、节点的移动速度受到一定限制的MANET。

关键词：MANET；簇；安全路由；Qos

中图分类号：TP311文献标识码：A文章编号：1009-3044(2010)20-5436-03

A Cluster-based Routing Algorithm for MANET

TIAN Bo

(Department of Computer, Tongren College, Tongren 554300, China)

Abstract: Cluster-based routing algorithm operated in large Mobile Ad hoc networks can successfully solves the problem of scalability. The paper proposes a new cluster-based routing algorithm which introduced the Weight_ID of node when the head of cluster is selected. It provided a more balance of cluster in Ad hoc networks, and enhances the efficiency of routing in large Ad hoc network. The security is improved for signature is included in routing. The simulation result shows that compared with some protocols in mobile Ad hoc network, CBRP can increase the network performance and easy operation in large mobile Ad hoc network which its nodes moving at restrict speed.

Key words: mobile Ad hoc network; cluster; secure routing; quality of service

MANET网络( Mobile Ad Hoc Network,)是一种在无固定网络基础设施的条件下，各节点自组织、自构建、自管理的无线多跳网络。各通信节点带有无线收发装置，具有数据处理及路由功能，通过分布式协议构建成一个动态的、拓扑结构多变的自治性网络系统。MANET具有如下特点[1]：1) 节点可随机移动，导致网络拓扑变化频繁，路由协议要适应这种动态的变化。2) 采用无线传输介质，带宽有限且不稳定，易受外界干扰。3) 无中心控制结点，在部分节点出现故障的情况下，其余节点仍可相互通信。4) 节点能源受限，且无线信号具有开放性、误码率高的特点，极易遭受路由攻击。5) 现有的成熟安全技术主要是相对静态的有网络骨干基础设施的有线网络，在Ad hoc网络中不能直接使用。

目前在具有固定基础设施的有线网络中，路由协议基于以下两种原理运行：距离向量与链路状态，如 DSDV 和AODV 协议[2]。其特点是节点周期性地向网络中的路由器广播路由信息，进而更新自己的路由表。DSDV协议基于Bellman-Ford路由算法，使用目的序列号来消除环路问题，每个节点周期性与邻居节点交换路由信息，当MANET的拓扑快速变化时，网络负荷比较严重，导致DSDV算法收敛速度慢，能源消耗高[3]。文献[4]提出了几个改进的安全DSDV协议的方案，以分区的方式实现路由，同时在两个节点间保留一对偶密码，确保路由信息的安全，但会导致网络开销增大，链路传输效率降低。OLSR协议是一种表驱动的路由协议，包括“路由建立”和“路由维护”两个阶段，但安全性低，易受路由攻击[5]。为此，文献[6]提出使用数字签名对OLSR路由消息进行认证，从而构建了安全OLSR协议。但协议在工作需要一套完善的认证方式和密钥管理方案，不易实现。目前一些新的协议，如HSR、CBRP协议等[7]，为适应MANET移动性和稳定性、优化网络带宽、提高QoS性能，采用了分簇算法，文献[8]对这类算法做了详细的分析，证明分簇算法能很好地支持节点的快速移动，提高MANET的可扩展性。文献[9]从平衡负载、降低路由开销的角度出发，在分簇算法的基础上使用多路径并行传输数据包，有效地提高了网络的QoS性能，但路由协议的安全性也不高，易受洪泛或虫洞攻击。

利用分簇的思想，本文提出了一种基于簇的路由算法（CBRP）。以分簇的方式管理MANET中的结点，簇内使用一种改进的DSDV算法计算路由，不同的簇之间使用按需路由算法。为提高CBRP算法安全性，节点对路由消息进行认证，确保路由消息不会被攻击者所篡改，为源结点和目的节点提供安全的路由。仿真结果表明，该算法有效提高了MANET的可扩展性和安全性，减少了数据传输时延，降低了路由计算开销，具有良好的QoS性能。适合节点数目较多的MANET或传感器网络。

1 CBRP算法描述

随着MANET中的节点数目增多、网络覆盖范围的扩展，计算和更新路由变得复杂耗时，网络拥塞和丢包的概率增大，降低网络的QoS性能。一种解决方案是采用分层的拓扑结构，如图1所示。将一定数量的相邻节点构造成一个簇[10]。簇的大小根据链路的容量、QoS需求、MAC层协议等因素来确定，规模在30个节点[11]之内，会在QoS性能和管理的复杂度之间达到较好的平衡。

CBRP算法中，同一个簇内的节点相互通信时采用DSDV的思想进行路由的计算。簇间的路由采用按需路由协议，考虑到中等以上规模的MANET中的节点可能比较多，CBRP算法采用了DSR协议的思想，通过广播一个路由请求消息来创建到目的节点的路由，节点不需要动态地维护路由更新信息。

1.1 CBRP中的簇首选取算法

一种生成簇的典型算法是最小ID法[12]，每个节点在MANET中有唯一的标识（ID），取ID值最小的节点为簇首节点。此算法可能会导致某些节点被孤立而无法通信。CBRP算法对最小ID算法做了改进，对节点ID赋予了一个权值，选取权值最大的节点作为簇首。另外，随着软、硬件技术的进步，各节点之间的链路都是全双工的。在此前提下，CBRP算法按以下策略选取簇首节点：

1) 计算MANTET中每个节点的带权ID（WID），其中权值由以下因素确定：① 邻居节点的个数；② 节点的位置；③ 节点的有效带宽。

2) 在固定的时间间隔内，每个节点周期性地向邻居节点广播QUERY消息,此消息中包含发送者的WID、IP地址、数字签名等信息。

3) 每个节点将自己的WID值与邻居节点的WID值进行比较，如本身的值最大，则自动成为簇首节点。

4) 向邻居节点广播消息，声明自己成为簇首节点。邻居节点收到此消息后，修改自己的邻接表，再发送一个应答消息，声明已加入该簇。

从以上策略可知，簇首节点至簇成员节点只有一跳的距离。一个簇成员节点可以同时属于多个不同的簇。簇首节点维持了所有簇成员的信息，并动态维护和更新全簇范围内的路由表。当同一个簇内节点之间通信时，簇首节点查询路由表，寻找合适的路由，转发数据包至目的节点。

1.2 网关节点

连接两个不同簇的节点称为网关节点，两个相邻的簇之间至少有一个网关[13]节点。簇之间的数据流量都通过网关节点转发。网关节点可以同时是两个相邻簇的成员，也可以只属于一个簇的成员，但另一个簇中中至少有一个节点在其通信范围内。MANET中的任一节点的角色可以是簇首节点（head）、网关节点（gateway）、簇成员(member)节点中的一种。CBRP算法采用以下策略指定网关节点：1) 邻居节点之间广播邻接表，获得相邻节点的角色；2) 如果两个相邻节点的角色都为head,说明属于两个不同的簇，将自己的邻接表中的相应网关标识设为1; 3) 节点检查收到邻接表后，如发送方不在本节点的邻接表中，说明发送方位于另一个簇中，将自己邻接表中相应的网关节点设为1；4) 发送消息至簇首节点，声明自己为网关，簇首节点随后返回一个消息予以确认。

生成网关节点后，除非簇首节点更新簇内的路由表，否则网关节点的角色不会改变。网关节点将承担相邻簇之间的数据流量。

1.3QUERY消息与邻接表的结构

在簇首节点的选取时，每个节点广播QUERY消息。其结构如下：1) WID：带权值的节点标识，在MANET中唯一；2) 所属的簇的序号：初始值为0；3) 序号：标识了此消息的序列；4) 数字签名：用于验证发送者的身份；5) 本节点的IP地址。

每个节点维护一张邻接表结构，用于保存邻居节点的相关信息，CBRP中的每个邻接表由以下几部分构成：1) 邻居节点WID；2) 邻居节点角色：可取簇首、簇成员、网关中的一种，初始值为簇成员；3) 邻居IP地址；4) 本节点角色；5) 网关标识：安始值为0，如被作为网关，则改写为1；6) 本节点的IP地址。

1.4 簇的动态更新

随着网络拓扑结构的动态改变，可能会导致簇的改变。当一个新节点加入MANET中时，将广播一个QUERY消息至1-hop邻居节点。邻居节点返回其邻接表，新节点检查其角色域，如为簇首，则将自己的WID值与此簇首节点的WID值进行比较，如本身的值较大，标志自己为簇首节点。否则宣布自己成为该簇的成员节点。簇首节点定期广播本节点的邻接表，簇成员收以此消息后，返回一个应答消息，如簇首节点在连续两个时间周期内没有收到簇成员节点的应答消息，认为此成员节点脱离了本簇范围。该节点需按照簇首的选取算法重新生成簇首节点，即产生一个新的簇。

2 CBRP的路由发现

2.1 同簇的节点间路由算法

同一簇内的节点间在计算路由时借鉴DSDV协议的路由思想，各节点保存一张至本簇内其它节点的路由表。CBRP采用了一种表驱动的路由方法，按以下步骤计算路由：

1) 源节点发出路由请求消息（RREQ）至簇内其它节点，目的节点根据反向链路标记，标识出至源节点的路径,发送回RREP消息。

2) 簇中每个节点在时间间隔T内广播它的当前路由表信息，路由表中包含自身的序列号，初始值为0，节点收到此消息后，每转发一次加1，当大于2时，说明已超出所在簇范围，随即丢弃此消息。

3) 收到该数据包的节点将目的节点的序列号与自身路由表中相应的序列号表项相比较，如收到的数据包的序列号较大，则更新本节点的路由表，否则将其转发，距离增1。

4) 如果某节点发现一条链路失效，则将通过该节点转发的路由的序列号增1。

2.2 不同簇的节点间路由算法

CBRP算法在时，要求每个网络节点拥有一系列的非对称密钥，类似DSR的按需路由思想，CBRP算法将按以下步骤计算簇间路由：

1) 簇成员S向所在簇的簇首节点发送路由请求，此消息中包含簇首节点的数字签名。

2) 簇首节点通过网关节点向其它簇首成员节点发送路由请求消息，此消息中包含了源节点和目的节点的地址（IP）。

3) 其它簇的簇首节点首先验证数字签名，检查是否已收到此消息（通过检查发送者的ID），如此前没有收到，则广播此消息，否则丢弃此消息。

4) 当目的节点D收到此消息，则把路由信息封装在应答消息RREP中发送到所在簇的簇首节点。

5) 簇首节点记录下目的节点的ID，将RREP消息发送至节点S所在簇的簇首节点。

数字签名机制要求每个网络节点拥有一系列的非对称密钥[14]，这会增加计算开销、网络开销以及管理开销，在目前的技术条件下，MANET中的网络节点具有足够的计算机能力。CBRP算法中由簇首负责密钥的管理和分配，可有效地抵御利用篡改、伪造或者假冒的攻击，提高路由协议的安全性和有效性。

3 CBRP算法性能分析

SEAD协议是一个使用较广泛的安全的DSDV协议，其路由算法在大规模的MANET中很有代表性。为验证本文的CBRP算法在规模较大的MANET中的有效性，采用了NS2平台对CBRP算法和SEAD协议进行了模拟，并对两者的平均时延、路由开销二个关键的Qos性能作了比较。仿真参数设定如下：1) 网络节点数：150；2) 节点分布的物理区域： 1200mC2000m；3) 节点的移动速度：0C50 m/s 之间变化；4) 单个节点的信号范围：800m；5) 数据包的长度：1k；6) 网络有效带宽：512kb/s ；7) 仿真时间：1000秒；8) 重复次数：> 200次。

网络中的节点在区域内随机移动，速度在0-50m/s之间随机变化。到达设定的位置后停留的时间也是随机的。对仿真的结果进行绘图后，如图2与图3所示。

从仿真结果可以看出：

1) 从图2可以看出，与SEAD协议比较，CBRP路由算法点对点的平均延迟要小，说明CBRP更适合传输实时的数据流。因为同一簇内的节点间采用表驱动的路由算法，计算路由时，路由表的维护在簇首节点的管理下仅局限于对簇内节点广播路由信息。而不同簇内节点通信时使用按需路由算法，只有在必要时才申请路由，减少了通信开销。平均而言，采用分簇的方法，CBRP的分组投递效率比SEAD协议要高。

2) 图3表明在一定的节点移动速度范围内，CBRP路由算法的开销始终小于SEAD协议。但当节点移动速度超过阀值>40m/s，CBRP的路由开销急速增加，算法效率有所降低， 因为节点移动速率增加，导致簇的更新频率提高，大量的网络开销用于簇的重构和维护。从仿真结果可看出，CBRP算法提高了MANET的可扩展性，适合节点数目比较多的网络，但不适合网络拓扑变化频率极高的情况，例如车载MANET网络。

4 结束语

结合各种分簇算法的优点，本文提出的CBRP算法采用了一种新的分簇方法，在选取簇首节点时，引入了节点的带权ID，综合考虑了节点的邻居节点数量、位置和有效带宽。CBRP算法簇首的选取更加合理，提高了MANET的可扩展性。簇内节点通信时采用表驱动的路由算法，不同簇的节点通信时使用按需路由算法，降低了路由计算时间，改善了大规模MANET的路由计算效率。利用在路由请求信息中使用数字签名的方法，确保由CBRP路由安全性。仿真结果表明，与当前广泛使用的SEAD协议比较，CBRP算法适合于结点较多、节点的移动速度受到一定限制的MANET。但在节点移动速度相当快的MANET中，CBRP算法导致网络开销迅速增大，严重影响网络Qos性能。如何改进CBRP算法，使之适应节点移动速度极快的MANET，值得进一步研究。

参考文献：

[1] Perkins C E.Ad Hoc Networking[M].London:Addison Wesley,2001,2(1):2-5.

[2] Chrales E Perkins,Elizabeth M Belding-Royer,Samir R Das.Ad hoc On-demand Distance Vector Routing Draft-ictf-manet-aodv-13.txt,2003,3(2):3:4.

[3] Perkins C E and Bhagwat P.Highly Dynamic Destination-Sequenced DistanceCVector Routing for Mobile Computers[C]. Proceedings off the ACM SIGCOMM Conference on Communications Architectures. Protocols and Apllication,London,UK,September 1994:234-244.

[4] Y.C.Hu,D.B.Johnson,and A.Perrig. SEAD:Secure Efficient Distance Vector Routing for Mobile Wireless Ad hoc Networks [M].Ad Hoc Networks, 2003,1(1),175:192.

[5] A.Halfslund,A.Tonnesen,R.B.Rotvik,J. Anderson,and O.Kure.Secure Extension to the OLSR Protocol[J]. OLSR Interop and Workshop.2004.

[6] D.Raffo,T. Clausen,C. Adjih,and P. Muhlethaler. An Advanced Signature System for OLSR. SASN[M]. October 2004.

[7] Jiang M L,Li J Y,Tay Y C. Cluster Based Routing Protocol[J].Internet Draft, National University of Singapore,1999.

[8] 安辉耀,王新安.移动自组网中的先进路由算法与路由协议[M].深圳:科学出版社,2009:67-83.

[9] Tsirigos A,Haas Z J.Multipath routing in the presence of frequent topological changes[M].IEEE Communications Magazine,2001,132:139.

[10] Kim D,Ha S,Choi Y. K-hop cluster-based dynamic source routing in wireless Ad Hoc packet radio networks[J].IEEE VTC,1998:224:228.

[11] Chatterjee M,Das S K, Turgut D.WCA:a weighted clustering algorithm for mobile Ad Hoc networks[J].Journal of Clustering Computing IEEE 2002,193:205.

[12] Gerla M,Tsai T C.Multiculster,mobile,multimedia radio network.ACM Journal of Wireless Networks,1995.

[13] 冯永新,王光兴.一个应用于移动Ad Hoc 网络管理的簇生成算法[J].软件学报,2003,14(1):132-138.

[14] Farooq Anjum Petros Mouchtaris. Security for Wireless Ad Hoc Networks[M].2009(43):48.