基于ＲＳＳＩ的无线传感器网络三角形质心定位算法

林　玮　陈传峰

摘 要：节点定位是无线传感器网络中的关键技术之一。基于RSSI的定位技术是现阶段研究的热点，为解决RSSI测量方法定位误差较大的问题，提出一种将RSSI测量方法与三角形质心算法相结合的新型定位算法，该算法用三角形质心算法减小RSSI的测量误差。仿真表明该算法比基于RSSI的三边测量法定位算法的定位精度有较大提高。

关键词：无线传感器网络;定位算法;RSSI;质心;三角形质心定位算法

中图分类号：TP393文献标识码：B

文章编号：1004 373X(2009)02 180 03

RSSI－based Triangle and Centroid Location in Wireless Sensor Network

LIN Wei,CHEN Chuanfeng

(College of Physics and Information Engineering,Fuzhou University,Fuzhou,350002,China)

Abstract：Node location is one of the key technologies in wireless sensor network.RSSI－based location is a hotspot in nowadays.For resolving biggish error in RSSI－based location,the paper presents a new method of location,RSSI－based triangle and centroid location,using triangle and centroid method to reduce the error of RSSI measurement.Simulation experiments prove that this algorithm can obviously improve the location accuracy compared to trilateration.

Keywords：wireless sensor network;location algorithm;RSSI;centroid;triangle and centroid location algorithm

0 引 言

无线传感器网络是面向事件的监测网络，对于大多数应用，不知道传感器位置而感知的数据是没有意义的［1］。实时地确定事件发生的位置或获取消息的节点位置是传感器网络最基本的功能之一，也是提供监测事件位置信息的前提，所以定位技术对传感器网络应用的有效性起着关键的作用［2］。

在无线传感器网络中，按节点位置估测机制，根据定位过程中是否测量节点间的实际距离或角度，可分为基于距离(Range－based)的定位算法和距离无关(Range－free)的定位算法［3］。前者需要测量节点间的实际距离；后者是利用节点间的估计距离来计算末知节点的位置。在基于距离的定位算法中，测量节点间距离或方位时采用的方法有TOA(Time of Arrival)，TDOA(Time Difference of Arrival)，RSSI(Received Signal Strength Indication)和AOA(Angle of Arrival)。距离无关的算法主要有质心算法、DV－hop算法等。相比之下，基于距离的定位算法测量精度较高，距离无关的定位算法对硬件要求较低。

比较各种基于距离的测距算法，TOA需要精确的时钟同步，TDOA需要节点配备超声波收发装置，AOA需要有天线阵列或麦克风阵列，这三种算法对硬件要求较高。RSSI技术主要是用RF信号，而节点本身就具有无线通信能力，故其是一种低功耗、廉价的测距技术。

接收信号强度指示RSSI的定位方法，是在已知发射节点的发射信号强度，根据接收节点收到的信号强度，计算出信号的传播损耗，再利用理论和经验模型将传输损耗转化为距离，最后计算节点的位置。因为理论和经验模型的估测性质，故而RSSI具有较大定位误差。

基于RSSI技术，提出一种将RSSI测量方法与三角形质心算法相结合的新型定位算法，该算法用三角形质心算法减小RSSI的测量误差。仿真表明，该算法基于RSSI的三边测量法

定位算法相比，极大提高了定位精度。

1 国内外相关研究

当无线信号在大气环境中传播时，由于多种因素影响，信号强度会随着其传播距离的增加而

衰减。这表明，信号强度变化与传播距离间存在着某种函数关系，且通常情况下传感节点均可很容易配置测定接收信号强度的模块。所以，近年来研究人员开始将RSSI技术用于传感器节点定位中。

目前，对RSSI的研究主要有两个方面。一是，提高改良传输损耗模型，建立更符合实际环境的数学模型；二是，结合各种测量算法，减小传输损耗模型带来的误差。这里研究重点在第二个方面。

最早的研究人员使用RSSI加三边测量法的定位技术，如文献［4］中的RADAR室内定位系统。

