基于混合人工蜂群策略的改進(jìn)DV-Hop定位算法

江　濤

(重慶工商職業(yè)學(xué)院,重慶 400052)

?

基于混合人工蜂群策略的改進(jìn)DV-Hop定位算法

江濤

(重慶工商職業(yè)學(xué)院,重慶 400052)

摘要:為了減小DV-Hop算法在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中的誤差,提出了一種基于混合人工蜂群算法的改進(jìn)算法。該算法結(jié)合了粒子群算法收斂速度快和蜂群算法搜索能力強(qiáng)的特性,首先通過DV-Hop算法估計(jì)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離,然后采用粒子群算法計(jì)算未知節(jié)點(diǎn)的初始位置,最后利用蜂群算法進(jìn)行迭代求精,從而實(shí)現(xiàn)基于不同距離測(cè)量方法的總體優(yōu)化。仿真結(jié)果表明,改進(jìn)算法的定位精度較DV-Hop算法和基于粒子群的定位算法有明顯改善。

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò);定位;DV-Hop算法;蜂群算法;粒子群算法

位置信息對(duì)于無(wú)線傳感器網(wǎng)絡(luò)的監(jiān)測(cè)活動(dòng)至關(guān)重要,沒有位置信息的監(jiān)測(cè)消息是毫無(wú)意義的[1]。作為大多數(shù)應(yīng)用基礎(chǔ)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù),現(xiàn)有的無(wú)線傳感器網(wǎng)絡(luò)定位算法大體可分為基于測(cè)距和非測(cè)距兩類[2]。前者需要先通過實(shí)際測(cè)量方法獲得節(jié)點(diǎn)間的距離信息或角度信息,再使用三邊測(cè)量法或極大似然估計(jì)法來(lái)計(jì)算節(jié)點(diǎn)的位置;后者無(wú)需實(shí)際測(cè)量,僅根據(jù)網(wǎng)絡(luò)連通度等信息實(shí)現(xiàn)節(jié)點(diǎn)定位。基于測(cè)距的定位方法需要增加額外的硬件設(shè)備和通信量,這樣加大了能耗和成本;而非測(cè)距定位方法無(wú)需額外的硬件設(shè)備,能降低對(duì)節(jié)點(diǎn)硬件的要求,更適合于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用。因此,非測(cè)距定位方法越來(lái)越受到國(guó)內(nèi)外學(xué)者的關(guān)注[3]。

DV-Hop算法是目前最受關(guān)注的定位算法之一,它的優(yōu)點(diǎn)是不受測(cè)距誤差的影響,具有較強(qiáng)的魯棒性,但僅適用于各向同性的均勻網(wǎng)絡(luò),且定位誤差較大[4]。人工蜂群算法(ABC)是由土耳其埃爾吉耶斯大學(xué)Karaboga[8]在2005年提出的一種基于蜜蜂群智能搜索行為的優(yōu)化算法。目前,關(guān)于ABC算法的研究與應(yīng)用還處于初級(jí)階段,但由于其控制參數(shù)少、易于實(shí)現(xiàn)、計(jì)算簡(jiǎn)潔等優(yōu)點(diǎn),已經(jīng)被越來(lái)越多的學(xué)者所關(guān)注。然而對(duì)蜂群算法[8]在無(wú)線傳感器網(wǎng)絡(luò)定位方面的研究還較少,本文在分析蜂群算法原理的基礎(chǔ)上,將蜂群算法與粒子群算法結(jié)合,應(yīng)用到DV-Hop算法的節(jié)點(diǎn)定位階段,以期提高DV-Hop算法的定位精度。

1　算法描述

1.1DV-Hop算法描述

DV-hop算法[4]是由Niculescu等人提出的,其定位過程分為3個(gè)階段:

(1)使用典型的距離矢量交換協(xié)議,通過節(jié)點(diǎn)間的信息交換,使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得與錨節(jié)點(diǎn)之間的跳距,每個(gè)錨節(jié)點(diǎn)根據(jù)式(1)計(jì)算自己的平均每跳距離:

