基于遗传算法的传感器优化部署方法研究*

陈升来，陆　宏，李　涛

（中国电子科技集团公司第二十八研究所，江苏 南京 210007）

基于遗传算法的传感器优化部署方法研究*

陈升来，陆宏，李涛

（中国电子科技集团公司第二十八研究所，江苏 南京 210007）

针对传感器优化部署问题，提出了基于遗传算法的传感器优化部署方法。以空间覆盖率、覆盖重数、资源利用率为评价指标，构建传感器优化部署模型，提出了基于遗传算法的传感器部署模型求解方法。仿真实验表明，提出的方法能够实现传感器优化部署，遗传算法经过迭代后，一般区域覆盖率达到了92%，重点区域覆盖率达到了99%。此外，与基于二进制编码的遗传算法相比，该方法具有算法收敛快、传感器资源利用率高等优点。

遗传算法；优化部署；混合编码；传感器网络

0　引 言

传感器组网是实施情报感知的基础。在网络中心战中，地理上分散的传感器通过有线或无线网络组成网络化探测系统，对作战目标进行协同感知和融合处理，生成实时或近实时情报信息，为作战部队、武器系统提供实时战场态势。

为发挥网络化探测系统整体效能，提高探测系统的检测概率，必须对有限的传感器资源进行优化部署及合理使用［1-2］，实现对战场空间的全方位探测。

由于受探测任务、探测效能、资源效费比等条件的约束，传感器部署成为一个复杂的非线性、多约束问题。本文从空间覆盖率、覆盖重数、资源利用率等方面研究传感器优化部署问题，建立传感器优化部署模型，提出基于遗传算法的最优求解方法，实现了部署模型的快速求解，并通过仿真实验实现了验证。

1　模型建立

在军事领域，根据重要性的不同，传感器探测区域分为一般区域和重点区域。前者侧重于目标监视，后者侧重于目标跟踪。由于目标监视和目标跟踪的侧重点不同，故对传感器探测提出了不同的要求：第一，为了达到警戒效果，要尽可能覆盖一般区域；第二，为了确保重点区域的目标都能被监视和跟踪，要完全覆盖重点区域；第三，为了提升重点区域目标跟踪效能和探测概率，要对重点区域实施多重覆盖；第四，为了提高传感器资源效费比，减少电磁辐射，参与探测的传感器数量要尽可能少，避免传感器过度冗余。

针对上述要求，利用一般区域覆盖率、覆盖重数、重点区域覆盖率、传感器资源利用率等指标建立传感器优化部署模型。

1.1一般区域覆盖率

一般区域覆盖率，定义为传感器覆盖区域总面积与一般区域面积的比值，即：

式中，Si为第i部传感器的探测区域，S为给定的一般区域，N为传感器总数，ρ∈［0,1］表示覆盖率。

1.2覆盖重数

覆盖重数说明传感器探测区域覆盖的重数。它与覆盖率并不矛盾，只是两者关注的侧重点不同。覆盖率关注的是目标区域整体的覆盖情况，而覆盖重数侧重于局部的重点观测情况［3］。

覆盖重数定义为：

一般来说，覆盖重数超过3时，不会明显增大传感器的联合探测概率。本文要求重点区域覆盖重数λarea≥2，一般区域的覆盖重数λ一般≥1。

1.3重点区域覆盖率

重点区域覆盖率是指二重覆盖条件下，传感器对重点区域的覆盖率，即：

式中，Sarea为重点区域，Sarea2为二重覆盖下传感器覆盖的区域，θ为重点区域的覆盖率；约束条件表示Sarea2区域至少为二重覆盖。

1.4传感器资源利用率

为了节约传感器资源，需要将传感器资源限制在感兴趣的区域内。

资源利用率定义为：

1.5传感器优化部署模型

利用式（1）～式（4）可以得出，传感器优化部署模型为：

