多目标进化算法在wsn的动态覆盖控制中应用.doc

摘要
多目标进化算法在WSN动态覆盖控制中的应用
摘要
随着无线传感器网络的广泛应用，关于无线传感器网络的问题，特别是无线传感器网络的动态覆盖的问题得到了越来越多的关注。研究如何规划传感器合理的激活方案，来使无线传感器网络既要达到合理的区域覆盖度，又尽可能的延长网络寿命已经成为研究的一个热点。本文以多目标进化算法在无线网络传感器网络动态覆盖中的应用为研究课题，首先概述无线传感器网络和无线传感器网络动态覆盖问题的基础知识，作为本文研究的理论基础；然后，以无线网络传感器网络的评价标准，即网络覆盖率和网络寿命，确定性部署和随机部署为依据构建无线传感器网络覆盖问题模型；在此基础上提出多目标遗传算法的概念、特点、关键技术和基本流程，并以此为依据对无线网络传感器网络动态覆盖问题进行算法设计，通过基于多目标遗传算法的无线传感器网络动态覆盖问题算法设计，实现无线传感器网络动态覆盖的最大优化。

关键词：无线传感器网络；动态覆盖；模型；多目标遗传算法

Abstract
MUITI-OBJECTIVE EVOLUTIONARY ALGORITHM IN WSN DYNAMIC OVERLAY
Abstract
With a wide range of issues related to the application of wireless sensor networks , wireless sensor networks , especially dynamic coverage problem in wireless sensor networks , namely, how to activate the program through rational planning sensor reaches a certain target area under the premise of coverage as possible the extension of the life of the network has become a hot research. In this paper, multi- target algorithm in wireless sensor networks dynamic overlay network for research , first outlined the basics of wireless sensor networks and wireless sensor networks dynamic coverage problem , as the theoretical basis for this study ; then to a wireless network sensor networks evaluation criteria, that is, network coverage and network lifetime , deterministic and stochastic deployment is based on the deployment of wireless sensor network coverage issue to build the model ; concept proposed multi-objective genetic algorithm based on this , characteristics, basic key technologies and processes, and to this is based on wireless sensor network dynamic network coverage problem for algorithm design, dynamic coverage problem algorithm design through pre- arranged opening sequence -based wireless sensor networks , wireless sensor networks to achieve maximum optimization of dynamic coverage.

Keywords : wireless sensor networks ; dynamic coverage ; model ; multi-objective Genetic Algorithms

目录
第1章 绪论 1
1.1无线传感器网络的研究背景 1
1.2无线传感器网络的研究目的及意义 2
1.3无线传感器网络的发展概况 2
1.4无线传感器网络覆盖控制问题概述 3
1.5本文主要研究目标及主要工作 3
1.6本文章节结构 4
第2章WSN网络覆盖模型分析 4
2.1无线传感器网络简介 5
2.2 WSN的动态覆盖问题 6
2.3 网络覆盖度的评价标准 6
2.4 传感器探测概率模型 8
2.5无线传感器网络覆盖的评价标准 9
2.5.1网络覆盖度 9
2.5.2网络寿命 10
2.5.3延长网络寿命和有限时间段内节能的关系 10
第3章 多目标进化算法分析 12
3.1多目标进化算法简介 13
3.1.1多目标进化算法概念及特点 13
3.1.2多目标进化算法的通用算法过程及优缺点 13
3.2 各类多目标进化算法分析 14
3.2.1 分布式启发式算法 14
3.2.2多目标差分进化算法 16
3.2.3多目标粒子群优化算法 18
3.2.4多目标遗传算法 21
第4章 基于多目标进化算法的WSN动态覆盖问题算法实现 25
4.1多目标遗传算法简介 25
4.1.1多目标遗传算法概念及特点 25
4.1.2多目标遗传算法关键技术 26
4.1.3多目标遗传算法基本流程 26
4.2算法设计 27
4.3 仿真结果分析 31
4.3.1仿真环境及参数设定 31
4.3.2仿真结果分析 33
第5章 总结与展望 35
第6章 致谢 37
参考文献 39

I

