基于多元变量泰勒级数展开模型的定位算法

夏　斌，刘承鹏，孙文珠，李彩虹

(山东理工大学计算机学院　山东 淄博　255049)

基于多元变量泰勒级数展开模型的定位算法

夏斌，刘承鹏，孙文珠，李彩虹

(山东理工大学计算机学院山东 淄博255049)

传统Taylor级数展开模型只考虑未知节点和锚节点之间的距离，没有考虑未知节点之间的距离，定位信息不够全面，从而导致定位精度不高。为了进一步提高定位精度，该文提出了一种新的基于多元变量Taylor级数展开模型的定位算法。首先考虑未知节点之间的距离信息，建立新的基于多元变量Taylor级数展开的定位模型。然后，在对新的定位模型求解过程中，采用粒子群算法对未知节点进行定位，获得其位置的初始值。再根据加权最小二乘法求出新模型的解，作为未知节点的估计位置。最后，为评价该算法的性能，对定位结果的克拉美罗界(CRLB)进行推导。仿真结果表明基于多元变量Taylor级数展开模型的定位精度更高，定位误差接近CRLB。

物联网;多元变量泰勒级数展开;粒子群算法;定位模型

精确的节点定位是物联网位置服务应用的关键。获得了节点的准确位置信息，与位置服务应用的有关数据才有价值。因此，研究精确定位对物联网的位置服务应用至关重要[1-2]。根据测量距离建立的定位方程组多数情况下是非线性方程组，对该方程组的求解方法整体上可分为两大类：一类是非线性处理方法，将定位问题看作优化问题进行求解，如遗传算法[3]等；另一类是线性处理方法，通常利用Taylor级数展开法或其他方法[4]将非线性定位方程组变换成线性方程组后求解。与非线性处理方法相比，基于Taylor级数展开的线性方法具有求解精度高、收敛速度快等优点，成为近年来的一个热点研究。文献[5]提出了基于Taylor级数展开和到达时间的定位算法；文献[6]采用Taylor级数展开和最速下降法实现混合定位；文献[7]利用Taylor级数展开法将二次方程组线性化，实现了基于接收信号强度指示的定位等。这些工作通过不同算法与Taylor级数展开法[8-10]相结合的方式，对精确定位进行了一些有益的探索，但是并没有对传统Taylor级数展开的定位模型进行改进。该模型只考虑未知节点和锚节点的距离，没有考虑未知节点之间的距离，定位信息不够全面，从而导致定位精度不高。因此本文考虑未知节点之间的距离，建立一种新的多元变量Taylor级数展开的定位模型。在此模型的基础上，提出了一种新的定位算法。该算法充分发挥粒子群算法的群体搜索性和多元变量Taylor级数展开法的局部细致搜索性，克服了粒子群算法后期搜索效率低下和多元变量Taylor级数展开法对初始值敏感的缺陷。由于增加了未知节点之间的距离信息，该方法能有效地提高定位精度。为了评价该算法的性能，对定位结果的Cramer-Rao下界进行了推导，并通过仿真验证算法的有效性。

1　基于多元变量Taylor级数展开的定位模型

1.1传统Taylor级数展开的定位模型

考虑I个未知节点和K个锚节点随机均匀部署在二维空间中。物联网获得到达时间的测量值[11-12]，经过计算得到第i个未知节点与所有锚节点之间的测量距离：

由式(3)可得到定位模型：

利用该模型可以求出第i个未知节点的位置估计值。传统Taylor定位模型只能实现单个未知节点的定位，若要对所有未知节点进行定位，需要循环计算。

1.2基于多元变量Taylor级数展开的定位模型

通过TOA测量法可得到所有节点间的测量距离：

式中，di,j和分别表示未知节点与未知节点的测量距离和实际距离；ei,j表示距离测量误差，假设该误差服从均值为0、方差为的高斯分布。在未知节点的初始值上，对式(5)中的实际距离进行基于多元变量的Taylor级数展开并忽略二阶以上分量，有：

由式(7)可得到新的定位模型：

式中，E1为距离测量误差矩阵；Δ1为节点位置偏差矩阵；测量距离和估计距离之差矩阵D1是一个矩阵；Q1为矩阵，若D1中第q个元素为，则Q1中第q行第2i−1、2i、2j−1和2j个元素分别为，该行其余元素为0；若D1中第q个元素为，则Q1中第q行第2i−1、2i个元素分别为，该行其余元素为0。

