一種無線傳感器的Amorphous定位算法改進

劉 穎

（江蘇食品職業技術學院 計算機應用技術系，淮安 223003）

一種無線傳感器的Amorphous定位算法改進

劉 穎

（江蘇食品職業技術學院 計算機應用技術系，淮安 223003）

0 引言

無線傳感器網絡主要由部署在監測區域內的微型、具有感知及無線通信能力的傳感器節點組成,節點間以無線通信方式構成一個多跳的自組織網絡[1]。對無線傳感器網絡的多數應用來說,無時空標識數據是沒有價值的,所以獲得傳感器節點位置是需要知道的最基本的信息之一[2]。近年,無線傳感器網絡節點定位問題已成為研究熱點。

根據節點定位過程中是否需要知道節點間的絕對距離或相對角度等信息,將無線傳感器網絡定位算法分為:距離相關定位算法和距離無關定位算法。距離相關定位算法可獲得較高的定位精度,但對傳感器節點要求較高,且易受外界環境影響,典型的算法有TOA、AOA以及RSSI等。距離無關定位算法利用節點間估算距離來計算節點位置,無需額外硬件支持、功耗和成本低、定位精度適中,典型算法有質心算法、凸規劃算法、DV-hop算法、Amorphous算法等。與距離相關定位算法相比,距離無關定位算法更加適合大規模無線傳感器網絡的應用。

本文首先對Amorphous定位算法基本原理進行介紹,并指出該算法的不足,接下來提出改進的Amorphous算法,最后通過算法仿真比較驗證算法性能。

1 Amorphous定位算法

1.1 基本原理

Amorphous同DV-Hop算法,該算法思想是利用兩節點之間跳段距離代表二者之間的直線距離。其實現大致分三個步驟:

1)計算未知節點距各信標節點的最小跳數

各信標節點通過泛洪等方式廣播分組消息,使網絡中所有節點獲得各信標節點的位置信息與距各信標節點的最小整數跳數,并用式(1)計算h局部跳數來代替整數跳數。

各參數定義如下:

s(i,k):未知節點i到信標節點k的跳數h(i,k):未知節點j到信標節點k的整數跳數h(i,k):未知節點i到信標節點k的整數跳數nbrs(i):未知節點i的鄰居節點集合 |nbrs(i)|:未知節點i的鄰居節點個數。

2)計算平均每跳距離

采用式(2)來計算平均每跳距離:

其中,r為節點通信半徑,nlocal為網絡平均連通度。

根據平均每跳距離及距各信標節點的局部跳數,計算未知節點距各信標節點的距離,如(3)式所示。

其中,HopSizei為未知節點i獲得的平均每跳距離,hop (i, j)則代表未知節點i到信標節點j的最小跳數。

3)采用三邊測量法或極大似然估計法進行定位

當未知節點獲得了距三個或三個以上信標節點的估算距離,便可以采用三邊測量法或極大似然法計算自身位置。

利用最小二乘法對上述方程進行求解,可求得未知節點位置。

其中,(x1,y1),(x2,y3),(x3,y3),…,(xn,yn) 對應n個信標節點的坐標,(x,y) 為未知節點的坐標,未知節點到各信標節點的距離依次為d1,d2,d3,…,dn。

1.2 缺點分析

1.2.1 累積誤差

圖1為傳感器節點個數為150,隨機分布區域為300×300 (m2),信標節點比例為17.2%,平均網絡連通度為15.3%時,Amorphous定位算法所對應的跳數值與累積誤差關系圖。

圖1 跳數值與累積誤差關系圖

由圖1可以看出,隨著未知節點與信標節點之間的跳數值的增大,二者間估算距離與真實距離的誤差也隨之增大。未知節點到達信標節點每增加一跳,便引入不同程度的累積誤差。如何減少由于跳數值過大而引入的累積誤差,是Amorphous算法要解決的一個問題。

1.2.2 不良參考節點的引入

在無線傳感器網絡的定位算法中,有這樣一個結論:在未知節點的定位過程中,參與定位的信標節點數目越多,未知節點的定位精度越高。但是在基于跳段距離的定位算法中,這個結論并不總是正確的[3]。

圖2 三邊測量法與極大似然測量法定位性能比較

圖2為信標節點比例為10%,平均網絡連通度為10時,Amorphous算法分別采用三邊測量法與極大似然測量法的定位性能比較圖。其中,橫坐標對應節點定位精度,縱坐標為各定位精度以內的節點比例。由圖2可知,定位精度在40%(絕大多數應用已滿足)以內時,三邊測量法對應的未知節點比例大于極大似然法。這說明采用極大似然法進行定位會引入不良信標節點,可降低未知節點定位精度。

