（计算机应用技术专业论文）无线传感器网络覆盖控制研究.pdf

江苏大学硕士研究生毕业论文 摘要 随着无线通信、嵌入式和传感器技术的不断发展和进步，无线传感器网络作 为一种特殊形式的计算机网络，在军事、安全监视、生态环境监测、医疗健康等 领域具有广泛的应用前景。覆盖控制作为无线传感器网络( w s n ) 中的一个基 本问题，可以使无线传感器网络的空间资源得到优化分配，进而更好地完成环境 感知、信息获取和有效传输的任务。 本文首先研究了无线传感器网络的特点，综述了网络覆盖控制问题的研究现 状；在此基础上，提出了一种基于感知概率的覆盖控制算法；接着考虑了不均匀 覆盖导致的“覆盖洞”问题，提出了基于移动节点的“虚拟力”方法。具体工作如下： ( 1 ) 研究了无线传感器网络的特点，综述了无线传感器网络覆盖控制问题的 研究现状，分析并指出了覆盖控制研究需要考虑的问题单重覆盖中网络的服 务质量仅仅依赖于单个节点的监测结果，如果个别节点失效可能会导致单点失败 的现象，单个节点单重覆盖往往很难满足应用的需求，为此重点介绍了几类典型 的k 重覆盖算法，并指出了各自方法的特点和当前研究存在的问题。 ( 2 ) 提出了一种新的无线传感器网络覆盖控制算法基于感知概率模型 的k 重覆盖算法。该算法依据节点感知能力的强弱，将监测区域中的任一点被该 节点监测的情况赋值为某一概率，通过节点间相互交换信息，考虑节点能量大小， 进行k 组不同工作节点的选择。该方法在有效地保证k 重覆盖的前提下，可减少 网络工作节点的数目和延长网络的使用寿命。通过定性分析表明，该方法具有较 低的数据传输开销和较少的时间耗费。 ( 3 ) 提出了保证覆盖的移动节点优化部署方法。该方法有机结合了动态规划 算法和启发式的虚拟力算法，由动态规划算法来保证最佳的连通性，而虚拟力算 法考虑合理地移动相应节点。该方法有效地提高了无线传感器网络的连通性和覆 盖区域面积，可解决因节点分布局部过于稀疏的先天不足，或因能耗不均匀部分 节点过早死亡等导致的“覆盖洞”问题。 最后，在n s 2 网络仿真环境下，设计实现了基于感知概率模型的k 重覆盖 和移动节点优化部署的仿真程序，仿真实验表明了所提方法的有效性。 关键词：无线传感器网络，布尔模型，感知概率模型，覆盖控制，移动节点 江苏大学硕士研究生毕业论文 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k sa r eu s e di naw i d e rr a n g e ，s u c ha si nt h ef i e l d so f m i l i t a r y , s e c u r i t y , s u r v e i l l a n c e ，e c o l o g i c a l e n v i r o n m e n tm o n i t o r i n g ，m e d i c a la n d h e a l t h c o v e r a g ec o n t r o lc a no p t i m i z et h es p a c er e s o u r c e s ，s e r v et ot h ee n v i r o n m e n t a l c o m p l e t ea w a r e n e s s ，a n db ee f f e c t i v et oi n f o r m a t i o nt r a n s m i s s i o n i nt h i sp a p e r , t h e c o v e r a g ec o n t r o lo fw s n s i st h ef o c u so fr e s e a r c h ，a n ds o m ep r o b l e m so fk - c o v e r a g e c o n t r o la r ed i s c u s s e d a tf i r s t ，t h ec h a r a c t e r i s t i c so fw i r e l e s ss e n s o rn e t w o r k sa r ec o n s i d e r e da n da l l o v e r v i e wo fc o v e r a g ec o n t r o li sp r e s e n t e d o nt h i sb a s i s ，ac o v e r a g ec o n t r o la l g o r i t h m b a s e do nt h ep r o b a b i l i t ys e n s i n gm o d e li s p r o p o s e d t h e nt h e c o v e r a g eh o l e ” p r o b l e mr e s u l t e d i nu n e v e nc o v e r a g ei sc o n s i d e r e d ，a n dt h em e t h o do ft h e ”v i r t u a l f o r c e ”b a s e do nm o b i l en o d e si sp r e s e n t e d t h em a i nw o r k sa r ea sf o l l o w s ： f i r s t l y , t h i sp a p e rg i v e sac o m p r e h e n s i v ea n a l y s i so ft h ec h a r a c t e r i s t i c so f w i r e l e s ss e n s o rn e t w o r k s ，a n a l y z e st h ec u r r e n tc o v e r a g ec o n t r o lr e s e a r c ho fw i r e l e s s s e n s o rn e t w o r k ，i n t r o d u c e st h ec l a s s i f i c a t i o no fat y p i c a lw i r e l e s ss e n s o rn e t w o r k s c o v e r a g ec o n t r o la l g o r i t h m s ，a n dp o i n t so u tt h ei s s u e so fc o v e r a g ec o n t r o lo fw i r e l e s s s e n s o rn e t w o r k ，o fw h i c ht h es e r v i c eq u a l i t yi ns i n g l ec o v e r a g eo n l yd e p e n d so nt h e m o n i t o r i n gr e s u l t so f as i n g l en o d e an o d ef a i l u r em a yl e a dt ot h en e t w o r kf a i l u r e ，s o s i n g l ec o v e r a g ei sd i f f i c u l tt of u l f i l lt h en e e d so ft h ea p p l i c a t i o n s a c c o r d i n gt ot h e p r o b l e m sm e n t i o n e da b o u t ，t h ep a p e ri n t r o d u c e ss o m et y p i c a lt y p e so fk - c o v e r a g e c o n t r o la l g o r i t h m sa n dd i s c u s s e st h e c h a r a c t e r i s t i c so fe a c ha l g o r i t h ma n dt h e p r o b l e m si nc u r r e n tr e s e a r c h e s s e c o n d l y , an o v e lk - c o v e r a g ec o n t r o la l g o r i t h mb a s e do nt h ep r o b a b i l i t ys e n s i n g m o d e li sp r e s e n t e d a n yp o i n ti nt h et a r g e ta r e as e n s e db yas e n s o ri sg i v e nav a l u e b a s e do nt h es e n s i n gc a p a b i l i t y i nt h ea l g o r i t h mas e n s o rc o m p a r e si t sr e s i d u a le n e r g y 、析t 1 1t h en e i g h b o r h o o d t h es e n s o ra n di t sn e i g h b o r h o o dc o o p e r a t et oc o n s t r u c tk w o r k i n gc o v e r st h a tp r o v i d ep r o b a b i l i s t i cc o v e r a g ef o rt h ew h o l et a r g e tr e g i o n t h e a l g o r i t h ma c t i v a t e sl e s sn u m b e ro fn o d e s ，p r o l o n g st h el i f e t i m eo ft h en e t w o r k t h e i i 江苏大学硕士研究生毕业论文 t h e o r e t i c a la n a l y s e sp r o v et h a tt h ea l g o r i t h mh a sl o w e rd a t at r a n s m i s s i o nc o s t sa n d l e s st i m ew a s t i n g t h i r d l y , am o b i l en o d eb a s e dm e t h o di sp r e s e n t e d t op r o v i d et h ew h o l e c o v e r a g e t h em e t h o dc o m b i n e sad y n a m i cp r o g r a m m i n ga l g o r i t h m ，a n dah e u r i s t i cv i r t u a l f o r c e sa l g o r i t h m ，w h i c hp r o v i d e sag o o db a s i sf o rc o n n e c t i v i t ya n da t t r a c t sm o b i l e s e n s o r sm o v et h e r e i nt h i sm e t h o daf e wm o b i l es e n s o r sa r ea d d e di n t oa l le x i s t i n g s e n s o rn e t w o r kt oi m p r o v et h ec o n n e c t i v i t ya n dc o v e r a g e ，w h i c hm a k e su pt h eh o l eo f c o v e r a g ec a u s e db yr a n d o md e p l o y m e n to rt h eu n e v e ne n e r g yc o n s u m e i nt h ee n d ，t h et w op r e s e n t e da l g o r i t h m sa l ei m p l e m e n t e do nn s 2 ，a n dt h e r e l m i v ep e r f o r m a n c e sa r ea n a l y z e dt h r o u g hc o n t r a s t s s i m u l a t i o nr e s u l t sp r o v et h a t t h ea l g o r i t h m sa l ee f f e c t i v e k e yw o r d s ：w s n ，b i n a r y d e t e c t i o nm o d e l ，p r o b a b i l i t ys e n s i n gm o d e l ， c o v e r a g ec o n t r o l ，m o b i l en o d e i i i 学位论文版权使用授秋书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，同意学校保留并向国家有关部门或机构送交论文的 复印件和电子版，允许论文被查阅和借阅。本人授权江苏大 学可以将本学位论文的全部内容或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密。 学位论文作者躲畸指剥币签弛 呷年j f l 月；j 日吁年5 月3 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已注明引用 的内容以外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者躲带译 日期： 呵年 歹月乡l 曰 江苏大学硕士研究生毕业论文 第一章绪论 无线传感器网络是继i n t e m e t 之后的又一新兴i t 技术，具有广阔的应用前景 和科研价值。网络覆盖是网络运行的基础，针对无线传感器网络特点的覆盖控制 研究是网络应用迫切需要解决的问题。本章首先介绍了无线传感器网络的特点、 网络结构、节点组成和应用前景；阐述了无线传感器网络覆盖控制含义和意义； 最后综述了本文所作的主要研究工作。 1 1 研究背景 1 1 1 无线传感器网络简介 无线传感器网络是随着无线通信和嵌入式计算技术、传感器技术、微机电技 术、分布式信息处理技术的进步而发展起来的一种新兴的信息获取技术，是当前 在国际上备受关注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域 i i - t 。m i t 技术评论t e c h n o l o g yr e v i e w 在预测未来技术发展的报告中指出，无线 传感器网络处于在不远的将来将改变世界十大新兴技术之剖8 1 。 无线传感器网络【2 1 是由具有感知、计算和通信能力的微型传感器节点通过自 组织的方式构成的无线网络。其主要功能是传感器节点感知和采集各种环境或监 测对象的信息，将这些信息通过无线方式发送，并最终传送到用户终端，从而实 现物理世界、计算世界以及人类社会三元世界的连通。 无线传感器网络与传统的a dh o c 网络相比，有很多相似之处，但同时也存 在着很大的差别。在研究各种网络协议和应用系统时，和传统的a dh o c 网络相 比，无线传感器网络具有以下几方面的特点【1 刀： ( 1 ) 超大规模、分布密集。为了获得物理世界的精确信息，通常在被监测区 域部署大量的传感器节点，传感器节点的数量可能达到成千上万，甚至更多。 ( 2 ) 自组织。网络的部署和展开无需依赖于任何预设的网络设施，节点通过 拓扑控制机制和网络协议协调各自的行为，节点开机后就可以快速、自动地组成 一个独立的监测网络。 江苏大学硕士研究生毕业论文 ( 3 ) 硬件资源有限。节点由于受价格、体积和功耗的限制，其计算能力、程 序空间和内存空间比普通的计算机功能要弱很多。这一点决定了在节点操作系统 设计中，协议层次不能太复杂。 ( 4 ) 电源容量有限。传感器节点由电池供电，电池的容量一般不是很大。其 特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池，一旦电池能 量用完，这个节点也就失去了作用( 节点失效) 。因此在传感器网络设计过程中， 任何技术和协议的使用都要以节能为首要条件，以提高网络的使用寿命。 ( 5 ) 动态拓扑。无线传感器网络是一个动态的网络：一些节点可能会因为电 池能量耗尽、环境因素或其他故障而失效，退出网络；一些节点也可能由于工作 的需要而被添加到网络中。这些都会使网络的拓扑结构随时发生变化，因此网络 应该具有动态拓扑组织功能。 ( 6 ) 以数据为中心的网络。由于传感器节点大多是随机部署，构成的网络和 节点编号之间的关系是动态的，表现为节点编号和节点位置没有直接的关系。无 线传感器网络不像传统的网络以连接为中心，而是以数据为中心的网络，因此需 要节点进行数据聚合、融合、缓存和压缩等处理。 无线传感器网络一般有两种结构：同构型和异构型结构。同构型：监控区域 内的节点，对感兴趣的数据进行采集、处理、融合，并通过汇聚节点( s i n k ) 路由 到基站，用户可以通过卫星或因特网进行查看、控制整个网络。异构型：传感器 节点自组织成子网，每个子网通过网关同数据库中心连接，终端用户通过数据中 心对各个子网进行监控。 无线传感器网络中传感器节点由传感器模块、处理器模块、无线通信模块和 能量供应模块四部分组成。传感器模块负责监测区域内信息的采集和数据转换； 处理器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其 他节点发来的数据；无线通信模块负责与其他传感器节点进行无线通信，交换控 制信息和收发采集数据；能量供应模块为传感器节点提供运行所需的能量，通常 采用微型电池。传感器节点集数据采集、数据处理、数据传输于一体，能够通过 各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信 息。 2 江苏大学硕士研究生毕业论文 无线传感器网络能够客观有效的获取物理信息，如：环境中的热、红外、声 纳、雷达和地震波等信号 4 1 ，探测包括温度、湿度、噪声、光强度、压力、土壤 成分、移动物体( 其大小、速度和方向) 等信息，能应用于军事国防、工农业控 制、城市管理、智能家居、生物医疗、环境检测、抢险救灾、防恐、危险区域远 程控制等诸多领域】。环境恶劣、无人职守，资源受限的环境，具有十分广阔 的应用前景。 1 1 2 无线传感器网络应用 无线传感器网络具有广阔的应用背景，主要表现在军事国防、环境监测、医 疗等领域。在空间探索和灾难拯救等特殊领域，传感器网络有着得天独厚的技术 优势。 ( 1 ) 军事领域 无线传感器网络具有快速部署、自组织、隐蔽性强和高容错性的特点，非常 适合于军事应用。无线传感器网络由密集的、低成本、随机分布的节点组成，在 无任何基础设施支持下，能够自组织迅速配置成网络，较高的容错能力使其不会 因为某些节点的损坏而导致整个系统的崩溃。这一点是传统的传感器技术所无法 比拟的，如其在目标跟踪与监测中的应用。 ( 2 ) 环境监测和预报 随着人们对环境的日益关注，无线传感器网络逐渐被广泛应用于环境监测领 域，无线传感器网络在环境监测方面可应用于土壤空气状况和大面积的地表监 测，以及用于气象地理研究、洪水和森林火灾监测等，还可以通过跟踪鸟类、小 型动物和昆虫进行生物种群复杂性勘测等。 ( 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 就是为 火星探测进行技术准备的。无线传感器网络的出现与应用将会推动人类太空事业 江苏大学硕士研究生毕业论文 的发展，加速人类空间探索的进程。 此外，无线传感器网络还应用于智能家居、城市车辆监测等领域。 1 1 3 课题背景 本文在国家自然科学基金“容忍入侵的无线传感器网络拓扑控制理论与方 法研究”与江苏省自然科学基金“可生存的无线传感器网络拓扑控制方法研 究 等项目的支持下，研究无线传感器网络覆盖控制方法，其目的是在节点部署 阶段实现k 重覆盖，为容忍入侵的拓扑控制提供冗余性基础。 1 2 研究意义 在无线传感器网络中，大量的传感器节点组成多跳无线自组网，传感器节点 负责感知本地的数据，将其融合后的处理结果发送给基站，基站再将数据转发给 用户。在这一过程中，涉及到传感器网络许多重要机制，如：覆盖、介质访问控 制、数据收集、数据传输等。而这一过程的第一步就是对目标区域进行覆盖，它 是无线传感器网络配置首先要面临的关键问题。 无线传感器网络覆盖是指通过网络中传感器节点的空间位置分布实现对被 监测区域或目标对象物理信息的感知，它从根本上反映了网络对物理世界的感知 能力。 网络覆盖在无线传感器网络设计中的重要性与网络连接并列，二者均是网络 运行必须解决的基本问题。网络连接侧重于节点间的通信能力的连接，使得采集 的物理信息能够顺利的传送给网络终端；而网络覆盖则从网络感知物理世界的角 度，关注通过网络节点的位置分布完成满足应用需求的被监测区域物理信息的采 集。优化无线传感器网络覆盖( 即覆盖控制) 对于合理分配网络的空间资源，更 好地完成环境感知、信息获取任务以及提高网络生存能力都具有重要的意义。 无线传感器网络中融入高效地覆盖控制策略后，不但可以更大范围、更精确 地对目标进行探测、跟踪，还可以显著节约网络的能量消耗，延长网络的生存时 间。因此，研究无线传感器络的覆盖控制问题，具有积极的理论意义和广泛的应 用价值。 1 3 本文的主要工作 4 江苏大学硕士研究生毕业论文 本文首先综合分析了无线传感器网络覆盖控制的研究现状，详细探讨了各种 无线传感器网络覆盖控制算法及其特点，明确了无线传感器网络覆盖控制研究所 面临的困难和挑战；之后，提出一种新的基于感知概率模型的无线传感器网络k 重覆盖算法，并对其性能进行分析和评价；最后，在此基础上提出覆盖控制中保 证覆盖的移动节点优化部署方法。本文的主要工作包括： ( 1 ) 对现有无线传感器网络覆盖控制算法的分析和评价 研究了无线传感器网络的特点，综述了无线传感器网络覆盖控制问题的研究 现状，分类介绍了典型的无线传感器网络覆盖控制算法，分析并指出了无线传感 器网络覆盖控制研究需要考虑的问题。 ( 2 ) 基于感知概率模型的k 重覆盖算法设计和实现 由于目前研究的无线传感器网络覆盖算法，大多基于布尔感知模型：节点感 知半径内发生的事件以概率l 感知，而半径之外的事件感知率为0 。而实际应用 中，传感器节点的物理信号并不是非1 即0 的骤降。为此，本文采用基于感知概 率的模型。此外，单重覆盖中网络的服务质量仅仅依赖于单个节点的监测结果， 如果个别节点失效可能会导致单点失败的现象，单个节点单重覆盖往往很难满足 应用的需求，为此本文提出了一种新的k 重覆盖算法。该算法依据节点感知能力 的强弱，将监测区域中的任一点被相关节点监测的情况赋值为某一概率，并通过 节点与邻居交换信息，根据能量大小竞选找出k 组不相交工作节点集，保证监测 区域中每一点被k 重覆盖。文中同时给出基于感知概率模型的k 重覆盖算法的仿 真实现并从定性和定量两个方面对基于感知概率模型的k 重覆盖算法的性能进 行分析和评价。 ( 3 ) 提出保证覆盖的移动节点优化部署方法 对随机部署方式下，节点分布存在不确定性，以及节点失效而导致网络覆盖 洞，影响数据的健壮性和精确性的情况，提出保证覆盖的移动节点优化部署方法： 在已有的网络中加入少量移动传感器节点，利用移动节点的可移动性，改善网络 的覆盖质量。文中同时给出保证覆盖的移动节点优化部署方法的实验证明。 各章节安排： 第一章介绍课题的研究背景和意义，概述了无线传感器网络的起源、发展， 以及研究现状，同时分析和提出论文研究的主要内容。 5 江苏大学硕士研究生毕业论文 第二章介绍设计无线传感器网络所面临的困难和挑战，详细阐述各种无线传 感器网络的覆盖控制算法，对各种不同覆盖控制算法进行对比和分析，并讨论研 究了无线传感器网络覆盖控制应考虑的问题。 第三章详细描述基于感知概率模型的k 重覆盖算法，并从定性和定量两个方 面给出算法的分析和评价。 第四章介绍在无线传感器网络覆盖中引入移动节点，对其实施优化部署，以 调整网络的拓扑结构和提升其性能、覆盖面积和连通性。 第五章在n s 2 环境的网络仿真下，设计实现了基于概率模型的k 重覆盖和 移动节点优化部署的仿真程序。 第六章对全文进行了总结，并提出进一步需要开展的工作。 6 江苏大学硕士研究生毕业论文 第二章无线传感器网络覆盖问题研究 无线传感器网络的覆盖由于受网络本身特性的影响，其关注的问题不同于传 统的网络覆盖，它反映了传感器网络所能提供的“感知 服务质量。本章详细解 释了网络覆盖的基本概念，分析总结了常用的网络覆盖算法，归纳了网络覆盖的 评价标准，为以后的研究和算法设计奠定基础，最后对六种典型的k 重覆盖算法 做了详细的比较分析。 2 1 网络覆盖的基础知识 本节首先介绍了感知范围、覆盖效率、网络寿命等网络覆盖的相关概念，然 后对几种感知模型进行了比较介绍，最后针对不同的节点部署方式给出各自的适 用环境。 2 1 1 相关概念 ( 1 ) 感知范围 无线传感器网络中，单个传感器节点所能感知的物理世界的最大范围，我们 称为节点的感知范围，有时也称为节点的覆盖范围或节点的探测范围。现实应用 中，节点的感知范围由节点本身的硬件特性等条件决定。在网络覆盖研究中，传 感器节点的感知范围一般都是通过节点的感知模型确定，在布尔模型中，感知范 围也称为感知半径。 ( 2 ) 感知精度 节点的感知精度是指节点采集的被监测对象的信息的准确程度，一般用节点 感知数据与物理世界真实数据的比值表示。网络的感知精度是指网络提供的被监 测对象的信息的准确程度，也可以用网络监测值与物理世界真实值的比值表示。 1 ， p = 卫 ( 2 - 1 ) u 式2 1 中，p 表示感知精度，表示节点或者网络的监测值，m 表示物理世 界的真实值。传统覆盖的定义是基于布尔模型，认为如果节点与监测对象的距离 小于感知半径，则称该节点覆盖监测对象。 7 江苏大学硕士研究生毕业论文 环境监测应用中，网络的监测精度是指网络的感知精度。有时也用感知误差 来表示感知精度，感知误差定义为网络的感知数据与真实数据的差值。 ( 3 ) 感知概率 感知概率也称为覆盖概率，一般是指在目标覆盖中，监测对象被节点或者网 络感知的可能性。在覆盖算法研究中，感知概率一般和节点或者网络的感知模型 密切相关。 ( 4 ) 漏检率 在目标覆盖中，漏检率和感知概率相对应，是指监测对象被节点或者网络漏 检的可能性，其大小和节点本身特性以及应用环境密切相关。 ( 5 ) 覆盖程度 为衡量网络区域覆盖的质量，g a g e l 9 1 最先提出了覆盖程度这个概念，它定义 为所有节点覆盖的总面积与目标区域总面积的比值。其中节点覆盖的总面积取集 合概念中的并集，所以覆盖程度一般是小于或等于1 的： u4 c 。孝_ ( 2 - 2 ) 其中c 代表覆盖程度，彳表示整个目标区域的面积，代表节点数目，彳， 表示第f 个节点的覆盖面积。 ( 6 ) 覆盖效率 覆盖效率用来衡量节点覆盖范围的利用率，它定义为区域中所有节点的有效 覆盖范围的并集与所有节点覆盖范围之和的比值。一方面可以反映覆盖的情况， 另一方面可以反映整个网络的能量消耗情况。覆盖效率c e 的计算如下式( 2 - 3 ) 所示： u4 叩2 茕 ( 2 。3 ) 1 = 1 根据覆盖效率的定义，不难发现覆盖效率同时反映了节点的冗余程度，覆盖 效率越高，节点冗余度越小，反之节点冗余度越大。 ( 7 ) 覆盖重数 针对需要较强监测能力或较高容错率的应用环境，研究学者提出了多重覆盖 的概念【l o l ，即某一事件是否被颇胗1 ) 个节点覆盖。这与上面的覆盖程度并不矛盾， 8 江苏大学硕士研究生毕业论文 只是关注的侧重点不同。前者关注的是对目标区域的整体覆盖情况，后者则侧重 于局部的重点观测。覆盖重数表示某个区域的覆盖的冗余程度，如果这个区域在 k 个节点的感知范围之内，那么它的覆盖重数就是k 。具体的数学表达式为： k a = 菩1k ；k = 倍箫t - 冬1 一l - ，i p 4 ， 二k ；k = ：_ 毒：1 。 ( 2 4 ) i =ii 月i1 这里肠表示a 区域的覆盖重数，a ，为i 节点的传感范围，墨表示第f 个节点 传感范围是否覆盖a 区域，覆盖时墨为1 ，否则为0 。 ( 8 ) 网络寿命 不同的无线传感器网络应用，对网络寿命的定义是不同的。有些定义网络中 所有节点全部死亡时，网络寿命结束；有些定义网络中失效的节点数量超过某个 阈值时，网络寿命结束；有些定义在网络出现不连通情况时，网络寿命结束；有 些定义网络提供的覆盖率低于某个阈值时，网络寿命结束。 ( 9 ) 覆盖时间 覆盖时间是指目标区域被完全覆盖或者跟踪时，所有工作节点从启动到就绪 所需要的时间( 在有移动传感器节点的覆盖中是指移动传感器节点移动到最终位 置所需要的时间) 。覆盖时间在营救或者突发事件监测中是一个很重要的节点覆 盖衡量指标，可以通过算法优化和改进硬件设施来减少覆盖时间。 ( 1 0 ) 平均移动距离 移动传感器节点的覆盖方案中，每个节点到达最终位置所移动距离的平均 值。这个距离越小，系统消耗的总能量就越少。在实际应用中，不仅要减少节点 移动的平均距离，而且要尽量减少节点间能量消耗的差异。因此距离可以用节点 移动的平均距离和标准方差来表示更为准确，即每个节点移动的距离与整个网络 中节点移动平均距离的偏差来表示。这个标准差越小，则系统中节点消耗的能量 就越均衡，不易导致网络因为某个节点能量的过多消耗而中断。 2 1 2 感知模型 无线传感器网络的覆盖问题通常与每个节点的感知模型及所有节点的位置 部署紧密相关。简而言之，传感器节点的感知模型构建了节点物理位置与空间位 置的几何关系，可以看作是传感器感知函数的服务质量的量度。传感器节点的感 知模型很多，根据不同的性质有不同的分类。 9 江苏大学硕士研究生毕业论文 根据感知区域形状，节点的感知模型可分为全向感知模型和有向感知模型。 全向感知模型的感知区域是以节点为圆心、感知范围为半径的一个圆( 三维空间 中则是一个球) ，而后者的感知区域是以节点为圆心、感知范围为半径、张角为y 的扇形( 三维空间中则是一个圆锥体) 。此外，还有更一般的感知区域为任意形 状的感知模型，如信息覆盖模型【l l 】。 根据节点的感知特性，节点的感知模型可分为布尔模型( 即0 1 模型) 和概 率模型。布尔模型认为只要目标处于传感器节点的感知范围内即可成功地被感 知。假设在被监测区域的某个节点f 的坐标( & ，劬，节点的传感半径为b ，目标的 位置弓的坐标为抗劝，则节点与目标点的距离d ( f ，d = ( t 一丘) 2 + ( 一矗) 2 。用 c 仁来表示f 节点对乃的感知质量，当被关注事件乃的位置在节点f 的感知范围 尼的圆内，认为节点耐关注事件乃的感知质量为l ，即节点f 对乃的感知度为l ， 否则当乃在节点f 的感知范围外时，节点f 对乃的感知度为0 ，因此数学表达式 为： c ( f ，) ： 1 ，矿d ( l 胚r( 2 - 5 ) c ( “) 2 锰：淼磊5 ( 2 。5 ) 概率模型认为即使目标处于感知区域内也仅仅只能以一定的概率被传感器 节点感知；第三节将详细介绍概率模型。 在早期无线传感器网络覆盖研究中使用的节点感知模型一般都是布尔模型 ( 即0 1 模型) ，它忽略了一些外界因素的影响，使得问题更为理想化。 2 1 3 节点部署方式 目前认为传感器网络中节点的部署方式主要有以下几种部署方式：确定性部 署、随机部署和可移动部署1 2 1 。 确定性部署是指事先根据业务需求和传感器节点性能设计节点放置的位置， 将节点逐个定点部署。比如，现有的规则部署，他部署的节点可以构成规则的拓 扑结构，如网格、立方体等。这种部署方式适用于环境状况良好、定点部署代价 低、网络规模小的情况。无线传感器网络采用确定性部署方式，通常具有良好的 网络特性和业务特性，网络资源使用合理，可最大限度地满足用户需求并延长网 络寿命。其缺点是适用条件相对苛刻，无法适应无线传感器网络广泛的应用需求。 1 0 江苏大学硕士研究生毕业论文 随机部署则指采用抛撒方式批量部署传感器节点。根据具体的部署手段，通 常认为节点在目标区域内呈均匀分布或高斯分布等。这种部署方式适用于恶劣环 境或大规模网络，其优点是部署易于实现，价格低廉。对于预先未知监测区域情 况的应用场景，可采用随机部署方式。目前，大多数的研究是基于节点随机部署 方式的。其存在的主要问题是有可能存在感知盲区或局部资源高度重复；网络的 覆盖性、连通性等都处于非最佳状态，需要通过一定的控制策略改善网络性能。 可移动分布分为节点全部可以自由移动和部分可以移动两种。前者自由程度 较高，在带来较高覆盖质量的同时会增加能量的消耗。后者是一种混合型网络， 可以弥补静止节点覆盖的不足，又可以给网络带来一定的灵活性。 节点部署方式的不同对网络拓扑控制将产生很大的影响，因此我们需要根据 不同的部署方式，采用不同的覆盖控制技术。 2 2 覆盖控制算法简介 为进一步深入研究网络覆盖，本节首先将覆盖问题进行分类，分别是目标 ( 点) 覆盖、栅栏( 线) 覆盖和区域( 面) 覆盖，然后介绍覆盖算法的评价指标， 为以后的研究和算法设计奠定了基础。 2 2 1 覆盖问题分类及算法介绍 从不同角度看，网络覆盖的分类也不同，若按照传感器节点的部署方式，可 分为节点确定性部署的覆盖，节点随机部署的覆盖以及可移动部署的覆盖。按照 节点的类型，可分为同构节点覆盖、异构节点覆盖、以及混合节点覆盖等。本节 从应用角度研究无线传感器网络覆盖的分类及相关算法。 无线传感器网络覆盖，从应用性质角度分析，可分为时间驱动类型( 周期性 报告) 和事件驱动类型( 检测事件等) 两种；若根据覆盖对象来分，静态传感器 网络可分为以下三种：目标( 点) 覆盖、栅栏( 线) 覆盖和区域( 面) 覆盖【1 3 】 【1 4 1 。如下图2 1 、2 2 、2 3 所示，图中虚线圆代表节点的感知范围( 布尔模型) 。 ( 1 ) 目标( 点) 覆盖 无线传感器网络应用中需要对被监测区域中位置确定的某些重要目标进行 数据采集和监测，这类覆盖的研究主要是通过对自由分布节点的调度，完成目标 江苏大学硕士研究生毕业论文 的监测。目标覆盖如图2 1 所示，目的是覆盖一些己知位置的离散的点集合。经 典的画廊问题就属于目标覆盖问题【1 5 】。 图2 - 1 目标覆盖 在目标覆盖中，另一个研究的热点就是在满足覆盖要求的同时考虑网络能量 和寿命的优化。任务驱动型网络覆盖策略就是在预知被监测目标的位置的前提 下，选择随机部署在区域内的部分传感器节点对这些特定位置进行监控，优化网 络资源应用，确保监控任务的完成。 c a r d e i 1 6 考虑了离散目标点的能量高效覆盖问题。在军事应用中，常常将 大量传感器节点随机部署在若干个离散目标点附近。如果将网络节点划分为若干 个互不相交的节点集合且每个节点集合能够完全覆盖这些目标点，那么，通过周 期性的调度这些节点集合，在任意时刻只有一个节点集合处于活跃工作状态，其 它节点全部处于睡眠状态，就可以有效延长整个网络的生存时间。显然，这样的 节点集越多，网络生存时间越长。如何构造最大数量的无交节点集是一个n p 完 全问题，为此c a r d e i 提出了一种基于混合整数规划的启发式算法。c a r d e i 1 7 对 前一问题进行了扩展，不再限制每个节点只能加入一个节点集合，而是允许一个 节点同时加入多个节点集合。c a r d e i 1 8 讨论了当节点感知半径可变时的能量高 效目标覆盖问题。l u 1 9 讨论了如何通过调整节点的感知半径实现能量高效覆 盖，同时通过构建虚拟骨干网络保证网络的连通性。 但是在一些场合，不同目标对于覆盖效果的要求不同，需要区别对待。 ( 2 ) 栅栏( 线) 覆盖 栅栏覆盖( 如图2 2 ) 是指，当移动目标沿任意路径穿越传感器节点部署区 域时，工作节点要能够检测移动目标的全程移动轨迹。它考察了目标穿越无线传 感器网络时被检测的情况，反映了给定无线传感器网络所能提供的传感、监视能 1 2 江苏大学硕士研究生毕业论文 力。 o l ：o 水： o oj o ” o | oo o o f oo oo l v o 口 l q o 。弋 。 o 9 图2 - 2 栅栏覆盖 根据目标穿越无线传感器网络时所采用模型的不同，栅栏覆盖又可以具体分 为“最坏与最佳情况覆盖”和“暴露穿越”两种类型。在“最坏与最佳情况覆 盖”问题中，对于穿越网络的目标而言，最坏情况是指考察所有穿越路径中不被 网络传感器节点检测的概率最小情况；对应最佳的情况是指考察所有穿越路径中 被网络传感器节点发现的概率最大情况。 与单纯考虑离传感器节点距离的“最坏与最佳情况覆盖 不同，“暴露穿 越 同时考虑了“目标暴露( t a r g e te x p o s u r e ) 的时间因素和传感器节点对于 目标的“感应强度”因素。这种覆盖模型更为符合实际环境中，移动目标由于穿 越无线传感器网络区域的时间增加而导致“感应强度”累加值增大的情况。 m e g u e r d i c h i a n 2 0 首次提出了无线传感器网络的栅栏覆盖模型。给定目标穿 越网络部署区域的起始点和终止点，文献 2 0 】试图确定网络的最优覆盖以及最差 覆盖质量。m e g u e r d i c h i a n 2 1 提出了一种新的基于e x p o s u r e 的栅栏覆盖模型。 l i u 2 2 讨论了基于网格部署以及随机部署的无线传感器网络的覆盖以及目标检 测问题，提出一种基于渗透理论 2 3 1 的临界节点密度。当节点密度小于该临界密 度时，以概率l 的方式存在一条不被发现的网络穿越路径。相反，当节点密度大 于该临界密度时，无论目标如何移动，能够以概率1 的方式保证检测到该目标。 l i u 2 4 分别讨论了布尔感知模型以及概率感知模型下，节点分布满足p o i s s o n 点 过程的随机无线传感器网络的覆盖比例、保持网络原始覆盖质量所能关闭的节点 数以及网络对移动目标的检测能力与节点密度之间的关系。 栅栏覆盖问题和点覆盖问题的区别在于覆盖的目标位置是不是确定的。 ( 3 ) 区域( 面) 覆盖 区域覆盖是覆盖问题中最常见的也是被研究的最多的问题之一。区域覆盖 1 3 江苏大学硕士研究生毕业论文 ( 如图2 3 ) 要求工作节点的传感范围完全覆盖整个目标区域，即目标区域中的 任意一点能够至少被一个工作节点覆盖。在区域覆盖问题中考虑最多的是如何能 够使网络区域中的每个点均被传感器节点覆盖。除了理论上完全覆盖问题的研究 外，节约能量的区域覆盖优化和移动节点覆盖引起了越来越多的关注。 图2 - 3 区域覆盖 节约能量的区域覆盖优化是指如何用最少的节点完成对被监测区域的完全 覆盖。c h e n 2 5 设计了一种基于网格划分的活跃工作节点选择算法。该算法用网 格点作为网络覆盖区域的近似，使用集合覆盖问题和线性规划问题对该问题进行 抽象，试图选择尽可能少的活跃节点来覆盖全部网格点。z h a n g 2 6 等人考虑如 何使用最少数量的节点来保持无线传感器网络的原始覆盖质量以及维持网络的 连通性。z h a n g 等人在证明了若节点的通信范围如至少两倍于节点感知范围 咫( 舻2 咫) 时，如果活动节点能够覆盖整个监测区域，则该节点集合也是连通的。 根据这个结论，提出了一个分布式的节点密度控制算法o g d c 。算法以轮次循环 运行，每轮开始时，随机选择开始节点并广播消息。当节点接收到广播消息后， 根据其邻居信息、自己的位置信息，计算是否被邻居节点所覆盖。对于r p 2 咫的情 况下，k 重覆盖的网络一定是k 度连通的网络，并提出了一种旨在为网络中不同 区域实现不同覆盖等级的覆盖配置协议c c p 。其基本思想仍然是通过减少活跃工 作节点数量，降低系统整体能耗，延长网络生存时间。当节点通信半径尺口不小于 2 倍感知半径b 时，c c p 协议能够保证活跃节点组成的网络的连通性。另外在随 1 4 江苏大学硕士研究生毕业论文 机分布的传感器节点区域监测中，节点的的工作调度直接影响着网络的使用寿 命，也有很多的研究着重于工作节点的调度。y a n 2 9 提出了一种可以为目标区 域不同点提供不同覆盖质量的节点调度算法。网络生存时间被划分为若干等长的 时段。在每个时段初期，节点首先随机产生一个位于该时段内的参考时间点。此 外，该算法使用离散网格点作为网络覆盖区域的近似，并使用网格点来判断目标 区域是否被充分覆盖。对于落在其覆盖范围内的每个网格点，节点根据自身的参 考时间点以及该点被邻居节点覆盖的情况决定相对于该网格点的工作周期。节点 在每个时段内的工作周期为针对其覆盖范围内全部网格点的工作周期的并集。 在节点相对稀疏、或者存在障碍和覆盖盲区的区域覆盖应用中，引入移动节 点，帮助改进覆盖性能。我们将在第四章介绍相关内容。 2 2 2 算法的评价指标 无线传感器网络覆盖控制技术的应用，有助于节点能量的有效控制、感知服 务质量的提高和网络寿命的延长，此外也会带来数据传输、管理、存储和计算等 代价的提高，所以无线传感器网络覆盖控制算法的性能评价标准对于分析一个覆 盖控制算法的可用性与有效性非常重要。 ( 1 ) 覆盖能力 无线传感器网络最基本的