基于几何原理的无需测距传感器节点定位

赫佳星

(内蒙古科技大学 信息工程学院，内蒙古 包头 014010)

0 引 言

无线传感器网络(wireless sensor network，WSN)广泛应用于环境监测、安全保障、卫生保健和工业领域等[1]；定位、部署和覆盖是WSN中的几个基本问题，其中定位是最重要的，因为定位信息对于覆盖、部署、路由、位置服务和目标跟踪都极其重要，如在基于位置的路由协议中[2,3]，路由和数据转发都是根据地理位置确定。

针对定位问题的方案大致可分为两类。一是基于测距的方案，这种方案需要节点到节点的距离或角度信息来估计位置。这些信息可以通过到达时间(time of arrival，ToA)、到达时间差(time difference of arrival，TDoA)、到达角(angle of arrival，AoA)和接收信号强度指示(received signal strength indicator，RSSI)技术[4,5]来获得，但基于测距方案大大增加了成本；二是无需测距的方案，这种方案不需要距离或角度信息，但大大节省了经济成本，使得无需测距方案成为更好的选择。

基于测距方法的定位机制得到了广泛研究。文献[6]针对非视距误差对室内定位的影响，提出了一种室内三维定位算法；文献[7]针对不同传感器的测量值时间不匹配、定位精度低等问题，提出了一种改进型三角定位法；文献[8]提出计算相邻节点之间的比较角作为角度测量。

为了适应WSN固有的低功耗和低成本特点，无需距离或角度信息来估计位置得到了研究。文献[9]引入质心公式，根据包含参考信标点位置的接收信标来计算节点的位置；文献[10]提出DV-Hop定位方法来测量每个节点到特定锚点的跳数，然后利用跳数和三角测量计算出传感器节点的近似位置；文献[11]提出了一种基于区域的定位机制，以缩小传感器节点的可能区域。上述方案通常需要大量的固定参考点才能获得较高的精度，而且一些方案还需要在相邻传感器节点之间进行大量的通信[10,11]；文献[12]提出了一种采用单个移动信标发送其当前位置的定位机制；文献[13]基于超声波技术估计传感器节点到移动目标的距离，只要节点到节点之间的距离可用，传感器节点的位置就可以通过基于测距方案来测量；文献[14]提出了采用移动信标的概率定位方案；文献[15]采用无线连通性约束，提出了一种无需测距的定位算法。

本文提出了一种采用弦的垂直平分线必经过圆心的几何原理的无需测距的传感器节点定位方案。仿真结果表明，本文定位方案在定位误差、定位执行时间和信标开销方面都优于其它无需测距定位方案。

1 基于几何原理的定位方案

1.1 系统模型

本文的WSN节点定位模型如图1所示。其中WSN由传感器节点和移动锚点构成，传感器节点随机分布在感测区域中，而且一旦节点部署完成，它们就停留在自己的位置上执行感测任务；传感器节点可以接收来自其它节点和锚点的信息；移动锚点能够巡游以辅助传感器节点确定它们的位置。假设每个移动锚点配备一个全球定位系统接收机，且在定位过程中有足够的能量，以便移动和广播信标消息。

图1 本文的WSN节点定位模型

1.2 定位原理

假设传感器节点的传输范围(无线电范围)R是一个圆(也称为通信圆)，圆心表示传感器节点的位置。方案利用移动锚点在感测区域中移动，并周期性地广播信标消息(包括它们当前的位置信息)。当传感器节点接收到信标消息后，就可以确定有效的信标点和弦。如果得到任意两条弦，则可以根据任意弦的垂直平分线必经过圆心来找到圆心，从而计算出传感器节点的位置；为了提高方案的定位性能，还提出了一些改进措施，包括随机信标调度、弦的合理选择和增强信标选择机制。

