国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

免疫粒子群優(yōu)化的DV-Hop定位算法

2018-05-23 06:17:13吳珍珍方旺盛
關(guān)鍵詞:信標(biāo)適應(yīng)度半徑

吳珍珍,方旺盛

(江西理工大學(xué) 信息工程學(xué)院,江西 贛州 341000)

0 引言

WSN節(jié)點定位技術(shù)是WSN應(yīng)用于目標(biāo)監(jiān)測、目標(biāo)識別和目標(biāo)跟蹤的支撐技術(shù),其算法可分為基于非測距(Range- free)的算法和基于測距(Range-based)的算法[1],其中非測距DV-Hop算法因具有成本低、能耗小、算法實現(xiàn)簡單等特點而被廣泛應(yīng)用,但該算法也存在定位誤差較大的不足。

為了提高DV-Hop算法的定位精度,國內(nèi)學(xué)者對此引入群體智能算法進(jìn)行優(yōu)化。文獻(xiàn)[2]提出了一種改進(jìn)的粒子群優(yōu)化DV-Hop算法,從慣性權(quán)重的計算、粒子速度的更新等方面對粒子群算法進(jìn)行改進(jìn),提高算法的搜索速度,再采用改進(jìn)粒子群算法優(yōu)化節(jié)點的定位結(jié)果,降低了定位誤差。文獻(xiàn)[3]利用免疫系統(tǒng)里的調(diào)節(jié)機制來提高種群的多樣性,避免了過早陷入局部最優(yōu)解,優(yōu)化的DV-Hop算法提高了定位效果,但該算法未考慮粒子群算法的收斂速度問題。文獻(xiàn)[4]使用遺傳機制中的前攝估計縮小粒子搜索范圍,再用改進(jìn)粒子群算法以代替最小二乘法優(yōu)化了DV-Hop算法定位精度。本文根據(jù)免疫粒子群算法的特點,利用該算法來優(yōu)化DV-Hop定位算法求解未知節(jié)點的坐標(biāo)。

1 DV-Hop定位算法

1.1 基本原理

DV-Hop(Distance Vector-Hop)是一種非測距定位算法。該算法依賴于節(jié)點間的互相通信,具體定位算法由3個階段組成[5]:

第一階段:信標(biāo)節(jié)點通過全網(wǎng)泛洪廣播數(shù)據(jù)包,所有節(jié)點可以記錄下到每個信標(biāo)節(jié)點的最小跳數(shù)。

第二階段:估算從未知節(jié)點到信標(biāo)節(jié)點的跳距。

第三階段:利用三邊測量法或最小二乘法等計算未知節(jié)點坐標(biāo)[6]。

1.2 定位誤差的分析

從DV-Hop的工作原理可知,其產(chǎn)生定位誤差的主要原因有跳數(shù)、平均每跳距離、定位的計算方法等。

(1)跳數(shù)信息不合理

WSN在定位時通過使用跳數(shù)信息計算節(jié)點之間的距離,而無線傳感器網(wǎng)絡(luò)中的節(jié)點大都是隨機分布,未知節(jié)點與錨節(jié)點之間并非都是直線距離,所以節(jié)點之間存在彎曲路徑,將會導(dǎo)致較大誤差。

(2)平均跳距的估計值不準(zhǔn)確

在DV-Hop定位算法中,節(jié)點間的距離計算是采用同一個平均距離的估計值乘以對應(yīng)的跳數(shù)來計算的,存在一定的定位誤差。

(3)定位的計算方法累計誤差

計算未知節(jié)點的坐標(biāo)時經(jīng)常采用三邊測量和極大似然估計法。三邊測量方法雖然降低了計算量,但其受限于第二階段的跳距估計。而在最大似然估計法求解過程中需要較多的浮點預(yù)算,計算開銷帶來的功耗不容忽視。

2 免疫粒子群優(yōu)化的DV-Hop定位算法

鑒于上述誤差分析,針對經(jīng)典DV-Hop定位算法在計算未知點坐標(biāo)上存在較大誤差,本文提出了一種免疫粒子群優(yōu)化的DV-Hop定位算法。

2.1 粒子群算法進(jìn)化模型

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是1995年由Kennedy和Eberhart提出的一種新型的隨機群體智能的進(jìn)化算法[7]。其原理為:在D維空間里有很多“粒子”,這些“粒子”通過“位置+速度”模型來更新自身的位置與速度,每個粒子不斷地搜索迭代,向最優(yōu)值位置不斷地靠近[8]。該算法存在以下缺點:(1)容易陷入局部極小值,導(dǎo)致得不到全局最優(yōu)解;(2)沒有充分的優(yōu)選機制,收斂速度較慢。本文為了提高粒子群算法的全局搜索能力,借鑒免疫算法的思想改進(jìn)PSO算法,當(dāng)PSO算法陷入局部最優(yōu)解時,通過免疫抗體的選擇、促進(jìn)和抑制機制產(chǎn)生新的粒子空間,使該算法跳出局部最優(yōu)值,避免“早熟”;另外生成的免疫記憶細(xì)胞可以加快收斂速度,確??焖偈諗坑谌肿顑?yōu)解。

