一种未知节点利用多跳锚点邻居对其自身进行定位的方法

摘要

本发明公开了一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，步骤为：未知节点收集距离自己n跳以内的全部锚点邻居的位置信息以及跳数信息，并据此确定其每个锚点邻居相对于自己的虚拟辐射范围；未知节点将整个网络区域作为自己的初始可能位置区域；未知节点遍历自己的所有锚点邻居，分别求出这些锚点邻居相对于自己的虚拟辐射范围与自己的当前可能位置区域的交叠区域作为自己的更新的可能位置区域；未知节点计算出自己最后得到的可能位置区域的质心坐标作为估计位置。本发明的有益效果：定义了可能位置区域和虚拟辐射范围的概念；利用未知节点的多跳锚点邻居来参与定位，从而大幅提高了未知节点的定位精度，使定位覆盖率达到100%。

权利要求

1.一种未知节点利用其多跳锚点邻居对自己进行定位的方法，其特征在于包括如下步骤：

步骤一、未知节点收集距离自己2跳以内的全部锚点邻居的位置信息以及跳数信息k，并据此确定其每个锚点邻居相对于自己的虚拟辐射范围，1≤k≤2；

步骤二、未知节点将整个网络区域作为自己的初始可能位置区域；

步骤三、未知节点用自己的当前可能位置区域与某一锚点邻居相对于自己的虚拟辐射范围求交叠区域，未知节点用该交叠区域作为自己的新的可能位置区域；未知节点再利用自己的新的可能位置区域与下一个锚点邻居相对于自己的虚拟辐射范围求交叠区域,未知节点用该交叠区域作为自己的更新的可能位置区域；未知节点重复这一过程，从小跳数到大跳数依次遍历自己的所有锚点邻居，分别求出这些锚点邻居相对于自己的虚拟辐射范围与自己的当前可能位置区域的交叠区域作为自己的更新的可能位置区域；

步骤四、未知节点计算出自己最后得到的可能位置区域的质心坐标，并以该质心坐标作为自己的估计位置；

其中某个锚点 相对于某个未知节点 的虚拟辐射范围是一个圆范围，该圆的中心坐标就是 所在的位置坐标，该圆的半径是kR；

其中k是 到 的跳数，R是所有节点的实际辐射半径的最大值。

2.根据权利要求1所述的一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，其特征在于：当未知节点采用8051单片机时，将距离自己为k跳的锚点邻居相对于自己的虚拟辐射范围设定为以该锚点邻居所在处为中心、边长为2kR的正方形区域，该正方形区域的边与x轴或y轴平行，则最后得到的该未知节点的可能位置区域为所有锚点邻居的正方形区域的交叠区域，其中，R为所有节点的真实辐射范围的半径的最大值。

3.根据权利要求1所述的一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，其特征在于：当未知节点采用16位或32位单片机时，则先将整个无线网络区域划分成密集的网格并给每个网格赋予一个唯一编号，则最后得到的该未知节点的可能位置区域为在每个锚点邻居相对于该未知节点的虚拟辐射范围内都出现过的网格的集合。

4.根据权利要求1所述的一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，其特征在于：当未知节点采用ARM类型的处理器时，所述锚点邻居相对于该未知节点的跳数为k，则将该锚点邻居相对于该未知节点的虚拟辐射范围设为半径为kR的圆范围，R是所有节点的真实辐射范围的半径的最大值，最后所得的未知节点的可能位置区域则为若干条圆弧所围成的凸多边形区域，将该凸多边形区域中每条圆弧的两个端点直接相连，从而形成一个凸多边形。

5.根据权利要求2、3或4所述的一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，其特征在于：取未知节点最后得到的可能位置区域的所有顶点的x坐标的平均值和y坐标的平均值代替质心算法得到未知节点的估计位置。

说明书

一种未知节点利用多跳锚点邻居对其自身进行定位的方法

技术领域