2　基于多元变量Taylor级数展开模型的定位算法

基于多元变量Taylor级数展开模型的定位算法先用粒子群算法[15-16]计算未知节点的初始值，再根据加权最小二乘法求出其位置的估计值。具体步骤如下：

1)首先计算第i(i=1)个未知节点的初始值。

2)假设有N个粒子组成的种群，其中第n个粒子的位置和速度分别表示为。计算每个粒子的适应度值。

5)若所有未知节点都计算完毕，转向步骤6)。否则转向步骤2)，继续下一个未知节点(i=i+1)初始位置的计算。

7)利用加权最小二乘法[17]可求解出：

3　定位精度CBLB的推导

4　仿真结果和分析

4.1距离测量误差对定位误差的影响

图1给出了3种算法的定位误差随距离测量误差的方差变化的曲线及CRLB曲线。可以看出，3种算法的定位误差都随测量误差方差的增加而增加，但新算法的定位误差明显小于其他两个算法，且非常接近CRLB曲线。这是因为多元变量Taylor级数展开模型比传统Taylor级数展开模型多考虑了未知节点之间的距离信息，使定位精度得到进一步提高。此外，随着测量误差的变化，新算法的定位误差斜率小于其他两种算法，说明该算法能有效减小测量误差对定位误差的影响。

图1 距离测量误差对定位误差的影响

4.2锚节点数目对定位误差的影响

图2给出了锚节点数目对3种算法定位误差的影响。未知节点数不变时，锚节点数目的变化对定位误差有很大的影响。锚节点数越多，节点的定位误差越小。与此同时，在锚节点数目相同的情况下，新算法的定位精度在原有算法的基础上有了明显的提高。

图22σ=1.5时，锚节点数目对定位误差的影响

4.3定位误差的累积分布函数

图32σ=1时，定位误差的累积分布函数曲线图

图3给出了3种算法定位误差的累积分布函数曲线图。可以看出，在90%的累积分布点，粒子群算法、粒子群和传统Taylor级数展开结合的算法、新算法的定位误差分别在14.5、12.2和0.68 m以内，新算法具有较高的定位精度。

5　结 束 语

针对物联网定位精度不高，难以适应复杂信道环境等方面存在的不足，提出了一种新的基于多元变量Taylor级数展开模型的定位方法。该方法结合粒子群算法和多元变量Taylor级数展开法的特点，充分发挥各算法的优点，扬长避短，实现整体定位性能的最优化。通过仿真验证，新算法能有效地减少测量误差对定位精度的影响，提高定位精度。但该算法只考虑了所有距离测量信息已知的情况，部分距离测量信息未知的情况还有待进一步研究。

[1]肖竹,王东,李仁发,等. 物联网定位与位置感知研究[J].中国科学: 信息科学,2013,43(10): 1265-1287. XIAO Zhu,WANG Dong,LI Ren-fa,et al. Localization and nodes location-aware in internet of things[J].Scientia Sinica: Sinica Informationis,2013,43(10): 1265-1287.

[2]钱志鸿,王义君. 面向物联网的无线传感器网络综述[J].电子与信息学报,2013,35(1): 215-227. QIAN Zhi-hong,WANG Yi-jun. Internet of things-oriented wireless sensor networks review[J]. Journal of Electronics & Information Technology,2013,35(1): 215-227.

[3]ASSIS A F,VIEIRA L F M,RODRIGUS M T R,et al. A genetic algorithm for the minimum cost localization problem in wireless sensor networks[C]//2013 IEEE Congress on Evolutionary Computation. Washington: IEEE,2013,797-804.

[4]朱国辉,冯大政,向平叶,等. 传感器误差情况下的线性校正TOA定位算法[J]. 系统工程与电子技术,2015,37(3): 498-502. ZHU Guo-hui,FENG Da-zheng,XIANG Ping-ye,et al. Linear correction TOA localization algorithm with sensor location error[J]. Journal of Systems Engineering and Electronics,2015,37(3): 498-502.

[5]ZHENG Xiao-neng,HUA Jing-yu,ZHENG Zhi-long,et al. Wireless localization based on the time sum of arrival and Taylor expansion[C]//Proceedings of 2013 IEEE International Conference on Networks. Washington: IEEE,2013.

