WSN中免测距距离估计算法的实现与比较

王利凯，罗 沛

(西安电子科技大学电子工程学院，陕西西安 710071)

WSN中免测距距离估计算法的实现与比较

王利凯，罗 沛

(西安电子科技大学电子工程学院，陕西西安 710071)

在无线传感器网络中，节点定位技术是保证其他应用有效的基本功能，而定位过程可分为距离估计和位置计算两个阶段。文中就距离估计阶段介绍了Sum－Dist、DV－Hop以及Euclidean算法，并在Matlab中仿真实现，最后分析比较其结果表明，各算法在响应的环境中具有良好的表现，和一定的提升空间。

无线传感器网络;距离估计;Sum－Dist;DV－Hop;Euclidean

无线传感器网络(Wireless Sensor Networks，WSN)的出现对于许多应用领域都具有重要意义，因此，其吸引了越来越多的研究者［1］。近年来，微电子、无线通信和计算等技术的进步推动了传感器的快速发展，使得已经在体积和短距离通信方面有优势的传感器又向低成本、低功耗和多功能方面发展并逐渐成熟，并引起国际学术界和工业界的重视，被认为是对21世纪产生巨大影响力的技术之一［2－7］。

无线传感器节点在部署时往往是不可控制的，如在大型无线传感器网络中，节点通常被撒播在广泛的区域之中，而其中大部分节点的位置不能事先确定。然而，无线传感器网络中，节点的位置信息对传感器网络的监测活动尤为重要，没有位置信息的监测消息是毫无意义的［8］。对于一些突发事件，事件监测到之后所关心的一个重要问题就是事件发生的位置信息。如需要告知火灾的发生地点、战场上车辆运动的区域、天然气管道泄漏的具体地点等;又如在环境监测应用中，需要获取采集信息所对应的物理位置。

因此，节点的定位问题已成为无线传感器网络的一个重要研究方向。传感器节点的自身定位是一种通过估计距邻居节点的距离或邻居数目，并利用节点间的信息交换来确定各节点自身位置的机制。无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机制分为:基于测距的(Range－based)定位和距离无关的(Range－free)定位方法。

由于无线传感网络不同于传统网络，其能源有限，节点的通信能力、计算能力相对较弱，而节点数量较多，导致其定位算法必须考虑能源有效性、生命周期、通信延迟、感知精度、可扩展性、鲁棒性等指标。而Range－free算法则仅利用节点间距离的关联关系来计算目标节点位置。定位精度较Range－based算法稍差，但由于其降低了对节点硬件的要求，相对更适于无线传感器网络中的定位。典型算法有:DV－Hop、Sum－Dist、Euclidean等。这些定位算法都需要经过如图1所示的定位过程:

1 免测距距离估计算法

1.1 Sum－Dist算法

Sum－Dist［9］算法是距离估计算法中较简单的方法，其主要思想是将网络泛洪过程中的每跳距离相加，以此作为两个节点间的距离。从锚节点开始，该锚节点会广播一条包含自身标志、位置信息、并将路径长度置为0的消息。每个接收该消息的节点都会将测量距离加到路径长度上，并在泛洪限制许可的情况下，将该消息再次在网络中广播。如果关于同一个锚节点的消息两次或多次广播至未知节点，即仅在当前路径长度小于以前路径长度时，才允许继续广播。这样，最终结果就是每个节点都储存了每个锚节点的位置以及到达该锚节点跳数最少的距离。

图1 节点定位过程

图2是一个简单的Sum－Dist算法模型，节点A到锚节点1只有一条路径，且仅有一跳，距离为5;到锚节点2也只有一条路径，距离为5+6+6=17;到锚节点3有两条路径:A－D－3以及A－D－E－3，需选择跳数最少的路径，即A－D－3，距离为7+7=14。

图2 Sum－Dist算法模型

1.2 DV－Hop算法

DV－Hop［10］定位算法测距过程分为两个阶段:

第一阶段 首先计算待定位节点与锚节点的最小跳数。为获得节点间的跳数，锚节点向所有邻居节点广播一个包含其自身标志、位置信息、跳数被置为0的消息。当未知节点接收到该消息时，将跳数加1，并在泛洪限制许可的情况下，将消息继续向它的邻居节点转发，此过程一直持续下去，直至网络中每个节点都获得每个锚节点的位置信息和相应的跳数值。为了保证能得到最小跳数，未知节点收到消息时，会查看是否已经收到过关于该锚节点的消息，若已经存在，则比较当前跳数是否比之前收到的小，若不是则丢弃该消息，这样就能保证得到的跳数最小跳数。

