基于OMNeT++平臺(tái)的DV-Hop 定位算法改進(jìn)

劉 排，武 一，南京婭，劉建民

(1.河北工業(yè)大學(xué) 信息工程學(xué)院，天津300401;2.天津現(xiàn)代職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院，天津300350)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)中，位置信息對(duì)無線傳感網(wǎng)絡(luò)的監(jiān)控活動(dòng)至關(guān)重要，事件發(fā)生的位置是無線傳感器節(jié)點(diǎn)監(jiān)控消息中所包含的重要信息，沒有位置信息的監(jiān)控消息往往毫無意義。因此，確定事件發(fā)生的位置對(duì)無線傳感網(wǎng)絡(luò)應(yīng)用的有效性起著關(guān)鍵作用［1］。

根據(jù)定位機(jī)制可將現(xiàn)有無線傳感器網(wǎng)絡(luò)自身定位算法分為基于測距的和無需測距的定位算法兩類。無需測距的算法不需要節(jié)點(diǎn)自身的測距設(shè)備，通過跳數(shù)或是其他信息估計(jì)自身到選定的信標(biāo)節(jié)點(diǎn)的距離值。由于是估計(jì)得到的數(shù)值，相對(duì)于基于測距的算法獲得的距離值誤差偏大。常用的定位算法有質(zhì)心法、凸規(guī)劃、DV-Hop 算法、Amorphous算法、MDS-MAP 和APIT 算法等，DV-Hop 算法因憑借其定位過程實(shí)現(xiàn)簡單，對(duì)節(jié)點(diǎn)硬件要求不高，在各向同性的網(wǎng)絡(luò)中性能良好等優(yōu)勢，成為了目前應(yīng)用最廣泛的算法之一。

但是DV-Hop 算法的未知節(jié)點(diǎn)依靠測量與鄰近信標(biāo)節(jié)點(diǎn)之間的距離來推算自身位置產(chǎn)生的誤差較大，為此，本文提出了通過定位出離信標(biāo)節(jié)點(diǎn)距離較近的未知節(jié)點(diǎn)升級(jí)為信標(biāo)節(jié)點(diǎn)的方法來減小定位中的誤差，并且采用自由搜索算法取代誤差較大的三邊測量法來計(jì)算未知節(jié)點(diǎn)坐標(biāo)，并在仿真平臺(tái)OMNET++上驗(yàn)證。

1 DV-Hop 算法過程

傳統(tǒng)的DV-Hop 算法的實(shí)現(xiàn)過程大致分為三步驟:

1)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)采用典型的距離矢量交換協(xié)議，信標(biāo)節(jié)點(diǎn)發(fā)起第一次泛洪廣播，廣播的信息包括自己的ID，坐標(biāo)信息和初始跳數(shù)。直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都獲得信標(biāo)節(jié)點(diǎn)的廣播信息。

2)當(dāng)信標(biāo)節(jié)點(diǎn)獲得其他信標(biāo)的位置和相隔跳數(shù)后，信標(biāo)節(jié)點(diǎn)利用下面公式來計(jì)算平均毎跳距離

式中 (xiyi)為信標(biāo)節(jié)點(diǎn)的坐標(biāo)，hi為信標(biāo)節(jié)點(diǎn)i 與j(j≠i)之間的跳段數(shù)。信標(biāo)節(jié)點(diǎn)發(fā)起第二次泛洪廣播，將計(jì)算出的平均跳距廣播到網(wǎng)絡(luò)中，未知節(jié)點(diǎn)利用接收到的平均跳數(shù)值和第一階段中得到的距各個(gè)錨節(jié)點(diǎn)跳數(shù)來近似計(jì)算到各個(gè)參考節(jié)點(diǎn)之間的距離［2］。

3)當(dāng)未知節(jié)點(diǎn)獲得距離錨節(jié)點(diǎn)的估算距離后，利用三邊測量法或極大似然法來估計(jì)節(jié)點(diǎn)的二維坐標(biāo)值，實(shí)現(xiàn)節(jié)點(diǎn)的定位［3］。

2 DV-Hop 算法的改進(jìn)

