基于混合人工蜂群粒子群改進(jìn)的WSN定位研究

朱正偉，宋麗萍

（常州大學(xué)信息科學(xué)與工程學(xué)院，江蘇常州 213164）

0 引 言

近年來(lái)，隨著計(jì)算機(jī)技術(shù)、微機(jī)電系統(tǒng)、人工智能等技術(shù)的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)得到了更為密切的關(guān)注，使得其廣泛地應(yīng)用于工業(yè)生產(chǎn)、環(huán)境監(jiān)控、軍事偵察等多個(gè)領(lǐng)域[1]。其中，對(duì)于無(wú)線傳感器網(wǎng)絡(luò)的定位技術(shù)是實(shí)現(xiàn)其應(yīng)用的重要基礎(chǔ)。全球定位系統(tǒng)（GPS）是目前應(yīng)用最廣泛、最成熟的定位系統(tǒng)，通過(guò)衛(wèi)星的授時(shí)和測(cè)距對(duì)用戶節(jié)點(diǎn)進(jìn)行定位，其定位精度高，實(shí)時(shí)性好。但GPS 定位由于其高成本以及對(duì)硬件設(shè)施較高的要求使其無(wú)法適用于低成本自組織的無(wú)線傳感器網(wǎng)絡(luò)[2]中。因此，對(duì)于無(wú)線傳感器的定位問(wèn)題，現(xiàn)階段已經(jīng)出現(xiàn)了許多適應(yīng)其要求的方法。

DV-Hop 作為一種無(wú)需測(cè)距的定位方法，其環(huán)境適應(yīng)性強(qiáng)，應(yīng)用方便，但是定位精度不高，針對(duì)這一缺點(diǎn)，國(guó)內(nèi)外已經(jīng)有大量學(xué)者對(duì)其做出了改進(jìn)與優(yōu)化。文獻(xiàn)[3]通過(guò)分析網(wǎng)絡(luò)節(jié)點(diǎn)分布特性得到最優(yōu)節(jié)點(diǎn)通信半徑，并使用最小二乘法校正錨節(jié)點(diǎn)的平均跳距，最后采用加權(quán)方法修正未知節(jié)點(diǎn)位置，使得定位精度得到了提高。文獻(xiàn)[4]首先考慮最近錨節(jié)點(diǎn)之外的其他錨節(jié)點(diǎn)在局部范圍和全局范圍的影響，并依據(jù)閾值選擇最優(yōu)的校正平均跳距來(lái)估計(jì)距離，基于閾值機(jī)制與距離校正有效地降低了定位誤差。文獻(xiàn)[5]提出一種基于位置計(jì)算過(guò)程的參考節(jié)點(diǎn)選擇算法，該方法在復(fù)雜的WSN 系統(tǒng)中仍然有較良好的定位精度。除了在原有的DV-Hop 算法中進(jìn)行改進(jìn)之外，將其他智能算法與DV-Hop 算法相結(jié)合也能大大提高其定位精度。文獻(xiàn)[6]將自適應(yīng)粒子群優(yōu)化與DV-Hop 算法相結(jié)合，將定位精度提高了20%左右。同時(shí),文獻(xiàn)[7]運(yùn)用人工蜂群算法與DV-Hop 算法相結(jié)合，也大大提高了定位精度。

綜合看來(lái)，傳統(tǒng)的DV-Hop 在定位中很難做到精準(zhǔn)定位，只有通過(guò)與其他定位算法結(jié)合，修正未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離，改進(jìn)定位計(jì)算方法等手段才可以達(dá)到較為精準(zhǔn)的定位效果。根據(jù)前人的研究發(fā)現(xiàn)，一些智能算法的引入可以較好地提高DV-Hop 的定位精度，本文在傳統(tǒng)定位方法中首先引入人工蜂群算法，提高其定位精度，并針對(duì)其容易陷入局部最優(yōu)解與求解速度慢的缺點(diǎn)，將變異粒子群算法的思想融入其中，使其能夠更為快速地收斂從而實(shí)現(xiàn)節(jié)點(diǎn)的定位。

1 傳統(tǒng)算法說(shuō)明

在當(dāng)前的節(jié)點(diǎn)定位問(wèn)題研究中，往往基于以下3 個(gè)前提：

