吳 斌，金潔麗

（1.浙江郵電職業(yè)技術(shù)學(xué)院，浙江 紹興 312016；2.吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000）

0 引 言

智能優(yōu)化算法模擬地球上生物的行為，是一類具有自我學(xué)習(xí)、自我組織的方法，適合大規(guī)模問題求解，眾多學(xué)者將該類算法應(yīng)用于求解定位問題[1]。

林鳳德等人[2]針對經(jīng)典DV-Hop 方法定位精度低且計(jì)算復(fù)雜度高等難題提出一種利用遺傳與蟻群混合優(yōu)化算法的DV-Hop 定位方法。該方法中除利用遺傳方法搜找最優(yōu)解外，還利用蟻群進(jìn)一步搜找，增強(qiáng)了定位精度和迭代速度，測試表明該算法增加了計(jì)算效率，迭代速率和定位適應(yīng)度值。面對Amprphous 算法存在較低的定位精度的缺點(diǎn)，胡偉等人[3]利用遺傳-禁忌搜索算法求解該問題。首先修正最小跳數(shù)的估計(jì)值然后經(jīng)過遺傳算法優(yōu)化，優(yōu)化后的解在經(jīng)過禁忌搜索策略進(jìn)一步增強(qiáng)了算法的精度。靳春景等人[4]通過大量的實(shí)驗(yàn)仿真發(fā)現(xiàn)單一算法定位精度容易受環(huán)境等因素的影響較大，提出一種利用DVC-Hop 的算法，它修正了平均跳距，并引入PSO 優(yōu)化方法加快尋優(yōu)速度，因?yàn)镻SO 方法較易陷入局部解空間卻無法跳出等缺點(diǎn)，因此提出隨機(jī)擾動策略解決PSO的早熟難題。姚汝賢等人[5]提出一種利用改進(jìn)量子PSO 的RSSI 測距方法，為了加快PSO 優(yōu)化算法的收斂速率，在算法中引入學(xué)習(xí)自動機(jī)，粒子在獲得自學(xué)習(xí)能力以后可以自適應(yīng)的選擇相應(yīng)的動作。實(shí)驗(yàn)論證顯示該方法具有較高的定位質(zhì)量，并且速度快。

上述算法雖然有效的求解節(jié)點(diǎn)定位問題，但是在實(shí)時性和定位精度上仍有待改善，因此本文提出融合粒子群和差分進(jìn)化算法的HPSO-DE 算法，并和文獻(xiàn)[6]的PSO、文獻(xiàn)[7]的DFOA 等方法進(jìn)行比較，證明本文算法在適應(yīng)度函數(shù)值和收斂速度方面的優(yōu)勢。

1 節(jié)點(diǎn)定位問題建模及目標(biāo)函數(shù)

設(shè) 錨P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)和 未 知 節(jié) 點(diǎn)P(x,y)的實(shí)際真實(shí)長度分別是r1,r2,…,rn，測距誤差分別是ε1,ε2,…,εn，則滿足|ri-di|<εi，其中i=1,2,…,n，那么未知節(jié)點(diǎn)P(x,y)約束條件：

解(x,y)，使得：

由此節(jié)點(diǎn)定位問題轉(zhuǎn)換成求如式2 中測距誤差最小值的優(yōu)化問題，本文將改進(jìn)智能優(yōu)化算法應(yīng)用于節(jié)點(diǎn)位置估計(jì)的優(yōu)化問題，以降低誤差對定位性能的干擾，提高定位的精度。

2 粒子群算法及差分進(jìn)化算法

2.1 粒子群算法（PSO）

PSO 算法的核心思想是粒子的在解空間里面隨意飛行，然后在每次迭代過程中通過和其他粒子進(jìn)行信息交互，然后根據(jù)個人經(jīng)驗(yàn)和其他粒子的影響決定下一次飛行的位置。受到其他優(yōu)秀的個體的影響，粒子從最初無序的狀態(tài)朝著熵減狀態(tài)轉(zhuǎn)變，直至最終搜索到食物位置。

假設(shè)一個種群規(guī)模為N 的粒子群在解空間里面搜索最優(yōu)解，搜索維度為D。粒子i 在t 時刻的狀態(tài)屬性設(shè)置如下：

則在t+1 代更新過程里，個體的速度和位置更新公式分別為：

式中，u1,u2為介于（0,1）內(nèi)隨機(jī)服從uniform分布的數(shù)；c1,c2分別表示個體認(rèn)知因子和社會認(rèn)知因子（二者統(tǒng)稱加速度因子），一般取c1=c2=2.0。

2.2 差分進(jìn)化算法(DE)

（1）種群初始化

