郑滨红

（宜春幼儿师范高等专科学校初等教育学院，江西 高安 330800）

基于距离平方差的目标定位估计算法研究

郑滨红

（宜春幼儿师范高等专科学校初等教育学院，江西 高安 330800）

无线传感器网络定位技术作为无线传感器网络的重要支撑技术之一，具有很大的实际价值和研究意义。无线传感器网络的目标定位估计技术主要应用于目标跟踪和目标运动分析，在工业领域具有广阔的发展前景。无线传感器网络由许多在空间中分布的传感器组成，这些传感器能够测量出传感器与定位目标之间的距离，但是该观测距离因为受环境影响所以是有噪音的。目前基于距离的最小二乘估计的定位算法已得到广泛关注，但是该问题是一个非凸问题，精确求解十分困难。因此学者们提出了基于距离平方的最小二乘估计的定位算法，该算法的数学模型虽然相对精确，但是计算起来十分复杂。本文基于距离平方差，提出了新的目标定位估计算法，该算法计算简单，稳定性强，且能得到与基于距离平方的最小二乘估计的定位算法相当的结果。仿真实验结果表明，无论在低噪音水平、中噪音水平还是高噪音水平下，本文提出的新算法都更有优势，在工程领域有极高的应用价值。

无线传感器网络；距离估计；目标定位；最小二乘

0 引言

无线传感器网络是随着无线通信、嵌入式技术、传感器技术、微机电技术及分布式信息处理技术的进步而发展起来的一门新兴的信息获取技术。无线传感器网络的发展最初起源于战场监测等军事应用，而现今无线传感器网络被应用于很多民用领域，如环境与生态监测、健康监护、家庭自动化、以及交通控制等。无线传感器网络定位技术作为无线传感器网络的重要支撑技术之一，无疑是具有很大的实际研究价值和意义的。无线传感器网络最重要的运用在于目标定位估计，这一技术主要应用于目标跟踪和目标运动分析[1-4]。

无线传感器网络由许多在空间中分布的传感器组成，由于传感器具有体积小、价格低、自组织、隐蔽性好等特点，同时还兼备无线通信及网络随机部署等功能，因此非常适合用于目标的定位和跟踪。在无线传感器网络中有一个辐射目标源，该目标源向周围辐射信号，同时无线传感器网络中的传感器接收目标源的信号，传感器能够基于接收信号测量出传感器与定位目标之间的距离，但是该观测距离因为受环境影响所以是有噪音的。近年来，利用传感器的测量距离来定位一个辐射目标源的位置坐标的问题已经在信号处理领域引起了极大的关注[5-7]。

基于距离的最小二乘估计的定位算法已得到广泛关注，该算法的模型本质上是对目标定位的最大似然估计[5],但是该问题是一个非凸问题，精确求解十分困难[6-7]。因此 Beck等人提出了基于距离平方的最小二乘估计的定位算法，该算法能够计算出一个不错的定位，但是计算过程过于复杂[6]。本文基于距离的平方差，提出了新的目标定位估计算法，该算法计算简单，稳定性强，且能得到与基于距离平方的最小二乘估计的定位算法相当的结果。无论在低噪音水平、中噪音水平还是高噪音水平下，新算法相比 Beck等人提出的计算十分复杂的算法都更有优势。

1 基于距离的目标定位估计

1.1 物理模型介绍

本文考虑在空间中分布的m个传感器，用s∈Rn表示第i个传感器的坐标向量（在实际场景

1.2 基于距离的最小二乘估计模型

估计目标源位置的坐标向量的最基本的方法是基于距离观测值ir的最小二乘（range-based least squares，RLS）估计模型：

（RLS）问题的最优解称为目标源坐标的基于距离的最小二乘估计。特别地，当ε服从高斯分布，且协方差矩阵与单位矩阵成比例时，（RLS）问题的最优解事实上就是对目标源坐标的最大似然估计[5]。（RLS）问题是非凸的，所以找到它的精确解是十分困难的。为求解该问题，人们通过半正定松弛技术将（RLS）问题转化为半定规划问题[5]。半定规划问题可利用内点法[8]在多项式时间内有效求解。但是，半定规划问题得到的最优解并不是（RLS）问题的最优解，该算法有时会得到很差的估计定位。所以人们开始尝试构造不同的模型来得到更好的定位算法。

