无线双通道Ad Hoc网络分层路由协议设计与分析

杜传报 全厚德 李召瑞 崔佩璋

大规模战术场景应用下,DCN通常使用基于全连通子网的分层分布式网络拓扑结构[1],设计合适的分层路由协议成为关注对象.基于分层分布式网络拓扑结构的Ad Hoc网络路由协议研究很多,主要有簇头网关交换路由CGSR[2]、分布式核心抽取Ad Hoc路由CEDAR[3]、区域路由协议ZRP[4]、分簇结构路由协议CBRP[5]、区域分层链路状态ZHLS[6]、开放最短路径OSPF[7]、分簇发布/订阅路由CPSR[8]和大规模MANET分层共享路由LSRM 模型[9]等协议.CGSR要求簇内使用TDMA和簇间使用CDMA多址接入协议,CEDAR使用最小连通支配集构建虚拟核心结构传输路由,ZRP是基于混合表驱和按需路由思想实现路由寻找,CBRP基于表驱策略利用邻跳拓扑信息实现路由查找,ZHLS需要使用GPS定位设备完成寻路.CPSR引入发布/订阅树规则,通过使用以内容为基础的路由方式转发事件以避免过高的路由开销.LSRM是在网络的物理拓扑结构上构造P2P逻辑覆盖环以提高路由效率和网络扩展性.依据DCN网络拓扑结构特点,将借鉴CBRP路由设计思想,设计符合DCN网络的分层路由协议.

本文设计了一种面向基于分层拓扑的双通道网络分层路由协议(Dual-channel network clustered routing protocol,DNCRP).簇内路由,由于子簇为全连通网络,簇内节点1跳可达,则簇内节点直接进入DNCRP的数据通道分配阶段.簇间通信,DNCRP使用2跳邻簇信息和节点信息以表驱方式完成基于源簇的2跳邻簇内簇间路由寻找,使用基于总簇首的拓扑信息计算和AODV混合方式完成2跳邻簇外簇间路由寻找.最后使用OPNET网络仿真软件仿真DNCRP.仿真结果表明DCN路由具有优越的端到端时延和网络吞吐量.

1 无线双通道网络

战术网络中群网内部的子网区分通常使用码分组网方式,其使用的跳频序列本质是时频序列,代表的时频资源称为码分资源.以正交同步组网为例,实际使用的子网数目远远小于可用的正交跳频序列数目,造成码分资源的严重浪费.如图1所示,群网1频率集为{f0,f1,f2,...,fn−1},频率集数目为n,组网容量为n,子网数目为m,序列m+1∼m为空闲码分资源.

图1 空闲码分资源示意图

双通道网络[10]使用分簇结构,每个子簇为全连通网络结构,由子簇头节点和网关节点构成虚拟骨干网络.子簇簇头节点负责维护本簇管理信息,网关节点负责连接相邻簇间的通信,虚拟骨干网络选举出一个总簇首节点负责全网管理信息的维护.节点通过时分机制切换收发信机完成控制通道和数据通道的转换.全网管理、路由等维护信息均在控制通道上传输,数据通道只传输数据业务.同时,传输数据业务的路由上所有节点的收发机信道切换至数据通道,并固定周期返回到控制通道收发相关控制信息分组;无数据业务的节点收发机信道一直停留在控制通道上收发控制分组.图2为分层分布式DCN网络结构示意图,其中上层虚拟骨干网络由各子簇簇首和网关节点构成,实线为数据通道,虚线为控制通道.

2 DNCRP协议设计

由于子簇为单跳网络,DNCRP协议不考虑簇内路由寻找,仅考虑簇间路由寻找.其中,DNCRP使用邻簇信息表(Neighbor cluster information table,NCIT)记录2跳邻簇范围内的相邻子簇ID号,使用节点信息表(Node information table,NIT)记录全网节点所属子簇ID号,并且总簇首节点使用簇信息表(Cluster information table,CIT)记录所有子簇的邻簇关系,使用簇内节点信息表(Intracluster node information table,INIT)记录子簇内部节点状态属性.不同于传统分簇路由协议,DNCRP的路由发现将目的节点的路径寻找转换为对其所属子簇的路径寻找.簇间路由发现时,2跳邻簇范围内的目的节点路由寻找使用基于源簇的2跳邻簇拓扑信息查找获得;两跳范围之外的路由寻找使用基于总簇首的拓扑信息路由计算和AODV路由寻找的混合方式实现.由于战术应用场景和指挥隶属关系的特定限制,双通道网络数据业务主要为簇内通信,而簇间通信业务则主要以2跳范围内友邻单位间通信为主.因此,AODV路由寻找只有在基于总簇首路由计算方法寻路失败时才作为补充路由策略启动使用.DNCRP协议主要分为主要数据结构、网络拓扑信息更新、路由发现、数据通道分配和路由维护组成,均是在节点切换在控制通道上完成信息交换.以下为协议主要工作流程.

