嵌套細菌覓食優(yōu)化算法在無線傳感器網(wǎng)絡中的研究*

鄒汪平

(池州職業(yè)技術學院 安徽 池州 247100)

?

嵌套細菌覓食優(yōu)化算法在無線傳感器網(wǎng)絡中的研究*

鄒汪平

(池州職業(yè)技術學院 安徽 池州 247100)

為優(yōu)化無線傳感器網(wǎng)絡節(jié)點配置，探索了基于細菌覓食優(yōu)化算法的傳感器節(jié)點配置方法.以二維目標監(jiān)測區(qū)域內(nèi)既定數(shù)目的傳感器節(jié)點總覆蓋率作為評價函數(shù)，以三種操作相嵌套的細菌覓食優(yōu)化算法對實際問題進行優(yōu)化.通過計算機仿真實驗評價了該方法的可行性，同其他方法進行了比較，分析了原始參數(shù)對優(yōu)化結(jié)果的影響.結(jié)果顯示：嵌套細菌覓食優(yōu)化算法有效提高了無線傳感器網(wǎng)絡的總覆蓋率.

細菌覓食優(yōu)化算法；傳感器網(wǎng)絡；覆蓋率

引言

得益于科技的迅猛發(fā)展，生產(chǎn)生活中對信息化要求的不斷提高，無線傳感器網(wǎng)絡得到了越來越多的應用.無線傳感器網(wǎng)絡依托智能傳感器信息控制模塊，通過現(xiàn)場總線將傳感器節(jié)點并入控制器構成局域網(wǎng)絡，通過無線網(wǎng)絡實現(xiàn)復雜的總體分析和遠程操控[1].覆蓋率是評價無線傳感器網(wǎng)絡的一個重要指標，理想中的無線傳感器節(jié)點部署應盡可能實現(xiàn)對整個監(jiān)測區(qū)域物理空間的覆蓋，同時保證節(jié)點不過分冗余.實際應用中，由于監(jiān)測面積大，傳感器節(jié)點分布具有隨機性，有效覆蓋率不能滿足高要求.為了優(yōu)化無線傳感器網(wǎng)的實際覆蓋率，傳感器節(jié)點部署策略得到了廣泛研究.燕山大學鄧成玉等人提出了一種基于跳段校正的定位算法，在不同網(wǎng)絡規(guī)模、不同網(wǎng)絡連通度條件下均可以顯著提高傳感器網(wǎng)絡節(jié)點的定位精度.黃亮等人提出了改進的蟻群算法對離散網(wǎng)監(jiān)測局域的覆蓋率進行優(yōu)化[2].鄭磊等人研究了微粒群改進算法，對監(jiān)測區(qū)域的覆蓋率進行優(yōu)化并取得了一定的效果[3].

細菌覓食優(yōu)化算法(BFOA)是Passino等人模仿大腸桿菌在動物腸道內(nèi)攝取食物的行為而提出的一種計算方法，該計算方法的核心思想是模仿人類腸道中的大腸桿菌在覓食過程中表現(xiàn)出的智能特征，具有群體算法并行搜索、易跳出局部極小值等優(yōu)點，是計算研究領域的新熱點[4,5].

為提高無線傳感器網(wǎng)絡覆蓋率，研究了基于細菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡部署策略，并以仿真實驗驗證了算法的可行性，分析了算法的初始參數(shù)對優(yōu)化結(jié)果的影響.

1　細菌覓食優(yōu)化算法與無線傳感器網(wǎng)絡的數(shù)學模型

1.1無線傳感器網(wǎng)絡節(jié)點的數(shù)學模型

為便于分析，選取二維平面作為目標監(jiān)測區(qū)域，目標監(jiān)測區(qū)域內(nèi)暴露于網(wǎng)絡節(jié)點監(jiān)測范圍內(nèi)的區(qū)域為監(jiān)測區(qū)，否則為盲區(qū).以g(j)標識位于目標監(jiān)測區(qū)域內(nèi)的一個無線傳感器節(jié)點，該節(jié)點的具體位置由坐標(xj,yj)確定，監(jiān)測半徑為r，節(jié)點間互聯(lián)半徑為R，實際應用中R≥2r.目標監(jiān)測區(qū)域內(nèi)某點q(i)的二維坐標為(xi,yi).二維平面內(nèi)傳感器節(jié)點g(j)到某點q(i)的距離為

(1)

目標檢測區(qū)域內(nèi)某點q(i)被某傳感器節(jié)點g(j)監(jiān)測到的概率為

(2)

