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

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

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

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

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

3.2 基于非測距的算法

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

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

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

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

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

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

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

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