基于共面性與區(qū)域限制的三維wsn定位算法

1、第 43 卷 增刊8 月計(jì) 算 機(jī) 研 究 與 發(fā) 展JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENTVol.43, Suppl. Aug. 2006基于共面性與區(qū)域限制的三維 WSN 定位算法譚大元宋國治廖冬陽李潤東(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300387)(guo)摘要 定位是無線傳感器網(wǎng)絡(luò)技術(shù)和應(yīng)用的重要組成部分，相對于二維定位，三維定位更符合實(shí)際需求。在三維空間中，我們利用四面體的特性，提出一個基于共面性和區(qū)域限制的 3D 定位算法，并給出算法實(shí)現(xiàn)。仿真表明，對節(jié)點(diǎn)進(jìn)行定位中，我們提出的定位算法，定位精度明顯優(yōu)于經(jīng)典的 DV-ho

2、p 算法和質(zhì)心算法，并且穩(wěn)定性也高于另外兩者。關(guān)鍵詞 無線傳感器網(wǎng)絡(luò)；三維定位；共面性；體積比閾值中圖法分類號 TP3913D Localization Algorithm for Wireless Sensor Networks Based on Degree ofCoplanarity and Restricted SpaceDayuan Tam,Guozhi Song,Dongyang Liao and Rundong Lee(School of Computer Science & Software Engineering, Tianjin Polytechnic University

3、, Tianjin 300387)Abstract Localization is an important part of Wireless Sensor Networks technology, and only the 3D location technology is appropriate for real applications. We propose a novel 3D localization algorithm based on DCP (Degree of Coplanarity) and Restricted Space. Simulation results ind

4、icate that the average location accuracy of the improved localization algorithm is much better than classical 3D DV-hop algorithmand Centroid algorithm. Moreover the stability of the new algorithm is better than others.Keywords Wireless Sensor Network; Degree of Coplanarity ; 3D Localization ; Volum

5、e Ratio threshold無線傳感器網(wǎng)絡(luò) (Wireless Sensor Networks, WSNs )技術(shù)是一種全新的信息獲取和處理技術(shù)，由于自身具有自組織、部署快捷、高容錯等特性，因此可以廣泛應(yīng)用在軍事、工農(nóng)業(yè)、醫(yī)療、智能家居、海洋探測等領(lǐng)域中1。其中傳感器位置信息對于無線傳感器網(wǎng)絡(luò)來說是一個非常重要的信息2，許多傳感器網(wǎng)絡(luò)的應(yīng)用都是以位置信息為基礎(chǔ)的，因此能否精確定位顯得尤為重要。傳統(tǒng)的傳感器節(jié)點(diǎn)定位算法可以分為基于測距的定位算法和基于非測距的定位算法兩大類3，基于測距的定位算法是通過獲取節(jié)點(diǎn)到節(jié)點(diǎn)的距離來計(jì)算節(jié)點(diǎn)定位，常見的基于測距定位算法有 RSSI(Received S

6、ignal Strength indication) 4、TDOA (Time Difference of Arrival) 5、AOA (Angle of Arrival ) 6等；非測距的定位算法一般利用節(jié)點(diǎn)間的關(guān)系和連通性來估計(jì)位置坐標(biāo)，典型的基于非測距的定位算法有 DV-hop (Distance Vector-hop)算法7, 8、質(zhì)心算法9、 APIT (Approximate PIT Test)算法10等。由于基于測距的定位算法往往需要在節(jié)點(diǎn)上添加額外的設(shè)備，因此有較高的成本限制和硬件條件的約束，所以我們更傾向于研究基于非測距的定位算法?，F(xiàn)實(shí)應(yīng)用中，節(jié)點(diǎn)的位置可能在山峰、海底等非

7、平面的位置，測定的區(qū)域也非平面，所以二維節(jié)點(diǎn)定位算法無法滿足現(xiàn)實(shí)應(yīng)用的需求，有必要進(jìn)行三維定收稿日期：2015-05-17基金項(xiàng)目：國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201410058046)，國家自然科學(xué)基金（61272006），天津市教委科技發(fā)展基金(No.20110808)本論文第一作者為學(xué)生2計(jì)算機(jī)研究與發(fā) 展位算法的研究?，F(xiàn)階段很多學(xué)者已經(jīng)開始著手于三維定位算法 的研究。針對不同的問題與應(yīng)用，人們已經(jīng)提出了多 種三維定位算法，其中有許多三維定位算法是由傳統(tǒng) 的二維定位算法衍生而來的，文獻(xiàn)11中就是將一個 二維質(zhì)心算法進(jìn)行加權(quán)改進(jìn)，擴(kuò)展至三維空間衍生成 為三維加權(quán)質(zhì)心算法；文獻(xiàn)12首先

