氣味標記法優化免疫算法的覆蓋策略*

郭凱東，馮秀芳

（太原理工大學計算機科學與技術學院，太原030024）

氣味標記法優化免疫算法的覆蓋策略*

郭凱東，馮秀芳*

（太原理工大學計算機科學與技術學院，太原030024）

覆蓋問題一直是無線多媒體傳感器網絡研究的重點領域。為了能夠達到對目標區域有效覆蓋的同時，減少網絡能耗，延長網絡壽命的目的，提出了一種氣味標記法優化的免疫算法SMOIA（Scent Marking Optimization Immune Algorithm）。該方法利用改進的氣味標記算法，在被覆蓋區域設置必要的氣味標記點，在這些點設置傳感器節點能夠有效提高對目標區域的覆蓋率，減少冗余節點數量；使用免疫算法來避免一般算法容易陷入局部最優的問題。仿真實驗表明，該算法能夠有效提高網絡覆蓋率，減少網絡中傳感器節點數量，延長了網絡壽命，并且收斂迅速。

無線多媒體傳感器網絡；免疫算法；氣味標記算法；覆蓋策略

隨著現代科技的發展，無線多媒體傳感器網絡WMSN（Wireless Multimedia Sensor Networks）由于其所具備的多媒體特性，能夠將所捕獲的環境信息以音視頻等多種形式呈現出來，使人們能夠直觀的感受到周圍環境的狀態，定量分析環境中的各種因素，從而被廣泛運用于交通監控、醫療衛生、戰場監測、災難預警等諸多領域［1］。例如在森林防火中，傳感器網絡能夠有效記錄林場環境，一旦出現突發情況，便能夠及時提醒相關人員采取措施。又如在戰場監測中，能夠通過邊界地帶部署的傳感器節點監測敵方動向，為指揮者制定軍事行動計劃提供有效的參考情報。

1　相關研究

在對WMSN的研究中，覆蓋問題又是其研究的重要內容之一。在文獻［2，4］中，提出了一種基于重疊感知率的覆蓋增強算法，通過相機傳感器節點的自我調整來減少重疊覆蓋區域，提高了覆蓋率，但算法復雜度過大。文獻［3］采用了一種基于二進小波變換的覆蓋算法，將覆蓋優化問題轉化為了離散信號模型，利用小波模極大值理論來求解信號極值點，從而尋求最優覆蓋方案。文獻［5］提出了一種集中式貪心算法，通過增加網絡中冗余節點的數量來提高覆蓋率，但增加了網絡能耗，縮短了網絡壽命。

上述覆蓋算法大多采用隨機部署傳感器節點的方式，難以克服隨機部署帶來的不確定性；同時，當一些參數選擇較大時，會使得計算過程復雜而漫長，給計算工作帶來不小的負擔。為了解決這些問題，受到生物學的啟發，將遺傳算法、魚群算法、免疫算法等運用到解決WMSN中的覆蓋問題時，體現出了較好的效果。文獻［6］利用動物通過氣味標記自己領土行為的特點，提出了多目標領土捕食者氣味標記算法 MOTPSMA（Multi-Objective Territorial Predator Scent Marking Algorithm），通過在氣味標記點部署傳感器實現對目標區域的監測，以達到最大覆蓋率和最小網絡能量消耗的目的，但算法收斂速度慢。文獻［7］給出了螢火蟲算法的改進策略，使得改進后的算法以概率1收斂于全局最優解。基于此，提出了一種覆蓋優化算法，能夠有效的給出網絡優化覆蓋方案。文獻［8］根據遺傳算法的特點，采用了一種新的歸一化方法，通過使用蒙特卡羅方法來設計一個評估函數，在減少計算復雜度和隨機部署的傳感器節點數量的同時不會影響網絡覆蓋率，但該算法容易陷入局部最優。文獻［9］在網絡中使用可移動的傳感器節點，在節點被初始部署到網絡中之后，通過免疫算法優化部署方案，使節點移動到最佳位置，來提高目標區域的覆蓋率，但網絡能耗增加明顯。

