無線傳感器網絡的節點定位算法分析綜述目錄TOC\o"1-3"\h\u21247無線傳感器網絡的節點定位算法分析綜述 131991距離測量方法 112307TOA測距 11700TDOA測距 227253AOA測距 38934RSSI測距 316021無需距離的測量方法 32674質心定位算法 416466DV-Hop算法 512216APIT定位算法 622053節點坐標計算方法 819955三邊測量法 82675三角測量法 931143極大似然法 10距離測量方法獲取節點與節點的距離，一般常用的方法有：TOA、TDOA、AOA、RSSI。TOA測距到達時間(TOA)測距方法原理相對簡單，如圖3.1所示，節點A將信號發送給節點B，通過信號從A傳輸到的時間來計算出節點A與節點B之間的距離。圖STYLEREF1\s3.SEQ圖\*ARABIC\s11TOA原理圖Fig3.1schematicdiagramofTOA時刻，信號從節點A向節點B發送，在時刻，信號到達節點B，信號空氣中的傳播速率為v，d為節點A與節點B之間的距離，則距離d的計算公式如下：(3-1)在應用中，信號的傳播速度非常的快，而節點由于自身能量有限，節點與節點之間的距離比較小，這樣就會導致信號的傳輸時間會非常的小，根據公式可知，即使只有1納米的誤差，也會產生0.3米左右的誤差，這會產生很大的測距誤差，最終會影響定位的精度。所以TOA測距方法對于硬件需要很高的要求，以此來保證發射節點與接收節點嚴格的時間同步。TDOA測距到達時間差(TDOA)的測距方法需要更高的硬件支持，需要在節點上安裝信號發射器，并且要求發射器能夠發送兩種不同速率的信號，再根據兩種信號到達接收節點的時間的不同，來計算節點間的距離，TDOA原理圖如3.2圖所示。圖STYLEREF1\s3.SEQ圖\*ARABIC\s12TDOA原理圖Fig3.2schematicdiagramofTDOA信號1和信號2在空氣中傳播的速度分別為和，信號1與信號2從節點A到節點B所用的時間分別為與，節點A與節點B之間的距離為d。那么時間之差公式可以表示為如下： (3-2)由(3-2)式變形可得節點A與節點B之間的距離為： (3-3)TDOA測距方法在提高精度的同時，也進一步增加了成本。TDOA雖然不需要控制時間同步，但是在節點上要安裝兩種射頻信號發送裝置，在節點分布密度較高時，成本會非常大，并且射頻信號易受到多徑、折射等環境因素的影響，因此不適用于復雜的環境下。AOA測距圖STYLEREF1\s3.SEQ圖\*ARABIC\s13AOA原理圖Fig3.3schematicdiagramofAOAAOA測距原理圖如圖3.3所示，傳感器節點需要配置感知信號方向的設備，接收節點接收到節點A與節點B發送的信息的同時，也可以得到節點與基準方向的夾角，這樣可以利用角度進行定位，也可以利用角度轉化為距離進行定位。AOA算法需要安裝支持感知信號方向的設備，增加了節點的耗能和成本。AOA測量結果易受到環境中非視距條件(NLOS)、信號反射的影響，并且只適用于節點固定的情況下，但是在精度方面AOA技術還是不錯的表現。RSSI測距RSSI即接收信號強度指示，發射節點發送一個信號至接收節點，信號到達接收節點后，會接收到一個信號強度值，之后會根據RSSI的測距模型將RSSI轉換為對應的距離d，再利用基于測距的定位算法求得未知節點的坐標。因為RSSI測距是本文研究的重點內容，詳細內容將在第四章進行介紹。無需距離的測量方法無需距離(Rang-free)的定位方法與基于距離(Rang-based)相比，不需要過高的硬件支持，在很大程度上節約了成本，它是依據監測區域中節點之間的連通度或者錨節點自身的位置信息來估算出未知節點的距離，下面介紹三種常見的無需距離的定位算法。質心定位算法質心算法原理圖如圖3.4所示。圖STYLEREF1\s3.SEQ圖\*ARABIC\s14質心定位算法原理圖Fig3.4Schematicdiagramofcentroidlocationalgorithm以圖3.4為例來講述質心定位算法的計算過程，O節點為未知節點，A節點、B節點、C節點、D節點、E節點分別為能夠與O節點進行通信的錨節點，它們的坐標分別為、、、、，那么O點坐標可以表示為： (3-4)關于哪些錨節點能夠參與到未知節點的定位，這就需要用到通信成功率來判斷，具體過程如下:在監測區域里，分布了m個錨節點(i=1,2,3……m)，在周每個期T錨節點發送包含自身的位置信息與ID的數據包，在該錨節點通信范圍內的未知節點O會接收到發送來數據包，在時間t=T*n內，錨節點向周圍發送了n個數據包，節點O會計算出每個錨節點發送來的數據包的成功率，如果大于設定的閾值，那么說明此錨節點與未知節點連通，可以作為質心運算中多邊形的一個頂點，通信成功率的公式如下： (3-5)為未知節點在時間t內接收到錨節點的數據包個數，表示錨節點在時間t內向周圍發送的數據包個數。質心定位算法復雜度低，但是非常依賴網絡的連通度與錨節點的密度大小。在具有較好的網絡連通度情況下和錨節點分布比較均勻的情況下，質心定位算法的誤差較小；相反，在錨節點密度低且隨機分布在監測區域時，質心定位算法的誤差會大幅度的增加。DV-Hop算法DV-Hop算法其原理簡單且不需要其他硬件設備加以輔助，算法大體可有分為三個步驟：(1)節點j會收到來自通信范圍內其它節點發送來的關于錨節點i數據包，該數據包包含了錨節點i位置與跳數信息，j節點依據跳數最小原則，對于收到的多個關于錨節點跳數進行舍取，留下最小跳數，并最小跳數的基礎上加一，將跳數與位置信息繼續轉發給其它節點。(2)計算錨節點i平均跳距。以步驟(1)中節點j與錨節點i為例，則兩節點之間的平均跳數計算公式如下：（3-6），分別為節點j和錨節點i的坐標，為節點j與錨節點i之間的最小跳數。（3）根據錨節點的平均跳距計算該錨節點與未知節點k之間的距離，計算公式如下：（3-7）其中，表示錨節點i與未知節點k之間的距離，表示錨節點i與未知節點k之間最小跳數。以圖3.5為例，闡述DV-Hop算法的運算過程。圖STYLEREF1\s3.SEQ圖\*ARABIC\s15DV-Hop算法原理圖Fig3.5SchematicdiagramofDV-Hopalgorithm圖中，節點A、B、C為錨節點，U為未知節點。L1、L2、L3表示錨節點之間的距離。節點間的最小跳數如下表所示：表格STYLEREF1\s3.SEQ表格\*ARABIC\s11節點間的最小跳數Tab3.1Minimumhopsbetweennodes節點UABCU0234A2056B3502C4620根據式(3.6)求得節點A、B、C的平均跳距分別為： (3-8) (3-9) (3-10)根據式(3.7)求得錨節點A、B、C與未知節點U之間的距離分別為：(3-11)(3-12)(3-13)由（3-11）、（3-12）、（3-13）可以得到未知節點U與錨節點A、B、C之間的預估距離，之后可以采用極大似然估計計算出未知節點的坐標。DV-Hop算法原理簡單且無需硬件支持，但在錨節點隨機分布、拓撲結構不規則的情況下，DV-Hop算法在估算未知節點與錨節點之間的距離時會出現較大偏差。APIT定位算法APIT(ApproximatePointInTriangulation)算法示意圖如圖3.6所示，該算法主要由三個步驟組成，具體如下：圖STYLEREF1\s3.SEQ圖\*ARABIC\s16APIT算法示意圖Fig3.6SchematicdiagramofAPITalgorithm(1)選擇未知節點P通信范圍內錨節點N個，將錨節點每三個一組得到個錨節點組，再將每組的錨節點作為三角形的頂點構成三角形。(2)從n個三角形中篩選出包含未知節點的三角形，這也是APIT算法最為關鍵的一步，具體方法如下：(a)P在三角形內 (b)P在三角形外圖STYLEREF1\s3.SEQ圖\*ARABIC\s17APIT算法測試原理圖Fig3.7testschematicdiagramofAPITalgorithm三角形內點測試法(PIT)可以用來判斷某一點P是否在內部，假設點P向某一方向移動，移動后點P都遠離或者靠近A、B、C三點，則點P在外部，若移動后點P既有遠離也有靠近，則點P在內部。在WSN中可以通過接收到信號強度大小來判斷距離的遠近，相同條件下，接收到信號強度越大說明距離越近，信號強度越小則距離越遠。以圖3.7（a）為例，節點P往節點1的方向移動，那么P會接近A、B而遠離C，從信號強度上體現就是，節點P接收到來自錨節點A與B的信號強度會增強，而接收到來自錨節點C的信號強度會減弱，那么就可以判斷節點P在三角形內部。但是在無線傳感器網絡中節點在絕大多數的情況下都是靜止的，通過上述方法無法完成節點位置判斷，那么需要對上述方法進行改進，將節點P與節點1進行互換，互換后用節點1代表移動后的節點P，即可通過接收強度的變化得到互換后靠近錨節點A、B，遠離錨節點C，進而得到節點P在三角形的內部的結論。對于圖（b）節點P與節點1互換，互換后同時靠近三個錨節點，則可判斷出節點P在三角形的外部。(3)求出篩選后的三角形組形成的重疊區域，選擇合適的定位算法求出未知節點坐標。APIT算法縮小的定位區域，提高了定位精度，但是該算法特別依賴節點分布密度，在節點分布不均勻和節點密度低的情況下，定位精度會大打折扣。節點坐標計算方法三邊測量法三邊測量法的原理圖如圖3.8所示。圖STYLEREF1\s3.SEQ圖\*ARABIC\s18三邊測量法原理圖Fig3.8SchematicdiagramofTrilateration節點A、B、C為錨節點，坐標分別為，節點P為未知節點，其坐標為，錨節點A、B、C到節點P的距離分別為、、。由歐式距離公式可得到如下方程組： (3-14)將公式（3-14）整理可得未知節點P的坐標為： (3-15)三角測量法三邊測量法的原理圖如圖3.9所示，圖STYLEREF1\s3.SEQ圖\*ARABIC\s19三角測量法原理圖Fig3.9Schematicdiagramoftriangulation圖3.9中，錨節點A、B、C的坐標分別為，節點P為未知節點坐標，其坐標為，錨節點A、B、C與節點P分別形成、、，通過AOA技術可以求出、、的值。以錨節點A與B為例闡述方法原理，在錨節點A、B與節點P不共線的情況下，由點A、B、P三點形成唯一圓弧，延長圓弧形成唯一圓，同理，點B、P、C形成，點C、P、A形成，三圓半徑分別為、、，圓心坐標分別為、、、，則有，根據歐式距離公式與三角函數變換可建立以下方程組： (3-16)求解方程組可得圓的圓心坐標與半徑，同理可以求出與半徑、與半徑，之后根據求出來三個圓心坐標與半徑，利用三邊測量法可以求出未知節點P的坐標。極大似然法極大似然法原理圖如圖3.10所示。圖STYLEREF1\s3.SEQ圖\*ARABIC\s110極大似然法原理圖Fig3.10Schema