陈立伟,简依雯,王桐,欧阳敏,高山
1. 哈尔滨工程大学 信息与通信工程学院,黑龙江 哈尔滨 150001
2. 哈尔滨工程大学 先进船舶通信与信息技术工业和信息化部重点实验室,黑龙江 哈尔滨 150001
近年来,由于生物群体行为的启发[1],大规模的无人飞行器(unmanned aerial vehicle ,UAV)在各行业领域得到了广泛的关注[2],通过集群协作完成搜索[3]、地形勘测[4]等各项任务。为实现集群中的协同交流与数据传输,无人飞行器自组网应运而生。每个无人飞行器通过无线信号连接进行多跳传输,既是任务执行节点也是通信中继节点。而无人飞行器多任务网络则是以完成多项协同任务[5]为目的的无人飞行器自组网,通过多个无人飞行器分系统实现自组织的行动[6]。
优化链路状态路由协议(optimized link state routing,OLSR)作为先应式路由协议[7],查找路由时延小,与按需式路由协议相比更适合需要低时延的无人飞行器多任务网络。同时OLSR 协议的多点中继(multipoint relay,MPR)技术能有效减少网络中广播消息的泛滥,在一定程度上减轻了先应式路由协议在高速场景下网络冗余信息占用带宽多的问题,因此OLSR 十分适用于规模大的无人飞行器集群通信[8]。目前学者们针对OLSR 路由协议的优化,大多以提升链路稳定性和减少路由开销作为直接出发点进行研究。针对无人飞行器网络节点高速移动问题,文献[9]提出一种按需寻路的可靠OLSR 协议,提出基于拓扑控制报文全网寻路机制和基于HELLO 邻居寻路机制,通过增加路由获取途径,维护多跳链路的稳定性。针对OLSR 协议路由开销大的问题,文献[10]基于博弈论改变节点选择意愿从而改善MPR 选择,以此减少网络中控制数据包的数量,但主要适用于密集型低速无人飞行器网络。文献[11]则在相同意愿值条件下计算节点能量消耗,从而优化MPR选择,降低网络平均能量消耗。这些优化算法在动态变化程度高的无人飞行器网络中无法始终保持高性能,不能随着应用需求、任务环境自适应变化,与实际任务匹配的灵活性差,实用性、可移植性不高。
近年对于无人飞行器网络拓扑自适应的路由算法研究逐渐成为热点。文献[12]提出基于QLearning 思想的移动自组网OLSR 路由策略,通过在线学习来适应网络高度动态变化的拓扑结构,但基于在线强化学习的优化将带来庞大的计算量与多余的能量消耗。文献[13]设计了基于动态拓扑的路由协议,根据卡尔曼滤波预测节点位置,预测节点的加入、退出网络情况动态调整HELLO消息的广播周期,从而提升网络连通性,但该算法的实现基于无人飞行器节点在匀速不变的环境。文献[14]中通过网络拓扑变化情况将无人飞行器网络分为编队飞行与自主飞行2 种模式,从而调整HELLO 消息的广播周期,但仅设置了高、低2 类广播周期,拓扑自适应性程度不高。
综上,现有对面向任务的无人组网架构研究较少,针对OLSR 的改进协议在无人飞行器高速环境下无法保持高性能的网络通信,在多任务环境下动态适应性不够。由此,本文具体解决方案如下:针对无人飞行器多任务网络中任务集群拓扑变化程度高、难以度量的问题,提出基于模糊逻辑的拓扑稳定度计算方法;针对现有探测拓扑状态方法的动态适应性不高问题,提出探测周期自适应的动态探测方法;针对OLSR 路由协议在无人飞行器集群低动态任务时冗余信息多、高动态任务时链路易断开的问题,提出HELLO 控制消息的自适应广播策略和MPR 优化选择策略。
联盟结构主要出现在多智能体模型[15]及博弈过程中,用于描述智能体间的逻辑关系。同为分组结构,路由算法常用的分簇算法聚焦于如何使组内节点间尽可能拥有稳定的通信链路,多以通信距离、网络连通度等加权参数为分组依据[16];而联盟结构则聚焦于如何使得分组后利于完成任务并最大化任务联盟收益,其分组依据是任务分配或博弈的结果[17]。因此联盟结构与现有分簇结构的最大差异是集群分组的驱动力不同,联盟是面向任务的。
现有基于分簇的路由算法对拓扑变化适应能力相对较差,多适用于拓扑变化较为缓慢的网络。在多任务环境中,无人飞行器集群网络拓扑结构剧烈变化,采用分裂或合并策略的传统分簇路由算法需要很大的开销用于构建簇或者维持簇结构的稳定。但实际上此时各组无人飞行器正有序完成不同类别的协同任务,无需重新分组构建簇。因此联盟结构更适合无人飞行器集群在多任务环境下的任务驱动特性。决策系统将满足目标任务资源需求且通信链路稳定的多个无人飞行器分配给该目标任务,无人飞行器以任务分配的结果进行结盟[18],阶段性任务结束后联盟解散,等待下一次小任务的分发及联盟更新。同时在必要环境下可以实现同一无人飞行器分属2 个任务联盟[19]等复杂情况,快速响应各项不确定任务。
本文提出基于联盟的无人飞行器集群组网架构,如图1 所示,完成初始组网工作。
图1 面向任务的无人飞行器自组网
在给定的任务集合的情况下,建立满足需要的无人飞行器集群自组网有3 个重要步骤:任务量化、资源分配和联盟划分。
1)任务量化
通过任务分析评估,将任务细化为一系列子任务。在整体无人飞行器集群待完成的任务集合中,各任务可被视为一系列子任务的组合,例如搜索任务可被看作是数据收集任务和数据整合任务等多个子任务的组合。不同的任务对应不同的任务优先级、通信需求、资源利用优先级[20]等。因此定义子任务拥有属性(重要性、风险性、完成所需时间级别等),规划子任务序列执行时间线,涉及任务分解、规划的相关算法。
2)资源分配
分析任务数据、依据子任务属性完成资源高效分配,完成子任务与资源平台的映射。资源主要分为无人飞行器资源与频谱资源。无人飞行器资源分为联盟领导无人飞行器(coalition leader UAV,CLU)与联盟成员无人飞行器(coalition member UAV,CMU),拥有更高的硬件能力,能进行信息处理与决策制定的才能作为CLU。频谱资源的分配即为每个任务联盟划分合适的带宽。
3)联盟划分
建立联盟形成博弈模型[21],确定所有子任务的任务收益与相关约束条件,在相关约束下最大化总体任务收益,完成任务联盟的划分。可用相关约束有无人飞行器执行任务类型约束、任务重要性及执行顺序约束、任务所需无人飞行器数目约束等,任务收益的设定与任务执行相关(燃料损失、悬停时间等),也与通信效率相关(联盟数量、大小等)。任务驱动组网的关键就是形成初始稳定的无人飞行器任务联盟。在形成稳定任务联盟后,依据各联盟内的子任务执行要求进行邻居发现、建立路由,联盟间的通信则由CLU 实现。因此,在面向无人飞行器多任务网络中,不同联盟针对各自任务表现出的网络拓扑存在显著差异。作为空中通信平台的无人飞行器将悬停在所需区域上空[22],链路与拓扑的变化是缓动态的,与此相反,完成搜索扫描任务则要求无人飞行器集群在大范围内移动,链路经常中断需要重新建立链接,同时任务的二次分配也会使得联盟拥有相对高动态的拓扑变化,而目标跟踪、有计划编队等类型的任务则使得联盟拥有相对静态的拓扑变化。
处于不同任务环境下无人飞行器的任务状态不同,导致无人飞行器集群的飞行状态有显著差异,从而形成不同的拓扑结构。同时,各无人飞行器联盟处于不同任务状态下,联盟的拓扑变化情况可以直观反映出该联盟中无人飞行器的飞行状态,因此可以利用联盟拓扑变化信息增强路由算法对于无人飞行器联盟网络的适用性。由此定义拓扑稳定度(topological stability, TS),以度量一段时间内的网络拓扑变化程度,根据TS 对路由算法中进行自适应调整,实现整个无人飞行器集群的稳定通信。
无人飞行器集群中,节点的移动性可能会导致邻居节点间的相对变化,引起邻居节点间局部拓扑的改变。某联盟中有n架无人飞行器,定义其无人飞行器节点集合U={u1,u2,...,un},每个节点维护一个一跳邻节点集合。无人飞行器节点i的一跳邻节点集合记为Ni_1,一跳邻节点数目为m。在t时刻,无人飞行器节点i相对节点j的速度为vij(t)。定义从t时刻经过T时间,节点i与其所有一跳邻节点的平均相对速率变化因子(relative velocity change,RV)Ri为
式中:|v|max为该联盟中允许的最大速率,Ri(t,t+T)∈[0,1]。
考虑节点i和节点j某时刻的相对运动情况,dij为两节点间距离,如图2 所示。将节点j视为参考节点,则节点i相对节点j的运动速度为vij,Rx为节点的最大通信半径。则视线段L为两节点链路预测保持连接的相对运动路径,dver为节点j与线段L的距离,将节点i在线段L上运动时间视为链路预测存活因子,由此定义节点i与其所有一跳邻节点的平均链路预测存活因子(link hold,LH)Li为
图2 某时刻两节点的相对运动情况
同时,计算可得Li∈[0,1]。
式(1)~(2)均使用一跳邻节点集合中的节点进行计算,存在局限性,即无法对邻节点失效进行判断。在该节点无失效邻节点变化时利用Ri(t,t+T)和Li进行计算处理后可以很好表现网络中该节点局部飞行状态的变化,但网络可能存在链路中断,邻居节点失效的情况,此时已无法获取更新该节点的变化信息。例如某场景有Ri,j(t1,t2)=0,则无法判断t2时刻节点i与节点j是完全不存在相对移动性变化、保持稳定链接的情况,还是节点j已与节点i断开连接,已经成为其失效邻居节点。针对该局限性,加入一跳邻节点损失因子。
定义时间T内节点i的一跳邻居节点损失因子(neighbor loss,NL)Ni为
式中:ni_loss1(t,t+T)为t时刻到t+T时刻节点i在t时刻的邻居集合中失效的一跳邻节点数目;ni_1(t)为t时刻节点i的一跳邻节点个数,Ni(t,t+T)∈[0,1]。
3 个因子均为[0,1]的值,将之作为输入进行模糊化处理,得到该节点局部拓扑稳定度。3 个模糊输入变量均有3 个等级{Low,Medium,High},隶属度函数使用三角函数及梯形函数,使用if-then规则定义27 条模糊规则完成输入输出映射,如表1所示。其中,输出参数为该节点的局部稳定度,具有5 个等级{Worst,Weak,Middle,Good,Best}。图3为输入、输出参数的隶属度函数。
表1 模糊规则库
图3 输入、输出参数的隶属度函数
使用Min-Max 决策处理所有模糊结果,再使用重心法进行解模糊运算,即得到所求节点的局部稳定度。由此,将计算出的每个节点的局部稳定度求均值,得到联盟内网络的拓扑稳定度为
式中:x为隶属度函数的自变量,fi(x)为节点i隶属度函数集。
OLSR 算法通过定期广播控制消息中的HELLO消息来维护节点的邻居关系,更新计算拓扑表、路由表。相对更静态拓扑的任务过程中,无人飞行器间的动态性低,链路更加稳定,这种情况下高频率的HELLO 消息的广播不仅会带来控制信息的冗余,造成不必要的资源浪费,增大网络阻塞的几率。相反,在集群内节点转为相对高动态的情况下,HELLO 的广播频率依旧维持不变将难以获取最新的邻居关系,导致数据消息包的丢失率增大。本文通过探测无人联盟的拓扑状态,基于模糊逻辑计算联盟的TS,根据TS 值实现HELLO 消息广播周期的自适应调整。同时为增强算法的自适应程度,自适应调整无人联盟的拓扑状态探测周期,形成动态探测。
OLSR 协议中的MPR 技术可以有效减少网络中的控制分组数量,主要思想是仅有MPR 集合中的节点才能转发拓扑控制消息,因此MPR 集合的选择将直接影响整体路由性能。原始OLSR 协议中通过节点连接度来选择MPR 节点,选择能尽可能多的连接其他节点的节点成为MPR 节点。但该方案应用于无人飞行器多任务网络时,可能由于任务的高速移动性导致节点间链路稳定度下降,仅考虑节点间的连接度显然不够。因此TA-OLSR 算法在节点连接度的基础上加入节点局部TS 值作为MPR 节点的选择依据,在不过多增加计算量的同时提升无人飞行器联盟网络连接的稳定性。
TA-OLSR 算法的主要实现思路如图4 所示。
图4 TA-OLSR 协议实现思路
每个节点都维护一个本地链路信息表和邻居节点信息表,它们的建立是通过周期性广播HELLO消息进行链路探测得到的。以Tprobe的时间间隔探测联盟网络的拓扑变化,进行TS 的计算。第k次探测(k>1)与第k−1次探测的时间间隔为
式中 µ是控制系数,用来将TS 探测周期调整至合适范围,与整体任务情况相关。以任务信息驱动完成组网,无人飞行器快速形成联盟,此时HELLO 广播周期为初始常量值TH_cons,在联盟网络开始探测拓扑后,将自适应的改变广播周期,即THELLO。2 次TS 探测的时间间隔根据前一次探测计算的THELLO信息反馈得出。在网络拓扑相对动态性低的情景下,一定时间内的拓扑变化比动态性高的情景下小,因此在低动态性的网络拓扑中应延长下一次探测的时间。在根据网络情况调整THELLO的同时,THELLO可以反映当前时间段内网络拓扑变化情况,从而有依据地改变下一探测的间隔时间,即实现TS 探测周期的自适应改变,如图5 所示。
图5 探测周期与HELLO 广播周期的动态改变
定义 δk是无人飞行器第k次探测时的空间密度,通常来说高密度的网络拓扑情况通常比低密度的链路变化情况更复杂,本文使用它来增大这种差异。Rx为该网络中每架无人飞行器的最大通信距离,具有更长传输范围的无人飞行器可以在更长HELLO 间隔内保持网络吞吐量[23],因此第k次探测计算HELLO 广播周期为
式中 γ为控制系数,用来将HELLO 广播周期调整至合适大小,在本文场景取0.01。
利用任务规划步骤[24]中得到的任务联盟相关数据(任务类型、无人飞行器数目等),限制联盟最大、最小HELLO 广播周期,可以防止过高、过低的周期出现,同时减少不必要的计算开销。由此进一步约束为
式中:h1和h2为控制阈值,Thigh、Tlow为整体任务规划中限制的最大、最小HELLO 广播周期。
针对网络中的节点,OLSR 算法首先创建其一跳对称邻居集合N1={u1_1,u1_2,···,u1_n1}、两跳对称邻居集合N2={u2_1,u2_2,···,u2_n2}, 用于计算MPR 集合M,首先根据N1中节点的意愿来初始化合集M,然后计算N1中节点的连接度Degree(优先选择Degree值大的节点)用以覆盖完全集合N2中的节点,直到集合N2为空集则该节点的MPR 集合M建立完毕。
本文在连接度的基础上加入节点局部TS 值作为MPR 节点的选择依据,能在避免额外增加过多计算量的情况下进一步确定待选节点的稳定性。则MPR 选择度量改为中继节点权重(weight of relay node,WR)Wi为
式中:Di为候选节点i的连接度大小,Ti为候选节点i当前时段的Ti(t,t+T)值。平均链路状态越稳定则广播丢包率将越低,因此使其选中可能性越大。计算出N1中每个节点的WR 值,从大到小排序用以选择MPR 节点,直至覆盖完全集合N2中的节点,直到集合N2为空集则该节点的MPR 集合M建立完毕。计算MPR 流程如图6 所示。
图6 MPR 选择流程
在本节中使用离散事件模拟器NS-3(network simulator 3)对算法进行了仿真实验。为了更好地反映算法对无人飞行器集群的影响,仿真实验涉及到的数据设定如表2 所示。
表2 仿真参数设置
仿真实验中原始OLSR 算法的HELLO 广播周期为1 s,将Thigh设定为4 s、Tlow设定为0.2 s。每次仿真设定10 条数据流,分别计算每条数据流的各项指标,再对其求均值,同时为捕捉不同拓扑情况下的性能,每个实验均对节点取随机起始位置进行10 次仿真取均值,以下是每条数据流的平均性能。文中将本文TA-OLSR 算法与原始OLSR算法、使用分簇的OLSR Med+[25]算法进行了比较。
图7、图8 分别是在节点数目变化下3 种算法平均包投递率(packet delivery rate,PDR)和平均端到端时延的对比图,其中无人飞行器节点的最大速度为10 m/s。
图7 节点数目影响下的平均包投递率
图8 节点数目影响下的平均端到端时延
可以看出TA-OLSR 在节点数目增多的情况下仍能保持较高的包投递率,尤其是在90 个节点情景下TA-OLSR 的PDR 相比于OLSR Med+提升了5.19%,相比于原始OLSR 则提升了17.39%。图中3 种算法的包投递率在节点数50~70 之间有一段明显的上升过程,这主要是由于仿真环境中节点通信半径设置不大,在速度低时无人飞行器密度对性能造成了很大影响,此无人飞行器数量区间形成了较为适合本仿真环境的节点密度,一定程度上促进了节点间的通信质量。因此在图8中,此区间内网络的平均端到端时延的增大情况也存在放缓的现象。
图8 中可以看到,在节点数目较少时与其他2 种算法的时延差异不大,但随着节点数目增多,原始OLSR 的平均端到端时延明显大幅度增加,TA-OLSR 和OLSR Med+2 种算法的时延表现都优于原始算法。在节点个数为100 个时,TAOLSR 的平均端到端时延相比于OLSR Med+降低了3.93%,相较于原始OLSR 降低了31.22%。
图9、图10 分别是在无人飞行器节点速度影响下3 种算法的平均包投递率和控制消息占比情况的对比图,其中无人飞行器节点数目为50 个。
图9 节点速度影响下的平均包投递率
图10 不同的速度网络中控制消息占比变化
随着无人飞行器速度增大,节点间动态差异增大,原始OLSR 的丢包率逐步升高,这正是高动态性对于路由性能的影响。但TA-OLSR 在高动态的复杂环境中网络数据接收依旧良好,在无人飞行器速度40 m/s 场景中的数据包投递率比OLAR Med+提升了17.02%,比原始OLSR 提升34.14%,这是由于在TA-OLSR 中感应到链路中断情况增加时,HELLO 消息的广播周期缩短,增加了邻居感应力度,重建邻居表用于路由更新,同时MPR 集合选择了更稳定的节点进行消息转发,减少了由于路由变更不及时导致的丢包情况。在探测网络拓扑相对稳定时减少HELLO 等控制消息包的广播,此时网络路由变化情况少,相对少的HELLO 探测并不会增大丢包率,同时可以减少控制类信息在网络中的传播,使得消息冗余度降低,不仅能很好地节省网络资源,同时也有效降低了冗余信息对于网络吞吐量的影响。
图10 中是利用控制消息长度与接收消息长度的比率衡量控制消息的开销,当包投递率一定时,网络开销越低,网络性能更好。在节点速度为20 m/s 时TA-OLSR 的控制消息占比相较于OLSR Med+降低了19.08%,相较于原始OLSR 降低了19.90%。TA-OLSR 可以在整体动态较小时有效节省不必要的控制开销,在节点速度增大后节省开销的程度逐渐降低,但仍优于原始OLSR。节点最大速度为40 m/s 时,TA-OLSR 的控制消息占比相较于原始OLSR 降低了8.51%。
本文针对路由算法与复杂任务环境中的拓扑变化动态耦合度低导致丢包率高、冗余信息过多的问题,提出了面向任务的无人飞行器自组网的TA-OLSR 协议,通过每个任务联盟内部的拓扑自适应实现宏观上整个无人飞行器集群的任务自适应。仿真结果表明TA-OLSR 算法能有效改善网络稳定性、增大网络包投递率与网络吞吐量,能够至上而下的依据无人飞行器集群任务拓扑完成路由自适应调整,实现网络的适应性节能。
当前研究主要利用不同任务联盟内无人飞行器间移动特征的相似度来衡量网络拓扑的变化,从而实现路由算法在整体无人飞行器集群的任务自适应。后续研究将结合不同任务所需性能指标的差异性,进一步充实任务信息,使得路由协议在多种无人飞行器集群任务中达到更好的自适应性。本文研究了联盟内的通信路由情况,可以进一步研究如何优化任务联盟间的通信,使整个无人飞行器集群的通信体系更加完整。后续仿真实验还将考虑构造多任务变化场景来进一步模拟复杂无人飞行器集群的动态任务环境,更好地研究无人飞行器集群自组网的各项数据指标。