CN104735778B - 一种计算未知节点的可能位置区域的切分定位方法 - Google Patents

Abstract

本发明公开了一种计算未知节点的可能位置区域的切分定位方法，方法为：未知节点收集其n跳以内的所有锚点邻居的信息；选择一个切分方向，求出这些锚点邻居相对于自己的虚拟辐射范围边界的两条切线之间的区域的交叠区域，得到未知节点的初始可能位置区域；换一个切分方向，再求所有虚拟辐射范围边界的两条切线之间的区域的交叠区域，然后利用该区域的两条边界切线去切分未知节点的当前可能位置区域得到更新的可能位置区域；重新选择一个切分方向，重复执行上一步N次；将未知节点可能位置区域的质心作为该未知节点的估计位置。本发明简化了对未知节点可能位置区域的计算复杂度和计算过程。计算结果特别接近于理论计算值，能够实现分布式计算。

Description

一种计算未知节点的可能位置区域的切分定位方法

技术领域

本发明涉及无线网技术领域，特别是一种计算未知节点的可能位置区域的切分定位方法。

背景技术

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

在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算法只利用了未知节点的一跳锚点邻居，其定位精度和定位覆盖率都不高，且Bounding-Box计算其未知节点可能位置区域的简化方法使其定位精度与理论精度有较大偏差。

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

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

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

综上， Bounding Box，DV-HOP，APIT等方法定位精度都不高且定位覆盖率也不能完全满足应用需要，SOM的定位覆盖率虽然有提高，但不能实现分布式计算，且由于需要收集全网络节点间的跳数信息，通信量大，计算复杂。且Bounding-Box和APIT对未知节点可能位置区域的计算方法都有不足，因此，本发明开发了计算未知节点可能位置区域的新方法，很适合于工程应用。

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

发明内容

本发明的发明目的在于：针对上述存在的问题，提供一种计算未知节点的可能位置区域的切分定位方法。该方法特别适用于无线传感器网络节点定位的工程应用，能够减少未知节点计算其可能位置区域（缩写为PLA）的计算复杂性，且能够提高节点的定位精度。

本发明采用的技术方案是这样的：

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

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

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

概括地说，本发明方法包括：通过引入未知节点的k跳锚点邻居相对于的虚拟辐射范围（其值表示为）这一概念，从而将定位问题转化为求该未知节点的所有n跳以内的锚点邻居相对未知节点的虚拟辐射范围的交叠区域的问题。这个交叠区域就是未知节点在当前时刻只可能出现的可能位置区域（缩写为PLA），当前时刻未知节点不可能出现在该区域以外的地方。该可能位置区域可以表示为。

一种计算未知节点的可能位置区域的切分定位方法，包括以下步骤：

步骤一，收集某个未知节点的n跳以内的全部锚点邻居的位置信息，并根据每个锚点邻居距离该未知节点的实际跳数k（k≤n）确定其相对于该未知节点的虚拟辐射范围的半径为kR，其中，R是所有节点的实际辐射半径的最大值；

在无线网络中，首先要将各锚点的位置信息嵌入邻居发现信息中，以便在利用现有邻居发现算法实现邻居发现的同时，实现对锚点的位置信息的传递。也就是说，让所有未知节点在获知自己的锚点邻居距离自己的跳数的同时，还能够获知这些锚点邻居的具体位置坐标。

在计算时，选定的n值越大，当然定位精度就越高，但是系统的成本就越高。一般情况下，n值设置为2～5即可。

步骤二，选择一个切分方向，在该切分方向上求出该未知节点的每个锚点邻居相对于该未知节点的虚拟辐射范围边界的两条切线，再求出这两条切线之间所组成的区域，最后求出所有虚拟辐射范围边界所对应的两条切线之间所组成的区域的交叠区域，初步得到未知节点的初始可能位置区域；

这时，该未知节点所得交叠区域的两条边界切线是所选切分方向上距离未知节点最近的两条切线。