第二阶段 计算未知节点与锚节点的实际跳距。每个锚节点根据第一阶段中得到的其它锚节点的位置信息和相距跳数，利用式(1)估算平均跳距

DV－Hop算法能够计算出离锚节点很远未知节点的位置。而且其不需要额外信息，但是其误差与其路径的弯曲程度成正比。由于一个未知节点只能通过一条路径得到跳数，所以它需要通过每跳平均距离来计算自身的位置，这样导致计算出位置的误差量大。假设一个DV－Hop模型如图3所示。

图3 DV－Hop算法模型

其中，A1，A2，A3是锚节点;A 是一个未知节点，A1，A2，A3之间的距离已知，分别为30，30和40。A点到A1点为8，跳数为1;根据最小跳数原则，A点到A2，A3的跳数分别为3和2。

首先，锚节点广播包括位置信息、自身标志及开始跳数为0的消息，当消息广播至另一个节点，跳数根据最小跳数的原则变化，最终，每个节点都可得到离锚节点的最小跳数，而锚节点得到与其他锚节点的最小跳数后便可以计算平均跳距。在图3中，A1、A2、A3的平均跳距如下

在计算出平均跳距后，锚节点将在网络中广播该信息，未知节点将平均跳距与最小跳数的乘积作为与锚节点的间距。即，A1、A2、A3将广播 8.6、7.8、7.8 的3个平均跳距。如，A收到A1、A2、A3这3点广播的跳距后，即能计算A到各锚节点的距离AA1=8.6;AA2=7.8×3=23.4;AA3=7.8×2=15.6。

1.3 Euclidean算法

如果网络的拓扑结构不规则，DV－Hop算法的测距误差会较大。针对这些问题，Niculescu和Nath提出了另一种方法，即为Euclidean［11］。该方法依靠锚节点周围节点的几何关系进行计算，若一个节点的两个邻居节点已知各自到锚节点的距离等于彼此之间的距离，这时，即可计算该节点到锚节点的距离了。

如图4是一个Euclidean算法的模型。

图4 Euclidean算法模型

在图4中，A有两个邻节点B、C，已知B、C与锚节点ANC的距离分别是a和b，结合已知的节点间距c、d、e，Euclidean算法得到两个解:r1和r2。为确定哪个解为正解，可采用邻居节点投票的方法:若存在第3个邻居节点D，与B或C相连，且已知它到锚节点的距离。这时，可用D替换C或B，再重新计算A的位置，得到另一对解，正解必然在这两对解中，如此，用简单的选择法便可得到正解。当然，若是有更多的邻居节点参与计算，最终结果会更精确。

2 仿真实现与结果分析

默认环境如下:在100个单位的正方形场景中，有300个节点，通信距离设为15，锚节点比例设为5%，通信误差是通信距离的10%，以下从不同参数进行仿真比较。

图5 不同通信误差下各算法的测距方差

图5是不同通信误差下，DV－Hop、Sum－Dist、Euclidean算法执行距离估计得到的标准方差，图6和图7则分别是在不同的通信距离、锚节点比例下所得到的方差。(1)Sum－Dist是3种方法中通信量最少、计算量最小的测距算法。但在通信误差＜10%时，其测距结果仍是理想的。实际上，有两个完全不同的趋势影响着Sum－Dist的测距精度。其一，如果完全没有通信误差，多条路径上的距离总和大于实际距离，这样就导致估计值过大;其二，由于Sum－Dist算法寻找的是最短路径，所以当存在通信误差时，其所选的路径就会比实际距离小。因为有这两个影响，通信距离的小误差反而提高了Sum－Dist的测距精度。最初，由于路径存在弯曲，导致距离估计值过大，但在最短路径的影响下，通信距离误差的增大反而使距离估计值更小。

当通信距离增大时，更多的节点可以直接通信，这样就可以得到更多的直线路径，并为最短路径提供了更多选择。所以，对于Sum－Dist算法来说，提高测距精度并不一定要增加锚节点比例。