如图2所示，圆C的两条弦AB和EF是端点在圆上的两段。在同一圆的两条弦中，两条弦的垂直平分线的交点必在圆心。基于这一原理，可以对定位问题进行转化。圆心就是传感器节点的位置，圆的半径就是传感器节点与移动锚点可以通信的最大距离，弦的端点就是移动锚点经过圆的位置。

图2 两条弦的垂直平分线的交点必过圆心

1.3 信标点选择

在该方案中，在圆上至少要收集3个端点，用来构建两条弦。每个移动锚点在传感器网络中移动时周期性地广播信标消息，信标消息包含锚节点的id、位置和时间戳；每个传感器节点维护一组信标点和一个访问者列表。把信标点看成是传感器节点通信圆上的一个近似端点。访问者列表存储已被传感器节点接收消息的移动锚点及其相关寿命。传感器中第i个信标点表示为(idi、locationi、timestampi)，访问者列表中第j条记录可以表示为(idj, lifetimej)。当一个传感器节点从一个移动锚点接收到信标消息时，该节点将检查锚点是否在其访问者列表中。如果没有，将添加一个信标点，并在访问者列表中插入具有预先确定寿命的锚点。否则，忽略信标消息，并延长移动锚点的寿命。当锚点的寿命结束，就删除访问者列表中相应的记录，并将锚点的最后信标消息记录为信标点。

图3所示为信标点选择示例。移动锚点M在间隔t(Ti+1-Ti,i=0,1,…,16)内移动并广播信标消息。M的移动轨迹表示为从(x,y)通过(x′,y′)到(x″,y″)的虚线。在T1的信标点为(M,(x1,y1),T1)，且在访问者列表中M的记录为(M,T1+δ)。δ是移动锚点的预先确定寿命，且δ的值应大于信标间隔t(δ=αt,α≥1)。当M到达T2,T3,T4和T5时，M的寿命将被更新(Ti+δ,i=2,…,5)。在M离开传感器S的传输范围且M的寿命到期后，访问者列表中M的记录被删除。与此同时，在T5的信标即M的最后信标，将被选作为信标点。同样，在T12和T15的两个信标也被选作为信标点，用于构成弦来估计传感器S的位置。

图3 信标点选择

1.4 传感器节点的位置计算

在3个信标点都得到之后，就可以生成两条不同的弦。如图4所示，选择的信标点集合为{Bi,Bj,Bk}，且它们的位置分别为(xi,yi),(xj,yj)和(xk,yk)。随机选择的两条弦BiBj和BjBk基于信标点构成。考虑到直线Lij和Ljk分别为弦BiBj和BjBk对应的垂直平分线，因此，通过代数运算，两条直线Lij和Ljk的方程就可以表示为

图4 位置计算

(1)

基于Cramer法则，Lij和Ljk的交点即传感器节点的估计位置为

x=(|cij*bjk-cjk*bij|)/(|aij*bjk-ajk*bij|)

(2)

y=(|aij*cjk-ajk*cij|)/(|aij*bjk-ajk*bij|)

(3)

其中

aij=xj-xi,bij=yj-yi

(4)

cij=(xj-xi)((xi+xj)/2+(yj-yi)(yi+yj)/2)

(5)

ajk=xk-xj,bjk=yk-yj

(6)

cjk=(xk-xj)((xj+xk)/2+(yk-yj)(yj+yk)/2)

(7)

1.5 性能提高措施

1.5.1 随机信标广播机制

无线自组织网络中的广播可能导致破坏性的带宽拥塞、争用和碰撞[16]。同样，本文定位方案中的周期性信标消息广播可能会导致传感器节点上的碰撞。为了解决这一问题，广播信标信息的调度就必是抖动的[17]。抖动时间从0～(0.01*信标间隔)之间的均匀分布中随机选择，抖动信标间隔计算如下

抖动信标间隔=信标间隔+抖动时间

(8)

这样，随机信标调度就防止了传感器节点上的信标碰撞，使得每个节点都能从不同的移动锚点有效地获得信标消息。

1.5.2 弦的选择