8、將二維 DV-hop 擴(kuò) 展到三維 DV-hop，然后在三維 DV-hop 算法的基礎(chǔ) 上，對形狀和層次結(jié)構(gòu)進(jìn)行分析，接著引入共面和投 影的性質(zhì)，實(shí)現(xiàn)位置定位。這些算法采用將二維平面 的算法加上 Z 軸坐標(biāo)直接拓展為三維空間算法，然而 由于三維空間相對于二維平面更加復(fù)雜，所以這樣簡 單的轉(zhuǎn)化衍生的效果并不太理想。還有另外一種解決 三維定位問題的思路，是把三維問題轉(zhuǎn)化為二維問題，然后利用二維定位算法將問題解決，最后再將結(jié)果轉(zhuǎn) 化為三維結(jié)果。比如文獻(xiàn)13中利用水下聲音傳感器 提出一種水下定位算法，就是把三維的水下環(huán)境轉(zhuǎn)化 為二維來解決問題。另外還有的是提出了新型的三維定位算法，文獻(xiàn)14 提出了一個

9、基于空間限定的三維定位算法 Constrain 3-D，基于傳統(tǒng)的三角運(yùn)算，測量并計(jì)算與鄰接節(jié)點(diǎn)的距離來估計(jì)自身位置；文獻(xiàn)15通過使用數(shù)學(xué)中向量和矩陣的理論，進(jìn)行四面體的構(gòu)造，然后通過四面體的質(zhì)心估算未知節(jié)點(diǎn)的位置；文獻(xiàn)16在其他三維定位算法的基礎(chǔ)上，引入位置估算偏差值，然后使用加權(quán)質(zhì)心算法進(jìn)行位置估算。本文中，筆者對四面體的形狀特征和體積進(jìn)行分析，基于數(shù)學(xué)中的幾何原理，引入體積比閾值并結(jié)合四面體質(zhì)心算法進(jìn)行位置估算，提出一個新的三維定位算法。論文的余下內(nèi)容分為四部分，第 1 部分概述四面體質(zhì)心算法的推導(dǎo)過程；第 2 部分介紹理論背景，并在第 3 部分我們提出的新算法并給出算法原理及步驟；第

10、4 部分與第 5 部分中我們將提出的算法進(jìn)行詳細(xì)的仿真并分析；最后在第 6 部分中，我們得出總結(jié)。2 12 12 13 23 24 34 316 3 2=4 3坐 標(biāo) 為 (x, y, z) ， 令 A =設(shè) 未 知 節(jié) 點(diǎn)1122211134113434然后通過(1)我們推導(dǎo)未知節(jié)點(diǎn) K(1, 2, 3, 4)，則34341= =2 3 4(2)= 1 (+ + + )1121314162= =3413 4(3)34= 1 (+ + + )1222324263= =41241 24(4)= 1 (+ + + )1323334364= =31 2 3(5)123= 1 (+ + + )1424

11、34446從式(2)至式(5)可以推得12112131411111122232423 =46= 6 (6)33344411四面體質(zhì)心定位算法21 3 = (7)三維空間中，文獻(xiàn)17利用數(shù)學(xué)中四面體坐標(biāo)的 理論提出了一種四面體質(zhì)心算法。以下簡述具體過程：引理： 假設(shè)四面體 頂點(diǎn) 的坐標(biāo)為 411112令1 = 222則，根據(jù)(7)可以轉(zhuǎn)換( , , ),那么其體積可由如下行列式表示：34333444 (=1,2,3,4)V =4(1)23推出1234 = (8)3計(jì) 算機(jī)研究與 發(fā) 展11 =221其中 = x, y, z，h = 3 3， (14)21623 ( +

12、+ )( + )( + )( + )=044DCP = 0 , 111(15), = 222。333444用最小二乘法(LS),可以推得DCP 的值域?yàn)?0,1，其中當(dāng) DCP 的值趨近于 1時，四面體越趨近于正四面體；反之，當(dāng) DCP 的值趨近于 0 時，四面體四個頂點(diǎn)越接近共面。 = ( )1(9) 經(jīng)過計(jì)算可以得出114111222141 = 3 3 = 14 3(10)2.2 區(qū)域位置限制文獻(xiàn)17中介紹四面體質(zhì)心算法，首先未知節(jié)點(diǎn)選取周邊最近的四個信標(biāo)節(jié)點(diǎn)并把它們組成四面體，然后將四面體的質(zhì)心的坐標(biāo)位置作為未知節(jié)點(diǎn)的坐標(biāo)，從而實(shí)現(xiàn)三維空間的定位。但在這種四面體質(zhì)心算法中，未知節(jié)點(diǎn)本身可

