DV-Hop定位算法^{[ 10]}通过洪泛模式,待定节点首先获得与信标节点的最小跳数。然后根据信标节点间的距离和跳数,可以估算出节点间的平均每跳跳距。最后利用未知节点到信标节点的最小跳数乘以平均每跳跳距,未知节点就可以得到与信标节点之间的估计距离。再利用三边测量法或极大似然估计法求解未知节点的坐标。

假设一个简单的网络如图1所示:

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 DV-Hop算法示意图Fig.1 DV-Hop example

图中 的距离和跳数可以计算得到平均每跳跳距:

未知节点 与3个信标节点之间的距离分别为

在洪泛的过程中,信标节点首先广播自身的位置信息,此时在信标节点通信范围内的节点都能够接收到广播信息,接收到信标广播的节点称为该信标节点的邻居节点,本文称之为信邻节点。信邻节点记录到信标节点的最小跳数,忽略来自同一个信标节点的较大跳数。然后将跳数值加1,并转发给其通信范围内的邻居节点。如此反复,信标节点的位置信息以及到信标节点的跳数信息在网络中传播开来。最终每个节点只保留到信标节点的最小跳数。在这个过程中通信范围(即节点的通信半径)是至关重要的因素,因为通信半径决定了哪些节点是上一级节点的邻居节点,也进一步决定了节点间的最小跳数,同样也决定了每跳距离。

为了研究通信半径与定位精度之间的关系,本文做了如下实验。在100 m×100 m的区域内随机布设100个节点,其中10%为信标节点,研究在不同通信半径下DV-Hop定位算法的定位误差。本文采用相对定位误差 :

式中: 为每个节点的绝对定位误差。

通过100次的仿真实验得到的平均结果见表1:

表1

Table 1

表1(Table 1)

表1 DV-Hop算法相对定位误差与通信半径的关系 Table 1 Relative localization errors of DV-Hop algorithm with difference communication ranges 通信半径 R/m 相对定位误差 通信半径 R/m 相对定位误差 20 0.4802 52 0.3355 24 0.4067 56 0.3182 28 0.3695 60 0.3029 32 0.3537 64 0.2883 36 0.3454 68 0.2853 40 0.3343 72 0.2881 44 0.3333 76 0.2966 48 0.3365 80 0.3078

表1 DV-Hop算法相对定位误差与通信半径的关系 Table 1 Relative localization errors of DV-Hop algorithm with difference communication ranges

从表1中可以明显看出,随着通信半径的增大,相对定位误差逐渐减小。除通信半径外,另外一个重要的因素就是信邻节点。从信标节点发出的信息全部通过这些信邻节点传播出去,所以网络中其他节点到信标节点的跳数和跳距都与这些节点有关。

根据前文的分析,通信半径和信邻节点是DV-Hop定位算法中重要的两个因素。因此,如果能够得到信邻节点与信标节点相对更准确的距离,无疑能够提高所有未知节点的定位精度。本文考虑对每个信标节点引入两个通信半径,一个是与其他未知节点相同的全网通信半径 R,另一个是信标节点所独有的通信半径0.5 R。当信标节点以通信半径 R广播信息时,所有能够收到广播的邻居节点构成信邻节点组1;当信标节点以通信半径0.5 R进行广播时,收到广播的邻居节点构成信邻节点组2。显然,信邻节点组1包含信邻节点组2的所有节点。在广播过程中,信邻节点组2中的所有节点保留的与信标节点的最小跳数是0.5,信邻节点组1中除去信邻节点组2的其他节点保留与信标节点的最小跳数为1。在此基础上,信邻节点继续以通信半径 R洪泛的方式转发信标节点传来的信息。洪泛结束后,每个节点都保留到所有信标节点的最小跳数。其中,最短传播路径通过信邻节点组2的节点中保留的最小跳数不再是一个整数,而是一个整数加上0.5。显然,与只用一个通信半径 R的情况相比,这些节点的绝对定位误差就减小了0.5 R,从而使这些节点的定位精度有了明显提高。此外,信标节点采用多一个通信半径0.5 R也能够使跳距的计算更接近真实值,同样能达到提高定位精度的目的。

同样以图1的网络为例,信标节点 计算得到平均每跳跳距为

由式(4)计算得到的平均每跳跳距比式(1)的结果更接近真实值。未知节点 的跳距为1.5,也比原来的跳距2更接近真实值。

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 双通信半径DV-Hop算法示意图Fig.2 DV-Hop with two communication ranges example

如果在100 m×100 m的区域内随机布设100个节点,其中10%为信标节点,当通信半径分别为20 m和10 m时,信标节点与信邻节点拓扑关系图如图3所示:

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 信标节点与信邻节点拓扑关系图Fig.3 Topology of beacon and beacon’s neighbor

从图3(a)与图3(b)的对比来看,采用0.5倍通信半径后,信邻节点的数量约占原信邻节点数量的三分之一,这对整个网络中未知节点定位精度会有较大程度的影响,而且随着网络连通度的增加,这个比例还会增加,影响程度也会随之增加。

(1)未知节点获取到每个信标节点的最小跳数。

网络启动工作时,信标节点会主动广播自身位置信息的分组,信息中包括信标节点的坐标和初始化的跳数字段。另外,每个节点都会预留出足够的存储空间,用于保存与每个信标节点的最小跳数。网络初始化阶段,这些存储空间全部置0。当某个信标节点的信息首次传送到一个节点时,该节点将直接存储接收到的跳数字段;当这个信标节点的信息并非首次传送到该节点时,该节点比较本次接收的跳数字段与之前存储的与该信标的跳数系数后,存储二者较小的数值作为最小跳数。存储完成后,将最小跳数加1后赋值给传播信息的跳数字段,转发给邻居节点。这样,最后网络中的所有节点都能记录下到每一个信标节点的最小跳数。

本算法中,信标节点有两个通信半径,一个为的作用是确保第一次广播的信息被信邻节点接收到并完成更新最小跳数的操作。

每一次洪泛式传播节点都会消耗较大的通信能量。由于无线传感器节点能量受限,所以本算法只是第二次广播采用洪泛式传播,而第一次广播仅仅是信标节点发送信息给信邻节点,信邻节点并不继续广播。信标节点通常是特殊节点,存储的能量会远远大于其他节点,而多一次广播也不会增加很多的能量开销。

(2)计算未知节点与信标节点之间的距离。

每个信标节点依据存储的其他信标节点的坐标以及与它们之间的最小跳数估算平均每跳距离为

式中: 之间的最小跳数。

由于增加了以0.5 R为通信半径的第一次广播,这里的最小跳数可能是一个整数或者一个整数加上0.5。

信标节点以通信半径 R将平均每跳距离以洪泛的方式广播出去,每个未知节点仅记录第一次接收到的平均每跳距离,并转发给邻居节点。洪泛结束后,未知节点根据接收到的平均每跳距离以及先前记录得到各个信标节点的最小跳数计算到每个信标节点的跳距。

(3)每个未知节点利用极大似然法计算自身位置。