基于DV—Hop大型中心區(qū)域的改進定位算法

李博文+李盛欣

摘要：研究了一些目前在無線傳感器網(wǎng)絡(luò)中存在的定位技術(shù)，基于最小化洪泛法和能量消耗及便于信標節(jié)點的部署，提出了針對大型中心區(qū)域基于DV-Hop改進的定位算法，并借助OMNET++網(wǎng)絡(luò)模擬器對兩種算法進行性能測試，仿真結(jié)果表明改進的定位算法有明顯的性能優(yōu)勢。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；DV-Hop；洪泛法；能量消耗；OMNET++

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2015）22-0034-03

Abstract： In this study， a number of positioning technology in wireless sensor networks， based on the minimize flooding Law and the energy consumption and facilitate the deployment of the beacon nodes is proposed for a large central area of ??an improved localization algorithm based on DV-Hop， by OMNET + + network simulator two algorithms for performance testing， simulation results show improved positioning algorithm has a significant performance advantage.

Key words： wireless sensor networks； DV-Hop； the flooding method； energy consumption； OMNET ++

無線傳感器網(wǎng)絡(luò)的應用是當前最廣泛的應用領(lǐng)域之一，例如環(huán)境監(jiān)測和衛(wèi)生保健系統(tǒng)[1]。而定位對于無線傳感器網(wǎng)絡(luò)應用是最大的難題[2]，例如追蹤森林里動物、探測敵人和跟蹤病人等，如沒有找到發(fā)送數(shù)據(jù)信息的傳感器位置，傳送的數(shù)據(jù)信息就毫無作用。最初的方法是給傳感器加裝一個GPS接收器，然而這種方法不適合無線傳感器網(wǎng)絡(luò)，因為GPS接收器太昂貴，能量消耗太大，并且GPS接收器不能在稠密的植被和封閉的環(huán)境中工作。

輔助定位算法假設(shè)只有少部分傳感器有確定位置通過手動配置或者使用GPS接收器，這些傳感器叫做信標節(jié)點，可以用它們來估算其他傳感器的位置。隨著信標節(jié)點密度的增加，未知傳感器的定位精確度也隨之增加。研究表明除信標節(jié)點的密度外，恰當?shù)夭渴鹦艠斯?jié)點也對定位精確度有影響[3]。

1 定位算法

無線傳感器網(wǎng)絡(luò)定位算法可以分為兩類[4]：基于距離的算法Range-Based，如RSSI（Received Signal Strength Indicator）[5]、TOA（Time of Arrival）[6]、TDOA（Time Difference on Arrival）[7]、AOA（Angel of Arrival）[8]和距離無關(guān)的算法Range-Free，如DV-Hop（Distance Vector-Hop）算法[9]、凸規(guī)劃算法[10]和MDS-MAP算法[11]等。前者需要測量相鄰節(jié)點間的絕對距離或方位，并利用節(jié)點間的實際距離來計算未知節(jié)點的位置，并且對于傳感器需要增加額外的硬件，這使得費用和能量消耗增加；后者無需測量節(jié)點間的絕對距離或方位，而是利用節(jié)點間的估計距離計算節(jié)點位置。

1.1 DV-Hop定位算法

DV-Hop算法的定位過程分為三個階段[12]：

（1）信標節(jié)點向鄰居節(jié)點廣播自身位置信息的分組，其中包括跳數(shù)字段，初始化為0。接收節(jié)點記錄具有到每個信標節(jié)點的最小跳數(shù)，忽略來自同一個信標節(jié)點的較大跳數(shù)的分組。然后將跳數(shù)加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點。通過這個方法，網(wǎng)絡(luò)中的所有節(jié)點能記錄下到每個信標節(jié)點的最小跳數(shù)。

（2）計算未知節(jié)點和信標節(jié)點的實際跳段距離。每個信標節(jié)點根據(jù)第（1）階段中記錄的其他信標節(jié)點的位置信息和相距跳數(shù)，利用式（1）估算平均每跳的實際距離：

其中，（xi，yi）、（xj，yj）是信標節(jié)點i、j的坐標；hj是信標節(jié)點i與j（j≠i）之間的跳段數(shù)。然后，信標節(jié)點將計算的每跳平均距離用帶有生存期字段的分組廣播至網(wǎng)絡(luò)中，未知節(jié)點僅記錄接收到的第1個每跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點。這個策（略確保了大多數(shù)節(jié)點從最近的信標節(jié)點接收到每跳平均距離值。未知節(jié)點接收到平均每跳距離后，乘以記錄的跳數(shù)計算到每個信標節(jié)點的跳段距離。

