摘要：本文结合舰船编队无线组网的实际需求，提出一种基于QoS 机制的路由协议-CS_AODV.在AODV 协议的基础上，引入用户和数据类型分级机制和多点中继站思想（MPR），设计并实现路径稳定性的度量。应用NS2 仿真软件对AODV 与CS_ AODV 路由协议进行仿真，通过比较分析表明CS_AODV 协议在分组丢失率、端到端延时以及负载开销方面得到有效改善。

0 引言

无线Mesh 网络是一种多跳、自组织和自愈性的分布式宽带无线网络，由于部署简单、使用方便而被广泛应用。但由于无线链路的不稳定性以及带宽资源的有限性，其网络性能无法满足用户对带宽、时延、路由稳定性以及丢包率的需求，这需要提供一定的QoS 保证，而QoS 路由是实现QoS 保证的一个关键因素。目前国内外文献中已经提出很多基于无线Mesh网络的QoS 路由协议。文献[2] 中提出一种基于带宽的QoS路由协议-QRBC,协议应用于实时数据服务环境，为实时数据流选择一条干扰小，保证带宽的稳定路由；文献[3],应用数据传输失败概率去估算路由的有效带宽，这种估算方法主要用于接入控制算法和QoS 路由协议；文献[4] 提出一种多径QoS 路由协议AODV_MQ,采用同时多径机制并以时延为QoS 参数；舰船编队无线移动网络是一种专用网络，应用环境以及传输数据类型都有其特殊性，本文针对舰船编队间的无线移动网络对路由稳定性以及不同数据类型进行分级的QoS 保证要求，通过对现有移动自组网路由协议-AODV 进行改进，提出一种基于AODV 的QoS 机制改进路由协议-CS_AODV（ ClassificaTIonand Path Stability Routin gProtocol based on AODV）。

1 AODV 协议

AODV是一种源路由按需路由协议，实质是DSDV与DSR结合，已被IETF MANET工作组于2003年7月正式公布为自组网路由协议的RFc标准。只要两个节点都都有通向对方的正确路由，AODV是不工作的。当某节点需要同某个目的节点通信而本身没有到该目的节点的路由时，它将广播一个RREQ（路由请求消息）来尝试找到一条到目的节点的路由，所有接到请求的节点都会缓存一条回到发起节点的路由，通过比较分组中的序列号丢弃重复收到的RREQ.如果RREQ消息到达目的节点，这条路由将被找到，目的节点朝源节点单播一个RREP后，这条路由就建立了。中间节点收到RREP 后会建立一条到源节点的前向路由。如果收到RREQ的中间节点拥有到目的节点的路由，且该路由的序列号足够大，则该路由也就被找到，同样返回RREP.如果该路径上某个节点下一跳变得不可达，它就向上游节点发送RERR 分组，通知源节点链路断裂，源节点重新开始路由发现。

2 CS_AODV 协议设计

2.1 优先级设置

舰船编队无线Mesh 组网主要是实现舰船编队统一高效的指挥控制，传输信息主要是指控指令以及各种传感器信息，多媒体业务较少，但对实时性要求很高。网络中不同的节点具有不同的业务优先级别，同一节点的不同数据类型也有不同的级别。而且由于无线移动网络的带宽资源相对有限，信道间控制指令所消耗的带宽必须控制在一定范围内，数据业务等级划分不能太过复杂。CS_AODV 将节点划分为2 个等级（如旗舰和非旗舰），节点产生的数据业务流也划分为4 个等级（如指控、探测、图像及一般业务等），共有8 个等级；等级高的业务先发送，业务等级相同则节点级别高的先发送。协议将AODV 的RREQ 分组中3 个保留位定义为优先级区，如表1,其中3~4 位设为业务等级，级别由高到低依次设为00、01、10、11 ;第5 位设为节点级别，优先级高的节点设为0 ;通过比较优先级区的值来区分不同节点和业务的级别，分组级别越低，其值越大。AODV 的路由表中有到目的节点的路由，也需要对Data 分组增加类似的优先级设置。

舰船编队网络的数据类型以指控和探测消息等为主，以单个分组形式在网络中传送。分组发送过程占用整条路径，在发送分组竞争信道时进行优先级区分。源节点发送分组，先判断网络中是否存在其他高级别分组，若有，在等待NET_TRYTIME = 基本等待时间+ random（class,class+1）（优先级别加上随机退避时间）时间后再次探测，若无，则开始发送分组；否则要继续等待NET_TRYTIME 时间，直到没有更高级别分组发送为止。参数class 表示服务级别，范围：0~7,级别越高，class 值就越小，保证级别高的数据业务优先建立路由。

2.2 引入多点中继

AODV 协议的路由发现以洪泛方式进行，没有给QoS 路由提供引导作用，占用大量网络资源，容易造成网络风暴。为此，本文引入多点中继（Multi-Point Relaying,MPR）[6-7],网络节点在自己的一跳邻节点中选择一部分节点作为自己的MPR,由MPR 转发链路状态消息，实现路由控制消息的选择性洪泛；通过对HELLO 消息进行改进，只传递MPR 选择节点与MPR 之间的链路信息，实现链路状态信息的压缩。

