解放軍61112部隊，黑龍江牡丹江 157011

一、引言

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

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

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

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

二、入侵雜草算法

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

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

（1）初始化種群

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

（2）繁殖

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

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

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

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

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

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

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

（3）空間分布

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

其中，σ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)化對應(yīng)的標(biāo)準(zhǔn)差并不一樣，隨著進(jìn)化的進(jìn)行，標(biāo)準(zhǔn)差從σinit一直變化到σ fi nal；一般情況下設(shè)置為n=3。

（4）競爭性排斥規(guī)則

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

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

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

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

三、雜草入侵算法離散化

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

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

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

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

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

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

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

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

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

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

（4）競爭排斥規(guī)則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9. 把種子加入種群；

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

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

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

13. End if；

14. End for。

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

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

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

（1）能量消耗模型

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

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

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

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

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

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

我們使用一個變量γi,j代表一個傳感器節(jié)點i能否覆蓋某個為j的POI。若一個POI位于一個傳感器節(jié)點的感知范圍γs內(nèi)，γi,j為1，否則取0?？梢远x為：

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

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

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

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

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

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

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

五、仿真實驗

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

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

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

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

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

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

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

六、結(jié)束語

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