[0001] 本发明涉及无线网络技术领域，特别是一种在无线网络中未知节点利用其多跳锚点邻居对其自身进行定位的方法。

背景技术

[0002] 无线网和传感网在机场中的应用非常普遍，这些应用对位置信息的依赖也越来越严重，因此依托于这类网络的定位方法一直很受重视。目前，一般把无线传感器网络的节点定位算法分为两类：一类是基于测量距离(range-based）的定位方法；另一种是非测距（range-free）的定位方法。基于测距的定位方法虽然定位精度高，但一般需要专门的硬件来实现对节点间的距离或角度的测量，成本较高；而非测距定位方法虽然定位精度有限，但由于不需要额外的硬件支撑，因此成本较低。由于不同的应用对定位精度有不同的要求，非测距定位算法能够满足很多应用系统对定位精度的要求，且其成本最低，因此这类算法越来越受到青睐。然而，现有非测距定位算法的定位精度都很有限，比如：Bounding-Box、DV-HOP、APIT、SOM等等，它们的定位精度都不高，这限制了这些方法在实际系统中的应用。

[0003] 在2002年由Simic 提出的Bounding-Box算法 (Simic S., and Sastry S.: ‘Distributed localization in wireless ad hoc networks’, UC Berkeley, Tech. Rep., UCB/ERL M02/26, 2002)属于非测距算法，通过求未知节点的直接锚点邻居的辐射范围的交集实现了对未知节点的定位。它首先将未知节点的直接锚点邻居的辐射范围简化为一个正方形，然后求出未知节点的所有直接锚点邻居的正方形辐射范围的重叠区域，并将重叠区域的中心作为未知节点的位置。Bounding-Box算法简化了定位计算，但是它的定位精度和定位覆盖率都不高。

[0004] DV-hop算法是Niculescu于2003年提出的非测距定位算法（Niculescu D. and Nath B.: ‘DV based positioning in ad hoc networks’ Telecommun. Syst., 2003, 22, (1-4), pp. 267-280）。该算法由3个阶段组成：首先，通过邻居发现算法让每个锚节点获得除自己以外的其他每一个锚节点距离自己的跳数，并让每个未知节点获得每一个锚节点距离自己的跳数；其次，每个锚节点分别计算除自己以外的其他每一个锚节点到自己的平均每跳距离，并将该信息发送给它周边的未知节点，未知节点则以距离自己的跳数最少且最先收到消息的锚点计算所得的平均每跳距离作为各锚点到自己的平均每跳距离，并乘以相应的跳数得到各锚点距离自己的估计距离；最后使用三边测量法确定节点的位置。该方法的定位覆盖率得到了较大提高，但该方法所达到的定位精度也不高，应用范围有限。

[0005] APIT算法是Tian在2003年提出的非测距定位算法，并于2005年发表在ACM Trans.Embed. Comput. Syst上（He T., Huang C., Blum B.M., Stankovic, J.A., and Abdelzaher, T.F.: ‘Rangefree localization and its impact on large scale sensor networks’, ACM Trans.Embed. Comput. Syst., 2005, 4, (4), pp. 877-906.）。该算法首先收集未知节点所有邻居锚节点的信息，然后测试未知节点是否位于不同的三个锚节点组成的三角形内，计算所有包含该未知节点的三角形的重叠区域，最后用该区域的质心作为未知节点的坐标。该方法获得了较高的精度，但是其定位覆盖率有限。尤其对于那些不在任何由三个锚点组成的三角形内的未知节点，该方法无法定位。

[0006] SOM算法（Giorgetti, G., Gupta, S.K., and Manes, G.: ‘Wireless localization using selforganizing maps’. Intl. Conf. on Information processing in sensor networks, (IPSN), Cambridge, MA, USA, Aptil, 2007)）是Giorgetti在2007年提出的非测距定位算法。该算法利用全网络的节点间的跳数关系，并通过机器学习的方法实现了对节点的位置估计。该方法提高了定位覆盖率，且其定位精度也有大幅提升，但依然无法满足一些需要较高定位精度的应用，且该方法需要集中计算，通信开销和计算开销都较大。

