[發明專利]一種計算未知節點的可能位置區域的切分定位方法

在審

• 申請號: 201310705362.6
• 申請日: 2013-12-20
• 公開（公告）號: CN104735778A
• 公開（公告）日: 2015-06-24
• 發明（設計）人: 黃榮順;羅曉;羅謙;程華;張恂;湯永勝;李建斌;張揚;楊二雄;涂新
• 申請（專利權）人: 中國民用航空總局第二研究所
• 主分類號: H04W64/00
• 分類號: H04W64/00
• 代理公司: 成都九鼎天元知識產權代理有限公司 51214
• 代理人: 錢成岑;詹永斌

技術領域

本發明涉及無線網技術領域，特別是一種計算未知節點的可能位置區域的切分定位方法。

背景技術

無線網和傳感網在機場中的應用非常普遍，這些應用對位置信息的依賴也越來越嚴重，因此依托于這類網絡的定位方法一直很受重視。目前，一般把無線傳感器網絡的節點定位算法分為兩類：一類是基于測量距離(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.?and?Nath?B.:?‘DV?based?positioning?in?ad?hoc?networks’?Telecommun.?Syst.,?2003,?22,?(1-4),?pp.?267-280）。該算法由3個階段組成：首先，通過鄰居發現算法讓每個錨節點獲得除自己以外的其他每一個錨節點距離自己的跳數，并讓每個未知節點獲得每一個錨節點距離自己的跳數；其次，每個錨節點分別計算除自己以外的其他每一個錨節點到自己的平均每跳距離，并將該信息發送給它周邊的未知節點，未知節點則以距離自己的跳數最少且最先收到消息的錨點計算所得的平均每跳距離作為各錨點到自己的平均每跳距離，并乘以相應的跳數得到各錨點距離自己的估計距離；最后使用三邊測量法確定節點的位置。該方法的定位覆蓋率得到了較大提高，但該方法所達到的定位精度也不高，應用范圍有限。

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.）。該算法首先收集未知節點所有鄰居錨節點的信息，然后測試未知節點是否位于不同的三個錨節點組成的三角形內，計算所有包含該未知節點的三角形的重疊區域，最后用該區域的質心作為未知節點的坐標。該方法獲得了較高的精度，但是其定位覆蓋率有限。尤其對于那些不在任何由三個錨點組成的三角形內的未知節點，該方法無法定位。APIT將定位區域分成很多小網格，并對網格進行編號，通過獲得出現在所有包含未知節點的三角形區域的網格編號而得到重疊區域，該方法需要全網絡標號，計算過程繁瑣。