13、能在組成的四面體區(qū)域的外部，這種情況將會引起較大的節(jié)點(diǎn)定位誤差，因此為了避免出現(xiàn)此類狀況，我們通過設(shè)定一個閾值，來保證未知節(jié)點(diǎn)處于組成的四面體的區(qū)域內(nèi)，具體如下。如圖 1 所示，假設(shè)四面體1234 的體積為44414從(8)和(10)式我們可以計(jì)算未知節(jié)點(diǎn)的坐標(biāo)1 = ( )1(11) 12理論背景在第三節(jié)介紹我們提出的基于共面性與區(qū)域限制的 WSN 定位算法之前，需要先介紹一些新算法中用的基本概念，分別是四面體的共面性判斷和如何進(jìn)行區(qū)域位置的限制。1234 ， M為四面體質(zhì)心的估計(jì)節(jié)點(diǎn)， 則有M234、1M34、12M4、123M 四個小四面體，體積分別是234 、134 、124 、2.1

14、 四面體的共面性判斷四面體的共面性(Degree of Coplanarity, DCP)可以用于判斷四面體共面程度，文獻(xiàn)18和19已經(jīng)進(jìn)行了對四面體的研究并且在定位里有所應(yīng)用，其中文獻(xiàn)18描述測量方法有“最小立體角(Minimum Solid Angle)”、“半徑比(Radius Ratio)”和“平均比(Mean Ratio)”三種，而文獻(xiàn)19將半徑比應(yīng)用于三維定位算法，這次我們也使用半徑比來判斷共面程度，并將其與質(zhì)心算法相結(jié)合。判斷的公式定義為： = 3/，其中代表四面體內(nèi)切球的半徑，代表四面體外接球的半徑，為半徑比，值域?yàn)?0,1。四面體內(nèi)切球與外接球的半徑公式為：123。為了判斷點(diǎn)

15、 M 是否在四面體1234內(nèi)部，我們引入一個體積比閾值 T： =234 + 134 + 124 + 123234(16)從純理論上講，當(dāng)點(diǎn) M 在四面體1234內(nèi)部時，四面體1234的體積應(yīng)當(dāng)?shù)扔谒膫€小四面體的體積之和，即 T=1，此時即可保證未知節(jié)點(diǎn)一定在四面體內(nèi)部。但由于在實(shí)際中 M 的坐標(biāo)為測量值，存在誤差，所以 T 的范圍則非常不確定。我們將最終確定一個 T 的閾值，以確保滿足閾值條件的四面體均能保證未知節(jié)點(diǎn)在其區(qū)域內(nèi)部。關(guān)于 T 值的選擇將在第4 部分閾值選取中予以分析。3 =(12)3=0 =( + + )( + )( + )( + )(13)24其中 v 為四面體的體積，為四面體

16、四個面的面積，a、b、c 為分別為四面體的三條對邊，接著將(12)和(13)結(jié)合：4計(jì)算機(jī)研究與發(fā)展開始NNDCP是否滿足？Y區(qū)域位置是否在附近？圖 1 四面體1234Y3基于共面性與區(qū)域限制的三維WSN 定位算法我們提出的基于共面性與區(qū)域限制的 WSN 定位算法是通過設(shè)定的閾值不斷進(jìn)行篩選，對符合條件的四面體運(yùn)用四面體質(zhì)心定位，再將各四面體質(zhì)心定位的結(jié)果的平均值作為未知節(jié)點(diǎn)最后的位置坐標(biāo)，具體步驟如下：第 1 步：信標(biāo)節(jié)點(diǎn)在它的通信范圍內(nèi)廣播自身的位置信息，未知節(jié)點(diǎn)收集到信標(biāo)節(jié)點(diǎn)的信息，并收集和計(jì)算節(jié)點(diǎn)到節(jié)點(diǎn)之間的距離；第 2 步：每個未知節(jié)點(diǎn)對通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)按照遠(yuǎn)近順序進(jìn)行編號，并將