第1章 绪论
第1章 绪论
无线传感器网络凭借它的广阔应用前景而受到外界广泛关注,无线传感器网络指的是那些工作在没有人值守的地方，它消耗的能量很少，但是能源的限制能制约网络覆盖度及传感器工作的时间，传感器工作的时间又可称为网络寿命，从而我们知道了无线传感器网络的网络覆盖度和网络寿命这两个评价标准。从目前的研究前景来看，无线传感器网络的动态覆盖问题中的核心就是对传感器组成网络进行合理的布局规划，来使无线传感器网络能在不同的场合都能达到在一定的网络覆盖度前提下，尽可能的延长网络寿命。
采用何种方法来优化网络覆盖度以及网络寿命成为我们研究的核心，在现实生活中，很多的优化问题是为了实现一个目标的最大化，而我们研究的网络覆盖度和网络寿命是两个互相作用且互相冲突的目标，显而易见它的最优解肯定不会是一个解，而是一组均衡解。对于这个问题，我们选择用多目标进化算法来解决是个可行的方案，首先我们了解进化算法是一种群体智能搜索方法，它比较适合用来求解多目标优化的问题。从1980年开始，人类就运用进化算法来解决多目标优化的问题。近年来，国内外的学者研究了大量的多目标进化算法，其中的一些算法已经可以成熟的应用到工程实践的过程中。如何使多目标优化算法更加趋于完美，即进化多目标优化算法和多目标优化领域成为当今的热门的研究方向。多目标进化算法能用来组合优化问题，具有重要的理论研究和工程应用价值，并且常常被用来测试多目标进化算法的性能，而利用多目标优化算法来对无线传感器网络动态覆盖问题进行算法设计可以找到网络覆盖度和网络寿命的最优解。
鉴于此，本文选择基于多目标进化算法用来研究无线传感器网络动态覆盖问题，构建无线传感器网络动态覆盖问题模型，并根据多目标进化算法的关键技术和基本流程，对基于无线传感器网络动态覆盖问题算法进行设计，以期对实现无线传感器网络动态覆盖最优化有所帮助。
1.1无线传感器网络的研究背景
在无线传感器技术发展日趋成熟的今天，无线传感器通信也由原来有了长足的进步，无线传感器技术发展日益成熟，它的应用方向更趋于多元化，很多的数据采集和通信工作都采用了无线技术。低成本、低功耗、小体积的传感器节点的产生使得微机电系统和低功耗高集成数字设备的发展得以实现。大量的传感器节点配合各种型号的传感器，就能组成一个无线传感器网络。无线传感网络的产生开创了一个新的应用领域，它是一种新兴的概念和技术，无线传感器网络被认为是未来四大高科技技术产业之一，可见它的研究价值。无线技术被广泛应用于中大型区域领域，如大型的无人值守环境监测和目标跟踪，可以适用于战争。因此，传感器技术和传感器网络的研究被认为是最重要的方向。无线传感器节点的工作环境对电池供电是非常苛刻的，因为大量的传感器和难以更换，所以低功率无线传感器网络的一个最重要的设计标准，即延长传感器网络的寿命，使得传感器更加可靠，耐用。
综上所述，在无线传感技术应用如此广泛的今天，在使得网络覆盖度尽可能大的前提下，又能实现传感器的低功耗非常具有研究价值。
1.2无线传感器网络的研究目的及意义
（1）研究目的
无线传感技术的研究发展日新月异，传感器节点的低功耗是它的发展方向之一，而低功耗与高网络覆盖度的结合目前难以实现。如何实现更好的无线传感模块功能，增加模块的可靠性和使用寿命是当今热门的问题。我们知道通过降低无线传感节点的硬件功耗，确定无线传感模块各单元的基本功率消耗，并进行相应比较，确定需重点降耗的单元能够增加网络寿命。本文对从硬件上的探讨不予研究，我们选择基于多目标进化算法用来研究无线传感器网络动态覆问题，构建无线传感器网络动态覆盖问题模型，并根据多目标进化算法的关键技术和基本流程，对基于无线传感器网络动态覆盖问题算法进行设计，以期获得一组最优解。
（2）研究意义
无线传感器网络是一种新的理念和技术，它可以创造很多新的应用。无线传感器技术以其广阔的应用前景和巨大的价值，被认为是在未来十大改变世界的技术之一。目前，无线传感器网络节点的稳定运行的研究，可以提高整个网络的可靠性，低功耗无线传感器模块的研究具有重要的研究价值，它的功能的实现对理论和实际应用都大有裨益。在实践中，许多现有的研究中，高性能和低功耗相结合的研究很少进行，而有些研究只考虑低功耗，有的只在性能上追求卓越而忽视能源消耗的问题。只有综合了性能和低功耗的共同需求，通过对芯片的数据的深入分析，才能得出低功耗高性能的无线传感模块的硬件设计方案。增加传感模块在无线传感模块应用中已经非常的广泛，除了对组成无线传感网络的应用，无线传感技术还能应用到环境监测中去，特别是一些极端恶劣、无人值守的环境，它还可以运用于短距离的无线通信。若能实现无线传感模块的低功耗和高性能的目标，那么其对电能的需求就会更小，能耗的减少能使得无线传感网络的应用范围得到进一步的扩大。
1.3无线传感器网络的发展概况
当前无线传感器网络巨大的应用前景得到了越来越多的关注,从而学者从上个世纪70年代就展开对无线传感网络的研究。最早可以追溯到1978年,美国国防部高级研究计划署在当时就成立了一个分布式传感器网络学习组，并在卡内基梅隆大学对其展开研究。随着嵌入式技术、传感技术等不断发展和进步的80年代，无线传感器凭借具有更强的信息信号采集、处理能力构成了具有信息融合和处理能力的传感器网络。
当今社会，国内外涌现了许多基于无线传感器网络节点的硬件平台，典型的传感器包括Imote2、Mica系列、IRIS系列等。各硬件平台采用了不同的处理器和无线通信模块是其主要的区别。有的传感器节点（Telos、Mica）由于设计的历史很早，其性能已经落后于当今的集成电路工业设计水平，能耗也非常巨大，只能完全进行重做。而有的传感器为了追求具有高性能，使得其功耗过大，而当前能量受限的应用环境已经不再适用。我们知道无线传感器网络的节点采用电池供电，且一般工作在极端恶劣、无人值守的环境。由于传感器节点电池更换困难以及数量庞大的原因，使其能耗耗完后和出现故障时的难以替换，无线传感器网络最重要的设计准则之一就是降低传感器节点的功耗。在21世纪初，美国再生能源办公室工业技术计划（ITP）发布的报告“21世纪工业无线技术”第一页中就引用了总统科技顾问的一段话的提到：无线传感器可将传感器的能源损耗变得更少，能源利用率能提高到原来的110%。而Intel(r)Mote等一些后来的科学研究项目，更注重低功耗操作、系统级集成和硬件的重新配置这三个方面的要求。当今的研究是为了做到低功耗和高性能的平衡，MIT发展的模块化平台对于具体的传感器有不同的硬件设计，传感器的主要功能是数据收集，采用垂直连接器来使不同的处理层整合到一起，为了实现传感器网络的低功耗、低成本和通用性,使得无线传感器网络的实现有了新的解决方案。
1.4无线传感器网络覆盖控制问题概述
覆盖控制技术是无线传感器网络的研究最根本的问题之一，它是一种通过传感器感知建模，使用传感器节点配置和监控目标的感知模型来实现充分和有效地获取必要的信息手段。无线传感器网络反映了物理世界的无线传感器网络的感知根本，无线传感器网络是从现有的移动网络和无线网络的不同点出发，网络覆盖将面临设计方案与节点的能量供给约束的沟通能力和计算能力，传感器节点的部署有大量，分布范围广，网络动态性强的特点。该协议的一个重要目标是扩大网络覆盖网络的寿命，并延长网络的生存能有效地节省资金重新部署的传感器节点。此外，由于传感器节点通常是依靠电池作为能量源，并且节点数量巨大，也有可能被部署在偏远地区或无法达到的区域，这样不能更换传感器节点的电池能量作为主要约束网络系统的生命周期。因此，提高节点的能量效率，延长系统的寿命是无线传感器网络中是必不可少的。并有各种不同的方式来延长系统的寿命，主要是从减少能源消耗和平衡节点的能量消耗，节点之间的两方面考虑降低节点的能量消耗可以使系统更加可靠，从而延长网络寿命周期，可避免能源系统的几个节点过早耗尽而提前终止网络周期，节点之间的能量消耗应得到平衡。综上所述，覆盖控制技术取决于传感器节点的综合质量，基础研究的问题也是服务于一种无线传感器网络。
1.5本文主要研究目标及主要工作
本课题是基于多目标进化算法在WSN的动态覆盖控制中应用，通过学习多目标进化算法，多目标遗传进化对无线传感器网络动态覆盖问题进行算法设计，我们知道多目标进化算法是解决多目标优化问题的一种方法，在现实生活中，很多的优化问题是为了实现一个目标的最大化，而我们研究的网络覆盖度和网络寿命是两个互相作用且互相冲突的目标，显而易见它的最优解肯定不会是一个解，而是一组均衡解，所以大大增加了问题的复杂程度。利用多目标进化算法求解多目标问题是进几年新出现的一种求解思路，在无线传感器网络的应用中，两个重要的参考指标就是网络覆盖度和网络寿命，我们可以用两个函数来表示网络覆盖度和网络寿命，再利用多目标进化算法来求解两个目标的最优解，这就是求一个双目标问题的最优解集。
本文主要做的两个工作为：
(1) 无线传感器网络动态覆盖问题的建模。根据传感器能源特性、布局特点等因素，建立动态覆盖问题模型，明确网络覆盖度和网络寿命两个评价标准的具体定义。
(2) 基于多目标进化算法对无线传感器网络动态覆盖问题进行算法设计。利用多目标进化算法的特点，针对我们建立的模型，从不同出发点考虑设计算法，得出不同覆盖水平和网络寿命的规划方案。依次进行分析和学习，找到适合的算法设计过程，进行仿真环境和参数的设定，对得到的仿真结果进行分析和比较，得出结论。
1.6本文章节结构
本文分为四大章。第一章绪论，阐述了无线传感器网络的研究背景及意义，国内外发展水平概况，以及本文对无线传感器网络主要的研究目标和工作。第二章进行了对无线传感器网络进行了模型分析，分别包括无线传感器网络的简介、无线传感器动态覆盖的评价标准和概率模型。第三章先描述了多目标进化算法的概念和算法过程，然后依次介绍了四种多目标进化算法并对网络覆盖度进行建模和算法分析。第四章选取了基于多目标遗传算法的进化算法对WSN进行算法设计，得出仿真结果并对结果进行分析比对，从而得出结论。

