尚俊娜，劉春菊，岳克強(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）

針對無線傳感器網(wǎng)絡(luò)（WSNs）節(jié)點(diǎn)的定位誤差較大的問題，提出了一種新的具有局部搜索能力強(qiáng)的多智能體蝙蝠算法。改進(jìn)算法中對尋優(yōu)蝙蝠個體融入多智能體技術(shù)，通過鄰域競爭合作算子以及自學(xué)習(xí)過程提高了算法全局搜索能力，避免算法陷入局部最優(yōu)，加快算法的收斂速度。通過對標(biāo)準(zhǔn)測試函數(shù)的仿真，改進(jìn)算法相比于其他算法，尋優(yōu)精度和進(jìn)化效率得到了較大的提高。隨后采用多智能體蝙蝠算法求解無線傳感節(jié)點(diǎn)定位問題，仿真結(jié)果表明改進(jìn)算法減少了測距誤差對定位精度的影響，提高了未知節(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)定位有基于測距和非測距兩種方式，其中測距定位算法具有定位精度相對較高、通信開銷較小等優(yōu)點(diǎn)，成為當(dāng)前研究的熱點(diǎn)。測距定位［1］包括節(jié)點(diǎn)測距和定位兩部分，首先通過接收信號強(qiáng)度值（Received Signal Strength Indicator，RSSI）、到達(dá)時間（Time of Advent，TOA）、到達(dá)角（Angle of Arrival，AOA）［2］等技術(shù)測量出待定位節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離，然后再通過三邊測量法、三角測量定位、極大似然估計(jì)等算法［3］實(shí)現(xiàn)待測節(jié)點(diǎn)的位置估計(jì)。無線傳感器節(jié)點(diǎn)定位問題可以轉(zhuǎn)換成一個多約束優(yōu)化問題，通過智能算法對節(jié)點(diǎn)進(jìn)一步優(yōu)化來提高定位精度［4-5］，尤其是精度高、容錯能力強(qiáng)的算法成為研究的重點(diǎn)。

蝙蝠算法（Bat Algorithm，BA）具有模型簡單［6］，尋優(yōu)精度高等特點(diǎn)，該算法逐漸成為研究的熱點(diǎn)。文獻(xiàn)［7］將無線傳感網(wǎng)節(jié)點(diǎn)定位的問題通過數(shù)學(xué)模型轉(zhuǎn)換為節(jié)點(diǎn)優(yōu)化問題，針對最小二乘算法節(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)化算法，蝙蝠個體利用自身回聲定位能力，通過所發(fā)出的脈沖頻率、響度、脈沖發(fā)射的頻度的變化來捕獲獵物。在實(shí)際的優(yōu)化算法中，每只蝙蝠為搜索解空間的一個點(diǎn)，由適應(yīng)度函數(shù)來決定蝙蝠位置的優(yōu)劣。蝙蝠的每一次有效飛行就是BA算法的一次迭代更新。在t時刻，d維空間中，蝙蝠個體的飛行速度vi和空間位置xi的更新公式如下:

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

Xnew=x*+σAt（4）

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

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

1.2MA-BA算法

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

①單個Agent的定義

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

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

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

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

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

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

④Agent的行動策略

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

從式（9）知，Ai，j解空間位置更新后不僅保留了自身有用信息同時吸收了最優(yōu)鄰居Mi，j的有用信息，使其適應(yīng)度值進(jìn)一步減小。通過Agent的行動策略，Agent自身信息在Agent局部環(huán)境中的逐步傳遞，同時與全局最優(yōu)Agent進(jìn)行信息交換，通過Agent之間的信息的交流對其行動策略進(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)個體搜索空間。通過這個網(wǎng)絡(luò)和已知的信息進(jìn)行局部尋優(yōu)，用尋找到更好的解來替換原來解空間中位置。通過自學(xué)習(xí)過程，最優(yōu)個體更可能找到全局最優(yōu)位置，從而可以指導(dǎo)其他個體盡快找到最優(yōu)解，提高進(jìn)化效率。

假設(shè)Agent Li，j在解空間中的位置為Li，j=（a1，a2，…，aN），構(gòu)造一個類似圖1結(jié)構(gòu)的網(wǎng)格，大小為n=sLsize×sLsize。在該Agent局部環(huán)境中的個體記為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個體較少，能快速地將信息傳遞到整個環(huán)境，通過設(shè)定的迭代次數(shù)完成最優(yōu)解替換。

2.3MA-BA算法步驟

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

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

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

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

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

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

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

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

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

1.3MA-BA算法性能測試

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

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

蝙蝠算法中各種參數(shù)設(shè)置目前沒有明確的理論依據(jù)，因此本文所設(shè)置的參數(shù)值根據(jù)反復(fù)實(shí)驗(yàn)獲得的經(jīng)驗(yàn)值來確定。MA-BA算法中:個體總數(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算法中各個參數(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)測試函數(shù)

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

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

②Rosebrock函數(shù):

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

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

③Griewank函數(shù)

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

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

④Ratrigin函數(shù):

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

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

1.3.3仿真效果分析

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

圖2顯示了以上4個標(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時，算法成功找到全局最優(yōu)解。對于具有混沌搜索策略的CBA算法，采用對精英個體進(jìn)行混沌優(yōu)化，然而對于復(fù)雜的問題其尋優(yōu)效果并沒有較大提高。MA-BA算法則是在每個個體所處的局部環(huán)境中通過競爭合作尋找最優(yōu)個體，具有較強(qiáng)的適應(yīng)能力和搜索能力，同時最優(yōu)個體具有自學(xué)習(xí)能力可以有效引導(dǎo)全局進(jìn)化方向加快算法尋優(yōu)速度。從圖2可以看出，對于單模的Sphere函數(shù)，四種算法均能尋找到最優(yōu)解，但是MA-BA算法的優(yōu)化精度比其他三種算法提高很多，尋優(yōu)效率大幅度提高。對于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ù)的融入，使得每個Agent局部搜索能力大大增強(qiáng)，可以跳出局部最優(yōu)避免早熟。

在標(biāo)準(zhǔn)函數(shù)的測試中，對于單模函數(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中各個函數(shù)的測試結(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ù)測試結(jié)果

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

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

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

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

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

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

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

2.2仿真分析

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

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

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

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

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

圖5　測距誤差對定位性能的影響

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

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

3　結(jié)束語

針對基本蝙蝠算法中蝙蝠個體局部搜索能力不強(qiáng)易陷入局部最優(yōu)解的缺點(diǎn)，提出了基于多智能體的蝙蝠算法，對蝙蝠個體賦予局部感知、競爭合作和自我學(xué)習(xí)的能力，通過個體Agent之間的相互作用增強(qiáng)了蝙蝠個體局部和全局的搜索能力，使個體迅速跳出局部最優(yōu)解避免早熟，提高了算法的進(jìn)化效率，能更快更迅速的找到全局最優(yōu)解。通過對標(biāo)準(zhǔn)測試函數(shù)的仿真，驗(yàn)證了MA-BA算法具有高精度的全局尋優(yōu)能力以及收斂速度快的優(yōu)點(diǎn)。將多智能體蝙蝠算法應(yīng)用到無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位中，仿真結(jié)果表明MA-BA算法不僅對測距誤差的忍受能力較強(qiáng)，而且可以在較少的錨節(jié)點(diǎn)個數(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］.模式識別與人工智能，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］.中國電機(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］劉長平，葉春明.具有混沌搜索策略的蝙蝠優(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測距分析［J］.傳感技術(shù)學(xué)報(bào)，2007，20（11）:2526-2571.

尚俊娜（1979-），女，河南開封人，副教授，博士，主要研究方向?yàn)橥ㄐ判盘柼幚怼⒅悄芩惴ǎ?/p>

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

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

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］其性能有待提高。本文針對基本蝙蝠算法的缺點(diǎn)，提出了基于多智能體蝙蝠算法（Multi-Agent Bat Algorithm，MA-BA）。建議算法中通過采用基本蝙蝠算法的拓?fù)浣Y(jié)構(gòu)來構(gòu)建多智能體的體系結(jié)構(gòu)，將每一個蝙蝠個體作為一個智能體，通過與鄰域的智能體競爭、合作以及自我學(xué)習(xí)，從而避免算法陷入局部最優(yōu)，提高算法的收斂速度，個體的更新機(jī)制減少了算法不可行解的產(chǎn)生，提高了算法效率。通過對標(biāo)準(zhǔn)測試函數(shù)仿真，改進(jìn)的MA-BA算法在尋優(yōu)精度上相比于基本BA算法有較大提高，同時將其應(yīng)用在無線傳感器節(jié)點(diǎn)定位的應(yīng)用中，節(jié)點(diǎn)的平均定位誤差相對較低，獲得了比較理想的節(jié)點(diǎn)定位結(jié)果。