基于区域自调整的WSN近似三角形内点测试定位方法

摘要

本发明涉及无线传感器网络中节点定位的技术领域，尤其是一种基于区域自调整的WSN近似三角形内点测试定位方法。其包括以下步骤：一、网络部署；二、获取邻居锚节点信息；三、邻居节点交换信息；四、第一轮定位，包括APIT方法定位和区域自调整的APIT方法定位；五、引入辅助节点定位；六、第二轮定位，针对步骤四未完成定位的节点采用区域自调整的APIT方法定位；七、定位完成。该方法根据网络连接情况，对节点的定位区域进行了调整，以减少不可定位节点数目及提高节点定位精度。在获得相同定位精度的要求下，区域自调整的APIT方法更能节省网络部署的成本。

权利要求

1.一种基于区域自调整的WSN近似三角形内点测试定位方法，其特征是，它包括以下步骤：一、网络部署；二、获取邻居锚节点信息；三、邻居节点交换信息；四、第一轮定位，包括APIT方法定位和区域自调整的APIT方法定位；五、辅助节点定位；六、第二轮定位，针对步骤四未完成定位的节点采用区域自调整的APIT方法定位；七、定位完成，所述第一轮定位包括以下步骤：（1）判断邻居锚节点数是否大于等于3，若满足继续（2）；不满足视为不可定位节点；

（2）继续判断邻居锚节点数是否大于阈值K，若满足继续（3）；不满足则采用区域自调整的APIT方法定位；

由于未知节点一定在其邻居锚节点的通信区域内，所以未知节点一定位于其三个邻居锚节点的通信区域的交叠区域，其中锚节点的通信区域是以锚节点为圆心、锚节点通信半径为半径的圆形区域；

然后再判断未知节点是否在三个邻居锚节点组成的三角形内部，若不在其内部，则选取邻居锚节点的通信区域的交叠区域的作为未知节点的定位区域，其质心作为未知节点的估计位置；若在其内部，则选取邻居锚节点组成的三角形区域与上述定位区域的交叠区域作为未知节点的定位区域，其质心作为未知节点的估计位置；

（3）接着判断未知节点是否在邻居节点组成的三角形内部，若满足继续（4）；不满足视为不可定位节点；

（4）上述步骤（1）（2）（3）均满足时，则采用APIT方法进行定位，

所述第二轮定位包括以下步骤：

（1）第一轮定位结束后记录下不能定位的节点；

（2）判断未知节点的邻居锚节点数与邻居辅助节点数之和是否大于等于3个，若满足，采用区域自调整的APIT方法定位；

选取各邻居锚节点的通信区域的交叠区域和邻居锚节点组成的三角形区域，将两者的交叠区域作为未知节点的定位区域，其质心为未知节点的估计位置；

（3）判断未知节点的邻居锚节点数与邻居辅助节点数之和是否大于等于3个，若不满足，引入辅助节点采用区域自调整的APIT方法进行定位；

首先选取辅助节点和邻居锚节点的通信区域的交叠区域以及辅助节点与邻居锚节点组成的三角形区域，将两者的交叠区域作为未知节点的定位区域，其质心作为未知节点的估计位置；其中将第二轮定位过程中未知节点的邻居锚节点中来源于第一轮定位成功的节点称为辅助节点。

2.根据权利要求1所述的基于区域自调整的WSN近似三角形内点测试定位方法，其特征是，所述网络部署指通过仿真器或搭建真实的网络场景，产生多跳的自组织的无线传感器网络拓扑，网络中的节点协作地感知、采集和处理网络覆盖区域中被感知对象的信息，网络拓扑中的节点包括普通节点和坐标信息已知的锚节点。

3. 根据权利要求1所述的基于区域自调整的WSN近似三角形内点测试定位方法，其特征是，所述获取邻居锚节点信息指网络中的节点具有获取邻居节点信息的能力，通过锚节点的通信传播过程，未知节点获取所有邻居锚节点的信息，包括锚节点的位置、标识号和信号强度。

