一种改进的无线传感器网络非测距定位算法

付松涛，杨爱玲，高镇，郭振乾

（1.中国人民解放军61655部队；2.中国人民解放军61936部队；3.四川大学）

引 言

无线传感器网络具有部署灵活、便于信息获取和传输等特征[1]，得到大量应用。由于无线传感器网络节点一般采用低功耗设置以解决长时工作状态下能量补给困难的问题，其节点定位技术不同于全球卫星定位系统（Global Positioning System，GPS）定位技术。如果采用基于测距的定位算法，可以达到良好的精度，但要求额外的物理测量设备，硬件成本和功耗偏高，不适合于大规模无线传感器网络。基于非测距的定位算法，由于不需要测量传感器节点之间的物理距离或角度，在实际中具有更佳的实用性，因此成为研究热点。

目前基于非测距的算法有DV-Hop（Distance Vector-Hop）算法[2]、Centroid 算法[3]、APIT 算法[4]、SBL（Sequence-Based Localization）算法[5]。SBL算法是一种利用接收信号强度RSSI来采集信标节点序列，通过区域划分实现节点定位的非测距定位算法。该算法对比RSSI信号的强弱获得待定位节点与不同信标节点之间距离的相对大小，具有复杂度低、定位精度高、健壮性强的特点。但是SBL算法不能充分利用一跳范围以外的信标节点和未知节点的信息等，本文通过分析一跳范围以外的节点信息，在相同条件下提高了算法的定位精度，仿真实验表明ASBL（Advanced Sequence-Based Localization）算法相对于SBL算法在性能上有大幅的提升。

1 模型化

在无线传感器网络中，节点分为两类：信标节点和未知节点。信标节点所占比例较小，可以获知自身的精确位置，未知节点利用信标节点的位置信息通过某种算法来确定自身位置。如图1所示，区域中有A、B、C三个信标节点，在A和C中垂线的上侧区域中任意一点与A、C的距离关系为DA＜DC，同理在中垂线下侧区域有DC＜DA。不同的中垂线相互交叉把网络所在区域分割成更小的独立区域，每个独立区域到信标节点的距离排序是唯一的，这个排序序列称为该独立区域的签名序列。如果一个待定位节点在DB＜ DA∩DB＜ DC∩DA＜ DC区域中通过RSSI测量各个信标节点的信号强度，那么得到的信号强度应该是SB＞SA＞SC，待定位节点认为自己测得的定位序列为B-A-C。

图1 区域划分和求签名序列

两个序列之间的匹配相似度采用斯皮尔曼相关系数[6]（Spearman＇s Rank Order Correlation Coefficient）和肯德尔等级相关系数[6]（Kendall＇s Tau）来衡量。给定两个序列 U＝｛ui｝和 V＝｛vi｝，1≤i≤n，其中n表示信标节点的个数，ui和vi表示序列中的信标节点的位置。用ρ表示斯皮尔曼相关系数，用τ表示肯德尔等级相关系数，则有：

其中，nc表示两个序列中先后顺序一致的节点对的数目，nd表示两个序列中先后顺序不一致的节点对的数目，ntu和ntv分别表示两个序列的内部关系数。

ρ和τ的值都介于-1和1之间。两个完全相同序列的ρ和τ的值为1，完全不相关的两个序列的ρ和τ的值为0，两条相逆的序列的ρ和τ的值为-1。SBL算法取ρ和τ值最大的序列作为匹配序列。如图2所示，待定位节点通过式（1）的匹配算法与“签名序列表”中的序列进行匹配，可以得出自己所在的区域，以该区域的质心作为自己的坐标。

图2 匹配探测序列完成定位

2 ASBL算法

ASBL算法的待定位节点只能接收到通信半径范围内的信标节点的RSSI值，无法充分利用通信半径外的信标节点信息来定位。当网络中信标节点增多时，理论上被分割区域并没有发挥作用。

