基于ODMRP的分布式核心稳定路由算法①

傅 伟,周新力,刘 军

1(海军航空大学 电子信息工程系,烟台 264001)

2(66135部队,北京 100144)

1 前言

当前无人机的作战形式由单机作战向多机联合作战形式转变,无人机群所展现出来的全方位大范围的作战能力是单个无人机所无法比拟的,但是这种高速高动态的作战环境需要更加灵活的通信方式和严密的标准.移动自组网络(Mobile Ad hoc NETwork,MANET)以其无中心、自组织、动态拓扑和多路径的特点,成为集群作战的首选方式.组播网络作为MANET网络形式中的一种就具有广阔的应用空间,特别是在无人机战术网络平台,通过一对多的数据分发使得信息的传输更加及时高效.和单播路由协议相比,组播网络可以实现多种信息的同传,大大节省了网络带宽.但是移动网络中由于拓扑结构不断变化,对于组播组的结构和维护消息也会大幅增加,这就要求对组播网络进行改进以适应移动网络环境.

近些年不少学者研究并提出了较多组播路由协议.文献[1]提出了一种结合贪婪算法与区域组播的结合的组播协议,虽然通过源节点能够较快的聚合出最优路径但也增加了源节点的负担,也没有解决贪婪算法会遇到的空洞问题.文献[2]提出了一种基于区域划分的地理组播协议,但是区域角的确定只适用于静止的网络,节点的移动会产生较大影响.文献[3]提出了一种基于能量高效的组播协议,采用最短路径的思想寻找耗能最低路径,算法对特定节点的过分消耗会加速网络的崩溃.文献[4]通过改变路径来实现能量的动态均衡,但是没有考虑路径信息的传输对网络能量的消耗.文献[5]提出了一种分层式的节点自适应修复方法,通过设置冗余节点对失效节点进行修复,但是大量冗余信息的储存造成网络资源的消耗.文献[6]提出了一种混合式的应用层组播恢复方法,解决了中心节点失效造成的网络瘫痪,但是网络的组织具有较高的复杂性.

虽然我国在无人机领域取得了一定的成就,一部分民用无人机研发机构也实现了对多无人机的操控,但是这种基于表演性质的操控对于真正应用于战场环境还有较大差距.同时,军用无人机对于提升无人机协同作战能力具有迫切需求,目前为止只实现了对两架无人机的同时操控.因此,开展对于无人机自组织网络协议的研究,为实现真正的无人机集群作战的通信,具有较大的军事价值和研究意义.

2 ODMRP协议改进机制

ODMRP(On-Demand Multicast Routing Protocol)协议是一种网格型的组播路由协议,转发路径的形成是按需发起的.由于采用洪泛机制发起路由,多节点的重复广播很容易引起冲突导致报文丢失,同时随着网络的扩大,即使有范围洪泛对开销的控制,也会造成无法避免的巨大开销.同时,协议虽然通过网格结构建立了冗余链路,但由于属于按需型,链路稳定性难以保证.

针对ODMRP协议存在的不足,文章引入了贪婪算法优化机制,解决因为洪泛问题导致的开销过大,同时提出了分布式核心节点选择机制和链路抢修机制分别用以减少节点的信息存储和提高链路的鲁棒性.在第3节中将三个优化机制整合,提出分布式核心稳定路由算法.仿真实验证明,该算法在平均端到端时延、分组交付率及网络开销等方面明显优于ODMRP协议与以VCMP协议为代表的改进算法,适用于多无人机联合通信环境.

2.1 贪婪算法优化机制

ODMRP协议通过洪泛Join-Request分组的方式寻找到达目的节点的路由,虽然这种方式可以建立起到达目的节点的冗余路径,但是路径的稳定性无法得到保证,且选出的“最短”路径并非最佳.当网络中数据交换量较大的情况下会导致网络开销过大.因此引入贪婪算法作为路由发现机制,并进行改进解决贪婪算法过程中出现的路由空洞问题.

2.1.1 空洞问题分析

贪婪算法寻找到达目的节点的路径,这种方法在一般情况下往往会以最快的速度选择一条最短路径,但是当发送节点在其通信范围内找不到比本节点“距离”目的节点更“近”的节点时,就会产生路由空洞[7].解决路由空洞问题最常用的方法是根据节点的分布,将网络连接图平面化[8,9],将数据向着更接近于目的节点的节点转发,直到能够恢复到贪婪算法[10].但是这种单纯的依据静止的拓扑信息进行路由发现的周边转发算法不适用于动态拓扑,需要一种更加灵活的方式完成路由.

