地空异构网络中无人机辅助的文件协作缓存算法①

郑 云,徐哲鑫,陈锦峰,吴 怡

1(福建师范大学 医学光电科学与技术教育部重点实验室,福州 350117)

2(福建师范大学 福建省光电传感应用工程技术研究中心,福州 350117)

每次地震、泥石流等自然灾害发生后,灾区附近的通信等电力设施都遭到严重破坏.因灾后建筑掩埋,短时间内难以恢复通信线路,受灾人员无法联系外界,无法发送求救信息,因此建立应急通信网络服务显得尤其重要.无人机凭借灵活多变的特性,在救援人员到达前可用其搭载无线设备进入灾区,建立应急通信架构,也可通过无人机携带或投放无线mesh 路由,在短期内保障受灾人员的通信需求,方便受灾人员向外界发送求救信息.灾区内的文件请求预测中,大多为灾区救援重建以及与亲友联系的内容,通信请求的内容重复性较高,短时间内某些文件被重复请求,产生大量的数据冗余.因此需建立地面mesh 缓存功能,减少网络内的重复能量消耗与路由开销,缩短获取内容的时间,同时减轻用于中继通信的无人机负载,改善受灾人员的通信体验感.目前,无人机和通信设备资源有限,灾后短时间内无法筹集足够的设备,且大部分灾区面积大、区域分散等,故在无线mesh 混合网络中选择簇状网络作为应急通信网络.

在应急通信方面,卫星、无人机、海岸、舰船、水下可构成的一体化应急通信系统建设[1].物联网高速公路应急救援平台也可快速获取事故信息[2].已设计的电力应急现场指挥通信方案优化设计路由协议[3],开发出集定位、信息交互的软件,可移动和可部署资源单元用于灾难网络快速恢复[4].灾后应急救援网络把无人机网络与无线mesh 网络共同构建簇状网络的架构[5],使用节点流量感知的无人机动态调度算法,有效提升网络吞吐量.对mesh 网络节点布放要求和节点覆盖能力进行估算[6].构建无线mesh 网络内部干扰模型[7],验证无线mesh 节点休眠策略有效性.优化无线网络拓扑覆盖方案[8],调整天线的覆盖角度易于用户接收信号；增大功率可以增加天线的发送距离并且保证信号的畅通性.加入卫星通信系统在应急领域的应用[9].基于3G/4G 的应急指挥车辆管理信息系统设计方案可简化监测与维护难度[10].优化应急通信网络架构和指挥中心保证前、后方决策部门之间通信无堵塞[11].

在无人机搜寻救治人员方面,提出海上落水伤员救援决策方案[12],对落水伤员搜索定位、伤员伤情监测、救援物资投送.建立无人机搜索系统[13],制定短距离通信协议,获得野外遇险人员的地理位置.多无人机协同区域监视的航路规划方法[14],使用遗传算法达到无人机监视覆盖率最大.蚁群算法在灾区无人机搜救场景遍历所有区域形成封闭环状搜救路径[15].野外生命搜救探测的无人机探测系统利用摄像头、热释电红外识别系统[16]、雷达生物识别系统对野外遇险人员的准确定位.具有体征监测功能的UAV 搜救系统,待搜救人员提前携带的救援信标机和体征监测仪[17],将体征信息通过与无人机的通信链路传给救援中心来实施针对性救援.

在协作缓存方面,结合基站缓存容量大小及文件请求的分布[18],构造了基于最小时延传输的0-1 整数规划最优化问题.ICN 方案[19]对数据内容的流行度分布视图偏向于缓存不同的数据内容,减少冗余的缓存.基于用户偏好下不同缓存容量节点间的协同缓存放置策略利用坐标下降算法对子问题进行迭代得到近似最优解[20].CCPNC 缓存策略对不同流行度的内容对象分类缓存[21],调动网络内核心路由节点与非核心路由节点协同工作.基于邻域可用性的协作缓存策略充分利用节点的邻域缓存信息[22],提升系统性能.基于缓存管理的网络编码中继传输方案[23]结合编码流速率增加编码机会,获得中继处不同流的缓存阈值实现编码决策.基于半定松弛的方法来获得缓存策略在缓存命中率和端到端时延方面具有竞争力[24].协作组缓存策略选择具有最低内容缓存概率的相邻节点作为最佳候选者来减少内容冗余[25].

上述研究的角度多种多样,但是这些没有考虑灾区应急通信中无线mesh 路由的协作缓存与无人机调度的配合.本文使用Matlab 遗传算法工具箱,综合考虑地面无线mesh 路由的协作缓存与空中的中继无人机的飞行情况,将无人机作为传输中继与地面mesh路由协作缓存结合,提升用户获取文件的效率.以中继无人机转弯角为基因完成轨迹规划,协作缓存以各个地面无线mesh 路由所存储的文件块为基因优化缓存分布.仿真表明,可将用户的平均时延收敛在较低水平.

