第三章-路由、覆盖与拓扑控制技术

无线传感器网络技术及其应用第三章路由、覆盖与拓扑技术3.13.2无线传感器网络路由无线传感器网络拓扑控制技术无线传感器网络覆盖技术3.33.1无线传感器网络路由12无线传感器网络路由概述路由协议设计的关键问题简单的无结构路由协议345树类路由协议地理路由协议无线传感器网络路由协议比较61无线传感器网络路由概述11无线传感器网络路由概述2无线传感器网络路由21路由协议设计的关键问题无线传感器网络路由概述简单的无结构路由协议345树类路由协议地理路由协议无线传感器网络路由协议比较62路由协议设计的关键问题1无线传感器网络路由31简单的无结构路由协议无线传感器网络路由概述路由协议设计的关键问题245树类路由协议地理路由协议无线传感器网络路由协议比较6简单的无结构路由协议：Flooding和Gossiping路由协议Flooding路由协议ABCDEFGHPPPPPPP以此类推，直到p到大汇聚节点D或到达TTL源节点A需要将数据包p发送至汇聚节点D节点A首先将p的副本广播，则其邻居节点B接收到p副本节点B直接将p副本通过广播的形式转发给E、F、CFlooding路由协议优缺点Gossiping路由协议Ds初始设置每个数据包TTL=6此时TTL=0，资料包在此处丢失，不再往下传至D简单的无结构路由协议：SPIN路由协议154320DATAADVADVADVADV0号节点向1号节点发送传感数据当1号节点接收到数据后，向其周边邻居节点广播ADV数据包，通知邻居节点自己有传感数据需要转发当1号节点的邻居节点接收到ADV数据包后，根据自己的情况，自主选择接受数据DATA与否，节点3与节点5选择接收数据DATA，因此其向1号节点发送REQ数据包当1号节点接收到节点3和节点5发送的REQ，即立刻将DATA发送至这两个节点REQREQDATADATASPIN路由协议转发过程简单的无结构路由协议：定向扩散路由协议兴趣消息扩散：DFBACE汇聚节点节点B收到节点A发送过来的消息，判断是否与刚才转发给D的消息相同，如果是则丢弃该消息否则检查本地新区列表，如果没有相“兴趣”，则增加新表项并转发“兴趣”，否则判断表项中是否有邻居节点等于兴趣消息数据包中的发送节点，如果是则更新最新时间戳，否则添加新邻居节点，转发“兴趣”。以A、B、D演示兴趣消息的扩散过程汇聚节点向传感器网络内节点A、B广播兴趣消息节点A、B接收到兴趣消息，然后，节点A向节点B、D广播接收到的消息，同时节点B向节点D广播接收到的消息。简单的无结构路由协议：谣传路由协议汇聚节点相交节点传感器节点传感器节点检测区域谣传路由协议示例无线传感器网络路由41树类路由协议无线传感器网络路由概述路由协议设计的关键问题235简单的无结构路由协议地理路由协议无线传感器网络路由协议比较6高弹性多经路由协议树类路由协议：SAR路由协议树类路由协议：LEACHLEACH路由拓扑按照规定选取合适的簇头当网络中部分节点选择自己为簇头节点后,则发布消息通知网络中其它节点自己是簇头节点。每个非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并通知该簇头，簇头收到消息后将该节点加入到簇成员表中。非簇头节点在簇内指定的持续时间内发送一次数据，在没有数据发送时，将进入休眠状态以节省能量，而簇头节点保持工作状态以接收数据。簇头收到所有的簇内数据之后，就执行数据融合功能，然后将处理后的数据传输到Sink节点。Sink节点树类路由协议：PEGASIS及Hierarchical-PEGASIS路由树类路由协议：TEEN和APTEEN路由无线传感器网络路由51地理路由协议无线传感器网络路由概述路由协议设计的关键问题234简单的无结构路由协议树类路由协议无线传感器网络路由协议比较6基于局部地理拓扑的单播路由协议基于局部地理拓扑的典型单播路由协议是指每个节点仅仅知道其邻居节点所在的地理位置，而不知道全网所有节点地理位置，利用局部地理信息位置，进行路由的选择。经典PALR路由协议中，要求每个传感器节点仅知道自己、目标节点与其邻居节点的地理位置信息。PALR是根据地理位置来优化网络的传输能量。设网络中源节点为S，汇聚节点为BS，S的邻居节点为{s1,s2,‥‥sn}，则S在选择路径时，将整个路径拆分为两个部分：一是从S到其邻居节点的单跳路径，二是从其某邻居节点到汇聚节点的单跳或多跳路径，实线表示源节点到邻居节点的路径，虚线表示从邻居节点到汇聚节点的路径。对于任意一条从源节点S到汇聚节点BS的路径，其能量消耗可以等于两端路径消耗能量之和表示，其中表示第一段路径的能量消耗，表示第二段路径的能量消耗，则寻找的路径应满足，即总能量消耗最小。对于，由于节点知道其邻居节点的地理坐标，因此能够较为容易且准确地计算出通信代价，但是并不能准确计算出，因此需要估计出来，PALR采取的办法是利用最小理想能耗来计算。每个节点在选择下一跳时，都选出使得最小的下一跳节点。基于地理位置信息改善的多播路由协议LBM则是在保证多播精确度的前提下，利用地理位置信息，进行有目的的广播数据包转发，从而降低整个网络的通信能耗。LBM利用多播目的节点的地理位置信息，定义了转发区域，只有在转发区域内的节点才会转发多播数据包。通常，转发域主要有以下3种类型:（1）静态转发域静态转发域是通过将目标域与源节点限制在一定范围空间中，从而将节点的数据转发范围缩小，有效降低广播的通信量。（2）自适应转发域自适应转发域是指转发域会随着数据包的不断转发进行相应的变化。通过自适应将转发区域根据当前数据发送节点进行调整，可以进一步提高网络数据通信效率，避免冗余数据通信，但是，由于节点每一次收到新数据时都需要计算自适应转发域的大小，增加了个别节点的计算复杂性程度。（3）基于前进距离的非显示转发域基于前进距离的非显示转发域不像前面两种转发域那样具有一种范围较为准确、形状相对规整的区域，而是一种根据每个节点自身计算值，决定是否将数据包向前转发，即这个转发区域是时刻在变的且没有固定形状。栅格划分：边长的选择d是两节点之间的通信距离。任意两个相邻的栅格之间，若要使得在两栅格中任意地理位置的两簇头都能够正常通信，则边长r与通信半径d满足：基于地理栅格的分层网络路由协议1234001235dr2222rrd整个网络划分成一个个正方形的小栅格，节点通过每个栅格内的簇头节点构成网络的骨干网络完成数据通信。每个栅格都有自己的编号，栅格内的所有节点都共享这个栅格编号，栅格内的簇头节点负责栅格中分组转发。栅格簇头节点的选择原则是按照停留在栅格内时间最长的节点作为簇头节点，一旦某节点担当了簇头节点，只有其离开该栅格时才会进行新一轮的簇头选择。GRID路由协议主要包括3个阶段：栅格划分路由建立路由维护节点以自己和归属栅格中心点的距离设定定时器，定时器到时，选举自己成为簇头，并周期性地发送通告消息，其他节点接收到消息后，则加入该栅格。如果同时有多个节点竞争簇头，在收到其他簇头的通告消息后，距离栅格中心较远的簇头放弃簇头地位，保证栅格中的簇头个数不超过一个。节点无线传感器网络路由61无线传感器网络路由协议比较无线传感器网络路由概述路由协议设计的关键问题234简单的无结构路由协议树类路由协议地理路由协议5路由协议单路径多路径平面结构树状结构混合路由基于地理位置基于数据融合Flooding√√可选Gossiping√√可能SPIN可能可能√√DD√√√Rumor√√√√高弹性多路径√√可能可能SAR√√LEACH√√可能√PEGASIS√√√H-PEGASIS√√√TEEN√√√APTEEN√√√PALR√√√LBM√√√√GRID√√√√√基于地理栅格的分层网络路由协议第三章路由、覆盖与拓扑技术3.2无线传感器网络路由3.1无线传感器网络拓扑控制技术无线传感器网络覆盖技术3.33.2无线传感器网络拓扑控制技术12拓扑控制技术概述拓扑控制意义拓扑控制的设计目标345功率控制技术典型的层次型拓扑控制方法拓扑控制中的休眠调度技术6路由层拓扑管理/控制MAC层拓扑控制技术是无线传感器网络中的基本问题。动态变化的拓扑结构是无线传感器网络最大特点之一，因此拓扑控制策略在无线传感器网络中有着重要的意义。目前，在网络协议分层中没有明确的层次对应拓扑控制机制，但大多数的拓扑算法是部署于介质访问控制层（MAC）和路由层（Routing）之间，它为路由层提供足够的路由更新信息i，反之，路由表的变化也反作用于拓扑控制机制，MAC层可以提供给拓扑控制算法邻居发现等消息。拓扑控制技术概述向上提供信息向上提供信息触发算法运行触发算法运行3.2无线传感器网络拓扑控制技术21拓扑控制意义拓扑控制技术概述拓扑控制的设计目标345功率控制技术典型的层次型拓扑控制方法拓扑控制中的休眠调度技术6拓扑控制的意义①影响整个网络的生存时间②减小节点间通信干扰，提高网络通信效率③为路由协议、时间同步提供基础④影响数据融合⑤弥补节点失效的影响3.2无线传感器网络拓扑控制技术31拓扑控制的设计目标拓扑控制技术概述拓扑控意义245功率控制技术典型的层次型拓扑控制方法拓扑控制中的休眠调度技术6为了实现传感器节点间的相互通信,生成的拓扑必须保证连通性,即从任何一个节点都可以发送消息到另外一个节点。连通性是任何无线传感器网络拓扑控制算法都必须保证的一个重要性质。覆盖可以看成是对传感器网络服务质量的度量。在覆盖问题中，最重要的因素是网络对物理世界的感知能力。生成的拓扑必须保证足够大的覆盖度，即覆盖面积足够大的监视区域。根据文献，衡量全网覆盖情况有一个量化指标——平均每个节点的覆盖率c（%）：在无线传感器网络中，一般情况下是不设置认证中心的，传感器节点只能依据自身从网络中收集的信息做出决策。另外，任何一种涉及节点间同步的通信协议都有建立通信的开销。显然，若节点能够了解全局拓扑和传感器网络中所有节点的能量，就能做出最优的决策；若不计同步消息的开销，得到的就是最优的性能。但是，若所有节点都要了解全局信息，则同步消息产生的开销要多于数据消息，这将导致网络系统开销大大增加，从而使得网络的生存期减少。当网络负载较高时，低发射功率会带来较小的端到端延迟；而在低负载情况下，低发射功率会带来较大的端到端延迟。减少通信干扰、减少MAC层的竞争和延长网络的生命期基本上是一致的。功率控制可以调节发射范围，层簇式网络可以调节工作节点的数量。这些都能改变一跳邻居节点的个数，即与它竞争信道的节点数。无线传感器网络拓扑结构的对称性是指若从节点m到n有一条边，那么一定存在从节点n到m的边。由于非对称链路在目前的MAC协议中没有得到很好的支持，而且非对称链路通信的开销很大，对于传感器网络能量小的特点而言是一个瓶颈，因此一般都要求生成的拓扑中链路是对称的。如何合理利用传感器节点能量问题一直都是无线传感器网络研究热点之一，因此，能量优化也必然成为无线多跳网络拓扑控制研究的一个重要目标。Chandrakasan等指出，设计能量消耗最小化的网络协议是无线传感器网络成功应用的关键。拓扑控制的设计目标•能量消耗1•覆盖度2•连通性3•算法的分布式程度4•对称性7•鲁棒性和可扩展性8•网络延迟5•干扰和竞争62N**RC所有节点覆盖区域面积传感器节点一般采用干电池来储备能量，其能量很有限，节点易造成因能量耗尽而失效，无线通信链路易受环境影响而无法保证通信质量。另外，新节点的加入、部分传感器节点的可移动性等均会造成网络拓扑结构的变化。这就要求拓扑控制具有鲁棒性和可扩展性，以适应变化，从而保证网络的连通性和覆盖度。3.2无线传感器网络拓扑控制技术41功率控制技术拓扑控制技术概述拓扑控意义235拓扑控制的设计目标典型的层次型拓扑控制方法拓扑控制中的休眠调度技术61•统一功率分配算法COMPOW2•基于节点度的功率控制LMN/LMA3•基于邻近图的功率控制1•统一功率分配算法COMPOW2•基于节点度的功率控制LMN/LMA3•基于邻近图的功率控制1•统一功率分配算法COMPOW2•基于节点度的功率控制LMN/LMA3•基于邻近图的功