2.1.2 改进方案

为了解决上述问题,文章提出基于已有路径采取反向优化机制,改进了数据传输过程中的数据结构,很好的解决了这种路径绕行问题,既不产生多余的数据包,也不会增加时延.

通过对路由空洞形态的分析可以发现,在周边节点中必然会存在某些特殊的几何位置,在这些位置上的节点之间可以通过贪婪算法建立路由,而不需要周边转发,且路由跳数较少.因此,当目的节点在接收到数据包后,读取数据包内所包含的信息,为保证后续数据能够以更短的时延、更小的能量损耗传输,对处于周边转发状态的路径进行优化.例如图1所示空洞,S节点首先向D节点发起一次数据传输,根据贪婪转发算法当数据到达A节点后遇到路由空洞,随后转发方式变为周边转发算法到达B点,转发方式恢复为贪婪转发发送到C节点,再次遇到路由空洞周边转发到E节点,由E贪婪转发到D节点.转发过程中,数据包将正向路径中由周边转发转为贪婪转发的节点标记为分段点(如B和E).

反向优化时,目的节点D首先读取数据包中的分段点,通过贪婪转发的方式反向发送到E节点,再从分段点中寻找下一个最近分段节点B,并发起一次贪婪转发,若转发过程中由于节点的移动性产生新的空洞,同样将更新后的路径和状态记录到数据包中.由B到S进行相同操作,不再赘述.

优化后的路径在数据传输过程中同样保留路径优化功能,当由于节点的移动导致中间节点失效时能够及时发现、及时优化.

2.2 分布式核心节点选择机制

上节中虽然引入贪婪算法来解决网络开销问题,但无法保证所选链路的稳定性,而且在移动网络中节点加入或退出时需要告知所有节点网络拓扑的变化,大大增加了节点的储存空间[11].文章提出通过建立分布式核心节点,在核心节点中存储组播组的地址以及组成员的信息,在拓扑发生变化时只更新核心节点中的信息,而不用通知所有组成员,这样既降低了储存空间,也降低了网络开销.

2.2.1 核心节点选择标准

在贪婪算法对节点的选择上,为了能够满足更多的传输需求,需要对贪婪算法进行改进.通常,无人机在执行飞行任务时会根据航程、能量携带情况规定一定的巡航时间,当能量耗尽就退出所属机群返航,因此为了增加无人机巡航范围和巡航时间,需要尽可能的合理分配功率消耗.在通信领域,能量的消耗主要来自于数据的发送,尽可能的避免低能量节点发送数据包是提高侦查能力的主要方法.

如图2所示,将节点的传输范围划分为三个部分,以源节点与目的节点的连线为轴方向左右各取α角,在此区域内接收节点与目的节点之间的欧氏距离小于发送节点与目的节点的欧氏距离,选得的接收节点为I区域最优点.由2α向两边继续扩张到180度,上下两部分共同组成II区域,该区域中依然有部分节点满足I区域条件,节点选择需要考虑在内.节点传输范围内的剩余部分组成III区域,在I区域和II区域都无法选择符合要求的节点时,需在该区域选择周边转发节点,此时空间传输的优势已不再作为主要标准,能量均衡显得尤为重要[12].由此得到核心节点的选择标准:

图2 节点选择范围

其中,N(i)是核心节点的选择判据,选择可选区域内判据最大的点作为下一跳节点,β是修正系数,根据节点所在位置取值,d(S,N)是发送节点与接收节点的距离,Eres是 节点的剩余能量,Ecap是节点的总能量.

2.2.2 核心节点选择方案

根据改进贪婪算法方案,源节点首先发起一次向多个组播目的节点的寻路过程,并将源节点作为第一个核心节点.路由节点的选择根据核心节点选择标准,并在数据包中记录路由发现与优化过程中N(i)最高的节点,核心节点的选择分为以下三个优先级:

(1)同一个节点收到来自于同一个源节点不同目的节点的Join-Request分组,则将该节点作为核心节点;

(2)不存在交叉路径时,选择贪婪转发过程中第一个分段点作为核心节点;

(3)既不存在交叉路径也不存在路由空洞时,选择核心节点标准N(i)最高的节点作为核心节点.

每一条路径上除源节点外只存在一个核心节点,核心节点选择完成后通知源节点并获得组播网络中所有节点的路由信息.

2.3 链路抢修机制

由于节点的移动特性,部分中间节点不再适用于路由传输,需要重新改变路由信息,这样不但会导致链路的断裂与部分数据的丢失,同样会增加网络负载.为此,将一种基于链路生存时间的抢修机制引入算法,在链路断裂之前发起局部链路的修复过程,保证数据不丢失.

