朱瑞金， 王聯(lián)國(guó)

(1.甘肅農(nóng)業(yè)大學(xué) 工學(xué)院，甘肅 蘭州 730070；2.甘肅農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，甘肅 蘭州 730070)

0 引 言

利用無(wú)線傳感器網(wǎng)絡(luò)(WSNs)對(duì)草地進(jìn)行監(jiān)控是近些年農(nóng)業(yè)生態(tài)領(lǐng)域?qū)Σ莸厣鷳B(tài)環(huán)境進(jìn)行管理的一種手段，具有易部署、成本低、信息收集全面持續(xù)等特點(diǎn)。傳感器節(jié)點(diǎn)的布置策略是監(jiān)控網(wǎng)絡(luò)的基礎(chǔ)，只有合理的節(jié)點(diǎn)部署，才能得出準(zhǔn)確的原數(shù)據(jù)。但是，通過(guò)隨機(jī)拋撒等手段得出的數(shù)據(jù)具有很大的不確定性[1]，因此，很多學(xué)者利用智能優(yōu)化算法對(duì)WSNs節(jié)點(diǎn)的部署策略進(jìn)行了優(yōu)化。例如:文獻(xiàn)[2]利用改進(jìn)的蟻群算法對(duì)離散成網(wǎng)監(jiān)測(cè)局域的覆蓋率進(jìn)行優(yōu)化，文獻(xiàn)[3]提出一種改進(jìn)的微粒群算法，以覆蓋面積比為標(biāo)準(zhǔn)對(duì)監(jiān)測(cè)區(qū)域的覆蓋率進(jìn)行優(yōu)化，都取得了一定的效果。對(duì)具有普遍性的監(jiān)測(cè)區(qū)域，通常以提高覆蓋面積比例或覆蓋的網(wǎng)格比例(網(wǎng)格比例指將監(jiān)測(cè)區(qū)域離散成網(wǎng)格形式)為目標(biāo)進(jìn)行部署優(yōu)化，從而盡可能減少盲區(qū)和重復(fù)覆蓋面積[4,5]。

細(xì)菌覓食優(yōu)化 (bacterial foraging optimization,BFO) 算法是由Passino K M在2002年基于大腸桿菌在在人體的覓食行為提出的一種全局啟發(fā)算法[6]。該算法求解的過(guò)程中能夠在區(qū)間內(nèi)并行搜索并通過(guò)群體之間的信息互換實(shí)現(xiàn)群體智能性，在公交調(diào)度[7]、背包問(wèn)題[8]、BP神經(jīng)網(wǎng)絡(luò)[9]等問(wèn)題上的應(yīng)用都取得良好的效果。

本文提出一種基于BFO算法，對(duì)草地的WSNs部署策略進(jìn)行了應(yīng)用性研究，仿真結(jié)果驗(yàn)證了該算法的可行性和有效性。

1 傳感器節(jié)點(diǎn)的優(yōu)化模型

本文傳感器采用0/1的監(jiān)測(cè)模型，將傳感器的監(jiān)測(cè)區(qū)域離散為[10]：監(jiān)測(cè)區(qū)和盲區(qū)。例：假定傳感器節(jié)點(diǎn)u(j)的二維坐標(biāo)是(xj,yj),監(jiān)測(cè)區(qū)半徑為r，通信半徑為R，通常假定R≥2r。監(jiān)測(cè)目標(biāo)點(diǎn)k(i)的二維坐標(biāo)為(xi,yi)，那么兩點(diǎn)之間的距離

(1)

對(duì)于監(jiān)測(cè)點(diǎn)k(i)被此傳感器u(j)監(jiān)測(cè)到的概率為P(k(i),u(j))

(2)

假定監(jiān)控草地區(qū)域是面積為m×n的區(qū)域A[11]，則區(qū)域A離散成m×n像素點(diǎn)，傳感器只數(shù)為v，傳感器的集合集為U，則對(duì)于像素點(diǎn)k(i)被傳感器集合集U監(jiān)控的概率為

