多目标进化算法在WSN的动态覆盖控制中应用.docx
- 文档编号:5510267
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:47
- 大小:742.40KB
多目标进化算法在WSN的动态覆盖控制中应用.docx
《多目标进化算法在WSN的动态覆盖控制中应用.docx》由会员分享,可在线阅读,更多相关《多目标进化算法在WSN的动态覆盖控制中应用.docx(47页珍藏版)》请在冰点文库上搜索。
多目标进化算法在WSN的动态覆盖控制中应用
多目标进化算法在WSN动态覆盖控制中的应用
摘要
随着无线传感器网络的广泛应用,关于无线传感器网络的问题,特别是无线传感器网络的动态覆盖的问题得到了越来越多的关注。
研究如何规划传感器合理的激活方案,来使无线传感器网络既要达到合理的区域覆盖度,又尽可能的延长网络寿命已经成为研究的一个热点。
本文以多目标进化算法在无线网络传感器网络动态覆盖中的应用为研究课题,首先概述无线传感器网络和无线传感器网络动态覆盖问题的基础知识,作为本文研究的理论基础;然后,以无线网络传感器网络的评价标准,即网络覆盖率和网络寿命,确定性部署和随机部署为依据构建无线传感器网络覆盖问题模型;在此基础上提出多目标遗传算法的概念、特点、关键技术和基本流程,并以此为依据对无线网络传感器网络动态覆盖问题进行算法设计,通过基于多目标遗传算法的无线传感器网络动态覆盖问题算法设计,实现无线传感器网络动态覆盖的最大优化。
关键词:
无线传感器网络;动态覆盖;模型;多目标遗传算法
MUITI-OBJECTIVEEVOLUTIONARYALGORITHMINWSNDYNAMICOVERLAY
Abstract
Withawiderangeofissuesrelatedtotheapplicationofwirelesssensornetworks,wirelesssensornetworks,especiallydynamiccoverageprobleminwirelesssensornetworks,namely,howtoactivatetheprogramthroughrationalplanningsensorreachesacertaintargetareaunderthepremiseofcoverageaspossibletheextensionofthelifeofthenetworkhasbecomeahotresearch.Inthispaper,multi-targetalgorithminwirelesssensornetworksdynamicoverlaynetworkforresearch,firstoutlinedthebasicsofwirelesssensornetworksandwirelesssensornetworksdynamiccoverageproblem,asthetheoreticalbasisforthisstudy;thentoawirelessnetworksensornetworksevaluationcriteria,thatis,networkcoverageandnetworklifetime,deterministicandstochasticdeploymentisbasedonthedeploymentofwirelesssensornetworkcoverageissuetobuildthemodel;conceptproposedmulti-objectivegeneticalgorithmbasedonthis,characteristics,basickeytechnologiesandprocesses,andtothisisbasedonwirelesssensornetworkdynamicnetworkcoverageproblemforalgorithmdesign,dynamiccoverageproblemalgorithmdesignthroughpre-arrangedopeningsequence-basedwirelesssensornetworks,wirelesssensornetworkstoachievemaximumoptimizationofdynamiccoverage.
Keywords:
wirelesssensornetworks;dynamiccoverage;model;multi-objectiveGeneticAlgorithms
第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.2WSN的动态覆盖问题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
第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进行算法设计,得出仿真结果并对结果进行分析比对,从而得出结论。
第2章WSN网络覆盖模型分析
2.1无线传感器网络简介
由传感器技术、分布式信息处理、嵌入式计算技术、无线通信技术以及微机电系统(MEMS)这五项技术结合而形成的一种全新的信息获取与处理技术,就叫做无线传感器网络(WirelessSensorNetwork,WSN)。
由传感器节点、汇聚节点(Sink)、后台管理中心三部分组成了无线传感器网络,如图2-1所示。
传感器节点收集有关通过其他传感器节点的多跳传输简单的数据处理环境的信息,监测数据可以在传输过程中被处理的多个节点,通过多跳中继数据到汇聚节点将最后直接发送到管理中心或实现传感器网络通过互联网背景交通管理中心,如通信卫星和GPRS,从整个区域将数据发送到集中处理的后台管理中心。
用户管理和传感器网络管理中心通过后台,发布控制任务的配置和收集监测数据,以监控整个网络。
图2-1无线传感器网络结构
无线传感器网络具有很多鲜明的特点:
(1)网络传感器的规模巨大。
无线传感器网路由数千个微小的传感器组成,所以通常主要依靠增加的不是单个设备的能力,而是但大规模的、冗余的嵌入式设备协同工作,来提高系统的可靠性和稳定性。
(2)传感器节点工作在无人值守的环境。
微型传感器节点通常密集分布在需要监测的区域环境中,由于规模巨大,这是不可能人工照顾每个节点的网络系统往往在无人值守的状态下工作。
每个节点只能依靠自己或独立获得能源(电池,太阳能电池)和电源。
由此产生的能量是最重要的限制瓶颈,阻碍了无线传感器网络和应用的发展方向之一。
(3)无线传感器网络是一个以数据为中心的网络。
基于任务网络是一个传感器网络,其核心是感知信息的数据,而不是网络硬件,这是从传统互联网,无线传感器网络的重要特征不同。
由于传感器节点随机部署的传感器网络是节点数目之间完全动态的组成,我们会问一个具体的方向是什么在一个角落里的温度,但温度不会。
所需的无线传感器网络以数据为中心的功能设计必须检测数据管理和处理中心,它通常说的无线传感器网络是一个以数据为中心的网络。
(4)动态变化的网络拓扑。
移动终端可以在任何高速网络和任意方式移动,可随时关闭;无线收发装置的天线类型多种多样,与发射功率带来的变化中的能量变化;再加上广播的频道,地形和气候的方式和等因素可能会发生在由网络拓扑结构的变化和改变所形成的任何无线电信道的移动终端的冲击速度的组合之间的相互干扰是难以预测的。
2.2WSN的动态覆盖问题
覆盖问题是指:
在相关资源受到限制的情况下,采取传感器节点布置和路由选择等方法,优化分配各种资源,最终使感知、监视、传感、通信等各种服务质量得到改善。
通常情况下,网络覆盖度是评价无线传感器网络的探测质量的一个最重要的标准。
从目前的研究看出,评价方式有障碍覆盖度、区域覆盖度和点覆盖度,我们是从这三个方式来评价一个无线传感器网络的探测质量。
本文就碍覆盖度、区域覆盖度和点覆盖度会一一给出模型并进行分析,最终会选择一个适合的覆盖度模型来评价无线传感网络的探测效果。
由于传感器的电源能量有限,无线传感器网络研究的核心问题就是如何节省无线传感器网络的工作过程中能量,最大化网络的运行寿命。
为传感器节点收集有关通过其他传感器节点的多跳传输简单的数据处理环境的信息,监测数据可以在传输过程中被处理的多个节点,通过多跳中继数据到宿节点将最后直接发送到管理中心或实现传感器网络通过互联网背景交通管理中心,如通信卫星和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时间段内网络被覆盖的覆盖度。
从实际出发,无线传感器网络覆盖度如果太低了,就起不到作用,比如无线传感器网络覆盖度太低,就对整个覆盖区域监测弱到无法检测,这样就失去了监测的意义。
所以我们要设置一个覆
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多目标 进化 算法 WSN 动态 覆盖 控制 应用