无线传感器网络中基于传输时间比的定位算法及改进

刘 俞

(1.南京航空航天大学，南京 210016；2.马鞍山职业技术学院，马鞍山 243031)

无线传感器网络中基于传输时间比的定位算法及改进

刘 俞1，2

(1.南京航空航天大学，南京 210016；2.马鞍山职业技术学院，马鞍山 243031)

提出一种基于测距的定位新算法，即基于节点间信号传输时间比的定位算法。利用TROA算法的思想改进DV-Hop算法并且进行仿真对比。仿真结果表明，改进后的算法定位精度有明显提高。

无线传感器网络；节点定位；时间比；DV-Hop算法

无 线 传 感 器 网 络［1］（wireless sensor network，WSN）是由部署在监测区域内的大量传感器节点组成，这些节点通过无线通信方式形成一个多跳的自组织网络系统，从而构成一个无线传感器网络。其中，节点定位是无线传感器网络配置和运行的一个基本和关键问题。所谓节点定位是指对于一组未知位置坐标的网络节点，通过估计至邻居节点的距离或邻居数目，利用节点间交换的信息，确定每个节点位置的机制。通常配置网络时不能对所有节点实施精确控制和人工设置。

无线传感器网络的应用大多需要掌握节点的位置信息，节点定位的重要性主要在于以下两个方面：（1）须知道节点感知数据的发生位置才有应用价值；（2）无线传感器网络的很多通信协议是在已知节点位置的基础上运行的。另外基于节点的已知位置可优化网络运行期间的值守调度机制，使网络中冗余节点不定期地轮休以延长寿命。

目前，无线传感器网络节点定位算法总体分为两类［2］：基于测距的(range-based)定位算法和距离无关的(range-free)定位算法。Range-based定位算法常用的测距技术有 RSSI［3］、TOA［4］、TDOA［5］和 AOA［6］，而典型的 range-free 定位算法有质心［7］、DV-Hop［8］、APIT［9］、MDS-MAP［10］等。

1 基于节点间信号传输时间比的定位算法

本次研究首先提出一种新的基于测距的定位算法——基于节点间信号传输时间比的定位算法，简称为TROA。

图1 TROA算法示意图

此算法的基本思想是，利用节点间信号传输所需的时间比值求出未知节点与锚节点间的距离，进而对未知节点进行定位。这种算法首先求出邻近两个锚节点间的距离，如图中锚节点A与C间的距离D(A，C)；同时利用定时器测出两个相邻锚节点A与C间的信号传输所需时间Δt(A，C)，以及未知节点与邻近的锚节点间的信号传输所需时间，如图中B与C、D与C、E与C之间信号传输所需时间Δt(B，C)、Δt(D，C)和 Δt(E，C)；接下来通过时间比值即可分别计算出未知节点B、D、E到邻近锚节点C之间的距离：

本算法需要在网络中每个节点内置一个计时器，用于记录信号传送所需的时间。在每个节点中设置一个 Void Message(idi，idj)数据包（其中，idi为发出节点的id号，idj为接收节点的id号），用于在节点间传送，从而测出其在某两个节点之间的路径上传输所需要的时间。每个锚节点设置一个数据包：InfoMa （idi，xi，yi，hopsi）， 其中包含了该锚节点的 id号、 位置信息 （xi，yi） 以及跳数信息hopsi， 初始化hopsi为0，数据包InfoMa主要在锚节点节传送，用于测算两个锚节点的距离和相隔跳数，从而估计网络平均每跳距离。另外，为了能测算出两个节点间传送数据包所需的精确时间，需要将计时器记录的时间减去传送路径中途径的所有节点的转发延时，所有事先要求测出节点转发Message数据包所需的延时，此延时时间与传感器节点的工作频率以及转发数据包的大小相关。

算法具体实现方法如下：

（1)利用已有的路由协议，在网络中的所有锚节点同时广播InfoMa数据包和Message数据包，此时锚节点的计时器开始计时。