[0007] 综上， Bounding Box，DV-HOP，APIT等方法定位精度都不高且定位覆盖率也不能满足应用需要，SOM的定位覆盖率虽然有提高，但不能实现分布式计算，且由于需要收集全网络节点间的跳数关系，通信量大，计算复杂。

[0008] 在民航领域，各种无线网的应用非常普及，许多应用需要较高精度的位置信息，但又不必花费专门硬件去实现精确定位，这就为无须任何辅助定位设备的适用于固定或者移动终端定位的非测距定位方法提供了广阔的应用空间。本发明正是在这样一种应用和需求背景下提出的。

发明内容

[0009] 本发明的发明目的在于：针对上述存在的问题，提供一种在无线网络中未知节点利用其多跳锚点邻居对其自身进行定位的方法，特别适用于无线传感器网络节点定位，不需要额外的硬件支持，可以较大幅度地提高定位精度和定位覆盖率。

[0010] 本发明将实际场景中部署的节点分为两类：一类是锚点，即已知自身位置坐标的节点，比如：带有GPS的节点，标记为 ；另一类是未知节点，即不知道自身位置坐标的节点，标记为 ，它们需要借助于某种定位方法来实现对自身的定位。本发明所指节点包含锚点（锚节点）和未知节点。

[0011] 本发明还给出了虚拟辐射范围（缩写为VRR其值表示为 ）的定义：某个锚点相对于某个未知节点 的虚拟辐射范围是这样一个圆范围——该圆的中心坐标就是所在的位置坐标，该圆的半径是kR。其中k是 到 的跳数，R是所有节点的实际辐射半径的最大值，通常所有节点（包括锚点和未知节点）的实际辐射半径取相同值。

[0012] 锚点的虚拟辐射范围是一个相对的概念，锚点只有相对于某个未知节点才具有虚拟辐射范围。对于不同的未知节点而言，同一锚点的虚拟辐射范围可能是不同的。此外，当某锚点是某未知节点的一跳邻居时，则该锚点相对于该未知节点的虚拟辐射范围就是其实际辐射范围。

[0013] 概括地说，本发明方法通过引入未知节点Ui的n跳锚点邻居Aj相对于该未知节点的虚拟辐射范围，从而将定位问题转化为求该未知节点的所有n跳锚点邻居相对于该未知节点的虚拟辐射范围的交叠区域的问题；这个交叠区域就是 在当前时刻只可能出现的可能位置区域（缩写为PLA），当前时刻 不可能出现在该区域以外的地方。该可能位置区域可以表示为 ，其值表示为 。最后求出交叠区域的质心坐标作为该未知节点的估计位置。

[0014] 本发明的方法具体如下：

[0015] 一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，包括如下步骤：

[0016] 步骤一、通过邻居发现技术，未知节点收集距离自己n跳以内的全部锚点邻居的位置信息以及跳数信息k（1≤k≤n），并确定这些锚点邻居相对于自己的虚拟辐射范围。

[0017] 步骤二、未知节点将整个网络区域作为自己的初始可能位置区域。

[0018] 步骤三、未知节点从小跳数到大跳数依次遍历自己的所有锚点邻居，分别求出这些锚点邻居相对于自己的虚拟辐射范围与自己的当前可能位置区域的交叠区域作为自己的更新的可能位置区域。

[0019] 步骤四、未知节点计算自己最后得到的可能位置区域的质心坐标，并以该质心坐标作为自己的估计位置。

[0020] 求未知节点的可能位置区域的第一种优选方法：当未知节点功能较弱时，比如：采用类似8051的普通单片机，未知节点将把距离自己k跳的锚点邻居相对于自己的虚拟辐射范围设定为以该锚点邻居所在处为中心、边长为2kR的正方形区域，该正方形区域的边与x轴或y轴平行。则最后得到的该未知节点的可能位置区域为其所有锚点邻居相对于自己的虚拟辐射范围（为正方形区域）的交叠区域。其中，R为所有节点的真实辐射范围的半径的最大值。

