多智能體蝙蝠算法在無線傳感器中的應(yīng)用*

尚俊娜，劉春菊，岳克強(qiáng)，李　林

（1.杭州電子科技大學(xué)通信工程學(xué)院，杭州310018；2.杭州電子科技大學(xué)電子與信息學(xué)院，杭州310018）

多智能體蝙蝠算法在無線傳感器中的應(yīng)用*

尚俊娜1*，劉春菊1，岳克強(qiáng)2，李林1

（1.杭州電子科技大學(xué)通信工程學(xué)院，杭州310018；2.杭州電子科技大學(xué)電子與信息學(xué)院，杭州310018）

針對(duì)無線傳感器網(wǎng)絡(luò)（WSNs）節(jié)點(diǎn)的定位誤差較大的問題，提出了一種新的具有局部搜索能力強(qiáng)的多智能體蝙蝠算法。改進(jìn)算法中對(duì)尋優(yōu)蝙蝠個(gè)體融入多智能體技術(shù)，通過鄰域競(jìng)爭(zhēng)合作算子以及自學(xué)習(xí)過程提高了算法全局搜索能力，避免算法陷入局部最優(yōu)，加快算法的收斂速度。通過對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真，改進(jìn)算法相比于其他算法，尋優(yōu)精度和進(jìn)化效率得到了較大的提高。隨后采用多智能體蝙蝠算法求解無線傳感節(jié)點(diǎn)定位問題，仿真結(jié)果表明改進(jìn)算法減少了測(cè)距誤差對(duì)定位精度的影響，提高了未知節(jié)點(diǎn)定位的精度，為無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位的實(shí)際應(yīng)用提供理論參考。

無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位；多智能體；蝙蝠算法；定位精度

EEACC:6150，6510Pdoi:10.3969/j.issn.1004-1699.2015.09.025

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身定位至關(guān)重要，在軍事和民用領(lǐng)域中有著廣泛的應(yīng)用前景，因此，研究無線傳感器節(jié)點(diǎn)定位十分必要。節(jié)點(diǎn)定位有基于測(cè)距和非測(cè)距兩種方式，其中測(cè)距定位算法具有定位精度相對(duì)較高、通信開銷較小等優(yōu)點(diǎn)，成為當(dāng)前研究的熱點(diǎn)。測(cè)距定位［1］包括節(jié)點(diǎn)測(cè)距和定位兩部分，首先通過接收信號(hào)強(qiáng)度值（Received Signal Strength Indicator，RSSI）、到達(dá)時(shí)間（Time of Advent，TOA）、到達(dá)角（Angle of Arrival，AOA）［2］等技術(shù)測(cè)量出待定位節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離，然后再通過三邊測(cè)量法、三角測(cè)量定位、極大似然估計(jì)等算法［3］實(shí)現(xiàn)待測(cè)節(jié)點(diǎn)的位置估計(jì)。無線傳感器節(jié)點(diǎn)定位問題可以轉(zhuǎn)換成一個(gè)多約束優(yōu)化問題，通過智能算法對(duì)節(jié)點(diǎn)進(jìn)一步優(yōu)化來提高定位精度［4-5］，尤其是精度高、容錯(cuò)能力強(qiáng)的算法成為研究的重點(diǎn)。

蝙蝠算法（Bat Algorithm，BA）具有模型簡(jiǎn)單［6］，尋優(yōu)精度高等特點(diǎn)，該算法逐漸成為研究的熱點(diǎn)。文獻(xiàn)［7］將無線傳感網(wǎng)節(jié)點(diǎn)定位的問題通過數(shù)學(xué)模型轉(zhuǎn)換為節(jié)點(diǎn)優(yōu)化問題，針對(duì)最小二乘算法節(jié)點(diǎn)定位的不足通過BA進(jìn)行優(yōu)化，節(jié)點(diǎn)定位精度得到提

項(xiàng)目來源:浙江省自然科學(xué)基金青年基金項(xiàng)目（LQ13F010010）；浙江省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)項(xiàng)目（2013TD03）

1　MA-BA算法

1.1標(biāo)準(zhǔn)BA算法基本原理

