基于Dijkstra-ACO混合算法的应急疏散路径动态规划

曹祥红; 李欣妍; 魏晓鸽; 李森; 黄梦溪; 李栋禄

doi:10.11999/JEIT190854

基于Dijkstra-ACO混合算法的应急疏散路径动态规划

doi: 10.11999/JEIT190854

郑州轻工业大学建筑环境工程学院郑州 450000

基金项目: 河南省科技攻关项目“高层住宅建筑家庭集聚疏散行为的实验与模拟研究”(172102310670)

详细信息

作者简介:
曹祥红：女，1972年生，副教授，研究方向为建筑电气节能技术、智能照明控制技术、智能供配电技术

李欣妍：女，1994年生，硕士生，研究方向为智能照明控制技术

魏晓鸽：女，1987年生，讲师，研究方向为建筑科学与工程、安全科学与灾害防治

李森：男，1987年生，讲师，研究方向为建筑科学与工程、安全科学与灾害防治

黄梦溪：女，1995年生，硕士生，研究方向为建筑电气节能技术

李栋禄：男，1994年生，硕士生，研究方向为智能供配电技术

通讯作者:
曹祥红　caoxhong@zzuli.edu.cn

中图分类号: TP312
计量
- 文章访问数: 3837
- HTML全文浏览量: 1700
- PDF下载量: 161
- 被引次数: 2
出版历程
- 收稿日期: 2019-11-01
- 修回日期: 2020-05-08
- 网络出版日期: 2020-05-17
- 刊出日期: 2020-06-22

Dynamic Programming of Emergency Evacuation Path Based on Dijkstra-ACO Hybrid Algorithm

School of Building Environmental Engineering, Zhengzhou University of Light Industry, Zhengzhou 450000, China

Funds: The Science and Technology in Henan Province Project “An Experimental and Simulated Study on Family Agglomeration and Evacuation Behavior in High-rise Residential Buildings” (172102310670)

摘要

摘要:
现代建筑设计趋于多样化，内部结构和功能越来越复杂，而传统疏散系统逃生指示方向固定、人员疏散时间较长，火灾发生时，不能够及时改变指示方向，易将逃生人员导向危险区域，威胁被困人员生命安全。该文提出了一种Dijkstra-ACO混合路径动态规划算法，在Dijkstra算法获得全局最优路径的基础上再采用蚁群优化(ACO)算法对每个节点进一步优化以获取最优路径，并节省算法运行时间。通过实验仿真验证了混合算法的有效性，能够根据起火点动态规划疏散路径，及时调整疏散指示方向，为火场中人员疏散逃生赢得宝贵时间。
- 应急疏散路径 /
- 动态规划 /
- Dijkstra算法 /
- 蚁群优化算法
Abstract:
With an increasing diversity in modern architectural design, the inner structure of buildings is much more complex than before, which makes the traditional fire emergency escape indication system fail to provide people with real-time instructions because of its inflexibility of changing direction. These failures always lead people to dangerous areas during a fire emergency, which is actual a threaten to people in buildings. A combined algorithm to find a path dynamically during a fire emergency based on Dijkstra and Ant Colony Optimization (ACO) algorithm is presented in this article. This new algorithm shortens the programming time by getting a globally optimal path based on Dijkstra algorithm and operates every single point with ACO algorithm in sequence to get a best path. The combined algorithm is tested by a simulation, in which it is proved effective in adjusting evacuation path depending on the point of ignition. The changeable real-time indication will extend the escaping time with people in a burning building, which is quite precious for saving lives.
- Emergency evacuation path /
- Dynamic programming /
- Dijkstra algorithm /
- Ant Colony Optimization (ACO) algorithm

HTML全文

1. 引言

近年来，自动驾驶、远程医疗和增强现实等一系列新兴业务和产业蓬勃发展，这对无线网络的信息处理能力提出了更高要求，促使无线网络逐步发展成为通信网络、感知网络和计算网络的融合体^[1–3]。与单纯的无线通信技术相比，通信感知一体化技术不仅具有原生的通信功能，而且还具有对环境的感知功能。此外，系统中的资源被通信和感知功能共享，如何协调分配系统资源成为性能优化的新挑战^[4]。

无人机(Unmanned Aerial Vehicle, UAV)具有按需部署、机动可控等优点^[5]。无人机辅助通信感知一体化系统可以充分利用无人机的机动性，动态调整无人机的位置，提高通信用户或者感知目标的信道质量，更好地实现通信和感知性能的优化^[6–10]。文献[6]联合优化无人机位置和发射功率来最大化通信感知一体化系统的网络效用。文献[7]联合设计无人机的飞行轨迹和发射波束赋形，最大化通信用户的通信速率。文献[8]联合优化无人机轨迹、发射波束赋形和感知任务执行时刻，最大化通信用户的通信速率。文献[9]提出一种联合无人机基站和地面基站预测和跟踪用户位置的通信感知一体化方法，并联合优化无人机轨迹以及无人机和用户的关联来最大化用户通信速率和位置克拉美罗下界的加权和。文献[10]考虑概率视距信道模型，在通信和感知服务质量的约束下，联合优化波束赋形和无人机轨迹来提高系统吞吐量。

然而，在上述工作中，空地信道模型大多采用视距信道模型，并忽略了无人机与回程基站之间的回程链路，具有一定的局限性。具体而言，无人机与地面用户或者感知目标的视距信道模型在城市或山区环境下是不准确的，因为它忽略了随机阴影和小尺度衰落^[11]。为了更加准确地建模实际信道，空地信道模型可以采用莱斯信道模型。莱斯信道模型由一个确定性的视距分量和一个由障碍物的反射、散射和衍射引起的随机多路径分量组成，考虑了小尺度衰落等实际因素，对实际信道建模更加准确。同时，当无人机中继回程链路的信道质量较差或者可用带宽受限时，可能会导致用户通信速率下降^[12]。

解决回程链路问题的一种有效方法是在系统中考虑空地协同网络。将无人车(Unmanned Ground Vehicle, UGV)基站作为无人机中继的回程基站和能源补给站，二者协同构建空地通信感知协同网络，提升通信感知一体化系统的性能和服务范围。文献[13]提出一种无人车基站和无人机基站集群组成空地合作应急网络帮助灾区快速重建通信。文献[14]提出了一种空地协同车载组网体系结构。然而，在上述空地协同工作中，空地协同的方式集中在通信或者感知单一方面，因此其无法直接应用在通信感知一体化系统上。

基于上述工作的局限性，本文研究空地协同通信感知一体化系统，由无人车基站和无人机中继集群组成空地协同网络。采用更加精确且与高度角相关的莱斯信道模型建模空地信道。在莱斯信道下，无人机中继与回程基站、用户或者感知目标的高度角越大，传输过程中遇到的障碍物越少^[11]，所以空地协同网络的通信感知性能不仅与传输距离有关，还受高度角的影响。因此，本文提出面向空地协同通信感知一体化系统的资源分配和轨迹联合优化方法，在保证系统感知性能的同时，提高通信性能。

2. 系统模型

如图1所示，本文考虑一个由无人车基站和无人机中继集群组成的空地协同通信感知一体化系统，其中，1个单天线无人车基站作为K个无人机中继的回程基站，无人机中继集群接收无人车基站发送的数据，然后将其发送给G个单天线用户，并感知R个目标区域。假设无人车、无人机和用户天线各个方向的增益相同^[5,11,15]。在任务开始时，无人车基站搭载并发射无人机集群执行通信感知任务，在任务结束后，无人车回收无人机集群，获取无人机集群对目标区域的回声感知信息。

图 1 空地协同通信感知一体化系统

下载: 全尺寸图片幻灯片

