0 引言

无线传感器网络(wireless sensor network,WSN)被誉为21世纪最有影响力的21项技术和改变世界的10大技术之一^[1-3]。无线传感器网络是由部署在监测区域的大量微型、低成本、低功耗的传感器节点组成的多跳无线网络,旨在实现网络覆盖区域内敏感数据的采集、处理和传输^[4]。此外,利用节点位置信息还可提高网络的覆盖质量和路由效率,实现网络的负载均衡及网络拓扑的自配置^[5]。节点定位的精准度在无线传感器网络中起关键性作用,目前的节点定位算法根据实际测量和计算节点间的距离,可划分为基于测距的定位机制^[6-7]和与距离无关的定位机制^[8-9]。基于测距的定位机制主要有基于到达时间、基于到达时间差、基于到达角度、基于接收信号强度指示等^[10]。目前主要的测距技术有:RSSI(received signal strength indication)、TOA(time of arrival) 、AOA(angle of arrival)和贝叶斯滤波^[11]。基于TOA的系统对定时的精度和时间同步性要求很高,导致系统的复杂度增加;基于AOA的系统在天线序列上要求非常高;贝叶斯侧重于过滤法高。相比之下,基于RSSI测距技术是低成本和低复杂度的^[12]。

DV-distance算法属于分布式定位算法,定位原理依赖于测距技术和距离矢量路由协议。文献^[13]中的试验表明:在网络平均连通度为9,锚节点(已知节点)比例为10％,测距误差小于40％的各向同性网络中平均定位精度可以达到30％,这对于WSN定位应用是足够的^[13]。该算法最大的缺点是在实际应用中需要进行多方面的约束。

SBL^[14](sequence-based location)定位算法能够取得一定的定位精度,但是该算法在定位序列表的建立、存储和比对上耗时过多,此算法需要M⁴ (M为锚节点个数)个定位序列表,在计算复杂度方面高达O(n^m) (m为锚节点数量)^[15]。朱剑等人提出的FTML定位模型,把模糊数学中的贴近度概念与节点定位相结合,对定位算法做了局部优化^[16]。该定位模型具有一定的定位精度,但定位的前提是未知节点必须落在定位单元(本研究中的三角形)内部,然后没有解决未知节点在定位单元外时的问题。

无论采用何种定位方法,信标节点的数量和布局都直接影响定位的精度,但使用的信标节点越多,网络的成本和能耗等方面的开销就会增加,不符合 WSN 各方面的约束^[17]。在无线传感器网络中,由于 RSSI 信息不需要额外的代价就可以在信息的发送接收过程中获得^[18-19],所以RSSI被公认为是一种非常具有吸引力的定位信息。基于 RSSI 的定位算法可以分为基于经验拟合^[20-21]和基于经验值匹配^[22-28]两种。其中,基于RSSI的定位方法根据无限信号衰落和距离的关系,利用理论或经验模型获得距离信息^[29]。RSSI信号易受环境(反射,多径传播的影响),所以将RSSI值转化成距离的时候必然存在误差^[30]。

针对以上描述,本研究主要研究基于RSSI向量的定位算法。本研究选择四边形作为定位单元,适当扩大定位区域,使更多的未知节点落在定位单元内。与三角形定位单元比较,减小了节点在定位单元外部时,因为定位误差过大而造成对整体平均误差的影响。采取了内部定位和外部定位相结合的节点定位机制。如果未知节点落在四边形内部,采用图形内部的定位机制,借助中位线不断缩小未知节点所在区域求解未知节点坐标;如果未知节点落在四边形外部,通过求解两个共点三角形的公共顶点坐标,估算未知节点坐标。借助于向量相近度,寻找距未知节点最近的参考样本点,不断逼近未知节点真实坐标。

1 相关工作及问题 1.1 问题的提出

