引言

作為信息采集和數(shù)據(jù)處理的關(guān)鍵組成部分，無線傳感器網(wǎng)絡(luò)（ wireless sensor networks,WSNs） 也得到了快速發(fā)展。WSNs 是集無線通信技術(shù)、傳感器技術(shù)、嵌入式計算技術(shù)、信息處理技術(shù)、組網(wǎng)技術(shù)等現(xiàn)代網(wǎng)絡(luò)技術(shù)于一體的網(wǎng)絡(luò)，突出優(yōu)點是能在惡劣環(huán)境下實現(xiàn)無線的信息采集和處理，具有非常廣的應(yīng)用前景。節(jié)點的位置信息是WSNs實現(xiàn)應(yīng)用的重要一環(huán)，目前，針對節(jié)點定位的研究中有很多很成熟的算法，依據(jù)是不是需要測距，主要分為基于測距算法（ range-based） ,典型的有cooperative ranging 算法、NHopmultilateration primitive 算法、Euclidean等，無需測距算法，典型的有DV-Hop 算法、Amorphous 算法、APIT算法、Bounding Box 算法、Centroid 算法等。

由于WSNs 的節(jié)點非常多，雖然測距算法有很好的精度保證，但節(jié)點必須攜帶額外的測距設(shè)備，這樣會很大程度上增加定位成本，而無需測距盡管不如測距那樣準(zhǔn)確，但在很多應(yīng)用場合能達(dá)到需要的精度，而且在功耗等方面有較大的優(yōu)勢。本文選取無需測距算法中典型的4 個算法，包括Amorphous 算法、APIT 算法、Bounding Box 算法、Centroid算法，分別給出在不同參數(shù)條件下的仿真定位效果，以便于技術(shù)人員在不同條件下選取最優(yōu)的算法。

1 無需測距算法原理

1. 1 Amorphous 算法

Amorphous 算法是由麻省理工大學(xué)的Nagpal R 等人提出的，其主要思想就是把錨節(jié)點和未知節(jié)點的跳數(shù)以及平均每跳距離的乘積作為兩者之間的距離，共分三步： 1） 根據(jù)距離矢量交換協(xié)議，使網(wǎng)絡(luò)中的每個節(jié)點都獲得到錨節(jié)點的最小跳數(shù)； 2） 平均每跳距離用節(jié)點的通信半徑表示，未知節(jié)點計算到每個錨節(jié)點的距離； 3） 利用最大似然估計或者三角測量法估計未知節(jié)點的位置。

1. 2 APIT 算法

APIT 算法基本思路是，未知節(jié)點首先收集鄰近錨節(jié)點的信息。假設(shè)其周圍有n 個錨節(jié)點能與未知節(jié)點通信，然后未知節(jié)點任意選取其中的3 個錨節(jié)點，這樣就確定C3n個三角形。之后利用PIT 測試法逐一判斷未知節(jié)點是否在這些三角形中，最后計算包含未知節(jié)點的那些三角形重疊區(qū)域，把該重疊區(qū)域的質(zhì)心作為未知節(jié)點的位置。

1. 3 Bounding Box 算法

Bounding Box 算法是由美國加州大學(xué)伯克利分校Semic S N 等人提出的，該算法與APIT 的算法有相似之處，也是計算包含未知節(jié)點的重疊區(qū)域。只不過該算法定義一種離散的通信模型，這里假定節(jié)點的通信范圍是以2 倍的通信半徑為變長，以自身為中心的正方形。如果未知節(jié)點周圍有m 個錨節(jié)點能與其通信，則計算這些錨節(jié)點所組成的正方形重疊區(qū)域，以該重疊區(qū)域的中心作為未知節(jié)點的位置。

1. 4 Centroid 算法

Centroid 算法基本思想是，網(wǎng)絡(luò)約定一個定位時間，在該時間段內(nèi)，錨節(jié)點向未知節(jié)點發(fā)送包含自身未知信息的數(shù)據(jù)包。未知節(jié)點記錄下從每個錨節(jié)點的發(fā)來的數(shù)據(jù)包數(shù)目，等到定位時間結(jié)束后，未知節(jié)點計算與錨節(jié)點的通信成功率。根據(jù)預(yù)先設(shè)定的閥值，選出那些通信成功的錨節(jié)點，最后把這些錨節(jié)點的質(zhì)心作為未知節(jié)點的坐標(biāo)。

2 算法仿真比較

本文給出了以上述4 種無需測距定位算法在不同參數(shù)下的仿真結(jié)果比較，通過分析這些結(jié)果，結(jié)合實際情況可以選擇最優(yōu)的定位算法。

本文分別從定位誤差和定位精度2 個方面考慮，模擬200 m × 200 m 的區(qū)域，節(jié)點的部署都采用隨機(jī)撒播的方式。

本文平均定位誤差定義為估計位置到真實位置的歐式距離與通信半徑的比值。定位比例定義為除錨節(jié)點之外成功定位的節(jié)點數(shù)和未知節(jié)點的總數(shù)的比值。使用Matlab 仿真軟件。

1） 假定區(qū)域有150 個節(jié)點，包括錨節(jié)點和未知節(jié)點，采用散亂撒播的方式。無線傳感器的節(jié)點的能量有限，通信半徑一般在幾十米左右、不失一般性，這里假定通信半徑為30 m,把錨節(jié)點的比例作為變量，給出比較仿真結(jié)果如圖1、圖2 所示。

圖1 散亂布置條件下平均定位誤差隨錨節(jié)點比例變化趨勢圖

