引言

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

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

1 無需測(cè)距算法原理

1. 1 Amorphous 算法

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

1. 2 APIT 算法

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

1. 3 Bounding Box 算法

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

1. 4 Centroid 算法

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

2 算法仿真比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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