1 引言
随着微机电系统(micro-electro-mechanism system,简称MEMS)、无线通信和数字电子技术的进步孕育了无线传感器网络(wireless sensor network,简称WSN)。从军事应用、目标追踪、环境检测到空间探索,WSN的未来应用将超出我们的想象力。但是对于大多数的WSN应用,不知道传感器位置而感知的数据是没有意义的[1]。传感器节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”,从而实现对外部目标的定位和追踪[2]。而人工部署和为所有网络节点安装GPS接收器都会受到成本、功耗、扩展性等问题的限制,甚至在某些场合可能根本无法实现,如在室内由于受到建筑物的阻挡其定位性能并不理想,因此必须采用一定的机制与算法实现WSN的自身定位。
2 DV-HOP定位算法的研究
2.1 DV-HOP定位算法的基本原理
DV-Hop算法是由美国Rutgers University的Dragos Niculescu等人利用距离矢量路由和GPS定位原理提出来的一种无需测距的定位算法[3]。因传感器节点通信距离有限,往往通过多跳路由的方式传送数据,节点本身仅与其邻接节点交换信息,DV-Hop算法就是利用了这一特性。其基本原理是将未知节点到锚节点之间的距离用网络平均每跳距离和两者之间的最短跳数乘积表示。虽然待定位节点通信范围内的参考节点数量不多,但是采用上述方法可以获得通信范围外多个参考节点的估计距离,利用大量的冗余信息实现节点定位。该算法首先使用距离矢量交换协议,使网络中所有节点获得距锚节点的跳数,然后锚节点计算网络平均每跳距离值,并将其广播至网络中。当未知节点接收到该值后,则根据跳数计算与锚节点的距离。当未知节点获得与3个或3个以上锚节点的距离时,则执行三(多)边测量或极大似然估计法[4]。
虽然DV-Hop算法相对基于测距的定位技术精度较低,但不需要节点具备测距能力,无需额外硬件、能耗较低、受环境影响较小,算法简单,易于实现,对于各向同性的密集网络,可以得到合理的平均每跳距离,定位精度等方面能满足大多数应用的要求,在硬件尺寸和功耗上更适合大规模低能耗的WSN,是目前备受关注的定位机制,许多定位系统都采用了该算法来实现[5]。
2.2 影响DV-HOP算法定位性能的因素
DV-Hop属于无须测距定位算法,定位精度在很大程度上受到网络拓扑结构的制约[6],其误差主要来源于两方面:
(1) 由于节点是随机部署的,未知节点与信标节点之间的跳段距离通常不是二者之间的直线距离。在各向同性的密集网络中,校正值才能合理地估算平均每跳距离,这是基于多跳的定位算法普遍存在的问题,采用DV-Hop算法过大估计了跳段的距离;
(2) 未知节点计算与信标节点之间的跳数,结果都是整数,这大约增加了0.5个平均跳数的误差。通过DV-Hop算法中节点间距离度量的分析,可以发现利用这些距离没有反映出信标节点对节点位置的影响力的大小,影响了定位精度。
因此为了改善在稀疏网络中DV-Hop算法的定位精度,同时提高定位节点的覆盖率,文章对传统DV-Hop算法进行了改进,提出了一种新的改进型算法,既对平均每跳距离的计算进行了改进,同时采用基于角度阈值的锚节点选择策略,有选择性的选取锚节点参与三边定位过程,然后通过引入角度加权因子对其定位结果进行修正。
3 改进型DV-HOP定位算法
3.1 改进算法的基本思路
通过研究发现:两个锚节点间,通过较短传输线路的中央点与两端锚节点的夹角接近180°;若传输发生绕路,则该夹角相对小一些。一般而言,越大的夹角表明经过该点的传输路越短;越小的夹角表明传输所绕的路越远,即表明可能导致相对大的跳距背离。
如图1所示,锚节点与之间有两条线路和(图中实线和虚线),其中和为线路和的中央节点,和与两端锚节点的夹角分别为和。>表明路线相对更接近实际距离。基于这个特性,考虑在估计不同传输路径中的平均跳距时,根据该夹角值和传输跳数进行相应调整以修正估计值,可减少定位距离误差,进而获得更精确的节点位置数据。一般而言,该夹角越趋近180°,该传输路径与实际距离越接近。
3.2 改进的算法具体步骤
第一步:计算未知节点与每个锚节点的最小跳数
在DV-Hop中,每个锚节点向邻居节点广播自身位置信息的分组,其中跳数字段初始化为0。接收节点记录具有到每个锚节点的最小跳数、忽略来自同一个锚节点的较大跳数的分组。将跳数加1,并转发给邻居节点。通过这个方法,网络中的所有节点能够记录到每个锚节点的最小跳数。
第二步:计算未知节点和锚节点的实际跳段距离(引入基于角度的加权因子Kij)
(1) 找到连接各锚节点间跳数最少的传输路径,获取其中央的节点与两端锚节点的夹角。记录与每个锚节点的值,从大到小排列。引入加权因子,的值与成正比,因为越大,表示两锚节点间距离越接近实际距离。
(2) 每个锚节点根据第1阶段中记录的其他锚节点的位置信息和相距跳数以及2.1的值,进行加权平均,求出每个锚节点的每跳平均距离。
(3) 锚节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中,未知节点可利用与锚节点的每跳平均距离和记录的跳数,计算到每个锚节点的跳段距离。
第三步:利用三边测量法计算自身位置,对参与三边算法的节点进行选择,避免三边算法的缺点,同时减小计算量;
(1) 根据具体环境设置角度阈值X(0<X<1),注意X应该尽可能接近1;
(2) 从锚节点中选取与未知节点跳数最小的3个节点,,构成定位ΔABC;
(3) 根据余弦定理计算ΔABC的3个内角的余弦绝对值;
(4) 比较ΔABC的3个内角的余弦绝对值与阈值X的大小,只要有1个角度的余弦绝对值大于阈值X,则重新选择锚节点;若3个角的余弦绝对值都小于阈值X,则可根据三边定位算法,估计未知节点的实际位置坐标;
4 算法仿真
通过MATLAB对传统DV-HOP算法与新的改进型DV-HOP算法进行了定位仿真。仿真的软件环境为:windowsxp SP2 MATLAB7.0.4,假设在一个10*10的正方形区域随机产生210个节点,锚节点个数为90。仿真结果如图所示:
其中:黑色三角形表示锚节点位置,红色圆圈表示未知节点位置,蓝色圆圈表示利用传统DV-HOP算法定位的节点位置。
其中黑色三角形表示锚节点位置,红色圆圈表示未知节点位置,蓝色花形表示利用新的改进型的DV-HOP算法定位的节点位置。
通过仿真可以看出新算法在定位性能上有了明显改善,尤其对于传统DV-HOP定位结果误差较大的节点更是有了较大改善。随着总节点数量的增多,可定位未知节点比例也随之增多,在节点密集型网络中的可定
但WSN节点是随机分布的,用于定位的锚节点位置也是随机的。由三边定位算法可知,当3个点共线时,无法对其进行准确定位。同时由于在传统的DV-Hop算法中 (1)得出的值本身就有一定误差,因此当用于定位的3个锚节点近似成直线时,会给定位结果带来很大误差。如图2所示,由于锚节点A、B、C近似成直线,对于未知节点D的估计就出现了严重错误。若选择离未知节点较远的锚节点E进行定位,由于锚节点B、C、E的位置相对较分散,因此对节点D的定位效果较好。
位节点比例比传统方法有很大提高。无线传感器网络的规模很大,单个节点的资源十分有限,基于夹角修正的节点定位算法,有效提高了节点的定位精度,用于估计节点位置的平均跳距得到了很好的修正,且不增加额外开销,不受节点分布的影响,能够降低无线传感器网络的造价,比较实用,能满足大多数无线传感器网络的应用要求,是无线传感器网络节点定位的一种可选方案。
5 结束语
定位成本和定位的精确度是衡量定位算法好坏的两个重要标准。本文介绍了一种新的定位算法,这种定位算法在传统的DV-HOP算法上对平均每跳距离的计算进行了改进,同时有选择性的选取锚节点参与三边定位过程,通过引入角度加权因子,进行仿真实验。从仿真实验结果可以清楚地看出,无线传感器网络中节点定位的精确度得到了充分地改善。
参考文献:
[1] 孙利民,李建中等.无线传感器网络[M].北京,清华大学出版社,2005.
[2] 马祖长,孙怡宁等.无线传感器综述[J].通信学报,2004,25(4):114-124.
[3] 王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.
[4] 张文祥,马银花,郭继坤.无线传感器网络路由算法的研究[J].计算机测量与控制,2009,17(3): 617-619.
[5] 杨磊,张政保等.基于角度阈值的改进型DV-HOP定位算法[J].计算机工程,2008,34(20):96-100.
[6] 林金朝,李小铃等.无线传感器网络DV-hop算法改进与性能[J].重庆大学学报 2010,33(2):127-132.