环球电气之家-午夜精彩视频-中国专业电气电子产品行业服务网站！

　　1. 引言
　　定位技術是無線傳感器網絡中的支撐技術，缺少位置數據的信息往往是沒有意義的。隨著無線傳感器網絡向節點數量多，鋪設范圍廣，基礎設施簡單和硬件成本低的方向發展，如何在減少節點硬件組件，算法實現簡單的同時獲得相對準確的定位信息已成為主要研究的課題之一?，F有定位算法根據定位過程中是否需要使用已知位置的信標節點，分為絕對定位算法和相對定位算法。前者一般是在待測區域事先布置一定比例的錨節點，這些節點通過GPS或是其他方法已得知自身絕對坐標，其余的未知節點通過與這些信標節點通信獲得自身坐標。相對定位算法則完全不需要事先布置信標節點，通過算法制定的方案，選取一定數量的未知節點建立相對坐標，其余的節點通過節點之間的協作關系和消息傳輸獲取自身在相對坐標系中的相對位置實現定位。相對定位算法無需信標節點和基礎設施，硬件成本低，并且不會受到復雜環境對遠距離信號傳輸的影響，適合于對節點硬件，能耗以及環境適應性有很高要求的無線傳感器網絡應用。

　　2. 定位算法分析

　　在無線傳感器網絡中，節點定位一般包括三個部分：距離測定、位置計算和定位過程。

　　(1) 距離測定：就是獲得兩個節點之間距離的方法，可分為基于測距和無需測距?；跍y距的算法(range-based)通過節點自身攜帶的測距功能直接測量兩個節點之間的距離。當前比較重要的測距方法主要是到達時間(TOA)、到達時間差(TDOA)和信號強度測距(RSSI)或者到達角度(AOA)。

　　TOA(Time of Arrival)：該技術通過測量信號傳播時間來測量距離。使用TOA 技術最基本的定位系統是GPS，GPS 系統需要昂貴、高性能的電子設備來精確同步衛星時鐘。因WSN節點硬件尺寸、價格和功耗限制，GPS 和其他TOA 技術無法廣泛應用于WSN。
　　
　　TDOA(Time Difference On Arrival)：TDOA測距技術被廣泛應用于WSN定位方案中。通過記錄兩種不同信號(常使用RF和超聲波)到達時間差異，基于已知信號傳播速度，直接把時間轉化為距離。已有多種定位算法使用TDOA實現測距。但該技術受限于超聲波傳播距離有限(超聲波信號通常傳播距離僅為20-30英尺，因而網絡需要密集部署)和NLOS(Non-Line-Of-Sight)問題對超聲波信號的傳播影響。雖然已有發現并減輕NLOS影響的技術，但都需要大量計算和通信開銷，不適用于低功耗的WSN應用中。
   
　　RSSI(Received Signal Strength Indicator)：已知發射功率，在接收節點測量接收功率，計算傳播損耗，使用理論或是經驗的信號傳播模型將傳播損耗轉化為距離，該技術主要使用RF 信號。因傳感器節點具有無線通信能力，故是一種低功率、廉價的測距方式，RADAR、SpotON等許多項目中使用了該技術。他的主要誤差來源是環境影響所造成的信號傳播模型的建模復雜性；反射、多徑傳播、NLOS)、天線增益等問題都會對相同的距離產生顯著不同的傳播損耗。通常將其看為一種粗糙的測距技術，它可能產生50%的測距誤差。
   
　　AOA(Angle of arrival)：該技術是估算鄰居節點發送信號方向，可通過天線陣列或多個接收器來實現，除定位外，還能提供方向信息，如MIT 的The Cricket Compass 等項目中都使用AOA 技術。

　　無需測距的算法(range-free)不需要節點自身的測距設備，通過跳數或是其他信息估計自身到選定的信標節點的距離值，由于是估計得到的數值，相對于基于測距的算法獲得的距離值誤差偏大。

　　(2) 位置計算：在獲取上述距離值之后，節點需要通過位置計算的方法計算得到坐標值?，F有的算法一般采用三邊測量法和三角測量法計算坐標。

圖1 三邊測量法示意圖

　　如圖1 所示，在未知節點獲得三個以上的信標節點距離值之后，就可以通過式(1)、式(2)和式(3)計算自身坐標。式中，(xa , ya)、(xb , yb)、(xc , yc)分別是三個信標節點的坐標，da、db、dc 是未知節點到三個信標節點的距離。

　　式(1)經過線性化，可得線性方程式(2):

