树路由算法

树路由算法（精选7篇）

树路由算法 篇1

0 引言

近年来，无线传感网络（Wireless Sensor Networks,WAN）作为物联网的关键技术之一，成为当前的研究热点。为此，涌现了一批无线传感网络协议，如ZigBee、蓝牙、超宽带和无线USB等等。由于ZigBee是基于IEEE 802.15.4[1]标准的低速率、低功耗、低成本、低复杂度、高安全性、自组织、可拓展的无线个域网协议，Zig Bee网络已被广泛应用于诸多领域，如楼宇自动化、智能家居、保健、智能能源、电信和零售服务等[2,3,4]。

ZigBee协议的物理层（PHY）和媒体接入层(MAC)是由IEEE 802.15.4定义的，在此基础上，ZigBee联盟制定了ZigBee协议的网络层和应用层，由此组成了ZigBee标准协议。在ZigBee协议网络层[5]中定义了基于分层地址分配的ZigBee树路由（ZTR）算法和基于路由表的AODVjr路由算法。由于ZTR算法无需路由表和路由发现过程，在内存资源有限的设备中，有着广泛的应用。但是ZTR必须遵循树型拓扑结构的基本限制，从而导致跳数多，上层节点能量消耗过快等问题。针对以上问题，戚剑超[6]和刘丹[7]等提出利用邻居表来减少ZTR算法跳数多的问题，但当在目的节点是转发节点的子节点时，都选择将数据包按树型结构向下发送给相应的子节点，改进后算法一定程度上减少了路由跳数，但效果并不显著。尚雪辉[8]和Atefeh Khatiri[9]等提出了综合跳数、节点能量消耗和链路质量的节点选择优化函数，转发节点计算所有邻居节点的函数值，将有最优解的邻居节点做为下一跳节点，这种方法虽然综合了三种因素，但也正是由于这个原因，函数并不能保证向目的节点收敛，结果导致算法丢包率过高。Saeyoung Ahn[10]等提出了目的节点家庭组（Destination Family Group）的概念，将目的节点的父节点，子节点，隔代父，子节点看做一个家庭，基于此概念提出了Destination Family Group-Tree Routing(DFG-TR）算法。该算法在转发节点的邻居表中没有目的节点的情况下，继续寻找目的节点的家庭成员作为其下一跳节点，以此达到减少跳数的目的。但是该算法只是考虑了邻居节点中存在目的节点家庭成员的特殊情况，在减少跳数和节约能量方面的效果并不明显。本文对ZTR算法进行深入研究，通过对ZTR算法的改进，提出了快捷树路由（Shortcut Tree Routing,STR）算法并对其进行了算法仿真与分析。

1 ZigBee的网络块地址分配和块寻址方法

ZigBee支持星型，树型和网状型三种网络拓扑结构，其结构如图1所示。另外在ZigBee协议中，还定义了两种节点类型，即全功能节点(FFD)和精简功能节点(RFD)。FFD有路由功能，可以作为网络的协调器和路由器并拥有子节点，而RFD没有路由功能，只能作为终端节点。同时，ZigBee协议还定义了最大网络深度Lm，最大路由节点数Rm和最大子节点数Cm三个基本参数。

ZTR算法的实现，主要依靠其基于Cskip值的块寻址分配方法[11]。在ZigBee协议中，每个节点都会由其父节点为其分配一个唯一的16位网络地址。每个节点可以利用自己的网络地址计算得到自己的网络深度和其子节点的地址范围。Cskip(d)是网络深度为d的父节点为其子节点分配地址的偏移量，它可以由Lm、Rm和Cm计算得到，即：

地址为Aparent的父节点为其接收的第n个作为路由器节点的子节点分配的网络地址为：

为其接收的第n个作为终端节点的子节点分配的网络地址为：

另外，ZigBee协议中规定，协调器节点的网络地址为0，其网络深度为0，是所有网络节点的根节点。基于以上块地址分配方法，建立的分层树型结构，使每个节点都可以计算出目的节点是否自己的子代节点。例如，当一个节点的网络地址为A，其网络深度为d，目的节点的网络地址为D，如果目的节点满足公式(4):

就可以确定目的节点为该节点的子代节点，按照公式(5):

选择下一跳节点N，否则将数据包发送给其父节点。

2 ZTR算法分析

ZTR算法是以树路由（Tree Routing,TR）算法[12为基础加以改进的，ZTR算法的主要缺陷实际上是TR算法缺陷的延伸。TR算法在选择下一跳的转发节点时，仅仅考虑了节点之间的父子关系，如图2(a)所示，即使目的节点在源节点的1跳范围内，因为目的节点和源节点不存在子节点或者父节点一类的关系，数据包依然通过分层树结构进行转发。这不仅造成了网络能量的极大浪费，也会导致网络深度越低的节点能量消耗越快。

ZigBee协议为解决数据包传输过程中的迂回问题，引入了邻居表和直接传输原则。邻居表中存放了每个节点1跳范围内的网络节点。ZTR算法在转发数据包前会检索自己的邻居表，如果目的节点是自己的邻居节点，转发节点会将目的节点作为下一跳节点。否则，ZTR算法将按树型结构的父子关系进行数据包的转发。ZTR虽然利用邻居表进行了改进，仍然存在数据包跳数多，上层节点能量消耗过快的问题，如图2(b)和图2(c)所示，当目的节点在转发节点1跳范围之外时，仍然存在数据包迂回问题。

3 快捷树路由（STR）算法实现

利用源节点或转发节点的一跳邻居表，本文提出的STR算法可以有效的解决ZigBee树路由的迂回问题和上层节点能量消耗过快的问题。当邻居节点不存在目的节点时，该算法会选择邻居节点中具有到达目的节点最小树路由跳数的节点作为下一跳节点。如图2(b)所示，STR算法计算所有邻居节点到达目的节点的树路由跳数，然后选择跳数最小的N4作为下一跳节点，然后由N4将数据包发送给目的节点。

在TR算法中，一个数据包总要由源节点或转发节点向上传到它和目的节点的公共父节点，再由公共父节点向下传到目的节点。STR算法的主要思想是，利用ZigBee的分层树型结构和块地址寻址方法，可以计算得到任意节点到目的节点的分层树路由跳数。换言之，可以计算任意节点和目的节点的网络深度和它们的公共父节点。

当源节点或转发节点和目的节点在同一个树型分支上，即两个节点有直接的父代和子代的关系时，可以直接用两个节点的网络深度值相减，其绝对值就是任意两个节点之间的树路由跳数L。另外，当两个节点不在同一个树型分支上时，必须求得其最底层的公共父节点，才能算得这两个节点之间的树路由跳数。首先计算转发节点的网络深度dA，然后将该节点看做是目的节点，通过公式(5)，从根节点协调器开始计算出该节点在每层树型结构的父系节点，记作集合A。通过同样方法计算出目的节点的网络深度dD和父系节点，将其父系节点记作集合D。通过A和D的交集就可以求出两个节点的所有公共父节点，按照ZigBee树路由的地址分配方法，交集中，地址值最大的即是要求的最底层的公共父节点。

求得转发节点和转发节点的最底层公共父节点后，可计算得到公共父节点的网络深度dC，通过公式(6):

就可以求得任意转发节点到目的节点的树路由跳数。

在STR算法中，就是通过上述方法，在源节点或转发节点的邻居表中不存在目的节点时，调用自己的邻居表，分别计算出每个邻居节点到目的节点的树路由跳数，把跳数最少的邻居节点作为下一跳节点N。如果存在最小跳数相同的节点，则选择能量剩余较多的节点作为下一跳节点。STR算法的流程如图3所示。

4 仿真实验结果

为评估STR算法的性能，在MATLAB中分别对TR算法、ZTR算法、DFG-TR算法和STR算法进行了算法仿真。重点通过数据包传输所用的跳数、网络能量消耗的均衡性、和整个网络的寿命来做对比，仿真结果表明，STR算法有效改善了ZTR算法的迂回问题和其上层节点消耗过快的问题。

仿真实验模拟设计了一个100×100m2的网络区域，设定网络节点的最大传输范围为20m，且每个节点的位置是随机给出的。这样形成的ZigBee网络具有一般性。另外，为了使形成的ZigBee网络具有一般性，网络的其他参数如下：Cm=4,Rm=4,Lm=6。仿真实验中每个节点基数的实验进行3次，记为一组，将3次实验的结果取平均，记为该节点基数的实验结果。仿真实验从32网络节点开始进行试验，每组实验结束，将节点增加32个再进行实验，直至节点增加至224个。仿真共进行了组，即21次实验。实验结果如图4、图5所示。

图4是各不同算法发送200个数据包和其需要的总跳数之间的关系图。有图可以看出，STR算法所需跳数对ZTR算法有明显优势，相比DFG-TR算法也有较大提高，而且优势随着网络节点的增多有扩大的趋势。在网络中有224个网络节点时，STR算法比ZTR算法所用的总跳数减少了25%，比DFG-TR算法减少了19%。

图5是各不同算法由于能量耗尽出现第一个死节点时，其发送数据包的总个数相对于TR算法所发送数据包的相对倍数。从图中可以看出，ZTR算法和DFG-TR算法相对于TR算法的优势很小，且随着网络中节点数目的增加，优势越来越弱。相反，STR算法不仅优势明显，而且随着网络节点数目的增加，优势越来越明显。

另外，在仿真中，除STR算法外，其他算法第一个耗尽能量的节点通常为协调器，即网络的根节点。而STR算法在多数情况下，耗尽的节点为靠近协调器的节点，这是STR算法能量消耗更均衡的表现。

5 结束语

针对树型结构中数据包的迂回问题和节点能量消耗不均匀的问题，提出了STR算法有效利用邻居表和ZigBee协议中的块地址寻址进行了改进。从仿真结果看，STR算法降低了网络的路由跳数并均衡了能量消耗。尤其适用于节点密度大，个数多的无线传感器网络。例如在对畜禽舍、化工厂和矿井中温湿度、氨气、硫化氢和甲烷等环境因子进行监控时，可以解决根节点及上层监控节点由于网络能量消耗不均匀导致其能量消耗过快的问题并延长监控网络的使用寿命。

参考文献

[1]郦亮.IEEE 802.15.4标准及其应用[J].电子设计应用,2003,(1):14-16.

[2]Han Dae-Man,Lim Jae-Hyun.Smart Home Energy Management System Using IEEE 802.15.4 and Zig Bee[J].IEEE Transactions on Consumer Electronics,2010,56(3):1403-1410.

[3]Chen Shyr-Kuen,Kao Tsair,Chan Chia-Tai et al.,A Reliable Transmission Protocol for Zig Bee-Based Wireless Patient Monitoring[J].IEEE Transactions on Information Technology in Biomedicine,2012,16(1):6-16.

[4]Yi Peizhong,Iwayemi Abiodun,Zhou Chi.Developing Zig Bee Deployment Guideline under Wi Fi Interference for Smart Grid Applications[J].IEEE Transactions on Smart Grid,2011,2(1):110-120.

[5]刘丽钧,童丽丽.Zig Bee技术网络层的路由算法分析[J].计算机与信息技术.2008,(1):70-72.

[6]戚剑超,魏臻.Zig Bee树型路由算法的改进[J].合肥工业大学学报(自然科学版).2010,33(4):529-532.

[7]刘丹,钱志鸿,刘影.Zig Bee网络树路由改进算法[J].吉林大学大学学报(工学版).2010,40(5):1392-1396.

[8]尚雪辉.基于Zig Bee技术的热计量表物联网路由协议研究[D].秦皇岛:燕山大学,2012.

[9]Atefeh Khatiri,Ghasem Mirjalily,Ahmad Khademzadeh.Energy-efficient Shortcut Tree Routing in Zig Bee Networks[A].Fourth International Conference on Computational Intelligence,Communication Systems and Networks[C].2010.

[10]S.Ahn,D.Ko,B.Kim,S.Lee,S.An.Energy-efficient Tree Routing Algorithm-based Destination Family Group in Zig Bee Networks[A].Fourth International Conference on Sensor Technologies and Applications[C].2010.

[11]薛艳亮,胡建萍,王江柱.基于分布式编址机制的Zig Bee组网技术研究[J].杭州电子科技大学学报.2008,28(2):33-36.

树路由算法 篇2

水声通信网( UACN) 是在一定水下区域内,通过固定或移动传感器节点获取水下信息,并对节点进行声学通信和组网,再以无线形式将信息传送到岸上控制中心的智能网络[1,2]。这是当前唯一可在水下进行远程信息传输的通信形式,且在军事、环境、能源、自然灾害防治等方面均已表现出良好的应用潜力,因此受到了普遍重视与高度关注[3]。同时,又随着物理层MIMO技术的日益成熟,近年来的水声网络也相应获得了长足的进步和可观的发展[4,5,6,7,8]。

如今,UACN主要采用按需路由算法及其相应的改进算法。具体来说,文献[9]提出了无线自组网按需距离矢量( AODV) 路由算法。该算法使用目的序列号来防止路由死循环。但是,AODV通过采用洪泛寻路和HELLO消息来维护路由,却造成了过多的控制开销。同时,还有文献[10]结合AODV算法和地理位置路由算法,提出了一种定向搜索( DSAODV) 路由算法。该算法利用地理位置信息约束请求分组RREQ查找的范围,使得RREQ只在最优的路径方向上传播,从而减少了网络拥塞和路由开销,并提高了网络吞吐量。但是,DSAODV算法通过节点的位置信息和网络节点疏密来设定和计算转发角度,则需要水下定位技术的支持,因此限制了其应用。上述算法在广播寻路分组RREQ的过程中均使用了洪泛操作,导致了冗余开销。更重要的是,这些算法在建立路由时并未考虑节点能量的均衡,这就明显影响了算法的效率和网络的寿命。此外,文献[11]则提出了一种基于均衡网络业务的拓扑优化控制路由算法,综合考虑了节点的剩余能量、网络业务量和边缘路径条件,从而降低了节点的能量消耗,避免了网络节点过早死亡,进一步提升了网络吞吐量,而且也延长了网络寿命。但是,该算法选择剩余能量较多的节点来转发数据,而未考虑网络的平均剩余能量,因此上加重了某些节点的负载量,容易造成网络拥塞。基于此,又有文献[12]提出一种 按需多播 树路由算 法( MAODV) ,可以支持各种密切协作的应用业务,有效节省了带宽资源,且对于每一个数据分组均有着更好的整体控制和传输能力。但是,MAODV对于频繁变化的网络拓扑结构,其分组投递率将会下降; 同时,节点通过全网广播加入多播树,也随即增加了网络开销。综合以上分析,本文拟提出旨在改善网络整体 性能的一 种基于能 量均衡的 混合树路 由( HTREB) 算法。通过建立混合树网络拓扑图,采用洪泛抑制,综合考虑平均剩余能量( 优先使用剩余能量均方差较大的节点) 来进行路由查找,由此而减少控制分组的转发,并均衡节点能量,以最终获得网络整体性能的提升。

1 网络模型

将水声网络抽象为数学模型: G = ( V,L) 有向图,其中,V表示所有节点的集合,且V = { S} ∪Vm; S表示水面网关Sink节点,Vm表示所有水声传感节点的集合,m≥1; 所有无线水声对称双向传输链路的集合L = { l1,l2,···,ln} ,ln表示网络中第n条链路; 具体地,链路的代价可以是链路长度( 跳数) 、数据传输的时延花费等。

1. 1 能量模型

本文能量消耗模型[13]为: 当节点A向与之相距d的节点B发送k bit的信息时,A消耗的能量由两部分组成,分别是: 发射电路损耗和功率放大损耗。即:

式中,Eelec表示节点发送k bit信息的发射电路损耗,d0表示功率放大损耗的距离阈值,d则表示节点间的通信距离。若d < d0,功率放大损耗以自由空间模型进行计算; 若d≥d0,则需依据多径衰减模型相应计算。另外,Efs和Emp分别表示自由空间模型、多径衰减模型功率放大器的能耗因子。而且,节点接收k bit信息所消耗能量为:

1. 2 问题描述

网络中信息的发送、转发和接收均需要消耗节点的能量,因此,UACN网络路由算法将遵循如下准则来进行能量优化: 减少不必要的开销,降低节点的能量消耗; 均衡网络的能量消耗,避免部分节点过早死亡。但是,现有的UACN网络按需路由算法却存在两个问题,具体分析如下:

( 1) 源节点广播RREQ以及中间节点转发无效RREQ,产生了大量冗余的RREQ信息,而这些冗余RREQ信息的收发增加了网络开销,进而增大了k值,就造成了节点的能耗加剧。

( 2) 数据传送选路时没有考虑节点的剩余能量均方差因素。若当前节点没有足够的剩余能量,而仍承担转发数据的任务,就会因过度使用而造成电池提前耗尽,由此导致路径的断裂,影响网络通信。

1. 3 能量均衡的混合树路由算法设计

针对UACN网络现有的按需路由算法在寻路开销和节点能耗等方面的不足,本文提出一种基于能量均衡的水声通信网混合树路由算法—HTREB。HTREB算法采用洪泛抑制的优化路由建立方式,减少部分控制分组的转发; 而且使用节点距离和剩余能量均方差作为选路标准,进而达到能耗均衡效果。

1. 3. 1 HTREB 算法描述

HTREB算法包含邻节点信息的收集与反馈,路由建立及数据转发两个阶段。下面给出每一阶段的具体实现过程。

( 1) 邻节点信息的收集与反馈阶段

信息收集: 节点定期向一跳范围内的节点发送HELLO分组,接收到HELLO分组的邻居节点获知其可视邻居区内节点的网络地址等信息。

信息反馈: 节点向其父节点及节点与邻居节点深度最大的公共父节点反馈自己收集的可视邻居信息。

( 2) 路由建立阶段

步骤1: 当源节点有数据发送时,会首先查询路由表中是否缓存了到目的节点的有效路由。如果是,则使用此路由发送数据分组。否则,将转为步骤2,即源节点开始路由查找过程。

步骤2: 源节点欲加入到多播组,则需查找多播路由表中是否可获得父节点信息。如果获得,则选择下一跳单播RREQ到父节点,否则,即向邻居节点及所在分支树的邻居节点的子节点多播RREQ请求分组。

步骤3: 中间节点收到RREQ分组,执行以下过程:

1判断该RREQ的序列号是否大于自己路由项中的序列号或者RREQ的跳数是否小于TTL( Time To Live) 阈值。如果是,执行2,否则删除该RREQ分组。

2若当前节点是源节点的邻树枝节点,则转步骤2处理该RREQ; 若当前节点是源节点的子节点,则判断当前节点及其子节点是 否有邻树 枝节点。如果 有,则向其多 播RREQ,否则,删除该请求; 若当前节点是目的节点的父节点或子节点,通过计算判断自己到目的节点的跳数加上RREQ中的TTL值是否小于TTL阈值。若是,就沿着树路由路径转发该请求直到目的节点,若不是,将删除该请求。

3若当前节点是源节点的父节点,但不是源节点和目的节点的公共父节点,也不是源节点和目的节点的最大深度公共父节点的子节点,则转步骤2处理该请求; 而若当前节点是源节点和目的节点的最大深度公共父节点的子节点,即需判断当前节点是否有邻树枝节点或与源节点不同树枝的子节点。若为有,则向其多播该请求,否则,就删除该请求。

步骤4: 源节点发送的RREQ请求到达目的节点时,如果RREQ历经的跳数未超过TTL阈值,则单播路由回复RREP至源节点。中间节点收到RREP后,更新RREP中相应字段的值,而后沿RREQ传播时建立的反向路径发送RREP给邻节点。源节点收到RREP后,存储链路权值、跳数等信息,完成正向路径的建立。

1. 3. 2 路由度量新指标—链路权值

在HTREB算法中,提出一种新的路由度量指标—链路权值( Link Weight) ,用于在节点收到不同的路由响应时,优先选择距离更远、剩余能量均方差更大的节点参与路径建立。链路权值ωc定义为:

式中,k1和k2是可变参数,k1+ k2= 1; di表示节点i与同树枝源节点之间的距离,dj表示节点j与不同树枝源节点之间的距离( 0 < i≤m) ,m为同类节点数( 0 < j≤n) ,n为不同类节点数; E0是节点初始能量,Er是节点剩余能量均方差。

2 仿真与分析

2. 1 仿真统计量

仿真统计量涉及网络开销、端到端平均能耗、网络生存期、数据分组平均端到端延时和分组投递率。其中,网络开销是网络中所有节点发送和转发的控制分组比特数和到达目的节点的数据分组比特数与目的节点成功接收的数据分组比特数的比值。端到端平均能耗将具体定义为网络中单个节点能耗与所有节点平均能耗的均方差值。而且,网络生存期即是网络的运行时间。当死亡节点的数量大于等于网络总节点数30% 时,判定网络运行截止。在此,数据分组平均端到端延时就是网络中所有数据分组从源节点到达目的节点所消耗的时间与成功接收数据分组个数的比值。分组投递率则指网络中目的节点成功接收的数据分组数与源节点发送数据分组数的比值。

2. 2 仿真参数设置

仿真实验使用OPNET 14. 5作为软件平台,主要仿真参数设置如表1所示。本文采用由一个网关节点和若干个信息采集节点组成的UACN网络模型,网关节点在场景中心,传感器节点随机均匀分布在网关周围。水下节点物理层采用文献[14]设置的水声信道模型,定义节点的能量都是有限且均为10 J初始能量; 当节点剩余能量低于0. 5 J时,判定节点死亡; 当网络中死亡节点数高于30% 时,网络生存期结束。

2. 3 仿真结果及分析

图1为网络开销比较,与AODV算法相比,HTREB算法能够有效减少网络开销8. 08% ( 50节点数) ~ 29. 32% ( 110节点数) ; 与MAODV算法相比,HTREB算法减少网络开销0. 01% ( 50节点数) ~ 20. 76% ( 110节点数) 。主要原因在于,AODV算法节点存储的路由信息较少,通常使用广播RREQ的方式来进行路由查找以及周期地发送HELLO控制分组来维护路由,如此将导致网络开销过大; MAODV算法和HTREB算法通过发送RREQ路由请求或者查找邻居表来建立数据传输的多播树,避免了全网洪泛查询,同时又减少了控制分组的转发次数; 且HTREB算法在寻路过程中利用路由跳数抑制RREQ的洪泛深度,而且通过相邻树枝的节点信息找到优化路径,减少RREQ的转发,从而进一步降低了网络开销,获得了更高效率。

图2为端到端平均能耗比较。与AODV和MAODV算法相比,HTREB算法降低端到端平均能耗分别为4. 70% ( 50节点数) ~ 19. 86% ( 140节点数) ,2. 50% ( 50节点数) ~15. 53% ( 140节点数) ,说明HTREB算法节点的能耗偏离网络平均能耗的程度更小,能量消耗也更为均衡。主要原因在于,AODV算法中,部分中间节点转发数据分组较多,节点能耗偏大,而某些通信量较小的节点,能量消耗将会偏小。因而导致网络中节点能耗速率不均衡,端到端平均能耗较大;MAODV算法则通过建立的树路由限制RREQ的洪泛,减少了网络中冗余的RREQ转发,但在寻路时因未考虑节点当前剩余能量,而过度使用剩余能量均方差较小的节点转发数据分组,另有些剩余能量均方差较大的节点却较少地转发数据分组,由此导致网络中节点能耗不均衡; 相应地,HTREB算法即使用链路权值较小的节点作为下一跳,减轻了距离近的“热区”节点的数据分组转发任务,且使其能量消耗速率得到缓解,这就避免了剩余能量均方差较小的节点过早死亡,从而均衡了网络节点能耗; 同时又采用了短跳代替长跳传送分组,节点耗能减少,端到端平均能耗也随即更小。

网络生存期的仿真结果如图3所示。图3显示,与AODV和MAODV算法相比,HTREB算法至少能够延长网络生存期分别为29. 61% ( 20节点数) ,11. 52% ( 20节点数) 。这是因为在AODV算法中,数据分组经常沿着某一条路径到达目的节点,造成部分节点承担较大的负荷量,消耗能量更多,节点死亡就越快; 而MAODV算法则广播RREQ分组寻找最短路径生成多播树,并沿树路径发送数据分组。但是MAODV在建路时却未考虑节点当前剩余能量,若剩余能量均方差小的节点继续转发数据,则会加速节点的死亡,甚至网络拓扑的分裂; 另外的HTREB算法源节点比较不同路径的链路权值,选择距离远、剩余能量均方差较大的节点,即权值较小的路径建立路由,因而延缓了负荷重的节点死亡,使网络中节点能耗更加均衡,藉此延长了网络生存期。

数据分组平均端到端延时的仿真结果如图4所示。在图4中,与AODV算法相比,HTREB算法能够有效降低分组平均端到端延时30. 58% ( 110节点数) ~ 71. 63% ( 20节点数) ; 与MAODV算法相比,HTREB算法分组平均端到端延时降低1. 47% ( 50节点数) ~ 16. 75% ( 20节点数) 。主要原因在于,当一条链路断裂,AODV算法需要重新发送RREQ查找路由,且数据分组总是沿着单播路由进行转发、直至到达目的节点,当网络通信业务增大时,容易引起信道冲突,并增加延时; MAODV算法则是通过RREQ分组寻路建立多播树,限制了RREQ的转发次数,因而利于数据分组在树路由节点上的快速传送,并使得时延获得了有效降低; 而HTREB算法却借助相邻树枝节点信息进行RREQ寻路,缩短了路由建立时间。且HTREB优先选择链路权值较小的节点进行分组传送,如此既平均了业务流量,又避免了网络拥塞,进而使得分组平均端到端时延进一步减少。

3 结束语

本文提出的HTREB路由算法,采用树路由的单、多播代替广播,限制RREQ分组的转发,并利用邻居节点信息建立路由,在一定程度上减少了网络开销; 同时,综合节点的距离和剩余能量均方差两种因素形成链路权值ωc,且将其引入路由参照标准,由此实现节点能量均衡。具体到理论分析及仿真结果即都表明,与AODV和MAODV算法相比较而言,HTREB算法在网络开销,端到端平均能耗,网络生存期和平均端到端延时等方面的性能均已得到了有效改善,因而获得了较为理想的现实研究效果。

摘要：水声通信网在军事、能源、自然灾害预防和处理等方面均具有巨大的应用潜力。针对当前水声通信网按需路由算法存在网络开销大、能量不均衡的问题,提出了旨在改善网络整体性能的HTREB算法。通过采用洪泛抑制与优先使用剩余能量均方差较大的节点进行路由查找,来减少控制分组的转发,并均衡节点能量。基于Opnet软件进行了仿真。结果表明,与现有按需路由算法相比,HTREB算法降低了网络开销8.08%~29.32%、端到端平均能耗4.70%~19.86%、平均端到端延时30.58%~71.63%,延长了网络生存期29.61%以上。因此,HTREB算法明显改善了系统的整体性能。

路由器的构造及路由算法的研究 篇3

关键词：网络时代,路由器构造,路由算法

1 路由器的构造

路由器是组建互联网的重要设备，路由器和PC机非常相似，有硬件部分和软件部分组成，只不过它没有键盘、鼠标、显示器等外设。IOS是路由器的操作系统，是它的软件组成。路由器是第三层设备，通过运行路由协议了解整个网络的路由情况，并建立一个指示路径的路由表。当用户数据进入路由器后，路由器根据接收到的数据包包头中的第三层地址信息，查阅路由表，把数据从一个接口交换到另一个接口。

1.1 中央处理器（CPU)

和计算机一样，路由器也包含中央处理器。路由器的处理器负责许多预算工作，比如维护路由所需的各种表项以及做出路由选择等。路由器处理数据包的速度在很大程度上取决于处理器的类型。某些高端的路由器上会拥有很多个CPU并行工作。

1.2 内存

在路由器中，主要有以下几个类型的内存：1)只读内存(ROM);2)随即访问内存(RAM);3)闪存(FLASH);4)非易失性内存 (NVRAM) 。