本文采用布爾感知模型，將SMOIA算法應用到WMSN的覆蓋優化問題中，通過利用免疫算法不容易陷入局部最優，可求解多目標優化問題［10］等的特點，結合了氣味標記算法SMA（Scent Marking Algorithm）優先考慮關鍵節點的優勢，來尋找網絡中最優的目標區域覆蓋方案，在保證算法效率與覆蓋率的同時，能夠確保消耗盡可能少的網絡能量，以延長網絡壽命，節約成本。

2　模型建立

我們將目標區域劃定在一個二維坐標平面內，在該平面內部署若干個傳感器節點，采用布爾感知模型模擬傳感器探測過程。

2.1布爾感知模型

設傳感器節點為s，感知半徑為r，感知角度為θ，目標區域為A，目標區域內任意一點為c，c與s的歐式距離為d（如圖1所示）。則布爾感知模型描述如下：

其中，P（c）為傳感器s感知c的概率。即若目標進入傳感器感知區域，則必將被識別；否則，無法識別。

圖1　布爾感知模型

2.2傳感器覆蓋模型

本文中所采用的傳感器為可旋轉傳感器，故該傳感器能夠感知一個圓形區域，如圖1中虛線圓所示。當有目標c進入目標區域時，傳感器s可通過調整朝向對目標c進行監測。

設在目標區域A部署的n個傳感器集合為S= ｛s1，s2，…，si，…，sn｝，由傳感器si的感知半徑ri圍成的區域為，則傳感器集合S所覆蓋區域為：

而未被傳感器覆蓋到的盲區為：

理想狀態下，我們希望使得：

同時使得GS中的重疊區域（如圖2所示）：

圖2　目標區域覆蓋模型

在實際情況中，由于受到環境、成本、設備等因素的影響，很難達到理想狀態，但為了實現對目標區域的有效覆蓋，至少可以使得

同時使

其中ξ、φ為給定的閾值，Gols為重疊覆蓋面積。

3SMOIA算法

在自然界中，獅子、老虎、狼等食肉動物習慣用氣味標記自己的領地范圍［6］。SMOIA算法受到了該行為的啟發，在目標區域設置一些氣味標記點，用以標記監控區域。這些點能否被覆蓋直接影響著整個目標區域的覆蓋率以及重疊覆蓋率。

免疫算法IA（Immune Algorithm）是模仿免疫系統抗原識別、抗原與抗體結合及抗體產生過程，并利用免疫系統多樣性和記憶機理抽象得到的一種算法［11］。免疫算法獨有的區別與其他算法的免疫記憶、疫苗接種、克隆選擇等特性，使得其能夠產生陰性選擇算法［11］、克隆選擇算法［11］等優良的衍生算法，對各個領域都有深遠影響。

故此，我們利用IA算法善于求解多目標［12］問題以及使得求解過程避免陷入局部最優的特點，來改進優化SMA算法，解決了其求解過程復雜、收斂速度慢等問題，形成了本文提出SMOIA算法。

3.1免疫算法

我們利用免疫算法來尋找一組傳感器節點的合適坐標，使得這組傳感器集合能盡可能多的覆蓋到目標區域，同時所用到的傳感器數量最少，也就是說能夠達到式（6）和式（7）的目標。定義目標函數如下：

其中，σ為大于0的常數，Gols′、GΩ′分別表示目標區域的重疊覆蓋率以及未覆蓋率。則在免疫算法中抗體與抗原的親和力函數為：

從式（9）可以看出，重疊覆蓋率和未覆蓋率最小的一組傳感器節點的集合就是我們所求問題的解。