DE 算法的種群由NP 個D 維向量個體組成。記xi為一個D 維向量，則一個種群可以表示為Pop={x1.x2,…,xNP}。其中，NP 是種群的規(guī)模大小，該值在每次迭代過程中保持不變。種群的初始化應(yīng)在符合邊界約束的條件下盡可能均勻覆蓋全部區(qū)域，假設(shè)個體第j 維的上下邊界分別為和那么個體按下面的方式進(jìn)行初始化：

式 中，i=1,2,…,NP；j=1,2,…,D。randj（0,1）是一個在（0,1）上服從uniform 分布的隨機(jī)數(shù)。

（2）變異操作

種群經(jīng)過初始化賦值后，利用差分變異操作產(chǎn)生變異矢量。常見的差分變異操作有DE/rnad/1、DE/best/1、DE/rand-to-best/1、DE/best/2、DE/rand/2、DE/current-to-best/1、DE/current-to-rand/1等。其中，經(jīng)典的“DE/rand/1”變異策略如式（6）所示：

式中，r1,r2,r3 ∈[1,2,….NP]為兩兩不相同的整數(shù)，縮放因子F 是（0，1）區(qū)間內(nèi)的常數(shù)，用于控制差分向量的大小。

（3）交叉操作

在進(jìn)行變異操作之后，需要將目標(biāo)向量xi,g與變異向量vi,g進(jìn)行二項(xiàng)式交叉生成最終的試驗(yàn)向量ui,g=[ui1,g,ui2,g,uiD,g]，按照公式（7）執(zhí)行交叉操作。

式中，jrand是從集合{1,2,…,D}內(nèi)隨機(jī)選擇的一個整數(shù)，以保證變異向量vi,g至少有一維信息被保留下來。交叉概率CR 是區(qū)間（0,1）內(nèi)的一個常數(shù)。

（4）選擇操作

試驗(yàn)向量與對應(yīng)的目標(biāo)向量之間執(zhí)行一對一的錦標(biāo)賽選擇。對試驗(yàn)向量ui,g與vi,g目標(biāo)向量的目標(biāo)函數(shù)值進(jìn)行比較，如果試驗(yàn)向量具有更優(yōu)的目標(biāo)函數(shù)，則將目標(biāo)向量替換成試驗(yàn)向量；否則，該目標(biāo)向量保持不變。以目標(biāo)函數(shù)最小化為例，選擇操作可用公式（8）來表示：

式中，f(·)為優(yōu)化問題的目標(biāo)函數(shù)。

3 節(jié)點(diǎn)定位的HPSO-DE 算法

粒子群算法較易出現(xiàn)局部最小[8]，主要因?yàn)樵撍惴▋?yōu)化過程中，種群的差異性喪失，趨向于同一性，但是粒子群收斂速度快，差分進(jìn)化算法雖然全局探索能力強(qiáng)，但是其在進(jìn)化的前提和中期一般都探索解空間，而未對較優(yōu)解的局部空間進(jìn)行細(xì)致的開發(fā)，導(dǎo)致尋優(yōu)速度慢，因此本文提出混合粒子群和差分進(jìn)化算法HPSO-DE 以平衡算法的局部尋優(yōu)和全局探索的能力，其中自適應(yīng)慣性權(quán)重更新策略和混合進(jìn)化策略使得該算法不僅尋優(yōu)能力強(qiáng)而且尋優(yōu)速度快。

3.1 自適應(yīng)慣性權(quán)重更新策略

粒子群算法中的w 衡量了前一時刻的速度對當(dāng)前速度的影響[9]，用于平衡算法的局部搜索能力和全局搜索能力。傳統(tǒng)的粒子群算法將w 設(shè)置為固定值，導(dǎo)致該算法無法在不同的優(yōu)化階段下相應(yīng)的做出調(diào)整導(dǎo)致陷入局部最優(yōu)。本文在計(jì)算w 時考慮到每次迭代過程中種群的分布情況，首先定義第i 個粒子距離其他N-1 個粒子的平均距離di為：

其中，N 和D 分別表示種群規(guī)模大小和編碼維度。然后定義進(jìn)化因子δ 如式（10）所示：

其中，dg表示為全局最優(yōu)個體的平均距離，dmax、dmin分別表示種群中最大和最小的平均距離。最終w 的更新公式如式（11）所示：

其中w 隨著δ 的增加而增加，變化范圍是[0.4 0.9]，在早期的迭代過程中，δ 較大，此時w 也較大，有利于粒子快速找到最優(yōu)解的大致位置區(qū)域，在迭代后期，w 較小，此時檢測到種群趨于同一開始收斂，減小w 有利于進(jìn)行精準(zhǔn)的局部搜索。

3.2 混合優(yōu)化策略

