無線傳感網(wǎng)絡(luò)定位技術(shù)研究與實現(xiàn)

1、無線傳感網(wǎng)絡(luò)定位技術(shù)無線傳感網(wǎng)絡(luò)定位技術(shù)無線傳感網(wǎng)絡(luò)定位技術(shù)摘要當代移動通信和無線網(wǎng)絡(luò)技術(shù)的不斷進步，使得我們在平時的生活中更加依賴于自動化或半自動化的設(shè)備。目前無線傳感網(wǎng)絡(luò)技術(shù)越來越受到人們的重視，并且已經(jīng)應(yīng)用在航天、生態(tài)、救災(zāi)和家居生活等眾多領(lǐng)域。其中定位技術(shù)在無線網(wǎng)領(lǐng)域中有著非常關(guān)鍵的作用，大多數(shù)情況下沒有坐標信息的無線傳感器節(jié)點缺少實際使用價值。目前已有較為成熟的無線傳感網(wǎng)定位技術(shù)可以被分為需要測距的定位技術(shù)和與測距無關(guān)的定位技術(shù)。本文首先分別介紹了基于測距的定位技術(shù)和無需測距定位算法的基本原理，并在此基礎(chǔ)上研究了常用二維和三維無線傳感網(wǎng)定位算法。關(guān)鍵詞：無線傳感網(wǎng)絡(luò)定位 二維定位 三

2、維定位 Abstract With the development of mobile communications and wireless networking technology, people have increasingly high demand for automation equipment. Currently,wireless sensor network technology draws more and more peoples attention,and it has been used in many fields,such as aerospace, mili

3、tary, medical,disaster rescue and medical area. Positioning technology plays a very important role in wireless sensor networks. In most cases, a wireless sensor node without location information is of no value useless. Currently,positioning technology is divided into the localization algorithm based

4、 on ranging and localization algorithm based on non-ranging. Firstly,the paper introduces the basic principles of the localization algorithms based on ranging and non-ranging. On the basis of these,we investigated common two-dimensional and three-dimensional localization algorithm for wireless senso

5、r networks. KEY WORDS： wireless sensor networks positioning, two-dimensionalpositioning, three-dimensional positioning1.緒論1.1引言23無線傳感器網(wǎng)路（WNS）被譽為21世紀最有影響力的21項技術(shù)和改變世界的l0大技術(shù)之一，無論在民用領(lǐng)域還是軍用領(lǐng)域均有巨大的應(yīng)用前景。無線傳感器節(jié)點通常隨機布放在不同的環(huán)境中執(zhí)行各種監(jiān)測和跟蹤任務(wù)，以自組織的方式相互協(xié)調(diào)工作，最常見的例子是用飛機將傳感器節(jié)點布放在指定的區(qū)域中，隨機布防的傳感器節(jié)點無法事先知道自己位置，傳感器節(jié)點必須能夠?qū)崟r

6、地進行定位。因此位置信息對傳感器網(wǎng)絡(luò)的監(jiān)測活動至關(guān)重要，事件發(fā)生的位置或獲取信息的節(jié)點位置是傳感器節(jié)點監(jiān)測消息中所包含的重要信息，對于大多數(shù)應(yīng)用而言，在不知道具體位置信息的監(jiān)測消息往往是毫不意義的。傳感器節(jié)點必須先明確自身位置才能夠詳細說明“在什么區(qū)域或位置發(fā)生了特定事件”，來實現(xiàn)對外部目標的定位、追蹤和覆蓋。因此，確定事件的發(fā)生的位置或獲取信息的節(jié)點位置是傳感器網(wǎng)絡(luò)最基本的功能之一，對傳感器網(wǎng)絡(luò)應(yīng)用的有效性起著關(guān)鍵的作用1。在無線傳感器網(wǎng)絡(luò)的各研究分支中，定位技術(shù)是無線傳感器網(wǎng)絡(luò)中關(guān)鍵的支撐技術(shù)之一。首先，在無線傳感器網(wǎng)絡(luò)的各種應(yīng)用中，節(jié)點的感知數(shù)據(jù)必須與位置相結(jié)合，離開位置信息，感知數(shù)據(jù)是

7、沒有意義的，如環(huán)境監(jiān)測、搶險救災(zāi)、森林火災(zāi)監(jiān)控等，沒有地理位置信息就無法確定事件發(fā)生何處，也不能夠采取有效及時的處理措施。其次，使用傳感器節(jié)點的位置信息能夠提高路由效率，節(jié)約能耗，增強網(wǎng)絡(luò)安全性及實現(xiàn)網(wǎng)絡(luò)拓撲的自配置等。然而，傳感器網(wǎng)絡(luò)規(guī)模通常比較大，給網(wǎng)絡(luò)中所有節(jié)點均安裝GPS收發(fā)器或者人工配置節(jié)點位置會受到成本、能耗、效率等問題的限制，甚至在某些場合可能無法實現(xiàn)。因此必須開展適合無線傳感器網(wǎng)絡(luò)特點的定位技術(shù)研究?；谏鲜鲈?，定位技術(shù)在無線傳感器網(wǎng)絡(luò)的理論研究和應(yīng)用中具有重要的意義，已經(jīng)成為了無線傳感網(wǎng)絡(luò)技術(shù)中的一個研究熱點。1.2無線傳感網(wǎng)定位技術(shù)概述在定位領(lǐng)域中，無線傳感網(wǎng)絡(luò)的節(jié)點可以

