黄　炜　李　强　陈媛媛

1(电子科技大学通信与信息工程学院　四川 成都 611731)2(通信网信息传输和分发技术国家重点实验室　河北 石家庄 050000)



220D无线自组网路由拓扑更新分析与优化

黄炜1,2李强1陈媛媛1

1(电子科技大学通信与信息工程学院四川 成都 611731)2(通信网信息传输和分发技术国家重点实验室河北 石家庄 050000)

拓扑更新是无线自组网路由协议的重要组成部分，是影响网络性能的关键因素。220D无线自组网路由协议规定其节点在每个最小时间间隔内最多发送一次拓扑更新消息。针对最小时间间隔值设置不合理时，会影响网络性能的问题，提出一种自适应改变最小时间间隔值的路由拓扑更新优化方法，仿真结果显示该方法可以改善网络性能。

无线自组网路由协议拓扑更新220D

0　引　言

路由拓扑更新是设计无线自组织网络时的重要考虑因素[1,2]。由于频繁变化的无线自组织网拓扑结构需要有效的路由协议支持，所以对无线自组网路由协议拓扑更新规则的研究是很有必要的。文献[3]分析了路由拓扑更新策略对MANET路由协议性能的影响。文献[4]分析了AODV协议在不同节点移动速度下的路由性能。

MIL-STD-188-220D协议标准(简称220D协议)是无线自组网络技术的典型应用成果。它是美军CNR(战斗网无线电台)的标准的最新版，我国高端军用和民用电台设计时也参考了220系列协议。因此，对220D无线自组网路由拓扑更新的分析与优化具有广泛的意义。

220D路由协议采用的是源路由选择算法，使用稀疏路由树来交换拓扑结构信息，并定义了“最小网络拓扑更新时间间隔”(简称最小时间间隔)来防止节点过于频繁地发送拓扑更新消息，以节约无线频率资源。但当“最小网络拓扑更新时间间隔”设置较大时，会使拓扑更新消息得不到及时发送；设置较小时，则使拓扑更新消息与数据分组竞争无线信道导致数据因碰撞而丢失，进而影响网络性能。针对此问题，本文提出一种自适应改变最小时间间隔的路由拓扑更新优化方法。仿真结果显示该方法可以改善220D及同类自组织网络性能。

1　220D路由拓扑更新分析

220D无线自组网协议采用的是源定向路由选择算法，节点入网时就要维护一张到网内其他节点的路由表，由事件触发拓扑更新。每个节点周期性地向邻居节点广播拓扑更新包，用于交互拓扑信息。

1.1最小网络拓扑更新时间间隔

为了防止网络拓扑剧烈变化时拓扑信息交换过于频繁，减小路由对无线信道的竞争，220D协议围为0～255，且只能取整数，单位为分钟。220D规定拓扑更新消息在每个最小时间间隔内发送不得超过一次，拓扑更新请求消息在每MIN_UPDATE_PER/2内最多发送一次。将其置0则可以禁止拓扑更新消息的发送与传输，即使网络中某个节点不移动也不能将其MIN_UPDATE_PER设置为0。因为当其检测到其他节点移动导致链路变化时也要发送拓扑更新消息。

1.2源定向路由

源定向中继方式为一种简单地从源节点到目的节点的非动态的中继过程。源节点需要发送分组时，首先从自己的路由表中查找、计算出经过内部网到达目的节点的路径，然后将路由信息编码进内部网报头，这就是表驱动路由协议的特点。其优点是节点发送报文时可以获得准确度较高的路由，能避免路由环路的发生，时延较小。

1.3拓扑更新

220D网络依靠节点间积极地交换拓扑信息来保证网络的正常通信。为此，220D协议专门定义了其拓扑更新数据结构，如图1所示。其中节点1的状态字节描述的是节点1的前驱节点和源节点之间的链路状态。

图1　拓扑更新数据结构

如果网络在拓扑更新时，交换的是完整路由表，就会产生数据量很大的拓扑更新包，交互时就会占用很大的带宽，不适用于资源有限的adhoc网络。因此，220D协议规定，只在相邻两个节点之间传递完整路由树的较小副本，即稀疏路由树。220D协议根据以下规则删除节点间的重复路径：

1) 只保留从根节点到其他节点的最短路径；

2) 根节点到另一节点之间长度相同的路径，最多保留两条。

假设两相邻两节点A与C的路由树如图2所示。如果节点A与C之间交换完整的路由树，节点A就会把节点C的路由树保存到其自己的路由树里，如图3所示。如果按照220D规定的交互规则，A与C之间只交换完整路由树的较小副本，那么交互后节点A的路由树如图4所示。可以看出相邻节点之间交换稀疏路由树可以减少节点存储的路由树的数据量。

图2　节点A与C的路由树

图3　节点A的包括冗余路径的路由树　图4　节点A的稀疏路由树