3

第2章 WSN网络覆盖模型分析
第2章WSN网络覆盖模型分析
2.1无线传感器网络简介
由传感器技术、分布式信息处理、嵌入式计算技术、无线通信技术以及微机电系统(MEMS)这五项技术结合而形成的一种全新的信息获取与处理技术，就叫做无线传感器网络(Wireless Sensor Network，WSN)。
由传感器节点、汇聚节点（Sink）、后台管理中心三部分组成了无线传感器网络，如图2-1所示。传感器节点收集有关通过其他传感器节点的多跳传输简单的数据处理环境的信息，监测数据可以在传输过程中被处理的多个节点，通过多跳中继数据到汇聚节点将最后直接发送到管理中心或实现传感器网络通过互联网背景交通管理中心，如通信卫星和GPRS，从整个区域将数据发送到集中处理的后台管理中心。用户管理和传感器网络管理中心通过后台，发布控制任务的配置和收集监测数据，以监控整个网络。

图2-1无线传感器网络结构
无线传感器网络具有很多鲜明的特点：
（1）网络传感器的规模巨大。无线传感器网路由数千个微小的传感器组成，所以通常主要依靠增加的不是单个设备的能力，而是但大规模的、冗余的嵌入式设备协同工作，来提高系统的可靠性和稳定性。
（2）传感器节点工作在无人值守的环境。微型传感器节点通常密集分布在需要监测的区域环境中，由于规模巨大，这是不可能人工照顾每个节点的网络系统往往在无人值守的状态下工作。每个节点只能依靠自己或独立获得能源（电池，太阳能电池）和电源。由此产生的能量是最重要的限制瓶颈，阻碍了无线传感器网络和应用的发展方向之一。
（3）无线传感器网络是一个以数据为中心的网络。基于任务网络是一个传感器网络，其核心是感知信息的数据，而不是网络硬件，这是从传统互联网，无线传感器网络的重要特征不同。由于传感器节点随机部署的传感器网络是节点数目之间完全动态的组成，我们会问一个具体的方向是什么在一个角落里的温度，但温度不会。所需的无线传感器网络以数据为中心的功能设计必须检测数据管理和处理中心，它通常说的无线传感器网络是一个以数据为中心的网络。
（4）动态变化的网络拓扑。移动终端可以在任何高速网络和任意方式移动，可随时关闭；无线收发装置的天线类型多种多样，与发射功率带来的变化中的能量变化；再加上广播的频道，地形和气候的方式和等因素可能会发生在由网络拓扑结构的变化和改变所形成的任何无线电信道的移动终端的冲击速度的组合之间的相互干扰是难以预测的。
2.2 WSN的动态覆盖问题
覆盖问题是指:在相关资源受到限制的情况下,采取传感器节点布置和路由选择等方法,优化分配各种资源,最终使感知、监视、传感、通信等各种服务质量得到改善。
通常情况下，网络覆盖度是评价无线传感器网络的探测质量的一个最重要的标准。从目前的研究看出，评价方式有障碍覆盖度、区域覆盖度和点覆盖度，我们是从这三个方式来评价一个无线传感器网络的探测质量。本文就碍覆盖度、区域覆盖度和点覆盖度会一一给出模型并进行分析，最终会选择一个适合的覆盖度模型来评价无线传感网络的探测效果。
由于传感器的电源能量有限，无线传感器网络研究的核心问题就是如何节省无线传感器网络的工作过程中能量，最大化网络的运行寿命。为传感器节点收集有关通过其他传感器节点的多跳传输简单的数据处理环境的信息，监测数据可以在传输过程中被处理的多个节点，通过多跳中继数据到宿节点将最后直接发送到管理中心或实现传感器网络通过互联网背景交通管理中心，如通信卫星和GPRS，从整个区域将数据发送到集中处理的后台管理中心。用户管理和传感器网络管理中心通过后台，发布控制任务的配置和收集监测数据，以监控整个网络。在满足覆盖率要求的前提下，科学合理的规划传感器的激活顺序，才能尽量延长无线传感器网络的使用寿命这就是无线传感器网络的动态覆盖问题。
2.3 网络覆盖度的评价标准
首先，我们来定义一下网络覆盖度。网络覆盖度可以分为以下三种，即障碍覆盖度、区域覆盖度以及点覆盖度。我们一一解释，如下：
（1）障碍覆盖度
障碍覆盖度指的是通过障碍物而未被发现的概率，图2-2是一个障碍覆盖度的示意图，其中出发点和终点分别在矩形区域上下的边上。