如前文所述，粒子群算法容易陷入局部最優(yōu)，全局搜索能力差，但是差分進(jìn)化算法的搜索能力卻很強(qiáng)，因此可以將經(jīng)過PSO 進(jìn)化的種群再經(jīng)過DE算法進(jìn)化，同時為了減少算法的復(fù)雜度，我們設(shè)定了閾值，將種群劃分為優(yōu)等群和劣等群，只將劣等群中的個體經(jīng)過差分進(jìn)化，然后將進(jìn)化后的種群和優(yōu)秀群合并繼續(xù)進(jìn)行下一次迭代。即，首先設(shè)定閾值favg，計(jì)算公式如式（12）所示：

然后將每個粒子的適應(yīng)度值與之比較，若小于該值，表示該個體較優(yōu)秀，即歸入優(yōu)等群，反之，如果該粒子的適應(yīng)度值大于該值意味著該個體當(dāng)前解較差，因此要?dú)w入到劣等群中通過DE 算法進(jìn)一步優(yōu)化。

在經(jīng)過DE 進(jìn)化后，利用貪婪選擇機(jī)制，確定當(dāng)前種群中的最優(yōu)解。

綜上所述可得HPSO-DE 算法的步驟如下：

（1）初始化粒子群中的粒子的速度和位置，設(shè)置迭代次數(shù)I=1.

（2）利用式2 計(jì)算每個粒子的適應(yīng)度值。

（3）利用式12 計(jì)算種群的閾值favg，將種群劃分為優(yōu)等群Su 和劣等群In。

（4）將In 中的個體依次利用式6、7 和8 進(jìn)行變異和交叉和選擇操作，進(jìn)一步提高劣等群中個體的適應(yīng)度值。

（5）將優(yōu)等群和劣等群合并，并更新全局最優(yōu)值和個體最優(yōu)值

（6）若I 等于最大迭代次數(shù)則進(jìn)行步驟7，否則轉(zhuǎn)步驟2

（7）輸出最優(yōu)個體的位置作為對未知節(jié)點(diǎn)的位置估計(jì)。

4 仿真實(shí)驗(yàn)與分析

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

在PSO 算法中，設(shè)置學(xué)習(xí)因子c1=c2=1.4945，在DFOA[7]算法中,設(shè)置搜索步長radiusX 為0.1，本文HPSO-DE 算法中，設(shè)置常數(shù)交叉概率cr=0.6。三種算法中設(shè)置種群規(guī)模大小為30，最大迭代次數(shù)設(shè)置為80。

4.2 實(shí)驗(yàn)仿真分析

本文參考文獻(xiàn)[10]以平均定位誤差（average location error，AVE）為評價(jià)標(biāo)準(zhǔn)。其公式如式（13）所示：

式中：M 為已知節(jié)點(diǎn)的總個數(shù)，(x,y)為預(yù)測位置，(xi,yi)為實(shí)際位置。

首先設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)的通信半徑為10 m，隨機(jī)將30 個傳感器置于30 m×30 m 的區(qū)域中，隨機(jī)挑選10 個節(jié)點(diǎn)為錨節(jié)點(diǎn)，設(shè)置算法的最大迭代次數(shù)為200 次，每一個未知節(jié)點(diǎn)的坐標(biāo)估計(jì)值都是20 次獨(dú)立實(shí)驗(yàn)的平均。將HPSO-DE 算法與參考文獻(xiàn)[7]中的DFOA 算法進(jìn)行節(jié)點(diǎn)定位結(jié)果的對比，見表1。

表1 給出了在HPSO 算法和DFOA 算法下，挑選的10 個無法測量自身坐標(biāo)的節(jié)點(diǎn)的預(yù)測值比較，由表可以看出（1）首先兩種算法都可以應(yīng)用于WSN 網(wǎng)絡(luò)的定位場景中，同時，由10 個未知點(diǎn)的預(yù)測誤差來看，HPSO-DE 的AVE 比DFOA 要低很多，證明了本文所提算法的優(yōu)勢。

PSO、DFOA 和HPSO-DE 等算法在已知自身精確位置信息的節(jié)點(diǎn)個數(shù)為10 個時的AVE 隨測距誤差關(guān)系圖如圖1 所示。圖中的每條曲線均進(jìn)行了20 次獨(dú)立重復(fù)實(shí)驗(yàn)而得到。由圖1 可知：（1）由圖中的三條曲線的走向可以看出總體定位精度是HPSO-DE>DFOA>PSO（2）本文提出的HPSO-DE隨著迭代次數(shù)自適應(yīng)的變化慣性權(quán)重的值和混合進(jìn)化策略使得該算法不僅定位能力強(qiáng)而且尋優(yōu)速度快，在測距誤差為30%時，HPSO-DE 的定位誤差分別比DFOA 和PSO 降低2 m 和1 m。（3）由表可以看出當(dāng)測距誤差由25%增加到30%時，PSO算法和DFOA 算法的曲線的斜率顯著增大，說明該兩種算法的魯棒性能差，但是所提HPSO-DE 算法卻增加的很平緩，說明在較大測距誤差情況下，HPSO-DE 也可以有較高的定位精度。