1.2 DV-Hop定位算法的不足

（1）在大型的無線傳感器網(wǎng)絡(luò)中為了節(jié)約成本，使用有限處理和微控制的傳感器。微控制和微處理不能運行計算復雜的算法，例如三邊測量法中需要使用的非線性最小平方問題。因此在DV-Hop定位算法中估算傳感器距離時把非線性最小平方問題線性化，再加上能量有限的傳感器無法承受接收大量來自信標節(jié)點信息時的能量消耗。所有這些因素都阻礙了DV-Hop定位算法定位的精確度和改進。

（2）針對特定的環(huán)境例如在稠密的森林，對于這些環(huán)境很難在內(nèi)部部署信標節(jié)點，最好的方法就是在這些環(huán)境的周界上部署信標節(jié)點。

1.3改進的DV-Hop定位算法

改進的DV-Hop定位算法的思想是針對中心區(qū)域部署信標節(jié)點，這些信標節(jié)點能夠在監(jiān)控下均勻部署在中心區(qū)域的周界上，最小化洪泛法傳播，根據(jù)必要的有限信標節(jié)點精確定位從而減少能源消耗，三邊測量法將用在基站，因為基站可以快速完成NLLS計算和充足的能量保留所有可能到信標節(jié)點的距離記錄。例如要在茂密的森林里定位追蹤某個動物比如熊貓，信標節(jié)點部署如圖2所示。

改進的DV-Hop算法的定位過程如下：

（1）信標節(jié)點向鄰居節(jié)點廣播自身位置信息的分組，其中包括跳數(shù)字段，初始化為0。接收節(jié)點記錄具有到每個信標節(jié)點的最小跳數(shù)，忽略來自同一個信標節(jié)點的較大跳數(shù)的分組。然后將跳數(shù)加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點。通過這個方法，網(wǎng)絡(luò)中的所有節(jié)點能記錄下到每個信標節(jié)點的最小跳數(shù)。

（2）計算未知節(jié)點和信標節(jié)點的實際跳段距離。每個信標節(jié)點根據(jù)第（1）階段中記錄的其他信標節(jié)點的位置信息和相距跳數(shù)，利用式（1）估算平均每跳的實際距離。在這個階段不同于DV-Hop定位算法，不再是信標節(jié)點根據(jù)式（1）估算平均每跳長度后開始第二次洪泛法傳播給其他的傳感器所估算的平均每跳長度，而是每個信標節(jié)點發(fā)送他們的估算平均每跳長度給基站，基站保留著一張每跳長度表，包括了每個信標節(jié)點的平均每跳長度。

（3）傳感器報告監(jiān)測數(shù)據(jù)信息給基站，在報告中傳感器產(chǎn)生一個新包由兩部分組成：報告信息和傳感器的跳數(shù)表（到每個信標節(jié)點的跳數(shù)）。傳感器先根據(jù)跳數(shù)表判斷找到最近的信標節(jié)點，然后通過信標節(jié)點按編號位置以就近原則依次轉(zhuǎn)播給基站。如圖3所示。

（4）基站定位報告監(jiān)測數(shù)據(jù)信息的傳感器，用它保留的跳數(shù)長度表的記錄和收到報告的跳數(shù)表的記錄進行匹配，然后計算傳感器到所有信標節(jié)點的距離，最后用三邊測量法計算傳感器的位置。

2 仿真實驗及分析

借助OMNET++網(wǎng)絡(luò)模擬器，對DV-Hop定位算法和改進的DV-Hop定位算法進行平均定位誤差和平均能量消耗性能測試比較。在每個仿真實驗中N個傳感器隨機部署在一個平面中心區(qū)域里，以圓形區(qū)域為例，M個信標節(jié)點均勻的放置在周界上，設(shè)定傳感器無線通信半徑為20 m，N為無線傳感器網(wǎng)絡(luò)面積除以π的平方根，M為N的0.1倍，分析不同參數(shù)對算法性能的影響，仿真次數(shù)為20次，用平均值來進行性能測試。