(1)

式(1)中,j為錨節(jié)點(diǎn)i數(shù)據(jù)表中的其他錨節(jié)點(diǎn)號(hào),hopSij為錨節(jié)點(diǎn)i和j之間的跳數(shù)。

(2)每個(gè)錨節(jié)點(diǎn)根據(jù)第1階段中自己計(jì)算的平均跳距采用可控洪泛法廣播至網(wǎng)絡(luò)中,每個(gè)節(jié)點(diǎn)僅接收獲得的第1個(gè)平均跳距,而舍棄所有后來(lái)的信息。

(3)未知節(jié)點(diǎn)根據(jù)上一階段中計(jì)算出來(lái)的估計(jì)距離,利用三邊或多邊定位法計(jì)算估計(jì)坐標(biāo),從而完成定位。

1.2標(biāo)準(zhǔn)粒子群優(yōu)化算法描述

在1995年由Kennedy和Eberhart[9]提出基本粒子群算法后,于1998年,ShiYuhui和Eberhart[10]提出了一種改進(jìn)的粒子群算法,也就是在基本粒子群算法上添加了一個(gè)慣性因子w,用來(lái)調(diào)整上一刻速度對(duì)下一刻速度的影響,同時(shí)也對(duì)全局搜索能力和局部搜索能力起到了一個(gè)平衡作用。下面就是標(biāo)準(zhǔn)PSO算法的更新公式:

(2)

(3)

其中,v表示粒子的速度,X表示粒子的未知,i表示第i個(gè)粒子,w表示慣性因子,c1,c2都是正的加速因子,而r1,r2都是[0,1]之間均勻分布的隨機(jī)數(shù),p表示單個(gè)個(gè)體在歷史上已經(jīng)尋到的最優(yōu)位置,pg表示整個(gè)種群所已尋到的最優(yōu)位置,t表示t時(shí)刻或者說是第t次迭代。

1.3蜂群算法描述

首先,ABC算法生成含有Ns個(gè)解(食物源)的初始蜂群,每個(gè)解Xi是一個(gè)d維的向量;然后,蜜蜂對(duì)所有的食物源進(jìn)行循環(huán)搜索,循環(huán)次數(shù)為C(C=1,2,…,N)。引領(lǐng)蜂首先對(duì)相應(yīng)的食物源(解)進(jìn)行一次鄰域搜索,如果搜索到的食物源(解)的花蜜數(shù)量(適應(yīng)度)優(yōu)于以前的,則用新的食物源位置代替舊的食物源位置,否則保持舊的食物源位置不變。所有的引領(lǐng)蜂完成搜索之后,回到舞蹈區(qū)把食物源上花蜜數(shù)量的信息通過跳搖擺舞傳達(dá)給跟隨蜂。跟隨蜂根據(jù)得到的信息按照概率選擇食物源?；墼蕉嗟氖澄镌?被選擇的概率越大。跟隨蜂選中食物源后,也進(jìn)行一次鄰域搜索,并保留較好的解。ABC算法就是通過如此重復(fù)搜索,最終來(lái)找到最優(yōu)解。式(4)為引領(lǐng)蜂和跟隨蜂進(jìn)行食物源位置更新的公式:

vij=xij+rij(xij-xkj)

(4)

其中:k∈{1,2,…,Ns},j∈{1,2,…,d},這2個(gè)數(shù)都是隨機(jī)選取的,但是k不等于i(k是i鄰域的一個(gè)解);rij∈[-1,1]是一個(gè)隨機(jī)數(shù),它控制小xij鄰域的生成范圍,隨著搜索接近最優(yōu)解,鄰域的范圍會(huì)逐漸減小。