[0021] 求未知节点的可能位置区域的第二种优选方法：当未知节点的计算能力较强时，比如采用16位或32位单片机时，则先将整个无线网络区域划分成密集的网格并给每个网格赋予一个唯一编号，未知节点的每个锚点邻居相对于自己的虚拟辐射范围与自己的当前可能位置区域的交叠区域就是自己的更新的可能位置区域。则最后得到的该未知节点U1的可能位置区域为在其每个锚点邻居相对于自己的虚拟辐射范围内都出现过的网格的集合。

[0022] 求未知节点的可能位置区域的第三种优选方法：当未知节点采用功能强大的处理器时，比如ARM类型的处理器，当所述锚点邻居相对于该未知节点的跳数为k时，则将这些锚点邻居相对于该未知节点的虚拟辐射范围设为半径为kR的圆范围，圆心为这些锚点所在的位置坐标，R是所有节点的真实辐射范围的半径的最大值。则最后所得的未知节点的可能位置区域为若干条圆弧所围成的凸多边形区域，将该凸多边形区域中每条圆弧的两个端点直接相连，从而形成一个凸多边形。这种求未知节点的可能位置区域的方法虽然舍弃了部分扇形区域，但该方法的估计误差相对较低，因为它只在最后一步进行了合理的舍弃，并不影响之前的精确计算。

[0023] 优选其中一种求未知节点估计位置的方法：取未知节点最后得到的可能位置区域的所有顶点的x轴坐标的平均值和y轴坐标的平均值代替质心算法得到未知节点的估计位置。

[0024] 综上所述，由于采用了上述技术方案，本发明的有益效果是：

[0025] 1、定义了未知节点的可能位置区域和锚点相对于某个未知节点的虚拟辐射范围的概念，从而让未知节点可以利用其n跳锚点邻居相对于自己的虚拟辐射范围来大幅提高自己的定位精度；

[0026] 2、利用了未知节点的多跳锚点邻居来参与定位，从而能够对网络中的所有非孤立节点提供定位，让定位覆盖率达到100%；

[0027] 3、可以基于精度要求和未知节点的具体设备性能差异采用比较灵活的多种方法求各个锚点邻居相对于未知节点的虚拟辐射范围之间的交集。

附图说明

[0028] 图1是本发明实施例1所述方法的示意图。

[0029] 图2是本发明实施例2所述方法的示意图。

[0030] 图3是本发明实施例3所述方法的示意图。

[0031] 图中标记：A1 、A2、A3为未知节点U1的2跳以内的锚点邻居，anchor为锚点邻居，unknown为未知节点。

具体实施方式

[0032] 下面结合附图，对本发明作详细的说明。

[0033] 实施例1：

[0034] 一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，包括如下步骤：

[0035] 步骤一、未知节点U1收集距离自己2跳以内的所有锚点邻居的位置信息以及跳数信息k（1≤k≤2），并根据每个锚点邻居距离自己的实际跳数确定其相对于自己的虚拟辐射范围。收集到的距离自己2跳以内的锚点邻居为A1、A2、A3。

[0036] 在本实施例中，未知节点U1采用功能较弱的普通单片机时，比如8051单片机，将距离未知节点U1的k跳锚点邻居相对于U1的虚拟辐射范围设定为以该锚点邻居所在处为中心、边长为2kR的正方形区域，该正方形区域的边与x轴或y轴平行，其中，R为所有节点的真实辐射范围的半径的最大值。

[0037] 步骤二、未知节点U1将整个网络区域作为自己的初始可能位置区域。

[0038] 步骤三、未知节点从小跳数到大跳数依次遍历自己的所有锚点邻居，分别求出这些锚点邻居相对于自己的虚拟辐射范围与自己的当前可能位置区域的交叠区域作为自己的更新的可能位置区域。最后得到的该未知节点U1的可能位置区域为所有锚点邻居相对于自己的虚拟辐射范围（为正方形区域）的交叠区域。最后效果如图1所示。