4. 根据权利要求1所述的基于区域自调整的WSN近似三角形内点测试定位方法，其特征是，所述邻居节点交换信息指网络中所有节点都与自己的邻居节点交换信息，包括位置、标识号和信号强度。

5. 根据权利要求1所述的基于区域自调整的WSN近似三角形内点测试定位方法，其特征是，所述辅助节点定位指对于步骤四未完成定位的节点，引入辅助节点进行定位，辅助节点来源于第一轮定位成功的节点。

说明书

基于区域自调整的WSN近似三角形内点测试定位方法

技术领域

[0001] 本发明涉及无线传感器网络中节点定位的技术领域，尤其是一种基于区域自调整的WSN近似三角形内点测试定位方法。

背景技术

[0002] 无线传感器网络的大量应用都需要网络中节点的地理位置信息，如在军事战术中，士兵、战车等所携带的传感器节点的位置信息是作战指挥的关键依据，节点发回的战术信息都与该节点当时所处的位置有关。另外，了解传感器节点位置信息还可以提高路由效率，为网络提供命名空间，向部署者报告网络的覆盖质量，实现网络的负载均衡及网络拓扑的自配置。无线传感器网络的定位问题主要分为两类：(1)无线传感器网络对自身传感器节点的定位；(2)利用传感器节点对外部目标的跟踪定位，而节点自身的定位是实现外部目标跟踪定位的基础。现有的无线传感器网络节点定位方法都有各自的特点和应用范围，根据定位的需求，各方法在性能评价参数上各有取舍。综合考虑方法的各个性能评价参数，使节点的定位精度最优是定位方法的主要目标。定位方法的分类有很多种，根据定位过程中是否测量实际节点间的距离，可以把现有的定位方法主要分为两类：基于距离(Range-based)的定位方法和距离无关(Range-free)的定位方法。基于距离的定位方法利用RSSI、TDOA、TOA和AOA等技术测量节点之间的距离，然后用数学方法计算节点的坐标。基于距离的定位方法能够实现节点的精确定位，但对节点的硬件要求比较高，其硬件成本高、能耗高。现有的APIT定位方法存在的问题，包括两类不能进行定位的节点：第一类，邻居锚节点数大于等于3而不能进行定位的未知节点；第二类，邻居锚节点数小于3而不能进行定位的未知节点。

发明内容

[0003] 为了克服现有的APIT定位方法存在的问题，本发明提供了一种基于区域自调整的WSN近似三角形内点测试定位方法。

[0004] 本发明解决其技术问题所采用的技术方案是：一种基于区域自调整的WSN近似三角形内点测试定位方法，包括以下步骤：一、网络部署；二、获取邻居锚节点信息；三、邻居节点交换信息；四、第一轮定位，包括APIT方法定位和区域自调整的APIT方法定位；五、辅助节点定位；六、第二轮定位，针对步骤四未完成定位的节点采用区域自调整的APIT方法定位；七、定位完成。

[0005] 根据本发明的另一个实施例，进一步包括所述网络部署指通过仿真器或搭建真实的网络场景，产生多跳的自组织的无线传感器网络拓扑，网络中的节点协作地感知、采集和处理网络覆盖区域中被感知对象的信息，网络拓扑中的节点包括普通节点和坐标信息已知的锚节点。

[0006] 根据本发明的另一个实施例，进一步包括所述获取邻居锚节点信息指网络中的节点具有获取邻居节点信息的能力，通过锚节点的通信传播过程，未知节点获取所有邻居锚节点的信息，包括锚节点的位置、标识号和信号强度。

[0007] 根据本发明的另一个实施例，进一步包括所述邻居节点交换信息指网络中所有节点都与自己的邻居节点交换信息，包括位置、标识号和信号强度。

[0008] 根据本发明的另一个实施例，进一步包括所述第一轮定位包括以下步骤：

