拓扑结构控制课件.ppt

拓扑结构控制概述n 在传感器网络中,传感器节 点 是体 积微 小的 嵌入 式 设备,采 用能量有限的电池供电,它的计算 能力 和通 信能 力十分有限,所 以除了要设计能量高效的 MAC 协 议、l路由协议以及应用层协议之外,还 要设计优化的网络拓扑控制机制。对于自组织的无线传感器网络而言,网络拓扑控制对网络性能影响很大。良好的拓扑结构能够提高路由协议和 MAC 协议的效率,为数 据融 合、时间同 步 和目 标 定位 等 很多方面提供基础,有利于延长 整个 网络 的生 存 时间。所 以,拓 扑控 制是传感器网络中的一个基本问题。网络的拓扑结构控制与优化意义n(1)影响整个网 络的 生存 时间n(2)减小节点间通信干扰,提高网络通信效率。n(3)为路由协议提供基础。n(4)影响数据融合。n(5)弥补节点失效的影响。拓扑控制主要研 究的问 题n在 满足网 络覆 盖度和 连通 度的 前 提下,通过功率控制和骨干网节点选择,剔除节点之间不必要的通信链路,形成一个数据转发的优化网络结构。具体地讲,传感器网络 中的 拓扑控 制按 照研 究方向 可以 分为两 类:节点功率控制和层次型拓扑结构组织。功率控制机制调节网络中每个节点的发射功 率,在满足网络连通度的前提下,均衡节点的单跳可达邻居数目。层次型拓扑控制利用分簇机制,让一些节点作为簇头节点,由簇头节点形成一个处理并转发数据的骨干网,其他非骨干网节点可以暂时关闭通信模块,进入休眠状态以节省能量。功率控制n 传感器网络中节点发射功率的控制也称功率分配问题。节点通过设置或动态调整节点的发射功率,在保证网络拓扑结构连通、双向连通 或者多连通 的基 础上,使得 网络 中节点的能量消耗最小,延长整个网络的生存时间。当 传感 器节 点部署 在二 维或三 维空 间中时,传感器网络的功率控制是一个 NP 难 的问题 。因 此,一般的 解决 方案都 是寻 找近似解法。NP难问题基于节点度的算法n 一个节点的度数是指所有距离该节点一跳的邻居节点的数目。n基于节点度算法的核心思想是给定节点度的上限和下限需求,动态调整节点的发射功率,使得节点的度数落在上限和下限之间。基于节点度的算法利用局部 信息 来调 整相邻 节点 间的连 通性,从 而保证整个网络的连通性,同时保证节点间的链路 具有一 定的 冗余 性和可 扩展 性。n本地平均算法 LM A(local mean algorit hm)和 本 地邻 居 平均 算 法 L MN(local mean of neighbors algorithm)是两种周期性动态调整节 点发 射功 率的算 法。它们 之 的区别在于计算节点度的策略不同本地平均算法（1）n(1)开始时所有节点都有相同的发射功率 TransPowe r,每个 节点定期 广播一 个包含己 ID 的 Life Msg 消息。n(2)如果节点接收 到 LifeMs g 消 息,发送 一个 LifeAckMsg 应 答消 息。该 消 息中 包含所应答的 LifeMsg 消息中的节点 ID。n(3)每个节点在下一次发送 LifeMsg 时,首先检查 已经收到 的 LifeAckM sg 消息,利用这些消息统计出自己的邻居数 NodeResp。本地平均算法（2）n(4)如果 NodeResp 小于邻居数下限NodeMinThresh,那么节点在这轮发送中将增大发射功率,但发射功率不能超过初始发射功率的 Bmax 倍,如式(4-1)所示;同理,如果 NodeResp大于邻居节 点 数 上 限 NodeMaxThresh,那 么 节点 将 减 小 发 射功 率,用 式(4-2)表 示,其 中Bm ax,Bmin,Ainc 和 Ade c 是四个可调参数,它们会影响功率调节的精度和范围。本 地邻 居 平均 算 法 LMNn本地邻居 平 均 算 法 L MN 与 本 地 平 均 算 法 L MA 类 似,惟 一 的 区 别 是 在 邻 居 数NodeResp 的计算方法上。在 L MN 算法 中,每 个节 点 发送 LifeAckMsg 消 息时,将自己的邻居数放入消息中,发送 LifeMsg 消息的节点在收集完所有 LifeAckMs g 消息后,将所有邻居的邻居数求平均值并作为自己的邻居数。基于节点度的算法的优缺点n这两种算法都缺少严格的理论推导。通过计算机仿真结果确定:这两 种算法 的收敛性和网络的连通性是可以保证的,它们通过少量的局部信息达到了一定程度的优化效果。n这两种算法对无线传感器节点的要求不高,不 需要严 格的 时钟 同步。但 是算法 还存 在一些明显不完善的地方,例如,需要进一步研究 合理的 邻居 节点判 断条 件,对从邻 居节 点得到的信息是否根据信号的强弱给予不同的权重等。其它功率控制算法n基于邻近图的算法基于邻近图的算法n 1.邻近图 n 基于邻近图的功率控制算法是指:所有节点都使用最大功率发射时形成的拓扑图为图 G,按照一定的规则 q 求出该图的邻近 图 G 最 后 G 中每 个节点 以自 己所邻 接的 最远通信节点来确定发射功率。这是一种解决功率分配问题的近似解法 。考虑到传感器网络中两个节点形成的边是有向的,为了避免形成单向边,一般在运用基于邻近图的算法形成网络拓扑之 后,还 需 要 进 行 节 点 之 间 边 的 增 删,以 使 最 后 得 到 的 网 络 拓 扑 是 双 向 连通的。nDRNG 算法和 DLSS 算法层次型拓扑结构控制n 在传感器网络中,传感器节点的无线通信模块 在空 闲状 态时的 能量 消耗与 在收 发状态时相当,所以只有关闭节点的通信模块,才 能大幅 度地 降低无 线通 信模 块的能 量开 销。n考虑依据一定机制选择某些节点作为骨干网节点,打开其通信模块,并关闭非骨干节点的通信模块,由骨干节点构建一个连通网络来负 责数据 的路 由转 发。这样 既保证 了原 有覆盖范围内的数据通信,也在很大程度上节省了节点能量。在这种拓扑管理机制下,网络中的节点可以划分为骨 干网 节点 和普 通节 点 两类。骨 干 网节 点对 周围 的普 通 节点 进行 管辖。这类算法将整个网络划分为相连的区 域,一般又 称为 分簇 算法。骨 干网节 点是 簇头节点,普通节点是簇内节点。由于簇头节点需要协调簇内节点的工作,负责数据的融合和转发,能量消耗相对较大,所以分簇算法通常采用周期性地选择簇头节点的做法以均衡网络中的节点能量消耗。优点n层 次型的 拓扑 结构具 有很 多优 点,例 如,由 簇 头 节 点 担负 数 据 融 合 的任 务,减 少 了数 据通信 量;分 簇式的 拓 扑 结 构 有 利 于 分 布 式 算 法 的 应 用,适 合 大 规 模 部 署 的 网 络;由 于大部 分节 点在相 当长 的时 间内关 闭通 信模 块,所 以 显 著地 延 长 整 个 网络 的 生 存 时间 等。层次型拓扑结构控制nLEACH 算法nGAF 算法nGAF 改进算法nTopDisc 算法(三色算法，四色算法）启发机制n 传感器网络通常是面向应用的事件驱动的 网络,骨 干网 节点在 没有 检测到 事件 时不必一直保持在活动状态。在传感器网络的拓扑 控制 算法 中,除了传 统的 功率控 制和 层次型拓扑控制两个方面之外,也提出了启发式的 节点唤 醒和 休眠 机制。该 机制能 够使 节点在没有事件发生时设置通信模块为睡眠状态,而在 有事 件发 生时及 时自 动醒来 并唤 醒邻居节点,形成数据转发的拓扑结构。这种机制的引入,使得无线通信模块大部分时间都处于关闭状态,只有传感器模块处于工作状态。由于 无线 通信 模块消 耗的 能量远 大于 传感器模块,所以这进一步节省了能量开销。这种机制 重点 在于 解决节 点在 睡眠状 态和 活动状态之间的转换问题,不能够独立作为一种拓扑结构控制机制,需要与其他拓扑控制算法结合使用。启发机制nSTEM 算法:（S T E M-B 和 ST E M-T算法）n2.STEM-T(STEM-TONE)算法ASCENT 算法n在功率控制方面提出了以邻居节点度为参考依据算法，以及利用邻近图思想生成拓扑结构的算法；n在层次型拓扑控制方面提出了很多分簇算法。n但是其中大多数算法停留在理沦研究阶段或者只做过少量节点的模拟，没有充分考虑实际应用的诸多困难，例如，节点大规模撤布时，如何保证算法的收敛速度，如何减小外界因素对通信的干扰，以及节点失效后如何追加等。n逐渐引入了启发式的节点唤醒和休眠机制，在数据消息中捎带拓扑控制信息的机制等。n现在的拓扑控制研究的发展趋势是以实际应用为背景，多种机制结合使用，强调网络拓扑控制的自适应性和鲁棒性，在保证网络连通性和覆盖度的前提下，提高网络通信效率，最大限度地节省能量来延长整个网络的生存时间。