第16章-物聯(lián)網(wǎng)通信技術(shù)(曾憲武)LXX2014.7

第16章WSN的節(jié)點(diǎn)定位16.1節(jié)點(diǎn)定位的概念及基本原理16.2距離定位16.3距離無(wú)關(guān)的定位算法本章小結(jié)16.1節(jié)點(diǎn)定位的概念及基本原理

16.1.1定位的幾個(gè)相關(guān)概念

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

（2）跳數(shù)(HopCount)：兩個(gè)節(jié)點(diǎn)之間間隔的跳段總數(shù)稱為兩個(gè)節(jié)點(diǎn)間的跳數(shù)。

（3）跳段距離(HopDistance)： 兩個(gè)節(jié)點(diǎn)之間間隔的各跳段距離之和稱為兩節(jié)點(diǎn)間的跳段距離。

（4）基礎(chǔ)設(shè)施(Infrastructure)： 用于WSN節(jié)點(diǎn)定位的固定或移動(dòng)設(shè)備，如衛(wèi)星、基站、GPS等。（5）到達(dá)時(shí)間(TimeofArrival，TOA)：信號(hào)從一個(gè)節(jié)點(diǎn)傳播到另一節(jié)點(diǎn)所需要的時(shí)間稱為信號(hào)的到達(dá)時(shí)間。

（6）到達(dá)時(shí)間差(TimeDifferenceofArrival,TDOA)：兩種不同傳播速度的信號(hào)從一個(gè)節(jié)點(diǎn)傳播到另一個(gè)節(jié)點(diǎn)所需要的時(shí)間之差稱為信號(hào)的到達(dá)時(shí)間差。

（7）接收信號(hào)強(qiáng)度指示(ReceivedSignalStrengthIndicator，RSSI)：節(jié)點(diǎn)接收到無(wú)線信號(hào)的強(qiáng)度大小稱為接收信號(hào)的強(qiáng)度指示。（8）到達(dá)角度(AngleofArrival，AOA)：節(jié)點(diǎn)接收到的信號(hào)相對(duì)于節(jié)點(diǎn)自身軸線的角度稱為信號(hào)相對(duì)接收節(jié)點(diǎn)的到達(dá)角度。

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

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

1.三邊測(cè)量法

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

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

如圖16.1.3所示，已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)分別

為(xa,ya)、(xb,yb)和(xc,yc)，節(jié)點(diǎn)D相對(duì)于A、B、C的角度

分別為∠ADB、∠ADC、∠BDC。節(jié)點(diǎn)D的坐標(biāo)為(x,y)，對(duì)于節(jié)點(diǎn)A、C和角∠ADC，如果弧AC在△ABC內(nèi)，則能

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

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

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

Ax=b

式中

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

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

（1）基于距離的定位算法和距離無(wú)關(guān)的定位算法。

根據(jù)定位過程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，把定位算法分為基于距離的(RangeBased)定位算法和距離無(wú)關(guān)的(RangeFree)定位算法。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，并利用節(jié)點(diǎn)間的實(shí)際距離來(lái)計(jì)算出未知節(jié)點(diǎn)的位置；后者無(wú)需測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方位，而是利用節(jié)點(diǎn)間的估計(jì)距離計(jì)算出節(jié)點(diǎn)位置。（2）遞增式的定位算法和并發(fā)式的定位算法。

根據(jù)節(jié)點(diǎn)定位的先后次序不同，把定位算法分為遞增式的(Incremental)定位算法和并發(fā)式的(Concurrent)定位算法。遞增式的定位算法通話從信標(biāo)節(jié)點(diǎn)開始，信標(biāo)節(jié)點(diǎn)附近的節(jié)點(diǎn)

