灾后应急通信网络下的中继选择与轨迹优化研究

陈海华 高飞帆 何 明

①(南开大学电子信息与光学工程学院 天津 300350)

②(天津市光电传感器与传感网络技术重点实验室 天津 300350)

③(薄膜光电子技术教育部工程研究中心 天津 300350)

1 引言

近年来，无人机(Unmanned Aerial Vehicle, UAV)凭借其机动性强、部署灵活、可重构性强等特点，开始在灾后救援工作中得到广泛应用，承担着灾情检测、通信覆盖和数据收集等重要任务[1–4]。自然灾害发生后，基站设备和主要道路往往会遭到破坏，使得灾区无法与外界取得联络，外界救援人员也难以进入。此时，便可以利用无人机参与灾后救援工作。无人机基站的快速部署可以迅速为灾区提供应急通信服务[5]，而且无人机的高分辨率相机和低空飞行高度可以产生比卫星图像更精确的2D图像和3D地图[6]，为后续大规模救援的开展提供极大的帮助。

关于中继无人机在灾后的部署，目前已有大量研究。文献[7]使用遗传算法优化中继无人机的部署位置，以提高应急网络的覆盖范围和吞吐量。文献[8]通过K均值聚类算法优化灾后中继无人机的实时部署，并以最大化通信系统的能量效率为目标提出了资源分配算法。在无人机为灾区提供应急通信网络后，使用中继选择技术可以进一步提升通信网络的质量，并降低中继无人机的能耗，延长应急通信网络的续航时间。文献[9]研究了多无人机非正交多址接入(Non-O rthogona l M u ltip le A ccess,NOMA)网络在过时信道下的中继选择算法，降低了系统的中断概率。文献[10]将无人机的信道竞争建模为拥塞博弈模型，研究了动态多无人机通信网络的中继匹配问题。

除了为灾区提供应急通信网络，无人机还经常被用来做灾情检测或数据收集等任务。文献[11]中无人机通过灾后地面的物联网节点来收集数据，并提出了一种最小能耗的无人机轨迹方案。文献[12]将任务分配问题转化为动态匹配问题，为无人机合理分配灾后监测任务。文献[13]为多个无人机规划飞行路线，以使无人机能在最短时间内收集到灾后所有监测点的信息。

上述关于灾后无人机的研究，大多都是单独考虑无人机部署或任务分配场景。在复杂地形条件下，执行低空任务的无人机信道条件比较差，此时需要借助中继无人机构建的应急通信网络来传输数据。因此本文针对灾后应急通信网络下勘察无人机执行任务的场景，研究了中继选择和飞行轨迹与系统能量效率之间的关系。本文的主要贡献如下：(1)考虑了中继无人机的可用通信能量以及勘察无人机的最大飞行速度和实时通信质量，通过联合优化中继选择和飞行轨迹来实现系统的能量效率最大化。(2)由于涉及问题是非确定性多项式难度(Nondeterm inistic Polynom ial hard,NP-hard)问题，难以直接求解。本文提出一种基于连续凸近似(Successive Convex App roxim ation,SCA)和禁忌搜索(Tabu Search,TS)的交替迭代算法，将原问题拆分成轨迹优化子问题和中继选择子问题分别求解，交替迭代直至收敛，得到原问题的近似最优解。(3)仿真结果表明，本文所提算法可以有效提高系统的能量效率，因而在保证勘察无人机的实时通信质量的同时，延长了应急通信网络的整体续航时间。

2 系统模型

考虑如图1所示的灾后应急通信网络的场景，该场景包括1个指挥中心(用D表示)，M个中继无人机(用Um表示第m个中继无人机)和1个勘察无人机(用S表示)。中继无人机悬停在受灾区域上空，为该区域提供应急通信服务。低空的勘察无人机S需要按照任务移动到指定地点，并且在飞行过程中与指挥中心D保持实时通信。由于地形因素的影响，勘察无人机S与指挥中心D之间无法形成直接链路，但可以通过多个中继无人机构建的应急通信网络与指挥中心D建立中继通信链路。假设指挥中心D位于地面的固定位置，所有中继无人机的悬停高度固定为H(U)，勘察无人机S的飞行高度为H(S)。设D的坐标为第m个中继无人机的坐标为m=1,2,...,M，其中[·]T表示转置。由于S的飞行轨迹是随时间连续变化的，为了降低轨迹优化的复杂度，采用离散近似方法[14]将S的飞行时间范围T平分成N个时隙，每个时隙的长度记为ΔT。当ΔT相对较小时，便可以近似认为S在该时隙内的位置是固定的。S在第n个时隙时的坐标可以记为q n=,n=1,2,...,N，因此可以将S的飞行轨迹记为Q=[q1,q2,...,q N]。设S的起点和终点坐标分别为q0和qN，则存在如式(1)的飞行速度约束