[0009] （1）判断邻居锚节点数是否大于等于3，若满足继续（2）；不满足视为不可定位节点；

[0010] （2）继续判断邻居锚节点数是否大于阈值K，若满足继续（3）；不满足则采用区域自调整的APIT方法定位；

[0011] 由于未知节点一定在其邻居锚节点的通信区域内，所以未知节点一定位于其三个邻居锚节点的通信区域的交叠区域，其中锚节点的通信区域是以锚节点为圆心、锚节点通信半径为半径的圆形区域；

[0012] 然后再判断未知节点是否在三个邻居锚节点组成的三角形内部，若不在其内部，则选取邻居锚节点的通信区域的交叠区域的作为未知节点的定位区域，其质心作为未知节点的估计位置；若在其内部，则选取邻居锚节点组成的三角形区域与上述定位区域的交叠区域作为未知节点的定位区域，其质心作为未知节点的估计位置；

[0013] （3）接着判断未知节点是否在邻居节点组成的三角形内部，若满足继续（4）；不满足视为不可定位节点；

[0014] （4）上述步骤（1）（2）（3）均满足时，则采用APIT方法进行定位。

[0015] 根据本发明的另一个实施例，进一步包括所述辅助节点定位指对于步骤四未完成定位的节点，引入辅助节点进行定位，辅助节点来源于第一轮定位成功的节点。

[0016] 根据本发明的另一个实施例，进一步包括所述第二轮定位包括以下步骤：

[0017] （1）第一轮定位结束后记录下不能定位的节点；

[0018] （2）判断未知节点的邻居锚节点数与邻居辅助节点数之和是否大于等于3个，若满足，采用区域自调整的APIT方法定位；

[0019] 选取各邻居锚节点的通信区域的交叠区域和邻居锚节点组成的三角形区域，将两者的交叠区域作为未知节点的定位区域，其质心为未知节点的估计位置；

[0020] （3）判断未知节点的邻居锚节点数与邻居辅助节点数之和是否大于等于3个，若不满足，引入辅助节点采用区域自调整的APIT方法进行定位；

[0021] 首先选取辅助节点和邻居锚节点的通信区域的交叠区域以及辅助节点与邻居锚节点组成的三角形区域，将两者的交叠区域作为未知节点的定位区域，其质心作为未知节点的估计位置；其中将第二轮定位过程中未知节点的邻居锚节点中来源于第一轮定位成功的节点称为辅助节点。

[0022] 本发明的有益效果是，该方法根据网络连接情况，对节点的定位区域进行了调整，以减少不可定位节点数目及提高节点定位精度。在获得相同定位精度的要求下，区域自调整的APIT方法更能节省网络部署的成本。本发明实现了对邻居锚节点数大于等于3而不能进行定位的未知节点和邻居锚节点数小于3而不能进行定位的未知节点进行高精度的定位。

附图说明

[0023] 下面结合附图和实施例对本发明进一步说明。

[0024] 图1是本发明的原理框图；

[0025] 图2（a）是采用区域自调整的APIT方法定位时未知节点在三角形外部的示意图，（b）是采用区域自调整的APIT方法定位时未知节点在三角形内部的示意图；

[0026] 图3是采用区域自调整的APIT方法定位时引入辅助节点的示意图；

[0027] 图4是节点数目对定位精度的影响；

[0028] 图5是节点数目对ELR的影响；

[0029] 图6是锚节点比重对定位精度的影响；

[0030] 图7是锚节点比重对ELR的影响；

[0031] 图8是节点DOI对定位精度的影响；

[0032] 图9是节点DOI对ELR的影响。

具体实施方式

[0033] 如图1是本发明的原理框图，一种基于区域自调整的WSN近似三角形内点测试定位方法，包括以下步骤：

[0034] 一、网络部署：通过仿真器或搭建真实的网络场景，产生多跳的自组织的无线传感器网络拓扑，网络中的节点协作地感知、采集和处理网络覆盖区域中被感知对象的信息，网络拓扑中的节点包括普通节点和坐标信息已知的锚节点；