图2-2障碍覆盖度图
（2） 区域覆盖度

图2-3区域覆盖度图
区域覆盖度是可监控区域占整个网络区域的比重。区域覆盖度C=N1/N2，N1为传感器所覆盖的目标区域的面积，N2为目标区域的总面积，n各节点处于工作状态。图2-3是随机部署的传感器覆盖整个矩形区域的示意图，黑色圆点是激活的传感器，空心圆是处于休眠状态的传感器。
（3） 点覆盖度
点覆盖度是指网络所能探测到的点的数目占整个需探测区域点的数目的比重。点覆盖度C=N1/N2，其中N1是可以被探测到的点数，N2是总的需要探测的点数。下图是点覆盖度的示意图，其中圆点是随机布置的传感器节点，黑色圆点是处于激活状态，空心圆点是处于休眠状态，空心方格是需要被覆盖探测的点集。

图2-4点覆盖度图
由图中我们可以看出，黑色圆点处于激活状态时三个圆的面积就把所有的传感器包含进去了，覆盖度就是100%。我们通常把探测的目标区域离散化为格点，从而将区域覆盖问题转化为点覆盖问题。
本文的模型采用了格点模型，在考虑点覆盖时，把要覆盖的区域分成许多小方格用每个小方格的中心点来代表这个方格区域，若点被覆盖，则这个小方格区域便被覆盖，因为无线传感器网络在应用中，通常会布置或撒播大量传感器节点在探测区域，传感器密度比较高，同时若我们划分的网格很密集的话，每个点也能代表这个小方格的探测状况，所以这种假设是合理的。这种方式同时也把所监测的区域离散化，有利于建模，每个传感器打开会覆盖一部分点。
图2-5是一个传感器有效覆盖范围示意图：

