（计算机应用技术专业论文）无线传感器网络覆盖和连通算法的研究.pdf

南京邮电人学硕上研究生学位论文摘要 摘要 无线传感器网络在军民用领域有着广阔的应用前景，是目前学术界研究的热点之一。 它综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，能够协作 完成实时监测、传感和采集目标对象的信息，并对其进行处理，从而传送给需要信息的用 户。 在无线传感器网络中由于传感器节点的分布通常具有随机性和密集性，监测区域会出 现覆盖盲区或者多重覆盖。同时，传感器节点之间信息的通信也是评价网络性能的主要指 标之一。因此，无线传感器网络的覆盖部署策略与连通方式是无线传感器网络中基本且必 须解决的问题。它们直接关系到传感器网络节点能量、尢线网络通信带宽、网络计算处理 能力等受限资源的优化分配。同时对无线传感器网络感知、监视、传感、通信等各种服务 质量目标的改善具有重要作用。 本文推导出了在无线传感器网络最优覆盖模型下，所使用的最少节点个数的计算公 式。对于遗传算法中的适应度函数公式做了改进，将覆盖度和多重覆盖度的组合作为适应 度函数。根据遗传算法的相关内容和流程图，利用遗传算法对覆盖策略做了仿真模拟，并 证明了所选用的方法的正确性和优越性。根据遗传算法所得到的节点分布图，采用分簇的 方法，通过寻找可作为簇首的最优节点实现了节点间连通。最后，对于国内研究甚少的三 维覆盖算法做了一定的介绍。 关键字：无线传感器网络，覆盖，连通，节点，遗传算法 南京邮电大学硕一t r 研究生学位论文 a b s t r a c t a b s t r a c t w s n ( w i r e l e s ss e n s o rn e t w o r k s ) c a nb ew i d e l yu s e di nt h em i l i t a r ya n d c i v i la p p l i c a t i o n ，i ti s ah o tr e s e a r c h s p o t a l s o ，i t h a ss y n t h e s i z e ds e n s o rt e c h n i q u e s ，e m b e d d e dc o m p u t a t i o n s ， d i s t r i b u t e di n f o r m a t i o np r o c e s s i n ga n dw i r e l e s sc o m m u n i c a t i o n w s nc a l lc o o p e r a t et oc o m p l e t e t h er e a l - t i m em o n i t o r i n g ，s e n s i n g ，c o l l e c t i n go ft h e o b je c t i v ei n f o r m a t i o n , t h e n c a r r i e so n p r o c e s s i n gt ot h eg a t h e r i n gi n f o r m a t i o na n dt r a n s m i t si tt ot h eu s e r a ss e n s o rn o d e si nw s na l eu s u a l l yd i s t r i b u t e dr a n d o m l ya n dd e n s e l y , t h i sm a ya r i s et o c o v e r a g eh o l e sa n dc o v e r a g e o v e r l a po fs e n s i n gr a n g e s s e c o n d l y , i n f o r m a t i o nc o m m u n i c a t i o n s b e t w e e ns e n s o rn o d e sa r ea l s oo n eo fe v a l u a t i n gn e t w o r kp e r f o r m a n c ei n d e x s ot h ec o v e r a g e d e p l o y m e n ta n dc o n n e c t i v i t yd i r e c t l ya f f e c tt h ee n e r g y - e f f i c i e n c y , c o m m u n i c a t i o n - b a n d w i d t ha n d p r o c e s s a b i l i t yw h i c h a r ea l ll i m i t e di nw s n t h e ya l s od e t e r m i n et h ei m p r o v e m e n to ft h eq o so f a p p e r c e p t i o n ，s u r v e i l l a n c e ，s e n s i n ga n dc o m m u n i c a t i o ni nw s n t h i sp a p e rd e d u c e st h ef o r m u l ao fc a l c u l a t i n gt h ef e w e s tn o d en u m b e ri nt h eb e s tc o v e r a g e m o d e li nw s n i ti m p r o v e st h ef i t n e s sf u n c t i o no fg e n e t i ca l g o r i t h m ，a n dp u t sc o m p o s i t i o no ft h e o v e r - l a pr a t ea n dc o v e r a g er a t e a st h ef i t n e s sf u n c t i o n t h i sp a p e ru s e sg e n e t i ca l g o r i t h mt o s i m u l a t et h ec o v e r a g es t r a t e g y , a n dp r o v e st h ec o r r e c ta n ds u p e r i o r i t yo ft h em e t h o db ec h o s e n i t u s e st h em e t h o do fd i v i d i n gc l u s t e rt oc h o o s et h em o s ts u i t a b l en o d e s 粥c l u s t e rh e a d s s o 嬲t o s o l v et h ep r o b l e mo fc o n n e c t i v i t yb e t w e e nn o d e s a tl a s t , t h i sp a p e rb r i e f l yi n t r o d u c e s t h e t h r e e - d i m e n s i o nc o v e r a g e k e y w o r d s w i r e l e s ss e n s o rn e t w o r k ( w s n ) ，c o v e r a g e ，c o n n e c t i v i t y , n o d e ，g e n e t i ca l g o r i t h m l l 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：盔遂日期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：基鱼塾导师签名： 期： 南京邮电人学硕士研究生学位论文第一章绪论 第一章绪论 1 1 论文的背景及研究现状 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 最早来源于军事领域，1 9 7 8 年卡内 基一梅隆大学在美国国防高级研究项目组( d a r p a ) 的资助下成立了分布式传感器网络工作 组，专门研究以无线传感器网络为基础的军事监视系统。但是由于当时技术条件的限制， 研究和应用的范围十分有限，直到2 0 世纪9 0 年代初期才正式发展成为一种新兴的信息获 取技术。进入2 1 世纪，随着技术水平的提高，无线传感器网络发展成为当前国际上备受 关注的、由多学科高度交叉的新兴前沿研究热点领域。它是传感器技术、嵌入式计算技术、 现代网络及无线通信技术、分布式信息处理技术等技术的综合应用。有越来越多的研究机 构和公司正加入到这方面的研究工作中来。 国外对无线传感器网络研究较早，在各方面取得了一定的成果，部分已经进入商用阶 段。2 0 0 3 年美国技术评论认为有十种新兴技术在不远的将来会产生巨大影响，这些 技术是全新的，很快就可以改变计算、医疗、制造、运输和能源基础设施，无线传感器网 络就是其中新兴技术之一。无线传感器网络有着广阔的应用范围，在国家安全、环境监测、 交通管理等领域具有重大的应用价值，因而引起了军界、工业界和学术界的高度关注。目 前，已经开发出的实际可用的传感器节点平台和面向无线传感器网络的操作系统。比较具 有代表性的传感器节点包括u cb e r k e l e y 大学和c r o s s b o w 公司联合开发的m i c a 系列节 点，i n t e lm o t e 口1 公司开发的节点等。而传感器网络操作系统中比较著名的操作系统有u c b e r k e l e y 大学开发的t i n y o s b l 系统，c o l o r a d o 大学开发的m a n t i s h l 等。 在国内，国家自然科学基金委员会在2 0 0 3 、2 0 0 4 年都设立了无线传感器网络相关研 究课题。2 0 0 4 年3 月，中科院和香港科技大学成立了联合实验室，开展传感器网络的研究 工作。但是总的来说目前还只能算是刚刚起步，处于研究的初级阶段。究其原因，很重要 的一个因素就是无线传感器网络对微电子的技术和工艺要求较高，从而制约了国内的研究 和发展。对于传感器网络的研究多数工作集中在协议、系统的设计以及算法的性能研究上。 南京邮电大学硕f j 研究生学位论文第一章绪论 1 2 论文研究目的和意义 1 2 1 无线传感器网络的概述 无线传感器网络打破了传统的点对点数据信息交互方式，提出了一种崭新的分散信息 交换模式，实现了物理世界、计算世界以及人类社会三元世界的连通。无线传感器网络在 环境恶劣、无人职守、资源受限的环境中显示了很大的应用价值。1 无线传感器网络由大量体积小、成本低、具有无线通信、传感、数据处理的传感器节 点以自组织方式构成。每个传感器节点构成了网络的硬件基础。传感器节点具备三个功能： 首先，作为现场信息采集单元要完成信息的采集并按要求对采集到的信息进行适当的预处 理，因此节点包括数据采集模块及数据预处理模块；其次，传感器节点还具有信息转发功 能，将采集到的现场信息通过一定的方式传输到其他节点或信息处理中心，因此节点还必 须包括通信模块来完成信息的接收、传递等；最后，当节点要实现某种控制作用时，还需 要有控制模块。 如图i - i 描述的是一个无线传感器网络工作的结构图，该网络由传感器节点、接收发 送器( s i n k ) 、通信卫星、任务管理节点等部分构成晴1 。在传感器网络中，大量传感器节点 是任意散落在被监测区域内。各个传感器节点以自组织形式构成网络，通过多跳中继方式 将所探测到的有用信息通过初步的数据处理和信息融合之后，传到s i n k 节点或基站，最 终借助长距离或临时建立的s i n k 链路将整个区域内的数据传送到远程中心或最终用户， 进行集中处理。 轴嗍i - 喇孓恻n 蜘 图i - i 个典型的无线传感器网络结构图 随着传感器尺寸不断缩小和价格不断降低，可以通过增加传感器数量来提高网络的可 2 南京邮电大学硕士研究生学位论文第一章绪论 靠性；另一方面，传感器趋向于通过无线网络通信，而无线网络的带宽远远小于有线网络。 这些变化给无线传感器网络设计带来了新的课题。具体表现为：第一，集成数据量大大增 加；第二，无线通信带宽减少：第三，单个传感器单元的能耗必须大大降低；第四，环境 更加恶劣，导致网络连接不可靠，增加了输入数据的错误率。 1 2 2 无线传感器网络的特点 无线传感器的各种网络协议和应用系统，和传统网络相比，具有以下几方面的特点： ( 1 ) 超大规模的监测范围和节点数量：为了获得物理世界的精确信息，通常在被监测 区域部署大量的传感器节点，传感器节点的数量可能达到成千上万，甚至更多。传感器网 络的超大规模包含两方面的含义：一方面是传感器节点分布在很大的地理区域范围内，如 森林火灾监护和环境监测等；另一方面是为了提高数据精度，节点部署一般比较密集，并 且存在大量的冗余节点，以期获得精确的监测效果。 ( 2 ) 网络自组：网络的布设和展开不需要依赖于任何预设的网络设施，节点通过分层 协议和分布式算法协调各自的行为，节点启动后就可以快速、自动地组成一个独立的网络。 由于传感器节点容易失效，传感器的计算资源很有限，难以处理巨大的实时数据流或者增 加监测精度时候需要弥补失效节点，及时补充一些节点到网络中，因此，网络需要在恶劣 的环境具有自动配置与容错的能力。 ( 3 ) 硬件资源有限：无线传感器网络是在数字电路技术基础上发展起来的，传感器节 点各部分集成度很高。嵌入式处理器和存储器都具有计算能力，可以完成一些信息处理工 作。但是，由于嵌入式处理器的处理能力和存储器容量是有限的；其次，无线传感器网络 是由大量的传感器节点组成的，单个节点成本直接影响到网络的总体成本；每个节点也受 价格、体积和功耗的限制。由于以上条件的限制，传感器节点计算能力、程序空间和内存 空间比普通计算机功能要弱很多。这一点决定了在节点操作系统设计中，协议层次不能太 复杂。 ( 4 ) 电源容量有限：传感器节点由电池供电，电池的容量一般不是很大。其特殊的应 用领域决定了在使用过程中，很难给电池充电或更换电池，一旦电池能量用完，这个节点 也就失去了作用( 节点失效) ，关键时刻会造成巨大的损失。因此在传感器网络设计过程 中，任何技术和协议的选用都要以节能为首要条件，尽量提高网络的使用寿命。 ( 5 j 网络动态拓扑性：无线传感器网络是一个动态的网络，有些节点可以随处移动i 南京邮电入学硕士研究生学位论文第一章绪论 有些节点可能会因为电池能量的耗尽、环境因素或其他故障而失效，从而退出了网络；有 些节点也可能由于工作的需要而被添加到网络中。以上这些都可能使网络的拓扑结构随时 发生变化，因此网络应该具有可重构和自调节性。 ( 6 ) 以数据为中心的网络：由于传感器节点多是随机部署，构成的网络和节点编号之 间的关系是动态的，表现为节点编号和节点位置没有直接的关系。无线传感器网络不像传 统的网络以连接为中心，而是以数据为中心的网络，因此需要节点进行数据聚合、融合、 缓存和压缩等处理。 根据对无线传感器网络特点的分析表明，w s n 是由一组传感器节点以a dh o c 方式构成 的无线网络，但又不同于传统的有线网络和无线a dh o c 网络，w s n 节点一般部署在“不可 达的环境中而很少对其进行移动，如恶劣的地形、灾难地域或敌方控制的军事区等。所 以在传感器节点部署时，大部分是采取随机部署的方式。同时，由于小体积、低成本的传 感器节点往往采用易耗尽能源的电池提供能量，这样的冗余数据将会极大地缩短整个网络 的生存时间。为了尽可能地减少冗余数据导致的额外能量消耗，延长网络生存时间，需要 对随机部署网络的拓扑结构进行优化控制，在保持覆盖性能的前提下，减少工作节点数。 针对以上问题一种解决办法是将高密度部署的节点划分成若干互不相交的节点集合， 每个节点集合都能维持目标区域或目标点的原始覆盖质量，通过轮换每个集合的工作时 间，在任意时刻只有一个节点集合处于工作状态，从而延长整个网络的生存时间。显然， 网络的生存时间与这样的节点集合数成正比。而研究无线传感器网络的目的是协作感知、 采集和处理网络所覆盖的地理区域中被感知对象的信息，并发布给监测中心，从而提供了 一种跟踪环境数据的新方式。因此，如何选取工作节点，才能保证网络覆盖质量和节点之 间信息通信是我们着重要研究的问题。 1 2 3 无线传感器网络研究的意义 微电子机械系统( m i c r oe l e c t r om e c h a n i c a ls y s t e m ，简称m e m s ) 支持下的微小传感 器技术和节点间的无线通信能力为无线传感器网络赋予了广阔的应用前景，主要表现在军 事、环境、健康、家庭和其他商业领域。当然，在空间探索和灾难拯救等特殊领域，无线 传感器网络也有其得天独厚的技术优势。 ( 1 ) 军事领域：该领域的应用需求是无线传感器网络产生的主要推动力量。对无线传 感器网络最早进行研究的是美国军方。在未来，无线传感器网络将会成c 4 i s r t ( c o m m a n d ， 4 南京邮电大学硕士研究生学位论文第一章绪论 c o n t r o l ，c o m m u n i c a t i o n ，c o m p u t l n g ，i n t e l l i g e n c e ，s u r v e i l l a n c e ，r e c o n n a i s s a n c ea n d t a r g e t i n g ) 系统不可或缺的部分嘲。c 4 i s r t 系统的目标是利用先进的高科技技术，为未来 的现代化战争设计一个集命令、控制、通信、计算、智能、监视、侦察和定位于一体的战 场指挥系统。因为无线传感器网络一般是由密集型、低成本、随机分布的节点组成的，自 组织性和容错能力使其不会因为某些节点在恶意攻击中的遭到损坏而导致整个系统的崩 溃，而且整个无线传感器网络还有无需外界配置管理的自组织特性，这些特点是传统的传 感器技术所无法比拟的。也就是因为这些特点，使得无线传感器网络易于快速部署，非常 适合应用于恶劣的战场环境中，可以提供监控敌军兵力、装备和物资，监视冲突区，侦察 敌方地形和布防，定位攻击目标，评估损失，侦察和探测核、生物和化学攻击等功能，及 时准确地将采集到的各种信息，通过汇聚节点将数据传送到各级指挥部门，最后融合成为 决定战场胜败的完备的及时更新的战区信息库，为指挥决策提供及时准确的信息。 ( 2 ) 环境科学：随着人们对于环境的日益关注，环境科学所涉及的范围越来越广泛。 通过传统方式采集原始数据是一件困难的工作。无线传感器网络为野外随机性的研究数据 获取提供了方便。比如，跟踪候鸟和昆虫的迁移，研究环境变化对农作物的影响，监测海 洋、大气和土壤的成分等。a l e r t 口1 系统中就有数种传感器来监测降雨量、河水水位和土壤 水分，并依此预测爆发山洪的可能性。类似地，无线传感器网络对森林火灾准确及时的预 报是有极大帮助的。此外，无线传感器网络也可以应用在精细农业中，以监测农作物中的 害虫、土壤的酸碱度和施肥状况等。 ( 3 ) 医疗健康：如果在住院病人身上安装特殊用途的无线传感器节点，如心率和血压 监测设备，利用无线传感器网络，医生就可以随时了解被监护病人的病情，进行及时处理， 还可以利用无线传感器网络长时间地收集人的生理数据，这些数据在研制新药品的过程中 是非常有用的，而安装在被监测对象身上的微型传感器不会给人的正常生活带来太多的不 便。此外，在药物管理等诸多方面，它也有新颖而独特的应用。总之，传感器网络为未来 的远程医疗提供了更加方便、快捷的技术实现手段。 ( 4 ) 空间探索：探索外部星球一直是人类梦寐以求的理想，借助航天器布撒的无线传 感器网络节点实现对星球表面长时间的监测，应该是一种经济可行的方案。美国国家宇航 局的j p l ( j e tp r o p u l s i o nl a b o r a t o r y ) 实验室研制的s e n s o rw e b s 就是为将来的火星探测 进行技术准备的，已在美国佛罗里达宇航中心周围的环境监测项目中进行测试和完善。无 线传感器网络的出现与应用将会推动人类太空事业的发展，加速人类空间探索的进程。 ( 5 ) 其它领域：自组织、微型化和对外部世界的感知能力是无线传感器网络的三大特 点，这些特点决定了无线传感器网络在商业领域也有不少的应用机会。比如，嵌入家具和 s 南京邮电人学硕士研究生学位论文 第一章绪论 家电中的传感器与执行机构组成的无线网络连接在一起会为我们提供更加舒适、方便和具 有人性化的智能家居环境。此外，还可以在城市车辆监测和跟踪系统中采用无线传感器网 络。德国某研究机构正在利用无线传感器网络技术为足球裁判研制一套辅助系统，以减少 足球比赛中越位和进球的误判率。在灾难拯救、仓库管理、交互式博物馆、交互式玩具、 工厂自动化生产线等众多领域，无线传感器网络也将会孕育出全新的设计和应用模式。 通过上述领域w s n 的应用可知，无线传感器网络与我们的日常生活、科学研究等方面 具有越来越紧密的联系。为了能够使传感器节点完成目标监测和信息获取的任务，必须保 证无线传感器节点能有效地覆盖被监测的区域或目标。无线传感器网络的覆盖问题是提供 监测和目标跟踪服务质量的一种度量。给定一个传感器网络，w s n 覆盖控制也可以一般性 地总结为通过各个传感器节点协作从而达到对监视区域的不同管理或感应效果。随着无线 传感器网络应用的普及，更多研究工作深入到其网络配置的基本理论方面，覆盖问题是无 线传感器网络设计和规划需要面i 临的基本问题之一。覆盖问题是在传感器网络节点能量、 无线通信带宽、网络计算处理能力等资源普遍受限情况下，通过网络传感器节点放置策略 以及路由选择等手段，最终使各种资源得到优化分配，进而使感知、监视、传感、通信等 各种服务质量得到改善。所以，如何部署传感器网络节点，在保证一定的服务质量( q o s ) 条 件下，达到网络覆盖范围最大化。如何有效地覆盖，保证在满足“覆盖要求 的同时减少 覆盖盲区和能量空洞，延长网络的使用寿命，并且使用的节点数目最小是传感器网络应用 中研究的重要问题。 对于网络连通性问题的研究，主要有两种机制：一种是通过节点状态调度，选取骨干 节点构建活动节点网络，并保证网络连通性，进行数据路由。另一种是功率控制，即在保 证网络连通的前提下，动态调整每个节点的发射功率，减少节点能量消耗，实现节点之间 以多跳方式进行数据转发。k i r o u s i s 等人将此问题简化为发射范围分配问题并详细讨论 了其计算复杂性阳1 ，c o w p o w 阳1 的基本思想是所有节点使用一致发射功率，在保证网络连通 的前提下，使节点功率最小化。l i n t ( 1 0 c a li n f o r m a t i o nn ot o p o l o g y ) 和l i l t ( 1 0 c a l i n f o r m a t i o nl i n k - s t a t et o p o l o g y ) n 们是基于节点度数的算法。但是上述工作并没有考 虑监测区域覆盖的问题。本文最大的优点是：首先无线传感器网络达到了我们的覆盖要求 和有效的覆盖质量；其次，保证传感器节点间的连通问题就是我们要解决的。这样，覆盖 和连通将同时满足，提高了研究工作的可用性，覆盖和连通可以完美的结合。既可以使在 覆盖度达到最高的前提下节点数量最少，又可以使此通信网络相互连通。 6 南京邮电大学硕士研究生学位论文第一章绪论 1 3 论文研究内容与结构 国内外一些专家学者对无线传感器网络的覆盖和连通提出各种算法理论。在文献 1 1 ，1 2 中提出求解最大覆盖集的方法，将所有的传感器节点分成若干个不相交的覆盖集 ( c o v e rs e t ) ，每个集合中的节点都可以独立地完成区域监测任务，这些集合中的节点按轮 次顺序执行区域监测任务。在文献 1 1 中，s l i j e p c e v i c 等人证明了计算最大的覆盖集是 一个n p 完全问题，文献 11 ，1 2 3 分别提出m o s t - c o n s t r a i n e d 、1 e a s t c o n s t r a i n i n g 算法 和基于g r a p h c o l o r i n g 近似算法。文献 1 1 ，1 2 提出的算法都是集中式的，并不适合大量 随机抛洒传感器节点的状况。 本课题所研究的无线传感器网络覆盖策略，直接关系到传感器网络检测性能的好坏， 同时关系到传感器网络的资源利用、网络部署、网络生存时间等根本性问题。对于无线传 感器网络节点的部署以及提高网络的服务质量也具有重要的作用，从而可以更好的完成目 标监测跟踪和信息传输任务。本文首先用遗传算法对w s n 优化覆盖策略，用最少的节点使 监测区域的覆盖率达到最大，尽力减少覆盖盲区。如果只考虑到最少节点和最高覆盖度， 而不顾节点能否能够和s i n k 节点进行通信，用遗传算法计算出的节点部署策略将很难工 作。因此，课题还对用遗传算法比较靠近最优解的部署情况进行研究，保证能够得到最高 连通度。通过对传感器节点多重覆盖度、监测区域的覆盖度、节点的连通度综合考虑来达 到最优部署。以上几点分析都是基于二维平面覆盖模型研究的。三维空间的无线传感器网 络覆盖至今在国内研究甚少，但对于三维模型的研究也将成为一种趋势。文章第五章对三 维空间覆盖做了一定的研究。 以下是各章节所阐述的主要内容： 第一章：绪论。主要介绍了无线传感器的研究背景，研究该课题的意义，以及目前国 际上的研究现状。无线传感器网络的特点，论文的主要研究内容和组织结构等。 第二章：无线传感器网络覆盖和连通的概述。主要是介绍无线传感器网络覆盖控制算 法的分类，对有些典型的覆盖和连通算法协议进行比较，并做了一定的分析。对于传感器 网络的部署模型、节点的感知和通信模型做了研究。 第三章：基于遗传算法的无线传感器网络覆盖控制。本章介绍了遗传算法的相关内容。 对无线传感器网络最优覆盖模型做了分析，并推导出了计算最优模型节点个数的公式。根 据所提出的适应度函数等公式，利用遗传算法对于覆盖策略做了仿真模拟。最后对仿真数 据进行了分析，并与以往的方法所得的结果做了比较，证明所选用方法的正确和优越性。 7 南京由口电大学硕上研究生学位论文第一章绪论 第四章：无线传感器网络连通问题的研究。针对第三章运用遗传算法所得到的网络节 点覆盖图利用分簇的方法做了连通性研究。根据给定的簇首通信半径寻找簇首节点的位 置，找出可以用来充当簇首的节点，从而通过簇首节点与s i n k 节点进行通信。 第五章：三维空间覆盖算法的研究。本章通过二维覆盖延伸到三维覆盖空间覆盖，分 析了二维平面覆盖问题分析三维空间覆盖以及把三维空间的覆盖度转化为二维问题来解 决算法，并针对算法提出作者自己认为可以改进的思路。 第六章：总结和展望。主要对全文进行了总结，并提出了未来的研究工作。 南京邮电大学硕士研究生学位论文第二章无线传感器网络覆盖和连通的概述 第二章无线传感器网络覆盖和连通的概述 2 1 无线传感器网络覆盖控制概述 无线传感器网络覆盖控制是无线传感器网络应用的一个基本问题，即在保证一定的服 务质量( o o s ) 条件下，如何达到网络覆盖范围最大化，提供可靠的监测和目标跟踪服务。 对网络覆盖的测量能够使我们了解是否存在监测和通信盲区，了解被监测区域的无线传感 器网络的覆盖情况，从而重新调整传感器节点分布或者指导在将来添加传感器节点时可采 取的改进措施。通过调整网络覆盖的密度，对被监测区域中重要区域设置热点，部署更多 的传感器节点，保证测量数据的可靠性。因此，网络覆盖有着很重要的意义，对网络性能 有着直接的影响。为了让无线传感器网络能够完成目标监测和信息获取的任务，必须保证 无线传感器节点能有效地覆盖被监测区域或目标。近年来，w s n 覆盖控制方面的研究工作 在国内外都取得了一定进展。 无线传感器网络覆盖控制问题，按照不同的要求可以分成不同的种类：根据节点的部 署情况( 即节点是否需要知道自身位置信息) 又可分为确定性覆盖和随机性覆盖。确定性覆 盖的w s n 状态相对固定或是w s n 环境已知，并且可以根据预先配置的节点位置确定网络拓 扑情况或增加关键区域的传感器节点密度。此种覆盖类型需要对网络的物理环境有预先的 了解，根据节点位置来确定网络拓扑结构的，通常适用于工业控制、智能家居等应用中： 随机部署方式通常用于危险或恶劣的环境，即人类很难到达的场所，用飞机空中抛洒节点 等方式进行部署，随机部署是在网络预先不知道节点位置的条件下，完成对监测区域的覆 盖任务。 根据传感器节点是否具有移动能力可分为静态网络覆盖和动态网络覆盖。针对静态无 线传感器网络的覆盖问题，根据覆盖对象的不同可以分为区域覆盖( a r e ac o v e r a g e ) 、点 覆盖( p o i n tc o v e r a g e ) 和栅栏覆盖( b a r r i e rc o v e r a g e ) i t 3 。区域覆盖是目前研究最多的一 种，此时w s n 主要用于监测某个区域，即目标区域的每个点至少被一个传感器节点覆盖， 同时还要保证网络内各节点的通信连通。如图2 - 1 ( a ) 所示，假定目标区域为一规则矩形 区域，图中黑色实心节点形成一组处于激活状态的工作传感器集合，而圆圈状的节点则表 示处于休眠状态的，其监测区域能覆盖整个矩形；点覆盖则是只需要对目标区域一组给定 离散地点的覆盖，图2 1 ( b ) 中，黑色传感器节点覆盖了组用小正方形代表的目标点， q 南京邮电大学硕士研究生学位论文第二章无线传感器网络覆盖和连通的概述 黑色实心节点可以完全覆盖所给定的离散地点；栅栏覆盖如图2 一l ( c ) 是考察目标穿越被无 线传感器网络监测的某一区域时，被节点监测到或是没有被监测的情况，这种覆盖类型主 要用在战场环境中，用来监测敌军的车辆、坦克或士兵是否正在穿越监测区域。 辫 o 图2 - 1 ( a ) 区域覆盖图2 - 1 ( b ) 点覆盖图2 1 ( c ) 栅栏覆盖 按照目标特性进行分类分为静态目标覆盖与动态目标覆盖，这两者的区别是根据目标 在网络监测期问是否静止而区分的。静态目标覆盖是比较普通的一种，比如温度监控、环 境观测等，设计此类控制算法或协议主要考虑覆盖的全面性以及对覆盖冗余节点的处理 等；动态目标覆盖的目标是运动的，具有一定的复杂性，如匀速运动与变速运动、直线运 动与曲线运动等，针对不同的运动情况，对节点的感知能力以及网络的覆盖控制会有各自 不同的要求，在设计覆盖算法时应当全面考虑。如在战场中，对敌军单兵运动的观测和对 敌军坦克运动的观测是明显不同的，因为两者能被节点监测到的信号在强度方面是有很大 区别的。 由传感器网络的特点可知，在多数情况下传感器节点的电池是无法置换的，因此节省 能量是传感器网络需要考虑的重要问题，研究覆盖控制算法也要遵循节能的原则。目前传 感器覆盖算法类型主要分为集中式和分布式算法。集中式计算是指把所需信息传送到某个 中心节点，并在那里进行计算的方式；分布式计算是指依赖节点间的信息交换和协调，由 节点自行计算的方式。由于w s n 的拓扑结构是动态的，有时每个节点的数据是不稳定或 者不是唯一的，人们比较倾向于采用分布式的算法。 表2 1 是针对无线传感器网络各种覆盖控制算法从不同的方面做了详细比较。该分类 能帮助我们更加深入研究w s n 覆盖算法。 1 0 南京邮电大学硕士研究生学位论文第二章无线传感器网络覆盖和连通的概述 表2 1 无线传感器覆盖控制算法的比较 覆盖类型覆盖控制算法感生耳模型覆盖能力算法复杂性算法类型节点能耗连通性网络寿命 基于冗余节点判断 二进制感知强中等 分布式 低中等中等 区 基于采样点覆盖 二进制感知强 中等分布与集中结合 中等中等中等 域 不交叉优势集 二进制感知 中等较高集中式 高中等较长 覆 多重k 级覆盖 二进制感知 强中等分布式低 较好中等 盖 网络连通性二进制感知强较低分布集中中等 较好中等 点覆盖不交叉优势集二进制感知中等较高集中式高中等 较长 栅栏最差和晟好情形二进制感知强较高分布式高较好较短 覆盖 暴露模型 指数感知中等中等分布式中等较差较短 2 2 无线传感器网络覆盖和连通算法的描述 国内外研究人员对无线传感器网络的区域覆盖和连通提出了各种算法，并对有些算法 的缺点提出了许多改进的地方。由于解决覆盖问题时，要特别考虑所研究网络的独有特性， 如大规模密集部署，节点以局部自治方式协同工作中节点的运算和通信资源有限，无线通 信链路不稳定，计算处理非本地执行，传感器节点能量供应有限且电源不易更换，节点易 因能量消耗完毕或恶劣环境影响而失效等一系列的问题，会对监控任务有很大的影响，特 别在军事应用方面具有苛刻的监控需求。因此，w s n 的自身特点对其网络连接性、能量有 效性以及部署覆盖完备性提出了更高要求，具有极大的挑战性。 文献 1 4 使用线性规划技术选取最小活动节点集合来保证覆盖性。文献 1 5 中，作者 从理论和统计的、最好情况和最坏情况几个角度出发定义了覆盖问题，结合计算几何和图 论的方法，尤其是v o n o r o i 图和图搜索的方法，作者对最坏和一般情况提出了覆盖计算的 最优多项式时间算法。k u m a r 等人采用了一种r i s 独立随机算法n 耵。该算法的核心思想是 每个节点以概率p 随机决定是否“工作，以概率卜p 决定是否“睡眠 ，因此，网络的 生命时间实际上提高了1 p 倍。 c h e n n 力设计了一种基于网格划分的活跃工作节点选择算法。该算法用网格点作为网络 覆盖区域的近似，并试图选择尽可能少的活跃节点来覆盖全部网格点，分别使用了集合覆 盖问题和线性规划问题对该问题进行了抽象。仿真实验表明，尽管线性规划方法能计算出 南京邮电大学硕士研究生学位论文第二章无线传感器网络覆盖和连通的概述 更小的覆盖集，但是其收敛速度慢，计算时间长，不太适用于大规模无线传感器网络。 y e n 刚提出了一种基于探测的分布式节点密度控制算法p e a s 。在此算法中，节点最初处 于睡眠状态，经过一个随机时间间隔后，节点被唤醒。被唤醒的节点探测在预先设定的范 围内是否存在其它活跃节点，如果存在，则继续进入睡眠状态，否则进入活跃状态，工作 节点持续工作，直到其能量耗尽。通过调整探测范围和唤醒间隔，可以实现不同的网络覆 盖质量。算法不依赖节点的精确位置信息，计算开销小，但是不能保证网络的覆盖质量。 h u a n g 在文献 1 9 中将随机节点覆盖类型的圆周覆盖归纳为决策问题：目标区域中配 置一组传感器节点，要看该区域能否满足k 覆盖，即目标区域中每个点都至少被k 个节 点覆盖。我们考虑每个传感节点覆盖区域的圆周重叠情况，进而根据邻居节点信息来确定 一个给定传感器的圆周是否被完全覆盖，如图2 - 2 所示汹1 。 该算法可以用分布式方式实现：传感器节点s 首先确定圆周被邻居节点覆盖的情况， 如图2 5 ( a ) 所示，3 段圆周 o ，a ， b ，c ， d ， 分别被s 的3 个邻居节点所覆盖。再 将结果按照升序顺序记录在 0 ，2 丌 区间，如图2 - 2 ( b ) 所示，这样就可以得到节点s 的圆 周覆盖情况： 0 ，b 段为1 ， b ，a 段为2 ， a ，d 段为1 ， d ，c 段为2 ， c ，北 段为l 。文 献 1 9 给出证明：“传感器节点圆周被充分覆盖等价于整个区域被充分覆盖”。每个传感器 节点收集本地信息来进行本节点圆周覆盖判断，并且该算法还可以进一步扩展到不规则的 传感区域中使用。 正j 1 。l 一 s o i 一 _ f r r 广专重 c a ) 尸 弋 r 嚣s 0 y l 扩1 尸 1 1 氕 ( ” 图2 - 2 传感器节点s 圆周的覆盖情况 1 2 南乐邮电大学硕士研究生学位论文第二章无线传感器网络覆盖和连通的概述 另外有些协议用来保持网络的连通性，而不保证覆盖特性，如a s c e n t 2 2 ，s p a n 2 3 等。文献 2 2 中，c e r p a 和e s t r i n 提出a s c e n t 协议，用来自动设置网络拓扑。该协议通 过邻居节点数目和与邻居间链路的丢包率来决定自己是否需要进行工作，a s c e n t 不考虑完 全覆盖监视区域的问题。文献 2 3 中的协议设计了节省能量的技术，在不减弱链路容量和 连通性的基础上减少能量消耗。 本文主要是利用目前生物界比较流行的遗传算法对静态覆盖中区域覆盖问题进行研 究，并且在此覆盖策略的基础上，对连通问题也采用了分簇的方法进行研究，从而使网络 节点间的连通度达到最优。因此，在满足一定覆盖度的基础上同时实现了很好的连通度。 从而利用分布的方式实现了无线传感器网络的覆盖和连通问题。 2 3 无线传感器网络覆盖的相关问题和定义 2 3 1 传感器节点的感应和通信模型 无线传感器网络中节点的感应和通信模型是分析部署模型的前提。根据感知区域的形 状，可以分为全向感知模型和有向感知模型。这点和通信模型很相似，因此，按照其全向 和有向的规则，无线传感器节点感应和通信模型可以分为以下三类： 1 布尔模型 针对布尔模型首先作两个定义： 定义1 ：圆型感应模型。这里假设每个传感器的感应半径f s ，任何一个物体处于以一 个工作的传感器为圆点，r s 为半径的圆内，它就能被此传感器所感知。 定义2 ：圆型信号发射模型。这里假设每个工作的传感器都有一个通信距离f c ，两个 工作的传感器如果相距r c ，那么它们之间就能够通信。 在二维平面中，布尔感应模型的传感器节点都具有固定的感应半径，每个传感器只能 感知和发现其传感半径内的环境或事件。这样，监测区域就被分为两个部分：覆盖区和盲 区。覆盖区中的任意一点至少被一个传感器节点所覆盖，而盲区则是覆盖区的补集。事实 上，有的应用对事件的监测需要较高的准确度，要求覆盖区中的任意一点至少要同时位于 k 个节点的传感半径内，否则就被作为盲点，这种覆盖我们称之为k 重覆盖。同样布尔信 号发射模型中每个传感器都有一个信号发射距离，两个工作的传感器节点的距离仅当小于 等于信号发射距离时，它们才能可靠的通信。假设在被监测区域的某个节点i 的坐标 ( i 。i ，) ，节点的传感半径为i s ，目标的位置t ，的坐标为( j 。，j ，) ，则节点与目标点的距离 1 3 南京邮电大学硕士研究生学位论文 第二章无线传感器网络覆盖和连通的概述 厂= - , - - y 以表示为矗= ( 厶一 ) 2 + ( 西一力) 2 。用c 来表示i 节点对t ，的感知质量，当被关注事 件t ，的位置在节点i 的传感范围r s 的圆内，认为节点i 对关注事件t j 的感知质量为l ， 即节点i 对的t ，感知度为l ，否则当t ，在节点i 的传感范围外时，节点i 对t ，的感知度为 0 ，因此数学表达式为： r 1d i i r s c i , j t 0other(2-1) 从二维感知和通信模型可以推广到三维空间中，和在二维中对于传感器节点采用同样 的假设条件。这时，传感器的感知模型是一个球体，即为以工作的传感器为圆点，以r s 为半径的球体，任何物体只要是在这个球体内，都可以被此传感器节点所感知。同理，通 信模型也是球形信号发射模型，在任何方向上的两个传感器节点只要是它们的距离在通信 距离r c 范围内，都可以相互通信。 为了保证数据传输的可靠性并结合实际传输精度的要求，一个传感器节点必须与多个 传感器节点连通，如果一个无线传感器网络中的任意一个传感器节点至少与周围k 个节点 相连通，我们称之为k 重连通。 在无线传感器网络进行信息采集的过程中，往往存在一些具有关键性作用的监控点， 掌握好这些点的监控数据对纵观全局目标信息有重要的指导意义。若仍采取单个传感器对 这些“关键目标点 进行监控，无法满足其监控需求，需采用多个传感器节点对该目标点 进行监控。有研究人员提出“k 一覆盖”问题。可以定义为：监控区域中存在一些“关键目 标点 ，其覆盖需求是至少采用k 个能覆盖该目标的传感器同时工作。 针对布尔感知模型，提出“k 一覆盖 问题，即需进行多重覆盖以提高监测信息精度 的情况，当k = i 时，该问题退化为一般性的布尔感知模型覆盖控制问题，即所有的监控目 标点都仅需一个传感器进行覆盖就可满足全局的覆盖需求。在w s n 实际应用中，可能出现 监控目标点的覆盖重数需求各异的情况，在某些关键点的覆盖重数需求较高，而其他的一 些目标覆盖重数需求较低。 1 4 南京邮电大学硕士研究生学位论文第二章无线传感器网络覆盖和连通的概述 图2 - 3k 覆盖( k = 4 ) 监控目标 佟感器 o 蝴瞳 图2 - 3 显示了一种k 覆盖的情况，监控目标需要其周边的四个传感器节点s l 、s 2 、 s 3 、s 4 同时工作，方可满足其高精度的感知需求。 但是考虑实际自然环境很多传感器的信号发射和感应的区域并不是一个理想的圆型。 因此，出现了其它的感应模型。 2 指数模型 尽管布尔模型考虑了距离因素对感知质量的影响，但是这种对于传感器节点感知能力 过于理想化或者过于简化。实际上节点采集的信息和对目标判定与节点到目标距离有很大 关系，一般来讲节点愈靠近目标位置其采集的信息越精确，目标判断越