为了减少链路之间的干扰，系统采用频分复用的方式，不同链路的信号带宽相互正交且相等^[6]，即 ${B_{{\mathrm{c}},k}} = {B_k} = {B_{{\text{sum}}}}/(2K),\forall k$ ，其中 ${B_{{\text{sum}}}}$ 表示系统总带宽， ${B_{{\mathrm{c}},k}}$ 表示无人车与无人机k链路所使用的信号带宽， ${B_k}$ 表示无人机k与关联用户以及目标区域链路所使用的信号带宽。

将任务周期T离散化为N个时隙，每个时隙的长度为 ${\delta _t} = T/N$ 。设无人车初始时刻和时隙n的水平位置分别为 ${{\boldsymbol{q}}_{\text{I}}}$ 和 ${{\boldsymbol{q}}_{\text{c}}}[n]$ ，无人机k在时隙n的水平位置和垂直高度分别为 ${{\boldsymbol{q}}_k}[n]$ 和 ${h_k}[n]$ ，则无人车和无人机集群的水平位置约束和速度约束分别为

${{\boldsymbol{q}}_k}[0] = {{\boldsymbol{q}}_{\text{c}}}[0] = {{\boldsymbol{q}}_{\text{I}}},{{\boldsymbol{q}}_k}[N] = {{\boldsymbol{q}}_{\text{c}}}[N],\forall k$

(1)

$\left\| {{{\boldsymbol{q}}_i}[n] - {{\boldsymbol{q}}_i}[n - 1]} \right\| \le {\delta _t}V_{i,\max }^{xy},\forall n,i \in \{ {\text{c}},k\}$

(2)

$\left| {{h_k}[n] - {h_k}[n - 1]} \right| \le {\delta _t}V_{k,\max }^z,\forall n,k$

(3)

其中， $\left\| \cdot \right\|$ 表示欧几里得函数， $V_{i,\max }^{xy},i \in \{ {\text{c}},k\}$ 表示无人车c或者无人机k最大水平行驶速度。 $V_{k,\max }^z$ 表示无人机k垂直方向最大行驶速度。

假设用户g、目标区域r和障碍物j的位置已知^[9]，分别为 ${{\boldsymbol{u}}_g}$ , ${{\boldsymbol{u}}_r}$ 和 ${{\boldsymbol{u}}_j}$ ，则无人车防碰撞约束表示为

${d_i} + {d_{{\text{c}},\min }} \le \left\| {{{\boldsymbol{q}}_{\text{c}}}[n] - {{\boldsymbol{u}}_i}} \right\|,\forall n,i \in \{ g,r,j\}$

(4)

其中， ${d_{{\text{c,min}}}}$ 表示无人车的防碰撞安全距离， ${d_i}[n], \forall i \in \{ g,r,j\}$ 表示用户g，目标区域r或者障碍物j边界与其中心位置的最大距离。

设 ${h_{k,{\text{I}}}}$ 为无人机k在时隙0和时隙N的垂直高度，最大最小飞行高度分别为 ${H_{\max }}$ 和 ${H_{\min }}$ ，则

${h_k}[n] = {h_{k,{\text{I}}}},n \in \{ 0,N\} ,\forall k$

(5)

${H_{\min }} \le {h_k}[n] \le {H_{\max }},\forall n,k$

(6)

设 ${d_{\min }}$ 表示无人机集群的最小安全距离，则无人机集群的防碰撞约束为

$\begin{split} {({d_{\min }})^2}\,& \le {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{k'}}[n]} \right\|^2} + {\left| {{h_k}[n] - {h_{k'}}[n]} \right|^2},\\ & \,\forall n,k \ne k' \end{split}$

(7)

定义物体集合 ${{I}} \triangleq \{ {\text{c}},g,r\}$ 。本文采用莱斯信道模型。在时隙n，无人机k到物体i的信道功率增益

${h_{k,i}}[n] = \sqrt {{\beta _{k,i}}[n]{f_{k,i}}[n]} ,\forall n,k,i \in {{I}}$

(8)

其中， ${\beta _{k,i}}[n] = {\beta _0}{({d_{k,i}}[n])^{ - 2}}$ ， ${\beta _0}$ 表示参考距离为1 m时的信道功率增益， ${d_{k,i}}[n]$ 表示无人机k到物体i的距离。 ${f_{k,i}}[n]$ 表示无人机k到物体i的有效衰落功率。

因为 ${f_{k,i}}[n]$ 可以用logistic函数(“S”形状)近似^[5,11,15,16]，即

$\begin{split} {f_{k,i}}[n]& = \left({C_1} + \frac{{{C_2}}}{{1 + \exp ( - ({B_1} + {B_2}{v_{k,i}}[n]))}}\right),\\ &\, \forall n,k,i \in {{I}} \end{split}$

(9)

其中， ${B_1}$ , ${B_2}$ , ${C_1}$ , ${C_2}$ 是最大最小莱斯因子决定的常数。 ${v_{k,i}}[n]$ 表示无人机k与物体i高度角的正弦值¹。

设无人车c和无人机k的峰值发射功率和平均发射功率分别为 ${P_{{\text{c}},\max }}$ , ${\bar P_{\text{c}}}$ , ${P_{k,\max }}$ 和 ${\bar P_k}$ 。在时隙n，设无人车c向无人机k发射的信号功率为 ${p_{{\text{c}},k}}[n]$ ，无人机k的发射功率为 ${p_k}[n]$ ，则

$\sum\limits_{k = 1}^K {{p_{{\text{c}},k}}[n]} \le {P_{{\text{c}},\max }},{p_k}[n] \le {P_{k,\max }},\forall n$

(10)

$\frac{1}{N}\sum\limits_{n = 1}^N {\sum\limits_{k = 1}^K {{p_{{\text{c}},k}}[n]} } \le {\bar P_{\text{c}}},\frac{1}{N}\sum\limits_{n = 1}^N {{p_k}[n]} \le {\bar P_k},\forall k$

(11)

设加性高斯白噪声功率谱密度为 ${N_0}$ 。在时隙n，无人机k回程链路可实现的通信速率(bit/(s·Hz))为

${R_{k,{\text{c}}}}[n] = \frac{1}{{2K}}{\log _2}\left(1 + \frac{{{{\left| {{h_{k,{\text{c}}}}[n]} \right|}^2}{p_{{\text{c}},k}}[n]}}{{{B_{{\text{c}},k}}{N_0}}}\right)$

(12)

为了减少不同用户之间的干扰，在每个时隙内，无人机与地面用户为1对1的关系^[6]，即

$\qquad 0 \le \sum\limits_{g = 1}^G {{a_{k,g}}[n]} \le 1,\forall n,k$

(13)

$\qquad 0 \le \sum\limits_{k = 1}^K {{a_{k,g}}[n]} \le 1,\forall n,g$

(14)

$\qquad {a_{k,g}}[n]({a_{k,g}}[n] - 1) = 0,\forall n,k,g$

(15)

其中， ${a_{k,g}}[n]$ 表示无人机k在时隙n与用户g的关联变量。

在不考虑回程链路的情况下，地面用户g在时隙n的通信速率(bit/(s·Hz))为

$\begin{split} {R_g}[n]& = \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]{{\log }_2}\left(1 + \frac{{{{\left| {{h_{k,g}}[n]} \right|}^2}{p_k}[n]}}{{{B_k}{N_0}}}\right)} ,\\ & \,\forall n,g\\[-1pt] \end{split}$

(16)

在任意时隙内，无人机k与关联的地面用户的通信速率之和不大于无人机k回程链路通信速率，即

${R_g} \le \sum\limits_{k = 1}^K {{a_{k,g}}[n]{R_{k,{\text{c}}}}[n]} ,\forall n,g$

(17)

为了减少无人机的能耗，在每个时隙内，无人机k最多感知1个目标区域^[17]，即