進一步將目標監(jiān)測區(qū)域設定為長寬分別為m和n的矩形區(qū)域，將目標監(jiān)測區(qū)域平均分割成m×n個面積為1 m2的正方形網(wǎng)格，則整個目標監(jiān)測區(qū)域?qū)⒊霈F(xiàn)(m+1)×(n+1)個網(wǎng)格節(jié)點.設目標監(jiān)測區(qū)域內(nèi)傳感器為a，在a個傳感器共同監(jiān)測下，某點q(i)暴露于監(jiān)測區(qū)的概率為

(3)

a個傳感器對整個目標監(jiān)測區(qū)域的總覆蓋率為

(4)

f客觀反映了統(tǒng)計學角度下無線傳感器網(wǎng)絡對目標監(jiān)測區(qū)域的覆蓋率，因此選用f作為評價函數(shù)，對算法進行量化評價，f值越大部署策略越好.

1.2細菌覓食優(yōu)化算法的數(shù)學模型

細菌覓食優(yōu)化算法的實現(xiàn)過程主要依據(jù)三種機制：趨化、復制和驅(qū)散[6,7].

1)趨化：大腸桿菌的運動以翻轉(zhuǎn)和游動為主.大腸桿菌時刻處于翻轉(zhuǎn)運動狀態(tài)，即等概率向不確定的方向移動一定距離.當翻轉(zhuǎn)后所處位置的生存環(huán)境不變或者更差，細菌將繼續(xù)進行翻轉(zhuǎn).當所處位置的生存環(huán)境得到改良，細菌不會立即終止運動.細菌終止運動的條件是連續(xù)運動后生存環(huán)境不發(fā)生改變，或者游動達到了既定的最大步長.細菌的趨化可表示為

(5)

式(5)中，θi(j+1,k,l)為第i個大腸桿菌的位置函數(shù)，θi(j+1,k,l)在是該細菌前一時刻的位置函數(shù).細菌移動次數(shù)用k表示，復制次數(shù)用l表示，趨化次數(shù)用j表示；c(i)為細菌i的趨化步長；Δ是標識細菌下一步運動方向的單位向量.

2)復制：細菌總數(shù)保持不變，在任何一步趨化發(fā)生后，累計適應值較小的一半細菌將死亡，累計適應值較大的一半細菌將存活，并進行分裂，使細菌總數(shù)不發(fā)生變化.第i個大腸桿菌適應值累加和的計算公式為

(6)

式(6)中，J(i,j,k,l)為細菌i在第l次驅(qū)散、第k次復制、第j次趨化中的適應值.

3)若干次趨化復制后，細菌個體將隨機分布在目標監(jiān)測區(qū)域內(nèi)，并呈現(xiàn)出統(tǒng)計學規(guī)律.為避免細菌過早收斂，遷徙范圍設定為可行解的范圍[8].

1.3基于細菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡部署策略

為將細菌覓食優(yōu)化算法應用于無線傳感器網(wǎng)絡，研究過程均基于以下假設：

1)目標監(jiān)測區(qū)域的網(wǎng)格劃分不變，網(wǎng)格節(jié)點總覆蓋率f為唯一評價函數(shù)；

2)每個細菌代表一個傳感器節(jié)點，細菌在二維目標監(jiān)測區(qū)域移動，細菌搜索半徑為傳感器節(jié)點監(jiān)測半徑；

3)細菌覓食算法參數(shù)及傳感器節(jié)點參數(shù)在一次優(yōu)化過程中不發(fā)生改變，傳感器節(jié)點具有平等地位，傳感器節(jié)點間雙向通信，細菌適應值為攜帶傳感器參數(shù)的細菌在當前位置所產(chǎn)生的覆蓋率；

4)嚴格依照適應值的排序確定細菌的存亡，每個存活的細菌必須且只能進行一分為二的繁殖；

5)經(jīng)過多次迭代后，新的細菌將按統(tǒng)計學規(guī)律分布.

為盡可能避免傳感器節(jié)點監(jiān)測范圍出現(xiàn)重合，細菌趨向操作過程中引入回避機制，設細菌兩兩之間有排斥力和引力，距離超過一定值的兩個細菌將互相吸引，距離小于一定值的兩個細菌將彼此遠離，細菌間的排斥和吸引作用可表示為：

2016年以來，谷城縣資金使用管理逐步規(guī)范，建立健全了覆蓋資金分配、撥付、使用、監(jiān)管和績效評價全過程的扶貧統(tǒng)籌資金管理制度體系。

sij=e-λDij

(7)