图2-5传感器有效覆盖范围示意图

2.4 传感器探测概率模型
在二维网格模型中，传感器在格点的位置，网格给传感器网络的探测范围提供了一个度量标准。每一个传感器的探测范围用以传感器为圆心的圆来表示圆的半径就是传感器的探测半径。我们把传感器si放置在格点（x,y）,若覆盖区域的点p坐标为（i,j）,我们就用s与p之间的欧氏距离d(s,p)=来表示s和p的距离。我们选择概率模型来进行研究，概率模型就是传感器s有效探测目标点P的概率随着s和p之间的欧氏距离d(s,p)的增大而指数级减小。在概率模型下，若存在多个传感器同时工作，则一个目标点p被有效探测的概率是几个传感器共同作用的结果。我们用c(s,p)为传感器s对格点p的探测概率，那么我们定义m(s,p)=1-c(s,p)，m(s,p)称为丢失概率，设S={s1,s2…sn}为无线传感器集合，传感器si对目标点p(xp,,yp)的检测概率为：
公式2-1
其中，d（si，p）为传感器节点si与目标点p的欧氏距离;Re是传感器节点测量可靠性参数。
整个监测区域内的传感器节点对目标节点p同时进行检测的联合检测概率为：
公式2-2
2.5无线传感器网络覆盖的评价标准
2.5.1网络覆盖度
我们用在每个打开的时间段，覆盖的点数/所有点数即来定义为这个时间段的网络覆盖度，即。从网络覆盖度的实际考虑，一个网络工作的过程是许多个时间段之和，为了使网络覆盖度在各个时间段尽可能均衡，考察网络的覆盖质量就用它在各个时间段的覆盖度的最小值作为整个网络的覆盖度，即：
公式2-3
其中，
covi为每一时间段网络的覆盖率；
为点的总数目量；
为在ti时间段内网络被覆盖的覆盖度。
从实际出发，无线传感器网络覆盖度如果太低了，就起不到作用，比如无线传感器网络覆盖度太低，就对整个覆盖区域监测弱到无法检测，这样就失去了监测的意义。所以我们要设置一个覆盖度门槛为，使得各个时间段的覆盖度都不能小于。不同的打开组合对各个时间段的覆盖度是有影响的，因此，构建无线传感器网络动态覆盖问题模型如下：
公式2-4
其中：
T是网络能维持的时间段数
是最小覆盖度门槛；
为每一时间段网络的覆盖率；
为点的总数目量；
为在ti时间段内网络被覆盖的覆盖度。
2.5.2网络寿命
当网络从部署开始到网络不工作的时间跨度就被称为无线传感器网络的生存周期。但是我们又考虑到非功能性网络的具体应用时，无线传感器网络节点的寿命可以是死亡的时间或范围发生的损失的第一个跨度。在某些情况下，延长的所有节点的存活是必需的，只要死亡的一个节点，该网络的质量将大大降低。另一方面，在某些情况下，传感器节点可以密集地放置。这样的数据可以被记录相邻传感器相关或相同的。因此，一个或几个节点不削弱的网络服务质量的工作是不会自动。
探测区域有产生冗余一般由两个原因导致：（1）网络规模过大；（2）传感器节点密集太过密集，这些原因会使电池间断的工作比持续工作维持时间提高了一倍不止，由此我们可以得知间断的打开各个传感器节点能延长网络寿命。网络寿命的定义就是根据电量设定每个节点能打开N个时间段，传感器在打开状态下每个时间段的耗能相同，如果一部分节点的打开能承担整个区域的监测任务，那么我们在该时间段只让这一部分节点打开，其他的传感器节点休眠，不消耗能量。这样依次轮流打开不同的节点集合，既能完整的监测需要检测的环境，又能降低能耗。那么网络寿命的定义就是无线传感器网络能维持所要求覆盖度的时间段数。
2.5.3延长网络寿命和有限时间段内节能的关系
下面我们用一个例子来说明这个问题，有图2-6所示传感器布局。

