基于WiFi的自组织网络路由协议算法研究

毕海霞 魏志强 薛广然 贯林林

(1.西安电子工程研究所 西安 710100;2.92995部队 青岛 266100)

0 引言

自组织网络是近年来无线移动通信网络发展的一个热点，其主要特征是无中心、自组织、多跳路由和动态拓扑，具有网络快速部署、抗毁性强和组网灵活等优点。网络中的节点具有双重角色，既是普通移动终端，又具有路由器的功能。当通信的源节点和目的节点无法直接通信时，可通过中间节点进行报文转发［1］，实现多跳无线通信的功能［2］。然而，在实际应用中，通常存在无线信道传输速率低的瓶颈，这成为制约自组网发展的重要因素。WiFi(Wireless Fidelity)，又称802.11标准，由IEEE工作组于1999年9月提出，其最大特点即传输速度高，其中，802.11b的速率可达到11Mbps［3］。近年来，WiFi业务呈现爆炸式增长，新的WiFi标准相继出台，802.11n的速度最大可至300Mbps，WiFi技术及产品亦日臻成熟。

将WiFi技术应用于自组织网络，建立高速的自组网移动网络，能够提高数据传输速率，充分发挥两种技术的优势，具有非常广阔的应用前景，可用于战场上部队的快速部署和推进，地震或水灾后的抢险救灾，以及其他临时组网应用等。近年来，各国军方都在积极论证将WiFi应用于战场车载自组织网系统。因为将基于WiFi的自组织网络应用于实际军事，可以带来很多突出优点。比如，可提高战术互联网的无缝链接，提高数据传输和态势感知能力。另外，其通信距离小，可提高系统的抗截获能力等。路由算法是自组织网络中最重要的一部分，其设计的高效与否直接影响到网络性能。本文通过对典型的自组网路由协议进行仿真实验分析，并针对战场环境下的大规模组网以及火控数据传输需求，并提出了一种新的路由算法。

1 基于WiFi的自组网路由算法

按照自组网路由发现策略的方式，可将自组织无线网络路由协议分为先应式路由与反应式路由。先应式路由又称为表驱动路由协议，在这种路由协议中，无论是否有通信需求，每个节点周期性的广播路由分组，交换路由信息，维护到达其他节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送更新消息。收到更新消息的节点将更新自己的路由表，以维护准确的路由信息。常用的先应式路由算法包括 DSDV［4］、WRP、OLSR、FSR 等。反应式路由协议又称为按需路由协议，它根据网络分组的传输请求，被动地搜索从源节点到目的节点的路由，当没有分组传递请求时，节点处于静默状态，并不需要交换路由信息。典型的反应式路由算法包括 DSR［5］、AODV［6］、LAR［7］等。

根据IETF RFC2501，自组网网络的仿真参数主要有端到端吞吐量和时延、寻由时延、分组投递率、寻由开销与效率以及平均跳数等。由于WiFi网络的传输速率较高，路由开销及寻由时延对网络效率影响不大，分析中不考虑这两个因素，而选择端到端时延、报文投递率和端到端吞吐量三个指标作为主要评价参数。

a.报文投递率(packet delivery ratio)，即目的节点接收到的数据包个数与源节点发送的数据包个数的比值，反映了网络传输的可靠性，报文投递率越高，可靠性越大。

b.端到端时延(end-to-end data delay)，即报文从源节点到目的节点的平均延迟，反映了应用层中分组的时间特性。它包括路由发现和端口排队时分组在缓冲区中的延时，也包括MAC层进行重传以及分组传播的时间。

c.端到端吞吐量(throughput)，在较大程度上可反映应用层数据的传递速率。

针对以上三个性能指标，本文选用OPNET仿真平台分别对AODV、DSR、LAR和OLSR路由协议进行分析比较。节点移动方式选取组移动模型(Group Mobility Model)，节点个数为50个，节点移动速度从1m/s到25m/s，范围是10km×10km的区域。MAC层采用IEEE802.11协议，网络带宽为5.5Mbps，每个数据包大小为500bytes。

1.1 节点移动速度的影响分析

节点移动速度的不同反映了网络拓扑结构变化的快慢。节点移动速度越快，则网络的拓扑结构变化越快。对基于 WiFi的自组织网络而言，由于WiFi无线信号覆盖的范围较小，节点间的通信距离较短，因此，网络拓扑结构的变化对于系统的影响较大。下面分析平均报文传递率、平均端到端时延和平均端到端吞吐量与节点移动速度的性能关系。

