Research on Relay Selection and Trajectory Optimization in Post-disaster Emergency Communication Network
-
摘要: 近年来,无人机(UAVs)凭借其机动灵活的特点,广泛应用于灾后救援工作。针对灾后应急通信网络下勘察无人机执行任务的场景,为了延长应急通信网络的整体续航时间,该文考虑了中继无人机的可用通信能量以及勘察无人机的最大飞行速度和实时通信质量,通过联合优化中继选择和飞行轨迹来实现系统的能量效率最大化。对于所涉及的非确定性多项式难度(NP-hard)优化问题,该文提出一种基于连续凸近似和禁忌搜索的交替迭代算法,将原问题拆成两个子问题交替求解,得到优化问题的近似最优解。仿真结果表明,该文所提算法具有较好的收敛性,可以有效提高系统的能量效率,相比于只优化中继和只优化轨迹的基准方案,能够提升31.1%和28.2%的性能。Abstract: In recent years, Unmanned Aerial Vehicles (UAVs) have been widely used in post-disaster rescue by virtue of their mobility and flexibility. Considering the scenario that a survey UAV performs tasks using the emergency communication network, in order to extend the overall endurance of the emergency communication network, in this paper, the energy efficiency of the system is maximize by jointly optimizing the relay selection and flight trajectory of the UAV. In addition, the available communication energy of the relay UAVs as well as the maximum flight speed and real-time communication quality of the survey UAV are also considered in the optimization. The resultant Nondeterministic Polynomial hard (NP-hard) optimization problem is approximately solved using an alternate algorithm, which consists of successive convex approximation and tabu search algorithm. The alternate algorithm splits the original problem into two subproblems and solves them alternately to obtain the approximate optimal solution of the optimization problem. Simulation results show that the proposed algorithm has a desirable convergence and can significantly improve the energy efficiency of the system. The performance of the proposed algorithm is improved by 31.1% and 28.2% compared to the benchmark schemes of relay or trajectory optimization.
-
1. 引言
近年来,无人机(Unmanned Aerial Vehicle, UAV)凭借其机动性强、部署灵活、可重构性强等特点,开始在灾后救援工作中得到广泛应用,承担着灾情检测、通信覆盖和数据收集等重要任务[1-4]。自然灾害发生后,基站设备和主要道路往往会遭到破坏,使得灾区无法与外界取得联络,外界救援人员也难以进入。此时,便可以利用无人机参与灾后救援工作。无人机基站的快速部署可以迅速为灾区提供应急通信服务[5],而且无人机的高分辨率相机和低空飞行高度可以产生比卫星图像更精确的2D图像和3D地图[6],为后续大规模救援的开展提供极大的帮助。
关于中继无人机在灾后的部署,目前已有大量研究。文献[7]使用遗传算法优化中继无人机的部署位置,以提高应急网络的覆盖范围和吞吐量。文献[8]通过K均值聚类算法优化灾后中继无人机的实时部署,并以最大化通信系统的能量效率为目标提出了资源分配算法。在无人机为灾区提供应急通信网络后,使用中继选择技术可以进一步提升通信网络的质量,并降低中继无人机的能耗,延长应急通信网络的续航时间。文献[9]研究了多无人机非正交多址接入(Non-Orthogonal Multiple Access, NOMA)网络在过时信道下的中继选择算法,降低了系统的中断概率。文献[10]将无人机的信道竞争建模为拥塞博弈模型,研究了动态多无人机通信网络的中继匹配问题。
除了为灾区提供应急通信网络,无人机还经常被用来做灾情检测或数据收集等任务。文献[11]中无人机通过灾后地面的物联网节点来收集数据,并提出了一种最小能耗的无人机轨迹方案。文献[12]将任务分配问题转化为动态匹配问题,为无人机合理分配灾后监测任务。文献[13]为多个无人机规划飞行路线,以使无人机能在最短时间内收集到灾后所有监测点的信息。
上述关于灾后无人机的研究,大多都是单独考虑无人机部署或任务分配场景。在复杂地形条件下,执行低空任务的无人机信道条件比较差,此时需要借助中继无人机构建的应急通信网络来传输数据。因此本文针对灾后应急通信网络下勘察无人机执行任务的场景,研究了中继选择和飞行轨迹与系统能量效率之间的关系。本文的主要贡献如下:(1)考虑了中继无人机的可用通信能量以及勘察无人机的最大飞行速度和实时通信质量,通过联合优化中继选择和飞行轨迹来实现系统的能量效率最大化。(2)由于涉及问题是非确定性多项式难度(Nondeterministic Polynomial hard, NP-hard)问题,难以直接求解。本文提出一种基于连续凸近似(Successive Convex Approximation, 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的坐标为pD=[x(D),y(D),0]T,第m个中继无人机的坐标为um=[x(U)m,y(U)m,H(U)]T, m=1,2,⋯,M,其中[⋅]T表示转置。由于S的飞行轨迹是随时间连续变化的,为了降低轨迹优化的复杂度,采用离散近似方法[14]将S的飞行时间范围T平分成N个时隙,每个时隙的长度记为ΔT。当ΔT相对较小时,便可以近似认为S在该时隙内的位置是固定的。S在第n个时隙时的坐标可以记为qn=[x(S)n,y(S)n,H(S)]T,n=1,2,⋯,N,因此可以将S的飞行轨迹记为Q=[q1,q2,⋯,qN]。设S的起点和终点坐标分别为q0和qN,则存在如式(1)的飞行速度约束
‖ (1) 其中,V表示S的最大飞行速度。
绝大部分情况下,中继无人机与S和D的通信链路都可以近似为视距(Light-of-Sight, LoS)链路[15]。因此本文中只考虑信道的大尺度衰落,其遵循自由空间的路径损耗模型。在第n个时隙中,S与Um的信道系数 {f_{n,m}}({{\boldsymbol{q}}_n}) 以及D与Um的信道系数gm分别可以表示为
\qquad {f_{n,m}}({{\boldsymbol{q}}_n}) = \sqrt {{\beta _0}{{\left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{q}}_n}} \right\|}^{ - 2}}} (2) \qquad {g_m} = \sqrt {{\beta _0}{{\left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{p}}_{\text{D}}}} \right\|}^{ - 2}}} (3) 其中\left\| \cdot \right\|表示向量的模,{\beta _0}是离信源单位距离时的信道增益。由于本文考虑中继无人机近似为悬停状态,因而中继无人机与指挥中心的信道可认为是类静态的。然而,本文所提方法可以直接推广至中继无人机处于飞行状态的情况。
本文假设所有中继无人机都采用半双工通信,因而每个时隙分成两个时间段。在第n个时隙的第1个时间段,中继无人机接收来自S的信号;在第2个时间段,中继无人机将接收信号转发给D。
在第1个时间段中,S以功率PS发送信号,记为\sqrt {{P_{\text{S}}}} s(t)。则Um在第n个时隙接收到的信号为
u_{n,m}^{}(t) = {f_{n,m}}({{\boldsymbol{q}}_n})\sqrt {{P_{\text{S}}}} s(t) + \mu _{n,m}^{}(t) (4) 其中,{\mu _{n,m}}(t)为Um的接收噪声,设该噪声满足高斯分布,即\mu _{n,m}^{}(t) \sim \mathcal{C}\mathcal{N}\left( {0,\sigma _{n,m}^2} \right)。
在第2个时间段,中继无人机Um采用放大转发(Amplify and Forward, AF)方式转发信号。因此,指挥中心D接收到的来自Um的信号可以表示为
y_{n,m}^{}(t) = {g_m}\sqrt {{p_m}} {w_{n,m}}u_{n,m}^{}(t) + \nu _{n,m}^{}(t) (5) 其中,pm是Um的发射功率,{w_{n,m}} = (\sigma _{n,m}^2 + f_{n,m}^2({{\boldsymbol{q}}_n}){P_s})^{ - 1}为中继转发系数, \nu _{n,m}^{}(t) 是指挥中心D的接收噪声,设其满足高斯分布\nu _{n,m}^{}(t) \sim \mathcal{C}\mathcal{N}\left( {0,\delta _{n,m}^2} \right)。
指挥中心D在接收到多个中继无人机转发的信号时,采用最大比合并(Maximal Ratio Combining, MRC)方式将所有信号进行合并。因而,在第n个时隙,D接收到的总信号为
{y_n}(t) = \sum\limits_{m = 1}^M {{x_{n,m}}{\alpha _{n,m}}y_{n,m}^{}(t)} (6) 其中,{x_{n,m}} \in \left\{ {0,1} \right\}为中继选择变量,xn,m = 1表示中继无人机Um在时隙n被选中参与转发信号,否则表示不参与转发,{\alpha _{n,m}}为各支路信号的加权系数,具体表达式为
{\alpha _{n,m}} = \frac{{{w_{n,m}}{f_{n,m}}({{\boldsymbol{q}}_n}){g_m}}}{{w_{n,m}^2g_m^2\sigma _{n,m}^2 + \delta _{n,m}^2}} (7) 在第n个时隙,链路S-D的数据传输速率可以表示为
{R_n}({x_{n,m}},{{\boldsymbol{q}}_n}) = \frac{1}{2}{\log _2}\left( {\sum\limits_{m = 1}^M {{x_{n,m}}{\gamma _{n,m}}({{\boldsymbol{q}}_n})} } \right) (8) 其中,{\gamma _{n,m}}({{\boldsymbol{q}}_n})为D接收到的中继Um转发信号的信噪比,具体表达式为
{\gamma _{n,m}}({{\boldsymbol{q}}_n}) = \frac{{{P_{\text{S}}}{p_m}g_m^2w_{n,m}^2f_{n,m}^2({{\boldsymbol{q}}_n})}}{{g_m^2w_{n,m}^2{p_m}\sigma _{n,m}^2 + \delta _{n,m}^2}} (9) 因此,在整个时间范围T内,系统的能量效率\eta ({\boldsymbol{X}},{\boldsymbol{Q}})可以表示为
\eta ({\boldsymbol{X}},{\boldsymbol{Q}}) = \frac{{\displaystyle\sum\limits_{n = 1}^N {{R_n}({x_{n,m}},{{\boldsymbol{q}}_n})} }}{{\displaystyle\sum\limits_{n = 1}^N {\left( {\displaystyle\sum\limits_{m = 1}^M {{x_{n,m}}{p_m}} + {P_{\text{S}}}} \right)} }} (10) 其中,X表示由所有xn,m构成的中继选择矩阵。
为了保证勘察无人机S的实时通信质量以及延长应急通信网络的续航时间,本文通过联合优化中继选择和飞行轨迹来最大化系统的能量效率,该联合优化问题可以表示为
\left. \begin{gathered} {\text{(P1) }}\begin{array}{*{20}{c}} {\mathop {\max }\limits_{{\boldsymbol{Q}},{\boldsymbol{X}}} }&\eta \end{array}({\boldsymbol{X}},{\boldsymbol{Q}}) \\ \begin{array}{*{20}{l}} {{\text{s}}{\text{.t}}{\text{.}}}&{{\text{C1}}:{R_n}({x_{n,m}},{{\boldsymbol{q}}_n}) \ge {R_{\min }},\forall n} \\ {}&{{\text{C2}}:{{\left\| {{{\boldsymbol{q}}_n} - {{\boldsymbol{q}}_{n - 1}}} \right\|}^2} \le {{\left( {V\Delta T} \right)}^2},\forall n} \\ {}&{{\text{C3}}:\displaystyle\sum\limits_{n = 1}^N {{x_{n,m}}{p_m}\Delta T} \le {E_m},\forall m} \\ {}&{{\text{C4}}:{{[{\boldsymbol{X}}]}_{n,m}} \in \left\{ {0,1} \right\},\forall m,\forall n} \end{array} \\ \end{gathered} \right\} (11) 其中,[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的整数约束。由于目标函数\eta ({\boldsymbol{X}},{\boldsymbol{Q}})以及约束C1和C4既包含连续变量Q,又包含整数变量X,因而该问题是NP-hard问题,难以在多项式时间内直接求解。本文提出一种基于SCA和TS的交替迭代算法求得其近似最优解。
3. 算法设计
本文将问题(P1)拆分成两个子问题交替求解,即在中继选择矩阵X固定的情况下,(P1)可以转化为轨迹优化子问题;而在飞行轨迹Q固定的情况下,(P1)可以转化为中继选择子问题。将上述两个子问题分别求解,交替迭代直至收敛,便可得到问题(P1)的近似最优解。
3.1 轨迹优化子问题
在已知中继选择矩阵X的情况下,可以将问题(P1)写成如式(12)的形式
\left. \begin{gathered} {\text{(P2) }}\begin{array}{*{20}{c}} {\mathop {\max }\limits_{\boldsymbol{Q}} }&\eta \end{array}({\boldsymbol{X}},{\boldsymbol{Q}}) \\ \begin{array}{*{20}{l}} {{\text{s}}{\text{.t}}{\text{.}}}&{{\text{C1}}:{R_n}({x_{n,m}},{{\boldsymbol{q}}_n}) \ge {R_{\min }},\forall n} \\ {}&{{\text{C2}}:{{\left\| {{{\boldsymbol{q}}_n} - {{\boldsymbol{q}}_{n - 1}}} \right\|}^2} \le {{\left( {V\Delta T} \right)}^2},\forall n} \end{array} \\ \end{gathered} \right\} (12) 问题(P2)只需要优化S的飞行轨迹Q即可。然而,由式(8)和式(10)可知,即使中继选择矩阵X已知,目标函数\eta ({\boldsymbol{X}},{\boldsymbol{Q}})和约束C1仍然是非凸的,所以问题(P2)难以求解。为了求解该问题,本文采用连续凸近似(Successive Convex Approximation, SCA)方法将(P2)近似为一系列凸优化问题进行迭代求解。
令Q(i)表示第i次迭代时S的飞行轨迹,{\boldsymbol{q}}_n^{(i)}表示第i次迭代时S在第n个时隙的坐标。将式(2)、式(3)和式(5)代入式(9)并重新整理可得
\begin{split} & {\gamma _{n,m}}({{\boldsymbol{q}}_n}) =\\ & \quad\frac{{{P_{\text{S}}}g_m^2{p_m}{\beta _0}}}{{\left( {g_m^2{p_m} + \delta _{n,m}^2} \right)\sigma _{n,m}^2{{\left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{q}}_n}} \right\|}^2} + {P_{\text{S}}}{\beta _0}\delta _{n,m}^2}} \end{split} (13) 显然,{\gamma _{n,m}}({{\boldsymbol{q}}_n})是关于{\left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{q}}_n}} \right\|^2}的凸函数。由于一个凸函数的1阶泰勒展开即为其下界,因而
\begin{split} \gamma _{n,m}^{({\text{low}})}({{\boldsymbol{q}}_n}) = & \chi _{n,m}^{(i)} - \kappa _{n,m}^{(i)}\\ & \cdot\left( {{{\left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{q}}_n}} \right\|}^2} - {{\left\| {{{\boldsymbol{u}}_m} - {\boldsymbol{q}}_n^{(i)}} \right\|}^2}} \right) \end{split} (14) 其中
\chi _{n,m}^{(i)} = \frac{{{P_{\text{S}}}g_m^2{p_m}{\beta _0}}}{{\left( {g_m^2{p_m} + \delta _{n,m}^2} \right)\sigma _{n,m}^2{{\left\| {{{\boldsymbol{u}}_m} - {\boldsymbol{q}}_n^{(i)}} \right\|}^2} + {P_{\text{S}}}{\beta _0}\delta _{n,m}^2}} (15) \kappa _{n,m}^{(i)} = \frac{{{P_{\text{S}}}g_m^2{p_m}{\beta _0}\left( {g_m^2{p_m} + \delta _{n,m}^2} \right)\sigma _{n,m}^2}}{{{{\left[ {\left( {g_m^2{p_m} + \delta _{n,m}^2} \right)\sigma _{n,m}^2{{\left\| {{{\boldsymbol{u}}_m} - {\boldsymbol{q}}_n^{(i)}} \right\|}^2} + {P_{\text{S}}}{\beta _0}\delta _{n,m}^2} \right]}^2}}} (16) 由式(14)可以看出,\gamma _{n,m}^{({\text{low}})}({{\boldsymbol{q}}_n})是关于qn的凹函数。把式(14)代入式(8)和式(10)可得链路S-D的数据速率阈值以及系统能量效率的下界,分别记为R_n^{({\text{low}})}({x_{n,m}},{{\boldsymbol{q}}_n})和{\eta ^{({\text{low}})}}({\boldsymbol{X}},{\boldsymbol{Q}})。结合复合函数的凹凸性质可知,R_n^{({\text{low}})}({x_{n,m}},{{\boldsymbol{q}}_n})和{\eta ^{({\text{low}})}}({\boldsymbol{X}},{\boldsymbol{Q}})都是关于qn的凹函数。因此,在给定第i次迭代中S的飞行轨迹Q(i)时,其飞行轨迹的第(i+1)次迭代问题可以写成
\left. \begin{gathered} {\text{(P3) }}\begin{array}{*{20}{c}} {\mathop {\max }\limits_{\boldsymbol{Q}} }&{{\eta ^{({\text{low}})}}} \end{array}({\boldsymbol{X}},{\boldsymbol{Q}}) \\ \begin{array}{*{20}{l}} {{\text{s}}{\text{.t}}{\text{.}}}&{{\text{C1}}:R_n^{({\text{low}})}({x_{n,m}},{{\boldsymbol{q}}_n}) \ge {R_{\min }},\forall n} \\ {}&{{\text{C2}}:{{\left\| {{\boldsymbol{q}}_n^{} - {\boldsymbol{q}}_{n - 1}^{}} \right\|}^2} \le {{\left( {V\Delta T} \right)}^2},\forall n} \end{array} \\ \end{gathered} \right\} (17) 优化问题(P3)的目标函数和约束条件均是关于qn(即Q)的凸函数或凸集,因而是一个凸优化问题,可以使用内点法求解[16]。
3.2 中继选择子问题
在求得S的飞行轨迹Q后,可以将问题(P1)化简成新的问题
\left. \begin{gathered} {\text{(P4) }}\begin{array}{*{20}{c}} {\mathop {\max }\limits_{\boldsymbol{X}} }&\eta \end{array}({\boldsymbol{X}},{\boldsymbol{Q}}) \\ \begin{array}{*{20}{l}} {{\text{s}}{\text{.t}}{\text{.}}}&{{\text{C1}}:{R_n}({x_{n,m}},{{\boldsymbol{q}}_n}) \ge {R_{\min }},\forall n} \\ {}&{{\text{C2}}:\displaystyle\sum\limits_{n = 1}^N {{x_{n,m}}{p_m}\Delta T} \le {E_m},\forall m} \\ {}&{{\text{C3}}:{{[{\boldsymbol{X}}]}_{n,m}} \in \left\{ {0,1} \right\},\forall m,\forall n} \end{array} \\ \end{gathered} \right\} (18) 由于约束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所示,算法描述如下。
步骤1 初始化TS算法迭代次数j = 0,收敛阈值{\varepsilon _0},利用贪心算法生成可行解X(0)作为初始解;
步骤2 生成邻域。以当前解为中心,利用设置的邻域算子生成L个邻域解,并将所有邻域解按优化问题(P4)的目标函数值排序得到候选解集合;
步骤3 判断是否满足特赦准则。当最优候选解的目标函数值大于当前的全局最优解时,忽略其是否被禁忌,直接采用其作为当前解;否则,采用未被禁忌的最优候选解作为当前解;
步骤4 更新禁忌表和禁忌长度。将本次迭代中更改的时隙节点加入禁忌表,并释放已满足禁忌长度的禁忌属性。如果在步骤3中满足特赦准则,增加禁忌长度;否则,减少禁忌长度;
步骤5 判断是否满足终止准则。若TS算法的迭代次数大于J(最大迭代次数)或者目标函数值在J0次迭代内的增加量小于{\varepsilon _0},此时TS算法结束循环,输出全局最优解;否则,j = j + 1,并转到步骤2。
3.3 交替迭代算法
根据以上两个子问题的解决方案,本文针对问题(P1)提出了基于SCA和TS的交替迭代算法,整个交替迭代算法的流程如图3所示,算法描述如下。
步骤1 初始化交替迭代次数i = 0,收敛阈值{\eta _0},目标函数值{\eta ^{(0)}} = 0,飞行轨迹Q(0)和中继选择矩阵X(0);
步骤2 根据Q(i)和X(i),利用内点法求解问题(P3)得到Q(i+1);
步骤3 将X(i)作为TS算法的初始解,根据Q(i+1)执行TS算法求解问题(P4)得到X(i+1)和{\eta ^{(i + 1)}};
步骤4 判断是否满足{\eta ^{(i + 1)}} - {\eta ^{(i)}} < {\eta _0}。若满足,算法结束循环并输出最终结果;否则,i = i + 1,并转到步骤2。
可以证明本文提出的交替迭代算法具有收敛性。在第i次迭代时,由式(14)可知 \gamma _{n,m}^{({\text{low}})}({{\boldsymbol{q}}_n}) 是指挥中心D的接收信噪比{\gamma _{n,m}}({{\boldsymbol{q}}_n})在点 {\left\| {{{\boldsymbol{u}}_m} - {\boldsymbol{q}}_n^{(i)}} \right\|^2} 处的1阶泰勒展开式。由于一个函数的1阶泰勒展开式在展开点的值与原函数值相等,因此 \gamma _{n,m}^{({\text{low}})}({{\boldsymbol{q}}_n}) 和{\gamma _{n,m}}({{\boldsymbol{q}}_n})在展开点 {\left\| {{{\boldsymbol{u}}_m} - {\boldsymbol{q}}_n^{(i)}} \right\|^2} 处相等,即 {\gamma _{n,m}}({\boldsymbol{q}}_n^{(i)}) = \gamma _{n,m}^{({\text{low}})}({\boldsymbol{q}}_n^{(i)}) 。结合式(8)和式(10)则有
\eta ({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i)}}) = {\eta ^{({\text{low}})}}({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i)}}) (19) 令Q(i+1)表示第(i+1)次迭代时问题(P3)的最优解,此时有
{\eta ^{({\text{low}})}}({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i)}}) \le {\eta ^{({\text{low}})}}({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i + 1)}}) (20) 又因为{\eta ^{({\text{low}})}}({\boldsymbol{X}},{\boldsymbol{Q}})是\eta ({\boldsymbol{X}},{\boldsymbol{Q}})的下界,因此对于Q(i+1)有
{\eta ^{({\text{low}})}}({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i + 1)}}) \le \eta ({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i + 1)}}) (21) 结合式(19)—式(21)可知
\eta ({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i)}}) \le \eta ({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i + 1)}}) (22) 不等式(22)表明,交替迭代算法的步骤2每次完成时,优化问题的目标函数\eta ({\boldsymbol{X}},{\boldsymbol{Q}})呈递增式变化。在步骤3中,TS算法总是输出所搜索到的全局最优解,因此有
\eta ({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i + 1)}}) \le \eta ({{\boldsymbol{X}}^{(i + 1)}},{{\boldsymbol{Q}}^{(i + 1)}}) (23) 结合式(22)和式(23)可知
\eta ({{\boldsymbol{X}}^{(i)}},{{\boldsymbol{Q}}^{(i)}}) \le \eta ({{\boldsymbol{X}}^{(i + 1)}},{{\boldsymbol{Q}}^{(i + 1)}}) (24) 即每次迭代完成时,目标函数值\eta ({\boldsymbol{X}},{\boldsymbol{Q}})都呈递增式变化。设中继无人机Um与勘察无人机S之间的水平和垂直距离分别为dv和dh,则二者之间的距离为 \left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{q}}_n}} \right\| = \sqrt {d_v^2 + d_h^2} ,因而\left\| {{{\boldsymbol{u}}_m} - {{\boldsymbol{q}}_n}} \right\| \ge {d_h}。由式(13)可得
\begin{split} {\gamma _{n,m}}({{\boldsymbol{q}}_n}) & \le \frac{{{P_{\text{S}}}g_m^2{p_m}{\beta _0}}}{{\left( {g_m^2{p_m} + \delta _{n,m}^2} \right)\sigma _{n,m}^2d_h^2 + {P_{\text{S}}}{\beta _0}\delta _{n,m}^2}} \\ & \triangleq \gamma _{n,m}^{(\max )}\\[-10pt] \end{split} (25) 由于{x_{n,m}} \in \{ 0,1\} ,结合式(8)、式(10)和式(25)可知
\begin{split} \eta ({\boldsymbol{X}},{\boldsymbol{Q}}) & \le \frac{{\displaystyle\sum\limits_{n = 1}^N {\frac{1}{2}{{\log }_2}\left( {\displaystyle\sum\limits_{m = 1}^M {{x_{n,m}}\gamma _{n,m}^{(\max )}} } \right)} }}{{\displaystyle\sum\limits_{n = 1}^N {\left( {\displaystyle\sum\limits_{m = 1}^M {{x_{n,m}}{p_m}} + {P_{\text{S}}}} \right)} }} \\ & < \frac{{\displaystyle\sum\limits_{n = 1}^N {\frac{1}{2}{{\log }_2}\left( {\displaystyle\sum\limits_{m = 1}^M {1 \cdot \gamma _{n,m}^{(\max )}} } \right)} }}{{\displaystyle\sum\limits_{n = 1}^N {\left( {\displaystyle\sum\limits_{m = 1}^M {0 \cdot {p_m}} + {P_{\text{S}}}} \right)} }} \\ & = \frac{{\displaystyle\sum\limits_{n = 1}^N {\frac{1}{2}{{\log }_2}\left( {\displaystyle\sum\limits_{m = 1}^M {\gamma _{n,m}^{(\max )}} } \right)} }}{{N{P_{\text{S}}}}} \triangleq {\eta ^{(\max )}} \end{split} (26) 从式(26)看出,优化目标函数\eta ({\boldsymbol{X}},{\boldsymbol{Q}})存在上界{\eta ^{(\max )}},结合式(24)可知\eta ({\boldsymbol{X}},{\boldsymbol{Q}})呈递增式变化,因而在交替迭代算法中\eta ({\boldsymbol{X}},{\boldsymbol{Q}})会最终收敛,从而证明本文提出的交替迭代算法具有收敛性。
本文所提出的交替迭代算法可在多项式时间内完成。在步骤2中,利用内点法求解问题(P3)的复杂度为\mathcal{O}\left( {{{(2N)}^{3.5}}} \right)[21]。在步骤3中,TS算法的复杂度主要与TS算法的迭代次数J以及邻域解的数量L有关。对每个邻域解计算\eta ({\boldsymbol{X}},{\boldsymbol{Q}})的复杂度为\mathcal{O}(NM),因此TS算法的复杂度为\mathcal{O}(JLNM)。综上所述,本文所提算法的总复杂度为\mathcal{O}\left( {I({{(2N)}^{3.5}} + JLNM)} \right),其中I是交替迭代算法的迭代次数。
4. 仿真结果
为了验证本文所提算法的有效性,本节对所提算法进行了仿真验证。在仿真中,将指挥中心D的坐标设置为{{\boldsymbol{p}}_{\text{D}}} = {[ - 1\;000,1\;000,0]^{\text{T}}},受灾区域设置为如图4所示的正方形区域。假设中继无人机在受灾区域上空均匀分布,覆盖整个受灾区域来提供应急通信网络,并且所有中继无人机的可用通信能量Em和发射功率pm相同。勘察无人机S的起点和终点坐标分别设置为{{\boldsymbol{q}}_0} = {[500,2\;000,{H^{({\text{S}})}}]^{\text{T}}}和{{\boldsymbol{q}}_N} = [1\;500, 0,{H^{({\text{S}})}}]^{\text{T}},初始轨迹Q(0)设定为从起点到终点的直线,如图4所示。其余仿真参数如表1所示。
参数 符号 设定值 中继无人机数量 (个) M 16 时间范围 (s) T 200 时隙数量 (个) N 200 TS算法的收敛阈值 {\varepsilon _0} 10–2 交替迭代算法的收敛阈值 {\eta _0} 10–2 中继无人机的悬停高度 (m) H(U) 50[6] 勘察无人机的飞行高度 (m) H(S) 20[6] 中继无人机的发射功率 (dBm) pm 30[3] 勘察无人机的发射功率 (dBm) PS 27[3] 单位距离时的信道增益 (dB) {\beta _0} –40[22] 中继无人机的接收噪声功率 (dBm) \sigma _{n,m}^2 –100 勘察无人机的接收噪声功率 (dBm) \delta _{n,m}^2 –100 勘察无人机的最大飞行速度 (m/s) V 13 中继无人机的可用通信能量 (J) Em 60 数据传输速率阈值 (bit/(Hz·s)) Rmin 4.6 图5给出了不同参数条件下,系统的能量效率与交替迭代次数i的关系。随着交替迭代次数的增加,系统的能量效率会升高并最终收敛。由图5可知,在不同的参数条件下,本文所提算法都可以在4次迭代后收敛,说明本文提出的基于SCA和TS的交替迭代算法具有较好的收敛性。
此外,本节还将本文所提的联合优化方案与以下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的飞行轨迹也会不同。
图7给出了不同优化方案下,系统的能量效率与最大飞行速度V的关系。随着V的增大,S的飞行轨迹可以更加靠近信道条件较好的中继无人机,从而具有更高的能量效率。因此,在联合优化或只优化轨迹时,系统的能量效率会随着V的增大而增加,而且联合优化方案的性能明显优于其他3种方案。但在只优化中继时,S的飞行轨迹始终是初始轨迹 ,因此系统的能量效率不受V的影响,是一个固定值。本文提出的联合优化方案与只优化中继和只优化轨迹的基准方案相比,在V=13 m/s时,分别能够提升12.9%和13.6%的性能;在V=15 m/s时,分别能够提升22.1%和21.3%的性能。
图8给出了不同优化方案下,系统的能量效率与中继无人机的可用通信能量Em的关系。从图8可以看出,随着Em的增大,系统的能量效率也会增加。因为当Em增大时,S可以在更多时隙内选择到信道较好的中继无人机。但当Em增大到一定值时,S在每个时隙内都能选择到信道条件最好的中继无人机,因此系统的能量效率不再增加。从图8可以看出,在Em=50 J时,本文所提方案与只优化中继和只优化轨迹的基准方案相比,分别能够提升21.8%和22.6%的性能。相比于其他方案,本文所提出的联合优化方案在Em较小时(比如Em≤70 J),仍然可以大幅提高系统的能量效率,此时还可以有效防止单个中继无人机的通信能量过度消耗,进一步延长应急通信网络的整体续航时间。
图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%的性能。
上述结果均是在中继无人机数量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%的性能。
综合上述分析,在不同的参数条件下,本文所提出的联合优化方案的性能均优于其他3种方案。因为与其他方案相比,联合优化方案具有更多的自由度来优化系统的能量效率。在约束条件比较苛刻时,联合优化方案与其他方案的性能差距更加明显,说明本文所提算法可以有效提高系统的能量效率。
5. 结论
针对灾后应急通信网络下勘察无人机执行任务的场景,本文考虑了中继无人机的可用通信能量以及勘察无人机的最大飞行速度和实时通信质量,通过联合优化中继选择和飞行轨迹来最大化系统的能量效率。针对该NP-hard优化问题,本文提出一种基于连续凸近似(SCA)和禁忌搜索(TS)的交替迭代算法,可以得到原问题的近似最优解。仿真结果表明,相比于只优化中继和只优化轨迹的基准方案,本文所提出的联合优化方案可以有效提高系统的能量效率,而且在约束条件较为苛刻时,与基准方案的性能差距会更加明显。因此本文所提算法可以在保证勘察无人机实时通信质量的同时,延长应急通信网络的整体续航时间。
-
表 1 仿真参数
参数 符号 设定值 中继无人机数量 (个) M 16 时间范围 (s) T 200 时隙数量 (个) N 200 TS算法的收敛阈值 {\varepsilon _0} 10–2 交替迭代算法的收敛阈值 {\eta _0} 10–2 中继无人机的悬停高度 (m) H(U) 50[6] 勘察无人机的飞行高度 (m) H(S) 20[6] 中继无人机的发射功率 (dBm) pm 30[3] 勘察无人机的发射功率 (dBm) PS 27[3] 单位距离时的信道增益 (dB) {\beta _0} –40[22] 中继无人机的接收噪声功率 (dBm) \sigma _{n,m}^2 –100 勘察无人机的接收噪声功率 (dBm) \delta _{n,m}^2 –100 勘察无人机的最大飞行速度 (m/s) V 13 中继无人机的可用通信能量 (J) Em 60 数据传输速率阈值 (bit/(Hz·s)) Rmin 4.6 -
[1] LIU Xiaonan, LI Zan, ZHAO Nan, et al. Transceiver design and multihop D2D for UAV IoT coverage in disasters[J]. IEEE Internet of Things Journal, 2019, 6(2): 1803–1815. doi: 10.1109/JIOT.2018.2877504 [2] AKRAM T, AWAIS M, NAQVI R, et al. Multicriteria UAV base stations placement for disaster management[J]. IEEE Systems Journal, 2020, 14(3): 3475–3482. doi: 10.1109/JSYST.2020.2970157 [3] 王博文, 孙彦景. 基于联盟图博弈的地下空间无人机应急通信网络拓扑控制算法[J]. 电子与信息学报, 2022, 44(3): 996–1005. doi: 10.11999/JEIT211205WANG Bowen and SUN Yanjing. Coalitional graph game based topology control algorithm for unmanned aerial vehicle emergency networks in underground space[J]. Journal of Electronics &Information Technology, 2022, 44(3): 996–1005. doi: 10.11999/JEIT211205 [4] WANG Jingjing, ZHU Shuang, LUO Xiangang, et al. Refined micro-scale geological disaster susceptibility evaluation based on UAV tilt photography data and weighted certainty factor method in Mountainous Area[J]. Ecotoxicology and Environmental Safety, 2020, 189: 110005. doi: 10.1016/j.ecoenv.2019.110005 [5] LIN Na, LIU Yuheng, ZHAO Liang, et al. An adaptive UAV deployment scheme for emergency networking[J]. IEEE Transactions on Wireless Communications, 2022, 21(4): 2383–2398. doi: 10.1109/TWC.2021.3111991 [6] YBAÑEZ R L, YBAÑEZ A A B, LAGMAY A M F A, et al. Imaging ground surface deformations in post-disaster settings via small UAVs[J]. Geoscience Letters, 2021, 8(1): 23. doi: 10.1186/s40562-021-00194-8 [7] MERWADAY A, TUNCER A, KUMBHAR A, et al. Improved throughput coverage in natural disasters: Unmanned aerial base stations for public-safety communications[J]. IEEE Vehicular Technology Magazine, 2016, 11(4): 53–60. doi: 10.1109/MVT.2016.2589970 [8] DO-DUY T, NGUYEN L D, DUONG T Q, et al. Joint optimisation of real-time deployment and resource allocation for UAV-aided disaster emergency communications[J]. IEEE Journal on Selected Areas in Communications, 2021, 39(11): 3411–3424. doi: 10.1109/JSAC.2021.3088662 [9] DENG Dan and ZHOU Qingfeng. Outdated relay selection for UAV-enabled networks with cooperative NOMA[J]. Physical Communication, 2019, 32: 112–119. doi: 10.1016/j.phycom.2018.11.005 [10] LIU Dianxiong, WANG Jinlong, XU Kun, et al. Task-driven relay assignment in distributed UAV communication networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(11): 11003–11017. doi: 10.1109/TVT.2019.2942095 [11] EJAZ W, AHMED A, MUSHTAQ A, et al. Energy-efficient task scheduling and physiological assessment in disaster management using UAV-assisted networks[J]. Computer Communications, 2020, 155: 150–157. doi: 10.1016/j.comcom.2020.03.019 [12] WANG Bowen, SUN Yanjing, LIU Dianxiong, et al. Social-aware UAV-assisted mobile crowd sensing in stochastic and dynamic environments for disaster relief networks[J]. IEEE Transactions on Vehicular Technology, 2020, 69(1): 1070–1074. doi: 10.1109/TVT.2019.2949634 [13] GUO Qing, PENG Jian, XU Wenzheng, et al. Minimizing the longest tour time among a fleet of UAVs for disaster area surveillance[J]. IEEE Transactions on Mobile Computing, 2022, 21(7): 2451–2465. doi: 10.1109/TMC.2020.3038156 [14] JI Jiequ, ZHU Kun, NIYATO D, et al. Joint cache placement, flight trajectory, and transmission power optimization for multi-UAV assisted wireless networks[J]. IEEE Transactions on Wireless Communications, 2020, 19(8): 5389–5403. doi: 10.1109/TWC.2020.2992926 [15] WU Qingqing, ZENG Yong, and ZHANG rui. Joint trajectory and communication design for multi-UAV enabled wireless networks[J]. IEEE Transactions on Wireless Communications, 2018, 17(3): 2109–2121. doi: 10.1109/TWC.2017.2789293 [16] MATTINGLEY J and BOYD S. Real-time convex optimization in signal processing[J]. IEEE Signal Processing Magazine, 2010, 27(3): 50–61. doi: 10.1109/MSP.2010.936020 [17] NGUYEN N T and LEE K. Groupwise neighbor examination for Tabu search detection in large MIMO systems[J]. IEEE Transactions on Vehicular Technology, 2020, 69(1): 1136–1140. doi: 10.1109/TVT.2019.2953635 [18] GAO Xinyu, DAI Linglong, YUEN C, et al. Turbo-like beamforming based on Tabu search algorithm for millimeter-wave massive MIMO systems[J]. IEEE Transactions on Vehicular Technology, 2016, 65(7): 5731–5737. doi: 10.1109/TVT.2015.2461440 [19] POLAT O. A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups[J]. Computers & Operations Research, 2017, 85: 71–86. doi: 10.1016/j.cor.2017.03.009 [20] XIA Yangkun and FU Zhuo. Improved Tabu search algorithm for the open vehicle routing problem with soft time windows and satisfaction rate[J]. Cluster Computing, 2019, 22(4): 8725–8733. doi: 10.1007/s10586-018-1957-x [21] YOU Changsheng and ZHANG Rui. Hybrid offline-online design for UAV-enabled data harvesting in probabilistic LoS channels[J]. IEEE Transactions on Wireless Communications, 2020, 19(6): 3753–3768. doi: 10.1109/TWC.2020.2978073 [22] ZENG Yong, XU Xiaoli, and ZHANG Rui. Trajectory design for completion time minimization in UAV-enabled multicasting[J]. IEEE Transactions on Wireless Communications, 2018, 17(4): 2233–2246. doi: 10.1109/TWC.2018.2790401 期刊类型引用(1)
1. 林永昌. 海上应急关键信息数据收集与传输技术研究. 数字通信世界. 2024(06): 69-71 . 百度学术 其他类型引用(1)