17、在其通信半徑內(nèi)所有信標(biāo)節(jié)點(diǎn)按照編號順序每次選取四個點(diǎn)組成四面體；第 3 步：對上一步組成的四面體進(jìn)行 DCP 閾值判斷，如果滿足條件則進(jìn)入下一步，如果不滿足條件則返回第二步按照順序重新選擇四面體；第 4 步：對第三部符合條件的四面體進(jìn)行體積比 倍數(shù)閾值的判斷，如果小于等于此閾值則繼續(xù)下一步，如果不滿足閾值條件則返回第二步按照順序重新構(gòu) 造四面體；第 5 步：對步驟 4 得到的四面體進(jìn)行四面體質(zhì)心定位算法，得到未知節(jié)點(diǎn)的測量坐標(biāo)。通過一系列滿足條件的四面體可以得到未知節(jié)點(diǎn)的一系列測量坐標(biāo)，計(jì)算出這些測量坐標(biāo)的平均值，并將其作為未知節(jié)點(diǎn)的最終坐標(biāo)。之后再繼續(xù)下一個未知點(diǎn)的定位。流程圖如圖 2 所示

18、。結(jié)束圖 2 算法流程圖4閾值分析上一節(jié)我們提出基于共面性和區(qū)域限制的 WSN定位算法，并且給出了算法步驟與流程圖。其中，我們設(shè)定了兩個閾值來作為對四面體的約束，然而如何選取合適的閾值，既讓算法有更好的定位精度，又能保證算法的穩(wěn)定性，成為算法的關(guān)鍵所在。對此，在這節(jié)中我們對閾值的取值進(jìn)行詳細(xì)的分析，實(shí)驗(yàn)采用的工具是 MATLAB。4.1 共面性閾值在共面性閾值(Degree of Coplanarity)的分析中，我們分別改變信標(biāo)節(jié)點(diǎn)比率、通信半徑和節(jié)點(diǎn)數(shù)目來觀察不同參數(shù)條件下不同閾值對定位精度的影響。在這個環(huán)節(jié)中，我們并未加入體積比閾值。首先，我們先設(shè)定一組參數(shù)來討論共面性閾值對定位精度的影

19、響，之后再通過改變實(shí)驗(yàn)參數(shù)獲取不同參數(shù)下 DCP 閾值對定位精度的影響。其中，圖 3 為實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)參數(shù)如表 1。圖 4 表示的是在第一組參數(shù)實(shí)驗(yàn)的基礎(chǔ)上，將信標(biāo)節(jié)點(diǎn)比率改為 30%，其他參數(shù)不變的情況下，共面性閾值對定位的影響，實(shí)驗(yàn)參數(shù)如表 2。同理圖 5 和取一系列未知點(diǎn)的平均值作為未知節(jié)點(diǎn)的最終坐標(biāo)四面體質(zhì)心求得估計(jì)未知點(diǎn)坐標(biāo)每個未知節(jié)點(diǎn)規(guī)則地選取四面體組未知節(jié)點(diǎn)收集信息信標(biāo)節(jié)點(diǎn)廣播節(jié)點(diǎn)位置5計(jì) 算 機(jī)研究與 發(fā) 展圖 6 分別表示了其他參數(shù)條件下共面性閾值對定位精度的影響，對應(yīng)的參數(shù)表分別為表 3 和表 4。表 1 共面性閾值對定位誤差的影響的實(shí)驗(yàn)參數(shù)（1）表 3 共面性閾值對定位誤

