使用分簇方式實現(xiàn)對無線傳感器網(wǎng)絡(luò)DV—Hop定位算法的改進(jìn)

童軒等

摘要：許多無線傳感器網(wǎng)絡(luò)定位算法已經(jīng)被提出來提供每個節(jié)點(diǎn)的位置信息，可將這些定位算法分為兩類：基于距離的和距離無關(guān)的?；诰嚯x的定位算法使用點(diǎn)到點(diǎn)的絕對距離估計值或角度估計值來計算位置，而距離無關(guān)的定位算法只利用網(wǎng)絡(luò)連通度等來得到近似的位置信息。文章研究了距離無關(guān)的無線傳感器網(wǎng)絡(luò)定位算法。

關(guān)鍵詞：無線傳感器；網(wǎng)絡(luò)定位算法；分簇方式；DV-Hop算法；質(zhì)心算法；APIT算法 文獻(xiàn)標(biāo)識碼：A

中圖分類號：TP393 文章編號：1009-2374（2015）28-0039-02 DOI：10.13535/j.cnki.11-4406/n.2015.28.019

目前從傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法所采用的技術(shù)手段來看，其可以分為兩大類：基于距離（range-based）的定位算法和距離無關(guān)（range-free）的定位算法，距離無關(guān)的定位算法主要有DV-Hop（Distance Vector-Hop）算法、質(zhì)心算法、APIT（Approximate Point-In-Triangulation Test）算法、Amorphous算法等。

1 DV-Hop算法缺陷分析

美國羅格斯大學(xué)的Dragos Niculescu等人提出了基于距離向量路由和GPS定位的APS（Ad hoc Positioning System）定位系統(tǒng)，DV-Hop（Distance Vector-Hop）定位算法就是其中之一。它的中心思想是：用未知節(jié)點(diǎn)距錨節(jié)點(diǎn)的最小跳數(shù)與未知節(jié)點(diǎn)的平均每跳距離的乘積來表示未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，然后通過極大似然估計法得出未知節(jié)點(diǎn)的坐標(biāo)。

DV-Hop定位算法在節(jié)點(diǎn)密度較高，節(jié)點(diǎn)分布較均勻的網(wǎng)絡(luò)中可以得到較高的定位精度。但該算法的缺點(diǎn)是當(dāng)節(jié)點(diǎn)密度降低或節(jié)點(diǎn)分布不均勻時，定位精度將會有較大惡化。

DV-Hop雖然實現(xiàn)簡單、易于擴(kuò)展，但其不足之處在于：（1）在信標(biāo)節(jié)點(diǎn)獲得平均每跳距離的計算過程中，由于是以跳段距離近似直線距離，當(dāng)節(jié)點(diǎn)個數(shù)非常少時，定位誤差將會非常大，若一些節(jié)點(diǎn)獲得的信標(biāo)節(jié)點(diǎn)位置不足3個而無法定位，導(dǎo)致定位覆蓋率較低；（2）全網(wǎng)使用統(tǒng)一的平均每跳距離，并不考慮節(jié)點(diǎn)分布密度在各個部分的不同導(dǎo)致的平均每跳距離的不同，從而在較大范圍隨機(jī)分布感知節(jié)點(diǎn)的時候會出現(xiàn)較大誤差。

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

第一，通過采取分簇計算平均每跳距離的方式來使它的值更加貼近于實際。實際應(yīng)用中，在較大范圍內(nèi)隨機(jī)分布信標(biāo)節(jié)點(diǎn)的時候，節(jié)點(diǎn)密度由于地形、隨機(jī)分布性等原因在每塊區(qū)域是不一致的，因而平均每跳距離也是不一樣的，那么平均每跳距離在這樣的情況下就不該取全網(wǎng)范圍內(nèi)所有信標(biāo)節(jié)點(diǎn)的平均每跳距離的平均值，而是應(yīng)該采取將無線傳感器網(wǎng)絡(luò)分簇，逐個算出適用于本簇的平均每跳距離，未知節(jié)點(diǎn)使用簇內(nèi)平均每跳距離，

從而提高未知節(jié)點(diǎn)計算到信標(biāo)節(jié)點(diǎn)的距離的準(zhǔn)確度。

上述算法的具體實現(xiàn)說明：每個節(jié)點(diǎn)都把自己看作簇的中心節(jié)點(diǎn)，跳數(shù)限制若為3跳，對于信標(biāo)節(jié)點(diǎn)而言，它只利用3跳范圍之內(nèi)的其他信標(biāo)節(jié)點(diǎn)進(jìn)行平均每跳距離的計算，對于未知節(jié)點(diǎn)而言，它只利用3跳范圍之內(nèi)的信標(biāo)節(jié)點(diǎn)的平均每跳距離，在收到簇內(nèi)信標(biāo)節(jié)點(diǎn)發(fā)來的平均每跳距離后，未知節(jié)點(diǎn)取它們的平均值作為它自己的平均每跳距離，未知節(jié)點(diǎn)使用最小二乘法計算自身位置的時候，它也是只使用簇內(nèi)信標(biāo)節(jié)點(diǎn)作為參考參數(shù)進(jìn)行計算。這樣的分簇方式只是在計算自身位置時使用，是邏輯上的分簇，并不會實際增加無線傳感器的能量開銷。