首先開始定位，依次向外延伸，各節(jié)點(diǎn)依次進(jìn)行定位。這類算法的主要缺點(diǎn)是定位過程中累積和傳播了大量的測(cè)量誤差。并發(fā)式的定位算法中所有的節(jié)點(diǎn)同時(shí)進(jìn)行定位計(jì)算。（3）基于信標(biāo)的定位算法和無(wú)信標(biāo)的定位法。

根據(jù)定位過程中是否使用信標(biāo)節(jié)點(diǎn)，把定位算法分為基于信標(biāo)節(jié)點(diǎn)的(BeaconBased)定位算法和無(wú)信標(biāo)節(jié)點(diǎn)的(BeaconFree)定位算法。前者在定位過程中，以信標(biāo)節(jié)點(diǎn)作為定位的

參考點(diǎn)，各節(jié)點(diǎn)定位后產(chǎn)生整體絕對(duì)坐標(biāo)系統(tǒng)；后者只關(guān)心節(jié)點(diǎn)間的相對(duì)位置，在定位過程中無(wú)需信標(biāo)節(jié)點(diǎn)，各節(jié)點(diǎn)先以自身作為參考點(diǎn)，將鄰近的節(jié)點(diǎn)包含到自己定義的坐標(biāo)系中，相鄰的坐標(biāo)系統(tǒng)依次轉(zhuǎn)換合并，最后產(chǎn)生整體相對(duì)坐標(biāo)系統(tǒng)。

16.2距離定位

基于距離的定位機(jī)制是通過測(cè)量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位來(lái)定位的。定位過程可分為測(cè)距階段、定位階段和修正階段。

在測(cè)距階段，未知節(jié)點(diǎn)先測(cè)量到鄰居節(jié)點(diǎn)的距離或角度，然后計(jì)算到鄰近信標(biāo)節(jié)點(diǎn)的距離或方位。在計(jì)算到鄰近信標(biāo)節(jié)點(diǎn)的距離時(shí)，可以計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的直線距離，也可以用兩者間的跳段距離作為直線距離的近似。在定位階段，未知節(jié)點(diǎn)在計(jì)算出到達(dá)三個(gè)或三個(gè)以上信標(biāo)節(jié)點(diǎn)的距離或角度后，利用三邊測(cè)量法、三角測(cè)量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。

在修正階段，需對(duì)求得的節(jié)點(diǎn)的坐標(biāo)進(jìn)行修正，以提高定位精度，減少誤差。

定位距離時(shí)，測(cè)量節(jié)點(diǎn)間的距離或方位主要有到達(dá)時(shí)間(TOA)、到達(dá)時(shí)間差(TDOA)、接收信號(hào)強(qiáng)度指示(RSSI)和到達(dá)角度(AOA)等定位方法。16.2.1TOA定位

在利用到達(dá)時(shí)間TOA的定位機(jī)制中，已知信號(hào)的傳播速度，可根據(jù)信號(hào)的傳播時(shí)間計(jì)算節(jié)點(diǎn)間的距離，然后利用已有算法計(jì)算出節(jié)點(diǎn)的位置。該方法計(jì)算量小、算法簡(jiǎn)單且定位精度高。一般采用如圖16.2.1所示的聲音收發(fā)裝置來(lái)完成測(cè)距和定位。圖16.2.1音頻收發(fā)定位裝置假設(shè)兩個(gè)節(jié)點(diǎn)的時(shí)間同步，發(fā)送端的揚(yáng)聲器發(fā)送聲音信號(hào)的同時(shí)，無(wú)線通信模塊發(fā)送同步消息通知接收節(jié)點(diǎn)的聲音信號(hào)發(fā)送的時(shí)間，接收節(jié)點(diǎn)的拾音器模塊在接收到聲音信號(hào)后，根據(jù)聲波信號(hào)的傳播時(shí)間和速度計(jì)算發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離。節(jié)點(diǎn)在計(jì)算出相鄰的多個(gè)信標(biāo)節(jié)點(diǎn)的距離后，可以利用三邊測(cè)量算法或極大似然估計(jì)算法計(jì)算出自身的位置。16.2.2TDOA定位

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

