基于改进虚拟力算法的无人机边缘节点部署

王峻伟，魏祥麟，范建华，胡永扬

(1. 陆军工程大学研究生院，江苏 南京 210000；2. 国防科技大学第六十三研究所，江苏 南京 210007)

1 引言

移动边缘计算通过将计算和存储资源下沉到网络边缘，为移动用户提供了高性能、低延迟与高带宽的服务环境。另一方面，得益于成本低、机动灵活、快速部署等优势，将无人机作为边缘计算节点的技术在灾难救援和应急响应等特殊环境中广泛应用。作为边缘节点的无人机可以缓存热门内容(地图数据、导航数据、灾难评估数据、气象水文数据等)，并根据地面设备发送的内容请求，将缓存内容直接传输给地面设备，无需从远端云服务器下载，大幅度地降低了内容传输时延[1]。然而，该技术也面临着许多挑战，包括无人机边缘节点的最佳部署、能量限制、干扰管理和路径规划等[2-6]。

基于此，本文重点研究了无人机边缘节点部署问题，针对传统部署算法在多无人机边缘节点部署中收敛速度慢、计算时延大的缺点[7]，设计了一种基于改进虚拟力算法(Improved virtual force algorithm，IVFA)的无人机边缘节点部署算法，在降低服务时延的同时，实现对地面设备的快速有效覆盖。

2 国内外研究现状

现有无人机部署可分为静态部署和动态部署两类：通过人工方式将每一架无人机部属在事先规划的位置并且位置不再改变，称为静态部署；动态部署则是根据环境和网络拓扑结构变化，通过无人机移动提高服务区域的覆盖率和连通度。

关于无人机的动态部署相关研究很多，Zeng等人以通信吞吐量和无人机能耗为约束，通过遗传算法求解所需无人机数目及其最优位置[7]。Wang等人基于负载均衡的思想，实现了节点最小移动距离下的均匀覆盖[8]。然而，上述研究侧重于单架无人机上通信信道以及传输功率的优化，无法保证边缘计算场景下的整体优化效果。文献[9-11]研究了多无人机场景下的部署，Hayajneh等人研究了固定无人机数量下的覆盖概率，同时也分析了多无人机间存在的干扰[9]。Akarsu在此基础上，考虑了地面设备的公平性，以最小化最大传输时延为目标优化了多无人机的部署[10]。Mozaffari等人将计算资源和覆盖效果进行博弈，给出了基于纳什均衡的部署算法[11]。

以上关于无人机的部署具有应用灵活、优化效果明显等优点，为无人机边缘节点的部署提供了理论支撑。然而，上述研究仅考虑了通信需求，忽略了边缘计算场景下地面设备内容请求对于部署的影响。事实上，每架无人机边缘节点的缓存空间有限，地面设备请求的动态性会导致部分无人机边缘节点请求承载不均匀，部分过载节点部署区域服务质量下降，显著增加了通信排队和内容响应时延[12]；另一方面，无人机边缘节点的机载能量有限，已有通过各类启发式算法求解所需无人机边缘节点数目及其最优位置的方法,大多只在理想状态下进行部署，在多个无人机边缘节点协作部署的联合优化过程中消耗了过多的计算资源，不适用于小规模、高机动性的典型无人机边缘计算场景。

因此，为优化无人机边缘节点的部署，研究者们引入了虚拟力的概念，即假定节点受到由周围环境根据某种关系所产生的虚拟力作用，使多个无人机边缘节点在动态环境中能够维持彼此间的关系，将复杂的多无人机边缘节点通信质量保证问题转换为节点控制问题，只要无人机边缘节点之间的距离维持在适当地范围之内，就能一定程度上保持覆盖的质量，降低计算开销，此类利用虚拟力推动部署优化的算法统称为虚拟力算法。Howard等人率先将虚拟力算法引入到解决提高无线传感节点的覆盖率的问题中，将网络中的每个传感器节点视为带有等量同性电荷的粒子，将节点间的力模拟为粒子间的虚拟力[13]。Liu等人在此基础上，提出了一种基于分子力的部署算法(Virtual force algorithm,VFA)，在固定节点数量下实现覆盖面积的最大化。同时，该算法还考虑到了实际部署中节点间障碍对于部署的影响，通过多次迭代寻找出节点的最优部署方案[14]。Loscri等人对于虚拟力算法进行了改进，限制了节点间力的作用范围，减少节点的频繁移动；同时限制节点的移动距离，防止因节点移出监测区域而降低覆盖率；并在节点运动受力公式中加入阻尼，随着节点间能量消耗，系统趋于稳定，以此设定了部署优化的终止条件[15]。