[0035] 二、获取邻居锚节点信息：在待定位节点通信半径γ以内的节点即为该节点的一跳邻居节点；网络中的节点具有获取邻居节点信息的能力，通过锚节点的通信传播过程，未知节点获取所有邻居锚节点的信息，包括锚节点的位置、标识号和信号强度；

[0036] 三、邻居节点交换信息：网络中所有节点都与自己的邻居节点交换信息，包括位置、标识号和信号强度；

[0037] 四、第一轮定位：包括APIT方法定位和区域自调整的APIT方法定位；

[0038] 第一轮定位包括以下步骤：

[0039] （1）判断邻居锚节点数是否大于等于3，若满足继续（2）；不满足视为不可定位节点；

[0040] （2）继续判断邻居锚节点数是否大于阈值K，若满足继续（3）；不满足则采用区域自调整的APIT方法定位；

[0041] 由于未知节点一定在其邻居锚节点的通信区域内，所以未知节点一定位于其三个邻居锚节点的通信区域的交叠区域，其中锚节点的通信区域是以锚节点为圆心、锚节点通信半径为半径的圆形区域；

[0042] 然后再判断未知节点是否在三个邻居锚节点组成的三角形内部，若不在其内部，则选取邻居锚节点的通信区域的交叠区域的作为未知节点的定位区域，其质心作为未知节点的估计位置；若在其内部，则选取邻居锚节点组成的三角形区域与上述定位区域的交叠区域作为未知节点的定位区域，其质心作为未知节点的估计位置；

[0043] （3）接着判断未知节点是否在邻居节点组成的三角形内部，若满足继续（4）；不满足视为不可定位节点；

[0044] （4）上述步骤（1）（2）（3）均满足时，则采用APIT方法进行定位；

[0045] 五、辅助节点定位：对于步骤四未完成定位的节点，引入辅助节点进行定位，辅助节点来源于第一轮定位成功的节点；

[0046] 六、第二轮定位：针对步骤四未完成定位的节点采用区域自调整的APIT方法定位；

[0047] 第二轮定位包括以下步骤：

[0048] （1）第一轮定位结束后记录下不能定位的节点；

[0049] （2）判断未知节点的邻居锚节点数与邻居辅助节点数之和是否大于等于3个，若满足，采用区域自调整的APIT方法定位；

[0050] 选取各邻居锚节点的通信区域的交叠区域和邻居锚节点组成的三角形区域，将两者的交叠区域作为未知节点的定位区域，其质心为未知节点的估计位置；

[0051] （3）判断未知节点的邻居锚节点数与邻居辅助节点数之和是否大于等于3个，若不满足，引入辅助节点采用区域自调整的APIT方法进行定位；

[0052] 首先选取辅助节点和邻居锚节点的通信区域的交叠区域以及辅助节点与邻居锚节点组成的三角形区域，将两者的交叠区域作为未知节点的定位区域，其质心作为未知节点的估计位置；其中将第二轮定位过程中未知节点的邻居锚节点中来源于第一轮定位成功的节点称为辅助节点；

[0053] 七、定位完成。

[0054] RSA_APIT(region self-adjusting APIT)是指基于区域自调整的WSN近似三角形内点测试定位方法。

[0055] WSN是指无线传感器网络。

[0056] APIT定位方法是指近似三角形内点测试定位方法。

[0057] RSA_APIT定位方法是指区域自调整的APIT定位方法。

[0058] 如图2所示，三角形实心点表示锚节点，圆形实心点表示普通节点，锚节点的通信区域是以锚节点为圆心、锚节点通信半径αγ为半径的圆形区域。由于未知节点一定在其邻居锚节点的通信区域内，所以未知节点i一定在其邻居锚节点M、N、P通信区域的交叠区域内，即图中A区域。

