基于接收信号强度的无线传感器网络质心定位算法

张颖颖

(浙江商业职业技术学院，浙江 杭州 310053)



基于接收信号强度的无线传感器网络质心定位算法

张颖颖

(浙江商业职业技术学院，浙江 杭州 310053)

摘要:针对原有质心定位算法精度低、锚节点比例过高的缺点，提出了基于接收信号强度(RSSI)的无线传感器网络质心定位算法。该算法将基于RSSI的测距值作为权重引入质心算法，通过仿真实验探寻算法模型最优权值，并运用迭代思想降低网络锚节点比例，同时采用测距校正、算法修正和设置RSSI阈值约束三种措施来控制算法误差。仿真表明，改进算法在定位精度、成本控制和环境适应性上优于原有质心定位算法。

关键词:无线传感器网络；定位算法；接收信号强度；迭代加权质心算法

0引言

无线传感器网络(Wireless Sensor Network，WSN)是无线通信技术、微机电系统和片上系统高度集成而发展出的一种新型信息获取和处理方式[1-2]。其工作形式为：将大量费用低廉体积微小的传感器节点随机部署在监测区域，相邻节点间可以相互通信，形成一个多跳的自组织网络，节点携带的传感器探测周边坏境的物体性状、部署、变化等信息，通过无线通信技术将所测数据传回设备终端，从而实现环境和研究者之间的信息交互。可广泛适用于国防军事、环境监测、远程控制等领域。

节点定位是无线传感器网络技术的重要环节，传感器节点所收集到的数据信息必须结合其所在的位置才有意义。为了降低成本，无线传感器网络的常规部署是让尽量少的一部分节点携带GPS，这部分已定位节点称为锚节点，其余大部分不携带GPS的未定位节点需通过与其附近区域内锚节点间的信息交流来计算自身的位置信息。因此，如何针对无线传感器网络密集型、低成本、低能耗的特点来设计有效的节点定位算法，对于无线传感器网络研究具有重要的理论意义和应用价值。

根据是否需要节点间的距离，国内外现有的节点定位算法可以分为两大类[3]：基于测距的定位算法(range-based)和基于非测距的定位算法(range-free)。基于非测距的定位算法[4-7]有质心算法、DV-Hop算法、凸规划法、APIT定位算法等，这些算法在简单性、可操作性、可扩展性等方面有较大优势，但在定位精度上逊于基于测距的算法。其中，经典的质心定位算法有其突出的性能优点，那就是实现简单、硬件要求较低并且通信开销小，适用于定位精度要求不高的无线传感器网络，在应用中得到了很大的认可。但是，质心算法较大的定位误差和较高的已知节点密度是其最大的缺陷，限制了算法的应用范围。本文针对此问题，提出了基于RSSI的无线传感器网络质心定位算法。

1质心定位算法

质心定位算法[4]是一种无需测距，基于网络连通性的定位算法。其思路是：无线传感器网络中的锚节点每隔一定时间广播一个无线信号，信号中包含自身ID及位置信息，周边的未定位节点接收到信号后，根据系统预设的阈值进行判断，确定与哪些锚节点是连通的，将自身位置定位为所有连通的锚节点所组成多边形的质心。假设某未知节点(x,y)其连通范围内锚节点坐标为(x1,y1),(x2,y2),…,(xn,yn), 则该未知节点的定位为：

(1)

显然，传统的质心定位算法实现非常简单，但要达到理想的定位精度，必须提高锚节点密度，并且对锚节点分布的均匀性要求较高，在实际应用中有较大的限制。因此，一些研究者对其进行了改进，其中一种改进思路是结合测距定位算法精度较高的优点，进一步提升质心定位算法性能。在结合测距算法中，常见的测距技术有RSSI、TOA、TDOA和AOA，这些技术在不同的环境和应用中各有其特点。其中，基于接收信号强度的测距技术RSSI(ReceiveSignalStrengthIndication)在无线传感器网络中具有较大优势，使用率最高[8]，因为无线传感器网络中的传感器节点本身可以方便地进行相互间信号的发送和接收，无需增加额外硬件支持，操作方便且易于实现。因此，综合能耗、误差、成本、可操作性等因素，本文所涉及的测距均使用RSSI技术。