220D规定网络拓扑更新由以下条件触发，采用全网通播地址专门发送。① 节点A检测到一条失败的链路；② 节点A检测到一条新的链路；③ 节点A检测到一条链路质量发送变化的链路；④ 节点A收到了一条改变了其稀疏路由树的拓扑更新消息；⑤ 节点A改变了其静默模式，并希望通告全网这一变化；⑥ 节点A改变了其中继能力；⑦ 节点A收到拓扑更新请求。

2　基于NS2的220D路由协议扩展

2.1NS2仿真器介绍

NS2(NetworkSimulator,version2)，是一款开源的、离散事件驱动的网络环境模拟器，主要用于解决网络研究方面的问题[6]。NS模拟分两个层次：一是只需编写Otcl脚本，利用NS已有的网络模块实现模拟；另一层次是基于C++和Otcl编程，对NS进行扩展，添加自己要模拟的模块[7]。

2.2220D路由协议扩展

由于NS2现有仿真库中不包括220D路由协议模块，需要添加C++类以实现220D路由协议。本文在添加220D路由协议的编程过程中参考了NS2下的DSDV和DSR路由协议源代码。为了减少拓扑更新的数据量，220D定义了稀疏路由树，类设计代码如下所示：

classspa_table{

public:

spa_table() {bzero(this,sizeof(spa_table));}

nsaddr_tdst;

//Destinationaddress

nsaddr_tpre_dst;

//Nodepredecessoraddress

uinthop;

//hops

uintcost;

boolnr;

boolquiet;

//Quietmode

};

NS2中的Agent代表生成和消耗网络层数据分组的端点，同时被用于实现不同网络层次的协议[4]，其主要功能是在源节点与目的节点之间创建一条端到端的连接。其他路由协议Agent类的实现要继承父Agent类。220D路由协议Agent类部分代码如下所示：

class220D_Agent:publicAgent{

public:

220D_Agent();

protected:

nsaddr_tmyaddr_;

//Nodeaddress

size_tMin_Update_Per;

//MIN_UPDATE_PER

virtualvoidrecv(Packet*,Handler*);

voidneedTriggeredUpdate(spa_table*prte,Timet);

//Triggeredupdate

Packet*makeUpdate(int&periodic);

voidupdateRoute(spa_table*old_stab,spa_table*new_stab);

};

3　220D路由协议性能分析

为了判断和衡量某种路由协议的性能高低，需要通过定性和定量的评估指标来度量[8]。本节主要仿真220D网络cbr流发送速率随着节点停留时间的增大时对网络分组传输成功率的影响。节点停留时间能表征网络拓扑变化的快慢，节点停留时间越短，网络拓扑变化越快，节点停留时间较长时，网络拓扑变化较慢。分组传输成功率指目的节点成功接收到的分组数与发送节点发送的分组数的比值。当节点来不及更新变化较快的网络拓扑时，或者网络负载较大分组之间竞争无线信道时，分组就会丢失，所以分组传输成功率能反映路由协议性能的好坏。

3.1仿真场景

由于本文主要研究220D路由协议，所以在仿真时采用NS2缺省的其他各层协议。设置了如下的仿真场景：在800m×800m区域内均匀放置20个节点，业务是cbr流，每包512字节，网络中节点的最大移动速度为20m/s，移动方向随机，节点停留时间手动设置，仿真时间为600s。

3.2CBR发送速率对220D网络性能影响

cbr流发送速率(单位为kbps)可以表征网络负载，是影响网络性能的重要因素。cbr发送速率越大，说明网络负载越大，网络负载过大时，会导致分组在MAC层碰撞而丢失，使网络性能下降。图5为cbr流发送速率分别取4、8、12和16kpbs时，网络的分组传输成功率情况。

图5　cbr发送速率对网络分组传输成功率的影响

从图5中可以看出，cbr发送速率不变时，网络分组传输成功率大致随节点停留时间的增加而增大；节点停留时间不变时，网络分组传输成功率大致随cbr发送速率的增大而减少。

4　220D路由拓扑更新优化

220D协议标准定义了最小时间间隔来减小拓扑更新频率，但当最小时间间隔取值较小时，拓扑更新发送过于频繁，和cbr流竞争无线信道，导致用户数据分组因碰撞而丢失。而当其值取值太大时，节点就不能及时获取网络拓扑结构，使用过期的路由信息发送或传递分组，会使分组不可达，进而降低了220D网络性能。对于真实的无线自组织网络，特别是在战术环境中，节点移动速度和网络负载都不确定，无法根据这两项参数设置合适的MIN_UPDATE_PER值。因此，如何在节点移动速度和网络负载动态、无规律变化的情况下，既能及时更新网络拓扑信息，又不会占用大量的网络资源导致分组冲突，是220D路由协议需要解决的问题。

