基于二進(jìn)制入侵雜草算法的無(wú)線傳感網(wǎng)絡(luò)覆蓋研究

解放軍61112部隊(duì)，黑龍江牡丹江 157011

一、引言

在許多目標(biāo)覆蓋的應(yīng)用中，比如導(dǎo)航、目標(biāo)定位等，每個(gè)被監(jiān)測(cè)目標(biāo)通常需要被多個(gè)無(wú)線傳感器節(jié)點(diǎn)所覆蓋。由于傳感器感知范圍、通信能力和數(shù)據(jù)處理能力的限制，通常每個(gè)傳感器節(jié)點(diǎn)所能感知的目標(biāo)數(shù)量是有限的。在無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)覆蓋中，如何在監(jiān)測(cè)能力和傳感器節(jié)點(diǎn)數(shù)量有限的前提下提高監(jiān)測(cè)區(qū)域的目標(biāo)覆蓋率，是影響網(wǎng)絡(luò)性能的重要因素，進(jìn)而也會(huì)影響網(wǎng)絡(luò)的生命周期。在無(wú)線傳感器網(wǎng)絡(luò)中，使用較少的節(jié)點(diǎn)工作可以減少通信跳數(shù)，降低數(shù)據(jù)冗余和通信干擾，降低能耗，從而提高網(wǎng)絡(luò)的生命周期?？梢钥紤]采用節(jié)點(diǎn)輪值的方法優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋。采用節(jié)點(diǎn)輪值方法時(shí)，選擇合適的節(jié)點(diǎn)工作和休眠是一個(gè)關(guān)鍵問(wèn)題。

入侵雜草算法（Invasive Weed Optimization，IWO）是C. Lucas和A. R. Mehrabian在2006年通過(guò)模擬自然界中雜草擴(kuò)散入侵過(guò)程的隨機(jī)搜索仿生優(yōu)化算法[1]。該算法是一種很強(qiáng)大的智能優(yōu)化算法，具有易于理解、收斂性好、魯棒性強(qiáng)、易于實(shí)現(xiàn)、結(jié)構(gòu)簡(jiǎn)單等優(yōu)點(diǎn)，目前，IWO算法已成功應(yīng)用于DNA序列計(jì)算[1]、線性天線設(shè)計(jì)、電力線通信系統(tǒng)資源分配、圖像識(shí)別、圖像聚類、約束工程設(shè)計(jì)、壓電激勵(lì)器放置等。

IWO算法主要解決連續(xù)空間的浮點(diǎn)數(shù)問(wèn)題，在離散空間中無(wú)法直接運(yùn)用。然而在實(shí)際應(yīng)用中，有許多問(wèn)題，比如生物科學(xué)及計(jì)算機(jī)科學(xué)中的組合問(wèn)題、背包問(wèn)題等，只能在離散空間中才能解決。

為了在離散空間應(yīng)用入侵雜草算法，將其進(jìn)行改進(jìn)，提出了一個(gè)二進(jìn)制的入侵雜草算法，即BIWO（Binary Invasive Weed Optimization algorithm，BIWO）算法。本文用改進(jìn)的二進(jìn)制入侵雜草算法解決無(wú)線傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題，采用了自適應(yīng)標(biāo)準(zhǔn)差，能保證較快地收斂于全局最優(yōu)解，能夠選擇合適節(jié)點(diǎn)進(jìn)行休眠及激活，能夠提高網(wǎng)絡(luò)的覆蓋率，延長(zhǎng)網(wǎng)絡(luò)的生命周期。

二、入侵雜草算法

1、入侵雜草算法的基本步驟

入侵雜草算法的實(shí)現(xiàn)通常也需要四個(gè)步驟，包括初始化雜草種群、繁殖、空間擴(kuò)散分布、競(jìng)爭(zhēng)性排斥規(guī)則[2]。

（1）初始化種群

設(shè)置入侵雜草算法的相關(guān)參數(shù)，設(shè)定最大種群規(guī)模Pmax，初始化種群數(shù)N0，所求問(wèn)題維數(shù)d，最大迭代次數(shù)itermax，繁殖的種子數(shù)的上下限Smax和Smin，非線性調(diào)和因子n。

（2）繁殖

雜草在進(jìn)化過(guò)程中所產(chǎn)生的種子數(shù)目與雜草的適應(yīng)度值是呈線性相關(guān)的關(guān)系[3]。每個(gè)雜草產(chǎn)生的種子數(shù)的表達(dá)式為：

其中：f—當(dāng)前雜草的適應(yīng)度值；

fmin—當(dāng)前種群中雜草的最小適應(yīng)值；