$\qquad 0 \le \sum\limits_{r = 1}^R {{b_{k,r}}[n]} \le 1,\forall n,k$

(18)

$\qquad {b_{k,r}}[n]({b_{k,r}}[n] - 1) = 0,\forall n,k,r$

(19)

其中， ${b_{k,r}}[n]$ 表示无人机k在时隙n与目标区域r的关联变量。

为了提高感知信息的准确性，在整个任务周期内，目标区域至少需要被感知 ${f_r}$ 次，即

${f_r} \le \sum\limits_{n = 1}^N {\sum\limits_{k = 1}^K {{b_{k,r}}[n]} } ,\forall r$

(20)

在时隙n，无人机k与目标区域r关联，则无人机k对目标区域r的有效感知功率

$\begin{split} {p_{k,r}}[n] = \,& \frac{{{\beta _0}{p_k}[n]}}{{d_{k,r}^2[n]}}\\ & \cdot\left({C_1} + \frac{{{C_2}}}{{1 + \exp ( - ({B_1} + {B_2}{v_{k,r}}[n]))}}\right),\\ \forall & n,k,r\\[-1pt] \end{split}$

(21)

设 ${\varGamma _{\min }}$ 表示区域r的最小有效感知功率阈值。为了保证感知链路的建立同时减少其他非关联区域 $r'$ 的回声信号的干扰，需要满足最小有效感知功率约束和感知水平距离约束^[17]，即

$\quad {b_{k,r}}[n]{\varGamma _{\min }} \le {b_{k,r}}[n]{p_{k,r}}[n],\forall n,k,r$

(22)

$\quad {b_{k,r}}[n]\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{u}}_r}} \right\| \le {b_{k,r}}[n]{d_{{\text{s}},\min }},\forall n,k,r$

(23)

定义优化变量 ${\boldsymbol{A}} \triangleq \{ {a_{k,g}}[n],\forall n,k,g\}$ , ${\boldsymbol{B}} \triangleq \{ {b_{k,r}}[n],\forall n,k,r\}$ , ${\boldsymbol{P}} \triangleq \{ {p_{{\text{c}},k}}[n],{p_k}[n],\forall n,k\}$ , ${\boldsymbol{Q}} \triangleq \{ {q_{\text{c}}}[n], {q_k}[n],\forall n,k\}$ 和 ${\boldsymbol{H}} \triangleq \{ {h_k}[n],\forall n,k\}$ 。本文通过联合优化无人机集群对用户的通信关联A、对目标区域的感知关联B、无人车与无人机集群的发射功率P、无人车与无人机集群的水平轨迹Q以及无人机集群的垂直轨迹H，在用户通信、目标感知、回程链路、轨迹等约束下，最大化用户最小平均通信速率，保证通信用户的公平性。相应的问题建模为

${\mathrm{P}}1: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{\boldsymbol{P}},{\boldsymbol{Q}},{\boldsymbol{H}},\eta } \eta$

(24a)

${\mathrm{s.t.}} \;\eta \le \frac{1}{N}\sum\limits_n^N {{R_g}[n]} ,\forall g$

(24b)

$式(1)-式(7)、式(10)-式(20)、式(22)、式(23)$

(24c)

其中， $\eta$ 表示用户最小平均通信速率。上述优化问题是一个包含高度耦合变量且非凸的问题，难以求解。为此，下节将利用块坐标下降法和连续凸优化法对其进行求解。

3. 算法设计

为了方便求解，引入松弛变量 ${\boldsymbol{S}} \triangleq \{ {s_{k,{\text{c}}}}[n],{s_{k,g}}[n], {s_{k,r}}[n],\forall n,k,g,r\}$ 和 ${{\boldsymbol{R}}_{{g}}} \triangleq \{ {R_g}[n],\forall n,g\}$ ，即

${\mathrm{P}}2: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{\boldsymbol{P}},{\boldsymbol{Q}},{\boldsymbol{H}},{\boldsymbol{S}},{{\boldsymbol{R}}_{{g}}},\eta } \eta$

(25a)

$\begin{split} & {\mathrm{s.t}}.\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {a_{k,g}}[n]\\ & \qquad\qquad\quad \cdot{{\log }_2}\left(1 + \frac{{{{\left| {{h_{k,g}}[n]} \right|}^2}{p_k}[n]}}{{{B_k}{N_0}}}\right) ,\forall n,g \end{split}$

(25b)

$\left. \begin{aligned} & {s_{k,i}}[n] \le {B_1} + {B_2}{v_{k,i}}[n],\forall n,k,i \in {{I}}\\ & 式(1)-式(7)、式(10)-式(15)、式(17)-式(20)、\\ & 式(22)、式(23)、式(24{\mathrm{b}}) \end{aligned}\right\}$

(25c)

3.1 通信感知关联优化

对于式(15)和式(19)约束，引入松弛变量 ${\bar a_{k,g}}[n]$ 和 ${\bar b_{k,r}}[n]$ ，等价转化为

${a_{k,g}}[n](1 - {\bar a_{k,g}}[n]) = 0,{a_{k,g}}[n] = {\bar a_{k,g}}[n],\forall n,k,g$

(26)

${b_{k,r}}[n](1 - {\bar b_{k,r}}[n]) = 0,{b_{k,r}}[n] = {\bar b_{k,r}}[n],\forall n,k,r$

(27)

设 ${{\bar {\boldsymbol{A}}}} \triangleq \{ {\bar a_{k,g}}[n],\forall n,k,g\}$ 和 ${{\bar {\boldsymbol{B}}}} \triangleq \{ {b_{k,r}}[n],\forall n,k,r\}$ ，在P, Q, H和S给定的情况下，P2近似表示为

${\mathrm{P}}3: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{{\boldsymbol{R}}_{{g}}},{{\bar {\boldsymbol{A}}}},{{\bar {\boldsymbol{B}}}},\eta } \eta - {\omega _\rho }$

(28a)

$\begin{split} {\mathrm{s.t.}}\;\;\rho = \,&\sum\limits_n^N \sum\limits_k^K \sum\limits_g^G ({{\left| {{a_{k,g}}[n](1 - {{\bar a}_{k,g}}[n])} \right|}^2}\\ & + {{\left| {{a_{k,g}}[n] - {{\bar a}_{k,g}}[n]} \right|}^2}) \\ & + \sum\limits_n^N \sum\limits_k^K \sum\limits_r^R ({{\left| {{b_{k,r}}[n](1 - {{\bar b}_{k,r}}[n])} \right|}^2} \\ &+ {{\left| {{b_{k,r}}[n] - {{\bar b}_{k,r}}[n]} \right|}^2}) \end{split}$

(28b)

${\omega _\rho } = \frac{1}{{2\mu }}\rho$

(28c)

$\begin{split} & 式(13)、式(14)、式(17)、式(18)、式(20)、式(22)、\\ & 式(23)、式(24{\mathrm{b}})、式(25{\mathrm{b}}) \end{split}$

(28d)

其中， $\mu$ 表示惩罚项系数， $\rho$ 表示关联变量惩罚项。当惩罚项 $\rho$ 趋近于0，式(15)和式(19)的约束满足^[17]。

将P3分解成松弛变量 ${{\bar {\boldsymbol{A}}}}$ , ${{\bar {\boldsymbol{B}}}}$ 和关联变量 ${\boldsymbol{A}}$ , ${\boldsymbol{B}}$ 这两个优化子问题，并通过交替优化求解。在 ${\boldsymbol{A}}$ , ${\boldsymbol{B}}$ , ${{\boldsymbol{R}}_{{g}}}$ 和 $\eta$ 给定的情况下，令目标函数对 ${{\bar {\boldsymbol A}}}$ 和 ${{\bar {\boldsymbol B}}}$ 的1阶偏导为0，得到最优的松弛变量形式^[17]

