第三章路由、覆盖与拓扑控制技术ppt课件.ppt

无线传感器网络技术及其应用,第三章 路由、覆盖与拓扑技术,3.1,3.2,无线传感器网络路由,无线传感器网络拓扑控制技术,无线传感器网络覆盖技术,3.3,3.1 无线传感器网络路由,1,2,无线传感器网络路由概述,路由协议设计的关键问题,简单的无结构路由协议,3,4,5,树类路由协议,地理路由协议,无线传感器网络路由协议比较,6,1,无线传感器网络路由概述,路由协议的作用是寻找一条或多条满足一定条件的，从源节点到目的节点的路径，将数据分组沿着所寻找的路径进行转发，由此可以看出路由协议的功能主要有两个方面：一、搜索满足条件的从源节点到目的节点的优化路径二、转发资料分组,1,1,无线传感器网络路由概述,传统有线网络的路由协议主要运行在路由器上，采用集中控制的路由寻找方法，即将整个网络拓扑、链路状态，如带宽、时延等信息收集并计算出相应的路由。无线自组织网络Ad-Hoc以及传统无线局域网WLAN的路由协议的设计目标是能够为终端用户提供高质量的服务，合理利用网络无线通信链路的带宽，避免发生网络拥塞，能够以较快的速度响应用户的服务请求。路由协议类型： 以数据为中心的路由协议 基于层次结构（树结构）的路由协议 基于地理信息路由协议 基于多路径的路由协议,2,无线传感器网络路由,2,1,路由协议设计的关键问题,无线传感器网络路由概述,简单的无结构路由协议,3,4,5,树类路由协议,地理路由协议,无线传感器网络路由协议比较,6,2,路由协议设计的关键问题,线传感器网络在设计路由协议时一个最重要的目标就是在传输数据的同时，最大限度地延长网络寿命并且避免网络连通性降低。因此，在设计路由协议时需要考虑到以下关键问题： 节点部署。部署方案：一、手工 二、随机 数据精确性前提下的能耗 以数据为中心的数据报告模型 鲁棒性与容错性 网络动态性 资料融合,1,无线传感器网络路由,3,1,简单的无结构路由协议,无线传感器网络路由概述,路由协议设计的关键问题,2,4,5,树类路由协议,地理路由协议,无线传感器网络路由协议比较,6,Flooding和Gossiping两个路由协议是传统网络中最为经典和简单的路由协议，它们都是基于洪泛机制的路由协议，可以应用到无线传感器网络中。,简单的无结构路由协议：Flooding和Gossiping路由协议,Flooding路由协议,Flooding路由协议不要求维护网络的拓扑结构和相关路由计算，仅要求传感器网络节点在接收到信息后以广播的方式向邻居节点转发数据包，邻居节点重复执行上述过程（转发时除去刚刚发送给它们的节点），直到数据包到达目的地或者该数据包的生命周期结束。特别指出的是，无线传感器网络中数据包的生命周期TTL，一般预先设定这个数据包所转发的最大跳数。,A,B,C,D,E,F,G,H,P,P,P,P,P,P,P,以此类推，直到p到大汇聚节点D或到达TTL,源节点A需要将数据包p发送至汇聚节点D,节点A首先将p的副本广播，则其邻居节点B接收到p副本,节点B直接将p副本通过广播的形式转发给E、F、C,Flooding路由协议优缺点,每个节点只需将接收到的数据包进行广播，而无需进行查找路由表，选择下一跳节点的计算，其次，其无需特殊的算法保持网络拓扑信息的更新以及新路由的发现。但是Flooding路由协议的漏洞也是十分明显且致命的，主要有以下3个方面。 信息内爆（Implosion）：所谓信息内爆是指网络中的节点收到一个数据的多个副本的现象。 部分重迭（Overlap）现象：由于无线传感器网络节点密集部署，因此在同一局部区域中，若干个节点对区域内同一个事件做出的反应相同，所感知的信息在数据性质上相似，数值上相同，那么这些节点的邻居节点所接收到的数据副本也具有较大的相关性。 网络资源利用不合理：每个节点只是单纯地将接收到的数据进行广播，并没有考虑到网络中节点能量消耗的问题，不能发现下一跳节点的可行性，从而不具备自适应性，造成网络资源浪费。尽管Flooding路由协议在数据传输时能量消耗巨大，网络生命周期一般较短，不适应大规模的网络，但其具有路径容错性好，传输延时短的优点，适用于对数据可靠性要求较高的应用场景。,Gossiping路由协议,Gossiping路由协议，即闲聊路由协议是对Flooding路由协议的改进，当节点接收到数据之后，并不是像Flooding协议那样，采用广播形式将数据包发送给所有邻居节点，而是按照一定概率随机地将数据包转发给邻居节点中不同于发送节点的某一个节点，这个节点以相同的方式向其邻居节点进行数据转发直到数据到达汇聚节点。Gossiping路由协议考虑了节点的能量消耗，因此在选择下一跳时只选择一个节点进行数据转发，但在每次选取下一跳节点时，并没有采用路径优化相关算法，因此所选择的路由往往不理想，这将导致数据包的端到端延时增加或者生命周期在没到达目的节点之前就结束。,D,s,初始设置每个数据包TTL=6,此时TTL=0，资料包在此处丢失，不再往下传至D,简单的无结构路由协议：SPIN路由协议,SPIN（Sensor Protocols for Information via Negotiation，信息协商的传感器协议）是无线传感器网络中一种基于数据中心的路由协议，其通过节点之间的协商以建立传输路径。SPIN协议的设计目标是能够解决Flooding以及Gossiping协议的内爆、重叠及资源利用不合理现象。SPIN协议在路由建立时，一共采用了3种类型的数据包：ADV、REQ与DATA。ADV数据包是一个路由请求发起的数据包，当某一节点接收到数据包时，它会向其周围的邻居节点广播这个ADV数据包，以通告是否需要接收数据，由于ADV数据包体积很小，所消耗的能量资源较少。REQ数据包是请求响应数据包，当邻居节点接收到来自传输请求节点发起的ADV数据包后，若其需要接收，则向请求发起节点发送REQ资料包。DATA数据包即为传感采集的数据内容。,1,5,4,3,2,0,DATA,ADV,ADV,ADV,ADV,0号节点向1号节点发送传感数据,当1号节点接收到数据后，向其周边邻居节点广播ADV数据包，通知邻居节点自己有传感数据需要转发,当1号节点的邻居节点接收到ADV数据包后，根据自己的情况，自主选择接受数据DATA与否，节点3与节点5选择接收数据DATA，因此其向1号节点发送REQ数据包,当1号节点接收到节点3和节点5发送的REQ，即立刻将DATA发送至这两个节点,REQ,REQ,DATA,DATA,SPIN路由协议转发过程,简单的无结构路由协议：定向扩散路由协议,定向扩散路由协议（Directed Diffusion）简称DD路由协议，是一种典型的以数据为中心，基于查询的路由机制。汇聚节点根据不同的应用需求定义不同的兴趣（Interest）请求消息，并通过洪泛的方式将兴趣请求消息数据包发送至全网或者局部网络的传感器节点。在进行兴趣消息洪泛发送过程的同时，每个节点根据缓存中的兴趣列表，沿着兴趣消息发送方向的反向建立数据传输梯度（Gradient），当兴趣消息到达源节点后，源节点则将数据沿着之前建立好的传输梯度进行正向传输，直到汇聚节点。 定向扩散路由协议为了能够适应网络拓扑的动态变化，采用周期性地对网络进行路由维护与更新，其主要分为3个阶段：兴趣消息扩散、数据传输梯度建立、路径加强。,兴趣消息扩散：,D,F,B,A,C,E,汇聚节点,节点B收到节点A发送过来的消息，判断是否与刚才转发给D的消息相同，如果是则丢弃该消息否则检查本地新区列表，如果没有相“兴趣”，则增加新表项并转发“兴趣”，否则判断表项中是否有邻居节点等于兴趣消息数据包中的发送节点，如果是则更新最新时间戳，否则添加新邻居节点，转发“兴趣”。,以A、B、D演示兴趣消息的扩散过程,汇聚节点向传感器网络内节点A、B广播兴趣消息,节点A、B接收到兴趣消息，然后，节点A向节点B、D广播接收到的消息，同时节点B向节点D广播接收到的消息。,简单的无结构路由协议：谣传路由协议,谣传路由协议（Rumor Routing Protocol）是在定向扩散路由协议的基础上建立起来的，是由Boulis等提出的适用于数据传输量较小的传感器网络，被认为是SPIN路由协议与定向扩散路由协议的折中，并且加入了Gossiping随机转发给其某一邻居节点的转发机制。由定向扩散路由协议可以看出，若汇聚节点对网络的数据查询只有一次，并且源节点只需向汇聚节点上报一次数据，使用定向扩散协议的开销就会比较大，谣传路由协议正是为了解决这一问题。该路由协议借鉴了欧式平面几何中的任意两条曲线相交的概率较大的思想，从源节点产生代理数据包（Agent）并发送，汇聚节点发送请求探测数据包，两者都随机进行下一跳节点的选择，直到两个数据包在某一节点上相交，则构成了一条可行路由。,汇聚节点,相交节点,传感器节点,传感器节点,检测区域,谣传路由协议示例,无线传感器网络路由,4,1,树类路由协议,无线传感器网络路由概述,路由协议设计的关键问题,2,3,5,简单的无结构路由协议,地理路由协议,无线传感器网络路由协议比较,6,高弹性多经路由协议,无线传感器网络由于其节点的能量有限，应用场景复杂多变，因此其网络的动态性较大，节点往往会由于某种原因而失效，人们将这种情况称为弹性。为了解决无线传感器网络中数据传输的可靠性问题，一种常见的策略是采取多条路径的路由策略。通过利用冗余路径，当一条路径失效时，可以选择其余路径进行数据分发。在多路径路由当中，通常多条路径中性能最优的路径作为主路径，性能最优可以根据需要定义不同的衡量标准，其余路径则作为备选路径。通常，多路径路由有两种：一种是分离多路径，另一种则是缠绕多路径。多路径的弹性和维护开销有着密切关系：弹性好，意味着协议能够快速检测到路径失效并切换到另外的路径上。,树类路由协议：SAR路由协议,SAR（Sequential Assignment Routing）有序分配路由协议是第一个在无线传感器网络中保证QoS的主动路由协议，也是一种基于多路径的路由协议。为了能够建立起从每个节点到达汇聚节点的多径路由，从汇聚节点每个邻居节点开始，以它们为树根，依次扩展建立树状结构。从汇聚节点开始，每一个树都会尽可能地向具有满足QoS或者剩余能量较多的邻居节点延伸和扩展。当构建树完成后，大多数节点都将成为所建树的一部分，并且由于汇聚节点周围的邻居节点都是这些树的树根节点，因此所形成的多条路径针对汇聚节点周围的邻居节点是不相交的，如图3-7所示，这样有效避免了汇聚节点周围节点能量消耗过快的问题。对于每条路径，都有两个参数与其相关联。,树类路由协议：LEACH,LEACH是一种低功耗自适应聚类路由协议，它打破了原有成簇算法中固定簇头的思想，采用本地簇头随机轮循机制将能量负载均匀分布到网络中的所有节点，提升了簇状无线传感器网络的性能。 LEACH也可以说是一种自适应分簇拓扑算法，其基本思想是将节点组织成簇结构形式，每个簇有一个簇头节点（Cluster Head Node），其他节点作为非簇头节点。所有的非簇头节点只与本簇的簇头节点通信，感知的数据由簇头节点传输到Sink节点，簇头节点除了传输非簇头节点的数据外，还要执行数据融合功能。因此，簇头节点要比非簇头节点消耗更多能量，为了避免节点长期担当簇头功能而过早耗尽能量，LEACH使用轮转的方式选举节点成为簇头节点，从而让所有的节点都有机会成为簇头节点而达到网络中节点能量消耗均匀的目的。,LEACH路由拓扑,按照规定选取合适的簇头,当网络中部分节点选择自己为簇头节点后,则发布消息通知网络中其它节点自己是簇头节点。,每个非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并通知该簇头，簇头收到消息后将该节点加入到簇成员表中。,非簇头节点在簇内指定的持续时间内发送一次数据，在没有数据发送时，将进入休眠状态以节省能量，而簇头节点保持工作状态以接收数据。,簇头收到所有的簇内数据之后，就执行数据融合功能，然后将处理后的数据传输到Sink节点。,Sink节点,树类路由协议：PEGASIS及Hierarchical-PEGASIS路由,PEGASIS（Power-Efficient Gathering in Sensor Information Systems），一种基于LEACH协议基础上建立起来的路由协议，主要解决LEACH协议中由于簇头频繁变更，导致通信开销较大的问题。与LEACH协议不同，PEGASIS协议并不采用全网多个簇头的方案，而是只采用一个簇头，其将全网看成是一个簇群，并将其称为链。簇头节点与汇聚节点能够通过一跳通信，其余传感器节点只能通过多跳的形式与簇头节点通信。 PEGASIS将全网看成是一个链，因此簇头节点将链分成两部分，则数据分别从两端传输至簇头节点，在传输的过程中，每个节点必须知道自己的所在地理位置，以便在转发时采用贪心策略，将数据转发给与其距离最近的节点，并在转发过程中应做相应的数据融合。当两端数据发送完毕后，进行下一轮簇头节点的选择。,树类路由协议：TEEN和APTEEN路由,TEEN能量有效的阈值敏感路由协议是一种具有实时性的路由协议，它采用多簇运行方式，但是它的网络结构具有多层次的分层结构，即一个簇内的普通节点可以被用作另一个簇的簇头节点。 TEEN协议引入了两个参数值：硬门限与软门限。在数据传输过程中，仍采用TDMA的机制，首先由汇聚节点向网络中传感器节点广播硬门限值，则传感器节点根据这个硬门限值，在第一次将监测到的数据上报给簇头节点时，仅仅上报其值大于硬门限的数据，并将当前的监测数据保存为监测值（Sensed Value，SV）。在这之后监测到的数据则根据硬门限与软门限两者共同决定是否需要上报给簇头节点，凡是数值大于硬门限值且与SV之差的绝对值不小于软门限时，节点才向簇头上报数据，并将当前观测到的数据作为最新的SV。,无线传感器网络路由,5,1,地理路由协议,无线传感器网络路由概述,路由协议设计的关键问题,2,3,4,简单的无结构路由协议,树类路由协议,无线传感器网络路由协议比较,6,基于局部地理拓扑的单播路由协议,基于局部地理拓扑的典型单播路由协议是指每个节点仅仅知道其邻居节点所在的地理位置，而不知道全网所有节点地理位置，利用局部地理信息位置，进行路由的选择。经典PALR路由协议中，要求每个传感器节点仅知道自己、目标节点与其邻居节点的地理位置信息。PALR是根据地理位置来优化网络的传输能量。,设网络中源节点为S，汇聚节点为BS，S的邻居节点为s1,s2, sn ，则S在选择路径时，将整个路径拆分为两个部分：一是从S到其邻居节点的单跳路径，二是从其某邻居节点到汇聚节点的单跳或多跳路径，实线表示源节点到邻居节点的路径，虚线表示从邻居节点到汇聚节点的路径。,对于任意一条从源节点S到汇聚节点BS的路径，其能量消耗可以等于两端路径消耗能量之和 表示，其中 表示第一段路径的能量消耗， 表示第二段路径的能量消耗，则寻找的路径应满足 ，即总能量消耗最小。对于 ，由于节点知道其邻居节点的地理坐标，因此能够较为容易且准确地计算出通信代价，但是 并不能准确计算出，因此需要估计出来，PALR采取的办法是利用最小理想能耗来计算。每个节点在选择下一跳时，都选出使得 最小的下一跳节点。,基于地理位置信息改善的多播路由协议,LBM则是在保证多播精确度的前提下，利用地理位置信息，进行有目的的广播数据包转发，从而降低整个网络的通信能耗。LBM利用多播目的节点的地理位置信息，定义了转发区域，只有在转发区域内的节点才会转发多播数据包。通常，转发域主要有以下3种类型:（1）静态转发域 静态转发域是通过将目标域与源节点限制在一定范围空间中，从而将节点的数据转发范围缩小，有效降低广播的通信量。（2）自适应转发域 自适应转发域是指转发域会随着数据包的不断转发进行相应的变化。通过自适应将转发区域根据当前数据发送节点进行调整，可以进一步提高网络数据通信效率，避免冗余数据通信，但是，由于节点每一次收到新数据时都需要计算自适应转发域的大小，增加了个别节点的计算复杂性程度。（3）基于前进距离的非显示转发域基于前进距离的非显示转发域不像前面两种转发域那样具有一种范围较为准确、形状相对规整的区域，而是一种根据每个节点自身计算值，决定是否将数据包向前转发，即这个转发区域是时刻在变的且没有固定形状。,栅格划分：边长的选择d是两节点之间的通信距离。任意两个相邻的栅格之间，若要使得在两栅格中任意地理位置的两簇头都能够正常通信，则边长r与通信半径d满足：,基于地理栅格的分层网络路由协议,1,2,3,4,0,0,1,2,3,整个网络划分成一个个正方形的小栅格，节点通过每个栅格内的簇头节点构成网络的骨干网络完成数据通信。每个栅格都有自己的编号，栅格内的所有节点都共享这个栅格编号，栅格内的簇头节点负责栅格中分组转发。,栅格簇头节点的选择原则是按照停留在栅格内时间最长的节点作为簇头节点，一旦某节点担当了簇头节点，只有其离开该栅格时才会进行新一轮的簇头选择。,GRID路由协议主要包括3个阶段：栅格划分路由建立路由维护,节点以自己和归属栅格中心点的距离设定定时器，定时器到时，选举自己成为簇头，并周期性地发送通告消息，其他节点接收到消息后，则加入该栅格。如果同时有多个节点竞争簇头，在收到其他簇头的通告消息后，距离栅格中心较远的簇头放弃簇头地位，保证栅格中的簇头个数不超过一个。,节点,无线传感器网络路由,6,1,无线传感器网络路由协议比较,无线传感器网络路由概述,路由协议设计的关键问题,2,3,4,简单的无结构路由协议,树类路由协议,地理路由协议,5,基于地理栅格的分层网络路由协议,第三章 路由、覆盖与拓扑技术,3.2,无线传感器网络路由,3.1,无线传感器网络拓扑控制技术,无线传感器网络覆盖技术,3.3,3.2 无线传感器网络拓扑控制技术,1,2,拓扑控制技术概述,拓扑控制意义,拓扑控制的设计目标,3,4,5,功率控制技术,典型的层次型拓扑控制方法,拓扑控制中的休眠调度技术,6,路由层,拓扑管理/控制,MAC层,拓扑控制技术是无线传感器网络中的基本问题。动态变化的拓扑结构是无线传感器网络最大特点之一，因此拓扑控制策略在无线传感器网络中有着重要的意义。目前，在网络协议分层中没有明确的层次对应拓扑控制机制，但大多数的拓扑算法是部署于介质访问控制层（MAC）和路由层（Routing）之间，它为路由层提供足够的路由更新信息i，反之，路由表的变化也反作用于拓扑控制机制，MAC层可以提供给拓扑控制算法邻居发现等消息。,拓扑控制技术概述,向上提供信息,向上提供信息,触发算法运行,触发算法运行,3.2 无线传感器网络拓扑控制技术,2,1,拓扑控制意义,拓扑控制技术概述,拓扑控制的设计目标,3,4,5,功率控制技术,典型的层次型拓扑控制方法,拓扑控制中的休眠调度技术,6,拓扑控制的意义,无线传感器网络节点一般采用电池供电,节能是网络设计主要考虑的问题之一.拓扑控制的一个重要目标就是在保证网络连通性和覆盖的情况下,尽量合理高效的使用网络能量,延长整个网络的生命存时间.,无线传感器网络中节点部署看可能在某范围内很密集，如果每个节点都以大功率进行通信，会加剧节点之间的干扰；若节点发射功率过小，又会导致网络的割裂，影响网络的连通性。,在无线传感器网络中，只有活动的节点才能够进行数据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系。,无线传感器网络中的数据融合指传感器节点将采集的数据发送给骨干节点，骨干节点进行数据融合，并把融合结果发送给数据收集节点。而骨干节点的选择是拓扑控制的一项重要内容。,传感器节点可能部署在恶劣的环境中，在军事应用中甚至部署在敌方区域中，所以很容易受到破坏而失效。这就要求网络拓扑结构具有鲁棒性以适应这种情况。,3.2 无线传感器网络拓扑控制技术,3,1,拓扑控制的设计目标,拓扑控制技术概述,拓扑控意义,2,4,5,功率控制技术,典型的层次型拓扑控制方法,拓扑控制中的休眠调度技术,6,为了实现传感器节点间的相互通信,生成的拓扑必须保证连通性,即从任何一个节点都可以发送消息到另外一个节点。连通性是任何无线传感器网络拓扑控制算法都必须保证的一个重要性质。,覆盖可以看成是对传感器网络服务质量的度量。在覆盖问题中，最重要的因素是网络对物理世界的感知能力。生成的拓扑必须保证足够大的覆盖度，即覆盖面积足够大的监视区域。根据文献，衡量全网覆盖情况有一个量化指标平均每个节点的覆盖率c（%）：,在无线传感器网络中，一般情况下是不设置认证中心的，传感器节点只能依据自身从网络中收集的信息做出决策。另外，任何一种涉及节点间同步的通信协议都有建立通信的开销。显然，若节点能够了解全局拓扑和传感器网络中所有节点的能量，就能做出最优的决策；若不计同步消息的开销，得到的就是最优的性能。但是，若所有节点都要了解全局信息，则同步消息产生的开销要多于数据消息，这将导致网络系统开销大大增加，从而使得网络的生存期减少。,当网络负载较高时，低发射功率会带来较小的端到端延迟；而在低负载情况下，低发射功率会带来较大的端到端延迟。,减少通信干扰、减少MAC层的竞争和延长网络的生命期基本上是一致的。功率控制可以调节发射范围，层簇式网络可以调节工作节点的数量。这些都能改变一跳邻居节点的个数，即与它竞争信道的节点数。,无线传感器网络拓扑结构的对称性是指若从节点m到n有一条边，那么一定存在从节点n到m的边。由于非对称链路在目前的MAC协议中没有得到很好的支持，而且非对称链路通信的开销很大，对于传感器网络能量小的特点而言是一个瓶颈，因此一般都要求生成的拓扑中链路是对称的。,如何合理利用传感器节点能量问题一直都是无线传感器网络研究热点之一，因此，能量优化也必然成为无线多跳网络拓扑控制研究的一个重要目标。Chandrakasan等指出，设计能量消耗最小化的网络协议是无线传感器网络成功应用的关键。,拓扑控制的设计目标,无线传感器网络是与应用密切相关的,不同的应用对应有不同的拓扑控制设计目标要求.,传感器节点一般采用干电池来储备能量，其能量很有限，节点易造成因能量耗尽而失效，无线通信链路易受环境影响而无法保证通信质量。另外，新节点的加入、部分传感器节点的可移动性等均会造成网络拓扑结构的变化。这就要求拓扑控制具有鲁棒性和可扩展性，以适应变化，从而保证网络的连通性和覆盖度。,3.2 无线传感器网络拓扑控制技术,4,1,功率控制技术,拓扑控制技术概述,拓扑控意义,2,3,5,拓扑控制的设计目标,典型的层次型拓扑控制方法,拓扑控制中的休眠调度技术,6,功率控制技术,在满足网络连通的前提下,通过节点功率控制或动态调整节点的发射功率,精简节点间的无线通信链路,保留生成一个高效的数据转发拓扑结构,在保证网络拓扑连通的基础上,使得网络中节点的能量消耗最小.,COMPOW（COMMONPOWER）协议是一种简单的将功率控制与路由协议相结合的解决方案，其基本思想是：所有的传感器节点A使用一致的发射功率，在保证网络连通的前提下将功率最小化。COMPOW建立各个功率级的路由表，在功率Pi级时，通过使用功率Pi交换HELLO消息建立路由表RTpi，所有可达节点都是路由表中的表项。COMPOW选择最小的发射功率Pcom，使得RTpcom与最大发射功率具有相同数量的表项，于是整个网络使用公共的发射功率Pcom。但该协议只适用于节点分布均匀的情况，缺陷较为明显。,LMN/LMA是基于节点度数的算法。一个节点的度数是指所有距离该节点一跳的邻居节点的数目。基于节点度的算法一般动态调节节点的发射功率，使得节点的度数处于一个合理的区间。局部平均算法LMN和本地邻居平均算法LMA是两种周期性动态调整节点发射功率的算法。 LMA算法的主要思想是：给定节点度的上下限，动态调整节点的发射功率，使得节点的度落在要求区间内。 LMN与LMA相似，区别在于LMN将所有邻居的邻居数求平均值作为自己的平均数。 LMN算法和LMA算法对节点的要求不高，不需要严格的时间同步，可以保证算法的收敛性和网络的连通性。但这两种算法都缺少严格的理论推导，还可以进一步研究合理的邻居节点判断条件。,RNG、DRNG和DLSS等基于邻近图的近似算法在基于邻近图的算法中，所有节点以最大功率发射时形成的拓扑图为图G，定义为G=(V，E)的形式，V代表图中顶点的集合，E代表图中边的集合，E中的元素可以表示为(u，v)，其中u，vV，按照一定的规则Q，求出该图的邻近图G，最后G中每个节点以自己所邻接的最远通信节点来确定发射功率。经典的邻近图模型有RNG（Relative Neighborhood Graph）、GG（Gabriel Graph）、YG（Yao Graph）以及MST（Minimum Spanning Tree）等。这是一种解决功率分配问题的近似解法。考虑到传感器网络中两个节点形成的边是有向的，为了避免形成单向边，一般在运用基于邻近图的算法形成网络拓扑之后，还要进行节点之间的增删，以使最后得到的网络拓扑是双向连通的。,3.2 无线传感器网络拓扑控制技术,5,1,典型的层次型拓扑控制方法,拓扑控制技术概述,拓扑控意义,2,3,4,拓扑控制的设计目标,功率控制技术,拓扑控制中的休眠调度技术,6,典型的层次型拓扑控制方法,LEACH是第一个被提出的聚类路由协议,也是一种自适应分簇拓扑算法,其基本思想是将节点组织成簇结构形式I,每个簇有一个簇头节点,其他节点作为非簇头节点.所有的非簇头节点只与本簇的簇头节点通信,感知的数据由簇头节点传输到Sink节点,簇头节点除了传输非簇头节点的数据外,还要执行数据融合功能.因此，簇头节点要比非簇头节点消耗更多的能量，LEACH使用轮转的方式选举节点成为簇头节点，从而让所有的节点都有机会成为簇头节点而达到网络中节点能量消耗均匀的目的。,HEED是一种混合式的分簇算法，通过定义簇内平均最小可达功率AMRP指标来衡量簇内节点通信成本。HEED算法首先根据节点的剩余能量来概率性地选择一些候选节点，以簇内通信代价的高低来竞争产生最终簇头，以簇内平均可达能量作为衡量簇内通信成本的标准。HEED算法将操作时间分为成簇持续时间TCP和网络操作时间TNO。在成簇持续时间内每个节点分布式的通过有限次的迭代选举出簇头节点，节点在网络操作时间内发送数据到本簇簇头节点，簇头节点可以选择一种路由协议将数据经过多条路径经由其他簇头节点传送到基站或者汇聚节点。在簇头选举阶段，每个节点以不同的初始概率发送竞争消息，每次迭代将概率加倍直至为1或有邻节点己经被选为簇头。簇头竞选成功后，其他节点在竞争阶段根据收到的簇头通告信息选择加入通信代价AMRP最低的簇头。,GAF算法将监测区域划分成虚拟单元格，将节点按照位置信息划入相应的单元格，相邻单元格的任意两个节点可直接通信。GAF节点有3种状态:工作状态,睡眠状态,发现状态.每个单元格只有一个定期选举产生的簇头节点处于工作状态,其他节点周期性地进入睡眠和发现状态.发现状态的节点可以竞争簇头.,TopDisc是基于走最小支配集问题的典型算法。在TopDisc算法中，由网络中的一个初始节点开始发送用于发现邻居节点的查询消息，该消息携带有发送节点的状态信息。随着查询消息在整个传感器网络中的扩散，算法依次为每个传感器节点标记上颜色即状态。根据算法中节点状态的个数，TopDisc包括两种具体的节点状态标记方法：三色算法和四色算法。 TopDisc算法在密集部署的无线传感器网络中执行速度快，但形成的网络拓扑灵活性不强，也没考虑节点能耗的均衡问题。,3.2 无线传感器网络拓扑控制技术,6,1,拓扑控制中的休眠调度技术,拓扑控制技术概述,拓扑控意义,2,3,4,拓扑控制的设计目标,功率控制技术,典型的层次型拓扑控制方法,5,拓扑控制中的休眠调度技术,拓扑控制中的休眠调度技术能够使节点在没有事情发生时设计通信模块为睡眠状态,而在有事情发生时自动醒来并唤醒邻居节点,形成数据转发的拓扑结构.这种机制的引入,使得无线通信模块大部分时间都处于关闭状态,只有传感器模块处于工作状态.此机制有效节省了能量开销.此机制重点在于解决节点在睡眠状态和活动状态之间的切换,拓扑控制中的休眠调度技术,STEM算法包含两种不同的机制：STEM-B 和STEM-T。STEM算法使节点在整个生命周期中的多数时间内处于睡眠状态，适用于类似环境监测或者突发事件检测等应用。,ASCENT算法是另一种节点唤醒机制，其重点在于均衡网络中骨干节点的数量，并保证数据通路的畅通。节点可以处于4种状态：1、休眠状态2、侦听状态3、测试状态4、活动状态,CCP有3个基本的状态：工作状态、侦听状态和睡眠状态。此外，为了避免由于每个节点根据局部信息独立进行调度而引起的冲突，CCP引入了加入和退出两个过渡状态。,SPAN算法的基本思想是在不破坏网络原有连通性的前提下，根据节点的剩余能量、邻居节点的个数、节点的效用等多种因素，自适应地决定是成为骨干节点还是进入睡眠状态。睡眠节点周期性地唤醒，以判断自己是否应该成为骨干节点，骨干节点周期性地判断自己是否应该退出。,第三章 路由、覆盖与拓扑技术,3.3,3.2,无线传感器网络覆盖技术,无线传感器网络拓扑控制技术,无线传感器网络路由,3.1,3.3无线传感器网络覆盖技术,1,2,无线传感器网络覆盖算法设计思路及性能评价标准,无线传感器网络覆盖感知模型,无线传感器网络覆盖算法分类,3,4,典型的无线传感器网络覆盖算法与协议,无线传感器网络覆盖算法设计思路及性能评价标准,无线传感器网络覆盖算法设计思路及性能评价标准,研究的目的:(1)使待检测区域中的每一点都至少在一个传 感器节点的覆盖范围内。(2)在保证覆盖要求的基础上，同时减少网络节点能量消耗、延长网络寿命。,无线传感器网络节点部署有两种,即确定性部署和随机部署,无线传感器网络往往节点硬件平台资源首限、网络节点数量巨大、实际应用的环境条件复杂且大多不允许对“失效”节点进行电池更换。,在设计覆盖算法需要考虑节点的传感和通信距离。,保证网络的可扩展性是无线传感器网络覆盖技术的另一项关键需求。,3.3无线传感器网络覆盖技术,1,无线传感器网络覆盖算法设计思路及性能评价标准,无线传感器网络覆盖算法分类,3,4,典型的无线传感器网络覆盖算法与协议,2,无线传感器网路覆盖感知模型,无线传感器网络覆盖感知模型,节点的感知范围是一个以节点为圆心，以感知距离为半径的圆形区域，只有落在该圆形区域内的点才能被该节点覆盖，数学表达式为：此模型简称为0-1模型，即当监控对象处在节点的感应区域时，它被节点监控到的概率恒为1，而当监控对象处在感应区域之外时，它被监控到的概率恒为0。,布尔感知模型,节点的圆形感知范围内，目标被感知到的概率并不是一个常量，而是由目标到节点间距离、节点物理特性等诸多因素决定的变量。、节点不存在邻居节点、节点存在邻居节点,概率感知模型,节点i对监测区域内目标j的感知概率有如下3种定义形式：,由于邻居节点的感应区域与节点自身的感应区域存在交叠，所以如果节点j落在交叠区域内，则节点j的感知概率会受到邻居节点的影响。假设节点i存在N个邻居节点n1，n2，nN，节点i及邻居节点的感知区域分别记为R(i)，R(n1)，R(n2)，R(nN)，则这些感知区域的重叠区域为：假设每个节点对目标的感知是独立的，根据概率计算公式，M中任一节点j的感知概率计算式：,3.3无线传感器网络覆盖技术,1,无线传感器网络覆盖算法设计思路及性能评价标准,无线传感器网络覆盖感知模型,2,4,典型的无线传感器网络覆盖算法与协议,3,无线传感器网络覆盖算法分类,无线传感器网络覆盖算法分类,面覆盖算法的目标是在大量冗余的节点中寻找能够覆盖同样区域大小并保证网络连通的节点集合。同时获取最长的网络生存周期及能量高效性也是面覆盖算法在设计时需要兼顾的目标。,点覆盖算法要覆盖的目标是一些离散的目标点.在点覆盖算法中,每一个目标点都要能够被至少一个传感器节点所覆盖.,栅栏覆盖考察了目标穿越网络时被检测或是没有被检测的情况,反映了给定的无线传感器网络所能提供的传感、监视能力。目标是找出连接出发位置和离开位置的一条或多条路径，使得这样的路径能够在不同模型定义下提供对目标的不同传感/监视质量。,随机覆盖考虑在网络中传感器节点随机分布且预先不知道节点位置的情况下,网络完成对检测区域的覆盖任务;动态网络覆盖则是考虑一些特殊环境中部分传感器节点具备一定运动能力的情况,该网络可以动态完成相关覆盖任务.,基于网格的目标覆盖是指当地理环境情况预先确定时，使用二维（也可以是三维）的网格进行网络的建模，并选择在合适的格点配置传感器节点来完成区域/目标的覆盖；确定性网络路径/目标覆盖同样也是考虑传感器节点位置已知情况，但这类问题特别考虑了如何对穿越网络的目标或其经过的路径上各点进行感应与追踪。,3.3无线传感器网络覆盖技术,1,无线传感器网络覆盖算法设计思路及性能评价标准,无线传感器网络覆盖感知模型,2,4,无线传感器网络覆盖算法分类,3,典型的无线传感器网络覆盖算法与协议,典型的无线传感器网络覆盖算法与协议,传感器节点及目标点都采用网格形式配置，传感器节点采用布尔覆盖模型，并使用能量矢量来表示格点的覆盖。单击如图所示，网络中的各格点都可至少被一个传感器节点所覆盖（即该点能量矢量中至少一位为1），此时区域达到了完全覆盖。例如，格点位置8的能量矢量为（0，0，1，1，0，0）。在网络资源受限而无法达到格点完全识别时，就需要考虑如何提高定位精度的问题。而错误距离是衡量位置精度的一个最直接的标准，错误距离越小，则覆盖识别结果越优化。,圆周覆盖归纳为决策问题：目标区域中配置一组传感器节点，看看该区域是否满足K覆盖，即目标区域中每个点都至少被K个节点覆盖。考虑每个传感节点覆盖区域的圆周重叠情况，进而根据邻居节点信息来确定是否一个给定传感器的圆周被完全覆盖。,当指令中心向网络发送一个监视区域查询消息时，连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖网络区域。连通传感器覆盖的分布式贪婪算法执行过程是：首先从M中最新加入的候选节点开始执行，在一定范围内广播候选路径查找消息（CPS）；收到CPS消息的节点判断自身是否为候选节点，如果是，则单播方式返回发起者一个候选路径响应消息（CPR）；发起者选择可以最大化增加覆盖区域的候选路径；更新各参数，算法继续执行，直到网络查询区域可完全被更新后的M所覆盖。,采用轮换“活跃”和“休眠”节点的Self-Scheduling覆盖协议可以有效延长网络生存时间，该协议同时属于确定性面/点覆盖和节能覆盖类型。协议采用节点轮换周期工作机制，每个周期由一个Self-Scheduling阶段和一个Working阶段组成。在Self-Scheduling阶段：各节点首先向传感半径内邻居节点广播通告消息，其中包括节点ID和位。节点检查自身传感任务是否可由邻居节点完成，可替代的节点返回一条状态通告消息，之后进入“休眠状态”，需要继续工作的节点执行传感任务。在判断节点是否可以休眠时，如果邻居节点同时检查到自身的传感任务可由对方完成并同时进入“休眠状态”，就会出现如图3-22所示的“盲点”。为了避免“盲点”的出现，每个节点在进入“休眠状态”之前还将等待Tw时间来监听邻居节点的状态更新。,最坏与最佳情况覆盖算法考虑如何对穿越网络的目标或其所在路径上各点进行感应与追踪，体现了一种网络的覆盖性质。 Meguerdichian等定义了“最大突破路径”（Maximal Breach Path）和“最大支撑路径”（Maximal Support Path），分别使得路径上的点到周围最近传感器的最小距离最大化及最大距离最小化。显然，这两种路径分别代表了无线传感器网络最坏（不被检测概率最小）和最佳（被发现的概率最大）的覆盖情况。,暴露穿越覆盖同时属于随机节点覆盖和栅栏覆盖的类型。如前所述，“目标暴露”（Target Exposure）覆盖模型同时考虑时间因素和节点对于目标的“感应强度”因素，更为符合实际环境中，运动目标由于穿越网络时间增加而“感应强度”累加值增大的情况。暴