這里，我們采用比較坐標點之間的歐氏距離來計算抗體與抗體之間的親和力。該方法通過逐一比較兩個抗體中傳感器坐標點之間的歐氏距離來判斷兩抗體之間的相似度，當坐標點之間的歐氏距離小于給定閾值χ，并且數量達到一定值 μ時，便可以認為這兩個抗體是相似的。我們可通過如下公式來計算抗體之間的親和力：

其中，fi，j表示抗體i與抗體j之間的親和力，num表示計算兩抗體中相似坐標數量的函數，ρ表示兩抗體中傳感器節點之間的歐氏距離。當親和力 fi，j＞μ時，就可以認為抗體 i與抗體j是相似的。此時所得到的兩組傳感器節點的集合在目標區域內有相似的覆蓋率、重疊覆蓋率以及未覆蓋率。由此，可以引出抗體濃度，即群體中相似抗體所占的比例的計算公式：

在免疫算法中，希望適應度高的個體被保留下來，同時，要抑制濃度過高抗體的繁殖，這樣做即保證了種群中優勢個體的數量，又保證了種群多樣性，這也是免疫算法的優良特性之一。為了能夠尋找到在目標區域具有最佳覆蓋率的傳感器集合，我們給出如下計算方法為：

其中，β為一給定常數。該方法在抑制高濃度抗體的同時，有可能也使得與抗原親和度高的抗體受到抑制，從而導致最優傳感器覆蓋集合丟失的情況發生。為了避免類似狀況，在每次更新記憶庫的時候，總會將優勢個體存入記憶庫，以保留最優傳感器覆蓋集合。

3.2氣味標記算法

自然環境中，動物往往在自己領地范圍內根據地形、樹木、河流等因素判斷應該在什么樣的位置留下氣味來標記自己的領土范圍。我們在坐標平面C內也要尋求這樣一個位置，稱為標記位置ML （Mark Location）。將目標區域設定在一個二維坐標平面C=｛（x，y）|0≤x≤lx，0≤y≤ly｝內，其中lx、ly分別表示目標區域在x、y方向上的最大長度，以（xml，yml）表示標記位置。

假設在坐標平面C內，對于?（x，y）∈C，若該點上存在傳感器節點s，則記為（xs，ys），被該點的傳感器s所覆蓋的區域為 fs（x，y）。那么，對于傳感器節點集合S來說，其中的每一個傳感器節點si所覆蓋的區域為 fsi（x，y），未被任何傳感器節點覆蓋的盲區為 fbi（x，y），?bi∈B，B為盲區組成的集合。則標記位置便是滿足如下定義的一個坐標點：

定義1設?（x，y）∈C，?（xmli，ymli）為氣味標記點，當且僅當（1）（xmli，ymli）∈fbi（x，y）；（2）（xsi，ysi）］-ρ［（xmli，ymli），（xsj，ysj）］/n＜γ，其中 ρ代表ML與相鄰傳感器節點si之間的歐氏距離，γ為給定閾值。

我們可以直接在標記位置放置一個新的傳感器節點，但這樣會增加網絡中傳感器數量，相應的也會增加能耗，提升成本。特別是在網絡中有較多傳感器重疊覆蓋時，新節點的加入只能增加網絡負擔，無益于網絡優化。這時，一個可行的方案是將重疊覆蓋的節點移動到標記位置，這樣既可將網絡規模控制在合理范圍內，又可充分利用資源。下面我們給出劣勢節點DN（Disadvantages Node）的定義：

定義2劣勢節點（xdni，ydni）是指部署在目標區域，其坐標位置滿足如下條件的點：（1）?（xsi，ysi）∈C 使 得ρ（xdni，ydni），（xsi，ysi）＜2*r；（2） ols（xdni，ydni）＞ols（xdnj，ydnj），其中ols代表該點與滿足條件（1）的節點的重疊覆蓋面積。

在定義1、定義2的基礎上，將氣味標記算法描述如下：

3.3SMOIA算法流程

SMOIA算法的主要步驟描述如下：

