無線傳感器網(wǎng)絡(luò)分布式定位算法研究與仿真_圖文

1、無線傳感器網(wǎng)絡(luò)分布式定位算法研究與仿真姜偉,趙方北京郵電大學(xué)軟件學(xué)院,北京(100876摘要:無線傳感器網(wǎng)絡(luò)是一種全新的信息獲取和處理技術(shù),能夠?qū)崟r監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息。傳感器多節(jié)點協(xié)調(diào)的自身定位是各種應(yīng)用的基礎(chǔ),論文深入分析比較了在無線傳感器網(wǎng)絡(luò)領(lǐng)域中有代表性的三種分布式定位算法(Bounding box,Euclidean 和Robust position,并在OMNET+平臺上作了性能的仿真檢驗;分別從理論和實際仿真結(jié)果上,對各定位算法的性能作了定量分析,并對各算法的應(yīng)用環(huán)境給出了建議;對Robust position算法的改進提出了建議,并對無線傳感器網(wǎng)絡(luò)定位算法的

2、未來研究作了展望。關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);自身定位;定位;仿真1. 引言1近些年來,微電子技術(shù)、計算技術(shù)和無線通信技術(shù)的進步,推動了低功耗多功能傳感器的快速發(fā)展,使其在微小的體積內(nèi)能夠集成信息采集、數(shù)據(jù)處理和無線通信等多種功能。由于傳感器節(jié)點在部署時的不可控制性(例如通過飛機撒放,網(wǎng)絡(luò)中大多數(shù)節(jié)點位置不能事先確定,而無線傳感器網(wǎng)絡(luò)的大量應(yīng)用都需要網(wǎng)絡(luò)中節(jié)點的地理位置信息,從而獲知信息來源的準確位置。此外,節(jié)點的位置信息還可以輔助實現(xiàn)數(shù)據(jù)路由。人工部署和為所有網(wǎng)絡(luò)節(jié)點安裝GPS 接收器都會受到成本、功耗、擴展性等問題的限制,甚至在某些場合可能根本無法實現(xiàn),因此必須采用一定的機制與算法實現(xiàn)WSN的

3、自身定位。由于傳感器網(wǎng)絡(luò)對能耗十分敏感,所以不宜將大量的通信和計算固定于某個或者某些節(jié)點,否則,這些節(jié)點的電能會很快耗盡,出現(xiàn)網(wǎng)絡(luò)的“空穴”。要求要盡量采用分布式的節(jié)點定位算法,盡量延長傳感器網(wǎng)絡(luò)的生命期。對定位算法性能的評價標準主要有:定位精度、規(guī)模、錨節(jié)點密度、節(jié)點密度、容錯性和自適應(yīng)性、功耗、代價等。1本課題得到國家高技術(shù)研究發(fā)展計劃(863資助(No. 2007AA12Z321。論文對定位算法仿真的意義在于能夠在盡量接近現(xiàn)實的環(huán)境中得出算法性能的數(shù)據(jù),進行定量分析,從而得出算法的應(yīng)用環(huán)境和不足之處,以待改進。論文要通過研究無線傳感器網(wǎng)絡(luò)中典型的分布式定位算法,選擇Bounding bo

4、x, Euclidean和Robust Position三種算法進行實現(xiàn),并在OMNET+平臺上對他們進行仿真比較,研究環(huán)境參數(shù)(測距誤差,錨節(jié)點密度,連通度變化對他們性能的影響。論文最后給出這些算法性能的評估和應(yīng)用環(huán)境的建議,并對算法改進提出建議。2. 分布式定位算法總結(jié)分布式定位算法,大都分為三個模塊:確定未知節(jié)點和錨節(jié)點間距離模塊;計算每個未知節(jié)點位置模塊;循環(huán)精確節(jié)點位置模塊。首先,未知節(jié)點通過基于測距或非測距方法確定其到錨節(jié)點的距離;然后,通過到錨節(jié)點的距離來計算每個未知節(jié)點的位置;最后,對未知節(jié)點的位置進行迭代求精,最終所有未知節(jié)點報告它們的位置。分布式定位算法的每個模塊中都有幾種

5、可選算法。其中確定未知節(jié)點和錨節(jié)點間的距離模塊中可選算法有基于RSSI的測距算法,美國路特葛斯大學(xué)(Rutgers University的Dragos Niculescu1等人提出的Euclidean,DV-Hop,DV-distance三種算法;計算未知節(jié)點位置模塊中可選算法有三邊測量法,多邊形算法法,Min-Max 算法;位置求精模塊主要有由Savarese 2等提出的根據(jù)所有可獲得的節(jié)點信息重復(fù)執(zhí)行三邊測量或多邊形算法過程重新確定節(jié)點位置。2.1 確定未知節(jié)點到錨節(jié)點距離模塊可選算法此算法已知節(jié)點發(fā)射功率,在接收節(jié)點測量接收功率,計算傳播損耗,然后使用理論或經(jīng)驗的信號傳播模型將傳播損耗轉(zhuǎn)

6、化為距離。所用公式如下:X d d (log 10d (PL P d (P 0100T +=的隨機變量期望為方差為是一個服從正態(tài)分布的是一個信號衰減指數(shù)時信號強度的損耗是在兩節(jié)點距離為是信號發(fā)射的強度時的信號強度為兩節(jié)點相距為其中0X d d (PL P d d (P 200T 根據(jù)如上公式可推導(dǎo)出信號強度轉(zhuǎn)換距離的公式:0T d 10P(d-PL(d -P X 10expd ×+= (2-1實際應(yīng)用中的情況要復(fù)雜的多,尤其是在分布密集的無線傳感器網(wǎng)絡(luò)中。反射、多徑傳播、非視距、天線增益等問題都會對相同距離產(chǎn)生顯著不同的傳播損耗。因此這種方法的主要誤差來源是環(huán)境影響所造成的信號傳播模

7、型的復(fù)雜性。信號強度測距法通常屬于一種粗糙的測距技術(shù),在現(xiàn)實環(huán)境中,溫度、障礙物、傳播模式等條件往往都是變化的,使得該技術(shù)在實際應(yīng)用中仍存在困難,通常會產(chǎn)生50%左右的測距誤差。DV-distance 算法很簡單,在泛洪傳輸中僅通過在每個節(jié)點上累加測得的距離來確定其距錨節(jié)點的距離。算法從錨節(jié)點開始,它們發(fā)送一個包含其身份,位置和設(shè)為0路徑長度的信息包。每個接收到信息的節(jié)點將測得的其距發(fā)送點距離加到路徑長度上,如果可控泛洪允許的話繼續(xù)廣播這個消息。另一個限制是,當(dāng)節(jié)點再次收到以前接收過的節(jié)點信息時,只有當(dāng)前信息中距錨節(jié)點路徑長度小于原先信息中距錨節(jié)點路徑長度時,才允許發(fā)送這個消息,并更新自身信息

8、。最終結(jié)果是,每個節(jié)點將存儲它們距錨節(jié)點的最短路徑長度。DV-distance 算法的缺點是,當(dāng)距離信息在多跳中傳播時,測距誤差被累加放大。在錨節(jié)點很少或測距硬件差的大型網(wǎng)絡(luò)中,這種累計誤差很大。DV-hop 算法可以克服DV-distance 算法的缺點,它通過計算跳數(shù)而不是累加有誤差的測距獲得網(wǎng)絡(luò)拓撲信息。定位算法可以分為兩個階段,即兩次廣播過程。第一個階段,每個錨節(jié)點采用廣播方式將其位置信息傳遞給其鄰居節(jié)點。廣播的信息包格式為:Id i ,x i ,y i ,Hops i ,其中包含了該節(jié)點的標識Id i 、位置坐標(x i ,y i ,以及跳數(shù)Hops i 信息。初始Hops i 為0

9、,接收到此數(shù)據(jù)的每個節(jié)點將此信息記錄到一張表中。然后繼續(xù)向其鄰居節(jié)點廣播,每廣播一次就將Hops i 加1。當(dāng)節(jié)點接收到一個相同Id 的數(shù)據(jù)包時,便要與原來的Hops i 進行比較,如果新的跳數(shù)小于原表中的跳數(shù),就用新的跳數(shù)更新表中的跳數(shù)信息,意味著找到了一條更短的到達該錨節(jié)點的路徑。如果新的跳數(shù)大于原表中的跳數(shù),就丟棄該數(shù)據(jù)包,也不再進行轉(zhuǎn)發(fā)。經(jīng)過第一階段的廣播過程后,錨節(jié)點也獲得其它所有錨節(jié)點的坐標及跳數(shù)距離,而且所有傳感器節(jié)點都已經(jīng)得到所有錨節(jié)點的坐標和跳數(shù)距離。這樣,每個錨節(jié)點即可用式2-2計算出錨節(jié)點i 到其它錨節(jié)點j 的每跳的平均間隔距離C ij : (2-2其中j是除i之外的所有

10、其它錨節(jié)點。第二個階段,每個錨節(jié)點廣播其計算出的每跳平均距離,數(shù)據(jù)包的格式為:Id i, C i。C i是該錨節(jié)點到所有其它錨節(jié)點的每跳平均距離。每個接收到此數(shù)據(jù)的節(jié)點將此信息添加到表中,然后繼續(xù)向其鄰居廣播。重復(fù)ID的數(shù)據(jù)包就丟棄。經(jīng)過此階段的廣播后,所有節(jié)點都已知所有錨節(jié)點計算的每跳平均距離C i。然后再將所有的每跳平均距離相加取平均: (2-3其中n為所有錨節(jié)點的個數(shù)。由此得到了全網(wǎng)所有錨節(jié)點之間的每跳平均距離。此時,各個節(jié)點也得到與各個錨節(jié)點的跳數(shù)。由此可計算出該節(jié)點到錨節(jié)點的距離:D i = hops × cc。圖1 DV-hop定位算法示意圖如圖1所示,已知錨節(jié)點L1與L

11、2,L3之間的距離和跳數(shù),L2計算得到平均每跳距離為(40+75/(2+5=16.42。同理,L1與L3也計算出平均每跳距離。節(jié)點A將分別從L1,L2與L3獲得平均每跳距離,然后去這三個距離的平均值cc。用cc乘以節(jié)點A到L1,L2與L3的跳數(shù)即可得到A到這三個錨節(jié)點的距離。Dv-hop算法的缺點是不適用于極為不規(guī)則的網(wǎng)絡(luò)拓撲結(jié)構(gòu),這種結(jié)構(gòu)中,實際每跳間的距離差別很大。Niculescu和Nath提出了另一種稱之為Euclidean的算法,這種測距算法是基于圍繞錨節(jié)點的未知節(jié)點的局部幾何算法。同樣,信息也從錨節(jié)點開始泛洪傳輸,但測距算法比前幾種情況復(fù)雜的多。如圖2(a所示,假設(shè)節(jié)點擁有RSSI

12、測距能力,已知未知節(jié)點B,C在錨節(jié)點L的無線射程內(nèi),BC距離已知或通過RSSI測量獲得;節(jié)點A與B、C相鄰。對于四邊形ABCL,所有邊長和一條對角線BC已知,根據(jù)三角形的性質(zhì)可以計算出AL的長度(節(jié)點A與L的距離。使用這種方法,當(dāng)未知節(jié)點獲得與3個或更多錨節(jié)點之間的距離后定位自身。未知節(jié)點B、C與錨節(jié)點L 兩兩相鄰,節(jié)點A 與B、C相鄰。對于四邊形ABCL,所有邊長和一條對角線BC已知,根據(jù)簡單的幾何原理可計算出AL 的長度。但節(jié)點A有兩個可能的位置A和A,假如A還有其他鄰居節(jié)點D 與錨節(jié)點L相鄰,并與B或C之一相鄰,那么可以使用D來替換B或C,再次計算AL的距離,則A節(jié)點就能在兩個可能的位置

13、中選擇出正確的一個。使用這種方法,當(dāng)未知節(jié)點獲得與三個或更多錨節(jié)點距離后定位自身。由基本的幾何知識,可以得出: (2-4 以上是在理想情況下,當(dāng)四邊形是凹四邊形時情況要復(fù)雜一些。如圖2(b所示,一個節(jié)點(self有兩個鄰居節(jié)點n1和n2,n1距錨節(jié)點的距離估算為a,n2距錨節(jié)點的距離為估算為b。再加上已知距離c,d和e, Euclidean算法能獲得self節(jié)點距錨節(jié)點距離的可能值r1和r2。Niculescu描述了兩種確定使用哪個值(如果有兩個的算法。如果存在第三個鄰居節(jié)點n3,n3距錨節(jié)點的距離已估算出,且與n1或n2連通,可使用neighbor vote算法進行測距。用n3代替n2(或n

14、1又將產(chǎn)生兩個估算距離。正確的距離是這兩對距離的一部分,且被一個簡單的投票算法選出。當(dāng)然,為了選出更精確的距離,可以考慮很多鄰居節(jié)點。 (a (b圖2 Euclidean 算法示意圖2.2 計算節(jié)點位置模塊可選算法 圖3 三邊測量法示意圖三邊測量法是最簡單的定位方法,在二維平面上用幾何圖形表示出來的意義是:當(dāng)?shù)玫轿粗?jié)點到一個錨節(jié)點的距離時,就可以確定此未知節(jié)點在以此錨節(jié)點為圓心、以距離為半徑的圓上。得到未知節(jié)點到3個錨節(jié)點的距離時,3個圓的交點就是未知節(jié)點的位置,如圖3所示。從被估測的距離(di 和已知的錨節(jié)點的位置(xi ,yi 中我們可以得到一組方程:(x 1 - x2 + (y 1 -

15、 y2 =21d (2-6 (x 2 - x2 + (y 2 - y2 =22d (2-7(x 3 - x2 + (y 3 - y2 =23d (2-8求出(x ,y即是節(jié)點位置。多邊形算法源于三邊測量法,當(dāng)參考節(jié)點數(shù)量超過3個時,就是通過定義方程組,利用冗余信息能夠更精確地計算節(jié)點的位置。假設(shè)未知節(jié)點坐標是( x ,y ,錨節(jié)點坐標分別為( x 1,y 1 ,( x 2,y 2 ,( x k , y k ,未知節(jié)點到錨節(jié)點的距離分別是r 1,r 2,r k ,我們可以得到一組方程:(2-9式(2-9可以線性化為:Ax = b 其中:(2-10(2-11由于存在測距誤差,合理的線性模型應(yīng)該是:

16、Ax +N = b其中,N 為k - 1維隨機誤差向量。利用最小二乘法原理,x 的值應(yīng)當(dāng)使模型誤差N = b - Ax 達到最小,即通過最小化Q ( x = |N|2d3d2d1B(x1,y1C(x2,y2A(x0,y0D= |b Ax|2。求x的估計,對Q ( x關(guān)于x求導(dǎo)并令其等于零,可以求解未知節(jié)點的最小二乘位置估計:$x=(ATA-1ATb基于最小二乘估計的多邊測量定位法是最常用的定位方法,在很多定位算法中得到應(yīng)用。多邊測量定位的缺點是需要大量的浮點運算。針對這個問題,加州大學(xué)伯克利分校的Semic提出了一種更為簡單的算法Bounding box。該方法的主要思想是利用錨節(jié)點的位置和測

17、距值劃出邊界框(bounding box,求解邊界框的交集(圖4中的黑框,黑框的中心就是未知節(jié)點的估計位置,從圖中可以看到Bounding box算法與三邊測量算法求解的差異。該算法實質(zhì)是將求解二次方程組的問題簡化為求解一次方程問題,從而避免了復(fù)雜的最小二乘解法,可以大大減少計算開銷。 圖4 Bounding box算法示意圖算法主要思想是,用距離估計和錨節(jié)點位置為每個錨節(jié)點構(gòu)建一個限定大小的盒子,然后確定這些盒子的重合部分。未知節(jié)點的位置即被設(shè)為重合部分的中心。如圖2-7所示,用Min-Max算法確定一個已知到三個錨節(jié)點距離估計的節(jié)點的位置。值得注意的是,用Min-Max算法估測的節(jié)點位置接

18、近于用多邊形算法計算出的位置(也就是,三個圓的重合部分。錨節(jié)點a的盒子是通過a的坐標(x a,y a加上和減去估測距離(d a得到的:x a-d a,y a-d a×x a+d a,y a+d a (2-12盒子的重合部分是通過取所有錨節(jié)點坐標與估測距離之差的最大值和所有錨節(jié)點坐標與估測距離之和的最小值計算得到的: max(x i-d i,max(y i-d i×min(x i+d i,min(y i+d i(2-13 2.3 循環(huán)定位求精模塊算法這個階段的目的是使在第二階段計算得出的(初始節(jié)點位置更精確。即使在好的條件下(高連通度,低測距誤差,這些節(jié)點定位也不可能很精確。

19、原因是前兩個階段并沒有用到所有可獲得的信息。由Savarese3等提出的精確過程正是當(dāng)節(jié)點更新他們的位置信息時考慮了與所有節(jié)點間的距離。在每步開始時,一個節(jié)點廣播它的位置并相應(yīng)地從它的鄰居節(jié)點那里接收鄰居節(jié)點位置和距離,然后執(zhí)行階段二的多邊形算法計算過程以確定它的新位置。在很多情況下,由到鄰居節(jié)點距離所限,將迫使新的位置向節(jié)點真實的位置靠近。經(jīng)過幾步迭代后,當(dāng)節(jié)點位置更新過程收斂時,精確過程結(jié)束并報告最終位置。3. 算法仿真對定位算法的仿真的意義在于能夠在接近現(xiàn)實的環(huán)境中得出算法性能的數(shù)據(jù),進行定量分析,從而得出算法的應(yīng)用環(huán)境和不足之處,以待改進。仿真工具選擇的是布達佩斯技術(shù)大學(xué)電信學(xué)院開發(fā)的

20、OMNET+離散事件模擬器。3.1 仿真算法選擇本文選擇完全的分布式算法,即節(jié)點位置的計算在節(jié)點本地完成。這種算法可以應(yīng)用于大規(guī)模的無線傳感器網(wǎng)絡(luò)。這樣的網(wǎng)絡(luò)要滿足:(1自組織,不依賴于全局基礎(chǔ)設(shè)施(如衛(wèi)星;(2健壯,能容忍節(jié)點失效和測距誤差;(3節(jié)能,只需要較少的計算和通信開銷。根據(jù)上述條件,排除了凸規(guī)劃(Convex Position,MDS-MAP等集中式算法。此外,質(zhì)心算法,APIT算法需要較高的錨節(jié)點密度,也被排除在外。本文對滿足以上條件的三種定位算法,Bounding box算法, Euclidean算法和Robust Position算法做了仿真分析,這三種算法具有良好的可實現(xiàn)性

21、和代表性。將上述三個算法分解,得到他們各個模塊的算法:表1 仿真算法按模塊分解3.2 仿真網(wǎng)絡(luò)環(huán)境設(shè)計鑒于無線傳感器網(wǎng)絡(luò)是自組織的,所以節(jié)點放置時是隨機的,因此仿真環(huán)境中的節(jié)點是隨機部署的。錨節(jié)點需要通過安裝特殊的定位系統(tǒng)和采取人工部署來確定其位置,所以仿真環(huán)境中錨節(jié)點的位置可以人為確定。仿真環(huán)境中的重要參數(shù)有:網(wǎng)絡(luò)中的節(jié)點數(shù)量;錨節(jié)點密度;節(jié)點通信半徑(連通度。仿真由100個節(jié)點組成的無線傳感器網(wǎng)絡(luò),開始時,依據(jù)上述參數(shù)產(chǎn)生一個隨機的網(wǎng)絡(luò)拓撲結(jié)構(gòu),節(jié)點在一個正方形區(qū)域內(nèi)隨機分布。通過指定通信半徑可以控制連通度。3.3 仿真測距誤差模塊1中得到的未知節(jié)點到錨節(jié)點的距離在實際中是有誤差的,這種誤

22、差在使用基于測距的RSSI方法時表現(xiàn)得更為明顯。因此在算法仿真中凡是用到RSSI測距時都要模擬引入的誤差,這樣建模才能和實際相符。因此,如何引入這個誤差是我們要考慮的問題。相關(guān)方面的論文有許多,最為經(jīng)典的是Noisy Disk模型,其數(shù)學(xué)模型如下:=則未定義若其中maxijmaxijijij dddd,d(d(3-1其中ijd為節(jié)點i到節(jié)點j的實際距離, maxd為節(jié)點最大連通距離,ijd為節(jié)點i到節(jié)點j之間的引入誤差后的距離。由此可知,該模型假設(shè)節(jié)點之間估測的距離服從正態(tài)分布。其中期望為真實距離,方差憑經(jīng)驗指定,因?qū)嶋H環(huán)境的不同而異。這種方法較容易在計算機中實現(xiàn),但算法在計算機中的模擬結(jié)果往

23、往與實際中的運行結(jié)果相差很大。在這里再介紹了另一種構(gòu)建模擬環(huán)境的方法。這種方法通過獲取大量的實際數(shù)據(jù)構(gòu)建經(jīng)驗數(shù)據(jù)庫。算法在計算機上進行模擬時就可以從經(jīng)驗數(shù)據(jù)庫中抽取相應(yīng)的數(shù)據(jù),以得到與實際環(huán)境更加貼近的仿真環(huán)境。本文中所述算法的模擬環(huán)境是Noisy Disk方法的一種變形。由于傳感器主要是通過測量RSSI值來獲得信號強度進而獲得節(jié)點間距離的,所以此處把測量的RSSI值當(dāng)作一個服從正態(tài)分布的隨機變量。4. 仿真結(jié)果和算法性能評估4.1 算法仿真結(jié)果在檢測算法的定位精度性能的仿真實驗中,將通信半徑設(shè)定為15。這里將測距誤差定義為一個比值,即算法計算得出的節(jié)點位置與真實位置之間的偏差比上節(jié)點到錨節(jié)點

24、的距離估計。仿真實驗獲得了一組在不同錨節(jié)點密度下三個算法在定位誤差方面的數(shù)據(jù),如圖5所示。在檢測算法的定位覆蓋率性能的仿真實驗中,將通信半徑也設(shè)定為15。仿真實驗獲得了一組在不同錨節(jié)點密度下三個算法在定位覆蓋率方面的數(shù)據(jù),如圖6所示。模塊Boundingbox Euclidean RobustPosition1 2 3 DV-distanceMin-max無Euclidean多邊形算法無DV-hop多邊形算法有在檢測算法能量消耗性能的仿真實驗中,依然將通信半徑定為15,錨節(jié)點密度定為10%,所以網(wǎng)絡(luò)平均連通度C(鄰居節(jié)點個數(shù)為6。能量開銷包括通信開銷和計算開銷,實驗獲得了一組在不同節(jié)點個數(shù)下三

25、個算法在能量消耗方面的數(shù)據(jù)。如圖7、8所示。 圖5 三個算法的定位精度仿真結(jié)果從定位精度仿真實驗中,可以看到,三個算法的定位誤差均隨錨節(jié)點密度的增大而降低。其中,Bounding box算法對網(wǎng)絡(luò)中錨節(jié)點密度最為敏感,錨節(jié)點密度從3%變化到10%時,定位精度顯著提升。Euclidean 算法和Robust position算法對錨節(jié)點密度沒有如此敏感。 圖6 三個算法的覆蓋率仿真結(jié)果定位覆蓋率是考察定位算法性能的重要指標,它表示通過執(zhí)行某個定位算法,網(wǎng)絡(luò)中被正確定位(定位誤差在可接受的范圍內(nèi)的比例。從定位覆蓋率的仿真實驗中,可以看到,三個算法的定位覆蓋率均隨錨節(jié)點密度的增大而提高。其中,Bou

26、nding box算法和Euclidean算法對網(wǎng)絡(luò)中錨節(jié)點密度很敏感,尤其當(dāng)錨節(jié)點密度從3%變化到10%時,這兩個算法的定位覆蓋率顯著提升。Robust position算法對錨節(jié)點密度并不敏感,在錨節(jié)點密度很小(只有3%時,其定位覆蓋率已達90%,在10%的錨節(jié)點密度下,覆蓋率已達100%。 圖7 三個算法的通信開銷仿真結(jié)果能量消耗包括通信開銷和計算開銷,它是無線傳感器網(wǎng)絡(luò)的瓶頸所在。因此,一切研究都要考慮盡量降低能量消耗。從能量消耗的仿真實驗中,可以看到,三個算法的通信開銷隨網(wǎng)絡(luò)規(guī)模的增長基本呈線性變化。其中,Bounding box算法的能量開銷隨網(wǎng)絡(luò)中節(jié)點數(shù)的增加增長得很快。Eucl

27、idean在這三個算法中的能量開銷最小。 圖8 三個算法的計算開銷仿真結(jié)果圖8顯示了仿真試驗中三個定位算法的計算開銷。其中,Bounding box算法在模塊2中計算節(jié)點位置信息時用Min-max方法代替了多邊形測量法,從而避免了復(fù)雜的最小二乘法,所以運算次數(shù)最少。而Robust Position算法不僅在模塊2中用了多邊形算法,而且引入了模塊3的迭代求精過程,所以計算開銷最大。4.2 算法性能評估算法的性能主要從以下三個方面進行評估:定位誤差、通信開銷和定位覆蓋率。在評估算法性能時,用到了如下的參數(shù): N網(wǎng)絡(luò)中節(jié)點數(shù)量,A錨節(jié)點數(shù)量, C平均鄰居節(jié)點數(shù)量(網(wǎng)絡(luò)連通度, K參加一次多邊形測量計

28、算的錨節(jié)點個數(shù)。通信開銷:錨節(jié)點發(fā)送廣播消息,消息只傳播到其鄰居,鄰居節(jié)點并不轉(zhuǎn)發(fā),每個節(jié)點需與其鄰居節(jié)點通信一次,所以整個網(wǎng)絡(luò)發(fā)送消息數(shù)量為NC。計算開銷:該算法的計算包括求每個交集的兩對最大值和最小值,對于每個交集,需要2C次比較運算和4C次加法運算,所以總的運算開銷為6C次。該算法需要非常少的計算和通訊開銷,算法的覆蓋速度很快,位置估計的精度隨著錨節(jié)點數(shù)量的增加而提高。算法的主要缺點是需要較高的錨節(jié)點密度,否則定位精度和覆蓋率將會很低。該算法適合于節(jié)點的計算能力非常有限的情況。通訊開銷:每個錨節(jié)點發(fā)送TTL為2的數(shù)據(jù)包,即數(shù)據(jù)包只轉(zhuǎn)發(fā)兩跳,錨節(jié)點的鄰居節(jié)點轉(zhuǎn)發(fā)一次數(shù)據(jù)包,整個網(wǎng)絡(luò)發(fā)送的數(shù)

29、據(jù)包數(shù)量為A +AC。計算開銷:算法的計算開銷包括距離計算和最小二乘算法。其中距離計算需要做44 × 2 + 2 = 90次。得到正確的距離AL,多邊測量定位需要17 k - 17 + 23 / 3次。算法的網(wǎng)絡(luò)通訊開銷為A + AC,節(jié)點計算開銷為(17k + 73 + 23 / 3。與DV-hop算法不同, Euclidean算法依賴于局部幾何拓撲,適用于網(wǎng)絡(luò)拓撲不規(guī)則的網(wǎng)絡(luò),由于數(shù)據(jù)包只傳送兩跳,該算法通訊開銷較小,同時具有適當(dāng)?shù)挠嬎汩_銷和定位精度。但該算法的覆蓋度受錨節(jié)點密度和局部幾何拓撲的影響較大。通訊開銷:初始階段與DV-hop類似,由每個錨節(jié)點發(fā)送廣播數(shù)據(jù)包,中間節(jié)點只

30、發(fā)送未發(fā)送的數(shù)據(jù)包,所以網(wǎng)絡(luò)中每個節(jié)點平均發(fā)送A個數(shù)據(jù)包。在求精階段,節(jié)點只廣播其位置信息到其一跳鄰居節(jié)點,所以每個節(jié)點發(fā)送s (迭代次數(shù)個數(shù)據(jù)包。通過優(yōu)化可以減少這個數(shù)量,例如只有當(dāng)位置信息變化較大時才廣播更新位置,這樣就比估計的通訊開銷要小。計算開銷:在初始階段的DV-hop算法過程中,每個節(jié)點將執(zhí)行17( k - 1 + 23 /3次。求精的每一次迭代,節(jié)點將做一次最小二乘估計并產(chǎn)生新的置信矩陣。如果算法共迭代s次,對于求精,每一次最小二乘估計將包含節(jié)點的一跳鄰居。因此,每一次最小二乘運算將消耗17( C -1 + 23 /3次。每一個置信度計算需要C次加法和1次除法。在整個求精過程中,

31、每個節(jié)點需要s 17(C - 1 + 23 / 3+ C + 1 = s 18C - 16 + 23 / 3 次。該算法能夠達到較好的精度,在網(wǎng)絡(luò)連通度較高的情況下能較好地容忍距離誤差。因為節(jié)點主要和其一跳鄰居節(jié)點通訊,該算法也是一個可擴展的算法。但是,由于迭代的過程,該算法是強計算的。如果初始位置估計非常不準確或誤差是相關(guān)的,算法可能不能達到精確的估計。由于依賴于網(wǎng)絡(luò)拓撲,該算法可能需要很長的覆蓋時間。5. 算法比較和改進建議5.1 算法性能比較上述三種算法均為完全分布式定位算法,且均可擴展,即每個節(jié)點的計算復(fù)雜度與網(wǎng)絡(luò)規(guī)模無關(guān)。從能耗方面分析,計算與通信開銷最小的是Bounding Box

32、算法;Euclidean算法的計算和通信開銷適中;Robust Position算法的計算與通信開銷最大。從定位精度上看,Bounding Box算法只有當(dāng)網(wǎng)絡(luò)中錨節(jié)點密度較高時才能獲得較好的定位精度;相比之下,Euclidean算法的在不同的網(wǎng)絡(luò)環(huán)境下定位精度都適中;而Robust Position算法采用了迭代求精過程,可以達到較高的定位精度。從覆蓋率的角度上說,Bounding Box算法和Euclidean算法的覆蓋率都與錨節(jié)點密度有關(guān),但后者由于采用與錨節(jié)點兩跳的距離估算,能夠獲得較高的覆蓋率。出于成本方面考慮,Bounding Box算法需要較高的錨節(jié)點密度,增加了網(wǎng)絡(luò)的成本?？梢?/p>

33、,從多種角度和不同網(wǎng)絡(luò)環(huán)境衡量,沒有一種算法是最優(yōu)的。在某一個環(huán)境下,這三種算法之一會優(yōu)于其他兩種算法,而且,每種算法都有可優(yōu)化和提升的空間。5.2 算法改進建議從上述分析中,我們看到Robust Position算法在定位精度、容錯性、網(wǎng)絡(luò)成本等方面有較大的優(yōu)勢。但算法的計算復(fù)雜度較高,可以考慮在計算節(jié)點初始位置階段采用Bounding Box算法的思想,其實質(zhì)是將求解二次方程組的問題轉(zhuǎn)化為求解一次方程問題,從而避免了復(fù)雜的最小二乘法,可以大大減少計算開銷。6. 總結(jié)6.1 論文總結(jié)論文深入研究了三種具有良好可實現(xiàn)性和代表性的無線傳感器網(wǎng)絡(luò)分布式自身定位算法:Bounding box算法,E

34、uclidean 算法和Robust Position算法,并設(shè)計了仿真程序,在OMNET+平臺上對三種定位算法進行了仿真檢驗,在仿真結(jié)果的基礎(chǔ)上對這三種算法的性能做了比較分析,并對他們的應(yīng)用環(huán)境給出了建議。論文最后提出了算法的改進意見和未來研究方向展望。Bounding box算法,Euclidean算法和Robust Position算法都是完全分布式算法,且均可擴展,即每個節(jié)點的計算復(fù)雜度與網(wǎng)絡(luò)規(guī)模無關(guān)。這三個算法均滿足自組織、健壯和節(jié)能這三個WSN定位算法的基本條件,且具有典型性和良好的可實現(xiàn)性。論文主要對這三種定位算法的定位精度、覆蓋率和能量開銷三個方面進行仿真檢驗和性能評估。通過對

35、仿真結(jié)果分析,比較了在不同網(wǎng)絡(luò)環(huán)境下這三個算法的表現(xiàn),并對他們的應(yīng)用環(huán)境給出了建議。論文的主要結(jié)論是從多種角度和不同網(wǎng)絡(luò)環(huán)境衡量,沒有一種算法是最優(yōu)的。在某一個環(huán)境下,這三種算法之一會優(yōu)于其他兩種算法,而且,每種算法都有可優(yōu)化和提升的空間。從仿真結(jié)果可以看到,Robust Position 算法在定位精度、容錯性、網(wǎng)絡(luò)成本等方面有較大的優(yōu)勢。但算法的計算復(fù)雜度較高,可以考慮在計算節(jié)點初始位置階段采用Bounding Box算法的思想,其實質(zhì)是將求解二次方程組的問題轉(zhuǎn)化為求解一次方程問題,從而避免了復(fù)雜的最小二乘法,可以大大減少計算開銷。6.2 未來研究工作在WSN自身定位領(lǐng)域,當(dāng)今主要是對定位

36、算法本身進行研究,在將來以下三個方向有可能成為熱點:(1定位算法性能評價的量化和模型化。WSN自身定位算法的性能直接影響其可用性,至關(guān)重要。如何評價是一個需要深入研究的問題。雖然已有幾個常用標準,例如定位精度、錨節(jié)點密度、節(jié)點密度、功耗等,但這些標準還沒有達到實用程度,需要進一步地模型化和量化。(2自身定位仿真系統(tǒng)。如何建立一套標準的仿真技術(shù)和仿真系統(tǒng)來模擬WSN 自身定位算法的實現(xiàn),將會極大地降低費用和時間成本,有利于各種定位算法的評測。(3移動性問題。以往的WSN自身定位算法大都假設(shè)網(wǎng)絡(luò)是靜止的,所以在網(wǎng)絡(luò)移動條件下,如何實現(xiàn)低成本、低功耗和高精度的定位,也是面臨的挑戰(zhàn)之一。參考文獻1 N

37、icolescu D. Nath B. Ad2hoc positioning systems (APS A. Proceedings of the 2001 IEEE Global Telecommunications Con2ference C. New York. USA: IEEE. 2001. 29262931.2 Savarese C. Rabaey JM. Beutel J. Locationing in distributed ad-hoc wireless sensor network. In: Proc. of the 2001 IEEE Intl Conf. on Acoustics. Speech. and Signal. V ol.4. Salt Lake: IEEE Signal Proces