在改进算法中，文献[9—10]将RSSI值作为权重引入质心定位算法。RSSI值越大，说明这两个节点间的距离越近，这个锚节点坐标在计算过程中所占的权重也就越大，从而对未知节点坐标定位的影响度增大。算法公式为[10]：

(2)

式(2)中，RSSIi表示未知节点接收到的第i个锚节点的信号强度值。此算法在不增加硬件资源的前提下，定位精度比传统质心定位算法要高。

在实际应用中，RSSI值受外界环境影响较大，存在一定的误差，而无线传感器网络覆盖区域大，外界环境复杂，单纯使用RSSI值作为权值的质心定位算法在操作中不易修正误差值，影响算法的定位精度。因此，文献[11—12]提出，把节点间距离值d作为权重系数引入质心定位算法，利用距离值d方便修正误差的优点来提升定位精度。由于节点间距离值d越大，其RSSI值越小，反之距离值d越小，其RSSI值越大，因此以距离值d的倒数作为权重，算法公式为[11]：

(3)

式(3)中，di为未知节点接收到的第i个锚节点的测距值。由于未知节点位置信息不明，无法与其余节点间进行直接测距，这里的节点间距离值d基于Shadowing信号转化模型[13]：

(4)

式(4)中，信号接收强度RSSI单位为dBm，参数A表示距离发射中心1m处传感器节点所接收信号强度值，n是和信号传输环境相关的路径损耗指数。其中A和n的取值随着环境不同相应变化[14]。

算法中距离值d的修正方案为：用已知锚节点间的实际距离值与以锚节点为未知节点进行测距得到的距离值进行误差比对分析，取误差平均值为全网测距误差校正值，对所有测距得到的未知节点距离值d进行误差修正。此算法在定位精度上高于传统质心定位算法和直接基于RSSI值的算法。

针对质心定位算法中锚节点数目过多的缺点，文献[15]在公式(3)的基础上提出了迭代式加权思想。思路是：若某未知节点通信范围内锚节点数目大于等于3个，用加权质心定位算法进行定位；若锚节点数目小于3个，则把可通信范围内已定位的未知节点升级为锚节点参与后续定位。算法公式为[15]：

(5)

2增强的质心定位改进算法

在上述原有质心算法的基础上，本文提出了一种增强的基于RSSI的无线传感器网络质心定位改进算法，通过改进算法数学模型和加强误差控制两方面措施来提升算法性能。

2.1算法模型改进

2.1.1算法权值调整

在加权算法中，算法模型权重取值的合理性对最终定位精度的影响很大，直接关系到整个算法性能的优劣。公式(2)和(3)的算法均基于RSSI，而公式(3)考虑了RSSI值的系统环境误差，以节点间测距值d为权值，采用测距校正的措施来修正误差，进一步提升了定位精度。本文保留以测距值d为权值利于修正误差的优点，但对此权值是否可以进一步优化展开探讨。

由Shadowing模型公式(4)的变形：

(6)

可知，在参数A和n取定的前提下，测距值d的倒数与RSSI之间并非简单的线性关系，而是更接近指数级的关系。因此，结合公式(2)、(3)，并考虑算法模型的简洁和操作性，把原有公式(3)中的权值d的倒数调整为d的倒数的t次方，探讨t是否有优于1的取值。调整后的算法公式为：

(7)

式(7)中，di为未知节点(x,y)与其通信范围内第i个锚节点(xi,yi)间的校正测距值。系数t为最优权值系数，定义为相同定位条件下，在适当的取值区间内，使得算法定位误差最小时所对应的值。系数t最优值的探讨是通过仿真实验，围绕原有算法公式中的取值t=1，在同等定位条件下，以0.1为步长取遍一定的取值区间，对每一个t值对应的算法公式进行仿真实验，以算法的定位精度为评价标准，探寻在t值变化时算法定位误差最小，也即定位精度最优时对应的t值。

