基于免疫算法的無線傳感網(wǎng)絡(luò)覆蓋研究*

馬敬思，史旭華，何婷婷，李瀟

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江 寧波 315211）

1 引言

微機電系統(tǒng)、片上系統(tǒng)、無線通信和低功耗嵌入式技術(shù)的飛速發(fā)展，孕育出無線傳感器網(wǎng)絡(luò)（WSN，Wireless Sensor Networks），并以其低功耗、低成本、分布式和自組織的特點帶來了信息感知的一場變革。由于傳感器節(jié)點能量有限，覆蓋范圍和形狀不穩(wěn)定，在進(jìn)行高密度部署時容易造成傳感器節(jié)點分布不均勻，節(jié)點嚴(yán)重冗余，因此如何對網(wǎng)絡(luò)覆蓋進(jìn)行優(yōu)化，以較少傳感器節(jié)點獲得較高網(wǎng)絡(luò)覆蓋率，成為當(dāng)前WSN研究中的關(guān)鍵課題。

針對WSN覆蓋優(yōu)化問題，大量學(xué)者對其進(jìn)行研究并取得較多的成果，但大部分的成果都是基于0-1感知模型和概率模型。0-1感知模型是一種離散的理想模型，適用于理論研究和數(shù)學(xué)證明。概率感知模型是一種連續(xù)模型，探測概率為目標(biāo)到傳感器的歐氏距離成指數(shù)關(guān)系。當(dāng)用網(wǎng)格數(shù)學(xué)模型建模時，這種概率感知模型在計算時會產(chǎn)生大量數(shù)據(jù)，對實驗結(jié)果并沒有明顯提升。文獻(xiàn)[1]中使用了混合感知模型，在覆蓋率一樣的情況下比0-1模型使用更少的傳感器節(jié)點，雖然在一定程度上減少了冗余覆蓋，但是采取的算法屬于單目標(biāo)優(yōu)化，不能同時使覆蓋率和節(jié)點利用率達(dá)到最優(yōu)。

本文采用混合感知模型，能較為實際地反映真實網(wǎng)絡(luò)。網(wǎng)格化建模后能較大地簡化概率計算數(shù)據(jù)，且能很好地處理聯(lián)合偵測概率的計算，同時采用基于濃度的克隆選擇多目標(biāo)優(yōu)化算法（CCSMOA），完成對可行解區(qū)域的全面搜索。另外，還區(qū)別個體的性能，在進(jìn)化過程中加大優(yōu)良個體的克隆倍數(shù)的同時也不放棄較差個體，以此來保證算法的優(yōu)良性能，使區(qū)域覆蓋率和節(jié)點利用率同時達(dá)到最優(yōu)。

2 無線傳感器的基本模型

2.1 0-1感知模型

根據(jù)上述描述，可以建立數(shù)學(xué)模型如下：

2.2 概率感知模型

隨著傳感器與監(jiān)控目標(biāo)間距離的增大，傳感器對目標(biāo)的感知概率也逐漸減小直至無法感知，稱為“概率感知模型”[3]。概率模型的探測概率函數(shù)可以表示為：

由式（2）可得，概率模型是一個感知概率隨著目標(biāo)節(jié)點j 與傳感器節(jié)點歐氏距離d(i,j)增大而成指數(shù)衰減的模型，λ是傳感器節(jié)點的衰減系數(shù)，只有當(dāng)d(i,j)為0時，p(x,y)才等于1。

2.3 混合感知模型

由于感知概率在靠近模型處一定范圍內(nèi)接近于1，在距離節(jié)點較遠(yuǎn)處接近為0，這種模型兼具0-1模型和概率模型的特點，所以也稱作混合感知模型[1]。

其中，λ是衰減系數(shù)，參數(shù)α=d(i,j)-rα。

2.4 節(jié)點的聯(lián)合感知

在隨機部署中，一個目標(biāo)可能被2個或以上的傳感器節(jié)點覆蓋，這個目標(biāo)的疊加的覆蓋概率為：

其中，n 為傳感器節(jié)點個數(shù)，Pri為傳感器i 的覆蓋概率。如果監(jiān)測目標(biāo)與兩個傳感器節(jié)點的任何一個的距離越近，則累積覆蓋概率也會增加[4]。

3 網(wǎng)格化平臺及編碼方案