蝙蝠算法［10］是一種群體智能隨機(jī)搜索優(yōu)化算法，蝙蝠個(gè)體利用自身回聲定位能力，通過所發(fā)出的脈沖頻率、響度、脈沖發(fā)射的頻度的變化來捕獲獵物。在實(shí)際的優(yōu)化算法中，每只蝙蝠為搜索解空間的一個(gè)點(diǎn)，由適應(yīng)度函數(shù)來決定蝙蝠位置的優(yōu)劣。蝙蝠的每一次有效飛行就是BA算法的一次迭代更新。在t時(shí)刻，d維空間中，蝙蝠個(gè)體的飛行速度vi和空間位置xi的更新公式如下:

式中:fi是第i只蝙蝠個(gè)體所發(fā)出的的脈沖頻率，且fi∈［fmin，fmax］，β∈［0，1］是均勻分布的隨機(jī)向量。x*是該時(shí)刻下的全局最佳位置。個(gè)體更新后以發(fā)射脈沖的頻度ri為門限值隨機(jī)選取個(gè)體進(jìn)行最優(yōu)解擾動(dòng):

Xnew=x*+σAt（4）

σ為［-1，1］上的隨機(jī)數(shù)值，At為某一個(gè)時(shí)間中所有蝙蝠個(gè)體平均求得的響度。

蝙蝠個(gè)體在尋找獵物的過程中，一開始發(fā)射脈沖的頻度r較低，脈沖響度A較大，一旦發(fā)現(xiàn)獵物，就逐漸減小脈沖音強(qiáng)和增大發(fā)射脈沖的頻度。A與r在發(fā)現(xiàn)獵物后的更新公式如下:

1.2MA-BA算法

標(biāo)準(zhǔn)BA算法中蝙蝠個(gè)體由于局部搜索能力不強(qiáng)容易陷入局部最優(yōu)解，我們從智能體系統(tǒng)的角度出發(fā)，把蝙蝠算法中的個(gè)體作為一個(gè)具有局部感知、競(jìng)爭(zhēng)協(xié)作和自學(xué)習(xí)能力的智能體，通過智能體與環(huán)境以及智能體間的相互作用達(dá)到全局優(yōu)化的目的［11］，據(jù)此本文提出基于多智能體的蝙蝠算法。通過將BA算法中的個(gè)體視為多智能體系統(tǒng)（Multi-Agent System，MAS）中的智能體，借助智能體的基本原理和操作，蝙蝠個(gè)體在搜索空間能夠由自身的局部搜索逐步擴(kuò)散到全局搜索，并通過自學(xué)習(xí)不斷優(yōu)化自身，尋優(yōu)迅速跳出局部極值避免早熟，更快更準(zhǔn)尋得全局最優(yōu)解。通常每個(gè)Agent具有以下特征:

①單個(gè)Agent的定義

在MA-BA算法中，每一個(gè)Agent相當(dāng)于BA算法中的一個(gè)蝙蝠個(gè)體，可以感知所在的局部環(huán)境，實(shí)現(xiàn)與鄰域Agent的競(jìng)爭(zhēng)合作以及自身學(xué)習(xí)過程，根據(jù)環(huán)境改變自己同時(shí)也改變所處環(huán)境。每個(gè)個(gè)體位置在解空間中的優(yōu)劣是由被優(yōu)化的目標(biāo)函數(shù)所決定，因此每一個(gè)Agent的目的是在搜索空間內(nèi)擁有局部最小適應(yīng)度值。

②Agent網(wǎng)格環(huán)境

由于每一個(gè)Agent相當(dāng)于BA算法中的一個(gè)個(gè)體，MAS體系結(jié)構(gòu)可以借鑒PSO的拓?fù)浣Y(jié)構(gòu)。本文同樣選取了結(jié)構(gòu)簡(jiǎn)單穩(wěn)定的Von Neuman結(jié)構(gòu)，如圖1所示。每一網(wǎng)絡(luò)節(jié)點(diǎn)就表示MA-BA算法中的一個(gè)Agent，即一個(gè)蝙蝠個(gè)體，而網(wǎng)絡(luò)節(jié)點(diǎn)的位置坐標(biāo)就表示Agent在網(wǎng)格中固定位置。每一網(wǎng)格節(jié)點(diǎn)除了包含自身節(jié)點(diǎn)固定位置坐標(biāo)以外還包括蝙蝠個(gè)體在解空間的位置和速度。圖1中共有m×n個(gè)Agent，即MA-BA算法中個(gè)體的總數(shù)。

圖1　Von Neumann結(jié)構(gòu)圖