步骤三，换一个切分方向，求出每个锚点邻居相对于该未知节点的虚拟辐射范围的边界的两条切线，再求出所有这些虚拟辐射范围的边界的两条切线所组成的区域的交叠区域。同样，该步骤所得交叠区域的两条边界切线也是所选切分方向上距离未知节点最近的两条切线。

步骤四，利用步骤三所得交叠区域的两条边界切线去切分未知节点的当前可能位置区域得到未知节点更新的可能位置区域。

步骤五，重新选择切分方向，重复执行步骤三和步骤四N次（N≥0），直到得到满意的未知节点可能位置区域为止。切分次数越多，未知节点可能位置区域将越趋近于理论值。

切分方向可以事先预设好，则步骤五按照预设的所有方向都执行一遍之后即可停止重复。

对切分方向的选择很灵活，比如：可依次选择0度、90度、45度、135度、22.5度、67.5度、112.5度……；也可以将0度到180度（或者360度）范围进行等间隔划分，然后按照递增或者递减方式一次设置切分方向等。

对未知节点的可能位置区域的切分次数越多，该可能位置区域的面积就越趋近于理论值，同时，未知节点的定位也就越精确。

步骤六，将计算所得的未知节点可能位置区域的质心作为该未知节点的估计位置。

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

1、本发明是一个分布式计算方法，特别适用于工程应用，可简化未知节点计算自己的可能位置区域的计算复杂度和计算过程；

2、本发明计算所得的未知节点的可能位置区域特别接近于理论计算值，因为随着所选切分次数的增加，切分所得的可能位置区域将收敛于理论计算值；

3、本发明可以基于定位精度要求设置不同的跳数n；

4、本发明对切分方向的选择很灵活。

附图说明

图1为实施例1通过未知节点收集周围锚点邻居的位置信息的效果图；

图2为实施例1在0度方向上利用切分方法进行切分的效果图；

图3为实施例1在0度方向和90度方向上利用切分方法进行切分的效果图；

图4为实施例1在0度、90度、45度和135度方向上利用切分方法进行切分的效果图；

图1-4中的标记：U₁为未知节点， R为节点的真实辐射范围的辐射半径的最大值，anchor为锚点邻居，unknown为未知节点。

具体实施方式

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

实施例1：

一种计算未知节点的可能位置区域的切分定位方法，包括以下步骤：

步骤一，收集某个未知节点U₁的3跳以内的全部锚点邻居的位置信息以及距离未知节点U₁的跳数信息，并根据每个锚点邻居距离未知节点U₁的实际跳数k（1≤k≤3）确定其相对于未知节点U₁的虚拟辐射范围的半径为kR，其中，R是所有节点的实际辐射范围的辐射半径的最大值；本实施例中的锚点邻居的位置信息如图1所示。

步骤二，选择0度切分方向，在该切分方向上求出三个锚点邻居相对于未知节点U₁的虚拟辐射范围边界的两条切线，再求出两条切线之间所组成的区域，最后求出所有虚拟辐射范围边界对应的两条切线所组成区域的交叠区域，初步得到U₁的初始可能位置区域，如图2所示。

步骤三，换90度切分方向，求每个锚点邻居相对于未知节点U₁的虚拟辐射范围边界的两条切线，再求出所有这些虚拟辐射范围边界对应的两条切线所组成的区域的交叠区域；

步骤四，利用步骤三所得交叠区域的两条边界切线去切分未知节点U₁的当前可能位置区域得到未知节点U₁的更新的可能位置区域，如图3所示。

步骤五，重新选择切分方向，重复执行步骤三和步骤四2次，两次重复时步骤三分别选择45度切分方向和135度切分方向，如图4所示。

步骤六，将计算所得的未知节点U₁的可能位置区域的质心作为未知节点U₁的估计位置。

