本站原创
摘要：
针对现有无线传感器网络（WSN）三维定位算法在精度和复杂度方面的不足，提出了一种改进的三维空间定位算法。利用栅格扫描分别求解邻居锚节点在两个坐标平面的投影交域，得出未知节点在两坐标平面的对应位置，最终实现三维位置估计。仿真结果表明：在100m×100m×100m的空间里，随机投放200个传感器节点，锚节点数为45时，其覆盖率达到了99.1%，相对定位误差仅为0.5533。且平面投影的引入，有效地降低了算法复杂度。
关键词：无线传感器网络；三维节点定位；降维；栅格扫描；质心算法
：A
0引言
随着无线通信技术、微系统技术与嵌入式技术的日益成熟，无线传感器网络（Wireless Sensor Network， WSN）可靠性逐渐提高，应用范围也日渐广泛，如道路状况监控、矿井安全监控和军事侦查等要求高可靠性的领域也开始引入无线传感器网络[1-3]。而没有位置信息的传感器节点采集数据通常毫无意义，所以为了提供有效的定位信息，随机部署的传感器节点能够在布置后确定自身的位置至关重要[4]。
目前的WSN定位算法，大多数是针对二维平面而设计的，如APIT算法[5]、凸规划算法[6]、APS（Ad Hoc Position System）[7]和MDAP算法[8]等。而现实生活中，如对海洋水温、洋流及生物活动的监测，气候及环境污染的监测以及在山区和丛林等复杂地形的传感器网络应用使得单纯的平面定位信息已经满足不了应用的需要。
为此，出现了一些针对无线传感器网络在三维场景下应用的定位算法，如文献[9]提出的Bounding Cube算法，该
本文将锚节点的球形通信范围向两个坐标平面投影，降低位置信息维度，进而降低了运算的复杂度。再通过投影的覆盖关系，分别在两个坐标平面上采用栅格扫描方法提高所得二维坐标估计值的精度，综合得出节点三维位置信息。最后与相同条件参数下的APIS算法定位结果进行比较。
1投影栅格化扫描算法
无线传感器网络中，如果一个未知节点接收到来自多个锚节点的信标， 则未知节点包含于这几个锚节点的通信范围的交集内。Delta算子递推最小二乘（Delta operator Recursive Least Squares， DRLS）栅格扫描算法[11]的基本原理就是利用这个交集的边缘初始化一个估计矩形区域，通过求解这个矩形质心来达到定位的目的，如图1所示。
2）锚节点比例及通信半径对定位精度的影响。
同等条件下的20次仿真结果取均值得到如表5的数据。节点通信半径一定时，锚节点数越多，定位精度越高。锚节点数目一定时，通信半径增加也能提高定位精度。而且，节点通信半径R的增加对定位精度的提高呈现逐步减缓的趋势，当R增长到一定程度时，不同锚节点数情况下的定位相对误差趋于相同，如图8所示。
这是因为，通信半径的增加，提高了节点的覆盖率，未知节点的邻居锚节点数更多，得出的定位数据更精确，而且原来无法定位的节点数也随之减小，使得锚节点数投放较少的情况也能达到高投放比例的效果。但高的通信半径会带来更大的能量开销，在实际的应用中，应综合考虑成本和持续性的关系，在满足定位精度要求的条件下，合理选取锚节点投放比例和节点通信半径。
3）本文算法与APIS算法定位性能比较。
如图9所示，在低锚节点投放率的情况下（锚节点比例<12.5%），两种算法的定位误差都超过未知节点通信半径的一倍。但随着锚节点比例的增大，本文算法定位精度提高更快。当锚节点数为20（锚节点比例=12.5%）时，算法定位精度比APIS高4
3结语
本文提出了一种基于投影和栅格扫描的WSN三维定位算法，利用空间向平面投影降低算法复杂度，且锚节点只进行一次广播，减少了通信量，达到节省节点能量的目的。栅格扫描的使用也进一步降低了节点定位误差。仿真实验测试了主要参数对定位的影响，结果表明，该算法能够满足传感器网络三维空间定位的要求，具有较高的定位精度。
参考文献：
孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学
出版社，2005：135-154.
任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）：1282-1291.
[3]孙亭，杨永田，李立宏.无线传感器网络技术发展现状[J].电子技术应用，2006（6）：27-29.
[4]余成波，李洪兵，陶红艳.无线传感器网络实用教程[M].北京：清华大学出版社，2012：48-136.
针对现有无线传感器网络（WSN）三维定位算法在精度和复杂度方面的不足，提出了一种改进的三维空间定位算法。利用栅格扫描分别求解邻居锚节点在两个坐标平面的投影交域，得出未知节点在两坐标平面的对应位置，最终实现三维位置估计。仿真结果表明：在100m×100m×100m的空间里，随机投放200个传感器节点，锚节点数为45时，其覆盖率达到了99.1%，相对定位误差仅为0.5533。且平面投影的引入，有效地降低了算法复杂度。
关键词：无线传感器网络；三维节点定位；降维；栅格扫描；质心算法
：A
0引言
随着无线通信技术、微系统技术与嵌入式技术的日益成熟，无线传感器网络（Wireless Sensor Network， WSN）可靠性逐渐提高，应用范围也日渐广泛，如道路状况监控、矿井安全监控和军事侦查等要求高可靠性的领域也开始引入无线传感器网络[1-3]。而没有位置信息的传感器节点采集数据通常毫无意义，所以为了提供有效的定位信息，随机部署的传感器节点能够在布置后确定自身的位置至关重要[4]。
目前的WSN定位算法，大多数是针对二维平面而设计的，如APIT算法[5]、凸规划算法[6]、APS（Ad Hoc Position System）[7]和MDAP算法[8]等。而现实生活中，如对海洋水温、洋流及生物活动的监测，气候及环境污染的监测以及在山区和丛林等复杂地形的传感器网络应用使得单纯的平面定位信息已经满足不了应用的需要。
为此，出现了一些针对无线传感器网络在三维场景下应用的定位算法，如文献[9]提出的Bounding Cube算法，该
摘自：论文查重站www.udooo.com
算法利用未知节点邻居锚节点的通信范围形成立方体，并取立方体交集的质心作为节点估计位置。文献[10]提出了对传感器节点进行三维定位的非距离定位算法——APIS（Approximate Point In Sphere）算法，此算法利用远近邻居锚节点之间的通信范围形成球壳，取这些球壳交集的质心作为节点估计坐标。两种算法都具有计算简单、计算量小且通信开销小的特点，而且都不需要准确测量节点间的距离，没有额外的硬件开销。但是，前者使用了立方体来近似表述节点的通信范围，本身就不够精确，而且直接使用质心算法也容易引入较大误差；后者在使用质心算法之前也并未对球壳交集做任何减小误差的处理，精度有待提高。本文将锚节点的球形通信范围向两个坐标平面投影，降低位置信息维度，进而降低了运算的复杂度。再通过投影的覆盖关系，分别在两个坐标平面上采用栅格扫描方法提高所得二维坐标估计值的精度，综合得出节点三维位置信息。最后与相同条件参数下的APIS算法定位结果进行比较。
1投影栅格化扫描算法
1.1栅格化扫描
1）初始化阶段。邻居锚节点通信范围交集的边界形成估计矩形。无线传感器网络中，如果一个未知节点接收到来自多个锚节点的信标， 则未知节点包含于这几个锚节点的通信范围的交集内。Delta算子递推最小二乘（Delta operator Recursive Least Squares， DRLS）栅格扫描算法[11]的基本原理就是利用这个交集的边缘初始化一个估计矩形区域，通过求解这个矩形质心来达到定位的目的，如图1所示。
2）锚节点比例及通信半径对定位精度的影响。
同等条件下的20次仿真结果取均值得到如表5的数据。节点通信半径一定时，锚节点数越多，定位精度越高。锚节点数目一定时，通信半径增加也能提高定位精度。而且，节点通信半径R的增加对定位精度的提高呈现逐步减缓的趋势，当R增长到一定程度时，不同锚节点数情况下的定位相对误差趋于相同，如图8所示。
这是因为，通信半径的增加，提高了节点的覆盖率，未知节点的邻居锚节点数更多，得出的定位数据更精确，而且原来无法定位的节点数也随之减小，使得锚节点数投放较少的情况也能达到高投放比例的效果。但高的通信半径会带来更大的能量开销，在实际的应用中，应综合考虑成本和持续性的关系，在满足定位精度要求的条件下，合理选取锚节点投放比例和节点通信半径。
3）本文算法与APIS算法定位性能比较。
如图9所示，在低锚节点投放率的情况下（锚节点比例<12.5%），两种算法的定位误差都超过未知节点通信半径的一倍。但随着锚节点比例的增大，本文算法定位精度提高更快。当锚节点数为20（锚节点比例=12.5%）时，算法定位精度比APIS高4
3.2%。
继续加大锚节点投放，两种算法的定位精度进一步提高。APIS算法中，未知节点能用来定位的锚节点数越多，用于定位的球壳交集越小，质心算法所带来的误差随之减小，使得两种算法的精度差距缩小。3结语
本文提出了一种基于投影和栅格扫描的WSN三维定位算法，利用空间向平面投影降低算法复杂度，且锚节点只进行一次广播，减少了通信量，达到节省节点能量的目的。栅格扫描的使用也进一步降低了节点定位误差。仿真实验测试了主要参数对定位的影响，结果表明，该算法能够满足传感器网络三维空间定位的要求，具有较高的定位精度。
参考文献：
孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学
出版社，2005：135-154.
任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）：1282-1291.
[3]孙亭，杨永田，李立宏.无线传感器网络技术发展现状[J].电子技术应用，2006（6）：27-29.
[4]余成波，李洪兵，陶红艳.无线传感器网络实用教程[M].北京：清华大学出版社，2012：48-136.
源于：www.udooo.com