1.3 接口（Interface)

路由器的接口是配置路由器的主要考虑对象之一，同一台路由器上不同接口的地址应属于不同的网络。路由器通过接口在物理上把处于不同逻辑地址的网络连接起来。这些网络的类型可以相同，也可以不同。路由器的一些接口是ISDN接口、串行接口，它们通常将路由器连接到广域网链路上;还有一些是局域网接口(LAN接口)，例如Ethe rne t、令牌环网和FDDI等。

1.4 路由器的软件

如PC机一样，路由器也需要操作系统才能运行。路由器的操作系统叫做IOS (InternetworkOperating System)。路由器平台不同、功能不同，运行的IOS也不尽相同。

2 路由器算法

2.1 硬件算法

目前使用最多的硬件实现方法是使用CAM (Content Addressable Me m ory)内容可寻址存储器，它是一种特殊的存储器件，用来实现路由表查找的一种硬件方法。CAM的最大特点是能够在一个硬件时钟周期内完成关键字的精确匹配查找。为了能够实现最长前缀匹配，一个CAM表存放一类定长的前缀集。IPV4下需要32个CAM。这种方法有一个明显的缺点，在对地址前缀长度具体分配没有准确的了解之前，为了能够保证存储N个前缀表项目，每个CAM都要有N个表项的空间，因此，CAM存储空间的利用率大大降低了。

