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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、1又將產(chǎn)生兩個(gè)估算距離。正確的距離是這兩對(duì)距離的一部分,且被一個(gè)簡(jiǎn)單的投票算法選出。當(dāng)然,為了選出更精確的距離,可以考慮很多鄰居節(jié)點(diǎn)。 (a (b圖2 Euclidean 算法示意圖2.2 計(jì)算節(jié)點(diǎn)位置模塊可選算法 圖3 三邊測(cè)量法示意圖三邊測(cè)量法是最簡(jiǎn)單的定位方法,在二維平面上用幾何圖形表示出來的意義是:當(dāng)?shù)玫轿粗?jié)點(diǎn)到一個(gè)錨節(jié)點(diǎn)的距離時(shí),就可以確定此未知節(jié)點(diǎn)在以此錨節(jié)點(diǎn)為圓心、以距離為半徑的圓上。得到未知節(jié)點(diǎn)到3個(gè)錨節(jié)點(diǎn)的距離時(shí),3個(gè)圓的交點(diǎn)就是未知節(jié)點(diǎn)的位置,如圖3所示。從被估測(cè)的距離(di 和已知的錨節(jié)點(diǎn)的位置(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é)點(diǎn)位置。多邊形算法源于三邊測(cè)量法,當(dāng)參考節(jié)點(diǎn)數(shù)量超過3個(gè)時(shí),就是通過定義方程組,利用冗余信息能夠更精確地計(jì)算節(jié)點(diǎn)的位置。假設(shè)未知節(jié)點(diǎn)坐標(biāo)是( x ,y ,錨節(jié)點(diǎn)坐標(biāo)分別為( x 1,y 1 ,( x 2,y 2 ,( x k , y k ,未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離分別是r 1,r 2,r k ,我們可以得到一組方程:(2-9式(2-9可以線性化為:Ax = b 其中:(2-10(2-11由于存在測(cè)距誤差,合理的線性模型應(yīng)該是:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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