第16章WSN的節點定位16.1節點定位的概念及基本原理16.2距離定位16.3距離無關的定位算法本章小結16.1節點定位的概念及基本原理

16.1.1定位的幾個相關概念

一般情況下，信標節點在WSN節點中所占的比例很小，可以通過諸如GPS等定位設備獲得自身的精確位置。信標節點是未知節點定位的參考點。未知節點可以通過信標節點的位置信息來確定自身位置。如圖16.1.1所示，M代表信標節點，S代表未知節點。S節點通過與鄰居節點M的位置信息及節點間的通信，并采用一定的定位算法計算出自身的位置。（1）鄰居節點(NeighborNodes)：傳感器節點通信半徑內所有的其他節點稱為該節點的鄰居節點。

（2）跳數(HopCount)：兩個節點之間間隔的跳段總數稱為兩個節點間的跳數。

（3）跳段距離(HopDistance)： 兩個節點之間間隔的各跳段距離之和稱為兩節點間的跳段距離。

（4）基礎設施(Infrastructure)： 用于WSN節點定位的固定或移動設備，如衛星、基站、GPS等。（5）到達時間(TimeofArrival，TOA)：信號從一個節點傳播到另一節點所需要的時間稱為信號的到達時間。

（6）到達時間差(TimeDifferenceofArrival,TDOA)：兩種不同傳播速度的信號從一個節點傳播到另一個節點所需要的時間之差稱為信號的到達時間差。

（7）接收信號強度指示(ReceivedSignalStrengthIndicator，RSSI)：節點接收到無線信號的強度大小稱為接收信號的強度指示。（8）到達角度(AngleofArrival，AOA)：節點接收到的信號相對于節點自身軸線的角度稱為信號相對接收節點的到達角度。

（9）視線(LineofSight，LOS)：兩個節點間沒有障礙物間隔，雙方能“看見”，并能夠直接通信稱為兩個節點間在視線內。

（10）非視線關系(NoLOS,NLOS)：兩個節點之間存在障礙物，雙方“看不見”。圖16.1.1信標節點與未知節點圖16.1.2三邊測量法示意圖16.1.2節點定位的基本原理

1.三邊測量法

如圖16.1.2所示，已知節點A、B、C三個節點的坐標已知分別為(xa,ya)、(xb,yb)和(xc,yc)，它們與未知節點D的距離分別da、db和dc，則D的坐標(x,y)可由下式確定。(16.1.1)則D點的坐標(x,

y)為(16.1.2)2.三角測量法(Triangulation)

如圖16.1.3所示，已知A、B、C三個節點的坐標分別

為(xa,ya)、(xb,yb)和(xc,yc)，節點D相對于A、B、C的角度

分別為∠ADB、∠ADC、∠BDC。節點D的坐標為(x,y)，對于節點A、C和角∠ADC，如果弧AC在△ABC內，則能

夠唯一確定一個圓。設圓心為O1(x1,y1)，半徑為r1，于是α=∠AO1C=（2π－2∠ADC)，并有由式(16.1.2)可確定圓心O1點的坐標(x1,y1)和半徑r1。同理，可分別確定相應的圓心O2、r2及O3、r3，最后利用三邊測量法，由O1(x1,y1)、O2(x2,y2)和O3(x3,y3)確定D點坐標(x,y)。該方法是利用角度和已知節點的坐標將問題轉化為求三邊法中的距離d，即半徑r來求出未知節點坐標的。3.極大似然估計法

極大似然估計法(MaximumLikelihoodEstimation)如圖16.1.4所示。已知1、2、3等n個節點的坐標分別為(x1,y1)，(x2,y2)，(x3,y3)，…，(xn,yn)，它們到節點D的距離分別為d1，d2，d3，…，dn，假設節點D的坐標為(x,y)。

圖16.1.4極大似然估計示意圖節點D與節點1、2、3、…、n之間有如下關系：(16.1.4)用最后一個方程去減第一個，直到最后第二個方程,有(16.1.5)將式(16.1.5)表示為線性方程:

Ax=b

式中

對式(16.1.6)用最小均方差進行估計，即求解f=(AX－b)T

(AX－b)的極小值。令Y=AX－b，則令上式等于零，即(16.1.7)16.1.3定位算法的分類

（1）基于距離的定位算法和距離無關的定位算法。

