李博文+李盛欣

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

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

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ú)線(xiàn)傳感器網(wǎng)絡(luò)的應(yīng)用是當(dāng)前最廣泛的應(yīng)用領(lǐng)域之一，例如環(huán)境監(jiān)測(cè)和衛(wèi)生保健系統(tǒng)[1]。而定位對(duì)于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用是最大的難題[2]，例如追蹤森林里動(dòng)物、探測(cè)敵人和跟蹤病人等，如沒(méi)有找到發(fā)送數(shù)據(jù)信息的傳感器位置，傳送的數(shù)據(jù)信息就毫無(wú)作用。最初的方法是給傳感器加裝一個(gè)GPS接收器，然而這種方法不適合無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，因?yàn)镚PS接收器太昂貴，能量消耗太大，并且GPS接收器不能在稠密的植被和封閉的環(huán)境中工作。

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

1 定位算法

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位算法可以分為兩類(lèi)[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]和距離無(wú)關(guān)的算法Range-Free，如DV-Hop（Distance Vector-Hop）算法[9]、凸規(guī)劃算法[10]和MDS-MAP算法[11]等。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，并利用節(jié)點(diǎn)間的實(shí)際距離來(lái)計(jì)算未知節(jié)點(diǎn)的位置，并且對(duì)于傳感器需要增加額外的硬件，這使得費(fèi)用和能量消耗增加；后者無(wú)需測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方位，而是利用節(jié)點(diǎn)間的估計(jì)距離計(jì)算節(jié)點(diǎn)位置。

1.1 DV-Hop定位算法

DV-Hop算法的定位過(guò)程分為三個(gè)階段[12]：

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

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

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

1.2 DV-Hop定位算法的不足

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

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

1.3改進(jìn)的DV-Hop定位算法

改進(jìn)的DV-Hop定位算法的思想是針對(duì)中心區(qū)域部署信標(biāo)節(jié)點(diǎn)，這些信標(biāo)節(jié)點(diǎn)能夠在監(jiān)控下均勻部署在中心區(qū)域的周界上，最小化洪泛法傳播，根據(jù)必要的有限信標(biāo)節(jié)點(diǎn)精確定位從而減少能源消耗，三邊測(cè)量法將用在基站，因?yàn)榛究梢钥焖偻瓿蒒LLS計(jì)算和充足的能量保留所有可能到信標(biāo)節(jié)點(diǎn)的距離記錄。例如要在茂密的森林里定位追蹤某個(gè)動(dòng)物比如熊貓，信標(biāo)節(jié)點(diǎn)部署如圖2所示。

改進(jìn)的DV-Hop算法的定位過(guò)程如下：

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

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

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

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

2 仿真實(shí)驗(yàn)及分析

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4] 楊冕，秦前清.對(duì)傳感器網(wǎng)絡(luò)定位技術(shù)現(xiàn)狀的研究[J].微機(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] 林金朝，劉海波，李國(guó)軍，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中DV-HOP節(jié)點(diǎn)定位改進(jìn)算法研究[J].計(jì)算機(jī)應(yīng)用研究，2011，26（4）：1272-1275.