（控制理论与控制工程专业论文）基于粒子群算法的无线传感网络覆盖问题优化策略研究.pdf

浙江工业大学硕士学位论文 基于粒子群算法的无线传感网络 覆盖问题优化策略研究 摘要 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 覆盖控制是无线传感器网络应 用的一个基本问题，它是研究在保证一定的服务质量条件下，如何实现网络覆盖范围的最 大化，以提供可靠的监测和目标跟踪服务。有效的覆盖控制策略及算法的应用可以使w s n s 的各种资源得到优化分配，有助于网络节点能量的有效利用、感知服务质量的提高和整体 生存时间的延长。如何结合不同的应用环境需要，设计切实可行的覆盖策略，是该领域一个 研究热点。 无线传感器网络是典型群体网络系统，其覆盖控制问题具有群体自组织的特征。本文 基于群体智能建立无线传感器网络的覆盖优化策略。首先利用基本粒子群算法和粒子进化 的多粒子群算法建立具体覆盖优化算法，并进行实验仿真，指出它们的不足之处；进而针 对这两种算法的不足，提出基于及拟物力导向的粒子群覆盖优化算法，实验结果表明这种 算法的有效性。论文的具体研究工作和成果如下： 1 利用基本粒子群算法和粒子进化的多粒子群算法分别设计了覆盖优化仿真实验， 通过仿真结果分析各参数对覆盖性能的影响，把两种算法的覆盖优化效果进行比较分析， 指出它们的不足之处，提出改进思路； 2 针对上述两种算法的不足，把基本粒子群算法和与拟物力算法相融合，设计出拟 物力导向的无线传感网络覆盖优化策略。与上述两种算法在相同的条件下进行相同的仿真 实验分析，把三种算法的覆盖优化效果进行比较，说明该改进后的组合算法具有更好的覆 盖优化效果； 3 为进一步证明该算法的有效性，把上述三种算法与传统遗传算法( c g a ) 和新量 子遗传算法( n q g a ) 两种算法在相同环境下的覆盖优化效果进行比较分析，实验结果证 明该组合算法比基本粒子群算法、粒子进化的多粒子群算法、传统遗传算法( c g a ) 和新 量子遗传算法( n q g a ) 具有更理想的优化效果。 浙江工业大学硕士学位论文 4 本论文在基本粒子群算法和粒子进化的多粒子群算法的覆盖优化仿真实验的基础 上，设计提出拟物力导向的粒子群无线传感网络覆盖优化策略，通过对不同优化算法在相 同条件下的仿真结果进行比较和分析，证明改进后的优化算法能更好地改善无线传感网络 的性能。 关键词：无线传感器网络，粒子群算法，拟物力导向，粒子进化，覆盖优化 浙江工业大学硕士学位论文 c o v e r a g eo p t i m i z a t i o ns t r a t e g y o f w i r e l e s ss e n s o rn e t w o r k sb a s e do n p a r t i c l es w a r mo p t i m i z a t i o n a b s t r a c t w i r e l e s ss e n s o r n e t w o r k s ( w s n s ) c o v e r a g ec o n t r o l i sab a s i cp r o b l e mi nw s n s a p p l i c a t i o n s i ti s as t u d yo nh o wt om a x i m i z et h en e t w o r kc o v e r a g et op r o v i d er e l i a b l e m o n i t o r i n ga n dt r a c k i n gs e r v i c e si nt h eg u a r a n t e e dq u a l i t yo fs e r v i c ec o n d i t i o n s e f f e c t i v e s t r a t e g i e so ft h ec o v e r a g ec o n t r o la n da l g o r i t h m sc a nb eu s e dt oo p t i m i z et h ea l l o c a t i o no f r e s o u r c e so fw s n s ，i n c r e a s et h ee f f i c i e n c yo ft h ee n e r g yu s a g eo fn e t w o r kn o d e s ，a n di m p r o v e t h ep e r c e i v e dq u a l i t yo fs e r v i c ea n dt h e o v e r a l ls u r v i v a lt i m e h o wt oc o m b i n ed i f f e r e n t e n v i r o n m e n t a ld e m a n d sa n dd e s i g nap r a c t i c a ls t r a t e g yf o rc o v e r a g ei sas i g n i f i c a n tr e s e a r c h f i e l d w i r e l e s ss e n s o rn e t w o r k si sat y p i c a lg r o u po fn e t w o r ks y s t e m ，w h o s ec o v e r a g ec o n t r o l p r o b l e mh a st h e c h a r a c t e r i s t i c so fs e l b o r g a n i z e dg r o u p s t h ep r e s e n tr e s e a r c hc o n s t r u c t sa w i r e l e s ss e n s o rn e t w o r kc o v e r a g eo p t i m i z a t i o ns t r a t e g yb a s e do ns w a r mi n t e l l i g e n c e f i r s t l y ，a s p e c i f i cc o v e r a g eo p t i m i z a t i o na l g o r i t h mm a k i n gu s eo ft h ee l e m e n t a r yp a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) a n dt h ee v o l u t i o no fm u l t i p a r t i c l ep a r t i c l es w a r mo p t i m i z a t i o n ( m p s o ) i s p r o p o s e d t h es h o r t a g e so ft h ea l g o r i t h m sa r es h o w nb ys i m u l a t i o n s ，i no r d e rt oc o v e rt h e s h o r t a g e so ft h e s et w oa l g o r i t h m s ，t h ev i r t u a l m a t e r i a lf o r c e d i r e c t e dp a r t i c l es w a r m o p t i m i z a t i o n ( v m f p s o ) i sp r o p o s e d ，t h ee x p e r i m e n t ss h o wt h ee f f e c t i v e n e s sa n ds u p e r i o r i t yo f t h en e w l yp r o p o s e da l g o r i t h m s t h em a i nr e s e a r c hw o r ka n dr e s u l t sa r ea sf o l l o w s ： 1 c o v e r a g eo p t i m i z a t i o ne x p e r i m e n t a ls i m u l a t i o ni sd e s i g n e db yu s i n ge l e m e n t a r yp s o a n d m p s o t h ee f f e c to fv a r i o u sp a r a m e t e r so nt h ec o v e r a g ep e r f o r m a n c ei sa n a l y z e da c c o r d i n gt o t h es i m u l a t i o nr e s u l t s c o m p a r e dw i t ht h ec o v e r a g eo p t i m i z a t i o ne f f e c to ft h et w oa l g o r i t h m s ， t h e i ri n a d e q u a c i e sa r ep o i n t e do u ta n dt h ei d e a sf o ri m p r o v e m e n ta r ep r o p o s e d 2 t h ev m f p s os t r a t e g yi sp r e s e n t e d ，w h i c hi n t e g r a t et h ee l e m e n t a r yp s oa n dv i r t u a l 浙江工业人学硕十学位论文 m a t e r i a lf o r c ea l g o r i t h m t h es i m u l a t i o ne x p e r i m e n to fv m f p s oi sc a r r i e do u tb y u s i n g t h et w o a l g o r i t h m su n d e rt h es a m ec o n d i t i o n s t h es i m u l a t i o n ss h o wt h a tt h ec o m b i n a t i o na l g o r i t h mh a s ab e t t e ro p t i m i z a t i o np e r f o r m a n c et h a nt h a to f t h ee l e m e n t a r yp s oo rm p s o 3 t of u r t h e rp r o v et h ee f f e c t i v e n e s so ft h ea l g o r i t h m ，t h ec o v e r a g eo p t i m i z a t i o ne f f e c to f t h ea b o v e - m e n t i o n e dt h r e e a l g o r i t h m si sa n a l y z e d t h ee x p e r i m e n t sd e m o n s t r a t et h a tt h e c o m b i n a t i o na l g o r i t h mo u t p e r f o r m st h a to ft h e e l e m e n t a r yp s o ，m p s o ，t h ec o n v e n t i o n a l g e n e t i ca l g o r i t h m ( c g a ) o rt h en e w q u a n t u mg e n e t i ca l g o r i t h m ( n q g a ) 4 t h ev m f p s oc o v e r a g eo p t i m i z a t i o ns t r a t e g yo fw i r e l e s ss e n s o rn e t w o r ki sd e s i g n e d b a s e do nt h ee x p e r i m e n t a ls i m u l a t i o no fp s oa n dm p s o i ti s p r o v e dt h a tt h ei m p r o v e d a l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h ep e r f o r m a n c eo fw s n st h r o u g hc o m p a r i n ga n da n a l y z i n g t h ed i f f e r e n to p t i m i z a t i o na l g o r i t h mr e s u l t su n d e rt h es a m ec o n d i t i o n s k e yw o r d s ：w i r e l e s s s e n s o r n e t w o r k s ，p a r t i c l es w a l mo p t i m i z a t i o n ，v i r t u a lm a t e r i a l f o r c e - d i r e c t e d ，p a r t i c l ee v o l u t i o n ，c o v e r a g eo p t i m i z a t i o n 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名： 日期：矽年t 月qe l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“”) 日期：。夕年岁月匕日 日期：哕年岁月q 日 方吃 ，妊0 魂钉 名名签签者师作导 浙江工业大学硕士学位论文 1 1 研究背景 第1 章绪论 无线传感器网络最早来源于军事领域，1 9 7 8 年卡内基梅隆大学就在美国国防高 级研究项目署的资助下成立了分布式传感器网络工作组，专门研究以无线传感器网络为基 础的军事监视系统n 2 1 。但是由于当时技术条件的限制，研究和应用的范围十分有限。进 入到2l 世纪，随着技术水平的大规模提高，当前对无线传感器网络的研究与开发已成为 目前信息领域的一个热点，在美国的移动计算和网络国际会议上，提出了无线传感器网络 是下一个世纪面临的发展机遇1 ，有越来越多的研究机构和公司正加入到这方面的研究工 作中来。 无线传感器网络是新一代的传感器网络，具有非常广泛的应用前景，其发展和应用将 会给人类的生活和生产的各个领域带来深远影响。无线传感网络一种典型的应用就是用来 监视一个区域，或者对区域中的某些特定位置进行观察。在传感器网络中，每个节点都有 一个很小的处理器和感应器，具有处理信息和无线通信的功能，节点可以收集节点的信息 并将处理结果传给数据汇集服务器，数据汇集服务器收集分析到的数据，判断在监视区域 是否发生重要的事件。由于传感器的作用范围都是有限的，为了让无线传感器网络能够完 成目标监测和信息获取任务，必须保证无线传感器节点的部署能有效的覆盖被监测的目标 或区域。因此，我们需要研究无线传感器网络的覆盖控制问题，即根据被监测的区域或目 标的分布情况，利用算法对传感节点的部署进行优化，保证传感器网络完全覆盖或以较大 概率覆盖被监测区域，并且尽量减少冗余和网络资源的浪费。 最优覆盖是无线传感器网络应用的一个基本问题，是提供监测和目标跟踪服务质量的 种度量。人们通常需要网络在完成监测任务的前提下，尽量节省能耗以延长网络寿命。 如何实现最优覆盖是网络拓扑管理的关键内容，能量高效和可靠监测两方面都直接相关， 在网络体系结构的层次上，它可视为网络层的研究范畴h 1 。覆盖反映了网络监测和实现目 标跟踪的质量效果，该问题已引起了业界越来越多的关注。 浙江工业大学硕士学位论文 1 2 研究目的 无线传感器网络最主要的任务就是监测物理环境，并将节点感知的信息转发到基站， 因此覆盖是无线传感器网络中的一个重要问题，它反映了网络所能提供的感知服务质量。 为了让无线传感器网络能够完成目标监测和信息获取的任务，必须保证无线传感器节点能 有效地覆盖被监测区域或目标。近年来，覆盖控制方面的研究工作在国内外都在积极展开， 取得了一定进展1 。优化无线传感器网络覆盖对于合理分配网络的空间资源，更好地完成 环境感知、信息获取等任务都具有重要的意义。 网络覆盖优化问题，可以看作是在传感器网络节点能量等资源普遍受限情况下，通过 传感器节点放置以及路由选择等手段，最终使无线传感网络的各种资源得到优化分配，进 而使感知、监视、传感、通信等各种服务质量得到改善。如何根据不同的应用环境需要， 对网络进行不同的覆盖控制就成了无线传感网络中一个基本但亟待解决的问题。为了更好 地解决覆盖优化问题，本论文通过改进粒子群算法来设计了w s n s 的覆盖优化算法，实 现无线传感节点的优化配置，达到无线传感器网络各种资源优化分配的目的。 1 3 国内外研究现状 近年来，无线传感网络覆盖控制方面的研究工作在国内外都取得了一定进展，现将近 些年来在这一领域中的研究成果进行总结、比较和分析。针对不同的应用，提出了不同的 覆盖控制算法。首先根据覆盖的分类，有区域覆盖、点覆盖和栅栏覆盖几种覆盖算法。 对于区域覆盖问题，提出了基于冗余节点判断的覆盖控制算法、基于采样点的覆盖控 制算法、基于不交叉优势集的覆盖控制算法、基于多重k 级覆盖控制算法、基于网络连通 性的覆盖控制算法。文献 6 提出了c o v e r a g e b a s e do f f - d u t ye l i g i b i l i t yr u l e 分布式算法，并 将该算法作为l e a c h 分簇协议的一个扩展进行了仿真实验，结果表明网络寿命较l e a c h 分 簇协议延长了1 7 倍，此算法适用于非单位圆问题和单位圆问题口1 。国内，蒋杰等人也利 用计算几何中v o r o n o i 图的性质，设计了一种基于目标区域v o r o n o i 划分的集中式近似算 法来判断冗余节点的存在，用于计算完全覆盖目标区域所需要的近似最小节点集随1 ，文献 9 又提出的一种基于概率覆盖模型的密度控制算法，能够在保证足够的网络覆盖能力的 前提下，关闭掉冗余节点，减少网络的总能量消耗。文献 1 0 将监测区域被所有的网格点所 代替，由此整个区域覆盖可被近似地看成点覆盖，从而把区域覆盖问题转化为集合覆盖问 题，该算法需要一个中心节点来执行，就会潜在的导致该节点的计算负担和网络瓶颈问题 一2 一 浙江工业人学硕十学位论文 的出现。h u a n g 设计了一种判断传感器节点周长覆盖的算法口1 ，用于计算确定的区域是否 能被k 个传感器节点覆盖，该算法可应用于定位、对环境监测能力要求较高或对容错能力 要求较高的环境。针对满足不同需求的覆盖度，提出一种网络配置协议( c c p ) 能动态的配 置网络，并将c c p 和s p a n n 2 1 协议相结合来保证网络的覆盖和连通性n 。g u pt ah 利用通 过选择连通的传感器节点路径来得到最大化的网络覆盖效果，分别设计了集中与分布式两 种贪婪算法n 3 1 。 针对点覆盖提出了基于不交叉优势集的覆盖控制算法。点覆盖就是要求离散的点目标 在任意时候至少被一个传感器覆盖。c a r d e i m 和d udz 将传感器节点划分成若干个不相 交的集合，每个集合能完全覆盖所有目标点n 钔。任意时刻只有一个传感器节点集合处于工 作状态，其他集合将依次被唤醒。由此可见，点覆盖的优化就是确定不相交集合的最大数， 就相应的延长了每个传感器两次激活的时间间隔，整个网络寿命也得到了延长。 针对栅栏覆盖提出了基于最差情形和最好情形的覆盖控制算法、基于暴露模型的覆盖 控制算法。m e g u e r d i c h i a ns 等人指出，如果某条路径上的每个点与最近节点的距离最大， 则该路径称为“最大突破路径”n 副。m e g u e r d i c h i a ns 提出了解决“最坏”和“最好 问 题的两种算法，为放置额外的传感器来改善覆盖提供了依据n 引。目标暴露覆盖模型控制算 法中，节点的感知能力随着距离的增加成指数衰减，被称为指数感知模型，并指出了随机部 署的传感器节点的感知模型的数学表达式n7 1 。 在上述的这些算法中，从感知模型分析，除了目标暴露覆盖模型控制算法采用指数感 知模型，其它都采用二进制感知模型，而这种模型不符合实际应用环境。从网络覆盖能力 上看，基于冗余节点判断的覆盖控制算法、基于采样点的覆盖控制算法、基于多重k 级覆 盖控制算法、基于网络连通性的覆盖控制算法、基于最差情形和最好情形的覆盖控制算法 较强。 其次在对覆盖问题算法的研究中，有很多是基于全局信息寻找次优结果的算法，这种 算法一般用于网络部署或者重部署。文献 1 8 使用线性规划技术选取最小活动节点集合来 保证覆盖性。作者使用二维和三维的点阵网格模型，提出使用整数线性规划解决在保证全 局覆盖情况下最小化传感器造价的问题，并且给出了设置适当节点位置的方法。文献 1 9 从理论和统计的、最好情况和最坏情况几个角度出发定义了覆盖问题，结合计算几何和图 论的方法对最坏和一般情况提出了覆盖计算的最优多项式时间算法。文献 2 0 提出了一种 对传感器网络中暴露计算的有效算法，该算法主要用来寻找最小暴露路径，对任意给定的 节点分布和密度模型，这种算法都能有效工作。在基于暴露的覆盖问题的最差情况下，最 浙江工业大学硕士学位论文 少暴露路径的计算就显得非常重要。文献 2 1 在发起区域概念的基础上提出了基于局部信 息计算来控制节点是否工作并保持完全覆盖的算法。该算法研究的是在节点部署后阶段如 何调度节点的工作以延长网络生存时间，但是该算法只是研究覆盖问题，并没有考虑连通 问题。文献 2 2 中定义了一个判断性的覆盖问题，目标是判断网络中的每一个点是否都在 k 个传感器的覆盖之下( k 是预先指定的值) 。它研究的是在被监测的区域或目标的分布情 况不同情况下的无线传感网络的覆盖优化问题。通过对传感器节点的部署优化，来保证传 感网络完全覆盖或以较大概率覆盖被监测区域，同时尽量减少冗余和网络资源的浪费。 要实现无线传感网络的覆盖，首先要保证其连通性，而连通覆盖与通信半径和感知半 径之间有着内在的关系。最早讨论这个问题的是文献 2 3 ，文中证明了如果通信半径大于 等于感知半径的两倍，那么传感器网络覆盖则保证网络的连通性。如果通信半径设置的太 大，无线通信会产生相互于，这样会大大降低网络的运行效率和生存时间。因此为了保证 网络的连通性，通信半径设置成感知半径的两倍是一个好的选择。在文献 2 3 的基础上进 一步对如下命题做出了严格证明乜引：在初始部署的网络是仁连通的条件下，“通信半径至 少是两倍感知半径”是肛覆盖保证一连通的充分必要条件。文献 2 5 利用数学建模的方 法，考虑一个单位区域平面中随机部署7 个传感器节点的情况下，传感器网络保证连通覆 盖的特性。作者假设感知半径和通信半径相等，得到传感器网络连通覆盖和网络直径与传 感器网络参数( 传感器数量、可靠性、感知半径、通信半径) 之间的数学关系。文献证明了 传感器网络保持连通覆盖的充分必要条件是若要使一个传感器网络保持连通覆盖，节点的 浓度必须很大。但是这样会导致节点过度冗余并带来通信数据的泛滥和无线通信干扰，大 大影响传感器网络的工作效率及生存时间。因此有必要对这些高密度的节点进行密度控 制，使一部分节点处于沉睡状态，同时保证网络的连通覆盖。 接着针对覆盖冗余问题，很多是借助图论或者最优化理论中的方法来寻找冗余传感器 节点的集合，这些算法主要分为分布式和集中式两大类。文献 2 6 考虑如何选择网络节点 的一个子集处于工作状态来节省能量的问题。他们尝试着把网络分成若干个不相交的子 集，每一个子集中的节点都能保证覆盖。然后，不同子集中的节点轮流进入工作状态，以 此来延长网络的生存时间。但是如何来选择最大数量的子集是n p 问题。虽然s 1i e p e e v i c 提出了解决这个问题的一个集中式算法啪1 。但是该集中式算法在大规模传感器网络中并不 具备可扩展性。文献 2 7 - 2 8 提出一个分布式的探测算法p e a s 。在p e a s 中，只有一部分 的传感器节点处于工作状态，而另外一部分节点处于节能的沉睡状态。处于工作状态的节 点一直工作着直到其能量消耗殆尽，处于沉睡状态的节点会每隔一个随机的时间醒来，探 浙江工业大学硕士学位论文 测其感知半径范围内是否有工作节点。若有，则继续进入睡眠状态；否则，它进入工作状 态。p e a s 的优点是算法简单，容易实现，缺点是它并不能保证网络的完全覆盖。文献 2 9 提出一个分布式的节点调度算法。这个算法把网络的生存时间分割成一轮一轮的。每一轮 中，传感器都根据其邻居节点的信息来判断自己需要重新进入睡眠状态。如果节点完全的 被其邻居节点所覆盖，则该节点是冗余的，可以重新进入沉睡状态；否则，此节点进入工 作状态。该算法就可以在保证网络的完全覆盖的前提下，利用节点冗余来实施调度算法， 合理安排节点工作时间。 最后随着2 0 世纪8 0 年代群体智能算法的出现，引起了多个学科领域研究人员的关注， 己经成为人工智能以及经济、社会、生物等交叉学科的热点和前沿领域。群体智能用群体 优势，在没有集中控制，不提供全局模型的前提下，为寻找复杂问题解决方案提供了新的 思路。对群体智能的定义进行扩展，有些学者把鱼群，蚁群，鸟群等自然界的群体运动都 理解为群智能活动，但普遍的理解主要有以下两种。一是由一组简单智能体涌现出来的集 体的智能，以蚁群优化算法和蚂蚁聚类算法等为代表；二是把群体中的成员看作粒子，而 不是智能体，以粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 为代表。 在近来无线传感网络的研究中，群体智能算法的应用越来越广。文献 3 0 利用遗传算 法实现覆盖优化，虽然遗传算法全局搜索能力强，且具有并行搜索能力，但在最优解附近 收敛速度慢，难以满足动态节点选择的实时性要求。文献 3 1 和文献 3 2 都提出一种基于 粒子群算法的无线传感网络覆盖优化方法，虽然证明粒子群算法能够有效实现无线传感网 络覆盖优化，但是标准粒子群算法在空间搜索时，容易陷入“早熟”现象，限制了粒子的 搜索范围。要想扩大搜索范围，就要增加种群的粒子数或者减弱粒子对当前种群搜索到的 全局最优位置的追逐，而增加粒子数将导致算法复杂度加大，减弱粒子对全局最优点的追 逐使得算法不易收敛。 基于上述讨论，群体智能算法的在无线传感网络的应用越来越广泛，实践证明它能够 有效实现网络覆盖优化，达到优化配置网络资源的目的。本论文的研究工作是以基本粒子 群算法为基础，通过改进和结合其它优化算法来设计无线传感网络覆盖优化算法，减少重 复覆盖，在兼顾全局搜索能力和局部搜索能力的平衡的基础上有效解决早熟问题，从而实 现无线传感器网络节点的优化配置，获得有限节点情况下的网络最大覆盖率。 浙江工业人学硕士学位论文 1 4 论文的组织结构 本论文共分五章，对w s n s 覆盖优化、粒子群算法的基本知识和所做的工作进行阐 述和说明。 第一章绪论；主要介绍项目的研究背景、目的和国内外研究现状，指出本论文的组织结 构。 第二章无线传感器网络覆盖问题；介绍w s n s 覆盖的类型、典型覆盖控制算法、优化数 学模型及问题描述、评价指标和标准。 第三章粒子群算法在无线传感网络覆盖优化中的仿真实验；简述基本粒子群算法和粒子 进化的多粒子群算法原理，设计覆盖优化仿真实验算法流程，得出计算机实验仿 真结果，分析各参数对覆盖优化性能的影响，对两种算法的覆盖优化结果进行分 析和比较，指出它们的不足之处，提出改进思路。 第四章w s n s 覆盖的拟物力导向粒子群优化策略研究；针对基本粒子群算法和粒子进化 的多粒子群算法的不足，引入拟物力算法，提出拟物力导向粒子群优化策略。把 该改进算法与基本p s o 、m p s o 的覆盖优化仿真结果进行比较，说明该改进算法 有更好的优化效果。为了进一步验证该算法的有效性，把p s o 、m p s o 、v m f p s o 与文献中提出的传统遗传算法( c g a ) 和新量子遗传算法( n q g a ) 在同样的条 件下进行仿真实验，并把他们的无线传感网络的覆盖优化性能进行比较和分析。 第五章结论与展望；简要回顾所做的工作，对所做工作进行总结，展望一下该方向的发 展前景。 浙江丁业大学硕士学位论文 第2 章无线传感器网络的覆盖问题 2 1 无线传感器网络覆盖类型 覆盖控制是无线传感器网络应用的一个基本问题，对网络覆盖的测量能够使我们了解 是否存在监测和通信盲区，了解被监测区域的无线传感器网络的覆盖情况，从而重新调整 传感器节点分布或者指导在将来添加传感器节点时可采取的改进措施。以通过调整网络覆 盖的密度，对被监测区域中重要区域设置热点，部署更多的传感器节点，保证测量数据的 可靠性。因此，网络覆盖有着很重要的意义，对网络性能有着直接的影响。 为了让无线传感器网络能够完成目标监测和信息获取的任务，必须保证无线传感器节 点能有效地覆盖被监测区域或目标。由于无线传感器网络是基于应用的网络，不同的应用 具有不同的网络结构与特性。因此无线传感器网络的覆盖问题也有着多种角度的分类方 式。 1 按配置方式分类 按照无线传感器网络节点不同配置方式( 即节点是否需要知道自身位置信息) ，可以将 覆盖问题分为确定性覆盖、随机覆盖两大类。 ( 1 ) 确定性覆盖 如果网络的状态相对固定或是环境己知，就可以根据预先配置的节点位置确定网络拓 扑情况或增加关键区域的传感器节点密度，这种情况被称为确定性覆盖问题。此时的覆盖 控制问题，就成为一种特殊的网络或路径规划问题。典型的确定性覆盖有确定性区域点 覆盖、基于网格的目标覆盖和确定性网络路径目标覆盖三种类型。 ( 2 ) 随机覆盖 在许多实际自然环境中，由于网络情况不能预先确定且多数确定性覆盖模型会给网络 带来对称性与周期性特征，从而掩盖了某些网络拓扑的实际特性。再加上网络自身拓扑变 化复杂，导致采用确定性覆盖在实际应用中具有很大的局限性，不能适用于战场等危险或 其他环境恶劣的场所。因此，需要进一步对节点随机分布在传感区域而预先没有得到自身 位置的情况进行讨论，这正是随机覆盖所要解决的问题。 2 按覆盖区域分类 一7 一 浙江工业大学硕士学位论文 按照无线传感器网络对覆盖区域的不同要求和不同应用，可以把覆盖问题分为区域覆 盖、点覆盖和栅栏覆盖三类。区域覆盖要求目标区域内的每个点至少被一个节点覆盖；点 覆盖考虑的是对若干离散目标点的覆盖；栅栏覆盖关注网络对移动目标的检测能力，要求 当某个移动目标沿任意路径穿越网络部署区域时，目标不被发现的概率最小。 3 按感知模型分类 传感器的感知能力很大程度上决定了传感器节点的覆盖情况，从而影响着整个网络的 覆盖性能。要研究无线传感器网络的覆盖问题，必须讨论其节点所配备的传感器感知模型 与特性。目前主要研究的有两类感知模型：二进制感知模型和指数感知模型。 ( 1 ) 二进制感知模型覆盖 一般情况下，大多数节点的感知范围是一个以节点为圆心，半径为其感知距离即探测 距离( 由节点硬件特性决定) 的圆形区域。只有在该圆形区域内的点，才能且一定被该节点 感知( 即被覆盖) ，否则不能被监测。通常情况下，目标在探测距离内被节点感知记为“l ， 超出探测距离而未被节点感知记为“0 ，因此也称此类覆盖为0 - 1 覆盖。在实际应用当中， 节点除了有圆形感知区域以外，还可能有其它规则或不规则的感知区域。 ( 2 ) 指数感知模型 节点探测到某一点处所发生的事件的概率与它们之间距离的删次方成反比，这样 的节点模型称为指数感知模型。在某些研究场合，特别是在考察运动目标时，指数感知模 型比较符合实际的情况，因此也受到人们的广泛关注。需要说明的是，目前使用的二进制 感知模型和指数感知模型并不能很好地全面反映传感器节点间的差异性和时间特性。设计 更多更实际的感知模型来实现无线传感器网络的覆盖算法是今后研究覆盖问题的一个重 要方向。 4 按目标特性分类 因为无线传感器网络收集的是目标区域或特定目标的信息，而不同的目标区域或目标 具有不同的物理特性，所以在覆盖控制算法的设计上需要考虑目标特性不同的情况。 ( 1 ) 静态目标覆盖 目标在网络监测期问是静止不动的，对于这样的目标的监测就属于静态目标覆盖。静 态目标覆盖是无线传感器网络覆盖问题中最普通的也是相对比较简单的情况。比如林区火 灾监测、温度监控等。在这种情况下，设计覆盖控制算法或协议是主要考虑的是覆盖的全 面性以及对覆盖冗余节点的处理等。 ( 2 ) 动态目标覆盖 浙江工业大学硕十学位论文 如何监测运动中的目标是动态目标覆盖应考虑的主要问题。因为目标的运动具有一定 的复杂性，如匀速运动与变速运动、直线运动与曲线运动等，对节点的感知能力以及网络 的覆盖控制会有各自不同的要求，在设计覆盖算法时应当全面考虑。如在战场中，对敌军 单兵运动的侦测和对敌军坦克运动的侦测是明显不同的，因为两者能被节点监测到的信号 在强度方面是有很大区别的。 2 2 典型无线传感网络覆盖控制算法分析 目前典型的覆盖控制算法有n o d es e l f - - s c h e d u l i n g 覆盖控制算法嘞1 、暴露穿越覆盖 控制算法m 3 、最坏与最佳情况覆盖控制算法5 1 三种，现对这三种算法进行以下分析。 1 n o d es e l f - - s c h e d u l i n g 覆盖控制算法 优点：该算法建立在圆形二进制感知模型的基础上，属于静态目标覆盖。它设计了专 门的机制避免出现节点休眠时网络出现覆盖盲点，因而可以在保持网络覆盖的充分性和全 面性情况下能有效控制网络节点的冗余，使得节点轮换工作，有效地延长了网络生存时间。 缺点：需要确定节点的位置信息并要求整个网络同时具有时间同步支持，增加了设备 成本和实现难度；无法使邻近边界区域的节点休眠，在一定程度上影响了整个网络的生存 时间的延长效果；节点轮换机制只能适用于传感器节点覆盖区域为圆周的情况，不适用于 不规则的节点感应模型；没有考虑对重点区域的覆盖控制，无法在网络需要多重覆盖的条 件下对节点进行轮换调度。 2 暴露穿越覆盖控制算法 优点：该算法属于随机覆盖、栅栏覆盖和动态目标覆盖三种类型。暴露覆盖模型更为 符合目标由于穿越w s n s 区域的时间增加而被检测概率增大的实际情况，在实际中能够 得到广泛的应用；采用分布式的算法执行方式，不需要预先知道整个网络的节点配置情况， 很好地降低了算法的计算成本，根据需要可以选择不同的感应强度模型和网格划分，从而 得到精度不同的暴露路径。 缺点：暴露精度与算法运行时间是矛盾的。较高的暴露精度要求更长的运算时间，将 会牺牲网络信息的实时性，减少运算时间必定要降低暴露精度，影响了网络检测的准确性， 因此两者需要平衡考虑。算法没有考虑实际中障碍、环境以及传感器节点本身运动等可能 造成的影响，应用受到一定的限制。 3 最坏与最佳情况覆盖算法 浙江工业大学硕士学位论文 该算法属于栅栏覆盖的一种。和暴露穿越覆盖类似，最坏与最佳情况覆盖也是考虑运 动目标通过监测区域时的检测问题。但是与暴露穿越覆盖不同的是，最坏与最佳情况覆盖 着重从距离和某些特殊路径上考察网络对目标的覆盖情况。 优点：在最佳与最差两种度量条件下，分别得到了临界的网络路径规划结果，可以指 导网络节点的配置来改进网络的整体覆盖性能，作为一种特殊的无线传感网络覆盖控制算 法，多适用于网络路径规划、目标观测等节点位置确定或已知的应用场所。 缺点：但是该算法采用集中式的计算方式，计算成本较高，并且需要预先知道各节点 的位置信息，限制了算法的应用；没有考虑实际中障碍、环境和噪声等可能造成的影响， 结论仅适用于均为同构节点的网络，不适用于网络中存在节点覆盖能力有差异的情况。 2 3 覆盖控制中的其他问题 除了考虑要覆盖所有的目标区域或者目标点以外，根据网络应用环境和设计的要求， 在研究覆盖控制问题的同时，经常需要同时对以下问题进行考虑：传感器节点的连通问题， 网络建设成本问题和能源控制问题等。 1 覆盖中的连通问题 为了将监测到的数据传送到s i n k 节点，每个传感器都要能够通过直接或者间接的方 式与s i n k 节点通信，因此，网络的连通性问题也是覆盖控制研究中要同时考虑的一个问 题，这里涉及到传感器的感应距离和通信距离的问题。如果节点的通信距离至少为感应距 离的2 倍，则对一个对凸多边形的覆盖意味着网络节点间的连通啪1 。这个结果意味着在区 域覆盖问题中，如果节点的通信距离至少为感应距离的2 倍，则在进行覆盖设计时就不需 要考虑连通性问题，但这个结果不适用于点覆盖问题。在点覆盖进行研究时考虑了一种特 殊情形，每个节点的通信距离都足够与s i n k 节点直接通信，在这种情况下，也不需要考 虑节点的连通问题。 2 网络的造价问题 在考虑造价问题时，要解决的问题是在满足覆盖和连通性要求的前提下，尽可能减少 所需节点数，使网络造价最小；或者使用几种有不同性能( 感应距离不同) 和价格的传感器， 如何计算他们的数量和部署的位置，在达到覆盖目标的同时，获得最少的网络造价乜5 1 。 3 覆盖中的节能问题 人们常常关心在保证对目标点或区域监视质量的同时，如何延长网络生存时间。为了 浙江工业大学硕士学位论文 提高随机网络的可靠性和监测数据的准确性，通常使用大量节点进行高密度部署。由于节 点密度高，某个点或某个区域往往同时被多个节点覆盖，称为“覆盖冗余”。如果所有节 点都保持工作状态，当某一事件发生时，所有监测到该事件的节点都试图向基站发送数据。 这些数据包含了大量的冗余内容，对网络性能、节点能耗都会造成负面影响。一方面，由 于无线传感器网络采用多跳通信方式，这些冗余数据将造成中间转发节点额外的能量消 耗；另一方面，大量节点同时发送数据会导致无线传输干扰和介质征用冲突，进一步导致 额外能量消耗。考虑到小体积、低成本的传感器节点往往采用电池等易耗尽能源提供能量， 这样的冗余数据将会极大地缩短整个网络的生存时间。为了尽可能地减少冗余数据导致的 额外能量消耗，延长网络生存时间，需要对随机部署的网络的拓扑进行优化控制，在保持 覆盖性能的前提下，减少工作节点数。 针对这一问题，一种解决办法是将高密度部署的节点划分成若干互不相交的节点集 合。每个节点集合都能维持目标区域或目标点的原始覆盖质量，通过轮换每个集合的工作 时间，在任意时刻只有一个节点集合处于工作状态，从而延长整个网络的生存时间。显然， 网络的生存时间与这样的节点集合数成正比。 另一种解决方法是消除或者减少节点的覆盖冗余。如果一个节点的感知区域完全被邻 居节点的覆盖区域包含，那么关闭该节点不会导致网络覆盖性能下降。问题的关键是节点 如何仅仅依赖局部邻居节点的信息，自主判断是否属于覆盖冗余。为此，需要设计分布式、 局部化的冗余覆盖检测算法。 2 4 传感器节点感知模型 传感器节点的感知模型直接决定了其覆盖范围和监测能力。在无线传感器网络研究 中，目f j 主要使用两种感知模型：二元感知模型和概率感知模型。 1 二元感知模型 在二维平面上，传感器节点的覆盖范围是一个以节点为圆心，半径为尺。的圆形区域。 该圆形区域称为传感器节点的“感知圆盘”，r ，称为传感器节点的感知半径，由节点感知 单元的物理特性决定。假设节点s 的坐标为( t ，y ，) 。在二元感知模型中，对于平面上任 意一点p ( x ，y ，) ，节点s 检测到点尸发生的事件的概率为： 浙江工业大学硕士学位论文 p ，( j ，p ) ：j 1竺景d ( s ，p ) r s ( 2 一1 ) 尸，( 卵i1o 其他 q 。1 ) 其中，d ( s ，p ) = o s 2 一工p 2 ) + ( j ，s 2 一y p 2 ) 为点尸和节点s 之间的欧氏距离汹1 。类似地，在二元 感知模型中节点在三维空间中的感知范围是一个以节点为中心，足为半径的球形区域。 2 概率感知模型 二元感知模型假定传感器节点对事件的检测是确定的。在实际应用环境中，由于环境 噪声干扰以及信号强度随传输距离衰减，传感器节点的检测能力表现出一定的不确定性， 概率感知模型反映了这种不确定性。在概率感知模型中，传感器节点s 检测到任意点尸处 发生的事件的概率为： p ，( s ，p ) = p a d ( s ，p ) ( 2 2 ) 其中，d ( s ，p ) 为节点s 与事件发生点p 之间的欧氏距离，参数a 表示节点的感知能力以及 信号随距离的衰减程度 蚰3 。显然，只有当d ( s ，p ) = 0 时，检测概率p r ( s ，p ) = 1 。z o u 对 概率检测模型式( 2 2 ) 进行了修正叫2 1 ： 0 ，+ r p d ( s ，