_無線傳感器網(wǎng)絡(luò)定位算法

1、無線傳感網(wǎng)絡(luò)定位算法目錄、常用定位技術(shù)1.1 GPS 與 A-GPS 定位1.2 基站定位（ cell ID 定位）1.3 Wifi AP 定位1.4 FRID 、二維碼定位 二、定位算法研究的目的和意義三、 WSN 定位算法分析3.1基于錨節(jié)點的定位算法3.1.1 距離相關(guān)定位算法3.1.2 距離無關(guān)定位算法3.2基于移動錨節(jié)點的定位算法四、總結(jié)3.2.1 基于移動錨節(jié)點的距離相關(guān)定位算法3.2.2 基于移動錨節(jié)點的距離無關(guān)定位算法附：組員及分工情況錯誤 ! 未定義書簽。1113、常用定位技術(shù)1.1 GPS 與 A-GPS 定位常見的GPS定位的原理可以簡單這樣理解：由24顆工作衛(wèi)星組成，使

2、得在 全球任何地方、任何時間都可觀測到 4顆以上的衛(wèi)星，測量出已知位置的衛(wèi)星到用戶接收機(jī)之間的距離，然后綜合多顆衛(wèi)星的數(shù)據(jù)就可知道接收機(jī)的具體位置。在整個天空范圍內(nèi)尋找衛(wèi)星是很低效的， 因此通過 GPS 進(jìn)行定位時， 第一次啟 動可能需要數(shù)分鐘的時間。 這也是為啥我們在使用地圖的時候經(jīng)常會出現(xiàn)先出現(xiàn) 一個大的圈， 之后才會精確到某一個點的原因。 不過，如果我們在進(jìn)行定位之前 能夠事先知道我們的粗略位置，查找衛(wèi)星的速度就可以大大縮短。GPS系統(tǒng)使用的偽碼一共有兩種，分別是民用的C/A碼和軍用的P（丫）碼。民用精度約為10米，軍用精度約為1米。GPS的優(yōu)點在于無輻射，但是穿透力 很弱，無法穿透鋼筋

3、水泥。 通常要在室外看得到天的狀態(tài)下才行。 信號被遮擋或 者削減時， GPS 定位會出現(xiàn)漂移，在室內(nèi)或者較為封閉的空間無法使用。正是由于 GPS 的這種缺點，所以經(jīng)常需要輔助定位系統(tǒng)幫助完成定位，就 是我們說的 A-GPS。例如iPhone就使用了 A GPS,即基站或 WiFi AP初步定位后，根據(jù)機(jī)器內(nèi)存儲的 GPS 衛(wèi)星表來快速尋星， 然后進(jìn)行 GPS 定位。例如在民用的車載 導(dǎo)航設(shè)備領(lǐng)域， 目前比較成熟的是 GPS + 加速度傳感器補(bǔ)正算法定位。 在日本 的車載導(dǎo)航市場是由 Sony 的便攜式車載導(dǎo)航系統(tǒng) Nav-U1 首先引入量產(chǎn)。例 如在增加了三軸陀螺儀的 iphone4 里可以利

4、用三軸陀螺儀來輔助完成定位，具 體可以參見這篇文章的介紹，不過三軸陀螺儀定位的誤差會隨著時間逐漸積累。1.2 基站定位（ cell ID 定位）小區(qū)識別碼（ Cell ID ）通過識別網(wǎng)絡(luò)中哪一個小區(qū)傳輸用戶呼叫并將該信息翻譯成緯度和經(jīng)度來確定用戶位置。 Cell ID 實現(xiàn)定位的基本原理：即無線網(wǎng)絡(luò)上報終端所處的小區(qū)號（根據(jù)服務(wù)的基站來估計），位置業(yè)務(wù)平臺把小區(qū)號翻譯成經(jīng)緯度坐標(biāo)?；径ㄎ涣鞒蹋涸O(shè)備先從基站獲得當(dāng)前位置（ Cell ID ）第一次定位）設(shè)備通過網(wǎng)絡(luò)將位置傳送給A gps位置服務(wù)器Agps 服務(wù)器根據(jù)位置查詢區(qū)域內(nèi)當(dāng)前可用的衛(wèi)星信息，并返回設(shè)備 設(shè)備中的GPS接收器根據(jù)可用衛(wèi)星

