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

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

2、得在 全球任何地方、任何時間都可觀測到 4顆以上的衛(wèi)星，測量出已知位置的衛(wèi)星到用戶接收機之間的距離，然后綜合多顆衛(wèi)星的數(shù)據(jù)就可知道接收機的具體位置。在整個天空范圍內(nèi)尋找衛(wèi)星是很低效的， 因此通過 GPS 進行定位時， 第一次啟 動可能需要數(shù)分鐘的時間。 這也是為啥我們在使用地圖的時候經(jīng)常會出現(xiàn)先出現(xià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ù)機器內(nèi)存儲的 GPS 衛(wèi)星表來快速尋星， 然后進行 GPS 定位。例如在民用的車載 導航設備領域， 目前比較成熟的是 GPS + 加速度傳感器補正算法定位。 在日本 的車載導航市場是由 Sony 的便攜式車載導航系統(tǒng) Nav-U1 首先引入量產(chǎn)。例 如在增加了三軸陀螺儀的 iphone4 里可以利

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

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

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

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

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

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

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

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

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

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

14、每個錨節(jié)點的跳段距離。3）利用三邊測量法計算自身位置未知節(jié)點利用第二階段中記錄的到各個錨節(jié)點的跳段距離，利用三邊測量法計算自身位置。已知A,B,C 3個節(jié)點的坐標分別為（?, ?） , （?爲?） ,（ ?假設節(jié)點D的坐標?）,以及它們到未知節(jié)點D的距離分別為？?,為（X, y）。那么，有下列公式：v(? ?)2 + (? ?)2v(? ?)2 + (? ?科2 = ?v(? ?)2 + (? ?5)2 = ?由式（1）、式、式可得未知節(jié)點D的坐標為: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é)點的坐標。利用移動錨節(jié)點替代傳統(tǒng)的靜態(tài)錨節(jié)點不但降低了無線傳感器網(wǎng)絡定位技術實現(xiàn)的成本，而且提高了定位精度和定位覆蓋率。3.2.1 基于移動錨節(jié)點的距離相關定位算法基于測距的移動錨節(jié)點發(fā)送的信標信號中包含距離信息， 然后未知節(jié)點通過 接受到的距離信息通過特定的計算方法實現(xiàn)定位。典型算法： MBAL 算法MBAL(mobile b

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

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

18、3個錨節(jié)點的位置信息，但 MBAL使用距離檢查技術（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距離檢查技術(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)絡的定位。 MBAL 算法提出的路徑規(guī)劃方 法比隨機路徑規(guī)劃的定位效果好， 但它在盡可能減小錨節(jié)點移動路徑的同時， 也 降低了定位的精度。對于小規(guī)模傳感器網(wǎng)絡， MBAL 算法通過上述的路徑規(guī)劃方法縮短了移動 錨節(jié)點運動的

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

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