基于T—Hop的无线传感器网络定位方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于T—Hop的无线传感器网络定位方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
1 引言
如果说Internet构成了逻辑上的信息世界，改变了人与人之间的沟通方式，那么无线传感器网络（WSN，Wireless Sensor Network）就是将逻辑上的信息世界与客观上的物理世界融合在一起，改变人类与自然界的交互方式[1]。无线传感器节点通常随机布放在不同的环境中执行各种检测任务，以自组织的方式相互协调工作，随机布放的传感器节点无法事先知道自身节点位置，因此传感器节点必须根据少数已知位置的节点，按照某种定位机制确定自身位置[2]。
在传感器网络中，定位算法通常分为基于距离的定位算法和与距离无关的定位算法，基于距离的定位算法需要测量节点间的绝对距离或方位，并利用节点间实际距离来计算未知节点的位置[3]。与距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件的要求，但是定位的误差也相应增加。距离无关定位算法主要有质心算法、DV-hop算法、Amorphous算法、APIT算法等[4]。
距离向量-跳段DV-Hop定位机制非常类似于传统网络中的距离向量路由机制[5]。该低功耗节点网络定位算法具有以下特点：（1）分布式，防止靠近信标节点的节点过度劳损；（2）尽可能减少节点之间的通信能量和计算能量，通信开销是电能消耗的主因；（3）网络部分断开后也能进行数据收集；（4）提供节点的绝对坐标[6]。因此DV-Hop定位网络能间歇性运作，生存能力强，能量高效，不需要特殊的基础设备[7]。
2 DV-Hop算法
DV-Hop算法是D.Nieulesu[8]等人提出的APS（Ad hoc Positioning system）系统采用的定位方法。其landmarks没有足够大的可覆盖整个网络的发射功率，避免了与本地通信系统的冲突；landmarks的位置不固定，以增加网络节点部署的随机性，方便网络重新部署和移动；landmarks之间是通过hop by hop方式联系而不是直接通信；节点选择hop by hop的传播方式计算节点到信标节点的距离。
2.1 算法描述
DV-Hop是APS最基本的方案，包括3个非重叠的阶段：首先采用经典的距离向量交换，使所有网络节点都能获取到信标节点的以hop为单位的距离。每一个节点与其邻居节点交互更新；第二阶段，一个信标节点在与其它信标累积距离后，估计其平均单跳距离，并且将该平均单跳距离作为此信标节点的邻居节点的标准部署校正；第三阶段，任意节点在接收校正时，估计自己到信标节点的距离，以米为单位表示，用于进行三边测量。其中校正值的计算方法如下：
（1）
式（1）中：（Xi，Yi）为第j个信标节点的位置；hj为从第j个信标节点到第i个信标节点的跳数。
2.2 算法不足
DV-Hop算法与距离测量误差无关，但是DV-Hop只工作于各向同性网络之中。在各向异性网络中，如果两个节点到相同landmarks有相同hop-counts，那么它们的位置将会是相同的。
如图1所示，节点a1、a2、a3到landmark的跳段距离均为1，但a2到landmark的距离明显较大，同理b4到landmark的距离明显小于b1、b2、b3、b5，但是它们的跳段距离都为2。因此，如何更精确反映节点到landmarks的距离是DV-Hop面临的严峻挑战。
DV-distance算法与DV-Hop方法相似，其节点与邻居节点之间距离使用信号强度来测量，但是它与测量误差相关度较高，其结果时常表现为不规律、动态和不对称。比如在地形复杂又多障碍物的森林中，基于RSSI的距离测量经常受到影响，引起不受欢迎但却普遍存在的误差。因此，在保证算法与距离测量误差无关的情况下提升定位精度也是我们研究的方向。
在现有的研究进展中，WANG Ying[9]等在未知节点到锚节点的路径中，考虑相邻3个节点组成的夹角对距离的影响，根据邻近节点重叠度计算夹角，引入网络平均连通度计算节点间的跳距。Guoqing GAO[10]等人提出CDDV-Hop方法，使用邻居节点的密切程度，建立数学模型，然后计算出单跳距离。ZHANG YingJie[11]等人提出Weighted DV-HOP将普通节点到锚节点的Hop信息作为权重来提高定位精确度。以上方法分别从网络拓扑和节点密度等方面对DV-Hop算法做出了改进，但是忽略了邻居节点分布以及原有Hop数对于整体定位的辅助参考作用，定位过程的开销较高。
3 T-Hop算法
为了方便表述，我们将节点i的一跳邻居节点，且该邻居节点到信标节点j的DV-Hop加1为节点i到信标节点j的DV-Hop数，称为节点i关于信标节点j的上游邻居节点；与节点i有相同上游的节点称为节点i同阶节点；节点i的一跳邻居节点，且该邻居节点到信标节点j的DV-Hop减1为节点i到信标节点j的DV-Hop数为节点i关于信标节点j的下游邻居节点。如图2所示，节点i与上游邻居节点越近，就有越多的同阶节点，越少的下游邻居节点。
图2 邻居节点与同阶节点
在各向同性网络中，网络节点分布均匀，网络中节点有相同的上下游邻居节点，节点距离接近于平均跳段距离，如图3（a）所示。当网络中节点分布不均匀时，节点越接近于上游邻居节点，就有越多的上游邻居节点，如图3（b）、（c）、（d）中，分别为3、2、3，节点的下游邻居节点个数为0、1、2。同样也有越多的同阶节点，分别为3、2、3，节点同阶邻居节点的下游邻居节点个数的平均值分别为1、1、2；节点同阶邻居节点的上游邻居节点个数的平均值分别为1、1、1。
节点到landmark的跳数计算公式如下：
（2）
其中，i为普通节点，j为landmarks，表示节点i关于信标节点j的上游邻居节点到信标节点j的平均跳数，表示节点i关于信标节点j的同阶节点上游邻居节点个数的平均值，表示节点i关于信标节点j的上游邻居节点个数，表示节点i关于信标节点j的下游邻居节点个数，表示节点i关于信标节点j的同阶节点的下游邻居节点个数的平均值。
图3（b）中节点a的hopsize值计算如下：
0.4
同理，图3（a）、（c）、（d）中a的hopsize分别为：2、1.8、1.75。其中图3（b）与（d）的跳数差距比较大是因为图3（d）网络节点密度较大，网络平均节点平均单跳距离相应减小。
图1中节点的跳数计算如表1所示：
4 实验结果及分析
为了验证新算法的优越性，我们将其与DV-Hop、CDDV-Hop和Weighted DV-HOP算法就定位误差进行了对比分析。在仿真实验中，我们将节点随机部署在500m*500m的区域中，将节点的通信距离设置为30m。信标节点个数为6，节点密度为6。为了实验结果更具区别性，我们选取其中100个节点在两种算法作用下的定位结果，并对其定位误差进行了对比，比较结果如图4所示。
图4 不同算法节点定位误差比较
由于新算法通过充分利用局部邻居节点的联通信息，更好地反映了非统一分布的性质并且将节点到landmarks的跳数精确到小数点后两位，减少了节点到相同landmarks有相同跳数的概率，使得节点在迭代之初就有较低的定位误差，明显提高了整体定位精度。
节点密度指的是节点一跳范围内平均邻居节点个数，是定位的重要因素。我们保持landmarks数量不变，通过增加或减少节点的数量的方式改变网络中节点密度，并观察它对定位精度的影响。试验结果如图5所示。
图5 不同节点密度下不同定位算法的误差对比
如图5所示，当节点密度较低时，DV-Hop性能较差，这是因为网络节点稀疏时，非统一部署的问题更严重了；随着节点密度的增加，这一问题得到缓解，节点到landmarks的距离越接近于直线距离，到landmarks的跳段越准确，网络节点的平均定位误差也就越小。但是由于landmarks的数量并未增加，所以网络节点的平均定位误差下降到一定程度后就呈现较平缓的趋势。
由于无线传感器网络部署和位置测量的复杂性，通常只有有限个landmarks。因此检测不同数量的landmarks下的平均定位误差是非常有意义的。在仿真中，我们将landmarks的数量从所需最小数量（3）调节至相对较大的数量（16），保持节点密度为6不变。如图6所示，两个算法都只是简单依靠节点到landmarks的跳数来计算节点位置，因此都会受到landmarks数量的影响。当landmarks只增加2到3个时，平均定位误差明显减少，但随着landmarks数量的增加，平均定位误差下降幅度减小并逐渐趋于平和。
图6 landmarks数量对平均定位误差的影响
5 结束语
本文通过分析经典的DV-Hop定位算法中计算节点到landmarks跳段距离的不足，提出算法的改进策略，通过节点局部邻居节点联通信息对节点的影响，设计了一种新的定位算法，更精确地计算节点到landmarks的跳段距离。实验证明，该算法具有较高的优越性，提高了节点的定位精度。
参考文献：
[1] 孙利民. 无线传感网络[M]. 北京： 清华大学出版社， 2005： 3-155.
[2] Niki Trigoni，Bhaskar Krishnamachari. Sensor network algorithms and applications[J]. Phil. Trans. R. Soc. A， 2012（370）： 5-10.
[3] ?kos Lédeczi，Miklós Maróti. Wireless sensor node localization[J]. Phil. Trans. R. Soc. A， 2012（370）： 85-99.
[4] Bulusu N，Heidemann J，Estrin D. GPS-less low cost outdoor localization for very small devices[J]. IEEE Personal Communications， 2000，7（5）： 28-34.
[5] Kong Y，et al. Density adaptive localization for irregularly deployed wireless sensor networks [J]. Int J Electron Commun（AE?）， 2012.
[6] Juan Cota-Ruiz，et al. A Low-Complexity Geometric Bilateration Method for Localization in Wireless Sensor Networks and Its Comparison with Least-Squares Methods[J]. Sensors， 2012，12： 839-862.
[7] Kaushik Mondal，et al. Localization in Presence of Multipath Effect in Wireless Sensor Networks[J]. Springer-Verlag Berlin Heidelberg， 2012，LNCS7277： 138-149.
[8] D Niculescu，B Nath. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems， 2003： 267-280.
[9] WANG Ying，SHI Hao-yang. Improved DV-Hop Localization Algorithm for Wireless Sensor Network[J]. Computer Engineering， 2012： 66-69.
[10] Guoqing GAO，Lin LEI. An Improved Node Localization Algorithm Based on DV-HOP in WSN[C]. Advanced Computer Control （ICACC） 2010 2nd International Conference on Shenyang.
[11] ZHANG YingJie，et al. Research of WSN Node localization Algorithm Based on Weighted DV-HOP[C]. Control and Decision Conference （CCDC） Chinese 2012 24th on Taiyuan， 2012.