根據(jù)WSN中待定位節(jié)點(diǎn)周圍的信標(biāo)節(jié)點(diǎn)的分布情況不同，AHLoS算法定義了以下三種不同的子算法：（1）原子多邊算法。

當(dāng)未定位節(jié)點(diǎn)相鄰的信標(biāo)數(shù)為3個(gè)或3個(gè)以上時(shí)，使用最大似然估計(jì)法，這里也叫原子多邊算法。這里所講的信標(biāo)數(shù)是指?jìng)鞲衅骶W(wǎng)絡(luò)部署完畢后初始的情況下還沒有執(zhí)行定位算法

之前，因?yàn)橐獔?zhí)行定位算法，一部分未定位節(jié)點(diǎn)就可能轉(zhuǎn)化成了信標(biāo)節(jié)點(diǎn)。（2）迭代多邊算法。

當(dāng)待定位節(jié)點(diǎn)相鄰的信標(biāo)節(jié)點(diǎn)數(shù)小于3個(gè)時(shí)，與之相鄰的信標(biāo)節(jié)點(diǎn)通過廣播自身的位置信息并被待定位節(jié)點(diǎn)獲知，經(jīng)過對(duì)這些信息運(yùn)算處理后，確定了自身的位置，也成為信標(biāo)節(jié)點(diǎn)。當(dāng)未知節(jié)點(diǎn)的相鄰信標(biāo)節(jié)點(diǎn)的數(shù)量達(dá)到3個(gè)或3個(gè)以上時(shí)，使用最大似然估計(jì)法進(jìn)行未知節(jié)點(diǎn)的定位計(jì)算。（3）協(xié)作多邊算法。

WSN中傳感器節(jié)點(diǎn)的部署在很多應(yīng)用場(chǎng)合中是隨機(jī)的，而且信標(biāo)節(jié)點(diǎn)的數(shù)量也很少，這種情況下如果要使用信標(biāo)的信息來(lái)對(duì)未知節(jié)點(diǎn)進(jìn)行定位，就無(wú)法使用原子多邊算法或迭代多邊算法。協(xié)作多邊算法是這樣一種算法：經(jīng)過多次迭代定位以后，待定位節(jié)點(diǎn)的鄰居數(shù)量仍然不足3個(gè)，此時(shí)要依托多跳的局部信息（即通過其他節(jié)點(diǎn)的協(xié)助）來(lái)計(jì)算自身的位置。圖16.2.3是協(xié)作多邊算法的示例。圖16.2.3協(xié)作多邊算法示例在圖16.2.3中，節(jié)點(diǎn)C為待定位節(jié)點(diǎn)，其信標(biāo)節(jié)點(diǎn)僅有

相鄰節(jié)點(diǎn)A、E兩個(gè)，數(shù)量還是不足三個(gè)，此時(shí)需要通過計(jì)算到達(dá)信標(biāo)節(jié)點(diǎn)的多跳距離獲得E和F的位置信息，再利用原子多邊算法完成定位計(jì)算。該算法主要應(yīng)用于傳感器網(wǎng)絡(luò)中信標(biāo)密度較高、網(wǎng)絡(luò)規(guī)模不太大的情況。16.2.3AOA定位