③Agent的局部環(huán)境

Agent的局部環(huán)境是由每個(gè)Agent的所有鄰居構(gòu)成即鄰域。假設(shè) Ai，j表示Von Neuman結(jié)構(gòu)中位于位置（i，j）的智能體，那么它的鄰域Agent可以由式（7）被定義:

④Agent的行動(dòng)策略

在MA-BA算法中，每一個(gè)Agent與其鄰域的智能體進(jìn)行競(jìng)爭(zhēng)合作，假設(shè)Agent Ai，j在解空間的位置向量為（a1，a2，…，aN），其鄰域個(gè)體可以有式（7）唯一確定。設(shè)Mi，j=（m1，m2，…，mN）為其鄰域中具有最小適應(yīng)度值的最優(yōu)個(gè)體，若Ai，j與Mi，j滿足下式（8），則說明Mi，j在解空間中的位置優(yōu)于Ai，j，對(duì)Ai，j在解空間中按照式（9）進(jìn)行重新賦值。若不滿足式（8），則保留Ai，j在解空間中的位置。f（Mi，j）≤f（Ai，j）（8）

從式（9）知，Ai，j解空間位置更新后不僅保留了自身有用信息同時(shí)吸收了最優(yōu)鄰居Mi，j的有用信息，使其適應(yīng)度值進(jìn)一步減小。通過Agent的行動(dòng)策略，Agent自身信息在Agent局部環(huán)境中的逐步傳遞，同時(shí)與全局最優(yōu)Agent進(jìn)行信息交換，通過Agent之間的信息的交流對(duì)其行動(dòng)策略進(jìn)行修正，增強(qiáng)了局部搜索能力和算法尋優(yōu)效率。

⑤Agent的自學(xué)習(xí)過程

要達(dá)到MAS的適應(yīng)性，智能體的自我學(xué)習(xí)能力是不可缺少的［12］。為了防止尋優(yōu)算法的計(jì)算復(fù)雜度過大，不利于算法的計(jì)算效率，我們一般選取較小的搜索半徑sR構(gòu)建智能體網(wǎng)格，在小范圍內(nèi)擴(kuò)展全局最優(yōu)個(gè)體搜索空間。通過這個(gè)網(wǎng)絡(luò)和已知的信息進(jìn)行局部尋優(yōu)，用尋找到更好的解來替換原來解空間中位置。通過自學(xué)習(xí)過程，最優(yōu)個(gè)體更可能找到全局最優(yōu)位置，從而可以指導(dǎo)其他個(gè)體盡快找到最優(yōu)解，提高進(jìn)化效率。

假設(shè)Agent Li，j在解空間中的位置為L(zhǎng)i，j=（a1，a2，…，aN），構(gòu)造一個(gè)類似圖1結(jié)構(gòu)的網(wǎng)格，大小為n=sLsize×sLsize。在該Agent局部環(huán)境中的個(gè)體記為sAi′，j′，i′，j′∈｛1，2，…，n｝，每一sAi′，j′有式（10）進(jìn)行賦。

式中:k=1，2，…，N，sR為智能體能夠進(jìn)行搜索到的空間范圍，一般取值范圍為［0，1］。由于在該MAS結(jié)構(gòu)中，Agent個(gè)體較少，能快速地將信息傳遞到整個(gè)環(huán)境，通過設(shè)定的迭代次數(shù)完成最優(yōu)解替換。

2.3MA-BA算法步驟

①按照?qǐng)D1的形式構(gòu)造Lsize*Lsize的Agent的生存環(huán)境，初始化各個(gè)參數(shù)以及Agent在解空間中位置x和速度v。

②計(jì)算種群每個(gè)Agent的適應(yīng)度值Fitness（i），根據(jù)式（7）求解出Agent Ai，j的鄰居，在所有鄰居個(gè)體中尋找適應(yīng)度值最小的最優(yōu)鄰居Mi，j，并記錄全局最優(yōu)解Agent（x*）。

③根據(jù)式（8）、式（9）進(jìn)行鄰居間競(jìng)爭(zhēng)合作操作，并改變失敗個(gè)體在解空間中的位置，重新計(jì)算所有Agent適應(yīng)度值Fitness（i），并記錄全局最優(yōu)Agent（x*）和對(duì)應(yīng)的適應(yīng)度值 f（x*）。