另一种基于硬件的改进CAM算法是基于TCAM(三值CAM)的算法。在进行搜索的时候，所有的TCAM项都需要同时进行匹配，在有多个匹配项时，TCAM规定在所有匹配的表项中选取地址最低的表项作为最后的结果。因此，为了能够进行最长前缀路由的查找，就需要保证在TCAM的低地址区域存储前缀路由项，而在高地址区域存储短前缀路由项。TCAM具有速度快、实现简单的优点，但它也具有几个不足之处：1)单位比特昂贵;2)容量小;3)并行匹配导致功耗很大;4)更新复杂。

2.2 软件算法

IP路由要求查找最长匹配的前缀地址，因此树形结构的路由查找算法将最长前缀匹配查找模型话为一棵二进制树的过程。用Trie表示前缀并不存储在Trie的结点中，而是用结点间的路径表示前缀，一般规定一个结点到其左子结点的路径表示前缀中的对应比特为0，结点到其右子结点的路径代表前缀中的对应比特为1。IPv4中地址长度为32，所以二进制trie树的深度为32层，前缀长度即子网掩码长度为L的网络路由会被存放在第L层的结点中。二进制trie树算法一次更新操作只需要首先查询定位并修改一个结点，开销较小，它的最大不足在于查找过程中要进行大量的存储访问，对于IPv4地址查找最多需要32次，IPv6地址为128次。