AOA定位技術(shù)稱為到達(dá)角交匯定位技術(shù)。該技術(shù)在兩個(gè)以上的位置點(diǎn)設(shè)置方向性天線或天線陣列，獲得節(jié)點(diǎn)發(fā)射的無(wú)線電波角度信息，通過陣列天線或多個(gè)接收機(jī)聯(lián)合確定相鄰節(jié)點(diǎn)發(fā)送信號(hào)的方向，從而構(gòu)成一個(gè)從接收機(jī)到發(fā)射機(jī)的方位線，兩個(gè)方位線的交點(diǎn)即為待定位節(jié)點(diǎn)的位置。如圖16.2.4所示，待定位節(jié)點(diǎn)在獲得與參考點(diǎn)A和B所構(gòu)成的角度后，通過交匯法可確定自身的位置。圖16.2.4兩方為線相交確定待定位節(jié)點(diǎn)示意圖另外AOA信息還可以與其他一些信息一起形成定位精度更高的混合定位算法，但AOA定位法所采用的系統(tǒng)較為復(fù)雜?；贏OA的APS(AdHocPositioningSystem)算法是利用兩個(gè)能測(cè)量方向信息和距離信息的接收器的相互之間的幾何關(guān)系來(lái)確定未知節(jié)點(diǎn)坐標(biāo)的定位的。其原理如圖16.2.5所示，圖中的兩個(gè)接收器間的距離為L(zhǎng)，節(jié)點(diǎn)A在這兩個(gè)接收器連線的中點(diǎn)上，以此中點(diǎn)做該連線的中垂線，該中垂線為計(jì)算兩個(gè)相鄰節(jié)點(diǎn)間的方位角的基準(zhǔn)線。當(dāng)測(cè)出節(jié)點(diǎn)B到接收器1的距離為x1，到接收器2的距離

為x2后，根據(jù)幾何關(guān)系可以容易地確定節(jié)點(diǎn)A、B之間的方向角θ。在圖16.2.6中，A、B和C三個(gè)節(jié)點(diǎn)是已知其自身位置信息的信標(biāo)節(jié)點(diǎn)，節(jié)點(diǎn)D是待定位節(jié)點(diǎn)。如果已知節(jié)點(diǎn)D與A、B和C三個(gè)節(jié)點(diǎn)之間的方向角，從圖中的幾何關(guān)系中就可以得

出∠ADB、∠ADC和∠BDC，并應(yīng)用三角測(cè)量法確定節(jié)點(diǎn)D的坐標(biāo)。圖16.2.5由幾何關(guān)系確定節(jié)點(diǎn)間方向圖16.2.6三角測(cè)量原理圖16.2.4RSSI定位

基于接收信號(hào)強(qiáng)度指示的RSSI定位算法是一種利用接收信號(hào)強(qiáng)度指示測(cè)距的定位算法。該算法通過測(cè)量發(fā)送功率與接收功率來(lái)計(jì)算傳播損耗，并利用理論和經(jīng)驗(yàn)?zāi)Ｐ蛯鞑p耗轉(zhuǎn)化為發(fā)送器與接收器的距離。該方法易于實(shí)現(xiàn)，無(wú)需在節(jié)點(diǎn)上安裝輔助定位設(shè)備。當(dāng)遇到非均勻傳播環(huán)境、有障礙物造成多徑反射或信號(hào)傳播模型過于不精確時(shí)，RSSI測(cè)距精度和可靠性降低，一般將RSSI和其他測(cè)量方法綜合起來(lái)實(shí)現(xiàn)定位。比較著名的RSSI定位系統(tǒng)有微軟研發(fā)的RADAR系統(tǒng)。RADAR系統(tǒng)定位的基本原理是：在建筑物內(nèi)(監(jiān)測(cè)區(qū)域)部署數(shù)個(gè)基站，對(duì)建筑物的需監(jiān)測(cè)區(qū)域進(jìn)行覆蓋，基站一旦部署完畢，一般情況不再進(jìn)行位置移動(dòng)，而被監(jiān)測(cè)的建筑物內(nèi)部區(qū)域中可以隨機(jī)地部署位置可移動(dòng)的傳感器節(jié)點(diǎn)，即具有移動(dòng)性的客戶端。通過測(cè)量移動(dòng)終端處的信號(hào)強(qiáng)度值，并與預(yù)先建立的信號(hào)強(qiáng)度區(qū)域中各參考點(diǎn)的分布經(jīng)驗(yàn)數(shù)據(jù)值進(jìn)

