童軒等

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

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

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

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

1 DV-Hop算法缺陷分析

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

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

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

2 改進DV-Hop算法

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

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

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

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

3 算法仿真實驗及分析

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

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

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

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

4 結語

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

參考文獻

[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)絡Range Free自身定位機制與算法[J].計算機工程與應用，2004，（23）.

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

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

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

（責任編輯：陳 倩）