無線傳感器網(wǎng)絡節(jié)點定位中的翻轉模糊問題研究.pdf

1、無線傳感器網(wǎng)絡足一種由大量結構簡單、廉價的傳感器集成無線通信接口所組成的網(wǎng)絡，它在環(huán)境監(jiān)測、災難救助、目標跟蹤等領域都有廣泛的應用前景。在這些應用中，傳感器節(jié)點的自我定位非常重要，因為沒有和具體的坐標聯(lián)系在一起的監(jiān)測信息通常是沒有意義的。同時，如基于地理信息的路由等無線傳感器網(wǎng)絡協(xié)議也需要節(jié)點的位置信息作為支撐。因此節(jié)點定位問題是無線傳感器網(wǎng)絡的重要研究內容之一。
　　根據(jù)是否需要測量節(jié)點之間的距離，無線傳感器網(wǎng)絡的節(jié)點定位方法可

2、以劃分為基于測距和基于非測距的兩種方法。其中基于測距的方法，由于定位精度高在無線傳感器網(wǎng)絡節(jié)點定位中被廣泛采用。不過基于測距的方法在定位過程巾面臨可能發(fā)生節(jié)點的翻轉模糊的問題，而且，如果節(jié)點在定位過程中發(fā)生翻轉模糊，就可能產生節(jié)點定位的雪崩效應，嚴重時甚至會導致整個網(wǎng)絡節(jié)點的定位失效。因此，有必要采取一定的措施去判斷節(jié)點是否會發(fā)生翻轉模糊，從而減小其對整個網(wǎng)絡定位過程的影響。
　　無線傳感器網(wǎng)絡節(jié)點定位中的翻轉模糊指的是，當參考節(jié)

3、點（包括錨節(jié)點和已經(jīng)定位的鄰居節(jié)點）間的位置幾乎共線（二維定位）或共面（三維定位）時，由于測距誤差的存在，導致未知節(jié)點的定位存在兩個關于某一條直線（二維定位）或平面（三維定位）成鏡像關系的估計位置。目前，在無線傳感器網(wǎng)絡節(jié)點的定位中，針對翻轉模糊的研究主要集中在兩個方面:翻轉模糊的檢測方法和翻轉模糊的處理方法。本文也將從以上兩個方面開展無線傳感器網(wǎng)絡節(jié)點定位的翻轉模糊研究。本文的主要工作和創(chuàng)新點如下:
　　(1)無線傳感器網(wǎng)絡節(jié)點

4、二維定位中的翻轉模糊檢測方法研究
　　目前，無線傳感器網(wǎng)絡節(jié)點二維定位中的翻轉模糊檢測方法主要可以分為三大類，即:魯棒四邊形檢測方法、共線度檢測方法和直線存在檢測方法。其中，魯棒四邊形檢測方法通過判斷未知節(jié)點和三個參考節(jié)點組成的一個四邊形是否滿足一定的幾何條件，來確定未知節(jié)點的定位是否會發(fā)生翻轉模糊。根據(jù)定位過程中使用的參考節(jié)點的數(shù)量，無線傳感器網(wǎng)絡的節(jié)點定位方法可以分為三邊定位方法和多邊定位方法。三邊定位方法只使用三個參考節(jié)點，

5、多邊定位方法則至少使用三個參考節(jié)點。由于使用的參考節(jié)點數(shù)量更多，多邊定位方法一般更能得到較小的平均定位誤差，因此在基于測距的無線網(wǎng)絡的節(jié)點定位中，大多采用多邊定位方法。魯棒四邊形檢測方法通常只適用于三邊定位方法，其用于多邊定位方法中計算復雜度較大，而且檢測效果較差。共線度檢測方法和直線存在檢測方法均適用于三邊定位方法和多邊定位方法。不過，由于共線度檢測方法在檢測的過程中，通常只考慮了參考節(jié)點的位置，而沒有考慮未知節(jié)點的位置，因此，其檢測

6、效果不好。而直線存在檢測方法同時考慮了參考節(jié)點和未知節(jié)點的位置，因此具有較好的檢測結果。
　　直線存在檢測方法的主要原理是將節(jié)點翻轉模糊問題等價為判斷是否存在一條直線與若干圓（以參考節(jié)點為圓心，以參考節(jié)點到未知節(jié)點的測距誤差絕對值的最大值為半徑）都相交的EIL(Existence of Intersecting Line)問題。因此，直線存在檢測方法主要是對EIL問題進行求解。針對目前求解EIL問題的公切線方法(Common Ta

7、ngent Algorithm，CTA)計算復雜度較高的問題，本文采用正交投影理論對EIL問題進行表示，證明了該問題實際上可以等價為在二維空間中存在某一直線，如任意兩個圓在該直線的正交投影線段有重疊部分時，就認為可能存在節(jié)點的翻轉模糊。根據(jù)該結論，本文進而提出了一種基于正交投影檢測節(jié)點翻轉模糊的方法(Orthogonal Projection Algorithm，OPA)。由于該方法將EIL問題轉化為一個角度計算問題，可以用坐標變換的方

