改進的遺傳優化算法在節點定位中的應用

董錚　張其林　吳中博　吳繼廣

摘要：針對無線傳感器網絡算法定位精度不高的問題，提出一種定位算法（GADO），該算法將動力學中進化計算和遺傳算法中迭代優選相結合。用GADO算法求解網絡信標節點與經典的DV-hop定位算法、遺傳算法進行對比，改進的算法定位誤差明顯減少，精度更好。

關鍵詞：動力學；遺傳算法；定位算法；精度

中圖分類號：TP391

文獻標志碼：A

文章編號：1006-8228（2017）01-27-03

0.引言

隨著數據業務的快速發展，人們對目標定位與導航的需求日益增長。定位領域吸引了越來越多的科技工作者的廣泛關注與深入研究。

無線傳感器網絡的定位，可以簡單地描述為：用已知數量的節點來計算出未知節點的距離信息。根據定位是否需要對節點問的距離進行測量，可以分為基于測距的定位算法和非測距的定位算法；根據節點位置信息表達的形式，分為絕對定位算法和相對定位算法；根據網絡中位置節點的定位狀態的不同，分為靜止節點定位和移動節點輔助定位。其中，免距離測量的DV-Hop算法的定位技術只利用網絡內部的連通性就可以實現未知節點的定位方法，已受到廣大學者的重視。

1.DV-Hop算法描述

1.1算法實現過程

DV-Hop算法主要由以下三個階段組成。

（1）利用典型的距離矢量路由協議，使網絡所有定位節點獲得參考節點跳數信息。

其中（x_i，y_i）為第j個參考節點的位置，h_j為第j個參考節點到第i個參考節點的跳數，將其結果作為一個校正值廣播至網絡中。當待定位節點獲得三個或更多參考節點距離后，使用三邊或多邊測量定位。因其采用簡單的平均單跳距離和最小跳數信息來估計節點問的距離。偏差較大的節點距離參與定位過程計算，會引入更大的誤差，使得定位精度大大降低，這也是其算法不足之處。

2.改進的遺傳優化算法

遺傳算法是以群體解為起點，通過選擇的方式選取具有較高適應度的個體再次進入循環圈，而被選擇的個體再經過交叉產生新的個體，變異操作用于保持種群的多樣性。通過新的群體不斷替代舊的群體的進化過程，實現群體適應度值的提高。

動力學算法是受復雜系統自組織臨界生物演化模型發展而來的一種自組織優化算法，選擇當前解中適應度最差的變量及其相互關聯的變量進行變異，從而使整個優化系統向自組織臨界狀態演化。

普通遺傳算法只是針對無約束問題，需要的種群多，收斂速度慢。對于一般為有約束優化的，設計問題需進行轉換。為解決這一問題，把動力學中表現的局部優化能力與普通遺傳算法的全局搜索功能相結合，提出GADO算法（dynamization optimization and geneticalgorithm），其實質就是尋找未知節點與已知節點實際距離與估計距離的最小誤差，達到對節點的準確估計。

2.2 GADO算法實現步驟

針對傳統文獻[4]中計算每跳估算粒度太粗，提出以下算法。

（1）網絡初始化，其參數變量有以下。

SW：監測區域邊長

NN：定義節點個數

CD：定義通信距離

AL（X，Y）：定義節點坐標矩陣（包括橫坐際，縱坐標）

（2）在初始t時刻將節點空間等分。

（5）將得到的優良節點中，隨機選擇兩個相互獨立的個體節點進行雜交，產生新解。

（6）判斷對新解是否變異，判斷條件為p_i

（7）由最佳個體和新生個體形成與原始規模相等的新一代群體節點。

重復（3）-（7）步驟直至平均適度趨于穩定。

3.仿真評價

為檢驗GADO算法的性能指標，將傳統文獻Dv-hop算法、文獻遺傳GA算法和GADO算法在Matlab7.11平臺進行仿真對比分析。其模型參數如下。

（1）在100*100的區域內布撒節點；

（2）節點通訊半徑均取50m；

（3）所有節點坐標用隨機函數分布；

（4）節點比例為0.03～0.15。

將GADO算法及DV-hop算法在平均定位誤差和覆蓋率作為評價指標，并與文獻[4-5]作對比（為保證實驗結果精確性，性能仿真都是100次的仿真結果）。

3.1網絡連通度對精度影響

圖1為傳統DV-hop定位算法、遺傳算法和GADO算法的仿真結果，從圖1可以看出，當連通為12時，三種算法誤差都會降低，這時已知節點都能較好定位未知節點，但GADO算法明顯優于其他兩種算法，而隨著連通度增加，相隔跳數的估計距離出現誤差，因此精度都有所下降，但GADO算法其下降幅度較為緩慢，這是由于其算法對節點進行優選，舍棄一些平均距離差的節點。本文算法較文獻[4]Dv-hop算法而言，整體平均誤差降低8%，比文獻[5]遺傳算法降低5.43%。

3.2節點數目對定位精度的影響

圖2為三種算法中的已知節點比例對定位誤差的影響，從中看出，隨著節點數目增加，其各自誤差均有所提高，其原因是網絡連通度提高，算法精度均有所提高，但GADO算法始終優于傳統算法，較文獻Dv-hop算法，整體平均誤差降低12.6%，比文獻遺傳算法降低4.6%。

3.3節點數目對覆蓋率的影響

從圖3可以看出，當節點數目500，已知節點個數在20-35內變化時，節點比率與網絡完整率成正比率關系，而且GADO算法明顯優于其他算法。在節點比率小時，GADO算法顯示出覆蓋率較大的特性，而隨著節點比率增大，與DV-hop算法、GA算法逐漸趨于一致。這也與實際情況相符。并且覆蓋比率隨已知節點個數整體比文獻[4]提高了11.3%，比文獻[5]遺傳算法提高了2.2%。

4.結束語

為提高節點定位精度，在不增加網絡通信開銷的前提下，提出一種基于GADO的無線網絡定位算法。對傳統算法進行優化修正，利用其算法獨特優勢對節點進行優選，結合遺傳算法和動力學算法各自優缺點，相互交叉，其算法定位效果更優，但由于算法復雜性較高，響應時間較長，下—步將繼續改進。