DV—Hop算法及改進(jìn)

1、傳感網(wǎng)DV-Hop定位算法研究與改進(jìn)Part1項(xiàng) 目 背 景01010202是一種全新的信息獲取和處理技術(shù),可以自組織網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),節(jié)點(diǎn)間通過(guò)協(xié)同工作能夠?qū)崟r(shí)監(jiān)測(cè)，感知和采集各種環(huán)境或監(jiān)測(cè)對(duì)象的信息，并對(duì)其進(jìn)行處理。是無(wú)線傳感器網(wǎng)絡(luò)眾多研究領(lǐng)域中的核心技術(shù)之一，是無(wú)線傳感器網(wǎng)絡(luò)用于目標(biāo)監(jiān)測(cè)、目標(biāo)識(shí)別以及目標(biāo)跟蹤等應(yīng)用的支撐。無(wú)線傳感器網(wǎng)絡(luò)及節(jié)點(diǎn)定位無(wú)線傳感器網(wǎng)絡(luò)（WSN）節(jié)點(diǎn)定位技術(shù)0303定位算法從定位手段上分有兩大類，基于測(cè)距算法(range-based)和無(wú)需測(cè)距算法(range-free)。雖然基于測(cè)距的算法能夠?qū)崿F(xiàn)精確定位，但對(duì)無(wú)線傳感器節(jié)點(diǎn)的硬件要求高。出于硬件成本、能耗等考慮，人

2、們提出了無(wú)需測(cè)距算法，如質(zhì)心算法、DV-Hop 算法、Amorphous 算法、APIT 算法等，不需要測(cè)量節(jié)點(diǎn)間的絕對(duì)距離或方位，可降低對(duì)節(jié)點(diǎn)硬件的要求，但定位誤差也將相應(yīng)有所增加。定位技術(shù)現(xiàn)狀DV-Hop 算法是由算法是由D.Niculescu和和B.Nath等人提出的。等人提出的。DV-Hop 定位算法的原理與經(jīng)典的距離矢定位算法的原理與經(jīng)典的距離矢量路由算法比較相似。在量路由算法比較相似。在DV-Hop算法中，錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播一個(gè)信標(biāo)，信標(biāo)中包含有此錨節(jié)點(diǎn)算法中，錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播一個(gè)信標(biāo)，信標(biāo)中包含有此錨節(jié)點(diǎn)的位置信息和一個(gè)初始值為的位置信息和一個(gè)初始值為1的表示跳數(shù)的參數(shù)。此信標(biāo)在網(wǎng)

3、絡(luò)中被以泛洪的方式傳播出去，信的表示跳數(shù)的參數(shù)。此信標(biāo)在網(wǎng)絡(luò)中被以泛洪的方式傳播出去，信標(biāo)每次被轉(zhuǎn)發(fā)時(shí)跳數(shù)都增加標(biāo)每次被轉(zhuǎn)發(fā)時(shí)跳數(shù)都增加1。接收節(jié)點(diǎn)在它收到的關(guān)于某一個(gè)錨節(jié)點(diǎn)的所有信標(biāo)中保存具有最。接收節(jié)點(diǎn)在它收到的關(guān)于某一個(gè)錨節(jié)點(diǎn)的所有信標(biāo)中保存具有最小跳數(shù)值的信標(biāo)，丟棄具有較大跳數(shù)值的同一錨節(jié)點(diǎn)的信標(biāo)。通過(guò)這一機(jī)制，網(wǎng)絡(luò)中所有小跳數(shù)值的信標(biāo)，丟棄具有較大跳數(shù)值的同一錨節(jié)點(diǎn)的信標(biāo)。通過(guò)這一機(jī)制，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都節(jié)點(diǎn)都獲得了到每一個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值。獲得了到每一個(gè)錨節(jié)點(diǎn)的最小跳數(shù)值。為了將跳數(shù)值轉(zhuǎn)換成物理距離，系統(tǒng)需要估計(jì)網(wǎng)絡(luò)中平均每跳的距離。錨節(jié)點(diǎn)具有到網(wǎng)絡(luò)內(nèi)為了將跳數(shù)值轉(zhuǎn)換成物理距離，系

4、統(tǒng)需要估計(jì)網(wǎng)絡(luò)中平均每跳的距離。錨節(jié)點(diǎn)具有到網(wǎng)絡(luò)內(nèi)部其他錨節(jié)點(diǎn)的跳數(shù)值以及這些錨節(jié)點(diǎn)的位置信息，因此錨節(jié)點(diǎn)可以通過(guò)計(jì)算得到距其他錨節(jié)點(diǎn)部其他錨節(jié)點(diǎn)的跳數(shù)值以及這些錨節(jié)點(diǎn)的位置信息，因此錨節(jié)點(diǎn)可以通過(guò)計(jì)算得到距其他錨節(jié)點(diǎn)的實(shí)際距離。經(jīng)過(guò)計(jì)算，一個(gè)錨節(jié)點(diǎn)得到網(wǎng)絡(luò)的平均每跳距離，并將此估計(jì)值廣播到網(wǎng)絡(luò)中，稱的實(shí)際距離。經(jīng)過(guò)計(jì)算，一個(gè)錨節(jié)點(diǎn)得到網(wǎng)絡(luò)的平均每跳距離，并將此估計(jì)值廣播到網(wǎng)絡(luò)中，稱作校正值。任何節(jié)點(diǎn)一旦接收到此校正值，就可以估計(jì)自己到這個(gè)錨節(jié)點(diǎn)的距離如果一個(gè)節(jié)點(diǎn)能作校正值。任何節(jié)點(diǎn)一旦接收到此校正值，就可以估計(jì)自己到這個(gè)錨節(jié)點(diǎn)的距離如果一個(gè)節(jié)點(diǎn)能夠獲得到夠獲得到3個(gè)以上錨節(jié)點(diǎn)的估計(jì)距離個(gè)以上

