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

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

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

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

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

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

3.2 基于非測距的算法

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

Bulusu 等人提出了一個(gè)單跳， 低功耗的算法，它利用錨節點(diǎn)的連通性來(lái)確定坐標。未知節點(diǎn)的坐標通過(guò)計算無(wú)線(xiàn)電范圍內所有節點(diǎn)的質(zhì)心獲得。節點(diǎn)將自己定位在與它們表現相近節點(diǎn)的質(zhì)心處， 該算法雖然簡(jiǎn)單， 但誤差較大， 需要的錨節點(diǎn)密度較高。約90%節點(diǎn)的定位精度在錨節點(diǎn)分布間距的1/3以?xún)取?p>He 等人提出了APIT 算法， 目標節點(diǎn)任選3 個(gè)相鄰錨節點(diǎn)， 測試未知節點(diǎn)是否位于它們所組成的三角形中。使用不同錨節點(diǎn)組合重復測試直到窮盡所有組合或達到所需定位精度。最后計算包含目標節點(diǎn)的所有三角形的交集質(zhì)心， 并以這一點(diǎn)作為目標節點(diǎn)位置， 該算法需要較高的錨節點(diǎn)密度， 其定位精度為40%。

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

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

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

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

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