改進(jìn)的遺傳優(yōu)化算法在節(jié)點(diǎn)定位中的應(yīng)用

董錚　張其林　吳中博　吳繼廣

摘要：針對無線傳感器網(wǎng)絡(luò)算法定位精度不高的問題，提出一種定位算法（GADO），該算法將動力學(xué)中進(jìn)化計(jì)算和遺傳算法中迭代優(yōu)選相結(jié)合。用GADO算法求解網(wǎng)絡(luò)信標(biāo)節(jié)點(diǎn)與經(jīng)典的DV-hop定位算法、遺傳算法進(jìn)行對比，改進(jìn)的算法定位誤差明顯減少，精度更好。

關(guān)鍵詞：動力學(xué)；遺傳算法；定位算法；精度

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

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

0.引言

隨著數(shù)據(jù)業(yè)務(wù)的快速發(fā)展，人們對目標(biāo)定位與導(dǎo)航的需求日益增長。定位領(lǐng)域吸引了越來越多的科技工作者的廣泛關(guān)注與深入研究。

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

1.DV-Hop算法描述

1.1算法實(shí)現(xiàn)過程

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

（1）利用典型的距離矢量路由協(xié)議，使網(wǎng)絡(luò)所有定位節(jié)點(diǎn)獲得參考節(jié)點(diǎn)跳數(shù)信息。

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

2.改進(jìn)的遺傳優(yōu)化算法

遺傳算法是以群體解為起點(diǎn)，通過選擇的方式選取具有較高適應(yīng)度的個(gè)體再次進(jìn)入循環(huán)圈，而被選擇的個(gè)體再經(jīng)過交叉產(chǎn)生新的個(gè)體，變異操作用于保持種群的多樣性。通過新的群體不斷替代舊的群體的進(jìn)化過程，實(shí)現(xiàn)群體適應(yīng)度值的提高。

動力學(xué)算法是受復(fù)雜系統(tǒng)自組織臨界生物演化模型發(fā)展而來的一種自組織優(yōu)化算法，選擇當(dāng)前解中適應(yīng)度最差的變量及其相互關(guān)聯(lián)的變量進(jìn)行變異，從而使整個(gè)優(yōu)化系統(tǒng)向自組織臨界狀態(tài)演化。

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

2.2 GADO算法實(shí)現(xiàn)步驟

針對傳統(tǒng)文獻(xiàn)[4]中計(jì)算每跳估算粒度太粗，提出以下算法。

（1）網(wǎng)絡(luò)初始化，其參數(shù)變量有以下。

SW：監(jiān)測區(qū)域邊長

NN：定義節(jié)點(diǎn)個(gè)數(shù)

CD：定義通信距離

AL（X，Y）：定義節(jié)點(diǎn)坐標(biāo)矩陣（包括橫坐際，縱坐標(biāo)）

（2）在初始t時(shí)刻將節(jié)點(diǎn)空間等分。

（5）將得到的優(yōu)良節(jié)點(diǎn)中，隨機(jī)選擇兩個(gè)相互獨(dú)立的個(gè)體節(jié)點(diǎn)進(jìn)行雜交，產(chǎn)生新解。

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

（7）由最佳個(gè)體和新生個(gè)體形成與原始規(guī)模相等的新一代群體節(jié)點(diǎn)。

重復(fù)（3）-（7）步驟直至平均適度趨于穩(wěn)定。

3.仿真評價(jià)

為檢驗(yàn)GADO算法的性能指標(biāo)，將傳統(tǒng)文獻(xiàn)Dv-hop算法、文獻(xiàn)遺傳GA算法和GADO算法在Matlab7.11平臺進(jìn)行仿真對比分析。其模型參數(shù)如下。

（1）在100*100的區(qū)域內(nèi)布撒節(jié)點(diǎn)；

（2）節(jié)點(diǎn)通訊半徑均取50m；

（3）所有節(jié)點(diǎn)坐標(biāo)用隨機(jī)函數(shù)分布；

（4）節(jié)點(diǎn)比例為0.03～0.15。

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

3.1網(wǎng)絡(luò)連通度對精度影響

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

3.2節(jié)點(diǎn)數(shù)目對定位精度的影響

圖2為三種算法中的已知節(jié)點(diǎn)比例對定位誤差的影響，從中看出，隨著節(jié)點(diǎn)數(shù)目增加，其各自誤差均有所提高，其原因是網(wǎng)絡(luò)連通度提高，算法精度均有所提高，但GADO算法始終優(yōu)于傳統(tǒng)算法，較文獻(xiàn)Dv-hop算法，整體平均誤差降低12.6%，比文獻(xiàn)遺傳算法降低4.6%。

3.3節(jié)點(diǎn)數(shù)目對覆蓋率的影響

從圖3可以看出，當(dāng)節(jié)點(diǎn)數(shù)目500，已知節(jié)點(diǎn)個(gè)數(shù)在20-35內(nèi)變化時(shí)，節(jié)點(diǎn)比率與網(wǎng)絡(luò)完整率成正比率關(guān)系，而且GADO算法明顯優(yōu)于其他算法。在節(jié)點(diǎn)比率小時(shí)，GADO算法顯示出覆蓋率較大的特性，而隨著節(jié)點(diǎn)比率增大，與DV-hop算法、GA算法逐漸趨于一致。這也與實(shí)際情況相符。并且覆蓋比率隨已知節(jié)點(diǎn)個(gè)數(shù)整體比文獻(xiàn)[4]提高了11.3%，比文獻(xiàn)[5]遺傳算法提高了2.2%。

4.結(jié)束語

為提高節(jié)點(diǎn)定位精度，在不增加網(wǎng)絡(luò)通信開銷的前提下，提出一種基于GADO的無線網(wǎng)絡(luò)定位算法。對傳統(tǒng)算法進(jìn)行優(yōu)化修正，利用其算法獨(dú)特優(yōu)勢對節(jié)點(diǎn)進(jìn)行優(yōu)選，結(jié)合遺傳算法和動力學(xué)算法各自優(yōu)缺點(diǎn)，相互交叉，其算法定位效果更優(yōu)，但由于算法復(fù)雜性較高，響應(yīng)時(shí)間較長，下—步將繼續(xù)改進(jìn)。