無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究

1、無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究      摘要：本文介紹了利用交疊換思想定位節(jié)點(diǎn)的分布式定位算法ROCRSSI，和N-hop multilateration算法以及Robust positioning算法。由于無線傳感器網(wǎng)絡(luò)在不同的應(yīng)用場合可以采用不同的節(jié)點(diǎn)定位算法，本文可以用來當(dāng)作選用算法的一個參考文獻(xiàn)。關(guān)鍵詞：無線傳感器；節(jié)點(diǎn)定位；算法      Abstract：This paper describes the use of overlapping ideological position

2、ing for the nodes distributed location algorithm ROCRSSI, and N-hop multilateration algorithm and Robust positioning algorithm. As wireless sensor networks in different applications can use different node location algorithm, the paper can be used as a selection method references.Key words：Wireless s

3、ensors; node location; Algorithm   一    引言 無線傳感器網(wǎng)絡(luò)是由許多傳感器節(jié)點(diǎn)通過自組織的形式組織成的一種特     殊的ad-hoc網(wǎng)絡(luò)，每個傳感器節(jié)點(diǎn)由數(shù)據(jù)采集模塊，數(shù)據(jù)處理和控制模塊和通信模塊和供電模塊等組成，此外還可能包括與應(yīng)用相關(guān)的其它部分，比如定位系 統(tǒng)，動力系統(tǒng)等。借助于內(nèi)置多樣的傳感器，可以測量溫度，濕度，氣壓，化學(xué)等我們感興趣的物理現(xiàn)象。由于無線傳感器在軍事，醫(yī)學(xué)，環(huán)境保護(hù)等領(lǐng)域有著非常 廣闊的應(yīng)用前景，受到眾多國家科研機(jī)構(gòu)的重

4、視。傳感器節(jié)點(diǎn)的自身定位是傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)。例如目標(biāo)監(jiān)測與跟蹤，基于位置信息的路由，智能交通，物流管理等許多應(yīng)用都要求網(wǎng)絡(luò)節(jié)點(diǎn)預(yù)先知道自身的位置，并在通信和協(xié)議過程中利用位置信息完成應(yīng)用要求。 二    問題描述     目前提出的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的自身定位算法主要是利用傳感器網(wǎng)絡(luò)中                   

5、60;  少量已知自身位置的接天通過計(jì)算獲得其他未知節(jié)點(diǎn)的位置信息，只要有兩類：基于距離（range-based）的定位方法和不基于距離（range-free）的定位方法。常用的定位方法是range-based方法，這種方法需要先測量出節(jié)點(diǎn)之間的距離或者角度信息，再通過數(shù)學(xué)方法計(jì)算出節(jié)點(diǎn)自身的位置。測量節(jié)點(diǎn)間距離或者角度信息通常采用的方法有：TOA，TDOA，RSSI和AOA等。Range-free定位方法無需測量距離或者角度信息，僅根據(jù)網(wǎng)絡(luò)的連通性等信息就可以實(shí)現(xiàn)節(jié)點(diǎn)的自身定位。這種方法降低了對接點(diǎn)硬件的要求，在成本和 功耗方面比range-based方法具有優(yōu)勢，但定位的誤差也相

6、應(yīng)有所增加。目前提出的算法只要有：質(zhì)心算法，DV-hop算法，Amorphous算 法，APIT算法等。綜上所述，較好的方法一般具有以下幾個特征：A較小的能耗傳感器節(jié)點(diǎn)所攜帶能源有限和不易更換的特點(diǎn)要求定位算法應(yīng)該是低能耗的。B較高的定位精度這是衡量定位算法的重要指標(biāo)，一般以誤差與無線射程的比值來計(jì)算，20%表示定位誤差相當(dāng)于無線射程的20%。C計(jì)算方式是分布式的分布式的定位算法，即計(jì)算節(jié)點(diǎn)位置的工作在節(jié)點(diǎn)本地完成，分布式算法可以應(yīng)用于大規(guī)模的傳感器網(wǎng)絡(luò)。D 較低的錨節(jié)點(diǎn)密度毛節(jié)點(diǎn)定位通常依賴人工部署或者GPS實(shí)現(xiàn)。大量的人工部署不適合ad-hoc網(wǎng)絡(luò)，而且毛節(jié)點(diǎn)的成本比普通的節(jié)點(diǎn)要高兩個數(shù)量