图2 分层分布式DCN网络结构

2.1 主要数据结构

总簇首节点维护数据结构为CIT和NIT,子簇首节点维护的数据结构为NCIT、INIT和NIT,每个节点均维护INIT.

每个子簇首节点维护一张NCIT,其表达式为

式(1)表示该子簇在2跳邻簇范围内的所有子簇ID,其中i∈Num1hopnc表示子簇的1跳邻簇范围内的子簇ID,j∈Num2hopncid1i表示该子簇1跳邻簇ncid1i的所有邻簇ID,ti表示最近更新时间.邻簇信息表是通过簇首间的Hello分组定期完成信息交换更新,如果ti大于更新时间门限,则主动向1跳邻簇i发送簇信息更新请求.以簇为单位的k跳邻簇范围示意见图3,其中簇2是簇1的1跳邻簇,簇3是簇1的2跳邻簇.

每个子簇首节点和簇内其他节点维护一张INIT, 表达式为表示该子簇簇内节点ID和节点状态类型stat,ti表示最近更新时间,Numintrac表示簇内节点数目.当簇内某节点离开此簇或进行控制通道和数据信道之间的信道切换时,均需要向该簇首节点发送状态更新分组.若ti大于更新时间门限,则节点i可能出现故障或关机等问题,需要主动向此节点发送探测分组.

上述信息表更新均是相关节点在控制通道完成节点状态探测和收发.限于文章篇幅,具体更新过程略去.

图3 k跳邻簇范围示意图

2.2 路由发现过程

源节点A发起到目的节点B的路由发现时,主要的路由控制分组格式见表1.路由发现流程如图4所示,具体步骤如下.

步骤1.源节点A查其簇内节点信息表INIT:若B不是簇内节点,则向其簇首节点(源簇首节点)发送路由申请分组RREQ_OCH,到步骤2;否则,源目节点1跳可达,直接进入数据信道分配阶段.

表1 路由发现过程中的主要控制分组格式

图4 DNCRP路由发现流程

步骤2.源簇首节点收到RREQ-OCH分组后,查找节点信息表NIT,获取目的节点B所属的目的簇ID,检查邻簇信息表NCIT:若目的簇为2跳内邻簇,到步骤3;否则,到步骤4.

步骤3.源簇首节点根据NCIT计算出2跳的源目簇路径(即簇路由表),向目的簇发起RREQ-DCH分组.目的簇收到该分组后,检查INIT:若节点B状态为空闲或其数据业务优先级低于节点A发起的数据业务,则进入数据通道分配阶段,到步骤6;若节点B的现有数据业务优先级和发起的数据业务相等,且节点B状态不是交叉节点,则设定B为交叉中继节点,同时进行原有数据业务和发起数据业务的双数据通道通信,进入数据通道分配阶段,到步骤6;否则,沿反向路径向源簇返回RREP-FL分组,源簇首节点向节点A发送RREP-FL分组.若找不到目的簇,则说明NCIT信息过时,向源簇首节点返回RREP-FL分组.源簇首节点收到RREP-FL分组后,到步骤4.

步骤4.源簇首节点向总簇首节点发送路由申请分组RREQ-CCH.总簇首节点检查簇信息表CIT,计算出源目簇路径,返回给源簇RREP-CCH.源簇首节点向目的簇发起RREQ-DCH分组.目的簇收到该分组后,检查INIT:若节点B状态为空闲或其数据业务优先级低于节点A发起的数据业务,则进入数据通道分配阶段,到步骤6;若节点B现有数据业务优先级和新建数据业务优先级相等,并且节点B不是交叉节点,则进入数据通道分配阶段,到步骤6;否则,沿反向路径向源簇返回RREP-FL分组,源簇首节点向节点A发送RREP-FL分组.若找不到目的簇,则说明NCIT信息过时,向源簇首节点返回RREP-FL分组,到步骤5.

