基于Amorphous的無線傳感器網(wǎng)絡定位算法研究*

安文秀，趙菊敏，李燈熬

(太原理工大學信息工程學院，山西太原030024)

0 引言

在無線傳感器網(wǎng)絡［1］(wireless sensor networks，WSNs)中，節(jié)點的位置信息是網(wǎng)絡消息中不可缺少的部分，是目標檢測與跟蹤、事件地理位置報告等功能的前提。針對傳感器節(jié)點能源有限、通信易受環(huán)境影響、數(shù)量龐大且隨機散播等特點，高效、精確的定位算法至關重要。

目前，無線傳感器網(wǎng)絡定位算法［2］根據(jù)是否需要測距分為兩類:基于測距和非測距?；跍y距的算法包括對節(jié)點之間角度與距離的測量，主要有RSSI，TDoA，AoA等，測得距離或角度，再通過三邊測量法或三角測量法得到未知節(jié)點坐標。基于非測距的算法包括質心算法、DV-Hop［3］，Amorphous等，利用構建多邊形求質心或者根據(jù)節(jié)點跳數(shù)與跳距得到未知節(jié)點坐標。非測距的算法定位性能通常不如基于測距定位，但非測距定位不需要硬件支持，實現(xiàn)成本較低，功耗較低，也可以滿足許多應用需要［4］。其中，Amorphous算法由DV-Hop算法改進得來，在DV-Hop算法中，未知節(jié)點通過計算與信標節(jié)點之間最小跳數(shù)，估算平均每跳距離，用最小跳數(shù)乘以平均每跳距離得到兩點距離，再利用三邊測量法或最大似然估計法對未知節(jié)點定位。有很多專家對DV-Hop算法提出改進，對于Amorphous定位算法提出的改進算法較少，由于Amorphous定位算法簡單，無需測距，容易實現(xiàn)，但是完全依靠網(wǎng)絡的連通性，節(jié)點部署密度越高，分布越均勻，則定位越精確;反之，則誤差較大。針對該算法的特點，一些專家提出了改進方法，都是從誤差修正入手。本文將從兩方面分別進行算法修正:1)對未知節(jié)點與信標節(jié)點之間跳數(shù)進行修正;2)利用質心算法計算定位結果，并且將已獲得位置信息的未知節(jié)點轉化為信標節(jié)點，對其他未知節(jié)點定位。

1 Amorphous定位算法模型

Amorphous定位算法［5］可以分為3個階段:

1)獲得未知節(jié)點計算與每個信標節(jié)點之間的最小跳數(shù)。信標節(jié)點向鄰居節(jié)點廣播數(shù)據(jù)包，包括ID號、自身位置和跳數(shù)(初始化為0)。收到包的節(jié)點記錄每個信標節(jié)點的信息，將跳數(shù)加1，并且轉發(fā)給鄰居節(jié)點，多次收到同一個信標節(jié)點的信息時，丟棄較大跳數(shù)的數(shù)據(jù)包。通過該方法，全網(wǎng)節(jié)點均獲得了距離每個信標節(jié)點的最小跳數(shù)hopsi。

2)假設網(wǎng)絡中節(jié)點的通信半徑相同，設為R，平均每跳距離為節(jié)點的通信半徑，未知節(jié)點計算到每個信標節(jié)點的跳段距離di=hopsi×R。

3)利用三邊測量法［6］或極大似然算法，計算未知節(jié)點的位置。

設3個信標節(jié)點 A，B，C 的坐標分別為(x1，y1)，(x2，y2)和(x3，y3)，它們與未知節(jié)點 D(x，y)的距離分別為 d1，d2和d3，則通過距離公式可得

寫成矩陣形式AX=b，即

三邊測量法估算D坐標極大似然估計法估算D坐標

2 改進算法模型

2.1 跳數(shù)修正

在經(jīng)典Amorphous定位算法中，以節(jié)點通信半徑為單跳距離計算，造成了很大的誤差，如圖1所示，節(jié)點A，B都在節(jié)點O的通信半徑R之內，因此，O到A，B都為一跳，然而，|OA|與|OB|相差較大，在實際的網(wǎng)絡中也普遍存在該問題，所以，得到的兩節(jié)點之間的跳數(shù)并不能確切反映兩點間的距離，因此，本論文針對經(jīng)典算法中的跳數(shù)問題提出改進方法。

由于在傳感器網(wǎng)絡中，節(jié)點通常采用無線電或超聲波的方式進行數(shù)據(jù)包的廣播，因此，在傳感器節(jié)點接收模塊中，加入信號強度分析模塊，設定一個功率閾值M，M為傳播距離為R/2時的信號強度，則當接收到節(jié)點發(fā)來的數(shù)據(jù)包時，若接收信號強度大于設定的閾值M，則定為1跳，若強度值小于M，則定為0.5跳，跳數(shù)相繼累加得到2個節(jié)點的跳數(shù)hops。

圖1 跳數(shù)修正原理圖Fig 1 Principle diagram of hops correction