图1 系统模型

其中，V表示S的最大飞行速度。

绝大部分情况下，中继无人机与S和D的通信链路都可以近似为视距(Light-of-Sight,LoS)链路[15]。因此本文中只考虑信道的大尺度衰落，其遵循自由空间的路径损耗模型。在第n个时隙中，S与Um的信道系数fn,m(q n)以及D与Um的信道系数gm分别可以表示为

其中，[X]n,m=xn,m，即矩阵X第n行第m列元素为xn,m。约束C1是对链路S-D的最小数据传输速率要求，以保证S的实时通信质量，其中Rmin是数据传输速率阈值。约束C2是S的飞行速度约束。约束C3是中继无人机的通信能量约束，其中Em表示第m个中继无人机的可用通信能量。而且约束C3可以保证单个中继无人机的通信能量不被过度消耗，进而延长应急通信网络的整体续航时间。本文中的飞行时间T根据勘察无人机S的具体任务来设定，并假设无人机动力能量足以支持飞行任务。约束C4是中继选择变量xn,m的整数约束。由于目标函数η(X,Q)以及约束C1和C4既包含连续变量Q，又包含整数变量X，因而该问题是NP-hard问题，难以在多项式时间内直接求解。本文提出一种基于SCA和TS的交替迭代算法求得其近似最优解。

3 算法设计

本文将问题(P1)拆分成两个子问题交替求解，即在中继选择矩阵X固定的情况下，(P1)可以转化为轨迹优化子问题；而在飞行轨迹Q固定的情况下，(P1)可以转化为中继选择子问题。将上述两个子问题分别求解，交替迭代直至收敛，便可得到问题(P1)的近似最优解。

3.1 轨迹优化子问题

在已知中继选择矩阵X的情况下，可以将问题(P1)写成如式(12)的形式

问题(P2)只需要优化S的飞行轨迹Q即可。然而，由式(8)和式(10)可知，即使中继选择矩阵X已知，目标函数η(X,Q)和约束C1仍然是非凸的，所以问题(P2)难以求解。为了求解该问题，本文采用连续凸近似(Su ccessive Convex A p p rox im ation,SCA)方法将(P2)近似为一系列凸优化问题进行迭代求解。

令Q(i)表示第i次迭代时S的飞行轨迹，表示第i次迭代时S在第n个时隙的坐标。将式(2)、式(3)和式(5)代入式(9)并重新整理可得

3.2 中继选择子问题

由于约束C3是整数约束条件，因此问题(P4)是一个NP-hard的组合优化问题，通常难以在多项式时间内求得最优解。禁忌搜索(Tabu Search,TS)算法对局部搜索算法进行了改进，通过对当前解的邻域进行搜索得到新的可行解，并利用禁忌表来避免陷入局部最优，因而对于上述组合优化问题具有很好的性能[17,18]。本文采用TS算法来求解问题(P4)。

3.2.1 TS算法改进

鉴于TS算法的特点，其关键在于初始解的选取、邻域结构还有禁忌表与禁忌长度的设置。本文对TS算法进行了相应改进，使其更适用于求解问题(P4)。

(1)初始解。TS算法对初始解有较强的依赖性，好的初始解可以使算法在邻域中更快搜索到好的解，而差的初始解则会影响算法的收敛速度。而且TS算法需要一个可行解作为初始解，才能进行后续的算法步骤。因此，本文利用贪心算法生成满足约束条件的可行解X(0)作为初始解。

(2)邻域结构。邻域结构的设计是决定TS算法性能优劣的关键。邻域结构的规模越大，TS算法每次迭代时搜索的解会越多，就会有更大的概率获得全局最优解，但每次迭代所需时间也会更长。现阶段，TS算法中常用的邻域有2-opt邻域、3-opt邻域和Cross邻域等[19]。本文针对带约束条件的问题(P4)设置了特有的邻域算子：随机选择两个时隙节点，利用贪心算法重置这两个时隙的中继选择变量。这样可以保证生成的邻域解都能满足约束条件，避免生成大量不可行的邻域解，节省了算法运行时间。