树路由算法 篇4

一般来说。路由包含着两个方面的功能, 一方面是对在搜集过程中的网络状态进行着不断的更新与整理。另一方面则是对已经搜集到的信息计算可行路。当前存在的很多的协议都是为了给目标地址搜寻最适合的短路。具体的过程是当数据包传送至路由器时, 路由器就会根据其数据的属性以及相关信息进行及时处理和分析。然后在进行科学的发送。由于目前比较热门的话题就是研发智能路由器, 如果在研发路由器时能够有具有某种能力的平台或媒介, 当给出的一组输出路线的数据包到达时, 接着根据资源管路系统中的信息, 就能够使路由器自己判断出这组线路中哪一条线路能够最先使用, 然后将数据包进行科学化的整理和归纳, 最后的一个步骤就是等待上传。整个路由过程是一个随着外界环境变化以及需求变化的一个系统, 所以要对整个路由算法进行及时的调整, 以保证整个信息的时效性与完整性。

2 Qos路由

一个比较完整而且较为系统的三元组所界定实时信息的产生。其包括最大信息尺寸, 最大信息速率以及最后一个最大突发信息数, 其实质是一个简单的模型控件, 而相对来说, 在每次模型连接的过程中, 一般都会有两个相对的约束, 第一个是在一定时间t的间隔中, 所达到的信息数一般不超过Bmax+t Rmax;第二个是每个信息的长度一般不超过Smax。因此在此基础上, 如果只是单方面的采用一个估算值来对实时信息就行分析与计算, 就会出现延迟以及不准确的情况。我们针对不同网络的运行情况, 给出了以下路由的算法:

在目前网络科技还不够发达的情况下, 为了根据实际情况的需要, 就应该建立起一个相对连接较少的通信量。简单得到可以表述为:若t点希望与dest点建立连接Mk+1.在点i的积极出狐集A中路由器现则最先空闲的路线A, 通过a上建立的Mk+1来计算出所需要的时间, 即rk+1, 如果计算结果不超过预定的边界值D, 连接请求信息被放于卢新A发热环城区内以等待发送。当然在此过程中, 连接请求信息包括:谜底地址、最大信息储存、信息到达最小间隔、端到端延迟边界、请求过时时间。当一个中间点A收到连接建立请求时, 首先需要确定信息是否已经超时, 如果采用A作为目的点, 就应该调用search-one来做出回答, 相反, 若不是采用A作为目的点, 我们就应该采取相对应的措施来对信息进行更加深入的加工与处理。通过上述的算法来计算发送信息传输的时间, 如果在同一延迟边界的条件下, 当期望值小于或等于最短路的传输时间, 这种连通率的算法远远超过了最短路的算法。

3 多路路由算法在Qo S路由中的应用

