论文部分内容阅读
[摘 要]随着无线传感器网络在国防、安全等领域的快速发展，节点定位算法作为它的主要技术之一，也逐渐的被更多的人所重视、研究。为了提高定位技术在无线传感器网络中的应用效率和计算速度，提出了基于信号衰减经验模型的定位算法。该算法通过大量抽取节点在移动路线上的位置及其信号强度，迅速缩小锚点所在的范围，快速缩小节点所在区域，减少搜寻时间。
[关键词]无线传感器网络；定位算法；节点；信号强度
中图分类号：TN95 文献标识码：A 文章编号：1009-914X（2014）30-0108-02
1 引言
无线传感器网络的研究始于20世纪70年代，它的出现和发展对现代科技产生了深远的影响并且还曾被列为21世纪最重要的21项技术之一。不同于传统的网络技术，无线传感器网络将信息技术、通信技术、传感器技术和网络技术等有机地融为一体，涉及了信号处理、通信、传感器、网络等多种领域，在国防、环境监测、精准农业、地震监测、医疗监护、家庭自动化、智能环境和其他许多领域都有着广阔的应用前景和极高的应用价值[1]。
无线传感器网络实际上是一种Ad Hoc网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者[2]。定位就是确定位置。无线传感器网络的定位是指自组织网络通过特定方法提供节点的位置信息，而这种特定的方法即为节点的定位算法。
节点定位算法在无线传感器网络中是不可或缺的一部分，它的学习和研究对无线传感器网络的发展有着重要的意义。由于无线传感器网络的工作区域可能多是恶劣环境或人类不适宜到达的区域，传感器节点也多是由飞机抛撒等方式散布于其中，因而其位置都是随机的。节点所收集的数据必须结合其所在环境才有意义，然而节点的存储、通信能力较弱且使用小容量电池供电，所以，如何以最小的代价实现节点定位成为无线传感器网络研究中的重要组成部分。
本文提出的基于信号衰减经验模型的节点定位算法是通过测量节点间的通信信号强度来逐步缩小未知节点所在的区域，以便对网络中的节点进行快速定位。
2 几种典型的节点定位算法
根据定位过程中是否需要测量实际节点之间的距离，可以将节点的定位算法分为两大类：基于测距（Range-based）的定位算法和无须测距（Range-free）的定位算法。下面将要介绍的几种典型的分布式节点定位算法——合称为APS[3，4]，均属于无须测距的节点定位算法。
2.1 DV-Hop算法
Niculescu等人提出的DV-Hop算法可以避免直接对节点间距进行测量[5]，它是利用距离矢量定位和GPS[6]定位思想提出的一种分布式定位方法。
算法的初始条件是网络中除了参考节点之外，没有其他节点的位置信息。
基本思想为网络内的节点需要获得它们到每个参考节点的跳数，将跳数与平均每跳距离相乘，就可以获得该节点到每个参考节点的估计距离[7]，其中第i个参考节点估计的平均每跳距离为
式中，（xj，yj）为第j个参考节点的位置；hj为从第j个参考节点到第i个参考节点的跳数。
最后，将计算所得的距离与参考节点的位置信息一起，进行三边或多变测量定位法，就可以获得该节点的位置信息。
2.2 Euclidean算法
Euclidean算法是基于围绕在参考节点周围的节点的局部几何拓扑，给出了一种估计与参考节点（锚节点）相隔两跳的未知节点位置的方法。该算法的主要思想如图1：
节点A、D在参考节点B的无线射程内，即可直接与B通信，且距离AD已知。待定位节点C与节点A、D相邻；边长AB、BD、CD、AC已知，则根据余弦公式可计算出∠CAD、∠DAB、∠CDA、∠ADB，此时计算结果发现节点C可能有两种情况，分别位于对角线AD的两侧，但节点C与B不相邻，故只有如图1的一种情况，逆向使用余弦定理可以计算出对角线BC的长度，进而对节点C进行准确定位。
2.3 DV-Distance算法
该算法类似于DV-Hop算法，但是不同于DV-Hop算法是通过将跳数与平均每跳距离相乘得出节点到参考节点的距离，DV-Distence算法则是先利用RSSI技术测得各个节点间的距离，从而计算未知节点与已知的每个参考节点的跳段累计距离，然后利用上一阶段得到的各参考节点的累计跳段距离作为有效距离，通过三边测量法来利用该有效距离计算出自身的坐标位置。采用如下公式：
3 基于信号衰减经验模型的移动节点定位算法
3.1 应用模型
本文设定应用模型为在相对静止的平面上，有一位置相对固定的待定位节点，有一移动节点相对待定位节点在平面中进行无规则移动，但仍保证位于待定位节点的感知半径内。
当无线信号在空气中传播时，由于多种因素的影响，信号强度会随其传播距离的增加而衰减，这表明信号强度变化与传播距离间存在某种函数关系，且通常情况下传感器节点都能够很容易配置测定接收信号强度的模块。
当节点移动时，能够检测到未知节点的信号强度的位置称为包含在未知节点的感知范围之内。假定图2中的圆所围的范围大致为未知节点的感知范围，参考节点在未知节点的感知范围内无规则移动。节点在移动过程中选取尽量多的点，并及时测量、记录所选位置的信号强度。
3.2 算法思想
由于我们在测量信号强度的过程中是非连续的，因而，对于一定时间间隔Δt0内所测的两个信号强度差距较大的点，取其中垂线，那么待测节点必然位于中垂线中的偏向于较强信号强度的一方。如图3所示：
在图3中，我们在测量线路上选取尽可能多的点，分别选择连线做中垂线，这样尽可能的缩小待测结点所在的位置区域，最后借助于质心定位算法[8]，取该封闭区域的质心/重心作为估计的待测结点的位置。 平面中已知节点N的运动轨迹为无规则的曲线运动，当其运动范围位于待测结点的感知范围中时，能够测出其相对信号强度。我们分别在节点N的运动过程中记录在位置S1，S2，S3，……，Sn，S’1，S’2，S’3，……，S’n所测得的信号强度分别为P（S1），P（S2），P（S3），……，P（Sn），P（S’1），P（S’2），P（S’3），……，P（S’n），然后分别连接S1与S’1、S2与S’2、S3与S’3、……、Sn与S’n并做对应线段的中垂线，最终可以确定一个未知节点所在位置的区域A0A1A2…An。通过上述方式，可以快速缩小针对未知节点的范围的搜索，在搜救过程中可以尽可能的缩短时间。同时，若针对该方法寻求尽可能准确的定位，可采用如下方式：
第一步，利用相交的两条中垂线计算交点Ai（i=0，1，2…，n）的坐标；
第二步，根据所得交点A0，A1，A2，…，An的坐标，利用如下公式来计算未知节点的大概位置：
（X，Y）=（（X1+ X2+ X3+…+ Xn）/n，（Y1+ Y2+ Y3+…+ Yn）/n）
式中，（Xi，Yi）表示Ai的位置，n表示所围区域的交点个数。
4 实验及分析
4.1 实验设备
实验设备主要包括：1个ZigBee无线网络固定节点，作为待测未知节点；1个ZigBee移动节点，作为参考节点。
实验环境为尽量确保为水平面的测试，选择外部开阔地为学校运动场，接近于理想环境。
4.2 实验设计
本文中使用的搭建仿真环境的工具为 Matlab8.0。具体仿真过程如下：
首先，设置实验模拟的环境，我们设置在边长为10（此处假设r=10为传感器节点的感知半径）的正方形区域内，随机放置一点，作为未知节点的位置；
然后设置一移动点，作为参考节点，它在边长为10r的正方形区域内无规则移动，假设当该点移动到未知节点半径为r的区域内时，根据公式
来计算参考节点接收到未知节点发送的信号的信号强度，作为判定与未知节点距离的依据。其中，为发射信号端的信号强度，是在接收端收到的信号强度，两节点间距为，为距离误差，k为衰减因子，为高斯随机变量。
当参考节点在移动过程中，我们同时每隔时间记录参考节点所在位置以及接收到未知节点发送的信号的强度；
之后，利用matlab来计算线段中点并做中垂线，然后记录中垂线相交的点；
下一步工作的重点为交点的筛选。并非是所有的交点都能围成我们需要的区域，我们按照交点的出现顺序逐步排除：当形成第一个封闭区域时，代表着未知节点必定存在于该区域，那么后出现的并且可以缩小该封闭区域的交点即可取代之前打的封闭区域的交点。
接下来需要统计符合条件的交点，并记录他们的位置信息。同时根据质心定位算法的公式：
计算出估计的质心位置，即为该算法能够得出的对于未知节点的最终的定位。
最后，为了后面顺利的进行结果分析，我们还需要统计一下该过程中代码执行的时间，即从开始到找到估计的未知节点的位置为止，共花费了多少时间。同时，还需要计算出估计的未知节点的位置与未知节点实际的位置的距离差到底有多少。
4.3 实验结果及分析
在相同的条件下，我们实验了本文提出的定位算法以及单纯的质心定位算法，两种方法分别执行了十次，对应的时间对比如图4所示：
图中黑色空心圆点连接的线段表示的是单纯的质心定位算法，蓝色空心方点连接的线段为本文提出的定位算法。从图中结果可以看出，本文算法在用时上，相对于单纯的质心定位算法来说总体要多一些，这可由算法原理中的计算过程比较可以看出。
下面来比较一下两种定位算法在定位误差上的区别。针对每次定位计算，我们记录了相应的估计位置与实际位置相差的距离，具体统计信息如图5所示：
通过图4-10所示的误差对比我们可以发现，本文提出的定位算法与纯粹的质心定位算法相比，明显要更进一步，误差相对更小一些，定位的精确度更高。
5 结束语
本文是基于信号衰减经验模型提出的节点定位算法，并在一定程度上结合了质心定位算法的计算方法，借助于节点在移动过程中能够随时记录自身位置以及测得未知节点的信号强度，通过链接信号强度哦不同的点，短时间内快速缩小未知节点所在的范围，减少搜寻难度。同时，借助于质心定位算法，还可以大致计算出未知节点的具体坐标。该方法只需在轨迹上找到多组满足信号强度不相同的位置，无需借助于其它硬件，不需要测量角度距离等信息，即可实现节点的定位。这对于在海面搜救工作以及空中搜索中快速缩小搜索区域具有很大的帮助。
参考文献
[1] Akyildiz L F， Sankarasubramaniam Y， Cayiric E. A Survey on Sensor Networks. IEEE Communications Magazine， 2002，40（8）：102-114.
[2] Tilak S， Abu-Ghazaleh N B， Heinzelman W. A Taxonomy of Wirless Micro-Sensor Network Models. Mobile Computing and Communications Review， 2002， 1（2）：1-8
[3] Pi Chun Chen. A non-line-of-sight error mitigation algorithm. Proceedings of IEEE Wireless Communications and Networking Conference（WCNC ‘ 99）， New Orleans，LA， USA ： IEEE Computer and Communications Societies ， 1999 ： 316-320.
[4] Wylie M P， Holtzman J. The non-line-of-sight problem in mobile location estimation. Proceedings of the International Conference on Universal Personal Communications，Cambridge，MA ： IEEE Communications Society ， 1996 ： 827-831.
[5] Bulusu N， Heidemann J， Estrin D. GPS – Less Low - Cost Outdoor Localization for Very Small Devices. IEEE Personal Communications， 2000， 7（5）：28-34.
[6] Hofmann Wellenho B， Lichtenegger H，Collins J.GPS Theory and Practice.Spring Wien， New York， 1997.
[7] Doherty L. Algorithms for Position and Data Recovery in Wireless Sensor Networks. Proc. IEEE Infocom 2001， 2001.
[8] Nirupama Bulusu，John Heidemann，Deborah Estrin. GPS-less Low Cost Outdoor Localization fot Very Small Devices.IEEE Personal Communications， 2000：7（5）：28-34.
[关键词]无线传感器网络；定位算法；节点；信号强度
中图分类号：TN95 文献标识码：A 文章编号：1009-914X（2014）30-0108-02
1 引言
无线传感器网络的研究始于20世纪70年代，它的出现和发展对现代科技产生了深远的影响并且还曾被列为21世纪最重要的21项技术之一。不同于传统的网络技术，无线传感器网络将信息技术、通信技术、传感器技术和网络技术等有机地融为一体，涉及了信号处理、通信、传感器、网络等多种领域，在国防、环境监测、精准农业、地震监测、医疗监护、家庭自动化、智能环境和其他许多领域都有着广阔的应用前景和极高的应用价值[1]。
无线传感器网络实际上是一种Ad Hoc网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者[2]。定位就是确定位置。无线传感器网络的定位是指自组织网络通过特定方法提供节点的位置信息，而这种特定的方法即为节点的定位算法。
节点定位算法在无线传感器网络中是不可或缺的一部分，它的学习和研究对无线传感器网络的发展有着重要的意义。由于无线传感器网络的工作区域可能多是恶劣环境或人类不适宜到达的区域，传感器节点也多是由飞机抛撒等方式散布于其中，因而其位置都是随机的。节点所收集的数据必须结合其所在环境才有意义，然而节点的存储、通信能力较弱且使用小容量电池供电，所以，如何以最小的代价实现节点定位成为无线传感器网络研究中的重要组成部分。
本文提出的基于信号衰减经验模型的节点定位算法是通过测量节点间的通信信号强度来逐步缩小未知节点所在的区域，以便对网络中的节点进行快速定位。
2 几种典型的节点定位算法
根据定位过程中是否需要测量实际节点之间的距离，可以将节点的定位算法分为两大类：基于测距（Range-based）的定位算法和无须测距（Range-free）的定位算法。下面将要介绍的几种典型的分布式节点定位算法——合称为APS[3，4]，均属于无须测距的节点定位算法。
2.1 DV-Hop算法
Niculescu等人提出的DV-Hop算法可以避免直接对节点间距进行测量[5]，它是利用距离矢量定位和GPS[6]定位思想提出的一种分布式定位方法。
算法的初始条件是网络中除了参考节点之外，没有其他节点的位置信息。
基本思想为网络内的节点需要获得它们到每个参考节点的跳数，将跳数与平均每跳距离相乘，就可以获得该节点到每个参考节点的估计距离[7]，其中第i个参考节点估计的平均每跳距离为
式中，（xj，yj）为第j个参考节点的位置；hj为从第j个参考节点到第i个参考节点的跳数。
最后，将计算所得的距离与参考节点的位置信息一起，进行三边或多变测量定位法，就可以获得该节点的位置信息。
2.2 Euclidean算法
Euclidean算法是基于围绕在参考节点周围的节点的局部几何拓扑，给出了一种估计与参考节点（锚节点）相隔两跳的未知节点位置的方法。该算法的主要思想如图1：
节点A、D在参考节点B的无线射程内，即可直接与B通信，且距离AD已知。待定位节点C与节点A、D相邻；边长AB、BD、CD、AC已知，则根据余弦公式可计算出∠CAD、∠DAB、∠CDA、∠ADB，此时计算结果发现节点C可能有两种情况，分别位于对角线AD的两侧，但节点C与B不相邻，故只有如图1的一种情况，逆向使用余弦定理可以计算出对角线BC的长度，进而对节点C进行准确定位。
2.3 DV-Distance算法
该算法类似于DV-Hop算法，但是不同于DV-Hop算法是通过将跳数与平均每跳距离相乘得出节点到参考节点的距离，DV-Distence算法则是先利用RSSI技术测得各个节点间的距离，从而计算未知节点与已知的每个参考节点的跳段累计距离，然后利用上一阶段得到的各参考节点的累计跳段距离作为有效距离，通过三边测量法来利用该有效距离计算出自身的坐标位置。采用如下公式：
3 基于信号衰减经验模型的移动节点定位算法
3.1 应用模型
本文设定应用模型为在相对静止的平面上，有一位置相对固定的待定位节点，有一移动节点相对待定位节点在平面中进行无规则移动，但仍保证位于待定位节点的感知半径内。
当无线信号在空气中传播时，由于多种因素的影响，信号强度会随其传播距离的增加而衰减，这表明信号强度变化与传播距离间存在某种函数关系，且通常情况下传感器节点都能够很容易配置测定接收信号强度的模块。
当节点移动时，能够检测到未知节点的信号强度的位置称为包含在未知节点的感知范围之内。假定图2中的圆所围的范围大致为未知节点的感知范围，参考节点在未知节点的感知范围内无规则移动。节点在移动过程中选取尽量多的点，并及时测量、记录所选位置的信号强度。
3.2 算法思想
由于我们在测量信号强度的过程中是非连续的，因而，对于一定时间间隔Δt0内所测的两个信号强度差距较大的点，取其中垂线，那么待测节点必然位于中垂线中的偏向于较强信号强度的一方。如图3所示：
在图3中，我们在测量线路上选取尽可能多的点，分别选择连线做中垂线，这样尽可能的缩小待测结点所在的位置区域，最后借助于质心定位算法[8]，取该封闭区域的质心/重心作为估计的待测结点的位置。 平面中已知节点N的运动轨迹为无规则的曲线运动，当其运动范围位于待测结点的感知范围中时，能够测出其相对信号强度。我们分别在节点N的运动过程中记录在位置S1，S2，S3，……，Sn，S’1，S’2，S’3，……，S’n所测得的信号强度分别为P（S1），P（S2），P（S3），……，P（Sn），P（S’1），P（S’2），P（S’3），……，P（S’n），然后分别连接S1与S’1、S2与S’2、S3与S’3、……、Sn与S’n并做对应线段的中垂线，最终可以确定一个未知节点所在位置的区域A0A1A2…An。通过上述方式，可以快速缩小针对未知节点的范围的搜索，在搜救过程中可以尽可能的缩短时间。同时，若针对该方法寻求尽可能准确的定位，可采用如下方式：
第一步，利用相交的两条中垂线计算交点Ai（i=0，1，2…，n）的坐标；
第二步，根据所得交点A0，A1，A2，…，An的坐标，利用如下公式来计算未知节点的大概位置：
（X，Y）=（（X1+ X2+ X3+…+ Xn）/n，（Y1+ Y2+ Y3+…+ Yn）/n）
式中，（Xi，Yi）表示Ai的位置，n表示所围区域的交点个数。
4 实验及分析
4.1 实验设备
实验设备主要包括：1个ZigBee无线网络固定节点，作为待测未知节点；1个ZigBee移动节点，作为参考节点。
实验环境为尽量确保为水平面的测试，选择外部开阔地为学校运动场，接近于理想环境。
4.2 实验设计
本文中使用的搭建仿真环境的工具为 Matlab8.0。具体仿真过程如下：
首先，设置实验模拟的环境，我们设置在边长为10（此处假设r=10为传感器节点的感知半径）的正方形区域内，随机放置一点，作为未知节点的位置；
然后设置一移动点，作为参考节点，它在边长为10r的正方形区域内无规则移动，假设当该点移动到未知节点半径为r的区域内时，根据公式
来计算参考节点接收到未知节点发送的信号的信号强度，作为判定与未知节点距离的依据。其中，为发射信号端的信号强度，是在接收端收到的信号强度，两节点间距为，为距离误差，k为衰减因子，为高斯随机变量。
当参考节点在移动过程中，我们同时每隔时间记录参考节点所在位置以及接收到未知节点发送的信号的强度；
之后，利用matlab来计算线段中点并做中垂线，然后记录中垂线相交的点；
下一步工作的重点为交点的筛选。并非是所有的交点都能围成我们需要的区域，我们按照交点的出现顺序逐步排除：当形成第一个封闭区域时，代表着未知节点必定存在于该区域，那么后出现的并且可以缩小该封闭区域的交点即可取代之前打的封闭区域的交点。
接下来需要统计符合条件的交点，并记录他们的位置信息。同时根据质心定位算法的公式：
计算出估计的质心位置，即为该算法能够得出的对于未知节点的最终的定位。
最后，为了后面顺利的进行结果分析，我们还需要统计一下该过程中代码执行的时间，即从开始到找到估计的未知节点的位置为止，共花费了多少时间。同时，还需要计算出估计的未知节点的位置与未知节点实际的位置的距离差到底有多少。
4.3 实验结果及分析
在相同的条件下，我们实验了本文提出的定位算法以及单纯的质心定位算法，两种方法分别执行了十次，对应的时间对比如图4所示：
图中黑色空心圆点连接的线段表示的是单纯的质心定位算法，蓝色空心方点连接的线段为本文提出的定位算法。从图中结果可以看出，本文算法在用时上，相对于单纯的质心定位算法来说总体要多一些，这可由算法原理中的计算过程比较可以看出。
下面来比较一下两种定位算法在定位误差上的区别。针对每次定位计算，我们记录了相应的估计位置与实际位置相差的距离，具体统计信息如图5所示：
通过图4-10所示的误差对比我们可以发现，本文提出的定位算法与纯粹的质心定位算法相比，明显要更进一步，误差相对更小一些，定位的精确度更高。
5 结束语
本文是基于信号衰减经验模型提出的节点定位算法，并在一定程度上结合了质心定位算法的计算方法，借助于节点在移动过程中能够随时记录自身位置以及测得未知节点的信号强度，通过链接信号强度哦不同的点，短时间内快速缩小未知节点所在的范围，减少搜寻难度。同时，借助于质心定位算法，还可以大致计算出未知节点的具体坐标。该方法只需在轨迹上找到多组满足信号强度不相同的位置，无需借助于其它硬件，不需要测量角度距离等信息，即可实现节点的定位。这对于在海面搜救工作以及空中搜索中快速缩小搜索区域具有很大的帮助。
参考文献
[1] Akyildiz L F， Sankarasubramaniam Y， Cayiric E. A Survey on Sensor Networks. IEEE Communications Magazine， 2002，40（8）：102-114.
[2] Tilak S， Abu-Ghazaleh N B， Heinzelman W. A Taxonomy of Wirless Micro-Sensor Network Models. Mobile Computing and Communications Review， 2002， 1（2）：1-8
[3] Pi Chun Chen. A non-line-of-sight error mitigation algorithm. Proceedings of IEEE Wireless Communications and Networking Conference（WCNC ‘ 99）， New Orleans，LA， USA ： IEEE Computer and Communications Societies ， 1999 ： 316-320.
[4] Wylie M P， Holtzman J. The non-line-of-sight problem in mobile location estimation. Proceedings of the International Conference on Universal Personal Communications，Cambridge，MA ： IEEE Communications Society ， 1996 ： 827-831.
[5] Bulusu N， Heidemann J， Estrin D. GPS – Less Low - Cost Outdoor Localization for Very Small Devices. IEEE Personal Communications， 2000， 7（5）：28-34.
[6] Hofmann Wellenho B， Lichtenegger H，Collins J.GPS Theory and Practice.Spring Wien， New York， 1997.
[7] Doherty L. Algorithms for Position and Data Recovery in Wireless Sensor Networks. Proc. IEEE Infocom 2001， 2001.
[8] Nirupama Bulusu，John Heidemann，Deborah Estrin. GPS-less Low Cost Outdoor Localization fot Very Small Devices.IEEE Personal Communications， 2000：7（5）：28-34.