如果选择的信标点恰好在通信圆上，则定位就是精确的。但在实际环境中，由于碰撞或不合适的信标间隔，可能会选择错误的信标点，因此用信标点产生的弦可能无法准确估计传感器节点的位置。图5所示为由于错误的弦而造成的较大定位误差。根据观察，当弦的长度太短时，定位失败的概率会迅速增大，对此采用弦长度阈值λ来解决这个问题。阈值λ和通信圆半径之间的关系为

图5 失败的定位

0<λ≤2R

(9)

为了减小定位误差，弦的长度必须超过阈值，这在性能评价中将得到体现。

1.5.3 容许障碍物存在的增强信标选择机制

一般来说，传感器区域中可能存在障碍物，障碍物会导致WSN中的无线电信号出现异常。对此，我们提出一种基于同心圆特性的增强信标点选择机制来容许障碍物的存在。对于一个特定的圆，利用它的一个同心圆上的弦也可以计算圆心。如果不能得到圆上的两条弦，则同心圆上的其它弦也是有用的。如图6所示，只有B1在圆上，而其它信标点在圆中，但B3、B4和B5在同一个同心圆上，可以构成两条合适的弦来确定圆心。算法1为增强信标选择机制实现的伪代码。

图6 采用同心圆上的弦来定位

算法1：增强信标点选择机制实现伪代码

定义:

BS={(Bi,si)|i=1,2,…,m}:锚点及其对应信号强度集合；

D={dk|k=1,…,m-2}:3个相邻排序信号强度的差；

Sort(A):根据信号强度将A从弱到强排序；

Find_Min(A):从A中找出最小元素；

Check_Threshold(Ai,Aj,Ak):检查每条弦长的阈值(成功:1, 失败:0)。

算法：

(1)Sort(BS)→BS′

(2)//计算BS′中3个相邻排序信号强度的差//

(3)for(k=1;k≤m-2;k++)

(5)//搜索D中的最小值//

(6)Find_Min(D)→dmin

(8)first_min=min

(9)//检查弦的阈值//

(11){

(12) 从D中删除dmin

(13)if(D≠∅)

(14) 回到步骤(5)

(15)else

(17)}

(18)else

(20)end

2 方案性能评价

2.1 性能指标

用3个指标来评价定位方案的性能。

(10)

(2)平均执行时间：传感器节点计算其位置所需的平均时间，即

(11)

(3)信标开销：在全部执行时间内移动锚点的信标消息广播的平均数量，即

(12)

2.2 仿真环境及参数设置

仿真采用ns-2网络仿真器进行，其中无线模型基于2 Mbps带宽的光波局域网IEEE802.11，采用IEEE802.11无线局域网分布式协调功能作为介质访问控制模型。定位过程中使每个传感器节点都保持活跃状态，在获得其位置后，就可以进入低功耗模式，以提高功效。

对于无障碍物的环境，仿真的传感器区域设置为一个100m×100m的正方形区域。在感测区域中随机部署320个传感器节点。在开始时，每个移动锚点随机放置在仿真区域的一个角落，锚点不能放置在感测区域内，否则，传感器节点将把第一个信标作为信标点，而这个信标点并不位于通信圆上。移动锚点的传输范围为R，且按随机路点模型[18]移动。当移动锚点到达预定位置时，移动锚点朝下一个目的地移动。当全部传感器节点获得它们的位置时，就结束仿真；对于有障碍物的环境，信号在视距传播中接收，感测区域的大小、传感器节点的数量和移动锚点的起始位置与无障碍物环境的相同，但在感测区域中有4个10m×20m的障碍物。

为了评价本文方案的性能，还将本文方案与文献[9]采用质心的无需测距定位方案和文献[14]采用移动信标的概率定位方案进行比较；执行6组仿真作为评价，前5组在无障碍物环境下进行，最后一组在有障碍物环境中进行；表1所示为仿真的详细参数设置。

表1 仿真参数设置

2.3 仿真结果