5、，快速查找可用的 GPS衛(wèi)星，并返回GPS 定位信息。1.3 Wifi AP 定位設(shè)備只要偵聽一下附近都有哪些熱點，檢測一下每個熱點的信號強(qiáng)弱，然后 把這些信息發(fā)送給網(wǎng)絡(luò)上的服務(wù)端。 服務(wù)器根據(jù)這些信息， 查詢每個熱點在數(shù)據(jù) 庫里記錄的坐標(biāo)， 然后進(jìn)行運(yùn)算， 就能知道客戶端的具體位置了。 一次成功的定 位需要兩個先決條件：客戶端能上網(wǎng) ，偵聽到的熱點的坐標(biāo)在數(shù)據(jù)庫里有1.4 FRID 、二維碼定位通過設(shè)置一定數(shù)量的讀卡器和架設(shè)天線，根據(jù)讀卡器接收信號的強(qiáng)弱、到達(dá) 時間、角度來定位。 目前無法做到精準(zhǔn)定位， 布設(shè)讀卡器和天線需要有大量的工 程實踐經(jīng)驗難度大，另外從成本上來講 WIFI 經(jīng)濟(jì)實用些

6、。二、定位算法研究的目的和意義定位是大多數(shù)應(yīng)用的基礎(chǔ)。 由于節(jié)點工作區(qū)域往往是人類不適合進(jìn)入的區(qū)域， 或者是敵對區(qū)域， 甚至有時傳感器節(jié)點需要通過飛行器拋撒， 因此節(jié)點的位置通 常是隨機(jī)并且未知的。 而傳感器節(jié)點自身的正確定位是提供監(jiān)測事件位置信息的 前提，沒有位置信息的監(jiān)測消息往往是沒有意義的。 傳感器節(jié)點必須明確自身位 置才能詳細(xì)說明“在什么位置或區(qū)域發(fā)生了特定事件 " ，除能報告事件的發(fā)生地 外，還能進(jìn)行目標(biāo)跟蹤，實時監(jiān)視目標(biāo)路線，預(yù)測目標(biāo)軌跡等；實現(xiàn)對外部目標(biāo) 的定位和追蹤。另一方面，了解傳感器節(jié)點位置信息還可以協(xié)助路由，提高路由效率，為網(wǎng) 絡(luò)提供命名空間， 向部署者報告網(wǎng)絡(luò)

7、的覆蓋質(zhì)量， 實現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡以及網(wǎng)絡(luò) 拓?fù)涞淖耘渲玫染W(wǎng)絡(luò)管理。 因此，確定事件發(fā)生的位置或獲取消息的節(jié)點位置尤 為重要，對傳感器網(wǎng)絡(luò)應(yīng)用的有效性起著關(guān)鍵的作用。而全球定位系統(tǒng)是目前使用最廣泛最成熟的定位系統(tǒng)， 通過衛(wèi)星的授時和測 距對用戶節(jié)點進(jìn)行定位，具有精度高、實時性好、抗干擾能力強(qiáng)等優(yōu)點，但是定 位適應(yīng)于無遮擋的室外環(huán)境， 用戶節(jié)點通常能耗高且體積大， 成本也比較高， 需 要固定的基礎(chǔ)設(shè)施等。人工部署和為所有網(wǎng)絡(luò)節(jié)點安裝 GPS 接收器都會受到成 本、功耗、擴(kuò)展性等問題的限制，甚至在某些場合可能根本無法實現(xiàn)，這使得它 不適用于低成本自組織的傳感器網(wǎng)絡(luò)，因此必須采用一定的機(jī)制與算法實現(xiàn)W

8、SN 的自身定位。隨著計算機(jī)技術(shù)、 微電子技術(shù)和通信技術(shù)的進(jìn)步， 傳感器已朝著集成化、 微 型化、智能化和低能耗的方向快速發(fā)展，使其能夠在較小體積內(nèi)集成信息采集、數(shù)據(jù)處理和信息的傳輸?shù)榷喾N功能，這為無線傳感網(wǎng)（Wireless SensorNetworks WSN） 的產(chǎn)生和發(fā)展奠定了基礎(chǔ)。無線傳感網(wǎng)是由部署在監(jiān)測區(qū)域內(nèi)大量廉價微型的具有有限數(shù)據(jù)處理能力和裝備有低能耗無線信號收發(fā)器的傳感器節(jié)點通過無線通信方式形成的一個多跳自組織網(wǎng)絡(luò)，其目的是利用網(wǎng)絡(luò)節(jié)點協(xié)作地感知和采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感興趣的信息，并發(fā)送給觀察者。 它通過大量隨機(jī)部署在監(jiān)測區(qū)域的傳感器節(jié)點來監(jiān)測和感知周圍的物理環(huán)境。無線傳感網(wǎng)具