8、式簡化計算過程。經(jīng)理論分析和大量數(shù)據(jù)仿真證明本文提出的OPA方法與CTA方法的檢測結果是等價的，但計算復雜度得到大幅度降低。
　　(2)無線傳感器網(wǎng)絡節(jié)點三維定位中的翻轉模糊檢測方法研究
　　據(jù)我們所知，至今為止還沒有學者專門對無線傳感器網(wǎng)絡節(jié)點三維定位中的翻轉模糊檢測方法進行研究。而在實際應用中，傳感器節(jié)點往往分布在三維空間內，需要得到節(jié)點的三維空間信息，如海洋、山地、森林及各種空間飛行器等。因此非常有必要研究節(jié)點三維定位

9、中的翻轉模糊檢測方法。
　　針對無線傳感器網(wǎng)絡節(jié)點三維定位中的翻轉模糊檢測問題，本文提出并證明了無線傳感器網(wǎng)絡節(jié)點三維定位中的翻轉模糊檢測問題可以等價為判斷是否存在一個平面與若干球（以參考節(jié)點為球心，以參考節(jié)點到未知節(jié)點的測距誤差絕對值的最大值為半徑）都相交的EIP(Existence of Intersecting Plane)問題。為了求解EIP問題，本文提出并證明了EIP問題可以等價為在上述測距誤差球中存在三個球的一個公切面

10、，如該公切面與其余的球都相交時，就認為可能存在節(jié)點的翻轉模糊。在此定理的基礎上，本文進而提出了一種求解EIP問題的公切面檢測方法(Common Tangent Plane Algorithm，CTPA)，但是理論分析和仿真結果證明CTPA方法雖然具有較好的檢測效果，但是計算復雜度太大。
　　為了解決CTPA檢測方法計算復雜度太大的問題，本文首先定義了三維空間中球到直線的正交投影的概念。該定義表示三維空間中，球有一條和直線平行的直徑

11、，從該直徑的兩個端點分別向該直線做垂線，兩個垂足之間的線段稱為球在該直線上的正交投影線段。根據(jù)上述的定義，我們提出并證明了EIP問題可以等價為在三維空間中存在某一直線，如任意兩個球在該直線的正交投影線段有重疊部分時，就認為可能存在節(jié)點的翻轉模糊。在此證明的基礎上，本文進而提出了另外一種求解EIP問題的基于正交投影的檢測方法(Orthogonal ProjectionAlgorithm for Three-dimensional，OPA-

12、3D)。理論分析和大量的仿真證明，OPA-3D方法在幾乎獲得與CTPA方法相同的檢測結果的情況下，能夠大大降低求解EIP問題的計算復雜度。
　　(3)無線傳感器網(wǎng)絡節(jié)點定位中的翻轉模糊處理方法研究
　　對于在定位中檢測出有可能發(fā)生翻轉模糊的未知節(jié)點，研究翻轉模糊檢測方法的文獻大多數(shù)采用的都是悲觀的處理方式，即直接不對該未知節(jié)點進行定位，從而防止其影響后續(xù)未知節(jié)點的定位精度。這種處理方式雖然提高了節(jié)點的定位精度，但是也會降低網(wǎng)

13、絡中節(jié)點的定位數(shù)量，這在某些實際應用中是不可接受的。為此，有必要對翻轉模糊的處理方法進行研究。
　　根據(jù)算法的計算模式，節(jié)點定位算法可以分為集中式算法和分布式算法兩類。集中式算法要把所有的數(shù)據(jù)信息傳送到某個中心節(jié)點，由中心節(jié)點負責計算所有未知節(jié)點的位置信息。而分布式算法，未知節(jié)點只需與鄰居節(jié)點進行通信，在節(jié)點自身處即可完成計算。由于集中式定位算法需要較大的通信開銷，而且其擴展性能較差，因此，在無線傳感器網(wǎng)絡的節(jié)點定位過程中廣泛使用

14、的是分布式的定位算法。目前，提出的節(jié)點翻轉模糊的處理方法大多數(shù)都是屬于集中式的處理算法，分布式處理算法較少并且計算復雜度較大。
　　本文提出了一種基于拓撲約束的分布式處理翻轉模糊的定位方法(Distributed Localization Algorithm based on Topological Constraints,DLA-TC)。DLA-TC方法分為兩個階段。第一階段對網(wǎng)絡中所有的未知節(jié)點進行翻轉模糊檢測，檢測方法采用本

15、文提出的基于正交投影的檢測方法（在節(jié)點二維定位和三維定位時分別采用OPA方法和OPA-3D方法），對檢測出的不會發(fā)生翻轉模糊的節(jié)點用最小二乘法進行定位。這一階段的目的是為了對第二階段的處理提供更多的拓撲約束。第二階段，對于那些可能發(fā)生翻轉模糊的節(jié)點，根據(jù)網(wǎng)絡的拓撲約束生成一個目標函數(shù)，然后用粒子群優(yōu)化方法(Particle SwarmOptimization，PSO)尋找目標函數(shù)的最小值，對其進行定位。仿真結果證明了無論是在節(jié)點二維定位