基于改进距离向量算法的无线传感网定位研究

赵战民，岳永哲

(1.河北地质大学 信息工程学院,石家庄 050000;2.河北科技大学 信息科学与工程学院,石家庄 050000)

0 引 言

无线传感器网络(wireless sensor network,WSN)通常由大量的微型传感器节点组成，具备计算，通信和有限的存储能力[1]。传感器节点的典型任务是从环境中采集大量的感知数据，并将其传递给基站(中心节点)进行进一步地处理。对于大多数无线传感器网络算法而言，确定节点的物理位置，即事件发生之地，是一个至关重要的性能，同时也包括数据包路由选择，传感覆盖和安全问题。传感器的位置信息通常嵌入在传输信号中，由传感器节点生成，没有传感器的位置信息，无线传感器网络便不能正常工作。因此，定位问题在无线传感器网络的研究中是一个重大的挑战[2-4]。

许多定位方案都假设，通过手动放置或使用全球定位系统(global positioing system,GPS)，使得一小部分的传感器(表示为锚节点)知道自己的绝对位置。然而，这种使用GPS的方法并不适合无线传感器网络，因为GPS系统提供的解决方案昂贵，而且能耗又高[5]。其他节点，称为未知节点，并不知道它们自己的位置。锚节点可以帮助未知节点定位它们自己，而且它们的位置可以作为参考，用于估计传感器报告的位置。使用参考节点的定位方案一般可以分为2种类型:基于测距的方案和无需测距的方案[6]。

基于测距的定位方法，通过测量接收信号强度指示(received signal strength indicator,RSSI)，信号的到达时间(time of arrival,ToA)和到达角度(angle of arrival,AoA)，首先,需要测量相邻传感器之间的精确距离或角度信息[7]。然后，将这些测量数据应用于各种方法中，比如三角测量或三边测量，以此估计节点在网络中的位置。这些算法相对准确，但是需要额外的硬件，在大规模的无线传感器网络中，实现定位解决方案需要的代价太高(昂贵，能耗又高)。相反，无需测距的算法不使用任何的距离测量，而是应用其他方法，比如使用跳跃数作为估计节点之间的距离的一个数据。事实上，这些方法利用传感器之间的通信来定位未知节点。根据无线传感器网络设备的硬件限制，研究者常常寻求具有成本效益的解决方案来解决传感器网络中的定位问题。一般来说，为传感器网络设计一种好的定位算法，涉及到的相关问题都包括节点故障容忍、可伸缩性、发射成本、硬件限制以及能量损耗。因此，本文主要研究分布式无需测距的算法。

典型的无需测距定位方法包括距离向量-跳段(DV-Hop)[8]，三角测量中的近似点等。其中，DV-Hop是最著名的分布式无需测距算法之一，因为它很简单，成本效益好，稳定性高。DV-Hop算法令人感兴趣的一个优点是，它可以处理正常节点相邻的锚节点不到3个的情况。距离向量-跳段的核心理念是通过计算每个锚节点每跳的平均距离和计数未知节点与锚节点之间的跳段来表示未知节点和锚节点之间的距离。然而，一跳的粗略平均估算距离使得DV-Hop算法的定位精度有限。因此，曾有许多文章尝试改善DV-Hop算法。在一些文献提出考虑前者平均一跳的距离[9]。出于同样的原因，一些论文使用加权的方法来提高定位的准确性[10]。有些文献提出修改未知节点的位置估算，对DV-Hop算法进行了改进[11-12]。还有一些研究人员分析和研究了锚节点的布置和特性对节点定位精确度产生的影响[13]。

在本文中，侧重于静态网络，基于DV-Hop算法和接收信号强度指示测量，提出了一种改进的无线传感器网络定位算法。该方法的主要思想是结合基于接收信号强度指示和无需测距的方法，来估算校正一跳距离，并且应用莱文贝格-马奈特(Levenberg-Marquardt,LM)算法来计算节点的位置。仿真结果表明,该算法比传统的DV-Hop算法具备的性能更佳。