1 系统模型

1.1 系统整体架构

基础设施破坏严重的情况下,需要使用空中无线设备,即无人机携带通信设备.又因单个无人机能量与覆盖范围有限,故使用多个中继无人机共同组成联合网络,使得灾区通信受损严重的地方得以联系外界.本文采用簇状网络结构搭建应急通信网络,即以一个无人机作为簇头,与地面无线mesh 路由共同组成地面-空中无线mesh 网络.应急通信网络的整体组网[5]如图1所示,整体由分布在受灾区域的mesh路由器、外界基站,起到中继作用的无人机组成.图中灾区整体分为2 个受灾区域,每个受灾区域按大小分配有一架中继无人机与6 个无线mesh 路由器,组成区域内的应急通信系统.区域内无人机起到传输中继作用,向其余区域或外界请求文件块,实际上并不缓存.地面无线mesh路由主要缓存文件块,协同为用户提供文件.基站负责传输中继无人机请求的文件块.每个区域的中继无人机连接外界基站时,使用一架中继无人机作为桥梁.

图1 地面-空中无线mesh 网络整体构架

本文仅考虑一处区域的地面-空中无线mesh 网络的无线mesh 路由缓存情况与中继无人机的飞行.借助于中继无人机节点的可移动性,仅需确保与部分地面无线mesh 路由连接,减少能量消耗以及路由开销.

1.2 系统流程

如图2所示,每个区域的人员首先连接最近的mesh 路由请求文件,若该mesh 路由一跳与两跳连接的mesh 路由均未存储该文件,则通过中继无人机传递请求,向外界的基站或其余区域的mesh 路由请求该文件块,然后逐个传递回来.以上过程作为中继无人机与无线mesh 路由不改变下,一个周期内用户请求文件的流程.待下一个周期开始,将上一个周期用户请求情况输入,使用遗传算法计算得出最佳无人机位置与无线mesh 缓存情况,控制无人机飞到指定位置,使用集中式缓存控制对无线mesh 路由器直接进行缓存.

2 基于无人机中继的mesh 路由缓存策略

2.1 基于遗传算法的中继无人机轨迹规划

无人机只负责作为传输中继,不进行缓存.初始条件为中继无人机的初始位置和速度,中继无人机每次飞行的角度小于无人机飞行的最大转弯角.在约束条件下,中继无人机飞行转弯角选择下一时刻最优结果.即下一时刻区域范围内用户的平均时延最低.然后根据航路——位置坐标公式[14]更新中继无人机的位置和坐标,接着重复以上步骤,更新中继无人机的位置,直到用户平均时延收敛.

其中,xE和yE分别为目标节点E的横坐标和纵坐标；xA和yA分别为无人机之前的起始点A的横坐标和纵坐标；vp为无人机的飞行速度；Δt为固定的时间间隔；α为目标节点E相对于起始点A的位置偏转角；v2为无人机在目标节点E处的速度角度；v1为无人机在之前起始点A处的速度角度；θ为无人机由起始点A飞到目标节点E时速度变化的角度.下一次飞行时,将公式中的目标节点作为此次的起始点,不断迭代飞行.

图2 用户请求流程

将中继无人机的飞行角度作为基因.中继无人机可以由转弯角与当前的位置速度得出一定时间后无人机的位置与速度,故此处使用中继无人机的转弯角进行编码[14]；此种编码方式保证之后的选择交叉变异后,得出的新生代种群个体依旧可实现中继无人机的飞行.中继无人机约束条件是转弯角大小,设定无人机飞行的转弯角不大于最大转弯角θmax,即转弯角θ ∈[−θmax,θmax][14].

2.2 基于遗传算法的无线mesh 路由器协作缓存

地面无线mesh 路由器主要负责缓存,同时可以与两跳内的路由器或中继无人机传输文件.路由器节点作为主要的缓存设备,可配备较大的缓存空间.系统采用集中式缓存控制,根据之前周期区域内的所有用户的请求情况进行计算后统一缓存,随着系统运行时间累积以及用户请求量的增加,系统统计出的文件流行度分布将趋于用户整体请求分布.另外,采用遗传算法等启发式算法对于请求分布的约束不大,故本文将文件块流行度设为经典的Zipf 分布[26-28].初始条件为mesh 路由的存放位置,mesh 路由在用户曾经请求过的文件块集群中选择文件块缓存.在约束条件下,地面无线mesh 路由筛选并缓存合适的文件块,以使下一时刻区域范围内用户的平均时延最低.通过不断迭代更新地面无线mesh 路由的缓存分布,直到用户平均时延收敛.

