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

童軒等

摘要：許多無線傳感器網(wǎng)絡(luò)定位算法已經(jīng)被提出來提供每個節(jié)點的位置信息，可將這些定位算法分為兩類：基于距離的和距離無關(guā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é)點定位算法所采用的技術(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é)點距錨節(jié)點的最小跳數(shù)與未知節(jié)點的平均每跳距離的乘積來表示未知節(jié)點到錨節(jié)點的距離，然后通過極大似然估計法得出未知節(jié)點的坐標(biāo)。

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

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

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

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

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

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

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

3 算法仿真實驗及分析

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

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

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

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

4 結(jié)語

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