三角形质心或垂心等定位算法,采取不同划分方法来逐步缩小定位区域以取得一定的定位精度。这些算法执行的前提是未知节点在定位单元内部,有些没有区分节点在定位单元内部还是外部。例如FTLM定位模型和SBL算法,现对这些定位算法作如下分析。 图 1为节点在定位单位中的测量图,点P为待定位的未知节点,点A、B、C、D为距点P最近的4个参考锚节点。从图 1中可见,点P在四边形ABCD内部,在ABC外部。在图 1中,设定A点为坐标原点,B点坐标为(1,0),建立直角坐标系,可得到点C、D、P的坐标分别为:C(0.7,1) 、D (-0.8,0.6) 、P (0.4,0.8)。点P距离这4个节点的测距长度由小到大依次为C、A、B、D,因此点P接收到这4个锚节点的RSSI值由强至弱依次为C、A、B、D。

取P点接收到的RSSI值最强的3个锚节点C、A、B所形成的三角形为定位单元,且以其质心S作为P点的估算坐标。则P点估计坐标为

${{S}_{(x,y)}}=\frac{\left( {{x}_{A}}+{{x}_{B}}+{{x}_{C}} \right)}{3},\frac{\left( {{y}_{A}}+{{y}_{B}}+{{y}_{C}} \right)}{3}。$

(1)

由式(1)可计算出S_(X,Y)=(0.567,0.333),此时,估计坐标S与P点真实坐标所形成的定位误差L_-erro为估计位置与实际位置的距离,即如下:

${{L}_{-}}erro=\sqrt{{{\left( {{S}_{x}}-{{P}_{x}} \right)}^{2}}+{{\left( {{S}_{y}}-{{P}_{y}} \right)}^{2}}}=0.49596。$

(2)

通过上述分析,可以得出以下结论:在一个约为2m×1m的定位区域内,其误差约0.49596m。由于质心S一直处于ΔABC内部,节点P在ΔABC外部,这种定位即使迭代多次,P点的估算坐标依然偏离原始坐标,造成定位误差较大。

1.2 基于四边形的区域划分

选取距离未知节点最近的4个锚节点作为参考锚节点,把这4个锚节点所形成的四边形作为定位区域,通过面积约束关系确定待定位的未知节点在四边形内部还是外部。通过下面伪代码来确定未知节点P在定位单元的内部还是外部。

图 2为未知节点在定位单位内部的定位图,点P为待定位未知节点,设A点为坐标原点,建立直角坐标系,点A、B、C、D为距P最近的4个参考锚节点,则点A、B、C、D所围成的四边形为定位单元。四边形ABCD的两条对角线分别为线段AC和线段BD,这两条对角线相交于点O,因此点O作为新的参考样本点。通过以下面积约束公式(3),可确定未知节点P是在四边形ABCD内部,且在ΔDCO内部。