④通過式（1）～式（3）更新每個(gè)Agent解空間中的位置x和速度v，并記錄更新后的個(gè)體的適應(yīng)度值為Fnew。

⑤通過條件rand1＞r（i）來判斷是否進(jìn)行最優(yōu)解擾動(dòng)來產(chǎn)生新解。如果滿足條件，則根據(jù)式（4）產(chǎn)生局部解來替代當(dāng)前解，并替換當(dāng)前適應(yīng)度值。如果不滿足則跳過該步。

⑥如果更新后的蝙蝠個(gè)體滿足條件Fnew＜Fitness（i）&rand2＜A（i），則接受該新解，替換個(gè)體原來的位置狀態(tài)并根據(jù)式（5），式（6）開始脈沖響度A和發(fā)射脈沖的頻度r更新。如果不滿足條件表示這該個(gè)體的位置更新不成功，跳過該步。

⑦如果接受的新解對(duì)應(yīng)的適應(yīng)度值Fnew＜f（x*），則替換全局最優(yōu)解及其對(duì)應(yīng)的最小適應(yīng)度值。否則跳過該步。

⑧對(duì)全局最優(yōu)解Agent（x*）重新構(gòu)造搜索半徑為sR的小規(guī)模網(wǎng)格，按照式（10）、式（11）進(jìn)行自學(xué)習(xí)過程操作，尋找適應(yīng)度值更小的個(gè)體Agent（x′*）替換原來Agent（x*）。

⑨若算法搜索到最大迭代次數(shù)或者要求的精度則跳出循環(huán)輸出結(jié)果，否則返回步驟2）繼續(xù)搜索。

1.3MA-BA算法性能測(cè)試

為了驗(yàn)證本文提出的MA-BA算法的性能，選取了4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真測(cè)試，并與文獻(xiàn)［14］所改進(jìn)的具有混沌搜索策略的蝙蝠算法（Chaos bat algorithm，CBA）、標(biāo)準(zhǔn)BA算法和基本PSO算法進(jìn)行對(duì)比。

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

蝙蝠算法中各種參數(shù)設(shè)置目前沒有明確的理論依據(jù)，因此本文所設(shè)置的參數(shù)值根據(jù)反復(fù)實(shí)驗(yàn)獲得的經(jīng)驗(yàn)值來確定。MA-BA算法中:個(gè)體總數(shù)N= 64，網(wǎng)格Lsize×Lsize=8×8，維數(shù)d=30，搜索脈沖頻率范圍［0，100］，最大脈沖頻度r=0.5，最大脈沖音強(qiáng)A=0.25，脈沖音強(qiáng)衰減系數(shù)γ=0.95，脈沖頻度增加系數(shù) α=0.05，自學(xué)習(xí)半徑sR=4，迭代sGen=10。CBA、BA算法中各個(gè)參數(shù)與MA-BA算法保持一致。PSO算法采用文獻(xiàn)［15］中所提出的線性減少的慣性權(quán)重:Wmax=0.9，Wmin=0.4；學(xué)習(xí)因子:C1=0.5 C2= 1.4962。上述算法最大迭代次數(shù)均為200次，每種算法獨(dú)立運(yùn)行30次。其中，PSO表示基本粒子群算法，BA表示基本蝙蝠算法，CBA表示具有混沌搜索策略的蝙蝠算法，MA-BA表示多智能體蝙蝠算法。

1.3.2標(biāo)準(zhǔn)測(cè)試函數(shù)

實(shí)驗(yàn)選取的測(cè)試函數(shù)介紹如下:

Sphere函數(shù)該函數(shù)為非線性連續(xù)單峰函數(shù)，計(jì)算簡(jiǎn)單，容易實(shí)現(xiàn)，用于檢驗(yàn)算法的精確度。

②Rosebrock函數(shù):

搜索空間為［-2.048，2.048］；

Rosenbrack函數(shù)是單峰連續(xù)函數(shù)，其極小點(diǎn)所在的山谷易于找到，但取值區(qū)間走勢(shì)平坦，很難收斂到全局最優(yōu)點(diǎn)，是測(cè)試算法全局收斂性能的經(jīng)典函數(shù)。

③Griewank函數(shù)

搜索空間為［-600，600］；

Griewank函數(shù)是多峰多極值函數(shù)，有眾多局部極值，種群極易陷入局部極值中，主要用來評(píng)價(jià)算法的探索、開發(fā)能力。