ABC算法中跟隨蜂對(duì)食物源的選擇是通過觀察完引領(lǐng)蜂的搖擺舞來(lái)判斷食物源的收益率,并依據(jù)收益率的大小來(lái)選擇到哪個(gè)食物源采蜜。收益率通過適應(yīng)度值來(lái)表示,選擇概率Pi按照下式確定:

(5)

其中fiti是第i個(gè)解的適應(yīng)度值;Ns是解的個(gè)數(shù)。

在ABC算法中,還有一個(gè)控制參數(shù)limit,它用來(lái)記錄某個(gè)解被更新的次數(shù)。假定某個(gè)解連續(xù)經(jīng)過limit次循環(huán)之后沒有得到改善,表明這個(gè)解陷入局部最優(yōu),那么這個(gè)位置就要被放棄,與這個(gè)解相對(duì)應(yīng)的引領(lǐng)蜂也轉(zhuǎn)變?yōu)閭刹榉洹＜僭O(shè)被放棄的解是xi且j∈{1,2,…,d},那么就由偵查蜂通過式(6)隨機(jī)產(chǎn)生一個(gè)新的解來(lái)代替xi。

(6)

2　改進(jìn)算法

人工蜂群算法在全局和局部搜索精度都要優(yōu)于粒子群算法,然而收斂速度較慢,為了彌補(bǔ)這一缺點(diǎn),結(jié)合粒子群算法收斂速度快得特性,提出在粒子群算法所得到的全局最優(yōu)值作為人工蜂群算法初始蜂群的解,以期加快蜂群算法的收斂速度和搜索精度,同時(shí)可以相對(duì)減少人工蜂群算法的運(yùn)算量,從而得到更優(yōu)的解。

(7)

基于以上分析,提出了基于混合人工蜂群算法的DV-Hop改進(jìn)算法,其主要思想是,先通過DV-Hop算法計(jì)算出平均跳距和未知節(jié)點(diǎn)到錨節(jié)點(diǎn)間的距離,再根據(jù)式(7)通過較少迭代次數(shù)的粒子群算法得出全局最優(yōu)解,并將其作為蜂群算法的初始值,隨后再利用蜂群算法對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行優(yōu)化處理,從而完成最終定位。其主要步驟如下:

(1)確定參數(shù):慣性因子w,迭代次數(shù)t,種群數(shù)量Ng,循環(huán)次數(shù)C以及控制參數(shù)limit;

(2)隨機(jī)產(chǎn)生Np個(gè)粒子的種群;

(3)用式(2)、式(3)對(duì)粒子速度和位置進(jìn)行更新;

(4)通過計(jì)算適應(yīng)度將全局最優(yōu)解pg最為人工蜂群算法的初始解;

(5)根據(jù)式(5)計(jì)算與pg相關(guān)的概率值Pi;

(6)跟隨蜂根據(jù)Pi選擇食物源(解),并根據(jù)式(6)進(jìn)行鄰域搜索產(chǎn)生新解vi,計(jì)算其適應(yīng)度值;

(7)如果vi的值好于pg,則用vi替換pg,否則保留vi不變;

(8)判斷是否要放棄的解,如果存在,則返回步驟(6)產(chǎn)生一個(gè)新解來(lái)代替它;

(9)記錄迄今為止最好的解;

(10)判斷是否滿足循環(huán)終止條件,如滿足輸出最優(yōu)結(jié)果,否則返回步驟(8)。

3　仿真實(shí)驗(yàn)

3.1仿真環(huán)境