(3)禁忌表与禁忌长度。结合上述邻域结构，本文将禁忌表中的元素设置为算法每次迭代时更改的时隙节点。而且本文采用可变禁忌长度来提高TS算法的性能[20]，其规则为：在TS算法初始化时设置初始禁忌长度，当搜索过程中发现更优解时，增加禁忌长度来提高解的集中性；否则，减少禁忌长度来扩大解的搜索范围。

3.2.2 TS算法流程

结合上述的TS算法改进，本文中TS算法的流程如图2所示，算法描述如下。

图2 TS算法流程图

步骤1初始化TS算法迭代次数j=0，收敛阈值ε0，利用贪心算法生成可行解X(0)作为初始解；

步骤2生成邻域。以当前解为中心，利用设置的邻域算子生成L个邻域解，并将所有邻域解按优化问题(P4)的目标函数值排序得到候选解集合；

步骤3判断是否满足特赦准则。当最优候选解的目标函数值大于当前的全局最优解时，忽略其是否被禁忌，直接采用其作为当前解；否则，采用未被禁忌的最优候选解作为当前解；

步骤4更新禁忌表和禁忌长度。将本次迭代中更改的时隙节点加入禁忌表，并释放已满足禁忌长度的禁忌属性。如果在步骤3中满足特赦准则，增加禁忌长度；否则，减少禁忌长度；

步骤5判断是否满足终止准则。若TS算法的迭代次数大于J(最大迭代次数)或者目标函数值在J0次迭代内的增加量小于ε0，此时TS算法结束循环，输出全局最优解；否则，j=j+1，并转到步骤2。

3.3 交替迭代算法

根据以上两个子问题的解决方案，本文针对问题(P1)提出了基于SCA和TS的交替迭代算法，整个交替迭代算法的流程如图3所示，算法描述如下。

图3 交替迭代算法流程图

步骤2根据Q(i)和X(i)，利用内点法求解问题(P3)得到Q(i+1)；

步骤3将X(i)作为TS算法的初始解，根据Q(i+1)执行TS算法求解问题(P 4)得到X(i+1)和；

令Q(i+1)表示第(i+1)次迭代时问题(P3)的最优解，此时有

4 仿真结果

为了验证本文所提算法的有效性，本节对所提算法进行了仿真验证。在仿真中，将指挥中心D的坐标设置为pD=[-1 000,1 000,0]T，受灾区域设置为如图4所示的正方形区域。假设中继无人机在受灾区域上空均匀分布，覆盖整个受灾区域来提供应急通信网络，并且所有中继无人机的可用通信能量Em和发射功率pm相同。勘察无人机S的起点和终点坐标分别设置为q0=[500,2 000,H(S)]T和q N=[1 500,0,H(S)]T，初始轨迹Q(0)设定为从起点到终点的直线，如图4所示。其余仿真参数如表1所示。

表1 仿真参数

图4 仿真区域

图5给出了不同参数条件下，系统的能量效率与交替迭代次数i的关系。随着交替迭代次数的增加，系统的能量效率会升高并最终收敛。由图5可知，在不同的参数条件下，本文所提算法都可以在4次迭代后收敛，说明本文提出的基于SCA和TS的交替迭代算法具有较好的收敛性。

图5 收敛性验证

此外，本节还将本文所提的联合优化方案与以下3种基准方案进行了对比：(1)只优化中继：在该方案中，S的飞行轨迹采用初始轨迹Q(0)，并且采用TS算法对中继选择矩阵X进行优化。(2)只优化轨迹：在该方案中，中继选择矩阵采用贪心算法获得的初始解X(0)，并且采用SCA方法对S的飞行轨迹Q进行优化。(3)初始方案：在该方案中，S的飞行轨迹采用初始轨迹Q(0)，而且中继选择矩阵采用贪心算法获得的初始解X(0)。

图6展示了经过不同方案优化后勘察无人机S的飞行轨迹。从图6可以看出，相比于只优化中继，在联合优化和只优化轨迹时，S的飞行轨迹都会倾向于靠近离D更近的中继无人机，因为这些中继无人机具有更好的信道系数gm。而且相比于只优化轨迹的方案，联合优化方案中S的飞行轨迹会更加平滑且靠近D。这是因为贪心算法只能获得单个时隙内最优的中继选择，而经过TS算法优化后，S会在所有时隙中更合理地选择中继。两种优化方案得到的中继选择矩阵不同，因而经过优化后S的飞行轨迹也会不同。

图6 不同方案下的飞行轨迹