5、錨節(jié)點(diǎn)的估計(jì)距離，DV-Hop算法與基于測(cè)距算法具有相似之處，就是都需要獲算法與基于測(cè)距算法具有相似之處，就是都需要獲得未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，但是得未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，但是DV-Hop 獲得距離的方法是通過(guò)網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)信息的計(jì)算而獲得距離的方法是通過(guò)網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)信息的計(jì)算而不是通過(guò)無(wú)線電波信號(hào)的測(cè)量。不是通過(guò)無(wú)線電波信號(hào)的測(cè)量。DV-Hop算法簡(jiǎn)介DV-Hop算法流程泛洪各節(jié)點(diǎn)收集最小跳數(shù)信標(biāo)節(jié)點(diǎn)計(jì)算平均每跳距離未知節(jié)點(diǎn)獲取最近信標(biāo)節(jié)點(diǎn)的平均每跳距離未知節(jié)點(diǎn)用最小二乘法估算位置未知節(jié)點(diǎn)估算到信標(biāo)節(jié)點(diǎn)的距離Part2研 究 概 況DV-Hop算法的誤差分析由于傳感器節(jié)點(diǎn)隨機(jī)分布和廣播分

6、組過(guò)程中可能存在沖突等因素，節(jié)點(diǎn)得到的到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)存在有一定偏差，且跳數(shù)越多，偏差越大。1 1在信標(biāo)節(jié)點(diǎn)估算平均每跳距離時(shí)，所利用的是除本節(jié)點(diǎn)外所有其他信標(biāo)節(jié)點(diǎn)，所以得到的是全網(wǎng)絡(luò)范圍內(nèi)的平均每跳距離，不能反映本信標(biāo)節(jié)點(diǎn)局部范圍內(nèi)的網(wǎng)絡(luò)分布情況。2 2位置節(jié)點(diǎn)在最后階段估算自身位置時(shí)，利用最近的信標(biāo)節(jié)點(diǎn)的平均每跳距離，不能反映出該未知節(jié)點(diǎn)局部范圍內(nèi)的網(wǎng)絡(luò)分布情況。3 31利用全部信標(biāo)節(jié)點(diǎn)的平均每跳距離求平均作為標(biāo)準(zhǔn)2設(shè)置跳數(shù)閥值，篩選對(duì)未知節(jié)點(diǎn)影響最大的信標(biāo)節(jié)點(diǎn)3采取加權(quán)利用信標(biāo)節(jié)點(diǎn)的平均每跳距離4Matlab自動(dòng)隨機(jī)生成無(wú)線傳感器拓?fù)浞抡娓倪M(jìn)方案引入加權(quán)系數(shù)引入臨界值臨界值的作用是排

7、除不合法的數(shù)據(jù)或是會(huì)對(duì)結(jié)果產(chǎn)生過(guò)多負(fù)面影響的數(shù)據(jù)。引入臨界值的好處是使結(jié)果更加精確，符合實(shí)際。臨界值即為跳數(shù)。在定位過(guò)程中，未知節(jié)點(diǎn)A利用距離其最近的三個(gè)信標(biāo)節(jié)點(diǎn)的平均每跳距離。然而，當(dāng)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)間跳數(shù)很多，即認(rèn)為此信標(biāo)節(jié)點(diǎn)距離未知節(jié)點(diǎn)很遠(yuǎn)，對(duì)其位置的影響甚微或是會(huì)對(duì)未知節(jié)點(diǎn)的最終位置估計(jì)產(chǎn)生負(fù)面影響，此時(shí)，可排除此信標(biāo)節(jié)點(diǎn)參與未知節(jié)點(diǎn)的定位。Part3成 果 展 示平均誤差： 3.3247m平均平均誤差： 3.1m改進(jìn)前01020304050607080901000102030405060708090100* 紅 色 信 標(biāo) 節(jié) 點(diǎn) . 黑 色 未 知 節(jié) 點(diǎn)01020304050607080900123456每 個(gè) 未 知 節(jié) 點(diǎn) 的 誤 差平均誤差： 2.5354m平均平均誤差： 2.6m改進(jìn)后01020304050607080901000102030405060708090100* 紅 色 信 標(biāo) 節(jié) 點(diǎn) . 黑 色 未 知 節(jié) 點(diǎn)010203040506070809000.511.522.533.544.55每 個(gè) 未 知 節(jié) 點(diǎn) 的 誤 差1 1引入加權(quán)系數(shù)，突出錨節(jié)點(diǎn)在定位過(guò)程中的作用，以及最近錨節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的定位影響程度。2 2算法改進(jìn)靈活