fmax—當(dāng)前種群中雜草的最大適應(yīng)值；

Smin—一個(gè)雜草所能生成種子的最小數(shù)量；

Smax—一個(gè)雜草所能生成種子的最大數(shù)量。

當(dāng)前種群中雜草適應(yīng)度值范圍為[fmin,fmax]，一顆雜草所能繁殖種子的數(shù)量范圍為[Smin,Smax]。

（3）空間分布

雜草產(chǎn)生的種子在父代個(gè)體的周圍形成正態(tài)分布，其均值為零，標(biāo)準(zhǔn)差為σcur。隨著進(jìn)化次數(shù)的增加，標(biāo)準(zhǔn)差可按下式計(jì)算：

其中，σcur—當(dāng)前標(biāo)準(zhǔn)差；

itermax—最大進(jìn)化迭代次數(shù)；

iter—當(dāng)前進(jìn)化迭代次數(shù)；

σinit和σ fi nal—標(biāo)準(zhǔn)差的初始值和最終值；

n—非線性調(diào)和因子。

每輪進(jìn)化對(duì)應(yīng)的標(biāo)準(zhǔn)差并不一樣，隨著進(jìn)化的進(jìn)行，標(biāo)準(zhǔn)差從σinit一直變化到σ fi nal；一般情況下設(shè)置為n=3。

（4）競(jìng)爭(zhēng)性排斥規(guī)則

競(jìng)爭(zhēng)性排斥規(guī)則是經(jīng)過(guò)多次進(jìn)化之后，當(dāng)種群規(guī)模達(dá)到Pmax，按照適應(yīng)度值大小對(duì)所有的個(gè)體進(jìn)行排序，淘汰適應(yīng)度較差的個(gè)體，保留其余個(gè)體。

重復(fù)以上四步直至達(dá)到最大迭代次數(shù)。

2、入侵雜草算法的收斂性

對(duì)智能優(yōu)化算法我們要考慮它的收斂性，根據(jù)C.Lucas和A. R. Mehrabian的研究，要提高入侵雜草算法的搜索到最優(yōu)解成功率，把雜草種群的規(guī)模擴(kuò)大并不能起明顯作用，而非線性調(diào)和因子n對(duì)入侵雜草算法的收斂起著至關(guān)重要的作用[2]。入侵雜草算法在不斷迭代的過(guò)程中，適應(yīng)度值優(yōu)的個(gè)體，將繁殖許多相類似的個(gè)體，同時(shí)適應(yīng)度值較差的個(gè)體也會(huì)有產(chǎn)生子代的機(jī)會(huì)，且與子代個(gè)體一起執(zhí)行競(jìng)爭(zhēng)性排斥規(guī)則[4]。繁殖的子代個(gè)體是隨機(jī)地散布在父代個(gè)體周圍呈現(xiàn)正態(tài)分布的方式，根據(jù)正態(tài)分布的特點(diǎn)，這種方法產(chǎn)生的子代大多在上一代適應(yīng)度值較優(yōu)的個(gè)體附近集中，為了實(shí)現(xiàn)種群多樣性，同時(shí)對(duì)上一代適應(yīng)度值較優(yōu)的個(gè)體附近以外的區(qū)域也能兼顧。

三、雜草入侵算法離散化

1、入侵雜草算法離散化算法流程

BIWO算法的實(shí)現(xiàn)步驟和IWO算法類似，也分為四個(gè)步驟：

（1）初始化二進(jìn)制種群

對(duì)實(shí)際問(wèn)題采用適當(dāng)?shù)木幋a方法，每個(gè)雜草均為由隨機(jī)函數(shù)產(chǎn)生一個(gè)二進(jìn)制編碼序列。單個(gè)雜草使用序列(x1,x2,...,xi,...xn-1,xn)來(lái)表示，其中xi為雜草的比特位，其值只能取1或0。

（2）產(chǎn)生種子

與IWO產(chǎn)生種子的方法一樣，即利用式（1）計(jì)算雜草的繁殖的種子數(shù)目。

（3）二進(jìn)制空間擴(kuò)散

