无线传感器网络拓扑控制研究

无线传感器网络拓扑控制研究

无线传感器网络（无线传感器网络）是由具有随机分布功能的传感器节点组成的网络，这些节点通过无线通信形成多个自组织网络。WSNs集数据采集、数据处理和数据通信三大功能于一体,是21世纪最重要的技术之一,其巨大的应用价值和发展前景引起了军事界、工业界和学术界的广泛关注。WSNs的重要特征是资源受限,因此如何高效地利用网络的有限资源来延长网络寿命就成为研究WSNs的主要目标。拓扑控制作为WSNs重要的支撑技术,主要作用是在介质访问控制层(MAC)和路由层之间,为减少通信干扰提高MAC协议效率提供基础,为路由层提供足够的路由更新信息;而路由表的变化反作用于拓扑控制机制,MAC层也可以为拓扑控制算法提供邻居发现等消息。拓扑控制同时为网络时间同步、数据融合及目标定位等关键技术提供支撑,因此良好的拓扑结构在WSNs中至关重要,成为实现有限资源利用最大化的必要条件。目前,WSNs拓扑控制逐渐成为研究的热点,但目前看来,对拓扑控制全方位的分析和评述还很少,尤其是对拓扑控制与连通、调度之间关系的研究大多局限在单方面或仅泛泛而谈,没有深层次挖掘三者间“点、线、面”的关系。本文的研究无疑为推动拓扑控制的进一步发展奠定了一定的基础。1系统拓扑结构整体来说,WSNs拓扑控制的目标就是通过调整节点的发射功率、节点间的层次关系或工作状态等技术来满足网络结构的需要或特定应用场景的要求。在保证一定的连通度和覆盖的前提下,拓扑控制以提高能量使用效率、延长网络生存时间为核心目标,同时兼顾降低网络干扰、避免隐藏终端或暴露终端、提高网络吞吐量等因素。WSNs是与应用高度相关的,不同的应用系统对拓扑结构的要求不尽相同。从简化路由、提高MAC协议效率来讲,生成的拓扑应具备稀疏性和对称性;从消息转发的可达性和可扩展性的角度来讲,拓扑应具备平面性和局部性;从实现节点间互相通信和健壮性的要求考虑,拓扑结构必须具备连通性和容错性。另外,拓扑控制算法在执行报文交互时必然会消耗节点能量,而节点本身的计算能力、存储能力和通信能力有限,算法复杂必然会带来实现上的困难和物理成本的增加,所以在设计拓扑时要结合场景的实际需要,生成的拓扑应在稀疏性、对称性、连通性等这些错综复杂的关系中折中,并结合算法本身的实现代价综合考虑。2基于随机图理论的拓扑模型和控制算法2.1随机图理论拓扑模型随机图理论在信息科学中被广泛地应用,UDG、RNG和MST等都是基于随机图理论的经典拓扑模型,很多的拓扑结构都是在它们的基础上演变而来的。从连通和抗干扰的角度对拓扑模型进行分类,如图1所示。1udg的生成假定网络中N个节点构成了二维平面中的节点集V,所有节点都以最大功率工作时所生成的拓扑称为UDG(unitdiskgraph)。若所有节点最大的传输范围为1,无线节点在平面中就构成了一个UDG,当且仅当图中每对节点间的欧氏距离dis(u,v)≤1时,两个节点之间才有链路相连。UDG的连通性是网络能够提供的最大连通性,因此,任何拓扑控制算法生成的拓扑都是UDG的子图。2qudg的近似子图算法假设V、R是两个空间平面的节点集,且V⊂R,设参数d∈,则对称的欧氏图(V,E)被称为以d为参数的准规则单位圆图(QUDG)。图中对任意α,β∈V,若|αβ|≤d,则(α,β)∈E;若|αβ|>1,则(α,β)∉E。在实际应用中,节点的发射功率会因为硬件或环境等各种原因而变化,所以QUDG是比UDG更接近实际的拓扑模型。未经拓扑控制算法处理的UDG是非平坦的,非平坦图边的非顶点交叉现象将给信道带来干扰。为了对其作平面化处理,简化拓扑结构,许多UDG的近似子图算法被提了出来。其中最具代表性的有Gabriel图(GG)、相关邻近图(RNG)和最小生成树(MST)。3在有节点节点上设du,v为参数设置在二维欧氏空间中,V为节点集,w,u,v∈V,w≠u≠v。连接GG中任意两个节点u和v,则以边d(u,v)为直径、通过节点u和v的圆内不包含其他任何节点。如果(dis(u,v))2≤min((dis(w,u))2+(dis(w,v))2),w≠u≠v,则说明d(u,v)为GG的一条边。在传输功率正比传输距离的平方时,GG是最节能的拓扑模型。4以点为中心的分区在二维欧氏空间中,V为节点集,任意两个节点间的边长小于或等于u、v分别与其他任意一节点的距离的最大值,即欧氏距离dis(u,v)≤max(dis(w,u),dis(w,v)),w,u,v∈V,w≠u≠v。若d(u,v)为RNG的一条边,则在分别以点u或v为圆心,以dis(u,v)为半径的两个圆R1和R2的交集I内不能有其他节点,如图2所示。RNG是由GG产生的,RNG稀疏程度和连通性均介于MST与GG之间,优于MST,且冲突干扰优于GG,易于用分布式算法构造。5消除网络生成树MST是保持图连接所需的满足最小权值的链路子集。MST是RNG的子图,其特征是连通但不形成回路,任意两个节点均可以相互通信。每个节点出现在树上,链路总长度最小。构造MST有两种主要算法,即Kruskal和Prim算法。Kruskal算法总是选择剩余权值最小的边加入最小生成树;Prim算法则通过任意将节点加入最小生成树,同时仅将权值更小的边加入。6ytrengulation模型除了上面讨论过的几种模型外,Yao图(YG)、Voronoitessellation(VT)和Delaunaytriangulation(DT)也是常用的模型。YG分很多扇区,节点在扇区内选择最近的邻居进行通信,具有简单的分布式结构,节点的度较高;VT首先识别网络冗余节点,然后计算出可被关闭的冗余节点,最后由工作节点构建覆盖集;DT中点集V的一个三角剖分T只包含Delaunay边,具有最大化最小角、惟一性(任意四点不能共圆)等特性。2.2邻近图和直接本地最小生成树基于邻近图的功率控制算法是拓扑算法中非常重要的一类,其基本思想是假设传感器节点以最大的发射功率发射时形成的拓扑结构G,按照一定的邻居判断条件得出G的邻近图G′,每个节点又以与相距自己最远的邻居节点之间的距离来确定其发射功率,从而在建立起一个连通网络的同时使能量消耗最低。关于WSNs的基于邻近图的拓扑控制算法已有一些代表性的研究,较为典型的算法有直接相关邻近图(DRNG)和直接本地最小生成树(DLMST),两者分别是以RNG和MST为理论基础的拓扑算法。DRNG是一种基于方位信息的RNG分布式算法。DRNG算法思想是若节点u和v的距离dis(u,v)小于节点u的发射半径Ru,而且不存在节点i同时满足w(u,i)<w(u,v),w(i,v)<w(u,v)和dis(i,v)≤Ri时,则认为v是u的邻居节点。其中w表示权重,如图3所示。DLMST算法实质上等价于求解可达邻居子图的最小生成树。首先节点u确定自己可达邻居子图G,然后将u与所有可达邻居的边所对应的权重函数w(u,v)排序,从小到大依次取出w(u,v)对应的边,直到u与G中每个节点均可以直接或间接连通,而与u直接连通的邻居节点构成u的邻居节点集。为了实现拓扑控制,在DRNG和DLMST算法中节点需要获取有关邻居节点的一些信息,因此在算法初期有邻居节点信息收集阶段,每个节点以自己最大的发射功率广播包含ID和位置信息的Hello消息,每个节点根据接收到的Hello消息来确定自己的可达邻居集合N。DRNG和DLMST充分考虑到了网络的连通性,并对节点间的边进行必要的增删操作使优化后的拓扑保持双向连通。另外,在平均功率和节点度等方面两者也具有较好的性能。3网络拓扑信息马量大,导致路由计算复杂,增加计算资源WSNs拓扑结构具有稠密部署的特点,在拓扑控制之前,所有节点以最大发送功率工作。这样,一方面会造成网络中每个节点的无线信号覆盖的节点数目过多,使无线信号冲突频繁,直接影响到传感器节点的无线通信质量,降低整个网络的吞吐率;另一方面,节点有限的能量将被无线通信模块快速消耗,降低了网络的寿命;同时,在生成的网络拓扑中将存在大量的边,从而导致网络拓扑信息量过大,路由计算复杂,浪费宝贵的计算资源。因此,在保证网络强连通和覆盖的前提下通过一定的拓扑控制降低节点的发送功率,避免节点之间无线信道的频繁冲突,减少网络拓扑信息,从而降低节点能耗、提高网络吞吐量,有效地延长了网络寿命。目前,围绕拓扑机制进行的相关研究大致分为两类:a)通过控制节点睡眠或活动状态来控制活动节点数量;b)通过控制某些链路的使用状态来减少通信链路的数量。从路由的方面考虑,网络拓扑应保持全局连通,使任意两个传感器节点间存在可通信链路。为了实现数据转发过程中节点或区域的能量平衡,网络中能量相对充足的节点间的链路在路由时被优先选择。从MAC协议效率角度来看,网络拓扑的连通冗余度过高,节点的信号覆盖范围可能过大,会造成隐藏或暴露终端问题,从而引发数据通信碰撞,继而导致数据重传或串扰及其带来的不必要的能耗。具体来说,拓扑控制机制可以从平面网络、支配集和分簇的网络结构三方面分别讨论,如图4所示。3.1网内节点协同启发机制平面网络结构是WSNs中最简单的一类拓扑结构,其所有节点的地位相同、功能对等,每个节点均包含相同的MAC、路由、管理等协议。平面网络拓扑结构较为简单、易维护,具有较好的健壮性。平面网络没有中心管理节点,所以节点都能够与sink通信,数据包通过一跳或多跳转发至sink,通常其拓扑是通过功率控制或网内节点协同启发机制来产生。功率控制机制的思想是调整网络中传感器节点的发射功率,在保证网络连通和均衡节点的单跳可达邻居数目的同时,降低节点间的无线通信干扰。网内节点协同启发机制的思想是节点根据自身周边环境的变化进行自主控制以及与邻居节点进行交互的机制,当有通信要求时能够及时自动醒来并唤醒邻居节点,形成数据转发的拓扑结构。下面介绍平面网络拓扑控制的典型算法。1统一传输功率COMPOW算法是一种典型功率控制算法。该算法中节点采用同构方式,所有节点具有统一的传输功率,并且该功率是能确保整体网络连通的最小功率。虽然最小传输功率在降低能耗的同时提升了网络容量、减少了通信干扰,但也约束了COMPOW的适用范围,尤其当网内节点分布不均匀时节点被迫使用较大功率,这也是该算法的致命弱点。2嵌入/接收点偏入K-Negih算法是一种典型的基于邻居集合和距离估测技术的分布式算法。K-Negih算法思想是节点首先以最大功率广播ID,并根据接收到的广播报文运用距离估测技术进行由近至远的排序,因而确定K个最近节点置入邻居集,最后交互邻居集合,对单向链接实施删除或增加以满足链接的双向对称性。K-Negih算法具有连通性、节点度受限、算法执行简单等良好特性。3算法思想下的转发Rodoplu等人提出了一种基于闭包图的功率分配算法R&M,它是一种基于节点地理位置信息的拓扑算法。算法思想是在每个节点周围确定一个称做enclosure的区域,在enclosure区域中的节点称为该节点的真正邻居。通过计算转发区域和衡量转发代价,以低能耗实现网络连通。R&M算法是一种强连通、稀疏性、低能耗的高效拓扑算法,但是算法本身的计算复杂度较高,给网络带来较大的开销。4删除冗余链路LILi等人提出了基于方向的拓扑控制算法CBTC。该算法的思想是节点首先发送Hello消息,并收集其他节点的回复信息;然后节点独立调节发射功率,以保证在每α角度内至少有一个邻居节点;最后删除冗余链路以维持拓扑的对称性。该算法能达到全局连通、对称性、节点度受限等特点的拓扑,但CBTC未能对低能耗节点采取保护措施,忽略了节点在路由中的能耗不平衡问题。5监听阶段:主动节点+监听STEM算法是一种典型的启发式拓扑控制方法,采用低占空比的节点唤醒机制,并使用监听和数据通信双信道。算法思想是节点周期性地进入监听阶段,探测是否有邻居节点要发送数据,当其想与其他节点通信时,就作为主动节点先向目标节点发送唤醒包,然后再进行通信。STEM算法节点的唤醒速度能满足应用的需要,可以适用于类似环境监测等应用,但该算法在实际应用中需在节点的睡眠周期、部署密度以及通信延迟等之间进行权衡。6网络连通性覆盖控制网络连通性覆盖问题常常是与网络拓扑相互联系的,其所解决的是如何保证监测区域内所有节点形成的监测范围可以满足应用要求,同时节点都可以向sink转发数据,而不会产生网络分割。WSNs许多的重要的技术如拓扑控制、目标定位目标跟踪等都是依赖于网络有效的连通性覆盖范围。网络连通性覆盖控制的主要思想是利用节点的冗余性,通过节点状态转换、密度控制等机制,在不影响网络连通和覆盖的条件下让一部分节点处于活动状态,承担数据采集转发等任务,使另一部分节点处于睡眠状态,以减少网络能量开销。ZhangHong-hai等人提出当节点密度有限时,节点通信半径r需不小于节点感应距离d的两倍,即r≥2d是连通性覆盖的充分必要条件。XueFeng等人证明了在k-覆盖和k-连通情况下,且r≥2d时,一个凸区域的k阶覆盖必然包含k-连通。GaoYong等人证明了如果要覆盖某个节点的整个监测区域,该节点需要3～5个一跳的邻居节点。3.2基于聚类管理的网络拓扑在WSNs中,为了节约无线通信模块的能耗,可以将网络拓扑划分为相连的簇区域,并依据一定的机制选择部分节点作为骨干节点。骨干节点的通信模块处于工作状态,并由其构建连通网络来处理和传输数据,让非骨干节点处于睡眠状态并属于骨干节点管理,从而大幅度降低空闲状态时侦听对节点能量的消耗,进而延长网络寿命。分簇算法融合了聚类管理的理念,弥补了空闲状态节点无谓能耗过高的缺陷。分簇的网络拓扑有利于分布式算法的应用,适合大规模部署的网络。LEACH、HEED等都是很具代表性的分簇拓扑算法。1letch算法LEACH是一种很重要的分簇算法,许多拓扑控制的分簇算法都是在LEACH的基础上改进的。算法先选簇头后划分区域,节点周期性地轮换充当簇头来实现网络的负载均衡。LEACH算法中,节点产生的随机数,若随机数小于阈值T,则宣布自己成为簇头,普通节点选择离其最近的簇头并加入该簇头管辖的区域。未被选为簇头的节点随着时间的推移,能量比簇头愈显充足,成为簇头的可能性就越大。LEACH轮换选举簇头,易保证网络获取统一的能量分布,且集中、周期地采集数据,因此其非常适合要求连续监控的应用系统。但簇头的选择没有考虑节点的地理位置信息,且需要较为严格的时间同步,更致命的是LEACH不能保证簇头均匀分布,这可能直接会影响骨干网的形成。2heed分簇实现基于LEACH的缺陷,LEACH的改进算法HEED应运而生。HEED算法思想是综合考虑剩余能量和簇内通信代价两级因素周期性地通过迭代的方法实现分簇。HEED用最小平均可达功率(AMRP)作为某个节点被选为簇头时的簇内通信代价的度量。HEED不依赖于网络的规模,有效地改善了LEACH簇头可能分布不均的缺陷。HEED通过O(1)次迭代实现分簇,迭代每一步的时间要足够长,使得节点能够收到来自邻居节点的消息。每个节点要确定在一簇范围内的邻居节点的集合,计算并广播AMRP,计算自己成为临时簇头的初始概率。虽然,HEED考虑了负载均衡和扩展性,但其执行不依赖时间同步可能会严重影响分簇的质量。3节点基于gaf的混合式GAF是一种基于地理位置的分簇算法,该算法思想是首先将事件区域划分为若干虚拟网格,节点依据自身所处的位置加入相应的格内,然后定期在格内选取簇头。簇头节点始终保持清醒状态,非簇头节点进入睡眠状态。节点在休眠状态过后会再次与本格内其他节点交换信息来重选簇头,簇头通常由节点产生的定时随机值决定。由于簇头的选取具有一定的随机性,方格边长的选取必须能使相邻两格内任意节点可直接通信。GAF显著降低了节点侦听能耗,但仅适用于网络数据流量较小的场景。另外,GAF对GPS的依赖也会使节点部署受到限制。3.3减少冗余广播节点的无线通信模块的能耗占节点总能耗的绝大部分,基于此,尽可能地减少冗余广播是降低节点能耗的重要方法。如何在广播信息能够覆盖网内所有节点的前提下使参与广播的节点的数目最少,于是就引出了WSNs中另外一类拓扑问题——构造最小连通支配集(MCDS)。3.3.1节点连通支配集法drn构造MCDS一般有两种方法:a)基于删除冗余节点法(DRN)。首先生成最大连通的子集,然后逐一地删除节点,直到再删除节点就不能满足网络连通性为止。b)基于最大独立集法。先产生规模为mis(G)的最大独立集(MIS),然后添加节点,直到实现连通,从而形成规模为cds(G)的连通支配集(CDS)。基于DRN的算法复杂度相对较低,但构造的CDS没有明确上界;基于MIS的算法复杂度较高,但能获得明确上界的CDS。3.3.2骨干网络拓扑算法WuJie算法的基本思想是首先生成一个较大的CDS,然后采用修剪去除冗余节点。节点发送信令学习网络中的两跳拓扑结构信息,生成存在冗余的CDS,然后根据一定的规则去除CDS的冗余节点。该算法只利用了局部信息,具有较好的扩展性。ZKY算法也是一种典型的CDS的构造算法。算法思想是采用节点编号的组合作为节点的权值,其目的是减小CDS的规模,删除具有较小度的节点而保留较大度的节点。考虑到无线网络的特点,每个节点侦听到的通信信道状态是不同的。距离上邻近的链路如果同时传输数据,可能会造成干扰导致信号碰撞。在WSNs中,设计一个高效的拓扑控制算法应考虑到干扰对拓扑造成的影响,并将干扰降低到最小程度。Jain等人分析了干扰对无线多跳网络性能的影响,将网络中的干扰进行建模,得出了计算网络最优吞吐量的上下限方法。HeYan-xiang等人提出了减少干扰的次优最小连通支配集的骨干网络拓扑算法(I-CDS),算法构建了一个连通支配集,而且该连通支配集有效地减少了网络干扰,并讨论了干扰对网络拓扑造成的影响。若区域内有n个节点m条链路,则I-CDS算法具有O(n)的消息复杂度和O(m+n)的时间复杂度。3.4底层网络拓扑控制标准不统一由于WSNs网络依赖于应用,节点的硬件结构呈现多样性特征,许多的协议和标准也不统一,不同的应用对底层网络的拓扑控制的要求也不尽相同,很难直接评判拓扑算法的优劣,只能根据实际应用的需要权衡选择。基于以上对各种拓扑算法的讨论和分析,从节点密度、复杂度等指标上进行比较,结果如表1所示。4节点高效行为的影响在WSNs中,拓扑控制与调度、连通三者是相互紧密联系的,并通过不同的方式共同完成WSNs的既定功能。如何利用有限的能量最大化网络寿命是WSNs的核心问题。为达到这个目标,就需要综合考虑能量有效和负载均衡,合理化网络能量分配,而拓扑控制、调度和连通三者共同作用是能够实现这一目标的重要途径。节点调度是WSNs拓扑控制重要的研究方向,是在一定的时间阶段和空间范围内只使一部分节点保持工作状态,而使另一部分节点进入睡眠状态,其根本目的是节省空闲侦听时的能耗。非层次调度中每个节点均不属于某个簇,节点根据自己所能获得的信息,独立地控制自己在工作状态与睡眠状态之间的转换;层次型网络节点调度是由簇头节点组成骨干网络,让其他节点进入睡眠状态。通常情况下,节点在没有获悉兴趣数据和承担数据转发任务时并不关闭通信模块,而节点的通信模块在空闲状态仍然会侦听无线信道的占用情况和探测兴趣数据的传递需求,空闲状态的能耗与节点在收发状态时相当,覆盖冗余也造成了很大的能量浪费,所以,只有使节点进入睡眠状态才能大幅度地降低网络的能量消耗。相对整体网络而言,节点调度只能从微观层面上进行控制,哪些区域需要较多的工作节点采集、处理信息,哪些区域保持较少的工作节点就能完成任务,只使用节点调度显然是不能够很好地解决问题。如此势必会造成资源不足或资源严重浪费的不平衡现象,这时就需要采用拓扑控制策略从全局方面控制某些区域链路的使用状态,从而形成一个良好的网络拓扑结构。为了有效地实现节点间的相互通信,要求网络生成的拓扑本身必须保证连通性。非层次型网络节点需要获知邻居节点是否处于活动状态或当节点发生丢包现象时需要向邻居节点发送求救信息,所以要求拓扑具有连通性;层次型网络节点需要节点轮流工作,必然存在转发节点睡眠,继而要重新建立路由,所以拓扑的连通性也是实现这一过程的必要条件。传感器节点的邻居节点太少,会造成消息可达率过