拓扑结构控制

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