1）網(wǎng)絡(luò)中有一定比例的節(jié)點(diǎn)位置己知或具有GPS定位功能，這些位置已知的節(jié)點(diǎn)可作為定位參考點(diǎn)。

2）節(jié)點(diǎn)具有與鄰近節(jié)點(diǎn)通信的能力。

3）節(jié)點(diǎn)不具有自主移動(dòng)能力。

根據(jù)定位過(guò)程中是否需要測(cè)量實(shí)際節(jié)點(diǎn)間的距離，定位算法可分為基于測(cè)距的定位算法和無(wú)需測(cè)距的定位算法。兩者的區(qū)別在于前者定位精度相對(duì)較高，但對(duì)額外的硬件設(shè)施要求也比較高。后者成本低、功耗小、抗測(cè)量噪聲能力強(qiáng)、硬件設(shè)備簡(jiǎn)單[8]。因?yàn)閭鞲衅骶W(wǎng)絡(luò)往往具有數(shù)量大、分布雜等特點(diǎn)，所以一般采取無(wú)需測(cè)距的定位方法，而DV-Hop 則是這類算法中的一個(gè)，具有方法簡(jiǎn)單，易于實(shí)現(xiàn)等優(yōu)點(diǎn)。

1.1 傳統(tǒng)的DV-Hop 算法

DV-Hop 是利用距離矢量路由和GPS 定位的思想提出的一系列分布式定位方法之一。該算法的優(yōu)點(diǎn)是在節(jié)點(diǎn)間無(wú)線傳輸距離有限的情況下，節(jié)點(diǎn)通過(guò)多跳路由的方式進(jìn)行信息傳送，節(jié)點(diǎn)自身僅需要與鄰居節(jié)點(diǎn)進(jìn)行通信以及數(shù)據(jù)交換，根據(jù)節(jié)點(diǎn)的分布密度和距離矢量信息，合理地將跳數(shù)以及跳距轉(zhuǎn)換為節(jié)點(diǎn)間的距離[9]。

一般地，傳統(tǒng)DV-Hop 算法的實(shí)現(xiàn)流程可以分為如下三個(gè)步驟：

1）通過(guò)典型的距離矢量交換協(xié)議獲取未知節(jié)點(diǎn)和參考節(jié)點(diǎn)間的最小跳步數(shù)信息，在獲取了最小跳步數(shù)信息后，可以通過(guò)式（1）利用參考節(jié)點(diǎn)之間的距離與跳數(shù)計(jì)算出跳步距離：

式中：i,j表示選擇的不同參考節(jié)點(diǎn)，只要有兩個(gè)參考節(jié)點(diǎn)被選擇則可以計(jì)算出一個(gè)跳步距離，這里選擇不同的參考節(jié)點(diǎn)會(huì)得到不一樣的跳步距離，根據(jù)文獻(xiàn)[10]的研究，利用加權(quán)算法得到加權(quán)跳步距離，該跳步距離會(huì)更好地與實(shí)際跳步距離匹配。

2）再根據(jù)式（2）計(jì)算出未知節(jié)點(diǎn)與參考節(jié)點(diǎn)之間的距離：

式中：Dwi表示未知節(jié)點(diǎn)與第i個(gè)節(jié)點(diǎn)之間的估計(jì)距離；hwi表示未知節(jié)點(diǎn)與第i個(gè)節(jié)點(diǎn)之間的跳步數(shù)。

3）判斷未知節(jié)點(diǎn)是否獲得了3 個(gè)或3 個(gè)以上的與已知節(jié)點(diǎn)的距離，若有，則說(shuō)明該點(diǎn)可以被定位。

式中：DV-Hop 中的距離表示在傳統(tǒng)DV-Hop 算法中根據(jù)三邊測(cè)量法或極大似然估計(jì)法來(lái)計(jì)算未知節(jié)點(diǎn)的位置，即xw與yw。

1.2 人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）是模擬蜜蜂的采蜜行為來(lái)解決生活中一些多維和多模的優(yōu)化問(wèn)題[11]。在該算法中，用蜜源表示解，用蜜源的花粉數(shù)量表示解的適應(yīng)值。并把蜜蜂分為雇傭蜂、跟隨蜂和探索蜂。在數(shù)量上雇傭蜂和跟隨蜂各占蜂群總數(shù)的一半。每種蜜蜂有著不同的職責(zé)，雇傭蜂的任務(wù)是尋找蜜源并將其信息共享，跟隨蜂則主要負(fù)責(zé)根據(jù)雇傭蜂提供的信息去采蜜，探索蜂負(fù)責(zé)在原有蜜源被拋棄后隨機(jī)尋找新的蜜源。