图7(a)所示为对于不同信标间隔的随机信标广播机制和周期性信标广播机制的平均定位误差。可见，减小信标间隔可以提高两种机制的定位精度，且在信标间隔小于0.5 s后，随机性广播机制的定位误差急剧下降，采用0.1 s的信标间隔，定位误差小于1 m。这是由于随机信标广播机制改善了信标碰撞问题，从而提高了定位精度；图7(b)所示为两种广播机制的平均执行时间。可见，随机广播机制的平均执行时间相比于周期性广播机制平均减少了约60 s。这是因为前者较少的碰撞数量会产生较少的信息丢失，所以收集合适信标点的时间就缩短了，从而减少了定位所需的执行时间；图7(c)所示为两种广播机制的信标开销。可见，两种机制的信标开销都随着信标间隔的减小而增大。通常，周期性广播机制需要更多的信标消息，所以信标开销增加了。

图7 两种信标广播机制的性能比较

表2所示为对于5个不同的弦长度阈值(为无线电范围R的0%～50%)得到的性能，0%表示弦长度没有限制，对于一条有效的弦，它的长度必须超过阈值。从表2可见，随着弦长度的增加，定位误差迅速下降。当阈值大于R的20%时，定位误差小于1 m，当阈值为R的50%时，定位误差进一步改善为0.5 m左右。可见，弦的选择确实可以提高定位方案的性能；从表2还可看到，随着弦阈值的增大，平均执行时间略有增加，是因为需要收集更多的信标点来构造合适的弦；信标开销与执行时间有关，因此设置更高的阈值也会引起所需信标数据包数量的增加。根据表2的结果，合适的阈值约为R的30%～40%。后面的仿真采用30%的R作为弦的阈值。

表2 不同弦阈值的性能

表3所示为对于4个不同R时3种方案的性能比较。可见，文献[9]和文献[14]方案的定位误差随着R的增大而增大，相反，由于更长的弦，本文方案的定位误差随着R的增大只是略有增大，而且相比于文献[9]和文献[14]方案的定位误差分别平均改进了约86%和80%；当R从10 m增大到25 m时，3种方案的执行时间都减小。这是因为随着传输范围R的扩大，信标信息可以被更多的传感器节点监听到，因此，传感器节点在收集信标消息上花的时间更少；由于定位时间的减少，3种方案所需的信标开销也降低了；但与其它两种方案相比，本文方案所需的执行时间和信标开销相比于文献[9]和文献[14]方案，分别平均改进了约67.5%和77%。

表3 锚点的不同无线电范围R时的性能比较

表4所示为3种方案随锚点数量变化的性能。可以看到，本文方案在定位误差、执行时间和信标开销等方面都获得了最佳性能，且3种方案的定位误差受锚点数量变化的影响很小。显然，锚点数量的增加有助于减少执行时间，且更多的锚点广播的信标消息越多，传感器越容易获得足够的信标消息来定位，所以信标开销也大大减少。

表4 不同锚点数量时的性能比较

表5所示为无障碍物环境和有4个障碍物环境中本文方案的性能。可以看到，当环境中的参考信标点数量为3时，定位误差从0.74 m上升到3.82 m，执行时间和信标开销也增大了；当在有4个障碍物环境中采用增强信标选择机制时，如果有更多的参考信标点参与，则可以有效地降低平均定位误差，但增强信标选择机制需要更多的执行时间和信标消息来容许障碍物的存在。

表5 无障碍物环境和有障碍物环境时的性能比较

3 结束语

本文研究了不采用距离或角度信息的无需测距定位算法来实现传感节点的高精度定位。基于基本的几何原理和移动锚点的位置信息，传感器节点无需要额外的交互就能计算出它们的位置，且所有计算都在局部进行，信标开销仅发生在移动锚点上；为进一步提高方案性能，还提出了包括随机信标调度、弦的选择和高级信标点选择的增强措施；结果表明，提出的定位方案在定位误差、执行时间和信标开销等方面优于其它无需测距的定位方案。