根據定位過程中是否測量實際節點間的距離，把定位算法分為基于距離的(RangeBased)定位算法和距離無關的(RangeFree)定位算法。前者需要測量相鄰節點間的絕對距離或方位，并利用節點間的實際距離來計算出未知節點的位置；后者無需測量節點間的絕對距離或方位，而是利用節點間的估計距離計算出節點位置。（2）遞增式的定位算法和并發式的定位算法。

根據節點定位的先后次序不同，把定位算法分為遞增式的(Incremental)定位算法和并發式的(Concurrent)定位算法。遞增式的定位算法通話從信標節點開始，信標節點附近的節點

首先開始定位，依次向外延伸，各節點依次進行定位。這類算法的主要缺點是定位過程中累積和傳播了大量的測量誤差。并發式的定位算法中所有的節點同時進行定位計算。（3）基于信標的定位算法和無信標的定位法。

根據定位過程中是否使用信標節點，把定位算法分為基于信標節點的(BeaconBased)定位算法和無信標節點的(BeaconFree)定位算法。前者在定位過程中，以信標節點作為定位的

參考點，各節點定位后產生整體絕對坐標系統；后者只關心節點間的相對位置，在定位過程中無需信標節點，各節點先以自身作為參考點，將鄰近的節點包含到自己定義的坐標系中，相鄰的坐標系統依次轉換合并，最后產生整體相對坐標系統。

16.2距離定位

基于距離的定位機制是通過測量相鄰節點間的實際距離或方位來定位的。定位過程可分為測距階段、定位階段和修正階段。

在測距階段，未知節點先測量到鄰居節點的距離或角度，然后計算到鄰近信標節點的距離或方位。在計算到鄰近信標節點的距離時，可以計算未知節點到信標節點的直線距離，也可以用兩者間的跳段距離作為直線距離的近似。在定位階段，未知節點在計算出到達三個或三個以上信標節點的距離或角度后，利用三邊測量法、三角測量法或極大似然估計法計算未知節點的坐標。

在修正階段，需對求得的節點的坐標進行修正，以提高定位精度，減少誤差。

定位距離時，測量節點間的距離或方位主要有到達時間(TOA)、到達時間差(TDOA)、接收信號強度指示(RSSI)和到達角度(AOA)等定位方法。16.2.1TOA定位

在利用到達時間TOA的定位機制中，已知信號的傳播速度，可根據信號的傳播時間計算節點間的距離，然后利用已有算法計算出節點的位置。該方法計算量小、算法簡單且定位精度高。一般采用如圖16.2.1所示的聲音收發裝置來完成測距和定位。圖16.2.1音頻收發定位裝置假設兩個節點的時間同步，發送端的揚聲器發送聲音信號的同時，無線通信模塊發送同步消息通知接收節點的聲音信號發送的時間，接收節點的拾音器模塊在接收到聲音信號后，根據聲波信號的傳播時間和速度計算發送節點和接收節點之間的距離。節點在計算出相鄰的多個信標節點的距離后，可以利用三邊測量算法或極大似然估計算法計算出自身的位置。16.2.2TDOA定位

到達時間差（TDOA）定位是采用兩種信號到達的時間差以及兩個不同的傳播速率來計算距離的。以下介紹一種典型的基于TDOA的AHLoS(AdHocLocalizationSystem)算法。TDOA定位算法的原理如圖16.2.2所示。圖16.2.2TDOA定位算法原理圖圖16.2.2中，發射節點同時接收節點發送的無線信號和聲音信號，這兩個信號到達接收節點的時間分別為t1和t2，無線信號和聲音信號的傳播速度分別為v1和v2，那么發射與接收節點間的距離s為(16.2.1)AHLoS算法是一種基于TDOA定位算法的迭代算法。在該算法的起始階段，信標節點對外廣播自身的位置信息，使定位節點能測量與其相鄰的信標節點之間的距離，并可知道信標節點的位置信息。當信標節點的數量為3個或3個以上時，就可使用最大似然估計法計算節點的位置信息。如果帶定位節點的位置信息已經計算出來，該節點就轉化為信標節點，開始向外廣播自身位置信息。因此WSN中信標節點的數量隨著定位算法的進程在逐漸增多。

根據WSN中待定位節點周圍的信標節點的分布情況不同，AHLoS算法定義了以下三種不同的子算法：（1）原子多邊算法。