$\bar a_{k,g}^{{\text{opt}}}[n] = \frac{{{a_{k,g}}[n] + a_{k,g}^2[n]}}{{1 + a_{k,g}^2[n]}},\forall n,k,g$

(29)

$\bar b_{k,r}^{{\text{opt}}}[n] = \frac{{{b_{k,r}}[n] + b_{k,r}^2[n]}}{{1 + b_{k,r}^2[n]}},\forall n,k,r$

(30)

在 ${{\bar {\boldsymbol A}}}$ 和 ${{\bar {\boldsymbol B}}}$ 给定的情况下，P3可以简化为

${\mathrm{P}}4: \mathop {\max }\limits_{{\boldsymbol{A}},{\boldsymbol{B}},{{\boldsymbol{R}}_{{g}}},\eta } \eta - {\omega _\rho }\$

(31a)

$\begin{split} & {\mathrm{s.t}}. \;式(13)、式(14)、式(17)、式(18)、式(20)、\\ & \quad\;\; 式(22)、式(23)、式(24{\mathrm{b}})、式(26) \end{split}$

(31b)

问题P4是一个标准的凸优化问题，可以用内点法^[18]求解。

3.2 功率优化

在A,B,Q,H和S给定的情况下，P2可以简化为

$\qquad {\mathrm{P}}5: \mathop {\max }\limits_{{\boldsymbol{P}},{{\boldsymbol{R}}_{{g}}},\eta } \eta$

(32a)

$\begin{split} & {\mathrm{s.t}}. \;式(10)、式(11)、式(17)、式(22)、\\ & \quad\;\; 式(24{\mathrm{b}})、式(25{\mathrm{b}}) \end{split}$

(32b)

显然，P5是一个标准的凸优化问题，可以借助凸优化工具箱求解。

3.3 无人车与无人机集群水平轨迹优化

定理1　当 $2 \le \alpha \le 4$ , ${C_1},{C_2},\gamma ,x,y \gt 0$ 时， ${\psi _1}(x,y) \triangleq \left({C_1} + \dfrac{{{C_2}}}{x}\right)\dfrac{\gamma }{{{y^{\alpha /2}}}}$ 是关于x和y的凸函数。

证明　定义 ${\psi _1}^\prime (x,y) \triangleq \left({C_3} + \dfrac{{{C_4}}}{x}\right)\dfrac{1}{{{y^{\alpha /2}}}}$ , $(2 \le \alpha \le 4)$ , ${C_3} = {C_1}\gamma \ge 0,{C_4} = {C_2}\gamma \ge 0$ 。

令 ${\psi _1}^\prime (x,y)$ 的海森矩阵为 ${\nabla ^2}{\psi _1}^\prime (x,y)$ ，当 $2 \le \alpha \le 4$ 且 $x,y \gt 0$ 时，对于任意 ${\boldsymbol{t}} = {[{t_1},{t_2}]^{\text{T}}}$ ，有 ${{\boldsymbol{t}}^{\text{T}}}{\nabla ^2}{\psi _1}^\prime (x,y){\boldsymbol{t}} \ge 0$ ，即 ${\psi _1}(x,y)$ 是关于 $x,y \gt 0$ 的凸函数。证毕

为了方便处理1阶泰勒展开式，定义 ${X_{k,i}}[n] = 1 + {{\text{e}}^{ - {s_{k,i}}[n]}},\forall n,k,i \in {{I}}$ , ${Y_{k,{\text{c}}}}[n] = {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{\text{c}}}[n]} \right\|^2} + {h_k}{[n]^2},\forall n,k$ , ${Y_{k,i}}[n] = {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{u}}_i}} \right\|^2} + {h_k}{[n]^2}, \forall n, k, i \in \{ g,r\}$ , ${\lambda _{k,{\text{c}}}}[n] = {\beta _0}{p_{{\text{c}},k}}[n]/({B_{{\text{c}},k}}{N_0})$ , ${\lambda _{k,g}}[n] = {\beta _0}\cdot {p_k}[n]/({B_k}{N_0})$ 。设 $X_{k,i}^l[n]$ 和 $Y_{k,i}^l[n]$ 分别为 ${X_{k,i}}[n]$ 和 ${Y_{k,i}}[n]$ 第l次迭代的值。由定理1可知， ${p_{k,r}}[n]$ 是关于 ${X_{k,i}}[n]$ 和 ${Y_{k,i}}[n]$ 的凸函数。将 ${p_{k,r}}[n]$ 在 $X_{k,i}^l[n]$ 和 $Y_{k,i}^l[n]$ 处1阶泰勒展开，得到 ${p_{k,r}}[n]$ 的全局下界 $p_{k,r}^{{\text{lb}}}[n]$ ，即

$\begin{split} {p_{k,r}}[n] \ge\,& \frac{{{\beta _0}{p_k}[n]}}{{Y_{k,r}^l[n]}}({C_1} + \frac{{{C_2}}}{{X_{k,r}^l[n]}}) \\ & + \varphi _{k,r}^l[n]({X_{k,r}}[n] - X_{k,r}^l[n]) + \zeta _{k,r}^l[n]\\ & \cdot({Y_{k,r}}[n] - Y_{k,r}^l[n]) \end{split}\tag{33}$

(33)

$\left. \begin{aligned} & \varphi _{k,r}^l[n] = - \frac{{{C_1}{\beta _0}{p_k}[n]}}{{X_{k,r}^l{{[n]}^2}Y_{k,r}^l[n]}}\\ & \zeta _{k,r}^l[n] = - \frac{{{\beta _0}{p_k}[n]}}{{Y_{k,r}^l{{[n]}^2}}}\left({C_1} + \frac{{{C_2}}}{{X_{k,r}^l[n]}}\right) \end{aligned}\right\}$

(34)

${R_{k,i}}[n]$ 是 ${X_{k,i}}[n]$ 和 ${Y_{k,i}}[n]$ 的凸函数^[11]，将 ${R_{k,i}}[n]$ 在 $X_{k,i}^l[n]$ 和 $Y_{k,i}^l[n]$ 处1阶泰勒展开，得到 $R_{k,i}^{{\text{lb}}}[n]$