图2－6 无线传感器网路布局图
先来说明图中的各个元素的含义，A、B、C、D、E、F是传感器节点，同时点A、B、C、D、E、F都是要覆盖的点，要说明的是点 G不是传感器但是它要求被传感器覆盖到，我们设定每个节点的能耗相同。假定网络覆盖度为100%，即A、B、C、D、E、F、G都要被节点覆盖到。要完成这个目标，从图中可以看出，最简单的方法就是同时打开A和C两个传感器，这个方案又是打开节点最少的，所以能耗也最低。那么这就是最优的方案了吗？我们继续往下分析，当A和C两个传感器电量耗尽之后，剩余的节点B、D、E、F全部打开都不能覆盖到点G，即网络覆盖度达不到 100%，这个方案的网络寿命就是A和C两个节点的运行时间。显然网络寿命很低，我们采取另一个方案，现打开A、D和F三个节点，从图中可以看出七个点都被覆盖了，而在A、D、F三个节点能耗耗尽后，我们再打开B、C和E是那个节点，这样同样能满足覆盖度为100%的要求，那么这个方案的网络寿命是两次打开的时间之和，时间是上一个方案的两倍。把以有限时间内节能作为目标，求出的最优解为{A、C}，而若直接以延长网络寿命为目标，则求出的最优解为{{A、D、F}，{B、C、E}}。在这种情况下的最优解，得到为一个有限的时间周期来确定最节能的解决方案是不能够维持网络的寿命最长。因此节省了时间和最大化网络寿命的限定期间内是不能完全等同，但网络的寿命问题是由能量有限，但在某些情况下不延长网络的生命周期转化为节能考虑。多个覆盖网络是一种协同效应传感器节点的结果，单一的高能效不一定延长网络的寿命。这个带有一个固定量，例如汽车用汽油和机油，只有汽油和机油共同作用汽车才能运行，能跑最长时间的，不一定是剩的油总量最多的，若最后全剩下机油，没有汽油的配合，也不能开动。我们的本质需要就是要网络维持时间最长，回到问题的本质上，设定一个目标就是在满足覆盖度的条件下最大化网络寿命，这个目标更准确。
41