遗传算法中使用缓存的文件块编码作为缓存情况的基因,将地面无线mesh 路由所缓存的文件块作为编码.地面无线mesh 路由的约束条件设为同一个mesh路由的缓存空间内不能重复缓存同一个文件,设备数为N,每个设备缓存F个文件,缓存的文件块编码为1到NF,即每个设备的缓存情况为令其缓存编码为X.

2.3 代价函数及算法流程

根据编码方式初始化种群G,如式(4)所示,S代表种群中的个体数.每一行表示种群中个体的基因,即一种地面无线mesh 路由的协作缓存情况与中继无人机的飞行情况,这代表二者协同考虑,经过选择交叉变异的迭代后,其中的个体越来越优秀,适应值越来越高,并在最后达到收敛.

适应度函数设置.地面无线mesh 路由的协作缓存与中继无人机飞行情况协同考虑,目标是降低用户的平均时延.所以使用用户的平均时延作为适应度函数FIX.

式(5)中,D表示每个用户的时延,SP表示用户总数；HC0表示用户在连接的mesh 路由上直接取到文件；HC1表示用户在连接的mesh 路由上经过一跳取到文件；HC2表示用户在连接的mesh 路由上经过二跳取到文件；dAM表示用户取得文件经过的距离；dMU表示中继无人机传递给mesh 路由的距离；AU表示用户在连接的mesh 路由上取不到文件,需要借助中继无人机取得文件.式中0.1 表示一跳需要经历的额外时延,0.2 表示一跳需要经历的额外时延,0.5 表示通过中继无人机获取文件需要的额外时延.因灾区建筑遭到破坏,无论救援还是临时居住地,无线mesh 路由间的障碍较多,故设定每秒传输距离为100 m,因无线mesh 路由与中继无人机间障碍较少,故每秒传输距离为1000 m.

在用户请求模型中,用户的位置是均匀随机分布于区域内,连接到距离最近的地面无线mesh 路由,用户请求的文件按照预设的Zipf 分布随机生成.

遗传算法中,计算个体适应值后,直接把前5%的优秀个体作为子代一部分.父代使用随机遍历抽样法,抽取152%的父代个体,经过交叉步骤,得到76%的子代个体.父代抽取19%的父代进行变异.最终由选择交叉变异得到所有的子代个体.交叉操作选择多点交叉,即在个体编码串中选择部分基因段,以间隔交换的方式交换基因.本文设置6 个地面无线mesh 路由,每个设备可存储2 个文件块,文件块编码为1-20.选择第1、3、5 段基因进行交叉操作后结果如表1所示.

表1 多点交叉分析表

变异操作选择单段基因进行变异,如染色体“(2,5),(3,4),(18,1),(20,5),(10,7),0.023”含义为编号为1 的设备缓存文件块2 和文件块5,编号为2 的设备缓存文件块3 和文件块4,以此类推；中继无人机的转弯角为0.023 rad.某一路由的缓存变异后将重新缓存不同的2 个文件块.对转弯角进行变异时,转弯角取值范围为[ −θmax,θmax],并设无人机最大转弯角θmax为π/4.

3 仿真与分析

3.1 参数设置

如表2所示,仿真区域范围设为280 m×280 m,无人机一般飞行速度为13 m/s 以内[5],速度过高会导致无人机难以飞行到起始点附近的位置,故限定为3 m/s.无人机高度均衡用户通信效果与建筑高度约束,设为100 m,约30 层楼高.本实验中6 个地面mesh 路由器的位置分别为(40.2,74.8),(66.6,225.9),(152.8,227.8),(249.6,213.8),(136.2,78.1),(235.1,70.3).无线mesh 路由器的位置均衡通信覆盖范围最大[14]与路由器两跳范围内有尽可能多的路由器.文件块数量设为20,其流行度设为Zipf 分布,其中参数α取0.7.设定使用48 顶应急救援帐篷并均匀分布于该区域,每顶帐篷设5 人,故用户数为240 人.

表2 遗传算法仿真参数表

3.2 仿真实验

仿真实验中场景示意图,正方形代表受灾区域,圆心代表无线mesh 路由器的坐标,圆代表无线mesh 路由器的通信范围.图中圆心附近的数字代表该无线路由器所缓存的文件块编号,如(1,2)表示该路由器缓存文件块1 与文件块2.无人机始终从坐标(150,150)出发,飞行轨迹以星号表示,轨迹收敛位置为(150,150)小圆圈所在坐标.

3.2.1 中继无人机悬停场景下用户平均时延