$\begin{split} {R_{k,i}}[n] \ge\,& \frac{1}{{2K}}({\log _2}(1 + \frac{{{\lambda _{k,i}}[n]}}{{Y_{k,i}^l[n]}}\left({C_1} + \frac{{{C_2}}}{{X_{k,i}^l[n]}}\right) \\ & + \xi _{k,i}^l[n]({X_{k,i}}[n] - X_{k,i}^l[n]) + t_{k,i}^l[n]\\ & \cdot({Y_{k,i}}[n] - Y_{k,i}^l[n]))\\[-1pt] \end{split}$

(35)

$\begin{split} & \xi _{k,i}^l[n] =\\ & - \frac{{({{\log }_2}{\text{e}}){C_2}{\lambda _{k,i}}[n]}}{{X_{k,i}^l[n](X_{k,i}^l[n]Y_{k,i}^l[n] + {\lambda _{k,i}}[n]({C_1}X_{k,i}^l[n] + {C_2}))}} \end{split}$

(36)

$\begin{split} & t_{k,i}^l[n] =\\ & - \frac{{({{\log }_2}{\text{e}})({C_1}X_{k,i}^l[n] + {C_2}){\lambda _{k,i}}[n]}}{{Y_{k,i}^l[n](X_{k,i}^l[n]Y_{k,i}^l[n] + {\lambda _{k,i}}[n]({C_1}X_{k,i}^l[n] + {C_2}))}} \end{split}$

(37)

设 ${v_{k,i}}[n] \triangleq {h_k}[n]/{({Y_{k,i}}[n])^{1/2}},\forall i \in {{I}}$ 。 ${v_{k,i}}[n]$ 是 ${Y_{k,i}}[n]$ 的凸函数^[11]，将 ${v_{k,i}}[n]$ 在 $Y_{k,i}^l[n]$ 处展开，即

${v_{k,i}}[n] \ge \frac{{{h_k}[n]}}{{{{(Y_{k,i}^l[n])}^{1/2}}}} - \frac{{{h_k}[n]}}{{2{{(Y_{k,i}^l[n])}^{3/2}}}}({Y_{k,i}}[n] - Y_{k,i}^l[n])$

(38)

将式(4)和式(7)分别在 ${\boldsymbol{q}}_{\mathrm{c}}^l[n]$ 和 ${\boldsymbol{q}}_k^l[n] - {\boldsymbol{q}}_{k'}^l[n]$ 处1阶泰勒展开，得

$\begin{split} {d_i} + {d_{{\text{c}},\min }} \le \,& - \left\| {{\boldsymbol{q}}_{\text{c}}^l[n] - {{\boldsymbol{u}}_i}} \right\| + 2{({\boldsymbol{q}}_{\text{c}}^l[n] - {{\boldsymbol{u}}_i})^{\mathrm{T}}}\\ & \cdot({{\boldsymbol{q}}_{\text{c}}}[n] - {{\boldsymbol{u}}_i}),\forall n,i \in \{ g,r,j\} \end{split}$

(39)

$\begin{split} d_{\min }^2 \le \,& {\left| {{h_k}[n] - {h_{k'}}[n]} \right|^2} - {\left\| {{\boldsymbol{q}}_k^l[n] - {\boldsymbol{q}}_{k'}^l[n]} \right\|^2} \\ & + 2{({\boldsymbol{q}}_k^l[n] - {\boldsymbol{q}}_{k'}^l[n])^{\mathrm{T}}}({{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{k'}}[n]),\forall n,k \ne k' \end{split}$

(40)

在A, B, P和H给定的情况下，P2可以近似表示为

${\mathrm{P}}6: \mathop {\max }\limits_{{\boldsymbol{Q}},{\boldsymbol{S}},{{\boldsymbol{R}}_{{g}}},\eta } \eta$

(41a)

${\mathrm{s.t.}} \;{R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]R_{k,{\text{c}}}^{{\text{lb}}}[n]} ,\forall n,g$

(41b)

$\quad\;\; {b_{k,r}}[n]{\varGamma _{\min }} \le {b_{k,r}}[n]p_{k,r}^{{\text{lb}}}[n],\forall n,k,r$

(41c)

$\quad\;\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]} R_{k,g}^{{\text{lb}}}[n],\forall n,g$

(41d)

$\quad\;\; {s_{k,i}}[n] \le {B_1} + {B_2}v_{k,i}^{{\text{lb}}}[n],\forall n,k,i \in {{I}}$

(41e)

$式(1)、式(2)、式(23)、式(24{\mathrm{b}})、式(39)、式(40)$

(41f)

显然，P6是一个标准的凸优化问题，可以用内点法求解。

3.4 无人机集群垂直轨迹优化

式(7)中，在 $h_k^l[n] - h_{k'}^l[n]$ 处1阶泰勒展开，得

$\begin{split} d_{\min }^2 &\le {\left\| {{{\boldsymbol{q}}_k}[n] - {{\boldsymbol{q}}_{k'}}[n]} \right\|^2} - {\left| {h_k^l[n] - h_{k'}^l[n]} \right|^2} \\ & \quad + 2{(h_k^l[n] - h_{k'}^l[n])}({h_k}[n] - {h_{k'}}[n]),\\ & \,\forall n,k \ne k' \end{split}$

(42)

对于式(17)、式(22)和式(26)，与3.3节式(33)和式(34)同理，得到 ${p_{k,r}}[n]$ 和 ${R_{k,i}}[n]$ 的全局下界 $\varGamma _{k,r}^{{\mathrm{lb}}}[n]$ 和 $R_{k,i}^{{\mathrm{lb}}}[n]$ 。则在A,B,P和Q给定的情况下，P10可以近似表示为

${\mathrm{P}}7 \mathop {\max }\limits_{{\boldsymbol{H}},{\boldsymbol{S}},{\boldsymbol{R}}_g,\eta } \eta$

(43a)

${\mathrm{s.t.}}\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]R_{k,{\text{c}}}^{{\text{lb}}}[n]} \forall n,g,$

(43b)

$\quad\;\; {b_{k,r}}[n]{\varGamma _{\min }} \le {b_{k,r}}[n]p_{k,r}^{{\text{lb}}}[n],\forall n,k,r$

(43c)

$\quad\;\; {R_g}[n] \le \frac{1}{{2K}}\sum\limits_{k = 1}^K {{a_{k,g}}[n]} R_{k,g}^{{\text{lb}}}[n],\forall n,g$

(43d)

$\begin{split} & \quad\;\;式(3)、式(5)、式(6)、式(17)、式(22)、\\ & \quad\;\;式(24{\mathrm{b}})、式(25{\mathrm{b}})、式(25{\mathrm{c}})、式(42) \end{split}$

(43e)

其中，式(25c)不等号右边是关于H的凹函数^[11]，因此P7可以用内点法求解。

通过交替优化迭代上面各个子问题直至收敛，完整的优化算法如算法1所示。

表 1 双层迭代算法