式(7)中sij表示兩細菌反向移動距離，λ為敏感系數(shù)，即細菌對彼此之間距離的敏感程度，Dij為細菌i和細菌j之間的距離，λ和Dij共同決定了細菌反向移動距離.

當所有菌落的細菌的趨向運動結(jié)束時，細菌以菌落為單位進行復制操作，單個菌落適應值為

(8)

式(8)中，w為菌落內(nèi)的細菌總數(shù).

2　基于細菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡優(yōu)化部署實驗

2.1細菌覓食優(yōu)化算法的實驗結(jié)果及分析

實驗選用Matlab軟件，實驗選取面積為900 m2的正方形平面作為目標監(jiān)測區(qū)域.目標監(jiān)測區(qū)域被劃分為900個面積為1 m2的正方形網(wǎng)格，并形成961個網(wǎng)格節(jié)點.設傳感器的監(jiān)測區(qū)域半徑r=3 m，通信距離R=6 m，在目標監(jiān)測區(qū)域內(nèi)隨機分布40個傳感器節(jié)點.

設置細菌覓食優(yōu)化算法的細菌步長c為0.5 m，細菌“復制”操作次數(shù)Nre為5，遷徙操作概率為0.25，一次趨化操作中每只細菌移動距離上限Ned為2，一次迭代中，趨化操作次數(shù)Nc為50，敏感系數(shù)λ為0.05，單方向翻滾最大次數(shù)為15，覆蓋率收斂時終止運算.實驗重復操作10 次，以結(jié)果的平均值作為總覆蓋率.選取部分實驗結(jié)果如表1所示.

表1　基于細菌覓食優(yōu)化算法的傳感器節(jié)點部署實驗結(jié)果

表1中，Dd表示每次操作的迭代次數(shù)，Cz表示實驗組別.實驗結(jié)果顯示：設置合理的初始值，運算結(jié)果收斂，細菌覓食優(yōu)化算法可以用于無線傳感器網(wǎng)絡的節(jié)點部署設計；所選取的五組實驗結(jié)果中，當?shù)螖?shù)為500時，總覆蓋率值趨于穩(wěn)定，算法有較好的收斂性；每組實驗的細菌初始位置不同，優(yōu)化結(jié)果會有微小差異，五組實驗結(jié)果中，覆蓋率最大值為0.941 2，覆蓋率最小值為0.939 0，兩者相差約0.13%，可以忽略不計.

無線傳感器節(jié)點在若干次隨機分配中所產(chǎn)生的最大覆蓋率情形，如圖1所示；基于細菌覓食優(yōu)化算法的覆蓋率情形，如圖2所示.

圖1　無線傳感器網(wǎng)絡初始覆蓋示意圖

圖2　基于細菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡覆蓋示意圖

圖中離散的點代表傳感器位置.對比圖1和圖2，圖2的節(jié)點分布更加分散，傳感器監(jiān)測重合的面積較少.其中圖1中節(jié)點分布更加密集，傳感器監(jiān)測重合的面積較多.初始的傳感器節(jié)點最優(yōu)覆蓋率約為0.7，通過細菌覓食優(yōu)化算法得到的傳感器覆蓋率約為0.94.比較兩種傳感器節(jié)點部署方式，細菌覓食優(yōu)化算法使覆蓋率提高了約34%，有效實現(xiàn)了優(yōu)化部署，基于細菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡部署策略是可行的.

2.3細菌覓食優(yōu)化算法與兩種常見算法的比較

為驗證細菌覓食優(yōu)化算法在無線傳感器網(wǎng)絡節(jié)點部署優(yōu)化上的優(yōu)勢，設計了細菌覓食優(yōu)化算法和遺傳算法以及微粒群算法的對比實驗.驗證實驗中三種算法的初始參數(shù)如下：

1)細菌覓食優(yōu)化算法.細菌步長c為0.5 m，復制操作Nre為5，遷徙操作概率為0.25，步長Ned為2，Nc為50，敏感系數(shù)λ為0.05，單方向翻滾最大次數(shù)為15，覆蓋率收斂時終止運算.

2)遺傳算法.傳感器的初始值為40，為保證遺傳算法的高效性，Pc值和Pm值分別設為0.5和0.01，覆蓋率收斂時終止運算.

3)微粒群算法.微粒個數(shù)為40，微粒的飛行速度為-3～3 m/s，參數(shù)C1= 0.9，C2=0.9，覆蓋率收斂時終止運算.

每種算法迭代次數(shù)均為600，計算10次，對10次計算結(jié)果的覆蓋率平均值進行比較.實驗結(jié)果見表2.

表2　三種優(yōu)化方法的對比實驗結(jié)果