1.2.3 需要較大信標節點比例

在基于跳段距離的定位算法中,需要較高的信標節點比例,才能獲得較高的定位精度。但若信標節點比例太高,又大大增加無線傳感器網絡的成本。AHLos[4]算法中將定位成功的未知節點全部轉化為信標節點,雖然在一定程度上緩解了該問題,但同時也引入了更大的定位誤差。

2 改進的Amorphous定位算法

針對基于跳段距離算法的缺點,本文提出一種改進的Amorphous算法,該算法的實現大致分為以下幾個階段:

1)初始化跳數閥值

設置跳數閥值,如果信標節點距未知節點跳數大于此閥值,則其不參與未知節點定位。

2)求未知節點距各信標節點最小跳數及距離

3)擇優選取信標節點定位

判斷未知節點周圍滿足跳數閥值限制的信標節點數,如果它大于3個,則從中擇優選擇3個,之后采用三邊測量法進行定位。我們用圖3中來說明擇優選取信標節點的過程。

圖3 擇優選取信標節點實例圖

接下來,用式(8)來比較L1的估算坐標與真實坐標的誤差。

其中,L1的真實坐標為 (xreal,yreal) , (xi,yi) ,(1≤i≤6)為上述六種情況下計算所得的L1的估算坐標,R為節點通信半徑大小。

假設L16所對應的Erro最小,則可推出未知節點A的最優解為A6。

4)將未知節點轉化成信標節點

如果未知節點估算位置滿足一定約束條件,則將其轉化為信標節點,用以幫助其他未知節點進行定位。我們仍以圖3為例,假設未知節點A估算位置為A',如果A'滿足以下約束條件,則將其轉化為信標節點。

5) 更新跳數閥值

當本輪定位結束后,判斷是否有新的未知節點轉化為信標節點。如果有,則保持跳數閥值不變;如果沒有,則將跳數閥值加一。之后跳轉至第二階段,重新對剩余未知節點進行定位。直至所有未知節點定位完成。

6)定位結束

3 仿真

定位精度是評價定位性能的極為重要的一個指標。一般用未知節點真實位置與估算位置的距離與其通信半徑的比值來表示。定位精度值越小,說明算法定位性能越好。無論在不同的信標節點比例還是在不同平均網絡連通度下,改進Amorphous算法定位精度均遠高于原始算法。且相比原始算法,改進算法所對應的定位精度曲線較為平滑,定位精度隨著信標節點比例及平均網絡連通度的增大而增大。可見,改進Amorphous算法在很大程度上降低了累積誤差對定位精度的影響。

4 結束語

本文改進的Amorphous算法,因采用分輪定位機制,當節點分布不規則時,部分未知節點可能需要多輪定位過程才能完成自身定位,計算量較大。所以,如何在保證定位精度的前提下,盡量減少算法復雜度將成為接下來需要研究的重點。

[1]Akyildiz IF,Su W,Sankarasurbramaniam Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002,38 (4): 393-422.

[2]Bachrach J, Taylor C. Handbook of Sensor Networks:Algorithms and Architectures[M]. Wiley Interscience,2005: 552.

[3]Tian S, Zhang X, Wang X, et al. A Selective Anchor Node Localization Algorithm for Wireless Sensor Net-Works International Conference on Digital Object Identifier.Gyeongju 2007.

[4]Andreas S,Chih-Chieh H,Srivastava MB.Dynamic finegrained localization in ad-hoc networks of sensors[C].Proceedings of the 7th annual international conference on Mobile computing and networking Rome,Italy.2001: 166-1.

An adaptive multi-hop distance localization algorithm in WSN

LIU Ying

無線傳感器網絡中的Amorphous定位算法，利用跳段距離來代替兩節點之間的直線距離，雖然實現簡單，但在定位過程中會產生較大的累積誤差。本文引入了自適應跳數閥值，并提出了一種改進的Amorphous定位算法。仿真實驗結果表明，與原始算法相比，改進算法降低了累積誤差，同時提高了算法的定位精度和魯棒性。

無線傳感器網絡；Amorphous算法；累積誤差；定位精度；魯棒性

劉穎(1974－),男,江西宜春人,實驗師,碩士,主要從事計算機應用和現代教育技術研究工作。

TN92

A

1009-0134(2011)1(上)-0161-03

10.3969/j.issn.1009-0134.2011.1(上).49

2010-10-02