張 品，孫 巖

(杭州電子科技大學(xué)通信工程學(xué)院， 杭州310037)

近幾十年來(lái)，隨著通信技術(shù)、嵌入式計(jì)算機(jī)技術(shù)、微處理技術(shù)和傳感器技術(shù)的飛速發(fā)展與日益成熟，無(wú)線傳感器網(wǎng)絡(luò)(WSNs)在無(wú)線通信和數(shù)字電子技術(shù)的促進(jìn)下迅速發(fā)展，由于具有感知能力、通信能力和計(jì)算能力，所以開始受到廣泛的關(guān)注。在大多數(shù)應(yīng)用場(chǎng)景下，沒有傳感器的位置信息而只感知數(shù)據(jù)是沒有意義的，只有結(jié)合了位置信息傳感器獲取的數(shù)據(jù)才有實(shí)際的意義[2]。另外，了解傳感器的節(jié)點(diǎn)位置信息還可以提高路由效率，例如設(shè)計(jì)基于節(jié)點(diǎn)位置信息的路由算法以提高路由效率[3-4]，因此，實(shí)現(xiàn)節(jié)點(diǎn)的自身定位對(duì)WSNs有著重要的意義。

到目前為止，已經(jīng)提出了許多的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法，這些算法大部分都假設(shè)網(wǎng)絡(luò)中包含一小部分的錨節(jié)點(diǎn)，所謂的錨節(jié)點(diǎn)就是可以通過(guò)GPS定位設(shè)備[5]或者其他硬件設(shè)備來(lái)獲取自身位置信息的節(jié)點(diǎn)。而其他不知道自己的位置信息的節(jié)點(diǎn)被稱作是未知節(jié)點(diǎn)。錨節(jié)點(diǎn)可以協(xié)助未知節(jié)點(diǎn)來(lái)進(jìn)行位置定位。當(dāng)一個(gè)未知節(jié)點(diǎn)知道三個(gè)或者三個(gè)以上的錨節(jié)點(diǎn)的位置信息時(shí)，它就可以通過(guò)三邊定位來(lái)確定自己的位置。

在WSNs中，根據(jù)在定位過(guò)程中是否測(cè)量節(jié)點(diǎn)間的距離，可以將定位算法分為兩大類：range-based算法[6](基于測(cè)距的算法)和range-free算法[7](無(wú)需測(cè)距的算法)。Range-based定位算法需要測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或角度信息來(lái)進(jìn)行定位，其中測(cè)距技術(shù)包括：信號(hào)到達(dá)時(shí)間(time of arrival， TOA)、信號(hào)到達(dá)角度(angle of arrival， AOA)[6]、信號(hào) 到達(dá)時(shí)間差(time difference on arrival， TDOA)[8]、信 號(hào) 強(qiáng) 度(received signal strength indicator， RSSI)等[9]。此類算法對(duì)硬件要求較高，需額外的硬件支持。但其中RSSI(基于信號(hào)強(qiáng)度的測(cè)距)對(duì)硬件要求較低，是一種廉價(jià)而有效地測(cè)距解決方案。Range-free定位算法不需要測(cè)量節(jié)點(diǎn)間的距離和方位，對(duì)硬件要求簡(jiǎn)單，但定位誤差較大，不過(guò)可以滿足大部分不需要定位精度很高的場(chǎng)合。典型的Range-free算法包括：DV-hop算法、質(zhì)心算法、MDP-MAP算法及APIT算法等。

1 DV-Hop定位算法的描述

DV-hop算法[10]是為了克服直接三邊定位算法的缺點(diǎn)提出的，它有效的避免了對(duì)節(jié)點(diǎn)的直接測(cè)量，由美國(guó)路特葛斯大學(xué)的Niculescu等人提出的。該算法的核心思想是：將未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離用傳感器網(wǎng)絡(luò)的每跳平均距離和兩者之間的距離的乘積表示，然后再用三角計(jì)算理論獲得未知節(jié)點(diǎn)的位置信息。該算法要解決的問(wèn)題有2：第1，要計(jì)算出未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)；第2，要計(jì)算出每跳平均距離。未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離由它們之間的跳數(shù)乘以每跳平均距離得到。

