Ad hoc 网络的一种改进路由算法

2014-12-13陈恒

江苏科技信息 2014年21期

陈恒

（山东青年政治学院实验设备管理处，山东济南 250103）

0 引言

Ad hoc 网是一种多跳的、结构变动性强的自组织无线网络。整个网络中节点处于移动状态，并且以分布式协议保持与其他节点的联系。在这种网络中，没有固定的基础设施。由于终端无线覆盖取值范围的有限性，2 个无法直接进行通信的用户可以借助其他节点组成临时链路完成通信［1］。因为可以方便地随机组网，因此这种网络在各种临时性的无线通讯中应用广泛。但是由于各节点的移动性，可能造成通信链路断开而反复进行路径的重构。为了避免这种情况发生，本文提出一种改进的路由算法，在考虑路径距离的同时关注路径的稳定性，避免路径的频繁重构［2-4］。

1 原理介绍

传统通信网络的各级节点设备相对固定，设备性能在满足通常负载量的情况下一般还具有一定余量，因此网络稳定性较好。在这种前提下，网络的路由算法比较关注时效性，即跳数少、距离短、速度快等指标。但是对于Ad hoc 网络来说，每一个节点既可以是通信终端又可能承担路由功能。考虑到移动性的特点，最短路径的稳定性未必好。具体如图1 所示。

XLMY 是通信始端X 和终端Y 之间的最短路径，但是在这条路径上有中间节点处于传输范围的边缘，随着节点的移动，此条线路发生断裂的可能性较大。另一条线路X0PQRY，虽然距离远但是稳定性显然较好。因此在该网络系统中应统筹考虑线路的稳定性和距离的大小，从而确定最佳的路由选择。

Ad hoc 网络的通讯是否成功，取决于接收到信息的信号噪声比：S/N=Ps/Pn。其中Ps为信号功率，Pn为噪声功率。指定通道稳定因子：WDF=（S/N）/（S/N）th，其中（S/N）th为信噪比的阈值。当WDF＞1 时，信息传输正常，否则信息无法正确传送。

图1 边缘节点示意图

假设在某一通讯中，发射端到接收端存在t 条路径，指定该通讯中的稳定因子为ZWDF=min｛WDFk｝，k∈t，即所有路径中稳定性最小的因子为此通讯过程中的路径稳定因子。同时还应考虑到，在Ad hoc 网络中，随着中间节点数量的增加，端到端的通信速率会明显下降。所以需要在稳定性和效率之间进行综合评判。在保证线路稳定的情况下，应选择中间节点少的路径。定义路径判断依据：J=ZWDF/H-count。此处，ZWDF 为一通讯中的稳定因子，H-count 为该路径的节点数。当2 节点间有多条路径可供选择时，路由算法对J 进行排序，选择J 值最大的路径为首选，其他路径按排序大小候选。

2 技术实现

2.1 路由发现过程概述

当网络中2 节点间要进行通讯时，系统先查询现有路径中是否有满足要求的选择，如果没有源节点首先向其邻节点广播“路由请求”报文。信息中包含分组Group，该分组由以下内容构成：

S-Node//源节点编号；

D-Node//目的节点编号；

Se-ID//报文顺序号（标示该组信息编号）；

R-ID//路径中的节点列表；

ZWDF//路径稳定因子，为各条路径中稳定因子的最小值；

H-count//途径节点的个数；

当某节点收到一个Group 分组信息时，若确定该节点是目的节点，则发送路由确认消息给源节点。若（1）该节点是中间节点，（2）该节点不在路径节点列表中，（3）该节点未收到过此分组信息，则将自己的信息加入到节点了列表中，并比较分组信息中ZWDF 与该路径的WDF 的大小，并将较小值替换Group分组中的ZWDF 值，同时将途径节点的个数H-count 加1，之后将该分组信息继续广播。若不满足条件（2）（3），则说明对该节点在之前已进行过判别，可不予考虑。若有多条路径可供选择，对比综合判断依据J 的大小，选择J 值最大的路径。