[0059] 然后判断未知节点是否在锚节点M、N、P组成的三角形内部。若未知节点i不在三角形MNP内部或InToOut错误时，则A区域即为未知节点i的定位区域，即A区域的质心位置为未知节点i的估计位置，如图2(a)所示。若未知节点i在三角形MNP的内部，则用三角形MNP与A区域的交叠区域作为未知节点i的定位区域，即图2(b)中的B区域，B区域的质心即为未知节点i的估计位置。通过区域自调整技术可对邻居锚节点数小于阈值K的未知节点进行更加精确的定位。

[0060] 如图3所示，图中以K=3为例，图中三角形空心点表示辅助锚节点。

[0061] 首先对整个网络中的节点进行第一轮定位，记录下不能定位的节点j；然后判断未知节点j的邻居锚节点数与已经被定位的邻居节点数之和是否大于等于3个，如果未知节点j的邻居锚节点数与已经被定位的邻居节点数之和大于等于3个，则把已经定位的邻居节点当做辅助锚节点，应用区域自调整的APIT方法对未知节点j进行第二轮定位，否则未知节点视为不可定位节点。

[0062] 影响节点定位精度的因素很多，这里主要选择节点数目、锚节点比重和节点无线传输模式的不规则度作为仿真参数，观察这些参数变化对节点定位精度和节点有效定位比的影响。参数定义如下：

[0063] 节点数目定义为部署区域内的节点总数，包括普通节点和锚节点，用N表示；

[0064] 锚节点比重为锚节点数与节点数目的比例，用Ar表示；

[0065] 节点无线传输模式的不规则度定义为无线电波在传播方向上传播距离的最大变化范围，用DOI(Degree of Irregularity)表示。

[0066] 节点有效定位比定义为能够被定位的节点数(Nl)占节点数目的比例，即 ，用ELR表示。

[0067] 实验中具体的参数取值见表1。

[0068]

[0069] 图4和图5分别给出了节点数目对节点定位精度及ELR的影响。从图4中可以看出，随着节点数目的增加，该方法的定位精度在提高。这是由于随着节点数目的增加，未知节点的邻居锚节点数也在增加，采用RSA_APIT能够选取的定位区域更加精确。图5仿真结果显示节点有效定位比随着节点数目增加而增加。节点数目较低时，未知节点的邻居节点数目较少，RSA_APIT方法的区域自调整技术受到限制，能够引入辅助节点进行定位的节点数少，故节点有效定位比较低；随着节点数目的增加，RSA_APIT方法能够很好的调整未知节点的定位区域，并引入辅助节点进行定位，不能定位的节点数随之减少，即ELR增加直至逼近1。

[0070] 图6和图7显示了锚节点比重对节点定位精度和ELR的影响。仿真场景中的节点数目为200，锚节点比重从0.05逐渐增加到0.4。仿真结果显示，随着锚节点比重的增加，RSA_APIT方法的定位精度和节点有效定位比ELR都在增加。这是由于锚节点比重增加，能够选取的三角形数在增加，这些三角形的交叠区域也减小，另外随着锚节点比重的增加，使得InToOut错误和OutToIn错误发生的概率降低，RSA_APIT定位方法能够选取更加精确的定位区域，因此定位更加精确，能够定位的节点数也更多。

[0071] 为更充分地反映方法在实际应用中的性能，在仿真过程中引入了无线传输模式不规则度(DOI)。图8和图9反映了DOI对节点定位精度和ELR的影响。仿真结果图8反映了定位误差随着DOI的增加而逐渐增加，这是因为DOI的存在导致节点的通信区域不是理想的圆形区域，节点间的通信存在着不确定性，进而导致节点的定位误差增加。仿真结果图9表明了DOI对节点有效定位比ELR的影响不是太明显，在节点数目为200、锚节点比重为
0.2的场景下，RSA_APIT方法的ELR在0.9上下波动，能够较好地符合实际应用中的节点定位需求。