(2)DV－Hop算法是相对较稳定、可预测的算法，由于并不需要实际测量距离，所以它对误差源并不敏感。DV－Hop算法的路径是跳数最少的路径，所以其平均跳距接近通信距离。然而，从锚节点到未知节点路径上的最后一跳往往比通信距离短，这也会导致对锚节点和未知节点间距的少许高估。在短路径的情况下，高估的情况更为明显，正因如此，通信距离越大，锚节点比例越高，跳数越少，而其测距误差反而越大。

(3)Euclidean算法在精确测量锚节点和未知节点距离方面明显有效，但仅在没有通信距离误差和高连通的网络中。而这些条件一旦放松，Euclidean算法的性能会急速下降。Euclidean算法在一般情况下对距离的估计均过低，这是由于在选择时，被迫在两个相隔较远的位置间选择。而大部分情况下，最短距离是不正确的。图4所示，较短距离r2落在锚节点的通信范围内。如果r2是正确距离，那么该未知节点应该能够与锚节点直接通信，避免选择的需要。未知节点距锚节点有多跳距离时也同样存在上述情况。因此，在通信距离误差较小的情况下，相对于高估距离，未知节点更可能会低估其与锚节点的距离。

如图7所示，Euclidean算法对于锚节点比例并不敏感。缩小通信距离的主要影响是Euclidean算法无法广播其锚节点间距。在之前描述Euclidean算法的选择方法中，需要至少3个已经与锚节点之间仅有一跳，且已经得到距离估计值的邻居节点。在低连通的网络中，仅有少量链路连接的两部分往往共享一些锚节点，这也导致在定位阶段只能计算更少的一些节点位置。

3 结束语

文中实现无线传感器网络中3种免测距距离估计算法:Sum－Dist、DV－Hop和 Euclidean，在无线传感器网络中，由于节点的通信距离有限，为能够与更远的节点进行通信，节点间采用多跳的方式进行数据传递，这种方式提高了整个网络的通信能力，也为免测距算法带来了执行的可能性，实验结果表明，免测距算法更适合应用于能源携带有限、通信能力弱、计算能力弱的无线传感器网络网络中。

［1］MAO G，FIDAN B，ANDERSON B.Wireless sensor network localization techniques ［J］.Computer Networks，2007，51(10):2529－2553.

［2］AKYILDIZ I，SU W，SANKARA Y，et al.A survey on sensor networks ［J］.IEEE Communications Magazine，2002，40(8):102－114.

［3］TILAK S，ABU G N B，HEINZELMAN W.A taxonomy of wireless micro － sensor network models［J］.Mobile Computing and Communications Review，2002，6(2):1 －8.

［4］CULLAR D，ESTRIN D，STRVASTAVA M.Overview of sensor network［J］.Computer，2004，37(8):41 －49.

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

［6］李建中，高宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45(1):1 －15.

［7］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［8］ASIS N，LI K.A directionality based location discovery scheme for wireless sensor networks［C］.Shoul:WSNA'02，2002:105－111.

［9］SAVARESE C，LANGENDOEN K，RABAEY J.Robust positioning algorithms for distributed ad－hoc wireless sensor networks［C］.Monterey，CA:USENIX Technical Annual Conference，2002:317 －328.

［10］SAVVIDES A，PARK H，SRIVASTAVA M.The bits and flops of the N－hop multilateration primitive for node localization problems［C］.Atlanta，GA:First ACM International Workshop on Wireless Sensor Networks and Application(WSNA)，2002:112 －121.

［11］NICULESCU D，NATH B.Ad － hoc positioning system(APS)using AoA.［C］.In GlobeCom IEEE Computer and Communications Scotland，2001.

Implementation and Comparison of the Range-free Localization Algorithm in Wireless Networks

WANG Likai，LUO Pei
(School of Electronic Engineering，Xidian University，Xi'an 710071，China)

In the WSN，the node location technology is a basic function to guarantee the effectiveness of other application，and the positioning process can be divided into two stages:distance estimation and position calculation.This paper introduces three algorithms of distance estimation:Sum-Dist，DV-Hop，and Euclidean，and simulates them in Matlab.The result shows that in the response of the environment all the algorithms perform well and can be further improved.

wireless sensor network;distance estimation;sum-dist;DV-Hop;euclidean

TN92

A

1007－7820(2012)06－056－04

2012-01-03

中央高校基本科研业务费专项资金资助项目(K50510020034)

王利凯(1988—)，男，硕士研究生。研究方向:无线传感器网络。罗沛(1987—)，女，硕士研究生。研究方向:计算机网络。