8、分為兩類：一類是己知自身坐 標的節(jié)點，被稱為信標節(jié)點或銷節(jié)點，該節(jié)點通常是通過GPS或人工部署的 方式得到節(jié)點坐標的；另一類是位置坐標節(jié)點，被稱為未知節(jié)點(Unknown Node)，該類節(jié)點則是需要我們通過周圍的描節(jié)點所提供的信息來估算出自身節(jié)點的坐標信息。根據(jù)未知節(jié)點定位過程中是否需要周圍描節(jié)點提供距離信息，可以將定位算法具體分為兩大類：一類是需要測距的定位算法，即需要錯節(jié)點提供與 未知節(jié)點間的距離信息；另一類是無需測距的定位算法，即不需要錨節(jié)點提供測距信息，僅通過角度或數(shù)據(jù)傳輸經(jīng)過的跳數(shù)等信息則可以完成定位的算法。一般來說，基于測距的定位算法利用三邊測量法、三角測量法或極大似然估計法來計

9、算節(jié)點的位置，常用的測距技術(shù)有RSSI，TOA，TDOA和AOA。RSSI定位技術(shù)具有功耗低和硬件成本低的優(yōu)勢，但也存在多路徑損耗等問題影響從而存在一定的誤差。TOA(根據(jù)到達時間定位)需要節(jié)點間有較為精確的節(jié)點時間同步機制，對于硬件設(shè)備要求比較高，并且對網(wǎng)絡(luò)結(jié)構(gòu)較為不均勾的網(wǎng)絡(luò)來說更加難于實現(xiàn)。TDOA根據(jù)到達時間差定位技術(shù)，需要利用超聲波信號傳播對于到達時間的準確測量來定位，但超聲波距離有限并且有障礙物等環(huán)境問題對超聲波的傳播有一定的影響；AOA(根據(jù)信號到達角度定位技術(shù))受外界環(huán)境干擾嚴重，并且需要額外的硬件來計算信號到達時的角度?；跍y距的定位算法比較精確，但需要節(jié)點本身通信頻率較高，

10、從而節(jié)點能耗幵銷較大。無需測距的定位算法則無需通信頻率較快，提高了定位能耗，但是卻犧牲了一定的定位精度。雖然定位精度降低了，但其在實際應(yīng)用中仍然具有許多典型案例。目前常用的無需測距的定位算法有質(zhì)心算法，DV-Hop算法，APIT定位算法。質(zhì)心算法的原理是通過獲取網(wǎng)絡(luò)中節(jié)點間的連通關(guān)系來佔算連通節(jié)點問的距離，從而進一步利用連通節(jié)點組成的兒何圖形質(zhì)心來估算H標節(jié)點坐標。DV-Hop算法能夠通過多跳傳輸獲取到目標節(jié)點無線覆蓋范圍之外的信標節(jié)點的數(shù)據(jù)，從而獲取到更多的有用信息。APIT定位算法是將錯節(jié)點的區(qū)域劃分成一個個三角形區(qū)域，通過判斷未知節(jié)點位于哪些三角形區(qū)域內(nèi)，進一步縮小定位范圍。利用描節(jié)點本

11、身的坐標即可進一步得出目標點的位置。2.二維定位算法2.1基于測距的定位算法目前常用的測距方式有接收信號強度、紅外線、超聲波以及GPS，這四種測距方式的性格比較如表2-1所示：表2-1 常用測距方式的比較測試方式RSSI紅外線超聲波GPS額外硬件無有有有硬件成本低低高高測距誤差03m05m010cm010m由表2-1可以得知，除RSSI外的其他三種測距方法，都需要節(jié)點安裝相應(yīng)固件，提高了本身的體積和價格；GPS技術(shù)有其局限性，更適用于戶外定位，小范圍的定位并不可靠；紅外線技術(shù)的測距精度比較低，而超聲波的測距成本較高；基于RSSI的測距技術(shù)則被廣泛應(yīng)用，并且市場是大多數(shù)節(jié)點本身就可以完成對RSS

12、I的獲取，易于實現(xiàn)，因此基于RSSI的測距技術(shù)是WSN中最常用的技術(shù)。2.1.1 RSSI定位算法RSSI定位算法是已知節(jié)點發(fā)射信號強度，接收節(jié)點測量接收到的該信號的強度，并計算傳播過程中的損耗，使用理論或經(jīng)驗的信號傳播衰減模型將傳播損耗轉(zhuǎn)換為距離，再利用已有的算法計算出節(jié)點的位置。比較典型的應(yīng)用如RADAR、SpotON。雖然在實驗環(huán)境中RSSl定位方法表現(xiàn)出良好的特性。但在實際應(yīng)用中，由于反射、多徑傳播、NLOS和天線增益等問題都會產(chǎn)生顯著的傳播損耗和較大的誤差，因此RSSI技術(shù)定位誤差較大1?；?RSSI 的定位算法利用信號傳輸過程中的衰減模型來計算錨節(jié)點與未知節(jié)點之間的距離，然后利用