7、級。E 較短的覆蓋時間本文就介紹幾種典型的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法。  三    各種算法1              ROCRSSI算法ROCRSSI節(jié)點(diǎn)定位算法屬于分布式距離無關(guān)的節(jié)點(diǎn)定位算法，他提出了一種新的定位思想：利用包含位置節(jié)點(diǎn)的相互交疊的環(huán)形區(qū)域來定位未知節(jié)點(diǎn)。雖然算 法中利用了RSSI，但在未直接點(diǎn)出只是比較相應(yīng)RSSI的大小，并為利用它來測距，因此該算法受環(huán)境因素要比利用RSSI世界測距受環(huán)境影響

8、要小，定位 誤差相對較低，同時，由于算法簡單，網(wǎng)絡(luò)能量開銷相對較小且無需額外的硬件開銷的優(yōu)點(diǎn)，使得ROCRSSI在當(dāng)前各種定位方法中不失為一個理想的選擇方 案。R0CRSSI(Ring Overlapping based Oil Comparison ofReceived Signal Strength Indicator，簡稱ROCRSSI)算法的可行性基于以下假設(shè)：在方向的某個范圍內(nèi)，隨著發(fā)送者和接收者之間距離的增加，接收者接收到的信號強(qiáng)度單 調(diào)遞減。算法的基本思想是：網(wǎng)絡(luò)中每個未知節(jié)點(diǎn)利用RSSI求出某些環(huán)形區(qū)域，進(jìn)一步求出這些環(huán)形區(qū)域的相交部分，并以其質(zhì)心作為自身坐標(biāo)。如圖1所示， 假

9、設(shè)錨節(jié)點(diǎn)A發(fā)送信標(biāo)后，未知節(jié)點(diǎn)s、錨節(jié)點(diǎn)B、錨節(jié)點(diǎn)C接收該信標(biāo)的信號強(qiáng)度分別為RSSIAs、RSS 蛆、RSSk ，而且節(jié)點(diǎn)s比較三者大小得出RSSI>RSS >RSSlAc，則S可以判斷出它到A 的距離大于A與B之間的距離 AB而小于A與C之間的距離。因此，S可知它必在以A為中心、以dAB為內(nèi)半徑并以為外半徑的環(huán)形區(qū)域內(nèi)。類似地，S同樣可以求出分別以B、C為中心的環(huán) 形區(qū)域。S求出這些環(huán)形區(qū)域的相交部分，并以相交區(qū)域的質(zhì)心作為自身坐標(biāo)，如圖2所示。  ROCRSSI算法可分為兩個階段：(1).RSSI傳播階段：首先，每個錨節(jié)點(diǎn)廣播固定數(shù)量的信標(biāo)。在階段，其每個

10、鄰居節(jié)點(diǎn)持續(xù)對接收信號強(qiáng)度采樣。然后，所有鄰居節(jié)點(diǎn)計(jì)算接收到的該錨節(jié) 點(diǎn)信號強(qiáng)度的平均值。若鄰居節(jié)點(diǎn)為未知節(jié)點(diǎn)，則它只需保存該平均值；若鄰居節(jié)點(diǎn)為錨節(jié)點(diǎn)，則它需要廣播一條RSSI消息，包含自身id、位置坐標(biāo)、參考錨 節(jié)點(diǎn)id及接收信號強(qiáng)度的平均值。任何接收到該RSSI消息的未知節(jié)點(diǎn)記錄該RSSI消息。(2).位置估計(jì)階段：當(dāng)未知節(jié)點(diǎn)經(jīng)過RSSI傳播階段接收到足夠信息后，就可以利用這些信息求出它所在的每一個環(huán)形區(qū)域，計(jì)算這些環(huán)形區(qū)域的交集，并以相交區(qū)域的質(zhì)心作為自身坐標(biāo)。 利用如下幾個重要的參數(shù)標(biāo)識對R0CRSSI算法的能量開銷進(jìn)行分析。其中，N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量；A為網(wǎng)絡(luò)中錨節(jié)點(diǎn)的數(shù)