DV-Hop 算法在計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離時(shí)，使用折線距離代替直線距離，這樣就會(huì)導(dǎo)致在拓?fù)浣Y(jié)構(gòu)不均勻的傳感網(wǎng)絡(luò)中定位誤差很大［4］。在對(duì)未知節(jié)點(diǎn)的坐標(biāo)進(jìn)行估算時(shí)，通常用的三邊測量法和極大似然法也存在極大誤差。針對(duì)DV-Hop 算法的以上不足，本文提出了以下的改進(jìn)方法。

2.1 基于RSSI 測距增加信標(biāo)節(jié)點(diǎn)的改進(jìn)方法

大量實(shí)驗(yàn)表明:定位誤差較大的未知節(jié)點(diǎn)通常是那些遠(yuǎn)離信標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)，增加信標(biāo)節(jié)點(diǎn)的數(shù)目是最直接而有效的方法，但信標(biāo)節(jié)點(diǎn)價(jià)格昂貴，能耗大，這種方法并不可取。因此，本文提出了基于RSSI 測距增加信標(biāo)節(jié)點(diǎn)的改進(jìn)方法。首先讓所有信標(biāo)節(jié)點(diǎn)利用可控范洪進(jìn)行廣播，信標(biāo)節(jié)點(diǎn)發(fā)出的消息后只經(jīng)過一跳，就將消息刪掉不再轉(zhuǎn)發(fā)，利用RSSI 測距的方法，計(jì)算出信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離，如果有未接節(jié)點(diǎn)接知到三個(gè)及以上信標(biāo)節(jié)點(diǎn)發(fā)來的消息，便可用三邊測量法確定出此未知節(jié)點(diǎn)的位置［5］，確定出位置的未知節(jié)點(diǎn)便可升級(jí)為信標(biāo)節(jié)點(diǎn)。

如圖1 中，其中，●代表信標(biāo)節(jié)點(diǎn)模塊，○代表未知節(jié)點(diǎn)模塊，A，B，C，D，E 節(jié)點(diǎn)都接收到了三個(gè)臨近信標(biāo)節(jié)點(diǎn)的消息，利用RSSI 測距的方法分別計(jì)算出與信標(biāo)節(jié)點(diǎn)的距離，考慮到增加信標(biāo)節(jié)點(diǎn)在進(jìn)行泛洪廣播的能耗會(huì)增加，所以，當(dāng)增加信標(biāo)節(jié)點(diǎn)時(shí)要進(jìn)行選擇，圖中A，B 節(jié)點(diǎn)都接收到了信標(biāo)節(jié)點(diǎn)2 發(fā)來的消息，所以，A，B 只將其中一個(gè)升級(jí)為信標(biāo)節(jié)點(diǎn)即可，再利用三邊測量法，計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)，這些計(jì)算出坐標(biāo)的節(jié)點(diǎn)便可升級(jí)為信標(biāo)節(jié)點(diǎn)。這樣可在不增加額外硬件的基礎(chǔ)上，便可增加定位的精度。

2.2 基于加權(quán)的自由搜索

圖1 傳感器網(wǎng)絡(luò)節(jié)點(diǎn)分布圖Fig 1 Distribution of WSNs node

自由搜索(free search，F(xiàn)S)算法是一種吸收了GA，ACO算法，PSO 算法等算法的優(yōu)勢的新型智能優(yōu)化算法，F(xiàn)S 算法具有較快的全局收斂性和較強(qiáng)的自適應(yīng)性能力，在解決DV-Hop 算法定位的優(yōu)化問題顯示出了優(yōu)勢。在FS 算法模型中，一個(gè)種群包含有m 個(gè)個(gè)體，m 個(gè)個(gè)體在半徑為R 的搜索空間內(nèi)移動(dòng)，每個(gè)個(gè)體的移動(dòng)包括全局內(nèi)的搜索和局部范圍內(nèi)的搜索［6］，一次迭代個(gè)體移動(dòng)一個(gè)搜索步，每個(gè)搜索步包含T 小步，個(gè)體對(duì)搜索步內(nèi)找到的較優(yōu)解進(jìn)行記錄，稱為標(biāo)記信息素，其大小與目標(biāo)函數(shù)的適應(yīng)度呈正比，每完成一次迭代，信息素將會(huì)被完全更新。個(gè)體的搜索本質(zhì)上是一種標(biāo)記信息素的過程，這些信息素將做為所有個(gè)體在下一次搜索開始時(shí)，選擇起始點(diǎn)的依據(jù)之一，另一個(gè)依據(jù)則是個(gè)體的靈敏度［7］。當(dāng)個(gè)體的靈敏度小于信息素時(shí)，個(gè)體受其影響改變搜索起點(diǎn)，選擇搜索步T 中的最佳位置做為下一次搜索的起點(diǎn);否則，個(gè)體不改變搜索起點(diǎn)，仍使用上一次迭代的搜索起點(diǎn)。

