梁 青, 韓昊澎, 李卓冉, 熊 偉

(1.西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121； 2.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院， 陜西 西安 710077)

一種無(wú)線傳感器網(wǎng)絡(luò)定位算法的改進(jìn)

梁 青1, 韓昊澎1, 李卓冉1, 熊 偉2

(1.西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121； 2.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院， 陜西 西安 710077)

為了減小距離向量-跳段(DV-hop)算法中計(jì)算平均跳距時(shí)所造成的誤差對(duì)定位的影響，提出一種基于測(cè)距信息的改進(jìn)DV-hop算法。改進(jìn)算法充分考慮DV-hop算法中信標(biāo)節(jié)點(diǎn)計(jì)算平均跳距誤差較大這一因素，將接收的信號(hào)強(qiáng)度指示(RSSI)算法中測(cè)得信號(hào)強(qiáng)度值轉(zhuǎn)化為距離信息，再將距離信息引入DV-hop算法平均跳距的計(jì)算中，并在不同信號(hào)傳播模型下進(jìn)行仿真分析。仿真結(jié)果表明，在同一信號(hào)傳播模型下，改進(jìn)算法比原DV-hop算法有著更小的定位誤差。

無(wú)線傳感器網(wǎng)絡(luò)；距離向量-跳段(DV-hop)；接收信號(hào)強(qiáng)度；傳播模型

無(wú)線傳感器網(wǎng)絡(luò)(Wireless senor network, WSN)是由大量的傳感器節(jié)點(diǎn)以及匯集節(jié)點(diǎn)構(gòu)成的多跳自組織網(wǎng)絡(luò)。在監(jiān)測(cè)區(qū)域內(nèi)部署的傳感器節(jié)點(diǎn)感知采集監(jiān)測(cè)區(qū)域內(nèi)的信息，通過(guò)多跳、無(wú)線通信的方式將采集到的信息在網(wǎng)絡(luò)中傳遞并最終傳送給匯集節(jié)點(diǎn)[1]。傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的位置信息在應(yīng)用中有著重要意義，定位技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)的主要支撐技術(shù)[2]。

定位技術(shù)分為基于距離(Range-Based)的定位技術(shù)和與距離無(wú)關(guān)(Range-Free)的定位技術(shù)。距離向量-跳段(Distance Vector-Hop, DV-hop)算法是最受關(guān)注的與距離無(wú)關(guān)的定位算法[1];接收的信號(hào)強(qiáng)度指示(Received signal Strength Indicator, RSSI)定位算法是一種典型的基于距離的算法[3]。文[2]通過(guò)對(duì)DV-hop算法的網(wǎng)絡(luò)參數(shù)進(jìn)行優(yōu)化以減小定位誤差；文[3]提出一種混合定位策略，在同一種網(wǎng)絡(luò)中采用多種定位算法以減小定位誤差。文[4]在各向異性的網(wǎng)絡(luò)條件下對(duì)DV-hop算法進(jìn)行了仿真分析。

DV-hop算法的優(yōu)點(diǎn)是功耗小，但完全依賴(lài)信標(biāo)節(jié)點(diǎn)，定位誤差較大。RSSI算法實(shí)現(xiàn)簡(jiǎn)單，但定位精度受信號(hào)的衰落影響大。針對(duì)此種特點(diǎn)，本文擬提出一種基于信號(hào)功率的改進(jìn)DV-hop算法，對(duì)DV-hop算法平均跳距的計(jì)算進(jìn)行修正，以減小其定位誤差。

1 DV-hop算法

DV-hop算法根據(jù)傳感器節(jié)點(diǎn)的能量有限、節(jié)點(diǎn)間采用多跳通信且節(jié)點(diǎn)只與鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換等特點(diǎn)對(duì)未知節(jié)點(diǎn)進(jìn)行定位。在距離-向量定位機(jī)制下，未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)進(jìn)行通信，先記錄兩者間的最小跳數(shù)，再計(jì)算平均跳距，平均跳距乘以最小跳數(shù)，得到信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的計(jì)算距離，最后利用極大似然估計(jì)法或三邊測(cè)量法估算未知節(jié)點(diǎn)的位置坐標(biāo)。

DV-hop算法的基本定位過(guò)程描述如下。

(1)記錄信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的最小跳數(shù)。