针对以上问题，本文提出了一种通过自适应改变最小时间间隔来提高网络性能的方法。对于优化前的网络，当节点需要发送拓扑更新信息时，要等待当前的MIN_UPDATE_PER时间结束后才能发送。本文做如下优化：在每个节点上设定一个队列缓冲区，节点需要拓扑更新时，首先检查更改了的拓扑更新信息是否涉及正在使用的路由信息；如果是，则不需要等待当前最小时间间隔结束，而是立刻发送拓扑更新；否则将拓扑更新包缓存到缓冲区，等待新的最小时间间隔周期到来时，节点从缓存区取出第一条拓扑信息发送出去。当缓存区里的拓扑更新包大于两条时，节点就自动将当前最小时间间隔值减1，即增大拓扑更新频率；相反，如果缓存区里拓扑更新包为0条时，说明节点没有检测到链路变化，就不需要广播拓扑更新包，节点就自动将当前最小时间间隔值加1。

对上述的优化，本文进行了如下仿真和比较。 对优化前的网络将最小时间间隔值(图中用per表示)设置为1和3分钟(per=1或3min)；优化后的网络最小时间间隔自适应改变，优化前后的网络cbr流发送速率都为8kbps，仿真并统计优化前后的网络分组传输成功率，仿真结果如图6所示。

图6　优化前后网络分组传输成功率对比图

从仿真结果可以看出，对优化前的网络，拓扑变化较快时，最小时间间隔为1min时的网络性能优于最小时间间隔为3min时的；拓扑变化较慢时，最小时间间隔为3min时的网络性能稍优于最小时间间隔为1min时的。优化后的网络分组传输功率跟优化前的相比较高，即网络性能更好，且优化后的网络分组传输成功率上下波动较小，即网络性能更加稳定。

5　结　语

本文主要在分析220D无线自组网路由拓扑更新的基础上，针对拓扑更新参数“最小网络拓扑更新时间间隔”设置不合适时，会影响网络性能的问题，提出了一种自适应改变最小时间间隔的220D路由拓扑更新优化方法。基于NS2仿真平台对优化前后的网络进行了仿真对比，结果显示该方法可以改善220D网络性能。本文可为研究其他无线自组网路由拓扑更新或220D路由协议提供一定的参考价值。

[1] 周鑫.自组网中一种基于能量均衡的选择性洪泛路由算法[J].计算机应用与软件,2014,31(7):101-104.

[2] 刘军,孙茜,王英梅.支持网络编码的认知无线自组网拓扑控制算法[J].通信学报,2013,34(5):136-142.

[3]MohapatraS,KanungoP.PerformanceanalysisofAODV,DSR,OLSRandDSDVRoutingProtocolsusingNS2Simulator[J].ProcediaEngineering,2012,30(7):69-76.

[4]IsmailZ,HassanR.AperformancestudyofvariousmobilityspeedonAODVroutingprotocolinhomogeneousandheterogeneousMANET[C]//Communications(APCC),2011 17thAsia-PacificConferenceon.IEEE,2011:637-642.

[5]MIL-STD-188-220D.DepartmentofDefenseInterfaceStandardDigitalMessageTransferDEVICESubsystems[S].2005.

[6] 于斌,孙斌,温暖,等.NS2与网络模拟[M].北京:人民邮电出版社,2007.

[7]LiBaiping,ZhangXiaoqin.RsearchofdevelopmentinwirelesssensornetworkroutingprotocolsbasedonNS2[C]//ElectronicandMechanicalEngineeringandInformationTechnology(EMEIT),2011:1913-1916.

[8] 牛秋娜,王美琴,王英龙.基于NS-2的MANET路由协议仿真及性能评估[J].计算机应用研究,2006,23(9):242-246.

ANALYSISANDOPTIMISATIONOF220DMOBILEADHOCROUTINGTOPOLOGYUPDATES

HuangWei1,2LiQiang1ChenYuanyuan1

1(School of Communication and Information Engineering,University of Electronic Science and Technology of China,Chengdu 611731,Sichuan,China)2(Science and Technology on Information Transmission and Dissemination in Communication Networks Laboratory,Shijiazhuang 050000,Hebei,China)

Topologyupdatesisanimportantcompositionofmobileadhocnetworkroutingprotocol,andakeyfactorthataffectstheadhocnetworkperformance. 220DroutingprotocolsetsthatthetopologyupdatesinformationofnodesshouldnotbetransmittedmoreoftenthanonceeveryMIN_UPDATE_PER.SoinappropriateMIN_UPDATE_PERmayhaveanimpactonthenetworkperformance.Aimingatthisproblem,thispaperproposesaroutingtopologyupdateoptimisationmethodwhichadaptivelychangesMIN_UPDATE_PER.Resultsofsimulationshowthatthismethodcanimprovethenetworkperformance.

MobileadhocnetworkRoutingprotocolTopologyupdates220D

2014-09-10。黄炜，教授，主研领域：移动通信。李强，硕士。陈媛媛，硕士。

TP391.9

ADOI:10.3969/j.issn.1000-386x.2016.03.035