9、有布線成本低、監(jiān)測精度高、系統(tǒng)容錯性好、可遠(yuǎn)程監(jiān)控以及便于診斷與維護(hù)等眾多的優(yōu)點， 它的產(chǎn)生解決了傳統(tǒng)傳感器網(wǎng)絡(luò)在應(yīng)用中遇到的安裝、維護(hù)等方面的種種困難。其在軍事、工業(yè)、醫(yī)療、交通、環(huán)保等領(lǐng)域有著廣闊的應(yīng)用前景。 如果說互聯(lián)網(wǎng)改變了人與人之間的信息交流方式，那么，無線傳感網(wǎng)的產(chǎn)生將改變?nèi)伺c自然界的交互方式。三、 WSN 定位算法分析3.1 基于錨節(jié)點的定位算法3.1.1 距離相關(guān)定位算法距離相關(guān)定位算法一般利用一定的測距技術(shù)得到節(jié)點間距離，再利用三邊測量法、三角測量法或極大似然估計法計算出未知節(jié)點的位置。常用的測距技術(shù)包括接收信號強(qiáng)度（RSSI）技術(shù)、信號傳輸時間（TOA） 技術(shù)、信號到達(dá)時間

10、差（TDOA）技術(shù)和信號到達(dá)角度（AOA）技術(shù)。它們需要一些昂貴的輔助測量設(shè)備來測量節(jié)點間的距離，且受環(huán)境影響較大。如RSSI產(chǎn)生的測量誤差較大；TDOA需要節(jié)點具有超聲波發(fā)送與接收功能；AOA容易受到環(huán)境影響, 功耗較大等。但距離相關(guān)定位算法的一個突出優(yōu)點是定位精度高，因此對定位精 度要求比較高的場合都用基于測距的定位算法實現(xiàn)定位。典型算法：接收信號強(qiáng)度指示法（RSSI）通過信號在傳播中的衰減來估計節(jié)點之間的距離。假設(shè)已知發(fā)射功率，在接收節(jié)點測量接收功率，計算傳播損耗，使用理論或經(jīng)驗的信號傳播模型將傳播損耗轉(zhuǎn)化為距離。在自由空間中，距發(fā)射機(jī)d處的天線接收到的信號強(qiáng)度由下面的公式給出：CC _

11、 ?-? =（4?2 ?2?其中，？?為發(fā)射機(jī)功率，?是距離d處的接收功率，？猬？?分別是發(fā)射天 線和接收天線的增益，d是距離，單位為米（m），L為與傳播無關(guān)的系統(tǒng)損耗因 子，入是波長，單位為米（m）。由公式可知，在自由空間中，接收機(jī)功率隨發(fā)射 機(jī)與接收機(jī)距離的平方衰減。這樣，通過測量接收信號的強(qiáng)度，再利用上述公式 即可計算出收發(fā)節(jié)點間的大概距離。3.1.2距離無關(guān)定位算法利用節(jié)點間的連通情況來估測自己的位置。 其中一部分距離無關(guān)算法采用集 中式計算模式，用一些優(yōu)化方法來提高定位精度，但是集中計算方式需要網(wǎng)絡(luò)中 有計算中心支持，且計算中心附近節(jié)點通信量大，很快能量耗盡，使整個網(wǎng)絡(luò)不 可用。絕大

12、多數(shù)距離無關(guān)定位算法采取分布式計算模式， 可擴(kuò)展性好；由于位置 估測基于節(jié)點間的連通情況，計算簡單而且容易實現(xiàn)；計算在節(jié)點本地進(jìn)行，通 信量小。因為基于估測距離，距離無關(guān)算法定位精度不如距離相關(guān)算法好。典型算法：DV-h op算法距離向量一跳段（distanee vector-hop , DV-Hop）定位機(jī)制非常類似于傳統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制，DV-Hop算法的定位過程主要分為 3個階段: 1）計算未知節(jié)點與每個信標(biāo)節(jié)點的最小跳數(shù)，錨節(jié)點向鄰居節(jié)點廣播自身位置信息的分組，其中，包括跳數(shù)字段，初始化為接收節(jié)點記錄具有到每個錨節(jié)點的最小跳數(shù)，忽略來自同一個錨節(jié)點的較大 跳數(shù)的分組。然后，將跳