第二，吸收使用適用于分簇算法的加權(quán)最小二乘法，由近及遠(yuǎn)的權(quán)值是由大到小的。由于每個未知節(jié)點(diǎn)周圍的信標(biāo)節(jié)點(diǎn)數(shù)是不一樣的，權(quán)值是隨之變化的。在編寫程序時，不能一直像原算法一樣使用固定權(quán)值。算法的matlab仿真實現(xiàn)為：

3 算法仿真實驗及分析

為了檢驗可行性和有效性，本文算法在matlab平臺上進(jìn)行了仿真實驗，并對實驗結(jié)果進(jìn)行了比較分析。在實驗中，節(jié)點(diǎn)分布在1000m×1000m的正方形區(qū)域內(nèi)，有用戶輸入節(jié)點(diǎn)總數(shù)N、信標(biāo)節(jié)點(diǎn)個數(shù)n和節(jié)點(diǎn)通信半徑，程序在該區(qū)域內(nèi)隨機(jī)分布這些節(jié)點(diǎn)。設(shè)所有節(jié)點(diǎn)都處在相同的網(wǎng)絡(luò)環(huán)境下，實驗最終結(jié)果取多次運(yùn)算的平均值。算法的性能主要從平均定位誤差方面進(jìn)行了評估，本文使用的是相對誤差。本文不考慮網(wǎng)絡(luò)不連通的情況。

如圖1，在1000m×1000m的正方形區(qū)域內(nèi)，300個傳感器節(jié)點(diǎn)，其中60個為信標(biāo)節(jié)點(diǎn)，通信半徑為200m的實驗設(shè)置下，進(jìn)行的三輪實驗中，使用分簇方式改進(jìn)算法的平均定位誤差相比原算法降低了大約5倍。

采用分簇方法的DV-Hop算法在應(yīng)用到C型節(jié)點(diǎn)分布和S型節(jié)點(diǎn)分布的無線傳感器網(wǎng)絡(luò)中，效果也是十分明顯的。C型節(jié)點(diǎn)分布和S型節(jié)點(diǎn)分布分別如圖2和圖3所示。

由圖4、圖5給出在通信半徑不同、節(jié)點(diǎn)密度不同、信標(biāo)節(jié)點(diǎn)密度不同的情況下，C型節(jié)點(diǎn)分布和S型節(jié)點(diǎn)分布下，定位誤差的比較結(jié)果，可以看到改進(jìn)后的算法相對原算法平均定位誤差降低了將近9倍。隨著通信半徑的增加，平均定位誤差逐漸減小，隨著節(jié)點(diǎn)密度的增加，平均定位誤差逐漸減小，隨著信標(biāo)節(jié)點(diǎn)比例的增加，平均定位誤差也逐漸減少。

4 結(jié)語

定位精度是評價定位算法的首要指標(biāo)，本文針對DV-Hop定位算法精度不高、不適用于節(jié)點(diǎn)分布不均勻、位置計算方法籠統(tǒng)等缺陷，提出了采用分簇方式的DV-Hop算法，同時融入了適用于分簇方法的加權(quán)最小二乘法來改進(jìn)經(jīng)典DV-Hop算法。該算法無需額外硬件支持，不會有額外的能量開銷，小幅度增加了通信量，適用于實際生產(chǎn)環(huán)境。從仿真結(jié)果來看，本文算法在較大范圍內(nèi)隨機(jī)分布節(jié)點(diǎn)的定位精度要優(yōu)于經(jīng)典DV-Hop算法的定位精度，是可取的改善措施。

參考文獻(xiàn)

[1] Akyildiz L F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks[J].IEEE Communication Magazine，2002，40（8）.

[2] 史龍，王福豹，段渭軍，任豐厚.無線傳感器網(wǎng)絡(luò)Range Free自身定位機(jī)制與算法[J].計算機(jī)工程與應(yīng)用，2004，（23）.

[3] 張媛.基于無線傳感器網(wǎng)絡(luò)定位技術(shù)的研究[D].東北大學(xué)，2008.

[4] Harter A，Hopper A.A distributed location system for the active office[J].IEEE Network，1994，8（1）.

作者簡介：童軒（1994-），男，福建建陽人，南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院學(xué)生，研究方向：網(wǎng)絡(luò)工程。

（責(zé)任編輯：陳 倩）