當未定位節點相鄰的信標數為3個或3個以上時，使用最大似然估計法，這里也叫原子多邊算法。這里所講的信標數是指傳感器網絡部署完畢后初始的情況下還沒有執行定位算法

之前，因為要執行定位算法，一部分未定位節點就可能轉化成了信標節點。（2）迭代多邊算法。

當待定位節點相鄰的信標節點數小于3個時，與之相鄰的信標節點通過廣播自身的位置信息并被待定位節點獲知，經過對這些信息運算處理后，確定了自身的位置，也成為信標節點。當未知節點的相鄰信標節點的數量達到3個或3個以上時，使用最大似然估計法進行未知節點的定位計算。（3）協作多邊算法。

WSN中傳感器節點的部署在很多應用場合中是隨機的，而且信標節點的數量也很少，這種情況下如果要使用信標的信息來對未知節點進行定位，就無法使用原子多邊算法或迭代多邊算法。協作多邊算法是這樣一種算法：經過多次迭代定位以后，待定位節點的鄰居數量仍然不足3個，此時要依托多跳的局部信息（即通過其他節點的協助）來計算自身的位置。圖16.2.3是協作多邊算法的示例。圖16.2.3協作多邊算法示例在圖16.2.3中，節點C為待定位節點，其信標節點僅有

相鄰節點A、E兩個，數量還是不足三個，此時需要通過計算到達信標節點的多跳距離獲得E和F的位置信息，再利用原子多邊算法完成定位計算。該算法主要應用于傳感器網絡中信標密度較高、網絡規模不太大的情況。16.2.3AOA定位

AOA定位技術稱為到達角交匯定位技術。該技術在兩個以上的位置點設置方向性天線或天線陣列，獲得節點發射的無線電波角度信息，通過陣列天線或多個接收機聯合確定相鄰節點發送信號的方向，從而構成一個從接收機到發射機的方位線，兩個方位線的交點即為待定位節點的位置。如圖16.2.4所示，待定位節點在獲得與參考點A和B所構成的角度后，通過交匯法可確定自身的位置。圖16.2.4兩方為線相交確定待定位節點示意圖另外AOA信息還可以與其他一些信息一起形成定位精度更高的混合定位算法，但AOA定位法所采用的系統較為復雜。基于AOA的APS(AdHocPositioningSystem)算法是利用兩個能測量方向信息和距離信息的接收器的相互之間的幾何關系來確定未知節點坐標的定位的。其原理如圖16.2.5所示，圖中的兩個接收器間的距離為L，節點A在這兩個接收器連線的中點上，以此中點做該連線的中垂線，該中垂線為計算兩個相鄰節點間的方位角的基準線。當測出節點B到接收器1的距離為x1，到接收器2的距離

為x2后，根據幾何關系可以容易地確定節點A、B之間的方向角θ。在圖16.2.6中，A、B和C三個節點是已知其自身位置信息的信標節點，節點D是待定位節點。如果已知節點D與A、B和C三個節點之間的方向角，從圖中的幾何關系中就可以得

出∠ADB、∠ADC和∠BDC，并應用三角測量法確定節點D的坐標。圖16.2.5由幾何關系確定節點間方向圖16.2.6三角測量原理圖16.2.4RSSI定位

基于接收信號強度指示的RSSI定位算法是一種利用接收信號強度指示測距的定位算法。該算法通過測量發送功率與接收功率來計算傳播損耗，并利用理論和經驗模型將傳播損耗轉化為發送器與接收器的距離。該方法易于實現，無需在節點上安裝輔助定位設備。當遇到非均勻傳播環境、有障礙物造成多徑反射或信號傳播模型過于不精確時，RSSI測距精度和可靠性降低，一般將RSSI和其他測量方法綜合起來實現定位。比較著名的RSSI定位系統有微軟研發的RADAR系統。RADAR系統定位的基本原理是：在建筑物內(監測區域)部署數個基站，對建筑物的需監測區域進行覆蓋，基站一旦部署完畢，一般情況不再進行位置移動，而被監測的建筑物內部區域中可以隨機地部署位置可移動的傳感器節點，即具有移動性的客戶端。通過測量移動終端處的信號強度值，并與預先建立的信號強度區域中各參考點的分布經驗數據值進