在算法的實(shí)現(xiàn)中，首先生成初始蜂群，然后不斷進(jìn)行迭代，最終得到收斂結(jié)果。具體實(shí)現(xiàn)步驟如下：

1）初始化蜂群

生成初始蜜蜂，并將其均勻地分布于尋優(yōu)空間，其中雇傭蜂與跟隨蜂的數(shù)量相等且為種群數(shù)的一半。產(chǎn)生一個(gè)新蜜源的公式如下：

式中：Xi,j代表第i個(gè)蜜源Xi的第j維度值，而Xi,jmax和Xi,jmin分別表示Xi的第j個(gè)分量的上限和下限。

2）找尋新蜜源階段

式中：ni,j代表新的蜜源；φij為在[-1，1]中的隨機(jī)數(shù)。

根據(jù)式（4）產(chǎn)生了新蜜源后，與原來(lái)的舊蜜源相比較，雇傭蜂擇優(yōu)采蜜。

3）蜜蜂舞蹈階段

蜜蜂會(huì)通過(guò)舞蹈來(lái)傳遞蜜源的信息，跟隨蜂通過(guò)觀察舞蹈，依據(jù)輪盤(pán)賭策略選擇蜜源開(kāi)采，這樣可以保證適應(yīng)值更高的蜜源開(kāi)采率更高。

4）丟棄蜜源

若一個(gè)蜜源在多次開(kāi)采后沒(méi)有得到更新，那么該蜜源會(huì)被拋棄，并重新進(jìn)入搜索階段，搜索階段的公式與式（3）一樣。

1.3 粒子群算法

粒子群算法源于針對(duì)鳥(niǎo)群捕食行為的研究，所以也叫做鳥(niǎo)群算法。PSO 算法的優(yōu)勢(shì)在于可以較為簡(jiǎn)便地求出多個(gè)粒子共存或合作時(shí)的最優(yōu)解。定義單個(gè)粒子在飛行過(guò)程中所獲取的最優(yōu)解為個(gè)體最優(yōu)解（pBest），在整個(gè)粒子群所獲得的最優(yōu)解記作全局最優(yōu)解（gBest），用N維速度Vi=(vi1,vi2,…,viN) 與位置Pi=(pi1,pi2,…,piN)進(jìn)行粒子狀態(tài)的表示，在算法中不斷通過(guò)自身速度與位置進(jìn)行狀態(tài)更新，可以產(chǎn)生新一代群體。

式（6）表示的是速度的更新值，該值取決于個(gè)體最優(yōu)解與全局最優(yōu)解，還與學(xué)習(xí)因子常數(shù)c1，c2有關(guān)。式（7）則表示位置的更新方式。

該方法的具體實(shí)現(xiàn)流程如下：

1）粒子群初始化，將粒子群中各個(gè)參數(shù)設(shè)置好；

2）在適應(yīng)度函數(shù)的基礎(chǔ)上，將每一個(gè)粒子適應(yīng)度值表示出來(lái)；

3）將粒子的當(dāng)前適應(yīng)度值與歷史最優(yōu)適應(yīng)度值比較，更新歷史最優(yōu)值；

4）將當(dāng)前適應(yīng)度與種群歷史最優(yōu)位置適應(yīng)度值比較，更新歷史最優(yōu)值；

5）運(yùn)用方程（5）與方程（6）進(jìn)行計(jì)算；

6）若獲得最優(yōu)值，則輸出最優(yōu)值結(jié)果，否則跳轉(zhuǎn)步驟2）繼續(xù)進(jìn)行迭代。

2 混合人工蜂群粒子群改進(jìn)的DV-Hop 算法

在未引入智能算法的傳統(tǒng)DV-Hop 算法中，未知節(jié)點(diǎn)與參考節(jié)點(diǎn)之間的線路復(fù)雜，僅僅依靠平均每跳距離或者加權(quán)每跳距離均不能很好地反映實(shí)際距離，所以得到的預(yù)測(cè)距離與實(shí)際距離之間存在一個(gè)誤差，若記該誤差為ε，則在DV-Hop 中的節(jié)點(diǎn)估算距離可以表示為：

