基于免疫克隆多目標優化的WSN覆蓋控制研究

楊震 陳立萬 劉莎 劉子路

摘要：無線傳感器網絡在應用到大規模區域監測時，重點需要解決網絡最優覆蓋問題。對此本文提出一種基于免疫克隆多目標優化算法，該算法引入人工免疫原理，把多個約束條件轉化成一個約束目標，進而將實際中的復雜問題轉化成單目標優化問題，提高了網絡的覆蓋率。實驗結果表明，該免疫克隆多目標優化算法可以更好地改善網絡覆，有效實現無線傳感網絡的覆蓋優化。

關鍵詞：無線傳感器網絡；覆蓋率；免疫克隆；多目標優化；節點利用率

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）28-0172-04

Research on WSN Coverage Control Based on Multi-Objective Optimization of Immune Clone

YANG Zhen， CHEN Li-wan*， LIU Sha， LIU Zi-lu

（School of Electronics and Information Engineering， Chongqing Three Gorges University， Chongqing 404100，China）

Abstract：Wireless sensor network can be applied to the large-scale regional monitoring， solve the problem of network optimal covered. This paper presents a multi-objective optimization algorithm based on immune clone. Artificial immune principle， introduced the algorithm， the multiple constraints into a binding targets， and then turn the problem into a two objective optimization problem. The multi-objective optimization combined with immune clone algorithm， improve the network coverage of coverage. The experimental results show that the immune clone multi-objective optimization algorithm can better improve network， wireless sensor network coverage optimization effectively.

Key words： wireless sensor networks； coverage rate； immune clone； multi objective optimization； node utilization ratio

無線傳感器網絡依靠其易組網、耗能低、器件廉價等優勢，被廣泛應用到國防軍事、民生等大規模區域監測。而其網絡最優覆蓋一直是專家學者們研究熱點。在網絡最優覆蓋范圍內，覆蓋控制是一個基礎研究課題[1]。通過覆蓋控制，可以了解是否存在檢測和通信的盲點，并掌握監控區域的網絡覆蓋[2，3]。然后重新調整傳感器節點的分布[4，5]以獲得更好的覆蓋。通過調整傳感器節點的分布，提高網絡覆蓋的密度，設置受監視區域的熱點以及部署更多傳感器節點以確保測量數據的可靠性。因此，在保證無線傳感器網絡數據傳輸可靠性的前提下，網絡覆蓋最大化已成為一個重要研究課題。

許多學者把多目標優化技術引入到覆蓋控制中解決網絡覆蓋問題的方法中。多目標優化技術通常采用更成熟的單目標優化[6]技術將復雜的多目標問題轉化為單目標優化問題。實踐中，一些多目標優化問題[7]主要是復雜的非線性問題，使用這種方法通常會導致諸如非收斂或收斂速度不理想等情況。因此，標準粒子群優化算法、遺傳算法等進化多目標優化算法，如MOGA，NSGA，OAES等這種啟發式搜索策略[8]被用來解決復雜網絡的多目標優化問題。雖然這些算法取得了重要的突破，但是也存在一些缺陷與不足，例如 SPEA-Ⅱ[9]的收斂時間較長，NSGA-II[10]的多樣性差，PAES在這兩個方面都不理想。將多目標優化技術與人工免疫相結合可以改善傳統演化算法的缺陷和不足。人工免疫系統[11]是一種受生物免疫系統啟發，模仿自然免疫系統功能的智能方法。通過學習天然材料天然防御機制的學習技術，提供自組織和記憶等進化學習機制，同時結合分類器、機器推理和其他系統的一些優點，使得免疫算法[12-14]具有搜索效率高，避免早熟收斂，群優化和多樣性維護等優點。

基于免疫克隆多目標優化的WSN覆蓋控制可運用多目標進化算法模擬人工免疫系統而實現，其進化過程與傳統的抗體的適應度值進行克隆選擇方法有所不同，首先將抗體劃分為支配抗體與非支配抗體，然后選擇出非支配抗體，在克隆選擇后，采用抗體群更新操作，把比較密集區域的解刪除，從而使抗體群控制在一定規模之內，在網絡穩定情況下，保持所得解均勻同時保證算法的收斂，達到網絡最優覆蓋。

1 覆蓋模型

1.1 覆蓋區域

無線傳感器網絡的簡單覆蓋模型[15]。假設一個面積為[A]的監控區域，每個傳感器節點可以監測的區域為圓形面積，其半徑感知距離為[R]，所有傳感器節點相互獨立地進行工作，如圖1所示。