3 场景描述与定义

3.1 无人机边缘计算场景

典型的无人边缘计算场景如图1所示，其中包含了云数据中心、多个无人机边缘节点和地面移动设备。云数据中心维持一个完整内容清单，且具有足够空间存储所有的内容。无人机边缘节点具有有限的存储空间，但其可以连接到云数据中心请求特定内容，并由四个模块组成：无线接口模块、计算模块、存储模块和网络回程连接模块。无线接口模块通常采用IEEE 802.11无线网络通信协议，该协议具有实时调整无线链路上下行调制速率的功能，可以较好地适应动态条件下边缘计算范式中的异构环境；存储模块根据缓存策略有选择地存储流行度高的内容；计算模块用于处理用户请求和感知无人机边缘节点间的状态信息；网络回程连接模块用于提供到云数据中心和其它无人机边缘节点间的高速连接[16]。基于以上功能，无人机边缘节点在接收到地面设备的内容请求后，如果请求的内容已存储在缓存中，则无人机边缘节点直接为地面设备提供服务；否则，需要通过主干链路从云数据中心请求内容。

图1 典型无人机边缘计算场景

3.2 部署参数定义

3.2.1 地面设备覆盖率

地面设备覆盖率是衡量服务覆盖情况的重要指标，定义为部署区域内无人机边缘节点服务的地面设备数量与服务区域内所有发送请求的地面设备数量的比值，比值越大表明覆盖效果越好，覆盖率小于等于1。

3.2.2 区域覆盖均匀度

区域覆盖均匀度反映了区域内所有无人机边缘节点地理分布均匀状况，定义为无人机边缘节点间距离与理想部署距离的标准差。标准差值越小，无人机边缘节点覆盖均匀度就越高，在目标服务区域的覆盖就越均匀，反之，无人机边缘节点分布的均匀状态就越差，在部分目标服务区域会出现无人机边缘节点缓存服务的缺失。

3.2.3 服务时延

无人机边缘节点的部署，需要考虑地面设备接受服务的时延容忍度。无人机的部署必须满足每一个时隙中接受服务地面设备的时延需要，定义为自地面设备发起内容请求到获取完整内容之间的时间。

3.3 模型建立

3.3.1 无人机边缘节点二元感知模型

二元感知模型又称为圆盘感知模型，如图2所示，该模型中无人机边缘节点的服务范围是以该节点水平面坐标为圆心，r为服务半径的圆。为了表示无人机边缘节点与地面设备间的服务关系，引入了二元变量pic。当pic=1 时，表示地面设备c处于无人机边缘节点i的服务范内。

(1)

图2 无人机边缘节点覆盖场景

(2)

其中，d(i，c)为在无人机与地面设备的平面距离。

3.3.2 单个无人机边缘节点最优部署

每一个在边缘计算场景下的无人机节点，周期地收集地面节点的最新位置和内容请求信息,并根据收集到的信息计算当前的最优位置，以此动态地调整飞行轨迹。

假设地面设备处于同一水平面,无人机节点的飞行高度近似不变。在t时刻，无人机的平面坐标为XUAV(t),目标服务区域地面设备平面坐标为Yc(t)且数量C(t)，(xstart，xfinish)、(ystart，yfinish) 为服务区域的边界，计算单架无人机的最优位置问题可化为以下约束：

(3)

(4)

(5)

(6)

(7)

(8)

Zc(t)是目标服务区域内地面设备的服务请求权重，来源于无人机根据自身缓存对内容请求感知后的分配，例如：在t时刻，服务区域中有C(t)个地面设备，每个地面设备请求Mc个内容，Mc的大小会随着时隙改变。这些内容若处于无人机边缘节点的缓存中，可以通过无人机直接提供服务，称之为请求命中；否则，称之为请求丢失，具有较大的服务时延。因此，为了提高对地面设备的服务能力，将每个发送请求的地面设备请求权重Zc(t)设置为与请求命中数负相关的函数，请求命中数越小，请求权重越大，请求内容数量越多，权重越大。