1) 随着社会网络技术变革所带来的转变, 分布式多媒体的广泛应用, 在局域网或者广域网上进行语音、视频等实时信息的传输等的要求, 都给目前网络技术的研究提出了新的挑战, 就拿因特网来说, 同一个会话的数据包就能够有不同的路径达到同一个目的地, 虽然这种结果具有一定的合理性与科学性, 但在实际运用中远不能满足目前多种数据类型的综合服务的要求。因为数据包会因为多种不同上网因素造成一定的延迟, 导致的结果是到达目的地是错乱的, 因此信息的质量不仅得不到保障, 而且对整个信息网络的系统话都会带来很大的影响。一般来说, 在网络信息之间的服务质量通常是来表达服务者和使用者之间在数量或质量上有定义性的约定, 即一次连接的服务质量一般都是受着一系列的约束条件所限制的。最为常见的就是宽带约束、延迟约束以及抖动约束。在这种情况下, 寻找服一条资源可靠而且合理的可行路, 是非常有必要的。

2) 近年来, Qos路由已经已经被越来越多的人所关注, 很多新颖的具有创造性的算法被提出, 多路路元就是其中一个典型的算法, 也是在路由算法中一个发展趋势相对来说比较不错的路由算法, 但是其主要针对的是网络流量较少的情况。这也就是说, 多路路由存在的最为主要的任务就是更好的去实现网络信息数据承载的平衡性, 把流量分布得更加均衡, 这样就会增加路由未来连接请求的连通率, 并且能够使没有经过Qos保证的数据也有更充足的回应时间。除此之外, 如果整个网路的信息负载量过大, 同时还在不断的变化, 就能够把多路路由器的算法分成三类。其中, 最为常见的就是PNNI, 就是通过回绕的方式搜素连接路由的路径。但是如果其选择的路径不能够满足Qos的实际需要时, 整个寻路过程就回重新回到起点, 寻找下一条符合实际发展需要的路径, 这个方法的好处是可以比较能动性的去适应实际需求的变化, 但也有其缺点, 就是整个的连接所耗的时间比较长。另一个就是并行多由路径, 他就能够克服这方面的缺点, 所谓的并行多路路就是路由将所有的洗洗脑沿多条路径同时出发, 但是在沿途过程中会预留一些信息资源, 当其中任何一个信息到达所需要的目的地的时候, 整个过程中就算被完成, 其他路径的所有信息就会被停止释放。

4 总结

文章通过对路由的具体分析与探讨, 提出了一种可以调节服务质量的路由算法, 这种算法的基本原理就是根据实际网络情况变化而进行相应的调整与变化, 这种算法能够根据网络的实际运行情况自行的寻找路由范围, 即在设定的传输时间的上限期限值B, 如果B的值越大, 就表示寻路的范围越广, 需要花费的寻路也更多。如果当B减少了, 就表示寻路的范围也相应的减少, 从而减少寻路的花费, 但是会影响到连通率, 导致用户对连通率的期望值大打折扣, 也会影响到网络运营商对于网络资源的利用率。通过大量的实验证明, search-one的算法比最短路的算法具有更高的连通率, 并且通信的花费和连通率的比值最小。所以, 以后searchone的算法很有可能会代替最短路的算法。而在多路路由的算法之中, opti-mal可以选择的可行路具有最少的跳数, 并且所化的通信费与连通率的比值是最小的, 因此, 要想花费最少, 而且寻找出最可靠可行的线路, 就可以选择采用opti-mal的算法。

参考文献

[1]汪芸, 顾冠群, 网络服务质量 (Qos) 参数研究, 计算机研究与发展, 2012.35 (6) :543-547.

[2]李昌兵, 基于计算智能的多播QoS路由技术研究[D], 重庆大学, 2010年

ZigBee路由算法的改进 篇5

近年来, 作为在低速率的无线传感器网络和控制网络中最受瞩目的技术之一, Zig Bee以其低成本、低功耗、低速率、高可靠性等特性, 广泛应用于工业、医疗、军事、智能家居等需要低功耗、低成本, 对数据传输速率和服务质量要求不高的无线通信应用场合[1]。

Zig Bee网络层 (NWK) 介于MAC层和应用层之间, 是由Zig Bee联盟制定的。Zig Bee网络层的主要功能就是确保Zig Bee的MAC层能正常工作, 并且提供适合的服务接口给应用层。网络层提供了两个必要的功能服务实体用于向应用层提供接口:数据服务实体和管理服务实体[1,2]。

NWK主要功能有: (1) 加入和离开网络; (2) 帧的安全机制管理; (3) 根据路由发送帧到目的地址; (4) 发现和维护路由; (5) 发现单跳邻居节点和维护邻居节点信息。

二、Zig Bee网络层技术简介

2.1 网络拓扑结构及地址分配

Zig Bee网络中存在三种网络节点, 分别为中心协调器、路由节点和终端节点。协调器是整个Zig Bee网络的中心, 是协调点, 负责整个网络的组织、维护和管理工作, 必须由FFD (全功能设备) 构成;路由节点负责数据的传输和转发功能, 必须由FFD构成, 但路由节点必须由协调器控制;终端节点负责自身数据的发送并接收其他节点传过来的数据, 可以由FFD或RFD (精简功能设备) 构成。

Zig Bee网络有星型、网状型和树型三种拓扑组织形式。由于树型网络结合了星型结构和网状结构的优点, 且具有较好的扩展性, 所以Zig Bee网络一般采用簇树拓扑结构组织节点。中心协调器启动后就创建一个网络, 设置自身网络地址为0, 路由节点和终端节点选择相应的有路由功能的父节点加入网络, 形成父子关系。成功加入网络后, 该节点获得父节点分配的一个唯一的网络地址。

规定每个父节点最多可以连接Cm个子节点, 这些子节点中最多可以有Rm个路由节点, 网络的最大深度为Lm, Cskip (d) 是网络深度为d的父节点为其子节点分配的地址之间的偏移量, 它的值按公式 (1) 计算, 分配给第k个子路由节点的地址Ak满足式 (2) , 分配给第n个子路由器节点的地址Ak满足式 (3) 。其中, Afather代表父节点的地址。

2.2 Cluster-tree路由算法

Cluster-tree算法根据树结构转发分组, 如果终端节点要发送数据包到网络中的其他节点, 则直接将该数据包转发给其父节点, 由父节点进行转发。

如果一个路由器节点要转发数据包到网络地址为D的目的节点, 已知该路由器节点的网络地址和深度分别为A和d。

首先, 该路由器节点会依据下述表达式判断目的节点是否是其后裔节点:

如果目的节点是其后裔节点, 则下一跳节点地址为:

否则, 如果目的节点不是其后裔节点, 则下一跳节点为该节点的父节点。

2.3 AODVjr路由算法

AODVjr[3]是AODV的简化版本, 具有AODV的主要功能, 但考虑到降低成本、节能、使用的方便性等因素, 简化了AODV的一些特点。

首先AODVjr舍弃了AODV中的目的节点序列号, 为保证路由无环路, AODVjr中规定只有分组的目的节点可以对RREQ (路由请求) 分组进行响应, 即使中间节点存在通往目的节点的路由也不能回复。同时AODVjr不存在AODV中的“先驱节点列表”, 从而简化了路由表结构。另外AODVjr取消了HELLO信息的发送, 由目标节点定期向源节点发送KEEP_ALIVE连接信息来维持路由[4,5,6]。

三、改进的算法设计

3.1 问题的提出

Cluster-tree算法不存在路由发现过程, 限制了寻址的灵活性, 建立的路由不一定是最优的, 从而浪费网络能耗并且引入服务延迟。因而, Zig Bee中允许有路由能力的节点使用AODVjr去发现一条最优路由。但是AODVjr算法在路由发现过程中会产生多余的RREQ分组, 容易引起广播风暴。例如, 图1中节点1发起路由发现, 寻找到节点7的路径, 节点1向所有邻居节点发送RREQ分组, 而向节点1的后裔节点2和3发送RREQ分组对寻找路由帮助不大, 成为多余的RREQ分组。同理节点7要寻找到节点9的路径, 向其父节点0广播也将产生多余的RREQ分组。

此外, 由于网络中某些节点传输数据量过大, 特别是距离中心协调器越近的节点, 从而提前耗尽自身能量, 容易造成网络分割, 影响了整个网络的通信, 缩短了网络的寿命。

针对以上问题, 本文从控制RREQ分组以及能量均衡的角度出发, 提出一种改进的算法, 有效的限制AOD-Vjr路由发现过程中的RREQ的广播, 延迟网络分割出现的时间, 从而提高网络的性能。

3.2 改进的路由算法M_ZBR

3.2.1 冗余RREQ分组的控制