(1)

(2)

式中,c1表示個體學(xué)習(xí)因子,c2表示全局學(xué)習(xí)因子,而r1和r2為(0,1)上均勻分布的隨機數(shù);ω為慣性權(quán)重,表示粒子運動的趨勢,對全局搜索和局部搜索起到平衡作用[9]。該系數(shù)按照公式(3)進(jìn)行更新。

(3)

2.2 免疫機制

免疫機制源于生物免疫系統(tǒng),其具體思路為將待優(yōu)化適應(yīng)度函數(shù)最優(yōu)解看作入侵生命體的抗原,而免疫系統(tǒng)產(chǎn)生的抗體即為候選解,將個體最優(yōu)解以免疫記憶形式保存于記憶細(xì)胞,提高收斂速度;根據(jù)免疫調(diào)節(jié)機制,選擇具有親和度高且濃度低的抗體進(jìn)化,而親和度低濃度高的抗體加以抑制[10];通過抗原抗體相互促進(jìn)抑制來維持抗體的多樣性,克服了粒子群算法在實際工程優(yōu)化計算中的早熟收斂現(xiàn)象,提高了算法的全局搜索效率。

(1)親和度

親和度[11]用來衡量抗原與抗體間的匹配程度,即所求的解與最優(yōu)解的接近程度,記為aff,計算公式如下:

(4)

其中,f(xi)為xi的適應(yīng)度函數(shù),η為(0,1)上的常數(shù)。由上式可以看出,當(dāng)f(xi)越小時,抗體的親和度越大,所求的解與最優(yōu)解就越逼近。

(2)濃度

濃度表示抗體與其相似的粒子在群體中所占的比例,反映種群多樣性的程度。假設(shè)存在i個抗體x1,x2…,xi,每個抗體按照親和度從小到大排序并分成m個等份區(qū)間,其中m=1,2,…,m。計算每個區(qū)間的抗體數(shù),記為sum(m),得到每個區(qū)間的濃度為sum(m)/m,將每個抗體的濃度定義為該抗體所在區(qū)間的濃度,記為D,則有:

(5)

由上式可知,同一個區(qū)間上的抗體濃度是相同的,這使得抗體濃度越高反而越受到抑制,而抗體濃度越低反而得到進(jìn)化的機會。

(3)選擇概率

選擇概率是指抗體在進(jìn)化過程中得到促進(jìn)發(fā)展的概率。假設(shè)基于親和度的選擇概率為Pa,而基于濃度的選擇概率為Pd,計算公式如下:

(6)

(7)

則抗體被選中的選擇概率P為:

P(xi)=αPa(xi)+(1-α)Pd(xi)

0<α,Pa,Pd<1

(8)

式中i=1,2,…,n;α為免疫協(xié)調(diào)因子,用來協(xié)調(diào)概率Pd和Pa的權(quán)重。從式(8)可以得知,濃度越高、親和力越低的抗體被選擇的概率越??;而濃度越低、親和力越高的抗體獲得進(jìn)化的概率越大。這樣既提高了抗體的親和度,又保證了粒子的多樣性,從而得到較大的解空間。

(4)適應(yīng)度函數(shù)

適應(yīng)度函數(shù)即目標(biāo)函數(shù),用來評價給出的候選解(抗體)的優(yōu)劣。計算公式如下:

(9)

其中,M(M≥3)為未知節(jié)點接收到的信標(biāo)節(jié)點的個數(shù);(x,y)和(xi,yi)分別表示粒子位置和第i個信標(biāo)節(jié)點的坐標(biāo);di為未知節(jié)點到信標(biāo)節(jié)點i的歐式距離。適應(yīng)度函數(shù)f(i)的極小值點則為最優(yōu)的定位坐標(biāo)。

3 免疫粒子群優(yōu)化的DV-Hop定位算法步驟

本文算法優(yōu)化的DV-Hop算法步驟如下:

(1)初始化網(wǎng)絡(luò)區(qū)域、節(jié)點總數(shù)、粒子群相關(guān)參數(shù)。

(2)根據(jù)經(jīng)典DV-Hop算法的第一和第二階段獲得每個信標(biāo)節(jié)點和未知節(jié)點的最小跳數(shù)以及信標(biāo)節(jié)點i的平均跳距,計算跳段距離。