DV-hop算法的步驟有三個(gè)階段組成：

第1階段采用防洪廣播的形式廣播信息，錨節(jié)點(diǎn)在網(wǎng)絡(luò)中廣播一個(gè)消息，該消息包含了該信標(biāo)的標(biāo)識(shí)id，位置坐標(biāo)以及跳數(shù)Hops，初始化Hops為0，接收到此數(shù)據(jù)的每個(gè)節(jié)點(diǎn)將Hops+1并記錄到一張表格中，然后繼續(xù)向新的鄰居節(jié)點(diǎn)廣播。當(dāng)節(jié)點(diǎn)接收到一個(gè)相同的id數(shù)據(jù)包時(shí)便與表中相同id的數(shù)據(jù)包的Hops相比較，若新的跳數(shù)小于表中已存在的跳數(shù)，就用新的跳數(shù)更新表中的跳數(shù)信息，否則丟棄該數(shù)據(jù)包，也不再進(jìn)行轉(zhuǎn)發(fā)。這樣以泛洪的形式在整個(gè)網(wǎng)絡(luò)中廣播每個(gè)錨節(jié)點(diǎn)的信息，這樣錨節(jié)點(diǎn)獲得了其他所有的錨節(jié)點(diǎn)的坐標(biāo)及跳數(shù)，未知節(jié)點(diǎn)也知道了其與錨節(jié)點(diǎn)的跳數(shù)，這樣就由每一個(gè)錨節(jié)點(diǎn)的每跳平均距離可以由此節(jié)點(diǎn)到其他的錨節(jié)點(diǎn)的總的距離之和除以總的跳數(shù)之和得到。

第2階段求得每個(gè)未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，每個(gè)節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離可以由每跳平均距離乘以此未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳數(shù)得到。

第3階段進(jìn)行三角計(jì)算獲得節(jié)點(diǎn)的位置坐標(biāo)。

2 DV-Hop算法的不足之處

DV-hop算法可以獲得未知節(jié)點(diǎn)無(wú)線射程覆蓋范圍以外的錨節(jié)點(diǎn)的距離，并不需要測(cè)量節(jié)點(diǎn)之間的實(shí)際距離，但用每跳平均距離計(jì)算出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離是有誤差的，對(duì)于那些和錨節(jié)點(diǎn)相距只有一跳的未知節(jié)點(diǎn)來(lái)說(shuō)，它也需要用每跳平均距離來(lái)計(jì)算，這樣誤差將非常的大。例如，如圖1所示。

圖1 某一種節(jié)點(diǎn)分布情況(應(yīng)用傳統(tǒng)DV-Hop算法)

在圖中L1， L2， L3均是錨節(jié)點(diǎn)， A是需要定位的未知節(jié)點(diǎn)。三個(gè)錨節(jié)點(diǎn)知道它們相互之間的距離，分別如圖所示為30， 30和40。 A與L1之間的距離是15，跳數(shù)是1。 A到L2和到L3的跳數(shù)都是3。假設(shè)每一條邊的長(zhǎng)度為10。

由DV-hop算法可知， L1， L2， L3的計(jì)算如下所示：

L1： (30+30)/(4+4)=7.5；

L2： (30+40)/(4+6)=7；

L3： (30+40)/(4+6)=7

在錨節(jié)點(diǎn)計(jì)算完每跳平均距離之后，錨節(jié)點(diǎn)就將這個(gè)值在網(wǎng)絡(luò)中廣播，未知節(jié)點(diǎn)就將它第一個(gè)接收到的值作為每跳平均距離，在此例中L1， L2， L3將分別廣播它們計(jì)算出的值7.5， 7和7。由于節(jié)點(diǎn)A與L1的距離只有一跳，所以節(jié)點(diǎn)A將7.5作為每跳平均距離，然后節(jié)點(diǎn)A就計(jì)算它與其他三個(gè)錨節(jié)點(diǎn)的距離，與L1的距離為7.5，與L2、L3的距離都為7.5?3=22.5。接下來(lái)用三角計(jì)算獲得節(jié)點(diǎn)A的坐標(biāo)。

