无线传感器网络拓扑控制答案ppt课件.ppt
无线传感器网络拓扑控制,拓扑控制技术概述,什么是拓扑,拓扑学(topology)是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的学科。它只考虑物体间的位置关系而不考虑它们的形状和大小。,WSN的拓扑控制,WSN中的拓扑不仅考虑节点的位置，还包括了节点的状态以及节点间的链路WSN拓扑控制(Topology Control) ：节点活动状态的管理和调度；节点发射功率和调度计划的控制；节点通信覆盖范围和节点连通性的控制WSN拓扑控制的研究方向：功率控制；节点活动状态调度,拓扑控制技术概述,通信半径,感知半径,节点密度,覆盖范围,连通度,发射功率,拓扑控制技术概述,路由层,拓扑管理/控制,MAC层,向上提供信息,向上提供信息,触发算法运行,触发算法运行,拓扑控制技术概述,拓扑控制的最终目的高效利用网络能量，减少节点间干扰，延长网络寿命,网络部署,减少能量消耗,优化网络部署,目标,功率控制,活动调度,节点活动管理,聚簇管理,辅助路由协议,目标,目标,目标,网络部署,网络部署使每个节点充分发挥作用，保证数据准确获取和收集决定网络的覆盖范围和连通性,节点可靠性模型,主要思想：节点的可靠性是节点在网络中处于活动状态的概率；对于给定的能耗预算，可以估计满足系统可靠性的最小节点可靠性。连通性与覆盖范围无直接关系,节点数量：节点增多，维持连通性和覆盖范围所花费的总能耗下降节点忙闲比和冗余度对部署也有影响：密度上升，忙闲比可下调。超过某一阈值后，增加节点冗余度对于降低忙闲比无效果,功率控制,功率控制对节点发射功率进行静态设置或动态调整在保证网络连通性基础上，调整邻居节点数，降低节点能耗，延长网络寿命,维持必要的连通性在此前提下降低节点传输功率,目标,尽可能短的路径网络中平均一跳的实际传输距离缩短,目标,支持分布式操作有好的扩展性以便支持大规模网络,目标,基于节点度的方法,功率控制,什么是节点度,节点度是指距离节点一跳范围内的邻居节点数目。基于节点度的功率控制方法旨在通过寻找节点的最佳发射功率，在不影响网络连通性的前提下，减少能量消耗，延长网络寿命。,基于节点度的方法,功率控制,本地平均算法(LMA)初始状态下，各节点发射功率相同，定期广播自己的生命周期消息(LifeMsg)节点收到其他节点的LifeMsg后，发送确认消息LifeAckMsg进行应答；发送节点可以根据收到的LifeAckMsg数量判断自己的邻居节点数量nr 节点根据自己的邻居节点数量判断是否需要改变发射功率：若邻居节点数 nr 大于最大值nmax ，则降低发射功率；若邻居节点数 nr 小于最小值nmin ，则提高发射功率；若nr 介于nmin 和nmax 之间，则不调整发射功率,基于节点度的方法,功率控制,本地邻居平均算法(LMN)初始状态下，各节点发射功率相同，定期广播自己的生命周期消息(LifeMsg)节点将自己的实际邻居数放在LifeAckMsg中发送出去，发送LifeMsg消息的节点收到所有邻居的LifeAckMsg回复，计算出邻居节点的平均值作为自己的平均邻居节点数节点根据自己的邻居节点数量判断是否需要改变发射功率,基于邻近图的方法,功率控制,邻近图方法思想基本思想：设所有节点都使用最大发射功率发射时形成的拓扑图G(即UDG)，按照一定的邻居判别条件q求出该图的邻近图(即特殊生成子图)G，最后G中的每个节点以自己所邻近的最远通信节点来确定发射功率。 主要算法包括RNG、MST、LMST等LMST算法：每个节点构建各自的局部最小生成树，将这些局部最小生成树合并为一张新图。LMST优势：与UDG相比降低了能耗，包含的链路更少，降低了网络中的干扰，提升了效能。,基于邻近图的方法,功率控制,其他方法,功率控制,CONREAP方法思想基本思想：采用了基于机会的方法并考虑了无线通信范围内的“过渡区域”；处于过渡区域的节点既不是完全连通的也不是完全断开的，这些节点可能成功接收一部分数据 ，下次发送的数据可能无法正确接收。算法引入网络的可达性参数，当参数高于某一阈值时，网络的能耗最小。过渡区域：某些区域内的节点虽在圆心节点的通信半径内，但由于信号衰减等原因，造成通信质量不佳，此区域及过渡区域。目的：减少重复路由造成的节点能量快速衰减。,活动调度,活动调度通过控制节点活动和睡眠状态的切换来满足节能等需求“状态切换”指在维持连通度前提下，关闭冗余节点，留下部分可以满足网络需求的节点工作,节点的关闭或休眠只针对节点的无线收发模块，节点处于这两种状态时，其传感器等其他部件还可以工作,所处位置一般位于MAC层和网络层之间，与路由协议关系密切,地理自适应保真算法(GAF) 依据节点地理位置信息选择骨干节点，节点必须知道自己的地理位置。GAF算法在每个网格内维持一个骨干节点，保证网络连通性，让其他节点进入睡眠状态减少能耗发现状态：节点与邻居交换“邻居发现消息”，包括节点ID、网格ID、预估节点活动时间和节点状态活动状态：节点参与路由活动，处理网格内通信活动，每一网格内只有一个节点处于活动状态睡眠状态：除活动节点外，其他节点均关闭无线传输模块状态切换：若收到更高级别“邻居发现消息(预估活动时间)”，则节点进入睡眠状态，工作任务转移，,活动调度,基于连通度的方法,活动调度,基于连通度的方法,GAF算法实际是一种基于地理位置信息的分簇算法，每个网格内的节点自动成簇，活动节点即为簇头,优势根据单元格的大小，可以最大限度使大部分节点睡眠，节省能耗,劣势成簇条件苛刻载荷分配不均衡，汇聚节点附近的单元格能耗消耗大,自适应自配置传感器网络拓扑(ASCENT) 通过节点的本地“测量”来进行活动调度，保障网络连通性。ASCENT算法使用分布式调度机制，保留骨干节点，其余节点睡眠探测状态(Test)：节点与邻居交换“控制信息”，计算周围主动活动邻居数主动活动状态：可收发、路由数据被动活动状态：不关闭无线通信，不参与通信，侦听当前流量，搜集网络状态和邻居数据丢失率睡眠切换：除活动节点外，其他节点均关闭无线传输模块,活动调度,基于连通度的方法,活动调度,基于连通度的方法,ASCENT节点状态转换方式：节点发现丢包严重，即向源节点方向发送求助消息节点探测到邻居丢包严重或收到求助消息时，则进入主动活动状态，参与网络通信,活动调度,基于连通度的方法,ASCENT算法基本思想是节点自适应决定自己的状态，对节点的计算要求相对较高,优势节点可以自适应地根据本地状态改变自身状态，从而动态改变网络拓扑形态,劣势节点在自适应状态转换过程中计算、能耗开销均高于GAF算法；节点侦测也有通信开销,活动调度,基于网络容量的方法,SPAN算法 也采用了分布式骨干节点选举机制SPAN算法中节点与邻居定期交换控制信息(即HELLO消息)HELLO消息内容：节点状态(是否为骨干节点)、连接到的骨干节点列表、节点的邻居每个节点通过HELLO消息都知道自己周围的骨干节点，能在需要时决定自己是否成为骨干节点；消息内容也供路由协议使用，以便在骨干节点中选择中继节点,活动调度,基于网络容量的方法,SPAN算法中普通节点可以转换为骨干节点，骨干节点也可以转换为普通节点。成为骨干节点：如果节点发现有超过两个邻居节点不能通信，则有资格成为骨干节点；为防止过多节点成为骨干节点，SPAN算法有退避机制，由节点效用和剩余能量决定骨干节点停职：骨干节点检查邻居节点状态，如每个邻居都可通过其他的骨干节点进行通信，则该骨干节点停止当前职责，成为普通节点,活动调度,SPAN算法在保证了网络连通性的同时也保证了一定的网络容量,优势延长了网络寿命提高了网络的健壮度，如链路故障，有其他链路替代,劣势增加了消息传输的跳数和时延增加了控制消息的交换以及通信开销,基于网络容量的方法,活动调度,STEM协议,稀疏拓扑与能量管理(STEM)协议 属于非层次型的节点唤醒调度算法。STEM协议中网络无需始终维持连通性，通常情况下节点处于监视状态，在事件发生后，网络产生突发流量，快速唤醒整个网络，恢复连通性，传输数据。STEM协议采用双无线收发机模式：一个收发机用于调度和信道侦听；另一个用于实际数据通信。两个收发机采用不同信道，彼此互不干扰,活动调度,STEM协议,WSN网络,无实际数据通信节点关闭第二无线收发机以节省能量定期打开第一收发机侦听,网络发生触发事件节点第一收发机侦听到网络传输信号唤醒第二收发机，传输数据,活动调度,STEM协议,STEM协议可以与GAF等算法相结合，利用各自优势，进一步调整网络能量消耗,优势节省能量，延长了网络寿命适用于低速、基于事件的网络应用场景,劣势节点花费大量时间进行侦听不适用于监控型网络，节能效果不明显,聚簇管理,使用分簇形式的优势,扩展性好限制了一般节点到汇聚节点的传输跳数，支持大规模网络,高效能簇头保持活动状态，其他节点可睡眠；簇头可动态选举均衡能耗,减少碰撞几率节点簇内管理，数据簇内传输,获取更多局部信息通过和簇头节点交换信息,混合能效分布式(HEED)分簇算法在分簇时考虑了节点剩余能量与簇内通信成本，将节点划分为多个一跳的簇。HEED产生背景：HEED是在LEACH算法簇头分布不均匀这一问题基础上而作出对LEACH协议分簇算法的改进，它以簇内平均可达能量(AMRP)作为衡量簇内通信成本的标准。HEED 算法的实质：在LEACH算法基础上，重点修改了选举簇头的算法。在全网时间同步的基础上, 将节点根据当前剩余能量占初始能量的比例p 划分为若干“等级”，等级较高的节点率先公布自己为簇头，而等级较低的节点在收到簇头广播后加入这个簇。如果节点的剩余能量降为初始能量的1%就被除去竞选簇头的资格。,聚簇管理,HEED算法,聚簇管理,HEED算法,主要改进在簇头选择中考虑了节点的剩余能量, 并以主从关系引入多个约束条件。实结果表明, HEED分簇速度更快, 能产生更加分布均匀的簇头、更合理的络拓扑。,LEACH簇头分布,HEED簇头分布,聚簇管理,HEED算法,HEED算法混合式的分簇算法，并非所有节点都成簇，有些节点可以单独成簇,优势分簇时综合考虑生存时间、可扩展性和负载均衡等因素簇头节点分布均匀,劣势汇聚节点附近节点能耗过快能耗监测和交换能耗信息开销较大,拓扑控制技术,WSN中不同拓扑形态下的数据传输,拓扑控制技术,WSN中不同拓扑形态下的数据传输,
