一種無(wú)線傳感器的Amorphous定位算法改進(jìn)

劉 穎

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

一種無(wú)線傳感器的Amorphous定位算法改進(jìn)

劉 穎

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

0 引言

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

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

本文首先對(duì)Amorphous定位算法基本原理進(jìn)行介紹,并指出該算法的不足,接下來(lái)提出改進(jìn)的Amorphous算法,最后通過(guò)算法仿真比較驗(yàn)證算法性能。

1 Amorphous定位算法

1.1 基本原理

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

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

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

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

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

2)計(jì)算平均每跳距離

采用式(2)來(lái)計(jì)算平均每跳距離:

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

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

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

3)采用三邊測(cè)量法或極大似然估計(jì)法進(jìn)行定位

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

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

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

1.2 缺點(diǎn)分析

1.2.1 累積誤差

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

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

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

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

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

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

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

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

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

2 改進(jìn)的Amorphous定位算法

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

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

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

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

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

判斷未知節(jié)點(diǎn)周?chē)鷿M足跳數(shù)閥值限制的信標(biāo)節(jié)點(diǎn)數(shù),如果它大于3個(gè),則從中擇優(yōu)選擇3個(gè),之后采用三邊測(cè)量法進(jìn)行定位。我們用圖3中來(lái)說(shuō)明擇優(yōu)選取信標(biāo)節(jié)點(diǎn)的過(guò)程。

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

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

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

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

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

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

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

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

6)定位結(jié)束

3 仿真

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

4 結(jié)束語(yǔ)

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

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

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

劉穎(1974－),男,江西宜春人,實(shí)驗(yàn)師,碩士,主要從事計(jì)算機(jī)應(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