一种用于室内定位的线性规划算法
摘 要：针对基于ToA定位中存在的信标节点较少和发送时间不能提前预知的问题，提出了一种新的应用于无线传感网络室内定位的线性规划算法.通过考虑测量值的最小平均绝对值误差，利用线性逼近方法，将一个复杂的、非凸的室内定位问题转换为一个简单的线性规划问题，并用迭代求精的方法求出最优解.仿真结果表明，提出算法计算复杂度低，收敛速度快，可以快速地求出未知节点的坐标；通过和已有的定位算法相比，提出算法在信标节点较少的情况下，仍能保持很好的定位精度，利用较少的节点资源达到比已有算法更好的定位性能.
关键词：无线传感器网络；到达时间；定位；线性规划；迭代
中图分类号：TP393 文献标识码：A
Abstract：To solve the problem of fewer beacon nodes and unknown transmission time in Time of Arrival （ToA） based localization， a new linear programming algorithm was proposed to approximate nonlinear localization estimation problems. We consider the least-mean absolute errors of the residual and formulate the nonconvex localization problem as a simple linear programming by using linear approximation. Simulation results demonstrate that the proposed algorithm can maintain good positioning accuracy under fewer beacon nodes and achieve better performance by using less node resources than the existing algorithms.
Key words： wireless sensor networks；time of arrival；localization；linear programming；iteration
目前，随着无线通信技术、嵌入式技术和网络技术的快速发展，无线传感网络[1]（Wireless Sensor Networks，WSN）得到了前所未有的关注，已经成为研究热点.定位技术[2]是WSN中最重要的基础性研究之一，没有位置信息的WSN应用是没有任何意义的.基于WSN的定位是根据不同定位技术的测量值来确定网络中传感节点的位置，常采用的定位技术主要有基于到达时间[3]（Time of Arrival，ToA）的定位，基于到达时间差[4]（Time Different of Arrival，TDoA）的定位，基于到达角度[5]（Angle of Arrival，AoA）的定位和基于接收信号强度[6]（Received Signal Strength Indicator，RSSI）的定位等.基于WSN的定位系统被广泛用于各种实际应用中，如环境监测[7]、工业自动化过程控制[8]和家庭医疗保健[9]等.
基于ToA的定位技术具有定位精度高、实现简单等优点，得到了国内外研究者的广泛关注，目前已有很多基于ToA的定位研究方法.最大似然估计方法[10]（Maximum Likelihood，ML）是最常用的方法之一，但是，要得到基于ToA定位问题的最大似然估计量是一个困难的全局优化问题.很多研究者提出了一些替代方法来避免复杂的全局优化问题，文献[11]将定位问题转换成一个半正定规划松弛问题（Semidefinite Programming Relaxation，SDP）进行求解，通过采用解决SDP的方法来降低求解ML问题的复杂度.文献[12]提出用线性最小二乘法（Linear Least Square，LLS）解决定位问题.通过这个方法，能够在测量噪声较小的情况下得到较好的定位性能.文献[13]基于极小极大方法，提出了2个次优的方案来解决定位问题，虽然已经提出了很多有效的方法能够减少基于ToA的定位问题的复杂度和得到较好的定位精度，但是它们基本上都要求部署较多的信标节点和提前知道信号的发送时间，没有考虑信标节点较少和发送时间未知的情况.
在实际应用中，不可能在一个区域内部署大量的信标节点，而且这些信标节点也基本上不能提前知道目标节点发送信号的初始时间.本文针对信标节点部署较少、发送时间未知的情况，提出了一种新的基于线性规划的定位优化算法，通过多个信标节点接收到的ToA测量值，消除发送时间未知对定位的影响；考虑残差的最小平均绝对值误差，将一个原始形式为非凸优化的定位问题转换成线性规划问题（Linear Programming，LP）.线性规划结构简单，计算复杂度低，可以采用迭代求精的方法快速求出最优解，得到未知节点的坐标.仿真结果证明了提出的算法具有很好的定位性能，特别是在信标节点较少的情况下，提出算法的定位性能明显优于已有的定位算法.
从图1可以看出，在不同的测量噪声和信标节点个数下，提出算法要明显优于LLS算法，具有和SDR算法相似的定位精度.不管部署多少个信标节点，当测量噪声较小时，3种不同的定位算法都能得
到较好的定位性能，但随着测量噪声的增大，3种定位算法的定位误差也会跟着提高，信标节点部署较多时，定位误差增长的程度会降低，其中，LLS算法的定位误差增加的程度最为明显.当信标节点个数较少时，即使在测量噪声很小的情况下，LLS算法和SDR算法依然具有较高的定位误差，本文提出算法明显优于LLS算法和SDR算法.