本發明公開了一種未知節點利用多跳節點縮小其可能位置區域的定位方法，大體思路為：未知節點利用其錨點鄰居和未知節點鄰居相對于自己的虛擬通信圓以及錨點鄰居和未知節點鄰居的必然通信圓分別與未知節點的當前可能位置區域之間的位置關系來不斷縮小未知節點的可能位置區域。未知節點遍歷所有錨點鄰居后，再遍歷所有未知節點鄰居，當未知節點的可能位置區域不再變化時，計算出此時未知節點的可能位置區域的質心作為未知節點的估計位置。本發明利用了網絡中所有多跳節點來進行未知節點的可能位置區域的消除，有效地提高了定位精度；本發明基于對凸多邊形的運算，計算量小，可以有效減小節點及網絡的能量消耗，延長網絡的生命周期。

技術領域

本發明涉及一種未知節點定位方法，特別是一種利用多跳未知節點鄰居來提高定位精度的定位方法，屬于無線傳感器網絡技術領域。

背景技術

根據定位過程中是否需要測距，目前常用的定位算法可以分為基于測距的定位算法和非測距的定位算法。由于非測距的定位算法不需要傳感器節點配置額外的硬件，同時能量消耗低、便于部署、實現簡單，因此能滿足大多數傳感器網絡的需求。

目前研究主要就集中在非測距的定位算法方面，國內外的研究者也提出了許多非測距的無線傳感器網絡節點定位算法，下面例舉幾個算法并分別簡要分析它們的優劣之處。

Nicolescu D提出的DV-Hop算法(Dragos Nioulescu and Badri Nath,“DV basedpositioning in ad hoc networks”,in Journal Telecommunication Systems,PP.267-280,2003.)是最早的非測距定位算法。該算法使用節點之間的跳數來衡量節點之間的距離，在網絡分布均勻的情況下能夠達到較好的效果。但是當網絡中節點分布不均勻時，平均每跳距離的計算將會出現比較大的偏差，定位精度也會受到較大的影響。

在DV-Hop算法的基礎上，Agpal R N提出了Amorphous算法(Nagpal R,Shrobe Hand Bachrach J,“Organizaing a global coordirate systerm from localinformation on an AD Hoc sensor network[C].in Proc.Int.Workshop oninfremation Processing in Sensor Networks,2003,LNCS2634,PP.333-348.2003.)。該算法使用節點的通信半徑作為平均每跳距離，雖然網絡通信開銷降低并且計算簡單，但是定位誤差較大。

Simics N在同一時期提出了BoundingBox算法(Slobodan N Simic and ShankarSastry,“Distributed localization in wireless ad hoc networks”,in TechnicalReport,PP.1-13,2001.)。該算法將信標節點的通信區域設定為一個正方形，未知節點把其所有直接信標節點鄰居的正方形通信區域的交集作為自己的可能位置區域，并取其中心作為自己的定位位置，該算法實現簡單、計算簡便。但是該算法假設網絡中的各節點具有同樣大小的正方形通信范圍，同時對網絡中信標節點的密度要求相對較高，所以在應用中不是特別廣泛。