2.3.1 抢修发起时机

根据无线信号功率计算的地面反射模型可得:

Pr是无线信号的接收功率,Pt是无线信号的发射功率,Gt和Gr是发送天线和接收天线的增益,ht和hr为发送节点和接收节点的有效高度,d为两节点之间的水平距离.为了简化模型将公式中的常量抽象为统一参数k,得到简化模型:

假设每个节点发送的数据包功率相同,随着距离的增加节点接收到的数据包功率降低,节点能够接收到的数据包的最小功率为Pmin,节点通信范围为R,移动速度为v,单跳传输时间为ts.为了保证链路完整性以及不新链路会造成过多的开销,局部链路的修复在8跳时间内完成.由此可以得到数据包警告功率:

当节点数据包的接受功率处于降低状态且已触发路由警告后,节点会根据其移动方向计算链路的生存时间.若生存时间小于修复时间时,发起局部抢修.生存时间的计算公式如下:

2.3.2 抢修发起过程

抢修发起过程如图3所示,节点B连续收到来自节点A的数据包,接收到数据包的功率一直处于下降状态且最后一次的接收功率大小低于警告功率时(过程1),首先返回一个通知包通知上一跳节点链路处于危险状态(过程2),同时转发接收到的数据包,并等待两跳的时间(过程3).在两跳时间内未收到来自下一跳节点的警告信息,则判断该节点与上一跳节点之间链路危险,那么向上一跳节点的前跳节点D发起一次贪婪转发(过程4).若在两跳时间内收到来自下一跳节点的警告信息(过程5),则判断为该节点与链路远离,那么向上一跳节点返回通知包(过程6),通知前跳节点发起一次向下一跳节点的贪婪转发(过程7).

图3 抢修发起过程

为避免路由陷入连续的更新导致负载变大,收到链路危险通知的节点在收到来自同一源节点的寻路分组后不返回应答分组,不参与转发.

3 分布式核心稳定路由算法

3.1 数据包格式

为了实现改进后的协议功能需要对数据包的格式进行重新定义.

当源节点需要发送数据时,需要发送Join-Request分组去发现到达组播成员的路径来组建一个新的组播组.为了实现改进贪婪机制的功能,Join-Table分组采用与Join-Request分组相同的数据格式.表1为改进后的数据结构.图4为其数据封装结构.

算法将组播组中组播成员以及地址信息储存在核心节点中,普通转发节点只需要维护一张相邻两跳的路径信息表,减少了由于拓扑的变化产生的路由信息大量更新,也减少了普通转发节点的储存空间.表2为转发节点路径信息表.

表1 Join-Request/Join-Table分组数据结构

图4 Join-Request/Join-Table分组数据结构封装

表2 转发节点路径信息表

3.2 路由过程

3.2.1 正向路由建立

根据改进机制对ODMRP协议的路由建立过程进行优化,具体步骤如下:

(1)源节点有数据需要发送,首先将源节点设置为核心节点,但不计入Join-Request分组中.设置Core Node字段为空,NIMAX=0;

(2)向参与组播的目的节点发送Join-Request分组,并按照核心节点选择机制选择下一跳;

(3)节点接收到Join-Request分组首先判断之前是否接受过来自于同一个源节点的Join-Request分组.如果是,则将该节点写入Core Node字段.进行第(4)步;

(4)判断选择标准中是否满足0 ≤θ＜π.如果是,进行第(5)步;否则,将Prior Sending State设置为0,进行第(6)步;

(5)判断Prior Sending State的值是否为0,如果是,则将该节点的ID和地址插入到Segment Point字段中,进行第(6)步;若Prior Sending State的值为1,直接进行第(6)步;

(6)判断下一跳节点是否为目的节点,若是.则直接发送分组结束正向路由搭建过程;若不是,比较该节点到下一跳节点选择标准N(i)的值与NIMAX的值,将较大的值计入NIMAX字段,并发送分组,进行第(3)步.

3.2.2 反向路由建立

根据正向路由得到的信息构建Join-Table分组进行反向路径的确认,具体步骤如下:

(1)目的节点首先读取正向路径信息中是否存在核心节点,如若有,则将其设定为该路径的核心节点并写入Join-Table分组中的Core Node字段,按照记录的路由发送分组,进行第(4)步,若没有则进行第(2)步;

(2)查找Join-Request分组中Segment Point字段是否记录分段点信息,如果有,则将其设定为该路径的核心节点并写入Join-Table分组中的Core Node字段,按照记录的路由发送分组,进行第(4)步,否则,进行第(3)步;

