無線傳感器網絡基于移動信標優化路徑的定位算法研究_畢業論文-資料下載頁

【導讀】無線傳感器網絡應用的大多數領域,如：目標監測與跟。蹤、路由位置信息的獲取等，都需要知道節點的位置信息。為此我們需要研究更。為有效的定位算法，降低定位成本，提高定位精度。文章在DV-Hop定位算法。中引入移動信標節點，并研究信標節點的動態選擇算法及移動路徑優化算法。信標的定位算法的定位機制，研究利用移動信標的信息來進行定位計算。又減少了定位算法的通信開銷，提高無線傳感器網絡節點定位效率。

　　

【正文】 理位置的路由 (georouting)， 而且相對定位不需要 信標節點 。 在某些無需網絡節點絕對位置的應用中，可以采用無 信標節點的 定位算法來實現 整個網絡的相對定位。典型的無 信標節 點 的 定位算法包含 SPA[30] 、 SDGPS[31] 、 AFL[32] 等定位算法。 SPA 算法選擇網絡中密度最大處的一組節點作為建立網絡全局坐標系統的參考點，并在其中選擇連通度最大的一個節點作為坐標系統的原 點。首先根據節點間的測距結果在各個節點上建立局部坐標系統，通過節點間的信息交換與協調，以參考點為基準通過坐標變換逐步建立全局坐標系統。 SPA 算法的主要缺點是網絡通信開銷太大。 SDGPSN 算法在 SPA 算法的基礎上，提出了基于聚類的定位思想。基本思想 :網絡部署完后，每個傳感器節點開始運行一個隨機的定時器，如果與鄰居節點相比，節點 i 的定時器最先到期且沒有收到任何鄰居節點的消息，則 i 升級為主節點，并向鄰居節點廣播此消息，所有接收到該消息的鄰居節點中止其定時器并成為該主節點的從節點。這些節點構成一個以主節點 i 為坐標 原點的節點域，并隨掃 A 擇兩個與 i 相鄰的從節點為輔助節點對，構建一個局部坐標系。節點域廣東工業大學碩士學位論文 10 內的所有其他從節點通過選擇適當的輔助節點對來計算其在此局部坐標系中的坐標。然后相鄰的節點域依靠兩個域的共同邊際節點的相關坐標信息，以主節點ID 較小的局部坐標系為參照，進行相鄰局部坐標系間的坐標轉換， 直至建立 一個全局坐標系。 SDGPSN 算法和 SPA 算法相比，通信開銷明顯 降低 ，這使得它更適于大規模無線傳感器網絡的部署。 AFL 算法是完全分布式的節點定位方法。利用 AMP 所有節點從隨機初始坐標分配開始，只利用局部距離估計和通過局部信 息交換收斂到一個與距離估計一致的坐標分配。在給定一個未知坐標的節點集合和一種節點可以估測它到其鄰居節點距離機制的條件下，通過局部節點間的通信決定每個節點的位置坐標。 基于信標節點的定位 算法依賴于某些已知坐標位置的節點。這種定位算法需要預先定位 信標節點 ，否則無法正常運行，另外為了減小定位誤差， 信標節點的數目還須足夠多。 基于信標節點的定位 算法的 一個 重要特征是定位精度取決于 信標 點密度 。 為了解決基于信標節點的定位算法對信標節點的密度的依賴，近年來許多學者進行了移動信標節點定位算法的研究，通過在引入移動信標節點在網絡中按預定軌跡漫游并廣播自己的位置分組在構成虛擬信標節點，可以大大減少信標節點的投入。因為信標節點造價往往比普通節點高，在許多固定的傳感器網絡中，定位成功后信標節點將轉為普通節點使用，極大的浪費了資源。所以基于移動信標節點的定位算法成為近年來研究的一個熱點。 本章 首先介紹無線傳感器網絡常用的定位方式及其實現，然后 介紹常用的 基于測距和無需測距的 定位算法，并根據這些算法的特點，分析其優缺點，為下一章提出新的 基于移動信標的 定位算法奠定了理論基礎。 無線傳感器網絡 常用的定位方式的實現 極大似然估計法 傳感器網絡移動節點定位系統中節點有可能和多于 3 個的不同 信標 相連。因此可以使用更多的節點以獲得冗余信息來計算未知節點的位置。 極大似然估計多邊測量 [33] 就采用了上面的方法， 已知 n 個節點的坐標分別為 (X1,Y1)， (X2,Y2)，(X3,Y3)， … .， (Xn ,Yn )，它們到未知節點 D 的距離分別為 dl， d2， d3， … .，dn，假設節點 D 的坐標為 (X， Y)。那么，存在下列公式： 第二章 傳感器網絡常用節點定位算法相關研究 11 ? ? ? ? 222 111 dYYXX ???? ? ? ? ? 222 222 dYYXX ???? ∶ ? ? ? ? 222 dnYYnXXn ???? () 最后，使用標準的最小均方差估計方法可以得到未知節點 D 的坐標。 三邊測量 定位 法 三邊測量法是通過 RSSI 值得出未知節點到 3 個 信標 的距離，通過這 3 個距離值計算出未知節點的位置。如下圖 21 所示，當節點 P1， P2， P3 未知節點P 發出的定位信號時，根據 RSSI 值，可以得到 P1 到 P， P2 到 P， P3 到 P 的距離 d1， d2， d3； 分別以 P1， P2， P3 為圓心， d1， d2， d3 為半徑作圓，通 過這 3 個圓相交區域定出未知節點的位置。 P 1P 2P 3P 圖 23 三邊測量法原理 Fig. 23 Trilateration Method Principle 但是在真實環境下三邊測量法存在巨大的缺陷，如圖 36 所示，實際上測量得到的 3 個距離 RP1， RP2， RP3存在著誤差，導致以 RP1， RP2， RP3為半 徑建立的3 個圓并不是相交于一點，而是相交于一個區域。這樣建立起來的等式方程組沒有解，根本無法實現對節點的定位。有些文章提出了以區域的質點作為節點的位置，這種方法也不好，節點定位的誤差會隨著相交區域的增大而大大地提高。 總的來說，針對節點的定位算法都是在理想的仿真環境下進行研究的 ，當節點處于存在干擾或者移動的情況下，這些算法或不能夠實現節點精確的定位，或算法的計算量太大 。 廣東工業大學碩士學位論文 12 三角測量定位法 三角測量法原理如圖 22 所示，已知 A、 B、 C 三個節點的坐標分別為(xa,ya),(xb,yb)， (xc,yc)， 節點 D 相對于節點 A、 B、 C 的角度分別為： ? ADB，? ADC， ? BDC，假設節點 D 的坐標為 (x， y)， D 為圖 22 中三個圓的交點。 圖 24 三角測量法示意圖 Fig. 24 Triangulation Method Principle 對于節點 A， C 和角 ? ADC，如果弧段 AC 在 ? ABC 內，那么能夠唯一確定一個圓，設圓心為 ? ?111 ,ooO x y ，半徑為 r1，那么 ? ?1 22A O C A D C??? ? ? ? ?，并存在下列公式： ? ? ? ?? ? ? ?? ? ? ?111122122122 22112 2 c oso a o ao b o ba c a cx x y y rx x y y rx x y y r r ?? ? ? ? ????? ? ? ???? ? ? ? ? ??? () 由式 ()能夠確定圓心 O1 點的坐標和半徑 r1。同理對 A， B， ? ADB 和 B，C， ? BDC 分別確定相應的圓心 ? ?222 ,ooO x y 、半徑 r圓心 ? ?333 ,ooO x y 和半徑 r3。最后根據已知的 r1， ? ?11,ooxy ， r2， ? ?22,ooxy ， r3， ? ?33,ooxy ，采用三邊測量法確定 D 點坐標。 第二章 傳感器網絡常用節點定位算法相關研究 13 常用的節點定位 算法 常用的 Rangebase 節點定位算法 根據定位過程中是否測量實際節點間的距離，定位算法可分為：基于距離(RangeBased)的定位算法和距離無關 (RangeFree)的定位算法 [34] 。前者需要測量相鄰節點間的絕對距離或方位，然后利用該實際距離來確定未知目標節點位置；后者則僅利用節點間距離關聯關系計算目標節點位置 [35] 。 基于信號強度（ RSSI）定位 RSSI(Received Signal Strength Indicator)是接收到的信號強度指示器，是一種利用信號衰減推測距離的測距技術 [36]。 目前 很多定位算法都是利用 RSSI 技術實現的。目前， WSN 網絡中無線通信芯片主要有兩種： CC1000 和 CC2420。 CC1000的工作頻帶為 315MHz,868MHz,915MHz，數據傳送速率可達 ，適用于跳頻協議。 CC2420 工作頻帶在 ，采用的是 OQPSK 調制方式，數據速率在 250kbit/s，具有較高的抗干擾能力。對于 CC1000 通信芯片， RSSI值是一個 10 位的寄存器值，而對于 CC2420，該值卻是一個 8 位的寄存器值。它是通過 A/D 轉換器轉換而來的，芯片不同， RSSI 的轉換方式也是不同的。若芯片是 CC1000： B A TR S SI VVR S S I /)1 0 2 4*(? （ ） ][ d B mVP R S SI ??? （ ） ][0 d B mPPP c ur r e n t?? （ ） B a tc u r r e n t VPPR S S I /1024*)())(( 0 ???? （ ） 其中， RSSI 是寄存器值，也就是節點接收到的信號強度值， VRSSI是 A/D 轉換前的 RSSI 電壓值，單位為 (V)； Vbat 為電源電壓，該值為一個常數值 3V； Pcurrent是當前節點的發射功率，單位為 dBm； P0 為當節點與源節點足夠遠時接收到的功率值，一般來說 P0取 80dBm； P 為功率衰減值。（ ）式是由（ ），（ ），（ ）聯合而得的，表明在當前發射功率下，發送到最遠的 距離處，接收到的最大 RSSI 值，若超過該值的一定范圍，認為節點間通信不合理，丟棄該數據包。若芯片為 CC2420： ][2 5 6_ d B mR S S IV A LR S S I ?? （ ） 廣東工業大學碩士學位論文 14 ][__ d B mO F F S E TR S S IV A LR S S IP ?? （ ） 其中， RSSI 是一個 8 位的寄存器值； RSSI_VAL 為轉換前 RSSI 功率值，單位為 dBm， RSSI_OFFSET 是一個常數，約為 45dBm。本文采用的射頻芯片是CC2420，它相對于 CC1000，使用的范圍更廣。同時為了更好的利用 RSSI 值估計 節點與鄰節點之間的距離，需要建立一個 RSSI 模型。最常用的 RSSI 有三種：最優模型、線性模型和理論模型。最優模型如式 ()，根據給定 RSSI 的距離值r，對具有相同 RSSI 測量值的觀測數據來計算實際距離的平均值，這個模型可以很好地從收集到的數據中統計出有效的距離估計值。 最簡單的 RSSI 模型就是線性模型，它使用一對參數 a 和 ｂ 估計節點之間的距離，如式 ()。其中 r 是 RSSI 測距值。因為信號強度和距離之間并不是簡單的線性關系，因此，線性模型和理論模型之間還有一定的誤差。 RSSI 的理論模型是根據信號強度 隨著距離的變化成對數衰減的原理，如式（ ） ,其中 r0 是 1m距離處對應的 RSSI 測距值， a 是信號的衰減率，理論值為 2。 ]|[)( rRdErf ?? （ ） brad ?? *~ （ ） arrd /)0( ?? （ ） 大多數情況下， RSSI 的測距采用自由空間模型，它是理論模型的一種。因為 RSSI 在一個真實環境下的信號隨著距離的增大而減少。收發器之間各種各樣的阻礙影響能量的損失，從而直接影響接收器 接收 信號的對數分布 [37]。所以距離d 與 接收 到的信號強度的關系可以表示為： ? ? ? ? )(l o g10 0100 ddndPdP r ?? ?? （ ） 其中 P(d0)為參考距離 d0 接收到的信號。對于所有 d0=1 米的室內環境下以及距離的信號可以由自由空間路徑 損耗方程得到，路徑的損耗指數 n 由環境變量和周圍的結果決定。根據高斯分布功率表達式，得到的 接收 功率為： ? ? ? ? dBr ddndPdP ???? ?? )(l o g10 0100 （ ） 其中 ε dB 為零均值及以δ 2, N(0,δ 2)變化的高斯分布隨機變量。基于這個模型，距離估算為： 第二章 傳感器網絡常用節點定位算法相關研究 15n dPdrpdd 10 ))0()((0~ 10 ??? （ ） 總的來說，僅依靠 RSSI 方法的定位系統，應用在實時系統定位時非常方便。但由于受到地板、墻壁和人體等各種物體等障礙物的阻攔，電磁波會存 在著反射及衍射，使得 RSSI 值隨機變化較大，因此無法準確判斷某一個距離對應的 RSSI值。理論信號強度與實際信號強度曲線對比如下圖 23 所示： 1 0 09 59 08 58 07 57 06 56 05 55 00 2 0 4 0 6 0 8 0 1 0 0 1 2 0 1 4 0 1 6 0 1 8 0 2 0 0實 際 環