13、數(shù)值加 1，并轉(zhuǎn)發(fā)給鄰居節(jié)點。通過這種方法，網(wǎng)絡(luò)中的所有節(jié)點能夠記錄下到每個錨節(jié)點的最小跳數(shù)。2）計算未知節(jié)點與錨節(jié)點的實際跳段距離每個錨節(jié)點根據(jù)第一階段中記錄的其它錨節(jié)點的位置信息和相距跳數(shù)，并利用下式估算平均每跳的實際距離IM?7 ?2 + （?務(wù)?）2? ?=式中（?？?，（? ?為錨節(jié)點i, j的坐標(biāo)；？?為錨節(jié)點i與j（ i工j）之間的跳段數(shù)，然后，錨節(jié)點將計算的平均每跳距用帶有生存期字段的分組廣播至 網(wǎng)絡(luò)中，未知節(jié)點僅記錄接收到的第一個平均每跳距離， 并轉(zhuǎn)發(fā)給鄰居節(jié)點。這個策略確保了絕大多數(shù)節(jié)點從最近的錨節(jié)點接收平均每跳距離值。未知節(jié)點接收 到平均每跳距離后，根據(jù)記錄的跳數(shù)，計算到

14、每個錨節(jié)點的跳段距離。3）利用三邊測量法計算自身位置未知節(jié)點利用第二階段中記錄的到各個錨節(jié)點的跳段距離，利用三邊測量法計算自身位置。已知A,B,C 3個節(jié)點的坐標(biāo)分別為（?, ?） , （?爲(wèi)?） ,（ ?假設(shè)節(jié)點D的坐標(biāo)?）,以及它們到未知節(jié)點D的距離分別為？?,為（X, y）。那么，有下列公式：v(? ?)2 + (? ?)2v(? ?)2 + (? ?科2 = ?v(? ?)2 + (? ?5)2 = ?由式（1）、式、式可得未知節(jié)點D的坐標(biāo)為:2（© -攵2（兒-兒F20& - 億）2（7i -兒）丿3.2基于移動錨節(jié)點的定位算法2 . . 3. 2 .2 _r- -

15、一 -a2.22. J 2,2一九+幾一兒+心一%丿-1/22 ,32 , n 2 r兀一兀+兒一兒+N芒一£2目前移動錨節(jié)點定位算法一般包括以下兩類：第一類是同時采用移動錨節(jié)點和靜態(tài)錨節(jié)點協(xié)作來完成未知節(jié)點的定位過程； 另一類則是只通過移動錨節(jié)點來獲得未知節(jié)點的坐標(biāo)。利用移動錨節(jié)點替代傳統(tǒng)的靜態(tài)錨節(jié)點不但降低了無線傳感器網(wǎng)絡(luò)定位技術(shù)實現(xiàn)的成本，而且提高了定位精度和定位覆蓋率。3.2.1 基于移動錨節(jié)點的距離相關(guān)定位算法基于測距的移動錨節(jié)點發(fā)送的信標(biāo)信號中包含距離信息， 然后未知節(jié)點通過 接受到的距離信息通過特定的計算方法實現(xiàn)定位。典型算法： MBAL 算法MBAL(mobile b

16、eacon assisted localization scheme) 定位方法是典型的將移動錨節(jié)點定位算法與靜態(tài)錨節(jié)點定位算法相結(jié)合的一種方法， 移動錨節(jié)點在移動的同時更新其坐標(biāo)并周期的廣播自身的位置信息。未知節(jié)點通過 RSSI 測距方法獲得與錨節(jié)點之間的距離，當(dāng)接收到 3 個以上不共線的虛擬錨節(jié)點信息包 時，就可以使用三邊測量法來計算自身的位置。 未知節(jié)點定位完成以后， 就轉(zhuǎn)換 成為其他未知節(jié)點提供坐標(biāo)信息的靜態(tài)錨節(jié)點。 MBAL 算法假設(shè)錨節(jié)點始終能 知道自身的位置，未知節(jié)點可以利用 3 個及更多的來自移動錨節(jié)點或靜態(tài)錨節(jié) 點的數(shù)據(jù)包計算出自身的位置。 MBAL 定位可分為以下 3 個階

17、段： 錨節(jié)點初始移動階段 ：為了保證在傳感器網(wǎng)絡(luò)中存在交叉區(qū)域， 將移動錨節(jié)點的 初始位置設(shè)置在網(wǎng)絡(luò)的中心附近。如圖 3.16 所示，交叉區(qū)域是一個邊長為 R的等邊三角形。錨節(jié)點運(yùn)動結(jié)束后，節(jié)點移動的距離長度為2R，參考節(jié)點的數(shù)目是 3 個。經(jīng)過這個步驟，處于交叉區(qū)域的未知節(jié)點能夠計算出自身位置，從 而轉(zhuǎn)化為廣播自身位置數(shù)據(jù)包的靜態(tài)錨節(jié)點，進(jìn)行遞增式定位。錨節(jié)點初始運(yùn)動路徑(The initial path of a mobile beacon )未知節(jié)點定位階段：靜態(tài)參考節(jié)點為其他未知節(jié)點提供包括自身位置的數(shù)據(jù)包, 使更多的節(jié)點被定位，從而遞歸的產(chǎn)生更多的靜態(tài)參考節(jié)點。 三邊測量法至少需 要

18、3個錨節(jié)點的位置信息，但 MBAL使用距離檢查技術(shù)（The range check technique ）來計算接收到兩個數(shù)據(jù)包的節(jié)點位置。如下圖所示，一個未知節(jié)點 接收到來自參考節(jié)點 A和B的兩個數(shù)據(jù)包，估計自身到 A和B的距離，從而可以得到兩個可能的位置 1P和2P。圖中灰色點是參考節(jié)點 A和B的鄰居節(jié)點，也是未知節(jié)點的兩跳節(jié)點。這個未知節(jié)點只有兩個鄰居節(jié)點， 不能成為 兩跳節(jié)點的鄰居節(jié)點，而其中一個可能的位置2P是在節(jié)點C的范圍內(nèi)被定位。因此，1P是未知節(jié)點唯一的位置。參海節(jié)點節(jié)點可能ea距離檢查技術(shù)(The range check technique )錨節(jié)點移動路徑?jīng)Q策階段 ：經(jīng)過前

