基于邻节点空间顺序序列优化的DV_Hop定位算法
计 算 机 系 统 应 用 2010 年 第19卷 第 2 期
基于邻节点空间顺序序列优化的DV-Hop
定位算法
①
钟进发 许 力 叶阿勇 (福建师范大学 网络安全与密码技术重点实验室 福建 福州 350007)
摘 要： 针对典型的DV-Hop定位算法中未知节点在计算与信标节点间距离时估算的不足，在DV-Hop算法
的基础上提出了一种优化定位精度的算法。考虑并分析了未知节点与信标节点的路径中相邻三个节点的通信边组成的夹角对计算距离的影响，提出了一种基于“邻节点空间顺序”序列标号法计算夹角的方案，实验仿真验证了该优化定位算法的有效性和可行性。
关键词： 无线传感器网络；节点定位；DV-Hop；邻节点空间顺序序列
An Improved DV-Hop Localization Algorithm Based on the Ordered Neighboring Nodes in Space
ZHONG Jin-Fa, XU Li, YE A-Yong
(Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, China) Abstract: The precision of DV-Hop localization algorithm is not good enough when it is used to compute the distance
value between unknown nodes and beacon nodes. To overcome its disadvantage, a precision improved algorithm based on DV-Hop is proposed. The three neighboring nodes in the route of the unknown node to the beacon node are analyzed, and an improced DV-Hop Location Algorithm based on the Ordered Neighboring Nodes in Space is proposed. Simulation proves that the improved algorithm is effective and feasible.
Keywords: wireless sensor networks; localization; DV-hop; ordered neighboring nodes in space
1 引言
对大多数的无线传感器网络应用而言，不知道传感
等。在精度允许的情况下，无需测距的定位方法，更适合低成本、低功耗的无线传感器网络。DV-Hop算法是目前研究和应用最为广泛的无需测距定位算法之一，但其在计算未知节点和信标节点间的距离时估算较粗糙，使其定位精度受到较大影响。本文针对DV-Hop算法的这一不足，考虑未知节点到信标节点路径中相邻三个节点组成的夹角对求解未知节点到信标节点距离的影响[8]，提出了一种优化定位精度的方案。
器节点位置而感知的数据是没有意义的。现有无线传感器网络节点自身定位方法主要有：基于测距的定位方法和无需测距的定位方法。基于测距的定位方法通过节点配备额外测量设备测量节点间点到点的距离或角度信息，利用三边测量或最大似然估计定位法来计算出未知节点的位置信息，常用的测距方法有TOA[1], TDOA[2], RSSI[3]和AOA[4]等；无需测距的定位方法则仅根据网络的连通性和信标节点的位置信息实现相对精确的定位功能，典型的方法有质心算法、DV-Hop[5]，DV- distance[5]，凸规划算法[6]、APIT和MDS- MAP算法[7]
2 DV-Hop定位算法
DV-Hop算法由以下3个阶段组成：
① 网络中的节点获取自身与每个信标节点的最
① 基金项目:福建省科技计划(2008F5020);福建省教育厅重点项目(JA07030);福建省自然科学基金(2008J0014)
收稿时间:2009-06-08
62 研究开发 Research and Development
2010 年 第19卷 第 2 期 计 算 机 系 统 应 用
小跳数。
这一阶段利用典型的距离矢量交换协议来获取网络中的所有节点到每个信标节点的最小跳数及传播过程中经过的路径系列。
② 各信标节点计算平均单跳距离校正值。 每个信标节点根据第①阶段中记录的其他信标节点的位置信息和相距跳数,利用 (1) 式估算平均单跳距离校正值。其中,( xi,yi ) , (xj,yj) 是信标节点i, j的坐标, hj是信标节点i与j( j≠ i) 之间的跳数。然后,信标节点将计算的校正值广播至网络中。未知节点接收到校正值后, 根据记录的跳数, 计算到每个信标节点的距离。
HopSizei=
间的距离是通过采用该节点收到的最近信标节点的校正值和未知节点与信标节点间的最小跳数的乘积来表示的。这样粗糙的估算会使DV-Hop算法仅在各向同性的密集网络中,校正值才能较合理地估算。因为，在实际网络拓扑中，未知节点与信标节点间的路径往往不是直线的。
图2 DV-Hop定位 图3 余弦定理解三
i≠j
误差示图 角形第三边
(1)
如图2所示，设节点L为信标节点，A、B、C为未知节点，设信标节点L的平均单跳校正值为10m，未知节点C从L处获得校正值后应用DV-Hop算法计算到信标节点L的距离应该是3×10m。然而，节点C和节点L间的路径并非直线，使得这一估算的距离远大于它们间的实际距离。 3.2 DV-Hop算法的优化方案
在图3中，若已知AB、BC的长度分别为|AB|、|BC|，又知道它们间的夹角∠ABC，则AC的精确长度为：
|AC| 位置。
h
i≠j
j
③ 利用三边测量法或极大似然估计法计算自身未知节点利用第②阶段中记录的3个或更多信标节点的距离,利用三边测量法或极大似然估计法计算自身坐标。
图1 DV-hop定位算法示图
如图1
所示,已知信标节点L2与L1, 和跳数。
L2
L3之间的距离
(2)
图4 局部网络拓扑图
同理，在无线传感器网络中，如图4所示，节点L为信标节点，节点A、B、C均为未知节点，且A、C均为B的一跳邻节点。在平面网络拓扑图中，由于DV-Hop算法利用典型的距离矢量交换协议，且未知节点只接收到每个信标节点的最小跳数，这就使信标L到B的路径中经过的节点B的邻节点满足在空间位
Research and Development 研究开发 63
计
算得到校正值 (40+75)/
D1
(2+5)=16.42,假设未知节点A从获得校正值,则它与3个信标节点之间的距离分别为使用三边测量法确定。
=3×16.42,
D2=2×16.42, D3=3×16.42, 节点A的位置便可以
3 基于邻节点空间顺序序列优化的DV-Hop定位算法
3.1 DV-Hop算法的误差分析
在DV-Hop算法中，计算未知节点与信标节点之
计 算 机 系 统 应 用 2010 年 第19卷 第 2 期
置上与L有最短的欧氏距离，图4中B的邻节点A满 足此条件。假设信标节点L到未知节点C的路径中经过节点A和B，在节点L到C的链路中，称节点A为B的前驱节点，节点B为C的前驱节点。若节点B的位置信息已经通过计算获得，即|LB|的距离已经获得，又因为节点B是C的一跳邻节点，所以BC的距离|BC|以平均跳距估算。若此时再获取角∠LBC的值，便可以利用（2）式计算|LC|。虽然无法直接计算或获得角∠LBC的值，但我们可以利用节点C与其前驱节点B的边BC及B与其邻节点A组成的边AB组成的角∠ABC近似代替角∠LBC，而角∠ABC可以利用节点B的邻节点个数及其邻节点序列(如顺时针或逆时针序列)来间接估算。
在无线传感器网络中，若两个节点互为邻节点且它们的邻居列表里相同的元素越多，则在一定程度上反映这两个节点在位置上应该是越靠近。节点B的邻节点个数是容易获得的，而节点B的邻节点序列我们采用“邻节点空间顺序”标号法来实现。平面网络节点N实现“邻节点空间顺序”标号法有以下四个步骤组成：
步骤1: N节点创建邻节点集Sneighbor及创建各邻节点发过来的邻居列表中除去不在Sneighbor中的节点集
SLn−i。
中的元素都已经加入List，Sneighbor仍不为空，则该元素的SLn−i中一定存在两个节点互为邻节点且它们在空间顺序上是位于该元素的两端，所以把该元素插入这对互为邻节点元素在List中的位置，并在Sneighbor删除该元素。
步骤4: 从List的一端到另一端的元素系列进行顺序标号。
当List的链表尾(或链表头)元素节点对应的SLn−i表中未加入List的元素里有两个以上的元素分别对应的
SLn−j里的元素与List的链表尾(或链表头)元素节点对应
的SLn−i的相同元素个数相等时，此算法也可能存在局部排序误差。
如图4所示，节点A和节点C之间的节点数目可以间接反映出角∠ABC的大小。假设节点B有n个邻节点，在B的所有邻节点中节点A和B的空间顺序标
∠ ABC号分别是i和j，则： ≈ × 2 π (3)
|j−i|
n
节点随机放置的网络中，节点的网络密度越大即每个节点的邻节点数越多，在其周围节点的分布均匀的概率也就越大，即角∠ABC也就越逼近n× 2 π 的值。
3.3 优化后算法的定位过程
优化后的定位过程分以下三个阶段：
① 网络中的节点获取自身与信标节点的最小跳数及每个节点自己的邻居列表。
信标节点向其邻节点广播自身位置信息及路径序列。其中自身位置信息包括跳数字段,初始化为0,路径序列包括自身节点ID。接收节点记录到每个信标节点的最小跳数,忽略来自同一个信标节点的较大跳数的分组,然后将跳数加1,将自身节点ID加入到相应的路径序列中,转发给邻节点。每个节点在收集到自己的所有邻节点ID后创建自己的邻居列表Sneighbor。
② 信标节点计算平均单跳距离校正值。 每个信标节点根据第①阶段中记录的其他信标节点的位置信息和相距跳数,利用式(1)估算校正值。然后,信标节点将计算的校正值广播至网络中, 未知节点仅记录接收到的第一个校正值,并转发给其邻居节点。
③ 计算未知节点与信标节点间的距离并计算自身位置。
1) 节点从步骤①中得到的所有邻居列表信息实现“邻节点空间顺序”标号法对邻节点进行标号；
|j−i|
步骤2: 取出Sneighbor中的第一个元素加入双向链表
List中，并在Sneighbor中删除加入了List的元素。
步骤 3:
① 若Sneighbor已经为空则完成步骤3，进入步骤4，否则进入②；
② 若List的链表尾节点i对应的SLn−i表中还有未加入List的元素，则进行加入List链表尾操作，否则进入③；重复②；
③ 若List的链表头节点j对应的SLn−j表中还有未加入List的元素，则进行加入List链表头操作，否则进入④；重复③；
④ 进行插入操作，返回到①。
其中加入List链表尾(头)操作为：在List的链表尾(头)元素节点对应的SLn−i表中未加入List的元素里选取一个元素，要求该元素节点对应的SLn−j里的元素与List的链表尾(头)元素节点对应的SLn−i的相同元素个数最多，并把其加入List链表尾(头)，并在Sneighbor中删除该元素；插入操作为：若List链表尾和链表头元素对应的SLn−i 64 研究开发 Research and Development
2010 年 第19卷 第 2 期 计 算 机 系 统 应 用
2) 对于未知节点，如图4所示的节点C，在节点L到节点C的路径中C的前驱节点B的距离已经通过步骤③计算获得，设为D1；节点C到B的距离采用该节点获得的最近信标节点的平均每跳跳距表示，设为
节点L到C的路径中节点A是B的前驱节点，Dcorrection；
并通过节点B的邻节点个数n和B的邻节点空间顺序标号(设节点A、C在B的邻节点空间顺序标号为i和j)，通过(3)式估算出角∠ABC的值；则通过(4)式估算出节点L到C的距离DLC。
(4) DLC
3) 利用三边测量法或极大似然估计法计算自身 位置。
图5 网络节点密度对误差的影响
图6 信标节点比例对误差的影响
4 仿真实验结果及分析
为了验证本文提出的优化算法的有效性和可用性，将该算法与DV-Hop定位算法进行了在定位误差上的比较，每个实验场景都执行10次并对得到的结果取平均值。在本实验中，在固定大小的实验平面区域内通过改变节点的数量来改变平均网络节点密度；定位误差定义为未知节点经定位算法的估算坐标位置与其实际坐标位置间的距离与节点的通信半径值的比值，假设未知节点经定位算法的估算坐标位置为(xe,ye)，其实际坐标位置为(xi,yi)，节点的通信半径值
知节点的定位误差
为 I
。
图5是在500×500的平面区域内，网络节点
5 结语
本文针对典型的DV-Hop定位算法基础上提出了一种优化定位精度的算法，并设计了一种 “邻节点空间顺序标号法”计算夹角的方案。在实验仿真中进一步验证了该优化定位算法的有效性和可行性，特别是信标比例较低的情况下，从未知节点定位的精度角度看，优化后的算法比典型的DV-Hop算法优势更加明显。
然而，节点在获取邻节点的邻居列表过程中在一定程度上增加了通信代价，而且有可能产生一定的误差；节点为了计算更加精确的距离过程中增加了一部分计算量。因此，如何使误差最小化并最大化地减小计算、通信量方面是进一步要做的工作。
Research and Development 研究开发 65
随机放置，节点的通信半径为=100，信标节点的比例占10%的条件下不同平均网络节点密度的实验结果。优化后的定位算法在不同平均网络节点密度的情况下定位精度比典型的DV-Hop定位算法均有不同程度的提高，在一定程度上验证了本文提出的优化策略的有效性。图6是在500×500的平面区域内，200个网络节点随机放置，节点的通信半径为=100，通过改变信标节点的个数来改变信标节点比例的实验结果。从实验数据可以看出在信标节点比例小的情况下，优化后的定位算法在精度上的优势更为明显。
计 算 机 系 统 应 用 2010 年 第19卷 第 2 期
参考文献
1 Haretr A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. Proc. of the 5th Annual ACM/IEEE Int’l Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999,59－68.
2 Girod L, Estrin D. Robust range estimation using acoustic and multimodal sensing. Proc. of the IEEE/ RSJ Int’l Conf. on Intelligent Robots and Systems (IROS 01). Vol.3, Maui: IEEE Robotics and Auto- mation Society, 2001.1312－1320.
3 Girod L, Bychovskiy V, Elson J, Estrin D. Locating tiny sensors in time and space: A case study. Werner B, ed. Proc. of the 2002 IEEE Int’l Conf. on Computer Design: VLSI in Computers and Processors. Freiburg: IEEE Computer Society, 2002.214－219.
4 Priyantha NB, Miu AKL, Balakrishnan H, Teller S. The cricket compass for context-aware mobile appli- (上接第85页)
反锐化掩模法的ROI提取计算时间更短，更易于计算机编程实现。
(a) 原始图像 (b) ROI提取结果
图3 ROI提取结果
cations. Proc. of the 7th Annual Int’l Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 1－14.
5 Niculescu D, Nath B. DV based positioning in ad hoc networks. Journal of Telecommunication Systems, 2003:22(1/4):267－280.
6 Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. Proc. of the IEEE INFOCOM 2001. Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001,1655－1663.
7 Shang Y, Ruml W, Zhang Y, Fromherz MPJ. Localization from mere connectivity. Proc. of the 4th ACM Int’l Symp. on Mobile Ad Hoc Networking & Computing. Annapolis: ACM Press, 2003.201－212. 8 张晓龙,解慧英,赵小建,等.无线传感器网络中一种改进的DV-Hop定位算法.计算机应用, 2007,11:2672－2674. 行ROI提取，为后期钙化点的智能检测提供了良好的前提条件，有助于提高乳腺疾病诊断的准确率。
参考文献
1 Yuan X, Shi PC. Physics Based Contrast Marking and Inpainting Based Local Texture Comparison for Clustered Micro-calcification Detection. MIC-CAI(2), 2004,32(4):847－855.
2 Li LY, Chen WN. A robust and completely deter- ministic method for gray level picture thresholding. 模式识别和人工智能, 1993,6(3):235－241.
3 博斯.吴镇扬,周琳译.数字信号与图像处理.北京高等教育出版社, 2006,7:665－670.
4 李树楠,万柏坤,马振鹤,王瑞平.基于小波变换的乳腺X线影像微钙化点感兴趣区域提取新技术.生物医学工程学杂志, 2005,22(2):360－362.
4 结语
本文重点研究了乳腺X射线影像中感兴趣区域的提取。在对图像进行基本的背景分割后，通过区域扩张算法进行乳腺区域的提取，具有较高的准确率，从而降低了ROI分析的计算量，为后续的ROI分析提供了良好的前提条件。最后采用改进的反锐化掩模法进
66 研究开发 Research and Development