20、差的影響的實(shí)驗(yàn)參數(shù)（3）實(shí)驗(yàn)參數(shù)參數(shù)值實(shí)驗(yàn)參數(shù)參數(shù)值100m 100m 100m100 個15%100m 100m 100m100 個15%空間區(qū)域空間區(qū)域節(jié)點(diǎn)數(shù)目節(jié)點(diǎn)數(shù)目信標(biāo)節(jié)點(diǎn)比率信標(biāo)節(jié)點(diǎn)比率通信半徑50m0.10.9通信半徑70m0.10.9DCP()DCP()圖 3 不同參數(shù)下共面性閾值對定位誤差的影響（1）圖 5 不同參數(shù)下共面性閾值對定位誤差的影響（3）表 2 共面性閾值對定位誤差的影響的實(shí)驗(yàn)參數(shù)（2）表 4 共面性閾值對定位誤差的影響的實(shí)驗(yàn)參數(shù)（4）實(shí)驗(yàn)參數(shù)參數(shù)值實(shí)驗(yàn)參數(shù)參數(shù)值100m 100m 100m100 個100m 100m 100m300 個空間區(qū)域空間區(qū)域節(jié)點(diǎn)數(shù)目節(jié)點(diǎn)

21、數(shù)目信標(biāo)節(jié)點(diǎn)比率30%50m信標(biāo)節(jié)點(diǎn)比率15%50m通信半徑通信半徑DCP()0.10.9DCP()0.10.9圖 4 不同參數(shù)下共面性閾值對定位誤差的影響（2）圖 6 不同參數(shù)下共面性閾值對定位誤差的影響（4）6計(jì) 算 機(jī) 研究 與 發(fā) 展表 6 體積比閾值 T 對定位誤差的影響的實(shí)驗(yàn)參數(shù)（2）實(shí)驗(yàn)參數(shù)參數(shù)值從上述四組實(shí)驗(yàn)中我們可以看出，不同參數(shù)下，隨著共面性閾值的不斷增加，定位誤差總有著下降的趨勢，即不論參數(shù)如何變化，總是共面性閾值越大效果越好。但我們在實(shí)驗(yàn)中也發(fā)現(xiàn)當(dāng)我們選取的閾值大于 0.9 時，算法的穩(wěn)定性明顯降低，因此我們選取 0.9作為我們算法的最終共面性閾值。空間區(qū)域100m 1

22、00m 100m200 個30%節(jié)點(diǎn)數(shù)目信標(biāo)節(jié)點(diǎn)比率通信半徑50m0.9DCP()體積比閾值 T0.754.2 體積比閾值 T在關(guān)于共面性閾值對定位誤差影響的討論中，我們最終選擇設(shè) 0.9 作為我們算法的共面性閾值。在這個前提下，我們進(jìn)行體積比閾值的討論，同理我們設(shè)置不同的參數(shù)來對比不同情況下體積比閾值對定位誤差的影響。首先設(shè)定一組參數(shù)討論體積比閾值 T 對定位精度的影響，結(jié)果為圖 7 所示，參數(shù)如表 5。圖 8、圖 9、圖 10 分別表示了其他參數(shù)條件下定位誤差率與體積比閾值的關(guān)系，對應(yīng)的參數(shù)表分別為表 6、表 7 和表 8。圖 8 不同參數(shù)下體積比閾值 T 對定位誤差的影響（2）表 5 體

23、積比閾值 T 對定位誤差的影響的實(shí)驗(yàn)參數(shù)（1）表 7 體積比閾值 T 對定位誤差的影響的實(shí)驗(yàn)參數(shù)（3）實(shí)驗(yàn)參數(shù)參數(shù)值實(shí)驗(yàn)參數(shù)參數(shù)值100m 100m 100m200 個空間區(qū)域100m 100m 100m200 個15%70m空間區(qū)域節(jié)點(diǎn)數(shù)目節(jié)點(diǎn)數(shù)目信標(biāo)節(jié)點(diǎn)比率15%信標(biāo)節(jié)點(diǎn)比率通信半徑50m0.9通信半徑DCP()DCP()體積比閾值 T0.90.75體積比閾值 T0.75圖 7 不同參數(shù)下體積比閾值 T 對定位誤差的影響（1）圖 9 不同參數(shù)下體積比閾值 T 對定位誤差的影響（3）7計(jì) 算 機(jī)研究與發(fā) 展表 8 體積比閾值 T 對定位誤差的影響的實(shí)驗(yàn)參數(shù)（4）表 9 改變信標(biāo)節(jié)點(diǎn)比率的實(shí)驗(yàn)

