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

　　节点定位是实现传感器网络应用的前提，控制节点定位误差成为保证网络正常运行的关键。采用基于测距的定位算法，可以达到良好的精度，但需要测量装置，不适合能量受限的无线传感器网络。本文分析了常用的非测距定位算法，并在此基础上提出了一种改进的基于序列的非测距定位算法，以提高无线传感器网络定位算法的性能。

　　引言

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

　　目前基于非测距的算法有DVHop（Distance VectorHop）算法［2］、Centroid算法［3］、APIT算法［4］、SBL（SequenceBased Localization）算法［5］。SBL算法是一种利用接收信号强度RSSI来采集信标节点序列，通过区域划分实现节点定位的非测距定位算法。该算法对比RSSI信号的强弱获得待定位节点与不同信标节点之间距离的相对大小，具有复杂度低、定位精度高、健壮性强的特点。但是SBL算法不能充分利用一跳范围以外的信标节点和未知节点的信息等，本文通过分析一跳范围以外的节点信息，在相同条件下提高了算法的定位精度，仿真实验表明 ASBL（Advanced SequenceBased 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之间的平分线刚好与待定位区域的边缘相切，未能穿越待定位区域。因此，在均匀分布的网络中，距离待定位节点跳数越小的信标节点对于待定位节点的定位帮助越大，随着跳数的增加，三跳范围以外的的信标节点不能对待定位节点的定位提供有用的位置信息。在实际中，待定位节点发出的定位询问信息的跳数