2.2 質心算法加權

計算節(jié)點間距離用hops×R。當未知節(jié)點計算得到與最近的3個信標節(jié)點距離后，其他數(shù)據(jù)包信息可以忽略。設離未知節(jié)點O(x，y)最近的3個信標節(jié)點為 P(x1，y1)，Q(x2，y2)，R(x3，y3)，且與 P，Q，R 的跳數(shù)分別為 hops1，hops2，hops3，若節(jié)點分布均勻，采用傳統(tǒng)質心算法可以得到較為精確的定位結果。

在網(wǎng)絡中通常節(jié)點隨機分布，則應對質心算法進行改進，對3個信標節(jié)點進行加權，如圖2，P與O較遠，應賦較小的權值Q與O距離最近，則應賦較大的權值，這樣得到如下計算方法

圖2 加權質心算法原理圖Fig 2 Principle diagram of weighted centroid algorithm

經(jīng)過加權后的計算方法，為3個信標節(jié)點分別賦予不同大小的權值，區(qū)分了其在定位中的貢獻度，可以獲得較為精確的定位坐標。

3 仿真與結果分析

通過Matlab仿真軟件驗證提出算法的可行性。假設在100 m×100 m區(qū)域中規(guī)則撒布100個點作為無線傳感器網(wǎng)絡節(jié)點，其中，節(jié)點坐標為隨意產(chǎn)生。對經(jīng)典Amorphous算法與改進后算法在信標節(jié)點分布密度不同情況下，不同通信半徑的定位精度作比較。設未知節(jié)點真實位置是Xi，定位得到的位置為Xi，則定義未知節(jié)點平均誤差為 e=/KN(其中，N 為實驗次數(shù)，N=50，K 為未知節(jié)點個數(shù))，對通信半徑進行歸一化的平均誤差定義為e=e/R.

3.1 信標節(jié)點數(shù)量對定位誤差影響的對比

從圖3(a)～圖3(c)仿真結果可以看出:在信標節(jié)點數(shù)量相同的情況下，改進后的算法與經(jīng)典Amorphous相比，平均定位誤差下降明顯，這2種算法均隨信標節(jié)點數(shù)目的增多誤差呈下降趨勢，其中，在信標節(jié)點分布密度為20%時，改進的算法定位效果最好，歸一化平均誤差下降50.1%。

圖3 信標節(jié)點比例與定位精度的關系Fig 3 Relationship between anchor proportion and localization precision

3.2 節(jié)點通信半徑對定位精度影響對比

設定節(jié)點的通信半徑為40，50，60 m時，觀察并分析仿真結果。由圖4、圖5可以看出:2種算法的歸一化平均定位誤差在信標節(jié)點比較低，分布較稀疏時均隨節(jié)點通信半徑的增加而顯示減小趨勢:反之，誤差增加。這是由于通信半徑增加后導致節(jié)點接收到的數(shù)據(jù)量增多，對節(jié)點間跳數(shù)估計準確性降低，改進后的算法誤差降低了33.01%。

圖4 經(jīng)典算法節(jié)點通信半徑與定位精度的關系Fir 4 Relationship between radius of communication and localization precision of classical algorithm

圖5 改進算法節(jié)點通信半徑與定位精度的關系Fig 5 Relationship between radius of communication and localization precision of improved algorithm

4 結論

本文針對傳統(tǒng)Amorphous定位算法在跳數(shù)和定位計算中定位誤差較大的問題，提出了跳數(shù)修正，并且引用加權質心算法的思想，用跳數(shù)值轉化為權值，對定位結果進一步進行了修正。仿真實驗證明:改進算法克服了在節(jié)點分布不均勻、網(wǎng)絡拓撲不規(guī)則的網(wǎng)絡中定位誤差大的問題，另外，無需測距，無需額外的硬件支持，適合實際的大規(guī)模網(wǎng)絡節(jié)點定位。

［1］Mao Guoqiang，F(xiàn)idan Baris，Anderson B D O.Wireless sensor networks localization techniques［J］.Computer Networks，2007，51:2529-2553.

［2］孫澤宇，魏 巍.一種改進無線傳感器網(wǎng)絡定位算法的研究［J］.計算機仿真，2010，27(9):125-135.

［3］趙亞濤，王玉寶.一種無線傳感器網(wǎng)絡非均勻分布節(jié)點定位算法［J］.傳感器與微系統(tǒng)，2010，29(8):34-40.

［4］黃中林，鄧 平，梁甲金，等.無線傳感器網(wǎng)絡定位技術研究進展［J］.傳感器與微系統(tǒng)，2008，28(11):4-7.

［5］劉 穎.一種無線傳感器網(wǎng)絡的Amorphous定位算法改進［J］.制造業(yè)自動化，2011，33(1):161-163.

［6］文 舉，金建勛，袁 海.一種無線傳感器網(wǎng)絡四邊測距定位算法［J］.傳感器與微系統(tǒng)，2008，27(5):108-113.