24、參數(shù)實(shí)驗(yàn)參數(shù)參數(shù)值實(shí)驗(yàn)參數(shù)參數(shù)值空間區(qū)域100m 100m 100m400 個15%空間區(qū)域100m 100m 100m200 個10%25%節(jié)點(diǎn)數(shù)目節(jié)點(diǎn)數(shù)目信標(biāo)節(jié)點(diǎn)比率信標(biāo)節(jié)點(diǎn)比率通信半徑50m0.9通信半徑50m0.9DCP()DCP()體積比閾值 T0.75體積比閾值 T1圖 10 不同參數(shù)下體積比閾值 T 對定位誤差的影響（4）圖 11 改變信標(biāo)節(jié)點(diǎn)比率對定位誤差產(chǎn)生的影響由上述四圖可知，我們發(fā)現(xiàn)體積比閾值大于 1 時，定位誤差上升較為快速，小于1 則誤差變化不明顯。同時這與我們之前分析的純理論環(huán)境下的閾值非常接近，所以我們設(shè)1 為我們新算法的體積比閾值。即如果 T1，則說明 M 點(diǎn)在

25、此四面體區(qū)域內(nèi)部或附近，不會偏離較遠(yuǎn)；否則則與估計(jì)位置偏離區(qū)域較大。接著我們測試不同通信半徑對定位誤差的影響， 實(shí)驗(yàn)參數(shù)設(shè)定如表 10。結(jié)果如圖 12 所示，三角標(biāo)注 的線為原始的三維 DV-hop 算法，圓圈標(biāo)注的線為傳 統(tǒng)的質(zhì)心算法，星號標(biāo)注的線為我們提出的新三維定 位算法。隨著通信半徑的不斷增大，新型的 WSN 定 位算法依然優(yōu)于傳統(tǒng)的兩種算法，而且在較小的通信 半徑區(qū)域內(nèi)這種優(yōu)勢較為明顯。當(dāng)通信半徑增大到 85 以上時，質(zhì)心算法的精度優(yōu)于傳統(tǒng)三維 DV-hop 算法，但是無論通信半徑如何變化，我們的新算法總是最優(yōu)的。5實(shí)驗(yàn)結(jié)果與仿真分析接下來我們對提出的算法進(jìn)行仿真實(shí)驗(yàn)，我們將通過改變

26、不同參數(shù)，從不同角度分析比較我們的新算法與傳統(tǒng)三維 DV-hop 算法及經(jīng)典質(zhì)心算法的區(qū)別。在以下的所有仿真實(shí)驗(yàn)中，我們每個實(shí)驗(yàn)都執(zhí)行 100次然后取 100 個數(shù)據(jù)的平均值作為實(shí)驗(yàn)結(jié)果。圖 11 表示我們通過改變信標(biāo)節(jié)點(diǎn)的比率來對比在不同信標(biāo)節(jié)點(diǎn)比例的情況下三個算法的性能。三角標(biāo)注的線為原始的三維 DV-hop 算法，圓圈標(biāo)注的線為傳統(tǒng)的質(zhì)心算法，星號標(biāo)注的線為我們提出的新三維定位算法。同傳統(tǒng)的三維 DV-hop 算法和質(zhì)心算法進(jìn)行對比，實(shí)驗(yàn)參數(shù)如表 9。無論信標(biāo)節(jié)點(diǎn)比例如何變化，新三維 WSN 定位算法精度總是比其他兩個算法高，而且對比原始 DV-hop 算法效果更為明顯。表 10 改變通

27、信半徑的實(shí)驗(yàn)參數(shù)實(shí)驗(yàn)參數(shù)參數(shù)值100m 100m 100m200 個20%空間區(qū)域節(jié)點(diǎn)數(shù)目信標(biāo)節(jié)點(diǎn)比率通信半徑30m100m0.9DCP()體積比閾值 T18計(jì) 算 機(jī)研究 與 發(fā) 展綜上所述，通過與傳統(tǒng)的三維 DV-hop 算法和質(zhì)心算法的比較，我們得出基于共面性與區(qū)域限制的三維定位算法在定位準(zhǔn)確度方面有著較為明顯的提高，而且有更好的穩(wěn)定性。6 結(jié)束語我們提出了一種新的基于共面性與區(qū)域限制的 WSN 三維定位算法，并對該算法進(jìn)行大量的仿真實(shí) 驗(yàn)。結(jié)果表明，相比于兩種傳統(tǒng)的三維定位算法，新 算法能有效地降低節(jié)點(diǎn)定位誤差，并且提高定位的穩(wěn) 定性。另外該算法是在三維環(huán)境中布置的，相比較二 維平面的