13、所測量的距離來實現(xiàn)未知節(jié)點的定位。由于傳感器網(wǎng)絡(luò)節(jié)點自帶 RSSI 指示的功能，定位算法不會增加硬件消耗，應(yīng)用成本比較低，因而得到廣泛的應(yīng)用，其算法原理如圖2.1所示。圖 2.1 基于 RSSI 的定位算法原理示意圖如圖 2.1 所示，無線傳感器已知三個錨節(jié)點的位置信息，U表示未知節(jié)點的真實位置信息，U表示通過RSSI測量計算出來的位置信息。通常情況下，錨節(jié)點發(fā)送的廣播信號傳輸?shù)轿粗?jié)點的過程中，會受到環(huán)境和多路徑的影響，導致信號傳輸過程中產(chǎn)生衰減現(xiàn)象，未知節(jié)點收到的錨節(jié)點發(fā)送的信號強度會受到一定的影響。這種信號衰減會存在一定的規(guī)律性，通過測量未知節(jié)點接收的信號強度能夠估算錨節(jié)點與未知節(jié)點之間

14、的距離。信號的衰減模型表示如下： （2-1）其中n表示環(huán)境因子，它是隨著未知節(jié)點與錨節(jié)點之間距離的增加而路徑損耗的指數(shù)，一般取值范圍為2-4之間。本公式的計算單位為dB，PL(d)表示距離錨節(jié)點d處接收到的信號的功率；PL(d0)表示一個經(jīng)驗值，d0表示一個參考距離，即距離為d0接收到的信號功率。表示與傳播距離無關(guān)的高斯噪音，通常稱之為遮蔽因子。在環(huán)境因子和遮蔽因子已知的前提下，通過對未知節(jié)點接收功率的測量及其兩點之間的距離計算，其RSSI 模型如圖2.2所示：圖 2.2 RSSI 信號傳輸模型示意圖 由于不同的無線傳感器網(wǎng)絡(luò)定位的應(yīng)用環(huán)境的不同，無線傳感器網(wǎng)絡(luò)的目標監(jiān)測區(qū)域的環(huán)境因子和干擾因

15、子也不盡相同。上述提到的RSSI 測量中環(huán)境因子的經(jīng)驗值變化范圍多在 2-4 之間，是綜合室內(nèi)環(huán)境和室外環(huán)境的平均范圍。室內(nèi)環(huán)境因子的經(jīng)驗值在 1.9-2.2 之間。室外環(huán)境因子在1.4-5.4之間。環(huán)境因子的變化與最終未知節(jié)點測量的功率關(guān)系如圖2.3所示：圖 2.3 環(huán)境因子與功率之間的關(guān)系圖2.1.2基于TOA的定位算法基于TOA的定位算法是一種利用測量來自錨節(jié)點信號到達的時間來進行定位的一種算法。首先錨節(jié)點將發(fā)送時間設(shè)置在廣播信號中，并發(fā)送廣播信號，未知節(jié)點接收到錨節(jié)點發(fā)送的廣播信號并確定信號到達的時間，最終通過發(fā)送時間和接收時間來計算信號傳播的時間，然后在利用信號傳播速度來計算未知節(jié)點

16、與錨節(jié)點之間的距離，最后利用三邊測量法來實現(xiàn)計算出未知節(jié)點的坐標。TOA方法定位精度相對較高、但是需要錨節(jié)點與未知節(jié)點之間保持嚴格的時間同步，這對于硬件系統(tǒng)的要求比較高，因此對整個傳感器網(wǎng)絡(luò)的成本要求較高4。其算法原理如圖2.4所示： 圖 2.4 基于 TOA 的定位算法原理示意圖此外，從二維平面角度來研究節(jié)點到達時間定位算法需要至少在通訊半徑之內(nèi)的三個錨節(jié)點。其原理如圖2.5所示：圖 2.5 在二維平面的 TOA 定位原理示意圖其中r表示未知節(jié)點到錨節(jié)點的距離，而t表示信號從錨節(jié)點到未知節(jié)點的時間。C表示無線信號在介質(zhì)中的傳播速度，C是常數(shù)。設(shè)A(x1，y1)，B(x2，y2)，C(x3，y

17、3)為三個錨節(jié)點的坐標，未知節(jié)點的坐標設(shè)為 P(x，y)。測量的距離可以表示為如下： （2-2）將上三條公切弦屮任意兩條組合求交點，即可得到待測點P的估計坐標。2.1.3基于TDOA的定位算法基于TDOA的定位算法是一種基于測量錨節(jié)點到達未知節(jié)點的時間差來計算未知節(jié)點的位置的定位算法。在該算法中，錨節(jié)點首先設(shè)置兩種不同頻率的無線信號，然后同時廣播出去。由于這兩種信號在傳輸過程中的速度不一樣，因此到達未知節(jié)點的時間也不相同，可以根據(jù)這種時間差來計算錨節(jié)點與未知節(jié)點之間的距離，通過三邊測量法來計算未知節(jié)點的位置坐標信息。基于 TDOA的定位算法最大的特點是定位的精度高、誤差小。但同時監(jiān)測區(qū)域的環(huán)境