1 无需测距定位算法原理

DV-Hop算法作为最出名的分布式无需测距的定位算法之一，已经广泛应用于大型无线传感器网络节点定位[5]。传统的DV-Hop算法由3个步骤组成。

步骤1每个锚节点i通过网络传送一个信标数据包，包含自身ID，坐标和初始化为0的跳段值。在第一次会话中，每个接收节点(锚节点或未知节点)都会在表格中记录锚节点i的位置，并且将hopi初始化为跳段的值。只有在收到相同的消息中包含一个比hopi更低的跳跃数值时，对应着每个锚节点的hopi才会被更新。这意味着，在网络中将跳跃数值较低的信标转发给一个特定的锚节点，跳段的值增加了1；否则在传送期间将被忽略。在这一步的最后，网络中所有的节点都获得了坐标和到每个锚节点节点的最小跳段。

步骤2在锚节点i获得了到其他锚节点的最小跳段之后，从它的角度来计算每跳的平均距离，即

(1)

(1)式中：HSi表示未知节点j从最近的锚节点i获得的平均跳段；M表示锚节点的数量；hopij表示锚节点i和锚节点j之间的跳段值；(xi，yi)和(xj，yj) 分别表示锚节点i和锚节点j的坐标。

一旦计算出HS，锚节点i将被传送到整个网络中。未知节点收到来自所有锚节点的HS，并且选择最近锚节点的HS作为平均的跳段距离。最后，使用公式(2)，每个未知节点j都要估算距离dij，即它本身与每个锚节点i之间的距离。

dij=HSi×hopij

(2)

(2)式中，hopij表示未知节点j和锚节点i之间的最小跳段。

步骤3未知节点通过使用三边测量或多边测量方法的最大似然估计，根据锚节点的坐标和距离信息来计算自己的位置(坐标)。假设有M个锚节点用来估计未知节点s的位置，那么s的位置为

(3)

(3)式中：(xs，ys)表示未知节点s的坐标；(xi，yj)表示第i个锚节点已知的位置；dsi表示未知节点s和锚节点i之间的距离。由于平方项，公式(3)提出的公式是非线性的。为了让这个方程组线性，可以改写为aX=ba的形式，a,b和X分别由公式(4)—(6)表示为

(4)

(5)

(6)

根据最小平方法，节点s的位置可以运用公式(7)进行估计。

(7)

2 提出的改进DV-Hop方法

2.1 计算节点之间的距离

正如第1节内容所述，基本DV-Hop算法的主要缺点是未知节点和锚节点之间的估计距离影响了算法的准确性。当未知节点和锚节点之间的跳段数量增加时或网络不规则增加时，距离估计造成定位误差高。为了克服这个问题，区别于DV-Hop算法中锚节点要计算平均的跳段大小，我们采用2种不同的方法来估计单独一次跳的平均距离。在第1种方法中，表示为改进的DV-Hop1，通过以下方程未知节点计算不同锚节点跳段大小的平均值

(8)

(8)式中，M表示锚节点的数量，使用运用公式(1)获得HSi。

在第2种方法中，表示为改进的DV-Hop2,通过使用获得的跳段大小和跳段，每个锚节点首先估计它与其他锚节点之间的距离。

(9)

(9)式中，hopij表示锚节点i和锚节点j之间的跳段大小。此外,运用(10)式锚节点需要计算彼此之间的实际距离。

(10)

(10)式中，(xi,yi) 和 (xj,yj)分别表示锚节点节点i和j的坐标。通过运用以下公式，每个锚节点都要计算估计距离和实际距离之间的差异，即

(11)

(11)式中，errorij表示估算误差，对应于锚节点i和j之间的计算距离。通过这对应的估算误差，运用公式(12)，每个锚节点都要估算其平均跳段的有效值。

(12)

最后，每个锚节点在网络中都要传送其有效的跳段大小。