在取值連續(xù)的入侵雜草算法中，雜草種子個(gè)體僅在其父代個(gè)體周圍以0為均值，標(biāo)準(zhǔn)差為σ隨機(jī)的正態(tài)擴(kuò)散分布。但是這種擴(kuò)散方法并不能直接在BIWO算法中應(yīng)用，我們使用變異機(jī)制去產(chǎn)生和擴(kuò)散種子。在BIWO算法中，在整個(gè)的迭代過(guò)程中，標(biāo)準(zhǔn)差σ也將采用和IWO算法類似的變化過(guò)程。產(chǎn)生的擴(kuò)散值通過(guò)特定的映射產(chǎn)生變異概率后作用于父代雜草的比特位，并不是直接作用于雜草個(gè)體。種群在當(dāng)進(jìn)化進(jìn)行到第k輪時(shí)，對(duì)于當(dāng)前種群中某個(gè)雜草的某個(gè)比特位xik，當(dāng)前正態(tài)分布標(biāo)準(zhǔn)差為σk，Dik是根據(jù)正態(tài)分布隨機(jī)函數(shù)N(0,σk2)得到的其對(duì)應(yīng)擴(kuò)散值，設(shè)計(jì)的映射函數(shù)為式（3）。父代種子的每一位可以通過(guò)式（3）計(jì)算變異概率。式（3）所對(duì)應(yīng)的映射函數(shù)曲線見(jiàn)圖1。

當(dāng)雜草二進(jìn)制序列每位變異概率計(jì)算后，當(dāng)計(jì)算雜草所代表的每一位的變異率時(shí)，一個(gè)相同的在[0, 1]上的隨機(jī)分布數(shù)值會(huì)產(chǎn)生，從而可以通過(guò)公式（4）計(jì)算具體的變異的位：

其中，ρ—[0, 1]之間的隨機(jī)數(shù)。

（4）競(jìng)爭(zhēng)排斥規(guī)則

采用與入侵雜草算法一樣的方式，每輪迭代后種群按適應(yīng)度大小排序，種群規(guī)模保持不變。

2、開(kāi)拓能力和開(kāi)發(fā)能力

為了保證算法較快收斂到全局最優(yōu)解，我們必須考慮算法的開(kāi)發(fā)能力和開(kāi)拓能力。算法在某個(gè)較小的區(qū)域里進(jìn)行徹底搜索能力稱為開(kāi)發(fā)能力，算法在整個(gè)搜索空間中開(kāi)拓新區(qū)域能力稱為開(kāi)拓能力。入侵雜草算法同時(shí)具有這兩種能力。在迭代初期，設(shè)置較大的σi值，使種子個(gè)體散布到距離父代很遠(yuǎn)的地方，此時(shí)算法很強(qiáng)的擴(kuò)散能力，種群有較大的多樣性，即開(kāi)拓能力較強(qiáng)；當(dāng)種子進(jìn)化到后期時(shí)，逐漸減小σi值，從而種子的擴(kuò)散范圍也相應(yīng)地縮小，原先的優(yōu)勢(shì)群體會(huì)繁殖產(chǎn)生更多的后代，因?yàn)榉N群的規(guī)模是不變的，σi值減小會(huì)造成優(yōu)勢(shì)個(gè)體的后代由于擴(kuò)散半徑較小，生存能力更強(qiáng)，從而可以在適應(yīng)度值較好的局部區(qū)域搜索，從具有較強(qiáng)的開(kāi)拓能力逐漸變成有較強(qiáng)的開(kāi)發(fā)能力[3]，搜索范圍從全局也能逐漸變化到局部區(qū)域。

3、標(biāo)準(zhǔn)差取值

在入侵雜草算法中，σi會(huì)直接影響雜草個(gè)體的擴(kuò)散范圍。若σ fi n較大，將導(dǎo)致后期的σi較大，增大了種群的多樣性，但是會(huì)使算法不能有效地進(jìn)行局部開(kāi)發(fā)，較長(zhǎng)時(shí)間停留在全局開(kāi)拓階段，從而增大了搜索全局最優(yōu)解的難度；若σini較小，將導(dǎo)致初期的σi較小，表現(xiàn)為初始搜索范圍較小，使種群的多樣性小，同樣使搜索全局最優(yōu)解存在較大的困難。不同的實(shí)際問(wèn)題往往千差萬(wàn)別，故必須依據(jù)實(shí)際問(wèn)題預(yù)估σini和σ fi n，來(lái)確定其對(duì)開(kāi)發(fā)精度和開(kāi)拓范圍的要求，以便更好地搜索到全局最優(yōu)解，更加恰當(dāng)?shù)亟鉀Q實(shí)際問(wèn)題。

從上面我們知道，σcur定義了算法的開(kāi)發(fā)和開(kāi)拓能力，對(duì)最終的結(jié)果有極大的影響，很好的多樣性能使算法搜索到全局最優(yōu)解，算法通過(guò)該參數(shù)能夠確定全局最優(yōu)解的位置，適當(dāng)?shù)募心軌蚴顾惴ㄩ_(kāi)拓有潛在最優(yōu)解的區(qū)域而得到全局最優(yōu)解。它會(huì)增加算法的收斂速度和找到更優(yōu)的最終解。因此，保持算法的多樣性和集中的平衡是很重要的。但是若使用了固定的σcur去產(chǎn)生每個(gè)雜草的種子導(dǎo)致缺乏在開(kāi)發(fā)性和開(kāi)拓性之間的平衡。

