胡 伟，徐福缘

（1.上海理工大学 管理学院，上海200093；2.绵阳师范学院 数学与计算机科学学院，四川 绵阳621000）

0 引 言

现代无线技术、电子通信技术的快速发展促进了无线传感器网络的产生［1］。无线传感网是由部署在监测区域内大量的廉价微型并装备有低能耗收发器和有限数据处理能力的传感器节点通过无线通信方式形成的一个多跳自组织网络［2－3］，其中定位技术是实现无线传感器网络各种应用的前提和基础［4］。如果无线传感器网络节点所感知到的外部信息缺乏位置数据，则此信息是无意义的信息，因此对无线传感器网络 中的节点定位技术进行研究具有重要的意义。

目前研究者已经提出了许多节点定位算法，一般可分为基于测距和免测距两种类型。基于测距的定位技术一般定位精度较高，但是对无线传感器网络节点的硬件要求也比较高。对于免测距的定位算法其代表性的研究成果包括Cricket定位系统［5］、SPA［6］、凸规划定位算法［7］、APIT算法［8］、Bounding Box算法［9］、DV－hop算法［10］、Amorphoous算法［11］、Euclidean 算 法［12］和 Robust Position 算法［13］等。免测距的定位方案由于其实现简单、对硬件要求低，所以受到业界的重视。但是基于免测距的定位算法在定位精度和节点能耗方面都不是很理想，要么定位精度提高得不够明显，要么需要用较大的通信开销或计算量才能获得较高的定位精度，网络的拓扑结构对算法的性能影响非常大。基于以上原因，本文提出了一种基于信标优化的无线传感器网络定位算法ConDV－Hop，该算法采用贡献因子Contri对信标节点进行优化选择，用最优的3个信标节点组对待定位节点的位置进行初步估算；然后利用反馈思想引入修正系数α和β，用贡献因子次之的信标节点组去估算贡献因子最大的信标节点组的坐标，进而用计算出的位置修正系数α、β分别对待定位节点估算位置中的x和y进行修正，使网络中的累积误差减小。仿真实验结果表明，本文所提出的算法在定位精度、能耗和适应性方面都有明显的优势。

1 信标优化选择

传统的DV－Hop算法在节点分布的密集网络中性能表现良好，但是在非均匀网络中其定位效果和精度会急剧下降，网络的拓扑结构对DV－Hop算法的性能起着至关重要的作用。为了克服网络拓扑结构对DV－Hop算法的影响，在未知节点进行定位时，我们采取优化选择信标节点的策略，用贡献因子对邻近的信标节点组 （3个信标节点为一组）进行评价，将最优的信标节点组挑选出来。具体实现方法如下：

设A、B、C分别表示某一未知节点通信半径内的任意3个信标节点组成的三角形的内角，Nb为未知节点附近邻居信标节点的个数，组合数为未知节点可以选择的信标节点组的数目，NCi＝Max｛cosiA，cosiB，cosiC｝，其中i∈ ［1，］，NCi的取值范围为0.5到1之间。那么贡献因子Contri可表示为

式中：i∈ ［1，］。给定一个未知节点，利用上述方法可以分别求出每个信标节点组的贡献因子，记为Contr1、Contr2、…、Contri。比较个贡献因子的大小，将最大的贡献因子求出来，记为Contrmax，根据Contrmax可推出最优的信标节点组为 ｛NA、NB、NC｝，它们的坐标分别为（XA，YA）、（XB，YB）和 （XC，YC）。

2 基于信标优化选择的定位算法

传统DV－Hop算法比较适合于均匀网络，当网络节点分布均匀时，节点间的直线距离可以近似的用平均每跳距离乘以跳数来取代［14］。当网络为稀疏网络且不均匀时，那么在计算平均每跳距离时就会存在误差，待定位节点与信标节点之间的距离也会存在误差。在DV－hop算法中定位过程中的信息以波的形式从中心向网络四周扩散，误差随着扩散过程将不断累积和放大。

2.1 平均跳距

传统DV－Hop算法主要分为以下3个步骤［15］：

（1）信标节点在全网中洪泛分组信息，网络中的节点可以获得相应路数信息和信标节点的位置信息。

（2）信标节点之间利用如下公式计算平均每跳距离［16］

式中： （xi，yi）、 （xj，yj）——信标节点i和j的坐标，hij——信标节点i和j之间的跳数。然后将Hopsizei作为一个校正值广播至网络中。

（3）当待定位节点获得足够的信息后，利用三边或多边测量定位法进行定位。

为了克服DV－Hop算法的缺陷，我们引入贡献因子，优化待定位节点用于定位的信标节点。设待定位节点的坐标为 （x，y），通过本文上面的方法将其邻近的3个信标节点组求出来，求出的最优信标节点组为NA、NB和NC，它们的坐标分别为 （XA，YA）、（XB，YB）和 （XC，YC），则

