基于Amorphous的無線傳感器網絡定位算法研究*

安文秀，趙菊敏，李燈熬

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

0 引言

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

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

1 Amorphous定位算法模型

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

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

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

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

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

寫成矩陣形式AX=b，即

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

2 改進算法模型

2.1 跳數修正

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

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

圖1 跳數修正原理圖Fig 1 Principle diagram of hops correction

2.2 質心算法加權

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

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

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

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

3 仿真與結果分析

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

3.1 信標節點數量對定位誤差影響的對比

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

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

3.2 節點通信半徑對定位精度影響對比

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

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

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

4 結論

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

［1］Mao Guoqiang，Fidan Baris，Anderson B D O.Wireless sensor networks localization techniques［J］.Computer Networks，2007，51:2529-2553.

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

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

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

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

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