一种无线传感器网络非均匀分布节点定位算法

赵亚涛，王玉宝

(燕山大学信息科学与工程学院，河北秦皇岛066004)

0 引言

无线传感器网络(wireless sensor network，WSNs)越来越受到关注。定位技术是其关键技术之一，近年来，研究者们提出了很多只需用很少锚节点来协助计算未知节点绝对坐标的定位算法［1］。这些算法主要分为:基于测距的和无需测距的。其中，基于测距的算法主要由到达时间差［2］(time difference of arrival，TDoA)，到达角度［3］(angle of arrival，AoA)，接收信号强度指示［4］(received signal strength indicator，RSSI)和到达时间(time of arrival，ToA)等来获得距离或角度信息，进而定位;而无需测距的算法，只需要获得网络连通性等少量信息就可实现定位，且不需要节点额外的硬件开销。因此倍受关注，如，MDS-MAP算法［5］，凸规划算法［6］，质心算法，DV-Hop 算法［7］及其改进算法［8～10］等。本文基于DV-Hop算法的原理，利用加权思想处理锚节点的平均跳距，提出了一种无线传感器网络非均匀分布节点定位算法——W-DV-Hop(weighted-DV-Hop)算法。

1 计算节点位置的基本方法

传感器节点定位的过程中，未知节点获得锚节点的距离后，通常用三边测量法(Trilateration)来计算自己的位置，如图1所示。

图1 三边测量法Fig 1 Trilateration

已知 A，B，C 3 个锚节点的坐标分别为(xa，ya)，(xb，yb)，(xc，yc)，以及它们到未知节点 D的距离分别为da，db，dc，假设D的坐标为(x，y)。那么，存在下列公式

由此可得到未知节点D的坐标为

2 W-DV-hop算法

本算法的定位过程分为3个阶段:第一阶段，根据距离矢量协议使网络中所有节点获得各个锚节点的最小跳数信息;接着，锚节点利用公式(3)计算各自平均跳距［7］(Hop-Sizei)，由式(4)得到网络平均跳距HopSize;然后，作为校正值广播到网络，即有

其中，HopSizei表示第i个锚节点的平均跳距值，dij表示锚节点i，j之间的欧氏距离为(xi，yi)，(xj，yj)表示锚节点 i和锚节点 j的坐标，hij表示锚节点i与j(j≠i)之间的跳数，N表示网络中节点总个数，M表示锚节点的个数，ai表示到第i个锚节点有最少跳数的未知节点的个数，wi表示HopSizei的权重，即锚节点i的加权值等于到第i个锚节点有最少跳数的未知节点的个数除以未知节点的总个数。这样做一个归一化的处理，使用统一标准对锚节点的平均跳距进行处理，并保证各个平均跳距的权值之和为1。同时，通过对平均跳距赋以不同的权值，区分了不同锚节点的平均跳距对网络平均跳距的影响程度。

第二阶段，未知节点利用网络平均跳距和到锚节点的跳数信息计算到锚节点的距离(称为跳段距离)，如公式(5)所示

其中，hlk表示未知节点l到锚节点k的最小跳数。

当未知节点获得3个或更多锚节点的信息后，则在第3阶段进行自身定位。

若网络中有计算能力很强的节点，则可以由其收集锚节点的平均跳距并计算网络平均跳距，然后广播到网络;还可以由锚节点记录彼此的平均跳距来各自计算得到网络平均跳距。然后，将该值作为校正值广播到网络，由于锚节点广播的校正值是相同的，可以根据一定的转发策略广播到网络，以达到减少能量消耗的目的。具体的转发机制［11］包括:基于概率转发、基于计数器转发、基于距离转发、基于位置转发……，本文采用基于计数器转发。

3 非均匀分布网络模型

当无线传感器网络应用于河流、建筑物的环境监测、智能家居时，难免出现节点的非均匀布置。图2即为一常见的非均匀分布C型网络。

图2 C型网络模型Fig 2 C type network model

4 仿真结果与比较分析

为了验证算法的性能，在计算机上利用Matlab7进行仿真并与DV-Hop算法进行了比较，实验设置各个节点有相同的通信半径R。

4.1 平均定位误差

性能评价采用平均误差函数

其中，(xi，yi)表示未知节点 i的实际坐标，(x'i，y'i)表示未知节点i的估计坐标。平均误差越小，则定位精度越高;反之，越低。

在实验过程中，网络节点随机分布，生成如图2 C型网络和图3所示的网格分布网络。本文算法在图3所示网络模型下进行仿真。

图3描述了另一常见的非均匀分布网络模型，横轴和纵轴分别表示节点的横纵坐标值，其中锚节点和未知节点随机产生，且考虑定位因素从布置3个锚节点(星型节点)开始进行性能仿真。

图3 网格分布网络Fig 3 Grid distribution network