(3)

從而對(duì)于整個(gè)監(jiān)控區(qū)域的總覆蓋率P為

(4)

這樣得出的結(jié)果可以反映出監(jiān)視草地區(qū)域具有普遍性的狀況下的近似覆蓋率。

2 BFO算法

BFO算法有[12～14]趨向行為、復(fù)制行為、遷徙行為等三種主要操作。

1)趨向操作：大腸細(xì)菌在覓食過(guò)程中同時(shí)通過(guò)旋轉(zhuǎn)和游動(dòng)來(lái)尋找附近食物較為豐富的區(qū)域，避開(kāi)有毒區(qū)域。上述統(tǒng)稱趨向行為，對(duì)于細(xì)菌i在趨向運(yùn)動(dòng)中的數(shù)學(xué)模型表示為

θi(j+1,k)=θi(j,k)+C(i)φ(i).

(5)

其中,j為趨向行為次數(shù)，k為遷徙行為次數(shù)，C(i)為步長(zhǎng)，φ(i)為細(xì)菌i的隨機(jī)方向的單位向量，且

(6)

2)復(fù)制操作：當(dāng)整體細(xì)菌的趨向運(yùn)動(dòng)結(jié)束后，細(xì)菌進(jìn)行優(yōu)勝劣汰，健康值更好的細(xì)菌個(gè)數(shù)為Sr(Sr=S/2,其中,S為種群中細(xì)菌的個(gè)數(shù))分裂為成2個(gè)細(xì)菌，健康值較差的 50 %細(xì)菌死亡，保持種群個(gè)數(shù)的不變，細(xì)菌i的健壯函數(shù)值為

(7)

式中Nc為最大趨向次數(shù)，k為第k復(fù)制次數(shù)，l為第l次遷徙，函數(shù)值越大細(xì)菌的健康程度越差。

3)在復(fù)制操作完成后，由于外部環(huán)境原因，細(xì)菌有一定的概率遷徙的其他隨機(jī)的空間，遷徙范圍設(shè)定為可行解的范圍，從而避免細(xì)菌過(guò)早收斂。

3 基于BFO算法的WSNs節(jié)點(diǎn)部署優(yōu)化

3.1 編碼方案

菌落為監(jiān)測(cè)區(qū)域的傳感器集合，每個(gè)菌落由z個(gè)細(xì)菌組成，每個(gè)細(xì)菌代表一只傳感器，細(xì)菌的搜索維度為2，分別為二維平面的x軸和y軸的值。菌落的適應(yīng)度值代表監(jiān)測(cè)區(qū)域內(nèi)傳感器集合的有效覆蓋率。

菌落的細(xì)菌表示為P(z,b,i,j,k,l),其中，z為菌落里面細(xì)菌的編號(hào)，b為菌落里面單個(gè)細(xì)菌的維度，i為菌落的編號(hào)，j為趨向運(yùn)動(dòng)的次數(shù)，k為復(fù)制操作的次數(shù)，l為遷徙操作的次數(shù)。

3.2 BFO算法的三種操作的改動(dòng)

1)趨向操作：趨向操作是以細(xì)菌為單位進(jìn)行的，在細(xì)菌趨向操作開(kāi)始時(shí)，引入碰壁策略，設(shè)定菌落內(nèi)部細(xì)菌互相影響，當(dāng)細(xì)菌i和細(xì)菌j距離接近一定范圍，細(xì)菌i就會(huì)針對(duì)細(xì)菌j反方向，sij表示菌落內(nèi)細(xì)菌i相對(duì)細(xì)菌j的反向運(yùn)動(dòng)距離

(8)

式中α為細(xì)菌對(duì)食物的敏感系數(shù)，(此問(wèn)題中，α為單只傳感器覆蓋面積和整體覆蓋面積決定的)。

隨后菌落內(nèi)的細(xì)菌做各自的趨向運(yùn)動(dòng)，運(yùn)動(dòng)步長(zhǎng)一致，運(yùn)動(dòng)的單位向量各自獨(dú)立隨機(jī)產(chǎn)生