如图3所示，S表示待定位节点，最中心的虚线范围表示S经过RSSI序列进行初步定位之后可能的待定位区域。A表示在S通信范围内的信标节点，B表示2跳范围的信标节点，C和D表示三跳范围的信标节点。分别做AB、AC和AD之间的平分线，AB和AC之间的平分线穿越S的待定位区域，能够缩小待定位区域的面积，当信标节点D位于三跳范围边缘时，AD之间的平分线刚好与待定位区域的边缘相切，未能穿越待定位区域。因此，在均匀分布的网络中，距离待定位节点跳数越小的信标节点对于待定位节点的定位帮助越大，随着跳数的增加，三跳范围以外的的信标节点不能对待定位节点的定位提供有用的位置信息。在实际中，待定位节点发出的定位询问信息的跳数上限设置为6即可，既能最大化地利用多跳信标节点的位置信息，又不会消耗过多的能量用于通信。

图3 不同跳数的信标节点之间的中垂线

如图4所示，一跳的信标节点能给待定位节点提供大致的待定位区域，二跳信标节点一般情况下能将待定位区域的面积缩小75%左右，三跳及三跳以外的信标节点能在二跳的基础上继续将待定位区域面积缩小20%左右。

图4 不同跳数的信标节点对定位的帮助

3 仿真验证

本文使用Java语言开发了一个仿真平台，分析检验ASBL算法的各种性能指标。设置传感器节点随机部署在200 m×200 m的区域内，节点的通信半径默认为30 m，表1中的数据是仿真平台的各项参数信息。

表1 仿真平台默认参数信息

3.1 节点密度对定位精度的影响

本组仿真中，将节点随机部署，信标节点密度设为10%，节点数量在100～500之间变化，节点通信半径覆盖不规则度为0，其余参数保持不变。通过图5可以看出，随着节点密度的增大，各算法定位精度都有所提升，当节点达到400个时，各算法性能趋于稳定。因为能够使用一跳范围外的信标节点和未知节点协助定位，ASBL算法定位精度比DV-Hop算法提高25%左右，比APIT算法提高15%左右，比SBL算法提高12%。

图5 节点密度对定位精度的影响

3.2 节点通信半径对定位精度的影响

设置节点总数为300个，信标节点密度为10%，节点通信半径从10～50 m递增，其余参数按照默认设置，重复10次仿真。由图6可以看出，通信半径为10 m时，ASBL算法的定位精度要比SBL算法高75%，这是因为ASBL能充分利用一跳范围外的信标节点。通信半径为50 m时，ASBL算法的定位精度比SBL算法仅高1.4%，这是因为当节点通信半径增加时，原来位于一跳范围外的信标节点此时会位于一跳范围内。

图6 节点通信半径对定位精度的影响

结 语

非测距的定位技术以所需传感器节点能量少、硬件简单，成为目前无线传感器网络定位技术的主要研究方向。本文提出了ASBL算法，针对SBL算法作了改进，以提高算法良好的适应性和健壮性。恰当的定位算法是无线传感器网络正常工作的基础，针对非测距定位算法的研究将会朝着降低能量消耗和提高定位精度的方向发展，从而极大地提高网络的生存能力和工作效率。

[1]Bin Duan，Guojing Li，Chaowu Qiu，et al.Fault location and self-healing of distribution network based on function block and wireless sensor[J].Innovative Smart Grid Technologies（ISGT），2012（1）：16-20.

[2]Ying Zhou，Baojian Gao，Tianzhang Xing，et al.Improvement on Localization Error and Adaptability in DV-Hop Algorithm[C]//6th China Conference，CWSN 2012：725-733.

[3]Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications，2008，7（5）：28-34.

[4]He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks[C]//Proc 9th Annual Int＇1 Conf on Mobile Computing and Networking（Mobi-Com），San Diego，CA，2003：81-85.

[5]Krishnamachari，Bhaskar.Sequence-Based Localization in Wireless Sensor Networks[J].Mobile Computing，IEEE Transactions，2008（7）：81-94.

[6]W H Press，B P Flannerly，S A Teukolsky，et al.Vetterling：The Art of Scientific Computing[M].Second edition.England：Cambridge UnivPress，1992.