本文的實(shí)驗(yàn)在MATLAB平臺(tái)上進(jìn)行,為了驗(yàn)證改進(jìn)算法的性能,設(shè)節(jié)點(diǎn)隨機(jī)布置在150m×150m的網(wǎng)絡(luò)區(qū)域內(nèi);未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的坐標(biāo)隨機(jī)產(chǎn)生;每個(gè)節(jié)點(diǎn)的通信半徑R=25m。設(shè)仿真次數(shù)為k,錨節(jié)點(diǎn)個(gè)數(shù)為m,節(jié)點(diǎn)個(gè)數(shù)為N,定位節(jié)點(diǎn)的真實(shí)坐標(biāo)為(xt,yt),估計(jì)坐標(biāo)為(xe,ye),定義仿真一次時(shí),單個(gè)節(jié)點(diǎn)的定位誤差為erri,整個(gè)網(wǎng)絡(luò)的平均定位誤差為errnetwork,整個(gè)網(wǎng)絡(luò)的平均定位誤差的均方差為σnetwork,則基于k次仿真結(jié)果統(tǒng)計(jì)的歸一化平均定位誤差為

(8)

為了客觀地驗(yàn)證改進(jìn)算法的定位性能,并便于對(duì)傳統(tǒng)DV-Hop算法進(jìn)行比較,在仿真時(shí)作以下設(shè)定:

(1)各次仿真時(shí)的網(wǎng)絡(luò)區(qū)域、節(jié)點(diǎn)總數(shù)、錨節(jié)點(diǎn)總數(shù)、節(jié)點(diǎn)通信半徑等網(wǎng)絡(luò)參數(shù)相同。

(2)統(tǒng)計(jì)的歸一化定位誤差作為算法精度的衡量指標(biāo)[12]

3.2參數(shù)設(shè)置

由于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)受到體積、能量的限制,為了更好地減小為了最大程度減小改進(jìn)蜂群算法的定位誤差及能量消耗,通過MATLAB仿真軟件對(duì)混合人工蜂群(記為HABC)算法在循環(huán)次數(shù)和最終定位性能方面進(jìn)行了仿真驗(yàn)證。設(shè)節(jié)點(diǎn)隨機(jī)分布在一個(gè)無(wú)障礙的150m×150m的正方形區(qū)域內(nèi),網(wǎng)絡(luò)規(guī)模(節(jié)點(diǎn)總數(shù)N)為150,錨節(jié)點(diǎn)比例為10%,每個(gè)節(jié)點(diǎn)具有相同的通信半徑R=25m。假設(shè)所有錨節(jié)點(diǎn)均分布于第1象限,錨節(jié)點(diǎn)坐標(biāo)已知,且已知錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間的距離。

圖1為HABC算法與ABC算法的平均定位誤差隨循環(huán)次數(shù)變化的關(guān)系,可以看出兩種算法隨著循環(huán)次數(shù)的增加平均定位誤差都逐漸趨于0,但是改進(jìn)算法的收斂速度明顯優(yōu)于ABC算法,且具有較強(qiáng)的穩(wěn)定性,在循環(huán)次數(shù)大于7次后,平均定位誤差基本不變。

圖1　循環(huán)次數(shù)與平均定位誤差的關(guān)系

圖2　定位結(jié)果圖

為了進(jìn)一步比較本文所提出的HABC算法的性能。對(duì)PSO算法、ABC算法和HABC算法隨機(jī)獨(dú)立運(yùn)行100次,PSO算法循環(huán)次數(shù)t=7,ABC算法循環(huán)次數(shù)C=7,HABC算法循環(huán)次數(shù)t=1、C=6,其他參數(shù)設(shè)置不變,定位結(jié)果如圖2所示。

由圖2可以看出,HABC算法成功的融合了兩種算法的優(yōu)點(diǎn),克服了他們的不足之處,相比于ABC算法,HABC算法的搜索精度得到很大的提高。在循環(huán)次數(shù)相同,算法計(jì)算量和能量消耗較小的前提下,HABC算法的最差定位誤差值、最優(yōu)定位誤差值分別是PSO算法和ABC算法的5.6%、2.9%和7.8%、8.3%,歸一化平均定位誤差較上述兩種算法分別減小了14.5%和6.8%。

