无线传感器实验报告

1、基于锚同心圆的改进加权质心WSN定位算法的阅读报告 111905040 双控 朱夏冰本论文研究无线传感器定位准确性问题，针对测量位置节点信息，为了提高无线传感器网络的定位精度，采用同心圆定位算法(1)(CAB)是一种免测距的无线传感器定位算法，相比于传统的测距方法能降低节点的能量消耗，但是定位精度却不及传统的测距定位方法。提出在同心圆定位算法(2)(CAB)的基础上，通过分析无线电传播路径损耗采用了一种加权同心圆定位算法。给出了算法的流程，仿真分析了通信半径对新算法定位精度的影响，比较了算法定位精度与现有的几种免测距定位方法的定位精度。仿真结果表明，改进算法有较高的定位精度而且对距离不敏感，对

2、实际工程提供应用价值。本论文使用的方法是同心圆定位方法。同心圆定位方法(Concentric Anchor Beacons，CAB)(3)是目前免测距中比较实用的一种方法，目前，国内有很多学者对CAB算法提出了改进，文献(4)提出了一种利用相邻圆环内的未知节点相互通信的方式来减小交叉面积，从而提高定位精度的方式，然而该方法不可避免地增加了节点的能量开销。文献(5)提出了一种利用多能量级广播信号实现节点位置估计的分布式节点定位方法，该方法实际上是在CAB算法的基础上通过画线来优化信标节点的选取，虽然将误差因子的影响降到最低，但却极大地增加了时间复杂度。由于信标节点对未知节点的影响力不一样，显然C

3、AB算法以及这些改进算法均没有考虑信标节点影响力的概念。为了进一步提高CAB算法的定位精度，本文提出了一套权值方案来体现信标节点影响力，该方案计算简单且无需节点间的通信开销，相对于CAB算法本文算法能明显提高未知节点的定位精度。锚同心圆定位原理假设节点具有理想的球形无线信号传播范围。在本文中，以二维平面情况为例，锚同心圆就是以锚节点为圆心，分别以若干个无线射程为半径的同心圆集合(6)。为了实现未知节点的有效定位，未知节点必须要收到至少三个锚节点的广播信标消息。如图1所示，假设未知节点能够收到来自三个信标节点的第二级功率辐射(图中r2以标注) ，则未知节点必然位于三个信标节点圆环的公共区域。图1

4、 锚同心圆节点定位示意图如图1的情况，假设三个信标节点的坐标分别为( xb1，yb1)、( xb2，yb2)、( xb3，yb3)，节点的无线射程分别为r1和r2。记三个锚节点的信号公共覆盖区域的边界交汇点为( xjn，yjn)，其中( n= 1, 2, 3)。则公共区域的边界交汇点可以用以下方程两两求解得到：( xjxb1) 2+ ( yjyb1)2 = r12( xjxb1)2 + ( yjyb1)2 = r22( xjxb2) 2+ ( yjyb2)2 = r12 (2)( xjxb2)2 + ( yjyb2)2 = r22( xjxb3) 2+ ( yjyb3)2 = r12( xjx

5、b3)2 + ( yjyb3)2 = r22同时，对图1的情况，其交汇点的有效区域由下式规定：r12xj-xb12+yj-yb12r22 r12xj-xb22+yj-yb22r22 (3)r12xj-xb32+yj-yb32r22 (2)式中方程两两解方程，必然会求出很多的交点。如图1示，虽然求出18个交点，但有效的交点却只有5个。为了挑选出有效交点，判断方法如下：先求出第一个锚节点与第二个锚节点的所有锚同心圆的交点，再利用这些交点与第三个锚节点功率环之间的关系判断计算出的交点是否为有效交点(7)。依此再作两次判断。三次判断的有效交点共同围成了未知节点有效定位区域。如图1中存在共5个有效边界交