28、定位算法而言，更具有實(shí)際性質(zhì)。另一方面，本算法雖然定位誤差降低，但算法復(fù)雜性也有所增加，未來我們將繼續(xù)對三維定位算法進(jìn)行改進(jìn)與優(yōu)化以獲得定位精度與算法復(fù)雜度的平衡。圖 12 改變通信半徑對定位誤差的影響最后我們測試改變總節(jié)點(diǎn)數(shù)目對定位的影響，實(shí)驗(yàn)參數(shù)設(shè)定如表 11。結(jié)果如圖 13 顯示，三角標(biāo)注的線為原始的三維 DV-hop 算法，圓圈標(biāo)注的線為傳統(tǒng)的質(zhì)心算法，星號標(biāo)注的線為我們提出的新三維定位算法。其中，傳統(tǒng)的質(zhì)心算法在改變節(jié)點(diǎn)數(shù)目中優(yōu)于原始的三維 DV-hop 算法，而我們所提出的三維質(zhì)心算法優(yōu)于傳統(tǒng)的質(zhì)心算法，與原始的三維 DV-hop 相比則效果更為明顯。參 考 文 獻(xiàn)1Akyildi

29、z, I. F., Su, W., Sankarasubramaniam, Y, & Cayirci, E. (2002).Wireless sensor networks: a survey. Computer networks, 38(4), 393-422. MAO, Guoqiang; FIDAN, Bar; ANDERSON, Brian DO. Wirelesssensor network localization techniques. Computer networks, 2007, 51.10:2表 11 改變節(jié)點(diǎn)數(shù)目的實(shí)驗(yàn)參數(shù)2529-2553.Zhang J, Yang

30、R, Li J. An Enhanced DV-Hop Localization Algorithm3實(shí)驗(yàn)參數(shù)參數(shù)值using RSSI. 2013.T.S.Rappapport, Wireless Communications: Principles and Practice. Prentice Hall: New Jersey, pp.50-143 1996.100m 100m 100m200600 個空間區(qū)域4節(jié)點(diǎn)數(shù)目信標(biāo)節(jié)點(diǎn)比率15%40m5X. Cheng, T. A, G. Xue, D. Chen, “TPS: a time-based positioning scheme通信半

31、徑for outdoor wireless sensor networks,” IEEE2004, HongDCP()體積比閾值 T0.91Kong, China. pp. 2685-2696, March, 2004.T. D. J. “Statistical theory of passive location systems,” IEEE Trans. on AES. vol.20, no.2, pp. 183-198, Mar.1984.67Niculescu D, Nath B. Ad-hoc positioning system (APS). Proc. of theIEEE, S

32、an Antonio, 2001:2926-2931.8Niculescu D, Nath B. DV Based Positioning in Ad hoc Networks. Journalofmunication Systems, 2003, 22(1-4):267-2809Bulusu N, Heidemann J, Estrin D. GPS-less low cost outdoor localizationfor very small devices. IEEE Personal Communicaitons Magzine, 2000,7(5):28-3410 He T, Hu

33、ang C D, Blum B M, Stankovic J A, Abdelzaher T. Range-freeLocalization Schemes for Large Scale Sensor Netowrks. In: Poc. of 9th Annual International conference on Mobile Computing and Networking .San Diego USA: ACM, 2003.81-9511 XU, Lisheng, et al. A study on 2D and 3D weighted centroid localization

34、圖 13 改變節(jié)點(diǎn)數(shù)目對定位誤差的影響9計(jì) 算 機(jī) 研究與發(fā)展algorithm in Wireless Sensor Networks. In: Advanced Computer Control(ICACC), 2011 3rd International Conference on. IEEE, 2011. p. 155-159.12 陳慶章, et al. 基于共面度和分層結(jié)構(gòu)的 WSN 三維定位算法. 電子測量與儀器學(xué)報(bào), 2012, 26.8: 673-680.13 Cheng, W., Teymorian, A. Y., Ma, L., Cheng, X., Lu, X., & Lu, Z. (2008,April). Underwater localizat