設(shè)檢測區(qū)域為一個二維矩形區(qū)域，覆蓋區(qū)域的面積為A，將傳感器節(jié)點有計劃地投放到監(jiān)測區(qū)域中。本文首先對所投放的N 個傳感器節(jié)點的工作狀態(tài)進(jìn)行二進(jìn)制編碼：S=(s1,s2,…,sN)，則：

如圖1 所示，設(shè)定投放的節(jié)點有2 0 個，將它們進(jìn)行二進(jìn)制編碼，分成多組：10101 01010 10101 01010。

圖1 二進(jìn)制編碼

將長為m、寬為n 的矩形監(jiān)測區(qū)域離散化成m×n 個網(wǎng)格，每個網(wǎng)格的面積均為1。任何網(wǎng)格被一個傳感器節(jié)點覆蓋到就認(rèn)為是被該傳感器節(jié)點探測到，并且假設(shè)此網(wǎng)格被任意節(jié)點覆蓋是獨立的，任意節(jié)點之間對目標(biāo)的覆蓋互不干擾?？偟母采w率R 可以表示為：

其中，A 是面積為m×n 的檢測區(qū)域，A(S)是傳感器節(jié)點集合S=(s1,s2,…,sN)所監(jiān)測到的目標(biāo)區(qū)域面積，Pr(x,y)是處于第x 行、第y 列的網(wǎng)格點被偵測到的概率。則節(jié)點利用率的公式為：

其中，n 為點亮的傳感器節(jié)點數(shù)，N 為總的節(jié)點數(shù)。

對于0-1感知模型來說，網(wǎng)格點只要被任何一個或者多個傳感器節(jié)點覆蓋到，無論網(wǎng)格點被節(jié)點覆蓋的面積大小，就認(rèn)為此網(wǎng)格點100%被感知到了，而混合感知模型則不同。如圖2所示，將矩形區(qū)域離散化，小圓區(qū)域內(nèi)無論網(wǎng)格點被覆蓋的面積大小，被感知概率為100%，如網(wǎng)格點（4,4）；大圓區(qū)域以外的感知概率為0，如網(wǎng)格點（1,10）。大小圓之間的環(huán)形區(qū)域的網(wǎng)格點被感知概率隨著目標(biāo)距離傳感器節(jié)點越遠(yuǎn)而變得越小，具體見式（4）。

圖2 混合感知模型的網(wǎng)格化

4 人工免疫多目標(biāo)算法

4.1 人工免疫算法

使用免疫算法解決多目標(biāo)優(yōu)化問題，從高度抽象的角度來看，在邏輯上生物免疫系統(tǒng)與免疫多目標(biāo)優(yōu)化的映射關(guān)系如表1所示：

表1 生物免疫系統(tǒng)與免疫多目標(biāo)優(yōu)化的映射關(guān)系

抗體總是試圖以最佳的形態(tài)識別抗原，類似于線性規(guī)劃中求解最優(yōu)解，所以抗原可以被視為多目標(biāo)優(yōu)化的問題[1]。在這里抗原對應(yīng)覆蓋率和節(jié)點利用率；抗體被看作是多目標(biāo)優(yōu)化的候選解，對應(yīng)為傳感器節(jié)點的二進(jìn)制編碼；抗體鑒別抗原的程度可以被視為抗體的親和度，對應(yīng)的問題可以描述為：在點亮不同數(shù)目以及不同位置的傳感器節(jié)點情況下，覆蓋率和節(jié)點利用率的函數(shù)關(guān)系。

4.2 CCSMOA算法

本文采用基于濃度的克隆選擇多目標(biāo)優(yōu)化算法（CCSMOA）。該算法的關(guān)鍵在于將每代抗體的克隆次數(shù)與抗體濃度更新關(guān)聯(lián)，同時兼顧抗體-抗原親和力和抗體-抗體親和力的影響，使抗體濃度的計算轉(zhuǎn)化為一個關(guān)于抗體-抗原親和力和抗體-抗體親和力的函數(shù)，在進(jìn)化過程中加大對較好解的克隆倍數(shù)的同時也不放棄較差解，以此來保證算法的優(yōu)良性能。

CCSMOA算法流程圖如圖3所示，其中Pa為初始抗體濃度為C的抗體群。

（1）抗體-抗原親和力和抗體-抗體親和力的計算