1.3 基于距离平方的最小二乘估计算法

估计目标源位置的坐标向量的另一种方法是基于距离观测值ir的平方的最小二乘（squared-rangebased least squares，SRLS）估计模型：

（SRLS）问题的最优解称为目标源坐标的基于距离平方的最小二乘估计。注意到，（SRLS）问题的最优解只是对目标源坐标的最大似然估计的次优解，因为平方误差的协方差矩阵与单位矩阵不成比例[9]。与（RLS）问题一样，（SRLS）问题也是非凸的，但是Beck等人提出了求解该问题的可执行的算法[6]。（SRLS）问题等价于如下的约束优化问题：

进一步地，令：

则（SRLS）问题可写成如下的形式：

Beck等人提出了求解（SRLS）问题的算法如下[6]：

算法1：Beck求解（SRLS）问题的算法

步骤1：计算矩阵 A , D，计算向量 b, f。

步骤 4：目标源坐标的基于距离平方的最小二乘估计为yˆ(λ0)的前n项，即

算法1虽然能够计算出一个不错的定位，但是计算过程过于复杂。所以我们在下一节中将提出一个既能计算简单又能达到定位精度的新算法。

1.4 基于距离平方差的最小二乘估计新算法

假设无线传感器网络中第1个传感器位于坐标原点，那么我们可以得到估计目标源位置的坐标向量的新方法：基于第i个传感器与第 1个传感器的距离观测值的平方差（squared-range-difference，SRD），利用最小二乘（least squares，LS）策略来估计目标源的坐标向量x，即求解如下的优化问题：

其中：

令：则（SRDLS）问题可写成如下形式：

算法2：基于距离平方差的最小二乘估计新算法

步骤1：计算矩阵G与向量h。

虽然（SRDLS）模型没有（SRLS）模型精确，但是本文基于（SRLS）模型提出的新算法计算简单，稳定性强，在工程领域有极高的应用价值。

2 数值实验

例1：考虑在2维平面［- 1 0 ,10］ ×［- 1 0 ,10］平方米的传感器网络中有6个传感器，他们的位置坐标 si，每个传感器与定位目标之间的真实距离rˆi以及观测到的噪音距离 ri如表 1所示，其中，观测距离都在很低的噪音水平上。目标源的实际坐标为x=［4.8509, - 1 .5133］T，利用算法1得到的基于距离平方的最小二乘估计为差为：

此时，本文提出的基于距离平方差的最小二乘估计新算法对目标源的坐标估计更准确。

例2：考虑在2维平面［- 1 0 ,10］ ×［- 1 0 ,10］平方米的传感器网络中有4个传感器，他们的位置坐标 si，每个传感器与定位目标之间的真实距离以及观测到的噪音距离 ri如表 2所示，其中，观测距离都在很高的噪音水平上。目标源的实际坐标为x=［-1 .2992,- 8 .1697］T，利用算法1得到的基于距离平方的最小二乘估计为误差为

表1 例1的传感器坐标、真实距离与噪音距离Tab.1 Position of sensors, exact distances, and observed noisy distances in Example 1

此时，Beck等人提出的基于距离平方的最小二乘估计对目标源的坐标估计特别差，本文提出的基于距离平方差的最小二乘估计新算法对目标源的坐标估计更准确。

表2 例2的传感器坐标、真实距离与噪音距离Tab.2 Position of sensors, exact distances, and observed noisy distances in Example 2

除此之外，我们还进行了蒙特卡洛随机实验来对比Beck等人提出的算法1与本文提出的算法2，并观察每个算法随着传感器个数增多时的表现。在仿真实验中，我们假设每个距离观测值的噪音εi为高斯噪声，满足 N ( 0,σ2) 的高斯分布。每次实验都在 2维平面 ［-1 0 ,10 ］ ×［-1 0 ,10］平方米的传感器网络内定位一个目标源，每一次实验中目标源的坐标都在 ［-1 0 ,10 ］ ×［-1 0 ,10］平方米的正方形区域内均匀地随机选取，同时这m个传感器的坐标也在［-1 0 ,10］×［- 1 0 ,10］平方米的正方形区域内均匀地随机选取（每次实验都设定 s1= [ 0,0]T），并且每个传感器的距离观测值的噪音εi在N ( 0,σ2) 的高斯分布上随机选取。这里，我们采用均方误差（root mean square error，RMSE）作为算法的评价标准：

