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

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

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

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

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

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

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

無線傳感器網絡；距離向量-跳段(DV-hop)；接收信號強度；傳播模型

無線傳感器網絡(Wireless senor network, WSN)是由大量的傳感器節點以及匯集節點構成的多跳自組織網絡。在監測區域內部署的傳感器節點感知采集監測區域內的信息，通過多跳、無線通信的方式將采集到的信息在網絡中傳遞并最終傳送給匯集節點[1]。傳感器網絡節點的位置信息在應用中有著重要意義，定位技術是無線傳感器網絡的主要支撐技術[2]。

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

DV-hop算法的優點是功耗小，但完全依賴信標節點，定位誤差較大。RSSI算法實現簡單，但定位精度受信號的衰落影響大。針對此種特點，本文擬提出一種基于信號功率的改進DV-hop算法，對DV-hop算法平均跳距的計算進行修正，以減小其定位誤差。

1 DV-hop算法

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

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

(1)記錄信標節點與未知節點之間的最小跳數。

網絡部署完成后，未知節點接收到周圍信標節點所廣播的自身位置信息，包括未知節點與信標節點間的跳數字段，未知節點記錄能接收到周圍每個信標節點的最小跳數。在圖1所示的無線傳感器感知區域中，L1、L2和L3為信標節點，其余節點為傳感器,信標節點L1到L2的最小跳數為2，信標節點L1到L3的最小跳數為6。

圖1 DV-hop算法實例

(2)信標節點與未知節點平均跳段距離計算。

信標節點根據第一個階段中記錄的該節點到其他信標節點的跳數與位置信息，計算平均跳距[5]。平均跳距

(1)

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

到信標節點L2的平均跳距為

到信標節點L3的平均跳距為

(3)利用極大似然估計法或三邊測量法對未知節點位置進行估算。

未知節點根據第二階段中所計算的到周圍信標節點的平均跳距，根據極大似然估計法或三邊測量法計算位置坐標。

綜上，DV-hop算法中平均跳距完全依賴于信標節點，當網絡中信標節點分布均勻，DV-hop算法有較好的定位性能，當網絡中信標節點分布不均勻時，DV-hop算法定位誤差較大。

2 傳播模型

傳感器節點信號的傳播模型對基于距離的定位算法存在著重要影響。在傳感器網絡部署完成后，網絡所處的地理環境，天氣以及節點自身的影響等都與傳播模型有關，節點間進行數據的收發時，在不同的信號傳播模型下，RSSI算法有著不同的定位性能。

2.1 規則傳播模型

在規則傳播模型(RegularModel,RM)中，信號接收強度的表達式為[6]

(2)

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

規則傳播模型是理想模型，未考慮信號在實際傳播中受環境因子影響以及傳播過程中受到障礙物的阻擋而造成的衰落。因此，適用范圍較小，在實際部署的網絡環境中造成的誤差較大。

2.2 對數-陰影衰落模型

基于無線電波的傳播特性，以及反射、折射、衍射、散射、節點差異性等因素的存在，相同的傳感器節點將隨著環境的變化具有不同的信號傳播能力，因此，實際應用中傳感器節點的信號傳播具有衰落性。對數-陰影衰落模型(LogarithmicAttenuationModel，LAM)是一種典型的規則信號衰落模型，其信號接收強度的表達式為[6]

(3)

其中Xσ是由網絡部署的環境造成的均值為零的陰影損耗，是均值為0，標準差為σ的高斯隨機變量。該模型接收信號的均值表達式為[7-8]

(4)

對于RM和LAM，信號在各個方向上的路徑衰落都是相同的[9-11]，即具有各向同性，但LAM考慮到環境因素對信號的影響，增加了信號陰影衰落，更符合實際環境[12]。

3 DV-hop算法改進

當網絡中信標節點分布均勻，信號的傳播模型較為規則時，DV-hop算法有較小的能耗和較好的定位性能[13-14]。當整個網絡中信標節點局布分布不均勻，則DV-hop算法性能明顯下降[15-16]。針對這種問題，可考慮采用以下改進方法。

參照RSSI定位算法測距原理，將實際測得未知節點與信標節點間距離引入DV-hop算法平均跳距的計算中，用測得未知節點與信標節點間實際距離替代信標節點間距離來計算平均跳距，以修正網絡中節點分布的均勻度對定位性能的影響，減小計算平均跳距的誤差。改進后算法的基本步驟如下。

(1)計算未知節點與每個信標節點的最小跳數。

(2)參照RSSI算法中理論模型，確定未知節點到通信半徑內所有信標節點的距離dij。當信號傳播模型采用RM時，dij由式(2)確定,當信號傳播模型為LAM時，信號傳播模型由式(3)確定。

(3)計算未知節點與信標節點的實際跳段距離

(5)其中k為信標節點數,hij為未知節點到信標節點的最小跳數，而未知節點到信標節點之間的距離dij取決于

(6)

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

4 仿真分析

在相同的節點布局條件下，采用Matlab多次仿真并求均值，對原DV-hop算法與改進算法進行仿真分析。假設定位誤差定義為

(7)

其中(xi,yi)為未知節點的估計坐標，(xj,yj)為未知節點的實際坐標，N為未知節點個數，R為節點的通信半徑。

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

(a) RM模型

(b) LAM模型

由圖2可知，原DV-hop算法與改進算法誤差都隨著信標節點比例的增加而下降并趨于平穩。當傳播模型為RM時，改進算法定位誤差降低了18%；當傳播模型為LAM時，改進算法定位誤差降低了10%。

若假設在1 000×1 000m2的方形區域中，信標節點比例保持為0.3，節點通信半徑為200m。當節點總數由100變化到300時，原DV-hop算法與改進算法仿真100次的平均定位誤差如圖3所示。

(a) RM模型

(b) LAM模型

由圖3可知，當節點總數為100，在信標節點比例為0.3時，兩種算法都有著較大的定位誤差，隨著節點總數的增加，兩種算法的定位誤差都逐漸下降并趨于平穩。節點總數越少，定位誤差越大。當信號模型為RM時，改進算法定位誤差降低了19%,而當傳播模型為LAM時，改進算法相比較與原DV-hop算法，定位誤差降低了13%。

5 結 語

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

[1] 孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005：146-151.

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

[3] 方震,趙湛,郭鵬,等.基于RSSI測距分析[J].傳感技術學報,2007,20(11):2526-2530.

[4] 王敬東,賁偉,馬駿,等.無線傳感器網絡混合定位技術研究[J].現代電子技術,2012,35(18):60-63.

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

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

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

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

[9] 曹珊,何志琴,楊靖.無線傳感器網絡中一種改進的DV-hop算法[J].現代機械,2012,12(4):71-73.

[10] 劉剛,周興社,馬駿巖,等.傳感器網絡節點的測距與定位[J].傳感器與儀器儀表,2007,23(5):189-190.

[11] 張杰,胡向東.定位技術在無線傳感器網絡中的應用[J].論文選粹,2008,11(8):34-36.

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

[13] 王福豹,史龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-868.

[14] 顏嘉俊,雷勇.基于RSSI的無線傳感器網絡節點定位[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.

[責任編輯:王輝]

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

國家自然科學基金資助項目(61202490)；陜西省教育廳科學研究計劃基金資助項目(11JK1013)

梁青(1966-)，女，副教授，從事無線傳感器網絡研究。E-mail：liangqing@xupt.edu.cn 韓昊澎(1988-)，男，碩士研究生，研究方向為無線傳感器網絡。E-mail：han_hao_peng@foxmail.com

TP393

A

2095-6533(2014)03-0011-04