步骤5.若因为相关管理信息表项失效而导致寻找不到目的簇,则通过使用和AODV协议类似的按需路由寻找方法进行泛洪式寻找目的簇,具体过程略,详见文献[11].找到目的簇后,到步骤6.

步骤6.路由寻找结束,进入数据通道分配阶段.方案规定节点的通信状态为空闲、数据通信状态;交叉节点.其中,交叉节点最多只能同时中继两条数据通道.

2.3 数据通道分配

当路由发现结束时,即目的簇确认节点B可以进行新数据通道的建立时,目的簇向总簇首发送RREQ-SeqID分组.总簇首根据可用码分资源池中剩余跳频序列,携带预分配序列ID向节点B发送RREP-SeqID分组.节点B收到RREP-SeqID后,向源节点A发送RREP-SC分组,沿反向簇路由逐跳寻找前后簇的空闲网关节点,分组中须携带序列ID、信道切换起始时间和反向簇路由.中继节点转发RREP-SC分组时,RREP-SC分组将更改最新的到目的节点的前向路由.被选为该数据通道的中继节点,将根据RREP-SC分组中的前向路由信息更新自身路由表中关于该数据通道的路由表项.源节点收到该分组时,通过源簇首节点向总簇首节点报告数据通道分配完毕的分组COMPLETE,开始在约定的信道切换起始时间,路由上的所有节点同时将收发机切换到预分配的序列上,开始数据业务通信.为了更加形象说明数据通道分配过程,以源节点A和目的节点B的数据通道分配为例,如图5所示.

若源目节点位于相同子簇,则簇首节点向总簇首发送RREQ-SEQSPECIAL分组,总簇首通过源簇首节点向节点B发送RREP-SeqID分组.节点B再向源节点A发送RREP-SCSPECIAL分组,源节点A收到此分组后的后续处理过程同多跳路由处理过程.主要控制分组格式见表2.

图5 数据通道分配举例

2.4 路由维护

在源目节点使用数据通道通信时,通道上所有节点必须固定时间间隔同时将收发机切换至控制通道,完成控制管理信息的交互,比如了解是否有更高优先级的数据通信业务需要使用数据通道上的某个节点.方案规定只要是节点切换信道,必须及时向所在子簇首节点发送状态更新分组,如:1)当节点从控制信道切入数据通道前,须向子簇首节点发送状态更新分组;2)当节点从数据通道切入到控制信道后,须向子簇首节点立即发送状态更新分组.数据通道上的时间同步由源节点定期发送同步校准信号至目的节点,完成通道上所有节点的时间精准同步.假设某数据通道路由表为A−→C−→D−→E−→B,如果中继节点D出现故障、重启等原因,上一跳节点C联系不到节点D时,则节点C在下一个控制通道周期内,向此节点D发送携带序列ID、信道切换时间和路由表项的问询分组RREQ-REPAIR1,若是收到节点D的RREP-REPAIR1时,则修复成功;否则,认定节点D消失,同时向和节点D所属同簇且功能相同的空闲网关节点发送RREQ-REPAIR2分组,寻找能够连接到节点E的中间路径,如果找到某节点F可连接到节点E,则节点F向节点C发送RREP-REPAIR2,则数据通道路由表改为A−→C−→F−→E−→B,同时节点C向源节点A返回携带最新路由的REPAIR-SC分组,完成路由修复.如果上述修复均未能实现,则节点C向源节点A返回错误分组RERR-SN,收到该分组的上游路由节点均释放现有信道资源并返回控制通道,源节点A重启路由发现;而中继节点E在一段时间未收到上一跳节点的数据分组后,认为路由失效,同时向目的节点发送错误分组RERR-DN,释放信道资源,收到RERR-DN的路由节点均切换至控制通道.如果该路由上有交叉节点,则交叉节点收到错误分组后仅撤销故障路由并转到另一条数据通道上收发数据,并在下一个控制通道周期内向其子簇首节点更改节点状态.主要控制分组格式见表3.

