张 晨，王韦刚，许晨东，孙啸辰，郭建军，涂真珍，冒雨龙

(1.南京邮电大学电子与光学工程学院，江苏 南京 210023 2.南京邮电大学材料科学与工程学院，江苏 南京 210023)

近年来，随着无线通信技术的发展和物联网的广泛应用，基于位置信息的服务得到了迅速发展，覆盖了军事、农业、工业等众多领域。随着智能终端及设备的逐渐普及，如何提高室内无线定位系统的定位精度成为一个研究热点。面对室内环境复杂、各种障碍物遮挡、多径效应严重的情况，室内定位系统需要进一步寻求更好的应对方法以解决定位精度低的问题。

在无线传感器定位系统中，人们希望获得实时准确的位置信息，目前许多定位技术得到了广泛的研究，主要包括接收信号强度（RSS）［1］、到达时间（TOA）［2］、到达时间差（TDOA）［3］、到达角（AOA）［4］。这些应用通常假设节点间的距离为直线距离，即假设信号通过锚节点和目标节点之间的传播是没有障碍物遮挡的直线传播，也称为视距传播（Line-of-sight，LOS）。 然而，在室内定位场景中往往有很多障碍物，如桌子、墙壁、行人等障碍物都会干扰信号的传播，此时节点间的视距传播路径会被阻断。由于障碍物的存在，非视距（Non-line-of-sight，NLOS）传播在定位场景中很常见，如图1所示的室内环境中，发射信号到达各个接收节点的传播过程中同时存在LOS传播和NLOS传播。当LOS传播路径不存在时，仅在NLOS环境中，发送节点发出的无线信号经过反射、衍射、绕射等方式到达接收节点，对定位系统测距精度的影响更严重，并进一步降低定位精度。鉴于NLOS传播对目标节点的定位影响非常大，人们希望能够抑制NLOS传播带来的误差，从而减少NLOS误差对目标节点定位的影响。

图1 信号传播示意图

目前有两种研究思路来减少NLOS误差。一种是先识别 LOS／NLOS连接，如采用神经网络［5-7］、能量检测［8］等识别方法。 Wylie 等［9］通过节点之间的距离结合测量噪声标准差以及残差分析测试，来判断测量数据中是否存在NLOS误差。若检测到LOS连接数量能够满足定位要求，可以舍弃NLOS信息并直接采用LOS信息进行定位，然后利用LOS数据使用最大似然估计方法进行计算［10］，它可以提供一种逐步优化的定位方法，在这种情况下，定位精度可以达到Cramer-Rao下界（CRLB）。而当NLOS连接较多不可忽略时，可以利用NLOS传播的信息进行定位，Xie 等［11］采用残差加权对 NLOS／LOS 混合场景下进行定位。文献［12］提出了一种利用NLOS信号传播过程的多径反射提高定位鲁棒性的方法。文献［13］提出了一种误差项统计特征算法。文献［14］把定位维度扩展到三维空间中，利用接收信号强度与到达时间相结合来进行定位。然而，如果观测数据与假设的概率模型不匹配，也就是没能准确识别出 NLOS／LOS连接时，上述定位算法的性能下降非常严重。实际上，在大多数网络中，区分NLOS／LOS连接非常困难，因为很难获得有关NLOS的先验信息。另一种是不先识别LOS／NLOS连接而直接进行定位。该方法采用基于鲁棒的统计方法［15］，利用NLOS传播的特性，计算复杂度低且易于实现，但算法实际效果依赖于目标函数的选择，实际的应用场景会影响算法的性能，它需要一定大小的统计窗口，会有相应的延时。使用位置滤波［16］的方法，可以递归地给出位置估计结果，灵活地选择合适的滤波算法以适应不同的应用场合，然而一些算法计算复杂度较高，在滤波模型与实际系统不匹配时，性能会严重下降。Li等［17］提出了利用数据库对NLOS误差进行修正的动态定位算法，从坐标已知的信标节点中获得NLOS误差信息并记录在数据库中，用来进一步生成校正图。然而，该方法不能覆盖所有区域，并且建立数据库的过程复杂，存在降噪和基准点检测的问题。文献［18］采用三步最优化法，利用泰勒级数扩展，对非线性方程进行线性化处理，并用线性最小二乘得到初始的移动节点位置估计，在正偏差的约束下，采用基于迭代最优化方法估计非视距误差，再用估计误差修正初始的移动节点位置估计。由于此方法的成本函数定义为移动节点位置和多个距离圆交点之间的距离平方和，但当距离圆内部交点数量很大时，计算量会很大。

