无线传感器网络分簇路由协议研究

无线传感器网络分簇路由协议研究

无线传感器网络（wsd）是一个由大量电子传感器以自组织和跳转方式构建的网络。其特点是检测范围广、持续时间长、感知能力强、信息传递及时等,目的是协作地感知、采集、处理和传输感知对象的监测信息,并报告给所需用户,起到物理世界和电子世界便捷沟通的桥梁。在工农业控制、城市污染监测、军事领域、电子感知医疗、抢险救灾、智能交通等领域具有广阔的应用前景,是当前国际科技竞争的焦点和制高点,已经成为国内外研究的热点。1基于分簇网络的路由协议路由协议在WSN体系结构中,具有非常重要的地位,路由协议的好坏直接影响WSN的性能,要实现网络快速及动态构建,行之有效的方法是采用分簇机制。在分簇网络中,所有节点根据簇首(clusterhead)选举办法,形成一个基于分簇的自组织网络。该网络不受网络规模限制,路由开销较小,抗毁性强,容易实现移动管理和网络的局部同步。基于分簇路由的网络中,由一个簇首节点(sink)和多个簇成员节点(clustermember)构成,形成一个树状结构,自下而上的传递信息,最终由簇首节点与基站BS(basestation)进行信息通信,其拓扑结构如图1所示。与传统的无线传感器网络路由协议相比,分簇路由协议具有拓扑结构便于管理,无需维护复杂的路由表,较高的网络能量利用率,较好的可扩展性以及适合大规模网络等特点,因此以分簇为基础的路由协议在无线传感器网络中已得到了广泛的应用,是目前路由协议研究的热点,其优点是具有自适应性、节能性、消除健壮性和扩展性等。本文对当前的分簇路由协议进行分类、分析,剖析典型分簇路由协议的设计思想、优点及缺点,并从多个性能参数进行比较和总结,目的是为进一步研究作指引和参考。2分簇路由协议的核心问题是什么?WSN分簇协议较传统的无线路由协议更为复杂,好的分类方法和比较分析有利于研究人员对分簇路由协议进行研究和改进。分簇路由协议中簇的结构、大小、数量以及节点的能耗和网络生命周期,决定因素是簇头的产生方法、数量及位置。分簇路由协议工作过程中最关键的核心问题是如何合理选举簇首节点、如何快速有效地构建分簇结构、如何节约能量和延长网络生命周期。目前研究者已经做了大量的工作[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22],按照簇首节点的选举依据与实现机制,分簇路由协议划分为3种类型,分别为基于随机选举、基于地理位置和基于剩余能量。2.1随机选举后的集群协议该协议是最简单的一种选举簇首方法,网络随机地按照一定概率选举簇首,形成簇结构。典型协议如下。2.1.1打造网络实名协议,控制网络结构LEACH(low-energyadaptiveclusteringhierarchy)是一个典型自适应分簇协议,是最早的基于层次结构的路由协议,其后的大部分协议是在它的基础上进行改进及发展的。该协议采用分布式算法,使各节点的任务均等、消耗的能量均衡,很好地减轻了节点的负载,达到了延长整个网络运行时间的目的。运行机理是采用“轮”循的方式随机选取簇首,每一轮由簇的建立和数据传输两个阶段组成。选举簇首时,每个节点都产生一个之间的随机数,并且按照当前轮数计算出一个门限值,当随机数小于该门限值时,该节点就被选为簇首。随后,簇首向全网广播消息,让其余节点加入到与之最近的簇,簇成员按TDMA时隙采集数据并发送给簇首,簇首融合数据后报告给sink节点。这样不停地轮循工作。协议的关键是门限值计算,公式为:式中,p为簇首数占总节点数的百分比;S为最近1/p轮中未当选过簇首的节点的集合;r为当前轮数。优点:1)簇首的选举用“轮”循的方式和分布式算法,使得各节点机会均等,能量消耗均衡,有效避免了簇首过快消耗能量,达到了延长网络运行时间的目的;2)数据融合因在簇内完成,减少了传输距离,节省了能量。缺点:1)每一轮都进行一次簇重组,选举簇首的开销量比较大;2)在整个网络中,簇首的分布不太均匀,且簇内的成员节点也不均匀,簇首间负载不均衡,造成有的簇首早死亡有的被闲置;3)簇内各成员节点因直接和簇首传递信息,加速了簇首的能量消耗,降低了网络的生存寿命,也造成了每个簇的规模有限,网络的扩展性不强,不适用于大型网络。针对这个典型协议的缺点,改进措施是在簇首选举过程中,分两个步骤进行:1)上一轮剩余能量多的节点作为下一轮候选簇首;2)设计一个随机数和阈值,根据这两个参数选举候选簇首,然后,该节点向簇内各节点进行广播自己的信息,再根据候选簇首的剩余能量和个数决定成为簇首,这样保证了网络的稳定性和低功耗。2.1.2letch协议ERC(ERPefficientroutingprotocol)主要适合于大规模无线网络中,在分簇算法中引入了智能算法。该算法采用两层路由,在第一层中采用LEACH协议的分布式算法,也是采用随机选举簇首,簇成员直接将数据传递给它们的簇首;在第二层中,这些簇首用蚁群优化算法,找最佳的路径去感知、采集和处理各节点的数据。优点:1)协议采用双层路由,争强了网络结构的稳定性;2)簇内采用蚁群优化算法,减少了网络时延。缺点:1)随机选举簇头造成簇首分布不均匀;2)每一轮都进行一次簇重组,簇头的开销量较大。总之,此类协议,因随机选举簇首,使得簇首节点分布不均衡,造成节点能量的消耗差异性很明显,对整个网络的寿命很不利。2.2基于剩余能量的集群协议簇首节点的选举,主要是依据每个候选节点的剩余能量而定,剩余能量值大的被选为簇首节点。典型的协议如下。2.2.1多跳+letchHEED(hybridenergy-efficientdistributedclustering)协议在选举簇首时,依据主、次参数进行选举,主参数的选取主要依赖于节点的剩余能量。初始时随机选举出簇首节点,剩余能量多的节点成为簇首节点的概率最大,能否成为簇首要看该节点比周围节点的能量大多少而定。而次参数依赖于簇内通信代价,主要是平衡簇首间的负载,确定节点属于的簇。HEED协议与LEACH协议类似,均采用“轮”循方法选举簇首,簇成员按TDMA时隙采集数据并发送给簇首,带来了簇间干扰问题。HEED协议通过多跳方式与基站通信,而LEACH协议采用单跳方式与基站通信。优点:1)簇首的分布均匀,分簇效率更快,网络结构更加合理;2)簇首的选举主要依赖于剩余能量,并以主次参数引入多个约束条件,很好地控制了报文开销。缺点:1)每一轮都进行一次簇重组,簇首的开销量比较大;2)因形成簇的覆盖区域有重叠,存在严重的簇间干扰,为了解决这个问题,文献提出DCHS协议算法,该协议减少因簇间干扰导致的数据碰撞。2.2.2无区分区分节点间竞争半径和网络能量EEUC(energy-efficientunevenclustering)协议簇首的选举也是依赖于剩余能量,为解决均匀分簇协议,在转发远距离sink的簇首消耗较大的能量,导致过早耗尽能量而死亡的问题。为了解决簇首将节约的能量供簇间转发数据时使用,该协议采用非均匀的竞争机制规划大小不等的簇,而靠近sink的簇内成员较少,具有竞争半径小的特点,因此该协议关键点是簇半径的计算,其计算公式为:式中,R0是候选簇首竞争半径的最大值;c在之间,是簇半径控制参数;dmax和dmin分别表示节点到sink距离的最大值和最小值;d表示簇首i到sink的距离。优点:1)簇首的选举考虑了能量消耗不平衡的问题,提高了网络生存时间;2)簇间选用多跳通信,节约了网络流量。缺点:1)簇的生成过程复杂,代价较大;2)因与sink距离不同的簇具有不同的簇半径,所以,传输数据和采集数据的精确度有很大的差异和误差产生。2.2.3第4轮机制的优缺点EBLP(energybalancedcluster-basedroutingprotocol)协议针对LEACH协议的缺点,结合PEGASIS协议优点,提出一种能量均衡的分簇路由协议。基本思想是网络运行采用“轮”机制,每轮进行簇首选择和数据传输,每隔一定时间周期性地进行一次簇的重组。在簇首选举时,先要计算出最优簇首数,并根据网络的范围确定每个簇首间的最短距离,然后根据剩余能量确定初始簇首;建立簇时,簇首采用贪心算法将簇成员节点形成链式结构,簇首控制簇内成员节点数,使整个簇结构合理和最优;簇首负责构建一个层次结构的路由树,选择最佳路由将采集、融合到的数据传给基站;数据传输时,每周期第一轮用初始选举的簇首传递数据,簇首的选举根据剩余能量多的而定,这样不停地轮询进行簇首的更新和重组。优点:1)因结合能量均衡和最优分布,网络的生命周期延长,能耗降低;2)簇首选举合理,建簇路由最优,数据传输速度快。缺点:1)延迟方面还要进一步改进;2)没有考虑安全因素。2.2.4节点k-dijpstor算法EQR(energy-awareQoSrouting)协议簇首的选举,是依据剩余能量、整个链路的误码率和簇首到邻节点的距离3个条件来计算出整个链路的开销,用分类排队模型,将节点设置成两种队列,即非实时队列和实时队列,用k-Dijkstra算法找出k条开销小的路径,将数据端到端的传输。优点:1)最大化地提高了网络的吞吐量,达到了实时业务的QoS要求;2)采用k-Dijkstra算法使开销的计算更加准确,簇首的选择更加合理。缺点:1)因采用集中式路由策略,使节点保留了整个网络的信息,不适合大型网络;2)各节点带宽一样,导致负载均衡差;3)开销的计算量大,花销值大。总之,此类协议能确保簇首节点最优、最佳地获得能量,来承担数据采集和数据转发工作。但簇首间的路由相对复杂,也很难保证簇首节点的合理分布和均衡性。2.3基于地理的集群协议在选举簇首节点时主要依据地理位置信息,典型协议如下。2.3.1节点传输方法PEGASIS(power-efficientgatheringinsensorinformationsystems)协议借鉴了LEACH的思想,通过贪心算法将网络中的节点利用定位技术串成基于地理位置的一条链,簇首也是周期性选举,节点只与距离它最近的邻居节点通信,采用令牌进行数据传输,邻节点将收到的数据连同自己的数据一起进行融合处理,然后传输给下一个节点,依次传输到目的节点,簇首负责将最后融合的数据传输给基站。优点:1)基于地理位置,使节点平均通信距离较短,减少了成簇开销;2)采用令牌,确保数据传输的可靠性;3)采用数据融合,减少了数据分送次数,降低了能量消耗。缺点:1)因节点基于地理位置,形成一条链,数据传输时的延长比较大;2)簇首的选举基本是均匀的,导致簇间干扰大、开销大。2.3.2距离节点数据传输在TTDD(two-tierdatadissemination)协议中,簇首的选举是由数据源节点的地理位置而定,簇首由距离发送数据最近的节点承担,该协议主要是为了解决汇聚节点频繁移动情况下的数据传递问题。协议工作过程由网格构建阶段、查询发送节点和数据传输3个阶段组成。优点:1)解决了汇聚节点频繁移动的问题;2)基于地理位置,使得节点平均通信距离较短。缺点:1)在快速移动的监测目标时,数据延迟大,数据采集的实时性较差;2)数据源太多,网络的构建重复比较大,开销太大。2.3.3节点位置和距离阈值LACA(locationawareclusteringalgorithm)是针对LEACH协议的缺点,提出的一种基于地理位置感知的分簇协议。该协议引入角度比和距离比两个感知参数,使节点通过其所在的位置自主地决定是否作为簇首。主要是计算出节点间的距离和连线与水平线之间的夹角,角度、角度比和距离比的计算公式分别为式中,R为通信距离;Nx和Ny分别为节点N的横纵坐标;Mx和My分别为节点M的横纵坐标。通过上述公式,就可以确定节点偏离理想簇首位置的程度。簇首的选举主要根据角度比n和距离比uf064而定,所以,合理设置角度和距离的阈值是非常重要的,这样才能构建理想的分簇结构,保证能量的有效性和网络的可靠性。优点:1)能量有效性高、网络寿命长、网络能量和负载均衡性好;2)无需构建网络拓扑结构,路由表的建立、维护和存储实现简单。缺点:1)协议有局限性,可扩展性较差;2)协议根据网络规模自适应地改变角度比和距离比阈值差。2.3.4节点间通信优化GAF(geographicadaptivefidelity)协议是根据地理而选择路由的算法,所有节点通过GPS定位获知自己的“位置”,把所有这样的“位置”连接起来就形成了一个虚拟网络。在网络中,根据节点“位置”是否相同来决定节点是否工作。如两个节点“位置”相同,则看作是等价路由,这样的节点只需其中之一工作,剩下的节点就进入到休眠状态,这样大大节约了能量。优点:1)节点定位比较准确,节能性好;2)无需建立、维护和存储路由表,无需网络拓扑信息,实现简单。缺点:1)算法只考虑了地理位置的平面关系,而没有考虑实际网络中节点通信与节点间的距离没有关系的问题,因为,实际网络应该是逻辑的而与物理位置无关;2)硬件要求高,适用性差。总之,此类协议的簇首节点分布合理,路由间通信简单,但没有考虑到节点的剩余能量,可能会存在新当选的簇首节点因能量不够而无法胜任数据转发任务的情况。还有,簇中的节点如想工作必须要定位好自身的地理位置,这样会增加系统的负担,所以适用于需要地理信息的应用。3当前wsn路由协议性能分析综上所述,本文总结、分析了3类目前典型的分簇路由协议的运行机理、优缺点。在已有的算法中,HEED、EBLP、GAF节能性较好;LEACH、HEED、ERC因采用分布式算法,扩展性、能量有效性和收敛性较好,但算法健壮性较差。综合影响协议的多个因素,对典型的分簇路由协议进行综合对比,如表1所示。表中,A为协议类型;B为簇头产生速度;C为数据融合;D为簇负载平衡性;E为簇形成速度;F为簇维护开销;G为健壮性;H为扩展性;I为算法节能性;J为延迟;K为控制方式;“…”表示当前该参数不清楚。从表1中发现,现有的WSN路由协议在节能、数据融合、收敛速度等方面都有很多优势,但仅仅是体现在某一个