行對比匹配，根據信號傳播模型和信號傳輸損耗確定移動終端與基站之間的距離，在此基礎上應用三邊測量法計算節點位置。RADAR系統工作的示意圖如圖16.2.7所示。建筑物內的被監測區域部署了三臺基站，對指定區域進行了覆蓋；移動終端的位置是隨機移動的，它們與基站之間隨時可進行通暢的無線通信。圖16.2.7RADAR系統工作示意圖1.信號強度經驗數據表匹配算法

在建筑物內的監測區域內，當基站部署后，選取若干個信號強度經驗數據測試點來測試信號的強度，以測得的數據進行定位。

每個基站記錄移動終端放置在這些測試點時所能接收到的信號強度為Ss。這樣就建立了一個測試點信號強度經驗數據

庫(x,y,Ss1,Ss2,Ss3)。經比較，該均方差序列中最小值對應的節點的坐標就是該待定位節點的坐標。

為提高數據處理的精度，采用對同一個監測點采集的多個信號強度數據取平均值的方法，也可以選取均方差序列中幾個最小的均方差值對應的幾個點，使用它們的質心作為待定位節點的位置。2.信號傳播模型算法

由于建筑物內部的墻壁內含有鋼筋等金屬媒質，會對無線信號產生較大衰減及反射干擾，所以無線信號在室內的傳播遠比室外空曠空間的傳播復雜。在WSN的傳輸中，當數據從匯聚節點向遠程監控中心的傳送過程中，經過室內障礙物或墻壁后，信號功率將衰減相當大的一部分。RADAR系統充分地考慮了這種衰減，建立了信號衰減

和傳播距離之間的關系。如考慮了室內的障礙物結構對無

線信號的傳播產生反射、折射、散射和透過衰減等綜合性

因素后，國外學者提出了一種墻壁衰減系數模型，也稱為WAF(WallAttenuationFactor)模型。該模型根據三個基站實際測量所得到信號強度數據，經過理論分析、經驗及仿真得到的一個公式，可計算出待定位節點與三個基站之間的距離，然后利用三邊測量法計算出待定位節點的位置。計算基站接收到待定位節點發送的無線信號強度為(16.2.2)式中，P(d0)表示基站接收到參考點d0處發送信號的強度

（假設各點發送信號強度均相同），n為路徑長度和路徑損耗之間的比例因子，d為待定位節點與基站間的距離，d0為參考

節點到基站的距離；nW為待定位節點與基站間相隔的墻壁數目，C為無線信號穿過墻壁數目的閾值，WAF為無線信號穿過墻壁時的衰耗因子（它取決于建筑物的具體結構和墻壁的

建筑材料），［dBm］為信號的功率單位。當采用式(16.2.2)計算出基站接收到待定位節點發送的無線信號強度后，與基站接收到參考點d0處的發送信號的強度比較，就可以解出待定位節點和基站之間的距離，在此基礎之上解出位置坐標信息。無線信號穿過墻壁傳輸時的衰耗系數可以采用經驗值。基于信號傳播模型的算法與根據信號強度經驗數據表匹

配的算法相比其成本低，無需先建立一個監測區域中各測試點的信號強度經驗數據值數據庫，而且在建筑物內的基站重新部署后，也無需重新建立該數據庫；但基于信號傳播模型的算法的定位精度不如根據信號強度經驗數據表匹配的算法

的定位精度。16.3距離無關的定位算法

16.3.1質心算法

質心是指多邊形的幾何中心，多邊形頂點坐標的平均值就是質心節點的坐標。如圖16.3.1所示，多邊形ABCDE的頂點坐標分別為A(x1,y1)、B(x2,y2)、C(x3,y3)、D(x4,y4)、

E(x5,y5)，其質心坐標為（16.3.1)質心定位算法首先確定包含未知節點的區域，計算這個區域的質心，將其作為未知節點的位置。

在質心算法中，信標節點周期性地向鄰近節點廣播信標分組，信標分組中包含信標節點的標識號和位置信息。當未知節點接收到來自不同信標節點的信標分組數量超過某一門限k或接收一定時間后，就將其自身位置確定為這些信標節點所組成的多邊形的質心，即(16.3.2)式中，(xi1,yi1),(xi2,yi2),…，(xik,yik)為未知節點能夠接收到其分組的信標節點坐標。