在仿真实验中，具体仿真环境和仿真条件设置详见第3章，仿真中t的取值范围为[0.5, 2.5]，在具体实验中，超出此范围时结果变化极小，故忽略不计。仿真结果如下：

1)给定仿真条件为节点总数100，定位区域大小100m×100m，通信半径30m，λ取15%，测距误差介于[-λ,λ]时，改变锚节点密度，结果如表1。

表1　不同锚节点密度下的t值

2)给定仿真条件为节点总数100，锚节点10，通信半径30 m，λ取15%，测距误差介于[-λ,λ]时，改变定位区域大小，结果如表2。

3)给定仿真条件为节点总数100，锚节点10，定位区域大小100 m×100 m，通信半径30 m，测距误差介于[-λ,λ]时，改变环境影响参数λ，结果如表3。

表2　不同定位区域下的t值

表3　不同环境影响下的t值

由仿真实验结论可知，改进公式中的最优权值系数t主要与无线传感器网络中的锚节点密度有关，与定位区域大小及环境干扰情况无关。即对于一个预先设定的无线传感器网络，公式(7)中t值的确定由网络中已知的锚节点密度决定，如密度为5%，则t取1.7，如密度为10%，则t取1.9，具体取值见表2。

2.1.2引入迭代思想

运用迭代计算，把已定位的未知节点升级为锚节点参与后续定位运算，从而解决质心定位算法锚节点比例过高的缺陷。结合原有算法公式(5)，改进算法数学模型调整为：

(8)

式(8)中的权值系数t取值同公式(7)，qi取值同公式(5)。

2.2误差控制

2.2.1局部式测距校正

在基于RSSI测距的定位算法中，由于信号在传输过程中极易受外界因素干扰，直接影响最终的定位精度，原有算法通过测距校正的方法对此进行误差修正。但在实际应用中，大型的无线传感器网络分布情况比较复杂，各个区域内环境影响程度不同，所产生的测距误差也各不相同。因此，原有算法的全网测距误差校正无法体现网络环境的复杂性，应以个体节点为中心，在其通信范围内根据其区域特点进行局部测距校正，更利于降低测距误差，提高算法对环境的自适应。实施方法为：

(9)

则锚节点i在通信范围内测距误差校正值ui为：

(10)

(11)

2.2.2迭代误差控制

由接收信号强度特点，节点距离越远，接收的RSSI值误差越大，尤其当此节点是由未知节点定位后升级所成时，如果继续参与后面的迭代计算，会造成相当大的误差累加。因此，算法中如果要用到这一部分升级节点时，可以通过设置距离阈值，仅选择距离比较近的那部分升级节点参与后续定位。

距离阈值设定方法：如果要用到升级节点，需要先判断其接收的RSSI值是否在设定的门限范围内，如果符合，则接收其发送的信息参与定位计算，如果不符合，则放弃该节点信息。门限设定时结合网络情况，若网络平均连通度较高，则此待定位节点的邻居节点数目比较多，可选择余地大，门限范围相应可以收紧，比如阈值设为其最大通信半径对应RSSI值的2倍，过滤掉较远处误差大的升级节点，保证一定的定位精度。若网络平均连通度较低，则门限范围相应放松，比如阈值设为最大通信半径对应RSSI值的1.5倍或者更小，以保证一定的定位覆盖率。

2.2.3算法误差修正

导致定位误差的因素除了测距误差和环境影响外，另一个重要原因就是定位算法本身带来的误差。改进算法中给出了算法误差补偿措施，具体方法是：

把锚节点i当成未知节点进行定位，由估算坐标(xci,yci)和实际坐标(xi,yi)得到定位误差：

(12)

把此定位误差(uxi,uyi)作为该锚节点自身信息加以储存并广播，周围的未知节点j接收信息后，求出其通信范围内所有n个锚节点定位误差的平均值作为自身的定位误差校正值：

(13)

(14)

2.3增强的质心定位改进算法实现步骤

改进算法实现步骤如下：

1)网络初始化，锚节点每隔一段时间向周围广播信息；

2)所有节点接收邻居锚节点信息，把接收到的RSSI平均值换算成距离值d并校正；

3)未知节点在其通信区域内的锚节点数若大于等于3个，则用改进算法公式进行定位计算；