④Ratrigin函數(shù):

搜索空間為［-5.12，5.12］；

Rastrigrin函數(shù)為多極值函數(shù)，加入的余弦函數(shù)使函數(shù)的優(yōu)化更為復(fù)雜，在解空間內(nèi)存在大約10 d個(gè)（d為解空間維數(shù)）局部極小點(diǎn)，極易陷入局部最優(yōu)。

1.3.3仿真效果分析

圖2　標(biāo)準(zhǔn)測(cè)試函數(shù)尋優(yōu)曲線圖

圖2顯示了以上4個(gè)標(biāo)準(zhǔn)函數(shù)的尋優(yōu)曲線，其中f1、f2、f3理論上全局最優(yōu)解為:min（f（0，0，…，0））=0。f4的全局最優(yōu)解min（f（1，1，…，1）=0，規(guī)定當(dāng)優(yōu)化精度達(dá)到10-6時(shí)，算法成功找到全局最優(yōu)解。對(duì)于具有混沌搜索策略的CBA算法，采用對(duì)精英個(gè)體進(jìn)行混沌優(yōu)化，然而對(duì)于復(fù)雜的問題其尋優(yōu)效果并沒有較大提高。MA-BA算法則是在每個(gè)個(gè)體所處的局部環(huán)境中通過競(jìng)爭(zhēng)合作尋找最優(yōu)個(gè)體，具有較強(qiáng)的適應(yīng)能力和搜索能力，同時(shí)最優(yōu)個(gè)體具有自學(xué)習(xí)能力可以有效引導(dǎo)全局進(jìn)化方向加快算法尋優(yōu)速度。從圖2可以看出，對(duì)于單模的Sphere函數(shù)，四種算法均能尋找到最優(yōu)解，但是MA-BA算法的優(yōu)化精度比其他三種算法提高很多，尋優(yōu)效率大幅度提高。對(duì)于Griewank函數(shù)，Rosenbrack函數(shù)和Rastrigrin函數(shù)的尋優(yōu)曲線，MA-BA算法的優(yōu)化性能均明顯優(yōu)于其他算法，不僅尋優(yōu)精度高而且收斂速度快，在較少的迭代次數(shù)內(nèi)達(dá)到所設(shè)定的最優(yōu)解，體現(xiàn)了MA-BA算法由于多智能體技術(shù)的融入，使得每個(gè)Agent局部搜索能力大大增強(qiáng)，可以跳出局部最優(yōu)避免早熟。

在標(biāo)準(zhǔn)函數(shù)的測(cè)試中，對(duì)于單模函數(shù)，以其理論最優(yōu)值的1‰為標(biāo)準(zhǔn)，多模函數(shù)以最優(yōu)理論值5‰為標(biāo)準(zhǔn)，如果最小適應(yīng)度值小于以上標(biāo)準(zhǔn)說明該算法取得了正確解，用尋優(yōu)成功率來表示算法的穩(wěn)定度。表1中是圖2中各個(gè)函數(shù)的測(cè)試結(jié)果，解空間為30維，取30次尋優(yōu)值結(jié)果進(jìn)行平均，其他仿真參數(shù)如上文中所設(shè)置。由表1可知，無論是病態(tài)單峰函數(shù)還是具有較多局部極值的多峰函數(shù)，相比CBA、BA和PSO，MA-BA算法的尋優(yōu)成功率較高，體現(xiàn)了算法的魯棒性。平均最小適應(yīng)度值很接近于理論值最優(yōu)解，說明MA-BA算法的局部搜索能力比較強(qiáng)，能跳出局部最優(yōu)解，使算法具有較高的優(yōu)化精度。

表1　標(biāo)準(zhǔn)函數(shù)測(cè)試結(jié)果

2　MA-BA算法在無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位中的應(yīng)用

下面將MA-BA算法用于無線傳感器網(wǎng)絡(luò)定位的問題上來驗(yàn)證本算法在最優(yōu)解尋優(yōu)精度上的性能。對(duì)于傳感器定位問題，由于傳感器節(jié)點(diǎn)上自帶的RSSI指示功能，采用基于RSSI算法測(cè)距并不增加硬件設(shè)備成本［16］，所以本算法建立在RSSI測(cè)距的基礎(chǔ)上對(duì)定位計(jì)算進(jìn)行優(yōu)化。在仿真研究中，以平均定位誤差A(yù)VE作為定位誤差大小的評(píng)判標(biāo)準(zhǔn)，為了便于比較，所有定位誤差均為絕對(duì)誤差，其公式如下:

