1. 引言
定位技術是無線傳感器網(wǎng)絡中的支撐技術，缺少位置數(shù)據(jù)的信息往往是沒有意義的。隨著無線傳感器網(wǎng)絡向節(jié)點數(shù)量多，鋪設范圍廣，基礎設施簡單和硬件成本低的方向發(fā)展，如何在減少節(jié)點硬件組件，算法實現(xiàn)簡單的同時獲得相對準確的定位信息已成為主要研究的課題之一。現(xiàn)有定位算法根據(jù)定位過程中是否需要使用已知位置的信標節(jié)點，分為絕對定位算法和相對定位算法。前者一般是在待測區(qū)域事先布置一定比例的錨節(jié)點，這些節(jié)點通過GPS或是其他方法已得知自身絕對坐標，其余的未知節(jié)點通過與這些信標節(jié)點通信獲得自身坐標。相對定位算法則完全不需要事先布置信標節(jié)點，通過算法制定的方案，選取一定數(shù)量的未知節(jié)點建立相對坐標，其余的節(jié)點通過節(jié)點之間的協(xié)作關系和消息傳輸獲取自身在相對坐標系中的相對位置實現(xiàn)定位。相對定位算法無需信標節(jié)點和基礎設施，硬件成本低，并且不會受到復雜環(huán)境對遠距離信號傳輸?shù)挠绊懀m合于對節(jié)點硬件，能耗以及環(huán)境適應性有很高要求的無線傳感器網(wǎng)絡應用。
2. 定位算法分析
在無線傳感器網(wǎng)絡中，節(jié)點定位一般包括三個部分：距離測定、位置計算和定位過程。
(1) 距離測定：就是獲得兩個節(jié)點之間距離的方法，可分為基于測距和無需測距。基于測距的算法(range-based)通過節(jié)點自身攜帶的測距功能直接測量兩個節(jié)點之間的距離。當前比較重要的測距方法主要是到達時間(TOA)、到達時間差(TDOA)和信號強度測距(RSSI)或者到達角度(AOA)。
TOA(Time of Arrival)：該技術通過測量信號傳播時間來測量距離。使用TOA 技術最基本的定位系統(tǒng)是GPS，GPS 系統(tǒng)需要昂貴、高性能的電子設備來精確同步衛(wèi)星時鐘。因WSN節(jié)點硬件尺寸、價格和功耗限制，GPS 和其他TOA 技術無法廣泛應用于WSN。
TDOA(Time Difference On Arrival)：TDOA測距技術被廣泛應用于WSN定位方案中。通過記錄兩種不同信號(常使用RF和超聲波)到達時間差異，基于已知信號傳播速度，直接把時間轉(zhuǎn)化為距離。已有多種定位算法使用TDOA實現(xiàn)測距。但該技術受限于超聲波傳播距離有限(超聲波信號通常傳播距離僅為20-30英尺，因而網(wǎng)絡需要密集部署)和NLOS(Non-Line-Of-Sight)問題對超聲波信號的傳播影響。雖然已有發(fā)現(xiàn)并減輕NLOS影響的技術，但都需要大量計算和通信開銷，不適用于低功耗的WSN應用中。
RSSI(Received Signal Strength Indicator)：已知發(fā)射功率，在接收節(jié)點測量接收功率，計算傳播損耗，使用理論或是經(jīng)驗的信號傳播模型將傳播損耗轉(zhuǎn)化為距離，該技術主要使用RF 信號。因傳感器節(jié)點具有無線通信能力，故是一種低功率、廉價的測距方式，RADAR、SpotON等許多項目中使用了該技術。他的主要誤差來源是環(huán)境影響所造成的信號傳播模型的建模復雜性；反射、多徑傳播、NLOS)、天線增益等問題都會對相同的距離產(chǎn)生顯著不同的傳播損耗。通常將其看為一種粗糙的測距技術，它可能產(chǎn)生50%的測距誤差。
AOA(Angle of arrival)：該技術是估算鄰居節(jié)點發(fā)送信號方向，可通過天線陣列或多個接收器來實現(xiàn)，除定位外，還能提供方向信息，如MIT 的The Cricket Compass 等項目中都使用AOA 技術。
無需測距的算法(range-free)不需要節(jié)點自身的測距設備，通過跳數(shù)或是其他信息估計自身到選定的信標節(jié)點的距離值，由于是估計得到的數(shù)值，相對于基于測距的算法獲得的距離值誤差偏大。
(2) 位置計算：在獲取上述距離值之后，節(jié)點需要通過位置計算的方法計算得到坐標值。現(xiàn)有的算法一般采用三邊測量法和三角測量法計算坐標。
圖1 三邊測量法示意圖
如圖1 所示，在未知節(jié)點獲得三個以上的信標節(jié)點距離值之后，就可以通過式(1)、式(2)和式(3)計算自身坐標。式中，(xa , ya)、(xb , yb)、(xc , yc)分別是三個信標節(jié)點的坐標，da、db、dc 是未知節(jié)點到三個信標節(jié)點的距離。
式(1)經(jīng)過線性化，可得線性方程式(2):
式(2)中的N 是由于存在測距誤差加入的參數(shù)，它是根據(jù)測距誤差的分布形式存在的一個隨機誤差向量。如果未知節(jié)點測得的到信標節(jié)點的距離值大于三個，則可以加入(1)式中，進行更精確的計算。三角測量法與三邊測量法類似，通過獲取相對三個信標節(jié)點的角度值，計算得到圖1中三個圓的半徑，再經(jīng)過三邊測量法計算得到坐標。三邊測量法和三角測量法由于涉及大量的矩陣運算和最小二乘的運算，計算量較大，針對這種情況，加州大學洛杉磯分校的Andreas Savvides等人提出的n-hop multilaterationprimitive定位算法中提出的最大最小值法通過簡單的折線運算估計未知節(jié)點的位置，如圖2所示。
圖2 最大最小值法示意圖
圖中A點和B點為信標節(jié)點，C點為未知節(jié)點。在獲得C點到A點和B點的折線距離a、b、c之后，在三角形ACK中，利用斜邊AC的長度a代替直角邊AK的長度，從而K點移動到K/點，B點類似，從而有：
最大最小值法估計得到的坐標值由于是取矩形區(qū)域的質(zhì)心代替實際位置，若測得的距離值本身就存在較大的誤差，那么得出的結(jié)果沒有三邊定位精確，在一些要求精度不是很嚴格的情況或者是結(jié)果經(jīng)過求精之后，可以滿足需要。
(3) 定位過程：不同算法根據(jù)上面兩步獲得的有限的距離值和部分節(jié)點的坐標，計算其余未知節(jié)點的機制。由于各種算法采取的策略不同，各種性能參數(shù)的區(qū)別主要由這一步?jīng)Q定。在分析定位算法的時候，一般要針對具體情況綜合考慮上述三個方面來考察算法性能。
3. 典型的相對定位算法
3.1 SPA 算法
瑞士洛桑聯(lián)邦工業(yè)大學的Srdjan Capkun 等人最早針對沒有基礎設施的移動無線自組網(wǎng)，提出SPA(self–positioning algorithm)算法[23]。它以網(wǎng)絡中節(jié)點密度最大的地方選取一個參考點作為全局相對坐標系的原點，其余每個節(jié)點分別通過測距功能測得鄰居節(jié)點之間的距離值，如圖3所示，實線表示二者距離可測得，虛線表示二者不是鄰居節(jié)點。每個節(jié)點在鄰居節(jié)點中選取兩個點A、B，選取原則是這兩個點本身也是鄰居節(jié)點，并且三個點不在同一直線上。以直線OA作為x 軸，以B點在OA上的投影BxB為y 軸正方向建立局部相對坐標系。所有的局部坐標系建立完成后，相鄰的坐標系通過坐標變換實現(xiàn)坐標統(tǒng)一，最終所有節(jié)點都變換形成以選取的參考點為原點的坐標系實現(xiàn)定位。由于每個節(jié)點都要參與多次的坐標變換，計算量和通信開銷都非常大。此算法開始是針對無線自組網(wǎng)提出的，不太考慮功耗問題，但是用到無線傳感器網(wǎng)絡當中，這種通信開銷和節(jié)點數(shù)量呈指數(shù)比上升的算法需要根據(jù)實際情況進行改進。
圖3 SPA算法示意圖
3.2 聚類 SPA 算法
美國仁斯利爾理工學院Rajagopal Iyengar 等人提出的聚類SPA(clustering-basedself–positioning algorithm)算法[24]是針對上述SPA算法通信量過大而提出的改進算法。首先通過運行隨機的定時器選取網(wǎng)絡中的主節(jié)點，主節(jié)點一跳范圍內(nèi)的其他節(jié)點成為它的從節(jié)點。每個主節(jié)點使用SPA算法中相似的方法建立局部相對坐標系，并計算得到其余從節(jié)點的局部坐標。完成第一步之后，相鄰的局部坐標系依據(jù)ID號由大到小的原則進行坐標變換，最終以ID號最小的主節(jié)點為原點建立相對坐標系，從而實現(xiàn)定位。由于算法以節(jié)點簇為單位進行坐標變換，計算量和通信量相對SPA算法來說都得到大幅度減少，基本與節(jié)點個數(shù)呈線性比。該算法由于簇之間變換要求拓撲結(jié)構(gòu)比較規(guī)則，通信無障礙，所以在地形復雜，節(jié)點之間通信容易產(chǎn)生沖突的環(huán)境下，定位效果不是很好，節(jié)點覆蓋率比較低。
… …
5. 結(jié)論
相對定位算法由于無需事先布置錨節(jié)點，很大程度上節(jié)約了硬件成本，受外界信號干擾的影響較小，適合用于對節(jié)點硬件成本，算法計算能耗以及節(jié)點分布有嚴格限制的無線傳感器網(wǎng)絡。本文從通信量、覆蓋率和定位精度三個主要的性能指標對現(xiàn)有的幾種典型定位算法進行了綜合分析，通過圖表的形式比較節(jié)點密度和節(jié)點分布兩個方面對算法的影響，闡述了各算法在不同的節(jié)點布置環(huán)境下性能對比，說明了算法具體的適用范圍，并提出了適當?shù)母倪M方案。目前存在的算法大都需要在節(jié)點密度較高的環(huán)境下能獲得比較理想的定位效果，如何通過節(jié)點之間的消息傳輸和節(jié)點協(xié)作使得算法在某些節(jié)點密度較低的環(huán)境中也能實現(xiàn)定位精度和節(jié)點覆蓋率二者很好結(jié)合的問題，將是相對定位算法需要主要關注的方面。
