无线传感器网络节点定位算法研究

于耕

摘要：在本文中首先介绍了节点坐标的计算方法，然后从集中式定位算法和分布式定位算法两个方面讨论了典型的节点定位算法。分析了当前无线传感网络节点定位技术存在的一些问题并指出了未来的研究方向和发展趋势。

Abstract： In this paper， the calculation method of node coordinates is introduced first， and then the typical node localization algorithm is discussed from two aspects： centralized localization algorithm and distributed location algorithm. This paper analyzes some problems existing in the localization technology of wireless sensor networks， and points out the future research directions and development trends.

关键词：无线传感器网络；节点定位；定位算法

Key words： wireless sensor networks；node localization；localization algorithm

中图分类号：TN929.5；TP212.9 文献标识码：A 文章编号：1006-4311（2018）30-0194-03

0 引言

无线传感器网络（WSN）是将传感器技术、嵌入式技术、无线通信技術和分布式数据计算技术相结合的一种自组网络系统[1]。它可以实时采集网络覆盖区域的监测信息，并且将这些信息发送给观察者。

WSN最开始是在军事领域中应用的[2]，随着MEMS和微芯片制造技术的发展，传感器节点成本的大大降低，功耗和体积的减小，WSN的新技术广泛应用于日常生活和社会建设中，例如森林火灾监控、智能交通、健康医疗、物联网[3]和车联网[4]等。在这些应用中，传感器节点的位置是至关重要的[5]。然而对于大规模的传感器网络来说，为每个节点安装GPS接收器以获得精确位置是不现实的[6]。因此，现在的办法是给一部分节点安装上GPS接收器[7]，剩下的节点利用这些节点进行自定位。所以，现在研究WSN节点的定位问题具有重要的理论意义和实际应用价值。

1 WSN节点定位的坐标计算方法

在WSN定位方法中，我们将知道自己位置坐标的节点称为锚节点，需要定位的节点成为未知节点，在通信范围内可以直接通信的节点称为该节点的邻居节点。在节点定位阶段，未知节点如果能够获得与临近锚节点之间的距离，或者获得未知节点与临近锚节点之间的相对角度后，就可以用三边测量法、三角测量法、极大似然估计法来计算未知节点的位置。

1.1 三边测量法

2 节点定位常用算法分析

经过多年的研究，国内外学者对无线传感器中的节点定位提出了众多的改进算法，我们将这些算法可以分为集中式定位算法和分布式定位算法[11]。

2.1 集中式定位算法

集中式定位要求网络把所有用于节点定位的信息通过多条路由传送到一个点，然后在该节点运行定位算法对节点进行定位。这样可以从整体出发来进行节点定位，获得较高的定位精度。

2.1.1 基于传输时间差（TDOA）的算法

TDOA算法[12]是节点发送两种已知传播速度的测量信号，例如，电磁波和超声波。因此，接收节点可以根据电磁波与超声波的传播时间差及其在空气中传播的速度来计算发送节点与接收节点之间的距离。根据计算出的距离利用第一节给出的坐标计算方法，即可计算出节点的坐标。利用该算法在视距范围内可以获得较高的定位精度，但是该算法容易受外界环境的影响，而且该算法需要额外的硬件导致定位费用高。

2.1.2 MDS-MAP节点定位算法

MDS-MAP节点定位算法[13]是由哥伦比亚大学的Yi等人最早提出来的一种集中式的定位算法，这种定位算法是基于多维定标（multidimensional scaling，MDS）技术来实现的。MDS-MAP节点定位算法可以分为三个部分：第一部分，计算任意节点之间的距离，然后用任意节点之间的最短距离生成定位算法用到的距离矩阵。第二步，使用MDS技术来处理第一步得到的距离矩阵，求出定位所需要的特征值。并且利用得到的特征值计算出所有节点的相对坐标。第三部，利用锚节点的绝对坐标将上一步得到的节点相对坐标转换成绝对坐标。

MDS-MAP节点定位算法在锚节点密度较低的情况下具有较高的定位精度，但是由于该算法是集中式定位算法，计算量和通信代价较大。

2.1.3 基于信号强度（RSSI）的节点定位算法

RSSI算法[14]是根据接收到的信号强度与距离之间的关系来估计节点间的距离，然后节点的位置可以用三边法或其他基于估计距离的方法计算出。因为目前几乎所有的无线通信模块都支持RSSI的测量功能，所以该算被广泛的应用。由于该算法容易受到环境的影响，因此，可以应用在对定位要求不高的环境中。

2.2 分布式定位算法

分布式定位算法是将定位算法所需的任务根据一定规则分配给各个节点，节点和自己的邻居节点交换定位算法所需的信息，然后各个节点根据交换得到的消息各自的计算自己的位置。

2.2.1 质心定位算法

质心定位算[15]是根据节点之间的连通性来进行定位的，是一种分布式计算的定位算法。Bulusu等人最早提出的质心定位算法是用在GPS定位上的，随后该方法被用在了无线传感器节点定位上。质心算法是求多边形的几何中心，多边形顶点坐标的平均值就是所求的未知节点的坐标。

质心算法简单，容易在实际应用中实现，适合定位精度要求不高的环境中。

2.2.2 SBSL定位算法