图4描述了图3所示网络的节点平均定位误差和锚节点个数的关系曲线，锚节点个数依次为3，4，5，6，7，8。由图示曲线描述:随着锚节点个数的增加，2种算法的平均定位误差总体呈现降低趋势，由于网络节点布置的随机性曲线产生波动。看出当锚节点个数为3时，新算法平均定位误差值比DV-Hop算法降低最多为29%左右，主要原因是锚节点的个数较少时，在非均匀分布网络锚节点的平均跳距不能很好地接近网络每跳距离，而影响定位精度，由于新算法采用的网络平均跳距能体现大多数节点所适合采用的网络每跳距离，能从总体上降低节点的平均误差，且可以在满足需要的同时降低网络成本。

需要说明的是，网络中节点的平均定位误差不总是随着锚节点个数的增加而降低，这是因为平均误差是所有未知节点误差的和除以未知节点个数，当网络中节点总数一定而锚节点的个数增加时，相应的未知节点的数目将会减少，即公式(6)中的分母变小，这将使平均误差值具有不确定性。

图5曲线的横纵坐标分别表示图3所示网络节点的通信半径和平均误差，由曲线描述看出:新算法相比原算法定位误差最好时要低28%左右，当R≥60 m时，2种算法的平均误差值趋于一致，这主要是由网格之间的间距决定的，但相对DV-Hop算法，新算法在R从刚好满足节点通信的大小增大到R为60m的阶段平均定位误差要比DV-Hop算法低很多。

图4 不同锚节点的平均定位误差Fig 4 Average localization error of different anchor nodes’number

图5 平均定位误差与半径R的关系Fig 5 Relation between average localization error and R

4.2 能耗分析

网络能耗主要包括通信开销和计算开销。假设网络总节点个数为N;锚节点个数为M;计数器门限为L(N·L≥M)，分析可知，当L取值较小时，出现部分未知节点不能定位;当取值较大时，锚节点的覆盖会出现重叠，造成能量的浪费。对于L的取值可以根据实际取值，为满足网络的整体要求要适当偏大，当节点接收的计数信息大于L时，不再转发网络平均跳距。对于DV-Hop算法采用两次泛洪，则通信开销为2MN;新算法采用基于门限转发则通信开销为MN+N/M。新算法需要得到网络平均跳距，则相对DVHop算法增加的计算开销为2M+1(M次除法，M次乘法和一次加法)，可得2种算法的能耗差值∀

进一步化简得到

在实际应用中，锚节点的比例很小，式(8)肯定会大于0，由此可知新算法的能耗较低。

由图6可以看出:当满足定位的最低要求时，本文算法的数据包个数大约为DV-Hop算法的1/3，当锚节点个数增加时，DV-Hop算法用于定位的数据包数目急剧增加，而本文算法变化不十分明显。且新算法的计算开销只是在锚节点(或参与计算网络平均跳距)的能耗加大时对于占总节点大比例的未知节点能耗会相对DV-Hop算法减少很多，能很好地延长节点寿命。

图6 网络能耗Fig 6 Energy consumption of network

5 结论

本文提出一种无线传感器网络非均匀分布的节点定位算法——W-DV-Hop算法。该算法不需要节点的额外配置，网络成本低，主要采用加权处理锚节点的平均跳距作为网络平均跳距HopSize，使未知节点到锚节点的跳段距离更接近实际距离。仿真结果表明:同等条件下，新算法比DVHop算法定位精度要高，并且能量消耗降低，能有效延长节点的寿命。

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

［2］陈鸿龙，李鸿斌，王 智.基于TDoA测距的传感器网络安全定位研究［J］.通信学报，2008，29(8):11－21.

［3］Niculescu D，Nath B.Ad Hoc positioning system(APS)using AoA［C］∥Proc of IEEE the InfoCom，San Francisco，CA，USA，2003:1734－1743.

［4］赵 昭，陈小惠.无线传感器网络中基于RSSI的改进定位算法［J］.传感技术学报，2009，22(3):391－394.

［5］Shang Y，Ruml W.Improved MDS-based localization［C］∥Proc of the IEEE Infocom，Hong Kong，2004:2640－2651.

［6］Doherty L，Pister K，Ghaoui L.Convex position estimation in wireless sensor networks［C］∥Proc.of the IEEE Infocom，Anchorage，AK，USA，2001:1655－1663.

［7］Niculescu D，Nath B.Ad Hoc positioning system(APS)［J］.IEEE Globe Com，2001(5):2926－2931.

［8］嵇玮玮，刘 中.DV Hop定位算法在随机传感器网络中的应用研究［J］.电子与信息学报，2008，30(4):970－974.

［9］付 华，胡 冰.一种无线传感器网络节点定位算法的改进［J］.传感器与微系统，2009，28(3):27－29.

［10］彭 刚，曹元人，孙利民.无线传感器网络节点定位机制的研究［J］.计算机工程与应用，2004，40(35):27－29.

［11］Ni SY，Tseng Y C，Chen Y S，et al.The broadcast storm problem in a mobile Ad Hoc Network［C］∥Proceedings of Mobicom’99 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking，1999:51－162.