2.2 路由维护过程概述

在进行网中通讯时，路径的选择既要考虑稳定性因素，又要考虑通信速率的因素，因此选择结果一般依赖于综合判断依据J 的大小。在通讯发起时将ZWDF 值赋予一个足够大的值，在路由的过程中，即时比较ZWDF 值与现有路径的WDF 的大小，并将较小值赋予ZWDF 值，从而实现对J 值的优化调整。

但是当ZWDF 值接近于1 时，应引起高度重视。此时意味着通讯过程处于稳定性崩溃的边缘，通讯链路有较大可能断开，从而引起路径的重新构造。如不预先处理，必然引起网络中负载量的大幅增加。源节点接收到即时的Group 信息后，如果发现以上情况，立即启动预先切换模式，根据J 值的候选顺序，将通讯切换到备用线路上，从而避免路径的频繁重构。

在信息传输过程中，所有节点各自维护自己的线路信息状态表，表中含有如下字段：N-List，WDF，time。N-List 字段内容为临节点的ID 号；WDF 为通道稳定因子；time 为WDF 维持现值的时间。按照之前的定义，WDF 的取值等于某节点接收到的正确信号的功率与接收到的噪声信号的功率之比。当WDF 的值长时间未得到更新时，为避免该线路退出路径选择，此时启动广播机制，向邻近的节点发送WDF-应答信号。其他节点收到该信号时，向发射节点回传一个应答，从而通过该通信过程计算出通道稳定因子WDF 的最新取值，用以进行路径选择。当通讯线路中多条通道都可使用时，依据J 值的大小，选择综合性能较好的几线路，由系统自动控制向目的节点发送状态确认信息，目的节点收到信息后回传应答信号至源节点。由此实时更新链路状态，以保证当前线路在稳定性达到临界值前，通讯过程及时切换到备用路径。

3 性能测试

3.1 测试环境介绍

为了对改进后的实际效果有直观的了解，可以采用仿真软件对改进算法和普通DSR 算法进行性能比较。采用NS2 软件进行仿真，测试范围：800m×800m；网络类型：Ad hoc 网络；设置有效带宽为2Mb/s；每节点无线信号通讯范围：150m；节点的移动速度在10m/s 以内变化。共设定40 个节点随机分布在测试范围内，通信中源节点和目的节点随机选取，选择恒定比特率的数据，包长256 字节，发送速率为每秒300 包，仿真时间设置为500s，重复30 次，对取值平均处理后进行对比。

3.2 性能分析

该仿真主要在节点移动的情况下，考察改进算法和DSR 协议的分组成功传输率、延时抖动和开销性能的差异。由图2 可以看到，在节点移动速度较小时，2 种方式的成功传输率都比较高，且差别不太大。随着移动速度的增加，DSR 协议的成功传输率快速下降。改进算法的成功率虽然也有下调，但明显高于前者。合理的解释是随着节点移动速度的增加，链路的稳定性快速下降。改进算法中由于具备了链路稳定性检测及备用链路的切换机制，所以确保了成功传输率没有出现严重的下滑。

由图3 可以看到节点移动速度对延时抖动的影响。DSR算法随着节点移动速度的增加，其稳定性明显下降。因此，整个通讯过程中可能要频繁进行通道的重构，DSR 协议由于不具备这方面的预处理机制，所以其延时抖动增加明显。

图4 可以看到，在节点移动速度较小时，通讯线路的稳定性尚可，由于改进算法加入了若干监测信息，因此其网络开销略大于DSR 协议。随着节点移动速度的增加，DSR协议链路稳定性下降，其断开次数不断增加，此时需要频繁进行网络重构，由此向网络中发起大量广播信息，带来的结果就是产生大量网络开销。改进算法的优化机制发挥作用后，可有效控制网络开销的大幅增加。