以上結(jié)果分析表明HABC算法沒有引入復(fù)雜的操作,同時(shí)也加快了算法的收斂速度,大大減小了算法的循環(huán)次數(shù)和運(yùn)算量,從而減小了能量的消耗。與此同時(shí),由于引進(jìn)粒子群算法,通信開銷和計(jì)算量有稍微增大,但新算法在定位過程中的搜索精度、收斂速度和魯棒性都明顯優(yōu)ABC算法和PSO算法,從而驗(yàn)證了HABC算法在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方面的優(yōu)越性,下節(jié)將3種算法分別引入到DV-Hop算法的定位階段,參數(shù)設(shè)置保持不變,并通過與傳統(tǒng)DV-Hop算法在定位性能方面的比較,進(jìn)一步驗(yàn)證本文改進(jìn)算法在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方面的性能。

3.3仿真結(jié)果分析

本實(shí)驗(yàn)每次通過1 000次仿真實(shí)驗(yàn)分別計(jì)算傳統(tǒng)DV-Hop算法、文獻(xiàn)[13]提出的基于ABC算法DV-Hop算法(ADV-Hop)及本文提出的基于HABC算法的DV-Hop算法(簡(jiǎn)記HADV-Hop)歸一化的定位精度,從而客觀的分析比較3種算法的定位性能。圖3給出了錨節(jié)點(diǎn)比例在5%～40%變化時(shí),節(jié)點(diǎn)通信半徑R=25 m、節(jié)點(diǎn)總數(shù)為150個(gè)時(shí),由式(8)計(jì)算出的歸一化平均定位誤差變化情況。

圖3　錨節(jié)點(diǎn)比例與歸一化的平均定位誤差關(guān)系

從圖3可以看出:在節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)通信半徑不變的情況下,3種算法的平均定位誤差和均方差都隨著錨節(jié)點(diǎn)比例的增加而減小,并逐漸趨于平穩(wěn);另外,在相同條件下,HDV-Hop的平均定位誤差明顯小于DV-Hop和ADV-Hop,具體的本文改進(jìn)算法HDV-Hop分別比DV-Hop歸一化的平均定位誤差平均減小了35%～38%,較ADV-Hop平均減小了25%～27%。

圖4為15個(gè)錨節(jié)點(diǎn),節(jié)點(diǎn)通信半徑R=25 m,3種算法歸一化平均定位誤差隨節(jié)點(diǎn)總數(shù)變化規(guī)律曲線。從圖4可以看出,在錨節(jié)點(diǎn)不變的情況下,3種定位算法的定位誤差、定位誤差均方差都隨節(jié)點(diǎn)個(gè)數(shù)的增多而逐漸減小,并趨于平穩(wěn)。HDV-Hop的定位誤差較DV-Hop平均減小了34%～36%,較ADV-Hop減小了18%～21%。

圖4　節(jié)點(diǎn)個(gè)數(shù)與歸一化平均定位誤差關(guān)系

從以上的結(jié)果分析中可以看出本文提出的HDV-Hop算法在定位精度方面優(yōu)于傳統(tǒng)DV-Hop算法,說明了將粒子群算法經(jīng)過1次迭代后與人工蜂群算法相結(jié)合可以有效的提高無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的定位精度;相比于ADV-Hop算法,HDV-Hop算法定位誤差也有較大的改善,即驗(yàn)證了本文提出的HABC算法叫ABC算法在定位方面具有較大改善,有效的提高了人工蜂群算法的收斂速度并提高了算法的計(jì)算精度。

4　結(jié)束語(yǔ)

本文在基于人工蜂群算法DV-Hop改進(jìn)算法的基礎(chǔ)上,針對(duì)ADV-Hop算法中人工蜂群算法計(jì)算未知節(jié)點(diǎn)坐標(biāo)時(shí)搜索速度慢精度不高的問題,與粒子群算法相混合,對(duì)人工蜂群算法進(jìn)行了改進(jìn),并在此基礎(chǔ)上結(jié)合DV-Hop算法,對(duì)未知節(jié)點(diǎn)坐標(biāo)的計(jì)算過程進(jìn)行了優(yōu)化求精。在不增加硬件開銷的前提下,提高了定位精度,從而降低了算法的定位誤差。仿真結(jié)果表明,本文改進(jìn)的算法有效的提高了定位的精度及穩(wěn)定性,對(duì)于無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題,是一種簡(jiǎn)單實(shí)用的解決方案。