当节点移动速度的增大时，四种协议的报文传递率均出现下降的趋势，如图1所示。三种反应式路由算法AODV、DSR和LAR的报文传递率相差不大，而先应式路由算法OLSR的报文传递率明显低于三种反应式路由算法，尤其是当移动速度大于5m/s时，OLSR的报文传递率下降迅速。这是因为，随着节点移动速度的加快，网络拓扑变化频繁，OLSR作为先应式路由算法，其维护路由信息的开销迅速增长，导致报文传递率的下降。

端到端的时延受节点移动速度影响。节点移动速度增大，时延亦随着增加，如图2所示。OLSR作为先应式路由，由于周期性地维护最新的路由信息，在报文传递时，无需重新寻由，因此，其端到端时延的性能指标优于其他三种反应式算法。反应式路由DSR和LAR的端到端时延随移动速度的增长呈现明显的增长趋势。这是由于随着节点移动速度的增大，网络拓扑变化增快，反应式路由协议需不断重新寻找路由及建立连接，从而导致报文传输的端到端时延增大。AODV虽然也是反应式路由，但它维护了到目的节点的多条路由，即具有冗余路由的特性，当网络拓扑变化频繁且原路由失效时，该算法可迅速切换至其他活跃路径上的路由。该特性使得AODV算法较其他反应式路由在端到端时延性能上表现优异。需注意的是，LAR算法的端到端时延性能曲线呈现出不稳定增长的特征，这是由于LAR根据节点位置信息不断变换查询范围所致。

图1 平均报文传递率与移动速度的关系

图2 平均端到端时延与移动速度的关系

端到端吞吐量随着节点移动速度的增大而呈下降趋势，如图3所示。三种反应式路由算法的吞吐量性能优于先应式算法OLSR，这是因为作为先应式算法，为使得路由信息及时更新，OLSR需要周期性地向其他节点发送路由信息，导致路由开销花费较大。在三种先应式路由算法中，LAR的性能略优于AODV和DSR，这是由于LAR利用地理位置信息，缩小了搜索范围，寻由开销更小。

图3 平均吞吐量与移动速度的关系

1.2 包发送间隔的影响分析

网络负载是评估算法性能的重要因素，本文用报文的发送间隔的变化模拟网络负载的变化，对三个性能指标与报文发送间隔的关系进行了仿真，节点移动速度设为10m/s。

三种反应式路由算法AODV、DSR和LAR的平均报文传递率随包发送间隔的增大呈现先减小后增大的趋势，如图4所示。网络负载初始增大时，网络逐渐变得拥塞，所以，报文传递率下降。当包发送间隔较小时，由于节点在持续移动，网络拓扑在不停地变化，导致反应式路由算法需重新寻由。而当包发送间隔的增大到一定程度时，路由在两次包发送间隔之间变化较小，使得之前的路由可被重用，因此，报文传递率曲线重新上扬，AODV的增长趋势尤其明显。随着网络负载的增大，先应式路由算法OLSR的维护路由的开销持续增大，加剧了网络负载的增长，报文传递率呈现下降趋势。

随网络负载的增大，四种算法的端到端时延总体呈现上升趋势，如图5所示。其中，AODV和OLSR的延时明显低于反应式路由LAR和DSR，这是由于OLSR为先应式路由，发送数据时无需重新寻由，而AODV则具有链路快速切换机制。

随着网络负载的增大，吞吐量总体呈现减小趋势，如图6所示。由于维护路由的开销较大，OLSR的吞吐量较其他三种反应式路由算法小。三种反应式路由算法AODV、DSR和LAR的吞吐量性能相差不大，但当负荷持续变大时，AODV的吞吐量性能略优于其他两种算法。

图4 报文传递率与包发送间隔的关系

图5 端到端时延与包发送间隔的关系

图6 平均吞吐量与包发送间隔的关系曲线

从上述分析结果看，在基于WiFi的自组织网络中，反应式路由的性能优于先应式路由的性能。由于WiFi节点间的通信距离有限，当节点处于移动速度状态时，拓扑结构变化频繁，路由失效的几率变大，先应式路由算法维护路由的开销也会增大，因此，反应式路由的性能更强大。而AODV协议由于具有链路快速连接机制以及快速切换至活跃路径的特性，在高节点移动速度及高负载的网络中性能优异，具有优良的吞吐量和报文传递率，更小的端到端延时，以及高稳定性。

2 分簇网络路由算法