圖1 平均定位誤差與測距誤差關(guān)系

如圖2 給出了PSO、DFOA 和HPSO-DE 在測距誤差為10%時的AVE 和已知自身精確位置信息的節(jié)點(diǎn)個數(shù)變化關(guān)系。由圖可以看出，（1）由圖中的三條曲線表示的平均定位誤差與錨節(jié)點(diǎn)個數(shù)的關(guān)系圖走向可以看出總體定位精度是HPSODE>DFOA>PSO，（2）雖然PSO 算法的誤差在信標(biāo)節(jié)點(diǎn)的數(shù)目增加的時候而下降，但是AVE 仍然高于DFOA 算法和HPSO-DE 算法，說明該算法很敏感，和對成本要求較高。（3）本文在仿真場景中設(shè)置相同數(shù)量的已知個體坐標(biāo)精確位置的節(jié)點(diǎn)的情況下，HPSO-DE 具有最小的誤差性能，例如當(dāng)錨節(jié)點(diǎn)個數(shù)為4 個時，HPSO-DE、DFOA 和PSO 算法的定位誤差分別是1.5 m、2.2 m 和3.35 m。

圖2 平均定位誤差與錨節(jié)點(diǎn)個數(shù)關(guān)系

PSO、DFOA 和HPSO-DE 在定位誤差為10%，信標(biāo)節(jié)點(diǎn)個數(shù)為10 個時，AVE 與種群規(guī)模的關(guān)系如圖3 所示。由圖可知，（1）隨著種群規(guī)模的增大，有更多的個體在搜索空間里尋找更優(yōu)解，因此三種算法的定位誤差都在逐漸減小。（2）HPSO-DE、DFOA 和PSO 算法在達(dá)到最小的定位誤差時需要的種群個體數(shù)量分別是20、20 和47。說明HPSODE 和DFOA 的尋優(yōu)能力強(qiáng)，同時算法復(fù)雜度低，特別是HPSO-DE 算法，在個體數(shù)量為10 時平均定位誤差就很小，而PSO 達(dá)到同等的平均定位誤差，需要的種群個體數(shù)量為37。這是因?yàn)楸疚奶岢龅腍PSO-DE 算法的自適應(yīng)慣性權(quán)重更新策略和混合進(jìn)化策略使得該算法同時擁有PSO 的開采性能高和DE 的勘探能力強(qiáng)的特點(diǎn)，在保持較快收斂速度的同時具有更高的優(yōu)化性能。

圖3 平均定位誤差與種群規(guī)模大小關(guān)系

4.3 實(shí)測分析

上述理論仿真表明所提算法具有良好的定位性能，為了實(shí)測算法定位效果，搭建了如圖4 所示的實(shí)驗(yàn)平臺，在一塊6 m×6 m 的正方形操場上，按圖5 設(shè)置8 個錨節(jié)點(diǎn)（T1～T8），然后測量未知節(jié)點(diǎn)（1～9）的位置信息。

圖4 定位實(shí)驗(yàn)點(diǎn)實(shí)測

將實(shí)測數(shù)據(jù)與參考文獻(xiàn)[11]中的改進(jìn)PSO 算法測得的數(shù)據(jù)進(jìn)行比較，得到結(jié)果對比如圖6 所示。由圖可以看出，本文所提HPSO-DE 算法約比改進(jìn)PSO 算法的平均定位誤差低0.1 m。

圖5 定位實(shí)驗(yàn)點(diǎn)布置

圖6 錨節(jié)點(diǎn)為8 時平均誤差對比圖

5 結(jié) 語

如何確定傳感器節(jié)點(diǎn)的精確位置是WSN 網(wǎng)絡(luò)技術(shù)需要解決的重要難題之一。針對由測量誤差造成的精度不高的問題，本文首先改進(jìn)PSO 的固定權(quán)重為自適應(yīng)變化方式，增強(qiáng)了PSO 優(yōu)化的整體勘探能力，然后改進(jìn)差分進(jìn)化算法的變異策略，增強(qiáng)DE 算法的局部尋優(yōu)能力，然后將經(jīng)過粒子群優(yōu)化后的較差個體繼續(xù)通過差分進(jìn)化算法優(yōu)化，得到混合粒子群與差分進(jìn)化的HPSO-DE 算法，將該算法應(yīng)用于本文建模的WSN 定位場景中，仿真實(shí)驗(yàn)和實(shí)測實(shí)驗(yàn)結(jié)果表明，HPSO-DE 算法不僅提高了定位精度而且減少了定位需要消耗的時間。