[0039] 步骤四、未知节点U1计算出自己最后得到的可能位置区域的质心坐标，并以该质心坐标作为自己的估计位置。

[0040] 本实施例中求未知节点估计位置的方法：取未知节点最后得到的可能位置区域的所有顶点的x坐标的平均值和y坐标的平均值代替质心算法得到未知节点的估计位置。

[0041] 实施例2：

[0042] 一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，包括如下步骤：

[0043] 步骤一、未知节点U1收集距离自己2跳以内的所有锚点邻居的位置信息以及跳数信息k（1≤k≤2），并根据每个锚点邻居距离自己的实际跳数确定其相对于自己的虚拟辐射范围。收集到的距离自己2跳以内的锚点邻居为A1、A2、A3。

[0044] 在本实施例中，未知节点U1采用功能较强的单片机时，比如16位或32位单片机等，先将整个无线网络区域划分成密集的网格并给每个网格赋予一个唯一编号。

[0045] 步骤二、未知节点U1将整个网络区域作为自己的初始可能位置区域。

[0046] 步骤三、未知节点从小跳数到大跳数依次遍历自己的所有锚点邻居，分别求出这些锚点邻居相对于自己的虚拟辐射范围与自己的当前可能位置区域的交叠区域作为自己的更新的可能位置区域。最后得到的该未知节点U1的可能位置区域为在其每个锚点邻居相对于自己的虚拟辐射范围内都出现过的网格的集合。最后效果如图2所示。

[0047] 步骤四、未知节点U1计算出自己最后得到的可能位置区域的质心坐标，并以该质心坐标作为自己的估计位置。

[0048] 本实施例中求未知节点估计位置的方法：取未知节点最后得到的可能位置区域的所有顶点的x坐标的平均值和y坐标的平均值代替质心算法得到未知节点的估计位置。

[0049] 实施例3：

[0050] 一种未知节点利用其多跳锚点邻居对其自身进行定位的方法，包括如下步骤：

[0051] 步骤一、未知节点U1收集距离自己2跳以内的所有锚点邻居的位置信息以及跳数信息k（1≤k≤2），并根据每个锚点邻居距离自己的实际跳数确定其相对于自己的虚拟辐射范围。收集到的距离自己2跳以内的锚点邻居为A1、A2、A3。

[0052] 在本实施例中，未知节点U1采用功能强大的ARM类型的处理器等，所述其锚点邻居距离未知节点U1的跳数为k，则将这些锚点邻居相对于未知节点U1的虚拟辐射范围设为半径为kR的圆范围，圆心为这些锚点所在的位置，R是所有节点的真实辐射范围的半径的最大值。

[0053] 步骤二、未知节点U1将整个网络区域作为自己的初始可能位置区域。

[0054] 步骤三、未知节点从小跳数到大跳数依次遍历自己的所有锚点邻居，分别求出这些锚点邻居与自己的当前可能位置区域的交叠区域作为自己的更新的可能位置区域。

[0055] 最后所得的未知节点U1的可能位置区域则为若干条圆弧所围成的凸多边形区域，将该凸多边形区域中每条圆弧的两个端点直接相连，从而形成一个凸多边形。最后效果如图3所示。这种求未知节点U1的可能位置区域的方法虽然舍弃了部分扇形区域，但该方法的估计误差相对较低，因为它只在最后一步进行了合理的舍弃，并不影响之前的精确计算。

[0056] 步骤四、未知节点U1计算出自己最后得到的可能位置区域的质心坐标，并以该质心坐标作为自己的估计位置。

[0057] 本实施例中求未知节点估计位置的方法：取未知节点最后得到的可能位置区域的所有顶点的x坐标的平均值和y坐标的平均值代替质心算法得到未知节点的估计位置。

[0058] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。