11、量；CA為網(wǎng)絡(luò)節(jié)點(diǎn)的平均鄰居錨節(jié)點(diǎn)個數(shù)。為了便于表示，我們限定算法運(yùn)行的環(huán)境在二維空間內(nèi)。(1)通信開銷；由于該算法只需錨節(jié)點(diǎn)發(fā)送信標(biāo)信息，而且接收到該信標(biāo)信號的所有鄰居錨節(jié)點(diǎn)要廣播其接收信號強(qiáng)度，所以整個網(wǎng)絡(luò)發(fā)送的消息數(shù)量為A+A CA。(2)計(jì)算開銷：該算法的計(jì)算包含三部分，分別為未知節(jié)點(diǎn)處所有相關(guān)RSSI的比較、S所在環(huán)形區(qū)域的內(nèi)外半徑的計(jì)算(如圖1中，假設(shè)A、B、C三點(diǎn)坐標(biāo)分別為(X1 ，Y1)、(X2，Y2)和(X3，Y3)，則S所在的以A為中心的環(huán)的內(nèi)外半徑分別為d 1=（X1-X2）2+（Y1-Y2）2）0.5 和d2=（X1-X3）2+（Y1-Y3）2）0.5、S所在的所有環(huán)形

12、區(qū)域交集和質(zhì)心的計(jì)算。假設(shè)單個flop的能量消耗為F，則前兩部分的計(jì)算開銷分別為2CA(CA-2)F和12 CA F，假設(shè)該算法第三部分的計(jì)算開銷為 。     (3)能量消耗：節(jié)點(diǎn)的能量消耗主要包括通信和計(jì)算開銷，綜合上面的分析結(jié)果并使用發(fā)送的數(shù)據(jù)包的數(shù)量表示通信的能量消耗，該算法的網(wǎng)絡(luò)通信開銷為A(I+CA)，節(jié)點(diǎn)計(jì)算開銷為2CA(CA+4)F+。     節(jié)點(diǎn)定位算法雖然并沒有利用RSSI實(shí)際測距，但在實(shí)際的無線傳感器網(wǎng)絡(luò)中由于無線信道有著很強(qiáng)的不確定性，易受障礙物的反射、干涉、屏蔽、吸收等作用的 影響，無線

13、電傳播經(jīng)常會呈現(xiàn)異向傳播特性，在不同方向上具有不同的信號衰減速率，ROCRSSI算法也會因?yàn)椴灰?guī)則的信號傳播而得到錯誤的位置估計(jì)；而 且，未知節(jié)點(diǎn)利用與鄰近錨節(jié)點(diǎn)RSSI的對比來定位自身，使得該算法對網(wǎng)絡(luò)中錨節(jié)點(diǎn)密度要求較高；算法的定位精度依賴于網(wǎng)絡(luò)錨節(jié)點(diǎn)密度和周圍環(huán)境，容錯性 較差。該算法中每個錨節(jié)點(diǎn)在接收到鄰居錨節(jié)點(diǎn)的信號并得到相應(yīng)的RssI后，均要將其廣播至鄰近的未知節(jié)點(diǎn)，使得網(wǎng)絡(luò)的通信開銷較大。 2Robust positioning算法Robust positioning算法分為測距、定位和求精三階段，在測距階段，算法采用了Dv一hop算法的思想，首先使用典型的距離矢量交換

14、協(xié)議，使網(wǎng)絡(luò)中所有 節(jié)點(diǎn)獲得距錨節(jié)點(diǎn)的跳數(shù)(distanceinhops)。第二階段，在獲得其他錨節(jié)點(diǎn)位置和相隔跳距后，錨節(jié)點(diǎn)計(jì)算網(wǎng)絡(luò)平均每跳距離，然后將其作為一個 校正值(corection)廣播至網(wǎng)絡(luò)中。當(dāng)接收到校正值后，節(jié)點(diǎn)根據(jù)跳數(shù)計(jì)算與錨節(jié)點(diǎn)距離。如圖1所示，錨節(jié)點(diǎn)L2計(jì)算出他的網(wǎng)絡(luò)平均每跳距離為（40+75）/（2+5）=16.4m。在定位階段，采用了最小二乘法（lateration）進(jìn)行計(jì)算，當(dāng)未知節(jié)點(diǎn)獲得與3個或者3個以上錨節(jié)點(diǎn)（xi，yi）的距離di時，根據(jù)以下式子，可推出計(jì)算公式：（x1-x）2+（y1-y）2=d12（xn-x）2+（yn-y）2=dn2 

