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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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