此时NA、NB和NC之间的跳数分别为hAB、hBC和hAC，所以平均跳距为

引入贡献因子Contri，更新后的平均跳距可表示为

2.2 位置估计

待定位节点到NA、NB和NC的修正距离，可用dA、dB和dC表示，那么

根据上面的已知数据，可以得到如下的方程

上述二元二次方程可以用标准的最小二乘法求解，可计算出待定位节点的估算位置 （x，y）。下面利用反馈思想对待定位节点的估算位置进行修正。用贡献因子次之的信标节点组去估算贡献因子最大的信标节点组的坐标，得出的贡献因子最大信标节点组的估算坐标分别为 （x′A，y′A）、 （x′B，y′B）和 （x′C，y′C），设α、β为估算位置的修正系数，则

用α、β对 （x，y）进行修正

此时，（x′，y′）即为修正后的待定位节点的坐标。

2.3 ConDV－Hop算法描述

基于信标优化选择的无线传感网络定位算法ConDVHop描述如下：

步骤1 初始化。将待定位节点和信标节点随机布署在传感区域中，设置好信标节点的比例及节点的通信半径。

步骤2 跳数的计算。信标节点将自身的位置信息进行全网洪泛，使网络中的所有节点获得相应的跳数信息。

步骤3 信标优化选择。采取优化选择信标节点的策略，用贡献因子Contri对待定位节点邻近的信标节点组进行评价，将Contri按大小进行排列，并且将最大的和次大的信标节点组保存起来。

步骤4 平均跳距的计算。利用步骤3中求出的信标节点估算平均跳距Hopsize，并用贡献因子对Hopsize进行更新，更新后的平均跳距为Hopsize′。

步骤5 估算位置。待定位节点根据更新后的跳距Hopsize′和hA、hB及hC的大小，分别计算出到3个最优信标节点的距离dA、dB和dC。然后利用最小二乘法求解出待定位节点的估算位置 （x，y）。

步骤6 位置修正。用位置修正系数α、β分别对待定位节点估算位置中的x和y进行修正，得出的新坐标为（x′，y′）。

3 仿真实验及性能分析

为了检验ConDV－Hop算法的性能，本文在MATLAB平台上进行了仿真，并分析了算法的性能，和传统的DVHop算法进行了对比。仿真环境配置及一些概念如下：

（1）仿真区域：所有传感器节点随机分布在100×100m的正方形区域内。

（2）通信半径R：在无线传感器网络里，节点通信半径最开始设为15m。

（3）单个节点定位误差ES：设rest为未知节点的估计位置，rreal为未知节点的真实位置，则

（4）总平均定位误差Et：设m为网络中信标节点的数目，n为网络中所有节点的数目；为第i个未知节点的估计位置，为为第i个未知节点的实际位置，则

我们比较了在均匀网络和非均匀网络中，ConDV－Hop算法与DV－Hop算法在信标节点比例、总节点数目和通信半径大小变化的情况下网络的平均定位误差变化情况。

图1和图2表示在信标节点比例变化的情况下，在均匀网络和非均匀网络中节点的平均定位误差变化图。在实验中，节点总个数为200，信标节点的比例分别是10%、15%、20%、25%、30%、35%，其中横坐标表示信标节点所占的比例，纵坐标表示节点的平均定位误差。

从图1和图2可以看出，两种算法在均匀网络的定位误差要低于在非均匀网络中的定位误差，其中传统DVHop算法的变化最为明显，网络的拓扑结构对DV－Hop算法的性能影响非常大，而对ConDV－Hop算法的影响要小于对DV－Hop算法的影响，说明本文提出的ConDV－Hop算法其适应性更强。在均匀网络和非均匀网络中，ConDV－Hop算法平均定位误差分别为19.4%和32.4%，而传统的DV－Hop算法平均定位误差分别约为26.5%和41.8%。

图3和图4表示在节点通信半径变化的情况下，在均匀网络和非均匀网络中节点的平均定位误差变化图。在实验中，节点总个数为200，信标节点的比例为10%，节点的通信半径从最初的15m逐渐增大，分别为15m、20m、25m、30m、35m和40m。

从图3和图4可以看出，无论是在均匀网络还是在非均匀网络中，ConDV－Hop算法比传统的DV－Hop算法定位精度都有明显的提高。在均匀网络中，ConDV－Hop算法比传统的DV－Hop算法平均定位误差降低6.1%；在非均匀网络中，ConDV－Hop算法比传统的DV－Hop算法平均定位误差降低约10.9%。