(1) 初始化迭代次数 ${l_1}$ =0和 ${l_2}$ =0，关联变量 ${{\boldsymbol{A}}^{{l_1},{l_2}}}$ 和 ${{\boldsymbol{B}}^{{l_1},{l_2}}}$ ，功率变量 ${{\boldsymbol{P}}^{{l_1}}}$ ，水平轨迹变量 ${{\boldsymbol{Q}}^{{l_1}}}$ ，垂直轨迹变量 ${{\boldsymbol{H}}^{{l_1}}}$ ，惩罚项系数　 ${\mu ^{{l_1},{l_2}}}$ ，目标函数 ${\eta ^{{l_1}}}$ ，收敛阈值 ${\varepsilon _1}$ >0, ${\varepsilon _2}$ >0，内层循环最大迭代次数 ${L_2}$
(2) repeat
(3) 　　令内层迭代次数 ${l_2}$ =0，repeat
(4) 　　　　给定{ ${{\boldsymbol{A}}^{{l_1},{l_2}}}$ , ${{\boldsymbol{B}}^{{l_1},{l_2}}}$ , ${{\boldsymbol{P}}^{{l_1}}}$ , ${{\boldsymbol{Q}}^{{l_1}}}$ , ${{\boldsymbol{H}}^{{l_1}}}$ }，通过式(29)和式(30)计算{ ${{{\bar {\boldsymbol A}}}^{{l_1},{l_2} + 1}}$ , ${{{\bar {\boldsymbol B}}}^{{l_1},{l_2} + 1}}$ }
(5) 　　　　给定{ ${{{\bar {\boldsymbol A}}}^{{l_1},{l_2} + 1}}$ , ${{{\bar {\boldsymbol B}}}^{{l_1},{l_2} + 1}}$ , ${\mu ^{{l_1},{l_2}}}$ }，通过求解P4得到{ ${{\boldsymbol{A}}^{{l_1},{l_2} + 1}}$ , ${{\boldsymbol{B}}^{{l_1},{l_2} + 1}}$ , ${\rho ^{{l_1},{l_2} + 1}}$ }
(6) 　　　　更新惩罚项系数 ${\mu ^{{l_1},{l_2} + 1}}$ , ${l_2} = {l_2} + 1$
(7) 　　until ${\rho ^{{l_1},{l_2}}} \le {\varepsilon _2}$ or ${l_2} \ge {L_2}$
(8) 　　更新 ${{\boldsymbol{A}}^{{l_1} + 1}} = {{\boldsymbol{A}}^{{l_1},{l_2}}}$ , ${{\boldsymbol{B}}^{{l_1} + 1}} = {{\boldsymbol{B}}^{{l_1},{l_2}}}$ ，计算 $\eta _1^{{l_1} + 1}$
(9) 　　给定{ ${{\boldsymbol{A}}^{{l_1} + 1}}$ , ${{\boldsymbol{B}}^{{l_1} + 1}}$ , ${{\boldsymbol{Q}}^{{l_1}}}$ , ${{\boldsymbol{H}}^{{l_1}}}$ }，通过求解P5得到{ ${{\boldsymbol{P}}^{{l_1} + 1}}$ , $\eta _2^{{l_1} + 1}$ }
(10) 　给定{ ${{\boldsymbol{A}}^{{l_1} + 1}}$ , ${{\boldsymbol{B}}^{{l_1} + 1}}$ , ${{\boldsymbol{P}}^{{l_1} + 1}}$ , ${{\boldsymbol{H}}^{{l_1}}}$ }，通过求解P6得到{ ${{\boldsymbol{Q}}^{{l_1} + 1}}$ , $\eta _3^{{l_1} + 1,{\text{lb}}}$ }
(11) 　给定{ ${{\boldsymbol{A}}^{{l_1} + 1}}$ , ${{\boldsymbol{B}}^{{l_1} + 1}}$ , ${{\boldsymbol{P}}^{{l_1} + 1}}$ , ${{\boldsymbol{Q}}^{{l_1} + 1}}$ }，通过求解P7得到{ ${{\boldsymbol{H}}^{{l_1} + 1}}$ , $\eta _4^{{l_1} + 1,{\text{lb}}}$ }
(12) 　更新 ${l_1} = {l_1} + 1$ , ${{\boldsymbol{A}}^{{l_1},0}} = {{\boldsymbol{A}}^{{l_1} - 1}}$ , ${{\boldsymbol{B}}^{{l_1},0}} = {{\boldsymbol{B}}^{{l_1} - 1}}$ , ${\mu ^{{l_1},0}}$ ，计算 ${\eta ^{{l_1}}}$
(13) until $\dfrac{{{\eta ^{{l_1}}} - {\eta ^{{l_1} - 1}}}}{{{\eta ^{{l_1} - 1}}}} \lt {\varepsilon _1}$

下载: 导出CSV

| 显示表格

由的步骤(3)–步骤(12)可得， ${\eta ^{{l_1}}}\mathop \le \limits^{\mathrm{a}} \eta _1^{{l_1} + 1}\mathop \le \limits^{\mathrm{b}} \eta _2^{{l_1} + 1}\mathop = \limits^{\mathrm{c}} \eta _2^{{l_1} + 1,{\text{lb}}}\mathop \le \limits^{\mathrm{d}} \eta _3^{{l_1} + 1,{\text{lb}}}\mathop \le \limits^{\mathrm{e}} \eta _4^{{l_1} + 1,{\text{lb}}}\mathop \le \limits^{\mathrm{f}} {\eta ^{{l_1} + 1}}$ 。其中不等号a表示在的步骤(3)–步骤(7)中，惩罚项趋近于0时，目标值具有非减性；不等号b,d和e分别表示在步骤(9)–步骤(11)中，子问题P5, P6和P7的目标函数max(·)具有非减性。等号c表示在步骤(9)中，1阶泰勒展开式在给定局部点具有相同的值。不等号f表示在步骤(11)中1阶泰勒展开得到的 $\eta _4^{{l_1} + 1,{\text{lb}}}$ 是 ${\eta ^{{l_1} + 1}}$ 的下界。因此每次迭代的目标函数值是非减的，且存在上界，因此是收敛的。假设求解器精度为 $\varepsilon$ >0^[18]，算法1的时间复杂度为O((N(1+G+K+KG+KR))log₂(1/ $\varepsilon$ ))。

4. 仿真结果分析

本节给出仿真结果来验证本文提出方案联合优化算法的性能，并且与以下3种方案作对比：

方案1　固定通信感知关联和功率方案，优化无人车和无人机集群的轨迹。将用户和目标区域分成K簇。无人车和无人机在纯通信时隙分配相等的发射功率，在感知时隙，无人机保持峰值发射功率。

方案2　固定无人机集群高度方案，优化无人机集群的通信感知关联、发射功率和水平轨迹以及无人车的发射功率和行进轨迹，即无人机集群保持相同的高度，即 ${h_k}[n] = {h_{k,{\text{I}}}},\forall n$ 。

方案3　固定无人车基站方案，优化无人机集群的通信感知关联、功率和3维轨迹以及无人车的发射功率。在这个方案中，无人车基站保持静止，即， ${{\boldsymbol{q}}_{\text{c}}}[n] = {{\boldsymbol{q}}_{\text{I}}},\forall n$ 。

对比方案1和方案2的优化算法复杂度均为O((N(1+G+K+KG+KR))log₂(1/ $\varepsilon$ ))，方案3优化算法复杂度为O((N(G+max(K+1,R)+KG+KR))log₂(1/ $\varepsilon$ ))。在仿真中，工作区域的长宽均为1 250 m，无人车初始位置为(625,0,0) m，无人机数量K为3，用户数G为6，用户最大半径0.5 m，目标区域数R为4，目标区域最大半径为1 m，障碍物数J为5，障碍物最大半径为30 m。3架无人机的初始高度分别为80 m, 90 m, 100 m，无人车峰值发射功率0.15 W，平均发射功率0.015 W，无人机峰值发射功率0.12 W，平均发射功率0.024 W。无人车和无人机最大水平速度分别15 m/s和30 m/s。无人机最大垂直速度为20 m/s，最大最小飞行高度分别为300 m和50 m，无人机感知目标区域的最大水平距离为200 m。系统总带宽为1 MHz，任务总周期为160 s，时隙长度为0.5 s，高斯白噪声功率谱密度N₀= –169 dBm/Hz，无人车防碰撞距离为20 m，无人机防碰撞距离为10 m，有效感知功率阈值为–95 dBm，任务周期内每个目标区域的感知频数为20次，参考距离1 m的信噪比为-60 dB，莱斯信道参数^[11]B₁=–4.3221, B₂=6.0750, C₁=0, C₂=1。设中 ${\varepsilon _1}$ =1e–4, ${\varepsilon _2}$ =1e–5, ${L_2}$ =10。

给出了算法1目标函数和惩罚项的迭代情况。在不同的 ${\varGamma _{\min }}$ 和 ${f_r}$ 条件下，所提出算法迭代到30次左右，惩罚项趋近于0，且目标函数值收敛，说明在不同参数下，算法1可以达到良好的收敛效果。

图 2 所提算法中目标函数和惩罚项与迭代次数的关系

下载: 全尺寸图片幻灯片

是在 ${\varGamma _{\min }}$ = –95 dBm和 ${f_r}$ =20 次时，算法1得到的无人机中继的通信感知关联情况。可以看出，感知任务较少的无人机会分配通信时隙给感知任务较多的无人机所关联的用户。

图 3 无人机集群通信感知关联

下载: 全尺寸图片幻灯片

给出了当 ${\varGamma _{\min }}$ = –95 dBm和 ${f_r}$ =20 次时，算法1得到的无人车与无人机集群的水平轨迹和3维轨迹。在图4(a)中，无人车依次为无人机提供信道质量较好的回程链路，无人机飞往关联的目标区域执行感知任务，在感知完后，靠近关联的用户和无人车，获得较好的信道质量。从图4(b)中看出，无人车和无人机动态调整位置，改变回程链路、通信链路和感知链路的信道质量，协调通信感知性能之间的权衡。