计算机信息工程学院毕业设计说明书

第3章 多目标进化算法分析
第3章 多目标进化算法分析
3.1多目标进化算法简介
3.1.1多目标进化算法概念及特点
一、多目标进化算法概念
进化算法又称为演化算法，是一种模拟自然进化过程的随机优化算法。和传统优化技术来比较，群体搜索策略和群体间个体之间的信息交换是进化算法的两个特点。
先明确一个概念：帕累托最优解。资源分配的一种理想状态就被称为帕累托最优，我们假定有可分配的资源分配给固定的一群人，在没有是任何一个人的资源变少的情况下，从改变分配的方式，使得群体中至少有一个人的资源更多，这就被称为帕累托改进或帕累托最优化。帕累托最优的状态就是帕累托改进能达到帕累托最优的路径和方法。
进化算法中，个体需要有分辩优劣的能力。这能通过一个单一的目标函数来实现，但在同时有多个目标，面对现实中的多目标问题，对个体的优劣评价适应度的困难程度变得相对复杂。
根据帕累托最优的概念，对多目标进化算法中分配适应度时主要需要考虑两个问题，一是如何支配越多个个体应分配更优的适应度；二是如何在分布在稀少区域的个体分配更优的适应度。我们通过不同的多目标进化算法，能获得在目标空间广泛分布的不同的解，这就使我们有了更多的选择余地。只有采取了各自的适应度分配方式，才能用不同的多目标进化算法来进行实现。
本文主要研究了四种多目标进化算法，分别为多目标遗传算法、改进的多目标差分进化算法、多目标粒子群优化算法、分布式启发式算法对无线传感器网络动态覆盖问题进行学习与分析，下文会一一进行介绍。
二、多目标优化问题的特点
顾名思义，多目标问题肯定具有多个目标函数，而且各个函数之间在最优化方向上存在冲突。最重要的是，目标函数集要么是求极大，要么是求极小值，两者只能取其一。就拿本文我们研究的无线传感器网络来说，传感器网络有两个重要指标，即网络覆盖度和网络寿命，我们设计的要求是让网络覆盖度和网络寿命尽可能的大。而网络寿命和网络覆盖度又是一对矛盾的对象，要让网络覆盖度大，那么必然要打开更多的传感器节点。节点打开的越多，那么可以维持的时间就越短，网络寿命就越小，这就是两者在最优化的方向上存在冲突。
3.1.2多目标进化算法的通用算法过程及优缺点
（1）算法过程
输入：基于多目标算法的通用算法过程
输出：多目标优化解集
步骤1：初始化种群
步骤2：适应值评价
步骤3：进化算子操作，生成新的种群
（a） 选择算子
（b） 组合算子
（c） 交叉算子
步骤4：如果满足终止条件，结束算法迭代，否则转到步骤2。
（2）优缺点
1）每轮迭代可以找到多个帕累托近似最优解。
2）迄今为止还没有找到其他方法比进化算法更能有效的解决多目标问题。
3）在许多复杂的应用问题中搜索最优解还存在一定的困难。
4）多目标进化算法能解决一些不容易解决特征的优化问题，如不连续、多模态、可行空间不连续的问题。
5）多个个体能同时找到多种解决方案，即帕累托解集。这对于对问题信息了解较少的情况，或者决策者难以给出偏好时很有用。
3.2 各类多目标进化算法分析
由于文章的篇幅限制以及个人精力有限，本本文主要研究了四种多目标进化算法，分别为多目标遗传算法、改进的多目标差分进化算法、多目标粒子群优化算法、分布式启发式算法，对无线传感器网络的动态覆盖进行学习与研究。
3.2.1 分布式启发式算法
本文基于分布式启发式算法对无线传感器网络的研究借鉴了文献[8]的知识，K覆盖问题的定义是：有些传感器网络中对监测区域或目标的覆盖质量具有特殊的要求，因此要求监测区域中的每个目标点至少被K个不同传感器节点同时覆盖。
假设有向传感器节点可在几个覆盖方向中切换，根据传感器节点的覆盖方向协同优化，实现覆盖区域和目标的最大化有向覆盖。视频传感器节点具有视频传感器的感知模型范围是指传感器节点是节点P（X，Y）为圆心、感知距离为R（半径）、夹角为α的扇形区域，扇形区域的中心线Vp角度为θ，如图3-1所示，因此，每个有向感知节点模型都可以用一个五元组<X,Y,R,α,θ>来表示，分别表示每个有向感知节点的中心位置坐标，感知半径，感知视角及感知方向角。

