鄒汪平

(池州職業(yè)技術(shù)學(xué)院 安徽 池州 247100)

?

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

鄒汪平

(池州職業(yè)技術(shù)學(xué)院 安徽 池州 247100)

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

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

引言

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

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

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

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

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

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

(1)

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

(2)

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

(3)

a個(gè)傳感器對(duì)整個(gè)目標(biāo)監(jiān)測(cè)區(qū)域的總覆蓋率為

(4)

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

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

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

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

(5)

式(5)中，θi(j+1,k,l)為第i個(gè)大腸桿菌的位置函數(shù)，θi(j+1,k,l)在是該細(xì)菌前一時(shí)刻的位置函數(shù).細(xì)菌移動(dòng)次數(shù)用k表示，復(fù)制次數(shù)用l表示，趨化次數(shù)用j表示；c(i)為細(xì)菌i的趨化步長(zhǎng)；Δ是標(biāo)識(shí)細(xì)菌下一步運(yùn)動(dòng)方向的單位向量.

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

(6)

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

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

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

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

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

2)每個(gè)細(xì)菌代表一個(gè)傳感器節(jié)點(diǎn)，細(xì)菌在二維目標(biāo)監(jiān)測(cè)區(qū)域移動(dòng)，細(xì)菌搜索半徑為傳感器節(jié)點(diǎn)監(jiān)測(cè)半徑；

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

4)嚴(yán)格依照適應(yīng)值的排序確定細(xì)菌的存亡，每個(gè)存活的細(xì)菌必須且只能進(jìn)行一分為二的繁殖；

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

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

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

sij=e-λDij

(7)

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

當(dāng)所有菌落的細(xì)菌的趨向運(yùn)動(dòng)結(jié)束時(shí)，細(xì)菌以菌落為單位進(jìn)行復(fù)制操作，單個(gè)菌落適應(yīng)值為

(8)

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

2　基于細(xì)菌覓食優(yōu)化算法的無線傳感器網(wǎng)絡(luò)優(yōu)化部署實(shí)驗(yàn)

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

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

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

表1　基于細(xì)菌覓食優(yōu)化算法的傳感器節(jié)點(diǎn)部署實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

表2　三種優(yōu)化方法的對(duì)比實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

3　結(jié)論

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

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

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

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

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

[5]黃守志,趙學(xué)增等.基于網(wǎng)格劃分的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)冗余分析[J]. 東北石油大學(xué)學(xué)報(bào),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)絡(luò)部署及其覆蓋問題研究[J].電子與信息學(xué),2006,28(9):1752-1757.

[8]戴秋萍,馬良,郗瑩.連續(xù)優(yōu)化問題的細(xì)菌覓食改進(jìn)算法[J]. 上海理工大學(xué)學(xué)報(bào), 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)秀青年人才支持計(jì)劃重點(diǎn)項(xiàng)目(gxyqZD2016531)；安徽省2015年度省級(jí)質(zhì)量工程項(xiàng)目(2015gxk113)；安徽省2014年度省級(jí)質(zhì)量工程項(xiàng)目(2014jyxm524)

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

TP18

A