4)逐一检查未定位节点，在其通信区域内接收步骤3)中新一轮定位的节点信息，判断所接收的RSSI值是否属于所设阈值范围，若是，升级为锚节点(全部由升级锚节点实现定位的节点不能再升级)，若锚节点数不小于3，回到步骤3)，若所有节点均已定位或者没有增加新的定位节点，转到步骤5)，若未定位节点周围锚节点数小于3且没有可升级的，标为不可定位；

5)进行算法误差修正，得到最终坐标。

3算法仿真分析

3.1仿真环境设置

为了验证算法的有效性，采用Matlab软件进行仿真。仿真环境设定为：100个节点随机部署在100m×100m区域，锚节点比例按需要设定，由于无法真实模拟实际环境中信号接收强度RSSI值的接收情况，故节点定位后升级成锚节点的RSSI阈值用距离阈值表示，阈值取节点通信半径R的70%，引入测距误差系数λ来模拟环境影响，所有仿真结果取10次仿真的平均值。

在仿真中，将原有的公式(3)对应的算法称为WCLA算法；原有的公式(5)对应的算法称为IWCLA算法；本文的改进算法称为IWCLAAdvanced算法，公式见(8)。仿真主要针对这三种算法进行比较和分析。

3.2仿真结果分析

3.2.1锚节点密度对定位的影响

取锚节点数为5、10、15、20、25、30，节点通信半径R为30m，λ取15%，测距误差为介于[-λ,λ]之间的随机误差。仿真结果见图1和图2，由图2可知，锚节点为5个时WCLA算法的定位覆盖率过低，研究其定位精度无实际参考意义，故图2中锚节点数从10开始。

仿真表明：当锚节点数目变化时，改进算法在定位覆盖率上远超WCLA算法并与IWCLA算法基本持平，在定位精度上高于IWCLA算法并与WCLA算法基本持平，说明其在提高定位覆盖率的同时仍能维持较高的定位精度，算法综合性能优于原有算法。

3.2.2测距误差对定位精度的影响

一般而言，测距误差和网络所在环境的影响程度密切相关。这里λ值取5%、10%、15%、20%、25%、30%，为了体现实际环境中不同区域受不同因素影响的局部性环境特点，仿真中，把节点分布区域按田字格形状均分成四块，每块区域测距误差分别为[-λ,-0.5λ]、[-0.5λ,0]、[0,0.5λ]、[0.5λ,λ]，这样即体现了局部环境差异也保证了整体区域测距误差仍然为[-λ,λ]之间的随机误差。此外，节点通信半径R取30m，锚节点数取15。仿真结果见图3。

仿真表明：改进算法定位精度最优，IWCLA算法受环境影响最大。随着测距误差的增大，改进算法中的局部测距校正和算法修正策略使其比原有算法在定位精度这个性能上体现出更好的稳定性。因此，改进算法与原算法相比，更适用于环境复杂的布设区域，在环境自适应性上有更大的改善。

3.2.3节点通信半径对定位精度的影响

本次实验通过逐渐调整节点通信半径R，也即在不同的网络连通度情况下研究算法定位性能。实验中R取20m、25m、30m、35m、40m、45m，锚节点数取15，λ取15%，测距误差为介于[-λ,λ]之间的随机误差。仿真结果见图4。

图1　锚节点数目对定位覆盖率的影响Fig.1　The influence of anchor node number to location coverage

图2　锚节点数目对定位精度的影响Fig.2　The influence of anchor node number to location accuracy

图3　测距误差对定位精度的的影响Fig.3　The influence of distance-measuring error to location accuracy

图4　节点通信半径对定位精度的的影响Fig.4　The influence of node communication radius to location accuracy

仿真表明：改进算法相比原有算法定位精度较高，在通信半径变化过程中受影响程度最小，定位性能最稳定。

4结论