1)初始化

需要初始化的變量有:種群包含的個(gè)體m，空間維數(shù)d，搜索步中的搜索小步數(shù)T，搜索半徑R，搜索空間的范圍［Vmin，Vmax］，最大迭代次數(shù)Gmax。m 個(gè)個(gè)體被隨機(jī)分散到搜索空間內(nèi)

式中 rand(0～1) 為0～1 之間的隨機(jī)實(shí)數(shù)。

2)搜索過程

所有個(gè)體在一個(gè)搜索步內(nèi)行走T 小步，搜索到T 個(gè)新的位置。搜索過程中，目標(biāo)函數(shù)的適應(yīng)度記作

式中 fk為個(gè)體k 搜索到的T 個(gè)新位置中，對(duì)應(yīng)的目標(biāo)函數(shù)最佳值。信息素的定義如下

式中 min(fk)為所有個(gè)體中找到的最佳適應(yīng)值。靈敏度的定義如下

式中 Smax為Smin靈敏度的最大和最小值，Pmax和Pmin為信息素的最大和最小值，并規(guī)定Smax=Pmax，Smin=Pmin;一個(gè)搜索步完成后，確定下一個(gè)搜索步，即下一次迭代的起始點(diǎn)

式中 Xhk為個(gè)體k 在搜索步T 內(nèi)搜索到的最佳位置。

3)終止判斷

FS 算法的判斷標(biāo)準(zhǔn)有三種:

a.達(dá)到全局最優(yōu)解:fmin＜fopt

b.當(dāng)前迭代數(shù)g 大于最大迭代次數(shù)Gmax:g ＞Gmax

c.上述條件滿足其中之一即可。

目標(biāo)函數(shù)的獲得:

由未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離可得

其中xi，yi分別信標(biāo)節(jié)點(diǎn)i 的x，y 坐標(biāo)，di為未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i 的距離。由上式可得

目標(biāo)函數(shù)為

其中，wi為權(quán)值，n 為信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)。

3 仿真結(jié)果與分析

為了驗(yàn)證改進(jìn)算法的有效性，采用OMNeT++進(jìn)行仿真，仿真結(jié)果導(dǎo)入到Matlab 中進(jìn)行提取和分析。仿真面積是400m×400 m 的正方形區(qū)域，節(jié)點(diǎn)間的通信半徑為100 m，未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)在仿真區(qū)域內(nèi)隨機(jī)分布，平均誤差作為評(píng)定定位精度的標(biāo)準(zhǔn)，其公式如下

自由搜索算法的參數(shù)設(shè)定:種群包含的個(gè)體數(shù)量m=60，最大迭代次數(shù)Gmax=600，搜索小步總數(shù)T=60，搜索半徑R=0.1 m，x，y 坐標(biāo)的搜索范圍均為0～400 m。

3.1 算法穩(wěn)定性能仿真結(jié)果

為了得到更加合理、接近于實(shí)際的仿真數(shù)據(jù)，對(duì)100 個(gè)傳感器節(jié)點(diǎn)其中信標(biāo)節(jié)點(diǎn)比例為5%的定位進(jìn)行仿真22 次。