因最后所得未知节点U₁的可能位置区域是一个凸多边形，因此，可通过求取该凸多边形的所有顶点的x坐标的平均值和y坐标的平均值代替质心算法得到U₁的估计位置。

实施例2：

一种计算未知节点的可能位置区域的切分定位方法，包括以下步骤：

步骤一，收集未知节点U₁的3跳以内每个锚点邻居的位置信息以及距离U₁的跳数信息，并根据每个锚点邻居的实际跳数k（1≤k≤3）确定其相对于未知节点U₁的虚拟辐射范围的半径为kR，其中，R是所有节点的实际辐射范围的辐射半径的最大值；本实施例中的锚点邻居的位置信息如图1所示。

步骤二，选择0度切分方向，在该切分方向上求出每个锚点邻居相对于未知节点U₁的虚拟辐射范围边界的两条切线，再求出两条切线之间所组成的区域，最后求出所有虚拟辐射范围边界对应的两条切线所组成区域的交叠区域，初步得到未知节点U₁的初始可能位置区域，如图2所示。

步骤三，换90度切分方向，求每个锚点邻居相对于未知节点U₁的虚拟辐射范围边界的两条切线，再求出所有这些虚拟辐射范围边界的两条切线所组成的区域的交叠区域；

步骤四，利用步骤三所得交叠区域的两条边界切线去切分未知节点U₁的当前可能位置区域得到未知节点U₁的更新的可能位置区域，如图3所示；

步骤五，重复执行步骤三和步骤四0次；

步骤六，将计算所得的未知节点U₁的可能位置区域的质心作为未知节点U₁的估计位置。

因最后所得未知节点U₁的可能位置区域是一个凸多边形，因此，可通过求取该凸多边形的所有顶点的x坐标的平均值和y坐标的平均值代替质心算法得到U₁的估计位置。

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

Claims (5)

1.一种计算未知节点的可能位置区域的切分定位方法，其特征在于包括以下步骤：

步骤一，未知节点收集自己的n跳以内的全部锚点邻居的位置信息，并根据每个锚点邻居距离该未知节点的实际跳数k（1≤k≤n）确定其相对于该未知节点的虚拟辐射范围的半径为kR，其中，R为所有节点的真实辐射范围的辐射半径的最大值；

步骤二，选择一个切分方向，在该切分方向上求出该未知节点的每个锚点邻居的虚拟辐射范围边界的两条切线，再求出这两条切线之间所组成的区域，最后求出所有这些虚拟辐射范围边界所对应的两条切线之间所组成的区域的交叠区域，初步得到未知节点的初始可能位置区域；

步骤三，换一个切分方向，求每个锚点邻居相对于该未知节点的虚拟辐射范围边界的两条切线，再求出所有这些虚拟辐射范围边界的两条切线所组成的区域的交叠区域；

步骤四，利用步骤三所得交叠区域的两条边界切线去切分未知节点的当前可能位置区域得到未知节点更新的可能位置区域；

步骤五，重新选择切分方向，重复执行步骤三和步骤四N次（N≥0），直到得到满意的未知节点可能位置区域为止；

步骤六，将计算所得的未知节点可能位置区域的质心作为该未知节点的估计位置。

2.根据权利要求1所述的一种计算未知节点的可能位置区域的切分定位方法，其特征在于：所述步骤三和步骤四共执行一次。

3.根据权利要求2所述的一种计算未知节点的可能位置区域的切分定位方法，其特征在于：所述步骤二的切分方向选择0度，所述步骤三的切分方向选择90度。

4.根据权利要求1所述的一种计算未知节点的可能位置区域的切分定位方法，其特征在于：所述步骤三和步骤四共执行三次。

5.根据权利要求4所述的一种计算未知节点的可能位置区域的切分定位方法，其特征在于：所述步骤二的切分方向选择0度，所述步骤三的切分方向选择90度，所述步骤三在两次重复执行时的切分方向分别选择45度和135度。