　　式(2)中的N 是由于存在測距誤差加入的參數，它是根據測距誤差的分布形式存在的一個隨機誤差向量。如果未知節點測得的到信標節點的距離值大于三個，則可以加入(1)式中，進行更精確的計算。三角測量法與三邊測量法類似，通過獲取相對三個信標節點的角度值，計算得到圖1中三個圓的半徑，再經過三邊測量法計算得到坐標。三邊測量法和三角測量法由于涉及大量的矩陣運算和最小二乘的運算，計算量較大，針對這種情況，加州大學洛杉磯分校的Andreas Savvides等人提出的n-hop multilaterationprimitive定位算法中提出的最大最小值法通過簡單的折線運算估計未知節點的位置，如圖2所示。

圖2 最大最小值法示意圖

　　圖中A點和B點為信標節點，C點為未知節點。在獲得C點到A點和B點的折線距離a、b、c之后，在三角形ACK中，利用斜邊AC的長度a代替直角邊AK的長度，從而K點移動到K/點，B點類似，從而有：

　　最大最小值法估計得到的坐標值由于是取矩形區域的質心代替實際位置，若測得的距離值本身就存在較大的誤差，那么得出的結果沒有三邊定位精確，在一些要求精度不是很嚴格的情況或者是結果經過求精之后，可以滿足需要。

　　(3) 定位過程：不同算法根據上面兩步獲得的有限的距離值和部分節點的坐標，計算其余未知節點的機制。由于各種算法采取的策略不同，各種性能參數的區別主要由這一步決定。在分析定位算法的時候，一般要針對具體情況綜合考慮上述三個方面來考察算法性能。

　　3. 典型的相對定位算法

　　3.1 SPA 算法

　　瑞士洛桑聯邦工業大學的Srdjan Capkun 等人最早針對沒有基礎設施的移動無線自組網，提出SPA(self–positioning algorithm)算法[23]。它以網絡中節點密度最大的地方選取一個參考點作為全局相對坐標系的原點，其余每個節點分別通過測距功能測得鄰居節點之間的距離值，如圖3所示，實線表示二者距離可測得，虛線表示二者不是鄰居節點。每個節點在鄰居節點中選取兩個點A、B，選取原則是這兩個點本身也是鄰居節點，并且三個點不在同一直線上。以直線OA作為x 軸，以B點在OA上的投影BxB為y 軸正方向建立局部相對坐標系。所有的局部坐標系建立完成后，相鄰的坐標系通過坐標變換實現坐標統一，最終所有節點都變換形成以選取的參考點為原點的坐標系實現定位。由于每個節點都要參與多次的坐標變換，計算量和通信開銷都非常大。此算法開始是針對無線自組網提出的，不太考慮功耗問題，但是用到無線傳感器網絡當中，這種通信開銷和節點數量呈指數比上升的算法需要根據實際情況進行改進。

圖3 SPA算法示意圖

　　3.2 聚類 SPA 算法

　　美國仁斯利爾理工學院Rajagopal Iyengar 等人提出的聚類SPA(clustering-basedself–positioning algorithm)算法[24]是針對上述SPA算法通信量過大而提出的改進算法。首先通過運行隨機的定時器選取網絡中的主節點，主節點一跳范圍內的其他節點成為它的從節點。每個主節點使用SPA算法中相似的方法建立局部相對坐標系，并計算得到其余從節點的局部坐標。完成第一步之后，相鄰的局部坐標系依據ID號由大到小的原則進行坐標變換，最終以ID號最小的主節點為原點建立相對坐標系，從而實現定位。由于算法以節點簇為單位進行坐標變換，計算量和通信量相對SPA算法來說都得到大幅度減少，基本與節點個數呈線性比。該算法由于簇之間變換要求拓撲結構比較規則，通信無障礙，所以在地形復雜，節點之間通信容易產生沖突的環境下，定位效果不是很好，節點覆蓋率比較低。

… …

　　5. 結論

　　相對定位算法由于無需事先布置錨節點，很大程度上節約了硬件成本，受外界信號干擾的影響較小，適合用于對節點硬件成本，算法計算能耗以及節點分布有嚴格限制的無線傳感器網絡。本文從通信量、覆蓋率和定位精度三個主要的性能指標對現有的幾種典型定位算法進行了綜合分析，通過圖表的形式比較節點密度和節點分布兩個方面對算法的影響，闡述了各算法在不同的節點布置環境下性能對比，說明了算法具體的適用范圍，并提出了適當的改進方案。目前存在的算法大都需要在節點密度較高的環境下能獲得比較理想的定位效果，如何通過節點之間的消息傳輸和節點協作使得算法在某些節點密度較低的環境中也能實現定位精度和節點覆蓋率二者很好結合的問題，將是相對定位算法需要主要關注的方面。