參考文獻(xiàn):

[1]孫利民,李建中,陳渝,等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005:146-168.

[2]王福豹,史龍,任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5):857-868.

[3]史龍,王福豹,段渭軍,等.無(wú)線傳感器網(wǎng)絡(luò)Range-Free自身定位機(jī)制與算法[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(23):127-130.

[4]Niculescu D,Nath B.Ad-Hoc Positioning System(APS)[A].Proc of the 2001 IEEE Global Telecommunications Conf[C]//San Antonio:IEEE Communications Society,2001:2926-2931.

[5]林金朝,劉海波,李國(guó)軍,等.無(wú)線傳感器網(wǎng)絡(luò)DV-Hop節(jié)點(diǎn)定位算法研究[J].計(jì)算機(jī)應(yīng)用研究,2009,26(4):1272-1275.

[6]趙清華,劉少飛,張朝霞,等.一種無(wú)需測(cè)距節(jié)點(diǎn)定位算法的分析和改進(jìn)[J].傳感技術(shù)學(xué)報(bào),2010,23(1):122-127.

[7]葛宇,王學(xué)平,梁靜.基于蛙跳算法的DV-Hop定位改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2011,31(4):0922-03.

[8]Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization,Technical Report-TR06[R].Kayseri:Erciyes University,Engineering Faculty,Computer Engineering Department,2005.

[9]Kennedy J,Eberhart R C.Particle Swarm Optimization[C]//Proc IEEE International Conference on Neural Networks(Perth,Australia),IEEE Service Center,Piscataway,NJ,IV,1995:1942-1948.

[10]Shi Y,Eberhart R C.A Modified Particle Swarm Optimizer[C]//Proc IEEE World Congress on Computational Intelligence,1998:69-73.

[11]Karaboga D,Basturk B.On the Performance of Artificial Bee Colony(ABC)Algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[12]嵇瑋瑋,劉中.DV-Hop定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J].電子與信息學(xué)報(bào),2008,30(4):970-974.

[13]李牧東,熊偉,郭龍.基于人工蜂群算法的DV-Hop定位改進(jìn)[J].計(jì)算機(jī)科學(xué),2013,40(1):33-36.

江濤(1974-),男,重慶合川人,副教授,研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)、職業(yè)教育教學(xué)管理,jiangtao1974jt@163.com。

ImprovedLocalizationAlgorithmofDV-HopBasedonHybridArtificialBeeColonyAlgorithm

JIANGTao*

(ChongQing Technology and Business Institute,Chongqing 400052,China)

Abstract:In order to reduce the node localization error of DV-Hop algorithm in Wireless Sensor Network(WSN),an improved algorithm based on Hybrid Artificial Bee Colony(HABC)algorithm was put forward.Combining the fast convergence speed characteristics of Particle Swarm Optimization(PSO)and strong searching capability of ABC,improved algorithm firstly estimated the distance between unknown nodes and anchor-nodes by DV-Hop algorithm.Secondly,the initial position of unknown nodes was calculated by PSO.Finally,the iterative numerical method with the initial values of estimated node locations was presented by ABC.It can be concluded that the improved algorithm has obviously better locating precision than PSO and DV-Hop.

Key words:Wireless Sensor Network(WSN);location;DV-Hop algorithm;Artificial Bee Colony(ABC)algorithm;Particle Swarm Optimization(PSO)algorithm

doi:EEACC:6150P;720010.3969/j.issn.1005-9490.2014.05.025

中圖分類號(hào):6150P

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1005-9490(2014)05-0912-05

收稿日期:2013-10-28修改日期:2013-11-14