為引入適應(yīng)度函數(shù)，將該公式進(jìn)行變形，將變量體現(xiàn)出來(lái)，并將其作為適應(yīng)度函數(shù)，式（9）也是算法的目標(biāo)函數(shù)。

根據(jù)式（9）可以利用人工蜂群算法進(jìn)行未知節(jié)點(diǎn)的計(jì)算。本文所提出的的混合方法在原有的人工蜂群算法中引入粒子群算法思想，在雇傭蜂尋找新蜜源時(shí)，由原來(lái)的式（5）進(jìn)行修改得到式（10）：

式中：ni,j代表新蜜源；ω代表粒子群算法中的慣性權(quán)重；c代表學(xué)習(xí)因子常數(shù)；Xi,j代表原始解；Xi,jbest 代表局部最優(yōu)解。由于在WSN 定位中，僅考慮在通信范圍內(nèi)尋找最優(yōu)解，所以不存在全局最優(yōu)。

雇傭蜂在尋找新蜜源時(shí)，按照局部最優(yōu)解提供的方向去找尋，但是若該點(diǎn)本身為最優(yōu)點(diǎn)，則需要運(yùn)用：這是為了防止陷入初始最優(yōu)解，不斷對(duì)最優(yōu)解進(jìn)行更新。算法的具體步驟如下：

1）初始化蜂群，隨機(jī)生成蜂群初始種群，均布于尋優(yōu)空間，其中雇傭蜂與跟隨蜂的數(shù)量相等且為種群數(shù)的一半。

2）雇傭蜂在尋優(yōu)區(qū)間內(nèi)尋優(yōu)，每次尋優(yōu)結(jié)束會(huì)更新最優(yōu)值，并增加訓(xùn)練數(shù)，若為最優(yōu)點(diǎn)，則進(jìn)行隨機(jī)優(yōu)化。

3）將已經(jīng)由迭代產(chǎn)生坐標(biāo)的未知節(jié)點(diǎn)進(jìn)行更新，當(dāng)做已知節(jié)點(diǎn)看待，并進(jìn)行下次迭代。

4）在訓(xùn)練過(guò)程中若發(fā)現(xiàn)有蜜源的訓(xùn)練數(shù)超過(guò)邊界值，則需要拋棄該蜜源，重新選擇新的蜜源。軟件的具體流程圖如圖1 所示。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證該算法是否能提高定位精度，將上述算法在Matlab 中進(jìn)行模擬仿真。在算法參數(shù)的確定中，人工蜂群算法中蜂群的初始大小與DV-Hop 的節(jié)點(diǎn)個(gè)數(shù)有關(guān)，并將各種網(wǎng)絡(luò)節(jié)點(diǎn)的參數(shù)進(jìn)行變化，測(cè)試在不同條件下傳統(tǒng)DV-Hop 的定位精度與本文方法的差異，搜索范圍均為100 m 的正方形區(qū)域，混合人工蜂群粒子群算法收斂條件為式（9）提出的適應(yīng)度ε≤10-4。

3.1 各方法定位精度比較

在以往的DV-Hop 算法優(yōu)化中，已經(jīng)有不少人提出了將一些智能算法引入，從而優(yōu)化DV-Hop 算法。其中，人工蜂群算法利用蜜蜂之間尋優(yōu)的正反饋機(jī)制，有效加快全局尋優(yōu)過(guò)程，并且算法中參數(shù)較少，但在接近最優(yōu)解時(shí)速度會(huì)變慢。這一缺點(diǎn)在粒子群算法中并未出現(xiàn)，而粒子群算法在后期精度無(wú)法得到進(jìn)一步提高，容易陷入局部最優(yōu)解。本文將這兩種算法相結(jié)合，首先在參數(shù)相同的情況下比較幾種算法的定位精度。

圖1 混合方法的流程圖Fig.1 Flowchart of hybrid method

