基于二進制入侵雜草算法的無線傳感網絡覆蓋研究

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

一、引言

在許多目標覆蓋的應用中，比如導航、目標定位等，每個被監測目標通常需要被多個無線傳感器節點所覆蓋。由于傳感器感知范圍、通信能力和數據處理能力的限制，通常每個傳感器節點所能感知的目標數量是有限的。在無線傳感器網絡目標覆蓋中，如何在監測能力和傳感器節點數量有限的前提下提高監測區域的目標覆蓋率，是影響網絡性能的重要因素，進而也會影響網絡的生命周期。在無線傳感器網絡中，使用較少的節點工作可以減少通信跳數，降低數據冗余和通信干擾，降低能耗，從而提高網絡的生命周期。可以考慮采用節點輪值的方法優化無線傳感器網絡的目標覆蓋。采用節點輪值方法時，選擇合適的節點工作和休眠是一個關鍵問題。

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

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

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

二、入侵雜草算法

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

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

（1）初始化種群

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

（2）繁殖

雜草在進化過程中所產生的種子數目與雜草的適應度值是呈線性相關的關系[3]。每個雜草產生的種子數的表達式為：

其中：f—當前雜草的適應度值；

fmin—當前種群中雜草的最小適應值；

fmax—當前種群中雜草的最大適應值；

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

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

當前種群中雜草適應度值范圍為[fmin,fmax]，一顆雜草所能繁殖種子的數量范圍為[Smin,Smax]。

（3）空間分布

雜草產生的種子在父代個體的周圍形成正態分布，其均值為零，標準差為σcur。隨著進化次數的增加，標準差可按下式計算：

其中，σcur—當前標準差；

itermax—最大進化迭代次數；

iter—當前進化迭代次數；

σinit和σ fi nal—標準差的初始值和最終值；

n—非線性調和因子。

每輪進化對應的標準差并不一樣，隨著進化的進行，標準差從σinit一直變化到σ fi nal；一般情況下設置為n=3。

（4）競爭性排斥規則

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

重復以上四步直至達到最大迭代次數。

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

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

三、雜草入侵算法離散化

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

BIWO算法的實現步驟和IWO算法類似，也分為四個步驟：

（1）初始化二進制種群

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

（2）產生種子

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

（3）二進制空間擴散

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

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

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

（4）競爭排斥規則

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

2、開拓能力和開發能力

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

3、標準差取值

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

從上面我們知道，σcur定義了算法的開發和開拓能力，對最終的結果有極大的影響，很好的多樣性能使算法搜索到全局最優解，算法通過該參數能夠確定全局最優解的位置，適當的集中能夠使算法開拓有潛在最優解的區域而得到全局最優解。它會增加算法的收斂速度和找到更優的最終解。因此，保持算法的多樣性和集中的平衡是很重要的。但是若使用了固定的σcur去產生每個雜草的種子導致缺乏在開發性和開拓性之間的平衡。

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

改進的BIWO算法的偽代碼如下：

1. 用二進制序列隨機產生雜草P0；

2. Foriter〈itermax執行下一步；

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

4. 對這些適應度進行分類；

5. 記錄最大的和最小的適應度值；

6. 計算種子的數目Num；

7. 通過公式（2）和（5）計算每個種子的標準差；

8. 通過公式（4）產生種子；

9. 把種子加入種群；

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

11. 對種群依據適應度值進行分類；

12. 保存適應度值最好的雜草直到Num=Pmax；

13. End if；

14. End for。

四、基于BIWO算法的WSN目標覆蓋優化

1、無線傳感器網絡節點部署模型

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

（1）能量消耗模型

我們要考慮無線傳輸的能量消耗，其他比如接收數據、訪問內存的能量消耗在此忽略不計。

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

Eelec—發送和接收一位數據的能量消耗；

Eamp—每位數據進行功率放大的損失；

β—路徑能量損耗的指數。

（2）無線傳感器的二進制模型

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

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

2、適應度評價函數

我們設定兩個相關的參數εx和γx,分別代表在當前雜草X覆蓋比例和可用的節點數，因此適應度函數可以表示如下：

其中，α1和α2—權重系數；

β1和β2—指數因子。

通過調整權重系數和指數因子，可以確定相應的適應度。Ai代表雜草二進制序列的每一位，其取值是0或者1。我們可以通過下列公式計算ρx和εx：

如果雜草x有較大的適應度，表明此時能監視更多的目標區域。ρx越大，適應度越大；而εx越小，適應度越大。在搜索的過程中，每個雜草都需要按照適應度值大小進行排序。

五、仿真實驗

為了檢驗該算法的性能，采用Matlab對算法應用于無線傳感器網絡的目標覆蓋問題進行仿真實驗。

1、參數設置

我們需要在大小不同規模的無線傳感器網絡評價入侵雜草算法的收斂性。我們可以設置目標點m=64隨機地分布在100m×100m的監控區域內，隨機分布的傳感器節點數目為50～500，節點的感知半徑rs為17.675m。數據包的大小為H位。

Eelec—發送和接收一位數據的能量消耗；

Eamp—每位數據進行功率放大的損失；

β—路徑能量損耗的指數；

α1、α2—適應度函數權重系數；

β1、β2—適應度函數指數因子。

主要參數設置如表1。

表1 實驗參數設置

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

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

3、覆蓋保持和網絡生存時間的延長

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

六、結束語

無線傳感器網絡覆蓋控制問題是當前學者們研究的一個熱點問題。本文研究在無線傳感器的目標覆蓋中如何提高覆蓋的質量和效果，延長網絡的生命周期。在入侵雜草算法的基礎上，把入侵雜草算法二進制化，并在生成種子時采用自適應的擴散機制。仿真結果表明，相比GA，此算法在收斂性和延長網絡的壽命上具有明顯的優勢，且能夠提高目標的覆蓋度。