(9)

(10)

其中mc(t)为每个地面设备在时隙t的请求命中数。

此外，在实际无人机运动中，还需要考虑无人机的能耗、速度v、最大转弯角W1等影响因素。本文假设无人机以固定高度飞行，固定高度下的无人机飞行能量消耗只取决于速度和最大转弯角[17]，在此基础上定义无人机在飞行约束下的最大移动距离Mstep。

上述问题可以描述为一个混合整数非线性规划问题，采用多种群优化遗传算法求解得到无人机边缘节点的服务最优位置，其中，输入XUAV(t)和Yc(t)作为多种群优化遗传算法的移民算子，由式(3)可得适应度函数，通过选择、交叉、变异生成下一代后，执行移民操作和人工选择，得到单个无人机边缘节点的最优位置。

4 无人机边缘节点的部署算法IVFA

在单架无人机边缘计算场景中,无人机边缘节点只需周期地计算服务最优位置,然后沿飞行轨迹飞往预定区域上空即可。然而,在多无人机边缘节点的动态部署中,为了确保服务区域内的地面设备能够得到稳定的服务，不仅需要考虑地面设备覆盖率还需兼顾区域覆盖均匀度，以适应动态条件下的对地面设备的服务需要。

为此，本文在传统虚拟力模型的基础上，改进虚拟力为无人机边缘节点与地面设备的万有引力和节点间的分子力，通过虚拟力的作用优化部署，在保证对地面设备的服务的同时提高了覆盖的效率。

4.1 初始状态下的理想部署

在对于服务区域进行初始状态下的部署时，可以假设地面设备为均匀分布，此时的部署可以简化为一个在固定服务区域内，用多个圆覆盖该区域的数学模型。圆的半径为无人机边缘节点的服务半径r，目标是以最小节点数实现最大化的区域覆盖率。由于解析初始状态下部署时，覆盖区域中的盲区和重叠是无法避免的。因此，当相邻圆的相交面积越小时，区域覆盖效率越高，如图3所示，所有实线圆表示无人机边缘节点的服务范围。

图3 初始状态下的几种部署方法

图4 补偿半径选取

通过补偿半径计算出无人机边缘节点的服务面积S(R)，此时在服务区域面积Ssevcie中的无人机边缘节点数量为

(11)

(12)

在此基础上，给出了初始状态下的理想部署，如图5所示。其中，每个圆表示无人机边缘节点的覆盖范围，圆中的数字为无人机编号。

图5 理想状态初始分布图

4.2 改进虚拟力算法

4.2.2 无人机边缘节点间的作用力

对于动态场景中的无人机边缘节点部署，本文参考带电电子之间相互作用的分子力，使用排斥、吸引、盘旋这3个准则来调整节点的分布位置，使节点的区域覆盖率达到最大。无人机边缘节点i受到节点j的作用力定义如下

(13)

无人机边缘节点i所受其它节点作用力的合力为

(14)

4.2.3 无人机边缘节点与地面设备间的作用力

动态部署中地面设备对无人机边缘节点同样具有作用力，促使节点维持在服务区域内的最优部署。假设地面设备作用于节点间的虚拟力基于万有引力定律，无人机边缘节点与地面设备的作用力如下

(15)

其中,M分别为无人机边缘节点i服务地面设备数量的倒数，m为地面设备在通信范围内可以选择的无人机边缘节点数的倒数。dic为节点与地面设备之间的距离，G为万有引力系数。无人机边缘节点与地面设备间万有引力越大，其建立的连接稳定性越强。

4.2.3 虚拟力转化为位移策略

在每个时隙计算完无人机边缘节点动态部署的虚拟力后，需要将虚拟力转化为相应的移动距离，驱动所有受力无人机边缘节点移动到最佳部署位置。

首先，计算无人机边缘节点上受到虚拟力的合力

(16)

