真三维定位算法（通用5篇）
真三维定位算法 篇1
1 引言
随着无线传感器网络 (Wireless Sensor Networks WSN) 的发展, 无线定位技术也被应用到了越来越广的领域。目标跟踪、矿下定位、医院特殊人群检测[1,2]等都用到了无线定位技术。
目前应用最为广泛的无线定位技术为GPS[3], 但由于其功耗大、成本高、对室内区域定位精度不高等原因, 就要求有低功耗、低成本, 适用用室内无线定位的技术出现。基于芯片cc2430/cc2431的zigbee定位技术就是一种满足这些要求的技术[4]。zigbee室内定位技术应用的是基于RSSI测距的定位算法。此算法要求定位节点接收多个参考节点的坐标值与RSSI值, 根据这些信息计算出自身坐标。
2 信号模型
此处采用自由空间无线电传播路径损耗模型[3] (free space pregaration model) 和对数-常态分布模型[5] (logdistance distribution) 。
自由空间无线电传播路径损耗模型:
式中:
d为距信源的距离, 单位为km;
f为频率, 单位为MHz;
k为路径衰减因子。
实际中由于环境的复杂性与节点性能的分散性, 无线电传播路径损耗与理论值并不十分吻合。对数-常态分布模型相较于上式将更加合理:
式中:
PL (d) 为经过距离d后的路径损耗单位为d B m;X0为均值为0的高斯分布随机数, 其标准差范围为4~10;k为路径衰减因子, 范围为2~4。
取d=1代入 (1) 得Loss即为, 这样可得节点接收的信号强度值为:
式中:
d为接受度到发射端的距离, 单位km;A为信号传播1m时的接收信号强度指示, 一般取45~49;pt为影响因子, 服从均值为0、标准差范围为4~10的高斯分布。
3 基于RSSI测距的三维定位算法
3.1 第一种算法[6]
设定位节点的坐标为 (x, y, z) , 接收到四个参考节点的坐标、RSSI值分别对应为:
(a1, b1, c1) , RSSI1;
(a2, b2, c2) , RSSI2;
(a3, b3, c3) , RSSI3;
(a4, b4, c4) , RSSI4;
根据公式
(把得出的RSSI值植入硬件用于计算时, 必须用绝对值) 分别计算出对应的距信源距离为d1, d2, d3, d4。列如下方程组:
令:
将 (4) 式转换为:
令:
则 (5) 式转化为:
Qθ=b
得最小二乘解:
3.2 第二种算法[4]
(1) 参考节点在原有二维坐标 (X, Y) 的前提下, 加入第三个坐标Z表示第三维, 于是参考节点的坐标变为 (X, Y, Z) ; (2) 找到离定位节点距离最近的参考节点A (X, Y, Z2) (假设此节点的RSSI值最大) ; (3) 因为A节点的RSSI值最大, 因此定位节点可以认为自己与A位于同一层, 即Z2层; (4) 定位节点选取其余2个RSSI值最大且位于Z2层的参考节点; (5) 定位节点利用选取的3个参考节点的 (X, Y, RSSI) 计算出自己的坐标; (6) 经过计算得出的定位节点坐标X, Y加上之前的Z, 就得到了定位节点的三维坐标。
根据得到的坐标值与用 (3) 式计算出的d值列方程如下:
令:ri2=di2-ai2-bi2, i=1, 2, 3
则 (6) 式可化为:
同第一种方法, 上式化为:
Qθ=b
得最小二乘解:
3.3 最小二乘算法[7]
与3.1一样, 根据定位节点自身坐标与接收到的参考坐标信息列如下方程组:
令:
ri2=di2-ai2-bi2-ci2, i=1, 2, 3, 4
前三个方程分别去减第四个方程, 则 (7) 式可化为:
令:
则 (8) 式可化为:
Qθ=b
得最小二乘解:
3.4 RSSI值的均值估计[8]
由于信号在传播过程中受到各种因素影响, 从而导致定位节点接收到的RSSI值存在很大的随机误差, 从而影响定位精度。要进一步提高定位精度, 便要对接收到RSSI值进行滤波, 从而到达降低随机误差的目的。此处, 对接收到的RSSI进行均值估计。设定位节点接收到同一个参考节点的m个RSSI, 对这些值进行均值估计:
代入 (3) 式得:
根据 (9) 式得出的距信源距离:
4 实验数据
用matlab对上述算法进行仿真比较, 得实验数据如下。
4.1 图4.1是第一种算法对RSSI值进行均值估计滤波前后的实验数据对比
由图1可以看出, 对RSSI值进行均值估计滤波后, 定位精度有非常明显的提高。
4.2 图2是第一种算法与第二种算法的实验数据对比
由图4.2可以看出, 第二种算法的误差波动范围较第一种方法小, 也就是说第二种算法定位的精度比第一种算法高。但是, 如果第二种算法在第 (2) 步时出错, 则将导致第三维的定位完全错误, 但第一种算法则无此风险。
4.3 图3是一种算法与最小二乘法的实验数据对比
由图3可以看出, 第一种算法定位精度要比最小二乘法定位精度稍高。
综合4.2与4.3可以看出, 第一种算法在此三种算法中可信度是最高的。4.2与4.3实验数据对比均是在对接收到的RSSI值进行完均值估计的基础上进行的。
5 结束语
本文给出了三种基于RSSI测距的室内三维定位算法, 得出实验数据对比。并且基于此, 给出了一种对接收的RSSI值进行估计滤波的方法——均值估计。通过数据对比, 可以看出, 均值估计滤波后, 定位精度明显提高。作者相信, 在定位要求越来越普遍的今天, 基于RSSI测距的定位算法一定可以得到更广泛的应用, 定位精度也会随着技术的改进越来越高。
摘要：RSSI算法是一种被广泛使用的无线定位算法。定位节点根据接收到的参考坐标值与对应的RSSI值进行计算得出自身坐标。区别于平面定位, 提出了三种基于RSSI测距的三维定位算法。第一种与第二种算法运用矩阵求解二元二次方程组得出定位节点坐标, 第三种方法为最小二乘法。并且, 给出了一种关于RSSI值的均值估计滤波法。最后给出三种算法仿真定位精度比较。
关键词：RSSI,三维,室内定位,均值估计
参考文献
[1]SOHRABI K., GAO 1., AILAWADHI V..Protocols for self-organization of a wireless sensor network[J].IEEEPersonal Communications, 2000, 7 (5) :16-27.
[2]WOO-CHOOL PARK, MYUNG YOON.The Implementation of Indoor Location System to Control Zig Bee Home Network.SICE-ICASE International Joint Conference 2006[C], Korea:Yatap Dong, 2006:2158-2161.
[3]ELLIOTTOTT D.KAPLAN, CHRISTOPHER J.HEGARTY.GPS原理与应用.第二版[M].寇艳红译.北京:电子工业出版社, 2007.
[4]TI.CC2431 Location Engine[OL].http://www.ti.com
[5]张洁颖, 王侠.基于RSSI与LQI的动态距离估计算法[J].电子测量技术, 2007, 30 (2) :142-145.
[6]朱浩, 顾宗海等.一种基于交点质心求解的RSSI定位算法及其优化[J].郑州大学学报工科版.2010, 31 (6) :43-46.
[7]熊小华, 何能通.无线传感器网络节点定位算法的研究综述[J].机电工程, 2009, 26 (2) :14-17.
[8]张贤达.现代信号处理.第二版[M].北京:清华大学出版社, 2002:49-59.
真三维定位算法 篇2
关键词：WSN,三维定位,RSSI,估计位置过滤,DBSCAN
1 引言
随着物联网技术的迅猛发展,无线传感网络(WSN)迅速成为21世纪最具影响力的技术之一[1],由于无线传感网络综合了传感技术、网络传输技术、无线通讯技术、无线定位技术、数据融合技术、嵌入式技术等多种技术,使得WSN成为当今研究的热点。而无线传感节点的定位是支撑无线传感网络的核心技术[2],在目标定位、目标跟踪、地理信息获取等方面发挥着巨大作用,因此对无线传感网络定位算法的研究具有重要的意义。
目前,无线传感网络定位在二维平面中的应用已非常成熟,但随着社会的发展,三维定位需求日益成明显,三维定位使得传感器节点呈现出立体分布,而非平面分布的特点,因此在平面上的定位算法已不能满足空间场景的定位需求。为了解决上述问题,人们提出了基于三维的节无线传感网络定位算法。无线传感器网络中的定位方法较多,可以根据数据采集和数据处理方式的不同来进行分类。在数据采集方式上。算法根据需要对采集的数据有所侧重,比如角度、时间、周围节点信息等,其目的是采集与定位相关的数据。在数据处理方面,不管数据时被自身节点处理还是上传到其他设备上处理,其结果是将数据转换为定位坐标,从而完成定位。其中依据距离测量与否算法可划分为两大类:基于测距的定位和与距离无关的定位。目前,在测距的定位算法中基于接收信号强度(RSSI)的定位是研究的热点。相对于与距离无关的定位方法,基于RSSI的定位方法增添了额外的通信链路质量信息,并且获取简单,对于定位精度的提高具有一定的作用。
RSSI通过比较发射结点发送信号强度和接收结点接收信号的强度,再考虑信号在传播过程中的损失,使用理论或者经验的信号传播模型将传播损耗转化为发送节点和接收节点的距离[3]。在实际应用环境中,由于复杂的环境中的多径干扰,非视线关系等因素,该方法的定位精度不高。但由于这种基于RSSI的测距技术,具有方法简单、成本低、效率高、设备少、距离远等优点,因此,许多定位算法都结合了RSSI技术[4]。
2 相关研究
基于RSSI理论的研究已经比较成熟,根据无线电传播理论,无线电信号在传播过程中会有能量损耗,这种损耗与无线电传播路径相关,测距模型正是基于这种相关性从而得出待测节点到参考点之间的距离,在实际环境中,由于多径衰落、反射以及扰射、不规则传播等因素,使得模型比较复杂,同时使得定位误差较大。目前普遍使用的统计模型[5]如下:
式1中d为距信号源的距离,单位一般为km;d0为参考距离,P(d)为在距离d处的信号强度值,np为路径衰减因子,一般取值为2~4,环境不同取值不同。室内环境通常取1.4~1.8,P0是在参考距离d0处的信号强度(d Bm)。由于式1参考模型的理论环境与复杂的实际环境有较大的差别,使得无线电传播路径损耗在一定的程度上与理论值相比并不吻合,这就使得实际测量存值存在误差。通常基于RSSI技术的定位机制使用各种算法来减少测距误差对定位的影响,其中包括多次测量、循环定位求精等算法。
由于无线传感网分布的地理位置及环境复杂多变,无线信号会受到环境的各种因素影响,导致接收节点接收到的信号,并不是全部对定位有帮助,有时会增大误差,所以对接收的信号进行预处理就显得很有必要了。通过RSSI距离模型可知,当未知节点距离锚节点越近,接收到的RSSI值波动越小(最大值和最小值之差越小),说明由RSSI值计算得到的距离越接近实际距离。当未知节点距离锚节点越远,由于实际环境的多径效应使得测得的RSSI值波动变大,导致误差也大。为了消除较大波动值对定位的影响,我们首先将周围锚节点的RSSI值聚集起来形成一个数据集,并且从大到小排好序。数据集形式如下:
我们从数据集中选取RSSI值较大的锚节点,进行多次RS-SI值采集,记录,结合高斯滤波模型,舍去波动较大的RSSI值,最后对于收集到的N个该锚节点RSSI值取算数平均数作为该锚节点的最终RSSI值。表达式如下:
在进行定位时,如果待测节点与锚节点的距离已知,则至少需要4个不位于同一个平面内的参考节点才能唯一确定待测节点的坐标值,否则无法进行定位[6]。我们假设这4个锚节点的坐标为Pi=(xi,yi,zi),i=1,2,3,4;待测节点到4个锚节点的距离为di,i=1,2,3,4,根据三维空间两点间距离公式有:
方程组中四个方程三个未知量,那么就可以确定未知节点N(x,y,z)的坐标:
根据以上理论基础,许多学者对三维定位方法做了深入的研究。例如,文献[7]提出了坐标四面体质心定位算法,该算法比传统算法定位精度要高。文献[8]提出了一种利用四面体质心算法替换三维APIT算法的网格扫描法。文献[9]提出了一种基于多次测量提高定位精度的思想等。但是目前的这些研究对于由客观或主观因素会产生不可靠数据的情况,都未涉及,因此,本文提出一种基于估计位置进行过滤的改进定位算法。
3 基于估计位置过滤的改进定位算法
3.1 估计位置过滤
在三维空间定位过程中通常需要布置较多的锚节点,所以对于某个待定节点周围存在多个1跳参考点,由相关研究的理论可知对于任意四个锚节点都能计算得到一个估计位置,所以在计算的结果中会有多个估计位置,譬如,当周围环境中有10个锚节点时,取其中4个作为参考节点,那么就会有C410=210种取法。对于位置的估计,由于存在一些主观因素和客观因素,如选取节点不合理、数据传输错误等。存在某些明显已知的错误,使得这些估计位置对定位精度影响较大,所以对这些位置需要屏蔽过滤,以提高定位精度。对于多组估计位置,如果很多估计位置比较集中,而少数估计位置距离群体比较远,则可以认为这几个少数位置是不可靠的,因此可以剔除掉,其他的位置则认为是可靠位置点。如图1所示,假如对一个位置估计得到如下六个估计位置(A,B,C,D,E,F),由图中可以看出A,B,C,D,E五个位置较为集中,而F这个位置距离群体较远,如果将这六个点求平均值作为未知节点的最终估计位置的话,会造成误差较大,因此将F剔除,仅对A,B,C,D,E五个点进行算术平均运算,结果作为未知节点的估计位置。
其中对于只有两个估计位置的点不采取位置过滤,取这两个估计位置连线的中点作为节点的最终估计位置。
对于估计位置较多的,本文采用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法,DBSCAN[10]算法是一种基于密度的聚类算法[11,12],它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪声的空间数据库中发现任意形状的聚类,所以该算法可以有效识别噪声,即不可靠位置。
DBSCAN具体算法描述如下:
(1)检测数据库中尚未检查过的对象p,如果p为被处理(归为某个簇或者标记为噪声),则检查其邻域,若包含的对象数不小于,建立新簇C,将中所有点加入C;
(2)对C中所有尚未被处理的对象q,检查其邻域,若中至少包含个对象,则将中未归入任何一个簇的对象加入C;
(3)重复步骤2),继续检查C中未处理的对象,知道没有新的对象加入当前簇C;
(4)重复步骤1)~3),直到所有对象都归入了某个簇或标记为噪声。
输入数据:数据对象集合,半径,密度阈值
输出数据:聚类C
从算法中我们可以看出DBSCAN算法通过检查数据库中每个点的Eps-邻域来寻找聚类。如果一个点P的Eps-邻域包含多于Min Pts个点,则创建一个以P作为核心对象的新簇。然后,DBSCAN反复地寻找从这些核心对象直接密度可达的对象并加入该簇,直到没有新的点可以被添加,该过程结束。
由于该算法可以有效地去除噪声即不可靠数据,因此DB-SCAN算法能够很好的应用到空间位置过滤中去除空间不可靠数据。
3.2 改进后的定位算法
1)锚节点周期性发送自身信息:节点ID、自身位置信息。
2)待测节点接收其通讯范围内的所有节点的信息,并记录他们的RSSI值,建立从大到小的RSSI数据集,选取通讯RSSI值较大的锚节点进行多次通讯测值,并运用高斯滤波,舍去波动较大的RSSI值,得到N组RSSI值取其算术平均值:
作为该锚节点的最终RSSI值。
3)如果未知节点接收到的锚节点的个数N<=3,则执行5)。否则随机选择一组锚节点组成四面体,并根据三维APIT算法判断未知节点是否在四面体中。如果不在则舍弃,如果在则记录这组锚节点并重复该过程,直到选取次数大于一个阀值M。
4)由3)得到四面体后,运用四边测量算法来对集合中的所有组合计算坐标位置。对计算得到N组坐标值过滤,对于只有两个估计位置的点不采取位置过滤,取这两个估计位置连线的中点作为节点的最后估计位置。对于估计位置较多的点,采用DBSCAN算法,选取集合最大的所有数据进行计算平均值作为最终坐标估计值。
5)若未知节点接收到的锚节点个数N<=3或者四面体集合为空,则对所有锚节点采用RSSI均值加权质心算法来进行未知节点估计。对于接收到P个锚节点信号,相应的RSSI的值为R1,R2,...,Rp,则第i个锚节点的加权系数为,那么RSSI均值加权算法估计坐标为:
具体定位算法的流程如图2所示:
3.3 定位误差
定位误差公式:
其中,(xi,yi,zi)为未知节点的估计坐标,(x0,y0,z0)为未知节点的实际坐标。N个未知节点的平均定位误差为:
4 仿真试验
为了比较本文改进的定位算法和传统定位算法的性能,利用MATLAB建立了一100m×100m×100m的仿真环境,锚节点均匀地分布在这个范围内,在数据中添加方差为20、均值为3的随机噪声,用来模拟现实环境的影响。500个定位结果是在相同的环境下运行50次试验的平均值,部分区域仿真结果对比如图3、图4所示:
由图3和图4的仿真结果对比可以看出,由于在实际应用的环境中会出现节点异常或者环境异常带来的不可靠数据,会对系统定位精度产生影响,我们通过对采集的RSSI值过滤和估计位置进行过滤,定位结果要比未进行位置过滤和RSSI值高斯过滤的误差要小,提高了定位精度。
如图5所示,在锚节点小于10个的时候本文算法定位精度明显优于传统算法,这是因为锚节点较少时环境误差对定位精度影响较大,造成了传统算法的定位不精确,而本文所提出的改进算法具有明显的优点。但随着锚节点个数的增加两种算法的精度都在不断提高,这是因为随着锚节点的增加,由于最后取几何均值使得环境误差数据对总的定位结果影响较少,所以定位精度就得到了提高。
图6给出的是定位误差随通讯距离变化的趋势。由图中可知随着通讯距离的增加,传统算法和本文算法的定位误差都减小。因为增加节点的通讯距离后,会使距离估计更加接近节点间的欧氏距离。
由以上结果分析可知,在定位过程中节点的噪声数据会影响定位的精度,本文在质心定位算法的基础上先通过对RSSI值进行高斯过滤从而优化了采集的RSSI值,保证了入口数据的准确性和稳定性。然后对计算结果进行基于DBSCAN算法的估计位置过滤,通过仿真结果可以看出该算法有效的减少了不可靠数据对定位的影响,提高了定位精度。
4 总结
本文在研究了传统的三维定位算法的基础上,提出了一种估计位置过滤算法。该算法通过高斯过滤模型对采集的RSSI的值进行过滤得到稳定的RSSI值,然后对待定位的节点进行估计位置过滤,去除了在定位过程中由于主观或者客观因素带来的不可靠位置,减少了其对定位精度的影响。文章通过仿真对比了本文算法和传统算法在定位精度上的优劣,由对比结果可知本文算法在定位精度上有了明显的提高,能够有效的减少实际应用中随机噪声对定位的影响,该算法在三维定位中有着较大的应用潜力。
参考文献
[1]SUOMELA J.Computational complexity of relay placement in sensor networks[J].Lecture Notes in Computer Science,2006,3831:521-529.
[2]KIM S,KO J G,YOON J,et al.Multiple-objective metric for placing multiple base stations in wireless sensor networks[A].Proc of the 2rd International Symposium on Wireless Pervasive Computing[C].Pis-cataway,USA,2007:627-631.
[3]Zhang Jie,Wu Ling-xi,Tang Zhi-jun.Ranging Method and Accuracy Analysis Based on RSSI of Wireless Sensor Network[J].Telcommunication Engineering,2010,50(4):83-87
[4]WU Jie,FENG Feng,DING Zhi-yi Research on coal mine underground localization algorithm based on integration of RFIDand WSN[J].Computer Engineering And Design.2014(7):2278-2282.
[5]SHEN X,WANG Z,JIANG P,et al.Connectivity and RSSIbased localization scheme for wireless sensor networks[J].Lecture Notes in Computer Science,2005,3645(2):578-587.
[6]Laitinen E,Lohan E S,Talvitie J,et al.Access point significance measures in WLAN-basedlocation[C]//Positioning Navigation and Communication(WPNC),2012 9th Workshop on.IEEE,2012:24-29.
[7]Chen Hong-yang,Huang Pei,Martins M.Novel Centroid Localization Algorithm for Three Dimensional Wireless Sensor Networks[C]//Wi COM'08 4th International Conference on Wireless C'ommunications,Networking and Mobile Computing.2008:1-4
[8]Liu Zhuang,Fang Zhi-yi,Ren Nai-ji.A New Range-Free Localization Algorithm Based on Annulus Intersection and Grid Scan in Wireless Sensor Networks[J].Journal of Information and Computational Science,2012,9(4):831-841
[9]VIANI F,LIZZI L,ROCCA P,et al.Object tracking through RSSI measurements in wireless sensor networks[J].Electronics Letters,2008,44(10):653-654.
[10]ESTER M,KRIEGEL H,SANDER J,et al.A den-sitybased algorithm for discovering clusters in largespatial databases with noise[C]//Proc of the 19962nd Int'l Conf on Knowledge Discovery and Data Mining.Portland:AAAI Press,1996:226-231.
[11]QIAN Wei-ning,GONG Xue-qing,Ao Ying-zhou.Clustering in very large databases based on distanceand density[J].Journal of Computer Science and Technology,2003,18(1):67-76.
真三维定位算法 篇3
由于井下煤矿工作环境的特殊性, 各种自然因素都威胁着井下人员的生命安全, 实时掌握井下人员的位置信息是一项有效的监管措施, 不仅有利于日常井下人员地理位置信息的管理, 而且在矿难事故发生时更有利于救援工作的进展。目前的井下人员定位的计算大多数局限在二维平面上, 而实际井下工作环境是一个三维空间, 特在三维空间中对定位参考的节点位置进行了分析, 并运用BFGS算法提高了定位精度。
1 三维定位的原理
目前普遍使用的井下人员定位方法是采用了基于Zigbee协议的无线传感器网络的接受信号强度RSSI定位算法, 通过RSSI的测距技术可以计算出未知节点与参考节点的距离。RS-SI测距的工作原理是已知发射节点的发射信号强度, 由于信号在传输过程中要损耗, 在接收节点测量出接受到的信号强度, 根据无线信号衰减模型 (如式 (1) 所示) , 计算出发射节点到接收节点之间的距离[1]。
其中:d:发射节点与接收节点之间的距离, d0为参考距离, 单位m;P (d) :距离发射端d处的移动节点接收到的信号强度值, 单位d Bm;P (d0) :距离发射端d0处的移动节点接收到的信号强度值, 单位d Bm;λ:路径衰减指数, 与环境有关;X:平均值为μ, 标准偏差为δ2的随机变量, 服从N (μ, δ2) 的高斯分布随机变量, 一般μ=0。
设三维空间中任意不同的n个参考节点的坐标分别为S1 (x1, y1, z1) , S2 (x2, y2, z2) , …, Sn (xn, yn, zn) , 未知节点P的坐标为 (x, y, z) , 点P到第1个、第2个、…、第n个参考节点的距离分别为d1, d2, …, dn, 通过已知节点可以确定未知节点P的坐标, 如图1所示。
根据空间两点间距离公式有:
化简方程组式 (2) , 可得到非齐次线性方程组:
令:
则有AX=b。
(1) 当n个参考节点位于同一个平面内, 矩阵A的某一列全为0, 矩阵A的秩r (A) =2, 增广矩阵[A, b]的秩r ([A, b]) ≥r (A) 。根据d1, d2, …, dn取值的不同, 若:
r ([A, b]) =r (A) =2时, 方程组式 (2) 有无穷多解;r ([A, b]) >r (A) 时, 方程组式 (2) 无解。故不能确定P点的坐标。
(2) 当n个参考节点位于不同的平面内, r (A) =3, 当r ([A, b]) =r (A) =3时, 方程组式 (2) 有唯一解。
此时方程组式 (2) 至少需要3个方程, 即n-1=3, n=4, 即在三维空间的定位计算中, 至少需要4个位于不同平面内的且已知坐标的参考节点才能计算出一个未知节点的坐标。
用标准最小二乘法可以得到P的坐标为:
2 参考节点的选择算法
由文献[2]可知, 在二维平面对未知节点定位过程中, 当三个参考节点组成等边三角形时, 定位误差最小, 此时参考节点的配置方法即为最优配置。将此结论应用到三维空间的定位中。在三维空间设置参考节点时, 必须考虑到在水平平面和竖直平面中都要有参考节点能组成等边三角形。将井下巷道模拟成一个长方体, 需要在顶部和巷道的两侧设置参考节点才能对未知节点定位。考虑到硬件成本, 尽量使用较少的参考节点, 参考节点设置方法如图2所示 (图中的数字表示每个参考节点的编号) 。
由图2可知, 共设置了7个参考节点, 参考节点1、2、3;4、5、6和1、4、7可以分别组成等边三角形, 此设置方法确保了水平平面和竖直平面都有等边三角形。在实际工程应用中, 可以根据需要和定位精度的要求增加参考节点, 以便在水平平面或竖直平面有更多的等边三角形, 通过多次测量计算求平均值的方法来确定待测节点的坐标值。
如图2所示, 以A点为坐标原点, AB→为x轴的正方向, AD→为y轴的正方向, A'→A为z轴的正方向, 可以根据实际情况设置参考节点的位置。
选择了能形成等边三角形的3个参考节点后, 只要与这3个参考节点不共面的参考节点均可作为第4个参考节点。但是第4个参考节点的位置会影响着定位精度。使用4个参考节点对未知节点P进行坐标计算时, 有方程组:
方程组的解 (x, y, z) 与选择的4个参考节点的坐标有关, 而测距后d1、d2、d3、d4即为确定值。因此, 需要研究在测距误差存在的情况下, 参考节点坐标对定位计算的影响。
由文献[10]可知, n阶线性方程组AX=b, 如果系数矩阵A或右端项b的微小变化, 会引起方程组的解的很大变化, 则称该方程组为病态方程组, 常用条件数k (A) 判定线性方程组AX=b的病态程度。由方程组式 (4) 可知, d1、d2、d3、d4存在着测距误差, 即b存在着误差Δb。当测距误差一定时, 即Δb一定时, k (A) 越大, 方程组AX=b的解x的误差Δx也越大。因此, 第4个参考节点的坐标值将直接影响着系数矩阵A的条件数k (A) 。
条件数的计算方法如下:k (A) =‖A‖‖A-1‖, 一般使用谱范数,
从条件数的计算公式可知:k (A) 与系数矩阵A有关, 即与所选择的4个参考节点的坐标值有关。综上论述, 参考节点的选择算法如图3所示。
如图2所示, 选择4个不同的参考节点组成的线性方程组的条件数如表1所示, 从而可以确定出第4个参考节点的编号 (表1中选择的第4个参考节点用红色标注) 。
3 BFGS算法减小定位误差
3.1 BFGS算法的原理
考虑到测距误差的影响, 需要用BFGS算法进行优化。
对于无约束最优化问题:minf (x) , x∈Rn, f (x) 是二阶连续可微函数。假设xk是其极小点x*的一个近似值, 将f (x) 在xk点展开成泰勒级数, 有:
其中。
式 (5) 的近似梯度可表示为:
该近似函数的极小点需要满足:
当f (x) 是二次函数, H是常数矩阵时, 由任意一个xk计算, 使用式 (8) 立即可得到f (x) 的极小值x*。
当f (x) 不是二次函数时, 式 (5) 仅是在极小点xk附近的近似表达。取-Hk-1gk作为搜索方向, 即:
按照式 (9) 求函数f (x) 的极小点的方法称为Newton法, -Hk-1gk为f (x) 在xk点的Newton搜索方向。在无约束条件求极值的各种算法中, Newton方法迭代次数最少, 且具有二次收敛速度。但是运用Newton法计算过程中, 需要计算二阶导数矩阵及其逆矩阵, 不仅计算量大, 且存在着误差, 从而导致Newton法无法在实际工程中得到应用, 需要进行修正。
拟Newton法的基本思想是构造一个矩阵Hk%, 用于逼近二阶导数矩阵Hk-1。DFP (Davidon-Fletcher-Powell) 算法由Davidon提出, 由Fletcher和Powell作了改进, 其修正公式为:
其中sk=xk+1-xk, yk=gk+1-gk。但运用DFP算法计算过程中, 由于计算误差的积累会导致某次迭代中Hk变成奇异矩阵, 从而导致计算终止, 因此还是要对其算法进行修正。
1970年Broyden、Fletcher、Goldfarb和Shanno四人共同提出了对DFP方法不足进行修正的式 (11) , 即为著名的BFGS算法[3]。BFGS算法是一个拟牛顿方法, 具有二次终止性, 整体收敛性和超线性收敛性。在进行计算时, Hk不易出现奇异, 具有广泛的使用性。
其中。
3.2 定位问题的应用
由第2节分析可知, 实际工程应用中需要将定位问题表述为最优化问题, 由于测量参考节点与未知节点之间的距离时有存在着测距误差, 测距模型为AX+N=b, 要求误差N尽可能得小, 则min N=min (b-AX) , 定义优化模型为:
其中:
BFGS的定位算法如下:
(1) 给定初始点x0, 初始矩阵H0, 控制误差ε, 计算g0, 令k=0;
(2) 令pk=-Hkgk;
(3) 由精确一维搜索确定步长αk, f (xk+αkpk) =αm≥in0f (xk+αpk) ;
(4) 计算xk+1=xk-αkHk-1gk, gk+1=f (xk+1) , 若‖gk+1‖≤ε, 则说明本次迭代计算得到的xk+1已经符合了所规定的误差的要求, 停止迭代并输出计算结果, 即近似解为x*=xk+1, 否则执行步骤 (5) ;
(5) 令sk=xk+1-xk, yk=gk+1-gk, 计算wk;
(6) 根据BFGS修正式 (11) 计算Hk%+1, 令Hk+1=Hk%+1, k=k+1, 转步骤 (2) 。
在本次定位计算中, 首先选择一组4个参考节点, 然后测距得到d1、d2、d3和d4, 再进行BFGS算法进行优化。再选择其他一组的4个参考节点, 重复上述步骤, 将多次计算出的结果求其平均值。
4 仿真结果
使用Matlab软件在三维区域100 m×10 m×5 m的空间内, 分别使用最小二乘法、DFP算法和BFGS算法对未知节点进行定位仿真, 用平均误差作为衡量各种算法性能的标准。仿真结果如图4所示, 横轴表示参与定位计算的参考节点的个数, 纵轴表示平均误差。结果表明:在参考节点个数相同的条件下, BFGS算法的误差比DFP算法和最小二乘法都小, 并且具有更好的数值稳定性。
5 结语
本文重点研究了参考节点的设置对未知节点的影响, 并且用BFGS算法对定位结果进行优化。BFGS算法比最小二乘算法和DFP算法误差小, 有很好的定位功能, 更适合应用于工程计算中。
参考文献
[1]孙迎春.基于ZigBee技术的井下人员定位系统设计[D].哈尔滨:哈尔滨理工大学, 2011.
[2]Guangjie Han, Choi D, Lim W.A novel reference node selection algorithm based on tri-lateration for indoor sensor networks[C]//Seventh International Conference on Computer and Information Technology, 2007:1003-1008.
[3]Li D H, Fukushima M.A modified BFGS method and its global convergence in non-convex minimization[J].Journal of Computational and Applied Mathematics, 2001, 129 (1) :15-35.
[4]Coluccia A, Ricciato F.On ML estimation for automatic RSS-based indoor localization[C]//2010 5th International Symposium on Wireless Pervasive Computing (Iswpc) , 2010:495-502.
[5]Liang Jianlin, Shao Jun, Xu Ying, et al.Sensor network localization in constrained 3-D spaces[C]//Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation.Luoyang, Henan, 2006:49-54.
[6]孟祥忠, 宋保业.无线传感器网络HWC定位算法[J].计算机工程, 2009, 35 (7) :104-106.
[7]黄天祥.无线传感器网络节点自定位技术研究[D].南京:南京航天航空大学, 2008.
[8]宋玉梅.无线传感器网络节点定位技术研究与实现[D].成都:电子科技大学, 2008.
[9]John A Stankovic.Wireless Sensor Networks[R].Department of Computer Science University of Virginia.June 19, 2006.
真三维定位算法 篇4
煤矿井下环境特殊,是事故高发区,对井下进行监控,特别是对位置信息的监控非常必要。
根据定位机制的不同,可以将无线传感器网络定位算法分为2类,即基于测距(Range-based)的定位算法和基于非测距(Range-free)的定位算法[1,2,3]。 目前在煤矿井下定位方面的研究已经有很多成果。 参考文献[4]提出了一种3DL-RD煤矿井下无线传感器网络节点三维定位算法。该算法是在巷道内构建三维坐标系,得到成对信标节点的坐标,并通过RSSI(Received Signal Strength Indication,接收信号强度指示器)测距方式得到信标节点到未知节点的距离。随后通过坐标投影,将信标节点投影到与位置节点同一高度的水平面上,然后利用三边测量法得到未知节点的平面坐标,通过相应的转换得到未知节点的三维空间坐标。这种算法能够得到比较高的定位精度,但却忽略了巷道顶部凹凸面对定位精度的影响,会导致对顶部微弧部位的节点位置估计出现较大的偏差。由参考文献[5]可知,RSSI值在15m之外的变化范围并不明显,因此,RSSI值只能稍微修正定位的结果,并不能很大程度上改善定位精度。参考文献[6]提出了一种最小二乘定位算法,对最小二乘法在煤矿巷道导航中的应用进行了较深入的研究,推导出了最小二乘定位算法和源选择算法,建立了最 小二乘平 滑滤波器,对TOA (Time of Arrival,到达时间)测距进行平滑过滤,消除了噪声,提高了定位精度。这种算法是通过对噪声的处理来实现定位精度的提高,但其得到的定位精度还是难以满足实际需求。
关于TDOA(Time Difference of Arrival,到达时间差)和AOA(Arrival of Angle,到达角)的混合算法目前已经有人做了大量的工作[7,8,9,10,11],但是其在煤矿方面的应用却非常少,主要是因为煤矿井下环境特殊,需要考虑井下的实际情况,并对基站的布置方法有要求。本文根据煤矿井下特殊的环境,结合基站布置方法,提出了一种基于TDOA和AOA的煤矿井下三维定位算法。该算法与3DL-RD算法、 最小二乘定位算法相比能够最大程度消除测量值中的噪声干扰与随机误差,从而实现良好的定位效果。 仿真结果证明了该算法的准确性。
1TDOA与AOA定位方法
1.1TDOA方法
设未知节点MS的位置为(x,y,z),第i个基站BS的位置为(xi,yi,zi)(i=1,2,3,…,n),在Chan算法的基础上,根据基站BS测量的电波传播时间 τi可建立BS和MS两者之间的距离方程[12]:
式中:c为电波传 播速度;Ki=xi2+yi2+zi2(i=1, 2,…,M,M为传感器基站BS的数目)。
当以基站1为基准 , 计算ri , 1=ri-r1时 , 式 ( 1 )可改写为
式中:xi,1=xi-x1;yi,1=yi-y1;zi,1=zi-z1。
未知节点与2个基站之间的到达时间差方程为
当考虑观测误差时,则有
式中:nΔti,1为观测误差。
1.2AOA方法
AOA测量模型如图1所示。
基站能够提供的未知节点的角度信息为方位角 θ0和俯仰角Φ0,根据图1可构建节点坐标与角度信息之间的关系方程为[13]
考虑到测量中的角度误差nθ,n,则得到的角度信息为
根据图1可得
其中:
综合式(7)—式(9) 可得
假设角度测量误差nθ,n很小,则有sin nθ= nθ,sin n=n,则式(10)可以转换为
2井下定位模型
煤矿井下巷道内的定位需要结合巷道模型以及井下巷道实际情况,因此,本文首先对井下定位模型进行分析。煤矿井下巷道基本是狭长型的,顶部存在微弧形或者侧面存在少许的凹凸,以往的节点布置方法都是将巷道近似地考虑成长方体,并将巷道进行区域划分,将信标节点部署在长方体的边棱上且成对放置,即每对信标节点的X,Y轴坐标相同, 只有Z轴坐标不同,如图2所示。
煤矿巷道中的监测信息主要为瓦斯浓度、温湿度等,而巷道顶部是瓦斯监测的重点部位,因此,需要在巷道的弧顶部位布署相当数量的节点。传统的节点布置中将巷道近似为长方体,这会导致对顶部微弧部位的节点位置估计出现较大的偏差。
本文提出了一种新的基站节点布置方法,将煤矿巷道进行区域划分,在保证所有未知节点与基站在小区域内的通信在一跳距离内的情况下,尽量扩大区域范围。随后将基站节点布置在交互 对角线上,并在每个区域空间的弧顶中间部位布置一个基站,这样在小区域 空间就布 置了5个位置已 知的基站。
本文的这种布置方法首先将定位区域进行细化,在该区域内保证节点之间的通信距离在一跳之内,减少由于多跳产生的误差,保证了基站提供的未知节点信息的准确度。同时,由于在此区域内布置了3个基站,保证了基 站的数目。这样通过 上面2个步骤即能在小区域内对未知节点进行较精确的定位。三维空间基站布置方式及剖面如图3所示。
图4给出了其中一个区域内的基站分布,在其中取任一未知节点,设其坐标为(x,y,z)。本文中将根据该模型进行仿真,并对本文算法进行验证。
3基于TDOA和AOA的定位算法
结合本文提出的井下定位模型,基站1放置在坐标原点处,即(0,0,0),取空间中另一位置的基站坐标为 (xi,yi,zi)(i=2,3,4,5)。 根据式 (2) 可得[13-17]
式中:r21=x2+y2+z2;ri2=(xi-x)2+(yi-y)2+ (zi-z)2。
对式(13)进行整理后得
式中 : Ki=x2i+y2i+z2i。
考虑到测量噪声的影响 , 可将式 ( 14 ) 写成 :
式中 :; X为未知节点的坐标信息 ;
式(15)即为利用TDOA方法得到的节点定位矩阵方程。
同样,根据本文提出的定位模型和 假设,结合式(11)可得坐标原点处的基站角度信息为
式(16)可写成向量的形式:
式(17)为通过AOA算法得到的节点定位矩阵方程。
通过观察可以发现,根据2种信息得到的节点定位矩阵方程具有相同的方程结构,因此,可以将2个矩阵方程组进行合并处理,得到
式(18)为2种信息共同组成的节点定位矩阵方程,通过对式(18)的处理可以得到未知节点的坐标信息为
4仿真试验
为了对基于TDOA和AOA的三维定位算法进行性能评估,本文进行了模拟仿真试验。根据上文中提出的煤矿井下定位模型,取节点的通信半径为30m,为保证所有节点的通信在一跳之内,将仿真模型设计为一个长为20m、宽为5m、顶部边缘高度为5m、中心高度为6m的不规则长方体三维空间。试验中各基站的位置如图5中所示。其中, 基站1的位置为(0,0,0),为基准点。其余基站的坐标为(5,0,5),(0,20,5),(5,20,0),(2.5,10,6),并从限定区域内随机选择5个未知节点。
为了验证基站数量对定位精度的影响,分别取基站数为3、4、5,对5个未知节点进行定位。对比5个未知节点在这3种情况下的平均定位精度。不同基站数目时本文定位算法对定位精度的影响曲线如图6所示。从图6可以看出,在小区域内随着基站数目的增加,未知节点的定位精度都在逐步提高, 并且都在节点为5个时实现最高定位精度。本文中基站数量有限,但是实现的定位精度较高,因此,验证了本文定位算法和模型是非常符合煤矿井下的定位要求的。
为了验证在TDOA算法中混合AOA算法的必要性,以及其是否对定位精度有影响,在本文定位模型中将本文算法与仅采用TDOA算法进行定位的情况进行对比,对比结果如图7所示。
从图7可以看出,将TDOA和AOA混合之后的算法能够实 现比TDOA算法更好 的定位精 度。 因为TDOA算法容易受到非视距传播、多径效应等多种不利因素的影响。AOA测量值与TDOA一样都能够提供未知节点的位置信息,只要基站提供的AOA测量值达到一定的精度,误差控制在一定范围内,采用两者混合的算法就能弥补单纯TDOA算法定位精度不高的缺陷,实现比单纯TDOA算法更好的定位精度。
目前煤矿井下应用最广泛的定位算法有加权最小二乘算法、3DL-RD算法等。为了验证本文算法是否优于现有的煤矿井下定位算法,将本文算法与目前现有的定 位算法进 行对比,对比结果 如图8所示。
从图8可以看出,本文算法 要优于加 权最小二乘法和3DL-RD算法,因为上述2种算法都是基于RSSI测距,RSSI测距容易受到环境的影响。而本文算法结合了TDOA和AOA算法,它们都能提供未知节点的位置信息,并且在所限定的小区域内, 受环境的影响比RSSI小,能够提供比较可靠稳定的信息,能够实现比较好的定位精度。
5结语
真三维定位算法 篇5
无线传感器网络(Wireless Sensor Networks,简称WSN)是由部署在监测区域内的大量低成本微型传感器节点组成,通过无线通信方式形成的一个多跳的自组织网络系统。[1]WSN中的节点采用协作方式感知、采集和处理监测区域中对象的信息,因此WSN广泛应用于军事、工业控制、智能交通、污染监测和精细化农业等领域。传感器节点采集到的信息只有和节点自身的位置联系起来,感知的信息才有参考价值。[2]多数情况下传感器节点的部署区域并不是简单的二维区域,而是随机投放在复杂多变的三维区域中,同时传感器节点取得的信息要与自身位置相结合才有应用参考价值,因此研究三维区域的传感器节点定位方法具有重要意义。
传统的传感器节点定位算法分为基于测距和非测距两大类。[3]基于测距的定位算法主要有TOA、TDOA、AOA以及RSSI等[4],一般通过测量获得节点间点到点的距离或角度信息,再使用三边测量法、三角测量法或最大似然估计法等计算节点位置;非测距的定位算法一般以带有GPS坐标定位的锚节点的位置为参照,利用节点间的邻近关系和连通性实现定位,典型的定位算法有质心算法[5]、DV-Hop算法[6,7]以及APIT算法[8]。其中质心算法和DV-Hop算法均可以直接扩充维数,把算法引入三维空间的定位场景。但由于三维场景下这些算法的精度和覆盖率都比二维部署环境低,因此本文分析和探讨了三维场景下的DV-Hop算法,并提出了改进措施,以适应节点分布不均匀和节点低密度的情况下对定位精度和定位覆盖率的要求。
1 DV-Hop 3D定位算法描述
DV-Hop 3D定位算法在原有二维算法的基础上用三维坐标代替二维坐标,算法思想与二维定位算法一致,其算法步骤分为三个阶段:
第一个阶段,锚节点通过距离矢量路由协议向邻居节点广播包含其自身ID和坐标的信息,直到网络中的所有节点都获得最大范围内锚节点的坐标和到锚节点的最小跳数;
第二个阶段,锚节点获得其他锚节点的坐标信息后使用公式(1)计算平均跳距,其中Hop Sizei代表平均跳距,(xi,yi,zi)、(xj,yj,zj)分别是锚节点i、j的坐标,hj是锚节点i与j之间的跳数;
第三个阶段,使用四边测量法或极大似然估计法计算未知节点坐标作为其位置的估计值。
2 DV-Hop 3D定位算法的改进
通过直接扩充维数得到的DV-Hop 3D定位算法与二维算法一样,定位精度依赖于节点分布的均匀度和节点连通度。本文为了提高定位精度和覆盖率,对算法作出如下改进:
在算法的第一个阶段引入跳段数阈值,记为Hop Max,其最小值可参考公式(2)。
其中,假设网络区域为正立方体区域,L是立方体边长,A为每个未知节点定位需要的平均锚节点数,S为网络中节点总数,P为锚节点的比例,R为节点通信半径。当节点到某个锚节点之间的跳数大于Hop Max时,则不记录该锚节点位置信息。引入该阈值的意义在于,当节点分布密度较大时可以在保持原有的定位精度的基础上,有效降低通信和计算量,从而减少节点能耗。
在算法的第二个阶段,由于未知节点计算与锚节点的距离时,选择的平均跳距是最近的锚节点计算的平均跳距,该值在一定程度上能反映出局部网络拓扑,但是大多数情况下会导致较大的定位误差。因此,本文算法进行了如下改进:
(1)网络中的未知节点保存并按序接收所有锚节点的平均跳距和锚节点ID,并计算所有平均跳距的均值,作为全网平均跳距,记为Hop Size_Avg;
(2)设未知节点M的最近的锚节点为i,其平均跳距为Hop Size,到锚节点i的跳数为hi,则到锚节点为i的估计距离为Hop Sizei×hi。若未知节点M到某个锚节点j的跳数hj与到锚节点i的跳数hi相同或非常接近,如│hj-hi│≤1,则表示未知节点M到锚节点i和j的跳数之差为1,到锚节点j的距离为Hop Sizei×hi;若未知节点M到某个锚节点j的跳数hj接近Hop Max时,到锚节点j的距离为HopSize_Avg×hj;其他情况下到某个锚节点j的距离用Hop Sizei×hj计算。
算法的第三个阶段,未知节点M(x,y,z)接收到n≥4个锚节点的坐标信息,n个锚节点的坐标为(x1,y1,z1),(x2,y2,z2),(x3,y3,z3),(x4,y4,z4),…,(xn,yn,zn),它们到未知节点M的距离分别为d1,d2,d3,d4,…dn,则有以下极大似然估计方程式(3)存在,使用标准的最小均方差估计方法即可以得到节点的坐标。
3 仿真实验与结果分析
为了检验改进的DV-Hop 3D定位算法的有效性,使用Matlab7.1对算法进行了一系列仿真实验。仿真实验构造了边长为100m的正方体三维空间实验区域,该空间区域内随机投放了200个节点,其中锚节点控制在10%~30%。为了计算方便,设所有节点的通信半径R相同,且均为30m。通过多次实验对跳段数阈值Hop Max的取值区间作了合理设定,为使实验数据可信,所有仿真实验均在相同参数下取50次仿真实验的平均值。实验证明,跳段数阈值Hop Max在锚节点比例达到30%时,取值为3较为合适;锚节点比例为10%时,取值为5较为合适。
仿真实验在相同条件下比对了本文的改进算法和普通DV-Hop 3D定位算法。本文中的定位精度用定位误差与节点通信半径的比值来表示,比值越小则定位精度越高。从图一可以看出,随着锚节点比例的提高,两种定位算法均可以达到较好的定位精度,在锚节点比例较少时本文的定位算法能比普通DV-Hop 3D定位算法的定位精度更好,随着锚节点的比例提高,两种算法的定位精度基本接近。从图二可以看出,本文的定位算法由于设置了跳段数阈值,定位覆盖率(可定位节点数与总节点数的比值)略有下降,但本文的定位算法通信量大为减少,定时时间短,能耗花费小。
4 结束语
本文对普通的DV-Hop 3D定位算法进行了改进,提出了一种新的DV-Hop 3D定位算法。在提出的算法中通过设置跳段数阈值解决了锚节点比例提高后节点通信量过大的问题,同时根据未知节点到锚节点的跳数分情况选用平均跳距计算未知节点与锚节点的距离。仿真实验表明:本文算法节点通信量能得到合理控制,在定位覆盖率没有明显降低的情况下,有效提高了定位精度。
参考文献
[1]Akyildiz I F,Su W,Sankarasubramaniam Y,et al,Wireless sensor networks:a survey[J].Computer Networks,2002,38(04):393-422.
[2]Su K F,Ou C H,Jiau H C.Localization with mobile anchor points in wireless sensor networks[J].IEEE Transactions on Vehicular Technology,2005,54(03):1187-1197.
[3]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(05):857-868.
[4]Takashima M,Zhao D.Location estimation using received signal power and maximum likelihood esti-mation in wireless sensor networks[J].Electronics and Communications in Japan,2007,90(12):62-72.
[5]Bulusu N,Heidemann J,Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine,2000.
[6]Niculescu D,Nath B.Ad Hoc positioning system[C]∥IEEE Global Telecommunications Conference,2001(,05):2926-2931.
[7]Niculescu D,Nath B.DV based positioning in ad hoc networks[J].Kluwer Journal of Telecommunication Systems,2003,(22):267-280.