(9)

2)復(fù)制操作：當(dāng)所有菌落的細(xì)菌的趨向運(yùn)動(dòng)結(jié)束時(shí)候，細(xì)菌以菌落為單位進(jìn)行復(fù)制操作，其中菌落健壯函數(shù)值為

(10)

3)遷徙操作：遷徙操作同樣以菌落為單位進(jìn)行。

3.3 目標(biāo)函數(shù)

目標(biāo)函數(shù)為總體覆蓋面積與整體面積的比例大小，覆蓋面積越大越優(yōu)越，故細(xì)菌覓食算法的適應(yīng)度函數(shù)應(yīng)該為

(11)

3.4 BFO算法流程

BFO算法流程如圖1。

圖1 BFO算法流程

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

本文在Matlab 7.6環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。假定需要檢測(cè)的草地區(qū)域范圍是20 m×20 m的矩形區(qū)域，草地的監(jiān)測(cè)區(qū)域?yàn)槎S平面。監(jiān)測(cè)區(qū)域離散成m×n像素點(diǎn)，傳感器的監(jiān)測(cè)區(qū)域半徑r=2.5 m,通信距離R=5 m,在區(qū)域隨機(jī)分布25個(gè)傳感器節(jié)點(diǎn)。

4.1 趨化操作對(duì)算法性能的影響

設(shè)置BFO的菌落個(gè)數(shù)為30，菌落內(nèi)細(xì)菌個(gè)數(shù)為25，細(xì)菌的搜索維度p為2，細(xì)菌的步長(zhǎng)c為0.1，碰壁系數(shù)α為0.05，復(fù)制操作Nre為10，遷徙操作Ned為2,在趨化操作為1，5，10,25,50情況下獨(dú)立計(jì)算50次(BFO的迭代計(jì)算可以換算為Ned×Nre×Nc)得到的實(shí)驗(yàn)結(jié)果如表1所示。

表1 趨化操作的實(shí)驗(yàn)結(jié)果

由表1可以得出:適當(dāng)增加趨化操作次數(shù)可以提高WSNs覆蓋率的平均值，但是當(dāng)趨化次數(shù)增大到一定的數(shù)值時(shí)，WSNs的覆蓋率最高值趨于收斂，同時(shí)WSNs覆蓋率的平均值有所下降。

4.2 復(fù)制操作對(duì)算法性能的影響

設(shè)置BFO的菌落個(gè)數(shù)為30，菌落內(nèi)的細(xì)菌個(gè)數(shù)為25，搜索維度p為2，步長(zhǎng)c為0.05，碰壁系數(shù)α為0.05，在Ned∶Nre∶Nc=2∶250∶1，Ned∶Nre∶Nc=2∶50∶5，Ned∶Nre∶Nc=2∶25∶10，Ned∶Nre∶Nc=2∶10∶25，Ned∶Nre∶Nc=2∶5∶50的比例下分別迭代計(jì)算，迭代次數(shù)為500次(BFO的迭代計(jì)算可以換算為Ned×Nre×Nc，3個(gè)嵌套的循環(huán),總的遷徙次數(shù)為Ned,總的復(fù)制次數(shù)是Ned×Nre)計(jì)算50次得到實(shí)驗(yàn)結(jié)果如表2所示。

由表2可以得出:在迭代次數(shù)確定的情況下，適當(dāng)增加復(fù)制次數(shù)，WSNs覆蓋率的平均值、最高值都得到了提高，同時(shí)算法的收斂速度也得到提升。但是當(dāng)復(fù)制次數(shù)過(guò)高的時(shí)，種群失去多樣性，收斂速反而變慢。

表2 復(fù)制操作的實(shí)驗(yàn)結(jié)果

4.3 遷徙操作對(duì)算法性能的影響

