高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

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

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

曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划[J]. 电子与信息学报, 2020, 42(6): 1502-1509. doi: 10.11999/JEIT190854
引用本文: 曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划[J]. 电子与信息学报, 2020, 42(6): 1502-1509. doi: 10.11999/JEIT190854
Li Fei, Zheng Bao-yu, Zhao Sheng-mei. Quantum Neural Network and Its Applications[J]. Journal of Electronics & Information Technology, 2004, 26(8): 1332-1339.
Citation: Xianghong CAO, Xinyan LI, Xiaoge WEI, Sen LI, Mengxi HUANG, Donglu LI. Dynamic Programming of Emergency Evacuation Path Based on Dijkstra-ACO Hybrid Algorithm[J]. Journal of Electronics & Information Technology, 2020, 42(6): 1502-1509. doi: 10.11999/JEIT190854

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

doi: 10.11999/JEIT190854
基金项目: 河南省科技攻关项目“高层住宅建筑家庭集聚疏散行为的实验与模拟研究”(172102310670)
详细信息
    作者简介:

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

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

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

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

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

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

    通讯作者:

    曹祥红 caoxhong@zzuli.edu.cn

  • 中图分类号: TP312

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

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)算法对每个节点进一步优化以获取最优路径,并节省算法运行时间。通过实验仿真验证了混合算法的有效性,能够根据起火点动态规划疏散路径,及时调整疏散指示方向,为火场中人员疏散逃生赢得宝贵时间。

  • 随着无线通信系统的逐步发展,定位技术在其中扮演着越来越重要的角色。在6G愿景中,定位服务将与通信、计算、控制和感知等功能进行更深度的融合,构成多功能、高聚合度、高效率的网络[1]。文献[2]也提出了增强的定位服务嵌入超密度移动网络中的架构,以提供更好的网络服务。并且定位的精度要求也从5G时代的2维空间10 cm提升到3维空间1 cm[3]。6G系统的设计特性为高分辨率定位的实现创造了条件,也对一些现有技术提出了挑战。

    首先,定位系统需要适应6G的信道特点。因为定位系统当中重要的一环是对信道中蕴含的到达时间(Time Of Arrival,TOA)和到达角(Angle Of Arrival, AOA)等传播参数的估计(并且TOA估计也是AOA估计的基础环节)。6G网络在THz频段以下的最大带宽约为1 GHz,典型带宽为300~800 MHz[4],这意味着信号在空间中的厘米级传播将导致在信道模型中出现小数时延。要设计和测试高分辨率定位系统,必须先在信道仿真实现中体现高分辨率的时延,以准确还原实际场景的传播环境对定位信号和算法产生的影响。

    经典的高分辨率信道仿真实现方案是时域过采样方法[5]。只要过采样阶数充分大,就可以对信道当中的小数采样时延参数进行精确仿真。但是过采样方法的弊端在于其复杂度随着过采样阶数的增加而指数增加,并且在实现过程中滤波器的因果性要通过截断窗函数来近似保证。另一种实现方案是多速率有限冲激响应(Finite Impulse Response, FIR)滤波器组[6]。与过采样方法不同,该方法通过线性插值或多相结构滤波器组来实现与过采样方法相同的效果,并且复杂度更低。然而当所需过采样阶数增高时,滤波器设计的复杂度以及滤波过程所带来的时延开销也会急剧增大。因此需要设计一种低复杂度但与过采样方法保持相同高精度的信道仿真实现方案。

    其次,该系统的实现依赖于6G系统的分布式网络架构[4]。分布式锚点系统可以给定位系统提供更细的坐标划分,更多的锚点数量,更完善的覆盖,这些都能为定位精度的提升创造有利条件。但是该系统也存在时钟漂移导致的同步问题。6G系统要求系统同步误差在1 ns水平[4],但1 ns的同步误差将会导致30 cm的定位误差,通信能够容忍的同步误差在高分辨率定位要求下变得不可接受。传统的基于匹配滤波的TOA估计和极大似然定位的系统[7]由于严重依赖系统的同步性,在没有任何外部信息输入的条件下难以克服上述同步误差带来的影响[8]。文献[9]采用节点优选法优化了到达时间差(Time Difference Of Arrival, TDOA)并取得了较好的定位结果;文献[10]采用半定松弛方法进一步优化了TDOA下的位置解算,适应更大的同步误差。但是在6G分布式场景中,基站与基站以及基站与锚点间均存在随机的同步误差,TDOA机制难以从根本上解决该问题。而基于往返时间(Round Trip Time, RTT)的定位方案[11]虽然可以使用同源时钟克服上述同步误差,但需要上下行链路的双向交互和持续进行的调度配合才能完成定位,对空口设计的要求高。因此该场景下的定位系统应该能够对抗同步误差,并且只需要单次链路传输和异步时钟系统。

    最后,6G中多入多出(Multi-Input Multi-Output, MIMO)支持的天线规模将进一步增长,超大规模MIMO(ultra-massive MIMO)的应用为信号参数提供了更多的维度[12],尤其为高分辨率的AOA估计提供了保障。

    基于上述分析,本文提出了一种新的面向6G的高分辨率无线信道频域仿真方法及定位技术;在信道仿真实现方面,采用频域等效的方法在信道中引入小数时延,利用时频等效将时域过采样过程转换为频域处理,在降低复杂度的同时直接产生基带采样率下的等效时频域信道响应;而在定位技术方面,设计了基于首到达径估计的AOA定位系统。虽然时延检测依然是AOA定位的基础,但是由于AOA信息不依赖于测量出的绝对时间,其检测只需要通过检测首到达径来完成,因此可以不受同步误差的影响并且利用大规模天线的增益完成高精度定位。

    AOA信息蕴含于阵列天线接收信号之间的相位差当中,并且与阵列天线的几何结构有关。为了简化系统,同时结合实际系统配置,每个锚点上的接收阵列建模为如图1所示的双ULA组合结构。

    图 1  接收阵列结构

    图1中的接收阵列由μλ两个方向的ULA组合而成,每个方向各M个以半波长为间隔排列的阵元,用蓝色和红色区分开来。黑色阵元是μλ子阵列的共同参考阵元,其基准相位设置为0。(xi,yi)为第i个锚点在公有直角坐标系中的坐标。每个锚点的来波方向采用其所带阵列的自有极坐标系来表示,如图1中第i个锚点的来波方向记为φi。每个阵列的μλ方向与公有直角坐标系的xy方向保持一致,因此自有极坐标系与公有直角坐标系只是原点平移关系。

    根据天线建模,定位目标与锚点之间构成一个单输入多输出(Single-Input Multiple-Output, SIMO)链路。为表述方便,以单个正交频分复用(Orthogonal Frequency Division Multiplexing, OFDM)链路的单次传输为例,在接收端子阵列μ上切除循环前缀后的信号为(λ子阵列的结构与之相同)

    y(m)μ=sh(m)μ+w
    (1)

    其中,y(m)μ表示第m个天线上的接收信号,s为发送的时域导频(即用于定位的特定格式的探测参考确知信号),w为加性高斯白噪声,表示圆周卷积。h(m)μ可以展开写成

    h(m)μ[n]=Npl=1αlexp(jπ(m1)sinθlμ)δ[nτsynl]
    (2)

    其中,αl为多径信道的第l径的复增益,θlμ表示μ子阵列上第l径的AOA, Np表示多径总数。τsynl=τpropl+τe是第l径的复合时延,由传播时延τpropl和同步误差τe构成。令OFDM子载波总数为Nsc, F为傅里叶变换矩阵,则频域接收信号

    Y(m)μ=Fy(m)μ=diag{S}H(m)μ+WH(m)μ[k]=Nl=1αlexp(jπ(m1)sinθlμ)exp(j2πkτsynlNsc)}
    (3)

    其中,Y(m)μμ子阵列第m个天线上的频域接收信号,diag{}表示由向量生成的对角矩阵,H(m)μ[k]μ子阵列第m个天线对应链路的频域信道响应,W为转到频域的加性高斯白噪声。令Yμ=[Y(1)μ  Y(2)μ  ···  Y(M)μ],则μ子阵列上的接收信号聚合为Nsc×M维的矩阵Yμ。由于μλ子阵列的接收信号在后续的AOA估计算法当中是独立作为输入的并且是独立处理的,为了表述方便将在接下来章节的表述中去掉脚标μλ

    在一般的定位系统中,定位信息的承载者是设计好的现有信号,即定位导频。而定位的几何结构由锚点与定位目标之间的空间关系决定。定位参数信息则蕴含在导频所经历的信道当中,例如信道的传播时延(TOA)或由到达角引起阵列间相位差(AOA)等等。通过特定的接收端算法对信号中的定位参量信息进行估计,再根据几何结构进行位置的联合解算,这是定位系统的一般架构,如图2所示。

    图 2  定位系统的一般架构

    图2可知,若要对高分辨率定位系统进行仿真,必须首先保证实现高分辨率的信道仿真。同时,定位算法也可以拆分为参数估计部分与位置解算部分。因此本文也按照该结构来展开。在第3节将介绍基于频域变换的高分辨率信道仿真,作为时延定位参量在信道中引入的基础。而在第4节中,基于首到达径检测的AOA估计算法以及基于AOA信息的位置估计方法构成整个定位方案。

    在前面的论述中,最基本的高分辨率信道仿真方法是过采样。而本文中将要提出的高分辨率信道仿真方法也源自于对过采样的频域等效,将时域过采样过程转换为频域处理。此时信道实现为基带信号与等效基带信道响应的直接作用(频域乘积或时域卷积),从而避开了复杂的升降采样和滤波操作,减少了对过采样信号中冗余信息的处理,使得信道实现在基带采样率下完成。具体方法分为如下3个步骤。

    设TDL信道的统计特性为广义平稳非相关散射(Wide Sense Stationary Uncorrelated Scattering, WSSUS)[13],且信道中同时存在时选衰落和频选衰落[14]。抽头时延t=[t0t1 ··· tL1],抽头平均功率P=[P0P1 ··· PL1],基带采样率fs以及最大多普勒频移fmax由TDL模型[5]提供,作为系统的输入。根据信道的WSSUS特性,其时域和频域的衰落特性可以分开先后实现[15]。信道系数是关于时间的函数,a[nTn]=a[n]表示对应第n个输入样值xn的信道响应。将所有N个发送采样对应的a[n]合并可以得到维度为N×L的2维信道系数矩阵A=[a[0]a[1] ··· a[N1]]T,其中L为信道记忆长度。而每一个A可以通过文献[15]中的正弦和方法得到。注意到此处的A相当于前面分析当中的h[n],因此抽头时延可以通过对A的每一列进行线性变换来引入。

    根据基带采样率得到小数时延d=t/Ts=[d0d1···dl1],而对小数时延进行公分母化可以得到每个采样的整数位置pn以及过采样系数q,即dn=pn/q。但此时最小公倍数法得到的q很容易变得过大,甚至超出某些处理器的位宽。根据sinc函数的特性,越靠近采样主值位置的值也越接近主值。因此可以先选择一个合理的q值,对小数时延进行如下的近似操作

    d=qtTs/Ts
    (4)

    其中<>操作表示四舍五入,近似调整后的d是对t在过采样倍率q之下的近似结果。

    接下来需要确定频域的截断窗长度为W=dL1,也就是最大小数时延的上取整。通过设置截断窗为

    w=[01···W12qLW12···qL1]
    (5)

    本文可以将低通滤波的限带特性引入,同时降低变换矩阵的维度。为了避免在ω=π出现频域混叠,需要将截断窗长W调整为奇数,否则频域等效关系无法得到保证。这个问题可以通过对信道响应填零调整dL1的值来得到解决。线性变换矩阵的每一个元素可以写成

    ˜Fk,l={exp(j2πwkdl)}
    (6)

    其中,˜Fk,lW×L维的变换矩阵˜F的第k行第l列的元素,wkdl分别为wd的第k个和第l个元素。

    对应第n个输入样值xn的信道响应a[n]的等效频域响应可以通过如下线性变换得到

    heq[n]=~Fa[n]
    (7)

    对该等效频域响应进行IDFT可以得到等效时域响应

    ˆheq[n]=F1{heq[n]}
    (8)

    而这里的F1{}操作可以直接用快速傅里叶逆变换(Inverse Fast Fourier Transform, IFFT)算法进行。重复上述式(7)和式(8),可以得到所有采样xn对应的时域等效信道响应。将所有的信道响应聚合为等效信道矩阵H=[ˆheq[1] ˆheq[2] ··· ˆheq[N1]]

    有以下几点结论值得注意。首先,H是通过对A进行频域变换得到的采样率适配的低通等效信道响应。再者,频域等效方法可以有效降低复杂度。在时域过采样方法中,若低通滤波器的符号扩展位数为Ls,则滤波器长度为qLs+1,其复杂度将会随着qLs的增长而急剧增长。过采样方法的复杂度为O(NLq2(Ls+1)2),即使采用FFT近似的方法实现卷积操作,其复杂度依然为O(Glg(G)),其中G=NLq(Ls+1)。而频域等效方法的复杂度则不取决于qLs,其线性变换矩阵˜F的尺度与q无关,且线性变换的复杂度为O(WL)。不考虑卷积,频域等效方法的复杂度是近似对数线性的,在O(NLlg(L))量级。可见频域等效方案在同等精度下有着巨大的复杂度优势。最后,虽然上述信号建模与推导均在SISO场景下完成,该方法也适用于非相干MIMO信道的精确时延实现,只需要逐链路采用该算法即可。因此该信道仿真方法可用来实现第2节定位场景中的SIMO信道,为下面的高分辨率定位技术仿真提供平台基础。

    观察式(3)可知,信道响应H(m)x当中包含了复合时延信息τsynl(τsyn1即为首到达径复合时延)以及角度信息θlx(θ1x为首径AOA)。将首到达径时延信息τsyn1补偿后可以认为H(m)x当中主要包含角度相位信息,随后通过错位共轭相乘即可解出H(m)x当中包含的关于角度的信息。根据上述思路,AOA估计算法可以分为3个部分:信道估计、时延补偿和角度估计。

    4.1.1   信道估计

    递归最小二乘(Recursive Least Squares, RLS)算法为信道估计的优选方案。RLS相比于最小均方误差(Least Mean Squares, LMS)算法的收敛速度更快,需要的采样数更少[16]。采用RLS的另一个好处是其对时变信道有一定的自适应能力,在室内低速移动的情况下可以较好地跟踪信道变化。RLS算法是迭代信道估计算法,需要多次传输定位导频信号。1次传输接收到的接收信号矩阵Y记为一个快照。由于链路之间不相关,RLS在同一组天线上的不同阵元之间是并行处理的,互相之间没有依赖关系,因此下面以单个阵元上处理流程为例。记第m个阵元的第u次传输快照为Y(m)u, Y(m)u[k]为该向量的第k个元素。假设总的快照数为Ut,那么RLS算法的总迭代次数即为Ut次。在第u次迭代当中,RLS算法依次执行以下4个步骤:

    (1) 计算误差:e(m)u[k]=Y(m)u[k]H(m)u1[k]S[k]

    (2) 计算卡尔曼增益向量:K(m)u[k]=P(m)u1[k]S[k]/(λ+P(m)u1[k]|S[k]|2)

    (3) 更新相关矩阵的逆矩阵:P(m)u[k]=1/λP(m)u1[k](1K(m)u[k]S[n])

    (4) 更新参数:H(m)u[k]=H(m)u1[k]+eu[k]K(m)u[k]

    随着u的步进,重复执行迭代过程,每次以新的快照作为输入,按照步骤逐次更新以上各项参数。最后一次迭代得到的H(m)Ut即为信道估计输出。算法启动时,对H(m)0[k]P(m)0进行初始化:H(m)0[k]=0, P(m)0=1/ddλ根据信道的时变性确定,是经验值。一般时变性弱时取d=0.01, λ=0.999。注意到每个阵元上的信道响应是独立计算的,因此对于每个接收天线最终都可以得到其信道估计值˜H(m)=H(m)Ut

    4.1.2   时延补偿

    在得到信道响应后,利用傅里叶变换的性质可以进行时延估计[17]

    ˆτsyn=argmaxτW1MMm=1|Nsc1k=0ˆH(m)|[k]exp(j2πkτNsc),W={τ0<τ<Lw,τZ+}
    (9)

    其中,Lw为搜索窗长度。时移补偿量exp(j2πkτ/Nsc)通过在频域补偿相移将首到达径向帧头移动。记相位补偿后的信道响应为˜H(m), H(m)[k]=ˆH(m)[k]exp(j2πkˆτsynNsc),则|Nsck=0˜H(m)[k]|=|˜h(m)[0]|。若首到达径为最强径,则式(9)寻找的是使补偿后0位置时域信道响应幅度最大的时延补偿值,即首到达径的混合时延估计值ˆτsyn

    ˆτsyn=τsyn1,则时延补偿后的首径信道响应为

    ˜h(m)[0]=Nscα1exp(jπ(m1)sinθ1x)+NscNpl=2αlexp(jπ(m1)sinθlx)+ξ(m)[n]
    (10)

    其中,ξ(m)为信道估计结果中带有的误差。可以观察到,在视距(Light-Of-Sight, LOS)传播条件下,|α1|远大于其他分量,此时可以认为˜h(m)[0]成功分离出了首到达径的信道响应。

    4.1.3   角度估计

    进一步地,对M个阵元上的首径信道响应进行共轭错位相乘

    ζ(m)=(Nsc1k=0˜H(m)[k])(Nsc1k=0˜H(m+1)[k])=N2sc|α1|exp(jπsinθ1)+(NscNpl=2αlexp(jπsinθl))2+η(m)
    (11)

    其中第1项当中的信道复增益α1已经通过共轭相乘变为实数幅值|α1|,而AOA信息蕴含在该项的复相位当中。η(m)ξ(m)与信道响应经过线性组合产生的综合噪声项,在LOS传播以及较高信噪比条件下,由于强度较弱,其对ζ(m)的相位产生的影响较小。将M1个共轭相乘结果ζ(m)合并,则AOA估计结果为

    ˆθ1=arcsin(1π(M1m=1ζ(m)))
    (12)

    其中,()表示对一个复数取角度。ˆθ1[π,π]之间的角度值,对应首径的AOA信息。

    分析式(10)和式(11)可知,加快照数Ut可以提升RLS算法的估计性能。因为当迭代次数增加时,由于其快收敛以及渐进无偏特性,误差ξ(m)将会逐渐降低,从而减小η(m)造成的相位影响。因此,适当增加Ut的值是一种有效提高角度估计精度的手段。而实际应用中Ut的取值需要在特定场景下仿真来确定。

    总结起来,基于首到达径检测的AOA估计算法可以分为以下几个步骤,如图3所示。

    图 3  基于首到达径检测的AOA估计算法流程

    该算法的每个环节都是线性操作,因此复杂度主要集中在通过快照迭代估计更新信道响应的过程,快照数增加虽然能一定程度上提高性能但是也会增加处理时延,信道响应的估计准确度反映在残余项ξ(m)当中,能直接影响AOA估计的准确程度。在实际应用中需要考虑到复杂度与性能的折中。

    在接收端通过上一小节的估计算法输出AOA信息后,将其转换到每个接收端的自有极坐标系可以得到定位角。对于锚点i,定位角为φi,与用户之间的距离为ri, AOA定位问题的几何示意图如图4所示。

    图 4  AOA定位问题的几何关系

    由此可以写出定位方程组

    p=pi+rivivi=[cosφi,sinφi]T}
    (13)

    其中,p=[x y]T为UE在公有直角坐标系当中的坐标,pi=[xi yi]T为第i个锚点在公有直角坐标系当中的坐标。对于每个锚点都有一个形如式(13)的方程组,将这些方程组联合起来改写成如式(14)的形式

    [x1sinφ1y1cosφ1xNBSsinφNBSyNBScosφNBS][sinφ1cosφ1sinφNBScosφNBS][x0y0]b(φ)ν(φ)}
    (14)

    其中,NBS为参与定位的锚点数目,φ=[φ1···φNBS]T。上面的矩阵展开式可以写成下面的变量方程形式,位置互相对应。式(14)可以通过最小二乘(Least-Squares, LS)方法解出[18]

    ˆp=(νT(φ)ν(φ))1νT(φ)b(φ)=ν(φ)pinvb(φ)
    (15)

    注意这里的ν(φ)pinvν(φ)的伪逆,其中

    det(νH(φ)ν(φ))=NBi=1NBj=i+1sin2(φiφj)
    (16)

    观察式(16)可知式(15)基本上不会出现无解的情况(除非φi=φj或者φi=φj+π,这些都可以通过简单的调度或检测机制避免),算法的鲁棒性可以得到保证。同时,由于式(15)是对所有角度的综合考虑,属于全局最小二乘(Total Least-Squares, TLS),相比于对每一个式(13)所示的方程进行LS解算后再估计的方法有更高的精度。并且,该方法得到的是闭式解,计算复杂度也较低。

    本节将给出高分辨率无线信道频域仿真方法和定位技术分别在实际参数信道模型和标准场景当中的数值仿真性能。根据前面的系统设计,高分辨率信道仿真也将作为信道实现模块应用在定位系统的场景仿真当中。

    根据前述推导,时域过采样方法是高精度信道仿真的对比方案,拥有最优的理论性能和最高的实现复杂度。而频域等效方法是不妥协精度的低复杂度实现方案。复杂度分析的部分在3.3节已经给出,而本节选取3GPP TS38.901[19]给出的SISO TDL-D信道模型仿真其实际性能,以频域等效方法与过采样方法分别产生的信道响应的均方误差作为性能指标。设定基带采样率为122.88 MHz,时延扩展因子为20 ns,归一化最大多普勒频移为0.001,多普勒频移特性为Jakes谱。同时过采样倍率设定为恰好能够将最接近的两径分量分辨开来的q=32

    在衰落信道下测试仿真方案的方法是考察其对信道统计特性的模拟能力,时选衰落体现为功率延时特性,而频选衰落体现为多普勒功率谱。在图5(a)当中可以观察到,频域等效和时域过采样方法产生的功率延时特性差别很小,且二者产生的等效信道响应的均方误差为2.17×103。频域方法的离散演示谱经过sinc插值后与信道的原始抽头平均功率参数吻合。图5(b)说明该方案也能以较高的精度来模拟信道的时选衰落。上述结果充分说明频域等效方案能够在根据TDL信道模型产生具有双选特性的信道响应时取得与过采样方案非常接近的性能表现,达到了高分辨率的要求。

    图 5  信道时频域统计特性仿真

    定位算法仿真按照2.2节的框架进行。首先根据3GPP TS38.901 Indoor-Office场景构建一个120m×50m大小、含有12个定位锚点的室内空间[19]。同时设定场景中的同步误差服从方差为σTe=50ns的截短高斯分布,其截断位置为[2σTe,2σTe],具体参见3GPP TS38.855[20]。接着生成上行发送的SRS信号,SRS信号的产生与资源映射方式参照TS 38.211[21]。然后运行高分辨率信道仿真算法,为每条定位链路生成等效SIMO信道响应。锚点接收到信号后,定位中心先根据各锚点接收信号功率进行锚点优选(留下最高质量的3个锚点),再执行高分辨率定位算法,最后得出定位结果。

    图6中共有3种方案参与对比,分别是基于AOA的高分辨率定位算法“AOA”、基于TOA信息采用匹配滤波器(Matched Filter,MF)进行TOA检测的定位算法“MF”以及华为在文献[22]中提出的基于TDOA的定位方案“HW”。“同步”和“非同步”分别表示测试场景中是否加入按照前述方式建模的同步误差。结果表明,AOA定位的效果能够显著对抗同步误差,并且取得比完美同步下基于TOA和TDOA的算法更好的性能,50%概率定位误差小于20 cm。虽然AOA算法在90%以上的概率收敛性由于阵列对极端入射角的象限判断会出现模糊导致大误差而比MF差,但是总体来说在90%性能线以前都能达到比理想下的MF算法更高的精度(极端角度的点只分布在特殊位置,只占整个场景面积的一小部分)。

    图 6  定位误差经验累积概率函数

    本文的主要工作有两部分:高分辨率的信道仿真以及高分辨率的位置估计算法。信道仿真将时域过采样处理转换为频域处理,能以低复杂度实现高时延分辨率的参数信道,从而为6G信道的数值仿真和针对这些场景的各项新算法的测试提供了基础。更进一步地,本文将基于首到达径检测的AOA估计与基于AOA信息的TLS位置估计算法结合起来,实现了高精度的位置估计,同时为存在同步误差的6G分布式网络当中的高分辨率定位提供了解决方案。并且该定位方案的导频采用与普通空口信号一致的信号格式,有助于导频的多用化,符合6G深度融合网络的设计目标。

  • 图  1  应急疏散环境模型

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

    图  3  Dijkstra算法仿真结果

    图  4  ACO算法仿真结果

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

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

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

    表  1  4种算法仿真结果

    DijkstraACODijkstra-ACO混合算法Dijkstra-GA混合算法
    运行时间(s)0.23719.8041.1755.134
    最短路径(m)41.681336.384833.804335.9051
    下载: 导出CSV
  • 十一届全国人大常委会第二十一次会议举行第二次全体会议听取关于消防工作情况的报告[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
  • 加载中
图(7) / 表(1)
计量
  • 文章访问数:  3842
  • HTML全文浏览量:  1703
  • PDF下载量:  161
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-11-01
  • 修回日期:  2020-05-08
  • 网络出版日期:  2020-05-17
  • 刊出日期:  2020-06-22

目录

/

返回文章
返回