一种基于分层结构的Ad Hoc网络分簇路由协议研究

冯永亮

（西安文理学院数学与计算机工程学院，陕西西安710065）

一种基于分层结构的Ad Hoc网络分簇路由协议研究

冯永亮

（西安文理学院数学与计算机工程学院，陕西西安710065）

传统Ad Hoc网络分簇路由协议存在分组投递率低的问题，论文提出一种基于分层结构的分簇路由协议。高级网络层采用基于备份路由的AODV协议，而低级网络层则采用时延较小的DSDV协议。仿真结果显示，改进后的路由协议提高了分组投递率，缩短了端到端时延。

Ad Hoc；AODV；簇；路由；协议

无线Ad Hoc网络是由任意分布且随机移动的节点通过自组织的方式构建的一种无线通信网络，广泛应用于军事行动、环境监测、医疗急救、抢险救灾等领域。其主要特征包括：无中心管理节点、节点双重身份、拓扑动态变化、自组织、多跳路由、链路带宽受限、能量受限和安全性较差等［1］。

按照拓扑结构，Ad Hoc网络可分为平面结构和分层结构［2］。平面结构中所有节点都是对等的，节点之间往往存在多条路径，可以根据网络状态参数选择适当的路径。平面结构的路由协议分为表驱动和按需驱动的路由协议。其中，表驱动路由协议包括DSDV、WRP、FSR等，按需驱动路由协议包括AODV、TORA、ABR、SSR等［3］。实践证明，基于平面结构的路由协议，健壮性、安全性比较强，但是随着网络规模的扩大，协议的性能会下降，网络开销越来越大［4］。因此，研究者寻求通过改变网络的物理结构从根本上解决平面结构的扩展性问题。于是，分层结构应运而生，所谓分层结构是指利用一定的策略将网络节点划分为若干个簇，每个簇包含一个簇头和若干个簇成员。簇头是通过算法选出，并负责簇内节点以及簇间节点之间的数据通信。常见的基于分层结构的路由协议包括ZRP、CBRP、CGRP、CHSR等。相对于平面结构，分层结构明显减少了节点间路由的跳数，降低了路由延时，改善了网络的扩展性，但是也导致可扩展性差等问题。

针对传统分簇路由协议导致Ad Hoc网络可扩展性差的问题，本文提出一种基于分层结构的Ad Hoc分簇网络路由协议，即在低级网络层簇成员之间采用一种基于路由备份的AODV路由协议，而在高级网络层簇头之间间则采用基于表驱动的DSDV路由协议。仿真实验结果显示，改进后的路由协议提高分组到达率，降低了端到端时延，提高网络可扩展性。

1　Ad Hoc分层网络结构

如图1所示，Ad Hoc分层网络结构按照一定的策略将网络节点划分为若干个簇，每个簇包含一个簇头和若干个簇成员。网络簇间节点的通信通过高层的簇头转发完成，通信过程只需要一次或少数几次转发即可完成，分层结构如图1所示。分层结构将网络分为低级网络层和高级网络层。低级网络层由簇内普通成员构成。高级网络层由簇头选举算法选举出的、综合性能较好的的簇头节点构成。簇头主要负责管理和维护簇内节点，以及簇与簇之间的通信。相对低级网络层，高级网络层减少了由于节点移动对网络拓扑结构造成的影响，结构较为稳定，因此提高了网络的可扩展性。

相对于ZRP协议直接在平面结构上划分簇，新的分层结构具备如下优点：①节点的改变或移动只影响到其所在簇的结构，降低了对整个网络拓扑的影响，减少了洪泛开销。②提高了网络稳定性，降低了由于节点变化造成的重路由发生的概率。③提高了网络扩展性，适合于大型网络。

图1　Ad Hoc网络分层结构Fig.1Hierarchical structure of the Ad Hoc network

2　基于分层结构的分簇路由协议的设计

2.1基本设计思想

高级网络层主要负责簇头节点间的稳定、高效的通信，由于簇头节点的处理能力、存储容量、传输速度、剩余能量等性能指标都比较良好，簇头改变概率相对低一些，因此，适合采用按需驱动路由协议AODV。本文设计一种基于备份路由的AODV，避免路由重新发现。低级网络层指各个分簇内部的网络结构，这种结构易受到簇成员节点移动影响。因此考虑选择实时性强、路由发现时延小的表驱动路由协议DSDV。

