基于节点速度和能量的MPR节点集选择*

陈炳才,孙少玮,宁 芊

(1.新疆师范大学计算机科学技术学院,乌鲁木齐 830054;2.大连理工大学计算机科学与技术学院,辽宁 大连 116024; 3.新疆师范大学物理与电子工程学院,乌鲁木齐 830054)

在公共领域和军事领域,无人机自组网都有很高的研究价值。因为,相较于单无人机系统而言,多无人机系统协同去完成一项任务时效率更高、成本更低。在军事任务中,无人机机群往往更加需要协同去完成一项任务,这就需要无人机之间组成无人机自组网,即由若干无人机动态形成的、无需借助任何中心站的多跳无线移动通信网络[1]。在公共领域中,无人机自组网可以与地面的人建立连接,也可收集传感器的信息实时传回控制中心,一般常常运用于野外救援、森林探测以及受灾地区网络的恢复。

不同于其他的无线网络,在无人机网络中经常会存在节点的高速移动,从而节点的相对位置发生高动态变化,所以移动自组织网络相对适合无人机网络[2]。这是因为自组织网络不需要任何的基础设施,每个节点的地位相同,在无人机节点快速移动的过程中,网络可以快速的进行部署和组织,网络自愈能力和抗毁能力强,在无人机协同完成任务时具备很高的适用性。

由于无人机机群在执行任务时,自组网中每个无人机节点都要进行信息的高实时共享,这就对时延提出了高要求,所以选择先验式路由协议OLSR具有很高的适用性。但是又考虑到节点速度和能量对整个网络的影响,例如一些无人机节点已经被选为MPR节点,但是由于节点的高速移动而脱离通信范围,或者能量耗尽而提前退出网络,都会致使其无法再选为MPR节点,而重新建立路由则会导致整个网络中端到端时延增加以及网络开销增大。另一方面,如果速度快能量低的节点被选为MPR节点,则会加剧节点的负担,加速其能量耗尽,从而会缩减整个网络的寿命。所以该算法从无人机节点的能量和速度着手,在MPR选举之前,先将速度高能量低的节点进行预处理,最后在意愿值相同的情况下再次对节点的速度和能量加权计算,从而求得最优MPR节点集。

1 路由协议

1.1 路由协议分析

目前,无线自组织网络常规的路由协议主要分为两类,一类是反应式路由,另一类是先验式路由。在反应式路由协议的研究中,王顶[3]等人针对无人机网络中链路间断性的问题对AODV(Ad hoc On-Demand Distance Vector Routing)协议进行了改进,该协议充分利用网络中节点的速度和邻居数等相关信息,在选择路由时根据预先设置的阈值判断链路质量。JDMM Biomo等人提出了在AODV协议的基础上,为了实现路由发现的跳数最小化,利用路径跳数、路径新旧程度、路径可靠性来进行路径的选择[4]。而在先验式路由协议中,Zheng Y等人[5]针对无人机自组网的特性提出了一种基于移动性和负载感知的ML-OLSR协议,得到了较高的分组交付率以及较低的时延。刘杰等人[6]针对OLSR中的MPR节点集提出一种基于贪婪算法改进的OP_MPR算法,该算法可以对MPR集进行优化,从而得到更优更小的MPR节点集。之后董思妤,张洪,王路等人提出一种多维感知的OLSR协议,针对无人机自组网的特性进行综合度量[7]。通过国内外文献可以看到,在无人机自组网中,先验式路由协议中OLSR协议的研究具有很高可行性。

1.2 OLSR路由协议