其中:（x，y）為預(yù)測(cè)位置，（xi，yi）為實(shí)際位置，M為已知節(jié)點(diǎn)的總數(shù)。

2.1無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位數(shù)學(xué)模型

設(shè)傳感器網(wǎng)絡(luò)有M個(gè)已知節(jié)點(diǎn)，N個(gè)未知節(jié)點(diǎn)。M個(gè)已知節(jié)點(diǎn)坐標(biāo)分別為（x1，y1），（x2，y2），…（xM，xN），對(duì)于任意一個(gè)未知節(jié)點(diǎn)D（x，y），測(cè)得到各個(gè)錨節(jié)點(diǎn)的距離分別為d1，d2，…，dM那么，未知節(jié)點(diǎn)的位置可以有方程求解出:

在實(shí)際的測(cè)距中總是存在誤差，所以定位問題就轉(zhuǎn)化為函數(shù)

求最小值的優(yōu)化問題。由上一節(jié)可知，利用MA-BA算法求解優(yōu)化問題時(shí)，該算法具有較強(qiáng)的局部搜索能力和較高的尋優(yōu)進(jìn)化效率，能避免個(gè)體陷入局部最優(yōu)解，具有較高的優(yōu)化精度和收斂速度。將該方法用于函數(shù) f（x，y）尋找最優(yōu)解的問題上，可以減小測(cè)距誤差的影響，提高未知節(jié)點(diǎn)的定位精度。

2.2仿真分析

仿真實(shí)驗(yàn)以MATLAB 7.0為平臺(tái)，節(jié)點(diǎn)的通信半徑設(shè)置為10 m，30個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在30 m×30 m的正方形區(qū)域內(nèi)，測(cè)距誤差在10%以下，錨節(jié)點(diǎn)個(gè)數(shù)為5，仿真算法中參數(shù)設(shè)置為上文1.3.1節(jié)所示，最大迭代次數(shù)為200次，每一個(gè)節(jié)點(diǎn)定位預(yù)測(cè)值選取20次平均值。分別用MA-BA算法和文獻(xiàn)［14］中采用CBA算法進(jìn)行節(jié)點(diǎn)定位結(jié)果進(jìn)行對(duì)比，結(jié)果如圖3、圖4所示。

圖3　未知節(jié)點(diǎn)預(yù)測(cè)比較圖

圖4　兩種算法的平均尋優(yōu)曲線

圖3是對(duì)30個(gè)未知節(jié)點(diǎn)預(yù)測(cè)位置的仿真，由圖3可知，BA算法預(yù)測(cè)位置與實(shí)際位置有一定的差距，定位精度不是很理想。MA-BA算法預(yù)測(cè)位置與節(jié)點(diǎn)實(shí)際位置幾乎完全重合，絕對(duì)誤差值較小，顯示了Agent個(gè)體在尋優(yōu)方面具有較強(qiáng)的局部搜索能力和全局尋優(yōu)能力，減少了測(cè)距誤差對(duì)定位精度的影響。圖4是在10%的誤差范圍內(nèi)圖3中30個(gè)節(jié)點(diǎn)的平均優(yōu)化曲線，從圖中可知，MA-BA算法的優(yōu)化精度和收斂速度明顯好于BA算法，多智能體技術(shù)使算法效率得到了很大的提高。

在基于RSSI測(cè)距定位的算法中，測(cè)距誤差對(duì)未知節(jié)點(diǎn)定位精度影響很大，在不同的測(cè)距誤差下MA-BA，CBA，BA，PSO的平均定位誤差如圖5所示。其中錨節(jié)點(diǎn)個(gè)數(shù)為10。從圖5可知，在5%內(nèi)的測(cè)距誤差下，MA-BA，CBA，BA均能達(dá)到較高的精度，但是隨著測(cè)距誤差的增加，與文獻(xiàn)［7］中結(jié)果相比較，MA-BA算法由于個(gè)體間的競(jìng)爭(zhēng)合作及自學(xué)能力，增強(qiáng)了局部和全局搜索能力有效降低了測(cè)距誤差對(duì)定位精度的影響，使其性能明顯優(yōu)于BA算法。當(dāng)測(cè)距誤差在15%到30%之間時(shí)，CBA，BA和PSO對(duì)測(cè)距誤差比較敏感使得平均定位誤差明顯增加而MA-BA算法的整體曲線整體變化比較平穩(wěn)，誤差忍受力較強(qiáng)性能比較強(qiáng)，算法性能比較穩(wěn)定。