式中q1、q2、q3为权重系数，且q1+q2+q3=1；C则为传感器部署优化效能。

2　基于遗传算法的模型求解

遗传算法（Genetic Algorithm）是一类借鉴生物界进化规律演化而来的随机优化搜索方法［4-5］。原理是通过生物选择、遗传和变异等操作，维持优秀基因并促使群体进化，从而获取最优解。目前，遗传算法已被广泛应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域［6］。

针对传感器优化部署这一复杂问题，对遗传算法的编码、选择、变异等方法进行改进，具体如下。

2.1编码

影响传感器i（i=1,2,…,N）覆盖范围的参数有：工作状态oi、传感器位置（xi, yi）、作用半径ri等。其中，ri属于传感器的固有特性，可以预先获知，不需要编码。

为了精确获取传感器部署位置，需选择混合编码的方法，即工作状态oi采用二进制编码，表示传感器开关机状态；传感器位置（xi, yi）采用实数编码。因此，一个基因包括三个分量Gk=（xi,yi,oi）；个体由N个基因组成，即I=（G1,G2,…GN）；种群P=｛I1,I2,…,Ik｝，其中K为种群大小。

2.2适应度函数

传感器优化部署模型的适应性函数定义如下：

2.3选择

为了实现快速收敛，本文采用精英选择和比例选择相结合的方法，即通过精英选择将群体中最优秀的个体不经选择环节直接进入下一代，而其余个体仍然通过比例选择法得到。

比例选择时，需要计算所有个体的适应度函数，以确定其被选择的概率和染色体累积概率。假设第k个个体的适应度为fk，则个体选择概率pk和染色体累积概率qk的计算方法为：

2.4交叉

针对混合编码方案，交叉方法如下：

（1）以一定的概率选择两个需要交叉的个体Ir、Is；

（2）在交叉个体中，随机选择两个需要交叉的基因Gm、Gn；

（3）对基因中的工作状态o采用单点交叉方法；对于基因中的x值采用算术交叉方法，即：

式中a为比例因子。

同理，y值通过相同的方法进行交叉。

2.5变异

变异操作类似于交叉操作，先是随机选择一个个体，然后以一定的突变概率选择基因，最后对基因进行变异。对工作状态o采用取反操作，对基因中的x值则采用如下的计算变异公式：

式（9）中，Lxmin为一般区域x方向的起点，Lxman为一般区域x方向的终点。

同样地，y值采用相同的方法进行变异。

3　仿真实验

假设由10个传感器组成的传感器网络对某作战区域进行探测。传感器作用距离为25 km；一般区域为100 km×100 km的方形区域；重点区域是以（60，60）为中心，大小为40 km×40 km的方形区域。

遗传算法的参数设置如下：初始种群大小为50；交叉概率为0.8；变异概率为0.15；模型权重系数q1=0.30，q2=0.50，q3=0.2。遗传算法停止迭代的条件是：一般区域覆盖率ρ≥90%，重点区域覆盖率θ≥99%，迭代次数小于50。随机选取个体初值，算法经过46次迭代后收敛，获取传感器的部署参数，如表1所示。从表1可知，只需开机8个传感器就能完成探测任务。一般区域和重点区域的覆盖情况如图1所示，其中一般区域覆盖率达到了92%，重点区域覆盖率达到了99%。可见，遗传算法能够很好地解算传感器部署问题。覆盖率随迭代次数变化的曲线，如图2所示。由图2可见，重点区域的覆盖率收敛较快，这是因为传感器优化部署模型中重点区域的覆盖率项被赋予了较大权值。

实验中，还采用基于二进制编码的遗传算法对传感器优化部署模型进行了解算，即组成基因的三个分量都使用二进制来表示，其中工作状态oi使用1位二进制码表示，传感器位置xi和yi分别使用16位二进制码表示，共同组成33位二进制编码串。随机设置个体初值，经过50次迭代后算法停止，获取传感器的部署参数，如表1所示。此时，9个传感器开机探测，一般区域覆盖率只达到了85.1%，重点区域覆盖率达到了95.3%。类似地，从图2看出，二进制编码的遗传算法与本文方法相比，收敛速度较慢。

