董錚 張其林 吳中博 吳繼廣
摘要:針對(duì)無(wú)線傳感器網(wǎng)絡(luò)算法定位精度不高的問(wèn)題,提出一種定位算法(GADO),該算法將動(dòng)力學(xué)中進(jìn)化計(jì)算和遺傳算法中迭代優(yōu)選相結(jié)合。用GADO算法求解網(wǎng)絡(luò)信標(biāo)節(jié)點(diǎn)與經(jīng)典的DV-hop定位算法、遺傳算法進(jìn)行對(duì)比,改進(jìn)的算法定位誤差明顯減少,精度更好。
關(guān)鍵詞:動(dòng)力學(xué);遺傳算法;定位算法;精度
中圖分類(lèi)號(hào):TP391
文獻(xiàn)標(biāo)志碼:A
文章編號(hào):1006-8228(2017)01-27-03
0.引言
隨著數(shù)據(jù)業(yè)務(wù)的快速發(fā)展,人們對(duì)目標(biāo)定位與導(dǎo)航的需求日益增長(zhǎng)。定位領(lǐng)域吸引了越來(lái)越多的科技工作者的廣泛關(guān)注與深入研究。
無(wú)線傳感器網(wǎng)絡(luò)的定位,可以簡(jiǎn)單地描述為:用已知數(shù)量的節(jié)點(diǎn)來(lái)計(jì)算出未知節(jié)點(diǎn)的距離信息。根據(jù)定位是否需要對(duì)節(jié)點(diǎn)問(wèn)的距離進(jìn)行測(cè)量,可以分為基于測(cè)距的定位算法和非測(cè)距的定位算法;根據(jù)節(jié)點(diǎn)位置信息表達(dá)的形式,分為絕對(duì)定位算法和相對(duì)定位算法;根據(jù)網(wǎng)絡(luò)中位置節(jié)點(diǎn)的定位狀態(tài)的不同,分為靜止節(jié)點(diǎn)定位和移動(dòng)節(jié)點(diǎn)輔助定位。其中,免距離測(cè)量的DV-Hop算法的定位技術(shù)只利用網(wǎng)絡(luò)內(nèi)部的連通性就可以實(shí)現(xiàn)未知節(jié)點(diǎn)的定位方法,已受到廣大學(xué)者的重視。
1.DV-Hop算法描述
1.1算法實(shí)現(xiàn)過(guò)程
DV-Hop算法主要由以下三個(gè)階段組成。
(1)利用典型的距離矢量路由協(xié)議,使網(wǎng)絡(luò)所有定位節(jié)點(diǎn)獲得參考節(jié)點(diǎn)跳數(shù)信息。
其中(xi,yi)為第j個(gè)參考節(jié)點(diǎn)的位置,hj為第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)距離后,使用三邊或多邊測(cè)量定位。因其采用簡(jiǎn)單的平均單跳距離和最小跳數(shù)信息來(lái)估計(jì)節(jié)點(diǎn)問(wèn)的距離。偏差較大的節(jié)點(diǎn)距離參與定位過(guò)程計(jì)算,會(huì)引入更大的誤差,使得定位精度大大降低,這也是其算法不足之處。
2.改進(jìn)的遺傳優(yōu)化算法
遺傳算法是以群體解為起點(diǎn),通過(guò)選擇的方式選取具有較高適應(yīng)度的個(gè)體再次進(jìn)入循環(huán)圈,而被選擇的個(gè)體再經(jīng)過(guò)交叉產(chǎn)生新的個(gè)體,變異操作用于保持種群的多樣性。通過(guò)新的群體不斷替代舊的群體的進(jìn)化過(guò)程,實(shí)現(xiàn)群體適應(yīng)度值的提高。
動(dòng)力學(xué)算法是受復(fù)雜系統(tǒng)自組織臨界生物演化模型發(fā)展而來(lái)的一種自組織優(yōu)化算法,選擇當(dāng)前解中適應(yīng)度最差的變量及其相互關(guān)聯(lián)的變量進(jìn)行變異,從而使整個(gè)優(yōu)化系統(tǒng)向自組織臨界狀態(tài)演化。
普通遺傳算法只是針對(duì)無(wú)約束問(wèn)題,需要的種群多,收斂速度慢。對(duì)于一般為有約束優(yōu)化的,設(shè)計(jì)問(wèn)題需進(jìn)行轉(zhuǎn)換。為解決這一問(wèn)題,把動(dòng)力學(xué)中表現(xiàn)的局部?jī)?yōu)化能力與普通遺傳算法的全局搜索功能相結(jié)合,提出GADO算法(dynamization optimization and geneticalgorithm),其實(shí)質(zhì)就是尋找未知節(jié)點(diǎn)與已知節(jié)點(diǎn)實(shí)際距離與估計(jì)距離的最小誤差,達(dá)到對(duì)節(jié)點(diǎn)的準(zhǔn)確估計(jì)。
2.2 GADO算法實(shí)現(xiàn)步驟
針對(duì)傳統(tǒng)文獻(xiàn)[4]中計(jì)算每跳估算粒度太粗,提出以下算法。
(1)網(wǎng)絡(luò)初始化,其參數(shù)變量有以下。
SW:監(jiān)測(cè)區(qū)域邊長(zhǎng)
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)判斷對(duì)新解是否變異,判斷條件為pi (7)由最佳個(gè)體和新生個(gè)體形成與原始規(guī)模相等的新一代群體節(jié)點(diǎn)。 重復(fù)(3)-(7)步驟直至平均適度趨于穩(wěn)定。 3.仿真評(píng)價(jià) 為檢驗(yàn)GADO算法的性能指標(biāo),將傳統(tǒng)文獻(xiàn)Dv-hop算法、文獻(xiàn)遺傳GA算法和GADO算法在Matlab7.11平臺(tái)進(jìn)行仿真對(duì)比分析。其模型參數(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算法在平均定位誤差和覆蓋率作為評(píng)價(jià)指標(biāo),并與文獻(xiàn)[4-5]作對(duì)比(為保證實(shí)驗(yàn)結(jié)果精確性,性能仿真都是100次的仿真結(jié)果)。 3.1網(wǎng)絡(luò)連通度對(duì)精度影響 圖1為傳統(tǒng)DV-hop定位算法、遺傳算法和GADO算法的仿真結(jié)果,從圖1可以看出,當(dāng)連通為12時(shí),三種算法誤差都會(huì)降低,這時(shí)已知節(jié)點(diǎn)都能較好定位未知節(jié)點(diǎn),但GADO算法明顯優(yōu)于其他兩種算法,而隨著連通度增加,相隔跳數(shù)的估計(jì)距離出現(xiàn)誤差,因此精度都有所下降,但GADO算法其下降幅度較為緩慢,這是由于其算法對(duì)節(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ù)目對(duì)定位精度的影響 圖2為三種算法中的已知節(jié)點(diǎn)比例對(duì)定位誤差的影響,從中看出,隨著節(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ù)目對(duì)覆蓋率的影響 從圖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é)束語(yǔ) 為提高節(jié)點(diǎn)定位精度,在不增加網(wǎng)絡(luò)通信開(kāi)銷(xiāo)的前提下,提出一種基于GADO的無(wú)線網(wǎng)絡(luò)定位算法。對(duì)傳統(tǒng)算法進(jìn)行優(yōu)化修正,利用其算法獨(dú)特優(yōu)勢(shì)對(duì)節(jié)點(diǎn)進(jìn)行優(yōu)選,結(jié)合遺傳算法和動(dòng)力學(xué)算法各自優(yōu)缺點(diǎn),相互交叉,其算法定位效果更優(yōu),但由于算法復(fù)雜性較高,響應(yīng)時(shí)間較長(zhǎng),下—步將繼續(xù)改進(jìn)。