6、点，其坐标分别为：( xj1，yj1)、( xj2，yj2)、( xj3，yj3)、( xj4，yj4) 、( xj5，yj5)。按照CAB算法, 未知节点的坐标估计值可由它们的平均值求得, 即：xunknow=n=15xjn5 yunknow=n=15yjn5 (4)锚同心圆加权质心算法，文献(8)首次提出了RSSI信标节点影响力的概念，认为信标节点对未知节点的估计位置有影响力大小之分。即RS-SI越大的信标节点，其影响力越大，对节点位置有更大的决定权。按照这个思想显然(4)式没有反映出不同信标节点对未知节点定位影响力的大小，这将影响定位精度。为了进一步提高定位精度，将通过分析无线信号传播模

7、型提出一种基于锚同心圆的改进加权质心定位算法。在文献(6)中, 作者已经证实了CAB方法在系统选用两个功率等级来进行定位时, 其表现相对于质心算法能极大地减小节点的定位误差；而当更进一步选用三个功率等级时，由于实际信号辐射圆域的非理想性, 其定位表现增强得并不多。因此本文选用两个功率等级来执行锚同心圆算法。本文引用如下的加权因子：w1= d2 + d3、w2= d1 + d3、w3= d1+ d2。由(1)式可以得，d=prd0prdd0 (5)则权值方案可表示为， w1=1prd2+1prd3 w2=1prd1+1prd3 (6)w3=1prd1+1prd2 引入加权因子w1，w2，w3后可

8、得，xi=w1jk23xj23+w2jk13xj13+w3jk12xj12k23w1+k13w2+k12w3 yi=w1jk23yj23+w2jk13yj13+w3jk12yj12k23w1+k13w2+k12w3 (7)上式中，(xi，yi )代表未知节点(xi，yi)的估计位置, w1、w2、w3由式(6)给出。k23是由锚节点2组成的锚同心圆与锚节点3组成的锚同心圆的有效交点的个数，xj23是由锚节点2组成的锚同心圆与锚节点3组成的锚同心圆的有效交点。其他变量如k13，xj13，k12，xj12等, 其意义可依此类推。算法流程步骤一：每个锚节点周期性地分别以一定信号强度进行广播，其中广播

9、消息包括了锚节点的位置信息，标识信息(第一功率级或第二功率级)。步骤二：每个未知节点收到广播信息后，对同一锚节点的RSSI值取均值, 并分别存储能收到广播信息的锚节点的位置信息以及功率级。步骤三：优选信标节点。设某未知节点能收到m个锚节点的广播信息，则在上一步的基础之上，对其确定优选信标节点的坐标，讨论如下：若m=1，即某个未知节点只能收到一个锚节点，则不能定位，抛弃；若m=2，即某个未知节点只能收到两个锚节点，则就选取这两个锚节点为下一步定位的锚节点。若m3，则此时有Cm3个可能的三角形供优化选择，取这些三角形中面积最大者的三个顶点为优选的信标节点。步骤四：估计位置节点的位置信息。位置的估计

10、公式由(7)式给出, 其中权值的取定参考( 6)式。本文所使用的方法中定位精度与通信半径的关系为了验证本算法的性能，采用MATLAB 7.0.1实现上述算法，实验所用PC 机为奔腾2.60GHz/1.93G RAM。在200m200m 的区域内随机撒播300个未知节点，在这些节点中选取锚节点，使其均匀地分布在整个网络。先用矩阵记录所有信标节点坐标beacon=B1，B2，. . . ，Bi以及未知节点坐标nodes=N1，N2， . . . ， Nj。首先计算出一个未知节点到所有信标节点的距离Distance-set= D1，D2，. . . ，Di，将Distance-set中的所有距离与射