15、0;        (1)由（1）可推出：x12-xn2-2（x1-xn）x+y12-yn2-2（y1-yn）y=d12-dn2xn-12-xn-2(xn-1-xn)+yn-1-yn-2(yn-1-yn)y=dn-12-dn2            (2)令：，X=(ATA)-1ATb利用公式：Residue=（累加（xi-x）2+（yi-y）2）2-di）/n來判斷所求的結(jié)果是否有效，當(dāng)residue超過無線射程時

16、，結(jié)果是無效的。在求精階段，節(jié)點(diǎn)測量得到所有一跳鄰居的距離并以此更新自己的位置。該算法的所有位置計(jì)算都是用最小二乘法。算法引入了置信度來提高求精階段的性能，置信 度被用來再三邊定位中加權(quán)。當(dāng)未知節(jié)點(diǎn)更新其位置估計(jì)是同樣也更新其置信度。這樣，網(wǎng)絡(luò)的平均置信度將隨迭代而增加，提高了覆蓋度和精度。 該算法定位精度比較高，在網(wǎng)絡(luò)連通度較高的情況下能較好的容忍距離誤差。但由于對網(wǎng)絡(luò)拓?fù)涞囊蕾囆枰^長的覆蓋時間。 3N-hop multilateration算法    在 N-hop multilateration算法中，測距使用的是超聲波測距技術(shù)，該算法

17、也分為3個階段，第一階段是生成協(xié)作子樹，根據(jù)判定條件，在網(wǎng)絡(luò)中生成多個由 未知節(jié)點(diǎn)和錨節(jié)點(diǎn)組成的限制條件完整或超限制條件的構(gòu)形，稱為協(xié)作子樹。每個構(gòu)形包括n個未知變量(未知節(jié)點(diǎn)的坐標(biāo))和至少n個非線性方程式，并確保每個 未知變量擁有惟一解.未被協(xié)作子樹包含的節(jié)點(diǎn)在整個算法的后處理階段進(jìn)行定位。第二階段是對未知節(jié)點(diǎn)位置的粗略估計(jì)，他通過粗略未知節(jié)點(diǎn)和錨節(jié)點(diǎn)間的距離來估算未知節(jié)點(diǎn)的位置。如圖2所示，未知節(jié)點(diǎn)C在錨節(jié)點(diǎn)A，B所形成的BOundingbox里面，可推算出節(jié)點(diǎn)所在位置的x坐標(biāo)的取值范圍是(|xA-a|，|xB+（b+c）|)。    第三階段采用了循環(huán)求精，

18、根據(jù)預(yù)設(shè)的定位精度，使用卡爾曼濾波技術(shù)在每個協(xié)作子樹范圍內(nèi)(每個節(jié)點(diǎn)位置有惟一解)對第二階段的結(jié)果進(jìn)行循環(huán)求精。該算法要求錨節(jié)點(diǎn)要求錨節(jié)點(diǎn)要部署在網(wǎng)絡(luò)的邊緣才能達(dá)到較好的效果，而且循環(huán)求精的次數(shù)無法預(yù)知。 四 具體的定位系統(tǒng)1MIT開發(fā)了最早的松散耦合型室內(nèi)定位系統(tǒng)Cricket ，使用基于超聲波和RF的測距技術(shù)和基于最dx- 乘和卡爾曼濾波的三邊定位算法，測距范圍為lOm，經(jīng)發(fā)展測距精度可達(dá)13cm，定位精度在10cm 以下。2 Medusa MK一2 (測距范圍3m，測距精度為2cm)，并在該平臺上開發(fā)了AHLos    和nhop multilateration primitive定位算法。AHLos算法，定義了原子式、協(xié)作式和重復(fù)式最大似然估計(jì)定位，并將已定位的未知節(jié)點(diǎn)直接升級為錨節(jié)點(diǎn)以緩解錨節(jié)點(diǎn)稀疏問題，但會造成誤差累計(jì)，且沒有給出能否執(zhí)行collab-orative multilateration的充分條件，定位精度約為20cm。3WhiteHouse等人開發(fā)的基于AdHoc的Calamari_6 定位系統(tǒng)，使用聲波探測器和麥克風(fēng)，利用聲波測距(TOF)和信號強(qiáng)度(RSS)定位，測距范圍為30m，經(jīng)過聯(lián)合較正方法，測距誤