其中，Mc为蒙特卡洛随机实验的次数，本文选择 M c= 10000，为第i次实验中对目标源的实际坐标 xi的定位估计。

表3 时算法1与算法2的均方误差Tab.3 RMSEs of Algorithm 1 and Algorithm 2： -6

表3 时算法1与算法2的均方误差Tab.3 RMSEs of Algorithm 1 and Algorithm 2： -6

m 算法1 算法2RMSE RMSE-2 1 4 1.70E-06 1.74E-06 3.59084E-08 5 1.38E-06 1.42E-06 4.12792E-08 6 1.25E-06 1.30E-06 5.20215E-08 7 1.16E-06 1.21E-06 5.32119E-08 8 1.10E-06 1.15E-06 5.49916E-08 9 1.05E-06 1.10E-06 5.808E-08 10 1.01E-06 1.06E-06 5.40873E-08 11 9.75E-07 1.03E-06 5.62406E-08 12 9.49E-07 1.01E-06 6.22055E-08 15 8.78E-07 9.37E-07 5.87932E-08 20 8.11E-07 8.68E-07 5.64922E-08 25 7.63E-07 8.16E-07 5.27814E-08 30 7.21E-07 7.75E-07 5.33403E-08 35 6.94E-07 7.42E-07 4.84185E-08 40 6.69E-07 7.20E-07 5.08104E-08 45 6.48E-07 6.94E-07 4.61784E-08 50 6.28E-07 6.75E-07 4.6576E-08 55 6.15E-07 6.60E-07 4.50884E-08 60 5.99E-07 6.42E-07 4.36453E-08

从表3、表4和表5的数值结果可以看出，虽然新算法2的（SRDLS）模型没有算法1的（SRLS）模型精确，但是无论在低噪音水平中噪音水平还是在高噪音水平σ=1下，算法2总能达到和算法1相当的定位精度。在低噪音水平下，本文提出的新算法2在传感器个数较少（ m ≤ 8 ）或者传感器个数较多时定位效果十分接近算法 1，这时利用本论文提出的新算法2进行定位既计算简单又效果良好，相比计算十分复杂的算法1更有优势。在中、高噪音水平下，本文提出的新算法2在传感器个数较多时定位效果较接近算法 1，这时利用本论文提出的算法2进行定位既计算简单又效果良好，相比计算十分复杂的算法1更有优势。

3 结论

本文基于距离平方差的最小二乘估计模型：（SRDLS）模型，提出了在传感器网络中定位目标源的位置坐标的新算法：算法 2。虽然（SRDLS）模型没有 Beck等人提出的基于距离平方的最小二乘估计模型：（SRLS）模型精确，但是本文基于（SRLS）模型提出的算法1计算简单，稳定性强且能得到与（SRLS）模型的定位算法1相当的结果。数值仿真实验表明，某些时候Beck等人提出的算法1对目标源的坐标估计特别差，但是本文提出的新算法2对目标源的坐标估计准确，效果良好。并且蒙特卡洛随机实验的仿真结果表明，无论在低噪音水平、中噪音水平还是高噪音水平下，新算法2相比Beck等人提出的计算十分复杂的算法1都更有优势。综上所述，本文提出的基于距离平方差的最小二乘估计模型更简单，基于该模型提出的新算法 2不仅计算简单，稳定性强，而且效果良好，在工程领域有极高的应用价值。

表4 时算法1与算法2的均方误差Tab.4 RMSEs of Algorithm 1 and Algorithm 2：

表4 时算法1与算法2的均方误差Tab.4 RMSEs of Algorithm 1 and Algorithm 2：