（2）待定位节点利用路由协议获得距锚节点的最小跳数。

（3)锚节点接收到其他锚节点发来的InfoMa数据包和Message数据包后，从InfoMa数据包中获得对方锚节点的位置信息，计算与邻近锚节点间的距离，同时立刻返回自己的Message数据包。

（4）当i号锚节点接收到j号锚节点返回的Mess age数据包时，计时器停止计时，此时计时器记录的时间即为i号锚节点与j号锚节点间传送数据包所经历的时间，是两个锚节点通过同一条路径来回传送数据包所需的时间Δt(i，j)，其值为单程传送用时的2倍。

（5）精确计算出两个锚节点间单程传送数据包所需的时间

h(i，j)为两个锚节点间的传送路径中经过的所有节点的个数，ω为每个节点转发Message数据包需要的延时。

（6）每个锚节点将计算得到的与相邻锚节点的距离值广播至网络中，每个未知节点接收第一个到达的距离值。

（7）未知节点k向发出距离值的那个锚节点i发出Message数据包，同时此未知节点中的计时器开始计时，当数据包到达锚节点i时，锚节点i立刻将此数据包返回，当未知节点k接收到返回的数据包时，其计时器停止工作，此时计时器记录的时间即为此未知节点与对方锚节点间传送数据包所经历的时间，是它们通过同一条路径来回传送数据包所需的时间Δγ(i，k)，其值为单程传送用时的2倍。

（8）精确计算出未知节点与对方锚节点间单程传送数据包所需的时间

h(i，j)为未知节点与对方锚节点间传送路径中经过的所有节点的个数。

（9）利用时间比值与锚节点间距离计算出未知节点与锚节点的距离：

本算法使用的环境是网络处于同一种介质中 （如在空气中或在水中等），虽然信号在不同介质中的传送速度不同，但在同一种介质中可保证节点间的信号传输速度是一致的。在定位精度要求不高的情况下，可以忽略数据包在路径中被途径节点转发所需的延时，则算法中的第三步可省略。

2 DV-Hop定位算法

DV-Hop算法是目前应用最广泛的定位算法之一。其优点是可以利用大量冗余信息提高节点的可靠性，而且传感器节点不需要任何附加硬件支持，能耗较低，受外部环境影响较小，算法简单，易于实现。该算法比较适合锚节点分布均匀、各向同性的密集网络，因为在这种条件下此算法求得的平均每跳距离值与实际距离值比较接近。

DV-Hop算法示意图见图2。假设锚节点L1与L2、L3之间的距离为已知，分别为40m和75m，则锚节点L2的平均每跳距离为：

未知节点A与锚节点L2之间相隔跳数最小，所以会得到从锚节点L2发送来的平均每跳距离值即16.43m，接下来分别计算出未知节点A与锚节点L1、L2以及L3之间的距离，分别为：

图2 DV-Hop算法示意图

经实际测量，未知节点A与锚节点L1、L2以及L3之间的实际距离分别为55、38、45m。可以看出采用DV-Hop定位算法会产生较大的误差。

该算法存在一定缺陷。由于采用锚节点之间的每跳平均距离作为未知节点到锚节点的平均每跳距离，通过平均每跳距离与跳数的乘积得出未知节点与锚节点之间的距离。然而在实际网络中锚节点与未知节点间往往不是直线路径，因此会带来较大的定位误差。

3 利用TROA算法思想对DV-Hop算法的改进

本文对DV-Hop算法的改进主要利用TROA算法中所述的时间比值的思想，利用信号传输的时间比值对标准DV-Hop算法中得出的未知节点到锚节点间的估计距离进行修正，从而提高未知节点的定位精度。

在本改进算法中，每个节点的硬件设置和数据包格式均与TROA算法中的一致。DV-Hop估计距离值误差修正算法具体过程如下：