改进的路由算法M_ZBR在路由发现阶段, 利用Cluster-tree结构及算法的特点, 根据公式 (4) 判断出目的节点与当前节点的关系, 从而判断出RREQ分组转发最佳的大致方向。因此, M_ZBR算法在RREQ分组中增加一个标志位flag。当目的节点为当前节点的后裔节点时, flag=0, 即表示当前节点的父节点不宜转发该RREQ分组;当目的节点不是当前节点的后裔节点时, flag=1, 即表示当前节点的后裔节点不宜转发该RREQ分组。

另外, 从树结构可以看出, 若在使用Cluster-tree路由算法时, 可能存在的最长路径应是网络最大深度的2倍。由此, M_ZBR算法通过设定最大传输跳数也可以减少部分冗余的RREQ分组, 本算法中, 当跳数hops>2Lm时, 节点便丢弃该RREQ分组。

3.2.2 节点能量的控制

M_ZBR算法根据Zig Bee路由算法的特点, 对Zig Bee网络中的路由节点采用了能量控制机制, 这对延长网络寿命, 延迟死亡节点以及网络分割出现的时间都是十分必要的。因此, M_ZBR算法定义了节点最小路由能量Emin, 当节点的能量低于Emin时, 路由节点将不再发起路由发现, 即不再采用AODVjr路由算法。

在Zig Bee网络中, 越靠近中心协调器的节点参与数据传输就越频繁, 对整个网络的通信来说也就越重要, 所以Emin的能量控制应与节点深度成反比, 深度越小节点应具有相对较大的最小路由能量, 因此, 将Emin定义为:

其中, Elimit为节点正常工作需要的最小能量值, 为控制系数, 可以根据需要人为的控制Emin的大小, d为节点的深度。

此外, M_ZBR算法依据节点最小路由能量的定义, 设置一个节点能量警戒值Ewarning:

其中, k为大于1的控制系数。

依据以上节点能量阈值的设置, M_ZBR算法在RREQ分组中增加了能量标志位energy_flag, 用于统计RREQ分组传输过程中统计处于能量警戒区内的节点个数。

3.2.3 算法流程

(1) 当RFD节点要给网络中其他节点发送数据时, 直接采用Cluster-tree算法, 即将数据转发给其父节点, 由其父节点转发。 (2) 当FFD节点要发送数据到网络中其他节点时, 首先查找路由表中有无到目的节点的路由表项, 若有则按路由表转发数据包, 若无则启动路由发现过程。 (3) 在路由发现阶段, 任意节点收到RREQ分组时, 首先检测本节点是不是该RREQ分组的目的节点, 如果不是, 则转 (4) ;若是, 则转 (9) 。 (4) 判断节点自身的剩余能量, 如果剩余能量小于节点最小路由能量Emin则直接丢弃RREQ分组, 否则转 (5) 。 (5) 查看RREQ分组中的跳数值, 若hops>2Lm, 则丢弃RREQ分组, 否则转 (6) 。 (6) 查看RREQ分组中的标志位flag, 若flag=0, 转 (7) , 若flag=1, 则转 (8) 。 (7) flag=0表明本节点不宜转发子节点发送的分组, 需判断本节点是否为前一跳的父节点, 若是, 则丢弃RREQ分组;若不是, 则判断目的节点是否为当前节点的后裔节点, 如果是, flag的值继续为0, 直接转发分组, 若目的节点是当前节点的后裔节点, 则设置flag=1。 (8) flag=1表明本节点不宜转发父节点发送的分组, 需判断本节点是否为前一跳的子节点, 若是, 则丢弃该分组;若不是, 则需判断目的节点是否为当前节点后裔节点, 如果是, 则设置flag=0, 若目的节点不是当前节点的后裔节点, flag的值继续为1, 直接转发分组。 (9) 当目的节点收到RREQ分组时, 判断自身剩余能量, 若小于Emin, 直接回复RREP;否则将收到的分组放入缓存区, 在缓存时间t内, 比较各RREQ分组的能量标志位energy_flag, 选择energy_flag最小的RREQ分组且回复RREP。

四、仿真结果分析

为了验证改进算法的实际效果, 通过仿真实验对比原来的AODVjr算法, 分别比较了死亡节点个数以及总能量损耗, 仿真结果证明了算法的可行性和有效性。

图3是原AODVjr算法与改进算法死亡节点数的比较, 曲线 (1) 是原AODVjr算法随数据流量增加而变化的死亡节点数, 曲线 (2) 是改进后的算法的死亡节点数。当数据流量较小时, 节点能耗就较少, 节点死亡数相对就比较少。当数据流量增加时, 死亡节点数也会增加, 改进的算法通过能量标志位的判断, 选取能量标志位最小的RREQ分组并回复, 明显比原算法的死亡节点数增加的缓慢。

图4比较了改进算法与原算法的网络总能量耗损。曲线 (1) 是原AODVjr算法随数据流量增加而变化的网络总能量耗损, 曲线 (2) 是改进后的算法的网络总能量耗损。显然, 改进的AODVjr算法通过控制了RREQ分组减少了网络的耗能。

五、结论

本文主要针对Zig Bee的路由协议进行分析, 基于能量均衡对Zig Bee现有的路由算法AODVjr提出了改进, 通过限制路由发现过程中的RREQ的广播, 很好的延迟网络分割出现的时间, 从而提高网络的性能。仿真实验将原算法和改进的算法进行了比较, 改进的路由算法有效地减少了总耗能与死亡节点数。

摘要：网络层的路由协议是ZigBee协议规范的研究重点之一, 因为网络节点中节点的能量资源、计算能力和带宽都非常有限, 路由算法优化与否对整个网络的性能有着至关重要的作用。从控制RREQ分组以及能量均衡的角度出发, 对AODVjr算法提出了改进。通过仿真实验, 将改进的算法与原AODVjr算法进行性能参数的比较分析, 实验结果验证了改进后的算法的有效性。

关键词：ZigBee,路由算法,AODVjr,无线传感器网络

参考文献

[1]ZigBee Alliance.ZigBee Document053474r13[S].December1, 2006.

[2]朱向庆, 王建明.ZigBee协议网络层的研究与实现.电子技术应用.2006.1:129

[3]Hakeres I D, KleinBerodt.AODVjr, AODVsimplified[J].Mobile Computingand Communication Review, 2002, 6 (3) :100-101.

[4]班艳丽, 柴乔林, 王芳.改进的ZigBee网络路由算法.计算机工程与应用, 2009, 45 (5) :95-97

[4]谢川.基于ZigBee的AODVjr算法研究.计算机工程, 2011, 37 (10) :87-89

浅谈机会网络路由算法 篇6

机会网络是一种不需要在源节点和目标节点之间存在完整连通路径, 利用节点移动带来的相遇机会实现通信的时延和断裂可容忍的自组织网络[1]。在机会网络中, 节点之间的链路经常间歇性的中断且这种中断一般持续时间较长, 以至于在任何时刻源节点和目标节点之间可能一直不存在连通的路径。

很明显, 机会网络和现有的常用的网络不同, 它具有以下特性:

(1) 低数据传输速率、高延迟 (2) 网络断开 (Network disconnection) (3) 长排队时间。正是由于这些特性, 使得传统的存储—转发模式不适合于机会网络, 在机会网络中要采用存储—携带—转发模式来进行通信。

2、机会网络路由算法

路由问题是任何组网技术的首要问题。机会网络的路由问题更是机会网络中的研究重点。现有常用的网络路由协议中都是假设在源节点和目标节点之间至少存在一条完整的通信路径, 所以不适合在机会网络中运行。机会网络中的路由转发机制是以“存储—携带—转发” (Store-CarryForwarding) 的模式工作。要设计出高效机会网络路由协议的关键问题在于如何针对每个消息来找出最好的下一跳转发节点和何时进行数据转发。良好的路由算法能提高报文传输的成功概率, 降低传输延迟, 减少能量的消耗。

人们针对不同类型的机会网络提出了各式各样的路由算法。目前现有机会网络路由算法主要有以下几类:

2.1 基于复制的转发算法

在基于复制的路由转发机制中, 一条消息会有多份拷贝被注入网络, 只要其中有一份拷贝被传送到目标节点, 这条消息则传输成功。然而, 它的核心问题在于消息拷贝数怎么确定才算合适以及怎样来产生消息拷贝。最简单的方法就是直接传输 (Direct Transmission, 简称DT) [2]方法, 即源节点直在和目标节点相遇时才进行数据转发, 这样做网络耗费是最小的, 但往往会传输延迟较大, 并且经常会因为源节点碰不到目标节点而造成传输失败, 其传输成功率最低。在源扩散Source Spray and Wait (SSW) 算法[3]中, 事先指定消息的最大拷贝数为L。源节点起始时拥有一个消息的L个拷贝, 源节点先将消息拷贝给最先遇到的L-1个中继节点, 然后源节点和中继节点只在遇到目标节点时才进行转发。

