無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述

3) 極大似然估計法。如圖4 所示， 已知n 個點的坐標和它們到未知節(jié)點的距離， 列出坐標與距離的n 個方程式， 從第1 個方程開始， 每個方程均減去最后一個方程， 得到n?1 個方程組成的線性方程組，最后用最小二乘估計法可以得到未知節(jié)點的坐標。

圖4 極大似然估計法原理示意圖

4) 極小極大定位算法， 在無線傳感器網(wǎng)絡(luò)定位中也被廣泛使用。如圖5 所示， 計算未知節(jié)點與錨節(jié)點的距離， 接著錨節(jié)點根據(jù)與未知節(jié)點的距離d, 以自身為中心， 畫以2d 為邊長的正方形， 所有錨節(jié)點做出的正方形中重疊的部分的質(zhì)心就是未知節(jié)點的坐標。針對極小極大定位算法對錨節(jié)點密度依賴過高的問題， 有學者利用錨節(jié)點位置信息提出了分步求精定位算法， 該算法在只利用適量的錨節(jié)點的情況下可達到較高定位精度。

圖5 極小極大定位算法原理示意圖

文獻[35]在12 m×19.5 m 的范圍內(nèi)對上述三邊測量法、極大似然估計法和極小極大法方法的計算量和精度進行了測試。實驗表明， 極大似然估計法的計算量最大， 錨節(jié)點小于10 個時， 極小極大法的計算量最小， 在錨節(jié)點較少情況下， 三邊法和極小極大法的精確度較高， 而當錨節(jié)點超過6 個時， 極大似然估計法精確度更高。因此， 在計算坐標時要根據(jù)實際情況合理選擇坐標計算方法。另外， 針對現(xiàn)存的定位算法都是假設(shè)信標節(jié)點不存在誤差， 與真實情況不符的情況， 文獻[36]提出信標優(yōu)化選擇定位算法(OBS)， 即通過減小定位過程中的誤差傳遞來提高定位精度。

3.2 基于非測距的算法

基于非測距的算法與測距法的區(qū)別在于前者不直接對距離進行測量， 而是使用網(wǎng)絡(luò)的連通度來估計節(jié)點距錨節(jié)點的距離或坐標， 由于方法的不確定性， 基于非測距的方法眾多。下面按時間順序，介紹部分典型非測距定位算法。

Bulusu 等人提出了一個單跳， 低功耗的算法，它利用錨節(jié)點的連通性來確定坐標。未知節(jié)點的坐標通過計算無線電范圍內(nèi)所有節(jié)點的質(zhì)心獲得。節(jié)點將自己定位在與它們表現(xiàn)相近節(jié)點的質(zhì)心處， 該算法雖然簡單， 但誤差較大， 需要的錨節(jié)點密度較高。約90%節(jié)點的定位精度在錨節(jié)點分布間距的1/3以內(nèi)。

He 等人提出了APIT 算法， 目標節(jié)點任選3 個相鄰錨節(jié)點， 測試未知節(jié)點是否位于它們所組成的三角形中。使用不同錨節(jié)點組合重復(fù)測試直到窮盡所有組合或達到所需定位精度。最后計算包含目標節(jié)點的所有三角形的交集質(zhì)心， 并以這一點作為目標節(jié)點位置， 該算法需要較高的錨節(jié)點密度， 其定位精度為40%。

Niculescu 等人提出了DV-Hop 定位算法， 它從網(wǎng)絡(luò)中收集相鄰節(jié)點信息， 計算不相鄰節(jié)點之間最短路徑。DV-Hop 算法使用已知位置節(jié)點的坐標來估測一個跳躍距離， 并使用最短路徑的跳躍距離估計未知節(jié)點和錨節(jié)點的距離， 該算法僅適用于各向同性的密集網(wǎng)絡(luò)， 當錨節(jié)點密度為10%時， 定位誤差為33%。

Radhika 等人提出的Amorphous Positioning 算法，使用離線的跳躍距離估測， 同DV-Hop 算法一樣， 通過一個相鄰節(jié)點的信息交換來提高定位的估測值，需要預(yù)知網(wǎng)絡(luò)連通度， 當網(wǎng)絡(luò)連通度為15 時， 定位精度20%。

Savvides 等人介紹了一種N-Hop multilateration算法， 使用卡爾曼濾波技術(shù)循環(huán)求精， 該算法避免了傳感器網(wǎng)絡(luò)中多跳傳輸引起的誤差積累并提高了精度， 節(jié)點通信距離為15 m, 當錨節(jié)點密度為20%,測距誤差為1 cm 時， 定位誤差為3 cm。

Capkun 等人提出了self-positioning algorithm(SPA)， 該算法首先根據(jù)通信范圍在各個節(jié)點建立局部坐標系， 通過節(jié)點間的信息交換與協(xié)調(diào)， 建立全局坐標系統(tǒng)， 網(wǎng)絡(luò)中的節(jié)點可以在與它相隔N 跳的節(jié)點建立的坐標系中計算自己的位置。

綜上可知， 非測距算法多為理論研究， 其定位精度普遍較低并且與網(wǎng)絡(luò)的連通度及節(jié)點的密集程度密切相關(guān)， 因此， 其適用范圍有一定的局限性， 在進行無線傳感器網(wǎng)絡(luò)定位技術(shù)研究過程中應(yīng)更多地考慮基于測距的定位算法。