第一步：锚节点广播消息，未知节点获取距锚节点的最小跳数。锚节点在网络中广播包含自身位置信息的InfoMa数据包，同时广播用于测量时间的Message数据包，此时节点内部的计时器开始计时。未知节点在此过程中统计出距离每个锚节点的最小跳数，如第k个未知节点与第i个锚节点间的最小跳数为 h(i，j)。

第二步：平均每跳距离的估算与广播。锚节点收到其他锚节点广播的消息，获得距离其他所有锚节点的最小跳数和坐标信息，同时立刻发出自己的Message数据包，当此锚节点利用接收到的信息估算出平均每跳距离后，如第i个锚节点计算得出的平均每跳距离为HopSizei，将此距离信息广播至网络中。

第三步：平均每跳距离的修正。未知节点接收到每个锚节点发来的数据包，将每个锚节点的平均每跳距离保存到自身的数据表中，然后继续向邻居节点广播。当遇到id号重复的数据包时将其丢弃。当广播结束后，将每个锚节点的平均每跳距离取平均值，从而得到整个网络的平均每跳距离值sc，将此值向整个网络广播。

第四步：估算锚节点间信息传送所需时间。当某锚节点收到其他锚节点返回的Message()数据包时，其计时器立刻停止计时，此时计时器所记录的时间即是Message()数据包在此锚节点与对方锚节点间路径来回传送所需的时间，如锚节点i与锚节点j间数据传送来回时间记为Δt(i,j)，其单程传送时间 Δτ(i,j)=Δt(i,j)/2，接下来，对此时间值进行求精：

其中，h(i,j)为两个锚节点间的传送路径中经过的所有节点的个数，ω为每个节点转发Message数据包需要的延时。

第五步：计算锚节点间平均每跳的传送时间。每个锚节点通过前一步所得到的与其他锚节点间的传送时间以及第二步获得的与其他锚节点间的最小跳数，计算出自己与其他锚节点的平均每跳传送时间。如锚节点i：

第六步：广播锚节点间平均每跳传送时间值。每个锚节点将计算出的平均每跳传送时间广播至网络中，采用可控泛洪法在网络中广播，每个未知节点仅接收第一次获得的时间值，并将其保存在自身的数据表中。

第七步：计算未知节点与锚节点间传送时间值。当未知节点k收到锚节点i传送来的锚节点间平均每跳传送时间值后，立刻向锚节点i发出Message数据包，同时其内部的计时器开始计时，到达锚节点i后立刻被其转发按原路返回至未知节点k，当未知节点k接收到返回的Message数据包时，其计时器停止工作，此时计时器记录的时间Δε(i，k)即为数据包在未知节点k与锚节点i之间来回传送所需的时间，其单程传送时间 Δδ(i，k)＝Δε(i，k)/2。 接下来，对此时间值进行求精：

第八步：利用时间比值对未知节点与锚节点间的估算距离进行修正。设节点间的距离估计距离为L(i，k)，第三步完成后就可得出：

设节点间的修正距离估计距离为L′(i，k)，他们之间应存在如下关系：

将式（7）代入式（8），化简后可得到：

针对图2，利用式（9）对未知节点到锚节点间的估计距离进行修正，其中锚节点L2计算出得平均每跳的传送时间σL2=20，平均每跳距离值=16.43m，经计算得出修正后的估计距离值分别为:

通过比较可以看出，改进后的DV-Hop算法求出的未知节点与锚节点的估计距离值比标准DVHop算法的精确度有了较大的提高，从而未知节点的定位精度也随之提高。

4 仿真结果

DV-Hop算法与改进后的DV-Hop算法仿真与分析如下：

在50×50的正方形网络区域中，随机部署100个节点，每个节点具有相同的通讯半径R=10m，在锚节点比例分别为 10%、15%、20%、25%、30%、35%、40%、45%、50%的条件下，对标准DV-Hop算法和改进后的DV-Hop算法各仿真100次，取其平均值，分别统计两种算法的定位精度。

