动态节点质心定位改进算法

张 军， 王潜平

(中国矿业大学计算机科学与技术学院，江苏徐州221116)

0 引言

目前，传感器网络已经迅速的融入了当今的生活，很好的应用于实时环境。无线传感器网络是一种全新的信息获取平台，可以在广泛的应用领域内实现复杂的大范围监测和追踪任务，而网络节点自身定位是大多数应用的基础和前提[1]，在如今动态环境下，网络节点的自我定位具有相当大的应用前景，可以应用于城市汽车定位，追踪任务等。但是，传感器网络的一些固有特性使得传感器节点的实时定位变得十分困难。为了能够满足为现实的需要，在应用无线传感器网络的环境中，往往会依靠外界的一些硬件设施来进行辅助。为了实现动态环境下的无线传感器网络节点定位，在适度的依靠硬件下，本文根据无线传感器网络质心定位算法的特点，提出了高定位精确、高覆盖度且实用的改进定位算法。该算法通过接收到的分组信息来得到虚拟三角形，通过内点测试的方法来判断未知节点的位置，在确定其位置之后，决定是否保存此三角形。计算出此虚拟三角形的质心位置，最终根据质心算法来确定最终的未知节点位置，相比较与传统的静态定位算法，本文算法具有更加的实用性。

1 定位算法介绍

至今，已发展了很多算法来解决无线传感器网络节点自身定位问题。目前的定位算法从定位手段上主要分为两大类：基于测距算法和无需测距算法[2]。基于测距算法通过测量节点间的距离或角度信息，使用三边测量、三角测量或极大似然估计定位法来计算节点位置，常用的定位算法有：RSSI[3]，TOA，TDOA[4]和AOA；无需测距定位算法则不需要距离和角度信息，算法根据网络连通性等信息来实现节点定位，常用的定位算法有：质心[5]，凸规划，DV-Hop，Amorphous，MDS-MAP和APIT。

在测距算法定位过程中，可以通过采用多次测量，以及循环定位来减少误差，这些算法在获得相对精确定位结果的同时，会产生大量的计算和通信开销，因此此定位机制虽然在定位精度上有可取之处，但是却并不适用于那些低功耗、低成本等应用领域。

而在无需测距算法定位中，在成本、功耗等方面极具有优势，与此同时对硬件要求较低，也无需任何基础设施，因此备受关注。但是，此类传统的定位算法更加的是适用于那些静态的传感器网络定位环境[6]，对于那些应用于动态环境的定位，这些算法就会显得很不适用，所以本文提出了一种新的定位算法。

本文提出的新的定位改进算法，即能够实现相对高的定位精度，又能够满足动态定位。该改进算法主要是依靠信标节点来帮助进行未知节点自我定位。在定位的过程中，通过依靠节点本身的硬件设备来获取接收到的信号强度[7]。在接收到分组信息之后，根据接收节点是否为信标节点来判断对此分组信息是否进行保存。如果接收节点是信标节点，则丢弃此分组信息；否则保存此分组信息。然后，通过循环的形式来选择3个分组信息进行组合三角形，在本文中被称为虚拟三角形。同时根据本文所提出的内点测试方法来进行有关判断此被定位未知节点是否在此三角形中，如果被定位未知节点在此虚拟三角形中，则保留此三角形；否则，丢弃此虚拟三角形，重新组合三角形，直到所需要的次数或者定位的精度。在确定虚拟三角形之后，根据传统的质心方法进行最终的定位，并且对节点进行升级，避免节点共线，不能够形成三角形问题[8]。

所以本文的新算法，主要是在传统的质心算法上增加了未知节点位置判断这个定位主要环节，使得新算法在拥有自我定位的特点上，避免了传统三角形质心与未知节点位置误差太大的情况出现，并且具有更高的定位精度和定位覆盖度。

2 算法基础介绍

此改进算法主要是对质心算法的定位误差和定位覆盖度进行了有关改进。在算法的实施过程中，首先需要节点的简单硬件支持，来判断未知节点所在的三角形，此过程主要是依靠虚拟三角形和内点测试方法，来确定未知节点所存在的虚拟三角形。

2.1 虚拟三角形介绍

虚拟三角形基本思想：假设存在n个端点，那么共有C(3，n)种不同的选取方法来确定不同的三角形，但是为了降低消耗，往往设置循环的次数或者定位所需的精度为限制条件，而在本论文中，此三角形被称为虚拟三角形，如图1所示。

图1 虚拟三角形的形成

2.2 内点测试方法

假如端点的移动存在一个方向，沿着这个方向节点D会同时远离或接近三角形的3个端点A、B、C，那么可以认为节点D位于△ABC之外，如图2所示；或者，当远离二个端点并且接近一个端点，以及靠近二个端点并且远离一个端点的时，则认为D位于△ABC内，如图3所示。