2008年，戴桂兰等人提出了一种基于球面坐标的动态定位算法[16]，该算法是一种分布式定位算法。此算法将节点定位问题转化成求解多元线性方程组解的问题，最终用克莱姆法则来解决多解和无解的问题。该算法假设定位模型是以未知节点为球心，最大通信半径为圆心的球面，锚节点在移动过程中周期性的向网络中广播锚节点的ID号，锚节点的空间位置。当能够获得球体表面上不共面的四个点后，未知节点的位置能够被准确的求出来。该算法的定位精度对锚节点密度和通信半径不敏感，并且该算法在通信量和计算量方面做到了适中。

2.2.3 矢量-路由（DV-Hop）算法

DV-Hop算法[17]是一种很常用的分布式定位算法，该算法的定位过程可以分三个部分：

①网络中的所有锚节点向整个网络洪泛自己初始化位置的数据包，每个接收数据包的节点都为锚节点建立一个表，其中包含锚节点的位置和最小跳数，然后将最小跳数值+1后转发给周围的节点。

其中Dsk是锚节点s和未知节点k的距离，hsk是这两点之间的最小跳数。

通过这样的方法可以求出未知节点到锚节点的距离，然后利用前面介绍的极大似然估计的方法可以求解出待定位节点的坐标。

3 节点定位进一步的研究方向

传感器节点定位已经得到了广泛的研究，但是，仍然有一些重要的问题有待解决，特别是节点定位的大规模应用。以下列举了存在的一些问题：

①人们在研究定位算法时只关注定位算法的精度，而忽略了能量消耗和定位效率。因此，传感器节点定位中的能量消耗最小化问题值得我们关注。

②现有的定位算法大多依赖于锚节点，随着锚节点数量的增加，定位精度也随之提高。然而，具有更多资源的移动锚节点比普通的传感器节点昂贵。因此，对于节点定位，我们需要充分利用未知节点和锚节点之间的独特关系，以减少锚节点的使用。

③在现有的定位场景中，大多数节点定位算法应用于二维平面网络区域。然而，在复杂的现实应用中，节点往往随机的分布在三维空间中，这就使得二维空间的定位算法不一定适用于三维空间。因此，在以后的研究中要注重三维空间的节点定位。

4 结论

对于网络功能和许多应用来说，无线传感器网络中节点的位置是至关重要的。在这篇论文中，我们介绍了节点坐标的计算方法，重点对集中式定位算法和分布式定位算法进行了分析，总结了节点定位研究领域存在的一些问题和今后可以研究的内容和方向。希望我们指出的定位技术存在的问题，可以为今后改进定位算法提供一些参考和借鉴。

参考文献：

[1]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）：1282-1291.

[2]Y. H. Liu， Z. Yang， X. P. Wang and L. R. Rong， Location， localization， and localizability[J]. Journal of Computer Science and Technology， 2010， 25（2）： 274-297.

[3]钱志鸿，王义君.面向物联网的无线传感器网络综述[J].电子信息学报，2013，35（1）：215-227.

[4]顿文涛，赵玉成，王力斌等.车联网的关键技术及研究进展[J].农业网络信息，2015，8：46-50.

[5]F. Cadger， K. Curran， J. Santos and S. Moffett， A survey of geographical routing in wireless ad-hoc networks[J]， IEEE Communications Surveys & Tutorials， 2013， 15（2）： 621-653.

[6]L. R. Tang， Y. Gong， Y. T. Luo， S. H. Ke， A 3D position algorithm based on Euclidean for wireless sensor network[J]. Acta Electronica Sinica， 2012， 40（4）： 821-825.

[7]Y. Ding， C. Wang， L. Xiao， Using mobile beacons to locate sensors in obstructed environments[J]. Journalof Parallel & Distributed Computing， 2010， 70（6）： 644-656.

[8]王小平，羅军，沈昌祥.三边测量法的结果稳定性[J].计算机工程与科学，2012，34（6）：12-17.

[9]李建坡，钟鑫鑫，徐纯.无线传感器网络动态节点定位算法综述[J].东北电力大学学报，2015，35（1）：52-58.

[10]徐原博，钟丽鸿，崔洋等.基于无线传感器网络的极大似然定位算法的分析[J].传感器与微系统，2011，30（10）：37-40.

[11]彭宇，王丹.无线传感器网络定位技术综述[J].电子测量与仪器学报，2011，25（5）：389-399.

[12]C. Liu， J. Yang， F. Wang， Joint TDOA and AOA location algorithm[J]. Journal of Systems Engineering and Electronics， 2013， 24（2）： 183-188.

[13]Shang Yi， Ruml W， Zhang Y， e1 al. Localization from Connectivity in Sensor Network[J]. IEEE Transactions on Parallel & Distributed Systems， 2004， 15（11）： 961-974.

[14]H. P. Mistry， N. H. Mistry， RSSI based localization scheme in wireless sensor networks： A survey[C]. International Conference on Advanced Computing & Communication Technologies， 2015， 7（1）： 1611-1615.

[15]龙佳，卑璐璐，张申等.基于虚拟信标节点的改进加权质心定位修正算法[J].微电子学与计算机，2017，34（3）：74-78.

[16]戴桂兰，赵冲冲，邱岩.一种基于球面坐标的无线传感器网络三维定位机制[J].电子学报，2008，36（7）：1297-1303.

[17]S Tomic， I Mezei. Improvements of DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Telecommunication Systems， 2016， 61（1）： 93-106.