将虚合力分解为沿x轴和y轴两个方向上的力，此时在虚拟力作用下对无人机边缘节点飞行轨迹进行调整，将虚拟分力转换为移动距离。

(17)

(18)

(19)

(20)

(21)

(22)

4.3 算法描述

本文的算法步骤描述如下：

① 初始化：按照理想部署分布，计算固定区域内补偿半径，最小化无人机边缘节点数，并记录下无人机节点的初始位置信息；

② 设置相关的虚拟力系数和部署系数。

③ 计算单个无人机边缘节点最优位置：根据不同时隙发送请求的地面设备的状态信息，统计每一架无人机边缘节点上的请求内容数和请求命中数，由式(3)-(10)计算地面设备请求权重，并在固定飞行速度，最大转弯角约束下，由多种群遗传算法计算得到单架无人机边缘节点的最优部署；

④ 虚拟力计算：根据不同时隙中无人机边缘节点服务用户数量以及地面设备可选择无人机边缘节点数量，由式(13)-(15)分别计算无人机边缘节点上相应的虚拟力。

⑤ 无人机边缘节点位移：根据式(16)-(22)将力转化为无人机边缘节点的位移，驱动无人机移动到最佳部署位置。

5 真与结果分析

5.1 仿真环境及参数设定

仿真平台为MATLAB R2017a。仿真研究的目标检测区域设置为7.5km × 4.5km 的水平区域，在该区域内随机分布500 个地面设备，每个设备选择距离最近的无人机边缘节点周期性地发送数量为Mc的内容请求。

目标检测区域中部署48架无人机边缘节点，具有固定的飞行高度和缓存容量。参考文献[20]中空对地信道模型的设计，处于相同高度的无人机边缘节点的服务半径为0.5km，其传输速率只与位置状态相关。无人机边缘节点飞行时还要受到最大转弯角等飞行条件约束。主要仿真参数如表1所示。

表1 仿真参数

5.2 结果分析

图6(a)为通过基于改进虚拟力算法IVFA对无人机边缘节点的部署示意图，为了更好地研究实际部署效果，选取了文献[16]中单纯依靠分子力的传统虚拟力算法VFA作为对比。可以发现VFA算法随着优化进行，过多的节点聚集到区域的边界，区域覆盖均匀度降低明显。而通过IVFA算法进行部署优化，能在保证地面设备覆盖率的同时，较好的维持区域的均匀覆盖，并且避免了无人机边缘节点在部署时由于距离过近而产生的碰撞。图6(b)中对两种虚拟力算法的地面设备覆盖率和区域覆盖均匀度进行了分析，可以发现，IVFA算法同时具有较高的地面设备覆盖率和覆盖均匀度，且随着时隙变化，覆盖效果始终保持稳定。

图6 无人机边缘节点部署示意图

图7分析了3组虚拟力系数条件下的地面设备覆盖率，可以看出，万有引力系数G较大时，在优化初期能保持较好的覆盖率，但随着优化次数的增加，覆盖效果下降明显。这是由于随着优化的进行，无人机边缘节点的部署过于集中于前一时隙中的地面设备，从而使得下一时隙对地面设备的优化效果下降。

图7 不同虚拟力系数下地面设备覆盖率

图8反应了30个时隙中地面设备的内容请求时延，这里忽略了任务处理时延，将用户的平均时延简化如下

Ttotal=E1+E2+E3

(23)

图8 地面设备平均服务时延

其中，E1为边缘节点到地面设备的传输时延，E2为任务排队时延，E3为云数据中心处理任务产生的额外时延。根据文献[20]中的定义，E1中传输速率由空地通道模型确立，E2根据M/M/1排队模型确定。可以看出IVFA算法大幅缩短了地面设备的内容请求时延，同时，随着迭代次数增长，性能保持稳定。

6 总结分析

本文针对无人机边缘节点动态部署问题，提出了一种基于改进虚拟力算法IVFA，在边缘计算场景下无人机边缘节点受虚拟力作用，根据地面设备和周围节点的情况，调整部署位置以满足服务区域覆盖需要。仿真显示，与传统虚拟力算法相比，该算法大大提高了地面设备覆盖率和区域覆盖均匀度，并降低了对地面设备的服务时延。