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

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

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

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

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

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

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

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