2.2高级网络层中簇头路由协议的设计

在高级网络层，源簇头节点收到需要转发的信息，首先会查找现有的路由表，如果发现存在到目标簇头节点的路由，则直接建立通信链路；若没有发现到目标簇头节点的路由，则会广播一个带有目标簇头节点信息的路由分组RREQ到所有邻居簇头，邻居簇头会依次向周围的簇头继续广播这个路由分组，若此路由分组到达目标簇头节点，则停止广播［5］。此时，目标簇头节点会沿着反向路由发送RREP，以便实现反向路由确认，当源簇头节点收到反向裸游发送的RREP时，就能确定从源簇头节点到目的节点之间的路由链路，从而实现簇头间的通信。

由于AODV路由协议一般只维护路由表中的一条到指定目标节点的路由，若该路由失效，源节点需要重新进行路由发现，带来大量的路由负载，增加了网络负荷。为了充分利用路由广播的RREQ，避免浪费路由资源，本文设计出目标簇节点收到RREQ后，按不同路径回复两个RREP，对于已经存在目标节点有效路由的中间节点收到RREQ后，只要有一个中间节点回复RREP给源节点即可。这样，源簇头节点可以收到两个RREP，而将最先达到的RREP里保存的路由作为主路由，第二个达到的作为备份路由［6］。当主路由断裂或失效时，源节点可以不必发起路由请求，直接调用备份路由［7］。基于备份路由的AODV模型如图2所示。从源簇头节点A到目标簇头节点G存在两条路径：（A，B，C，G）和（A，D，E，F，G）。

图2　基于备份路由的簇头间AODV路由模型Fig.2AODV routing model between cluster heads based on backup routing

2.3低级网络层中簇成员路由协议的设计

低级网络层由于受到簇成员影响较大，本文考虑采用按路由表驱动的、数据传输实时性强，路由发现延时小的DSDV路由协议。在DSDV中，每一个簇成员节点维护一个路由表，每个路由表项包括：目的地址、达到目的节点的度量、目的节点相关的序列号等，该序列号用来识别路由的新旧，作为路由更新和分组转发的依据。各节点周期性的向邻居节点通告其当前的路由表，由于未采用洪泛方式，大大减少了通信的信息量［8］。基于DSDV路由协议的簇成员节点的路由表信息如图3所示。

图3　各簇成员节点路由表信息Fig.3Routing table information of each cluster member node

簇成员节点必须周期性交换路由信息，路由表的改变也可触发路由更新。更新路由表有两种方式：一种是部分更新，更新的消息中仅包含变化的路由部分，主要针对变化较慢的网络；另一种是全部更新，主要用于变化较快的网络。DSDV选择使用序列号最高的路由，如果两个路由具有相同的序列号，则选择最优的路由。

3　仿真结果实现及分析

为了对改进的路由协议进行评估，仿真环境采用了NS2，仿真场景为1 000 m×1 000 m里的100个移动节点，节点的通信范围为200 m，节点停留时间分别为10 s，20 s，30 s。节点移动速度在0 m/s到20 m/s范围内均匀分布。仿真持续时间为120 s。

分组到达率是指目标节点最终接收到的数据分组数目和源节点发送的数据分组数目的比值［9］。

从图4可以看出，AODV、DSDV和改进后的路由等三种路由协议呈现出不同的分组投递率。DSDV协议采用表驱动路由方式，链接随着节点的移动不断发生变化，路由表中的信息大量失效，在链路较长时表现的更为明显，分组会因为链路的失效而被丢弃，因此其分组到达率较低。AODV则表现出良好的投递率，并且其稳定性并未受网络规模扩大的影响。改进后的路由协议综合了前两者的优势，将表驱动的旅游区域缩小，降低了路由表的信息量，降低了时延，提高了分组投递率。同时，又吸收了AODV的稳定性，但是，随着网络规模扩大，其性能有所下降。