表1　传感器部署情况

图1　传感器覆盖情况

图2　覆盖率变化曲线

4　结 语

传感器网络中，如何有效部署传感器成为传感器网络技术研究的一个重要方向。本文从覆盖率、覆盖重数、资源利用率等方面开展研究，建立了传感器网络优化部署模型，提出了一种改进的遗传算法，实现了模型的快速、有效解算。仿真实验表明，该模型不仅能够对重点区域进行重点探测，提高目标探测概率，而且能够有效利用传感器资源，从而为实际的传感器部署提供参考。

［1］ Ghosh A，Das S K.Review:Coverage and Connectivity Issues in Wireless Sensor Networks:A Survey［J］. Pervasive and Mobile Computing，2008，4（03）:303-334.

［2］ Dhillon S S，Chakrabarty K.Sensor Placemen for Effective coverage and Surveillance in Distributed Sensor Networks［C］.Proc of IEEE Wireless Communications and Networking conf，2003:1609-1614.

［3］ Huang C，Tseng Y.The Coverage Problem in a Wireless Sensor Network［C］.Proc of the 2nd ACM International Conference on Wireless Sensor Networks and Applications，2003:115-121.

［4］ 夏磊，俞能海.基于遗传算法的小卫星任务调度［J］.通信技术，2013，46（11）:64-68. XIA Lei，YU Neng-hai.Genetic Algorithm based Small Satellites Range Scheduling［J］.Communications Technology，2013，46（11）:64-68.

［5］ 狄海进，高璇.遗传模拟退火算法在多目标分配中的应用［J］.指挥信息系统与技术，2012，3（06）:22-24. DI Hai-jin，GAO Xuan.Application of Genetic Simulated Annealing Algorithm in Multi-target Assignment［J］.Command Information System and Technology，2012，3（06）:22-24.

［6］ 郑世明，苗壮，董磊.基于云遗传算法的防空火力优化分配［J］.指挥信息系统与技术，2011，2（01）:21-26. ZHENG Shi-ming，MIAO Zhuang，DONG Lei.Optimization of the Allocation of Targets of Air Defense based on Cloud-Model Genetic Algorithms［J］.Command Information System and Technology，2011，2（01）:21-26.

陈升来（1978—），男，博士，高级工程师，主要研究方向为总体技术、传感器网络控制技术；

陆 宏（1980—），女，本科，高级工程师，主要研究方向为传感器网络控制与仿真技术；

李 涛（1973—），男，博士，高级工程师，主要研究方向为传感器网络控制与数据融合技术。

Optimal Deployment Method of Sensors based on Genetic Algorithm

CHEN Sheng-lai， LU Hong， LI Tao
（The 28th Research Institute of China Electronics Technology Group Corporation， Nanjing Jiangsu 210007， China）

Optimal deployment method of sensors based on genetic algorithm is proposed， thus to solve the problem of sensors optimal deployment. With coverage ratio， resource utilization and coverage coefficient as the evaluation indexes， the optimal deployment model is established， and at the same time the solution to sensor deployment model based genetic algorithm designed. Simulation results indicate that the proposed method for optimal sensor network deployment is feasible and effective， with ordinary area coverage percentage reaching 92%， and the important area coverage percentage reaching 99% after genetic algorithm iteration. In addition， the proposed method is fairly high in convergence speed and sensor utilization ratio as compared with the traditional methods.

genetic algorithm； optimal deployment； hybrid encoding； sensor network

TP393.04

A

1002-0802（2016）-10-1360-04

10.3969/j.issn.1002-0802.2016.10.018

2016-06-07；

2016-09-23

data:2016-06-07；Revised data:2016-09-23