19、兩個步驟之后， 有些未知節(jié)點接收到的位置信 息仍然少于 3 個，這些節(jié)點被稱為請求節(jié)點，向移動錨節(jié)點請求更多的位置信 息。根據(jù)請求節(jié)點已接收到的數(shù)據(jù)包個數(shù)，可將這些節(jié)點分為 0- 型（已接收到 參考節(jié)點信息的個數(shù)為 0）、1- 型（已接收到參考節(jié)點信息的個數(shù)為 1）和 2-型（已接收到參考節(jié)點信息的個數(shù)為 2）。根據(jù)不同類型未知節(jié)點的請求，移動錨節(jié)點選擇合適的路徑來完成整個網(wǎng)絡(luò)的定位。 MBAL 算法提出的路徑規(guī)劃方 法比隨機(jī)路徑規(guī)劃的定位效果好， 但它在盡可能減小錨節(jié)點移動路徑的同時， 也 降低了定位的精度。對于小規(guī)模傳感器網(wǎng)絡(luò)， MBAL 算法通過上述的路徑規(guī)劃方法縮短了移動 錨節(jié)點運(yùn)動的

20、路徑， 減小了錨節(jié)點能耗； 采用遞增式的定位算法， 降低了定位實 現(xiàn)的成本； 使用距離檢查技術(shù)， 減少網(wǎng)絡(luò)中不能定位的節(jié)點。 但對于大規(guī)模的網(wǎng) 絡(luò)， MBAL 算法會產(chǎn)生嚴(yán)重的累積誤差且全網(wǎng)定位的執(zhí)行周期較長；網(wǎng)絡(luò)中節(jié) 點分布均勻且密度較大時， 采用遞增式定位能夠滿足所有未知節(jié)點都被定位的需 求，不需要再使用距離檢查技術(shù)。因此， MBAL 算法不適用于大規(guī)模無線傳感 器網(wǎng)絡(luò)定位。3.2.2 基于移動錨節(jié)點的距離無關(guān)定位算法距離無關(guān)的移動錨節(jié)點定位算法，無需測距。典型算法： LMAP 算法LMAP 算法是根據(jù)“圓的任何一條弦的垂直平分線都經(jīng)過該圓的圓心”這 個理論提出的， 它是一種非基于測距的算

21、法， 在定位的過程中不需要任何距離或 者角度的信息。 LMAP 定位原理如圖 3.18 所示，圓心是未知節(jié)點所在的位置，圓的半徑是未知節(jié)點能夠與錨節(jié)點之間進(jìn)行通信的最大距離，移動錨節(jié)點經(jīng)過弦 的中點。未知節(jié)點接收到 3個虛擬參考節(jié)點的信息后，就在以未知節(jié)點為圓心的圓中產(chǎn)生了兩條弦。如上圖所示，? ? ?身分別表示3個虛擬錨節(jié)點，假設(shè)它們的坐標(biāo)為（?），（ ? ?和（？?，?），未知節(jié)點S的坐標(biāo)設(shè)為（? ? 。?和?是3個錨節(jié)點產(chǎn)生的兩條弦，？?和?分別是兩條弦的垂直平分線，通過數(shù)學(xué)運(yùn)算，可以得到以下的方程組:?：?+?+?= ?= ?其中，?= ?- ?，?= ?- ?= ?- ?，?= ?- ?+?2?+?2 ?+?>?=(?- ?r+( ?- ? F?+?>?*?+?=(?>?