為了克服以上的缺點(diǎn)，我們采用自適應(yīng)的分散機(jī)制。保證σcur在當(dāng)前一代線性分布，最大的適應(yīng)值獲得最小的σcur，最小的適應(yīng)值獲得最大的σcur。j是根據(jù)他們適應(yīng)值大小分類的雜草的編號(hào)。σcur能夠通過(guò)公式（2）計(jì)算，Psum是當(dāng)前這一代的雜草的數(shù)量，σj是第j個(gè)雜草的σcur。因此，較低適應(yīng)度的雜草能夠在當(dāng)前這一代產(chǎn)生較好的種子，另外，這樣增加了算法的多樣性，因此算法能夠更有效地搜索空間。

改進(jìn)的BIWO算法的偽代碼如下：

1. 用二進(jìn)制序列隨機(jī)產(chǎn)生雜草P0；

2. Foriter〈itermax執(zhí)行下一步；

3.通過(guò)公式（9）計(jì)算每個(gè)雜草的適應(yīng)度；

4. 對(duì)這些適應(yīng)度進(jìn)行分類；

5. 記錄最大的和最小的適應(yīng)度值；

6. 計(jì)算種子的數(shù)目Num；

7. 通過(guò)公式（2）和（5）計(jì)算每個(gè)種子的標(biāo)準(zhǔn)差；

8. 通過(guò)公式（4）產(chǎn)生種子；

9. 把種子加入種群；

10. If(Num〉Pmax)，執(zhí)行下一步；

11. 對(duì)種群依據(jù)適應(yīng)度值進(jìn)行分類；

12. 保存適應(yīng)度值最好的雜草直到Num=Pmax；

13. End if；

14. End for。

四、基于BIWO算法的WSN目標(biāo)覆蓋優(yōu)化

1、無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署模型

現(xiàn)在假定在Fx×Fy的二維平面區(qū)域內(nèi)開(kāi)始隨機(jī)布置N個(gè)傳感器節(jié)點(diǎn)，同時(shí)有M個(gè)隨機(jī)或者通過(guò)某種特定的方式選出來(lái)的需要監(jiān)視的目標(biāo)點(diǎn)，同時(shí)有一個(gè)Sink節(jié)點(diǎn)。同時(shí)，有一些獨(dú)立的需要監(jiān)視的目標(biāo)點(diǎn)POI（points of interest），在整個(gè)網(wǎng)絡(luò)的生存期內(nèi)，這些目標(biāo)點(diǎn)必須被至少一個(gè)的傳感器節(jié)點(diǎn)監(jiān)視。采用二進(jìn)制編碼表示節(jié)點(diǎn)的狀態(tài)，節(jié)點(diǎn)休眠時(shí)，用“0”表示；節(jié)點(diǎn)處于激活狀態(tài)時(shí),用“1”表示。整個(gè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的工作狀態(tài)用一個(gè)二進(jìn)制串表示。這種表示方法簡(jiǎn)潔易懂。

（1）能量消耗模型

我們要考慮無(wú)線傳輸?shù)哪芰肯?，其他比如接收?shù)據(jù)、訪問(wèn)內(nèi)存的能量消耗在此忽略不計(jì)。

其中，ETx和ERx—傳送和接收一個(gè)H位的數(shù)據(jù)包的能量消耗；

Eelec—發(fā)送和接收一位數(shù)據(jù)的能量消耗；

Eamp—每位數(shù)據(jù)進(jìn)行功率放大的損失；

β—路徑能量損耗的指數(shù)。

（2）無(wú)線傳感器的二進(jìn)制模型

我們使用一個(gè)變量γi,j代表一個(gè)傳感器節(jié)點(diǎn)i能否覆蓋某個(gè)為j的POI。若一個(gè)POI位于一個(gè)傳感器節(jié)點(diǎn)的感知范圍γs內(nèi)，γi,j為1，否則取0。可以定義為：

其中，(xi,yi)和(yi,yj)—傳感器節(jié)點(diǎn)i和目標(biāo)j。

2、適應(yīng)度評(píng)價(jià)函數(shù)

我們?cè)O(shè)定兩個(gè)相關(guān)的參數(shù)εx和γx,分別代表在當(dāng)前雜草X覆蓋比例和可用的節(jié)點(diǎn)數(shù)，因此適應(yīng)度函數(shù)可以表示如下：