(3)初始化粒子群。初始化粒子位置X、粒子速度V、歷史局部最優(yōu)位置pbesti=Xi,計算種群的適應(yīng)度函數(shù)值,取該值的最小值為粒子群的全局最優(yōu)位置gbesti的初始值。

(4)免疫記憶。將粒子按親和度從小到大排序,取親和度較大的粒子存入免疫記憶細(xì)胞中。

(5)利用式(1)、式(2)分別更新粒子的飛行速度和位置,產(chǎn)生n個新的抗體,然后從免疫記憶細(xì)胞中抽取q個抗體,組成規(guī)模為n+q的抗體群。

(6)免疫替換,丟棄位置較差的粒子(抗體)。利用式(4)~(8)計算抗體的選擇概率,依據(jù)選擇概率從n+q個抗體中選擇出n個抗體,則選擇概率大的抗體將被選中,組成新的抗體群,從而實現(xiàn)抗體的多樣性,避免出現(xiàn)“早熟”。

(7)根據(jù)式(9)計算抗體的適應(yīng)度大小,比較所有粒子當(dāng)前的適應(yīng)度值F(Xi)和局部最優(yōu)位置適應(yīng)度值F(pbesti),若F(pbesti)>F(Xi),則更新pbest值;再用更新后局部最優(yōu)適應(yīng)函數(shù)值F(pbesti)與全局最優(yōu)位置的適應(yīng)函數(shù)F(gbesti)比較,若F(gbesti)>F(pbesti),則更新gbest值。

(8)若滿足終止條件,則輸出全局最優(yōu)解gbesti,適應(yīng)度函數(shù)F(gbesti)的極小值點即為未知節(jié)點的最終定位坐標(biāo)。否則返回步驟(4)。

4 實驗與仿真

4.1 實驗環(huán)境和參數(shù)設(shè)置

為驗證本文算法的有效性,本文基于Windows 10操作系統(tǒng)的MATLAB 2014平臺進(jìn)行仿真實驗。本文試驗場景設(shè)置為100 m×100 m的二維正方形區(qū)域,假設(shè)所有WSN網(wǎng)絡(luò)節(jié)點的通信半徑都為R。

免疫粒子群算法的初始化參數(shù)如表1所示。

表1 仿真參數(shù)

4.2 仿真分析

(1)信標(biāo)節(jié)點比例對定位精度的影響

假設(shè)通信半徑為30 m、節(jié)點總數(shù)為100,圖1給出信標(biāo)節(jié)點比例對定位精度的影響關(guān)系圖。從圖中可以看出,3種定位算法的平均定位誤差都隨著信標(biāo)節(jié)點的比例增加而減小。當(dāng)信標(biāo)節(jié)點比例相同時,本文算法的平均定位誤差與DV-Hop以及PSO-DV-Hop定位算法比較降低了15.03%、4.86%。另外,本文算法平均定位誤差曲線更平滑,表明其穩(wěn)定性更好。

圖1 信標(biāo)節(jié)點比例與定位誤差關(guān)系圖

(2)通信半徑對定位精度的影響

假設(shè)節(jié)點總數(shù)為100時,信標(biāo)節(jié)點比例為10%,改變通信半徑進(jìn)行仿真,結(jié)果如圖2所示。從圖中可以看出,在通信半徑小于30 m時,3種定位算法的平均定位誤差都隨著通信半徑的增大而明顯減小,這是因為通信半徑的增大提高了未知節(jié)點與信標(biāo)節(jié)點的連通性,從而可以獲得更大范圍的信息交換來提高定位精度。但在通信半徑大于30 m時,平均定位誤差緩慢減小,趨于平滑,因此通信半徑并不是越大越好,通信半徑的增大也將提高通信開銷。另外,從3種算法對比可以看出,本文算法的定位誤差與經(jīng)典DV-Hop、PSO-DV-Hop定位算法相比,定位精度提高了13.27%、8.27%。

圖2 通信半徑與定位誤差關(guān)系圖

(3)節(jié)點總數(shù)對定位精度的影響

假設(shè)網(wǎng)絡(luò)節(jié)點的通信半徑為30 m時,信標(biāo)節(jié)點比例為10%,節(jié)點總數(shù)變化的仿真結(jié)果如圖3所示。從圖中可以看出,在通信半徑和信標(biāo)節(jié)點比例相同的情況下,節(jié)點的平均誤差隨著節(jié)點總數(shù)的增加而下降。隨著節(jié)點總數(shù)的變化,平均定位算法的變化幅度相對較大,這也反映了該算法的可擴展性有待進(jìn)一步提高。但是,本文算法定位精度明顯優(yōu)于傳統(tǒng)的DV-Hop算法和PSO-DV-Hop算法,平均定位誤差分別降低了10.85%、5.89%。