未知节点收到锚节点发出的跳段大小之后,要估计与每一个锚节点之间的距离。值得注意的是,传统的DV-Hop算法假定整个网络的平均跳段距离都是一样的。这种假设降低了定位的精度,特别是当未知节点与锚节点节点之间的跳段是1的时候。事实上,一跳的距离可以小于或大于平均跳段距离，不完全与之相等。此外,在节点随机部署的网络中,有些节点距离很近,有些节点则相距遥远。因此,只运用一种测距方法不是一种有效的方式。受这种情况的启发,提出了一种基于接收信号强度指示和无需测距相结合的方法，以此获取节点之间有效的距离。

RSSI方案是最基本的方法，基于接收信号功率，计算2个传感器节点之间的距离。基于RSSI的测距作为距离估算的一种方式，基本上不受约束，因为无线传感器节点有无线电广播设备，还测量了每个无线数据包的信号强度。在本文中,利用RSSI测量来估计未知节点与锚节点之间的距离,它们之间只有一跳的距离。如果一个节点的覆盖范围可以到达其他节点，那么该节点可以直接与其他节点通信。所有的锚节点生成RSSI数据包，通过网络进行广播，任何未知节点收到该数据包,都要计算该节点本身到锚节点的RSSI距离。

在接下来的讨论中,实行了参考文献[11]提出的无需测距方案,用于估计节点之间多跳的距离。在该方案中, 未知节点和锚节点之间的实际跳段添加了一定量的校正值w,即

(13)

(13)式中：hopij表示未知节点i和锚节点节点j之间的跳段；HSavg表示所有锚节点的平均跳距离，k是一个调整系数。注意HSavg的数值由前面步骤的结果计算得出，如果应用第1种方法,它等于锚节点的平均跳段大小，而如果应用第2种方法,它等于所有锚节点的平均有效跳段大小。另一方面,hopij的数值越大,未知节点和锚节点之间的路径越不可靠,这意味着应该添加更多的校正值。注意,这个修正方案在一定程度上可以减少定位误差,但是增加了算法的复杂性。

在该步骤最后，未知节点i和锚节点节点j之间的校正距离为

(14)

(14)式中，k是一个实验参数，可以在实际应用场景的基础上特别挑选。实验结果表明，当k设置为1时，定位误差接近于最小值。

2.2 位置估计

在多跳的路线中使用所有锚节点的估计距离，每个未知节点利用3边测量算法找到自己的坐标。在基本的DV-Hop中,非线性方程组((3)式中概述)会导致非线性误差问题。如果不管线性化误差,这就导致位置估计不准确。因此,使用一种优化技术来解决非线性问题。

LM算方法在无线传感器网络定位的准确性方面体现了令人满意的结果[13]。LM算法使用搜索方向的方法(梯度下降法和Gauss-Newton方法相结合)找到公式(16)的解决方案，其中通过更新参数进行迭代改进，用来减少函数和测量数据点之间的误差平方和。该算法从未知节点坐标的初始值开始，迭代运行得到一个最优的解决方案。在每个迭代中，基于数学推导如梯度等，对非线性最小平方问题的新方向进行选择。

假设si是一个未知节点，坐标为si=(xi,yi)，aj是一个锚节点节点，坐标为aj=(xj,yj)，dij表示si与M个锚节点的估计距离，剩余的误差向量表示为

(15)

(15)式中，‖·‖表示欧几里得范数。为了找到si的更确切位置，细化问题可以用(16)式表示为最小方差问题

(16)

(16)式可以由线性搜索LM方法来解决，即

(JT(sk)J(sk)+μkI)-1·JT(sk)d(sk)

(17)

(17)式中：I表示恒等矩阵；J(sk)表示d(sk)在迭代k的雅可比行列式；μk表示可调整的阻尼因数，表示为

μk=ρ‖JT(sk)d(sk)‖

(18)

(18)式中，ρ∈(0,1)。应用初相获得了LM迭代算法要求的未知节点位置的第1个估算值，即

(19)