[6]LIU Li-chuan,MAVIDI G. A hybrid senor localization algorithm for wireless sensor networks[C]//Proceedings of 2013 IEEE International Conference on Systems,Man,and Cybernetics. Washington: IEEE,2013: 1087-1092.

[7]LIU Feng,ZHU Hao,GU Zong-hai,et al. A linear localization algorithm for wireless sensor network based on RSSI[J]. Communications in Computer and Information Science,2011,176(2): 384-389.

[8]熊瑾煜,王巍,朱中梁. 基于泰勒级数展开的蜂窝TDOA定位算法[J]. 通信学报,2004,25 (4): 144-150. XIONG Jin-yu,WANG Wei,ZHU Zhong-liang. A new TDOA algorithm based on Taylor series expansion in cellular networks[J]. Journal on Communications,2004,25(4): 144-150.

[9]张令文,谈振辉. 基于泰勒级数展开的蜂窝TDOA定位新算法[J]. 通信学报,2007,28(6): 7-11. ZHANG Ling-wen,TAN Zhen-hui. New TDOA algorithm based on Taylor series expansion in cellular networks[J]. Journal on Communications,2007,28(6): 7-11.

[10]FOY W H. Position-location solutions by Taylor series estimation[J]. IEEE Transactions on Aerospace Electronic Systems,1976,AES-12(3): 187-194.

[11]ZHANG Yan-long,CHEN Wei-dong. Nonparametric TOA estimators for low-resolution IR-UWB digital receiver[J]. Journal of Systems Engineering and Electronics,2015,26(1): 26-31.

[12]LI Y,QIAN Z,ZHAO S,et al. A research of TOA wireless sensor network localization algorithm[J]. Advanced Materials Research,2013,79(1): 1601-1604.

[13]PATWARI N,ASH J N,KYPEROUNTAS S,et al. Locating the nodes: Cooperative localization in wireless sensor networks[J]. IEEE Signal Process Mag,2005,22(4): 54-69.

[14]ALAVI B,PAHLAVAN K. Modeling of the ToA based distance measurement error using UWB indoor radio measurements[J]. IEEE communications letters,2006，10(4): 275-277.

[15]REN Xiu-li,GAO Chuan-gen,XI Yuan-hao. A node localization algorithm based on simple particle swarm optimization in wireless sensor networks[J]. Journal of Computational Information Systems,2013,9(22): 9203-9210.

[16]WEI Nuo,GUO Qiang,SHU Ming-lei,et al. Threedimensional localization algorithm of wireless sensor networks base on particle swarm optimization[J]. Journal of China Universities of Posts and Telecommunications,2012,19(2): 7-12.

[17]KAY S M. Fundamentals of statistical signal processing [M]//Volume I: Estimation Theory (v.1). Upper Saddle River: Prentice Hall,1993.

编辑叶芳

Localization Algorithm Based on Multivariable Taylor Series Expansion Model

XIA Bin,LIU Cheng-peng,SUN Wen-zhu,and LI Cai-hong
(School of Computer Science and Technology,Shandong University of TechnologyZibo Shandong255049)

Conventional Taylor series expansion model only considers the distances between unknown nodes and anchor nodes,without considering the distances between unknown nodes. As a result,the location information is not comprehensive enough to result in lower positioning accuracy. Thus,a novel localization algorithm based on multivariable Taylor series expansion model is proposed to further enhance positioning accuracy. Firstly,the new positioning model which considers the distances between unknown nodes in multivariable Taylor series expansion is established. In the process of model solution,the particle swarm algorithm is used to obtain the estimated position values of the unknown nodes. Then,the optimal position values are obtained by the weighted least squares method. Finally,the Cramer-Rao lower bound (CRLB)of the positioning result is derived to evaluate the performance of the proposed algorithm. Simulation results demonstrate that the proposed algorithm obtains a higher positioning accuracy,and its positioning error is very close to the CRLB.

internet of thing;multivariable Taylor series expansion;particle swarm algorithm; positioning model

TN911

A

10.3969/j.issn.1001-0548.2016.06.002

2015 − 05 − 27；

2015 − 09 − 28

国家自然科学基金(61473179)；山东省高校科技计划项目(J11LG24)

夏斌(1973 − )，男，博士，副教授，主要从事物联网定位方面的研究.