第16卷第1期 智能系统学报 Vol.16 No.1 2021年1月 CAAI Transactions on Intelligent Systems Jan.2021 D0:10.11992tis.201912012 一种非视距环境下的目标定位算法 齐小刚2，张海洋'，魏倩 (1.西安电子科技大学数学与统计学院，陕西西安710071；2.西安电子科技大学宁波信息技术研究院，浙江 宁波315200) 摘要：针对机器人、无人机和其他智能系统的位置信息，研究了非视距(non line of sight,.NLOS)环境中基于到 达时间(time of arrival,TOA)测距的目标定位问题。在建模过程中，通过引入平衡参数来抑制NLOS误差对定位 精度的影响，并成功将定位问题的形式与一个广义信赖域子问题(generalized trust region subproblem,GTRS)框架 进行耦合。与其他凸优化算法不同的是，本文没有联合估计目标节点的位置和平衡参数，而是采用了一种迭代 求精的思想，算法可以用二分法高速有效地进行求解。所提算法与已有的算法相比，不需要任何关于NLOS 路径的信息。此外，与大多数现有算法不同，所提算法的计算复杂度低，能够满足实时定位的需求。仿真结果 表明：该算法具有稳定的NLOS误差抑制能力，在定位性能和算法复杂度之间有着很好的权衡。 关键词：目标定位：非视距：到达时间：平衡参数：二分法：广义信赖域子问题；凸优化：误差抑制 中图分类号：TP393文献标志码：A文章编号：1673-4785(2021)01-0075-06 中文引用格式：齐小刚，张海洋，魏倩.一种非视距环境下的目标定位算法.智能系统学报，2021,16(1)：75-80. 英文引用格式：QI Xiaogang,ZHANG Haiyang,VEI Qian.A target localization algorithm in NLOS environments Jl..CAAI trans- actions on intelligent systems,2021,16(1):75-80. A target localization algorithm in NLOS environments QI Xiaogang,ZHANG Haiyang',WEI Qian' (1.School of Mathematics and Statistics,Xi'dian University,Xi'an 710071,China;2.Ningbo Information Technology Institute,Xi' dian University,Ningbo 315200,China) Abstract:The location information of robots,UAVs,and other intelligent systems is crucial.This paper mainly studies the target location problem based on TOA ranging in the non-line-of-sight (NLOS)environment.In the process of mod- eling,the influence of NLOS error on positioning precision is restrained,and the form of the localization problem is coupled with a generalized trust-region subproblem (GTRS)framework.Instead of joint estimation of the location and balance parameter of the object nodes,an iterative refinement idea is adopted,and the algorithm can be solved quickly and effectively by dichotomy.In contrast to existing algorithms,the proposed algorithm does not need information about the NLOS path.In addition,unlike most existing algorithms,the proposed algorithm has a low computational complex- ity and can meet the need of real-time localization.The simulation results show that the proposed algorithm has stable NLOS error mitigation capability and a good balance between localization performance and algorithm complexity. Keywords:target localization:non-line-of-sight (NLOS):time-of-arrival (TOA):balance parameters:bisection:general- ized trust region sub-problem (GTRS);convex optimization;error mitigate capability 机器人、无人机和其他智能系统山无法在建 系统获得准确的位置信息，所以研究室内目标定 筑物、地下商场和其他室内环境中利用全球导航 位变得更加重要。近年来各种基于测距的智能 体（机器人等）定位技术已经被提出，根据不同的 收稿日期：2019-12-10. 定位参数，可以分为基于接受信号强度(receive 基金项目：国家自然科学基金项目(61877067,61572435)：教育 部一中国移动联合基金项目(MCM20I70103):西安 signal strength,RSS)、基于到达时间差(time differ- 市科技创新项日(201805029YD7CG13-6):宁波市自 然科学基金项目(2016A610035,2017A610119). ence of arrival,TDOA)、基于到达角度(angle of 通信作者：张海洋.E-mail:1617978744@qq.com. angle,AOA)、基于到达时间(time of arrival
DOI: 10.11992/tis.201912012 一种非视距环境下的目标定位算法 齐小刚1,2，张海洋1 ，魏倩1 （1. 西安电子科技大学 数学与统计学院，陕西 西安 710071; 2. 西安电子科技大学 宁波信息技术研究院，浙江 宁波 315200） 摘 要：针对机器人、无人机和其他智能系统的位置信息，研究了非视距 (non line of sight, NLOS) 环境中基于到 达时间 (time of arrival,TOA) 测距的目标定位问题。在建模过程中，通过引入平衡参数来抑制 NLOS 误差对定位 精度的影响，并成功将定位问题的形式与一个广义信赖域子问题 (generalized trust region subproblem,GTRS) 框架 进行耦合。与其他凸优化算法不同的是，本文没有联合估计目标节点的位置和平衡参数，而是采用了一种迭代 求精的思想，算法可以用二分法高速有效地进行求解。 所提算法与已有的算法相比，不需要任何关于 NLOS 路径的信息。此外，与大多数现有算法不同，所提算法的计算复杂度低，能够满足实时定位的需求。仿真结果 表明：该算法具有稳定的 NLOS 误差抑制能力，在定位性能和算法复杂度之间有着很好的权衡。 关键词：目标定位；非视距；到达时间；平衡参数；二分法；广义信赖域子问题；凸优化；误差抑制 中图分类号：TP393 文献标志码：A 文章编号：1673−4785(2021)01−0075−06 中文引用格式：齐小刚, 张海洋, 魏倩. 一种非视距环境下的目标定位算法 [J]. 智能系统学报, 2021, 16(1): 75–80. 英文引用格式：QI Xiaogang, ZHANG Haiyang, WEI Qian. A target localization algorithm in NLOS environments[J]. CAAI transactions on intelligent systems, 2021, 16(1): 75–80. A target localization algorithm in NLOS environments QI Xiaogang1,2 ，ZHANG Haiyang1 ，WEI Qian1 (1. School of Mathematics and Statistics, Xi’dian University, Xi’an 710071, China; 2. Ningbo Information Technology Institute, Xi’ dian University, Ningbo 315200, China) Abstract: The location information of robots, UAVs, and other intelligent systems is crucial. This paper mainly studies the target location problem based on TOA ranging in the non-line-of-sight (NLOS) environment. In the process of modeling, the influence of NLOS error on positioning precision is restrained, and the form of the localization problem is coupled with a generalized trust-region subproblem (GTRS) framework. Instead of joint estimation of the location and balance parameter of the object nodes, an iterative refinement idea is adopted, and the algorithm can be solved quickly and effectively by dichotomy. In contrast to existing algorithms, the proposed algorithm does not need information about the NLOS path. In addition, unlike most existing algorithms, the proposed algorithm has a low computational complexity and can meet the need of real-time localization. The simulation results show that the proposed algorithm has stable NLOS error mitigation capability and a good balance between localization performance and algorithm complexity. Keywords: target localization; non-line-of-sight (NLOS); time-of-arrival (TOA); balance parameters; bisection; generalized trust region sub-problem (GTRS); convex optimization; error mitigate capability 机器人、无人机和其他智能系统[1] 无法在建 筑物、地下商场和其他室内环境中利用全球导航 系统获得准确的位置信息，所以研究室内目标定 位变得更加重要。 近年来各种基于测距的智能 体 (机器人等) 定位技术已经被提出，根据不同的 定位参数，可以分为基于接受信号强度 (receive signal strength，RSS)、基于到达时间差 (time difference of arrival，TDOA)、基于到达角度 (angle of angle， AOA)、基于到达时间 (time of arrival， 收稿日期：2019−12−10. 基金项目：国家自然科学基金项目 (61877067，61572435)；教育 部—中国移动联合基金项目 (MCM20170103)；西安 市科技创新项目 (201805029YD7CG13-6)；宁波市自 然科学基金项目 (2016A610035，2017A610119). 通信作者：张海洋. E-mail：1617978744@qq.com. 第 16 卷第 1 期 智 能 系 统 学 报 Vol.16 No.1 2021 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2021
·76· 智能系统学报 第16卷 TOA)以及混合参数等。其中，基于TOA测距的 化的方法显著提高了NLOS环境下的定位精度， 定位算法由于测量精度高和抗干扰性能好等优点 但是这些算法的复杂度高，一是对传感器的内 被广泛应用于室内定位系统。本文主要研究非视 存、CPU要求高，二是难以满足实时定位的需求， 距(non line of sight,.NLOS)环境下的TOA定位。 基于此，本文研究了一种低复杂度的NLOS环境 目前大部分算法在视距(line of sight,.LOS)条件下 下的定位算法。 得到了很好的估计值，但是在含有NLOS的环境 中，由于NLOS误差一般远大于节点间的测量噪 1无线电定位系统模型 声，传统算法的定位性能大大降低。另一个原 在智能体构成的局域网中，假设有N个锚节 因是在恶劣环境中，目标节点和传感器之间的 点和一个未知位置的目标节点，定位就是用N个 LOS信号难以提供足够的信息，不得不求助NLOS 锚节点的位置去估计目标节点的位置。假设锚节 信号。因此，抑制NLOS误差成为一项紧迫的 点的位置坐标为a(i=1,2,…,W),目标节点的位置 任务，解决这个问题最简单的办法是识别出 坐标为x,目标节点和锚节点之间的路径有视距 NLOS路径，然后丢掉NLOS测量，用LOS测量定 (LOS)和非视距NLOS)2种，第i个锚节点到目标 位源位置4。然而这种办法有2个缺点：1)如果 节点之间的距离基于TOA模型可以建模为21] LOS测量数量在二维空间小于3，三维空间小于 di =lx-aill+ei+ni (1) 4,则无法定位目标节点的位置；2)目前的技术下 NLOS识别的成功率还不能达到100%，存在一定 式中：i∈1,2，…，W;n表示测量噪声，大量文献中 的虚警和漏警，这会大大地降低定位的性能。 均假设测量噪声服从方差为2的Gaussian零均 近年来，基于凸优化的方法得到了广泛的应 值分布，即，n,~N0,);e,(i=1,2,…,W表示 用。Yang等通过利用二次规划(quadratic pro- NLOS误差，由于NLOS误差e:的产生是由于锚 gramming,QP)方法，提出了一种凸优化定位算 节点和目标节点之间的障碍物造成的，所以在文 法，该算法能较好地抑制NLOS误差，并且不需要 献中均假设NLOS误差e,非负，即e≥0，并且认 知道任何NLOS误差分布以及识别NLOS信号， 为NLOS误差e:远大于测量噪声n,即e:>m。 文献[7]提出了一种NLOS环境下RSS和 如果NLOS状态已知，式(1)可以变形为 TDOA联合的信源被动定位方法，通过建立加权 d= llx-all+e;+ni,NLOS 最小二乘模型来抑制NLOS误差对定位精度的影 llx-aill+ni,LOS (2) 响，最终的目标节点位置通过二分法迭代得到。 在一些文献中，建模过程中假设NLOS误差 Yu等]提出了一种基于非直瞄状态信息的优化 e:为一些确定的分布，如均匀分布、指数分布、 问题，并利用序列二次规划算法解决了问题。 高斯分布等，或者需要对NLOS误差e加人一个 Lui等例提出了一种最大后验(maximum a posteri- 约束，如NLOS误差的上界已知等。本文所提 oi,MAP)方法，该方法假定知道关于NLOS状态 的方法不需要知道NLOS误差e:的任何信息，适 的概率和NLOS误差的准确分布的先验信息。王刚等 用于所有的分布，也不需要知道NLOS误差e的 通过联合估计目标节点的位置和一个平衡参数， 上界等。 用于部分减轻NLOS误差的影响，将估计问题放 宽为二阶锥规划(second order cone programming,. 2NLOS误差抑制的无线电定位算法 SOCp)和半定规划(semidefinite programming, 在NLOS状态未知的情形下，来考虑目标节 SDP),但是该方法需要知道NLOS误差的上界。 点的定位。首先，通过对式(1)进行移项和平方 Tome等1o在王刚等的基础上，将估计问题表述 恒等变形，得到： 为一个广义信赖域子问题(generalized trust region subproblem,GTRS),并以全局最优的方式加以解 (di-e)2=lix-al+2nllix-aill+n (3) 决，算法计算复杂度逼近于线性。Chen等 对式(3)进行变形，得： 针对基于估计的方法在测量精确的稀疏NLOS环 境中性能更好，当NLOS误差的上界是紧的时候， d--k-a=%+2-a 2lx-al (4) 鲁棒方法在稠密的NLOS环境中表现得更好的问 由于测量噪声都比较小，所以可以忽略二 题，通过引入平衡参数，将问题建模为一个鲁棒 阶测量噪声，这样，由式(4)可以得到： 加权最小二乘问题，并利用凸松弛技术将原问题 (d;-e 2-lIx-al (5) 近似为一个SDP问题求解。目前，虽然基于凸优 2x-aill
TOA) 以及混合参数等。其中，基于 TOA 测距的 定位算法由于测量精度高和抗干扰性能好等优点 被广泛应用于室内定位系统。本文主要研究非视 距 (non line of sight，NLOS) 环境下的 TOA 定位。 目前大部分算法在视距 (line of sight，LOS) 条件下 得到了很好的估计值，但是在含有 NLOS 的环境 中，由于 NLOS 误差一般远大于节点间的测量噪 声，传统算法的定位性能大大降低[2]。另一个原 因是在恶劣环境中，目标节点和传感器之间的 LOS 信号难以提供足够的信息，不得不求助 NLOS 信号[3]。因此，抑制 NLOS 误差成为一项紧迫的 任务，解决这个问题最简单的办法是识别 出 NLOS 路径，然后丢掉 NLOS 测量，用 LOS 测量定 位源位置[4-5]。然而这种办法有 2 个缺点：1) 如果 LOS 测量数量在二维空间小于 3，三维空间小于 4，则无法定位目标节点的位置；2) 目前的技术下 NLOS 识别的成功率还不能达到 100%，存在一定 的虚警和漏警，这会大大地降低定位的性能[2]。 近年来，基于凸优化的方法得到了广泛的应 用。Yang 等 [6] 通过利用二次规划 (quadratic programming，QP) 方法，提出了一种凸优化定位算 法，该算法能较好地抑制 NLOS 误差，并且不需要 知道任何 NLOS 误差分布以及识别 NLOS 信号。 文 献 [ 7 ] 提出了一 种 NLO S 环 境 下 R S S 和 TDOA 联合的信源被动定位方法，通过建立加权 最小二乘模型来抑制 NLOS 误差对定位精度的影 响，最终的目标节点位置通过二分法迭代得到。 Yu 等 [8] 提出了一种基于非直瞄状态信息的优化 问题，并利用序列二次规划算法解决了问题。 Lui 等 [9] 提出了一种最大后验 (maximum a posteriori，MAP) 方法，该方法假定知道关于 NLOS 状态 的概率和NLOS误差的准确分布的先验信息。王刚等[2] 通过联合估计目标节点的位置和一个平衡参数， 用于部分减轻 NLOS 误差的影响，将估计问题放 宽为二阶锥规划 (second order cone programming， SOCP) 和半定规划 (semidefinite programming， SDP)，但是该方法需要知道 NLOS 误差的上界。 Tome 等 [10] 在王刚等的基础上，将估计问题表述 为一个广义信赖域子问题 (generalized trust region subproblem，GTRS)，并以全局最优的方式加以解 决，算法计算复杂度逼近于线性。 Chen 等 [ 1 1 ] 针对基于估计的方法在测量精确的稀疏 NLOS 环 境中性能更好，当 NLOS 误差的上界是紧的时候， 鲁棒方法在稠密的 NLOS 环境中表现得更好的问 题，通过引入平衡参数，将问题建模为一个鲁棒 加权最小二乘问题，并利用凸松弛技术将原问题 近似为一个 SDP 问题求解。 目前，虽然基于凸优 化的方法显著提高了 NLOS 环境下的定位精度， 但是这些算法的复杂度高，一是对传感器的内 存、CPU 要求高，二是难以满足实时定位的需求， 基于此，本文研究了一种低复杂度的 NLOS 环境 下的定位算法。 1 无线电定位系统模型 N N ai(i = 1,2,··· ,N) x i 在智能体构成的局域网中，假设有 个锚节 点和一个未知位置的目标节点，定位就是用 个 锚节点的位置去估计目标节点的位置。假设锚节 点的位置坐标为 ，目标节点的位置 坐标为 ，目标节点和锚节点之间的路径有视距 (LOS) 和非视距 (NLOS)2 种，第 个锚节点到目标 节点之间的距离基于 TOA 模型可以建模为[12-13] di = ∥x−ai∥+ei +ni (1) i ∈ 1,2,··· ,N ni δ 2 ni ∼ N(0,δ2 ) ei(i = 1,2,··· ,N) ei ei ei ⩾ 0 ei ni ei >> ni 式中： ； 表示测量噪声，大量文献中 均假设测量噪声服从方差为 的 Gaussian 零均 值分布，即， ； 表 示 NLOS 误差，由于 NLOS 误差 的产生是由于锚 节点和目标节点之间的障碍物造成的，所以在文 献中均假设 NLOS 误差 非负，即 ，并且认 为 NLOS 误差 远大于测量噪声 ，即 。 如果 NLOS 状态已知，式 (1) 可以变形为 di = { ∥x−ai∥+ei +ni , NLOS ∥x−ai∥+ni , LOS (2) ei ei ei ei 在一些文献中，建模过程中假设 NLOS 误差 为一些确定的分布，如均匀分布、指数分布、 高斯分布等，或者需要对 NLOS 误差 加入一个 约束，如 NLOS 误差的上界已知等。 本文所提 的方法不需要知道 NLOS 误差 的任何信息，适 用于所有的分布，也不需要知道 NLOS误差 的 上界等。 2 NLOS 误差抑制的无线电定位算法 在 NLOS 状态未知的情形下，来考虑目标节 点的定位。首先，通过对式 (1) 进行移项和平方 恒等变形，得到： (di −ei) 2 = ∥x−ai∥ 2 +2ni∥x−ai∥+n 2 i (3) 对式 (3) 进行变形，得： (di −ei) 2 −∥x−ai∥ 2 2∥x−ai∥ = ni + n 2 i 2∥x−ai∥ (4) ni n 2 i 由于测量噪声 都比较小，所以可以忽略二 阶测量噪声 ，这样，由式 (4) 可以得到： (di −ei) 2 −∥x−ai∥ 2 2∥x−ai∥ ≈ ni (5) ·76· 智 能 系 统 学 报 第 16 卷
第1期 齐小刚，等：一种非视距环境下的目标定位算法 ·77· 由式(5)可以得到极大似然估计的概率密度 函数为 )-(2-QFiexpjs (6) 式中：s= (di-e1)'-lix-al (d2-e2)2-llx-a2P (dy-ex)2-llx-axll 2lx-aill 2lx-azll 2llx-anll Q=diag6…J)o 关于x最大化式(6)，得到： 到此为止，建模过程便完成了，但是有2个问 argminaF 题需要解决，一是如何求解平衡参数e的估计值 (7) 2lx-aill e,二是怎么求解该模型。下面便正式提出改进的 通过研究发现，式(7)是一个高度非凸的表达 算法，解决上述2个问题。 式，因为其分子和分母均是x的函数，本文没有 式(12)的模型是一个GTRS问题，可以使用 解决式(7，而是解决了其一个近似问题： 二分法进行求解，对于平衡参数，首先假设平衡 金=aemn/4-6r-k-a 参数的估计值的初始值等于0，即不含有任何 (8) 2di NLOS测量值，这样便能求出目标节点的一个初 式(8)可以转化为一个约束最优化问题： 始值xo,然后计算平衡参数的方式为 minimize ((di-e)2-llx-aP 之d-l-aD 2d, (9) e1≈ (13) S.t. e:≥0，i=1,2,…,N N 为了求解式(9)，引入平衡参数e,用平衡参数 这样利用平衡参数的估计值e,便能计算出源 e代替式(9)中的NLOS误差eo由于平衡参数e 节点的位置x,同理可以计算出第m次平衡参数 可以看成是NLOS误差的均值，这样的优点是只 的估计值em与源节点的位置xm。算法1中总结 需估计一个平衡参数e。与文献[10]不同的是本 了提出的定位方法。 文并没有联合估计目标节点的位置x以及平衡参 算法1 数e,仅仅通过已有的SR-Ls算法进行了建模， 输入a(i=1,2,…,,d,m 求解得到了平衡参数e的估计值e,这样会降低 输出源节点的位置m。 算法的复杂度，仿真结果表明，这样有助于提高 初始化t=1,e=0 定位的性能。 while t≤m 这样(9)式可以通过已有的方法求解，通过 1)计算区间： 式(9)可以得到： minimize (di-2)2-lix-al (10) ((uATuA)D(uATUA) 2d, 式中mx代表最大的特征值。 把式(10)转化为一个约束最小化问题： 2)用二分法在区间1计算函数()的零点 minimize (d;-2)-lix-a s.t.=B (11) 心。其中： 2d ()=)'D()+2f) 式(10)转化为式(11)是直接的，本文的目的 (A)=(uA"uA+AD)(uAub-af) 是把原问题转化为一个广义信赖域的子问题 3)计算)的值，源节点的位置等于向量 (GTRS),这样便可以利用二分法求解该问题。把 d)的前2个分量。 式(11)用向量的形式表示为 t=t+1 minimize (l(Ayb))s.t.yDy+2fy=0 (12) 4)计算平衡参数的估计值e,: 式中：y=(xr,β；D=diag110]): llal2-(d-2)2 2a 之d-x--aD llazll-(d2-2) b= A= llawll2-(dy-2)2 2a-1 if <0 e=0 end end
由式 (5) 可以得到极大似然估计的概率密度 函数为 p(ς) = (2π) − N 2 |Q| − 1 2 exp( − 1 2 ς TQ −1 ς ) (6) ς = [ (d1 −e1) 2 −∥x− a1∥ 2 2∥x− a1∥ (d2 −e2) 2 −∥x− a2∥ 2 2∥x− a2∥ ··· (dN −eN) 2 −∥x− aN∥ 2 2∥x− aN∥ ] Q = diag([δ 2 1 δ 2 2 ··· δ 2 N 式中： ； ])。 关于 x 最大化式 (6)，得到： xˆ = argmin x ∑N i=1 ( (di −ei) 2 −∥x− ai∥ 2 2∥x− ai∥ )2 (7) x 通过研究发现，式 (7) 是一个高度非凸的表达 式，因为其分子和分母均是 的函数，本文没有 解决式 (7)，而是解决了其一个近似问题： xˆ = argmin x ∑N i=1 ( (di −ei) 2 −∥x− ai∥ 2 2di )2 (8) 式 (8) 可以转化为一个约束最优化问题： minimize x ∑N i=1 ( (di −ei) 2 −∥x− ai∥ 2 2di )2 s.t. ei ⩾ 0, i = 1,2,··· ,N (9) e e ei e e x e e eˆ 为了求解式 (9)，引入平衡参数 ，用平衡参数 代替式 (9) 中的 NLOS 误差 。由于平衡参数 可以看成是 NLOS 误差的均值，这样的优点是只 需估计一个平衡参数 。与文献 [10] 不同的是本 文并没有联合估计目标节点的位置 以及平衡参 数 ，仅仅通过已有的 SR-LS[12] 算法进行了建模， 求解得到了平衡参数 的估计值 ，这样会降低 算法的复杂度，仿真结果表明，这样有助于提高 定位的性能。 这样 (9) 式可以通过已有的方法求解，通过 式 (9) 可以得到： minimize x ∑N i=1 ( (di −eˆ) 2 −∥x− ai∥ 2 2di )2 (10) 把式 (10) 转化为一个约束最小化问题： minimize x,β ∑N i=1 ( (di −eˆ) 2 −∥x− ai∥ 2 2di )2 s.t. ∥x∥ 2 = β (11) 式 (10) 转化为式 (11) 是直接的，本文的目的 是把原问题转化为一个广义信赖域的子问题 (GTRS)，这样便可以利用二分法求解该问题。 把 式 (11) 用向量的形式表示为 minimize y (∥u(Ay− b)∥ 2 ) s.t. y T Dy+2 f T y = 0 (12) y = (x T ,β) T 式中： ； D = diag([1 1 0]) ； b = ∥a1∥ 2 −(d1 −eˆ) 2 ∥a2∥ 2 −(d2 −eˆ) 2 . . . ∥aN∥ 2 −(dN −eˆ) 2 ; A = 2a T 1 −1 2a T 2 −1 . . . . . . 2a T N −1 f = 0 − 1 2 ; u = diag([ 1 2d1 , 1 2d2 ,··· , 1 2dN ]) e eˆ 到此为止，建模过程便完成了，但是有 2 个问 题需要解决，一是如何求解平衡参数 的估计值 ，二是怎么求解该模型。下面便正式提出改进的 算法，解决上述 2 个问题。 eˆ0 x0 式 (12) 的模型是一个 GTRS 问题，可以使用 二分法进行求解，对于平衡参数，首先假设平衡 参数的估计值 的初始值等于 0，即不含有任何 NLOS 测量值，这样便能求出目标节点的一个初 始值 ，然后计算平衡参数的方式为 eˆ1 ≈ ∑N i=1 (di −∥x0 − ai∥) N (13) eˆ1 x1 m eˆm xm 这样利用平衡参数的估计值 便能计算出源 节点的位置 ，同理可以计算出第 次平衡参数 的估计值 与源节点的位置 。 算法 1 中总结 了提出的定位方法。 算法 1 输入 ai(i = 1,2,··· ,N)，d，m。 输出 源节点的位置 xˆm。 初始化 t = 1，eˆ1 = 0 while t ⩽ m 1) 计算区间 I ： I = − 1 λmax ( (uATuA) − 1 2 D(uATuA) − 1 2 ),∞ 式中 λmax(·) 代表最大的特征值。 I ψ(λ) λt 2) 用二分法在区间 计算函数 的零点 。其中： ψ(λ) = yˆ(λ) T Dyˆ(λ)+2 f T yˆ(λ) yˆ(λ) = (uATuA+λD) −1 (uATub−λ f) yˆ(λt) xˆt yˆ(λt) 3) 计算 的值，源节点的位置 等于向量 的前 2 个分量。 t = t+1 4) 计算平衡参数的估计值 eˆt： eˆt ≈ ∑N i=1 (di −∥xt−1 − ai∥) N if eˆt < 0 eˆt= 0 end end 第 1 期 齐小刚，等：一种非视距环境下的目标定位算法 ·77·
78 智能系统学报 第16卷 3 算法的复杂度分析 点位置。在本文的仿真中，设置M=5000。假设 节点间的测量噪声n,服从Gaussian零均值分布， 本节主要给出一些现有算法的复杂度以及本 即m;~N(O,)。节点间的NLOS误差e在这里假 文所提算法的复杂度，参考文献[10-11]中已有的 设服从均匀分布，即U(O,Bax)o 结果，表1给出了所有算法最坏结果下的计算复 为了验证所提算法的性能，主要从以下3个 杂度分析。可以看出，所有方法的计算复杂度主 方面进行仿真：1)NLOS测量的数量比较少的情 要取决于网络的规模，即锚的数量。 形：2)NLOS测量的数量比较多的情形；3)算法的 表1算法的计算复杂度 计算复杂度验证。 Table 1 The computational complexity of the algorithm 1)验证NLOS测量的数量比较少的情形下算 算法 计算复杂度 法的性能。设置锚节点的个数N=5,NLOS测量 SDpli3 O(NB) 与LOS测量的数量分别为1、4，等价于NLOS SOCp☒ 占比为20%，Bx=7m,m=1,这也就意味着本文 O(W3) 所提的算法仅仅迭代I次。仿真RMSE随σ测量 R-SDP14PI O(N65) 噪声的关系，其中设置σ的范围为0.15~0.90。图1 R-SDP1911 O(N65) 给出了算法的定位性能，可以看出本文所提算法 SR-LS112 O(KN) 的定位性能最好，QP、R-SDPI9算法的定位性能 次之。这是由于NLOS测量的数量少，本文所提 Random Guess O(N) 的算法能计算出比较准确的平衡参数初始值，所 Qpl6] O(NP) 以迭代过程中取得了不错的性能。当测量噪声 本文算法 O(m×KN 比较小，可以看出本文算法和QP算法的性能基 本一致，这是因为当LOS数量比较多，测量噪声 本文算法的计算复杂度虽然与迭代次数m有 比较小的时候，对QP算法的目标函数值影响比 关系，但该算法与锚节点的数量以及迭代次数之 较小，从而表现出了优异的性能。本文所提算法 间呈现出一种线性关系，在后面的仿真实验中证 在这种环境下性能优于其他的凸优化定位算法， 明，当算法迭代次数m=1时，算法便能取得较为 这是因为诸如SDP、SOCP等算法中含有经过凸 良好的定位性能。 松弛处理的约束条件，在大量的LOS测量中，定 4仿真结果以及分析 位性能自然会下降。 SDP 这节主要利用MTLAB仿真验证所提算法的 6.0 ASOCP R-SDP14 性能。为了更好说明本文算法的性能，与已有的 5.5 R-SDP19 二次规划(quadratic programming,QP),半定规划 5.0 —QP Random Guess (semide-finite programming,SDP),二阶锥规划 4.5 New algorithm SR-LS (second order cone programming,SOCP),随机高斯 A (random Guess),鲁棒半定规划(robust semidefinite 3.5 programming,.R-SDP)等算法进行了比较。算法 3.0 的定位性能使用均方根误差(root mean square er- 2.5 ror,RMSE)来衡量，RMSE计算方式为 2.0 0.15 0.300.450.600.750.90 o/m RMSE -x (14) L 图1不同定位算法性能的比较，NLOS=1,LOS=4 Fig.1 Comparison of performance of different position- 式中x与分别表示第i次定位目标节点的真实 ing algorithms,where NLOS=1,LOS=4 位置与估计位置。假设锚节点和目标节点随机 2)验证NLOS测量的数量比较多的情形下算 地分布在20m×20m的区域，执行M个独立的 法的性能。NLOS测量与LOS测量的数量分别 Monte Carlo(MC)运行，并且在每个运行中，使用 为3、2，等价于NLOS占比为60%，其他参数的设 随机的锚节点拓扑结构来定位随机定位的目标节 置同1)。在图2中显示了算法的定位性能，可以
3 算法的复杂度分析 本节主要给出一些现有算法的复杂度以及本 文所提算法的复杂度，参考文献 [10-11] 中已有的 结果，表 1 给出了所有算法最坏结果下的计算复 杂度分析。 可以看出，所有方法的计算复杂度主 要取决于网络的规模，即锚的数量。 表 1 算法的计算复杂度 Table 1 The computational complexity of the algorithm 算 法 计算复杂度 SDP[13] O(N 3 ) SOCP[2] O(N 3 ) R-SDP14[2] O(N 6.5 ) R-SDP19[11] O(N 6.5 ) SR-LS[12] O(KN) Random Guess O(N) QP[6] O(N 2 ) 本文算法 O(m×KN) m m = 1 本文算法的计算复杂度虽然与迭代次数 有 关系，但该算法与锚节点的数量以及迭代次数之 间呈现出一种线性关系，在后面的仿真实验中证 明，当算法迭代次数 时，算法便能取得较为 良好的定位性能。 4 仿真结果以及分析 这节主要利用 MTLAB 仿真验证所提算法的 性能。 为了更好说明本文算法的性能，与已有的 二次规划 (quadratic programming，QP)，半定规划 (semide- finite programming，SDP)，二阶锥规划 (second order cone programming，SOCP)，随机高斯 (random Guess)，鲁棒半定规划 (robust semidefinite programming，R-SDP) 等算法进行了比较。 算法 的定位性能使用均方根误差 (root mean square error，RMSE) 来衡量，RMSE 计算方式为 RMSE = vt 1 M ∑M i=1 ∥xˆi − xi∥ 2 (14) xi xˆi i 20 m×20 m M 式中 与 分别表示第 次定位目标节点的真实 位置与估计位置。 假设锚节点和目标节点随机 地分布在 的区域，执行 个独立的 Monte Carlo(MC) 运行，并且在每个运行中，使用 随机的锚节点拓扑结构来定位随机定位的目标节 M = 5 000 ni ni ∼ N(0,δ2 ) ei U(0,Bmax) 点位置。在本文的仿真中，设置 。假设 节点间的测量噪声 服从 Gaussian 零均值分布， 即 。节点间的 NLOS 误差 在这里假 设服从均匀分布，即 。 为了验证所提算法的性能，主要从以下 3 个 方面进行仿真：1)NLOS 测量的数量比较少的情 形；2)NLOS 测量的数量比较多的情形；3) 算法的 计算复杂度验证。 N = 5 Bmax = 7 m m = 1 σ σ 1) 验证 NLOS 测量的数量比较少的情形下算 法的性能。设置锚节点的个数 ，NLOS 测量 与 LOS 测量的数量分别为 1、4，等价于 NLOS 占比为 20%， ， ，这也就意味着本文 所提的算法仅仅迭代 1 次。仿真 RMSE 随 测量 噪声的关系，其中设置 的范围为 0.15~0.90。图 1 给出了算法的定位性能，可以看出本文所提算法 的定位性能最好，QP、R-SDP19 算法的定位性能 次之。这是由于 NLOS 测量的数量少，本文所提 的算法能计算出比较准确的平衡参数初始值，所 以迭代过程中取得了不错的性能。 当测量噪声 比较小，可以看出本文算法和 QP 算法的性能基 本一致，这是因为当 LOS 数量比较多，测量噪声 比较小的时候，对 QP 算法的目标函数值影响比 较小，从而表现出了优异的性能。 本文所提算法 在这种环境下性能优于其他的凸优化定位算法， 这是因为诸如 SDP、SOCP 等算法中含有经过凸 松弛处理的约束条件，在大量的 LOS 测量中，定 位性能自然会下降。 0.15 0.30 0.45 0.60 0.75 0.90 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 SDP SOCP R-SDP14 R-SDP19 QP Random Guess New algorithm SR-LS RMSE/m σ/m 图 1 不同定位算法性能的比较，NLOS=1，LOS=4 Fig. 1 Comparison of performance of different positioning algorithms,where NLOS=1，LOS=4 2) 验证 NLOS 测量的数量比较多的情形下算 法的性能。 NLOS 测量与 LOS 测量的数量分别 为 3、2，等价于 NLOS 占比为 60%，其他参数的设 置同 1)。 在图 2 中显示了算法的定位性能，可以 ·78· 智 能 系 统 学 报 第 16 卷
第1期 齐小刚，等：一种非视距环境下的目标定位算法 ·79· 看出，R-SDP19算法的性能最好，这是由于在含有 凸优化的定位算法。 大量的NLOS测量时，大量的约束条件就起到了 通过以上仿真实验可以看出，本文算法在 抑制NLOS误差的作用，能很好地提高算法的定 NLOS比例不是很高的时候占有很大的优势，在 位性能。并且在测量噪声不是很大的情形下，算 NLOS占比高的情形下虽然定位性能有所下降， 法R-SDPI4、SDP的定位性能也要好于QP,这也 但仍然优于一些凸优化算法。综合看来，本文的 是因为其中的约束条件发挥了抑制NLOS误差的 算法在定位性能和计算复杂度之间有着很好的平 作用。本文的算法中由于加入了平衡参数，从图2 衡，可以满足实时定位的需求。 可以看出，其定位性能仍然要优于一般的凸优化 算法，但次于算法R-SDP19。但是当测量噪声增 5结束语 加时，本文算法的性能比较稳定，并且与算法R- 在关于机器人、无人机和其他智能体的位置 SDP19的定位精度相差不大，也表现出了不错的 信息的研究领域中，目标节点的位置信息是至关 性能。 重要的环节。但是在含有NLOS环境中，节点的 7.0 定位精度大大下降。为了抑制NLOS误差对定位 ASOCP 6.5 精度的影响，本文引入了平衡参数这一关键量， 日 6.0 R-SDP14 将定位问题与一个GTRS问题框架进行对应。与 R-SDP19 5.5 OP 已有算法不同的是，本文所提算法并没有联合估 Random Guess 5.0 New algorithm 计目标节点的位置和平衡参数，而是采用了一种 -SR-LS 迭代求精的思想，算法用二分法进行求解，高速 4.5 有效。本文所提算法与已有的算法相比，不需要 4.0 任何关于NLOS路径的信息(NLOS状态、 3.5 3.0 NLOS的分布、NLOS误差的上界等)，另外，与大 0.150.300.450.600.750.90 多数现有算法不同，所提算法的计算复杂度低， o/m 能够满足实时定位的需求。仿真实验结果表明， 图2不同定位算法性能的比较，NL0S=3,L0S=2 该算法具有稳定的NLOS误差抑制能力，在定位 Fig.2 Comparison of performance of different position- ing algorithms,where NLOS=3,LOS=2 性能和算法复杂度之间有着很好的平衡。但不足 3)算法的计算复杂度验证。软件：MATALB 的是，如果所有的路径均是NLOS,所提算法表现 R2018 b,CPU:Intel(R)Core(TM)i5-7500 3.40 GHZ 不佳，还有待后续研究。 内存：4.0GB,6=0.2,其他参数设置同1)，平均每 参考文献： 次定位时间如表2所示。 [1]KOLEDOYE M A,FACCHINETTI T,ALMEIDA L.Im- 表2算法的平均定位时间 Table 2 Average localization time of the algorithm proved MDS-based localization with non-line-of-sight RF links[J].Journal of intelligent and robotic systems,2020. 算法 平均定位时间/s 98(1)227-237 SDP 0.79 [2]WANG Gang,CHEN H,LI Youmign,et al.NLOS error SOCP 0.64 mitigation for TOA-based localization via convex relaxa- R-SDP14 1.24 tion[J].IEEE transactions on wireless communications. 2014,13(8):4119-4131 R-SDP19 1.56 [3]胡楠，吴成东，刘鹏达，等.基于严格残差选择的非视距 SR-LS 0.002 定位算法.东北大学学报（自然科学版），2016,37(9)： Random Guess 0.0003 1221-1224 QP 0.44 HU Nan,WU Chengdong,LIU Pengda,et al.NLOS local- 本文算法 0.035 ization algorithm based on the strict residual[J.Journal of Northeastern University(natural science),2016,37(9): 从表2可以看出，本文所提算法的定位速度 1221-1224 仅次于Random Guess和SR-LS,远快于几种基于 [4]WYMEERSCH H,MARANO S,GIFFORD W M,et al.A
看出，R-SDP19 算法的性能最好，这是由于在含有 大量的 NLOS 测量时，大量的约束条件就起到了 抑制 NLOS 误差的作用，能很好地提高算法的定 位性能。 并且在测量噪声不是很大的情形下，算 法 R-SDP14、SDP 的定位性能也要好于 QP，这也 是因为其中的约束条件发挥了抑制 NLOS 误差的 作用。本文的算法中由于加入了平衡参数，从图 2 可以看出，其定位性能仍然要优于一般的凸优化 算法，但次于算法 R-SDP19。 但是当测量噪声增 加时，本文算法的性能比较稳定，并且与算法 RSDP19 的定位精度相差不大，也表现出了不错的 性能。 0.15 0.30 0.45 0.60 0.75 0.90 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0 RMSE/m SDP SOCP R-SDP14 R-SDP19 QP Random Guess New algorithm SR-LS σ/m 图 2 不同定位算法性能的比较，NLOS=3，LOS=2 Fig. 2 Comparison of performance of different positioning algorithms,where NLOS=3，LOS=2 δ = 0.2 3) 算法的计算复杂度验证。软件：MATALB R2018 b，CPU：Intel(R)Core(TM)i5-7 500 3.40 GHZ， 内存：4.0 GB， ，其他参数设置同 1)，平均每 次定位时间如表 2 所示。 表 2 算法的平均定位时间 Table 2 Average localization time of the algorithm 算 法 平均定位时间/s SDP 0.79 SOCP 0.64 R-SDP14 1.24 R-SDP19 1.56 SR-LS 0.002 Random Guess 0.000 3 QP 0.44 本文算法 0.035 从表 2 可以看出，本文所提算法的定位速度 仅次于 Random Guess 和 SR-LS，远快于几种基于 凸优化的定位算法。 通过以上仿真实验可以看出，本文算法在 NLOS 比例不是很高的时候占有很大的优势，在 NLOS 占比高的情形下虽然定位性能有所下降， 但仍然优于一些凸优化算法。 综合看来，本文的 算法在定位性能和计算复杂度之间有着很好的平 衡，可以满足实时定位的需求。 5 结束语 在关于机器人、无人机和其他智能体的位置 信息的研究领域中，目标节点的位置信息是至关 重要的环节。但是在含有 NLOS 环境中，节点的 定位精度大大下降。为了抑制 NLOS 误差对定位 精度的影响，本文引入了平衡参数这一关键量， 将定位问题与一个 GTRS 问题框架进行对应。与 已有算法不同的是，本文所提算法并没有联合估 计目标节点的位置和平衡参数，而是采用了一种 迭代求精的思想，算法用二分法进行求解，高速 有效。 本文所提算法与已有的算法相比，不需要 任何关 于 NLO S 路径的信 息 (NLO S 状态、 NLOS 的分布、NLOS 误差的上界等)，另外，与大 多数现有算法不同，所提算法的计算复杂度低， 能够满足实时定位的需求。 仿真实验结果表明， 该算法具有稳定的 NLOS 误差抑制能力，在定位 性能和算法复杂度之间有着很好的平衡。但不足 的是，如果所有的路径均是 NLOS，所提算法表现 不佳，还有待后续研究。 参考文献： KOLEDOYE M A, FACCHINETTI T, ALMEIDA L. Improved MDS-based localization with non-line-of-sight RF links[J]. Journal of intelligent and robotic systems, 2020, 98(1): 227–237. [1] WANG Gang, CHEN H, LI Youmign, et al. NLOS error mitigation for TOA-based localization via convex relaxation[J]. IEEE transactions on wireless communications, 2014, 13(8): 4119–4131. [2] 胡楠, 吴成东, 刘鹏达, 等. 基于严格残差选择的非视距 定位算法 [J]. 东北大学学报 (自然科学版), 2016, 37(9): 1221–1224. HU Nan, WU Chengdong, LIU Pengda, et al. NLOS localization algorithm based on the strict residual[J]. Journal of Northeastern University (natural science), 2016, 37(9): 1221–1224. [3] [4] WYMEERSCH H, MARANO S, GIFFORD W M, et al. A 第 1 期 齐小刚，等：一种非视距环境下的目标定位算法 ·79·
·80· 智能系统学报 第16卷 machine learning approach to ranging error mitigation for meter estimation[J].IEEE transactions on vehicular tech- UWB localization[J].IEEE transactions on communica- nology,2019,68(6):6177-6181 tions,.2012,60(6):1719-1728. [12]BECK A,STOICA P,LI Jian.Exact and approximate [5]CHAN Y T,TSUI W Y,SO H C,et al.Time-of-arrival solutions of source localization problems[J].IEEE trans- based localization under NLOS conditions[J].IEEE trans- actions on signal processing,2008,56(5):1770-1778. actions on vehicular technology,2006,55(1):17-24. [13]VAGHEFI R M,BUEHRER R M.Cooperative localiza- [6]YANG Kai,AN Jianping,BU Xiangyuan,et al.A TOA- based location algorithm for NLOS environments using tion in NLOS environments using semide-finite program- quadratic programming[C]//Proceedings of 2010 IEEE ming[J].IEEE communications letters,2015,19(8): Wireless Communication and Networking Conference. 1382-1385 Sydney,Australia,2010:1-5. 作者简介： [7]月千里，万鹏武，卢光跃，等.非视距环境下RSS和 齐小刚，教授，博士生导师，主要 TDOA联合的信源被动定位).西安电子科技大学学 研究方向为复杂系统建模与仿真、网 报，2019,46(3)：180-188. 络算法设计与应用。申请专利47项 YAN Qianli,WAN Pengwu,LU Guangyue,et al.Passive (授权19项)，登记软件著作权4项。 发表学术论文100余篇。 localization of the signal source based on RSS and TDOA combination in the non-line-of-sight environment[J]. Journal of Xidian University,2019,46(3):180-188. 张海洋，硕士研究生，主要研究方 [8]YU Kegen,GUO Y G.Improved positioning algorithms 向为无人机定位与导航。 for non line-of sight environments[J].IEEE transactions on vehicular technology,2008,57(4):2342-2353. [9]LUI K WK,SO HC,MA WK.Maximum a posteriori ap- proach to time-of-arrival-based localization in non-line-of sight environment[J].IEEE transactions on vehicular tech- nology,2010,59(3):1517-1523 魏倩，硕士研究生，主要研究方向 [10]TOMIC S,BEKO M.A bisection-based approach for ex- 为无人机定位与导航。 act target localization in NLOS environme-nts[J].Signal processing,2018,143:328-335. [11]CHEN Haotian,WANG Gang.ANSARI N.Improved ro- bust TOA-based localization via NLOS balancing para-
machine learning approach to ranging error mitigation for UWB localization[J]. IEEE transactions on communications, 2012, 60(6): 1719–1728. CHAN Y T, TSUI W Y, SO H C, et al. Time-of-arrival based localization under NLOS conditions[J]. IEEE transactions on vehicular technology, 2006, 55(1): 17–24. [5] YANG Kai, AN Jianping, BU Xiangyuan, et al. A TOAbased location algorithm for NLOS environments using quadratic programming[C]//Proceedings of 2010 IEEE Wireless Communication and Networking Conference. Sydney, Australia, 2010: 1−5. [6] 闫千里, 万鹏武, 卢光跃, 等. 非视距环境下 RSS 和 TDOA 联合的信源被动定位 [J]. 西安电子科技大学学 报, 2019, 46(3): 180–188. YAN Qianli, WAN Pengwu, LU Guangyue, et al. Passive localization of the signal source based on RSS and TDOA combination in the non-line-of-sight environment[J]. Journal of Xidian University, 2019, 46(3): 180–188. [7] YU Kegen, GUO Y G. Improved positioning algorithms for non line-of sight environments[J]. IEEE transactions on vehicular technology, 2008, 57(4): 2342–2353. [8] LUI K W K, SO H C, MA W K. Maximum a posteriori approach to time-of-arrival-based localization in non-line-of sight environment[J]. IEEE transactions on vehicular technology, 2010, 59(3): 1517–1523. [9] TOMIC S, BEKO M. A bisection-based approach for exact target localization in NLOS environme -nts[J]. Signal processing, 2018, 143: 328–335. [10] CHEN Haotian, WANG Gang. ANSARI N. Improved robust TOA-based localization via NLOS balancing para- [11] meter estimation[J]. IEEE transactions on vehicular technology, 2019, 68(6): 6177–6181. BECK A, STOICA P, LI Jian. Exact and approximate solutions of source localization problems[J]. IEEE transactions on signal processing, 2008, 56 (5): 1770–1778. [12] VAGHEFI R M, BUEHRER R M. Cooperative localization in NLOS environments using semide -finite programming[J]. IEEE communications letters, 2015, 19(8): 1382–1385. [13] 作者简介： 齐小刚，教授，博士生导师，主要 研究方向为复杂系统建模与仿真、网 络算法设计与应用。申请专利 47 项 (授权 19 项)，登记软件著作权 4 项。 发表学术论文 100 余篇。 张海洋，硕士研究生，主要研究方 向为无人机定位与导航。 魏倩，硕士研究生，主要研究方向 为无人机定位与导航。 ·80· 智 能 系 统 学 报 第 16 卷