OLSR[8-10]优化链路状态路由协议是经典的链路状态协议的一种优化改进后的算法。它是一种先验式的路由协议,它通过控制信息的洪泛感知邻居节点的信息,链路的状态以及整个网络的拓扑结构。运用HELLO分组的交互完成链路探测,邻居发现以及MPR节点的选择;利用TC分组的交互,在发布MPR节点信息后建立整个网络的拓扑结构;最后运用Dijkstra算法动态的计算到达成员节点间的最短路径,生成路由表,并对其进行周期性的维护。相对与传统的链路状态协议来说,OLSR路由协议主要进行了以下几点改进与优化:①拥有了辨别新旧路径的序列号。在TC分组中有一个序列号的字段,根据序列号的大小来区别新旧消息,从而使新旧路径不断地进行更新,并且控制分组也不用按照有序的方式进行传输。②MPR多点中继机制的增加。MPR机制大大减少了传统链路状态协议中消息洪泛的范围。选取部分的节点作为MPR节点,并保证通过MPR节点在转发广播分组的时候可以遍布整个网络。转发时节点先判断自己是否为MPR节点,如果是则转发分组,这样在保证低时延的情况下大大减少了网络的开销。③减少了路由表的条目。正是因为采用了MPR机制,在中心节点与其一跳邻居和二跳邻居之间的链路信息就会相应的减少,每个成员节点以此节点建立并保持的路由信息也会相应的减少。

2 基于速度和能量的MPR节点集选举

无线自组网的特点是多变的网络拓扑、有限的传输带宽、移动终端的局限性、单向信道的存在和分布式控制等。而在无人机自组网中由于节点的高速移动性和节点能量的限制性[11]给上述困难带来了更大的挑战,这种高速移动会导致拓扑的高动态变化,网络的连同性以及协议的性能都会因此而产生严重的影响。并且在无人机自组网中,由于无人机的随机移动[12-14]、无线信道间的相互干扰以及地形等综合因素的影响,网络拓扑结构变化的方式和速度都是不可预测的,这使得路由异常重要。这就要求充分的将速度和能量考虑到协议中去。为更好地适应无人机快速移动和能量有限的特性,提出了基于节点速度和能量的MPR选举算法,通过HELLO消息的交互感知邻居节点的速度和能量,然后将节点的速度和能量散布到整个网络,从而为MPR选举时的计算提供衡量标准。下面将对MPR机制和改进后的MPR机制进行介绍。

2.1 MPR机制

在OLSR路由协议中的核心就是MPR机制,由于在此机制下,网络中的每个节点都要选择一部分自己的对称邻居节点作为通信的中继节点,即 MPR 节点,而该节点自身则成为MS(MPR Selector)节点。MPR节点一般是中心节点的一跳邻居中可以和所有二跳邻居成对称链路的一跳邻居。之后每个节点选择MPR节点广播分组。这样,中心节点与其一跳邻居之间的广播分组数量会大量的减少,所以它的增加可以有效的减小网络的开销。尤其是在节点密度大,数量多的大规模网络中,MPR机制的优势会愈发明显。剩下的那些非 MPR 的节点也会接收和处理广播消息,但它们不会转发任何收到的控制消息。

从图1可以看出,利用MPR机制可以在消息散布到整个网络的情况下有效地减少中继节点的数量,从而减少了广播的范围,也减少了节点所接收到重复分组的数量,从而可以大大减少网络开销。

图1 非选择洪泛和MPR机制节点中继

2.2 基于速度和能量的MPR选举算法

本节针对标准OLSR协议中MPR节点选举的过程做以下改进:在MPR节点选举之前基于速度和能量对节点进行预处理,选出节点能量较小速度较快的几个节点使其永不会成为MPR节点;在计算MPR节点时,如果存在两跳邻居没有被完全覆盖,而且节点的意愿值和深度都相同,则再次对节点的速度和能量进行加权比较,将速度低能量高的节点加入MPR节点集,直至二跳邻居完全被覆盖。这样可以有效的减少MPR节点集的数量,并且通过对节点的预处理会减少算法中需要计算的节点规模,从而加快MPR节点集的计算速度。

2.2.1 算法相关概念

willingness:意愿值表示一个节点为另一个节点传输网络数据的意愿程度,其中包括5种,分别为WILL_NEVER 0、WILL_LOW 1、WILL_DEFAULT 3、WILL_HIGH 6和WILL_HIGH 7,从0-7传输消息的意愿程度逐渐递增。

N:以图2为例,节点1-6就是节点0的一跳邻居节点集。

图2 MPR算法相关概念示意图

N2:以图2为例,一个节点的两跳邻居节点集应该为a-f,但不包括下面这几类节点。

