基于免疫算法的無線傳感網絡覆蓋研究*

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

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

1 引言

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

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

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

2 無線傳感器的基本模型

2.1 0-1感知模型

根據上述描述，可以建立數學模型如下：

2.2 概率感知模型

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

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

2.3 混合感知模型

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

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

2.4 節點的聯合感知

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

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

3 網格化平臺及編碼方案

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

如圖1 所示，設定投放的節點有2 0 個，將它們進行二進制編碼，分成多組：10101 01010 10101 01010。

圖1 二進制編碼

將長為m、寬為n 的矩形監測區域離散化成m×n 個網格，每個網格的面積均為1。任何網格被一個傳感器節點覆蓋到就認為是被該傳感器節點探測到，并且假設此網格被任意節點覆蓋是獨立的，任意節點之間對目標的覆蓋互不干擾。總的覆蓋率R 可以表示為：

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

其中，n 為點亮的傳感器節點數，N 為總的節點數。

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

圖2 混合感知模型的網格化

4 人工免疫多目標算法

4.1 人工免疫算法

使用免疫算法解決多目標優化問題，從高度抽象的角度來看，在邏輯上生物免疫系統與免疫多目標優化的映射關系如表1所示：

表1 生物免疫系統與免疫多目標優化的映射關系

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

4.2 CCSMOA算法

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

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

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

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

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

圖3 CCSMOA算法流程圖

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

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

（2）抗體濃度的更新

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

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

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

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

隨后對克隆后的抗體群實施交叉和變異操作。交叉操作采用模擬二進制交叉，它的數學描述為：

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

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

變異操作采用由Deb提出的多項式變異[10]。多項式變異是目前多目標優化算法中常用的一種變異方法，它的數學描述是：

其中β 的數學描述為：

5 仿真及結果分析

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

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

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

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

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

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

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

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

6 結束語

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

[1] 王震,陳云芳. 基于人工免疫的多目標優化研究綜述[J]. 計算機應用研究, 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] 雷德明,嚴新平. 多目標智能優化算法及其應用[M]. 北京: 科學出版社, 2009.

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

[7] 焦李成,尚榮華. 多目標優化免疫算法、理論和應用[M]. 北京: 科學出版社, 2010.

[8] 曾廣樸,仲元昌,范會聯. 混合無線傳感網絡覆蓋優化的粒子群算法[J]. 微電子學與計算機, 2011(8): 105-107.

[9] 崔遜學. 多目標進化算法及其應用[M]. 北京: 國防工業出版社, 2006.

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

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