1 引 言
無線傳感器網(wǎng)絡(luò)作為一種全新的信息獲取和處理技術(shù)在目標(biāo)跟蹤,、入侵監(jiān)測及一些定位相關(guān)領(lǐng)域有廣泛的應(yīng)用前景,。然而， 無論是在軍事偵察或地理環(huán)境監(jiān)測,， 還是交通路況監(jiān)測或醫(yī)療衛(wèi)生中對病人的跟蹤等應(yīng)用場合,， 很多獲取的監(jiān)測信息需要附帶相應(yīng)的位置信息， 否則,， 這些數(shù)據(jù)就是不確切的,，甚至有時候會失去采集的意義， 因此網(wǎng)絡(luò)中傳感器節(jié)點自身位置信息的獲取是大多數(shù)應(yīng)用的基礎(chǔ),。首先,， 傳感器節(jié)點必須明確自身位置才能詳細(xì)說明“在什么位置發(fā)什么了什么事件”， 從而實現(xiàn)對外部目標(biāo)的定位和跟蹤,； 其次,， 了解傳感器節(jié)點的位置分布狀況可以對提高網(wǎng)絡(luò)的路由效率提供幫助， 從而實現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡以及網(wǎng)絡(luò)拓?fù)涞淖詣优渲茫?改善整個網(wǎng)絡(luò)的覆蓋質(zhì)量,。因此,， 必須采取一定的機(jī)制或算法來實現(xiàn)無線傳感器網(wǎng)絡(luò)中各節(jié)點的定位。
無線傳感器網(wǎng)絡(luò)定位最簡單的方法是為每個節(jié)點裝載全球衛(wèi)星定位系統(tǒng)（GPS） 接收器,， 用以確定節(jié)點位置。但是,， 由于經(jīng)濟(jì)因素,、節(jié)點能量制約和GPS 對于部署環(huán)境有一定要求等條件的限制， 導(dǎo)致方案的可行性較差,。因此,， 一般只有少量節(jié)點通過裝載GPS 或通過預(yù)先部署在特定位置的方式獲取自身坐標(biāo)。另外,， 無線傳感器網(wǎng)絡(luò)的節(jié)點定位涉及很多方面的內(nèi)容,， 包括定位精度、網(wǎng)絡(luò)規(guī)模,、錨節(jié)點密度,、網(wǎng)絡(luò)的容錯性和魯棒性以及功耗等， 如何平衡各種關(guān)系對于無線傳感器網(wǎng)絡(luò)的定位問題非常具有挑戰(zhàn)性,?？梢哉f無線傳感器網(wǎng)絡(luò)節(jié)點自身定位問題在很大程度上決定著其應(yīng)用前景,。因此， 研究節(jié)點定位問題不僅必要,， 而且具有很重要的現(xiàn)實意義,。
2 WSN 定位技術(shù)基本概念
2.1 定位方法的相關(guān)術(shù)語
1） 錨節(jié)點（anchors）： 也稱為信標(biāo)節(jié)點、燈塔節(jié)點等,， 可通過某種手段自主獲取自身位置的節(jié)點,；
2） 普通節(jié)點（normal nodes）： 也稱為未知節(jié)點或待定位節(jié)點， 預(yù)先不知道自身位置,， 需使用錨節(jié)點的位置信息并運用一定的算法得到估計位置的節(jié)點,；
3） 鄰居節(jié)點（neighbor nodes）： 傳感器節(jié)點通信半徑以內(nèi)的其他節(jié)點；
4） 跳數(shù)（hop count）： 兩節(jié)點間的跳段總數(shù),；
5） 跳段距離（hop distance）： 兩節(jié)點之間的每一跳距離之和,；
6） 連通度（connectivity）： 一個節(jié)點擁有的鄰居節(jié)點的數(shù)目；
7） 基礎(chǔ)設(shè)施（infrastructure）： 協(xié)助節(jié)點定位且已知自身位置的固定設(shè)備,， 如衛(wèi)星基站,、GPS 等。
2.2 定位方法的性能評價標(biāo)準(zhǔn)
無線傳感器網(wǎng)絡(luò)定位性能的評價標(biāo)準(zhǔn)主要分為7 種,， 下面分別進(jìn)行介紹,。
1） 定位精度。定位技術(shù)首要的評價指標(biāo)就是定位精確度,， 其又分為絕對精度和相對精度,。絕對精度是測量的坐標(biāo)與真實坐標(biāo)的偏差， 一般用長度計量單位表示,。相對誤差一般用誤差值與節(jié)點無線射程的比例表示,， 定位誤差越小定位精確度越高。
2） 規(guī)模,。不同的定位系統(tǒng)或算法也許可以在一棟樓房,、一層建筑物或僅僅是一個房間內(nèi)實現(xiàn)定位。
另外,， 給定一定數(shù)量的基礎(chǔ)設(shè)施或一段時間,， 一種技術(shù)可以定位多少目標(biāo)也是一個重要的評價指標(biāo)。
3） 錨節(jié)點密度,。錨節(jié)點定位通常依賴人工部署或使用GPS 實現(xiàn),。人工部署錨節(jié)點的方式不僅受網(wǎng)絡(luò)部署環(huán)境的限制， 還嚴(yán)重制約了網(wǎng)絡(luò)和應(yīng)用的可擴(kuò)展性,。而使用GPS 定位,， 錨節(jié)點的費用會比普通節(jié)點高兩個數(shù)量級， 這意味著即使僅有10%的節(jié)點是錨節(jié)點,， 整個網(wǎng)絡(luò)的價格也將增加10 倍,， 另外,， 定位精度隨錨節(jié)點密度的增加而提高的范圍有限， 當(dāng)?shù)竭_(dá)一定程度后不會再提高,。因此,， 錨節(jié)點密度也是評價定位系統(tǒng)和算法性能的重要指標(biāo)之一。
4） 節(jié)點密度,。節(jié)點密度通常以網(wǎng)絡(luò)的平均連通度來表示,， 許多定位算法的精度受節(jié)點密度的影響。
在無線傳感器網(wǎng)絡(luò)中,， 節(jié)點密度增大不僅意味著網(wǎng)絡(luò)部署費用的增加,， 而且會因為節(jié)點間的通信沖突問題帶來有限帶寬的阻塞。
5） 容錯性和自適應(yīng)性,。定位系統(tǒng)和算法都需要比較理想的無線通信環(huán)境和可靠的網(wǎng)絡(luò)節(jié)點設(shè)備,。
而真實環(huán)境往往比較復(fù)雜， 且會出現(xiàn)節(jié)點失效或節(jié)點硬件受精度限制而造成距離或角度測量誤差過大等問題,， 此時,， 物理地維護(hù)或替換節(jié)點或使用其他高精度的測量手段常常是困難或不可行的。因此,， 定位系統(tǒng)和算法必須有很強(qiáng)的容錯性和自適應(yīng)性,， 能夠通過自動調(diào)整或重構(gòu)糾正錯誤， 對無線傳感器網(wǎng)絡(luò)進(jìn)行故障管理,， 減小各種誤差的影響,。
6） 功耗。功耗是對無線傳感器網(wǎng)絡(luò)的設(shè)計和實現(xiàn)影響最大的因素之一,。由于傳感器節(jié)點的電池能量有限,， 因此在保證定位精確度的前提下， 與功耗密切相關(guān)的定位所需的計算量,、通信開銷,、存儲開銷、時間復(fù)雜性是一組關(guān)鍵性指標(biāo),。
7） 代價。定位系統(tǒng)或算法的代價可從不同的方面來評價,。時間代價包括一個系統(tǒng)的安裝時間,、配置時間、定位所需時間,； 空間代價包括一個定位系統(tǒng)或算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點的數(shù)量,、硬件尺寸等； 資金代價則包括實現(xiàn)一種定位系統(tǒng)或算法的基礎(chǔ)設(shè)施,、節(jié)點設(shè)備的總費用,。
上述7 個性能指標(biāo)不僅是評價無線傳感器網(wǎng)絡(luò)自身定位系統(tǒng)和算法的標(biāo)準(zhǔn),， 也是其設(shè)計和實現(xiàn)的優(yōu)化目標(biāo)。為了實現(xiàn)這些目標(biāo)的優(yōu)化,， 有大量的研究工作需要完成,。同時， 這些性能指標(biāo)相互關(guān)聯(lián),， 必須根據(jù)應(yīng)用的具體需求做出權(quán)衡以設(shè)計合適的定位技術(shù),。
3 主要的WSN 定位方法
WSN 的定位方法較多， 可以根據(jù)數(shù)據(jù)采集和數(shù)據(jù)處理方式的不同來進(jìn)行分類,。在數(shù)據(jù)采集方式上,， 不同的算法需要采集的信息有所側(cè)重， 如距離,、角度,、時間或周圍錨節(jié)點的信息， 其目的都是采集與定位相關(guān)的數(shù)據(jù),， 并使其成為定位計算的基礎(chǔ),。在信息處理方式上， 無論是自身處理還是上傳至其他處理器處理,， 其目的都是將數(shù)據(jù)轉(zhuǎn)換為坐標(biāo),， 完成定位功能。目前比較普遍的分類方法有3 種：
1） 依據(jù)距離測量與否可劃分為： 測距算法和非測距算法,。其中測距法是對距離進(jìn)行直接測量,， 非測距法依靠網(wǎng)絡(luò)連通度實現(xiàn)定位， 測距法的精度一般高于非測距法,， 但測距法對節(jié)點本身硬件要求較高,，在某些特定場合， 如在一個規(guī)模較大且錨節(jié)點稀疏的網(wǎng)絡(luò)中,， 待定位節(jié)點無法與足夠多的錨節(jié)點進(jìn)行直接通信測距,， 普通測距方法很難進(jìn)行定位， 此時需要考慮用非測距的方式來估計節(jié)點之間的距離,，兩種算法均有其自身的局限性,；2） 依據(jù)節(jié)點連通度和拓?fù)浞诸惪蓜澐譃椋?單跳算法和多跳算法。單跳算法較多跳算法來說更加的簡便易行,， 但是存在著可測量范圍過小的問題,， 多跳算法的應(yīng)用更為廣泛， 當(dāng)測量范圍較廣導(dǎo)致兩個節(jié)點無法直接通信的情況較多時,， 需要多跳通信來解決,；3） 依據(jù)信息處理的實現(xiàn)方式可劃分為： 分布式算法和集中式算法。以監(jiān)測和控制為目的算法因為其數(shù)據(jù)要在數(shù)據(jù)中心匯總和處理， 大多使用集中式算法,， 其精度較高,， 但通信量較大。分布式算法是傳感器節(jié)點在采集周圍節(jié)點的信息后,， 在其自身的后臺執(zhí)行定位算法,， 該方法可以降低網(wǎng)絡(luò)通信量， 但目前節(jié)點的能量,、計算能力及存儲能力有限,， 復(fù)雜的算法難以在實際平臺中實現(xiàn)。
普遍認(rèn)為基于測距和非測距的算法分類更為清晰,， 本文以其為分類原則介紹主要的WSN 定位方法,。此外， 由于目前非測距算法大多為理論研究,， 且實用性較差,， 因此， 本文將著重介紹基于測距的定位方法,。
3.1 基于測距的算法
基于測距的算法通常分為2個步驟,， 首先利用某種測量方法測量距離（或角度）， 接著利用測得的距離（或角度）計算未知節(jié)點坐標(biāo),。下面分別進(jìn)行介紹,。
3.1.1 距離的測量方法
本節(jié)將詳細(xì)說明3 種主流的測量方法， 第一種是基于時間的方法,， 包括基于信號傳輸時間的方法（time of arrival,， TOA）和基于信號傳輸時間差的方法（time difference of arrival， TDOA）,； 第二種是基于信號角度的方法（angle of arrival,， AOA）； 第三種是基于信號接收信號強(qiáng)度的方法（received signal strengthindicator,， RSSI）方法,。下面分別進(jìn)行介紹。
1） 基于時間的方法
a. 基于信號傳輸時間的方法：
TOA 技術(shù)通過測量信號的傳播時間來計算距離,，該技術(shù)可分為單程測距和雙程測距,， 單程測距即信號只傳輸一次， 雙程測距即信號到達(dá)后立即發(fā)回,。前者需要兩個通信節(jié)點之間具有嚴(yán)格的時間同步,， 后者則不需要時間同步， 但是本地時鐘的誤差同樣會造成很大的距離偏差,。最典型的應(yīng)用就是GPS 定位系統(tǒng)。
優(yōu)點： 測量方法簡單且能取得較高的定位精度。
缺點： Ⅰ,。 精確計時難,。通常傳感節(jié)點之間通信都采用無線電信號， 由于無線電的傳輸速度非?？?，而傳感節(jié)點之間的距離又較小， 這使得計算發(fā)送節(jié)點和接收節(jié)點之間的信號傳輸時間非常困難,。因此利用此技術(shù)定位的節(jié)點需要采用特殊硬件來產(chǎn)生用于發(fā)送和接收的慢速無線信號,。Ⅱ。 高精度同步難,。
有些算法還需要接收節(jié)點和發(fā)送節(jié)點之間具有嚴(yán)格的時間同步,， 時間同步的問題現(xiàn)在也是無線傳感器網(wǎng)絡(luò)中的一個研究熱點并且沒有完全解決， 這也限制了算法的實用性,。Ⅲ,。 易受噪聲影響。在空間傳輸?shù)男盘枙艿礁鞣N噪聲的影響,， 所以即使在不同的測量中得到了相同的信號傳輸時間也不能斷定這兩次測量中的發(fā)送節(jié)點和接收節(jié)點間的距離是相同的,。
最早的TOA 距離估計算法是在非時間同步網(wǎng)絡(luò)中利用對稱雙程測距協(xié)議進(jìn)行測量的。之后,， 單邊測距方法在后續(xù)的研究中被提出,， 如Harter 開發(fā)的Active Bat 定位系統(tǒng)［10］， 它由一系列固定在網(wǎng)格中的節(jié)點組成,。固定節(jié)點從移動節(jié)點中接收超聲波,， 并通過TOA 算法計算到移動節(jié)點的距離， 在通信范圍30 m 左右的情況下,， 其定位精度達(dá)到9 cm,， 相對精度9.3%。但TOA 只有在視距（line-of-sight,， LOS）的情況下才比較精確,， 在非視距（none line-of-sight， NLOS）情況下,， 隨著傳播距離的增加測量誤差也會相應(yīng)增大,。綜述了在視距和非視距情況下多種TOA 距離估計方法所需要的復(fù)雜度， 先驗知識和實驗結(jié)果等,。Hangoo Kang 等人在多徑環(huán)境下利用基于啁啾展頻技術(shù)（chirp spread spectrum,， CSS） 和對稱雙邊雙向測距技術(shù)（symmetric double sided two-wayranging， SDS-TWR） 的TOA 定位系統(tǒng)中提出了誤差補(bǔ)償算法,， 取得了較好的定位效果,， 在此基礎(chǔ)上Andreas Lewandowski 等人提出了一種加權(quán)的TOA 算法， 該算法應(yīng)用于工業(yè)環(huán)境下， 可提高系統(tǒng)容錯性,， 降低自身對測距系統(tǒng)的干擾,， 在7 m×24.5 m 的范圍內(nèi)， 測距誤差小于3 m,。
b. 基于信號傳輸時間差的方法：
TDOA 測距技術(shù)廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)的定位方案中,。通常在節(jié)點上安裝超聲波收發(fā)器和射頻收發(fā)器， 測距時錨節(jié)點同時發(fā)送超聲波和電磁波,，接收節(jié)點通過兩種信號到達(dá)時間差來計算兩點之間距離,。
優(yōu)點： 在LOS 情況下能取得較高的定位精度。
缺點： Ⅰ,。 硬件需求較高,。傳感節(jié)點上必須附加特殊的硬件聲波或超聲波收發(fā)器， 這會增加傳感節(jié)點的成本,； Ⅱ,。 傳輸信號易受環(huán)境影響。聲波或者超聲波在空氣中的傳輸特性和一般的無線電波不同,，空氣的溫度,、濕度或風(fēng)速都會對聲波的傳輸速度產(chǎn)生較大的影響， 這就使得距離的估計可能出現(xiàn)一定的偏差,， 使用超聲波與RF 到達(dá)時間差的測距范圍為5～7 m,， 實用性不強(qiáng)， 且超聲波傳播方向單一,， 不適合面向多點傳播,； Ⅲ。 應(yīng)用場合單一,。測距的前提是發(fā)送節(jié)點和接收節(jié)點之間沒有障礙物阻隔,， 在有障礙物的情況下會出現(xiàn)聲波的反射、折射和衍射,， 此時得到的實際傳輸時間將變大,， 在這種傳輸時間下估算出的距離也將出現(xiàn)較大的誤差。
由MIT 開發(fā)出的Cricket 室內(nèi)定位系統(tǒng)最早采用了RF 信號與超聲波信號組合的TDOA測距技術(shù),， 在2 m×2 m×2.5 m 的范圍內(nèi),， 該系統(tǒng)定位精度在10 cm以下， 現(xiàn)已成為Crossbow 的商業(yè)化產(chǎn)品,。加利福尼亞大學(xué)洛杉磯分校的Medusa 節(jié)點在AHLos定位系統(tǒng)之間傳輸距離為3 m 左右時,， 測距精度能夠達(dá)到厘米級別。加州大學(xué)伯克利分校開發(fā)的Calamari定位系統(tǒng)均采用TDOA 超聲波測距,， 在144 m2 的區(qū)域部署49 個節(jié)點,， 平均定位誤差達(dá)到0.78 m,， 文獻(xiàn)對于聲波收發(fā)器的方向單一性問題， 給出了兩種解決方法： 一是將多個傳感器調(diào)整成向外發(fā)射的形狀,； 二是在節(jié)點的平面上使用金屬圓錐來均勻地傳播和收集聲波能量,。結(jié)合TDOA 測距機(jī)制和NTP 協(xié)議時間同步原理， 一些學(xué)者提出了時間同步與節(jié)點測距混合算法,， 結(jié)合基于到達(dá)時間差的測距機(jī)制和網(wǎng)絡(luò)時間協(xié)議中的時鐘同步機(jī)制， 通過逆推時間非同步情況下相互測距的意義,， 不僅能實現(xiàn)時間同步,， 還可以實現(xiàn)相對測距甚至絕對測距。
基于時間的定位方法的定位精度雖高,， 但從上面的例子中可以看出其測距距離較短,， 且附加的硬件將增加節(jié)點的體積和功耗， 不適于實際應(yīng)用,。
2） 基于信號到達(dá)角度的方法
AOA 測距技術(shù)依靠在節(jié)點上安裝天線陣列來獲得角度信息,。由于大部分節(jié)點的天線都是全向的， 無法區(qū)分信號來自于哪個方向,。因此該技術(shù)需要特殊的硬件設(shè)備如天線陣列或有向天線等來支持,。
優(yōu)點： 能夠取得不錯的精度。
缺點： 傳感節(jié)點最耗能的部分就是通信模塊,，所以裝有天線陣列的節(jié)點的耗能,、尺寸以及價格都要超過普通的傳感節(jié)點， 與無線傳感器網(wǎng)絡(luò)低成本和低能耗的特性相違背,， 所以實用性較差,。
關(guān)于AOA 定位的文獻(xiàn)比較少，最早提出在室內(nèi)采集方向信息,， 并以此實現(xiàn)定位的方法,，它的硬件部分包括微控制器、RF 接收器,、5 個排成“V”型的超聲波接收器,， 其測量誤差精度為5°。隨后,， 一些學(xué)者提出了在只有部分節(jié)點有定位能力的情況下確定所有節(jié)點的方向和位置信息的算法,。
3） 基于接收信號強(qiáng)度的方法
RSSI 是在已知發(fā)射功率的前提下， 接收節(jié)點測量接收功率,， 計算傳播損耗,， 并使用信號傳播模型將損耗轉(zhuǎn)化為距離。
優(yōu)點： 低成本,。每個無線傳感節(jié)點都具有通信模塊,， 獲取RSSI 值十分容易,， 無需額外硬件。
缺點： 1） 錨節(jié)點數(shù)量需求多,。由于RSSI 值在實際應(yīng)用中的規(guī)律性較差,， 使得利用RSSI 信息進(jìn)行定位的算法在定位精度以及實用性上存在缺陷。所以為了達(dá)到較高的定位精度,， 利用RSSI 信息進(jìn)行定位的算法通常需要較多數(shù)量的錨節(jié)點,。2） 多路徑反射、非視線問題等因素都會影響距離測量的精度,。
早期的RSSI 距離測量方法有Hightower 等人設(shè)計的室內(nèi)定位SpotON tags 系統(tǒng),， 通過RSSI 方法來估計兩點間的距離， 通過節(jié)點間的相互位置來進(jìn)行定位,， 在邊長3 m 的立方體內(nèi),， 其定位精度在1 m 以內(nèi)。目前,， 基于RSSI 值的距離測量方法可以分為2 種,， 一種是需要預(yù)先測試環(huán)境信息的方法， 即在實驗開始前,， 對定位的區(qū)域進(jìn)行大量的RSSI 值測試,，將不同點得到的RSSI 值保存到數(shù)據(jù)庫中， 建成場強(qiáng)圖或擬合曲線,， 在實際測試時查詢和調(diào)用,。另外一種是無需預(yù)先測試環(huán)境信息的方法， 直接在定位區(qū)域進(jìn)行節(jié)點布置和定位,， 如雙曲線模型法,，迭代的分布式算法， 結(jié)合露珠洪泛思想引入RSSI 機(jī)制的HCRL（hop-count-ratio based localization）算法等,。
總體來說,， 需要預(yù)先測試環(huán)境參數(shù)的方法在實際定位中計算量小， 這類方法只需要簡單的查表或根據(jù)擬合曲線進(jìn)行計算,， 其缺點是實驗前需要做大量的準(zhǔn)備工作,， 而且一旦環(huán)境改變則預(yù)先建立的模型將不再適用。無需預(yù)先測試環(huán)境參數(shù)的方法需要定位引擎的計算操作,， 往往具有復(fù)雜的計算過程,，但適應(yīng)性較強(qiáng)。
以上幾種測距方法各有利弊,， 以2009 年發(fā)表的基于測距法的文獻(xiàn)來看,， 研究RSSI 方法的大約占了以上幾種方法總數(shù)的52%， TOA 方法25%,， TDOA 方法13%和AOA 方法10%,， 其比例圖如圖1 所示,， 從實用性的角度來看， 基于RSSI 的定位方法更簡便易行,， 因此,， 基于RSSI 測距方法的研究占基于測距算法研究總數(shù)的一半以上。
圖1 各類方法研究比例圖
3.1.2 節(jié)點坐標(biāo)計算方法
無線傳感器節(jié)點定位過程中,， 當(dāng)未知節(jié)點獲得與鄰近參考節(jié)點之間的距離或相對角度信息后,， 通常使用以下原理計算自己的位置。
1） 三邊測量法是一種基于幾何計算的定位方法,，如圖2 所示,， 已知3 個節(jié)點A， B,， C 的坐標(biāo)以及3 點到未知節(jié)點的距離就可以估算出該未知點D 的坐標(biāo)，同理也可以將這個結(jié)果推廣到三維的情況,。
2） 三角測量法也是一種基于幾何計算的定位方法,， 如圖3 所示， 已知3 個節(jié)點A,， B,， C 的坐標(biāo)和未知節(jié)點D 與已知節(jié)點A， B,， C 的角度,， 每次計算2 個錨節(jié)點和未知節(jié)點組成的圓的圓心位置如已知點A， C與D的圓心位置O,， 由此能夠確定3 個圓心的坐標(biāo)和半徑,。最后利用三邊測量法， 根據(jù)求得的圓心坐標(biāo)就能求出未知節(jié)點D 的位置,。
圖2 三邊測量法原理示意圖
圖3 三角測量法原理示意圖
3） 極大似然估計法,。如圖4 所示， 已知n 個點的坐標(biāo)和它們到未知節(jié)點的距離,， 列出坐標(biāo)與距離的n 個方程式,， 從第1 個方程開始， 每個方程均減去最后一個方程,， 得到n,？1 個方程組成的線性方程組，最后用最小二乘估計法可以得到未知節(jié)點的坐標(biāo),。
圖4 極大似然估計法原理示意圖
4） 極小極大定位算法,， 在無線傳感器網(wǎng)絡(luò)定位中也被廣泛使用。如圖5 所示,， 計算未知節(jié)點與錨節(jié)點的距離,， 接著錨節(jié)點根據(jù)與未知節(jié)點的距離d,， 以自身為中心， 畫以2d 為邊長的正方形,， 所有錨節(jié)點做出的正方形中重疊的部分的質(zhì)心就是未知節(jié)點的坐標(biāo),。針對極小極大定位算法對錨節(jié)點密度依賴過高的問題， 有學(xué)者利用錨節(jié)點位置信息提出了分步求精定位算法,， 該算法在只利用適量的錨節(jié)點的情況下可達(dá)到較高定位精度,。
圖5 極小極大定位算法原理示意圖
文獻(xiàn)［35］在12 m×19.5 m 的范圍內(nèi)對上述三邊測量法、極大似然估計法和極小極大法方法的計算量和精度進(jìn)行了測試,。實驗表明,， 極大似然估計法的計算量最大， 錨節(jié)點小于10 個時,， 極小極大法的計算量最小,， 在錨節(jié)點較少情況下， 三邊法和極小極大法的精確度較高,， 而當(dāng)錨節(jié)點超過6 個時,， 極大似然估計法精確度更高。因此,， 在計算坐標(biāo)時要根據(jù)實際情況合理選擇坐標(biāo)計算方法,。另外， 針對現(xiàn)存的定位算法都是假設(shè)信標(biāo)節(jié)點不存在誤差,， 與真實情況不符的情況,， 文獻(xiàn)［36］提出信標(biāo)優(yōu)化選擇定位算法（OBS）， 即通過減小定位過程中的誤差傳遞來提高定位精度,。
3.2 基于非測距的算法
基于非測距的算法與測距法的區(qū)別在于前者不直接對距離進(jìn)行測量,， 而是使用網(wǎng)絡(luò)的連通度來估計節(jié)點距錨節(jié)點的距離或坐標(biāo)， 由于方法的不確定性,， 基于非測距的方法眾多,。下面按時間順序，介紹部分典型非測距定位算法,。
Bulusu 等人提出了一個單跳,， 低功耗的算法，它利用錨節(jié)點的連通性來確定坐標(biāo),。未知節(jié)點的坐標(biāo)通過計算無線電范圍內(nèi)所有節(jié)點的質(zhì)心獲得,。節(jié)點將自己定位在與它們表現(xiàn)相近節(jié)點的質(zhì)心處， 該算法雖然簡單,， 但誤差較大,， 需要的錨節(jié)點密度較高。約90%節(jié)點的定位精度在錨節(jié)點分布間距的1/3以內(nèi),。
He 等人提出了APIT 算法,， 目標(biāo)節(jié)點任選3 個相鄰錨節(jié)點,， 測試未知節(jié)點是否位于它們所組成的三角形中。使用不同錨節(jié)點組合重復(fù)測試直到窮盡所有組合或達(dá)到所需定位精度,。最后計算包含目標(biāo)節(jié)點的所有三角形的交集質(zhì)心,， 并以這一點作為目標(biāo)節(jié)點位置， 該算法需要較高的錨節(jié)點密度,， 其定位精度為40%,。
Niculescu 等人提出了DV-Hop 定位算法， 它從網(wǎng)絡(luò)中收集相鄰節(jié)點信息,， 計算不相鄰節(jié)點之間最短路徑,。DV-Hop 算法使用已知位置節(jié)點的坐標(biāo)來估測一個跳躍距離， 并使用最短路徑的跳躍距離估計未知節(jié)點和錨節(jié)點的距離,， 該算法僅適用于各向同性的密集網(wǎng)絡(luò),， 當(dāng)錨節(jié)點密度為10%時， 定位誤差為33%,。
Radhika 等人提出的Amorphous Positioning 算法,，使用離線的跳躍距離估測， 同DV-Hop 算法一樣,， 通過一個相鄰節(jié)點的信息交換來提高定位的估測值，需要預(yù)知網(wǎng)絡(luò)連通度,， 當(dāng)網(wǎng)絡(luò)連通度為15 時,， 定位精度20%。
Savvides 等人介紹了一種N-Hop multilateration算法,， 使用卡爾曼濾波技術(shù)循環(huán)求精,， 該算法避免了傳感器網(wǎng)絡(luò)中多跳傳輸引起的誤差積累并提高了精度， 節(jié)點通信距離為15 m,， 當(dāng)錨節(jié)點密度為20%,，測距誤差為1 cm 時， 定位誤差為3 cm,。
Capkun 等人提出了self-positioning algorithm（SPA）,， 該算法首先根據(jù)通信范圍在各個節(jié)點建立局部坐標(biāo)系， 通過節(jié)點間的信息交換與協(xié)調(diào),， 建立全局坐標(biāo)系統(tǒng),， 網(wǎng)絡(luò)中的節(jié)點可以在與它相隔N 跳的節(jié)點建立的坐標(biāo)系中計算自己的位置。
綜上可知,， 非測距算法多為理論研究,， 其定位精度普遍較低并且與網(wǎng)絡(luò)的連通度及節(jié)點的密集程度密切相關(guān)， 因此,， 其適用范圍有一定的局限性,， 在進(jìn)行無線傳感器網(wǎng)絡(luò)定位技術(shù)研究過程中應(yīng)更多地考慮基于測距的定位算法,。
4 新型WSN 定位研究分析
除了傳統(tǒng)的定位方法， 新型的無線傳感器網(wǎng)絡(luò)定位算法也逐漸出現(xiàn),， 如利用移動錨節(jié)點來定位未知節(jié)點,、在三維空間內(nèi)定位未知節(jié)點、以及采用智能定位算法來提高定位精度等,， 下面分別介紹,。
4.1 基于移動錨節(jié)點的定位算法
利用移動錨節(jié)點定位可以避免網(wǎng)絡(luò)中多跳和遠(yuǎn)距離傳輸產(chǎn)生的定位誤差累計， 并且可以減少錨節(jié)點的數(shù)量,， 進(jìn)而降低網(wǎng)絡(luò)的成本,。如MBAL（mobilebeacon assisted localization scheme）定位方法， 錨節(jié)點在移動過程中隨時更新自身的坐標(biāo),， 并廣播位置信息,。未知節(jié)點測量與移動節(jié)點處于不同位置時的距離， 當(dāng)?shù)玫? 個或3 個以上的位置信息時,， 就可以利用三邊測量法確定自己的位置,， 進(jìn)而升級為錨節(jié)點。此外,， 移動錨節(jié)點用于定位所有未知節(jié)點所移動的路徑越長則功耗越大,， 因此對移動錨節(jié)點的活動路徑進(jìn)行合理規(guī)劃可以減小功耗。
文獻(xiàn)［48］提出了一種基于加權(quán)最小二乘法的移動錨節(jié)點定位距離估計算法,， 作者首先建立一個移動模型,， 錨節(jié)點沿著線性軌跡移動， 使用加權(quán)最小二乘法來減小距離估計誤差,， 并在Cramér-Raobound（CRB） 的基礎(chǔ)上分析了距離估計的最小誤差邊界,， 該算法在距離估計和位置估計方面都有較好的性能。
利用移動錨節(jié)點自身的可定位性和可移動性可定位網(wǎng)絡(luò)局部相關(guān)節(jié)點,， 但移動錨節(jié)點的路徑規(guī)劃算法和采取的定位機(jī)制需要深入考慮,。2009 年發(fā)表的關(guān)于WSN 定位的文章中， 約25%是關(guān)于移動節(jié)點定位的,。
4.2 三維定位方法
隨著傳感器網(wǎng)絡(luò)的空間定位需求不斷提升,， 三維空間場景下的定位也成為了一個新的研究方向。
目前的三維定位算法包括基于劃分空間為球殼并取球殼交集定位的思想,， 提出的對傳感器節(jié)點進(jìn)行三維定位的非距離定位算法APIS（approximatepoint in sphere） ,。在此基礎(chǔ)上針對目前三維定位算法的不足， 提出的基于球面坐標(biāo)的動態(tài)定位機(jī)制,， 該機(jī)制將定位問題抽象為多元線性方程組求解問題,，最終利用克萊姆法則解決多解、無解問題。建立了WSN 空間定位模型并結(jié)合無線信道對數(shù)距離路徑衰減模型,， 為解決不適定型問題提出了Tikhonov 正則化方法,， 并結(jié)合偏差遠(yuǎn)離方便的得到了較優(yōu)的正則化參數(shù)， 在3.5 m×6 m×3 m 的區(qū)域內(nèi)定位精度可控制在2 m,。
三維定位方法可擴(kuò)展WSN 的應(yīng)用場合,， 目前三維定位在許多方面還有待完善， 如獲取更準(zhǔn)確的錨節(jié)點需要尋求更精確的廣播周期和消息生存周期,， 縮減定位時間需要改進(jìn)錨節(jié)點的選擇和過濾機(jī)制等,。
4.3 智能定位算法
隨著電子技術(shù)的發(fā)展和芯片計算能力的提高，傳感器網(wǎng)絡(luò)節(jié)點本身的性能也有提升,， 復(fù)雜算法也可以在網(wǎng)絡(luò)中實現(xiàn),。因此， 智能定位算法也紛紛被提出,。
對于無線傳感器網(wǎng)絡(luò)的戶外三維定位,， 將錨節(jié)點固定在直升機(jī)上通過GPS 實時感知自身位置， 采用基于RSSI 的測距方法,， 利用粒子濾波定位技術(shù)實現(xiàn)定位,， 該方法不需要任何關(guān)于未知節(jié)點的先驗知識， 非常適合應(yīng)用于戶外定位,。
神經(jīng)網(wǎng)絡(luò)對于解決無線傳感器網(wǎng)絡(luò)的定位問題是一個切實可行的辦法,， 將3 種神經(jīng)網(wǎng)絡(luò)： 多層感知神經(jīng)網(wǎng)絡(luò)， 徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)和遞歸神經(jīng)網(wǎng)絡(luò)與卡爾曼濾波的2 個變形進(jìn)行比較,， 可以根據(jù)不同情況下的定位需求靈活選擇定位方法,。使用神經(jīng)網(wǎng)絡(luò)和網(wǎng)格傳感器訓(xùn)練的靈活的模型， 可以提高定位精度,， 且不需要額外的硬件支持。網(wǎng)絡(luò)訓(xùn)練每隔一段時間進(jìn)行一次更新來最小化誤差,， 并且通過增加網(wǎng)格節(jié)點密度來提高定位精度,。
對于節(jié)點定位中的非視距問題， 常規(guī)的辦法是采用機(jī)器學(xué)習(xí)中的支持向量回歸（support vector regression,，SVR） 方法進(jìn)行定位以降低誤差,， 但其定位精度仍然受到一定的非視距誤差影響， 為了降低這種影響,， 研究人員提出了基于直推式回歸的定位算法,。利用錨節(jié)點的坐標(biāo)和TOA 信息并借用核函數(shù)直接推導(dǎo)出未知節(jié)點的位置， 進(jìn)一步提高定位 精度,。
雖然智能定位算法已經(jīng)成為一個新的研究方向,，但由于WSN 網(wǎng)絡(luò)本身屬于低能耗的網(wǎng)絡(luò)， 單個節(jié)點的計算能力還比較低， 目前智能定位算法不普遍適用于實際的WSN 定位系統(tǒng),， 但隨著低功耗技術(shù),、微處理器技術(shù)、FPGA 技術(shù)的發(fā)展,， 智能定位算法將在未來的定位系統(tǒng)中得到廣泛的應(yīng)用,。
5 研究前景與應(yīng)用分析
截至目前， 無線傳感器網(wǎng)絡(luò)定位研究已廣泛開展并取得了許多研究成果,， 但仍存在著一些沒有被解決或被發(fā)現(xiàn)的問題,， 目前最為關(guān)鍵的問題仍然是WSN 節(jié)點的能耗問題， 一切的定位算法應(yīng)該在精度和能量消耗上選取一個較為折衷的效果,。下面將對目前存在的問題及相應(yīng)可能的解決方案進(jìn)行介紹,。
1） 實用性差。大部分基于非測距的定位算法只是停留在理論研究階段,， 且大都是在仿真環(huán)境下進(jìn)行的,， 需要假設(shè)很多不確定因素， 而這些因素在實際應(yīng)用中往往不能滿足,， 則這些算法就失去了實際的意義,。因此定位算法的設(shè)計應(yīng)該更多的從實際應(yīng)用上考慮， 結(jié)合實際應(yīng)用情況設(shè)計實用的定位算法,。
2） 應(yīng)用環(huán)境單一,。多數(shù)的算法都是針對特定的應(yīng)用場景進(jìn)行設(shè)計的， 也就是說,， 每個算法都只能解決特殊的問題或應(yīng)用于特定的場景,， 一旦環(huán)境發(fā)生變動， 算法或系統(tǒng)的測量誤差將增大甚至不再適用,。因此,， 探索更具通用性的定位算法或定位系統(tǒng)， 將其應(yīng)用于更為復(fù)雜多變的環(huán)境中是一項新的挑戰(zhàn),。
3） 受硬件限制,。在實際定位中， 一些算法由于受到傳感器節(jié)點硬件成本和性能的限制,， 如某些算法需要在定位節(jié)點上增加GPS,， 超聲波收發(fā)器， 有向天線陣列等設(shè)備,， 增加了節(jié)點硬件成本,， 阻礙了其在實際定位系統(tǒng)中的應(yīng)用。因此,， 算法設(shè)計應(yīng)多考慮WSN 節(jié)點的實際情況,， 如只在部分節(jié)點上增加額外硬件,， 或根據(jù)實際節(jié)點資源受限情況采用其他定位算法等。
4） 能量受限,。測量精度,、容錯性和能量消耗等問題也是目前無線傳感器網(wǎng)絡(luò)研究的熱點， 更是定位技術(shù)研究的熱點,。通常情況下,， 高測量精度和低能量消耗不可兼得， 往往需要在測量精度和能量消耗上進(jìn)行有效的折衷,。因此,， 可以在提高儲能設(shè)備的容量， 或利用可能的外界環(huán)境資源為節(jié)點提供能量方向進(jìn)行研究,， 另外,， 提出高效、節(jié)能,、符合實際情況的無線傳感器網(wǎng)絡(luò)定位算法將具有現(xiàn)實的意義,。
5） 安全和隱私問題。在大范圍部署的無線傳感器網(wǎng)絡(luò)中,， 安全和隱私的問題也是一個主要的研究方向,。一方面， 一些應(yīng)用需要節(jié)點位置信息,， 另一方面,， 向一些不需要知道位置的節(jié)點透露位置信息則會使網(wǎng)絡(luò)面臨安全問題。此外,， 鑒于無線傳感器網(wǎng)絡(luò)的性質(zhì),， 集中式算法在后臺處理定位程序也使得節(jié)點的位置信息通過層層傳遞被過多的節(jié)點所知曉，因此分布式算法相對于集中式算法可以減少信息傳遞次數(shù),， 增強(qiáng)網(wǎng)絡(luò)安全性,， 另外， 在網(wǎng)絡(luò)通信中使用信息加密也可以提高網(wǎng)絡(luò)安全性,。就2009 年發(fā)表的定位相關(guān)文章來說,， 每4 篇發(fā)表的文章中就有1 篇提出的是分布式算法。
未來的無線傳感器網(wǎng)絡(luò)定位在解決上述問題之后將廣泛應(yīng)用于各類領(lǐng)域,， 包括安全定位,、變化的環(huán)境,、三維空間等,。
6 結(jié) 論
結(jié)合近年來無線傳感器網(wǎng)絡(luò)定位技術(shù)的發(fā)展?fàn)顩r， 對無線傳感器網(wǎng)絡(luò)定位的基本概念,、評價標(biāo)準(zhǔn)以及國內(nèi)外研究現(xiàn)狀進(jìn)行了概述,， 重點對基于測距和基于非測距的無線傳感器網(wǎng)絡(luò)定位算法進(jìn)行了分析， 并列舉了一些新型WSN 定位的算法， 總結(jié)了目前無線傳感器網(wǎng)絡(luò)定位領(lǐng)域研究存在的問題和一些可以研究的內(nèi)容和方向,。希望本文能夠為無線傳感器網(wǎng)絡(luò)定位相關(guān)領(lǐng)域的研究者提供一些參考和借鑒,。