①從記憶庫中選擇M個個體與隨機產生的N個個體共同構成初始抗體群；若記憶庫為空，則隨機產生M個個體。

②根據目標函數f對所產生的抗體群中的每個抗體進行評價。

③對產生的初始抗體群的每個抗體按照目標函數f降序排列，并且取前N個構成父群體，前m個存入記憶庫。

④判斷是否滿足結束條件，若滿足，則執行步驟（7）；否則，進行下一步操作。

⑤對步驟③所產生的結果進行選擇、交叉、變異操作，從而得到新的群體，同時從記憶庫中選擇優良個體，與上述操作形成的群體共同構成下一代群體。

⑥執行步驟②。

⑦利用氣味標記算法對結果進行優化。

流程圖如圖3所示。

圖3　SMOIA算法流程圖

4　仿真實驗

為了檢驗算法性能及有效性，在Matlab中模擬在100 m×100 m的區域內部署傳感半徑為r=10 m 的60個傳感器節點，設置種群規模為60，交叉概率0.6，變異概率0.3，最大迭代次數為100次，其覆蓋結果如圖4所示。

圖4　覆蓋結果

從圖4的分段覆蓋結果中可以看出，經過SMOIA算法優化的傳感器節點覆蓋方案取得了較為理想的結果，傳感器節點分布比較均勻，重疊覆蓋區域和盲區都較少。圖5展示了SMOIA算法與IA算法、MOTPSMA算法的收斂速度比較結果，可以明顯看到SMOIA算法的收斂速度較快，在迭代56次之后便趨于穩定，而MOTPSMA算法需要迭代75次之后才能穩定，IA算法則在100次迭代完成之后仍然不能達到最優值。

圖5　收斂曲線

在仿真實驗中，我們將SMOIA算法與隨機部署、IA算法、MOTPSMA算法分別在保持上述條件不變，只改變傳感器感知半徑為r=5 m、r=10 m、r= 15 m、r=20 m、r=25 m的情況下，在覆蓋率方面做了比較，結果如圖6所示。

圖6　感知半徑與覆蓋率的關系

從圖6中可以看出，本文所提出的SMOIA算法在保持其他條件不變，只改變傳感器感知半徑r的情況下，在覆蓋率方面要優于其他三種算法。當感知半徑r=20 m時，覆蓋率為98.95%；而感知半徑r=25 m時，覆蓋率已達到99.81%。同樣，我們在只改變傳感器節點數量為n=30、n=40、n=50、n=60、n=70的同時，保持其他條件不變，仍然在覆蓋率方面做了比較，結果如圖7所示。從圖7中看到，SMOIA算法要優于其余算法，在傳感器數量達到70個時，覆蓋率為97.37%，覆蓋效果較好。

圖7　節點數量與覆蓋率的關系

5　總結

覆蓋問題是WMSN中的經典研究項目。本文提出了一種SMOIA算法，該算法利用了SMA算法模擬動物利用氣味標記劃分領地范圍的行為，融合了IA算法在保證解的多樣性的同時，不容易陷入局部最優的特點，期望能夠優化傳感器節點在目標區域的覆蓋，在不降低目標區域覆蓋率的情況下，以達到減少重疊區域、盲區以及網絡能耗的目的。

從仿真實驗結果來看，經過SMOIA算法調整的傳感器節點在目標區域都有較高的覆蓋率，且算法收斂速度較快。

［1］張蕾.無線傳感器網絡中多重覆蓋算法的研究［J］.傳感技術學報，2014，27（6）：802-806.

［2］Yang Chao，Zhu Weiping，Liu Jia，et al.Self-Orienting the Cameras for Maximizing the View-Coverage Ratio in Camera Sensor Networks［J］.Pervasive and Mobile Computing，2015，17：102-121.

［3］蔣敏蘭，陸鑫潮.一種新型的無線傳感器網絡覆蓋算法［J］.傳感技術學報，2012，25（8）：1112-1115.