①如果一个节点只能通过集合N中某成员到达,而N中成员的意愿值为WILL_NEVER,那么此节点不属于N2。例如图二中节点a只能通过N中成员节点1到达,但如果节点1的willingness为WILL_NEVER,那么节点a不属于N2。

②如果一个节点是正在进行计算的节点,那么此节点不属于N2。例如图二中节点0不属于N2。

③所有的对称邻居:它们与此节点的某些接口间存在对称链路。例如图二中节点2,它虽然可以通过节点1两跳到达,但与节点0具有对称链路,所以不属于N2。

D(y):一跳邻节点y的深度(y为N的一个成员),被定义为节点y对称邻节点的数量,不包括N的所有成员以及进行计算的这个节点。例如图二中节点1的深度为2,其中包括了节点a和节点b。

Reachability:到达性在进行计算MPR集时用到。表示在去除所有此时的MPR集节点及其覆盖的两跳节点后。某一跳邻节点的对称邻节点数量,不包括N的所有成员以及进行计算的这个节点。例如图二中若此时只有节点1被选为MPR,则计算节点2的到达性为2,包括节点c和节点d,而不包括被节点1覆盖的节点b。

2.2.2 剩余能量及节点权重建模

由于在HELLO分组的交互过程中要互相感知邻居节点的速度和能量,并在MPR节点的计算时需要根据剩余能量和速度对节点进行预处理,所以针对网络中节点发送和接收数据建立一阶能量消耗模型,如下所示:

Etx(k,r)=Eelk+kpr2

(1)

Erx(k,r)=Eelk

(2)

其中k为发送信息的比特数,r表示传输距离,Eel表示为电路元件发送和接收单位比特数据所消耗的能量,p表示功率放大器发送单位比特数据的能耗系数。Etx(k,r)表示发送k比特数据,传输距离为r的情况下的耗能情况。Erx(k,r)表示在传输距离为r,接收k比特数据所需要消耗的能量。

在对MPR节点集的选择进行预处理时,首先要将能量较低的节点除去,这就需要我们预先设置一个阈值,阈值设定如下所示:

El=Ei-Etx(k,r)-Erx(k,r)

(3)

(4)

其中Ei表示i节点的初始能量,并通过初始能量Ei减去节点发送和接收数据所消耗的能量,计算出节点的剩余能量El,limit表示节点剩余能量占所有节点初始能量均值的比值。文章中通过limit的值来衡量一个节点剩余能量的状况,limit的值越小表示剩余能量越低,并将limit值低于临界值的节点定义为低能量节点。经过实验分析,limit的临界值设置为20%较为合理,当limit<20%时,更新节点的willingness值为0,使其永远丧失成为MPR节点的资格。

如果二跳邻居没有被完全覆盖且MPR节点的候选节点意愿值和深度都相同,则需要对节点的速度和能量进行加权计算,本文设置的权重计算模型如下所示:

weight=αEi+βEl-γV

(5)

由于算法首先是依据节点能量高低进行预处理的,所以算法的重点在于节点的能量比较及处理。式(5)中,Ei和El分别表示节点的初始能量和剩余能量,weight表示节点竞争MPR节点时的权值,V表示节点的移动速度,α,β,γ分别对应节点这三个属性的权重因子。算法考虑到节点能量的重要性,为了提高节点在竞争MPR节点时初始能量和剩余能量的权重,将α,β系数的值均设为0.4,将速度对应的γ值设置为0.2。从式(5)还可以看出,能量越高,速度越低,weight值越大,也就是说高能量低速度的节点被选为MPR节点的机会就越大,从而权重模型满足算法的整体需求。

2.2.3 基于速度和能量的MPR集的选举

运用OLSR协议中HELLO分组的交互完成链路的探测和邻居的发现。在邻居信息交互的过程中,感知邻居节点的速度和剩余能量,并将其保存在邻居信息组中,以便于后面MPR节点集的计算。

考虑节点速度和能量MPR选举算法的具体步骤如下:

Step 1 for it=N.begin( ):N.end( )

其中N为中心节点一跳邻居节点集,在节点的一跳邻居节点集中选择出剩余能量较低的几个节点加入low节点集中,如果节点的剩余能量相同,对节点的速度进行比较,速度大的加入low节点集中。