質心算法完全依賴于網絡連通性，無需信標節點和未知節點之間的協調，因此比較簡單，容易實現。但質心算法假設節點都擁有理想的球形無線信號傳播模型，而實際上無線信號的傳播模型井非如此，因此存在著較大的誤差。16.3.2DV-Hop算法

在距離向量-跳段(DistanceVector-Hop,DV-Hop)算法中，未知節點首先計算與信標節點的最小跳數，然后估算平均每跳的距離，利用最小跳數乘以平均每跳距離，得到未知節點與信標節點之間的估計距離，再利用三邊測量法或極大似然估計法計算未知節點的坐標。DV-Hop算法的定位過程有以下三個階段：

第一階段，計算未知節點與每個信標節點之間的最小跳數。定位算法開始，WSN中的每個信標節點都向其鄰居節點廣播發送消息分組，包含自身的位置信息以及跳數，此時的初始跳數值設置為0。接收到信標節點消息分組的節點將自己的跳數由初始的0加1后，連同含有信標節點的位置信息一起再轉發給鄰居節點。這個過程覆蓋整個網絡，最后所有的節點都獲得了每一個信標節點的位置信息和最小跳數參數。在以中繼方式傳遞信標節點的位置信息和確定各節點到所有信標節點的最小跳數的過程中，如果某節點重復收到另一個信標節點的消息分組或該節點到另一個信標節點的最小跳數大于已經收到最小跳數值，則此時發生了信標節點的信息冗余，因此將其舍去。第二階段，計算每個信標節點與其他信標節點的實際跳段距離。當第一階段結束后，WSN中每個信標節點都記錄了到其他信標節點的位置信息和它們之間距離的跳數。利用這些信息就可以估算出平均每跳距離，并向整個網絡廣播該消息分組。第i個信標節點平均每一跳的距離ci為(16.3.3)現以圖16.3.2為例說明每跳平均距離的計算。節點A、B、C為信標節點，它們均有明確的坐標信息。節點A與B的距離為60m，節點A到C的距離為120m，節點B到C的距

離為90m。節點A到B的跳數為2跳，節點A到C的跳數為6跳。應用式(16.3.3)可得到：

節點A的每跳平均距離為（60+120)/(2+6)=22.5（m），節點B的每跳平均距離為(60+90)/(2+5)=21.4(m)，節點C的每跳平均距離為(120+90)/(5+6)=19.1(m)。圖16.3.2DV-Hop算法示意圖一個信標節點在計算完與其他各信標節點每跳的平均距離后，在對鄰居節點廣播的消息分組中，包含了各信標節點的最新信息。這樣，其他的節點可以得到信標節點的最新位置信息，一般是周圍的相鄰節點先得到該消息。在網絡中，位置信息以廣播的方式發射，網絡中的節點在收到位置信息時就與原來收到的位置信息進行比較，如果新收到的位置信息比原來的位置信息更新，就拋棄原來的位置信息，將新收到的位置信息儲存起來，這樣就可以保證節點只儲存l條最新的位置信息。第三階段，完成未知節點的位置估計。未知節點利用第二個階段獲取的網絡中每一個信標節點與其他信標節點的實際跳段距離的數據，使用三邊測量法和最大似然估計法來估算未知節點的位置信息。

從圖16.3.2可知，經過第一、二階段的計算，已知網絡中各信標節點之間的實際距離和跳數，未知節點M從信標節點B上獲得每跳平均距離為21.4m，則節點M與A、B、C三個信標節點之間的距離分別為l1=3×21.4=64.2m，l2=2×21.4=42.8m，l3=3×21.4=64.2m，最后使用三邊測量法可計算出M點的坐標。DV-Hop算法的優點是比較簡單，無需進行節點之間的距離測量，可以避免測量時帶來的誤差，傳感器節點不需要其他的附加硬件支持，是無線傳感器網絡節點定位的一個較經濟可行的方案。但是這種算法仍存在一些需要改進的地方：在獲得平均每跳的計算過程中，節點之間通信量較大，而且沒有考慮網絡中存在不良節點的影響，易造成平均定位誤差較大。16.3.3其他距離無關的定位算法

1.DV-Distance算法

DV-Distance算法類似于DV-Hop算法，它們之間的區別在于：DV-Hop算法通過節點的平均每跳距離和跳數算出節點間的距離；而DV-Distance算法是通過節點的射頻通信來