從圖2 可得出，傳統(tǒng)的DV-Hop 算法在仿真次數(shù)小于10 次時(shí)，誤差的波動(dòng)較大，在仿真次數(shù)大于10 次后，雖相對(duì)穩(wěn)定但也有小幅度的波動(dòng)。而改進(jìn)的DV-Hop 算法則一直處在比較穩(wěn)定的狀態(tài)。經(jīng)仿真數(shù)據(jù)計(jì)算可得，傳統(tǒng)的DV-Hop 算法的均方差為4.36，改進(jìn)后的均方差為1.35。改進(jìn)后的節(jié)點(diǎn)的定位在穩(wěn)定性能上要優(yōu)于原始的DV-Hop算法。

圖2 仿真次數(shù)對(duì)定位精度的影響Fig 2 Effect of simulation numbers on positioning precision

3.2 算法在精度上的仿真結(jié)果

為了驗(yàn)證改進(jìn)后算法在精度上的提高，對(duì)100 個(gè)傳感器節(jié)點(diǎn)進(jìn)行仿真，傳統(tǒng)的DV-Hop 算法與改進(jìn)后的DV-Hop算法誤差對(duì)比圖如圖3 所示。

圖3 不同信標(biāo)比例下的定位誤差Fig 3 Localization error of different beacon ratio

從上圖得出，無論上傳統(tǒng)的DV-Hop 算法還是改進(jìn)的DV-Hop 算法在整體上都是隨著信標(biāo)比例的增大，誤差會(huì)越來越小。傳統(tǒng)DV-Hop 算法在信標(biāo)比例大于15%后，誤差減小的幅度越來越小。改進(jìn)后的DV-Hop 算法在誤差會(huì)隨著信標(biāo)比例的增多而平穩(wěn)下降，且在信標(biāo)比例較小時(shí)，改進(jìn)的DV-Hop 算法的優(yōu)勢表現(xiàn)的更加明顯。

圖4 節(jié)點(diǎn)個(gè)數(shù)對(duì)定位精度的影響Fig 4 Effect of node numbers on localization precision

由圖4 可得，相較于傳統(tǒng)的DV-Hop 算法，改進(jìn)的算法在不同節(jié)點(diǎn)數(shù)目下的平均誤差都普遍減小。其中在節(jié)點(diǎn)個(gè)數(shù)為240 時(shí)，改進(jìn)后的DV-Hop 算法在精度上提高了15.3%，說明了改進(jìn)后的DV-Hop 算法在提高算法精度上有了很大提高。

4 結(jié) 論

針對(duì)傳統(tǒng)的DV-Hop 算法定位精度較低、算法穩(wěn)定不高的缺點(diǎn)，本文提出了用RSSI 測距增加信標(biāo)的改進(jìn)方法，在不增加節(jié)點(diǎn)能耗的基礎(chǔ)上，提高了算法的精度，并且用自由搜索算法取代了原來誤差較大的三邊測量法，自由搜索算法具有較快的全局收斂性和較強(qiáng)的自適應(yīng)性能力，恰好符合了DV-Hop 算法的定位要求，仿真結(jié)果表明:改進(jìn)后的定位算法在定位穩(wěn)定性上有了明顯的提高，相較于傳統(tǒng)的DV-Hop 算法，改進(jìn)的DV-Hop 算法性能穩(wěn)定，其定位誤差率減小了13.5%左右。

［1］ 方光偉.基于OMNeT+ +平臺(tái)Gossiping 協(xié)議的仿真實(shí)現(xiàn)［J］.科技信息，2010(22):208－209.

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

［3］ 楊石磊，樊曉平，劉少強(qiáng)，等.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop 定位算法［J］.計(jì)算機(jī)測量與控制，2008，16(9):1356－1358.

［4］ 劉 杰，董淑福，溫 東，等.基于移動(dòng)信標(biāo)的改進(jìn)DV-Hop算法［J］.傳感器與微系統(tǒng)，2013，32(5):142－145.

［5］ Penev K，Littlefair G.Free search—A comparative analysis［J］.Information Sciences，2005，172(1/2):173－193.

［6］ 周 暉.自由搜索算法及其在傳感器網(wǎng)絡(luò)中的應(yīng)用［D］.上海:東華大學(xué)，2010.

［7］ Pottie G J，Kaiser W J.Wireless integrated sensor networks［J］.Communications of the ACM，2000，43(5):51－58.