end

Step 2 for it=low.begin( ):low.end( )

如果low节点集中的一跳邻居的主地址和N节点集中一跳邻居的主地址相同,那么将N中与其相对应的节点的意愿值willingness设置为WILL_NEVER。

end

Step 3 先将N中所有意愿值willingness为WILL_ALWAYS的节点加入MPR节点集中。

Step 4 计算N中所有的节点y的深度D(y)。

Step 5 将N中满足条件的节点加入到MPR集:它是到达N2中某一节点的唯一节点。移除N2中目前被MPR集覆盖的节点。

Step 6 当N2中存在不被MPR集中任何节点覆盖的节点,执行以下过程。若不存在,算法结束。ⓐ对N中的每个节点,计算其到达性。ⓑ在N中到达性非0且具有最高willingness的节点中选择一个MPR,willingness相同时,选择到达性最高的。到达性相同时,选择D(y)高的。D(y)相同时,选择速度和能量加权计算后最佳的节点。移除N2中目前被MPR集覆盖的节点。回到Step 3。

3 仿真实验结果分析

在无人机自组网环境下,为了对改进后OLSR路由协议进行评估,运用OMNeT++仿真平台对其进行了仿真实验,并与原协议、反应式路由协议DSR(Dynamic Source Routing)在端到端时延、吞吐量[15]及节点能量消耗三个指标进行了对比分析。

3.1 仿真参数设置

图3 网络仿真场景图

网络的仿真实验场景图如图3所示,所有的无人机节点都采用随机移动模型,目的节点也是随机设置的。

本组实验的仿真场景为1 400 m×800 m的矩形区域,仿真时间为100 s,仿真节点个数为 20个,每个节点的无线覆盖范围为250 m。节点的移动模型设置为随机模型,移动速度为随机80 m/s～110 m/s,节点的初始位置也随机。节点的最大能量设置为1 J,每个节点能量的初始值随机。具体的仿真参数设置如表1所示。

表1 节点随机移动网络场景参数

表2 信道物理参数

表3 路由协议相关参数

3.1 仿真结果分析

从仿真结果中可以看到在无人机自组网中,基于节点速度和能量MPR选举的OLSR协议性能指标均优于DSR协议与原协议,并且得到了最优MPR节点集,从而降低了时延,提高了网络的整体性能。

图4为基于速度和能量MPR选举的OLSR协议与原协议、DSR协议的时延对比。

图4 端到端时延对比图

经过两次对曲线进行移动平均处理,从图4中可以清楚看出,在节点移动速度高的情况下,DSR协议的延时抖动很明显,但是基于速度和能量的OLSR协议延时抖动很小,而且时延明显低于DSR协议与原协议。

图5为基于速度和能量MPR选举的OLSR协议与原协议的吞吐量对比。

图5 吞吐率对比图

从图5中可以看出,由于起始阶段网络中各个模块处于初始化阶段,每个模块通过发送自消息进行初始化,所以吞吐量为0。但是之后可以看到,基于速度和能量MPR选举的OLSR协议吞吐量大于OLSR原协议,提高了网络的稳定性。

图6为基于速度和能量MPR选举的OLSR协议与DSR协议的节点能量消耗对比。

图6 节点能量消耗对比图

由图6可以看出,节点的初始能量值均为0.6J,随着仿真时间的增加,节点的剩余能量不断减少,同时可以清楚的看出基于速度和能量的OLSR协议在能量消耗方面低于DSR协议,为网络中节点的生命周期提供了保障。

4 结论

针对无人机自组网中节点高速移动和节点能量有限的问题,提出一种基于节点速度和能量的MPR选举算法。首先,对速度高能量低的节点进行预处理,减小了MPR节点计算的规模,从而提高MPR集计算的速度。之后在MPR集计算的过程中对速度和能量进行加权衡量,最终得到最优的MPR节点集。仿真实验结果表明,基于节点速度和能量MPR选举的OLSR协议在无人机自组网中有很好的适用性。进一步,我们将考虑通过缩减MPR节点的数量,得到一个最小MPR节点集,从而解决先验式路由协议开销大的问题。