$\left\{ \begin{align} & {{S}_{四边形ABCD}}={{S}_{三角形ABP}}+{{S}_{三角形BCP}}+{{S}_{三角形CDP}}+{{S}_{三角形DAP}} \\ & {{S}_{三角形DCO}}={{S}_{三角形DPO}}+{{S}_{三角形CPO}}+{{S}_{三角形DCP}}。 \\ \end{align} \right.$

(3)

算法 1  确定未知节点的位置

输入  距离未知节点P_i最近的4个锚节点组成的点集N_i=｛N_iA,N_iB,N_iC,N_iD｝,分布在待定位区域的u个未知节点。

输出 

未知节点P在定位单元内部还是外部。

Begin:

FOR i=1∶u｛

IF(S_{四边形ABCD}=S_三角形ABP+S_三角形BCP+S_三角形CDP+S_三角形DAP

Execute Internal A;//内部定位机制算法

ELSE

Execute External B;//外部定位机制算法｝

End

如果未知节点在四边形ABCD内部,如图 2所示,则采取算法Internal A,缩小定位单元。

算法 2  Internal A

STEP 1  判断点P位于这4个三角形ΔABO、ΔBCO、ΔCDO、ΔDAO中的哪一个。

STEP 2  确定点P所属的三角形后,通过取该三角形每条边中点的方式,获得3个新的参考样本点。

STEP 3  再将未知节点P的RSSI向量和原有三角形顶点及新得到的3个参考样本点的RSSI向量作相近度比对,找出相近度最高的参考样本点,即距离P最近的3个参考样本点,此处得到E,G,C。

STEP 4  重复上述步骤,通过不断寻找新的定位三角形的边的中点的方式,得到距离未知节点P最近的参考样本点,进而不断缩小未知节点所在的微三角区域,图 2中点P最终被锁定在FMN中。

假设未知节点在四边形ABCD的外部,如图 3所示,采取算法External B,主要操作如下。

算法 3  External B

STEP 1  找到未知节点P的RSSI向量(由强至弱)中最强的两个点C点和D点,并与P自身组成ΔPDC。

STEP 2  找到未知节点P的RSSI向量中第一和第三的两个点C点和A点,并与P自身组成ΔPAC。

STEP 3  已知两个三角形的三边,则可以求解出三角形的面积。两个顶点坐标已知,再借助三角形面积公式可求得点P到对边的高。

STEP 4  分别对ΔPAC和ΔPCD做上述Step3的操作,即可求得两个共点三角形公共顶点P的坐标。

2 RSSI向量模型的建立 2.1 相近度的计算

为了更贴切地描述待定位节点的RSSI向量和参考样本点的RSSI向量之间的相似程度,准确地找到未知节点附近“最近”的参考样本点,设计了向量相近度。向量相近度定义如下:

定义 1  若有n维向量,

$\begin{align} & X=\left[ \begin{matrix} {{X}_{1}} & {{X}_{2}} & {{X}_{3}} & \cdots & {{X}_{i}} & \cdots & {{X}_{n}} \\ {{X}_{R1}} & {{X}_{R2}} & {{X}_{R3}} & \cdots & {{X}_{Ri}} & \cdots & {{X}_{Rn}} \\ \end{matrix} \right]\text{ },\text{ } \\ & Y=\left[ \begin{matrix} {{Y}_{1}} & {{Y}_{2}} & {{Y}_{3}} & \cdots & {{Y}_{j}} & \cdots & {{Y}_{n}} \\ {{Y}_{R1}} & {{Y}_{R2}} & {{Y}_{R3}} & \cdots & {{Y}_{Rj}} & \cdots & {{Y}_{Rn}} \\ \end{matrix} \right]\text{ }, \\ \end{align}$

$\forall $i,j且i∈[1,n],j∈[1,n]时,其中n为向量长度,如果(X_i=Y_j)且(i=j),则有sim(X_i,Y_j)=i×|X_Ri-Y_Rj|。如果(X_i=Y_j)且(i≠j),则有sim(X_i,Y_j)=(i+|i-j|)²×| X_Ri-Y_Rj|。那么,X和Y的向量相近度为

$sim=\sum\limits_{i=1,j=1}^{n}{sim\left( {{X}_{i}},{{Y}_{j}} \right)}。$

(4)

相近度sim∈(0,∞)第2行是值(RSSI绝对值)由小至大(由强至弱)排列的RSSI向量,第1行X_i和Y_j分别表示排序后的X_Ri和Y_Rj分别对应的序号。

X和Y的第二行向量值皆由小至大排列,第1行是第2行由小至大排序后对应序号变动后的序号排列。以向量X为基准,如果序号i处相应位置上Y的序号与X的相同,则赋其权值为i,再计算二者的距离差异值|X_Ri-Y_Rj|;如果不同,则赋其权值(i+|i-j|)²,再计算二者的距离差异值|X_Ri-Y_Rj|,此处权值是该位置上原有权值i与序号偏离值|i-j|之和的平方,这可在于使有差异的向量元素间的差异更明显,而距离差异值来源于相同序号处的距离之差。权值i越小,元素间距离差异|X_Ri-Y_Rj|越小,sim值越小,说明向量间差异越小,相近程度越高。反之,向量间差异越大,相近程度越低。

2.2 定位机制的实现

定理 1  对一个三角形的每条边取中点,则新得到的3个中点连同原三角形的3个顶点一起被称作参考样本点,这6个参考样本点各自所接收到所有锚节点的信号强度值所形成的RSSI向量具有唯一性。

证明  利用反证法。如图 4所示,假设两个不同的节点P₁和P₂有不同的位置坐标,但有等维等值的RSSI向量(这里锚节点个数为3,向量维数为3),设P₁(x,y),且P₁到锚节点A、B、C的距离分别为d_A1、d_B1、d_C1,节点P₂亦有d_A2、d_B2、d_C2。

根据shadowing理论模型^[8]有以下结论成立:当P₁和P₂拥有等维且等值的距离向量,那么P₁、P₂到任一相同锚节点的距离相等^[8]。因此以下等式成立:

$\left\{ \begin{gathered} \sqrt {{{\left( {x - {x_A}} \right)}^2} + {{\left( {y - {y_A}} \right)}^2}} = {d_{A1}}, \hfill \\ \sqrt {{{\left( {x - {x_B}} \right)}^2} + {{\left( {y - {y_B}} \right)}^2}} = {d_{B1}}, \hfill \\ \sqrt {{{\left( {x - {x_C}} \right)}^2} + {{\left( {y - {y_C}} \right)}^2}} = {d_{C1}}, \hfill \\ \left( {\begin{array}{*{20}{c}} x \\ y \end{array}} \right) = {\left( {\begin{array}{*{20}{c}} {2\left( {{x_A} - {x_C}} \right)}&{2\left( {{y_A} - {y_C}} \right)} \\ {2\left( {{x_B} - {x_C}} \right)}&{2\left( {{y_B} - {y_C}} \right)} \end{array}} \right)^{ - 1}} \cdot \hfill \\ \left( {\begin{array}{*{20}{c}} {{x_A}^2 - {x_C}^2 + {y_A}^2 - {y_C}^2 + {d_C}^2 - {d_A}^2} \\ {{x_B}^2 - {x_C}^2 + {y_B}^2 - {y_C}^2 + {d_C}^2 - {d_B}^2} \end{array}} \right)。 \hfill \\ \end{gathered} \right.$

(5)

由式(5)求得P₁点坐标有唯一解:

$\left\{ \begin{gathered} {d_{A1}} = {d_{A2}}, \hfill \\ {d_{B1}} = {d_{B2}}, \hfill \\ {d_{C1}} = {d_{C2}}。 \hfill \\ \end{gathered} \right.$

(6)

因此P₂点势必与P₁点拥有相同坐标,而这与题目已知假设矛盾,故原定理成立。证毕。

根据定理,后续定位算法中每一个参考样本点向量具有唯一性,也保证了其坐标唯一性。

未知节点在图形内部的定位机制如下:

(1) ΔDAO共有D、C、O、E、K、G 6个参考样本;

(2) 比对点P的RSSI向量和上述6个参考样本点的RSSI向量之间的相近度;

(3) 找到相近程度最高的参考样本点,即距其最近的点E、C、G。

同理,ΔEGC中距P最近的参考样本点为M、N、F。同样对ΔMFN做上述操作,可知点P在ΔLIM中。此时不再缩小微三角区域,LJH就是最终需要的定位单元,取ΔLJH质心作为待定位节点P。

未知节点在图形外部的定位机制如下:如图 3所示,P为待定位的未知节点,A、B、C、D为距P最近的4个参考锚节点,AC和BD是四边形ABCD的两条对角线,O为两条对角线交点(坐标可求得),被视为新的参考样本点。

根据四边形面积约束关系,等式不成立,可知点P在四边形ABCD外部。根据未知节点P接收到4个参考锚节点RSSI值强弱排序为C、D、A、B。

在ΔPCD中,锚节点C和点D的坐标已知,可测得每两点之间的RSSI值,通过信号衰减模型,即可求得每两点之间的距离(三角形三边),通过以下方程组求得未知节点坐标:

$\left\{ \begin{align} & L={{d}_{AD}}+{{d}_{DP}}+{{d}_{PA}}, \\ & {{S}_{\Delta PAD}}=\sqrt{\frac{L}{2}*(\frac{L}{2}-{{d}_{AD}})*(\frac{L}{2}-{{d}_{DP}})*(\frac{L}{2}-{{d}_{PA}})}, \\ & {{S}_{\Delta PAD}}=\frac{1}{2}{{d}_{AD}}*{{d}_{PO1}}, \\ & {{d}_{PO1}}=\frac{A*X+B*Y+C}{\sqrt{{{A}^{2}}+{{B}^{2}}}}。 \\ \end{align} \right.$

(7)

其中:L是三角形周长,S是三角形面积,d是三角形边长,方程A*X+B*Y+C=0是AD所在直线的直线方程。解方程组(7)即可求得未知节点的两组坐标P(X,Y)和P₁(X₁,Y₁)。

同理,选取RSSI向量里RSSI值第一和第三的点C和点A,其与 P点构成ΔPAC,求解出未知节点坐标P(X,Y)和P₁(X₂,Y₂)。结合这两组解,求解出两个三角形的公共顶点P的坐标P(X,Y)。

2.3 算法的设计

基于RSSI的节点定位,包括未知节点在图形内部和外部两种定位机制,结合RSSI相近度来寻找距离未知节点最近的参考样本点,估算未知节点坐标。算法伪代码如下:

算法 4  基于RSSI的定位

输入:

全部锚节点组成的点集N=｛N₁,…N_n｝;

u个布撒在待定位区域的未知节点。

输出:

未知节点P的估计坐标P(X,Y)。

Begin

FOR i=1∶u｛

Execute｛

点集合P_-N(i)←可与之通信的锚节点;

向量表P_-RSSI(i)←接收到的RSSI值;

P_-RSSI_-decend(i)←P_-RSSI(i)排降序;｝

Execute｛

取P_-RSSI_-decend(i)中前4个锚节点形成的闭合四边形S为初始定位单元,两条对角线将定位单元分为4个小三角形1、2、3、4;

IF (S_Δ1+S_Δ2+S_Δ3+S₄=S)｛

Execute Internal A;

取点P所在Δi面积为S_i;

WHILE (S_新>S_i/256)｛

Execute RE(j)←取三角形各边中点与原顶点;

向量表RE_-RSSI(j)←6个参考样本点接收到的RSSI值,j∈^{[1, 6]};

RE_-RSSI_-decend(j)←RE_-RSSI(j)降序排列,求P_-RSSI_-decend(i)和RE_-RSSI_-decend(j) 之间的相近度sim,取sim值最小的前3个点得到新的定位区域;｝//END-WHILE

Execute 质心法估算节点坐标;｝//END-IF

ELSE｛

Execute External B;｝

｝//END-FOR

End

本算法中形成点集和向量表时间复杂度为O(n) (n为锚节点数),在进行向量排序时采用插入排序法,其时间复杂度为O(n²)。在缩小区域时定位区域面积为1/64,时间复杂度为O(1),每定位一个未知节点,只需要和6个参考样本点各自的RSSI向量比对,时间复杂度为O(1)。所以本算法的时间复杂度O(n²+n+1)小于SBL^[7]中时间复杂度O(n⁶)。

对于初始面积为S的三角形定位单元,3条中位线将原三角形分为4个小三角形,其中3条中位线所组成的三角形称作中位三角形,这4个小三角形的面积均为S/4。所以,依照本研究的划分方法,每迭代定位一次,定位区域面积缩至S/4,增加3个新的参考样本点。划分至第4次时,未知节点所在区域面积就被限制为S/256,此时,需要16个参考样本点。每定位一个未知节点所需要的参考样本点数量见表 1。当步骤7重复次数为K时,节点所在区域面积被缩至S/4^k,显然有$\underset{K\to \infty }{\mathop{\lim }}\,S/{{4}^{k}}=0$,即这种迭代是收敛的。

3 试验仿真

为了更好地模拟真实环境,采用Shadowing模型将RSSI值转换为与之对应的距离值,并设定一定的测距误差模拟测量环境。取锚节个数N为8,未知节点u个数为160,所有节点皆具同构性,未知节点均随机均匀布撒在实验环境为10m×10m的矩形区域内,且所有锚节点均在未知节点的可通信范围内。图 5是锚节点数为8时所有节点布局图,从图中可以,锚节点和未知节点的分布具有一定的随机性,未知节点在实验区域内分布较为均匀。

3.1 误差分析

图 6~9表示定位误差(L_erro:Location Erro)、RSSI测量误差(Dis_mea_erro:Dismea Erro)、锚节点个数之间的变化关系。选取RSSI测量误差[31]在5％、10％、20％时分别进行仿真,为了测量平均定位误差的变化,把锚节点分别从8增至32进行试验。图中标有“圆圈”线条的高度均大于标有“叉号”线条的高度,即Dis_mea_erro=0.2时的定位误差大于Dis_mea_erro=0.05时,因此,L_erro随Dis_mea_erro增加而变大。

在未知节点总数u=160不变情况下,随着锚节点个数增加,图 6~9中所有同型线条图示高度均呈明显的下降态势。分析图 6~9中当Dis_mea_erro=0.2时标有“圆圈”的线条,当锚节点数N=8时,L_erro=0.5;当锚节点数N=32时,L_erro=0.24,定位误差降低约50％。表明随着锚节点数增加,定位误差明显降低,这是因为待定位区域内锚节点数越多,距离未知节点较近的锚节点数也就越多,所围成的四边形区域就越小,样本参考点就更靠近未知节点。

3.2 算法性能对比

为了验证本算法的有效性,选取了相同的定位区域(即:10m×10m)把本算法和序列三点垂心法^[7]、序列定位法及三点垂心法进行比较,试验结果如图 10所示。表 1给出了每定位一个未知节点,本算法和LTFM模型定位算法所需参考样本点数量比较,由表 1可知,定位微区域的面积相同时,本研究算法需要的参考样本点数目更少,计算量明显较低,而且通过面积缩小进行的迭代定位是收敛的。

分析图 10可知,3种定位算法的定位误差都随锚节点数量增多而减小,这是因为锚节点越多,原待定位区域即被分为不同类型的更小区域,未知节点更靠近锚节点,定位就越准确。当锚节点数为8时,三点垂心法定位误差约为本研究定位算法的5倍。分析原因,本算法在定位过程中,不断以1/4的比例缩小未知节点所在区域,能更好地恢复原节点的实际位置。当锚节点数为32时,本算法和序列三点垂心法、序列定位法的定位误差相差不大。分析原因,锚节点数增加为32时,序列定位法和序列三点垂心法的定位序列已增至462273($\frac{{{n}^{4}}}{2}-2\div {{n}^{3}}+\frac{7*{{n}^{2}}}{2}-2\times n+1$,(n=32) )个,未知节点所在区域已经非常小了。

4 结语

本研究提出了基于RSSI向量相近度的定位算法,当未知节点在内部时,采用四边形定位单元不断地缩小未知节点所在的区域,确定最近的3个参考样本点,并以其质心作为未知节点的估算坐标。当未知节点在图形外部时,采用几何数学方法,求得两个共顶点三角形的公共顶点坐标。在现实中定位还受到其他环节因素影响,本研究考虑的因素还不够全面,这些问题将在以后的研究中改进,今后还要考虑把本模型放置多维空间里进行验证。