抗體-抗原親和力的計算參考了SPEA2算法，因此使CCSMOA算法所求得的解更接近真實的Pareto前沿，也更均勻地分布在Pareto前沿上[5-6]。公式如下：

其中，fiAg表示抗體i 的抗體-抗原親和力，fSPEA2(i)代表抗體i 在SPEA2算法中的抗體-抗原親和力。對于抗體-抗原親和力小于1的非支配解，這時fiAg的值越小表示該抗體和抗原的匹配程度越高，而且密度也小，此抗體越優(yōu)秀。

圖3 CCSMOA算法流程圖

抗體-抗體親和力主要是為了評估抗體之間的相似性，CCSMOA算法中計算抗體i 與其歐氏距離小于或等于閾值σs的抗體間的相似程度的函數(shù)為fiAb(t)，其計算公式如下：

其中，fiAb(t)表示抗體i 在t 代時的抗體-抗體親和力，G是歐氏距離小于或等于σs的抗體集合，表示抗體g 在t 代時的濃度，d(i,g)表示抗體i 和抗體g 之間的歐氏距離[6]。從式（9）可以看出，只有存在比抗體i 優(yōu)秀的抗體，抗體i 的抗體-抗體親和力才不為0，并且只將與其距離在σs范圍內(nèi)的抗體納入抗體-抗體親和力的計算，有效保留了在進(jìn)化過程中相對較差的解，也不至于使得較好的解很快地占據(jù)進(jìn)化過程。

（2）抗體濃度的更新

該算法中抗體濃度的更新取決于抗體-抗原親和力和抗體-抗體親和力?？贵w的濃度同時又影響了抗體的克隆次數(shù)，基于以上把抗體濃度的更新定義為上一代的抗體濃度和抗體-抗原親和力的函數(shù)，計算公式如下：

其中，Cit1和Cit的范圍都是[0,1]，且分別代表抗體i 的新舊濃度。比例系數(shù)α 決定了抗體濃度所占的比重，這個比重又取決于抗體的抗體-抗原親和力，其計算公式如下：

（3）克隆基因操作和外部記憶抗體群更新

在每次迭代中，每個抗體都有自己的克隆倍數(shù)，此算法中每個抗體的克隆倍數(shù)取決于自身的抗體濃度。那么，濃度為 Cit抗體i 的克隆倍數(shù)為：

隨后對克隆后的抗體群實施交叉和變異操作。交叉操作采用模擬二進(jìn)制交叉，它的數(shù)學(xué)描述為：

式（13）、式（14）分別表示抗體 x1和抗體 x2經(jīng)過交叉得到的抗體 x1'和抗體 x2'的計算公式。其中β的數(shù)學(xué)描述為：

其中，r 是[0,1]的隨機數(shù)，η 為分布指數(shù)。η 越大，則通過交叉操作產(chǎn)生的子代抗體就與父代抗體越相近；反之，則會越遠(yuǎn)[9]。

變異操作采用由Deb提出的多項式變異[10]。多項式變異是目前多目標(biāo)優(yōu)化算法中常用的一種變異方法，它的數(shù)學(xué)描述是：

其中β 的數(shù)學(xué)描述為：

5 仿真及結(jié)果分析

設(shè)定檢測區(qū)域為200m*200m的矩形區(qū)域，混合感知模型的ra為10m、rb為15m，衰減系數(shù)λ 為0.01，分別部署1 5 0 個節(jié)點到此區(qū)域，CCSMOA 算法和NINA算法的參數(shù)指標(biāo)：變異概率β 為0.1，抑制閾值σs為0.06，算法迭代次數(shù)為100。則得到的仿真圖如圖4所示：

圖4 2種算法的混合感知模型仿真圖

由圖4可以看出，CCSMOA算法的曲線比NINA算法的平滑，而且覆蓋率超過0.8曲線部分，CCSMOA算法的點數(shù)明顯比NINA算法的密集，這是由于NINA加強了對所謂精英區(qū)域的搜索，而放棄對那些可能存在好的解的區(qū)域的搜索，從而導(dǎo)致過早地局部收斂，很難達(dá)到全局最優(yōu)。而CCSMOA算法能對可行解區(qū)域全面搜索，同時也要區(qū)別好的和壞的個體，在進(jìn)化的過程中加大對較好解的克隆倍數(shù)的同時也不放棄較差解，以此來保證算法的優(yōu)良性能，使區(qū)域覆蓋率和節(jié)點利用率同時達(dá)到最優(yōu)。

