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