从上文的仿真结果看，AODV算法在基于WiFi的自组织网络中性能较其他三种算法优异，但对于战场应用环境，仍不满足要求。首先，AODV算法是针对平面式拓扑结构而设计的，而在战场环境下，存在按照部队编制进行扩展的需求，对网络的扩展性要求较高，因此，需要将路由算法设计为分层路由算法;再次，火控数据对端到端时延要求较高，一般要求控制在一百毫秒以内，而AODV路由算法在节点移动速度较高时，无法满足该要求。为满足战场环境下的上述需求，结合AODV算法的优势，本文引入建立分簇结构的思想，提出了一种新的分簇路由算法CRP(Cluster Route Protocol)。

该算法包括分簇算法和路由协议两部分。分簇算法描述如下:

CRP对节点进行传输功率的判别，只有满足一定传输功率的节点才能参与簇头的选举。簇头选举算法设计的原则为选择节点密度大处的节点作为簇头，综合考虑节点度数以及与邻居节点的距离和。对每个满足功率约束的节点，进行综合权值结算，选择权值最小的节点作为簇头。权值计算公式如下:

其中，Wi代表节点 i的权值，w(j=1，2，3)代表不同影响因素的权值系数;N为节点i的邻居节点个数，D为该节点与其邻居节点的距离和。从该权值判断规则可知，若某节点的邻居节点个数越多，与其邻居节点距离越近，则其更适合成为簇头。

网络初始化流程如下:所有的节点广播自己的ID，其辐射范围内的节点收到此广播后，记录此ID，之后，两者互发消息，告知对方节点自己的发射功率，通常发射功率的衰减与距离的四次方成正比，因此，通过对发射功率衰减的测量，可估算出两节点间的距离。这样，所有的节点均维护了其邻居节点的ID以及它们之间的相对距离。此时，根据上文提出的分簇算法，每个节点进行权值计算，权值最小的节点成为簇头。但是，簇不可无限制地增大，因为如果簇的节点过多，则分簇路由的性能得不到体现，会导致整个网络吞吐量的降低。本文利用跳数限定簇的大小，簇头与簇内节点之间的跳数必须小于两跳。分簇结束后，簇内非簇头节点需维护自己所在簇ID以及其簇头节点的信息。

簇的维护流程如下:簇头与簇内每个普通节点定期进行心跳包交互。当簇头在一定时间段内未收到某节点的心跳包时，则认为该节点已离开该簇，将该节点从簇内成员列表中删除;当收到新的节点的入网申请时，则判断该节点是否满足入簇条件，比如与簇头节点是否两跳内可达，该簇的节点数是否超出限制等，若满足入簇条件，则将该节点加入本簇;若不满足条件，则通知该节点继续寻找新的簇头，若寻找不到，则自立新簇。当移动的两簇之间的距离小于等于某一规定要求，且满足簇合并条件时，需对其进行合并。

CRP路由协议部分描述如下:

a.协议帧的结构与AODV路由协议的帧结构类似，只是在协议头中新增2个bit，一个bit用于标识本节点的角色，即本节点是否为簇头、普通节点或者网关节点，另一个bit用于标识节点所在簇的簇ID。因此，当传输的源节点和目的节点在同一个簇内时，则直接在簇内进行转发;若源节点和目的节点不在同一个簇内，则通过簇头节点或者网关节点进行转发，以至到达目的簇中的目的节点。

b.当源节点需要和目的节点通信时，如果在路由表中可查询到对应的路由时，不进行任何操作。当源节点需要和新的目的通信时，就会发起路由发现过程，通过广播RREQ信息来查找相应路由。当这个RREQ到达目的节点本身，或者是一个拥有足够新的到目的节点路由的中间节点时，路由确定。目的节点或中间节点通过原路返回一个RREP信息来向源节点确定路由的可用性。转发RREQ的节点将根据RREQ是否设置了快速转发标记来决定采用快速路由查找或与AODV相同的普通路由查找。快速路由查找是按簇ID和簇节点ID的方式实施的。如在规定的时间内未找到路由，再采用普通的路由查找方法。

c.AODV采用的是超时删除路由机制，因此即使路由未失效，在超时时限后也将被删除。CRP将路由超时删除机制修改如下:若路由超过时限，则判断路由是否有效，若有效，则此路由继续保持;若无效，则删除。

d.当链路破坏时，节点并不立即发送RERR给源节点，而由其下游节点尝试进行局部路由修复。若局部路由可成功修复，则可将网络的链路坏区局限在一个小的范围内，避免了大规模的网络重构，提高了网络修复效率。如果路由局部修复不成功，再向源节点发送RERR信息。