其中定位误差为利用定位算法估算出得未知节点的坐标位置和它的实际坐标位置之间的偏差距离与节点通信半径R的比值。

如假设在网络中共有n个未知节点，第i个未知节点的真实坐标为(xi，yi)其定位坐标为(xi',yi')，定义第i个定位节点的定位误差为ei：

仿真结果如图3所示。

图3 DV-Hop算法改进前后锚节点比例与平均定位误差关系的比较

通过图3可以看出，标准DV-Hop算法与改进后DV-Hop算法的平均定位误差都随着锚节点比例的增加而单调递减，但后者的平均定位误差明显小于前者，即改进后的DV-Hop算法的定位精度有了很大的提高。

5 结 语

研究并提出一种新的基于测距的定位算法，即基于节点间信号传输时间比的定位算法 （简称为TROA算法）。另外，利用TROA算法思想对DVHop算法进行改进及仿真对比。仿真结果表明，改进后算法比标准DV-Hop算法的定位精度有明显提高。但由于该方法在能耗方面有较大的增加，所以如何使改进算法在提高定位精度的同时，尽可能地降低节点的能耗，是今后研究的重点内容之一。

[1]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

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

[3]Girod L,Bychovskiy V,Elson J,Estrin D.Locating Tiny Sensors in Time and Space:A Case Study[C]//Werner B,ed.Proc.of the 2002 IEEE Int.Conf.on Computer Design:VLSI in Computersand Processors.Freiburg:IEEE Computer Society,2002：214-219.

[4]Harter A,Hopper A,Steggles P,et al.The Anatomy of a Context-aware Application[C]//Proc.of the 5th Annual ACM/IEEE Int.Conf. on Mobile Computing and Networking.Seattle:ACM Press,1999：59-68.

[5]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(IROS 01).Vo1.3,Maui:IEEE Robotics and Automation Society,2001：1312-1320.

[6]Priyatha N B,Miu A K L,Balakrishnan H,et al.The Cricket CompassforContext=awareMobileApplications[C]//Proceedings of the 7th Annual International Confence on Mobile Computing an Networking.Rome:ACM Press,2001:1-14.

[7]Nirupama Bulusu,John Heidemann,Deborah Estrin.GPS-less Low Cost Out-Door Localization for Very Small Devices[J].IEEE Personal Communications,2000,7(5):28-34.

[8]Nicolescu D,Nath B.DV Based Positioning in Ad Hoc Networks [J].JournalofTelecommunication Systems,2003,22(1/4):267-280.

[9]HE Tian， HUANG Cheng-du， BLUM B M,et al.Range-free Localization Schemes in Large Scale Sensor Networks [C]//Procof the9th AnnualInternational Conference on Mobile Computing and Networking.San Diego:ACM Press,2003：81-95.

[10]SHANG Y,RUML W,ZHANG Y,et al.Localization from Mere Connectivity[C]//Proc of the 4th ACM Int Symp om Mobile Ad Hoc Networking&Computing.Annapolis:ACM Press,2003:201-212.

Abstract：A new range-based localization algorithm(TROA)that based on time ratio of the signal transmission between nodes is stated.It improves DV-Hop algorithm by TROA and simulation comparisonis done.Results of the simulation show that the improved algorithm has a better performance than the standardized DV-Hop algorithm in localization accuracy.

Key words：wireless sensor network;node localization;time ratio;DV-Hop algorithm

The Localization Algorithm for Wireless Sensor Network Based on the Time Ratio of Transmission and Improved Algorithm

LIU Yu1,2
(1.Nanjing University of Aeronautics and Astronautics，Nanjing 210016;2.Maanshan Technical College，Maanshan 243031)

TP212

A

1673-1980（2012）02-0142-05

2011-12-16

安徽省自然科学研究项目（KJ2010B223）

刘俞(1976-)，男，辽宁沈阳人，南京航空航天大学信息科学与技术学院在读硕士研究生,马鞍山职业技术学院讲师，研究方向为嵌入式系统。