增大無線傳感器網(wǎng)絡(luò)面積，使無線傳感器網(wǎng)絡(luò)面積從0.1km2到20 km2逐漸增大，平均定位誤差每2 km2增加，在圖4中仿真實驗結(jié)果表明增大無線傳感器網(wǎng)絡(luò)面積，對于平均定位誤差增長率來說改進的DV-Hop定位算法比DV-Hop定位算法低。

增加傳感器和信標節(jié)點的數(shù)量，設(shè)定無線傳感器網(wǎng)絡(luò)面積為600 km2，傳感器的個數(shù)從600到2800增加，平均定位誤差每200增加。在圖5中仿真實驗結(jié)果表明隨著傳感器個數(shù)的增加平均定位誤差在DV-Hop定位算法中有明顯的改變，而在改進的DV-Hop定位算法中沒有明顯的改變，這也說明改進的DV-Hop定位算法非常適合用在大型中心區(qū)域無線傳感器網(wǎng)絡(luò)中。在大型中心區(qū)域無線傳感器網(wǎng)絡(luò)中確保精確定位并且能夠達到最小化無線傳感器個數(shù)，這樣可以減少部署開銷。

增加無線傳感器網(wǎng)絡(luò)面積比較兩種定位算法的能量消耗情況。在圖6中仿真實驗結(jié)果表明隨著無線傳感器網(wǎng)絡(luò)面積的增加，能量消耗隨之增加，但改進的DV-Hop定位算法能量消耗比DV-Hop定位算法低些，這又更進一步說明改進的DV-Hop定位算法能夠適應大型中心區(qū)域無線傳感器網(wǎng)絡(luò)。

3 結(jié)論

對于改進的DV-Hop定位算法，目的在于最小化洪泛法，減少能量消耗，在確保必要定位精確度的情況下最小化信標節(jié)點的個數(shù)。改進的DV-Hop定位算法適合監(jiān)測大型中心區(qū)域，因為信標節(jié)點可以部署在中心區(qū)域的周界上。通過仿真實驗，增加無線傳感器網(wǎng)絡(luò)面積和傳感器的數(shù)量，與DV-Hop定位算法進行比較，得到了更低的定位誤差和能量消耗。

參考文獻：

[1] 任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學報，2003，l4（2）：1148-1157.

[2] 王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學報，2005，16（5）：857-868.

[3] 曹文明，王瑞.傳感器網(wǎng)絡(luò)覆蓋定位模糊信息處理方法[M].北京：電子工業(yè)出版社，2013.

[4] 楊冕，秦前清.對傳感器網(wǎng)絡(luò)定位技術(shù)現(xiàn)狀的研究[J].微機發(fā)展，2005，16（3）：26-28.

[5] Chen Xiaoyan，Pei Yanli.The Application of QGA in SensorOptimization Design[C]//Proc.of the 6th International Conferenceon Distributed Computing and Applications for Business，Engineering and Sciences.Wuhan，China：2012：14-17.

[6] Bachrach J，Taylor C，Girod L.Localization in Sensor Net-works[M].New York，USA：Wiley Press，2012：30-41.

[7] Girod L，Estrin D.Robust Rang Estimation Using Acoustic andMultimodal Sensing[C] //Proc. of IEEE/RSJ InternationalConference on Intelligent Robots and Systems.Maui，USA：IEEE Press，2011：1312-1320.

[8]Tang Zijian，Gannizzaro R C，Leus G，et al.Pilot-assisted Time-varying Channel Estimation for OFDM Systems[J].IEEE Trans.on Signal Processing，2012，55（5）：2226-2238.

[9] Niculescu D，Nath B.DV Based Positioning in Ad Hoc Net-works[J].Journal of Telecommunication Systems，2013，22（1/4）：267-280.

[10]Cerpa A，Estrin D.ASCENT：Adaptive Self-c0nfiguring SensorNetwork Topologies[C] //Proc.of the 1lth Joint Conference on IEEE Computer and Communications Societies，IEEE Press，2012：1655-1663.

[11]Shanc Y，Ruml W，Zhang Y，et al.Localization Form MereConnectivity[C] //Proc.of the 4th ACM Intemational Symposiumon Mobile Ad Hoc Networking，Computing.Annapolis，USA：ACM Press，2013：201-212.

[12] 林金朝，劉海波，李國軍，等.無線傳感器網(wǎng)絡(luò)中DV-HOP節(jié)點定位改進算法研究[J].計算機應用研究，2011，26（4）：1272-1275.