多目标进化算法在wsn的动态覆盖控制中应用毕业论文(编辑修改稿)

多目标进化算法在wsn的动态覆盖控制中应用毕业论文(编辑修改稿)内容摘要：

1：初始化种群步骤2：适应值评价步骤3：进化算子操作，生成新的种群（a） 选择算子（b） 组合算子（c） 交叉算子步骤4：如果满足终止条件，结束算法迭代，否则转到步骤2。 （2）优缺点1）每轮迭代可以找到多个帕累托近似最优解。 2）迄今为止还没有找到其他方法比进化算法更能有效的解决多目标问题。 3）在许多复杂的应用问题中搜索最优解还存在一定的困难。 4）多目标进化算法能解决一些不容易解决特征的优化问题，如不连续、多模态、可行空间不连续的问题。 5）多个个体能同时找到多种解决方案，即帕累托解集。 这对于对问题信息了解较少的情况，或者决策者难以给出偏好时很有用。 各类多目标进化算法分析由于文章的篇幅限制以及个人精力有限，本本文主要研究了四种多目标进化算法，分别为多目标遗传算法、改进的多目标差分进化算法、多目标粒子群优化算法、分布式启发式算法，对无线传感器网络的动态覆盖进行学习与研究。 分布式启发式算法本文基于分布式启发式算法对无线传感器网络的研究借鉴了文献[8]的知识，K覆盖问题的定义是：有些传感器网络中对监测区域或目标的覆盖质量具有特殊的要求，因此要求监测区域中的每个目标点至少被K个不同传感器节点同时覆盖。 假设有向传感器节点可在几个覆盖方向中切换，根据传感器节点的覆盖方向协同优化，实现覆盖区域和目标的最大化有向覆盖。 视频传感器节点具有视频传感器的感知模型范围是指传感器节点是节点P（X，Y）为圆心、感知距离为R（半径）、夹角为α的扇形区域，扇形区域的中心线Vp角度为θ，如图31所示，因此，每个有向感知节点模型都可以用一个五元组X,Y,R,α,θ来表示，分别表示每个有向感知节点的中心位置坐标，感知半径，感知视角及感知方向角。 图31有向感知节点模型本文研究的有向K覆盖问题属于目标覆盖，K覆盖算法可解释为如图32所示的模型：假设有一个内存覆盖区有四个传感器和三个目标点，在一个特定的方向四个方向的传感器传感器，因此，目标1是传感器1和2和传感器4覆盖，目标2所覆盖的传感器2和4中，在靶3上覆盖传感器2和3，具有至少两个包括的传感器传感器的所有目标，以满足K 为2的覆盖范围。 在无线视频传感器网络的实际应用，至少需要一些目标点同时覆盖K个不同的传感器传感器，因此，必须保证设定k的最大目标传感器已经覆盖到。 本算法接着建立了K覆盖问题，以优化理论模型给出的指令级并行的形式整数线性规划的准确描述。 图32视频传感器网络覆盖模型有向感知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覆盖控制算法也属于一种一跳覆盖范围内的分布式方法。 最后，使用算法验证了算法性能，特别相比较于随机覆盖算法，能大大减低覆盖盲区比例。 本文基于多目标差分进化算法对无线传感器网络的研究借鉴了文献[9]的知识，多目标差分进化算法的特点是：收敛速度快，控制参数小以及容易实现和理解的。 建议多目标覆盖的无线传感器网络的控制策略K重覆盖，无线传感器网络节点的传感单元的能源消耗和优化目标的可靠性系数，采用改进的多目标进化算法求解差。 它们的差别是在覆盖范围的分析的控制策略，并结合来自控制高精度K重覆盖研究的角度考虑，泊松分布模型的传感器节点。 在研究能量消耗的问题，考虑到调度和传感器节点感知半径可调在这两种情况下，量化传感器节点传感半径和工作状态传感传感器节点能量消耗的数量的影响。 从网络上的生命周期的工作传感器节点的数目的影响，提出了一种可靠性因子，获得了网络的可靠性趋势知觉半径和传感器节点密度的影响。 仿真结果表明，该控制策略可以保证K重覆盖，同时有效降低能耗，保证网络的可靠性。 目前的研究无线传感器网络的可靠性，通常分为两大类：基于任务的可靠性模型和基于寿命的网络可靠性模型。 基于寿命的网络覆盖模型从连通性对生命周期的角度可靠性分析定义了以下三个概念：（1）第一个传感器节点的能量耗尽可视为网络生活。 （2）达到网络不能够接受的事件探测率时所用时间，看作网络寿命；（3）当网络中存活节点数量所占比例低于某一阈值时，可认为已经达到网络寿命。 当使用节点调度机制，处于休眠状态的每个节点，以监视在其覆盖范围运行状态的邻居节点，如果该节点不是活动的，它进入工作状态，否则它保持休眠状态。 第三类是根据网络的生命周期定义，这种机制可以有效地延长网络的生命周期。 因此，为了确保在工作状态的前提下使网络寿命得到延长，高可靠性能获得高覆盖度，因此，需要定义一个体现可靠性的因子P: 公式31覆盖模型的用途的范围是通过设置节点密度和半径的合理感知，使得传感器网络的覆盖区域来监视多个满足预定值时，该网络的最大覆盖范围的前提下，要求控制，最低的能耗，网络工作寿命最长的。 通过上述推导的优化问题，区域覆盖优化可以被定义为下面的多目标。 （1） K重覆盖率。 保证目标区域内的目标事件能够以最大的概率被感知： 公式32（2） 单位感知能耗。 在满足网络覆盖指标后，整个网络的能耗越少，网络性能越好： 公式33（3） 可靠性因子:基于多目标差分算法的传感器随机覆盖控制问题求解流程如图33所示：图33多目标差分进化算法流程无线传感器网络覆盖控制策略，本文考虑了K重覆盖，节点的单位能耗和可靠性因子这三项指标的信度系数。 为确保高覆盖率监控能力的无线传感器网络，使能耗低可靠性高的传感器得以延长网络的寿命。 本文通过对多目标优化和改进的多目标差分进化算法的研究，从调节传感器K重覆盖密度和节点半径的大小以及单位能耗的角度来看，对有关传感器可靠性的因素进行了优化，以期能获得最佳的节点部署密度和传感半径，并且能够确定一段时间内传感器的睡眠时间的理论数量。 通过改进多目标非支配排序遗传算法和比较差分进化算法能够看出，多目标差分进化算法具有更好的数据挖掘和保持非支配解能力，还可以提供更丰富的信息，为决策者进行决策提供了多样性的选择余地。 正如从仿真结果中看到的，该控制策略能够确保覆盖区域的可靠性，同时降低了能量消耗，提供最优的实际布局，以期能够获得实时的密度传感器节点传感半径和的大小的参考值。 本文基于多目标粒子群进化算法对无线传感器网络的研究主要来自[10]。 多目标粒子群优化算法在最近几年得到了很大的发展，被看作是解决多目标优化算法的一种有效的群智能算法，算法基于一个群体中的粒子能够从过去的经历和其他粒子中获取有效信息这一个假设。 因为无线传感器的部署网络节点随机部署有很高密度和各自的特征，因此大多数传感器之间的横截面覆盖区域的重叠一方面，如果同样的工作将导致能源的浪费和缩短网络寿命，另一方面一些区域不需要进行监测，这就造成了浪费，因此如何确定网络覆盖范围是无线传感器网络中的关键问题之一。 本算法旨在对人工很难准确监测的环境，使用固定传感器和移动传感器来构建混合无线传感器网络，研究如何最大限度地提高无线传感器网络监控和网络部署优化策略，来提高网络的范围覆盖。 对于无线传感器网络覆盖问题，部署在除了随机最大化网络覆盖的无线传感器网络，有一个值得研究的问题，这将导致传感器随机重叠覆盖区域的部署，然后换另外的移动传感器的位置，如在重叠区域中找到应冗余传感器进入休眠状态中的区域中，从而提高了网络的使用寿命。 该算法是基于非支配排序策略，通过改进多目标粒子群优化算法和粒子群粒子模拟移动节点的位置，再加上冗余节点基于加权自适应邻干扰检测在每次迭代取适应值的粒子效果，从中选择最佳的粒子参与的下一次的进化，从而提高网络的覆盖范围并延长无线传感器网络的生命周期的目的。 目标标区域A为被离散化成LW个网格的二维矩形平面，每个网格代表一个待监测小区域。 在区域A随机投放M个移动传感器节点和N个固定传感器节点构成混合无线传感器网络，在不影响问题本质的前提下，作以下假设：①固定传感器节点的能量不能补充，即当其能量耗尽时，该节点不能工作；② 所有节点的无线通信范围是以节点为圆心、半径的Rc的圆形区域，节点感知半径为Rs且Rc＝2Rs；③所有节点均采用布尔感知模型；④各节点通信模型采用布尔通信模型；⑤每个节点具有工作、侦测和休眠3种状态。 目标区域A内任一离散网格k，其中心坐标为（xk，yk），如果与最邻近传感器节点si（xi，yi）的距离 公式34那么k点被传感器ｓ感知到的概率P（k，s）=1；否则P（k，s）=0，在此基础上，将网格k（xk，yk）的覆盖定义为该网格被处于工作状态的传感器节点集X=｛s1,...,sn｝中至少一个感知到的概率，即： 公式35因此，无线传感网络覆盖就是该网络中处于工作状态的传感器节点集X所覆盖网格点的总和，记为Cov（X）即： 公式36处于休眠状态的传感器数量记为：Sleep（X）=N+M|X||X|表示集合Ｘ的元素个数。 混合无线传感网络的覆盖问题就是如何优化移动节点的位置，在保证网络全连通的前提下，使得处于工作状态的传感器节点尽可能少，且目标区域被无线传感器网络覆盖的面积尽可能大。 因此，混合无线传感网络的覆盖问题可以归结为满足网络全连通条件两目标优化问题，即：maxF（X）=[f1(X),f2(X)]由于随机部署的传感器节点是很容易形成感知覆盖重叠区域，以便关闭由冗余节点来扩展网络的生命周期。 在本算法中，对于主动检测睡眠时间表的自适应方法来关闭或启动传感器节点。 首先，随机设置传感器节点处于休眠状态和工作条件，所以经过一段时间的休眠随机睡眠时间ts后，每个节点醒来的工作。 具体的检测方法是：节点的功率唤醒在该地区的适当直径为工作节点的区域内发射接收回复信息答复消息，如果睡眠检测节点答复消息的一声，和睡眠时间调整进入休眠状态；没有接收到应答消息，如果在一段时间内，该节点的睡眠状态转移到工作。 本文提出了一种邻里干扰与多目标粒子群优化算法，基于全局最优粒子从F1在基于加权法非劣效性面前可供选择，并从随机选取的不同，NSGAⅡ非支配排序策略，其自己粒子局部最优的粒子。 中的运动效应的方程式粒子位置更新，以及基于自适应邻干扰它们的值相适应。 该算法的基本流程如图34所示：图34 算法流程图用基于邻域扰动的多目标粒子群优化算法能较好优化随机部署的混合无线传感网络的覆盖性能，有三个原因：首先，算法对粒子群进行克隆并采用动态邻域扰动操作，通过该操作，一方面适应性强的粒子扰动幅度小，达到增强局部精确搜索的目的，另一方面，对于适应性较差的粒子，增大扰动幅度，从而增加发现更好位置的机会；其次，基于精英保留的非支配排序策略为算法提供了良好的非劣解集；最后，通过加权法从当前非劣解集中选出全局最优粒子并从非劣解集中随机选取个体最优粒子从而为粒子下一次进化指引了方向。 本文基于多目标遗传算法对无线传感器网络的研究主要来自文献[11]，多目标遗传算法通常实现方式为一种计算机模拟。 对于一个最优化问题，一定数量的候选解的抽象表示的种群向更好的解进化。 多目标遗传算法常用的基本概念主要包括个体、群体、基因、基因型、适应值等。 在无线传感器网络中，节点一般采用电池作为能源，更换节点电池难以实现，同时其计算能力和通信能力受限，网络的节点部署在一定程度上决定了网络的性能和使用寿命。 因此，在运行过程中保证能量有效和延长网络寿命成为无线传感器网络应用的关键。 基于粒子群优化的策略，可以提高无线传感器网络覆盖性能，但算法本身就容易陷入局部最优，导致无法收敛到全局极值点。 很多算法的目标都是优化网络覆盖度，但不考虑网络能量平衡的问题，能量平衡也是在运行整个网络的寿命和稳定性决定的一个重要因素。 该算法不同于算法是，在确保使用较少的节点，同时考虑网络区域的能量平衡策略之前工作。 仿真结果表明，新的覆盖控制策略可以显著提高覆盖率，节约能源消耗，并确保网络的能量平衡。 为了获得较高的覆盖率的无线传感器网络的需要，通常可以增加传感器节点的密度，这可以有效减少感知盲点出现的概率。 但是大量的冗余数据传输网络会导致传感器节点会产生冲突，从而导致过度的能量消耗，因而在网络的过早地失效。 如果一个节点可以感知的区域完全能被其他节点完全覆盖，这那么个节点就被称为冗余节点，该传感器可以进入休眠状态并且不影响网络覆盖度。 通过一些可行的算法来确定冗余节点的存在，前提是确保最大的网络覆盖，同时又使用尽可能少的传感器节点，允许冗余节点休眠，这是一个传感器网络既能满足覆盖要求又能降低能耗的有效途径。 因此，在网络的初始阶段，选择对网络性能的节点的一个合理的工作和运行成本是十分重要的。 在同一时间，该网络的能量消耗的平衡，对于网络的稳定运行所必需，并延长了网络寿命，它存在与覆盖和。