搜索
第2章无线传感器网络结构、覆盖与连接2.1网络结构无线传感器网络拓扑结构1.平面网络结构平面网络结构是无线传感器网络中最简单的一种拓扑结构，所有节点为对等结构，具有完全一致的功能特性，也就是说每个节点均包含相同的MAC、路由、管理和安全等协议。特点：拓扑结构简单，易维护，具有较好的健壮性优点：源节点和目的节点之间存在多条路径，网络负荷由这些路径共同承担，一般不存在瓶颈缺点：影响传输速率，甚至造成网络崩溃；耗能巨大；可扩充性差传感器节点图2-1无线传感器网络平面网络结构2.分级网络结构如图2-2所示，分级网络结构(也叫层次网络结构)是无线传感器网络中平面网络结构的一种扩展拓扑结构，网络分为上层和下层两个部分：上层为中心骨干节点；下层为一般传感器节点。一般传感器节点图2-2无线传感器网络分级网络结构网络上层骨干节点网络下层分级网络结构优点：大大减少了网络中路由控制信息的数量，具有很好的可扩充性；簇头可以随时选举产生，具有很强的抗毁性缺点：簇头能耗大，很难进入休眠状态3.混合网络结构如图2-3所示，混合网络结构是无线传感器网络中平面网络结构和分级网络结构的一种混合拓扑结构，网络骨干节点之间及一般传感器节点之间都采用平面网络结构，而网络骨干节点和一般传感器节点之间采用分级网络结构。一般传感器节点图2-3无线传感器网络混合网络结构网络上层骨干节点网络下层4.Mesh网络结构Mesh网络结构是一种新型的无线传感器网络结构，从结构来看，Mesh网络是规则分布的网络，不同于完全连接的网络结构，如图2-4所示。通常只允许和节点最近的邻居通信，如图2-5所示。网络内部的节点一般都是相同，因此Mesh网络也称为对等网。传感器节点图2-4完全连接的网络结构传感器节点图2-5无线传感器网络Mesh网络结构如图2-6所示，采用分级网络结构技术可使Mesh网络路由设计要简单得多，由于一些数据处理可以在每个分级的层次里面完成，因而比较适合于无线传感器网络的分布式信号处埋和决策。图2-6采用分级网络结构技术的Mesh网络结构4×4Mesh网格分级分簇网络4.Mesh网络结构仁回顾无线传感器节点的限制条件包括：电源能量有限、通信能力有限、计算和存储能力有限无线传感器能耗模块包括：传感器模块、处理器模块、无线通信模块无线通信模块能耗大小：发送接收≈空闲睡眠通信能耗与通信距离关系：无线传感器网络关键性能指标：网络的工作寿命、网络的覆盖范围、网络搭建成本和难易程度、网络响应时间无线传感器网络覆盖无线传感器的覆盖与连通问题是无线传感器网络的基本问题。无线传感器网络的覆盖面积是用于衡量无线传感器网络测量性能的一个重要指标覆盖是对目标监控区域探测性的一种度量研究的目的:(1)使待检测区域中的每一点都至少在一个传感器节点的覆盖范围内。(2)在保证覆盖要求的基础上，同时减少网络节点能量消耗、延长网络寿命。节点特性：覆盖性：r连接性：C覆盖性与连接性的关系：C=2r无线传感器网络覆盖的计算一、AndrewHoward等专门针对移动无线传感器网络提出了一种增量自我配置的贪婪算法(CreedyandIncrementalSelf-deploymentAlgolithm)。算法的基本思想：就是每次配置一个节点到未知区域，每个加入的节点都充分利用先前配置的节点收集到的信息来确定其最佳目标位置。该算法的核心：就是贪婪和增量，该算法的复杂度为O（n2），其中n为配置的传感器节点数目。算法设计的目的：就是使网络的覆盖最大化，而同时又确保节点彼此保持视距通信，即本地化。无线传感器网络覆盖的计算二、A．Howard等提出了基于电势场技术的未知环境移动传感器网络的部署配置方法，网络内的节点可以随意扩展，使得网络覆盖最大化。算法的基本思想：就是将传感器节点当做假想的物粒子，且受到势力场的势力。势力压迫节点彼此之间和障碍物之间发生作用力。通过节点的初始简易配置快速地在整个网络扩散，从而最大化网络的覆盖。该算法的核心：就是利用了电势场技术，该算法具有较高的鲁棒性和扩展性。无线传感器网络覆盖的计算三、Huang和Tseng提出了一种基于传感器数目的多项式时间算法，将覆盖问题抽象表述为一个决策问题，并验证了一个传感器配置是否提供了k阶覆盖。该算法的目标：就是确定无线传感器网络服务区域中的每个点是否至少被k个传感器节点监视覆盖。四Gupta提出的算法是通过选择连接的传感器节点路径来得到最大化的网络覆盖效果。该算法同时属于连接性覆盖中的连接路径覆盖及确定性区域，点覆盖类型。当基站或汇聚中心向无线传感器网络发送一个感应区域查询消息时，连接传感器覆盖的目标是选择最小的连接传感器节点集合并充分覆盖无线传感器网络区域。Gupta分别给出了集中与分布式两种贪婪算法。2．无线传感器网络覆盖的计算如图2-9所示为该贪婪算法执行的方式，在如图2-9(a)所示中，贪婪算法会选择路径P2，得到如图2-9(b)所示，这是由于在所有备选路径中选择B3和B4组成的路径P2可以覆盖更多未覆盖子区域。图2-9连接传感器网络覆盖的贪婪算法B1P1B2K5K6B4P2B3(a)B1P1B2B5K6P4(b)P32．无线传感器网络覆盖的计算该连接传感器网络覆盖的贪婪算法的主要思想是：首先从M中最新加入的候选节点开始执行，在一定范围内广播候选路径查找消息，收到候选路径查找消息的节点判断自身是否为候选节点，如果是，则以单播方式返回发起者一个候选路径响应消息。发起者选择可以最大化增加覆盖区域的候选路径，更新各参数，算法继续执行，直到网络查询区域可完全被更新后的M所覆盖。2．无线传感器网络覆盖的计算无线传感器网络覆盖的一般准则：①已知传感器节点的通信距离（C），可以通过提出的方法得知所需配置的节点数，然后选择适当的感知覆盖半径（r）②已确定传感器感知覆盖半径，可先计算出布置的节点数，然后选择合适的通信距离或调整控制传感器节点功率大小③通信距离和感知覆盖半径都确定的情况下，只有增加或减少节点数来满足给定的最低连接可靠性和成本设计要求。如图2-10所示给出了一个无线传感器网络覆盖算法和协议分类。无线传感器网络的覆盖算法和协议分类部署和配置方式应用特点确定性覆盖随机覆盖能效覆盖障碍覆盖连接覆盖目标定位位置覆盖区域或点覆盖路径或目标覆盖基于Grid的覆盖随机节点覆盖动态覆盖最佳最差覆盖基于暴露的覆盖激活节点集覆盖路径覆盖图2-10无线传感器网络覆盖算法和协议分类2．无线传感器网络覆盖的计算无线传感器网络覆盖算法分类按照节点配置方式确定性配置随机性配置确定性区域/点覆盖是指传感器节点位置已知的无线传感器网络要完成目标区域或目标点的覆盖。确定性网络路径/目标覆盖还特别考虑了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪。随机覆盖考虑在网络中传感器节点随机分布且预先不知道节点位置的情况下,网络完成对检测区域的覆盖任务;（动态网络覆盖则是考虑一些特殊环境中部分传感器节点具备一定运动能力的情况,该网络可以动态完成相关覆盖任务.）按照不同覆盖目标面覆盖点覆盖边界覆盖面覆盖目的：是最大化无线传感网络覆盖(监测)范围能效性随机覆盖方法该算法的设计目标：在大量冗余的节点中寻找能够覆盖同样区域大小并保证网络连通的节点集合；获取最长的网络生存时间及能量高效性为满足能耗的限制采取的方法：节点集合化区域集合化动态能量管理策略目前无线传感网络覆盖问题的研究通常考虑网络随机初始化布置时各节点的位置和工作状态的优化问题，其目标是通过控制各节点的位置和工作状态提高无线传感网络的覆盖和能效性。方法一（节点集合化）由于无线传感网络中布置的节点数量远大于监测所需的数量，因此部分覆盖算法中将无线传感节点分为若干个分散集合，每个集合都可以完整地覆盖整个被监测区域。在监测过程中，同时间段内有且仅有一个集合处于工作状态，其它集合则进入低功耗的休眠状态（能耗低）。各集合通过轮休节约网络能耗。由此可知，通过最大化可用集合的数量，可以延长各节点切换到工作状态的时间，从而延长网络寿命。1.能效性随机覆盖方法方法二（区域集合化）除了将节点划分为不同集合外，还可以把测量区域划分成许多地域的集合，使每个区域集合中的任何一点都被同一个传感节点集合所覆盖。采用最大约束-最小约束算法能有效计算这些分散的覆盖区域，选择覆盖临界区域的传感节点，并为传感节点的布置提供被测区域的先验知识，让传感节点能够密集布置于未覆盖区域，提高网络覆盖率。同时，还可以通过非轮值检测规则检查各节点监测区域是否与其周围节点感知区域相重合，如重合则让其中部分节点处于休眠状态，这样也可以有效减少网络中工作节点的数量，提高网络能效性。1.能效性随机覆盖方法（动态能量管理策略）符合非轮值规则的节点---关闭自身通信和感知单元。相邻节点同时触发非轮值规则---延时---采用非轮值评价规则对自身工作状态进行评价---结果显示可以进入---对外发布广播消息并转入休眠。方法三基于探针的能效性无线传感网络动态能量管理策略是另一种常见的无线传感网络覆盖优化方法。该方法首先假设所有节点具有相同的感知区域。在网络工作过程中，每个无线传感节点将向距离小于r的所有节点发送一条探针消息PRB，所有工作节点在接收到该消息后返回一条PRB-RPY消息。如果发出指令的节点收到至少一条回复，则节点进入休眠状态。范围r的选择由期望工作节点密度和期望覆盖冗余度决定。1.能效性随机覆盖方法2.连接性随机覆盖方法除了网络能效性外，无线传感网络的连接性也是网络性能的重要评价指标。当任一激活节点都能与其余激活节点通信时，网络则处于连通状态。当节点布置完毕后，网络中的节点必须能够相互连通，获取的信息才可以返回接收器或控制器中。保证监测区域的覆盖性和节点的有效连通性对于确保网络测量性能而言都是十分重要的。以下将介绍几种用于提高无线传感网络连接性的随机覆盖方法。连接性随机覆盖方法连接性随机覆盖方法分布式最优地理密度控制算法覆盖结构协议设计目标：确保网络的连接性，保证节点间相互通信分布式最优地理密度控制算法(OGDC，OptimalGeographicalDensityControl)。该算法假设在任何时刻，节点可能处于以下3个状态中的一种：未决定、开和关。网络初始化时，随机激活若干个无线传感节点。而后这些节点将在网络中广播“能源开”的信息，同时将其自身状态设置为开。所传递的信息包含两部分：①发送者的位置；②下一个工作节点的位置与方向。网络中每个节点都保留邻近节点的信息列表。2连接性随机覆盖方法覆盖结构协议(CCP，CoverageConfigurationProtocol)是另一种用于优化网络连接性的网络协议。该协议能动态组织网络，为各类应用提供不同的覆盖度。为提高算法运算速度，每个节点都包含周围节点的信息列表，并周期性的发送信息以广播自身的位置和状态。2.连接性随机覆盖方法点覆盖该算法要覆盖的目标：是一些离散的目标点.在点覆盖算法中,每一个目标点都要能够被至少一个传感器节点所覆盖随机性点覆盖确定性点覆盖要求每个目标在任意时间内都能至少被一个无线传感器节点监测最大化传感器节点集合的数量研究目标：采用最少数量的无线传感器节点对确定的目标点集进行监测假设所有传感器具有相同的感知范围通信范围=感知范围2.2.3无线传感网络的边界覆盖1．边界覆盖模型I当前研究的边界覆盖问题包含两种边界覆盖模型。第一种模型为：在一个区域中布置了无线传感节点，已知一个要穿过该区域物体的起始和终止位置，测定该物体的最大突破路径(MBP，MaximalBreachPalh)和最大支持路径(MSP，MaximalSupportPath)。MBP和MSP分别与最差和最优覆盖相关，分别对应于使路径中的每个点与最近的无线传感节点之间的距离最大(最小)的情况。实验证明，MBP位于Voronoi图线上，MSP位于Delaunay三角测量线上。“最大突破路径”和“最大支撑路径”分别使得路径上的点到周围最近传感器的最小距离最大化及最大距离最小化。这两种路径分别代表了无线传感器网络最坏（不被检测概率最小）和最佳（被