m 算法1 算法2RMSE RMSE-2 1 4 0.001673575 0.001726044 5.24698E-05 5 0.001401963 0.001437599 3.56358E-05 6 0.00124557 0.001293063 4.74933E-05 7 0.001152459 0.001204964 5.25048E-05 8 0.001100961 0.00115893 5.79688E-05 9 0.001042693 0.00110106 5.83665E-05 10 0.001008347 0.001067364 5.90172E-05 11 0.000976917 0.001032559 5.56424E-05 12 0.000947434 0.00100615 5.8716E-05 15 0.000885099 0.000937738 5.2639E-05 20 0.000805867 0.000861516 5.56483E-05 25 0.000761324 0.000816398 5.50744E-05 30 0.000721129 0.000771009 4.98801E-05 35 0.000692966 0.000745235 5.22682E-05 40 0.000665711 0.000715053 4.93418E-05 45 0.000649754 0.000696768 4.7014E-05 50 0.000633085 0.000681442 4.83571E-05 55 0.000613027 0.000658757 4.57297E-05 60 0.000599056 0.000641312 4.22559E-05

表5 1σ=时算法1与算法2的均方误差Tab.5 RMSEs of Algorithm 1 and Algorithm 2： 1σ=

[1] 李杰, 李振波, 陈佳品. 一种基于遗传算法与蚁群算法混合算法的无线传感器网络定位算法[J]. 软件, 2017, 38(1)：11-15.

[2] 周唯, 刘冬, 刘会师. 基于无线传感器网络拓扑的研究与设计[J]. 软件, 2013, 34(12): 22-25.

[3] 任丰源, 黄海宁, 林闯.无线传感器网络[J]. 软件学报,2006, 14(7): 1282-1290.

[4] 王福豹, 史龙, 任丰源. 无线传感器网络中的自身定位系统和算法[J]. 软件学报, 2005, 16(5): 857-868.

[5] CHEUNG K W, MA W K, SO H C. Accurate approximation algorithm for TOA-based maximum likelihood mobile location using semidefinite programming[C]. IEEE International Conference on Acoustics, Speech, and Signal Processing,2004. Proceedings. IEEE, 2004, 2: 145-148.

[6] BECK A, STOICA P, LI J. Beck, A., Stoica, P., & Li, J.(2008). Exact and approximate solutions of source localization problems[J]. IEEE Transactions on Signal Processing, 2008,56(5): 1770-1778.

[7] CHEN S, HO K C. Achieving asymptotic efficient performance for squared range and squared range difference localizations[J]. IEEE Transactions on Signal Processing, 2013,61(11): 2836-2849.

[8] VANDENBERGHE L, BOYD S. Semidefinite programming[M]. Society for Industrial and Applied Mathematics, 1996.

[9] CHEUNG K W, SO H C, MA W K, et al. Least squares algorithms for time-of-arrival-based mobile location[J]. IEEE Transactions on Signal Processing, 2004, 52(4): 1121-1130.

A Squared-Range-Difference-Based Least Squares Estimation Algorithm of Source Localization Problems

ZHENG Bin-hong
(School of Primary education, Yichun infant normal college, Gaoan 330800, Jiangxi)

As one of the important support technologies of wireless sensor networks, wireless sensor network location technology has great practical value and research significance. The technology of target location estimation in wireless sensor networks is mainly used in target tracking and target motion analysis, which has broad prospects in the industrial field. Wireless sensor network consists of many spatially distributed sensors, these sensors can measure the range between the sensors and the target, but the observed range is with noise caused by the environment. At present, the localization estimation algorithm based on the range least squares estimation has drawn much attention, but the problem is a non-convex problem, so it is very difficult to exactly solve the problem. Therefore,scholars have proposed localization estimation algorithm based on least squares of the range squares. Although the mathematical model of that algorithm is relatively accurate, its computation is very complex. Based on the range square difference, a new targeting estimation algorithm has proposed in this paper, and the new algorithm is simple,is with high stability, and can reach nearly same good results as the algorithm based on the range least squares estimation. Simulation results show that the new algorithm proposed in this paper have more advantages than the other algorithm under low noise levels, medium noise levels, and high noise levels. Thus the new targeting estimation algorithm proposed in this paper has a very high value in the engineering field.

Wireless sensor network; Distance estimation; Source localization; Least squares

TP212.9

A

10.3969/j.issn.1003-6970.2017.12.054

本文著录格式：郑滨红. 基于距离平方差的目标定位估计算法研究[J]. 软件，2017，38（12）：270-274

郑滨红(1988-)，女，讲师，主要研究方向：科学计算。