圖2 散亂布置條件下定位比例隨錨節(jié)點比例變化趨勢圖

2） 和第一部分參數(shù)設(shè)置相同，但這里固定錨節(jié)點比例為10 %,考察定位誤差和定位比例隨通信距離變化情況，仿真結(jié)果如圖3、圖4 所示。

圖3 散亂布置條件下平均定位誤差隨通信半徑變化趨勢圖

圖4 散亂布置條件下定位比例隨通信半徑變化趨勢圖

3） 采用規(guī)則部署的方式，即把這部分區(qū)域采用網(wǎng)格法劃分成一個個規(guī)則的小正方形區(qū)域，每個節(jié)點部署隨機(jī)部署在小正方形邊上。為了和第一，二部分相似，這里設(shè)置小正方形邊長為17 m,那么，總節(jié)點數(shù)大約為144 個，錨節(jié)點和未知節(jié)點的部署仍采用隨機(jī)撒播方式。這里假定通信半徑為30 m,考察定位誤差和定位比例隨錨節(jié)點比例變化情況，仿真結(jié)果如圖5、圖6 所示。

圖5 規(guī)則部署條件下平均定位誤差隨錨節(jié)點比例變化趨勢圖

圖6 規(guī)則部署條件下定位比例隨錨節(jié)點比例變化趨勢圖

4） 參數(shù)和第三部分相同，只是這里固定錨節(jié)點比例為15 %,因為在這一部分錨節(jié)點比例為10 % 時仿真顯示有些算法的定位效果不太明顯，不易對比?？疾於ㄎ徽`差和定位比例隨隨通信半徑變化趨勢，仿真結(jié)果如圖7、圖8 所示。

圖7 規(guī)則部署條件下平均定位誤差隨通信半徑變化趨勢圖

圖8 規(guī)則部署條件下定位比例隨通信半徑變化趨勢圖

通過這些仿真圖，可以很方便地查找適合需要的定位算法。

例如： 對某一區(qū)域進(jìn)行定位，屬于隨機(jī)散亂部署情況，要求定位精度不是很高但要穩(wěn)定，但是定位比例要求要大，最重要成本要求很小，只是簡單的測試，而且要求能長時間工作。在這種要求情況下，考察圖1 ~ 圖4.注意到隨機(jī)散亂部署的情況下，Amorphous 算法雖然定位比例幾乎為100 %,但誤差大，且有很大跳躍性，排除。APIT 算法雖然定位精度最高，但定位的比例隨錨節(jié)點變化非常明顯，這顯然會需要很多錨節(jié)點，這樣會很大程度上增加成本，排除。

WSNs 節(jié)點的通信半徑會隨著發(fā)射功率減少而減少，為了能長時間工作，要求網(wǎng)絡(luò)能在通信距離較小時也能準(zhǔn)確定位。

Bounding Box 算法和Centroid 算法2 種算法，定位效果隨通信半徑變化的趨勢（ 圖3、圖4） 基本吻合，而且2 種算法的定位誤差在通信半徑相同時，變化趨勢（ 圖1） 基本相同，但注意到圖2,在錨節(jié)點比例相同情況，而且在錨節(jié)點比例較小區(qū)域（ 20%以下） ,Bounding Box 算法比Centroid 算法有更高的定位比例，所以，最終選擇Bounding Box 算法。然后根據(jù)實際具體的參數(shù)部署節(jié)點，在定位算法上選擇BoundingBox 算法即可。

使用Matlab 軟件給出一個具體的函數(shù)，例如： 對圖6 中Bounding Box 算法的變化趨勢圖，利用Matlab 曲線擬合函數(shù)，測試結(jié)果如圖9 所示。

圖9 數(shù)據(jù)擬合曲線圖

可以發(fā)現(xiàn)N = 2 階的擬合曲線和原曲線比較接近，故采用N = 2 階曲線擬合函數(shù)，根據(jù)Matlab 的計算結(jié)果，有：

確定這樣一個函數(shù)后就可以根據(jù)實際具體的需要值代入就可以計算出定位的效果。其他的算法在不同參數(shù)條件下利用這種方法確定一個函數(shù)，進(jìn)而計算出定位效果。

這里分別考慮散亂部署和規(guī)則部署2 種情況，對于每一種情況，f（ x） ,g（ x） 表示擬合定位誤差函數(shù)和擬合定位比例函數(shù)，x i（ i = 1,2,3,4） 分別表示APIT 算法，Amorphous算法，Bounding Box 算法，Centroid 算法錨節(jié)點比例，y i = 1,2,3,4分別表示以上4 種算法的通信半徑，wi,w2分別表示考慮定位誤差和定位比例的權(quán)重，定義定位效果Ci,這樣有：

根據(jù)實際給出的成本參數(shù)轉(zhuǎn)換為錨節(jié)點的比例，再根據(jù)實際要求的工作時間長短換算成一定通信半徑，代入上式就可以求出定位效果，最后有：

根據(jù)式（ 3） 求出定位效果中取得最大值的算法，這樣就確定哪種算法最優(yōu)了。

3 結(jié)束語

本文給出了無需測距算法中典型的4 種定位算法，給出了它們分別在不同參數(shù)下的仿真定位效果，對工程人員選擇適合的算法提供了很好借鑒，在此基礎(chǔ)上，本文提出了一種基于數(shù)據(jù)擬合方法的定位效果逼近函數(shù)，并根據(jù)這些函數(shù)給出了具體的計算公式，這樣就能根據(jù)實際要求，轉(zhuǎn)換為某范圍或某具體值代入計算公式就可以確定哪種算法最優(yōu)了。