［4］Chen Jian，Zhang Lu，Kuo Yonghong.Coverage-Enhancing Algorithm Based on Overlap-Sense Ratio in Wireless Multimedia Sensor Networks［J］.IEEE Sensors Journal，2013，13（6）：2077-2083.

［5］Costa Daniel G，Silva Ivanovitch，Guedes Luiz Affonso，et al.Enhancing Redundancy in Wireless Visual、Sensor Networks for Target Coverage［C］.//WebMedia 2014-Proceedings of the 20th Brazilian Symposium on Multimedia and the Web.Joao Pessoa，Brazil：Association for Computing Machinery，Inc，2014：31-38.

［6］Abidin H.Zainol，Din N.M.，Yassin I.M.，et al.Sensor Node Placement in Wireless Sensor Network Using Multi-objective Territorial Predator Scent Marking Algorithm［J］.Arabian Journal for Science and Engineering，2014，39（8）：6317-6325.

［7］劉洲洲，王福豹，張克旺，等.基于改進螢火蟲優化算法的WSN覆蓋優化分析［J］.傳感技術學報，2013，26（5）：675-682.

［8］Yoon Yourim，Kim Yong-Hyuk.An Efficient Genetic Algorithm for Maximum Coverage Deployment in Wireless Sensor Networks ［J］.IEEE Transactions on Cybernetics，2013，43（5）：1473-1483.

［9］Abo-Zahhad Mohammed，Ahmed Sabah M，Sabor Nabil，et al. Coverage Maximization in Mobile Wireless Sensor Networks Uti-lizing Immune Node Deployment Algorithm［C］//Canadian Conference on Electrical and Computer Engineering.Toronto，ON，Canada：nstitute of Electrical and Electronics Engineers Inc，2014.

［10］戚玉濤，劉芳，劉靜樂，等.基于免疫算法和EDA的混合多目標優化算法［J］.軟件學報，2013，24（10）：2251-2266.

［11］高彬彬，楊孔雨.免疫算法研究［J］.計算機技術與發展，2009，19（7）：249-252.

［12］Hu Zhi-Hua.A multiobjective immune algorithm based on a multiple-affinity model［J］.European Journal of Operational Research，2010，202（1）：60-72.

郭凱東（1990-），男，太原理工大學碩士研究生，主要研究方向為無線多媒體傳感器網絡，1215841370@qq.com；

馮秀芳（1966-），女，太原理工大學，教授，碩士生導師，主要研究方向為無線傳感器網絡，人工智能，feng_xf2008@126.com。

Coverage Strategy of Scent Marking Optimization Immune Algorithm*

GUO Kaidong，FENG Xiufang*
（College of Computer Science and Technology，Taiyuan University of Technology，Taiyuan 030024，China）

The coverage problem has been the focus of research in wireless multimedia sensor networks.In order to improve the efficiency of coverage in networks，meanwhile，to reduce energy consumption and prolong the network lifetime，a novel of Scent Marking Optimization Immune Algorithm（SMOIA）was proposed.The method uses an improved Scent Marking Algorithm，set the necessary scent marking points in the area.To set the sensor nodes at these points can improve the coverage of the target area effectively，reducing the number of redundant nodes.The immune algorithm can use to avoid the problem that the general algorithm is easy to fall into local optimization.Simulation results show that the algorithm can improve the coverage ratio effectively，reduce the number of sensors in networks，prolong the network lifetime and converges rapidly.

wireless multimedia sensor network；immune algorithm；scent marking algorithm；coverage strategy

TP393

A

1004-1699（2016）08-1267-06

EEACC：723010.3969/j.issn.1004-1699.2016.08.024

項目來源：國家自然科學基金面上項目（61472272）；山西省科技基礎條件平臺建設項目（2015091003-0103）；山西省回國留學人科研資助項目（2013-049）

2015-12-14修改日期：2016-03-25