行對(duì)比匹配，根據(jù)信號(hào)傳播模型和信號(hào)傳輸損耗確定移動(dòng)終端與基站之間的距離，在此基礎(chǔ)上應(yīng)用三邊測(cè)量法計(jì)算節(jié)點(diǎn)位置。RADAR系統(tǒng)工作的示意圖如圖16.2.7所示。建筑物內(nèi)的被監(jiān)測(cè)區(qū)域部署了三臺(tái)基站，對(duì)指定區(qū)域進(jìn)行了覆蓋；移動(dòng)終端的位置是隨機(jī)移動(dòng)的，它們與基站之間隨時(shí)可進(jìn)行通暢的無(wú)線通信。圖16.2.7RADAR系統(tǒng)工作示意圖1.信號(hào)強(qiáng)度經(jīng)驗(yàn)數(shù)據(jù)表匹配算法

在建筑物內(nèi)的監(jiān)測(cè)區(qū)域內(nèi)，當(dāng)基站部署后，選取若干個(gè)信號(hào)強(qiáng)度經(jīng)驗(yàn)數(shù)據(jù)測(cè)試點(diǎn)來(lái)測(cè)試信號(hào)的強(qiáng)度，以測(cè)得的數(shù)據(jù)進(jìn)行定位。

每個(gè)基站記錄移動(dòng)終端放置在這些測(cè)試點(diǎn)時(shí)所能接收到的信號(hào)強(qiáng)度為Ss。這樣就建立了一個(gè)測(cè)試點(diǎn)信號(hào)強(qiáng)度經(jīng)驗(yàn)數(shù)據(jù)

庫(kù)(x,y,Ss1,Ss2,Ss3)。經(jīng)比較，該均方差序列中最小值對(duì)應(yīng)的節(jié)點(diǎn)的坐標(biāo)就是該待定位節(jié)點(diǎn)的坐標(biāo)。

為提高數(shù)據(jù)處理的精度，采用對(duì)同一個(gè)監(jiān)測(cè)點(diǎn)采集的多個(gè)信號(hào)強(qiáng)度數(shù)據(jù)取平均值的方法，也可以選取均方差序列中幾個(gè)最小的均方差值對(duì)應(yīng)的幾個(gè)點(diǎn)，使用它們的質(zhì)心作為待定位節(jié)點(diǎn)的位置。2.信號(hào)傳播模型算法

由于建筑物內(nèi)部的墻壁內(nèi)含有鋼筋等金屬媒質(zhì)，會(huì)對(duì)無(wú)線信號(hào)產(chǎn)生較大衰減及反射干擾，所以無(wú)線信號(hào)在室內(nèi)的傳播遠(yuǎn)比室外空曠空間的傳播復(fù)雜。在WSN的傳輸中，當(dāng)數(shù)據(jù)從匯聚節(jié)點(diǎn)向遠(yuǎn)程監(jiān)控中心的傳送過程中，經(jīng)過室內(nèi)障礙物或墻壁后，信號(hào)功率將衰減相當(dāng)大的一部分。RADAR系統(tǒng)充分地考慮了這種衰減，建立了信號(hào)衰減

和傳播距離之間的關(guān)系。如考慮了室內(nèi)的障礙物結(jié)構(gòu)對(duì)無(wú)

線信號(hào)的傳播產(chǎn)生反射、折射、散射和透過衰減等綜合性

因素后，國(guó)外學(xué)者提出了一種墻壁衰減系數(shù)模型，也稱為WAF(WallAttenuationFactor)模型。該模型根據(jù)三個(gè)基站實(shí)際測(cè)量所得到信號(hào)強(qiáng)度數(shù)據(jù)，經(jīng)過理論分析、經(jīng)驗(yàn)及仿真得到的一個(gè)公式，可計(jì)算出待定位節(jié)點(diǎn)與三個(gè)基站之間的距離，然后利用三邊測(cè)量法計(jì)算出待定位節(jié)點(diǎn)的位置。計(jì)算基站接收到待定位節(jié)點(diǎn)發(fā)送的無(wú)線信號(hào)強(qiáng)度為(16.2.2)式中，P(d0)表示基站接收到參考點(diǎn)d0處發(fā)送信號(hào)的強(qiáng)度