其中，α1和α2—權(quán)重系數(shù)；

β1和β2—指數(shù)因子。

通過(guò)調(diào)整權(quán)重系數(shù)和指數(shù)因子，可以確定相應(yīng)的適應(yīng)度。Ai代表雜草二進(jìn)制序列的每一位，其取值是0或者1。我們可以通過(guò)下列公式計(jì)算ρx和εx：

如果雜草x有較大的適應(yīng)度，表明此時(shí)能監(jiān)視更多的目標(biāo)區(qū)域。ρx越大，適應(yīng)度越大；而εx越小，適應(yīng)度越大。在搜索的過(guò)程中，每個(gè)雜草都需要按照適應(yīng)度值大小進(jìn)行排序。

五、仿真實(shí)驗(yàn)

為了檢驗(yàn)該算法的性能，采用Matlab對(duì)算法應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問(wèn)題進(jìn)行仿真實(shí)驗(yàn)。

1、參數(shù)設(shè)置

我們需要在大小不同規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)評(píng)價(jià)入侵雜草算法的收斂性。我們可以設(shè)置目標(biāo)點(diǎn)m=64隨機(jī)地分布在100m×100m的監(jiān)控區(qū)域內(nèi)，隨機(jī)分布的傳感器節(jié)點(diǎn)數(shù)目為50～500，節(jié)點(diǎn)的感知半徑rs為17.675m。數(shù)據(jù)包的大小為H位。

Eelec—發(fā)送和接收一位數(shù)據(jù)的能量消耗；

Eamp—每位數(shù)據(jù)進(jìn)行功率放大的損失；

β—路徑能量損耗的指數(shù)；

α1、α2—適應(yīng)度函數(shù)權(quán)重系數(shù)；

β1、β2—適應(yīng)度函數(shù)指數(shù)因子。

主要參數(shù)設(shè)置如表1。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

2、與遺傳算法比較收斂性

圖2清晰的表明入侵雜草算法優(yōu)于遺傳算法（Genetic Algorithm，GA），因?yàn)槎M(jìn)制入侵雜草算法BIWO能夠更好地布置節(jié)點(diǎn)，在散布500個(gè)節(jié)點(diǎn)的情況下，平均的適應(yīng)度比GA提高了52.8%，同時(shí)雜草入侵算法比GA需要更短的收斂時(shí)間。但是隨著需要散布的節(jié)點(diǎn)數(shù)目增加，平均的收斂時(shí)間也隨之增加。這是因?yàn)楣?jié)點(diǎn)數(shù)目和目標(biāo)點(diǎn)的增加，增大了問(wèn)題的復(fù)雜度。這個(gè)現(xiàn)象在應(yīng)用GA時(shí)更加明顯。

3、覆蓋保持和網(wǎng)絡(luò)生存時(shí)間的延長(zhǎng)

延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生存時(shí)間，提高它的覆蓋度一直是無(wú)線傳感器網(wǎng)絡(luò)研究的重要目標(biāo)。在圖3中可以看到，隨著無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增多，對(duì)目標(biāo)點(diǎn)的完全覆蓋能夠持續(xù)更長(zhǎng)的時(shí)間。因?yàn)楫?dāng)出現(xiàn)死亡節(jié)點(diǎn)時(shí)，能夠喚醒合適節(jié)點(diǎn)的概率更大。若所有的節(jié)點(diǎn)在一開(kāi)始全部激活，覆蓋比率下降的很快。很多節(jié)點(diǎn)很快就耗盡了能量。通過(guò)采用改進(jìn)的二進(jìn)制雜草入侵雜草算法，網(wǎng)絡(luò)的壽命得到了顯著的提高。同樣表明，雜草入侵算法適用于不同的網(wǎng)絡(luò)規(guī)模。

六、結(jié)束語(yǔ)

無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制問(wèn)題是當(dāng)前學(xué)者們研究的一個(gè)熱點(diǎn)問(wèn)題。本文研究在無(wú)線傳感器的目標(biāo)覆蓋中如何提高覆蓋的質(zhì)量和效果，延長(zhǎng)網(wǎng)絡(luò)的生命周期。在入侵雜草算法的基礎(chǔ)上，把入侵雜草算法二進(jìn)制化，并在生成種子時(shí)采用自適應(yīng)的擴(kuò)散機(jī)制。仿真結(jié)果表明，相比GA，此算法在收斂性和延長(zhǎng)網(wǎng)絡(luò)的壽命上具有明顯的優(yōu)勢(shì)，且能夠提高目標(biāo)的覆蓋度。