WSN 的網(wǎng)絡(luò)參數(shù)邊界為100 m 的正方形，總節(jié)點(diǎn)數(shù)為100，已知節(jié)點(diǎn)個(gè)數(shù)為10，通信距離為20 m。對(duì)于人工蜂群算法的參數(shù)種群數(shù)量為50，最大循環(huán)數(shù)為1 000，蜜源的放棄參數(shù)為10。粒子群算法中粒子的慣性參數(shù)選為0.6，學(xué)習(xí)因子為2。利用Matlab 生成的模擬網(wǎng)絡(luò)節(jié)點(diǎn)圖如圖2 所示。

圖2 WSN 模擬節(jié)點(diǎn)圖Fig.2 Diagram of simulation nodes of WSN

針對(duì)該網(wǎng)絡(luò)，首先用傳統(tǒng)DV-Hop 算法進(jìn)行未知節(jié)點(diǎn)的定位，然后再分別利用人工蜂群算法、粒子群算法、混合算法進(jìn)行定位，從90 個(gè)未知節(jié)點(diǎn)中隨機(jī)取出30 個(gè)，比較他們的定位誤差。誤差比較圖如圖3 所示。

圖3 四種方法的定位相對(duì)誤差對(duì)比Fig.3 Comparison of relative errors for positioning of four methods

表1 為誤差精度的比較。從表1 中可以看出，在傳統(tǒng)的DV-Hop 算法中，對(duì)于未知的30 個(gè)節(jié)點(diǎn)的定位效果都浮動(dòng)很大，最大的相對(duì)誤差達(dá)到了72.12%，最小的相對(duì)誤差為20.19%，平均相對(duì)誤差為38.40%。在引入了算法進(jìn)行優(yōu)化后，定位精度得到了提升，從圖3反映的整體定位精度來(lái)看，定位精度由低到高依次是傳統(tǒng)DV-Hop算法、粒子群算法、人工蜂群算法、混合算法。本文提出的混合算法在同等條件下，定位的最大誤差為47.26%，最小為10.07%，平均降低了18.28%。同時(shí)也發(fā)現(xiàn)了在傳統(tǒng)DV-Hop 算法不能取得良好定位精度時(shí)，采用優(yōu)化算法有時(shí)也不能提高其精度，這或許是因?yàn)樵贒V-Hop算法中運(yùn)用了跳步數(shù)乘平均跳步距離所引入的誤差過(guò)大所導(dǎo)致的。

表1 四種方法的定位相對(duì)誤差對(duì)比Table 1 Comparison of relative errors for positioning of four methods %

本文提出的算法在收斂性上也要優(yōu)于僅僅使用單一算法進(jìn)行定位。

3.2 不同算法的收斂情況比較

三種定位算法的收斂性比較如圖4 所示。從圖4 中發(fā)現(xiàn)，本文算法與人工蜂群算法和粒子群算法相比收斂速度較快，定位函數(shù)值更準(zhǔn)確。本文算法當(dāng)?shù)螖?shù)為410 時(shí)，算法基本收斂，收斂值為10-12左右。雖然人工蜂群算法在320 次迭代就收斂，但陷入了局部最優(yōu)解，收斂值為10-6，粒子群算法也更早的陷入了局部最優(yōu)解。說(shuō)明本文的混合算法在定位中具有一定的優(yōu)勢(shì)，究其原因是在本文算法中優(yōu)化了算法粒子的尋優(yōu)項(xiàng)，這樣降低了由于算法速度引起算法收斂的問(wèn)題，通過(guò)擾動(dòng)因子有效降低算法的局部收斂可能性，使得算法能夠以更快的速度獲得最優(yōu)解。

圖4 三種算法收斂情況比較Fig.4 Comparison of convergence of three algorithms

4 結(jié) 論

本文針對(duì)傳統(tǒng)DV-Hop 算法中定位精度不高，誤差較大的問(wèn)題，提出混合蜂群粒子群的方法對(duì)該問(wèn)題進(jìn)行求解，并引入估算距離與跳步距離的差值的適應(yīng)度函數(shù)，通過(guò)優(yōu)化該值從而得到精確的定位，比以往的方法具有更好的效果。

通過(guò)實(shí)驗(yàn)仿真模擬，該算法在同樣的傳感器網(wǎng)絡(luò)條件下，相較于單一使用人工蜂群或者粒子群算法均具有一定的優(yōu)化性，且參數(shù)較少，操作方便，具有一定的實(shí)用價(jià)值。