图5和图6表示在节点总数变化的情况下，在均匀网络和非均匀网络中节点的平均定位误差变化图。在实验中，节点总数分别为200、250、300、350、400、450，节点通信半径为15m，信标节点的比例使终保持10%。横坐标表示节点的总个数，纵坐标表示平均定位误差。

从图5和图6可以看出，在均匀网络和非均匀网络中，随着总节点数的增加，两种算法的平均定位误差都在减少，ConDV－Hop算法的平均定位误差比传统的DV－Hop算法分别降低约7.2%和10.5%，其性能要优于传统的DV－Hop算法。

4 结束语

本文在继承传统DV－Hop定位算法优点的基础上，提出了一种新的算法ConDV－Hop。该算法采取优化选择信标节点的策略，克服了网络拓扑结构对DV－Hop算法的影响；利用反馈思想引入修正系数，对待定位节点的估算位置进行修正，提高了节点的定位精度。仿真实验结果表明，相比于传统的经典算法DV－Hop，本文所提出的算法在定位精度、能耗及适应性方面都有明显的优势。

由于无线传感器网络节点存在资源有限、随机部署、对环境依赖性过高等特性，因此如何使定位方案在满足自组织性、健壮性、能量高效和分布式计算等要求的前提下，具有低费用、低能耗和高适应性等性能成为下一步将要研究的重点。

［1］WANG Fubao，SHI Long.Self－localization systems and algorithms for wireless sensor networks ［J］.Journal of Software，2005，16 （5）：857－868 （in Chinese）. ［王福豹，史龙.无线传感器网络中的自身定位系统和算法 ［J］.软件学报，2005，16 （5）：857－868.］

［2］SUN L M，LI J Z.Wireless sensor network ［M］.Beijing：Tsinghua University Publisher，2005：1－3.

［3］SONG W，WANG B，ZHOU Y B.Technology and application of wireless sensor network ［M］.Beijing：Electronics Industrial Publisher，2007：2－6.

［4］SUN Limin，LI Jianzhong，CHEN Yu，et al.Wireless sensor network ［M］.Beijing：Tsinghua University Press，2005：141－146（in Chinese）.［孙利民，李建中，陈渝，等.无线传感器网络 ［M］.北京：清华大学出版社，2005：141－146.］

［5］YU K G.3Dlocalization error analysis in wireless networks［J］.IEEE Transaction on Wireless Communication，2007，6（10）：3473－3481.

［6］LI Z，Trappe W，ZHANG Y，et al.Robust statistical methods for securing wireless localization in sensor networks［C］.Los Angeles，CA，USA：Proc of International on Confabulation Process Sensor Networks，2005：91－98.

［7］Pradip De，LIU Yonghe，Sajal K Das.Modeling node compromise spread in wireless sensor networks using epidemic theory［C］.Proceedings of the International Symposium on a World of Wireless，Mobile and Multimedia Networks，2006：237－243.

［8］SHAN Z L，YUM TA，KSHIN G P.Precise localization with smart antennas in Ad Hoc networks［C］.Proceedings of IEEE GLOBECOM.Iscataway，NJ，USA：IEEE，2007：1053－1057.

［9］Kout sonilas D，Das S M，HU Y Charlie.Path planning of mobile landmarks for localization in wireless sensor networks ［J］.Computer Communication，2007，30 （13）：2577－2592.

［10］Peter Corke，Ron Peterson，Daniel a Rus.Localization and navigation assisted by cooperating networked sensors and robots［J］.International Journal of Robotics Research，2005，24 （9）：771－786.

［11］Aline Baggio，Koen Langendoen.Monte Carlo localization for mobile wireless sensor networks ［G］.LNCS 4325：2nd Int Conference on Mobile Ad－hoc and Sensor Networks，2006：317－328.

［12］Dil B，Dulman S，Havinga P J M.Range based localization in mobile sensor networks［G］.LNCS 3868：Proc of 3rd European Workshop on Wireless Sensor Networks，2006：164－179.

［13］Line Baggio A，Koen Langendoen.Monte Carlo localization for mobile wireless sensor networks ［J］.Ad Hoc Networks，2008，6 （5）：718－733.

［14］WANG W D，ZHU Q X.RSS based Monte Carlo localization for mobile sensor networks［J］.IET Communications，2008，2 （5）：673－681.

［15］Kuo Feng Ssu，Chia Ho Ou，Hewijin Christine Jiau.Localization with mobile anchor points in w ireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2005，54（3）：1187－1197.

［16］PAN J J F，YANG Q，CHANG H，et al.A manifold regularization approach to calibration reduction for sensor－network based tracking ［C］.Proc of the American Association for Artificial Intelligence.Boston：AAAI Press，2006：988－993.