图7给出了不同优化方案下，系统的能量效率与最大飞行速度V的关系。随着V的增大，S的飞行轨迹可以更加靠近信道条件较好的中继无人机，从而具有更高的能量效率。因此，在联合优化或只优化轨迹时，系统的能量效率会随着V的增大而增加，而且联合优化方案的性能明显优于其他3种方案。但在只优化中继时，S的飞行轨迹始终是初始轨迹，因此系统的能量效率不受V的影响，是一个固定值。本文提出的联合优化方案与只优化中继和只优化轨迹的基准方案相比，在V=13 m/s时，分别能够提升12.9%和13.6%的性能；在V=15 m/s时，分别能够提升22.1%和21.3%的性能。

图7 能量效率与最大飞行速度的关系

图8给出了不同优化方案下，系统的能量效率与中继无人机的可用通信能量Em的关系。从图8可以看出，随着Em的增大，系统的能量效率也会增加。因为当Em增大时，S可以在更多时隙内选择到信道较好的中继无人机。但当Em增大到一定值时，S在每个时隙内都能选择到信道条件最好的中继无人机，因此系统的能量效率不再增加。从图8可以看出，在Em=50 J时，本文所提方案与只优化中继和只优化轨迹的基准方案相比，分别能够提升21.8%和22.6%的性能。相比于其他方案，本文所提出的联合优化方案在Em较小时(比如Em≤70 J)，仍然可以大幅提高系统的能量效率，此时还可以有效防止单个中继无人机的通信能量过度消耗，进一步延长应急通信网络的整体续航时间。

图8 能量效率与可用通信能量的关系

图9给出了不同优化方案下，系统的能量效率与数据传输速率阈值Rmin的关系。从图9中可以看出，随着Rmin的增大，系统的能量效率会逐渐降低，但当Rmin≤3.8 bit/(Hz·s)时，每种优化方案所得到的能量效率会保持不变。这是因为当Rmin增大时，S需要选择更多的中继无人机来转发信号，这样才能满足链路S-D的最小数据传输速率要求。此时S也会选择一些信道条件较差的中继，系统的能量效率便会降低。但当Rmin较小时，S在每个时隙中只需要选择一个信道条件最好的中继无人机便可以满足最小数据传输速率要求，导致不同的Rmin最终会得到相同的中继选择矩阵X，因此系统的能量效率会保持不变。而且由图9可知，当Rmin较大时，联合优化方案的性能明显优于与其他3种方案。在Rmin=4.4 bit/(Hz·s)时，与只优化中继和只优化轨迹的基准方案相比，本文提出的联合优化方案能够提升31.1%和28.2%的性能。

图9 能量效率与数据传输速率阈值的关系

上述结果均是在中继无人机数量M=16的条件下进行的仿真，为了验证所提算法的合理性，本文还对不同数量的中继无人机进行了仿真。勘察无人机S的起点和终点坐标不变，中继无人机在受灾区域上空均匀分布。图10和图11分别是在M=25和M=36的条件下进行的仿真结果，即系统能量效率和最大飞行速度V的关系。从图中可以看出，对于不同数量的中继无人机，本文所提联合优化方案的性能均明显优于其他3种方案，从而验证了所提算法的合理性。本文所提出的联合优化方案与只优化中继和只优化轨迹的方案相比，在M=25,V=13 m/s时，分别能够提升19.4%和17.3%的性能；在M=36,V=13 m/s时，分别能够提升21.5%和17.4%的性能。

图10 M=25时能量效率和最大飞行速度的关系

图11 M=36时能量效率和最大飞行速度的关系

综合上述分析，在不同的参数条件下，本文所提出的联合优化方案的性能均优于其他3种方案。因为与其他方案相比，联合优化方案具有更多的自由度来优化系统的能量效率。在约束条件比较苛刻时，联合优化方案与其他方案的性能差距更加明显，说明本文所提算法可以有效提高系统的能量效率。

5 结论

针对灾后应急通信网络下勘察无人机执行任务的场景，本文考虑了中继无人机的可用通信能量以及勘察无人机的最大飞行速度和实时通信质量，通过联合优化中继选择和飞行轨迹来最大化系统的能量效率。针对该NP-hard优化问题，本文提出一种基于连续凸近似(SCA)和禁忌搜索(TS)的交替迭代算法，可以得到原问题的近似最优解。仿真结果表明，相比于只优化中继和只优化轨迹的基准方案，本文所提出的联合优化方案可以有效提高系统的能量效率，而且在约束条件较为苛刻时，与基准方案的性能差距会更加明显。因此本文所提算法可以在保证勘察无人机实时通信质量的同时，延长应急通信网络的整体续航时间。