網(wǎng)絡(luò)部署完成后，未知節(jié)點(diǎn)接收到周?chē)艠?biāo)節(jié)點(diǎn)所廣播的自身位置信息，包括未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的跳數(shù)字段，未知節(jié)點(diǎn)記錄能接收到周?chē)總€(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。在圖1所示的無(wú)線傳感器感知區(qū)域中，L1、L2和L3為信標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)為傳感器,信標(biāo)節(jié)點(diǎn)L1到L2的最小跳數(shù)為2，信標(biāo)節(jié)點(diǎn)L1到L3的最小跳數(shù)為6。

圖1 DV-hop算法實(shí)例

(2)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)平均跳段距離計(jì)算。

信標(biāo)節(jié)點(diǎn)根據(jù)第一個(gè)階段中記錄的該節(jié)點(diǎn)到其他信標(biāo)節(jié)點(diǎn)的跳數(shù)與位置信息，計(jì)算平均跳距[5]。平均跳距

(1)

其中(xi,yi)和(xj,yj)分別是信標(biāo)節(jié)點(diǎn)i和j的坐標(biāo)，hj是信標(biāo)節(jié)點(diǎn)i和j(j≠i)之間的跳段數(shù)。如圖1可知，信標(biāo)節(jié)點(diǎn)L1與L2之間的距離為40m，L2與L3之間的距離為75m，L1與L3之間的距離為100m,則未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)L1的平均跳距為

到信標(biāo)節(jié)點(diǎn)L2的平均跳距為

到信標(biāo)節(jié)點(diǎn)L3的平均跳距為

(3)利用極大似然估計(jì)法或三邊測(cè)量法對(duì)未知節(jié)點(diǎn)位置進(jìn)行估算。

未知節(jié)點(diǎn)根據(jù)第二階段中所計(jì)算的到周?chē)艠?biāo)節(jié)點(diǎn)的平均跳距，根據(jù)極大似然估計(jì)法或三邊測(cè)量法計(jì)算位置坐標(biāo)。

綜上，DV-hop算法中平均跳距完全依賴(lài)于信標(biāo)節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)分布均勻，DV-hop算法有較好的定位性能，當(dāng)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)分布不均勻時(shí)，DV-hop算法定位誤差較大。

2 傳播模型

傳感器節(jié)點(diǎn)信號(hào)的傳播模型對(duì)基于距離的定位算法存在著重要影響。在傳感器網(wǎng)絡(luò)部署完成后，網(wǎng)絡(luò)所處的地理環(huán)境，天氣以及節(jié)點(diǎn)自身的影響等都與傳播模型有關(guān)，節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)的收發(fā)時(shí)，在不同的信號(hào)傳播模型下，RSSI算法有著不同的定位性能。

2.1 規(guī)則傳播模型

在規(guī)則傳播模型(RegularModel,RM)中，信號(hào)接收強(qiáng)度的表達(dá)式為[6]

(2)

其中PR為接收信號(hào)功率，PT(d)為發(fā)射信號(hào)功率，PL(d0)為信號(hào)傳播參考距離,d0是損耗功率，η為路徑損耗指數(shù)，d為傳播距離。

規(guī)則傳播模型是理想模型，未考慮信號(hào)在實(shí)際傳播中受環(huán)境因子影響以及傳播過(guò)程中受到障礙物的阻擋而造成的衰落。因此，適用范圍較小，在實(shí)際部署的網(wǎng)絡(luò)環(huán)境中造成的誤差較大。

2.2 對(duì)數(shù)-陰影衰落模型

基于無(wú)線電波的傳播特性，以及反射、折射、衍射、散射、節(jié)點(diǎn)差異性等因素的存在，相同的傳感器節(jié)點(diǎn)將隨著環(huán)境的變化具有不同的信號(hào)傳播能力，因此，實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)的信號(hào)傳播具有衰落性。對(duì)數(shù)-陰影衰落模型(LogarithmicAttenuationModel，LAM)是一種典型的規(guī)則信號(hào)衰落模型，其信號(hào)接收強(qiáng)度的表達(dá)式為[6]

(3)

其中Xσ是由網(wǎng)絡(luò)部署的環(huán)境造成的均值為零的陰影損耗，是均值為0，標(biāo)準(zhǔn)差為σ的高斯隨機(jī)變量。該模型接收信號(hào)的均值表達(dá)式為[7-8]

(4)

對(duì)于RM和LAM，信號(hào)在各個(gè)方向上的路徑衰落都是相同的[9-11]，即具有各向同性，但LAM考慮到環(huán)境因素對(duì)信號(hào)的影響，增加了信號(hào)陰影衰落，更符合實(shí)際環(huán)境[12]。