3 算法的改進(jìn)——新的DV-Hop算法

A與L1的實(shí)際距離為15，用DV-hop算法估算出來(lái)的距離卻為 7.5， 這樣定位誤差就達(dá)到了200%。因此在最后用三角計(jì)算獲得的節(jié)點(diǎn)A的實(shí)際位置坐標(biāo)的誤差將會(huì)很大。節(jié)點(diǎn)A與錨節(jié)點(diǎn)L1之間的距離在一跳之內(nèi)， 可以很容易的獲得，但用DV-hop卻用曲線平均來(lái)計(jì)算它們之間的距離，因此增大了誤差。所以在本文中介紹了一種新的基于RSSI的DV-hop節(jié)點(diǎn)定位算法，名字叫做RDV-hop算法，這種算法同時(shí)運(yùn)用了DV-hop算法和RSSI技術(shù)，改善了未知節(jié)點(diǎn)定位的誤差減小了用DV-hop算法在錨節(jié)點(diǎn)附近的未知節(jié)點(diǎn)定位的誤差。例如，如圖2所示。

圖2 新的DV-Hop算法

在圖2中，我們假設(shè)L1， L2和L3均為錨節(jié)點(diǎn)，節(jié)點(diǎn)M為需要定位的未知節(jié)點(diǎn)。三個(gè)錨節(jié)點(diǎn)的實(shí)際距離分別為15， 30， 30。假設(shè)每條邊的長(zhǎng)度為10。用DV-hop算法三個(gè)錨節(jié)點(diǎn)將分別計(jì)算每跳平均距離：

L1： (15+30)/(2+4)=7.5；

L2： (15+30)/(2+4)=7.5；

L3： (30+30)/(4+4)=7.5

同時(shí)所有的錨節(jié)點(diǎn)產(chǎn)生并在網(wǎng)絡(luò)中廣播RSSI數(shù)據(jù)包，任何一個(gè)接收到RSSI數(shù)據(jù)報(bào)的節(jié)點(diǎn)都可以計(jì)算出它與此錨節(jié)點(diǎn)的距離。在圖2 中，節(jié)點(diǎn)M距L1、L2都只有一條的距離，所以節(jié)點(diǎn)M可以直接獲得從L1、L2發(fā)出的RSSI數(shù)據(jù)包，從而計(jì)算出它與L1、L2的距離(假設(shè)為10)。節(jié)點(diǎn)M所得到的錨節(jié)點(diǎn)的信息少于三個(gè)，然后用DV-hop算法計(jì)算節(jié)點(diǎn)M與其他錨節(jié)點(diǎn)的距離，節(jié)點(diǎn)M計(jì)算出它與L3的距離是7.5×3=22.5。最后節(jié)點(diǎn)M就可以用三邊定位來(lái)計(jì)算自己的坐標(biāo)了。

4 仿真

200個(gè)節(jié)點(diǎn)隨機(jī)的分布在10 000 m×10 000 m的區(qū)域內(nèi)，如圖3所示每個(gè)節(jié)點(diǎn)的無(wú)線覆蓋范圍設(shè)為1 500 m。錨節(jié)點(diǎn)以適當(dāng)?shù)谋壤植荚谄渲小?/p>

圖3 200個(gè)節(jié)點(diǎn)隨機(jī)分布