表2 数据信道分配阶段主要控制分组格式

表3 路由维护主要分组格式

3 仿真和分析

本节使用OPNET网络仿真软件对DNCRP协议进行了性能仿真,并和典型分层路由CBRP分别从平均端到传输时延、网络吞吐量等性能参数角度进行了性能比较.网络仿真场景选择超短波战术电台组网下的典型参数配置.网络覆盖范围在40×40km2的战场区域,节点传输范围为5km,节点数目为100,平均分布在10个子网中.节点工作频段为30MHz∼87.975MHz,信道带宽为64Kbps,跳速为200跳/s,频率集数目256,数据分组长度为128B,控制分组为128bit,信道切换时延为80ms,可用信道数目受DCN网络控制通道信道带宽和数据业务控制分组带宽的比值决定,这里设可用信道数目为80.物理层采用Two-Ray传播模型,节点使用参考点群组移动模型[10](Reference Point Group model,RPGM)跟随群组低速移动,链路层使用IEEE 802.11 DCF协议.网络使用基于CBR模型的业务流,其主要用于具有实时性传输质量要求的话音传输过程中,并且业务类型主要分为簇内通信业务和簇间通信业务两种,其业务生成速率、业务数目、业务类型等根据具体的性能评价标准设定.网络使用正交同步组网方式,跳频序列集为正交序列.CBRP应用于传统的Ad Hoc网络环境中,子网数目和双通道网络相同,但所有子网均使用同1条跳频序列,便于实现全网网间通信.再者,传统网络链路层使用IEEE 802.11 DCF协议.

首先分析网络性能随业务流速率的变化情况.设网络有10条簇内业务流和10条簇间业务流,业务流速率变化范围为512bps、1024bps、2048bps、4096bps、8192bps、16384bps和32768bps,业务流分布均匀,节点移动速率为0m/s.网络性能仿真结果取10次独立仿真运行后的性能参数结果平均值,仿真结果如图6和图7所示.

据图6可知,当业务流最大速率32768bps满足单条跳频序列的信道带宽并且业务流网络开销远远小于DCN网络控制通道信道带宽时,业务流速率对DNCRP协议的平均端到端时延影响很小.相反,由于传统网络所有业务竞争相同跳频序列的信道带宽资源,故随业务流速率增加业务的平均端到端传输时延快速增加,影响业务实时性能.据图7可知,由于DCN每条业务独自使用一条跳频序列的信道带宽,故业务流速率小于信道带宽时,DNCRP协议的网络吞吐量增加显著.相反,CBRP协议的网络吞吐量在业务速率较小时呈增加态势,当业务速率过大时,会产生更多的分组冲突,网络总业务负载趋于饱和,网络吞吐量趋于稳定.

图6 平均端到端时延VS业务流速率

图7 网络吞吐量VS业务流速率

其次分析网络性能随业务流数目的变化情况.业务流速率为4096bps,业务流数目分别为4、8、12、16、20、25和30,其中簇内和簇间业务流数目相同,业务流分布均匀,节点移动速率为0m/s.取10次网络运行结果的平均值作为仿真结果,如图8和图9所示.

据图8、图9可知,当业务流速率小于信道带宽,业务流数目小于DCN网络可用信道数目时,DNCRP的平均端到端传输时延不随业务流数目变化,而网络吞吐量随业务流数目增加快速上升.相反,传统网络由于竞争信道资源的业务数目增多,分组冲突加剧,网络趋于饱和,平均端到端时延增加,网络吞吐量逐渐趋于平缓.因此,DNCRP协议在高业务负载条件下具有无可比拟的优势.

图8 平均端到端时延VS业务流数目

图9 网络吞吐量VS业务流数目

4 结论

本文针对分层分布式拓扑结构的无线双通道网络提出了一种新的分层路由协议DNCRP,该协议在传统分层协议CBRP基础上改进设计而成.DNCRP协议借鉴混合表驱按需路由思想,充分利用网络拓扑已知信息,完成簇间通信路由寻路.仿真结果显示,在高业务负载条件和低速拓扑变化条件下,DNCRP协议由于利用了多条空闲跳频序列而具有更低的平均端到端传输时延和更高的网络吞吐量.