不考慮節點落入邊界區域造成覆蓋面積的減小，節點所感知的區域面積為[πR2]，傳感器監控整個區域的概率為[P=πR2/A]，每個節點的覆蓋概率為：

[P（A）=P] （1）

任意兩傳感器節點監測的覆蓋概率為：

[P（A+A）=P（A）+P（A）-P（A）P（A）=2P-P2=1-（1-P）2] （2）

任意三個傳感器節點監測的覆蓋概率為：

[P（A+A+A）=P（A+A）+P（A+A）P（A）=1-（1-P）2+P-[1-（1-P）2]P=1-（1-P）3] （3）

則[n]個節點的覆蓋概率為：

[P（A+A+…+A）=1-（1-P）n] （4）

為保證以概率[P]實時監測某傳感器感知半徑為[R]，面積為[A]的區域，隨機投放傳感器節點的數量為：

[n>lg（1-p）/lg（1-πR2A）] （5）

設矩形[A]表示被監測區域，矩形[B]表示監測外的區域，[a]、[b]、[c]、分別表示三個節點，其中[a]、[b]兩個節點隨機布置在邊界區域的示意，如圖2所示。

某些節點隨機布置在邊界區域，其覆蓋概率小于[P]，實際隨機布置的節點個數[n]應滿足：

[n>lg（1-p）/lg（1-πR2A）] （6）

區域[A]外節點感知面積為[B]，則[n]應滿足：

