质心定位（精选7篇）
质心定位 篇1
摘要：蓝牙定位问题中, 由于采样网格划分不够致密等原因, 如果测试点的位置并没有标记, 则会影响该点的定位结果精度。针对这种情况, 本文提出了一种利用对数衰减模型的加权质心定位算法。该方法首先使用对数衰减模型, 计算出强度值对应的距离;在此基础上, 应用强度值比值与距离的乘积作为加权因子的加权质心算法, 对未知坐标的Beacons进行定位。在固定环境下, 对算法进行测试, 实验结果表明, 与原始质心算法相比, 定位精度提高了约22%。
关键词：蓝牙定位,对数衰减模型,加权质心
定位算法是室内定位系统的关键, 定位结果的精确度很大程度上取决于定位算法。目前, 基于位置指纹的定位算法主要分为概率性算法和确定性算法[1,2,3,6]。由于环境多变, RSSI值并不稳定, 为了提高准确度, 将统计学中的概率引到定位中, 从而形成了基于概率的定位方法。确定性算法原理简单, 计算复杂度低, 但是应用到实际中定位精度不高。
本文实现了原始加权质心定位算法[3,4,5], 定位精度不尽如人意。所以提出了一种在信号衰减模型的基础上, 将信号强度比值与距离的乘积作为权重因子的改进加权质心定位算法, 定位精度有了明显的提高。
1 系统模型
1.1 对数衰减模型
通过大量的实验数据, 并通过计算机的拟合以及理论的辅助, 得到无论在室内还是室外, 接收端接收到的信号强度值与收发双方的距离是成一定对数变化的[7]。对于任意的接收端与发射端之间的距离, 路径损耗为:
根据路径损耗推导出信号强度与距信号源距离的关系:
根据公式 (2) 得出:
其中, PL (d0) 为参考距离d0处的路径损耗, r为路径传播损耗指数, d为接收端与发射端的实际距离, d0为参考距离, Pr (d) 为接收端距发射端d处的信号强度, Pr (d0) 为接收端距发射端d0处的信号强度。
1.2 加权质心算法
质心算法[3,4,5]的主要思想是:未知坐标点以某一范围内已知坐标的点构成多边形的质心作为自己的估计位置。加权质心算法主要是利用已知坐标点和未知坐标点之间接收的RSSI值计算权重, 通过权重决定已知坐标点对质心的影响程度。
已知m个采集点的坐标分别为, 根据对数衰减模型, 计算出每个采集点对应的距离值di, 我们设每个采集点对应的权值为, 应用距离加权的质心算法即可得到待测Beacon的位置坐标
2 定位算法的实现
2.1 改进的加权质心定位算法
对于Beacon来说, 环境对强度值的影响非常大。在固定环境中, 虽然信号强度值相同, 但是不同点对Beacon的距离有可能是不同的, 相应的权重也不相同[8]。所以, 在计算Beacon位置时, 不应该仅仅考虑收集到的强度值的影响, 而应该加入其他的修正方法。否则, 可能导致定位误差变大。
针对已有的加权质心定位算法的缺陷, 本文做的改进策略是把各采集点接收到的Beacon信号强度的比值与距离的乘积, 作为每个采集点的权值, 这样做既可以体现不同Beacon对采集点的影响, 也可以使环境改变时权值基本保持不变。
对于m个采集点, m个采集点测得的信号强度为。定位算法如图1所示。
则权值为
最终得到改进的加权质心计算公式为
2.2 实验测试及结果分析
利用Matlab对本文提出的加权质心算法进行仿真分析。实验环境为7m×18m区域, 采集点均匀分布在3×8网格内, Beacons均匀分布在3×10网格内, 网格间隔均为2m。采集点数为24个, Beacons数为30个。在实验中, 所有数据点强度值为100次实验的平均值。
在距离的倒数作为权值的质心算法中, 设d0=1, 根据测得的数据, 分别计算出对数衰减模型中, 30个未知点对应的未知参数r和Pr (d0) , 从而求得方程。接着, 根据1.2中所述, 计算出了30个未知点的坐标。在改进的加权质心算法中, 未知点坐标的误差和原始坐标误差如图2和表1所示。
从图2可以看出, 改进后的定位算法比原始定位算法精度有明显的提高, 提高了约22%。
3 结语
本文提出了基于信号强度比值和距离乘积作为权重因子的加权质心算法, 该方法考虑了不同距离对定位结果的影响, 减小了距离相同, 方向不同的点信号强度对定位结果的影响, 降低了环境对定位结果的影响。通过与距离倒数作为权重因子的质心算法比较, 实验结果表明, 定位精度均值有明显的提高。
参考文献
[1]曹喆.基于低功耗蓝牙和位置指纹的室内定位系统的研究与实现[D].云南大学, 2014.
[2]Wenzhe Zhang, Lei Wang.INBS:An Improved Naive Bayes Simple Learning Approach for Accurate Indoor Localization[C].Conference on Communications (ICC) .IEEE, 2014, 148-153.
[3]纪程程.基于接收信号强度测量的室内定位技术研究[D].山东师范大学, 2013.
[4]陈维克, 李文锋, 首珩, 等.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报, 2006, 30 (2) :265-268.
[5]杨新宇, 孔庆茹, 戴湘军.一种改进的加权质心定位算法[J].西安交通大学学报, 2010, 44 (8) :1-4.
[6]Gholoobi A, Stavrou S.RSS Based Localization Using a New WKNN Approach[C].Computational Intelligence, Communication Systems and Networks (CICSy N) , 2015 7th International Conference on.IEEE, 2015, 27-30.
[7]Rida, M.E, Liu F, Jadi, Y, et al.Indoor Location Position Based on Bluetooth Signal Strength[C].Information Science and Control Engineering (ICISCE) , 2015 2nd International Conference on.IEEE, 2015:769-773.
[8]Park S, Savvides A, Srivastava M B.Sensor Sim:a simulation framework for sensor networks.[C].In Proceedings of MSWi M.2000:104-111.
质心定位 篇2
光斑质心亚像素定位利用光斑在CCD芯片上具有一定的分布,占据数个像素单元,从而把光斑质心精确到亚像素[1,2,3]。
质心定位误差分析是光斑质心亚像素定位技术不可或缺的部分,国内外已有不少文献对这个问题进行了较详细的分析和讨论[4,5,6,7],但大都侧重于对其中某种误差的讨论,未对光斑质心亚像素定位误差进行比较全面的分析,尤其缺乏相应的测量方法。文献[5]、[6]分析了CCD噪声对光斑质心定位精度的影响;文献[7]分析了像元几何特性的影响;文献[4]提出了一种对CMOS相机亚像素细分精度测试的方法,但该方法需要价格昂贵的快速倾斜镜作为光束偏转控制器,测试成本较高。
本文根据误差的来源将光斑质心亚像素定位误差归类为随机误差和系统误差,提出一种简单有效的实验方法对光斑质心定位误差进行定量测试,并利用高精度一维电动平移台、POINTGREY Flea2-14S3CCD相机和LED光源构建了测试系统,对测试结果进行研究和讨论,计算了基于该CCD相机的光斑质心定位误差,为其在相关系统中的应用提供参考。
1 光斑质心定位算法及误差分析
质心法是计算光斑位置最常用的方法之一,它可以看成是以灰度为权值的加权形心法[8],表达式为
式中I(x,y)为信号强度。
CCD是以像素为单位的阵列图像传感器件,利用CCD确定成像在CCD像面上的光斑位置时,其定位误差主要有以下两方面的来源[9]:一个是因为像元的读出噪声、暗电流散粒噪声、光子散粒噪声、固定模式噪声和光谱响应不均匀性等产生的误差[5,6],由于噪声的随机性,这种误差是随机误差;另一个是图像传感器有限空间采样宽度带来的灰度平均效应以及像元填充率、填充形式带来的误差,这种误差由CCD像元填充形式和填充率等几何特性决定[7],可将其视为系统误差。
1.1 随机误差
光斑图像中像素(i,j)的测量信号Uij由真实信号Lij和噪声信号εij两部分组成,即Lij=Uij+εij,则由实测值估计的x方向的质心位置为[5,6]:
而无噪声真实信号的质心位置为
故噪声导致的x方向上的质心偏差为,相应的方差为σ2ˆx=〈δx2〉。噪声引入的误差σxˆ反映的是根据实测值计算出来的质心xˆ偏离真实信号的质心x′的大小,它一种随机误差,记为σr。通常可将同一位置的同一光斑多次拍摄采样求取的质心位置的标准差作为随机误差的大小,并将质心位置的平均值作为真实信号的质心位置。
1.2 系统误差
由于图像传感器有限空间采样宽度带来的灰度平均效应,以及像元填充形式、填充率等几何特性的影响,导致光斑无噪声真实信号质心x′与光斑的真实质心x0之间存在着偏差,这种偏差在光斑灰度分布和像元几何特性确定的条件下是固定不变的,自身具有一定的规律性,因而可将其视为一种系统误差,记为σs。
1.3 质心定位总体误差
质心定位总体误差σt指的是根据实测值计算得到的质心位置与光斑真实质心x0之间的偏差,因而由上述随机误差σr和系统误差σs两部分组成。二者来源不同,可认为是独立的,根据误差合成理论[10],光斑质心定位总体误差可表示为。
2 误差测试方案及实验系统组成
根据上述误差理论分析可知,随机误差σr可比较容易测量得到,一般通过对同一位置的同一光斑多次拍摄采样求取质心位置,再计算质心标准差即可。系统误差σs表征的是质心平均值与光斑真实质心间的偏差,而实际中光斑的真实质心位置是未知的。因此本文提出一种近似测量光斑真实质心位置的方法,具体如下:
利用一套高精度一维电动平移台,将LED光源固定其上,平移台可带动LED以精确至0.05μm的精度平移,用放置在数米外的CCD相机不断采集LED移动过程的图像。由于LED光源以固定步长平移,其在CCD像平面的光斑质心位置呈线性变化,对实测的质心位置进行直线拟合即可得到光斑真实质心位置。
根据上述方法构建了实验系统对LED光斑质心定位误差进行测试。实验系统主要由高精度一维电动平移台、CCD数字相机、计算机和LED光源组成,如图1所示。其中电动平移台为上海联谊公司的ALB-m-50-1X,该电动平移台行程50 mm,丝杆导程0.5 mm,电机50细分运行分辨率0.05μm;CCD数字相机为POINT GREY Flea2-14S3,该相机采用的是SONY公司生产的面阵CCD图像传感器Sony ICX2671/2″,像元尺寸4.65μm×4.65μm,分辨率1 392×1 032。
3 测试方法
对光斑质心定位误差进行测试的主要步骤如下:
1)将CCD相机架设在距离电动平移台数米的位置,使其正对电动平移台,与LED光源等高;
2)微调镜头焦距,使光斑清晰成像于像面,大小覆盖约10 pixels×10 pixels的范围。微调相机姿态,使光斑位于图像中心位置,且其平移方向大致与图像坐标系的x方向平行;
3)控制电动平移台以一定的步长平移。每平移一次拍摄20张光斑图像,求取光斑的质心位置,计算20次测量的平均值和标准差,标准差的大小即为随机误差σr。由贝塞耳公式,多次测量光斑质心的标准差为:;
4)连续平移100次,计算出每个位置的光斑质心坐标平均值。根据真实质心坐标线性变化的特征,对实验结果进行直线拟合,得出残差的变化规律,计算残差的RMS(均方根值)即为系统误差σs;
5)为排除残差变化规律出现的偶然性,实验中电动平移台往一个方向步进100次后,即反行程以相同的步长步进100次,重复进行3)、4)两步,记录逆行程的测量结果,和正行程进行比较。
4 实验结果分析讨论
测试实验相机横向视场角(FOV)13.4°,距离电动平移台约2.5 m,电动平移台平移步长为10μm,则在图像中LED光斑的平移长度为:。
正行程100个位置所计算得到的光斑质心坐标的标准差大致相同,有小的波动变化。表1给出的是正行程第7个位置处光斑质心坐标。
位置7处LED光斑质心坐标的标准差为:σx=0.017 pixels,σy=0.016 pixels
用同样的方法可以计算其他位置处质心坐标的标准差,平均值为:σx=0.018pixels,σy=0.017pixels此结果即是随机误差大小。
正行程光斑质心y坐标的变化在0.15 pixels之内,与x坐标近2 pixels的行程相差15倍,因此光斑在y方向上的位移相对于x方向可忽略不计,下面只讨论x方向的变化情况,图2给出了光斑质心x坐标变化曲线,显示了光斑质心在x方向上的运动情况。
从图2可以看出,质心x坐标运动呈典型的S曲线形式,具有非常明显的周期性。为了排除这种变化规律出现的偶然性,将逆行程和正行程光斑质心x坐标变化曲线绘于同一坐标系,如图3所示。
从图3可以看出,正行程与逆行程质心坐标值重复性非常好,质心坐标变化规律高度一致,则可说明这种变化规律并非偶然出现的。
利用最小二乘法对正行程光斑质心x坐标变化曲线进行直线拟合,近似认为拟合得到的直线为光斑真实质心变化曲线,如图4所示,对应的残差如图5所示。
图6给出了残差与光斑质心坐标之间的关系曲线。可以看出,残差随着光斑质心在像元内的位置不同而变化,在整像素位置残差较小,在0.5 pixels处残差最大,并且随着质心位置的偏移变化,残差周期性变化。由于每一个光斑质心坐标均为多次取样平均的结果,因此随机误差可以限制在较小的范围内,不会对光斑质心造成如此大的影响。那么初步分析认为,测量过程中出现的系统误差周期性变化现象应该与CCD图像传感器周期性的像元结构有关[4]。LED光斑在CCD图像传感器表面的移动过程中,每个受到光斑覆盖的像元光敏区域面积会发生非线性变化,导致不同位置的光斑质心偏差不同,在某些特定的位置偏差会达到极大或极小。光斑从一个像元平移到相邻的像元,质心偏差的情况就会重复一次,因此就出现了测量过程中周期性变化的规律,而且像元填充形式的不同、填充率的不同都会使周期性变化的大小产生变化。
计算残差的均方根值(RMS),即为系统误差σs的大小,σs=0.06 pixels。则光斑质心亚像素定位总体误差。由此可知,基于POINT GREY Flea2-14S3 CCD相机的光斑质心定位随机误差σr为0.018 pixels,系统误差σs为0.06 pixels,总体误差σt为0.063 pixels(约1/15 pixels),可满足大多数成像测量系统对光斑定位精度指标的要求。
5 结论
本文提出了一种结构原理简单,易于实现的,对光斑质心定位误差进行定量测试的实验方法。利用高精度一维电动平移台、POINT GREY Flea2-14S3 CCD相机和LED光源构建了测试系统,对基于该CCD相机的光斑质心定位误差进行了测试。通过对测试结果进行研究和探讨发现,测试系统LED光斑质心定位的系统误差具有周期性变化规律,且变化周期恰好为1 pixels,初步分析认为该周期性变化规律应该与CCD周期性像素单元的填充形式和填充率等几何特性有着紧密的联系;计算得到了基于Flea2-14S3 CCD相机的光斑质心定位随机误差为0.018 pixels,系统误差为0.06 pixels,总体误差为0.063 pixels(约1/15 pixels),可满足大多数成像测量系统对光斑定位精度指标的要求。实验表明,该测试系统可以作为估算光斑质心定位误差大小的一种有效的手段。
摘要：根据误差的来源将光斑质心亚像素定位误差归类为随机误差和系统误差,提出一种简单有效的实验方法对光斑质心定位误差进行定量测试。利用高精度一维电动平移台、POINTGREYFlea2-14S3CCD相机和LED光源构建了测试系统,对测试结果进行研究和讨论,发现了测试系统LED光斑质心定位系统误差的周期性变化规律,计算得到了基于Flea2-14S3CCD相机的光斑质心定位随机误差为0.018pixels,系统误差为0.06pixels,总体误差为0.063pixels(约1/15pixels),能够应用于以光斑质心检测为手段的测量系统中。实验表明,该测试系统可以作为估算光斑质心定位误差大小的一种有效的手段。
关键词：光斑质心定位,亚像素精度,随机误差,系统误差
参考文献
[1]李春艳,谢华,李怀锋,等.高精度星敏感器星点光斑质心算法[J].光电工程,2006,33(2):41-44.LI Chun-yan,XIE Hua,LI Huai-feng,et al.Centroiding algorithm for high-accuracy star tracker[J].Opto-Electronic Engineering,2006,33(2):41-44.
[2]李季,唐建博.天文导航中星体高精度细分定位方法研究[J].光学与光电技术,2007,5(2):75-77.LI Ji,TANG Jian-bo.High Precision Subdivided Locating Method of Star Image[J].Optics&Optoelectronic Technology,2007,5(2):75-77.
[3]李晓峰,罗彤,邓科,等.采用CCD的空间光通信光斑位置提取重心算法的分析及实验[J].光通信技术,2004,28(6):13-15.LI Xiao-feng,LUO Tong,DENG Ke,et al.Analysis and Experiment of CCD-applied spatial optical communications light spot position locating gravity center calculation[J].Optical Communication Technology,2004,28(6):13-15.
[4]刘智,翟林培,郝志航.互补金属氧化物半导体图像传感器亚像元细分精度实验研究[J].中国激光,2007,34(1):116-122.LIU Zhi,ZHAI Lin-pei,HAO Zhi-hang.Sub-Pixel Measurement Accuracy Experiment of Complementary Metal Oxide Semiconductor Imager[J].Chinese Journal of Lasers,2007,34(1):116-122.
[5]HANCOCK B R,STIRBL R C,CUNNINGHAM T J,et al.CMOS active pixel sensor specific performance effects on star tracker/imager position accuracy[J].Proc.of SPIE(S0277-768X),2001,4284:43-53.
[6]张辉,袁家虎,刘恩海,等.CCD噪声对星敏感器星点定位精度的影响[J].红外与激光工程,2006,35(5):629-633.ZHANG Hui,YUAN Jia-hu,LIU En-hai,et al.CCD noise effects on position accuracy of star sensor[J].Infrared and Laser Engineering,2006,35(5):629-633.
[7]LI Jie,LIU Jin-guo,HAO Zhi-hang.Active Pixel Sensor Geometrical Characteristic Effects on Star Image Subdivided Location accuracy for Star Tracker[J].Proc.of SPIE(S0277-768X),2006,6031:60310C-1-9.
[8]潘波,杨根庆,刘勇.星点质心定位算法最优门限研究[J].光学精密工程,2008,16(9):1787-1792.PAN Bo,YANG Gen-qing,LIU Yong.Study on optimization threshold of centroid algorithm[J].Optics and Precision Engineering,2008,16(9):1787-1792.
[9]李玉峰,郝志航.星点图像超精度亚像元细分定位算法的研究[J].光学技术,2005,31(5):666-671.LI Yu-feng,HAO Zhi-hang.Research of hyper accuracy subpixel subdivision location algorithm for star image[J].Optical Technique,2005,31(5):666-671.
质心定位 篇3
现有的无线传感网络未知节点定位算法很多, 20世纪末美国学者Bulusu等提出了质心定位算法[7,8], 2003年He等提出了APIT节点定位算法[9,10], 2001年Dragos Niculescu等提出了APS定位算法[11], 同年Andreas Savvides等提出了AHlo S定位算法[12]。但是, 这些无线传感网络定位算法对于现今高速发展的社会来说, 其定位的精度却远远不够[13]。所以, 研发可以对物联网节点进行精确定位的算法是目前迫切需要的。
本文从目前物联网节点定位精度需求出发, 在一般质心算法的基础上, 对其进行坐标加权和节点坐标误差优化等改进, 以优化原算法在物联网未知节点测量时的准确性。
1 质心定位算法
1.1 质心模型
质心算法的定位思路为:将网络中位置确定的节点定义为标记节点, 首先标记节点向网络中的邻节点传输标记节点的坐标数据, 然后当需要定位的节点收到一定数量的坐标数据后, 这些坐标组成一个多边形, 多边形质心的位置信息便为需要定位节点的信息。
假设网络中需要定位的节点坐标为P (x, y) , 收到n个标记节点传输的坐标数据 (本文设n=5) , 分别为A (x1, y1) , B (x2, y2) , C (x3, y3) , D (x4, y4) , E (x5, y5) , 需要定位的节点的模型如图1所示。
1.2 算法流程
如图1所示, 需要定位的节点P为多边形ABCDE的质心, 那么, 首先将多边形ABCDE分解为3个三角形, 分别为△ABC, △ACE, △CDE, 如图2所示。
然后对△ABC, △ACE, △CDE的中心O1, O2, O3求解, 最后求得△O1O2O3的几何中心的坐标, 求得的坐标便是需要定位的节点P的定位坐标。图3为多边形ABCDE中的一个三角形△ABC。
图3中:O1点的坐标为 (xO1, yO1) ;F, G, H为3边的中点, 其坐标为 (xF, yF) , (xG, yG) , (xH, yH) , 那么就有
那么直线AG和直线BH的方程可以表示为
所以, 点O1的坐标为
同理可得, 点O2和O3的坐标为
所以, 需定位节点P的坐标为
由此可知, 假如标记节点有n个, 那么需定位节点P的位置计算公式为
2 加权坐标误差修正
2.1 坐标加权
为了提高在节点定位时的准确性, 本文使用RSSI测量标记节点与需定位节点的距离, 并使用这个距离和信号弱化系数 (attenuation coefficient) 对坐标进行加权。信号弱化系数, 用函数λ表示, 现在假设标记节点的坐标为 (xi, yi) , 整个网络的节点数为n, 那么加权公式为
式中:ρi为坐标加权因子;di为使用RSSI测得的标记节点与需定位节点的估计距离。
2.2 节点坐标误差修正
从式 (10) 和式 (11) 可以看出, di对节点定位的精确性影响较大。所以, 本文采用节点坐标误差优化策略对其进行改进。
如图4所示, 标记节点A0 (x, y) 为需优化节点, 与其他标记节点A1 (x1, y1) , A2 (x2, y2) , A3 (x3, y3) , A4 (x4, y4) 的实际距离为d1, d2, d3, d4。使用RSSI测量的距离为d'1, d'2, d'3, d'4, 为加权后坐标。
定义一个标记节点的优化系数ε, 其公式为
使用标记节点的优化系数ε便可以对使用RSSI测量进行优化, 其优化公式为
由式 (13) , 可以得到在定位时候产生的误差值为
所以, 最终的坐标可以表示为
3 实验分析
为了检验本文提出方案的可行性和准确性, 对算法进行算法仿真实验。实验环境为Unix平台, 用C语言编程, 对上述算法进行了计算机仿真。仿真条件:标记节点参照MICA2 mote, 取200~300室外发射半径。传感区域为100 m×100 m, 标记节点较“均匀”地分布于传感区域。需要定位的节点随机布置于传感区域。
1) 在其他条件不变的情况下, 逐渐增加标记节点的个数, 测试原算法与本文算法的平均定位误差, 如图5所示。
从图5中可以看出, 逐渐向网络中增加标记节点, 原算法和本文算法在定位时的误差变小, 但是相比较而言, 本文算法的误差要比原算法小。
2) 在其他条件不变的情况下, 逐渐增加需定位节点的个数, 测试原算法与本文算法的平均定位误差, 如图6所示。
从图6中可以看出, 逐渐向网络中增加需要定位节点, 也使误差变小, 但是相比较而言, 本文算法的误差要比原算法小。
3) 在其他条件不变的情况下, 对整个网络进行人工信号干扰, 并逐渐增强干扰信号强度, 测试原算法与本文算法的平均定位误差, 如图7所示。
从图7中可以看出, 在网络中增加信号干扰强度, 导致定位误差都在不断增加, 但是相比较而言, 本文算法的误差要比原算法小。说明改进算法受到干扰信号影响小。
综上所述, 本文提出的改进算法比原算法拥有更高的精确度、更小的定位误差和更强的鲁棒性, 本方案切实有效。
4 小结
基于区域分割的二次质心定位算法 篇4
关键词：初次质心定位,二次质心定位,定位误差,区域分割
0 引言
无线传感器网络WSN(Wireless Sonser Networks)作为一种全新的技术，在国防军事、交通管理、制造业、环境监测、医疗卫生、反恐抗灾等领域得到了广泛的应用，在其众多的应用中，均须知道事件发生的位置，因此，节点定位技术是无线传感器网络的主要支撑技术之一。目前，无线传感器网络的定位算法可分为基于测距的算法和无需测距的算法两种[1]。基于测距的算法通过测量节点间的距离或角度信息，使用三边测量[2]、三角测量或最大似然估计法[3]计算节点的位置;无需测距的算法则根据网络的连通度等信息来实现节点定位。无需测距的算法属于粗粒度定位，定位精度较低，但在对硬件的需求及受实际环境的影响程度上与基于测距的定位算法相比都有很大的降低，因此也得到了较为广泛的应用。
在无需测距的算法中，质心定位算法[4]由于计算成本较低、网络生存能力较强、实现简单等优点而成为众多学者研究的热点。该算法在锚节点均匀分布时表现出较好的性能，当锚节点分布不均匀的时候，质心定位算法的定位精度会大幅下降。为了解决这一问题，以文献[5,6,7,8]为代表的方法主要通过不同信标节点的不同影响力来进行改进，文献[9,10,11,12]等主要从信标节点的分布角度来进行改进。本文主要针对未知节点周围分布的锚节点不均匀而产生较大的定位误差这一问题提出了一种改进的质心定位算法，用初次质心定位的估计位置取代离未知节点距离最远的锚节点，进行二次质心定位，有效地提高了质心算法的定位精度。
1 质心定位算法
1.1 质心定位算法原理
质心定位算法是一种仅基于网络连通性的室外定位算法。信标节点周期性地向邻居节点广播包含自身标识和位置信息的数据包，当未知节点接收到来自某一信标节点的数据包数量超过某个值或接收一定的时间后，就确定该信标节点处于自身的通信范围内，并将其通信范围内的所有信标节点构成的几何质心作为自身的估计位置。设某一未知节点通信范围内的信标节点个数为n，坐标分别为(xi,yi)，其中i=1,2，…，n，该未知节点的估计位置为(xe,ye)，则有:
显然，质心定位算法完全基于网络的连通度，方法简单，运算复杂度低。
1.2 质心定位算法缺陷
为了减少运算量，质心算法一般取接收到的信号能量值较大的三个信标节点构成三角形，将三角形的质心作为未知节点的估计位置。当信标节点是均匀分布的时候，采用质心定位算法可以取得较高的定位精度。然而，在诸如森林防火、环境监测等众多的应用场合中，信标节点不可能按照一定的位置预先布置好，即信标节点往往都是随机分布的，在这种情况下，质心定位算法会产生较大的定位误差。如图1所示，信标节点A、B、C在未知节点S的通信范围内呈不均匀分布，质心算法结果将未知节点定位在I点。在图1所示的三种情况中，均是信标节点A离未知节点的实际距离较远，由于其产生的负面作用力，使得未知节点的估计位置I不同程度地偏向A点，未知节点的实际位置距A点越远，偏离程度越大。因此，在实际的定位过程中，由于信标节点的不均匀分布使得质心定位算法的定位结果向距未知节点距离较远的信标节点一侧偏移，会产生较大误差。
2 二次质心定位算法
为了解决距离较远的信标节点对未知节点估计位置的负面影响，文献[5,6,7,8]等提出给距离未知节点较远的信标节点以较小的权值，给距离较近的信标节点以较大的权值，以此来消弱较远的信标节点的影响力，使未知节点的估计位置能更接近其真实位置;文献[9,10,11,12]则采用几何空间上覆盖所有锚节点的区域来估计目标位置，来有效地控制由于锚节点分布不均匀给定位精度带来的波动，这两类改进方法在一定程度上取得了较好的效果。不同于上述方法，本文结合三角形区域分割，用初次质心定位结果取代距未知节点距离最远的信标节点，进行二次质心定位，来减小定位误差。
2.1 区域分割
在理想的条件下，RSSI值和距离之间存在着一定的衰减关系，RSSI值越大，收发两方的距离越近，反之，距离越远。对于无线传感器网络节点而言，其RSSI值又很容易获取，因此可以通过比较未知节点S在同一时刻接收到三个顶点A、B、C发送来的信号强度，进一步的判断未知节点S距哪一个顶点较远，也就是缩小未知节点S在△ABC内可能存在的区域范围，确定二次质心算法所要取代的信标节点。
详细地说，利用有效三角形的三条中垂线将三角形及其周围的区域进行分割，以三条中垂线的交点P及由三条中垂线形成的6条射线为边界，将三角形及其周围的区域分割成6个区域。有效三角形为锐角三角形、直角三角形或钝角三角形时，分割情况分别如图2(a)、(b)、(c)所示。根据中垂线上的点到两端点的距离相等和比较未知节点接收到顶点发送来的信号强度，可以进一步的判断未知节点属于哪个区域。
以图3为例，RA、RB、RC分别表示未知节点S收到来自信标节点A、B、C的信号强度，SA、SB、SC分别表示未知节点S与信标节点A、B、C之间的距离，且需找出距未知节点S距离最远的信标节点，即需比较出RA、RB、RC中哪个值最小。根据这一需求在比较三个信号强度的大小时，可能会出现如下三大类情况。
情况一检测到其中两个信号强度值均大于另外一个信号强度。若检测到RA>RB且RC>RB，则有SA>SB且SC>SB，可判断出未知节点S距B点最远，通过检测到的RA>RB可推断未知节点S在并集区域P=﹛区域1∪区域6∪区域5﹜中，通过检测到的RC>RB可以推断未知节点S在并集区域Q=﹛区域4∪区域5∪区域6﹜中，综上可以推断未知节点S在区域TB=P∩Q=﹛区域5∪区域6﹜;同理，若检测到RA>RC且RB>RC，可推断未知节点S距C点最远，且S处于区域TC=﹛区域1∪区域2﹜中;若检测到RC>RA且RB>RA，可推断未知节点S距A点最远，且S处于区域TA=﹛区域3∪区域4﹜中。通过以上分析，可知，若未知节点S与B点距离最远，则S一定处于由射线PD和射线PE组成的区域中;若S距C点距离最远，则S一定位于由射线PE和射线PF组成的区域中;若S距A点距离最远，则S一定位于由射线PD和射线PF组成的区域中。三角形ABC及其周围的区域被射线PD、PE和PF划分为3个不同的区域，如图3(b)所示。
情况二检测到其中一个信号强度大于另外两个信号强度，且较小的两个值相等。若检测到RA>RB=RC，则有SA>SB=SC，可判断出S距B和C的距离一样远，通过检测到的RA>RB，可推断节点S在并集区域P=﹛区域1∪区域6∪区域5﹜中，通过检测到的RB=RC，可推断节点S在BC边的中垂线EH上，综上可以推断未知节点S在区域P和直线EH的并集区域，即在射线PE上;同理，若检测到RB>RA=RC，可推断节点S距A点和C点的距离一样远，且S在射线PF上;若检测到RC>RB=RA，可推断节点S距A点和B点的距离一样远，且S在射线PD上。
情况三检测到三个信号强度一样大。在这种情况下，未知节点S距三个节点A、B、C的距离一样远，S位于三角形ABC的垂心P处。
2.2 二次质心算法原理
对图1进行分析可知，如果以A方向上的某个距离未知节点S更近的点来取代信标节点A进行质心定位，可在一定程度上减小未知节点估计位置向A方向的偏向程度，进一步减小定位误差。基于这一思想，根据2.1节中所述的判断方法找出A、B、C三点中距未知节点S距离最远的点，假定是C点，则未知节点S应处于由射线PE、PF组成的区域内，如图4所示，用初次定位估计位置I来取代信标节点C，结合信标节点A、B构成新的三角形进行二次质心定位，估计位置为I'。由图4可以明显看出，二次质心定位结果I'更接近于未知节点的实际位置S，即SI'<SI。
2.3 误差分析
在图5中，未知节点S与信标节点A、B、C之间的关系同图4,A是被取代的信标节点，S仍处于由射线PE、PF组成的区域内，但其在该区域中的位置不同于图4，在这种情况下，由图5可以明显看出二次质心定位误差SI'大于初次定位误差SI。因此，本文所述的二次质心算法的定位误差并不是一定总是小于初次质心定位的误差，该误差和未知节点的分布位置有关。因此，需要确定当未知节点处于由射线PE和PF围成的区域中的哪些位置时，才能使二次质心定位结果优于初次定位结果，即满足SI'<SI。
作线段II'的中垂线，分别交PE、PF于M、N点，如图6所示，根据中垂线上的点到两端点的距离相等可推断，若S处于由射线PE、射线PF及中垂线MN围成的区域，即图6中的阴影区域三角形PMN，会有SI'>SI，此时，二次质心定位误差大于一次质心定位误差。为了便于描述，将由射线PE和射线PF围成的且包含线段AB的区域定义为区域TC，将区域TC中除去三角形PMN以外的区域定义为区域O，当S处于区域O中时，会有SI'<SI，此时，二次质心定位结果优于一次质心定位结果。
按照上述原理，图7分别画出了当信标节点A、B、C组成的三角形分别为锐角、直角及钝角三角形时，二次质心定位误差大于一次质心定位误差情况下未知节点S可能存在的区域，即为图中阴影部分。当未知节点处于阴影区域之外的空白区域时，二次质心定位结果一定优于一次质心定位结果。由于未知节点S有可能处于三角形外部，综合考虑三角形内外部的所有区域，由图7可以明显看出，阴影部分的面积远小于空白部分的面积，因此，我们有理由相信，在大多数的情况下，本文所述的二次质心定位算法的误差要小于一次质心定位误差，用二次质心定位结果的整体误差一定会小于一次质心定位的整体误差。
2.4 算法描述
(1)信息收集阶段
网络节点布撒后，网络进行初始化配置。信标节点向未知节点广播消息，消息中包含信标节点在网络中的ID、自身坐标信息。为了判断和信标节点之间距离的远近，未知节点还需记录来自各信标节点的RSSI值。在信息收集的时间内，未知节点随时更新其通信半径内锚节点传来的信息，通过这种方式降低由于网络拓扑结构变化原因造成的定位出错的可能性。
(2)定位阶段
(1)未知节点将其通信半径内的所有信标节点按照其接收到的RSSI值的大小进行排序，建立自身信标节点信息表，选择RSSI值较大的3个信标节点，计算出其质心，设为I(为了便于说明，此处设较大的三个RSSI值分别为RA、RB、RC，其对应的信标节点分别为A、B、C);
(2)比较RA、RB、RC的大小，若其中两个信号强度值均大于另外一个信号强度，则用第(1)步中计算出的质心I取代RSSI值最小的信标节点构成新的三角形进行第二次质心计算，并将计算出的二次质心I’作为未知节点S的最终估计位置;
(3)若RA、RB、RC中的一个信号强度大于另外两个信号强度，且较小的两个值相等，则用第(1)步中计算出的质心I取代两个较小的RSSI值所对应的信标节点中的任意一个进行二次质心定位，并将计算出的二次质心I'作为未知节点S的最终估计位置;
(4)若三个信号强度RA、RB、RC一样大，则将三角形ABC的垂心作为未知节点S的最终估计位置。算法流程如图8所示。
3 仿真实验
利用MATLAB仿真平台，在200 m×200 m的区域内随机分布200个节点，假设节点之间均能正常通信，对二次质心定位算法进行仿真，并与传统的一次质心算法进行比较。本文主要把绝对定位误差作为评估算法的主要性能指标。
绝对定位误差:
式中，(xr,yr)是节点n的真实坐标，(xe,ye)是用算法估计出的节点n的坐标。为消除节点随机分布对算法性能的影响，每种条件下均随机仿真1000次，并取1000次定位误差的平均值最为最终的绝对定位误差。
图9给出了在200个节点里，信标节点所占比例改变时，定位误差随之变化的情况。由图9可以看出，随着信标个数的增加，一次质心定位和二次质心定位的误差都呈减小趋势，但二次定位的误差总小于一次定位的误差，当信标节点的个数增大到50%以后，两种方法的定位精度提高并不明显。值得一提的是，当信标节点比较稀疏，所占比例为20%时，二次质心定位的性能远远优于一次质心定位，定位精度提高了近10米。因此，当网络中信标节点个数较少时，未知节点通信半径内的信标节点分布的不均匀性会更高，一次质心定位会差生较大误差，采用二次质心定位方法能大大提高其定位精度。
图10给出了信标节点所占比例为40时两种定位算法的定位误差的累积概率。结果显示，二次质心定位算法绝对定位误差在15米以内的的概率超过70%，而传统的一次质心定位算法达到这种精度的概率大约只有60%。
4 结语
本文提出了一种基于区域分割的二次质心定位算法，用初次质心定位结果取代未知节点通信半径内距离最远的信标节点，来减小由于信标节点分布不均匀而导致未知节点的估计位置偏向距离较远的信标节点的现象。仿真结果表明，在信标节点较为稀疏时，二次质心定位算法的定位精度远远高于传统的一次质心定位算法，且该方法无需复杂的数学运算，实施较为简单，同时能很好地应用在三维空间的场合，具有一定的应用价值。
但是，本算法中，采用RSSI值来实现未知节点和信标节点之间距离远近的判定，但RSSI值易受环境干扰，RSSI值大，并不意味着距离就近，RSSI测距的不准确性会导致算法产生额外的误差，因此，在实际的应用中需要解决RSSI测距精度的问题。
参考文献
[1]Wang Jing,Ghosh R K,Das S K.A survey on sensor localization[J].Control Theory Appl,2010,8(1):2-11.
[2]温立.无线传感器网络定位技术研究[D].上海:复旦大学,2008.
[3]刘克中.无线传感器网络分布式节点定位方法研究[D].武汉:华中科技大学,2006.
[4]Bulusu N,Heidemann J,Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine,2000(7):28-34.
[5]朱建新,高蕾娜,张新访.基于距离几何约束的二次加权质心定位算法[J].计算机应用,2009,29(2):480-483.
[6]Xia A L,Ma C W.Improved centroid detection method based on higher moment for shack-hartmann wavefront sensor[C]//Optoelectronic Imaging and Multimedia Technology,Oct,2010.
[7]郜丽鹏,朱梅冬,杨丹.基于Zigbee的加权质心定位算法的仿真与实现[J].传感技术学报,2010,23(1):149-152.
[8]朱博,陈曙.一种无线传感器网络质心定位改进算法[J].传感技术学报,2010,23(6):868-872.
[9]徐小玲,张福强,李少彪.基于APIT的无线传感器网络质心算法研究[J].传感器与微系统,2011,30(7):57-59,63.
[10]衣晓,刘瑜,邓露.一种基于PIT的无线传感器网络质心定位算法[J].传感器技术学报,2010,23(7):1012-1016.
[11]周全,朱红松,徐勇军,等.基于最小包含圆的无线传感器网络定位算法[J].通信学报,2008,29(11):84-90.
质心定位 篇5
无线传感器网络 (Wireless Sensor Networks, WSN) 将很多成本低且功耗小的微小型无线传感器节点分布于待监测区域。迅速地获取事件产生、参数变化的区域或者消息的节点位置是WSN重要的功能之一, 也是提供监测参数变化区域等信息的前提, 所以定位技术对WSN的广泛应用起着至关重要的作用[1], 因而, 节点定位技术成为WSN重要的技术之一。
现有无线节点定位算法主要分为距离无关算法和基于距离测定的算法两种[2]。距离无关的定位算法以硬件为基础, 因而对硬件的性能要求高, 定位精度也随之提高。通常使用较为广泛的算法包括质心算法、DV-Hop和APIT算法等。而基于距离测定算法主要有RSSI (接收信号强度指示) [3]、TOA和TDOA等。这类算法的精度相对较低, 其中RSSI算法对的硬件要求很低, 很多无线模块 (如Zig Bee等) 都可以较容易地测得RSSI值。因此, 基于RSSI的定位方法仍然使用广泛[4]。
RSSI方法是由发射节点发射信号强度根据接收节点收到的信号强度, 利用损耗模型计算传播损耗, 然后利用理论和经验模型将传输损耗转化为距离值, 根据距离值即可得节点位置相关信息[5]。由于理论和经验模型的估测特性, 故RSSI定位误差较高。基于此, 文献[6]提出一种将RSSI测距方法与三边测量质心算法相结合的新型定位算法。该算法先用三边测量方法确定未知节点的位置范围, 然后利用固定信标节点之间的距离和信号强度两种信息作为参考依据来校正RSSI测距值, 并优选信标节点;然后再利用加权质心算法估算未知节点的位置, 有效地减少了测距误差和计算量。
本文对文献[6]中提出的优选信标节点模型进行分析后, 对利用优选信标节点模型进行未知节点位置估算方法进行了修改, 提出了一种精度更高的未知节点位置的估算方法。
1 三边测量方法
常见的三边测量法的原理是:选取3个信标节点, 测出未知节点到这些信标节点间的距离。理想情况下, 分别以每个信标节点到未知节点的距离为半径做一个圆, 那么这3个圆的交点就是未知节点的位置, 也就得到了所需要的未知节点坐标。
但是现实中, 由于信道传播过程中存在路径损耗等各种因素的影响, RSSI测距误差较大, 并且由于理论模型比实际的路径损耗相比偏小, 所以测得的未知点到信标节点的距离往往大于实际距离, 这3个圆不会精确地交于同一点[7]。因此, 计算这3个圆的相交区域, 利用相交区域进行未知节点坐标估计, 以得到确定的估计结果是很有必要的。为了提高该方法的定位精度, 文献[8]采用加权质心估算未知节点的位置, 即在每组定位坐标中引入加权因子, 参与每次定位3个圆的半径和的倒数为加权因子。
理想情况下的三边测量法示意图如图1 (a) 所示。已知A, B, C3个节点的坐标分别为 (xA, yA) , (xB, yB) , (xC, yC) , dA, dB, dC分别是未知节点M到3个已知节点的距离。假设 (x, y) 为M的坐标, 那么存在下列公式:
考虑实际情况的三边测量法则如图1 (b) 所示。在实际环境中, 由于存在模型损耗等引起的测量误差, 3个圆不是交于一点, 将方程组 (1) 中的式子两两相减, 即可得图1 (b) 中所示的L1, L2, L3:
解出3条直线L1, L2, L3交点组成的方程组, 可以作为未知节点M的估计坐标[6]。
2 二次质心算法
2.1 建立相交区域模型
如图2所示, 假设由4个信标节点围成一个方形场地, 以信标节点kn1的位置为坐标原点, 设kn1, kn2, kn3和kn4已知4个节点的坐标分别为 (x1, y1) , (x2, y2) , (x3, y3) 和 (x4, y4) , 未知节点与它们之间距离分别为d1, d2, d3和d4。设 (xu, yu) 为未知节点knu的坐标。那么存在下列公式:
在理想情况下, 分别以各个信标节点为圆心, 以其到未知节点的距离为半径做圆, 那么4个圆的交点就是未知节点的位置, 也就是在定位中需要得到的未知节点坐标。但是在现实中, 由于信道传播过程中存在路径损耗等误差的影响, 得到的结果如图2所示。
先利用上述三边测量法, 即每次取3个信标节点即3个圆进行一次相交区域质心坐标的估计。那么, 以4个信标节点 (kn1, kn2, kn3, kn4) 为中心的4个圆共可产生4组组合, 得到的4次估计坐标为M1 (xm1, ym1) , M2 (xm2, ym2) , M3 (xm3, ym3) 和M4 (xm4, ym4) 。再将4组质心坐标值求平均值, 可得未知节点的初步估算坐标kum为:
2.2 二次质心估算
很多文献采用三边测量方法得到kum之后, 再利用加权方法或者其他修正模型对其估算坐标进行修正, 将修正值作为未知节点的最终估算位置。但是, 此方法每次取3个圆求相交区域质心坐标, 然后把所有的质心坐标取平均值得到的坐标作为未知节点的估算位置, 这样多次估算质心坐标会使误差累积, 所以得到未知节点估算位置误差较大。
为了进一步提高定位精度, 提出了基于二次质心方法的定位算法。该方法的基本思想是先求出代表信标节点与未知节点间距离的所有圆的交点坐标, 再计算所有交点与上述过程中所求的未知节点粗略位置kum间的距离, 以该粗略位置为核心, 寻找能够更精确地估算未知节点最终位置的坐标集合进行估算。
求取交点可将式 (3) 中的4个圆的方程两两联立。设所有交点的坐标集合为Li (xLi, yLi) , i=1, 2, …, 12;交点与kum间的距离集合为dLi, i=1, 2, ⋯, 12。则交点与kum间的距离公式可表示为:
将得到的距离按照从小到大排序并取较小的4个, 由这4组坐标构成的多边形的质心可作为未知节点的新的估算位置。设4个较小的交点坐标为N1 (xn1, yn1) , N2 (xn2, yn2) , N3 (xn3, yn3) 和N4 (xn4, yn4) , 进行平均可得到未知节点的第二次估算坐标kun (xun, yun) 为:
该方法利用三边测量法对未知节点的位置进行初步估算, 然后以该位置为核心, 寻找各圆的所有交点中距离该估算位置较近的交点;以这些交点作为基础, 估算未知节点的新坐标。因为各圆的交点通过两圆方程联立即可得到, 并不需要进行估算, 与传统的仅依靠三边测量方法进行估算的算法相比, 可有效避免多次估算累积的误差。
为了避免信息的淹没, 获得更准确的估算值, 可对三边测量法和二次质心法所得到的估算坐标求平均值。设此时待测节点坐标为ku L (xu L, yu L) , 然后将两次估算值求平均, 得到新的估算位置为Ku L= (kum+kun) 2, 估算位置坐标如公式 (7) 所示。
设待测节点ku L到信标节点kn1, kn2, kn3和kn4的距离分别是dn1, dn2, dn3和dn4。由于信道的不稳定和环境的干扰, 利用文献[9]提出的修正几何方法进行修正, 得出一个稳定性更好的公式:
3 算法流程
步骤1:信标节点kni (i=1, 2, 3, 4) 以相同功率周期性发送自身节点信息, 包括节点的ID和节点的坐标信息;同时节点kni接收其他信标节点knj发送的位置信息, 并对收到的多个RSSIij求平均值, 计算出未知节点接收到信标节点kni的信号强度平均值。
步骤2:未知节点先收集各个信标节点的信息, 并记录同一个信标节点的RSSI均值作为接收到的RSSI值, 然后根据RSSI校正模型计算出未知节点与各信标节点之间的距离di。
步骤3:
(1) 把步骤2中计算出的未知节点到信标节点的修正距离建立一个集合Dis_set={d1, d2, d3, d4}, 信标节点及其位置信息集合为Kn_Pos_set={kn1 (x1, y1) , kn2 (x2, y2) , kn3 (x3, y3) , kn4 (x4, y4) }。
(2) 把kn1, kn2, kn3和kn4三三组合, 建立三边测量集合:Triangle_set={ (kn1, kn2, kn3) , (kn1, kn2, kn4) , (kn2, kn3, kn4) , (kn1, kn3, kn4) }。把该集合中的每组测量数据利用方程组 (2) 进行求解, 得到各自的估计坐标。
(3) 设得到的4组估计坐标为Mi (xmi, ymi) , i=1, 2, 3, 4, 将步骤 (2) 得到的估计坐标值代入公式 (4) 中得到未知节点的粗略估算坐标kum (xum, yum) 。
步骤4:
(1) 把kn1, kn2, kn3和kn4两两组合, 一共可得6组, 建立集合Intersec_set={ (kn1, kn2) , (kn3, kn4) , (kn1, kn3) , (kn2, kn4) , (kn1, kn4) , (kn2, kn3) }, 把以每组信标节点为中心形成的圆联立求解交点, 得到12个交点坐标。
(2) 4个圆所有交点集合建立为:Li (xLi, yLi) , i=1, 2, ⋯, 12;交点与kum间的距离集合为dLi{i=1, 2, …, 12}, 利用式 (5) 求解距离, 并将距离从小到大排序, 取较小的4组交点坐标。设这4组交点坐标集合为Ni (xni, yni) , i=1, 2, 3, 4, 利用式 (6) 求平均得到kun (xun, yun) 。
步骤5:利用式 (7) 把步骤3与步骤4中得到的未知节点估计求平均值, 得到未知节点新的估算坐标。
步骤6:利用式 (8) 进一步修正, 得到最终的未知节点位置的估计坐标。
4 仿真分析
用Matlab 2013b作为计算仿真工具, 假设在100 m×100 m的方形区域内进行测距, 信标节点分布在该区域的4个角, 其坐标分别为 (0, 0) , (100, 0) , (0, 100) , (100, 100) 。信标节点采用无线信号载频为2.4 GHz的硬件方案且性能相同, 无线信道传播损耗模型采用Shadowing传播模型, 设定路径损耗系数为2, 信标节点通信的半径设为100 m。
未知节点坐标由Matlab 2013b的随机函数来生成, 在该正方形区域内随机分布, 一共生成30个未知节点。由传播损耗模型测算其修正的RSSI数值, 并在数值中添加均值为0方差为6的高斯噪声, 来代替实际环境中的反射和气候等带来的影响。仿真实验的比较对象为传统的RSSI质心定位方法, 基于加权校正的三边测量方法和本文的二次质心算法。实验中分别采用上述3种定位方法计算了未知节点预测位置, 与未知节点已知实际坐标相比较, 仿真结果如图3~图5所示。
图中节点预测位置和实际位置间的距离即是定位误差, 为了更直观反应上述三种定位方法的精度, 将图3~图5中30组节点预测位置和实际位置间的距离进行比较, 如图6所示。
为了更好地验证算法的定位精度及鲁棒特性, 将每次仿真的结果取平均值, 然后运行100次三种算法, 结果如图7所示。
从仿真结果可以得出, 基于多次仿真数据取其平均值以后, 传统的RSSI质心定位方法的平均误差为9.24%, 基于加权校正的三边测量方法为6.39%, 而二次质心算法为5.17%。相比三边测量方法, 二次质心算法精度提高了19.1%, 而且鲁棒性更好。
5 结论
本文提出的定位方法是先利用三边测量法确定未知节点的粗略位置, 以该粗略位置为核心, 寻找能够更精确地估算未知节点最终位置的坐标集合, 而不是直接将三边测量法的估算结果作为未知节点的最终位置。本文提出的算法与三边测量法相比, 有效地减小了多次估算质心产生的误差累积;而且整个算法采用几何运算, 不需要迭代, 具有较好的快速性;同时, 本定位算法对硬件要求低, 能较好适应WSN低功耗与低成本的要求, 是一种可选的WSN定位方法。由于本文的实验是在规则的场地上完成的, 在今后的研究中, 应讨论新算法如何在不规则场地中实现;另外, 还可以通过BP神经网络模型和贝叶斯网络模型优化定位算法, 从而得到更好的定位性能。
参考文献
[1]李晓维.无线传感器网络技术[M].北京:北京理工大学出版社, 2007.
[2]HUANG C D, BLUM B M.Range-free localization schemes inlarge scale sensor networks[C]//Proceedings of the Ninth An-nual International Conference on Mobile Computing and Net-working.San Diego, United states:[s.n.], 2003:81-95.
[3]LUTHY K A, E GRANT D, HENDERSON T C.Leveraging RSSI for robotic repair of disconnected wireless sensor networks[C]//Proceedings of 2007 IEEE International Conference on Robotics and Automation.Rome, Italy:IEEE, 2007:10-14.
[4]刘运杰, 金明录, 崔承毅.基于RSSI的无线传感器网络修正加权质心定位算法[J].传感技术学报, 2010, 23 (5) :717-720.
[5]HAN G, CHOI Deokjai, LIM Wontaek.Reference node placement and selection algorithm based on trilateration for indoor sensor networks[J].Wireless Communications and Mobile Computing, 2009, 9 (8) :1017-1027.
[6]赵昭, 陈小惠.无线传感器网络中基于RSSI的改进定位算法[J].传感技术学报, 2009, 22 (3) :391-394.
[7]葛文涛, 陈俊杰.基于三边定位的WSN锚节点加权补偿算法[J].测控技术, 2010, 29 (9) :92-95.
[8]赵飞.基于RSSI的无线传感器网络定位算法研究[D].南京:南京邮电大学, 2011.
[9]刘川来, 郭蓝天, 秦浩华.一种改进的Zig Bee无线传感器网络定位算法及应用[J].化工自动化及仪表, 2012, 39 (2) :204-208.
质心定位 篇6
目前, 大多节点定位技术都是利用少数已知位置信息的节点通过某种机制来确定未知节点的位置。根据是否需要测量相邻节点间的距离或角度信息, 将定位算法分为基于测距的算法和无需测距的算法[2]。基于测距的算法通过测量相邻节点间的距离或角度信息, 并利用实际测量的距离来计算未知节点的位置, 定位精度较高, 但对硬件依赖性高, 不适合低功耗、低成本的无线传感器网络应用领域。常用的基于测距的算法有TOA和TDOA、AOA和RSSI[3]。无需测距的算法无需测量相邻节点间的距离或角度信息, 利用网络的连通性等信息, 来估计未知节点的位置或可能存在的区域, 虽然定位精度较低, 但对节点的硬件要求不高, 能够满足多数无线传感器网络的定位要求。目前无需测距的定位算法主要有质心定位算法、凸规划定位算法、DV-Hop定位算法和APIT算法等[4]。
质心定位算法和DV-Hop定位算法作为两种经典的无需测距的定位算法, 一直以来都是研究的热点。文献[5]在分析质心定位算法和DV-Hop定位算法基础上, 提出了质心和DV-Hop混合算法, 文献[6-7]则从影响算法定位精度的因素入手, 对算法进行改进。该文则从对质心定位算法和DV-Hop定位算法概率分布特征分析入手, 研究质心定位算法和DV-Hop定位算法概率分布特征, 并设计了相应的分析算法, 对质心定位算法和DV-Hop定位算法的概率特征进行定量分析。
1 一种质心定位算法和DV-Hop定位算法概率分布特征的分析算法的研究
本文所研究的质心定位算法和DV-Hop定位算法概率分布特征的分析算法主要包括三个部分:首先利用质心和DV-Hop定位算法分别对未知节点进行定位;其次是利用概率分布检测方法对定位后的节点进行判断;最后分别计算两种定位算法落在规定范围内的概率大小。概率分布检测方法的设计是算法的核心部分, 本部分重点对其进行研究。
1.1 概率分布检测方法设计
质心定位算法和DV-Hop定位算法概率分布检测方法的主要思想是在利用质心和DV-Hop定位算法分别估算出目标节点位置的基础上, 分别以两种算法估算出的目标节点位置为基准点进行研究, 判断目标节点是否落在规定的范围内, 落在规定范围内则进行记录, 否则不记录。
在选择规定范围方面, 由于质心和DV-Hop定位算法都有一定的误差, 通过对节点的定位跟踪分析, 我们发现如果目标节点如果落在2倍半径之外, 说明估算出的目标点和实际目标节点差距很大, 失去了定位的意义;如果目标节点落在0.5倍半径之内, 说明估算出的目标节点非常接近实际目标节点位置。为此, 该文以1倍半径为参照, 并对讨论的范围适当进行放大和缩小至2倍和0.5倍半径, 分析两种定位算法的概率分布特征。
下面以质心定位和DV-Hop定位算法估算出的目标节点位置为基准节点, 即圆心, 以两种算法分别估算出目标节点位置之间的距离的2倍、1倍和0.5倍为半径所围成的圆这三种情况下实际目标节点的概率分布特征。如图1所示, 假设A、B两点分别为DV-Hop定位和质心定位算法估算出的目标节点的位置, r为AB之间的距离, 以估算出的目标节点位置A为基准点进行分析, 实际目标节点可能出现的位置有两种情况, 一种是落在以A为圆心, r为半径的圆内;另一种情况是落在以A为圆心, r为半径的圆外。D、D′、D〞为目标节点在这三种情况下可能出现的位置。
按照如上描述方法, 以1倍半径为例讨论如何建立概率分布检测模型, 假设目标节点di的位置为 (xi, yi) , 通过DV-Hop定位算法求出的未知节点的位置为ai, 坐标为 (pi, qi) , 通过质心定位算法求出的未知节点的位置为bi, 坐标为 (mi, ni) , 则目标节点与通过DV-Hop定位算法估算出的目标节点的距离为。
目标节点与通过质心定位算法估算出的目标节点的距离为。
通过DV-Hop定位算法估算出的目标节点ai与通过质心定位算法估算出的目标节点bi之间的距离为
如果以DV-Hop定位算法估算出的目标节点A为基准节点进行分析, 其概率检测公式如 (1) 所示:
如果以质心定位算法估算出的目标节点B为基准节点进行分析, 其概率检测公式如 (2) 所示:
2倍和0.5倍半径情况下的概率分布检测模型的建立和上述相同。
1倍、2倍和0.5倍半径情况下的概率检测公式可以统一归纳如下:
如果以DV-Hop定位算法估算出的目标节点A为基准节点进行分析, 其概率检测公式为 (3) 所示。
其中α为常量, 其值为2, 1或者0.5。
如果以质心定位算法估算出的目标节点B为基准节点进行分析, 其概率检测公式为 (4) 所示。
其中α为常量, 其值为2, 1或者0.5。
1.2 概率分布特征分析算法
概率分布特征分析算法的伪代码如下:
2 仿真结果分析
本文采用MATLAB 7.0对该算法进行仿真, 并对仿真结果进行比较分析。仿真参数设置如下表1所示, 仿真结果是经过100次仿真试验求得的平均值 (如图2到图4) 。
图2、图3、图4分别为节点通信半径为20m、30m、40m时, 质心定位算法和DV-Hop定位算法概率分布随锚节点数量变化分布图。试验结果表明, 质心定位算法在锚节点数量较少的情况下, 其落在规定范围内的概率较低, 但随着锚节点数量的增加, 特别是锚节点数量增加到20以后, 概率分布发生转折, 质心定位算法将逐渐接近并超过DV-Hop算法的概率分布, 并且节点的通信半径的改变对这种概率分布特征的影响不大。
从试验结果还可以看出, 在锚节点数量较少的情况下, DV-Hop定位算法和质心定位算法落在规定范围内的概率与锚节点数量较多情况下概率分布相比, 表现出很大的差距, 这主要是由于在锚节点数量较少的情况下, 其中很多节点误差已经非常大, 导致概率分布也呈现出较大的误差, 当锚节点数量变为20时, 随着其锚节点数量的增加, 定位误差的减小, 其概率分布也逐渐好转。
3 结束语
本文首先对质心定位算法和DV-Hop定位算法进行了分析, 接着提出了一种质心定位算法和DV-Hop定位算法概率分布特征的分析算法, 最后对该算法使用MATLAB进行仿真测试。经分析和仿真结果表明, 在100 m×100 m监测区域内, 锚节点数量个数为20是质心定位算法和DV-Hop定位算法概率分布发生变化的转折点, 并且这种变化不随节点通信半径变化而变化。同时, 我们还可以将算法中的概率检测方法应用于不同的定位算法, 验证其算法的概率分布特征, 为实际应用提供理论依据。
参考文献
[1]Chen Min Xiou, Wang Yin Din.An Efficient Location Tracking Structure for Wireless Sensor Networks[J].Computer Communications, 2009 (32) :1495-1504.
[2]He QinBin, Chen FangYue, Cai ShuiMing, et al.An efficient range-free localization algorithm for wireless sensor networks[J].SCIENCE CHINA Technological Sciences 2011, 54 (5) :1053-1060
[3]Niu YC, Zhang SD, Xu XY, et al.An enhanced DV-hop localization algorithm for irregularly shaped sensor networks[C].LNCS 4864, 2007, 694-704.
[4]NICULESCU DS.Forwarding and positioning problems in Ad hoc networks[M].New Jersey:State University of New Jersey, 2004:29-33.
[5]白进京.基于加权质心和DV-Hop混合算法WSN定位方法研究[J].计算机应用研究, 2009, 26 (6) , 2248-2250.
[6]石为人, 贾传江, 梁焕焕.一种改进的无线传感器网络DV-Hop定位算法[J].传感技术学报, 2011, 24 (1) :83-87.
质心定位 篇7
无线传感网络(wireless sensor network,WSN)中实现其应用的关键是如何能够准确定位节点的位置信息。无线传感网络中的节点定位包括锚节点和未知节点定位。其中,锚节点是指少量带有GPS定位装置的节点,由于加装GPS设备能量消耗高,因此无法广泛使用,未知节点需要通过锚节点来进行自身定位[1,2,3]。根据定位过程中测量节点间的距离,定位算法分为基于测距(range-based)的定位算法以及基于无距离(range-free)的定位算法[4]。基于测距的算法需要测量相邻节点之间的距离,利用节点之间的实际距离来计算未知节点的位置,这种算法大多对硬件要求比较高,不太适合消耗功率和成本低的应用领域,目前常用的测距技术主要有RSSI、TOA、TDOA、AOA[5,6];基于无距离的算法无需测量节点间的实际距离,而是通过节点之间的估计距离来计算节点位置,可以降低节点的硬件要求,但是节点之间定位误差会增加,常用算法主要有质心算法、DV-HOP算法[7]。其中,DV-HOP算法主要通过距离向量路由协议来获得各个锚节点的信息,但是伴随着锚节点与未知节点之间跳数距离的增加,所测算的距离也会逐渐积累,从而对接点的定位精度造成了一定的影响。
本文首先分析目前DV-HOP算法3个步骤中存在的问题,然后将加权质心算法和二维双曲线概念引入到算法中,通过加权质心算法计算校正值,将接受信号RSS作为参考标准,有效减少误差,同时针对距离估算问题采用改进的二维双曲线算法,在二维双曲线基础上引入权值概念,使得估算距离更加精确。仿真实验表明,本文算法在校正值定位误差、最大估算误差精度都有一定程度降低,相比于文献算法有明显提高。
1 基本知识
1.1 DV-Hop算法
DV-HOP算法的主要思想是将未知节点与锚节点之间的距离通过网络平均跳数和跳数的乘积来进行决定,然后通过似然估计得到节点的位置。其算法分为3个步骤:
(1)信息广播与校正值计算。在无线传感网络中,每一个锚节点都会将自己的位置信息通过数据分组的形式广播出去,设定初始化跳数为0,当未知节点记录到每一个锚节点的最小跳数时,与已经存在跳数进行比较,如果大于已存在的跳数,则忽略不计,然后将跳数值加1,继续转发其余未知节点,这样每一个未知节点就可以得到锚节点的最小跳数。
(2)校正值广播。每一个锚节点将自身校正值以广播的形式播放出去,没有定位的未知节点得到各个锚节点的校正值。
(3)未知节点定位。通过计算锚节点的校正值和自身到锚节点的跳数计算锚节点的距离。然后再通过锚节点的坐标信息和到锚节点的距离信息,计算出未知节点的坐标信息。
1.2 DV-HOP算法的不足
DV-HOP算法的3个阶段都存在一定误差,具体如下:
(1)校正值方面的误差。在无线传感网络中,所有未知节点全部使用跳数与校正值的乘积来表示距离,计算出来的估计距离与真实距离存在着很大的偏差。假设待定节点与锚节点之间的跳数为1时,采用DV-HOP算法来计算两点的距离,如图1所示。
假设节点N为未知节点,A,B,C三个节点都为锚节点,3个锚节点之间的相互之间的距离如图1所示。其中,AB之间的跳数为6,BC之间的跳数为5,AC之间的跳数为5。各个锚节点能够计算出自己的校正值。其中,节点A的校正值为:(30+110)/(6+5)=12.72,节点B的校正值为:(30+60)/(6+5)=8.18,节点C的校正值为:(60+110)/(5+5)=17。根据最近未知节点到锚节点获取校正值的原则,节点N从节点C获得校正值是17,因此节点N到3个锚节点的距离为:NA为3*17=51,NB为3*17=51,NC为17*2=34。从节点N到节点A的直线距离为42,节点N到节点B的距离为45,节点N到节点C的距离为50,因此误差分别是60-51=9,60-45=15,60-34=26,误差率分别为:9/60=15%,15/60=25%,26/60=43.3%。由于在真实的环节中,无线传感节点的分配更加复杂,通过这种定位方法,容易造成未知节点N的定位位置偏离真实位置。
(2)未知节点距离测算不准。在无线传感网络中,未知节点的位置使用校正值与锚节点之间的跳数乘积来进行代替,这种方式显然忽视了复杂情况下的节点定位,存在非常大的误差。以图1为例,NC之间通过上述方面测出的距离结果为34,而实际之间直线的距离为45,误差率为(45-34)/34=32.4%,可以发现,NC之间的实际距离是无法改变的,NC之间的测算距离决定着误差率,很显然NC之间的测算距离越接近实际距离,误差率越小,显然采用目前这种测算方法,无法尽可能减少误差。
(3)最大估算问题。目前,在DV-HOP算法中广泛采用估算法来衡量节点位置,主要是因为算法简单,容易实现,但由于未知节点需要3个以上的锚节点来确定位置,未知节点与锚节点存在误差,这样容易造成一定范围内的误差累计。
2 基于改进的加权质心和二维双曲线的DV-HOP定位算法
2.1 改进的加权质心算法
针对DV-Hop算法中未知节点定位误差导致校正值方面不准确的问题,本文将接受信号强度(RSS)作为一个权重值,用作针对未知节点的定位进行改进。以图2为例,在一个未知节点N周围存在着不同的锚节点{A,B,C,D,E,…..K},设定锚节点的坐标为A(xA,yA),B(xB,yB),C(xC,yC)…..K(xK,yK),因此未知节点N采用表1的方式来记录未知节点接收周围锚节点发出的RSSI信号的强度,未知节点与锚节点之间的路径距离以及锚节点坐标信息等。
根据信道传输模型的特点可以得出:信号传输距离越远,其RSSI的值越弱,因此锚节点对未知节点坐标求解的影响比较大,由于未知节点处于所在区域的位置不能随意更改,所以未知节点与锚节点的距离和RSSI值作为参考就显得非常重要。本文从以上两个因素考虑,将RSSI强度值的大小对比为具体的数值,然后通过RSS数值与路径距离的比值作为参考系数,通过与锚节点的坐标的乘积来确定未知节点的坐标。计算如下:
其中,RSSIN→R表示未知节点到锚节点R之间的信号强度,SN→R表示未知节点到锚节点之间的路径距离。
2.2 改进的二维双曲线定位算法
通过前述估算算法可以发现,由于DV-HOP算法通常采用似然估计法计算节点位置,这种通过3个方程组相减的方法对坐标信息具有一定程度的损失,为了避免这种误差,采用改进的双曲线定位算法,为了更好地提高节点的定位精度,引入一个误差值ε。
假设未知节点坐标为(x,y),锚节点的坐标为K(xK,yK),则未知节点与锚节点之间的距离为:
步骤1:在距离测量的过程中获得一个近似距离length′N→i
步骤2:综合公式(2)、(3)得到:
步骤3:展开公式(4)得到:
步骤4:设定S=x2+y2,T=x12+y12代入公式(5)中,得到公式(6)
步骤5:将式(6)按照矩阵进行展开,得到公式(7):
步骤6:利用误差ε最大值设定锚节点权值。从收到的锚节点中找出距离未知节点最远的锚节点,记作lengthmax,由于距离最远导致产生的误差可能比较大,设定权值为1,然后计算未知节点与锚节点之间的距离,按照不同的路径距离设定权值集。各个锚节点的权值计算按照公式(8)计算:
步骤7:将公式(8)中各个锚节点的权值按照对角矩形形式表示为:
步骤8:通过矩阵来控制锚节点与未知节点之间不同距离对于节点定位的影响。构造目标函数F:
步骤9:使用最小二乘对公式(10)进行求解,得到K=(A-TA′)-1(A-TB′),其中,
2.3 算法流程
本文算法如图3所示。
3 算法仿真与分析
为进一步验证算法的有效性和实用性,本文在Windows平台上采用Matlab2010进行仿真实验。仿真环境选择100*100的区域,选择500个节点,其中100个为锚节点,400个为未知节点,所有节点都进行随机分布。
3.1 校正值定位误差
选取本文算法与文献[8]算法在校正值定位误差上的比较,进行100次仿真实验,如图4所示
通过图4可以发现,本文算法的误差范围在8%左右,而文献[10]算法误差近20%,在校正值计算上由于采用了改进的加权质心算法,使得误差范围缩小。
3.2 最大估算定位误差
选取本文算法与文献[8]算法对最大估算定位误差进行比较,如图5所示。
通过图5可以发现,本文算法误差范围在12%左右,而文献[8]算法误差近21%,在最大估算定位选择上由于采用了改进的双曲线算法,使得最大估算误差范围缩小。
3.3 改进后的整体算法的结果
图4、图5分别从校正值误差定位和最大估算定位对两种算法进行了比较。本文算法与文献[9]、文献[10]算法从整体上进行比较,如图6所示。
4 结语
无线传感网络中未知节点的定位一直是WSN中研究的重点,特别是未知节点定位的好坏直接影响到无线传感网络效率的高低。本文针对DV-HOP算法中校正值的误差,未知节点距离测算不准以及最大估算误差进行分析,针对校正值方面存在的问题采用了改进的加权质心算法,在最大估算算法上采用了改进二维双曲线的方法,改进后的算法在定位精度上有了明显提高。
参考文献
[1]AKYILDIZ I,SU W,SANKARASUBRAMANIAM Y,et,al.A survey on snesor network[J].IEEE Communicaitons Magazine,2002,40(8):102-144.
[2]NICLESCU D,AMERIC N L.Communication paradigms for sensor networks[J].IEEE Communications Magazine,2005,43(3):116-122.
[3]BOUKERCHE A,OLIVERIRA H A,NAKAMURA E F.Localization systens for wireless sensor network[J].IEEE Wirless Communications,2007,14(6):6-12.
[4]谭志,张卉.无线传感网络RSSI定位算法的研究与改进[J].北京邮电大学学报,2013,36(3):88-91.
[5]刘运杰,金明录,崔承毅.基于RSSI的无线传感器网络修正加权质心定位算法[J].传感技术学报,2010,23(5):717-721.
[6]何艳丽.无线传感网络质心定位算法研究[J].计算机仿真,2011,28(5):163-166.
[7]NICULESCU D,NATH B.DV-based positioning in adhoc network[J].Telecommunication Systems,2003,22(1):267-280.
[8]夏少波,连丽君,王鲁娜.基于DV-Hop定位算法的改进[J].计算机应用,2014,35(5):1247-1250.
[9]李道全,刘月月,孙付龙.基于DV-HOP的WSN网络节点定位算法[J].计算机仿真,2014,31(4):303-306.
[10]金纯,叶诚,韩志斌.无线传感器网络中Dv-Hop定位算法的改进[J].计算机工程与设计,2013,34(2):18-25.
[11]苏兵,薛伟杰,王洪元.一种WSN非测距定位DV-Hop算法的误差改进方法[J].计算机测量与控制,2013,21(5):1357-1359.