本文提出了基于RSSI的无线传感器网络质心定位改进算法。该算法将基于RSSI的测距值作为权重引入质心算法，通过仿真实验探寻算法模型最优权值，并运用迭代思想降低网络锚节点比例，同时采用测距校正、算法修正和设置RSSI阈值约束三种措施来控制算法误差。仿真表明，改进算法在定位精度、成本控制和环境适应性上优于原有质心定位算法。进一步提高定位精度，并将算法推广到三维定位是下一步研究的方向。

参考文献:

[1]孙利民，李建中，陈渝，等. 无线传感器网络[M]. 北京: 清华大学出版社，2005.

[2]YickJ,MukherjeeB,GhosalD.Wirelesssensornetworksurvey[J].ComputerNetworks,2008,52(12):2292-2329.

[3]史洪宇，燕莎，曹建忠. 无线传感器网络节点定位的混沌粒子群优化算法[J].探测与控制学报，2010,32(5):46-49.

[4]BulusuN,HeidemannJ,EstrinD.GPS-lesslow-costoutdoorlocalizationforverysmalldevices[J].PersonalCommunications,IEEE, 2000, 7(5): 28-34.

[5]HeT,HuangCD,BlumBM,etal.Range-freelocalizationschemesforlargescalesensornetworks[C]//Proceedingofthe9thAnnualInternationalConferenceonMobileComputingandNetworking.SanDiego:ACMPress,2003: 81-95 .

[6]马骏，王敬东，温家旺，等.RSSI与凸规划相结合的无线传感器网络定位算法[J].指挥控制与仿真, 2013, 35 (4): 60-65.

[7]李牧东，熊伟，梁青，等. 无线传感器网络DV-Hop定位算法研究[J].空军工程大学学报(自然科学版), 2012, 13 (4): 77-80.

[8]吕鹏元. 无线传感器网络定位算法研究[D]. 西安：西安电子科技大学, 2009.

[9]何艳丽. 无线传感器网络质心定位算法研究[J]. 计算机仿真, 2011, 28 (5): 163-166.

[10]李文辰，张雷. 无线传感器网络加权质心定位算法研究[J]. 计算机仿真, 2013, 30(2): 191-194.

[11]张婵爱，马艳艳，白凤娥，等. 基于RSSI的加权质心定位算法的实现[J]. 太原理工大学学报, 2009, 40 (2): 146-148.

[12]王振朝，张琦，张峰. 基于RSSI测距的改进加权质心定位算法[J]. 电测与仪表, 2014, 51 (21): 63-66.

[13]朱明辉，张会清. 基于RSSI的室内测距模型的研究[J]. 传感器与微系统, 2010, 29(8): 19-22.

[14]AliS,NoblesP.AnovelindoorlocationsensingmechanismforIEEE802.11b/gwirelessLAN[C]//TheFourthWorkshoponPositioning,NavigationandCommunication(WPNC’ 07).Hannover:WPNCPress,2007: 9-15.

[15]王新芳. 面向消防现场的无线传感器网络定位技术研究[D]. 镇江：江苏科技大学, 2012.

Wireless Sensor Networks Centroid Location Algorithm Based on Receive Signal Strength Indication

ZHANG Yingying

(Zhejiang Vocational College of Commerce，Hangzhou 310053, China)

Abstract:To improve the positional accuracy and reduce the anchor node proportion of classic centroid localization algorithm, a new localization algorithm based on RSSI was proposed in this thesis. Firstly, the new algorithm introduced weighted centroid algorithm based on the distance. With conditions changing, the optimal weight was found through simulation. Secondly, the new algorithm introduced iterative thoughts to reduce the anchor nodes proportion. Finally, three measures are proposed to control the error of new algorithm. They are local distance correction, positioning error correction, and threshold setting. The simulation indicated that the new algorithm had better performance on positioning accuracy , cost control and environmental adaptability.

Key words:wireless sensor network; localization algorithm; RSSI; iterative weighted centroid algorithm

中图分类号:TP393

文献标志码:A

文章编号：1008-1194(2016)02-0103-06

作者简介:张颖颖(1975—)，女，浙江杭州人，硕士，讲师，研究方向：应用数学、无线传感器网络定位算法。E-mail:zyy@zjbc.edu.cn。

基金项目:浙江省教育厅科研项目资助(Y201534402)

*收稿日期:2015-10-09