移动Ad-hoc网络分层路由协议综述翻译版.doc

移动Ad Hoc网络分层路由协议综述
Hao Huang Nini Rao
School of Life Science and Technology
University of Electronic Science and Technology of China
Chengdu, PRC 610054
genehuang0123@ raonn@

摘要
在本文中，我们首先讨论MANET（移动Ad Hoc网络）中分层路由
协议的分类方式进而比较它们的不同特点。然后，我们将分析当前层次协
议和比较这些协议。最后，我们预测分析未来的路由协议的设计，并给出
结论。
关键字：MANET网络，Ad Hoc网络，分层路由协议；

1引言

无线网络有很多不同的方案，基本上分为两大类[1]。
第一类被称为“基础设施网络”。如蜂窝无线网络（无线局域网），节点（或用户）通过基站（或接入点）进行相互通信的基础设施网络。基站通常是固定的，可以形成一个固定节点固定网络或移动节点网络的基础设施。当旧基站“切换”到新基站时，移动节点从一个基站范围移动到另一个基站范围内继续无缝通信。
移动无线网络的第二种类型是没有基础设施的移动网络，俗称“移动Ad Hoc网络（MANET）”[2-3]。Ad Hoc网络是没有固定的基础设施，如战场或抗灾救援的情况下，移动Ad Hoc网络相比传统无线网络是更好的选择。Ad Hoc网络通过移动节点或终端之间的自我组织和相互协作，形成一个多跳无线网络，并维持自治系统的方式建立管理无线通道进行快速连接和断开节点之间的通信[4]。因为随着时间的推移，由于节点移动，新的节点出现拓扑结构会有所不同，无线通信将受到较大的影响，如噪声，衰落和干扰。此外，无线连接通常比有线网络的带宽更少。
由于这些网络带来了许多复杂的问题，还有许多已知的特设网络方面的难题等待研究人员去解决。关键问题之一是设计一种高效的路由协议，它允许节点通信，多跳路径和无环路径，并采用自启动和自组织的方式[4]。同时它也可以在数据传输中，花费最少的开销来获得快速收敛，并保持有效的动态拓扑。
当前无线网络的研究方案是越来越重要的关于节点数量的流动性和可扩展性的问题。在无线网络的规模和流动性增加一定的阈值，因为信道和加工开销，当前正常的主动路由方案可能将失效。因此，找到合适方案使可扩展的路由协议的网络可扩展性问题得到解决是非常重要的。分层次的路由[5-13]就是一种目前能够较好解决路由域问题的方案。
在本文中，我们提出的一项调查显示，分层路由是当前针对高密度或高流动性的解决方案的焦点。本次与前期论文[1，14-15]，在系统性介绍方面可能有一些不可避免的重复。为此，我们增加了一些协议的介绍，使之与以往的调查不同。
首先，我们讨论了MANET网络的分层路由协议的分类，然后比较它们的不同特点。下一节将介绍当前的分层路由协议的分类，而后面的一节则是对比这些协议。最后一节讨论设计未来的路由协议的挑战，并给出了本文的结论。

2 Ad Hoc网络路由协议的分类

无线自组网的路由协议有许多种分类方式。其中之一是针对Ad Hoc网络的体系结构进行分类。对于不同的体系结构，Ad Hoc网络路由协议分为三大类[14]。第一种是平面结构的路由协议。它可以进一步分为两大类：主动型和被动型，根据他们的设计理念。在平面结构中，所有结点的地位平等，所以又可以称为对等式结构。通常这类协议采用用距离向量（DV）[16]和链路状态（LS）[17]路由策略作为其基本的路由策略。第二种是分层结构路由。通常的分层路由网络节点分配不同的层次地址，有些协议还需要一个分层寻址系统。平面路由和分层路由协议是最基本最常见的路由协议。第三种是基于位置辅助型路由协议[18-22]。路由要求每个节点配备全球定位系统（GPS）[23]，或使用其他类型的定位服务[24-25]。

3现有的分层路由协议