注意锚节点与未知节点的距离跳段更多，由于跳段大小的误差，两者的距离包含更多误差，导致定位算法的总体准确性下降。因此，我们应用加权最小平方法来改进定位的准确性[10]。应用加权最小平方法，在三边测量法中，基于锚节点与未知节点的接近程度，它们被赋予不同的权重或影响力。假设wsi等于未知节点s与锚节点j之间跳段的倒数，权重矩阵Ws如(20)式所示。最后权重矩阵在函数f(si)中作为乘积。

(20)

3 实验结果

利用Matlab2009a平台将本文提出的算法，与其他定位方法进行了仿真对比实验[12]。在仿真实验中，所有传感器节点都是随机部署在100 m×100 m的正方形区域内，没有任何障碍和干扰(随机布置正方形)。在同一片区域内随机选择锚节点，比例为所有节点数量的20%。仿真参数设置包括以下几点：①所有传感器都是静止的(没有移动的节点)；②传感器是同类的节点的通信、能量和存储能力都是相似的；③通信渠道都是双向的。这意味着如果节点s1可以接收到节点s2的信息，那么s1可以发送信息给s2；④每个节点至少都有一个相邻的节点。随机节点分布如图1所示。

为了获得一个更好的统计结果，重复实施仿真实验；总体结果为50次实验的平均定位误差。

定位算法的准确性由平均定位误差(average localization error,ALE)进行评估，即

(21)

图1 随机节点分布Fig.1 Random node distribution

图2显示出了改进后定位算法在节点数量为250，锚节点比例为20%时，每个未知节点的定位精度。未知节点的定位精度大约在24%。

图2 提出改进定位算法中未知节点的定位精度Fig.2 Positioning accuracy of unknown nodes in the proposed improved localization algorithm

3.1 传感器节点数量的影响

设置锚节点的比例为20%，R设置为25 m。不同数量的节点定位误差如图3所示。可以看到，随着节点的数量增加，提出的算法实现了较低的定位误差。同时可以清晰看到提出的算法(表示为改进的距离DV-Hop1和改进的距离DV-Hop2)明显优于其他的改进算法[12]。

图3 节点数量对定位误差的影响Fig.3 Effect of the number of nodes on the position error

3.2 锚节点比例的影响

图4是随机部署200节点，R设置为25 m，锚节点比例逐渐增加时，提出算法和现有其他算法定位误差的比较结果。结果表明，随着比例的增加，各个算法的节点定位误差均随着锚节比例的增加而降低。但是，可以看出，在相同锚节点比例下，提出改进算法的平均定位误差最低。

图4 锚节点比例对定位误差的影响Fig.4 Effect of the proportion of anchor nodes on the positioning error

3.3 传感器节点通信范围的影响

在这部分中，所有节点的数量设置为200，锚节点的比例为20%。改变了传感器节点的无线电射程，得出了相应的测量定位误差。仿真结果表明，传感器的通信半径越大，误差越小。从图5可以看到，提出的算法性能要优于基本的DV-Hop算法和其他改进的算法。在所有的实验中，虽然改进的DV-Hop2算法与改进的DV-Hop1算法稍微有点差异，但计算的平均定位误差均最小。

从图3—图5可以看出，随着节点数量、锚节点比例和节点通信范围的增加，本文提出算法的平均定位误差逐步降低。但是当节点数量达到200以上，锚节点比例达到20%以上或者节点通信范围达到30 m以上时，提出算法的平均定位误差将不再下降，即达到最佳定位精度。此外，在相同参数的条件下，提出算法的平均定位误差均比现有DV-Hop算法更低。

图5 传感器节点通信范围对定位误差的影响

4 结 论

本文提出一种通过优化跳段大小来减少距离估计误差的DV-Hop定位算法。该方法的主要思想是结合基于接收信号强度指示和无需测距的方法，来估算校正一跳距离，并且应用LM来计算节点的位置，降低了那些远离未知节点的锚节点的作用。仿真结果表明，与传统的DV-Hop和一些现有的改进算法相比，提出算法具有更低的平均定位误差，即定位精度得到有效提高。提出算法能够在较低的节点数量和锚节点比例条件下，达到最佳定位性能，适用于各种无线传感网定位应用。