11、程r1和r2做比较，大于r2的距离是无效距离，舍弃。得到了有效的距离矩阵valid-Distance和相应的射程矩阵Radio，以及有效的锚节点矩阵beacons= B1， B2，. . .，Bm，将beacons中的所有有效锚节点任选三个作为一组，选取三个锚节点坐标围成的区域面积最大的的一组锚节点(8)。挑选出三个锚节点后按照3.2节的数学模型计算即可估计出一个未知节点的坐标，其余未知节点坐标采用同样方法。最后采用计算定位误差。取两级能量级的关系为r1 = 0.707r2, 取通信半径r2分别为10m、20m、30m和40m，各进行试验共计20次，分别统计每次试验的能定位的节点的平均定位精度

12、，由(8)式计算相对定位精度，仿真结果如图2。error=i=1MerroriMr2 (8) 由仿真结果可以得出：相对定位误差分布于0.07到0.27之间, 随着锚节点的密度增加定位精度提高，从而相对定位误差下降，但是下降到一定比例后，定位精度将不再增加。密度一定时，相对定位误差随通信半径的增加而减少，通信半径增加到30m后，相对定位误差就减小得很少了，说明本文算法的相对定位精度对通信半径并不敏感(9)。 图2 锚节点密度对相对定位误差的影响本文的创新点在于与现有算法的比较取两级能量级的关系为r1=0.707r2，取通信半径为30m，在200m200m的区域内随机撒播300个未知节点，在这些节

13、点中选取锚节点，使其均匀地分布在整个网络，在这样的网络模型下将文献(10)中的加权质心算法、原始的质心算法、近似三角形内点测试定位算法(APIT)以及CAB(11)算法，进行仿真比较，其中本算法计算方法和4.2节方法相同，结果如图3所示。由仿真结果可得，在同样的网络模型下CAB算法相对于质心算法和APIT 算法有更好的定位性能。例如当锚节点密度为15%时, 三者的相对定位误差分别为0.113，0.18和0.26。而当锚节点密度大于7%时，本文提出的锚同心圆加权质心算法相比于CAB算法则有更好的定位精度。例如当锚节点密度为15%时， 本文算法相对定位精度为0.095而CAB算法为0.113，提高

14、了约13%的定位精度。图3 不同算法的定位绝对误差比较总结通过分析无线电传播路径损耗，以及引入信标节点影响力的概念，提出了锚同心圆加权质心算法，利用MATLAB建模分析，计算出了本文算法的相对定位误差。仿真结果表明，本文算法比传统的免测距定位算法拥有更好的定位性能。此外本定位方法完全采用几何运算，实现简单，对硬件要求不高，能较好的适应WSN低成本与低功耗的要求, 是一种可以选用的定位方案。参考文献(1) IF Akyildiz, W Su, Y Sankara subram aniam, ECayirc.i Wirelesssensor network s: a survey J.Comput

15、er Networks, 2002, 38(4) : 393 - 422.(2) L Mills Kevin. A brief survey of self- organization inwireless sensor networksJ.Wireless Communications and Mobile Computing(S1530- 8669) , 2007, 7(7) : 823 - 834.(3) 李建中, 高宏. 无线传感器网络的研究进展J.计算机研究与发展, 2008, 45(1) : 63- 72.(4) NShah, I Zeid. Adhoc localization

16、technique for wireless Sensor networksJ.The International Society for Optical Engineering( S0277- 786X) , 2005, v6011: 60110A1 - 60110A12, 2005.(5) 王福豹, 史龙, 任丰原. 无线传感器网络的自身定位和算法J. 软件学报, 2005, 16(5) : 857- 868.(6) V Vivekanandan, WSV incent. Concentric anchor beacon localization algorithm for wireless sensor networksJ.IEEE Transactions on Vehicular Technology, 2007, 56(5) : 2733- 2744.(7) 姜志鹏, 高随祥. 无线传感器网络节点定位的同心圆改进算法J.计算机科学, 2009, 36(10) : 46- 54.(8) 刘克中, 喻钦. 无线传感器网络中多能量级质心定位方法