图 4 无人车和无人机集群的水平轨迹和3维轨迹

下载: 全尺寸图片幻灯片

给出了当 ${f_r}$ =20 次时几种算法用户最小平均通信速率和有效感知功率阈值的关系。随着有效感知功率阈值的减小，用户最小平均通信速率越来越大，但在–105 dBm以后受限于感知频率等因素，减小有效感知功率阈值，用户最小平均通信速率提升不大。所提优化算法的用户最小平均通信速率均比其他3个对比算法明显提高。因为所提优化算法方案拥有更多的优化自由度，实现通信感知性能之间更好的权衡。

图 5 用户最小平均通信速率随有效感知功率阈值的变化

下载: 全尺寸图片幻灯片

给出了当 ${\varGamma _{\min }}$ =–95 dBm时几种算法的用户最小平均通信速率和目标区域感知次数的关系。所提优化算法的用户最小平均通信速率均比其他对比方案高。从图5和图6可以看出，与其他3种优化方案相比，所提优化算法虽然增加了一定的复杂度(仍是可接受的多项式复杂度)，但显著提高了用户最小平均通信速率，从而验证了所提优化算法的有效性和必要性。

图 6 用户最小平均通信速率随感知频率的变化

下载: 全尺寸图片幻灯片

5. 结论

本文提出一种以空地协同的方式辅助通信感知一体化系统的方法，通过优化无人机中继集群对用户的通信关联和目标区域的感知关联、发射功率和飞行轨迹，以及无人车基站的发射功率和行进轨迹，最大化用户最小平均通信速率。基于块坐标下降和连续凸优化法，提出一种双层迭代的算法求解次优解。仿真结果表明，所提优化算法在不同参数下均有良好的收敛性。此外，相比于无人机集群高度固定、通信感知关联和发射功率固定以及回程基站静止这3种基准方案，所提算法可以实现通信感知一体化系统中通信感知任务关联的均衡，并且动态调整空地协同网络的位置和发射功率，使之与通信感知一体化系统的通信感知任务相适应，协调通信感知性能之间的权衡，使得在相同感知性能下，有效提高了用户最小平均通信速率。

图 1 应急疏散环境模型

下载: 全尺寸图片幻灯片

图 2 Dijkstra-ACO混合算法流程图

下载: 全尺寸图片幻灯片

图 3 Dijkstra算法仿真结果

下载: 全尺寸图片幻灯片

图 4 ACO算法仿真结果

下载: 全尺寸图片幻灯片

图 5 Dijkstra-ACO混合算法仿真结果

下载: 全尺寸图片幻灯片

图 6 Dijkstra-GA混合算法仿真结果

下载: 全尺寸图片幻灯片

图 7 假设着火点位置混合算法仿真结果

下载: 全尺寸图片幻灯片

表 1 4种算法仿真结果

Dijkstra ACO Dijkstra-ACO混合算法 Dijkstra-GA混合算法

运行时间(s) 0.237 19.804 1.175 5.134
最短路径(m) 41.6813 36.3848 33.8043 35.9051

下载: 导出CSV

参考文献(25)

十一届全国人大常委会第二十一次会议举行第二次全体会议听取关于消防工作情况的报告[J]. 中国消防, 2011(13): 4–5.

The 21st meeting of the Standing Committee of the 11th National People's Congress holds the second plenary session to hear a report on the work of fire protection[J]. China Fire, 2011(13): 4–5.

雷春英. 基于改进蚁群算法的火灾疏散路径优化研究[D]. [硕士论文], 武汉理工大学, 2014.

LEI Chunying. Route optimization of fire evacuation based on improved ant colony algorithm[D]. [Master dissertation], Wuhan University of Technology, 2014.

于振中, 李强, 樊启高. 智能仿生算法在移动机器人路径规划优化中的应用综述[J]. 计算机应用研究, 2019, 36(11): 3210–3219. doi: 10.19734/j.issn.1001-3695.2018.07.0483

YU Zhenzhong, LI Qiang, and FAN Qigao. Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots[J]. Application Research of Computers, 2019, 36(11): 3210–3219. doi: 10.19734/j.issn.1001-3695.2018.07.0483

杨雁莹, 徐仙伟, 曹霁. 基于仿生理论的新型优化算法综述[J]. 计算机仿真, 2016, 33(6): 233–237, 293. doi: 10.3969/j.issn.1006-9348.2016.06.051

YANG Yanying, XU Xianwei, and CAO Ji. Overview of new optimization algorithms based on bionic theory[J]. Computer Simulation, 2016, 33(6): 233–237, 293. doi: 10.3969/j.issn.1006-9348.2016.06.051

何梦男, 付瑜玲, 陈诚, 等. 基于元胞自动机的应急疏散最短路径优化算法[J]. 中国安全科学学报, 2019, 29(4): 51–57. doi: 10.16265/j.cnki.issn1003-3033.2019.04.009

HE Mengnan, FU Yuling, CHEN Cheng, et al. Shortest path optimal algorithm for emergency evacuation based on cellular automata[J]. China Safety Science Journal, 2019, 29(4): 51–57. doi: 10.16265/j.cnki.issn1003-3033.2019.04.009

任伟建, 左方晨, 黄丽杰. 基于GIS的Dijkstra算法改进研究[J]. 控制工程, 2018, 25(2): 188–191. doi: 10.14107/j.cnki.kzgc.150340

REN Weijian, ZUO Fangchen, and HUANG Lijie. The improvement research of Dijkstra algorithm based on GIS[J]. Control Engineering of China, 2018, 25(2): 188–191. doi: 10.14107/j.cnki.kzgc.150340

张银铃, 牛小梅. 蚁群算法在移动机器人路径规划中的仿真研究[J]. 计算机仿真, 2011, 28(6): 231–234. doi: 10.3969/j.issn.1006-9348.2011.06.057

ZHANG Yinling and NIU Xiaomei. Simulation research on mobile robot path planning based on ant colony optimization[J]. Computer Simulation, 2011, 28(6): 231–234. doi: 10.3969/j.issn.1006-9348.2011.06.057

陈月云, 简荣灵, 赵庸旭. 基于快速群体智能算法的毫米波天线设计[J]. 电子与信息学报, 2018, 40(2): 493–499. doi: 10.11999/JEIT170455

CHEN Yueyun, JIAN Rongling, and ZHAO Yongxu. Millimeter wave antenna design based on fast swarm intelligence algorithm[J]. Journal of Electronics &Information Technology, 2018, 40(2): 493–499. doi: 10.11999/JEIT170455

王晨旸, 张玉茹. 对基本蚁群算法的改进及其在TSP中的应用[J]. 哈尔滨商业大学学报: 自然科学版, 2017, 33(5): 561–564.

WANG Chenyang and ZHANG Yuru. Improvement of basic ant colony algorithm and its application in TSP[J]. Journal of Harbin University of Commerce:Natural Sciences Edition, 2017, 33(5): 561–564.

齐茁. 建筑火灾中人员疏散自适应蚁群算法的研究[D]. [硕士论文], 沈阳航空航天大学, 2011.

QI Zhuo. Adaptive ant colony algorithm based on evacuation in building fire[D]. [Master dissertation], Shenyang Aerospace University, 2011.

陈超, 张莉. 基于改进蚁群算法的三维路径规划[J]. 计算机工程与应用, 2019, 55(20): 192–196. doi: 10.3778/j.issn.1002-8331.1904-0212

CHEN Chao and ZHANG Li. Three-dimensional path planning based on improved ant colony algorithm[J]. Computer Engineering and Applications, 2019, 55(20): 192–196. doi: 10.3778/j.issn.1002-8331.1904-0212