图2 三角形外

图3 三角形内

此算法主要是通过传感器节点在网络中的移动，并且利用无线信号的传播特性，即信号在传输过程中的损耗情况，来判断是否远离或靠近信标节点，现阶段的传感器节点均具有此特性。

在算法实现的过程中，因为节点的移动很微小就可以满足需求，所以假设在节点移动前后的时间内，信标节点的能量消耗可以简单的忽略或者信标节点具有一个持续的供能系统，即具有相同的开始条件。

2.3 质心定位算法理论

质心算法：多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐标。质心定位算法首先确定包含未知节点的区域，然后计算这个区域的质心，最终将其作为未知节点的位置，如图4所示。

图4 多边形质心

在质心算法中，信标节点周期性地向邻近节点广播信标分组信息，信标分组信息中包含信标节点的标识号和位置信息。当未知节点接收到来自不同信标节点的信标分组信息数量超过某一个门限k或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心。

质心算法完全基于网络连通性，无需信标节点和未知节点之间的协调，因此比较简单，容易实现。但质心算法假设节点都拥有理想的球型无线信号传播模型，而实际上无线信号的传播模型并非如此。同时，质心定位算法对传感器节点的布置有很大的关系，密度越大，分布的越均匀，定位精度越高，所以很难实现理想的需求。

当网络节点分布不均匀时，如图2所示，未知节点与质心的位置存在了很大的误差，此时质心算法就很不适用。

3 改进的算法及其实现

3.1 有关节点描述

邻居节点之间的通信如下，在网络中所有的节点具有相同的通信半径R，如图5所示。

信标节点：装有GPS定位系统或其它定位装置硬件，并且位置信息已知的传感器节点。

未知节点：未知自己的位置信息，但是同样具有GPS定位系统或其它定位装置硬件的传感器节点。

图5 节点描述

邻居节点：是指在信标节点的信号发射范围内的所有节点。

虚拟节点：此节点是根据算法所虚拟得到，在未知节点收到分组信息，组合成三角形，进行三角形判断后计算所得出的三角形质心节点被称之为虚拟节点。

3.2 算法流程图

算法的流程图，如图6所示。

图6 算法流程

3.3 算法实现过程

在此算法的实施过程中，主要包括节点信息的发送阶段、接收阶段、定位阶段以及改进阶段。在节点部署之后，信标节点已经明确自己的位置坐标。

(1)初始化阶段：此阶段设定所有信标节点以一定的周期来广播自己的分组信息，包括位置(x，y)，ID号；对于未知节点，T=0；对于信标节点，T=1；其中的ID号被用于唯一的区别节点。

(2)接收阶段：在此定位算法中，未知节点会接收到二次分组信息，分别是移动前和移动后，在接收数据后，根据信号的信息，得到信号的强度，并存储。但是，信标节点会丢弃同是信标节点发送的分组信息。

(3)定位阶段：在此阶段中，未知节点已经存储n个分组信息，在这些分组信息信息中随机选择3个分组信息合行成虚拟三角形，在组合之后根据内点测试理论来判断未知节点的位置。

通常在未知节点的移动过程中，未知节点距信标节点越远，其接收到信标节点的信号强度就越弱，根据未知节点移动前所接收到信标节点所发出的分组信息中的信号强度值和在自己移动后所接收到的信号强度值进行比较，以此来判断此未知节点的移动情况，判断是否在此虚拟三角形中。由于节点的移动往往很快，距离很小，所以可以考虑忽略信标节点的能量消耗。

此判断过程主要是根据节点的信号强度参数，来决定三角形是否被放弃。在确定未知节点存在于此三角形中之后，计算出三角形的质心，称为虚拟节点，位置(Xn，Yn)；否则，放弃此三角形，如此的循环下去，直到完成所有的C(3，n)种组合或者得到算法所需的精度。

在得出所有的虚拟节点位置信息之后，根据质心定位算法来进行最终的未知节点自我定位，未知节点的坐标为(X，Y)

(4)改进阶段：在定位完成后，未知节点对自己进行初始化，将T=1；为的是将其变为信标节点来使用，以提高无线传感器网络的节点覆盖度。当节点处于静止状态时，可以被看为信标节点，从而提高了节点的定位精度。

4 算法理论验证

(1)信标节点发送的数据分组信息格式，如表1所示，其中包括节点ID和位置信息。

表1 发送的分组信息格式

(2)在邻居节点接收到此分组信息后，首先会判断自己的T，若为是1，表示自己是信标节点，则丢弃此分组信息；否则，表示自己是未知节点，于是根据接收到的信号得到信号强度，并存储，存储的分组信息格式如表2所示。

表2 存储的分组信息格式