18、對于信號傳輸?shù)挠绊懣赡苡行Фㄎ坏木取?圖 2.6 TDOA 原理圖（一）基于TDOA的定位算法與TOA方法相似，但是該算法有兩種方式進行定位計算，第一種就是采用發(fā)送兩種無線信號，并利用未知節(jié)點的時間差來進行定位，常用的無線信號包括無線電波和超聲波。這種方法的最大支出在于需要在節(jié)點中增加接受兩種信號的接收裝置，從而會增加傳感器節(jié)點的硬件設(shè)計的復雜度，相應(yīng)的制作成本也會隨之增加。該算法的原理如圖所示，錨節(jié)點a在 To時刻發(fā)送無線電波，未知節(jié)點b在T1時刻接收到a發(fā)送的無線電波。錨節(jié)點a在T2時刻發(fā)送超聲波，未知節(jié)點b在T3時刻接收到a發(fā)送的超聲波信號。通過錨節(jié)點a的發(fā)送時間To、未知節(jié)點b接收時

19、間T1、錨節(jié)點a的發(fā)送時間T2和未知節(jié)點b接收時間 T3 以無線電信號的傳播速度VRF和超聲波的傳播速度VUS就可以計算出錨節(jié)點與未知節(jié)點之間的距離。另外一種測量方式就是測量兩個不同的錨節(jié)點發(fā)送過來的無線信號的時間差來進行定位計算。與第一種方式最大的不同在于這種方式只需要發(fā)送一種無線信號，對于硬件成本有所降低。最大的缺點在于要求錨節(jié)點時間的同步性。其原理如圖2.7所示：圖 2.7 TDOA 原理圖（二）圖2.7中，r12表示錨節(jié)點1到未知節(jié)點的距離減去錨節(jié)點2到未知節(jié)點的距離。r23表示錨節(jié)點2到未知節(jié)點的距離減去錨節(jié)點3到未知節(jié)點的距離。假設(shè)圖中錨節(jié)點1、2、3的坐標表示為A(x1，y1)，

20、B(x2，y2)，C(x3，y3)，未知節(jié)點的坐標p表示為(x，y)。無線信號從未知節(jié)點到錨節(jié)點之間的時間分別表示為t1，t2和t3則可以分別計算出r12和r23： （2-3） 將坐標 A、B、C、P 坐標帶入到（2-3）中，得到基于TDOA的定位算法中雙曲線的表達式（2-4）：（2-4）然后利用數(shù)學計算方式進一步求解，最終求的未知節(jié)點 p 的坐標。2.1.4基于AOA的定位算法 基于AOA的定位算法是利用未知節(jié)點與錨節(jié)點之間的角度關(guān)系來進行定位的一種算法。這種算法依靠天線陣列或者超聲波接收陣來測量錨節(jié)點與未知節(jié)點之間的角度，因此需要傳感器節(jié)點能夠測量角度的硬件設(shè)施，相對于實施成本而言比較高。

21、其原理如圖2.8所示： 圖 2.8 基于AOA的定位算法示意圖如圖2.8所示，A，B表示兩個已知的錨節(jié)點，C表示未知節(jié)點。未知節(jié)點C與錨節(jié)點 A、B之間的形成兩個夾角。根據(jù)AB直線和其測量出的夾角就可以畫出C點的具體位置，然后就可以計算未知節(jié)點C點的坐標?；贏OA的定位算法最大的優(yōu)點在于只需要知道兩個錨節(jié)點就可以計算未知節(jié)點的位置。不過由于需要測量錨節(jié)點與未知節(jié)點之間的角度，所以需要多個接收器輔助完成定位。所以對于硬件的消耗也比較高。2.1.5基于無線射頻干涉定位算法無線電干涉測量方法很早就被用于天文學等相關(guān)研究，但直到 2005 年，Maroti 等第一次提出了射頻干涉定位系統(tǒng) (Radi

22、o Interferometric Positioning System，RIPS) 將信號干涉方法應(yīng)用到無線傳感網(wǎng)絡(luò)定位系統(tǒng)中來3。RIPS 通過兩個發(fā)送節(jié)點發(fā)射頻率相近的射頻在待定位節(jié)點處得到疊加信號。Maroti 等證明當兩個射頻的頻率相近，它們的疊加信號的包絡(luò)的頻率可以被低成本的傳感節(jié)點所測量到。由此可以進一步得到兩個接收傳感節(jié)點的相對相位偏移為： （2-5）圖 2.9 無線射頻干涉測量從式2-5來看，兩個接收節(jié)點的相對相位偏移只與發(fā)送節(jié)點和接收節(jié)點之間的距離以及射頻波長有關(guān)。發(fā)送節(jié)點通過發(fā)射不同波長的射頻，可以得到多個如式2-5的方程。求解它們的聯(lián)立方程，便可以得到待定位傳感節(jié)點和錨