我們將未知節(jié)點(diǎn)的實(shí)際位置與估算出的位置坐標(biāo)的誤差作為衡量?jī)煞N算法的標(biāo)準(zhǔn)，如圖4 ～圖7所示為在不同的錨節(jié)點(diǎn)比例下的DV-hop算法與改進(jìn)后的RDV-hop算法之間定位誤差的比較，圖4中的下邊的一條曲線表示新算法的定位誤差曲線，而圖4中上邊的曲線則表示老的DV-hop算法的定位誤差曲線。圖4 ～圖7分別表示了在錨節(jié)點(diǎn)的比例為5%， 10 %， 15%和20%的情況下兩種算法定位誤差的比較，圖中上邊的曲線均表示老的DV-hop算法的定位誤差曲線，而下邊的曲線則表示新算法的定位誤差曲線。

圖4 錨節(jié)點(diǎn)的比例為5 %

圖5 錨節(jié)點(diǎn)的比例為10 %

圖6 錨節(jié)點(diǎn)的比例為15 %

圖7 錨節(jié)點(diǎn)的比例為20 %

如圖4 ～圖7所示，我們可以看出新的DV-hop算法在不同的錨節(jié)點(diǎn)比例的情況下的定位誤差都要好于老的DV-hop算法。另外在圖中可以看到，隨著錨節(jié)點(diǎn)的增加可以用RSSI來(lái)計(jì)算距離的鄰居節(jié)點(diǎn)越來(lái)越多，所以隨著錨節(jié)點(diǎn)的增加算法的精確度有所提高。

5 結(jié)論

定位成本和定位的精確度是衡量定位算法好壞的兩個(gè)重要標(biāo)準(zhǔn)。本文介紹了一種新的定位算法，這種定位算法將DV-hop算法與RSSI結(jié)合起來(lái)，用RSSI的優(yōu)點(diǎn)來(lái)改善DV-hop算法，提高了DV-hop算法的精確度。用這種新的算法在計(jì)算那些與錨節(jié)點(diǎn)只有一跳距離的未知節(jié)點(diǎn)時(shí)用RSSI來(lái)替代DV-hop算法，此時(shí)定位誤差明顯減小。仿真實(shí)驗(yàn)已表明此種方法的正確性。但是這種算法有局限性，只有在那些與錨節(jié)點(diǎn)只有一跳距離的未知節(jié)點(diǎn)的定位誤差可以減小，如何改善整個(gè)網(wǎng)絡(luò)所有的未知節(jié)點(diǎn)的定位誤差還需進(jìn)一步的研究。

[ 1] Akyildiz F， SuW， Sandarasurbramaniam Y， et al.Wireless Sensor Networks：a Survey[ J] .Computer Networks Journal， 2002，38(4)：393-422.

[ 2] 王焱欣，王培康.一種無(wú)線傳感器網(wǎng)絡(luò)定位算法的分析和改進(jìn)[ D] .中國(guó)科技大學(xué)， 2007.

[ 3] 王珊珊，殷建平，蔡志平，等.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)自身定位算法[ D] .國(guó)防科技大學(xué)， 2008.

[ 4] 陳浩.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議的研究[ D] .吉林大學(xué)碩士學(xué)位論文， 30-35.

[ 5] 孫利民，李建中，等.無(wú)線傳感器網(wǎng)絡(luò)[ M] .北京：清華大學(xué)出版社， 2005.

[ 6] Bahl P， Padmanabhan V N.RADAR：An In-building RF-based User Location and Tracking System[ C] //Proc.of IEEE INFOCOM， March， 2000.

[ 7]He T， Huang C， Blum B M， et al.Range-free Localization Schemes in Large Scale Sensor Networks[ C] //Proceedings of ACM MobiCom.Canada， 2003.

[ 8] Harter A， Hopper A， Steggles P， et al.The Anatomy of a Context-a Ware Application[ J] .Proc.Of MOBICON， 1999.

[ 9] Tian S， Zhang X， Liu P， etal.A RSSI-based DV-hop A lgorithms for Wireless Sensor Networks[ C] //W ireless Communications，Network and Mobile Computing， 2007.China：Hefei， 2007：2555-2558.

[ 10] Niculescu D， Nath B.Ad Hoc Positioning System(APS)Using AOA[ C] //Proceedings of IEEE IN FOCOM.Sarrfransisco， 2003.