基于网格的k覆盖多连通WSN节点部署研究.doc

硕士专业学位论文论文题目基于网格的k覆盖多连通WSN节点部署研究研究生姓名指导教师姓名专业名称研究方向论文提交日期陈娟徐汀荣计算机技术网络技术与信息安全2014年5月 基于网格的 k覆盖多连通 WSN节点部署研究中文摘要基于网格的 k覆盖多连通 WSN节点部署研究中文摘要无线传感器网络(Wireless Sensor Networks，简称 WSN)是由大量密集部署在监测区域的无线传感器节点构成的采用自组织、多跳、无线通信方式的大规模网络系统。无线传感器网络适合大规模部署，广泛应用于军事、环境监测、医疗卫生和预报系统等领域。无线传感器节点的有效部署是组网及网络高效稳定工作的前提。考虑到无线传感器节点的脆弱性和能量存储量低等特点，为了组建一个高稳定性和高容错能力的网络就必须对监测区域实现 k覆盖和多连通部署。本文主要工作如下：(1)分析了现有的 DESK节点部署算法，该算法将对区域的 k覆盖转换成对节点覆盖周界的 k覆盖。算法通过与邻居节点之间的通信来判断本节点的周界覆盖度。本文使用让步机制改进了该算法，用于控制 DESK的参与竞争的节点数目，节约了节点的能量损耗，延长了网络的工作寿命。(2)针对现有节点部署算法，考虑到覆盖度和连通性的分布式节点部署算法多是以节点的通信半径大于等于 2倍的感知半径为前提，本文提出一个在通信半径小于 2倍感知半径情况下的分布式节点部署算法，将监测区域划分成网格，使用轮次工作机制，根据节点的能量和对网格覆盖贡献度选择出活跃状态节点集合，使得监测区域达到 k覆盖，节点达到多连通。关键字：无线传感器网络；节点部署；k覆盖；多连通；让步机制作者：陈娟指导老师：徐汀荣教授I AbstractResearch on Grid-based WSN Deployment for k-Coverage and Multi ConnectivityResearch on Grid-based WSN Deployment for k-Coverageand Multi ConnectivityAbstractWireless Sensor Network (WSN) is a mass high-density network system which iscomposed of a dense of wireless sensor nodes deployed in the monitoring area usingself-organization, consisting of multiple hops communication mode. It is suitable forlarge-scale deployment and widely used in military, environmental monitoring, health careand forecasting system, etc. The effective deployment of wireless sensor nodes is theprecondition of networks efficiency and stable working. Considering wireless sensornodes characteristics of vulnerability and low energy storage, we should make suremonitoring area is covered with sensor nodes in k coverage and multiply connected to forma high stability and high fault-tolerance network.The main work of this paper:(1) This paper analyzes the existing wireless sensor node deployment algorithmDESK. The algorithm converts regional k-cover to nodes perimeters k-cover. And judgenode perimeter k coverage through the communication between the neighbor nodes. Thispaper uses the concession mechanism to improve the DESK algorithm by controlling thenumber of the competition nodes to participate in the DESK. This improvement saves thenodes energy, so it can prolong the life of the network.(2) In view of the existing node deployment algorithms, the distributed nodedeployment algorithm that considered both the coverage and connectivity usually based onpremise of node communication radius is greater than or equal to 2 times of the senseradius. In this paper, we propose a distributed node deployment algorithm that is based onpremise of the communication radius is less than 2 times the radius of perception. In thisalgorithm, we divide monitor area into grids and use the rounds work mechanism,according to the energy of nodes and its coverage contribution for the grid to choice somenodes into active state. And make the monitoring area achieve k-cover and multiplyII Research on Grid-based WSN Deployment for k-Coverage and Multi ConnectivityAbstractconnected.Keywords: Wireless sensor network (WSN); Node deployment; k coverage;Multiply-connected; Concession mechanismWritten by：Chen JuanSupervised by：Xu TingrongIII 目录第一章绪论 . 11.1无线传感器网络的研究背景及意义.11.1.1研究背景 . 11.1.2研究意义 . 11.2无线传感器网络的关键技术.21.3国内外研究现状 .41.4本文的主要工作 .51.5论文组织结构 .6第二章背景知识 . 72.1无线传感器网络 .72.1.1无线传感器网络的基本概念. 72.1.2无线传感器网络的特征. 82.2无线传感器节点模型与节点部署.92.2.1无线传感器节点模型. 92.2.2无线传感器网络节点部署. 102.3 k覆盖多连通节点部署 .142.3.1 k覆盖多连通节点部署. 142.3.2技术指标 . 152.4本章小结 .16第三章改进的分布式能量有效 k覆盖部署(DESK)算法. 173.1引言 .173.2问题分析 .173.2.1 DESK算法. 173.2.2算法不足与改进. 213.3算法性能分析 .253.3.1改进后算法的正确性. 25 3.3.2时间复杂度 . 253.3.3实验仿真 . 253.4总结 .28第四章基于网格的分布式能量有效 k覆盖多连通部署算法. 294.1引言 .294.2相关问题描述 .304.2.1网络模型 . 304.2.2问题分析 . 314.3基于网格的分布式无线传感器网络 k覆盖多连通部署算法.324.3.1主要过程 . 324.3.2网格的划分及优先级计算. 344.3.3算法正确性分析. 364.4实验仿真 .384.5总结 .43第五章总结和展望 . 445.1本文工作总结 .445.2展望 .44参考文献 . 46攻读硕士学位期间本人的科研论文. 51致谢 . 52 基于网格的k覆盖多连通 WSN节点部署研究第一章绪论第一章绪论1.1无线传感器网络的研究背景及意义1.1.1研究背景无线传感器网络(Wireless Sensor Networks，简称 WSN)是由大量密集部署在监测区域的传感器节点构成的采用自组织、多跳路由协议、无线通信方式的网络系统。随着微电子技术和无线通信技术的发展，传感器网络作为收集信息最基本的技术也得到了发展，传感器节点变的越来越廉价、功能变得越来越多样。传感器的信息获取技术也已经从单一化逐渐转向集成化、微型化和网络化。根据实际应用的需要，传感器节点上通常会集成各种具有不同功能的传感器，如温度传感器、湿度传感器、噪声传感器、光强度传感器等。WSN通常由大量部署在监测区域的传感节点组成。这些节点会以无线通信的方式自组织构成网络，进行信息采集、处理和传输等任务，以完成对监测区域的监测。相比于早期的传感器节点，现在的传感器价格更低廉，所以，无线传感器网络也适合大规模的部署。1.1.2研究意义无线传感器网络广泛应用于军事监控、环境勘测、医疗卫生和预报预警系统等领域：(1)军事应用12在军事领域中，无线传感器网络主要应用于侦听军事命令、通信与计算、侦察敌方目标等方面。传感器网络的自组织性和较高的容错能力等特征使其成为军事中有很好发展前景的监测和通信技术。军事应用中，会在传感器网络中部署大量节点，因此敌方对网络中部分节点的破坏不会影响整个网络的工作。所以，传感器网络适用于环境恶劣的战场中，其主要应用包括对冲突区域的监控、对敌方地形和布防的侦察、定位攻击目标等。(2)环境监测3随着人们对环境的关注越来越多，人们对环境科学的研究也变得越来越广泛。传统的数据采集方式使得危险和恶劣环境中信息的采集工作变为一项比较困难的工作。1 第一章绪论基于网格的k覆盖多连通WSN节点部署研究无线传感器网络的出现为危险或恶劣环境下的数据采集提供了方便，传感器网络在环境监测方面的应用包括：跟踪动物的迁移、探测环境变化对人和动物的影响、森林火灾监测、气象或地质研究和环境污染监测。在 2012年，美国加州大学伯克利分校的研究小组利用二氧化碳传感器监测当地的二氧化碳排放量的监测4。国内将无线传感技术用于太湖蓝藻爆发的预警56。(3)医疗健康78WSN在医疗健康护理方面也有广泛应用。例如，医生通过在病人身上安装能测量人体心率或者血压传感器节点对病人进行诊断，从而可以随时了解病人的身体状态，进行及时的治疗和处理。除此之外，无线传感器网络还可应用药物管理。通过将传感器节点按药品种类分别放置，可帮助辨认药品，从而降低病人用错药物的可能性。(4)智能家居智能家居系统的目标是将住宅中各种家居设备联系起来，使它们能够自动运行，相互协作。用户可以在家电和家具中嵌入传感器节点，再将这些传感器节点通过无线网络与互联网连接，就可以实现对家居设备的远程智能控制，从而使人类的家居环境变得更加舒适和智能化。例如，用户可以在办公室远程控制家里的空调、电视、冰箱等。(5)城市车辆检测和跟踪传感器网络可以用于城市交通系统以实现对车辆的监测和跟踪。通过在城市车辆上嵌入声音、图像、视频、温度、湿度等传感器节点，实现对车辆及其周围环境的监测。在无线传感器节点中装入 GPS全球定位系统后，还可以实现对车辆的跟踪，为司机提供最佳行驶路线等功能。综上所述，WSN在军事、环境监测、生活等领域都具有广阔的应用前景，对人类的生产生活也会产生重大的影响，无线传感器网络的研究有着深远而重大的意义。1.2无线传感器网络的关键技术WSN是一门交叉学科，涉及到微机电系统、计算机、通信、自动控制、人工智能多个学科领域，因此对于 WSN的研究需要许多关键技术作为支撑。下面就列出一些 WSN的关键技术：(1)时间同步机制2 基于网格的k覆盖多连通 WSN节点部署研究第一章绪论WSN的许多应用需要时间同步，因此时间同步机制对于 WSN具有重要意义。传感器网络需要大量的传感器节点相互合作才能完成对环境感知和信息获取等任务，那么，就需要整个网络系统时间同步。另外，在实际应用中，当系统采用节能策略时，大部分节点会处于休眠状态。那么，节点的时间必须同步，才能保证休眠的节点被及时唤醒，在数据到来时，节点的接收器处于打开状态。(2)定位技术传感器节点采集数据中节点位置信息是不可缺少的一部分，不知道节点的位置信息就不能够了解在什么位置发生某个事件。另外，定位技术还有辅助提高路由效率，实现网络拓扑子配置，便于用户了解网络的覆盖质量等功能。(3)无线通信技术传感器节点之间相互通信的方式是无线通信，那么 WSN就离不开无线通信技术的支持。另外，由于传感器接的能量和带宽有限，传感器节点通常使用低功耗短距离的无线通信技术。IEEE802.15.4标准的网络特征与 WSN存在很多相似之处，因而一些研究机构通常会将它作为 WSN的无线通信平台。(4)能量管理技术传感器节点大多使用电池供电，存储的能量十分有限，因此如何有效的节省节点能量，延长网络的生命周期也是设计 WSN时需要考虑的问题之一。轮次工作机制和数据融合是目前常用的节能策略。传感器节点的主要能耗单元包括传感器部件、处理器部件、通信部件。传感器节点可以通过关闭某个不需要工作的部件来节约节点的能量消耗。例如，相比其他模块，通信模块的能量消耗较多，所以节点可以在不需要传输数据时将通信模块关闭，以达到节约能耗的目的。(5)数据融合技术数据融合是指节点将来自多个信息源的数据进行优化处理，从而获得更准确完整的信息。由于单个传感器节点的感知能力、能量储存能力有限，传感器网络通常会在监测区域中部署大量的节点。这样，可能会出现多个节点重叠监测同一片监测区域，导致一些节点采集的信息冗余。这种情况下，节点可以将这些冗余信息进行融合后再发送到汇聚节点。这样不仅能够获得完整的信息也能一定程度上减少需要传输的数据量，从而节约能量，减少网络拥塞。3 第一章绪论基于网格的k覆盖多连通WSN节点部署研究(6)网络安全技术对于任何网络，网络安全都是一个重要问题，无线传感器网络也不例外。 WSN采用的无线通信方式使其面临着窃听、消息篡改等安全问题。目前国内外学者已经对WSN各个层次的网络协议可能受到的攻击进行了研究，并给出了相应的防御手段。1.3国内外研究现状针对 WSN节点部署，国内外学者也已经作了大量研究，下面将简单介绍一些WSN节点部署算法。节点覆盖方法9可以是集中式的、分布式或者局部的。对于集中式的算法，根据整个网络的信息，由某个决策节点计算并决定节点的部署。例如：Anthony等人10提出的应用 Verona图的覆盖判定方法，利用 k序 Voronoi图的概念来检验网络覆盖度。文献中作者证明：若有界 Voronoi图的所有 Voronoi顶点被 k覆盖则整个目标区域也被 k覆盖。因此，算法先采用求得 k序 Voronoi图和Voronoi顶点，然后分别检验以下三类顶点是否被 k覆盖：(1)监控区域中的 Voronoi顶点；(2)区域边界与 Voronoi多边形的交点；(3)区域的边界。算法的时间复杂度主要由计算 k序 Voronoi图的时间复杂度决定，为 O(nlogn+nk2)。所以该算法的时间复杂度为 O(nlogn)，n为部署的节点数目。该算法利用了 Voronoi图的有关性质，计算结果比较准确。但这是一个集中式算法，并且计算 k序 Voronoi图时，需要节点定位准确，运行速度较慢、效率低、对决策节点的通信能力和能量要求很高。Huang等11设计了一种基于节点感知范围的周界覆盖的集中式 k覆盖判定算法。该算法是针对圆盘感知模型的节点部署算法。当监测区域中部署有足够多的传感器节点且每个节点的位置确定已知。该算法中首先确定每个传感器节点的覆盖圆盘，再对所有节点进行判断并计算后获得整个网络的覆盖范围。文献中作者证明了无论所有节点的感知半径是否相同，该区域能被节点集 k覆盖的充分条件是监测区域中所有节点的感知圆盘的周界能被节点集 k覆盖。该算法将整个监测区域的 k覆盖情况判断转化为所有节点的感知圆盘的周界 k覆盖。该算法主要优点是在异构网络中也同样适用，即网络中各节点的感知半径不同时该算法也适用。其缺点是对中心节点要求高且该算法复杂度偏高，在大规模应用时效率较低。文献12使用了线性规划技术来确定使监测区域达到需要的覆盖度的最小节点集4 基于网格的k覆盖多连通 WSN节点部署研究第一章绪论合。该算法中使用的模型是二维和三维的点阵网格，并且分析了如何定位目标的问题。该算法的前提条件是每个传感器节点都能够直接与数据汇集点通信，因而并未考虑网络的连通性。该文中，作者还对需要部署的节点数目的边界进行了分析。分布式或局部算法中节点根据自己和周围邻居的信息自主决定本节点的状态。例如 Wang等人13将 CCP和 SPAN协议相结合的方法实现网络的覆盖度和连通性。CCP算法思想和周界覆盖方法思想类似，两者都利用了凸区域的性质，将区域的覆盖度检测转化为节点覆盖边界检测。但与基于周界覆盖检测方法不同的是， CCP算法中考虑的是节点的感知圆盘之间的交点，以及感知圆盘与监测区域边界的交点。该文中作者证明了当所有的交叉点都能被 k覆盖时，整个监测区域就能被 k覆盖。因此，节点可以利用邻居节点信息确定出本节点感知范围内的交叉点，再根据这些交叉点的覆盖情况自主地确定自己的状态。CCP算法是一个分布式的控制策略，节点局部的、同时的、自主地确定节点的状态，效率高于集中式算法。1.4本文的主要工作本文主要研究了无线传感器网络的节点部署算法。节点部署是 WSN组网并稳定高效工作的前提条件，有较大的研究价值。文中分析了 k覆盖多连通节点部署算法的研究背景、意义以及研究现状，总结了现有的一些算法的优缺点。本文的主要工作如下：(1)使用让步机制改进了分布式能量有效 k覆盖部署算法。在分布式能量有效 k覆盖部署算法(DESK)29，每轮开始时，所有节点都参加竞争，所有的节点都处于侦听状态。一些剩余能量较少的节点进入活跃状态的机会很小，而参加竞争时侦听状态会消耗较多的能量。在 DESK算法中使用让步机制，能让竞争成功率较小的节点休眠的时间变长，减少侦听时消耗的能量，利于延长网络寿命。实验分析证明，该方法可行。(2)提出了基于网格的分布式 k覆盖多连通节点部署算法。以往的分布节点部署算法基本都是建立在通信半径大于等于 2倍感知半径假设前提下。当节点通信半径小于 2倍感知半径前提下都是采用集中式算法，并且大都未考虑网络的连通性。本文在通信半径小于 2倍感知半径情况，提出的基于网格的分布式 k覆盖多连通节点部署算法。并通过实验分析和理论证明了算法的正确性。5 第一章绪论基于网格的k覆盖多连通WSN节点部署研究1.5论文组织结构本文的组织结构安排如下：第一章，主要介绍了 WSN的研究背景、意义以及一些关键技术。另外，还介绍了节点部署算法的国内外研究现状以及本文主要工作和组织结构。第二章，简单介绍了无线传感器网络相关的一些基本概念与特征、与本文研究内容相关的无线传感器网络模型等背景知识。给出了轮次工作机制的概述、k覆盖、多连通等相关的定义以及评价节点部署算法的技术指标等。第三章，首先介绍分布式能量有效 k覆盖部署(DESK)算法，分析了该算法的优缺点。然后，提出了让步机制，并用其改进了 DESK算法。最后，利用实验仿真验证了改进后算法可行性。第四章，提出基于网格的分布式 k覆盖多连通节点部署算法。该算法是一个在通信半径小于 2倍感知半径情况下组建健壮 WSN的分布式节点部署算法，将监测区域划分成网格，使用轮次工作机制，根据节点的能量和对网格覆盖贡献度选择节点转为活跃状态，使得监测区域达到 k覆盖，节点达到多连通。理论和实验验证了算法的正确性。第五章，对本文所做工作和研究进行总结，并展望本文还需要进一步研究的内容。6 基于网格的k覆盖多连通 WSN节点部署研究第二章背景知识第二章背景知识本章主要介绍了无线传感器网络相关的基本概念与特征、跟本文研究内容相关的节点模型等背景知识。给出了轮次工作机制的概述、k覆盖、多连通等相关的定义以及评价节点部署算法的技术指标等。2.1无线传感器网络2.1.1无线传感器网络的基本概念无线传感网络(WSN)，是由低成本、密集型节点组成的自组织的网络系统。无线传感器节点之间采用无线通信的方式通信，节点间相互协作，采集信息，并将信息处理后通过多跳无线路由协议，将信息通过网络传输给用户。如图 2-1所示，传感器节点将收集的信息处理后传输给 Sink节点，最终传输到基站。图 2-1无线传感器网络体系结构图网络中的每个节点不知道自己与其它节点的相对位置，因此传感器网络必须使用定位技术和自组织协议，将区域中所有节点自动组织成一个网络，使得节点收集到的信息能通过路由协议传输到基站。基站会将收集到的数据通过互联网、卫星或其他传输媒介传送到服务器，即用户手中。典型的无线传感器节点由四个部分组成14：1感知单元(Sensing Unit)感知单元，负责感知监测环境，并将搜集到的数据用模拟信号表示，再将收集到7 第二章背景知识基于网格的k覆盖多连通WSN节点部署研究的模拟信号转换成数字信号，最后将数据传送到处理单元。2处理单元(Processing Unit)处理单元主要包含两个部分：储存器，节点将收集到的信息储存在储存器中；嵌入式处理器，负责执行程序代码，协调并控制不同的单元组件。处理组件可以根据程序指令，对感知单元收集的数据进行处理，再通过传输单元将数据发送回去。3传输单元(Transceiver Unit)传输单元也称为通信单元，负责各个传感器节点之间的通信，或是将传感器的数据传送给基站。4电源(Power Unit)电源提供传感器中所有单元的能量。2.1.2无线传感器网络的特征无线传感器网络除了具有 Ad Hoc网络的断接性、无线通信、电源能量有限等特征外，还有很多其他特点。以下为无线传感器网络的特点：(1)可大规模部署无线传感器网络往往由大量的无线传感器节点组成，大规模的部署在恶劣环境中。其中包括一些人难以或无法进入的环境，如火山、海底、火灾现场等。(2)自组织与自适应能力当节点部署到监控区域后节点会通过自组织算法与周围节点进行通信，形成一个无线网络。节点失效或移动后，网络能够重新调整达到稳定的工作状态。(3)数据处理能力无线传感器节点中的处理器和存储器可以将收集到的信息处理后发送给基站。(4)多跳通信无线传感器节点之间采用的多跳传输方式，相比传统的单跳传输方式不仅更能节约能量，还可以克服长距离信号传输过程中的信号衰弱、噪声等问题。无线传感器节点有下几个特点：(1)能量有限现有的节点一般采用电源供电。当节点电源能力耗尽时，节点就会失效。由于无线传感器网络大多部署于人难以或无法到达的环境，因此，很难为传感器节点更换电8 基于网格的k覆盖多连通 WSN节点部署研究第二章背景知识池。尽可能减少耗能是算法设计时需要考虑的重要因素之一。(2)计算、存储能力有限受能量的限制，传感器节点不能采用高能耗、高存储能力的处理器和存储器。所以，网络的计算机和存储能力都很有限。(3)通信带宽窄节点的能耗与传输数据的带宽和传输距离 k(2k4)次方成正比15。所以，同样受能量的限制，传感器节点大多采用低速、低电耗的 IEEE802.15.4等协议实现数据传输。2.2无线传感器节点模型与节点部署无线传感器网络是由大量的传感器节点组成，所以节点模型和节点部署是无线传感器网络组网的前提。节点的部署设计能影响网络的性能和使用寿命。2.2.1无线传感器节点模型假设无线传感器网络部署在一个 2-维欧式平面上，可以用一个无向图G(V (G),E(G)表示无线传感器网络。那么存在映射 f :V(G) 点v平面中都存在其位置 f (v)RR2，使得对于任意节2。同样的，对于每个节点v都存在一个区域 Av R2被节点v的无线发射范围覆盖到。对于不同节点 u，v，| f (u)- f (v) |表示两节点之间的欧式距离。常见的几种网络模型：(1)单位圆盘图模型(Unit Disk Graph)当监测区域中没有障碍物和干扰时，网络中的节点的感知半径相同为 Rs，且感知区域为以自身为圆心 Rs为半径的圆。假设部署于点 f (s)的传感器节点 s与位于 f (p)的任意点 p的欧式距离为| f (s )- f (p )，则该模型可表示为：Cp(s) = 1,| f (s)- f (p) | Rs2-1 0,otherwise式 2-1中Cp(s)为 p点被节点s覆盖的概率。(2)近似圆盘图模型(Quasi Disk Graph)169 第二章背景知识基于网格的k覆盖多连通WSN节点部署研究在受到环境干扰或有障碍物阻挡时，传感器节点的信号会受到影响，传感器节点的覆盖范围不一定为单位圆盘。可以设传感器节点的最大感知半径C和最小感知半径c。如果部署于点 f (s)的节点s与位于 f (p)的任意点 p的欧式距离| f (s)- f (p)| c，则 p点在节点 s的覆盖范围内；若 | f (s)- f (p)|C，则 p点不在节点 s的覆盖范围内；若c | f (s)- f (p)|C，则不能确定 p点是否在节点s的覆盖范围内。(3)覆盖区域图模型(Coverage Area Graph)17覆盖区域图模型是一种最一般的模型。对于网络中任意节点v，其覆盖区域 Av的形状不固定。(4)有界增长图模型(Growth Bounded Graph)18定义 2.1(r-hop邻居集)对于任意的vV(G)， N(v)表示v的 1-hop邻居顶点集，且v N(v)。当r 1， Nr(v) = N(Nr-1(v)表示v的 r-hop邻居顶点集。对于图 G中的任意的点 v和任意整数 r 1，都存在一个多项式函数 p，使得| I (Nr (v)| p (r成立，则称图 G是多项式有界增长图。 | I(Nr (v) |表示点v的r-hop邻居顶点集中极大独立集的基数。节点间的通信模型与感知模型类似。以单位圆盘图模型为例，任意两个节点 si，sj，| f (si)- f (sj)| Rc， Rc为节点的通信半径，则 si，sj直接可以相互通信，否则不能相互通信。现有的节点模型中，单位圆模型较常见，本文中节点也将使用单位圆模型。2.2.2无线传感器网络节点部署节点部署是在指定区域内，通过一定的方法布置传感器节点使其达到用户指定的需求。节点部署的合理性会直接影响到信息收集的准确性、完整性和时效性。合理的节点部署算法可以提高网络的效率、充分利用网络中的可用资源19。单个节点无论是计算能力还是通信能力以及电池能量储存等资源都极为有限。因此，实际应用中通常会采用密集部署大量节点的方式，通过成千上万的节点之间的协同而交替的工作达到用户的需求并延长网络寿命10。节点部署按照节点是否移动分为：固定节点部署和移动节点部署。固定节点部署是指节点一旦部署到目标区域，就不再移动。固定节点部署根据节点的分布又可以分为随机性部署和确定性部署。移动节点部署，指节点部署到目标区域后可以移动。10 基于网格的k覆盖多连通 WSN节点部署研究第二章背景知识(1)随机性部署2021随机性部署指采用随机抛撒的方式，如飞机播撒，将传感器节点大量部署于目标区域，通常认为节点在目标区域内呈均匀分布或高斯分布等，如图 2-2所示。这种部署方式适合应用于恶劣环境，人工无法或者难以靠近的区域或需要组建大规模网络的情况下。例如，火灾现场、海底探测等应用中。图 2-2随机性部署图 2-3正六边形部署(2)确定性部署22确定性部署是指监测区域确定且人工易到达，通过人工手动放置传感器节点，以保证使用最少数目的节点覆盖该区域。可根据节点位置确定网络拓扑情况或控制关键区域的传感器节点密度。此时覆盖问题，就成为一种网络或路径规划问题。典型的确定性部署有面或点覆盖、目标覆盖和确定性网络路径等类型 2324。文献25利用六形网格来部署节点，使得监测区域的覆盖达到最优，如图 2-3所示。确定性部署适用于环境状态良好且小规模情况，如室内入侵监测等。图 2-4运动性部署(3)移动性部署在有些应用中需要所有或者部分传感器节点能够移动，并且所形成的网络拓扑也11 第二章背景知识基于网格的k覆盖多连通WSN节点部署研究经常随之发生变化，如图 2-4所示。文献26所描述的算法就是这种情况。对于节点部署算法的研究目前主要是网络的覆盖度问题、连通性问题和能量消耗问题三个方面。(1)覆盖度问题传感器网络工作的首要目标是完全覆盖目标区域，减少一个现象或事件不被监测到的可能性，尽可能快速有效的收