基于細菌覓食優化算法的WSNs節點部署策略*

朱瑞金， 王聯國

(1.甘肅農業大學 工學院，甘肅 蘭州 730070；2.甘肅農業大學 信息科學技術學院，甘肅 蘭州 730070)

0 引 言

利用無線傳感器網絡(WSNs)對草地進行監控是近些年農業生態領域對草地生態環境進行管理的一種手段，具有易部署、成本低、信息收集全面持續等特點。傳感器節點的布置策略是監控網絡的基礎，只有合理的節點部署，才能得出準確的原數據。但是，通過隨機拋撒等手段得出的數據具有很大的不確定性[1]，因此，很多學者利用智能優化算法對WSNs節點的部署策略進行了優化。例如:文獻[2]利用改進的蟻群算法對離散成網監測局域的覆蓋率進行優化，文獻[3]提出一種改進的微粒群算法，以覆蓋面積比為標準對監測區域的覆蓋率進行優化，都取得了一定的效果。對具有普遍性的監測區域，通常以提高覆蓋面積比例或覆蓋的網格比例(網格比例指將監測區域離散成網格形式)為目標進行部署優化，從而盡可能減少盲區和重復覆蓋面積[4,5]。

細菌覓食優化 (bacterial foraging optimization,BFO) 算法是由Passino K M在2002年基于大腸桿菌在在人體的覓食行為提出的一種全局啟發算法[6]。該算法求解的過程中能夠在區間內并行搜索并通過群體之間的信息互換實現群體智能性，在公交調度[7]、背包問題[8]、BP神經網絡[9]等問題上的應用都取得良好的效果。

本文提出一種基于BFO算法，對草地的WSNs部署策略進行了應用性研究，仿真結果驗證了該算法的可行性和有效性。

1 傳感器節點的優化模型

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

(1)

對于監測點k(i)被此傳感器u(j)監測到的概率為P(k(i),u(j))

(2)

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

(3)

從而對于整個監控區域的總覆蓋率P為

(4)

這樣得出的結果可以反映出監視草地區域具有普遍性的狀況下的近似覆蓋率。

2 BFO算法

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

1)趨向操作：大腸細菌在覓食過程中同時通過旋轉和游動來尋找附近食物較為豐富的區域，避開有毒區域。上述統稱趨向行為，對于細菌i在趨向運動中的數學模型表示為

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

(5)

其中,j為趨向行為次數，k為遷徙行為次數，C(i)為步長，φ(i)為細菌i的隨機方向的單位向量，且

(6)

2)復制操作：當整體細菌的趨向運動結束后，細菌進行優勝劣汰，健康值更好的細菌個數為Sr(Sr=S/2,其中,S為種群中細菌的個數)分裂為成2個細菌，健康值較差的 50 %細菌死亡，保持種群個數的不變，細菌i的健壯函數值為

(7)

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

3)在復制操作完成后，由于外部環境原因，細菌有一定的概率遷徙的其他隨機的空間，遷徙范圍設定為可行解的范圍，從而避免細菌過早收斂。

3 基于BFO算法的WSNs節點部署優化

3.1 編碼方案

菌落為監測區域的傳感器集合，每個菌落由z個細菌組成，每個細菌代表一只傳感器，細菌的搜索維度為2，分別為二維平面的x軸和y軸的值。菌落的適應度值代表監測區域內傳感器集合的有效覆蓋率。

菌落的細菌表示為P(z,b,i,j,k,l),其中，z為菌落里面細菌的編號，b為菌落里面單個細菌的維度，i為菌落的編號，j為趨向運動的次數，k為復制操作的次數，l為遷徙操作的次數。

3.2 BFO算法的三種操作的改動

1)趨向操作：趨向操作是以細菌為單位進行的，在細菌趨向操作開始時，引入碰壁策略，設定菌落內部細菌互相影響，當細菌i和細菌j距離接近一定范圍，細菌i就會針對細菌j反方向，sij表示菌落內細菌i相對細菌j的反向運動距離