設(shè)置BFO的菌落個(gè)數(shù)為30，菌落內(nèi)細(xì)菌個(gè)數(shù)為25，搜索維度p為2，步長(zhǎng)c為0.05，碰壁系數(shù)α為0.05，在Ned∶Nre∶Nc=2∶50∶5，Ned∶Nre∶Nc=4∶25∶5，Ned∶Nre∶Nc=10∶10∶5，Ned∶Nre∶Nc=20∶5∶5，Ned∶Nre∶Nc=25∶4∶5的比例下分別迭代計(jì)算，迭代次數(shù)為500次，計(jì)算50次得到實(shí)驗(yàn)結(jié)果如表3所示。

表3 遷徙操作的實(shí)驗(yàn)結(jié)果

由表3可以得出:在迭代次數(shù)相同的情況下，隨著遷徙次數(shù)的提高，WSNs的平均覆蓋率小幅度的增加,同時(shí)算法的收斂速度變慢。

4.4 仿真結(jié)果

為了驗(yàn)證BFO算法的有效性，將BFO部署結(jié)果與初始部署結(jié)果相比較。設(shè)置BFO算法的菌落個(gè)數(shù)為30，菌落內(nèi)細(xì)菌個(gè)數(shù)為25，步長(zhǎng)c為0.5，Nre∶Nc∶Ned=5∶50∶2,碰壁系數(shù)α為0.05，遷徙概率為0.25，單方向翻滾最大次數(shù)為10，計(jì)算次數(shù)約500次，運(yùn)行50次，選取接近平均值的覆蓋率。與初始的無(wú)線傳感器覆蓋率中最優(yōu)值相比較，圖2(a)為基于初始WSNs覆蓋率最優(yōu)值的節(jié)點(diǎn)部署情況，圖2(b)為用BFO優(yōu)化得到的WSNs節(jié)點(diǎn)部署情況，點(diǎn)代表傳感器位置，圓形代表傳感器覆蓋區(qū)域。

圖2 覆蓋面積的對(duì)比

初始的WSNs節(jié)點(diǎn)最優(yōu)覆蓋率為71.75 %，通過(guò)BFO優(yōu)化得到的傳感器的收斂覆蓋率為92.45 %。相比初始節(jié)點(diǎn)部署，通過(guò)BFO得到節(jié)點(diǎn)部署的覆蓋率提高20.70 %，達(dá)到了優(yōu)化的效果。從圖2可以得知，比較圖2(a)，(b)的節(jié)點(diǎn)分布的更均勻，重復(fù)覆蓋的區(qū)域更少。其中圖2(a)中出現(xiàn)了孤立的傳感器節(jié)點(diǎn)或節(jié)點(diǎn)群(相互距離大于R)。通過(guò)上述分析得知，與初始的WSNs部署相比較，由BFO得到的WSNs部署具有較高覆蓋率和較好的部署合理性，由此對(duì)比表明，基于BFO算法的WSNs部署策略是可行的。

為了進(jìn)一步的驗(yàn)證BFO算法在WSNs節(jié)點(diǎn)部署的優(yōu)化問(wèn)題上的可行性，將遺傳算法，微粒群算法和本文的算法(菌落個(gè)數(shù)為30，菌落內(nèi)細(xì)菌個(gè)數(shù)為25，步長(zhǎng)c為0.1，Nc數(shù)值為5，Nre數(shù)值為50,Ned數(shù)值為2，Nc×Ned×Nre的計(jì)算值為500，碰壁系數(shù)α為0.05，遷徙概率Ped為0.25，單個(gè)方向細(xì)菌翻滾的最大次數(shù)為10)進(jìn)行對(duì)比，遺傳算法采用文獻(xiàn)[15]方法(種群規(guī)模的初始值為50,交叉概率Pc的初始值為0.05,變異概率Pm的初始值為0.01)，微粒群算法采用文獻(xiàn)[3]方法(微粒個(gè)數(shù)為30，微粒的飛行速度為-3～3 m/s之間，參數(shù)C1=0.9,C2=0.9 )。三種方法迭代次數(shù)均為500，計(jì)算50次得到實(shí)驗(yàn)結(jié)果如表4所示。