設(shè)定檢測區(qū)域為100m*100m的正方形區(qū)域，0-1感知模型的r(i)為12m，得到的仿真圖如圖5所示：

圖5 0-1感知模型和混合感知模型100m*100m區(qū)域覆蓋

從圖5可知：當(dāng)節(jié)點利用率為0.1時，0-1感知模型覆蓋率為45%，而混合感知模型能達(dá)到將近70%；當(dāng)利用率為0.2時，混合感知模型已經(jīng)達(dá)到90%，而0-1感知模型不到75%。

如圖6所示，將覆蓋區(qū)域改為200m*200m，投放的節(jié)點數(shù)目改為300，其他參數(shù)不變。CCSMOA算法在覆蓋率和節(jié)點利用率上的優(yōu)化并沒有什么改進(jìn)，但是100m*100m區(qū)域覆蓋在節(jié)點利用率從0.3到0.4之間出現(xiàn)了缺失或者曲線波動較大，這個情況在200m*200m的區(qū)域覆蓋時并沒有出現(xiàn)。這是由于100m*100m的解空間較小，算法的收斂出現(xiàn)問題，沒有找到最優(yōu)解。雖然混合感知模型的曲線由于CCSMOA算法的收斂性還不夠優(yōu)秀而呈現(xiàn)出些許曲折，但是在覆蓋率和節(jié)點利用率這2個目標(biāo)的優(yōu)化上，混合感知模型比0-1感知模型在仿真中表現(xiàn)得更優(yōu)異。

圖6 0-1感知模型和混合感知模型200m*200m區(qū)域覆蓋

6 結(jié)束語

本文將基于濃度的克隆選擇多目標(biāo)優(yōu)化算法（CCSMOA）用于無線傳感網(wǎng)絡(luò)的網(wǎng)格化平臺，通過對抗體濃度的控制，完成對可行解區(qū)域的全面搜索，同時也要區(qū)別不同的個體，在進(jìn)化的過程中加大對較好解的克隆倍數(shù)的同時也不放棄較差解，以此來保證算法的優(yōu)良性能。仿真結(jié)果表明，CCSMOA算法能使區(qū)域覆蓋率和節(jié)點利用率達(dá)到較好的平衡。

[1] 王震,陳云芳. 基于人工免疫的多目標(biāo)優(yōu)化研究綜述[J]. 計算機應(yīng)用研究, 2009(7): 2422-2426.

[2] Chakrabarty K, Iyengar S S, Qi H, et al. Grid Coverage for Sutveillance and Target Location in Distributed Sensor Networks[J]. IEEE Transactions on Computers, 2002,51(12): 1448-1453.

[3] Dhillon S S, Chakrabarty K, Iyengar S S. Sensor Placement for Effective Coverage and Surveillan in Distributed Sensor Networks[A]. IEEE Wireless Communication and Networking Record[C]. Piscataway: IEEE, 2003: 1609-1614.

[4] Cao Qing, Yan Ting. Analysis of Target Detection Performance for Wireless Sensor Networks[A]. International Conference on Distributed Computing in Sensor Systems[C]. 2005: 276-292.

[5] 雷德明,嚴(yán)新平. 多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2009.

[6] 劉楠楠,史旭華. 基于抗體濃度的克隆選擇多目標(biāo)優(yōu)化算法及其應(yīng)用[J]. 寧波大學(xué)學(xué)報: 理工版, 2013(3): 57-61.

[7] 焦李成,尚榮華. 多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用[M]. 北京: 科學(xué)出版社, 2010.

[8] 曾廣樸,仲元昌,范會聯(lián). 混合無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化的粒子群算法[J]. 微電子學(xué)與計算機, 2011(8): 105-107.

[9] 崔遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M]. 北京: 國防工業(yè)出版社, 2006.

[10] 焦李成,杜海峰. 人工免疫進(jìn)展與展望[J]. 電子學(xué)報, 2003(10): 1540-1548.

[11] 程博,郭振宇,王軍平,等. 一種并行免疫進(jìn)化策略算法研究[J]. 控制與決策, 2007(12): 1395-1398.★