文献［5］的作者提出采用交叠环定位的方式，利用包含未知节点的相互交叠的环形区域来定位未知节点。该方法只是比较相应RSSI的大小，并未利用它测距。

文献［6］提出一种加权质心定位算法，它提出信标节点影响力的概念，节点到信号源的距离越近，由RSSI值的偏差产生的绝对距离误差越小，影响力越大。影响力越大的信标节点对节点位置有更大的决定权。其采用优选信标节点的方式，根据信标节点对未知节点的不同影响力确定加权因子，以此来提高定位精度。

文献［7］提出综合RSSI算法和切圆圆心法的RCM算法，提高了定位精度，仿真表明，在RSSI测距误差散布达到50％时，定位误差可降到10％以内。

2 基于RSSI的三角形质心算法模型

与文献［6］一样，该算法针对大规模随机散布野外应用环境，这类应用大都不需要节点进行精确定位，只需要知道节点的大概区域就可满足需求，同时要求硬件成本低、定位过程通信开销小、节能。

2.1 基于RSSI的定位

RSSI测量，一般利用信号传播的经验模型与理论模型［2,6］。

对于经验模型，在实际定位前，先选取若干测试点，记录在这些点各基站收到的信号强度，建立各个点上的位置和信号强度关系的离线数据库(x,y,ss1,ss2,ss3)。在实际定位时，根据测得的信号强度(ss1′,ss2′,ss3′)和数据库中记录的信号强度进行比较，信号强度均方差最小的那个点的坐标作为节点的坐标。

对于理论模型，常采用无线电传播路径损耗模型进行分析［8－10］。常用的传播路径损耗模型有：自由空间传播模型、对数距离路径损耗模型、哈它模型、对数－常态分布模型等。自由空间无线电传播路径损耗模型为：

Loss=32.44+10klog10 d+10klog10 f(1)

式中，d为距信源的距离，单位为km；f为频率，单位为MHz；k为路径衰减因子。其他的模型模拟现实环境，但与现实环境还是有一定的差距。比如对数－常态分布模型，其路径损耗的计算公式为：

PL(d)=PL===(d0)+10klog(d/d0)+Xσ(2)

式中，Xσ是平均值为0的高斯分布随机变数，其标准差范围为4~10；k的范围在2~5之间。取d＝1，代入式（1）可得，Loss，即PL===(d0)的值。此时各未知节点接收锚节点信号时的信号强度为：

RSSI＝发射功率＋天线增益－路径损耗（PL(d)）

2.2 基于RSSI的三角形质心定位算法的数学模型

不论哪种模型，计算出的接收信号强度总与实际情况下有误差，因为实际环境的复杂性，换算出的锚节点到未知节点的距离d总是大于实际两节点间的距离。如图1所示，锚节点A，B，C，未知节点D，根据RSSI模型计算出的节点A和D的距离为r瑼 ；节点B和D的距离为r瑽 ；节点C和D的距离为r瑿。分别以A，B，C为圆心；r瑼 ，r瑽 ，r瑿 为半径画圆，可得交叠区域。这里的三角形质心定位算法的基本思想是：计算三圆交叠区域的3个特征点的坐标，以这三个点为三角形的顶点，未知点即为三角形质心，如图2所示，特征点为E，F，G，特征点E点的计算方法为：

(x璭－x璦)2+(y璭－y璦)2≤r璦

(x璭－x璪)2+(y璭－y璪)2=r璪

(x璭－x璫)2+(y璭－y璫)2=r璫（3）

同理，可计算出F，G，此时未知点的坐标为x璭+x璮+x璯3，y璭+y璮+y璯3。由仿真得，在图2中，实际点为D；三角形质心算法出的估计点为M；三边测量法算出的估计点为N。可知，三角形质心算法的准确度更高。

图1 三个有交集的图

图2 三角形质心算法

3 基于RSSI的三角形质心算法过程

3.1 步骤