23、節(jié)點之間的相對位置。利用 RIP 方法的優(yōu)點在于其不受多徑反射的影響而且并不增加普通傳感節(jié)點的成本。但使用該方法對錨節(jié)點之間的同步要求很高。2.2基于非測距的定位算法在非測距算法中，不需要測量節(jié)點之間的距離及角度關(guān)系，根據(jù)整個網(wǎng)絡(luò)的連通性來計算或者估計未知節(jié)點的位置信息。非測距算法是降低整個網(wǎng)絡(luò)的整體消耗，提高無線傳感器網(wǎng)絡(luò)的整體性能。常用的非測距算法包括質(zhì)心定位算法DV-Hop（distance vector-hop）算法、凸規(guī)劃定位算法及 APIT （approximate point-in-triangulation test）定位算法等。2.2.1質(zhì)心定位算法 在質(zhì)心算法中，第一，發(fā)送

24、廣播信號。在發(fā)送廣播信號之前，需要設(shè)置錨節(jié)點信號的發(fā)射周期，然后將自身的標識號與所在的位置信息存入廣播數(shù)據(jù)包中，將數(shù)據(jù)包以設(shè)置的發(fā)射周期發(fā)送出去。第二，接收廣播信號。未知節(jié)點每接收到錨節(jié)點發(fā)送的廣播信息就自動存儲，并將計數(shù)器加1。當未知節(jié)點的超過一定的時間閾值，就認為接收到所有的廣播數(shù)據(jù)都已經(jīng)收到。第三，質(zhì)心定位。未知節(jié)點利用收到的全部節(jié)點信息組成N邊形，并將未知節(jié)點的位置認為是N邊形的質(zhì)心，然后對取得的全部錨節(jié)點坐標取平均值，從而得到未知節(jié)點的坐標。 （2-6）其中(Xi，Yi)表示未知節(jié)點，(X1，Y1)(XN，YN)表示(Xi，Yi)受到的錨節(jié)點的坐標。其算法原理如圖2.10所示： 圖

25、2.10 質(zhì)心定位算法的原理示意圖 圖2.10表明，質(zhì)心算法的關(guān)鍵在于未知節(jié)點能否接受到全部錨節(jié)點發(fā)送的廣播信號，對于整個網(wǎng)絡(luò)的依賴性特別強。算法不需要具體錨節(jié)點和未知節(jié)點之間的頻繁通信，算法流程相對簡單，是非測距算法中易于實現(xiàn)的算法。但同時，該算法以錨節(jié)點發(fā)射的廣播信號按照理想的無線信號模型進行傳播，對于目標監(jiān)測區(qū)域的環(huán)境干擾因素考慮不夠全面，信號在現(xiàn)實環(huán)境下會在傳播過程中出現(xiàn)反射、折射、干擾等現(xiàn)象，無法按照理想的無線信號傳輸模型進行傳播。從幾何角度來講，錨節(jié)點的數(shù)量越多，對于算法的精度越高，這樣就增加整個無線網(wǎng)絡(luò)的成本，而且維護費用也相對增加4。2.2.2 DV-Hop定位算法 DV-Ho

26、p 定位算法的原理是錨節(jié)點向所有的傳感器節(jié)點發(fā)送廣播信號，未知節(jié)點收到錨節(jié)點發(fā)送的廣播信號后存儲并轉(zhuǎn)發(fā)，最后目標監(jiān)測區(qū)域的傳感器節(jié)點都接收該廣播信號。目標檢測區(qū)域的相鄰節(jié)點之間的通信表示為1跳，當未知節(jié)點接收到廣播信號時，先計算錨節(jié)點傳播的最小跳數(shù)，然后根據(jù)網(wǎng)絡(luò)的連通性，計算平均每一跳的距離。將最小跳數(shù)乘以平均跳距，得到未知節(jié)點與錨節(jié)點之間的相對距離。最后通過極大似然法或者三邊測量法來計算未知節(jié)點的坐標信息4。DV-Hop的主要原理示意圖如圖2.11所示： 圖 2.11 DV-Hop 原理示意圖如圖2.11所示，節(jié)點L1、L2和L3是已知的錨節(jié)點，并且它們之間的距離和跳數(shù)也是已知的。根據(jù)已知信