针对上述存在的问题，在本文中，提出了一种基于几何约束的二次规划优化方法来抑制NLOS误差。一方面，它不需要任何关于NLOS连接的先验信息。另一方面，由于采用了更严格的约束，它会比现有的优化方案具有更高的定位精度，可以应用于TOA系统中的NLOS误差抑制。实验结果表明，与现有优化技术相比，该方法具有更好的鲁棒性和更好的定位精度。

1 相关工作

1.1 基于三边定位的方法

三边定位利用各个锚节点到目标节点的距离进行定位。如图2所示，（xi，yi）表示第i个锚节点的坐标，di表示第i个锚节点到目标节点的距离，设未知目标节点坐标为（x，y），根据毕达哥拉斯定理可以得到以下方程

图2 三边定位原理图

通过求该方程解得到目标节点的坐标。然而由于室内环境中NLOS误差的存在，测得节点间的距离往往不是准确的距离，如图3所示，3个圆通常不会交于一点而是形成一个区域，这时候如果利用式（1）求解目标节点的坐标必然会出现较大误差。

图3 NLOS情况下的三边定位原理图

1.2 基于半正定的优化方法

在TOA定位技术中，得到的数据为目标节点和锚节点之间的距离。通常对第i个锚节点和目标节点之间的距离建模如下

然而在实际的室内环境中，目标节点和锚节点之间既有LOS连接也有NLOS连接，当计算路径是LOS连接时，测量误差会存在为负值的情况。在这种情况下，Su等［21］通过加入一个松弛变量对不等式进行松弛以满足条件，即ri＋ui＞di，保证不等式的成立。同时，确定ui的值很重要，这个变量必须足够大以确保不等式的可行性，同时也需足够小以确保约束方程。约束的目的是使目标函数最小化，以增加优化函数的可行性。模型如下

式中：pi为第i个锚节点的坐标，ρ和μ为常数，其取值根据不同的定位场景设定。

1.3 基于半正定的合作定位

一个合作定位网络［22］是由一部分已知坐标的锚节点来定位大量坐标未知的源节点，设xi∈R2，i＝1，2，…，N 是第 i个坐标未知的源节点，yj∈ R2，j＝1，2，…，M是第j个坐标已知的锚节点。 Ly和Lx包含了LOS中源-锚连接和源-源连接，Ny和Nx包含了NLOS中源-锚连接和源-源连接。

所运用的SDP方法能够利用节点之间的合作进行定位，当大多数是 NLOS时，可以改善定位性能。

2 改进的二次规划算法

2.1 系统模型

系统模型采取二次规划［23］的优化方法，通过对不等式的变换，将方程的最小二乘求解过程转化为二次规划问题。在NLOS连接中，锚节点与目标节点的距离如式（3）所示。目标节点与第i个锚节点的关系应满足

式中， B ＝ diag｛d1，d2，…，dN｝，Q 为噪声方差矩阵。

当NLOS误差不可忽略时，将式（17）作为约束项加入到式（19）中，可以得到目标位置估计为

2.2 改进的二次规划模型

在此基础上，本文提出了一种新的约束条件，利用三角形三边的关系，采用几何的方法对目标函数的解进一步约束。众所周知，在一个三角形中，两条边之和总是大于第三条边。如图4所示，BSi、BSj分别代表第i、j个锚节点，各个锚节点与目标节点的距离之和总是大于第i、j个锚节点之间的距离。

图4 节点间的位置关系

求解二次规划的方法有很多种，包括变量消去法［24］、拉格朗日乘子法［25］、积极集法［26］等。 这里采用凸优化方法中的内点法［27］来解决二次规划问题。根据上面所述，归纳出本文算法的步骤如算法1所示。