引入MPR 需要对HELLO 消息进行改进。AODV 协议中HELLO 分组只包含了本节点IP 地址、本节点序列号、跳数、发送周期、TTL 以及保留位等信息，邻居节点只能够检测跟本节点的链路信息，因此需要对HELLO 消息进行扩充，添加邻节点地址以及转发分组意愿、链路代码、链路信息大小等状态信息。

定义N1（a） 和N2（a） 为节点a 的一跳和二跳邻居节点表，D（b） 为a 的一跳邻居的出度，MPR（a） 为a 的多点中继站的集合，定义Stab（a）是为了得到节点的相对稳定度。MPR 选择实现算法如下：

1）MPR（a） 初始化为空。

2）计算N1（a） 中每个节点的出度D（b）（以及Stab（a））。

3）能提供唯一可达性到N2（a） 中某些N1（a） 节点的节点添加到MPR（a） ;并将已经添加到MPR（a） 的N2（a） 节点删除。

4）当N2（a） 中仍剩有节点，则计算N1（a） 中未选为MPR的节点的所属N2（a） 节点中仍未覆盖的节点数目，将覆盖最多剩余两跳节点的邻节点加到MPR（a），若出现相同情况，选择出度较大邻节点的作为MPR,并删除相应的N2（a） 节点。

5）比较MPR（a） 所覆盖的N2（a） 节点。若MPR（a） 中某节点的两跳邻居节点是其他MPR（a） 节点的两跳邻节点，则将此节点删除。

2.3 路径稳定性度量

舰船编队组成网络各个节点通常处于移动状态，以某个节点的移动速度来衡量此节点的稳定性并不可靠，但要计算整个网络中每个节点的相对移动速度又比较困难，实现难度大，而且同网络性能提升相比，所增加的网络负荷可能更大。

对于（绝大多数）节点具有相似运动模型的移动网络来说，每个节点都处于运动状态，但对整个网络来说，其拓扑结构是相对稳定，因此可以利用节点相对稳定度事先路由稳定性的QoS保证。CS_AODV 协议引入了MPR 节点，该协议依靠选出的MPR转发RREQ.但由于MPR 的选择不仅与该节点的邻节点相关，而且也与两跳邻节点相关，节点a 的相对稳定性应以该节点两跳范围内所有节点（包括一跳邻节点）的变化情况为依据。

和为节点a 的两跳范围内的邻节点数量，其相对稳定性公式变为：

其中∩和∪分别表示为交集和并集。从上式可以看出：邻节点数量变化越小，Stab 值越大，节点a 的相对稳定性也越高。

实现节点稳定性判定需要对AODV 的跳数判据进行改进，加入相对稳定性度量值，其联合判据函数表示为：

其中：β 为惩罚因子；数值1 表示为一跳，即通过本节点一次，跳数加1.可以看出：Stab 值越大，Metric 值越小。

其路径总度量值为：

根据上式对RREQ 消息格式进行扩充，在类型、标志位、跳数、RREQID、目的节点地址、目的节点序列号、源节点地址以及源节点序列号等内容的基础上，将跳数变为Metric（path）。

3 仿真分析

本文采用NS2 仿真软件进行仿真，设置场景如下：空间为500m*500m,节点随机分布；节点最大移动速度为20m/s ;CBR 数据流，发包率50.0,包大小512byts ;采用802.11 MAC协议、OminiAntenna 天线，Two-Ray Ground ReflectionModel 无线传播模型，仿真时间80s.分别设置10、20、30、40、50、60、80、100 个节点对CS_AODV 和AODV 协议进行仿真，利用MATLAB 进行计算分析。

图1 表示为分组接收率，节点个数小于20 个时，两种协议的分组接收率差别在5% 以内；随着节点个数增加， AODV的分组接收率急遽降低，而CS_AODV 下降比较平缓，这是因为CS_AODV 选择路径时剔除了那些移动速度快的节点，选择的路径相对比较稳定。图2 为端到端延时，如果节点个数比较少，CS_AODV 的延时要高于AODV,随着节点个数的增加，AODV 的时延的增长要比CS_AODV 快得多，节点数增至100 时，AODV 的延时比CS_AODV 高出40ms,主要是由于AODV 的路径相对不稳定，分组重发率高导致延时快速增加。分析图3 看出，在节点数很少的情况下，CS_AODV 的指令开销要比AODV大得多，这是由于选择MPR 节点导致控制开销大量增加；但随着节点数的增加，CS_AODV 协议的指令开销比例慢慢减小，而AODV 的开销在增加，其原因是由于CS_AODV 选择的路径相对稳定，路由发现和重传的指令相对减少。从以上分析来看，CS_AODV 适合于网络规模比较大，拓扑结构动态变化的网络环境中。

4 总结

本文针对舰船编队海上无线组网的实际需求，提出一种QoS机制路由协议-CS_AODV.仿真表明， CS_AODV协议付出一定开销后能大幅提高分组接收率，缩短了端到端延时，并一定程度上提高了路由对动态环境适应性。（作者：盛懿君，刘作学，孙昊翔）