實驗結(jié)果顯示：初始狀態(tài)相同，經(jīng)過600次迭代運算，細菌覓食優(yōu)化算法下的總覆蓋率收斂于0.940 1，遺傳算法下的總覆蓋率收斂于0.861 2，微粒群算法下的總覆蓋率收斂于0.821 1.通過細菌覓食優(yōu)化算法得到的覆蓋率分別比其他兩種算法提高了9%和14%.在無線傳感器網(wǎng)絡節(jié)點優(yōu)化部署問題上，細菌覓食優(yōu)化算法更有優(yōu)勢.

2.4細菌覓食優(yōu)化算法的初始參數(shù)對優(yōu)化結(jié)果的影響

細菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡部署策略是基于數(shù)學模型實現(xiàn)的，通過對數(shù)學模型進行分析，算法實現(xiàn)過程中的參數(shù)設置會對優(yōu)化結(jié)果有以下幾點影響：

1)趨化次數(shù)的改變可以影響平均覆蓋率和最高覆蓋率.趨化次數(shù)越少，覆蓋率平均值越高.趨化次數(shù)過多，將使運算速度減慢，同時會導致覆蓋率平均值降低.

2)適當?shù)牡螖?shù)可以提高運算速度且不影響覆蓋率值.迭代次數(shù)超過一定值，平均覆蓋率幾乎不變，但運算速度將大幅下降.

3)對目標檢測區(qū)域進行網(wǎng)格劃分時，采用了1m2作為最小網(wǎng)格，當縮小網(wǎng)格，即增加網(wǎng)格節(jié)點數(shù)量時，優(yōu)化結(jié)果將進一步提高，但計算速度將減慢.優(yōu)化過程中應針對不同參數(shù)傳感器適當進行網(wǎng)格劃分.

3　結(jié)論

細菌覓食優(yōu)化算法可以有效應用于無線傳感器網(wǎng)絡節(jié)點部署，相比于傳統(tǒng)的傳感器網(wǎng)絡節(jié)點部署策略，細菌覓食優(yōu)化算法有更好的優(yōu)化效果.適當選取目標檢測區(qū)域的網(wǎng)格劃分，可以有效改善細菌覓食優(yōu)化算法的收斂速度.

[1]王晟. 無線傳感網(wǎng)絡節(jié)點定位與覆蓋控制理論及技術研究[D]. 武漢：武漢理工大學， 2006.

[2]龐娜,程德福．基于Zig Bee無線傳感器網(wǎng)絡的溫室監(jiān)測系統(tǒng)設計[J]．吉林大學學報信息科學版，2010(1) : 55-60．

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

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

[5]黃守志,趙學增等.基于網(wǎng)格劃分的無線傳感器網(wǎng)絡節(jié)點冗余分析[J]. 東北石油大學學報,2013,37(3):113-122.

[6]Mishra S.A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation[J].I-EEE Trans On Evolutionary Computation,2005,9(1):61-73.

[7]劉麗萍,王智,孫優(yōu)賢.無線傳感器網(wǎng)絡部署及其覆蓋問題研究[J].電子與信息學,2006,28(9):1752-1757.

[8]戴秋萍,馬良,郗瑩.連續(xù)優(yōu)化問題的細菌覓食改進算法[J]. 上海理工大學學報, 2013,35(2),103-107.

Research on Nested Bacterial Foraging Optimization Algorithm in Wireless Sensor Networks

ZOU Wang-ping

(Chizhou Vocational Technical College, Chizhou Anhui 247100, China)

In order to optimize the configuration of wireless sensor networks, the paper explores a sensor node configuration method based on bacterial foraging optimization algorithm. Taking the total coverage of determined number of sensor node rate in two-dimensional target monitoring area as evaluation function, actual problems are optimized by nested bacterial foraging optimization algorithm. The feasibility of this method was compared with others in experimental evaluation by computer simulation and the influence of the original parameters on the optimization results was researched. The results show that the nested bacterial foraging optimization algorithm can effectively improve the overall coverage of wireless sensor networks.

bacterial foraging optimization algorithm; wireless sensor networks; coverage rate

1673-2103(2016)02-0018-05

2016-02-24

安徽省2016年高校優(yōu)秀青年人才支持計劃重點項目(gxyqZD2016531)；安徽省2015年度省級質(zhì)量工程項目(2015gxk113)；安徽省2014年度省級質(zhì)量工程項目(2014jyxm524)

鄒汪平(1982-)，男，安徽池州人，副教授，碩士，研究方向：智能算法應用.

TP18

A