TopDisc算法.ppt

TopDisc算法 无线传感器网络 wirelesssensornetworks WSNs 是由众多具有通信和计算能力的传感器节点用无线通信方式连接而成 节点具有低成本 低功耗 协同合作等功能 因为采用的是能量有限的电池供电 所以设计良好的拓扑控制结构能够提高路由协议和MAC协议的效率 为数据融合 时间同步 目标定位等提供基础保证 有利于延长整个网络的生存时间 所以 拓扑控制是无线传感器网络中的一个基本问题 传感器网络拓扑控制的主要研究的问题是 在满足网络覆盖度和连通度的前提下 通过功率控制和骨干节点的选择 剔除节点之间不必要的通信链路 形成一个数据转发的优化网络结构 传感器网络中的拓扑控制按照研究方向可以分为两类 节点功率控制和层次型拓扑控制组织 目前 在节点功率控制方面主要的算法有 COMPOW算法 LMN LMA算法 RNG DRNG和DLSS算法 在层次拓扑控制方面主要的算法有 TopDisc算法 改进的GAF算法 以及LEACH和HEED算法 但是目前每种算法都有它们各自的优缺点 而且普遍存在着模型过于理想化 对网络的综合性能考虑较少 我们还需要探索更加实用的拓扑控制技术 在实际应用在也要对采用的算法加以改进 达到适合应用的目的 TopDisc算法的描述 TopDisc算法是早期成簇算法中的经典算法之一 TopDisc算法是由Deb等人提出的一种基于图论中最小支配集问题的经典算法 利用颜色来描述节点状态 解决骨干网拓扑结构的形成问题 它由网络中一个节点启动并发送查询消息 查询消息携带状态信息 随着消息的传播 TopDisc算法依次为每个节点标记颜色 最后按颜色区分出簇头节点黑色节点 并反向寻找查询消息 在簇头节点之间建立通信链路 簇头节点管理自己簇内的节点 TopDisc算法中提出两种节点标记方法 分别为三色算法和四色算法 这两种方法的区别在于 四色算法中 节点多了一种深灰色状态的节点 从而使得两种算法在形成簇后的结构有所不同 四色算法能形成比三色算法更少的簇 且簇与簇之间的交叠更少 但四色算法相对于三色算法可能会形成一些孤独的黑色节点 它不覆盖灰色节点 两种算法的核心思想都是利用颜色标记理论找到簇头节点 利用与传输距离成反比的延时 使得一个黑色节点 簇头节点 覆盖更大的范围 TopDisc算法继承了图论中的经典算法 是早期成簇算法中的典型代表 该算法可以在节点密集的传感器网络中快速地形成分簇结构 并在簇于簇之间建立树型关系 但是由于这种算法构建成的层次型网络的灵活性不强 重复执行算法的开销过大 且该算法没有考虑到节点的剩余能量问题 TopDisc算法改进TopDisc算法主要是靠时延机制来实现对整个无线传感网络的划分 时延主要是依据节点间距离作为依据 因为节点之间距离直接决定的通讯能量消耗的水平 但是在实际中 网络生命周期还要考虑各自节点剩余能量 为防止个别节点 早死 剩余能量达不到标准不能作为簇首节点 另外节能也是能量均衡的前提 所以我们在延时机制中加入节点的剩余能量作为分簇权值的一部分 综合距离和节点本身的剩余能量 改进TopDisc算法分簇的权值 在原始的TopDisc算法中 网络拓扑结构一旦确定 直到网络瘫痪 同一节点自始至终一直扮演普通节点或簇首节点中的一个角色 簇首节点由于既要发送数据 又要转发数据 所以比普通节点耗电量大 尤其是越靠近汇聚点的簇首节点转发的数据越多 电量耗费也越快 网络的使用寿命也就越低 而在改进的TopDisc算法中 由于簇首节点的即时更换和网络拓扑结构切换 使得电能在网络中的节点间均衡消耗 从而减少了死亡节点数量 并且使网络的平均吞吐率增加 THANKS 三色算法三色算法是分簇算法的具体实现 节点可以处于三种状态 分别用白 黑和灰三种颜色表示 白色表示未被发现的节点 黑色节点代表簇头节点 灰色节点表示三色算法所确定的普通节点 即簇成员节点 在骨干网络形成之前 所有节点都被标记为白色 由一个初始节点发起三色算法 由初始节点启动发送用于发现邻居节点的查询消息 查询消息携带发送节点的状态信息 随着查询消息在网络中传播 三色算法依次为每个节点标记颜色 最后 按照节点颜色区分簇头和成员节点 簇头负责管辖自己簇内的节点 算法执行完毕后所有节点都将被标记为黑色或者灰色 三色算法的具体过程如下 1 初始节点将自己标记为黑色 并广播查询消息 2 白色节点收到黑色节点的查询消息时变为灰色 灰色节点等待一段时间再广播查询消息 等待时间的长度与黑色节点之间的距离成反比 3 当白色节点收到一个灰色节点的查询消息时 先等待一段时间 等待时间的长度与白色节点到该灰色节点的距离成反比 如果在等待时间内 收到来自黑色节点的查询消息 节点立即变成灰色节点 否则节点变为黑色节点 4 当节点变为黑色或者灰色后 它将忽略其他节点的查询消息 5 通过反向查找查询消息的传播路径形成骨干网 黑色节点成为簇头 灰色节点为簇内节点 注 三色算法需要知道发送节点和接收节点之间的距离信息 在无线传感器网络中 节点的具体位置信息很难获得 可以利用接收信号强度值RSSI ReceivedSignalStrengthIndicator 来映射节点之间的距离 1 三色算法由节点a发起 它将自己标记为黑色 并发送查询消息 2 节点b c收到节点a发送的查询消息 将自己标记为灰色 并等待一定时间再次广播这个查询消息 3 节点e d收到来自灰色节点b的查询消息后 等待一段时间 由于节点d比节点e距离节点b更远 所以节点d先超时 并将自己标记为黑色 继续向前发送查询消息 4 这时节点e收到了来自节点d的消息 所以停止等待 变为灰色 5 算法如此进行下去 算法运行到网络边缘后 将按照查询消息发送的路径进行回溯 构建网络的转发链路 四色算法四色算法和三色算法有两个相同的特点 利用颜色标记理论找到簇首节点 利用与传输距离成反比的延时 确定簇首节点 四色算法主要在三色算法的基础上加以改进 避免形成的簇重叠 所以根据具体网络的不同 最终的拓扑结构有不同程度的差异 四色算法主要增加了一个颜色 深灰色 深灰色节点表示该节点至少某一黑色节点的距离为两级跳 它可能成为黑色节点 但要满足在等待时间里没有收到黑色节点的查询消息 既此节点离最近的簇首的距离都较远 可以成为簇首 四色算法的构建过程如下 1 初始节点将自己标记为黑色 并广播查询消息 2 白色节点收到黑色节点的查询消息时变成灰色 灰色节点等待一段时间再广播查询消息 等待时间的长度与它到黑色节点的距离成反比 3 当白色节点收集到来自灰色节点的查询消息时变为深灰色 然后继续广播这个消息 同时等待一段时间 等待时间的长度与它到灰色节点的距离成反比 深灰色节点在这段时间内没有收到黑色节点的查询消息 它自己成为黑色节点 否则它将成为灰色节点 4 当白色节点收到来自深灰色节点的查询消息时 等待一段时间 等待时间的长度与它到发送此查询消息的深灰色节点的距离成反比 如果在这段时间内又收到来自黑色节点的查询消息 节点变成灰色节点 否则节点变成黑色节点 该节点变色后将立即广播查询消息 5 变为黑色或者灰色的节点不再响应其他节点的查询消息 6 通过反向查找查询消息的传播路径形成骨干网 黑色节点成为簇首 灰色节点成为簇内节点 但是由于这种算法建成的网络灵活性不强 一旦某些节点出现失效 网络必须重新拓扑 尤其特别是无线传感网络固有的能量有限性决定仅仅从距离的角度不能很好选择出当前的节点做簇头是最合适的 另外执行算法时 要求各个节点发出信息 并接受其他节点的信息 而且计算两节点间