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

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

圖4 極大似然估計(jì)法原理示意圖

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

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

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

3.2 基于非測(cè)距的算法

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

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

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

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

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

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

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

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