27、息首先計算出平均節(jié)點的跳距為（35+63）/(2+5)=14M。假設(shè)未知節(jié)點為P，L2的廣播信號首先傳遞到P處，未知節(jié)點P首先從L2處獲取最短跳數(shù)，然后在以此從L1、L3處獲取最短跳數(shù)，從而計算未知節(jié)點與三個錨節(jié)點之間的距離： P 與L1之間的距離：d1=2*14=28 P 與L2之間的距離：d2=2*14=28 P 與L3之間的距離：d2=4*14=56 假設(shè)未知節(jié)點的坐標為(X，Y)，L1 坐標為(X1，Y1)，L2 坐標為(X2，Y2)，L3 坐標為(X3，Y3)，那么未知節(jié)點的坐標信息計算公式如下所示： (2-7）2.2.3凸規(guī)劃定位算法 凸集規(guī)劃定位算法首先需要完成整個傳感器網(wǎng)絡(luò)的節(jié)

28、點互通性，使得各個傳感器節(jié)點之間構(gòu)成幾何約束關(guān)系，從而使得傳感器網(wǎng)絡(luò)形成一個凸集的幾何圖形。這樣就將傳感器定位轉(zhuǎn)換為幾何關(guān)系的最優(yōu)解的問題。凸集約束優(yōu)化的方式是將線性優(yōu)化方式和線性規(guī)劃優(yōu)化方式相結(jié)合，通過這樣的結(jié)合得到一個全局的優(yōu)化方案，從而實現(xiàn)未知節(jié)點的定位4。其原理如圖2.12所示：圖 2.12 凸規(guī)劃定位算法原理示意圖如圖2.12所示，算法首先要根據(jù)錨節(jié)點之間的位置以及錨節(jié)點的與未知節(jié)點P之間相互通信的范圍來計算位置節(jié)點存在的某個區(qū)域。如果能夠準確的計算出這個區(qū)域，可以將這個區(qū)域轉(zhuǎn)換為矩形圖形D，然后計算該矩形區(qū)域D的質(zhì)心坐標并將其轉(zhuǎn)換為未知節(jié)點的坐標。幾何約束條件越小那么算法的精度就會

29、越高。在算法的使用過程中，為了盡可能的使用約束條件，需要錨節(jié)點盡可能的分布在整個傳感器網(wǎng)絡(luò)的邊緣部分。如果傳感器節(jié)點離開了網(wǎng)絡(luò)中心，那么就會增加算法定位的誤差。 2.2.4 APIT定位算法 APIT 定位算法一種類似三角形內(nèi)點測試的算法，主要是基于區(qū)域規(guī)劃的傳感器節(jié)點定位算法。該算法的原理就是錨節(jié)點首先發(fā)送廣播信號，未知節(jié)點接收到所有的相鄰的錨節(jié)點的坐標信息，然后從得到的錨節(jié)點的坐標中隨機選取三個組成一個三角形。利用三角形的幾何關(guān)系來測試錨節(jié)點組成的三角形是否包括未知節(jié)點，如果不包括則摒棄，如果包括則存儲三個節(jié)點的位置信息。如此循環(huán)選取相鄰錨節(jié)點組成三角形，直到所有的相鄰的錨節(jié)點都選取完成或

30、者選取的三角形已經(jīng)達到了定位的精度則停止。通過上述過程形成一個多邊形區(qū)域。將多邊形的質(zhì)心作為未知節(jié)點的位置。其原理如圖2.13所示：圖 2.13 APIT 定位算法原理示意圖如圖2.13所示，對APIT算法主要流程進行分析： （1）錨節(jié)點發(fā)送廣播信號，所有的未知節(jié)點接受錨節(jié)點發(fā)送的信號，并存儲所有的錨節(jié)點位置信息； （2）從存儲的錨節(jié)點信息中隨機抽取三個錨節(jié)點組成三角形，并判斷未知節(jié)點是否在三角形內(nèi)部；如果在三角形內(nèi)部，則存儲起來； （3）將所有的符合條件（2）的三角形重疊起來，計算重疊區(qū)域的幾何圖形； （4）取幾何圖形的質(zhì)心為未知節(jié)點的位置P，并計算P的坐標信息。 APIT的算法是一種典型的

31、分布式定位算法，因為在定位計算中，都是由每個節(jié)點內(nèi)部完成。該算法最大的優(yōu)勢在于實現(xiàn)了分布式計算，節(jié)約了未知節(jié)點計算的開支，同時不受無線傳感網(wǎng)網(wǎng)絡(luò)節(jié)點的分布的影響，最大的缺點在于傳感器網(wǎng)絡(luò)中需要布置大量的錨節(jié)點來完成定位。 2.3典型算法比較表2-2 典型算法的比較名稱信標節(jié)點數(shù)鄰居節(jié)點數(shù)功耗成本外加裝置通道開銷定位精度RSSI影響小影響小低低無小低TOA影響小影響小較高高有小較高TDOA影響小影響小高高有小高AOA影響小影響小中高有小中RIPS影響小影響小低低無小低質(zhì)心算法影響較大影響大低低無中低DV-hop影響較大影響較大低低無大低凸規(guī)劃影響較大影響大低低無大低APIT影響大影響較大低低無中

32、中3.三維定位算法經(jīng)過前面兩章對WSN節(jié)點定位技術(shù)的介紹，我們對節(jié)點定位技術(shù)有了一定的了解，但其大多數(shù)算法針對的是針對二維空間的，而在實際應(yīng)用中許多情況都需要處于三維空間中，例如部署在高山、森林中的無線傳感器節(jié)點，懸浮在空氣中用來檢測空間不同位置的氣溫、懸浮顆粒物等情況。這些應(yīng)用的前提是已知節(jié)點的三維空間的坐標，所以有必要進行三維空間的定位算法的研究?，F(xiàn)如今，在國內(nèi)外無線傳感器節(jié)點定位領(lǐng)域中，仍然缺少一種被公認的三維空間定位算法。目前，針對實際應(yīng)用中的三維定位的需要，人們提出了許多的三維定位算法，如Landscape-3D、Constrained 3-D、Ou算法、APIS等幾種典型的無線傳感

33、器網(wǎng)絡(luò)三維定位算法。3.1 IRSSI-3D定位算法與二維定位算法類似，三維無線傳感器網(wǎng)絡(luò)中也需要充當不同角色的無線傳感器節(jié)點，包括信標節(jié)點、匯聚節(jié)點和未知節(jié)點。算法要求信標節(jié)點具有可以提取接收到的數(shù)據(jù)包信號強度RSSI的能力，并且目標網(wǎng)絡(luò)進行周期性的分布。假設(shè)無線傳感器節(jié)點符合理想的信號傳輸模型，即在三維空間中是一個中心福射的球，并且隨著點到球心距離的增加信號強度成逐漸衰減的趨勢。在目標區(qū)域(W，H，T)內(nèi)部署描節(jié)點和未知節(jié)點，將錨節(jié)點設(shè)置成向周圍廣播自身信息，包括自身的ID，信號能量大小，位置信息。首先，信標節(jié)點接收到其鄰居信標節(jié)點發(fā)送來的信號，并存儲，當獲取到多個鄰居信標節(jié)點后，根據(jù)距離

34、的不同設(shè)置加權(quán)平均數(shù)，并計算其對應(yīng)的衰減系數(shù)。然后每個描節(jié)點向位置節(jié)點發(fā)送自身坐標，和其所在位置的衰減系數(shù)，未知節(jié)點則根據(jù)鄰居錨節(jié)點的衰減系數(shù)和坐標進行計算，從而得出其到各個鄰居描節(jié)點的距離。最后，過濾較遠的鄰居節(jié)點，選擇最近的四個鄰居鋪節(jié)點，利用與鄰居節(jié)點的距離，根據(jù)四面體定位算法求出未知節(jié)點的坐標。算法的具體過程如下：1.確定目標監(jiān)測區(qū)域，部署描節(jié)點和未知節(jié)點。2.最佳節(jié)點數(shù)量計算：即根據(jù)所選區(qū)域和節(jié)點通信能力，估算出最佳節(jié)點數(shù)量。3.信標節(jié)點發(fā)送信號：每個信標節(jié)點向其他鄰居節(jié)點發(fā)送信號，信號包括自身坐標信息和ID信息。4.鋪節(jié)點處理接收到的信息：接收到其他鋪節(jié)點信號后，根據(jù)信號能量大小和

35、未知信息計算信號衰減系數(shù)，當有多個鄰居錨節(jié)點時，由于根據(jù)距離的不同，利用加權(quán)平均數(shù)求最后的衰減系數(shù)。5.鋪節(jié)點向未知節(jié)點發(fā)送自身所在位置的衰減系數(shù)，計算未知節(jié)點到各個鄰居鋪節(jié)點之間的距離。6.過濾較遠的鄰居節(jié)點，選擇最近的四個鄰居鋪節(jié)點，利用與鄰居節(jié)點的距離，根據(jù)四面體定位算法求出未知節(jié)點的坐標。3.2 Landscape-3D算法Landscape-3D算法的核心是采用了LA ( Location Assistant)設(shè)備每隔一段吋間就向周圍發(fā)射其坐標消息，并且LA裝置處予運動狀態(tài)，目標節(jié)點通過接收到LA裝置的位置信息后，利用RSSI測距技術(shù)獲取與LA之間的距離，從而利用數(shù)學模型來確定目標節(jié)

36、點的坐標，如圖所示。圖 3.1 Landscape-3D 原理圖假設(shè)LA裝置在三維空間中是運動的，并且在運動過程中隨時可以獲取自身的位置信息。LA裝置的位置信息可以是，提前設(shè)計好的運動軌跡，或者可以利用GPS等定位設(shè)備為其定位。LA裝置向網(wǎng)絡(luò)中每隔一段時間就向周圍廣播自身的坐標信息，被定位節(jié)點獲取到該消息后可以提取RSSI來計算到該節(jié)點的距離信息。為了提高測距的精確度，該算法嘗試用狀態(tài)預(yù)測和更新迭代的方法，當以離線方式進行處理時，每個節(jié)點首先收集距離信息并通過逐漸地增加觀察信息來更新估計的位置。Landscape-3D算法的最大優(yōu)點是不依賴與網(wǎng)絡(luò)中節(jié)點的密度和網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，減小了通信幵銷。并

37、且每個節(jié)點都是獨立的，可以獨立計算自身的位置坐標，因此對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和規(guī)模無關(guān)。其缺點是對LA裝置的硬件要求比較高，因為整個算法的前提是LA具有較準確的未知獲取能力，該裝置直接決定了算法的精確度。3.3 Ou算法Ou算法類似于Landscape-3D算法，需要在網(wǎng)絡(luò)中部署有一個可以周期性的廣播身位置信息的飛行描節(jié)點(Flying Anchor)。同樣的該算法需要做如下要求：1.每個飛行鋪節(jié)點可以周期性的獲取自身位置，并能夠?qū)⑽恢眯畔V播給被定位節(jié)點；2.在網(wǎng)絡(luò)中，飛行鋪節(jié)點的密度足夠，能夠用于未知節(jié)點坐標的獲??；3.節(jié)點間不互相干擾，相對獨立。圖3.2 Ou算法原理示意圖如圖所示，S點為目標