圖3 節(jié)點總數(shù)與定位誤差關(guān)系圖

5 結(jié)論

本文闡述了典型DV-Hop定位算法的基本原理,分析了DV-Hop定位算法的誤差來源,并結(jié)合免疫粒子群優(yōu)化算法的特點,提出了一種免疫粒子群算法優(yōu)化的DV-Hop定位算法。在免疫粒子群算法中,通過調(diào)節(jié)機制使各適應(yīng)度的粒子維持一定濃度,保證群體的多樣性,克服粒子早熟,使得粒子快速收斂于全局最優(yōu)點,優(yōu)化待測節(jié)點位置坐標(biāo)。該算法在無需增加額外硬件設(shè)備的情況下,有效降低了定位誤差。但免疫粒子群算法的引入增加了算法復(fù)雜度,這將是下一步研究的重點。

參考文獻(xiàn)

[1] 錢志鴻, 孫大洋. 無線網(wǎng)絡(luò)定位綜述[J]. 計算機學(xué)報, 2016, 39(6): 1237-1256.

[2] 于泉, 孫順遠(yuǎn), 徐保國, 等. 基于改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J].計算機應(yīng)用, 2015, 35(6): 1519-1522.

[3] FEI J.Optimization of immune particleswarm algorithmand application on wireless sensornetworks[J]. Computer Modeling & New Technologies,2014,18(11):1443-15448.

[4] 高美鳳, 李鳳超. 遺傳粒子群優(yōu)化的 DV-Hop 定位算法[J]. 傳感技術(shù)學(xué)報, 2017, 30(7): 1083-1088.

[5] 王林,趙錦.一種基于誤差修正的改進(jìn)DV-Hop算法[J].計算機工程與應(yīng)用,2014,50(24): 109-112.

[6] TAO Q, ZHANG L. Enhancement of DV-Hop by weightedhopdistance[C]//Advanced Information Management, Communicates, Electronic and Automation Control Conference(IMCEC),2016 IEEE, 2016:1577-1580.

[7] 邴曉瑛,徐保國.基于改進(jìn)粒子群優(yōu)化的WSN定位算法[J]. 電子設(shè)計工程,2015,23(22): 143-146.

[8] 張超, 李擎, 王偉乾, 等. 基于自適應(yīng)搜索的免疫粒子群算法[J]. 工程科學(xué)學(xué)報, 2017, 39(1): 125-132.

[9] 張曉, 范虹, 張莉, 等. 融入免疫思想的改進(jìn)型粒子群優(yōu)化算法[J].陜西師范大學(xué)學(xué)報(自然科學(xué)版),2017,45(3): 17-23.

[10] Jiao Wei,Cheng Weimin,Zhang Mei,et al. A simpleand effective immune particle swarm optimization algorithm[C]// International Conference in Swarm Intelligence. Springer, Berlin,Heidelberg, 2012: 489-496.

[11] He Xingshi, Han Lin. A novel binary differential evolution algorithm based on artificial immune system [C]// Evolutionary Computation,IEEE,2007: 2267-2272.

猜你喜歡
信標(biāo)適應(yīng)度半徑
改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
計算機仿真(2022年8期)2022-09-28 09:53:02
連續(xù)展成磨削小半徑齒頂圓角的多刀逼近法
RFID電子信標(biāo)在車-地聯(lián)動控制系統(tǒng)中的應(yīng)用
一些圖的無符號拉普拉斯譜半徑
基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
中國塑料(2016年11期)2016-04-16 05:26:02
基于信標(biāo)的多Agent系統(tǒng)的移動位置研究
熱采水平井加熱半徑計算新模型
無姿態(tài)補償?shù)乃滦艠?biāo)絕對位置傳遞研究
水道港口(2015年1期)2015-02-06 01:25:45
少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
IEEE 802.22.1信標(biāo)網(wǎng)絡(luò)應(yīng)用研究
北京市| 奉新县| 禹城市| 分宜县| 健康| 普宁市| 镇江市| 增城市| 永清县| 浑源县| 梅州市| 开远市| 旬阳县| 张掖市| 镇安县| 贺兰县| 涞源县| 乌拉特前旗| 珠海市| 东山县| 闻喜县| 清原| 蒲江县| 开鲁县| 库车县| 锦屏县| 濉溪县| 伊宁县| 济南市| 秦皇岛市| 若尔盖县| 新巴尔虎右旗| 鄯善县| 扎鲁特旗| 阳山县| 新田县| 蓬安县| 浦县| 正镶白旗| 新乐市| 仁寿县|