(3)将NIMAX字段中记录的节点设定为该路径的核心节点并写入Join-Table分组中的Core Node字段,按照记录的路由发送分组,进行第(4)步;

(4)接收到Join-Table分组的节点首先判断自己是否为源节点,如果是,则结束反向路由建立,如果不是,进行第(5)步;

(5)判断该节点是否为核心节点,如果是则标记为核心节点,建立核心节点路由表,记录组播组的地址及成员节点信息,进行第(6)步,否则直接进行第(6)步;

(6)判断该节点是否为分段点,如果是则发起一个向下一个分段点的寻路过程,直到到达下一个分段点,进行第(4)步.

由于节点的移动性导致路由过程中部分节点失效,在一段时间内没有接收到Sop包的转发节点判断路失效主动退出组播组.

路由抢修发起的时机与过程在2.3节中已有叙述,在此不再赘述.

4 仿真分析

本文使用opnet[13]进行仿真,在场景配置中,为使得最终的仿真结果更加直观,将本文协议分布式核心稳定路由协议命名为DKSR(Distribute Kernel Stable Routing).为了验证算法的优化性能,选择与组播路由中性能较好的ODMRP[14]路由协议以及同样针对ODMRP进行改进的变核心组播协议 VCMP(Variable Core Multicast route Protocol[15])算法从平均端到端时延、分组交付率和网络开销三个方面进行比较,并对不同节点密度下的协议性能进行仿真.VCMP算法通过在源节点与目的节点之间设置单个核心节点的方式建立路由,源节点与核心节点之间通过单播协议传输,由核心节点将数据洪泛给目的节点.主要仿真参数见表3.

表3 主要仿真参数设置

图5显示的是ODMRP协议、VCMP协议以及DKSR协议在不同节点密度下平均端到端时延的变化趋势.可以看出,比较于ODMRP协议,VCMP协议以及DKSR协议具有更加明显的优势.这是因为VCMP协议以及DKSR协议都通过贪婪算法对ODMRP协议的路由发现过程进行了改进,能够更快的寻找到组播成员节点.比较于VCMP协议,在节点密度较小的情况下,DKSR协议的端到端时延稍有增加,这是因为该协议在路由发现过程中会通过反向优化来减少路由绕行,随着节点数目的增加,链路的稳定性优势突出,优化效果更加明显.VCMP协议采用单一的路由发现方式,随着节点数目增加,链路不稳定因素增多导致核心节点频繁更新.因此,DKSR协议具有更好的网络扩展性.

图6显示的是ODMRP协议、VCMP协议以及DKSR协议在不同节点密度下分组交付率的变化趋势.可以看出,比较于ODMRP协议和VCMP协议,DKSR协议的分组交付率优势更加明显.这是因为DKSR协议能够选择一条更加稳定的路由,并且能够随着网络拓扑的变化及时的修复路径,保证节点能够准确的交付.而VCMP协议对核心节点的选取和变化条件单一,路径的修复不及时,因此导致部分数据丢失,交付率下降.

图5 平均端到端时延

图6 分组交付率

图7显示的是ODMRP协议、VCMP协议以及DKSR协议在不同节点密度下网络负载的变化趋势.可以看出ODMRP协议、VCMP协议以及DKSR协议在网络负载上相差不大.虽然在节点密度不大的情况下,VCMP协议以及DKSR协议对于路径优化信息的引入导致网络负载稍有增加,但是但随着网络节点密度的增大,对路径的优化效果明显,多余的节点传输减少,网络负载降低,而ODMRP协议通过洪泛的方式建立路由大大增加了网络的负载.DKSR协议通过稳定算法以及核心节点选择机制建立稳定链路,并且通过抢修机制保证链路有效性,减少了由于链路断裂导致重新建立链路,从而降低了网络负载,因此随着节点密度的增大曲线趋于稳定.而VCMP协议会因为拓扑的变化部分链路失效,从而网络负载上升.

图7 网络开销

5 结语

本文针对组播路由的建立问题提出改进算法,改进贪婪选择机制以减少路由发现过程中的数据洪泛以及路由空洞,考虑到成员节点负载能力有限提出了核心节点选择算法,以减少储存空间,同时提出通过链路抢修机制提前修复危险链路保证路径的有效性和交付率.仿真实验证明,DKSR协议能够很好的提升组播网络的性能,虽然造成了网络负载的稍有增加,但在可接受范围内对网络性能做出明显优化,能够达到多无人机联合通信需求.