e.该协议兼容AODV算法。当由于节点移动等原因，使得之前的簇结构遭到破坏，无法满足数据传输要求时，则不再使用分簇结构，而是利用AODV的路由进行广播，并在此过程中重新建簇。

针对平均报文传递率、平均端到端时延和平均吞吐量三个性能指标，本文选用OPNET仿真平台分别对本文提出的CRP路由算法、AODV路由算法和经典的分簇路由协议ZRP［8，9］进行仿真和比较。节点移动方式选取组移动模型(Group Mobility Model)，节点个数为50个，节点移动速度从1m/s到25m/s，范围是10km×10km的区域。MAC层采用IEEE802.11协议，网络带宽为5.5Mbps，每个数据包大小为500bytes。仿真结果如图7所示。随着节点移动速度及网络负载的增大，CRP协议的平均包传送率，平均端到端时延以及平均吞吐量三个性能均优于AODV算法。

随着节点移动速度的增大，网络的拓扑变化加快，导致需要频繁的重新寻找路由，所以，协议的时延会增加，而CRP协议中的节点增加了快速转发标记，使得路由查找的速度大为提高，从而能够更好地适应高速移动的场景;并且，在路由修复方面由于路由能够很快被修复，大大提高了准确率，从而减少了数据包的丢失;随着网络负载的增大，由于CRP协议采用了分簇结构，减少了节点移动对路由算法的影响和路由发现过程中的洪泛开销，加速了路由的查找过程，增加了网络吞吐量，缓解了网络局部拥塞，保证了分组传递的成功进行。端到端时延降低了约30%，在节点移动速度为25m/s时，仍小于100ms，满足了火控数据的传输要求。

经典分簇路由协议ZRP在簇内运行先应式路由协议，需要周期性的发送广播来维护和更新路由表;簇间运行反应式路由协议。在节点移动速度较小时，网络拓扑变化小，路由维持开销小，且先应式路由协议可以快速地寻由，因此，ZRP算法的性能总体优于CRP算法。但随着节点移动速度的加快，网络拓扑变化频繁，簇内先应式路由协议的网络开销迅速增大，此外，在进行簇间路由查找时，边界节点收到路由请求无法回应后，就需要把请求向未查找过的簇转发，势必会产生大量的多播或广播数据，网络的运行效率降低，因此，ZRP算法的性能比CRP算法差。

图7 AODV、CRP和ZRP性能比较

3 结束语

本文利用仿真平台OPNET对基于WiFi的自组织网络中的AODV、DSR、LAR和OLSR四种路由协议进行了仿真比较。通过对平均包传送率，平均端到端时延以及平均吞吐量三个性能指标的综合比较发现，AODV协议的性能优于其他三种算法。针对战场环境下，车载自组网网络扩展性以及火控数据传输时延的要求，基于AODV算法，本文提出了一种新的分簇自组网路由算法CRP，其分簇网络结构的设计减少了节点移动对路由算法的影响和路由发现过程中的洪泛开销;其快速转发机制加速了寻由过程;其局部路由修复机制限制了链路坏区的扩展，提高了网络的修复速度。实验仿真结果证明了该算法的优越性。

［1］于宏毅，无线移动自组织网［M］.北京:人民邮电出版社，2005.

［2］E.Baeeelli，C.Perkins.Multi-hop Ad Hoc Wireless Communication［OL］.IETF Internet Draft，draft-baccelli-multi-hop-wirelesscommunication-05，2010.

［3］O’Reilly.802.11无线网络权威指南［M］.南京:东南大学出版社，2007.

［4］Perkins C E，Bhagwat P.Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV)for Mobile Computers［OL］.ACM SIGCOMM’94 1994.

［5］David B Johnson，David A Maltz，Hu Yih-Chun.The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks(DSR)［OL］.IETF Internet Draft draft-ietf-manet-dsr-09.txt，2003.

［6］Charles E Perkins，Elizabeth M Royer.Ad Hoc On-Demand Distance Vector Routing［C］.2ndIEEE Workshop on Mobile Systems and Applications，2006.

［7］Ko Young-Bae，Nitin H.Vaidya.Location-Aided Routing(LAR)in Mobile Ad Hoc Networks［J］.Wireless Networks，2000，(6):307-321.

［8］ZygmuntJ.Haas，MareR.Pearlman，Prinee Samar.The Zone Routing Protocol for Ad Hoc NetworkS［OL］.IETF Internet Draft，draft-ietf-manet-zone-zrp-04.txt，2002.

［9］肖迎杰，肖宗水，苏继斌，基于工ZRP的移动Ad Hoc分级网络管理［J］.计算机工程，2009，35(13):114-116.