38、節(jié)點，虛線代表飛行錨節(jié)點所穿過的路徑，當節(jié)飛行錨節(jié)點處于A和B兩點之間時，目標點S可以收到飛行錨節(jié)點發(fā)送的距離信息。此時我們可以獲取到AS的距離以及BS的距離，同吋可以獲取到A和B的位置坐標，由此算法可以進一步利用幾何模型來計算出目標點S的坐標。綜上所述，現(xiàn)有常用的三維空間定位算法，大都在能量消耗、硬件成本和定位精度上做了折中，由于三維空間定位中環(huán)境更加復雜，現(xiàn)在沒有更加普遍適合各種環(huán)境的算法出現(xiàn)?，F(xiàn)有算法也對硬件要求比較高，Landscape-3D算法和Ou算法都需耍有特定軌跡的鋪節(jié)點，這一點在實驗室環(huán)境下，甚至在實際應(yīng)用中都較難于實現(xiàn)。4.總結(jié)無線傳感器網(wǎng)絡(luò)是一種新型通信技術(shù)，它基于嵌入式

39、設(shè)備，可以實現(xiàn)分布式無線信息的傳輸，被認為是21世紀最有價值的技術(shù)之一。無線傳感網(wǎng)絡(luò)己經(jīng)廣泛應(yīng)用于航天、生態(tài)、救災(zāi)和家居生活等眾多領(lǐng)域，能彌補傳統(tǒng)網(wǎng)絡(luò)在許多領(lǐng)域上的不足或空缺。傳感器網(wǎng)絡(luò)節(jié)點為智能系統(tǒng)提供周圍環(huán)境的上下文相關(guān)信息，在許多情況下，若節(jié)點本身不能獲取到關(guān)于位置的信息，則本身已經(jīng)失去了其使用價值。本文首先分別介紹了基于測距的定位技術(shù)和無需測距定位算法的基本原理，并在此基礎(chǔ)上研究了常用二維和三維無線傳感網(wǎng)定位算法。本文對無線傳感器網(wǎng)絡(luò)中的基本定位原理、國內(nèi)外研究現(xiàn)狀進行了歸納和介紹. 目前研究的各類定位算法都是在綜合權(quán)衡能耗、 成本和精度等因素的基礎(chǔ)上提出來的, 其計算量、 精度等方面