（假設(shè)各點(diǎn)發(fā)送信號(hào)強(qiáng)度均相同），n為路徑長(zhǎng)度和路徑損耗之間的比例因子，d為待定位節(jié)點(diǎn)與基站間的距離，d0為參考

節(jié)點(diǎn)到基站的距離；nW為待定位節(jié)點(diǎn)與基站間相隔的墻壁數(shù)目，C為無(wú)線信號(hào)穿過墻壁數(shù)目的閾值，WAF為無(wú)線信號(hào)穿過墻壁時(shí)的衰耗因子（它取決于建筑物的具體結(jié)構(gòu)和墻壁的

建筑材料），［dBm］為信號(hào)的功率單位。當(dāng)采用式(16.2.2)計(jì)算出基站接收到待定位節(jié)點(diǎn)發(fā)送的無(wú)線信號(hào)強(qiáng)度后，與基站接收到參考點(diǎn)d0處的發(fā)送信號(hào)的強(qiáng)度比較，就可以解出待定位節(jié)點(diǎn)和基站之間的距離，在此基礎(chǔ)之上解出位置坐標(biāo)信息。無(wú)線信號(hào)穿過墻壁傳輸時(shí)的衰耗系數(shù)可以采用經(jīng)驗(yàn)值?；谛盘?hào)傳播模型的算法與根據(jù)信號(hào)強(qiáng)度經(jīng)驗(yàn)數(shù)據(jù)表匹

配的算法相比其成本低，無(wú)需先建立一個(gè)監(jiān)測(cè)區(qū)域中各測(cè)試點(diǎn)的信號(hào)強(qiáng)度經(jīng)驗(yàn)數(shù)據(jù)值數(shù)據(jù)庫(kù)，而且在建筑物內(nèi)的基站重新部署后，也無(wú)需重新建立該數(shù)據(jù)庫(kù)；但基于信號(hào)傳播模型的算法的定位精度不如根據(jù)信號(hào)強(qiáng)度經(jīng)驗(yàn)數(shù)據(jù)表匹配的算法

的定位精度。16.3距離無(wú)關(guān)的定位算法

16.3.1質(zhì)心算法

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

E(x5,y5)，其質(zhì)心坐標(biāo)為（16.3.1)質(zhì)心定位算法首先確定包含未知節(jié)點(diǎn)的區(qū)域，計(jì)算這個(gè)區(qū)域的質(zhì)心，將其作為未知節(jié)點(diǎn)的位置。

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

質(zhì)心算法完全依賴于網(wǎng)絡(luò)連通性，無(wú)需信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的協(xié)調(diào)，因此比較簡(jiǎn)單，容易實(shí)現(xiàn)。但質(zhì)心算法假設(shè)節(jié)點(diǎn)都擁有理想的球形無(wú)線信號(hào)傳播模型，而實(shí)際上無(wú)線信號(hào)的傳播模型井非如此，因此存在著較大的誤差。16.3.2DV-Hop算法

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

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

離為90m。節(jié)點(diǎn)A到B的跳數(shù)為2跳，節(jié)點(diǎn)A到C的跳數(shù)為6跳。應(yīng)用式(16.3.3)可得到：

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

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

1.DV-Distance算法

DV-Distance算法類似于DV-Hop算法，它們之間的區(qū)別在于：DV-Hop算法通過節(jié)點(diǎn)的平均每跳距離和跳數(shù)算出節(jié)點(diǎn)間的距離；而DV-Distance算法是通過節(jié)點(diǎn)的射頻通信來(lái)