（1） 锚节点周期性向周围广播信息，信息中包括自身节点ID及坐标。普通节点收到该信息后，对同一锚节点的RSSI取均值。

（2） 当普通节点收集到一定数量的锚节点信息时，不再接收新信息。普通节点根据RSSI从强到弱对锚节点排序，并建立RSSI值与节点到锚节点距离的映射。建立3个集合。

锚节点集合：

B_set={a1，a2，…，a璶}

未知节点到锚节点距离集合：

D_set={d1，d2，…，d璶}，d1＜d2＜…d璶

锚节点位置集合：

P_set={(X1，Y₁)，(X2，Y2)，…，(X璶，Y璶)}

（3） 选取RSSI值大的前几个锚节点进行自身定位计算［4］。

在B_set中优先选择RSSI值大的信标节点组合成下面的锚节点集合，这是提高定位精度的关键。

T_set={(a1,a2,a3),(a1,a2,a4),…,

(a1,a3,a4),(a1,a3,a5)…}

对锚节点集合，依次根据（3）式算出3个交点的坐标，最后由质心算法，得出未知节点坐标。

（4） 对求出的未知节点坐标集合取平均，得未知节点坐标。

3.2 误差定义

定义定位误差为ER，假设得到的未知节点的坐标为(x璵,y璵)，其真实位置为(x,y)，则定位误差ER为：

ER=(x璵－x)2+(y璵－y)2

4 仿 真

利用Matlab仿真工具模拟三角形质心算法，考察该算法的性能。假设在100 m×100 m的正方形区域内，36个锚节点均匀分布，未知节点70个，分别用三边测量法［2］和三角形质心定位算法进行仿真，仿真结果如图3所示。由图3可知，三角形质心算法比三边测量法，定位精度更高，当测距误差变大时，用三角形质心算法得出的平均定位误差比用三边测量法得出的小得多。

5 结 语

在此提出了将RSSI方法和三角形质心定位算法相结合的方法，通过仿真实验，将该算法和三边测量算法相比较，证明了该算法的优越性。下一步将研究在锚节点数量不同时的平均定位误差。

图3 平均定位误差

参考文献

［1］Rabacy J J,Ammer M J,da Silva Jr J L,et al.Picorodio Supports Ad Hoc Ultra－low Power Wireless Networking ［J］.Computer,2000,33(7):42－48.

［2］孙利民,李建中,陈渝,等.无线传感器网络［M］.北京:清华大学出版社,2005.

［3］He T,Huang C D,Blum B M,et al.Range－Free Localization Schemes in Large Scale Sensor Networks［A］.In:Proc.of the 9th Annual Int′l Conf.on Mobile Computing and Networking.San Diego: ACM Press,2003:81－95.

［4］Elson J,Griod L,Esrein D.Fine－grained Network Time Synchronization Using Reference Broadcasts.In:Proc.5th Symp.Operating Systems Design and Implementation (OSDI 2002).Boston,MA.2002.

［5］Liu Chong,Wu Kui,He Tian.Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator［A］.2004 IEEE International Conference on Mobile Ad－Hoc and Sensor Systems.2004.

［6］陈维克,李文锋,首珩,等.基于RSSI的无线传感器网络加权质心定位算法［J］.武汉理工大学学报，2006,20(12):2 695－2 700.

［7］邓宏彬,贾云得,刘书华,等.一种基于无线传感器网络的星球漫游机器人定位算法［J］.机器人，2007(4):384－389.

［8］汪炀.无线传感器网络定位技术研究［D］.合肥：中国科学技术大学,2007.

［9］余义斌.传感器网络定位算法及相关技术研究［D］.重庆：重庆大学,2006.

［10］端木庆敏.无线传感器网络节点定位算法研究［D］.长沙：国防科学技术大学,2006.

作者简介 林 玮 女，1982年出生，福建福清人，硕士研究生。主要研究方向为无线传感器网络。

陈传峰 男，1963年出生，福建福州人，副教授，研究生导师。主要研究方向为计算机网络，无线传感器网络。