气味标记法优化免疫算法的覆盖策略*

郭凯东，冯秀芳

（太原理工大学计算机科学与技术学院，太原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