单独考虑缓存情况,中继无人机位置在(150,150)处,保持原地飞行时,仅地面无线mesh 路由进行协作缓存,由图3可知,当迭代至第20 代时,种群中出现了更加优秀的个体,曲线产生跳变,此后用户的平均时延就已经基本位于0.726 s 附近,随后在第50 代与第70 代分别微小跳变,直到结束.当用户平均时延相等的最优缓存结果可能不同,由图4可知协作缓存结果.

图3 中继无人机悬停场景下用户平均时延

图4 中继无人机悬停场景下协作缓存示意图

3.2.2 地面mesh 路由缓存不变场景下用户平均时延

单独考虑中继无人机飞行情况,地面无线mesh 路由的缓存情况为(1,2),(3,4),(5,6),(7,8),(9,10),(11,12)时,保持无线mesh 路由缓存的文件块不变,仅调动中继无人机飞行,结果如图5所示,迭代至第11 代时,用户平均时延开始产生均匀的波动,波动范围小于0.001,第11 代至第100 代波动仍旧存在且不变.可知,遗传算法面对有无穷多候选解时,结果产生小幅度波动.产生这一结果的原因在于中继无人机的基因编码为转弯角,经过不断的迭代,最佳的转弯角基本确定,那么中继无人机则会按照转弯角进行近似圆轨迹飞行,在用户平均时延上则体现为周期性波动.如图6及图7所示,无人机从坐标不断转弯飞行,最后盘旋飞行,轨迹为椭圆形,体现在图5上为不断波动的平均用户时延,在坐标(124,175)处为用户平均时延最低,为1.113 s.

图5 地面mesh 路由缓存不变场景下用户平均时延

图6 地面mesh 路由缓存不变场景下结果示意图

3.2.3 中继无人机飞行且地面mesh 路由协作缓存场景下用户平均时延

同时考虑中继无人机飞行加上地面无线mesh 路由的缓存情况,中继无人机起始点设为(150,150),如图8所示,曲线呈阶梯下降趋势.最终用户平均时延收敛于0.72.如图9及图10所示,无人机处于盘旋状态.

图7 中继无人机飞行轨迹图

图8 中继无人机保持飞行且地面mesh 路由协作缓存场景下用户平均时延

图9 中继无人机飞行且地面mesh 路由协作缓存场景下示意图

3.2.4 不同初始种群下所收敛的用户平均时延

同时考虑中继无人机飞行加上地面无线mesh 路由的缓存情况,设置不同的初始种群,观察它们的结果,如图11所示,在10 个初始种群种内用户平均时延收敛结果波动在0.008 范围内,在一定程度上可认为遗传算法迭代结果近似于最优解.如表3所示,每一行代表一种收敛情况,第一种收敛情况中,路由器1 表示编号为1 的路由器缓存文件块1 和文件块5,以此类推.横坐标x及纵坐标y表示中继无人机的最终位置坐标,第一种收敛情况中无人机最终坐标为(135.2,146.8).路由器缓存结果各异,中继无人机位置亦不同,故收敛的结果未必一致.

图10 中继无人机飞行轨迹图

综合上述仿真结果分析可得,无论是单独考虑缓存情况,中继无人机保持不动,或是单独考虑中继无人机飞行情况,地面无线mesh 路由的缓存情况不变,亦或二者都发生改变,不论何种,在遗传算法的迭代下,用户平均时延均呈现下降趋势.但仅考虑缓存改变的情况下平均用户时延为0.726 s,仅考虑中继无人机飞行时,用户平均时延为1.113 s,二者都考虑时,用户平均时延为0.72 s,显然,综合考虑地面无线mesh 路由缓存与中继无人机调度,对用户体验的提升更为明显.观察各个无人机轨迹图,可知待时延趋于收敛时,无人机飞行角应基本不变,轨迹近圆形.不同种群迭代收敛结果有一定波动,但相差不大,在一定程度上可认为遗传算法对求解问题有积极意义.

图11 不同种群收敛的平均用户时延

表3 不同初始种群的迭代收敛结果

4 总结与展望

本文从灾后通信设施遭到破坏,人员难以发送求救信息与居民对外通信受到影响的角度出发,研究地面与空中的混合mesh 网络,以及地面无线mesh 路由器协作缓存,作为传输中继的无人机飞行情况.本文重点考虑灾后通信的mesh 网络组建后,无线mesh 路由的协作缓存与传输中继无人机的飞行情况,使用遗传算法保证区域内用户取得文件的平均时延收敛在较低水平.通过设置不同的初始种群,判断遗传算法结果是否为最优解.后续研究将同时考虑多个中继无人机的情况,研究多个区域的通信情况.目前仅采用遗传算法,后续可以多采用几种算法比较,如退火算法,深度强化学习,比较它们的运行时间、准确度、收敛性等因素.