(3)在存储n个分组信息之后，进行内点测试，判断过程如下：

如表3和表4所示，其中表3为未知节点在移动前所接收到的周围信标节点的分组信息后存储的信息，其中包含信标节点的节点ID号，位置信息，以及计算得到的信号强度；表4为未知节点在移动后所接收到的周围信标节点的分组信息后存储的信息，其中包含信标节点的节点ID号，位置信息，以及计算得到的信号强度。

根据未知节点所接收到的二个分组信息中的信号强度，可以得出：在移动过程中，未知节点对信标节点A和C的信号强度在减小，即可以得出远离信标节点A和C；同时对B的信号强度在增加，即可以得出接近信标节点B。所以根据内点测试方法理论，可以得出未知节点存在于此3个信标节点A、B和C所组成的虚拟三角形中，所以保留此三角形。

表3 移动前的存储分组信息

表4 移动后的存储分组信息

(4)计算虚拟三角形的质心，在此算法中被称为虚拟节点(Xn，Yn)，存储在未知节点中，格式如表5所示。

表5 虚拟节点位置信息

最终根据质心算法，求出未知节点的位置，即得出

所以，未知节点的位置坐标为(36.67，46.67)。

5 算法仿真结果

在算法研究的基础上，借助Matlab，对算法进行了仿真，验证了其有关的性能。在实验环境下，在无线传感器网络规模中随即布置大约20个节点，随机分布在50×50的正方形区域中，每个节点具有相同的通信距离，其中的分组信息分发方式采用泛洪路由。

有关算法的性能主要从定位精度和定位覆盖率两个方面对其进行评估，每种算法仿真随机运行10次，然后取平均值，仿真结果如图7所示。

图7 节点定位误差曲线

图7是定位误差的仿真曲线，由于当信标节点较少时，并且在未知节点周围的多边形面积较小时，改进的定位算法误差和原算法的误差相当。这是因为，改进算法是采用取多个包含未知节点的三角形质心来缩小多边形面积，以减少误差，当未知节点的多边形面积较少时，就没有很大的必要去进一步缩小，从而效果不是很明显。

但是，随着未知节点多边形面积的增加，以及信标节点的分布不均匀，误差会明显的增大，此时改进的算法就起到了很大的作用。在未知节点被定位之后，可以通过升级的形式使得其变为信标节点。仿真结果如图8所示。

图8 节点定位覆盖率曲线

图8是节点定位覆盖率的分析曲线图，当信标节点个数较少时，有些节点无法找到3个以上的信标节点去进行自我定位，从而不能计算出自己坐标的位置信息，但是随着未知节点被确定后进行升级为信标节点的做法，势必会提高信标节点的数量，节点的覆盖率达到提高。所以改进后的算法，提高了定位的精确度。

由此可得出我们的算法，对于动态环境，具有更大的优势。

6 结束语

本文根据无线传感器网络质心定位算法的特点，提出了高定位精确度、高覆盖度且实用的新定位算法。研究发现该算法结合了测距算法定位和非测距算法的优点，即误差小和容易实现等特点。其主要通过接收到的分组信息来得到虚拟三角形，通过内点测试的方法来判断未知节点的位置，然后在确定其位置之后，决定是否保存此三角形。所以此算法主要解决了在定位过程中存在的不准确和难定位等困难。最后仿真结果显示，我们提出的算法与传统的静态定位算法相比，在更加适用于现实的动态环境外，大大的提高了节点的定位精度和无线传感器网络节点覆盖度。与此同时，在以后的工作中，我们仍希望可以对此算法进行有关的改进。

[1] 孙利民.无线传感器网络[M].北京:清华大学出版社,2005:148-155.

[2] He T,Huang C D,Blum B M,et al.Range-free localization schemes in large scale sensor networks[C].Proc of the 9th Annual Int'l Conf on Mobile Computing and Networking.San Diego:ACM Press,2003:81-95.

[3] Yu N,Wan J.SL-R distributed localization algorithm for wireless sensor networks[C].Proceedings of IEEE International Conference on Wireless Communications,Networking and Mobile Computing,2007:2360-2363.

[4] Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C].Proc of the IEEE/RSJ Int Conf on Intelligent Robots and Systems,2001:1312-1320.

[5] 安恂.一种用于无线传感器网络的质心定位算法[J].计算机工程与应用,2007,43(20):136-138.

[6] 王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.

[7] 陈维克,李文锋.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报(交通科学与工程版),2006,30(2):265-268.

[8] 于宁,万江文,吴银锋.无线传感器网络定位算法研究[J].传感技术学报,2007,20(1):187-192.

[9] 赵昭,陈小惠.无线传感器网络中基于RSSI的改进定位算法[J].传感技术学报,2009,22(3):391-394.