2.2 基于编码的转发算法

这类机制中, 会把要传输的数据先编码成互相冗余的消息, 目标节点接收到编码后的一部分消息, 就能够通过一定的运算来重组原始数据。在Ling-Jyh[4]等人提出的H-EC中, 针对每个编码后的小消息会生成两个拷贝。当遇见邻居节点的时候, 首先会将消息的第l份拷贝传递给该邻居节点, 然后会在该连接持续的时间内, 将其他消息的第2份拷贝传输给该节点。该机制因为充分利用了所有的连接机会所以传输性能更好。

2.3 基于相遇预测的转发算法

根据对历史概率进行统计, 每个节点都具有一个与目标节点相遇的概率, 人们也可以通过节点的历史移动来预测该概率值。在节点移动过程中每个节点选择与目标节点相遇的概率值更高的节点作为转发的中继节点, 这就是基于相遇预测的机会转发机制。比如Seek and Focus[5]协议中, 针对每一个节点, 当前节点都会记录下自上次相遇之后所经历的时间, 并据此来估计节点间的相遇概率值。此外, 节点间的相遇概率还可以根据节点的位置和节点的运动方向来进行估计。

2.4 基于链路估计的转发算法

基于链路估计的机会转发机制在选择转发节点时则根据节点之间的“端到端”的链路状态。在机会网络中是否转发可以依照根据收集到的单跳链路状态进行估算得出的端到端路径的效用值。在最短期望路径路由 (Shortest Expected Path Routing Protocol) [6]中, 利用节点所维护的到达已知节点的链路效用值也即链路可用概率值。再通过Dijkstra算法计算出当前节点与目标节点之间的最短路径。

2.5 冗余效用混合转发算法

冗余效用混合转发机制结合了并行传输和基于效用的转发决策的优点来提高传输的性能。PROPHET (Probabilistic Routing Protocol Using History of Encounters and Transitivity) [7]就是综合了传染转发和基于相遇预测转发二者的优点。在PROPHET中, 每个节点都维护着对网络中其它节点的一个效用值, 在转发过程中会根据节点对消息的目的节点的效用值来选择是否进行转发。只是在PROPHET中概率效用值的更新使用了概率的传递性, 即如果节点a有可能遇到节点b, 而节点b又有可能遇到节点c时, 则认为节点a也可以成为目标节点为c的消息的转发节点。当节点相遇的时候, PROPHET会将消息传输给那些到达目标节点的概率比自身高并且没有存储该消息的节点, 从而降低了传染转发中因为广播消息引起拥塞而导致的性能下降。

2.6 基于节点主动运动的转发算法

当网络中拓扑变化或因节点稀疏而存在较强的随机性时, 以上所介绍的机会转发机制都因为被动等待与更好的转发节点相遇, 而造成传输成功率降低或者传输时延增大。在基于节点主动移动的转发机制中, 有一部分特殊的节点可以通过自身的主动移动, 为其他的普通节点提供通信服务。DataMULEs系统[8]即是通过引入移动节点从而实现稀疏传感器网络中的数据收集。

3、结语

机会网络路由是一个富有挑战性的问题, 它要求对路径选择、评估传递性能、缓存管理和调度传输等多种技术来综合考虑。而目前的各种机会路由技术还存在一些关键的问题需要解决, 可以预见, 未来对于机会网络路由问题的研究可能会致力于实际应用的考虑, 使机会网络得到更大范围的应用。

摘要：随着传感技术、嵌入式技术、无线通信技术、高性能计算等相关领域的迅猛发展, 以物联网为代表的新一代的智能互联网络应运而生。出现了一种新的基于机会转发的路由技术, 使用该技术的网络, 称为机会网络。本文主要介绍了机会网络的概念和理论基础, 并分析比较了当前机会网络的一些较为重要的路由算法。

关键词：机会网络,路由,路由算法

参考文献

[1]熊永平, 孙利民, 牛建伟, 刘燕.机会网络[J].软件学报, 2009, 20 (1) :125-134.

[2]肖明军, 黄刘生.容迟网络路由算法[J].计算机研究与发展, 2009, 46 (7) :1065-1073.

[3]spyropoulos T, Psounis k, Raghavendra CS.Spray andwait:An efficient routing scheme for intermittently connect-ed mobile networks[C].In:Proc.of the 2005 ACM SIG-COMM Workshop on Delay-Tolerant Networking.Philadelphia:ACM, 2005, 252-259.

[4]Chen L, Yu C, Sun T, Chen YC, Chu HH.A hybrid rout-ing approach for opportunistic networks[C].In:Proc.of the2006 SIGCOMM Workshop on Challenged Networks.Pisa:ACM, 2006, 213-220.

[5]Spyropoulos T, Psounis K, Raghavendra C.Single-Copyrouting in intermittently connected mobile networks[C].In:Proc.of the 2004 1st Annual IEEE Communications SocietyConf.on Sensor and Ad Hoc Communications and Net-works.2004, 235-244.

[6]Tan K, Zhang Q, Zhu W.Shortest path routing in partial-ly connected ad hoc networks[J].In:Global Telecommunica-tions Conf.the GLOBECOM 2003, Vol.2, 2003, 1038-1042.

[7]Lindgren A, Doria A, Schelen O.Probabilistic routing inintermittently connected networks[J].ACM SIGMOBILEMobile Computing and Communications Review, 2003, 7 (3) :19-20.

树路由算法 篇7

随着Internet分布式计算的迅速发展, Anycast (选播) 这种新型网络通信方式也随之被定义, 选播是实现一台主机与一组主机之间的通信方式。其特点在于, 可以使多个www镜像服务器共享一个选播地址, 极大改善网络资源和服务器的负载均衡, 还能简化一些网络服务的工作。由于是接收者共享一个选播地址, 因此选播路由算法相当重要。该算法不仅要适用于选播通信服务, 而且要尽量保证服务质量 (QoS) , 尤其要考虑服务器负载、网络剩余带宽分配等问题。

本文利用遗传算法GA (Genetic Aglorithm) 来改进选播路由算法。

1 算法设计分析

我们把通信网看成是一个有向连通图G= (V, E) , 其中V={v1, v2, …, vn}是网络中的节点集, E={e1, e2, …, en}是网络中连接两个节点的链路集合。每一条链路上都具有链路带宽Bi, 在选播路由算法中包含如下一些度量值, R= (S, D, Q) , 其中S表达选播路由的源节点, D表一组目标节点组, Q则是一些QoS相关质量参数, 这些质量包括:传输带宽B, 传输延时T, 服务器负载P等。

· 有效传播带宽 反映网络动态性能的参数, 通过协议SNMP中的MIB来得到路径已用带宽b, 即某路径的有效传输带宽为:B-b 。

· 延时 假设路径上各节点的延时为静态可加性延时, 这样便可采用该路径中所经历的所有节点的延时总和来作为整条路径的延时。

即${\rm T}{}_{(Road)}={\displaystyle \sum _{i=1}^{n}i}{\displaystyle \sum _{j=1}^{n}t}{}_{i,j}\cdot p{}_{i,j}(i,j=1,2,\cdots ‚n)$

其中