40、也存在較大差別, 適合的應(yīng)用范圍也各不相同. 因此, 無線傳感器網(wǎng)絡(luò)中定位方法的應(yīng)用需要針對不同的場合, 綜合考慮節(jié)點的規(guī)模、成本及系統(tǒng)對定位精度等要求來設(shè)計和選擇. 同時, 對于具有分布式、 低復雜性、 高精度、 通用性等特點的無線傳感器網(wǎng)絡(luò)定位方法還有待進一步深入研究.參考文獻1 程海軍. 基于RSSI的無線傳感器網(wǎng)絡(luò)定位算法改進研究D. 重慶理工大學, 2013.2 楊軍.無線傳感網(wǎng)絡(luò)節(jié)點定位算法綜述J.儀器儀表標準化與計量, 2012, 01：38-41. 3 徐學永.面向應(yīng)用的無線傳感網(wǎng)絡(luò)定位問題研究D.中國科學技術(shù)大學, 2011. 窗體頂端窗體底端4 國海濤. 無線傳感網(wǎng)絡(luò)定位技

41、術(shù)研究與實現(xiàn)D.北京郵電大學,2014.5 汪煬;無線傳感器網(wǎng)絡(luò)定位技術(shù)研究D.中國科學技術(shù)大學;2007.6 馮硯毫. 無線傳感器網(wǎng)絡(luò)定位技術(shù)研究D.重慶大學,2011.7 Guan Weiguo,Deng Zhongliang,Ge Yuetao,et al.A location fingerprinting algorithm based on RSSI statistic parameters matching estimateJ.Key Engineering Materials,2011(6)： 480- 4818 Heurtefeux K，Valois F.Is RSSI a good choice for localization in wireless sensor networkC.2012 IEEE 26th International Conference on Advanced Information Networking and Applications.Fukuoka：s.n，2012：732- 7399 Diego Francisco La