圖5　測(cè)距誤差對(duì)定位性能的影響

圖6是不同算法在15%的測(cè)距誤差內(nèi)不同錨節(jié)點(diǎn)個(gè)數(shù)情況下平均定位誤差曲線圖。從圖中可知，MA-BA算法可以利用較少的錨節(jié)點(diǎn)實(shí)現(xiàn)高精度節(jié)點(diǎn)位置預(yù)測(cè)，整條曲線變化比較緩慢，利用MA-BA算法具有尋優(yōu)精度高的優(yōu)勢(shì)來補(bǔ)償定位精度對(duì)錨節(jié)點(diǎn)個(gè)數(shù)的依賴，而BA算法和PSO算法則對(duì)錨節(jié)點(diǎn)個(gè)數(shù)依賴性較強(qiáng)，平均定位誤差變化比較劇烈。雖然CBA算法曲線變化緩慢但是整體上定位精度沒有MA-BA算法的精度高。因此在相同的定位精度下MA-BA算法可以大大節(jié)省定位成本，有較大的應(yīng)用前景。

圖6　錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位性能的影響

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

針對(duì)基本蝙蝠算法中蝙蝠個(gè)體局部搜索能力不強(qiáng)易陷入局部最優(yōu)解的缺點(diǎn)，提出了基于多智能體的蝙蝠算法，對(duì)蝙蝠個(gè)體賦予局部感知、競(jìng)爭(zhēng)合作和自我學(xué)習(xí)的能力，通過個(gè)體Agent之間的相互作用增強(qiáng)了蝙蝠個(gè)體局部和全局的搜索能力，使個(gè)體迅速跳出局部最優(yōu)解避免早熟，提高了算法的進(jìn)化效率，能更快更迅速的找到全局最優(yōu)解。通過對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真，驗(yàn)證了MA-BA算法具有高精度的全局尋優(yōu)能力以及收斂速度快的優(yōu)點(diǎn)。將多智能體蝙蝠算法應(yīng)用到無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位中，仿真結(jié)果表明MA-BA算法不僅對(duì)測(cè)距誤差的忍受能力較強(qiáng)，而且可以在較少的錨節(jié)點(diǎn)個(gè)數(shù)下實(shí)現(xiàn)精確定位，節(jié)約定位成本。

［1］ Patwari N，Ash J N，Kyperountas S，et al.Locating the Nodes:Cooperative Localization in Wireless Sensor Networks［J］.IEEE Signal Processing Magazine，2005，22（4）:54-69.

［2］ Niculescu D，Bath B.Localized Positioning in ad-hoc Networks［J］.IEEE International Workshop on Sensor Network Protocols And Applications，Publish Elsevier Ad Hoc Networks，2003，1 （23）:421-150.

［3］ 程海軍.基于RSSI的無線傳感網(wǎng)絡(luò)定位算法的改進(jìn)研究［D］.重慶:重慶理工大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院，2013:29-32.

［4］ 李牧東，熊搖偉，梁搖青.基于人工蜂群改進(jìn)算法的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào).2013，26（2）:241-245.

［5］ 曹欲曉，嚴(yán)奎，徐金寶.一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-HOP定位算法［J］.傳感技術(shù)學(xué)報(bào).2015，28（3）:424-430.

［6］ Tsai P W，Pan J S，Liao B Y，et al.Bat Algorithm Inspired Algorithm for Solving Numerical Optimization Problems.Applied Mechanics and Materials，2012.

［7］ 王戰(zhàn)備.基于蝙蝠算法的無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50（11）:90-94.

［8］ 譚愛平，陳浩，吳伯橋.基于BADV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50（17）:125-129.

［9］ 康琦，汪鐳，吳啟迪.群體智能與人工生命［J］.模式識(shí)別與人工智能，2005，18（6）:689-697.

［10］Yang Xinshe.A New Meta-Heuristic Bat Inspired Algorithm［M］// Nature Inspired Cooperative Strategies for Optimization.Berlin: Springer-Verlag，2010:65-74.