(8)

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

隨后菌落內的細菌做各自的趨向運動，運動步長一致，運動的單位向量各自獨立隨機產生

(9)

2)復制操作：當所有菌落的細菌的趨向運動結束時候，細菌以菌落為單位進行復制操作，其中菌落健壯函數值為

(10)

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

3.3 目標函數

目標函數為總體覆蓋面積與整體面積的比例大小，覆蓋面積越大越優越，故細菌覓食算法的適應度函數應該為

(11)

3.4 BFO算法流程

BFO算法流程如圖1。

圖1 BFO算法流程

4 仿真實驗

本文在Matlab 7.6環境下進行仿真實驗。假定需要檢測的草地區域范圍是20 m×20 m的矩形區域，草地的監測區域為二維平面。監測區域離散成m×n像素點，傳感器的監測區域半徑r=2.5 m,通信距離R=5 m,在區域隨機分布25個傳感器節點。

4.1 趨化操作對算法性能的影響

設置BFO的菌落個數為30，菌落內細菌個數為25，細菌的搜索維度p為2，細菌的步長c為0.1，碰壁系數α為0.05，復制操作Nre為10，遷徙操作Ned為2,在趨化操作為1，5，10,25,50情況下獨立計算50次(BFO的迭代計算可以換算為Ned×Nre×Nc)得到的實驗結果如表1所示。

表1 趨化操作的實驗結果

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

4.2 復制操作對算法性能的影響

設置BFO的菌落個數為30，菌落內的細菌個數為25，搜索維度p為2，步長c為0.05，碰壁系數α為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的比例下分別迭代計算，迭代次數為500次(BFO的迭代計算可以換算為Ned×Nre×Nc，3個嵌套的循環,總的遷徙次數為Ned,總的復制次數是Ned×Nre)計算50次得到實驗結果如表2所示。

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

表2 復制操作的實驗結果

4.3 遷徙操作對算法性能的影響

設置BFO的菌落個數為30，菌落內細菌個數為25，搜索維度p為2，步長c為0.05，碰壁系數α為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的比例下分別迭代計算，迭代次數為500次，計算50次得到實驗結果如表3所示。

表3 遷徙操作的實驗結果

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

4.4 仿真結果

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

圖2 覆蓋面積的對比

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

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

表4 三種算法的優化結果

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

5 結 論

本文針對大規模草地區域監測中的傳感器節點優化部署問題，提出一種基于BFO算法的節點部署策略，對仿真實驗的數據和理論分析表明:這種策略是可行的。在實地草地監測中，等同于像素的監測點的密度并不是均勻分布的，在這種情況下求得WSNs的最優覆蓋率分布，是下一步研究工作的重點。

參考文獻:

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

[2] 黃 亮.基于改進蟻群算法的無線傳感器節點部署[J].計算機測量與控制,2010,18(9)：2210-2221.

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

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

[5] 龍 騰,孫 輝,趙 嘉.基于改進蛙跳算法的WSNs、移動節點的部署研究[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].交通運輸系統與信息,2012,12(2):155-161.

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

[9] 麥雄發,李 玲,胡寶清.優化BP神經網絡的快速細菌覓食算法[J].廣西科學院學報,2011,27(3):221-223.

[10] 袁 浩.基于改進蜂群算法無線傳感器感知節點部署優化[J].計算機應用研究,2010,27(7):2704-2708.

[11] 張云亞,紀志成.虛擬力導向多粒子群算法的WSNs部署策略[J].江南大學學報:自然科學版,2012,11(4):428-431.

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

[13] 梁艷春,吳春國,時小虎,著.群智能優化算法理論與應用[M].北京:科學出版社,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] 殷衛莉,陳 巍.遺傳算法在無線傳感器網絡覆蓋中的仿真研究[J].計算機仿真,2010,27(10):120-123.