算法1 改进的二次规划算法步骤

3 实验与分析

在本节中，我们将评估所提出的定位算法的性能，并将其与其他定位算法进行了比较。定位区域是一个8×8的正方形，在这里我们设置4个锚节点和1个目标节点。锚节点的位置是固定的，分别为（0，0）、（0，8）、（8，0）、（8，8），目标节点的位置则不固定，在每一次仿真实验中随机生成，环境设置如图5所示。测量噪声服从高斯分布，其均值为0，标准差和距离成比例，取实际距离的2%。NLOS误差服从指数分布，我们设置了三组不同均值的实验条件，分别是实际距离的10%、30%和50%，对于上述三种情况，分别进行1 000次蒙特卡罗实验。文中提到的几种优化算法通过内点法进行求解，各个算法的定位误差的累积分布函数（CDF）如图6所示。图中“trileration”表示三边定位算法，“qp”表示原始的二次规划求解方法，“the optimized qp”表示增加NLOS误差约束的算法，“the proposed method”表示本文所提算法。从图5中可以看出，当噪声为10%时，基于几何约束的定位算法与其他算法相比优势不明显，随着NLOS误差越来越大，噪声环境逐渐变差时，达到30%、50%的真实距离，本文提出的定位算法效果相比其他算法优势越来越明显。这就表明，本文所提出的算法更适合在低信噪比的环境中进行定位。

图5 仿真环境设置

图6 不同算法位置误差CDF分布图

上述算法在不同噪声条件下的定位均方根误差（RMSE）如图7所示。RMSE计算方式如下：

其中θi与分别表示第i次蒙特卡罗实验目标节点的真实坐标与估计坐标，M表示蒙特卡洛实验的次数。从图7中可以看出，当NLOS误差较小时，几种算法的定位误差相差不大。然而，随着误差的增加，所提出的方法的定位误差明显小于其他方法。同时可以看出，随着NLOS误差的变化，本文所提出的方法变化的幅度相对较小，这意味着其鲁棒性更好。

图7 不同算法的RMSE仿真结果

为了对算法的效果进行准确评估，接下来对上述算法的复杂度进行分析。本文所提的算法采用内点法进行求解，首先使用拉格朗日法将不等式去除，然后使用KKT条件将原问题转为方程组，最后使用牛顿法求解。

利用内点法求解的通用复杂度［28］为

式中，m为输入变量的维度，p*为函数的最优解，M为在进行内点法求解之前迭代收敛的坐标，ε＞0为解的精度，常数γ取决于回溯参数α和β，

常数c只取决于精确度εnt，c＝log2log2（εnt），通常c≈ 6。

最终计算得到内点法的复杂度为Ο（n3．5L2），其中n输入是变量的维度，L是输入的长度。在采用内点法计算式（30）中的坐标之前，需要对初始的坐标进行迭代收敛，若进行迭代N次后收敛，则总体的复杂度为Ο（Nn3．5L2）。

根据上述算法，求得不同算法的计算复杂度，各个算法的复杂度对比如表1所示。其中trileration和qp少了约束项，不需要采用内点法进行求解，因此它们的复杂度都为Ο（1）。而the optimized qp和the proposed method添加了约束项，则需要采用内点法进行求解。式（30）中的两项约束的形式是相同的，因此在实际的求解中，可以把这两项合并为一项，则the proposed method与 the optimized qp的复杂度是相同的，都为Ο（Nn3L2）。综合各个算法的定位性能来说，在噪声环境恶劣的情况下，使用本文所提算法更有优势。

表1 算法复杂度对比

4 结束语

在本文中，提出一种抑制NLOS误差的定位算法。该算法采用几何方法来进一步约束原有的目标函数，以提高定位精度。仿真结果表明，通过加入新的几何约束，基于二次规划的定位算法的性能有了较明显的提高。将所提出的算法与之前的定位方法在不同NLOS环境下进行比较。实验结果表明，当NLOS的误差较大时，基于几何约束的二次规划的定位效果较其他定位方法有一定的优势。