表4 三種算法的優(yōu)化結(jié)果

由表4可以得出,比較遺傳算法和微粒群算法，BFO算法得到的傳感器節(jié)點(diǎn)平均覆蓋率分別提高了13.85 %和5.65 %，最優(yōu)覆蓋率分別提高了14.80 %和6.85 %，收斂速度也比遺傳算法和微粒群算法快。可以看出:在解決WSNs覆蓋率問(wèn)題上，比之兩種算法，BFO算法具有明顯優(yōu)勢(shì)。

5 結(jié) 論

本文針對(duì)大規(guī)模草地區(qū)域監(jiān)測(cè)中的傳感器節(jié)點(diǎn)優(yōu)化部署問(wèn)題，提出一種基于BFO算法的節(jié)點(diǎn)部署策略，對(duì)仿真實(shí)驗(yàn)的數(shù)據(jù)和理論分析表明:這種策略是可行的。在實(shí)地草地監(jiān)測(cè)中，等同于像素的監(jiān)測(cè)點(diǎn)的密度并不是均勻分布的，在這種情況下求得WSNs的最優(yōu)覆蓋率分布，是下一步研究工作的重點(diǎn)。

參考文獻(xiàn):

[1] Yick J,Mukherjee B,Ghosal D.Wirless sensor networks sur-vey[J].Computer Network,2008,52(12):2292-2330.

[2] 黃 亮.基于改進(jìn)蟻群算法的無(wú)線傳感器節(jié)點(diǎn)部署[J].計(jì)算機(jī)測(cè)量與控制,2010,18(9)：2210-2221.

[3] 鄭 磊,朱正禮,候迎坤.基于改進(jìn)的微粒群算法的WSNs節(jié)點(diǎn)部署[J].廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2011,29(4):56-61.

[4] 曾映蘭,陳 靜,鄭金華.基于遺傳算法的WSNs覆蓋優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(11):89-91.

[5] 龍 騰,孫 輝,趙 嘉.基于改進(jìn)蛙跳算法的WSNs、移動(dòng)節(jié)點(diǎn)的部署研究[J].計(jì)算機(jī)工程,2012,38(5):96-116.

[6] Kevin M P.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine,2002,22(3):52-67.

[7] 劉 芹.差分進(jìn)化細(xì)菌覓食算法求解公交車(chē)調(diào)度問(wèn)題[J].交通運(yùn)輸系統(tǒng)與信息,2012,12(2):155-161.

[8] 戴秋萍,馬 良,都 瑩.求解0-1背包問(wèn)題的細(xì)菌覓食算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(3):178-183.

[9] 麥雄發(fā),李 玲,胡寶清.優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的快速細(xì)菌覓食算法[J].廣西科學(xué)院學(xué)報(bào),2011,27(3):221-223.

[10] 袁 浩.基于改進(jìn)蜂群算法無(wú)線傳感器感知節(jié)點(diǎn)部署優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究,2010,27(7):2704-2708.

[11] 張?jiān)苼?紀(jì)志成.虛擬力導(dǎo)向多粒子群算法的WSNs部署策略[J].江南大學(xué)學(xué)報(bào):自然科學(xué)版,2012,11(4):428-431.

[12] 周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(20):16-21.

[13] 梁艷春,吳春國(guó),時(shí)小虎,著.群智能優(yōu)化算法理論與應(yīng)用[M].北京:科學(xué)出版社,2009．

[14] Das S,Dasgupta S,Biswas A,et al.Onstability of the chemotactic dynamicsin bacterial foraging optimization algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics—Part A: Systems and Humans,2009,29(3):670-679.

[15] 殷衛(wèi)莉,陳 巍.遺傳算法在無(wú)線傳感器網(wǎng)絡(luò)覆蓋中的仿真研究[J].計(jì)算機(jī)仿真,2010,27(10):120-123.