图4　分组到达率Fig.4Packet arrival rate

端到端分组平均延时是指数据分组成功从源节点到达目的节点平均所经过的时间。端到端平均时延可以反映出网络是否畅通，时延越小网络越通畅［10］。

从图5可以看出，在节点数小于20的情况下，DSDV表现出良好的性能，充分发挥出表驱动路由的优势。而AODV和改进路由则表现出较大的延时，这是因为由于网络节点数较少，不容易建立链路。随着网络规模不断增大，AODV协议需要在每次发送数据包是才进行路由查询，端到端延时明显增加。而改进后的路由，由于节点数增加，高级网络层簇头节点按需进行路由驱动，需要消耗时间，增加了时延，但相对于AODV表现出较低的延时。

图5　端到端延时Fig.5End-to-end Delay

4　结束语

Ad Hoc网络因组网灵活，适应性强，所有有着广泛的应用前景，其路由协议一直是研究的热点。文中针对Ad Hoc网络分簇路由协议存在的分组投递率低，端到端传输时延大等问题，提出了基础分层结构的路由方案，在高级网络层的簇头之间采用按需驱动，基于路由备份的AODV协议，而在低级网络层采用实时性强，传输时延较小的DSDV协议。反震结果表明，改进后的路由协议提高了分组达到率，减少了端到端传输延时，提高了Ad Hoc网络的扩展性。

［1］荆文礼.基于AdHoc网络的AODV路由协议的研究与改进［D］.无锡：江南大学，2013.

［2］门福军.AdHoc网络路由协议及性能研究［D］.西安：西安电子科技大学，2006.

［3］彭永祥.无线Adhoc网络路由技术若干关键问题研究［D］.成都：电子科技大学，2013.

［4］倪旻明.移动网络中分簇组网技术的研究［D］.北京：北京交通大学，2012.

［5］徐文涛.一种移动Adhoc网AODV路由协议的改进方法［J］.计算机应用与软件，2013，30（3）：225-228. XU Wen-tao.Improvement of AODV routing protocol in Ad Hoc networks［J］.Computer Applications and Software，2013，30（3）：225-228.

［6］王忠恒，张曦煌.移动AdHoc网络AODV路由协议的改进［J］.计算机应用，2010，30（2）：333-336. WANG Zhong-heng，ZHANG Xi-huang.Improvement of AODV routing protocol in mobile Ad Hoc network［J］.Jounal of Computer Applications，2010，30（2）：333-336.

［7］梁龙.移动AdHoc网络中AODV路由协议的改进［J］.电子测试，2010（4）：8-11，21. LIANG Long.Improvement of AODV routing protocol in mobile Ad Hoc networks［J］.Electronic Test，2010（4）：8-11，21.

［8］王海涛.移动Adhoc网络路由协议及其性能比较［J］.重庆邮电学院学报，2002，14（4）：73-77. WANG Hai-tao.Routing protocols of Ad hoc network& theirs performance comparisons［J］.Journal of Chongqing University of Posts and Telecommunications，2002，14（4）：73-77.

［9］沈奔.无线AdHoc网络中AODV路由协议的研究与改进［D］.南京：南京邮电大学，2010.

［10］MAGNUS Frodigh，PER Johansson.WirelessAd hoc networking-the art of networkingwithout a network［J］.Ericsson Review，2000（4）：248-262.

Research based on the hierarchical structure of the Ad Hoc network clustering routing protocol

FENG Yong-liang
（School of Mathematics and Computer Engineering，Xi'an University of Arts and Science，Xi'an 710065，China）

The traditional Ad Hoc network clustering routing protocol has low packet delivery ratio problem，this paper proposes a clustering routing protocol based on hierarchical structure.The advanced network layer using AODV routing protocol based backup，and the lower network layer adopts a smaller delay DSDV protocol.The simulation results show that the improved routing protocol improves the packet delivery rate，Shortening the end to end delay.

Ad Hoc；AODV；cluster；route；protocol

TN915.04

A

1674-6236（2015）20-0086-03

2015-01-05稿件编号：201501037

冯永亮（1979—），男，陕西西安人，硕士，讲师。研究方向：计算机网络、物联网。