3 DV-hop算法改進(jìn)

當(dāng)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)分布均勻，信號(hào)的傳播模型較為規(guī)則時(shí)，DV-hop算法有較小的能耗和較好的定位性能[13-14]。當(dāng)整個(gè)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)局布分布不均勻，則DV-hop算法性能明顯下降[15-16]。針對(duì)這種問(wèn)題，可考慮采用以下改進(jìn)方法。

參照RSSI定位算法測(cè)距原理，將實(shí)際測(cè)得未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間距離引入DV-hop算法平均跳距的計(jì)算中，用測(cè)得未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間實(shí)際距離替代信標(biāo)節(jié)點(diǎn)間距離來(lái)計(jì)算平均跳距，以修正網(wǎng)絡(luò)中節(jié)點(diǎn)分布的均勻度對(duì)定位性能的影響，減小計(jì)算平均跳距的誤差。改進(jìn)后算法的基本步驟如下。

(1)計(jì)算未知節(jié)點(diǎn)與每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

(2)參照RSSI算法中理論模型，確定未知節(jié)點(diǎn)到通信半徑內(nèi)所有信標(biāo)節(jié)點(diǎn)的距離dij。當(dāng)信號(hào)傳播模型采用RM時(shí)，dij由式(2)確定,當(dāng)信號(hào)傳播模型為L(zhǎng)AM時(shí)，信號(hào)傳播模型由式(3)確定。

(3)計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離

(5)其中k為信標(biāo)節(jié)點(diǎn)數(shù),hij為未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，而未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離dij取決于

(6)

(4)按照DV-hop算法用平均跳距計(jì)算距離并利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算自身位置。

4 仿真分析

在相同的節(jié)點(diǎn)布局條件下，采用Matlab多次仿真并求均值，對(duì)原DV-hop算法與改進(jìn)算法進(jìn)行仿真分析。假設(shè)定位誤差定義為

(7)

其中(xi,yi)為未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，(xj,yj)為未知節(jié)點(diǎn)的實(shí)際坐標(biāo)，N為未知節(jié)點(diǎn)個(gè)數(shù)，R為節(jié)點(diǎn)的通信半徑。

假設(shè)在1 000×1 000m2的方形區(qū)域中隨機(jī)部署300個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)通信半徑為200m，分別在RM及LAM兩種模型下，就信標(biāo)節(jié)點(diǎn)比例由0.1增加到0.5，對(duì)原DV-hop算法與改進(jìn)算法進(jìn)行100次仿真，取其平均定位誤差，結(jié)果如圖2所示。

(a) RM模型

(b) LAM模型

由圖2可知，原DV-hop算法與改進(jìn)算法誤差都隨著信標(biāo)節(jié)點(diǎn)比例的增加而下降并趨于平穩(wěn)。當(dāng)傳播模型為RM時(shí)，改進(jìn)算法定位誤差降低了18%；當(dāng)傳播模型為L(zhǎng)AM時(shí)，改進(jìn)算法定位誤差降低了10%。

若假設(shè)在1 000×1 000m2的方形區(qū)域中，信標(biāo)節(jié)點(diǎn)比例保持為0.3，節(jié)點(diǎn)通信半徑為200m。當(dāng)節(jié)點(diǎn)總數(shù)由100變化到300時(shí)，原DV-hop算法與改進(jìn)算法仿真100次的平均定位誤差如圖3所示。

(a) RM模型

(b) LAM模型

由圖3可知，當(dāng)節(jié)點(diǎn)總數(shù)為100，在信標(biāo)節(jié)點(diǎn)比例為0.3時(shí)，兩種算法都有著較大的定位誤差，隨著節(jié)點(diǎn)總數(shù)的增加，兩種算法的定位誤差都逐漸下降并趨于平穩(wěn)。節(jié)點(diǎn)總數(shù)越少，定位誤差越大。當(dāng)信號(hào)模型為RM時(shí)，改進(jìn)算法定位誤差降低了19%,而當(dāng)傳播模型為L(zhǎng)AM時(shí)，改進(jìn)算法相比較與原DV-hop算法，定位誤差降低了13%。

5 結(jié) 語(yǔ)