图3-1有向感知节点模型
本文研究的有向K覆盖问题属于目标覆盖，K覆盖算法可解释为如图3-2所示的模型：假设有一个内存覆盖区有四个传感器和三个目标点，在一个特定的方向四个方向的传感器传感器，因此，目标1是传感器1和2和传感器4覆盖，目标2所覆盖的传感器2和4中，在靶3上覆盖传感器2和3，具有至少两个包括的传感器传感器的所有目标，以满足K 为2的覆盖范围。在无线视频传感器网络的实际应用，至少需要一些目标点同时覆盖K个不同的传感器传感器，因此，必须保证设定k的最大目标传感器已经覆盖到。本算法接着建立了K覆盖问题，以优化理论模型给出的指令级并行的形式整数线性规划的准确描述。

图3-2视频传感器网络覆盖模型
有向感知K覆盖控制算法的工作流程如下:无线视频传感器网络部署完成后，视频传感器传感器扫描各个覆盖方向上的目标信息，并与其一跳邻居节点交换目标信息，然后计算每个覆盖方向的效用函数值，选取效用函数值为最大概率选择自身的工作方向，最后将自己的方向决策通知其一跳邻居传感器。同时，有向感知K覆盖控制算法中进而还可以扩展考虑传感器的剩余能量：将一个工作时间间隔成为一轮，在每轮时间末期，一跳邻居传感器范围内交换剩余能量信息，依据自身剩余能量值决定是否在下一轮是否休眠，节点集按序完成有向覆盖的任务，从而延长网络生存时间。
下面给出有向感知K覆盖算法伪代码：
初始化：网络拓扑结构G（N，E）及目标集合M分布
%每一轮时间周期内重新选择
For(Round1,...7)
{
所有节点发送Beacon消息
%按节点序号在一跳邻居范围内自行遴选方向
For（i=1，...,N）
｝
1. 收集所有一跳邻居节点的数据，更新方向目标集合
2. 遍历所有的目标集合M，计算覆盖每个集合的方向节点
3. 根据遍历结果计算本节点所有方向的效用函数值
4. 计算每个方向的归一化效用函数值
5. 一效用函数值为概率随机选择覆盖方向
综上所述，对无线视频传感器网络中的有向K重覆盖问题，假设有向传感器节点可在几个覆盖方向中切换，根据传感器节点的覆盖方向协同优化，实现覆盖区域和目标的最大化有向覆盖。本算法利用网络有向覆盖的冗余特性，设计一种简单的分布式启发式算法对有向传感器节点的感知方向进行调度，使得目标集合被K覆盖的时间最多。与求解最大有向K覆盖问题的贪婪算法一样，有向感知K覆盖控制算法也属于一种一跳覆盖范围内的分布式方法。最后，使用算法验证了算法性能，特别相比较于随机覆盖算法，能大大减低覆盖盲区比例。
3.2.2多目标差分进化算法
本文基于多目标差分进化算法对无线传感器网络的研究借鉴了文献[9]的知识，多目标差分进化算法的特点是：收敛速度快，控制参数小以及容易实现和理解的。建议多目标覆盖的无线传感器网络的控制策略K重覆盖，无线传感器网络节点的传感单元的能源消耗和优化目标的可靠性系数，采用改进的多目标进化算法求解差。它们的差别是在覆盖范围的分析的控制策略，并结合来自控制高精度K重覆盖研究的角度考虑，泊松分布模型的传感器节点。在研究能量消耗的问题，考虑到调度和传感器节点感知半径可调在这两种情况下，量化传感器节点传感半径和工作状态传感传感器节点能量消耗的数量的影响。从网络上的生命周期的工作传感器节点的数目的影响，提出了一种可靠性因子，获得了网络的可靠性趋势知觉半径和传感器节点密度的影响。仿真结果表明，该控制策略可以保证K重覆盖，同时有效降低能耗，保证网络的可靠性。
目前的研究无线传感器网络的可靠性，通常分为两大类：基于任务的可靠性模型和基于寿命的网络可靠性模型。基于寿命的网络覆盖模型从连通性对生命周期的角度可靠性分析定义了以下三个概念：（1）第一个传感器节点的能量耗尽可视为网络生活;（2）达到网络不能够接受的事件探测率时所用时间，看作网络寿命；（3）当网络中存活节点数量所占比例低于某一阈值时，可认为已经达到网络寿命。当使用节点调度机制，