分层路由的设计分为以下四个部分：聚类算法，簇头选择，簇内路由协议，簇间路由协议。构建层次结构最流行的方式是簇，通过簇构建一些动态网络结构[26-31]。簇通常由簇头和多个簇成员组成。这些簇头形成了高一层的网络，在高一层网络中，又可以分簇，再次形成更高一层的网络，直至最高层。分层结构中，簇头结点负责簇间数据的转发。簇头可以预先指定，也可以由结点使用算法选举产生。为了实现簇头之间的通信，要有网关结点（同时属于两个簇的结点）的支持。分层网络的每个结点都可以成为簇头，所以需要适当的簇头选举算法，算法要能根据网络拓扑的变化重新分簇。不同的路由策略用于内部范围和外部的区域。通过这种灵活性，可以实现高效的路由性能。
由于簇头要做路由管理和维护工作，簇头的通信负荷肯定会高于一个普通节点，它们很容易达到饱和。因此，我们简要介绍聚类算法中重要的三种方案来解决上述问题。第一个方案是基于最高连通性（度）的聚类算法[29，32]。第二个是基于最简单识别（ID）的聚类算法[29，33-35]。第三个是基于最少的簇变化（LCC）的聚类算法[36]。
在基于最高连通性（度）的聚类算法中，度最高的节点作为簇头总是选择在同一簇的相邻节点。每个节点的度是单跳的相邻节点的数目。如果一个节点已经是簇头，那么它作为簇头可以有效作用另一个节点。
在基于最简单识别（ID）的聚类算法中，每个节点都被分配一个独特的ID。ID最低的节点总是选择在同一簇的相邻节点作为簇头。
基于最简单识别（ID）的聚类算法相比基于最高连通性（度）的聚类算法产生较少的簇群变化，簇群将更稳定。这是因为，当节点移动，拓扑结构发生变化时，相邻节点的（度）发生变化的概率是相对较高的[29]。
基于最少的簇变化（LCC）的聚类算法能够解决频繁簇变化问题是有两个条件的。其中之一，是节点位于簇头间有效传输范围内，另一个是节点断开与任何其他簇的连接。与基于最高连通性和基于最简单识别的聚类算法相比，在簇群变化方面LCC算法都优于其他算法。在简单介绍聚类算法的基础上，我们将在下文讨论各种分层路由协议。

3.1分簇路由协议（CBRP）[37]

CBRP协议规定节点只知道周围一跳及两跳节点，并采用最小分簇算法构建网络，维护路由信息。协议规定簇间可重叠或相交，但不允许簇头直接相邻，它们之间的网关节点，每个节点都必须至少有一个簇成员。当需要簇间通信时，按需源路由性质则满足线路需求。路线被发现后，簇通过网关节点数据信息知道链路拓扑结构。要实现这种有限的局部修复机制，需要使用路由缓存。CBRP支持多条线路，并可以使用单向链路和簇间路由。

3.2簇头网关交换路由协议（CGSR）[36]

CGSR使用DSDV的[38]作为底层协议和LCC的集群计划，以形成集群和选举簇头。每个节点维护两个表：集群成员表（记录每个目的节点）和距离矢量路由表（记录簇头的下一跳）。集群成员表周期更新，节点将更新其相邻的一个新的集群成员表中的信息。数据包在簇头和网关之间交替传递。协议计划使用一个序列号，以获得无环路的路线，避免陈旧的路由条目。

3.3分布式动态路由算法（DDR）[39]

DDR是利用路由周期性的消息构建森林的树型拓扑结构。在DDR中，每个树构建森林形成了一个区域。然后，网络被分成一组动态非重叠区。每个节点计算定期独立的区域ID。每个区域连接的节点，不是在同一棵树，但他们在对方的直接传输范围内。因此，整个网络可以看作是一组连接区，移动节点可以在路由器模式或在其树的位置通信。假定每个节点维护路由信息只给那些其区域内的节点，那么就只有其周边区域的信息。

3.4鱼眼效应路由协议（FSR）[40]

FSR的协议引入了依赖于数量的多层次“范围”的概念，从源头上达到减少在大型网络中的路由更新开销。一个节点存储网络中的每个目的地的链路状态。定期广播链路状态更新与频率上跳距离这一目标取决于其相邻的目的节点。在最小的范围内节点被认为是最经常更新的节点，这被认为是更频繁。从状态更新，节点构造整个网络的拓扑图，并计算有效的路线。虽然线路可能因为流动性增加遥远的目的地导致不准确的，但是数据包到达目的节点将更准确。

3.5模糊可视路由协议（FSLS）[41]

FSLS在解决有限的链路状态信息传播的问题上是和FSR类似的。 FSLS包括模糊的标准链路状态路由算法（HSLS）[42]，发送链路状态更新（LSU）每2K*T到2K的范围，其中k是单跳距离和T是最低LSU传输周期。

3.6层次状态路由协议（HSR）[6]