在DV-hop定位算法的基礎(chǔ)上提出一種基于RSSI值的改進(jìn)DV-hop算法。改進(jìn)DV-hop算法利用RSSI值轉(zhuǎn)化為距離，對(duì)原DV-hop算法平均跳距的計(jì)算進(jìn)行修正，并在兩種傳播模型下進(jìn)行仿真分析。仿真結(jié)果表明，改進(jìn)DV-hop算法相比較原DV-hop算法在RM和LAM兩種模型下都有著更小的定位誤差。

[1] 孫利民,李建中,陳渝,等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005：146-151.

[2] 李牧東,熊偉,梁青,等.無(wú)線傳感器網(wǎng)絡(luò)DV-hop定位算法研究[J].空軍工程大學(xué)學(xué)報(bào):自然科學(xué)版,2012,13(4):75-79.

[3] 方震,趙湛,郭鵬,等.基于RSSI測(cè)距分析[J].傳感技術(shù)學(xué)報(bào),2007,20(11):2526-2530.

[4] 王敬東,賁偉,馬駿,等.無(wú)線傳感器網(wǎng)絡(luò)混合定位技術(shù)研究[J].現(xiàn)代電子技術(shù),2012,35(18):60-63.

[5] 梁青,熊偉,韓昊澎.各向異性無(wú)線傳感器網(wǎng)絡(luò)DV-Hop算法性能仿真[J].西安郵電大學(xué)學(xué)報(bào),2013,18(5):31-36.

[6] 許紅艷,王經(jīng)卓,董自健,等.MDS-MAP算法在不同傳播模型中定位誤差的比較[J].淮海工學(xué)院學(xué)報(bào),2012,21(1):15-19.

[7] 方海濤,雷菁,胡昆明,等.基于RSSI修正的改進(jìn)DV-hop測(cè)距算法[J].通信技術(shù),2012,45(2):16-18.

[8] 張品,孫巖.一種新的無(wú)線傳感器網(wǎng)絡(luò)DV-hop算法[J].電子器件,2010,33(1):117-120.

[9] 曹珊,何志琴,楊靖.無(wú)線傳感器網(wǎng)絡(luò)中一種改進(jìn)的DV-hop算法[J].現(xiàn)代機(jī)械,2012,12(4):71-73.

[10] 劉剛,周興社,馬駿巖,等.傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的測(cè)距與定位[J].傳感器與儀器儀表,2007,23(5):189-190.

[11] 張杰,胡向東.定位技術(shù)在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用[J].論文選粹,2008,11(8):34-36.

[12] 竺如生.基于DV-hopWSN改進(jìn)算法的研究與仿真[J].計(jì)算機(jī)應(yīng)用,2012,31(6):18-20.

[13] 王福豹,史龍,任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5):857-868.

[14] 顏嘉俊,雷勇.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位[J].計(jì)算機(jī)仿真,2012,29(7):151-154.

[15]MaoG,FidanB,AndersonB.Wirelesssensornetworklocalizationtechniques[J].ComputerNetwork,2007,51(6):2529-2553.

[16]NiculescuD,NathB.Ad-hocpositioningsystem(APS)[C]//Proceedingsofthe2001IEEEGlobalTelecommunications.USATexasSanAntonio:IEEE,2003:1734-1743.

[責(zé)任編輯:王輝]

Improvement of a hybrid localization algorithm in wireless sensor network

LIANG Qing1, HAN Haopeng1, LI Zhuoran1, XIONG Wei2

(1. School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China； 2. Institute of Information and Navigation, Air Force Engineering University, Xi’an 710077, China)

In order to reduce the effect on positioning from the average hop distance error calculated by the DV-hop algorithm, a kind of improved DV-hop algorithm based on RSSI ranging is proposed. Considering the effect of beacon nodes while calculating the average hop distance in DV-hop，the improved algorithm can transform the measured signal intensity values into the distance information from RSSI algorithm ranging. Simulations are carried out in different transmission models and results show that the improved algorithm has smaller location error than the original algorithm in the same transmission model.

wireless sensor network, DV-hop algorithm,

signal strength indictor, transmission model

10.13682/j.issn.2095-6533.2014.03.003

2013-11-25

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202490)；陜西省教育廳科學(xué)研究計(jì)劃基金資助項(xiàng)目(11JK1013)

梁青(1966-)，女，副教授，從事無(wú)線傳感器網(wǎng)絡(luò)研究。E-mail：liangqing@xupt.edu.cn 韓昊澎(1988-)，男，碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。E-mail：han_hao_peng@foxmail.com

TP393

A

2095-6533(2014)03-0011-04