$p{}_{i‚,j}=\{\begin{array}{l}1:\text{此}\text{路}\text{径}\text{经}\text{过}i‚,j\\ 0:\text{此}\text{路}\text{径}\text{未}\text{经}\text{过}i‚j\end{array}$

· 服务器负载 服务器负载参数是为了均衡服务器负载, 提高服务质量的一个重要参数。

在具体应用中, 一般服务数据比请求数据多。服务数据的服务质量比请求数据更重要, 而两个方向的可用带宽不总是相同的, 所以选取的是逆向路径指标来度量服务质量[1]。

$\begin{array}{|c|}\hline \text{客}\text{户}\\ \hline\end{array}\underset{\text{应}\text{答}\text{所}\text{求}(\text{传}\text{送}\text{大}\text{文}\text{件})(\text{逆}\text{向})}{\overset{\text{请}\text{求}(\text{正}\text{向})}{\rightleftharpoons }}\begin{array}{|c|}\hline \text{服}\text{务}\text{器}\\ \hline\end{array}$

Q=t (kt+kb (1-b/B) +kpp)

t:路径逆向传输延时

b:路径逆向已用带宽

p:路径对应的选播成员的服务器负载

B:网络最大带宽

kt, kb, kp:相应调整系数, 可根据具体网络中应用情况来调整延时、带宽和负载的关系。

2 基于GA的路由算法设计

2.1 GA概述

GA是一种模拟生物种群自然选择的遗传进化机制。GA本质上是从一个初始种群进行不断迭代, 在迭代过程中根据一定条件进行优胜劣汰的选择, 从而产生出性能更优的下一代群体, 直到得到满意的解为止。

2.2 染色体的编码方法和初始种群的生成

本文讨论的是在一定约束条件下的最佳路径的搜索问题, 显然所得路径结果长度不尽相同, 因此采用不定长编码来构造染色体。在网络拓扑结构中, 每个节点都有相应的数字编号, 而每条染色体就代表一条搜索的路径, 因此, 从源点到目的节点的每个节点编号序列组织在一起便构成一条染色体[2]。

在生成初始种群时, 按照网络拓扑结构由宽度搜索算法生成popsize条路径 (popsize是规定的初始种群大小) 。初始种群中的染色体编码设计与节点的自然路径相同, 从而减少了编码转换的过程。

2.3 适应度函数

GA算法进行进化的根本依据是适应度函数, 由它引导着选择、交叉、变异等遗传操作的进行, 因此好的适应度函数对GA算法的收敛速度和有效进化、寻找全局最优解有着至关重要的作用。根据选播度量的参数, 将适应度函数定义为:

Fitness= (kt/t+kb (1-b/B) +kp/p)

可以看出, 它能充分地考虑到剩余带宽、延时和服务器负载等因素。

2.4 遗传操作

· 选择与复制操作

本文采用轮盘赌的方法进行染色体的选择, 按每个个体适应度值的比例得到一个轮盘赌的轮转切片, 然后转轮转动次数达到能够使个体在群体中满足popsize为止, 选出其中较优的染色体复制到下一代中, 以维持下一轮进化。

· 交叉操作的改进

适当的交叉和变异操作可以增强染色体多样性, 提高遗传算法搜索能力, 从而避免出现早熟的情况。交叉操作是交换一对父染色体部分基因片断而生成下一代染色体。本文采用单点交叉的方法[3]:

在两条父代染色体P1, P2中找到一个相同点, 以此为分界点将P1的前段基因与P2后段基因组合, P2的前段基因与P1后段基因组合, 生成两个新的子代基因P′1, P′2, 交叉后可能形成环路, 应对其进行修复, 判断新基因中是否有重复节点。若有则将两个相同的节点之间的路径删掉, 从而保证路径中不出现环路。P1: (1, 3, 4, 9, 7, 12, 13, 19, 26) , P2: (1, 2, 6, 5, 7, 11, 9, 17, 21, 22, 24, 26) , 搜索到第一个相同点7, 以此为分界点使P1, P2相互交叉。得到P′1: (1, 3, 4, 9, 7, 11, 9, 17, 21, 22, 24, 26) , P′2: (1, 2, 6, 5, 7, 12, 13, 19, 26) 。检查P′1中存在环路, 因此删除两个相同节点9之间的路径后变为:P′1: (1, 3, 4, 9, 17, 21, 22, 24, 26) 。P′1, P′2为交叉并修复后的染色体。

· 变异操作的改进

变异操作首先在群体中随机选择一个个体, 并将其中的基因片断作修改, 变异成一个新的个体。如P1: (1, 3, 4, 9, 7, 12, 13, 19, 26) 随机选择其中一个基因片断 (9, 7, 12) , 然后以9作为起点, 12作为终点, 随机生成一条路径: (9, 10, 13, 12) , 用此新路径替代原基因片断, 得到变异后新染色体P′1 (1, 3, 4, 9, 10, 13, 12, 13, 19, 26) ;若有环路出现, 则删除环路 (同交叉操作中去除环路的方法) , 修复后得到子代的变异染色体P′1为 (1, 3, 4, 9, 10, 13, 19, 26) 。

2.5 交叉率与变异率的改进

在进行交叉操作和变异操作时, 如果交叉率和变异率过小, 则种群很难产生出优秀新个体, 但若过大, 则容易破坏染色体中的优良基因, 导致搜索不稳定。本算法在考虑交叉率和变异率时, 不使用固定的交叉率和变异率[4]。当进化初期适应度较低时, 增强极差个体的变异能力, 使之更易产生出优秀新个体, 进化后期, 高适应度个体较集中, 此时降低交叉率和变异率, 更好地保护优良模式, 这样既能使算法跳出局部最优解, 克服早熟现象, 又能加快收敛速度, 提高全局搜索能力。在每代遗传操作中交叉率Pc和变异率Pm的定义如下:

${\rm P}{}_c=\{\begin{array}{l}\frac{{\rm P}{}_{c\max }-{\rm P}{}_{c\min }}{1+\exp (A\left(\frac{2(f{}^{\prime }-f{}_{avg})}{f{}_{\max }-f{}_{avg}}\right)}+{\rm P}{}_{c\min }f{}^{\prime }\ge f{}_{avg}\\ {\rm P}{}_{c\max }f{}^{\prime }<f{}_{avg}\end{array}$

$\begin{array}{l}{\rm P}{}_m=\{\begin{array}{l}\frac{{\rm P}{}_{m\max }-{\rm P}{}_{m\min }}{1+\exp (A\left(\frac{2(f{}^{\prime }-f{}_{avg})}{f{}_{\max }-f{}_{avg}}\right)}+{\rm P}{}_{c\min }f\ge f{}_{avg}\\ {\rm P}{}_{m\max }f<f{}_{avg}\end{array}\\ A=9.903438f{}_{\max }:\text{表}\text{示}\text{种}\text{群}\text{中}\text{最}\text{大}\text{适}\text{应}\text{度}\end{array}$

fmin:表示种群中最小适应度 favg:表示种群中平均适应度

f:表示变异个体的适应度

f ′:参与交叉的两个个体中较大的适应度

Pc:交叉率 Pm:变异率

Pcmin, Pcmax:表交叉率上、下限

Pmmin, Pmmax:表变异率上、下限

实验表明:Pcmin=0.5, Pcmax=0.9, Pmmin=0.005, Pcmax=0.05, 效果良好。

2.6 收敛性分析

论文中提出的遗传算法能够收敛到全局最优解。

证明, 根据文献[5] 定理2.6, 具有变异率Pm∈ (0.1) , 交叉率Pc∈[0, 1], 同时采用比例选择法, 且在选择后保留当前最优解的遗传算法, 最终能收敛到全局最优解。

3 仿真实验

实验设置为:种群规模50, 交叉率Pc∈[0.5, 0.9], 变异率Pn∈[0.005, 0.05]。进化终止代数100, 网络拓扑图30个节点, 源节点S=1, 目的节点为四个选播服务器D= (10, 15, 20, 25) , 服务器利用率设置为P10=0.5、P15=0.4、P20=0.3、P25=0.2 , 延时范围为10～20随机数, 剩余带宽率范围为 (0～1) 随机数, 适应度函数中调整系数设为Kt=3、Kb=1.5、Kp=1 。

4 结 论

本文针对选播路由算法的特点, 对遗传算法中的交叉、变异操作以及交叉率Pc和变异率Pm作了改进, 使之能更有效地满足选播路由中的最大剩余带宽、最小传输延时和最快服务器响应速度, 从而提高选播路由的服务质量。

摘要：随着基于IPv6选播应用的研究与发展, 选播路由算法已成为选播服务质量的关键。以遗传算法为基础, 提出一种改进的交叉、变异遗传操作, 在克服传统算法中早熟现象的基础上, 加快了收敛速度;同时本算法以延时、带宽和服务器负载作为选择操作的依据。仿真结果显示, 该算法能够在合理利用网络资源的同时找到最优解。

关键词：选播,遗传算法,服务质量

参考文献

[1]张丽, 贾维嘉, 严伟, 李晓明.使用特殊复合距离的选播路由算法[J].计算机研究与发展, 2005, 42 (1) :252-258.

[2]Massanori Sugisaka, Xinjian Fan.Adaptive Genetic Algorithm with a Cooperative Mode[C].Proceedings of IEEE International Symposium on Industrial Electronics, 2001.

[3]马炫.求解K条最优路径问题的遗传算法[J].计算机工程与应用, 2006, 12:100-101.

[4]邝航宇, 金晶, 苏勇.自适应遗传算法交叉变异算子的改进[J].计算机工程与应用, 2006, 12:93-96.