熊沂铖, 王栋. 基于蚁群算法的车辆路径问题研究[J]. 信息技术, 2019(7): 15–17, 23.

XIONG Yicheng and WANG Dong. Vehicle routing problem based on ant colony algorithm[J]. Information Technology, 2019(7): 15–17, 23.

段鹏飞. 面向校园疏散的均衡模型与疏导优化方法研究[D]. [博士论文], 武汉理工大学, 2013.

DUAN Pengfei. Research on equilibrium model and optimization method for campus evacuation[D]. [Ph. D. dissertation], Wuhan University of Technology, 2013.

杨桂华, 符士宾, 刘志毅, 等. 基于改进蚁群算法的室内移动机器人路径规划[J]. 科学技术与工程, 2019, 19(19): 175–179.

YANG Guihua, FU Shibin, LIU Zhiyi, et al. Path planning of indoor mobile robot based on improved ant colony algorithm[J]. Science Technology and Engineering, 2019, 19(19): 175–179.

温正. 精通MATLAB科学计算[M]. 北京: 清华大学出版社, 2015: 55–59.

WEN Zheng. Proficient in MATLAB Scientific Computing[M]. Beijing: Tsinghua University Press, 2015: 55–59.

王辉, 朱龙彪, 王景良, 等. 基于Dijkstra-蚁群算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(5): 489–496. doi: 10.3785/j.issn.1006-754X.2016.05.012

WANG Hui, ZHU Longbiao, WANG Jingliang, et al. Research on path planing of parking system based on Dijkstra-ant colony hybrid algorithm[J]. Chinese Journal of Engineering Design, 2016, 23(5): 489–496. doi: 10.3785/j.issn.1006-754X.2016.05.012

石晓达, 孙连英, 葛娜, 等. 应急资源配送中Dijkstra改进算法的研究[J]. 北京联合大学学报, 2018, 32(2): 61–66. doi: 10.16255/j.cnki.ldxbz.2018.02.011

SHI Xiaoda, SUN Lianying, GE Na, et al. Research on the improved algorithm of Dijkstra in emergency resource distribution[J]. Journal of Beijing Union University, 2018, 32(2): 61–66. doi: 10.16255/j.cnki.ldxbz.2018.02.011

WANG Han, ZHANG Hongjun, WANG Kun, et al. Off-road path planning based on improved ant colony algorithm[J]. Wireless Personal Communications, 2018, 102(2): 1705–1721. doi: 10.1007/s11277-017-5229-5

DENTLER J, ROSALIE M, DANOY G, et al. Collision avoidance effects on the mobility of a UAV swarm using chaotic ant colony with model predictive control[J]. Journal of Intelligent & Robotic Systems, 2018, 93(1/2): 227–243. doi: 10.1007/s10846-018-0822-8

CHEN Zhiping, LI Zhijun, LIU Zhen, et al. The research and application of improved ant colony algorithm with multi-thresholds in edge detection[C]. International Conference on Industrial Informatics-Computing Technology, Intelligent Technology, Industrial Information Integration, Wuhan, China, 2017: 5–9. doi: 10.1109/ICIICII.2017.27.

CHIN W, SAPUTRA A A, and KUBOTA N. A neuro-based network for on-line topological map building and dynamic path planning[C]. 2017 International Joint Conference on Neural Networks, Anchorage, USA, 2017: 2805–2810. doi: 10.1109/IJCNN.2017.7966202.

YAO Baozhen, CHEN Chao, SONG Xiaolin, et al. Fresh seafood delivery routing problem using an improved ant colony optimization[J]. Annals of Operations Research, 2017, 273(1/2): 163–185. doi: 10.1007/s10479-017-2531-2

FATHI M, RODRÍGUEZ V, and ALVAREZ M J. A novel memetic ant colony optimization-based heuristic algorithm for solving the assembly line part feeding problem[J]. The International Journal of Advanced Manufacturing Technology, 2014, 75(1/4): 629–643. doi: 10.1007/s00170-014-6068-0

DU Baigang and GUO Shunsheng. Production planning conflict resolution of complex product system in group manufacturing: A novel hybrid approach using ant colony optimization and Shapley value[J]. Computers & Industrial Engineering, 2016, 94: 158–169. doi: 10.1016/j.cie.2015.12.015

张勇, 高鑫鑫, 王昱洁. 基于SFLA-GA混合算法求解时间最优的旅行商问题[J]. 电子与信息学报, 2018, 40(2): 363–370. doi: 10.11999/JEIT170484

ZHANG Yong, GAO Xinxin, and WANG Yujie. Solving the time optimal traveling salesman problem based on hybrid shuffled frog leaping algorithm-genetic algorithm[J]. Journal of Electronics &Information Technology, 2018, 40(2): 363–370. doi: 10.11999/JEIT170484

施引文献

期刊类型引用(2)

1.	潘钰，胡航，金虎，雷迎科，冯辉，姜丽，张孟伯. 非授权频段下无人机辅助通信的轨迹与资源分配优化. 电子与信息学报. 2024(11): 4287-4294 . 本站查看
2.	郭丹. 无线传感器网络簇间通信信息自适应节能优化方法. 长江信息通信. 2024(11): 104-106 . 百度学术

其他类型引用(0)

资源附件(0)

访问统计

图(7) / 表(1)

计量

文章访问数: 3837
HTML全文浏览量: 1700
PDF下载量: 161
被引次数: 2

1. 引言
2. 系统模型
3. 算法设计
3.1 通信感知关联优化
3.2 功率优化
3.3 无人车与无人机集群水平轨迹优化
3.4 无人机集群垂直轨迹优化
4. 仿真结果分析
5. 结论

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于Dijkstra-ACO混合算法的应急疏散路径动态规划

doi: 10.11999/JEIT190854

通讯作者:
曹祥红　caoxhong@zzuli.edu.cn

计量

Dynamic Programming of Emergency Evacuation Path Based on Dijkstra-ACO Hybrid Algorithm

1. 引言

2. 系统模型

3. 算法设计

3.1 通信感知关联优化

3.2 功率优化

3.3 无人车与无人机集群水平轨迹优化

3.4 无人机集群垂直轨迹优化

4. 仿真结果分析

5. 结论

期刊类型引用(2)

其他类型引用(0)

计量

目录

1. 引言

2. 系统模型

3. 算法设计

3.1 通信感知关联优化

3.2 功率优化

3.3 无人车与无人机集群水平轨迹优化

3.4 无人机集群垂直轨迹优化

4. 仿真结果分析

5. 结论

	Dijkstra	ACO	Dijkstra-ACO混合算法	Dijkstra-GA混合算法
运行时间(s)	0.237	19.804	1.175	5.134
最短路径(m)	41.6813	36.3848	33.8043	35.9051

留言板

基于Dijkstra-ACO混合算法的应急疏散路径动态规划

doi: 10.11999/JEIT190854

通讯作者: 曹祥红 caoxhong@zzuli.edu.cn

计量

出版历程

Dynamic Programming of Emergency Evacuation Path Based on Dijkstra-ACO Hybrid Algorithm

1. 引言

2. 系统模型

3. 算法设计

3.1 通信感知关联优化

3.2 功率优化

3.3 无人车与无人机集群水平轨迹优化

3.4 无人机集群垂直轨迹优化

4. 仿真结果分析

5. 结论

期刊类型引用(2)

其他类型引用(0)

计量

出版历程

目录

1. 引言

2. 系统模型

3. 算法设计

3.1 通信感知关联优化

3.2 功率优化

3.3 无人车与无人机集群水平轨迹优化

3.4 无人机集群垂直轨迹优化

4. 仿真结果分析

5. 结论

通讯作者:
曹祥红　caoxhong@zzuli.edu.cn