HSR介绍了一种多层次聚类的基础设施。集群中有三种节点：簇头，网关和内部节点。集群可能是物理和逻辑的形式。如果MANET中所有节点形成的物理集群，在HSR中它们是相同的，这是代表一个簇每个集群作为在CBGP或CGSR。如果在底层形成集群的当选簇头，他们成为下一级更高层的成员，这些新成员共再次组织集群等，因此，他们形成了逻辑集群。 簇头是通过虚拟链接，这需要被映射到底层的物理链路连接。每个簇每个群集成员链路状态信息的收集，关于它的邻居节点，和传播其邻居簇头的上级，可能使用网关节点。在较高的水平，同样的情况，与有关虚拟链接，这是从较低级别的链路状态计算的链路状态信息。路线是由各个层面[43]的虚拟链接组成。

3.7大规模网络路由协议（LANMAR）[10，44-45]

LANMAR(Landmark Routing Protocol)是一个指定逻辑子网用于群体移动通信的路由协议。它基于这样一种假设：在大型网络中．有些节点趋向于在一起作为一个群体做相同的运动(比如战场上的一个排)。这样，就可以把节点根据群体的移动性，划分为不同的群组。LANMAR使用类似于IP地址的结构作为地址，包括一个群组ID(或者说子网ID)，一个主机地址。比如说<Group ID,Host ID>。LANMAR使用路标(landmark)的观点来保持逻辑群组的路径。每个逻辑群组有一个动态选定的节点作为一个路标。使用一个全局的距离矢量机制在整个网络中传播关于所有路标的路由信息。进一步．LANMAR协同工作，使用本地范围内的路由方案。这个本地路由方案可以使用常见的主动路由协议，群组内每个节点维持着它的本地范围内的详细拓扑信息和到所有路标的路由矢量。

3.8区域路由协议（ZRP）[46-51]

区域路由协议ZRP引入路由区的概念，每个节点记录在其区域的拓扑结构。它是一种混合协议，它结合了被动和主动的战略。总之，它结合了三种不同的方法进入一个协议的路由。ZRP 的区内路由采用传统的路由表驱动路由算法，支持距离向量和链路状态两种路由策略。节点和其邻居节点之间通过周期性的交互路由表获得到区内各节点的最新路由。相比之下，区域间路由协议（IERP）采用按需方式，适应现有的被动路由协议，在区间路由维护中当节点需要使用的链路断开时，节点选择通知源节点或进行局部查找路由，其局部查找方法和区间路由协议中的路由查找相同，只是查找的范围小。此外，区域半径设置将直接影响路由的效率，因此如何根据网络的实际通信环境设置一个最佳的区域半径是决定 ZRP 效率的一个重要因素。

4分层路由协议的比较

表1表示了上述的分层路由协议的特点。时间复杂度被定义为需要执行协议的操作步骤数。这些指标值代表最坏的情况。
CBRP，CGSR和高铁是明确的分层协议。指定的路线，去，通过clusterheads和网关节点，这样的路线并不总是OPTIM人。 clusterheads和网关节点是哪条路线必须经过的关键节点。 LANMAR地标也为他们收集的地标和链接状态在本地组之间的距离向量的关键节点。相反，DDR，FSLS（FSR），LANMAR和ZRP代表他们作为隐式​​的分层协议。DDR和ZRP计算他们的路线基础上的区域概念。 FSLS和FSR计算他们的路线基础上的概念的范围。 LANMAR计算簇不同的概念，这是具有里程碑意义的路线，因为路线并不需要去通过具有里程碑意义的。对于主动路由算法，其时间复杂度是O（四）在最坏的情况。与主动路由算法的异常，解除武装，复员和重返社会和IERP代表他们的时间复杂度是O（2D）作为反应的路由算法[1]。
在我们上面提到的路由协议，LANMAR非常适合在大型无线自组网在群体行为适用于高铁，尤其是巨大的，因为其升层次的无线自组网，通过层次化的地址方案设计提供了一个高效，可扩展的路由解决方案。

表1分层路由协议的特点

5挑战和结论

目前Ad Hoc路由方法引入了几个新的范式，如质量，服务质量（QoS）路由，功率感知路由，安全路由[52-54]。相反路由协议的仿真环境，一个真正的测试平台énvironment将给路由协议更实际的估计。随着越来越多的新的无线技术和设备的发展，各种应用将迫使所有异构的有线或无线网络的融合。混合路由方案是目前主要的研究组在世界上的时间表。这对分层路由协议的无线自组网设计的一大挑战。我们仍然有很多工作需要做的事的可扩展性，服务质量，能量感知和安全出口或新开发的分层路由方案。
在本文中，我们提供几个特设移动网络的分层路由方案的说明。根据各自的特点，差异和特点，我们还提供了这些计划的分类。我们已经确定了CH可伸缩的特设移动无线网络面临的allenges。没有协议出现的所有场景的赢家。每个协议都有其优点和缺点。在此同时，所有提到的计划适合不同的应用程序。