［11］趙波，曹一家.電力系統(tǒng)無功優(yōu)化的多智能體粒子群優(yōu)化算法［J］.中國(guó)電機(jī)工程學(xué)報(bào)，2005，3（5）:1-7.

［12］陳自郁.粒子群優(yōu)化的鄰居拓?fù)浣Y(jié)構(gòu)和算法改進(jìn)研究［D］.浙江:浙江大學(xué)，2009.

［13］肖琨，黃摯雄.多智能體粒子群算法在配電網(wǎng)絡(luò)重構(gòu)中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（8）:221-2244.

［14］劉長(zhǎng)平，葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真［J］.系統(tǒng)仿真學(xué)報(bào)，2013，25（6）:1183-1188.

［15］Shi Y，Eberhart R.A Modified Particle Swarm Optimizer［C］//Proceedings of IEEE International Conference on Evolutionary Computation.Anchorage，USA:IEEE，1998:69-73.

［16］方震，趙湛，郭鵬，等.基于RSSI測(cè)距分析［J］.傳感技術(shù)學(xué)報(bào)，2007，20（11）:2526-2571.

尚俊娜（1979-），女，河南開封人，副教授，博士，主要研究方向?yàn)橥ㄐ判盘?hào)處理、智能算法；

劉春菊（1988-），女，河南許昌人，碩士研究生，主要研究方向?yàn)橹悄芩惴ǎ?/p>

岳克強(qiáng)（1984-），男，河南信陽(yáng)人，講師，博士，主要研究方向?yàn)檫M(jìn)化計(jì)算、通信信號(hào)處理。

The Multi-Agent Bat Algorithm Applied to Wireless Sensor Networks*

SHANG Junna1*，LIU Chunju1，YUE Keqiang2，LI Lin1
（1.College of Telecommunication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China: 2.College of Electrical and Information Engineering，Hangzhou Dianzi University，Hangzhou 310018，China）

In order to solve the node location error in wireless sensor networks（WSNs），this paper proposes a new multi-agent bat algorithm，which possesses favorable local searching ability.In the proposed algorithm，the bat individual is a agent，which could compete and cooperate with its agent neighbor areas to improve the efficiency of local searching.In this way the multi-agent bat algorithm（MA-BA）could avoid the algorithm into a local optimum and increase the convergence speed.Simulation results for standard test functions indicate that the proposed algorithm remarkably improves the global optimizing ability and evolutionary efficiency compared to other algorithms.Through implementing the MA-BA to node location prediction，the precision of the unknown node location could be improved due to decreasing the ranging error and has a certain significance to practical application of wireless sensor network node localization.

WSNs node localization；multi-agent；bat algorithm；accuracy

TP393

A

1004-1699（2015）09-1418-07

2015-04-02修改日期:2015-06-29高。文獻(xiàn)［8］將BA算法與DV-Hop算法相結(jié)合，在DV-HOP的第三階段利用蝙蝠算法代替最小二乘法來計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，降低了平均跳距導(dǎo)致的定位誤差，定位精度有所改善。但基本BA算法存在易陷入局部最優(yōu)、發(fā)生過早收斂、后期收斂速度較慢等問題［9］其性能有待提高。本文針對(duì)基本蝙蝠算法的缺點(diǎn)，提出了基于多智能體蝙蝠算法（Multi-Agent Bat Algorithm，MA-BA）。建議算法中通過采用基本蝙蝠算法的拓?fù)浣Y(jié)構(gòu)來構(gòu)建多智能體的體系結(jié)構(gòu)，將每一個(gè)蝙蝠個(gè)體作為一個(gè)智能體，通過與鄰域的智能體競(jìng)爭(zhēng)、合作以及自我學(xué)習(xí)，從而避免算法陷入局部最優(yōu)，提高算法的收斂速度，個(gè)體的更新機(jī)制減少了算法不可行解的產(chǎn)生，提高了算法效率。通過對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)仿真，改進(jìn)的MA-BA算法在尋優(yōu)精度上相比于基本BA算法有較大提高，同時(shí)將其應(yīng)用在無線傳感器節(jié)點(diǎn)定位的應(yīng)用中，節(jié)點(diǎn)的平均定位誤差相對(duì)較低，獲得了比較理想的節(jié)點(diǎn)定位結(jié)果。