[lg（1-P）lg（1-πR2A）

1.2 性能分析

1） 覆蓋率

覆蓋率[16]作為衡量傳感器節點覆蓋范圍的度量，為目標區域全部傳感器節點的覆蓋面積的并集與全部傳感器節點的個體覆蓋面積之和的比值，即[P=πR2/A]。

2） 節點利用率

在保證覆蓋率的條件下，調度不同位置和數量的傳感器節點可以使能量的利用率[17]更加有效。感知過程中，無線傳感網絡在不激活全部節點的情況下實現高覆蓋率。工作的傳感器節點數[k]與網絡中其它節點之間距離倒數之和的平均值為節點利用率[Ik]。因此將[Ik]定義如下：

[Ik=1n-1i=1，i≠kn1ΔXij] （8）

[ΔXij]表示節點間的距離。

3） 節點感知半徑

節點間通過通信網絡組成傳感器網絡[18]，共同協作感知并采集環境或物體的準確信息，感知網絡運行環境的高度動態性和大規模部署的特點。傳感器節點具有自組織、自配置、自協調等自適應能力[19]，因此節點感知半徑[R]對網絡覆蓋具有重要意義。

2 免疫克隆多目標算法

2.1 免疫邏輯映射

為利用免疫算法解決多目標優化問題，生物免疫系統與免疫克隆多目標優化在邏輯上的對應關系如表1所示：

抗體識別抗原與線性規劃求最優解類似，抗原對應多目標優化的問題，即用抗原定義覆蓋率和節點利用率；抗體定義為多目標優化的候選解，等效為傳感器節點的二進制代碼；抗原親和度可認為抗體的識別，對應表示為不同數目與不同位置的傳感器節點，覆蓋率與節點利用率之間的函數關系。

在基于免疫克隆的多目標優化算法中，考慮到抗體-抗原親和力和抗體-抗體親和力的影響，每代抗體的克隆數與更新抗體濃度相關，將抗體的濃度計算轉換成關于抗體-抗原親和力和抗體-抗體親和力函數的關系，由此確保算法的優異性能。

2.2 克隆多目標算法

克隆多目標算法求解優化問題時，滿足約束條件的最優解為抗原，候選解是抗體。親和力表示抗原和抗體之間的匹配程度，斥力表示抗體之間的相似程度。

克隆多目標算法流程圖步驟如下：

1） 首先對參數進行初始化并初始化抗體群[M]，即分析問題的可行性，提取先驗知識，構造適當的親和函數，并制定各種約束條件。

2） 然后將抗體組[M（2）]與[M]組合以計算抗體-抗原親和力和抗體-抗體親和力，并更新外部抗體組[M']。

3） 根據濃度對克隆[M]中的抗體，產生抗體組[M（1）]。

4） 對[M（1）]進行克隆和基因操作，產生抗體群[M（2）]。

5） 把抗體群[M]與[M（2）]組合并計算其抗體-抗原親和力和抗體-抗體親和力。

6） 選取合適的抗體形成下一代。

7） 判斷是否滿足最大迭代次數，滿足則輸出計算結果[M]，否則回到第二步重復上述流程。

免疫克隆多目標優化算法流程圖如圖3所示：

2.3 親和力計算

抗體—抗原親和力的計算如（9）式所示。

[fAyi=fSPEA2（2）] （9）

其中，[fAyi]表示抗體[i]的抗體—抗原親和力，[fSPEA2（i）]表示抗體[i]在SPEA2算法中的抗體—抗原親和力。[fAyi]的值越小，抗體與抗原的匹配程度越高，密度越小，抗體越好。

（10）式所示為抗體[i]與歐氏距離不大于閾值[σs]的抗體間相似程度函數，用[ftyi（t）]表示。

[fAxi（t）=g∈GCgt[σs-d（i，g）]/g∈GCgt，ifG??∧d（i，j）<σs）0，其他]

（10）

[fAxi（t）]表示抗體[i]在第[t]代時抗體—抗體親和力，[G]表示歐氏距離不大于[σs]的抗體集合，[Cgt]表示抗體[g]在第[t]代的濃度，[d（i，g）]表示抗體[i]和抗體[g]之間歐式距離。

2.4 抗體濃度更新

抗體-抗原親和力和抗體-抗體親和力決定抗體濃度，同時抗體濃度又影響抗體克隆次數。因此，定義抗體濃度的更新為上一代抗體濃度和抗體-抗原的親和力函數，函數公式如下所示：

[Cit+1=min[αCit-fAxt（t），1]0，ifαCit（t）≥0，其他] （11）

其中，[Cit+1]和[Cit]的范圍是[[0，1]]，分別表示抗體[i]的新舊濃度。[α]為抗體濃度所占的比重的比例系數，計算公式如下所示：

[α=1+βfAy'i（t），iffAxi（t）=0∧β∈[0.1，0.5]0，iffAxi（t）=0∧γ∈[0.5，0.9]] （12）

其中，[fAyi（t）=1-fAyi（t）]，[fAyi（t）]是歸一化處理后的原始抗體—抗原親和力，且[fAyi（t）∈[0，1]]，這種轉化是因為抗體具有高比例的系數。

2.5 克隆基因操作與外部記憶抗體群更新

濃度為[Cit]的抗體[i]的克隆倍數為：

[Nit=nmin+|（nmax-nmin）Cit|] （13）

[nmax]表示抗體克隆倍數最大值，[nmin]表示最小值。

克隆抗體群進行二進制交叉與變異操作：

[x'1=0.5（1+ε）x1+（1-ε）x2] （14）

[x'2=0.5（1+ε）x1+（1-ε）x2] （15）

其中，[ε]的數學描述為：

[ε=（2λ）1μ+1，λ≤0.5（12（1-λ））1μ+1，λ>0.5] （16）

其中，[ε1=χk-lkuk-lk]，[η1=uk-χkuk-lk]，[λ]與[u]為[[0，1]]產生的隨機數，[μ]是分布指數。

3 仿真分析

3.1 覆蓋率與節點利用率的關系

假設邊長[100×100]的矩形檢測區域布置600個無線傳感器節點。傳感器節點的感知半徑全部設置為[r=3m]，通信半徑[c=2r=6m]，概率測量模型參數[c1=c2=1]，測量可靠性參數[re=0.5r=1.25m]，[α1=1]，[α2=0]，[β1=1]，[β2=0.5]，最大迭代次數400次。利用MATLAB2014a仿真工具進行模擬實驗，初始化節點布局，圖4（a）、（b）為粒子群仿真節點布局和免疫克隆多目標優化后的節點布局，通過與粒子群算法對比的仿真結果如5所示。

由圖5可以看出，粒子群算法和免疫多目標算法都能達到較好的覆蓋，但在節點利用率相同情況下免疫多目標算法的覆蓋率要優于粒子群算法的覆蓋率，且覆蓋率大于90%時區分的比較明顯，多目標免疫算法的曲線比粒子群算法的平滑，分布更均勻。

3.2 覆蓋率與節點感知半徑的關系

在設定的檢測區域的仿真環境下，粒子數設置為1500個，在前面假定的仿真環境下，只改變節點的感知半徑[r]，其他參數不變，分析節點感知半徑的變化對覆蓋性能的影響。免疫多目標算法的節點感知半徑對覆蓋性能的影響如圖6所示。

由圖6可知，感知半徑為5.5時，覆蓋率100%，當感知半徑為1.5m時，覆蓋率為32.14%；半徑為2m時，覆蓋率為54.39%；半徑為2.5m時，覆蓋率為76.35%，增幅約22%。由此可以看出，半徑為1.5m-3m時曲線斜率相對較大。隨著感知半徑r變大，在3m-5m時，其曲線斜率減小，感知半徑在5.5m時，斜率最小，幾乎達到完全覆蓋。這表明感知半徑變大時，系統穩定性高，且覆蓋率隨增大。

4 結論

無線傳感器網絡的優化覆蓋控制可以提高網絡性能，提高網絡的有效覆蓋率。提出一種用于無線傳感器網絡布局優化的多目標優化免疫算法。引入人工免疫算法克隆，變異和選擇個體種群，將多目標優化與免疫克隆算法相結合。實現網絡的有效覆蓋作為優化目標，優化無線傳感器網絡節點利用率和感知半徑對覆蓋性能的影響。并利用粒子的強大全局搜索能力和免疫克隆局部搜索的能力來增加搜索范圍，使個體覆蓋更加高效，優化了算法的性能并提高了節點覆蓋率。仿真實驗表明，與其他算法相比，有效覆蓋率和收斂速度均有明顯提高。免疫克隆多目標優化算法可以更好地提高網絡覆蓋范圍，有效實現無線傳感器網絡的覆蓋優化。

參考文獻：

[1] 劉維亭， 范洲遠. 基于混沌粒子群算法的無線傳感器網絡覆蓋優化[J].計算機應用， 2011， 31（2）：338-341.

[2] 王田， 彭臻， 陳永紅. 異構無線傳感器網絡對移動目標的連續跟蹤[J].小型微型計算機系統， 2015， 36（3）：503-507.

[3] M HEFEEDA， H AHMADI. Energy -efficient protocol for deterministic and probabilistic coverage in sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems， 2010， 21（5）： 579-593.

[4] 武江華， 邵清. 基于免疫克隆選擇機制的WSN節點調度算法[J]. 計算機仿真， 2015， 32（4）：231-234.

[5] 汪宏海， 張正球. 基于免疫克隆優化算法的傳感器網絡資源分配[J]. 福建師范大學學報（自然科學版）， 2013， 29（5）：26-29.

[6] 方芳， 陳世平. 無線傳感器網絡中多目標優化節點部署模型[J]. 計算機應用研究， 2015， 32（4）：1166-1168.

[7] 謝宏， 李云峰， 禹文科. 改進免疫克隆選擇算法的多目標軌跡優化[J]. 電子測量與儀器學報， 2016，30（10）： 1534-1542.

[8] Y YOON， Y H KIM. An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks [J]. IEEE Transactions on Cybernetics， 2013， 43（5）： 2168-2267.

[9] 談恩民， 朱峰， 尚玉玲. 基于SPEA-II算法的SoC測試多目標優化研究[J]. 國外電子測量技術， 2015（8）：29-33.

[10] Chu X Y， Yang H X， Zhi-Feng W U. An Improved NSG-Ⅱfor Multi-objective Optimization of Truss Structures[J]. Science Technology & Engineering， 2015.

[11] 王嬌. 基于人工免疫算法的傳感器節點布置策略[J].電子測量技術， 2015（6）：97-99.

[12] 方琳琳， 陳擁軍. 基于免疫機制的無線傳感器網絡路由優化[J].計算機工程與應用， 2015， 51（15）：96-101.

[13] 劉軍. 基于虛擬力算法的WMSNs覆蓋研究[J].傳感器與微系統， 2016， 35（11）：74-76+83

[14] 杜振華， 諶海云， 曾歡. 多目標系統最優控制方法研究[J]. 航天控制， 2014， 32（5）：3-10.

[15] 范興剛， 徐俊超， 車志聰. 一種概率柵欄覆蓋模型及其構建算法[J]. 計算機研究與發展， 2017， 54（5）：969-978.

[16] 劉偉， 胡安林. 無線傳感器網絡覆蓋率與節能性研究[J]. 電子技術應用， 2016， 42（6）：98-100.

[17] 田新越， 李翔宇. 無線傳感器網絡節點任務調度與功耗管理算法研究[J]. 傳感器與微系統， 2016， 35（2）：9-11.

[18] 方如舉， 王建平， 孫偉. 無線傳感器網絡通信的擁塞控制策略[J]. 電子測量與儀器學報， 2016， 30（4）：558-567.

[19] 范雄男， 陳慶奎. WSN中基于可調感知半徑的節點睡眠算法[J]. 計算機工程， 2010， 36（19）：123-125.

[20] Takaoka A. AS-1-6 A Polynomial-Time Algorithm for a Variation of the 2-Chain Subgraph Cover Problem Related to the Recognition of Simple-Triangle Graphs[C]// IEICE Engineering Sciences Society/ nolta Society Conference. The Institute of Electronics， Information and Communication Engineers， 2016.

【通聯編輯：唐一東】