源节点定位即通过在若干位置已知的点上进行测量来估算信号源的位置[1]。常用的定位测量技术包括到达时间(TOA)、到达时间差(TDOA)、到达角度(AOA)以及接收信号强度(RSS)等[2-3]。基于接收信号强度的源节点定位算法包括图心法[4]、半正定规划法[5]、最小二乘法[6]及其改进算法。图心法取已知采样点的坐标加权平均值作为源节点的坐标,容易实现但其定位精度低。半正定规划法把定位问题转化为一个凸优化问题,计算复杂。最小二乘法将多个已知采样点的接收信号强度转化为到源节点的距离,然后根据最小二乘准则计算源节点的坐标,但其前提是知道接收信号强度路径损耗模型的模型参数。研究人员对此进行改进,如文献[7]通过对距离值进行加权然后计算源节点的位置,文献[8-9]提出一种无需已知源节点发射功率的估计方法,文献[10]把路径损耗指数作为未知参数与位置参数一起进行估计,但这些改进方法仍无法解决模型参数全部未知的情况。文献[11]提出一种线性化法实现源节点的定位,通过将接收信号强度路径损耗模型线性化,使得求解位置参数时不再需要已知路径损耗模型参数,其不足为线性化将带来模型误差,当测量点的几何分布较差时导致位置估计不准确。
本文针对路径损耗模型的模型参数未知的情况,提出一种无需已知源节点发射功率及环境路径损耗指数的源节点定位算法。通过对路径损耗模型两次差分,消去与源节点发射功率相关的模型参数和路径损耗指数,再根据最小二乘准则来估计源节点的位置,并利用奇异值分解求广义逆来避免求解时测量误差放大。最后通过仿真数据评估了该算法的定位精度,并与其他源节点定位算法进行比较。
1 算法描述基于接收信号强度的源节点位置估计,一般是通过把若干已知位置的接收信号强度测量值转化为其到源节点的距离再进行相应的定位。接收信号强度路径损耗模型如下[12]:
(1) |
式中,Ri是已知位置i处的接收信号强度测量值(单位为dBm),通常利用多次测量取平均来减弱多路径效应的影响;R0是距离源节点参考距离d=1 m处的接收信号强度;np是信号的路径损耗指数;di是已知位置i到源节点的距离;Xσ是由阴影衰落效应引起的服从N(0, σdB2)正态分布的随机误差。
式(1)包括两个模型参数,即与源节点发射功率密切相关的R0和与环境因素相关的路径损耗指数np,当这两个参数已知时就可以获得已知位置i到源节点距离的极大似然估计
(2) |
式中, X (x, y)是源节点的坐标,(xi, yi)是已知位置的测量点坐标。
当获得m≥3个已知位置到源节点的距离时,即可利用最小二乘估算源节点的坐标。但实际应用中很多情况下路径损耗模型的模型参数是事先未知的,即不能通过路径损耗模型将测得的接收信号强度转化为距离。对此,在假定信号传播具有各向同性,即各路径上的路径损耗指数均相同的条件下,对路径损耗模型进行两次差分处理,在不考虑随机误差时可以得到:
(3) |
以式(3)的第1式为基准,进行第一次差分,消去与源节点发射功率密切相关的模型参数R0:
(4) |
再以式(4)的第1式为基准,进行第二次差分,消去路径损耗指数np:
(5) |
对上式进一步整理可得:
(6) |
此时,式(6)中不包含接收信号强度路径损耗模型的模型参数,唯一的未知参数为源节点的坐标X (x, y)。由于进行了两次差分,需保证进行接收信号强度测量的已知位置数量m≥5。上述问题为一个非线性最小二乘问题,其目标函数为:
(7) |
其中,
对此,可以采用Gauss-Newton迭代法求解源节点的坐标,其基本步骤如下。
1) 设源节点的初始坐标为X(0)=(x(0), y(0))T,并设置精度要求ε,令k=0;
2) 计算函数值fi(X(k))(i=1, 2, …, m-2),得到矩阵f(k)=[f1(X (k))…fm-2(X(k))]T,并计算一阶偏导数
3) 若‖ A(k)Tf (k)‖ ≤ε,则停止计算,X (k)为所求源节点坐标,否则求解A(k) d(k)=-f(k),得到Gauss-Newton的方向d(k);
4) 令X(k+1)=X(k)+d(k);
5) 令k=k+1,转步骤2)。
接收信号强度易受环境因素的干扰,当已知的测量点位分布不佳时,求解线性方程组A(k)d(k)=-f(k)时由于矩阵A (k)病态将导致解算结果严重偏离其真值。此时可以采用矩阵奇异值分解法(SVD)来求解广义逆以避免此问题[14]。对于任意矩阵Hm×n(m≥n):
(8) |
设Hm×n的秩为r,矩阵Hm×n的奇异值满足
(9) |
即在步骤3)中,Gauss-Newton的方向d(k)=-A(k)+f (k)。采用Gauss-Newton法求解非线性最小二乘问题的一个重要内容就是初始值的选取。在本文的双差分法中,选取位置已知的测量点的坐标加权平均作为源节点的初始位置。
2 仿真分析本文利用模拟数据对本源节点定位算法进行分析,并与同样不需要已知路径损耗模型参数的图心法、线性化法进行比较。仿真场景如图 1(a)所示,为50 m×50 m的区域,位置已知的接收信号强度测量点数量为5,分别分布在场景区域的4个角落及中心位置。在进行对比分析时,分别从不同的源节点位置、参数R0、路径损耗指数np及随机误差σdB展开讨论。
对于不同的源节点位置,其模型参数设置为R0=-30, np=3, σdB=2,将仿真区域分为1 m×1 m的格网并将源节点坐标设置在格网中心,即在2 500个位置进行源节点定位仿真。在每个位置上不同的算法运行1 000次,然后对定位误差取平均作为其定位精度。图 1(b)~(e)显示了不同算法的定位精度,其中图 1(b)是在R0、np、σdB已知的情况下基于接收信号强度的源节点定位的定位误差的克拉美劳下界(CRLB)[15],它代表了任何无偏估计的定位误差的理论下界。图 1(c)展示了图心法的定位误差,其受位置已知的测量点分布影响较大,当测量点相对于源节点分布不均匀时(如仿真区域的边缘位置),其定位误差较大。图 1(d)显示了线性化算法的定位误差,在场景中大部分区域都取得较好的定位结果,但在靠近场景4个角落的区域定位误差很大,这主要是由于此时已知位置的测量点相对于源节点的几何分布较差。同时还发现,线性化法的定位误差还与代入计算的已知测量点的顺序相关。图 1(e)是双差分法源节点定位的定位误差,图中显示该算法在整个场景区域内都有较好的定位结果,和其他算法相比有着较小的定位误差。
对于不同的模型参数R0,选取仿真场景中的(24.5, 9.5)位置采用不同的算法来定位,其他参数设置为np=3、σdB=2,保持不变。针对每个R0,不同的算法运行1 000次,然后对定位误差取平均作为其定位精度。图 2显示了不同模型参数R0下各种算法的定位误差。对于不同的模型参数R0,图心法、线性化法的定位误差及定位误差的CRLB不受影响,但图心法的定位误差较大,线性化法的定位误差接近于CRLB。而双差分法的定位误差随着模型参数R0的增大而增大,但和其他算法相比仍保持较好的定位精度。
对于不同的路径损耗指数np,同样选取仿真场景中的(24.5, 9.5)位置,采用不同的算法进行分析,其他参数设置为R0=-30, σdB=2。每种算法针对不同的路径损耗指数np运行1 000次,然后对定位误差取平均作为最后的定位精度。图 3显示了不同路径损耗指数np下各种算法的定位误差,图心法不受路径损耗指数的影响,但是其定位精度较低。定位误差的CRLB随着路径损耗指数np的增大而降低,而线性化法的定位误差虽有降低,但受路径损耗指数的影响较小。双差分法随着路径损耗指数np的增加其定位误差呈线性降低,具有较好的定位精度。
对于不同的随机误差σdB,仍然选取仿真场景中的(24.5, 9.5)位置来进行分析。路径损耗模型的模型参数设置为R0=-30, np=3。在不同的随机误差σdB下,每种源节点定位算法执行1 000次,并对所求的定位误差取平均作为最终的定位精度。图 4显示了不同的随机误差σdB下各种算法的定位误差。图心法由于与接收信号强度无关,故不受随机误差的影响,但是其定位误差较大。定位误差的CRLB随着随机误差σdB的增加而显著增加,线性化法的定位误差虽有所增大,但其受随机误差σdB的影响并不明显。双差分法的定位误差也有所增加,但是和其他算法相比其定位误差较小。
本文提出双差分源节点定位算法,能够在未知源节点的发射功率及环境路径损耗指数的情况下,通过多个位置已知的测量点对源节点的位置作出估计。它通过对路径损耗模型两次差分消去路径损耗模型的模型参数,构建一个非线性最小二乘问题,然后采用Gauss-Newton法来估计源节点的位置,并采用奇异值分解法求广义逆来防止测量误差的放大。利用仿真数据在不同的位置、参数R0、路径损耗指数np及随机误差σdB下通过与各种无需路径损耗模型参数的源节点定位算法对比分析,验证了算法具有良好的定位精度。其不足是在算法推导时假定各位置已知的测量点处的路径损耗指数相同,而实际中可能存在些许差异,这将是下一步的研究方向。
[1] |
Martin R, King A, Pennington J, et al. Modeling and Mitigating Noise and Nuisance Parameters in Received Signal Strength Positioning[J]. IEEE Transactions on Signal Processing, 2012, 60(10): 5451-5463 DOI:10.1109/TSP.2012.2207118
(0) |
[2] |
Le T, Ren P L, Hedley M. Rogue Access Point Detection and Localization[C]. IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), Sydney, 2012
(0) |
[3] |
Gu Y P, Lo A, Niemegeers L. A Survey of Indoor Positioning Systems for Wireless Personal Networks[J]. IEEE Communications Surveys and Tutorials, 2009, 11(1): 13-32 DOI:10.1109/SURV.2009.090103
(0) |
[4] |
Cheng Y C, Chawathe Y, Lamarca A, et al. Accuracy Characterization for Metropolitan-Scale Wi-Fi Localization[C]. 3rd International Conference on Mobile Systems, Applications, and Services, Seattle, Washington, 2005
(0) |
[5] |
Ouyang R, Wong A, Lea C. Received Signal Strength-Based Wireless Localization via Semidefinite Programming: Noncooperative and Cooperative Schemes[J]. IEEE Transactions on Vehicular Technology, 2010, 59(3): 1307-1318 DOI:10.1109/TVT.2010.2040096
(0) |
[6] |
Sarfraz N, Niki T. Convex Programming based Robust Localization in NLOS Prone Cluttered Environments[C]. 10th International Conference on Information Processing in Sensor Networks (IPSN), Chicago, Illinois, 2011
(0) |
[7] |
So H C, Lin L X. Linear Least Squares Approach for Accurate Received Signal Strength Based Source Localization[J]. IEEE Transactions on Signal Processing, 2011, 59(8): 4035-4040 DOI:10.1109/TSP.2011.2152400
(0) |
[8] |
Lin L X, So H C, Chan Y T. Accurate and Simple Source Localization Using Differential Received Signal Strength[J]. Digital Signal Processing, 2013, 23(3): 736-743 DOI:10.1016/j.dsp.2012.12.020
(0) |
[9] |
Vaghefi R, Gholami M, Buehrer R, et al. Cooperative Received Signal Strength-Based Sensor Localization with Unknown Transmit Powers[J]. IEEE Transactions on Signal Processing, 2013, 61(6): 1389-1403 DOI:10.1109/TSP.2012.2232664
(0) |
[10] |
Li X R. RSS-Based Location Estimation with Unknown Pathloss Model[J]. IEEE Transactions on Wireless Communications, 2006, 5(12): 3626-3633 DOI:10.1109/TWC.2006.256985
(0) |
[11] |
Koo J, Cha H. Localizing WiFi Access Points Using Signal Strength[J]. IEEE Communications Letters, 2011, 15(2): 187-189 DOI:10.1109/LCOMM.2011.121410.101379
(0) |
[12] |
Santiago M, Alfonso B, Ruben M, et al. Robust Indoor Positioning Provided by Real-Time RSSI Values in Unmodified WLAN Networks[J]. IEEE Journal of Selected Topics in Signal Processing, 2009, 3(5): 821-831 DOI:10.1109/JSTSP.2009.2029191
(0) |
[13] |
Chun S, Lee S, Nah J W, et al. Localization of Wi-Fi Access Point Using Smart Phone's GPS Information[J]. IEICE Transactions on Communications, 2013, E96B(1): 305-308
(0) |
[14] |
Lim H, Kung L C, Hou J, et al. Zero-Configuration Indoor Localization over IEEE 802.11 Wireless Infrastructure[J]. Wireless Networks, 2010, 16(2): 405-420 DOI:10.1007/s11276-008-0140-3
(0) |
[15] |
Neal P, Joshua N, Spyros K, et al. Locating the Nodes[J]. IEEE Signal Processing Magazine, 2005, 22(4): 54-69 DOI:10.1109/MSP.2005.1458287
(0) |