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

劉 穎

（江蘇食品職業(yè)技術(shù)學(xué)院 計算機應(yīng)用技術(shù)系，淮安 223003）

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

劉 穎

（江蘇食品職業(yè)技術(shù)學(xué)院 計算機應(yīng)用技術(shù)系，淮安 223003）

0 引言

無線傳感器網(wǎng)絡(luò)主要由部署在監(jiān)測區(qū)域內(nèi)的微型、具有感知及無線通信能力的傳感器節(jié)點組成,節(jié)點間以無線通信方式構(gòu)成一個多跳的自組織網(wǎng)絡(luò)[1]。對無線傳感器網(wǎng)絡(luò)的多數(shù)應(yīng)用來說,無時空標(biāo)識數(shù)據(jù)是沒有價值的,所以獲得傳感器節(jié)點位置是需要知道的最基本的信息之一[2]。近年,無線傳感器網(wǎng)絡(luò)節(jié)點定位問題已成為研究熱點。

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

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

1 Amorphous定位算法

1.1 基本原理

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

1)計算未知節(jié)點距各信標(biāo)節(jié)點的最小跳數(shù)

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

各參數(shù)定義如下:

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

2)計算平均每跳距離

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

其中,r為節(jié)點通信半徑,nlocal為網(wǎng)絡(luò)平均連通度。

根據(jù)平均每跳距離及距各信標(biāo)節(jié)點的局部跳數(shù),計算未知節(jié)點距各信標(biāo)節(jié)點的距離,如(3)式所示。

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

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

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

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

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

1.2 缺點分析

1.2.1 累積誤差

圖1為傳感器節(jié)點個數(shù)為150,隨機分布區(qū)域為300×300 (m2),信標(biāo)節(jié)點比例為17.2%,平均網(wǎng)絡(luò)連通度為15.3%時,Amorphous定位算法所對應(yīng)的跳數(shù)值與累積誤差關(guān)系圖。

圖1 跳數(shù)值與累積誤差關(guān)系圖

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

1.2.2 不良參考節(jié)點的引入

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

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

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

1.2.3 需要較大信標(biāo)節(jié)點比例

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

2 改進的Amorphous定位算法

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

1)初始化跳數(shù)閥值

設(shè)置跳數(shù)閥值,如果信標(biāo)節(jié)點距未知節(jié)點跳數(shù)大于此閥值,則其不參與未知節(jié)點定位。

2)求未知節(jié)點距各信標(biāo)節(jié)點最小跳數(shù)及距離

3)擇優(yōu)選取信標(biāo)節(jié)點定位

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

圖3 擇優(yōu)選取信標(biāo)節(jié)點實例圖

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

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

假設(shè)L16所對應(yīng)的Erro最小,則可推出未知節(jié)點A的最優(yōu)解為A6。

4)將未知節(jié)點轉(zhuǎn)化成信標(biāo)節(jié)點

如果未知節(jié)點估算位置滿足一定約束條件,則將其轉(zhuǎn)化為信標(biāo)節(jié)點,用以幫助其他未知節(jié)點進行定位。我們?nèi)砸詧D3為例,假設(shè)未知節(jié)點A估算位置為A',如果A'滿足以下約束條件,則將其轉(zhuǎn)化為信標(biāo)節(jié)點。

5) 更新跳數(shù)閥值

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

6)定位結(jié)束

3 仿真

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

4 結(jié)束語

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

[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

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

無線傳感器網(wǎng)絡(luò)；Amorphous算法；累積誤差；定位精度；魯棒性

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

TN92

A

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

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

2010-10-02