无线传感网络的应用与分簇组织

无线传感网络的应用与分簇组织

一、基于分簇的人工神经传感网络设计无线传感器网络由各种依靠微电池电源的传感器组成。这些传感器能够监测环境的变化，具有一定的数据处理和无线通信能力。传感器利用感知元件和相关电路测量所处环境中感兴趣的各种参数并将它们转换为电信号,然后利用自带的无线收发器来传输采集的数据。无线传感网络为了完成特定任务,必须按照某种网络协议或算法将大量传感器有机地组织起来。传感网络在军事和民用上都大有用武之地,如军事目标侦察、天气预测、抢险救灾和侦探考察等。传感网络的优点之一是无需人干预能够在恶劣环境下完成特殊的任务,因此,传感节点通常以一种随机非受控的方式部署在感兴趣的区域内,并以自组织方式构成传感网络。考虑到传感网络覆盖区域较大并且传感节点靠电池供电,因此通常需要部署数量巨大(成千上万个)的传感节点。因此,大规模传感网络的设计需要可扩展的体系结构和管理策略,并且需要设计能量意识的算法以延长传感节点和传感网络的寿命。为了提高网络的可扩展性,很多学者都提出采用分簇结构来组织网络中的节点。通过某种分簇算法将网络划分成多个簇,每个簇通常含有一个称为簇头的管理节点,有时也可以不选举簇头。在Adhoc网络中,由于网络规模不大,分簇算法的目标主要是在移动网络环境中获得稳定的簇结构和提高网络性能(如改善路由和方便网络管理等),而较少考虑网络可扩展性和网络寿命。迄今,针对传感网络已提出了一系列分簇算法,其目标和性能各不相同,这取决于节点的部署方式、希望获得的网络体系结构、簇头的特性和网络操作模式。举例来说,簇头可能是由节点推选出来的,也可能是预先指定的。簇成员可以是固定的,也可以是动态变化的。除了提高网络可扩展性之外,分簇结构还有如下优点:减少路由开销,保存网络带宽、防止簇内访问冲突,便于网络管理以及延长节点和网络寿命。本文旨在对传感网络中的各种分簇算法进行归纳、比较和分析,并说明其优缺点和适用场合。二、集群配置和集群特征的考虑1.监视过程主要表现为自适应的分簇策略不同的无线传感网络应用具有不同的体系结构和设计目标/约束,下面给出一些相关的体系结构参数并说明它们对网络分簇的影响。(1)网络动态性:无线传感网络的三个主要实体是传感节点、基站和感知的事件。大多数情况下传感网络假设传感节点是静止的,但有时也需要支持节点或基站的移动。另外,监视的事件是间歇式的或者是连续的。例如,在目标跟踪中监视的事件是连续的,而在天气预报或森林防火预警中监视的事件是间歇的。监视间歇事件允许网络以反应模式进行操作,也就是说只需在上报事件时产生流量;而连续监视则需要定期上报,将会产生较大流量。因此,连续事件监视适合采用稳定的分簇策略,而监视间歇事件倾向采用自适应的分簇策略。(2)数据聚集和处理:由于相邻的传感节点会产生大量冗余数据,可以聚集来自多个传感节点的数据以减少传输开销,可以采用的数据聚集方法包括求交集、最小值、最大值或平均值。能量聚集中数据处理和计算的能耗远小于数据通信消耗的能量,从而可以大大节省能量耗费。在分簇网络结构中,通常期望簇头执行数据聚集功能,但是这对簇头有特殊要求或限制每个簇中节点的数量以便不至于使簇头负担过重。有时,甚至需要个节点轮流充当簇头来分担数据处理开销。(3)节点部署及能力:节点部署方式与应用相关并影响网络分簇的目标。节点部署或者是预先确定的,或者是自组织的。如果采用确定性部署方式,那么传感器按预设位置部署并且数据沿预设路由传递。在这种情况下分簇或者是预置的或者没必要分簇。而在自组织部署方式中,传感节点随机布撒在网络中构成自组织网络结构,在这种情况下基站和簇头的位置对于网络性能和能量效率至关重要。节点能力不同,簇头的选择也不相同。对于同质传感网络而言,节点能力相同,通过某种选举算法由节点推选簇头。而对于异质传感网络而言,则倾向选择能量较强、功率较大的节点充当簇头。2.分簇算法的一般原则分簇目标通常是为了满足特定的应用需求,举例而言,如果应用对数据传输延迟敏感,分簇算法则必须考虑合理组织簇结构以减少分组传输所经路由的长度。下面列出一些常见的分簇目标:(1)负载平衡:分簇算法通常希望传感节点均匀分布在各个簇中,以便使簇头合理分担网络负载,从而延长网络寿命。此外,负载平衡有利于各簇头花费大致相同的时间聚集数据,从而减少向基站上报数据需要等待的时间。(2)错误容忍:无线传感网络很多时间工作在恶劣的环境中,节点出现故障或遭受损坏的风险较大。为此,分簇算法必须具有较好的错误容忍性,防止因簇头故障而导致重要信息的丢失。如果重新对网络分簇则会带来较大开销并且会中断正在进行的操作,因此希望簇头具有错误容忍能力。一种方法是为每个簇分配备用簇头,另一种方法是规定由节点轮流充当簇头。(3)增强连接和减少时延:除非簇头具有较强的功率并支持长距离的通信,否则都必须考虑簇间的连接,特别是在同质传感网络中。网络连接的基本目标是确保所有簇头都可以到达基站,更苛刻的目标则是限制路径的长度。也就是说,簇间连接性问题可以看成图论中的连接统治集问题。当考虑减少时延时,还要考虑簇内连接问题。此时,需要规定簇内允许的最大跳数和数据路径的最大跳数。(4)簇数量最小化:在异质网络中,这种目标很常见,因为设计者希望减少簇头节点的数量以便于网络部署和节省网络成本。特别是在军事应用中,这些簇头节点往往是体型较大的设备,数量越少越不容易暴露。(5)网络寿命最大化:这是无线传感网络普遍追求的目标。对于异质传感网络而言,应尽量减少簇内通信的能耗,例如簇头应与簇内大部分节点之间保持较近的距离。对于同质网络,负载平衡对于延长网络寿命非常有效。3.簇之间的连接(1)簇本身的特性:分簇算法设法使得到的簇结构都具有某些特性,主要包括:簇数量、稳定性、簇内拓扑、簇间连接等。举例来说,簇数量可以是预先设定或者根据节点部署情况动态变化的;簇结构的稳定性与簇内节点的变化紧密相关;簇内通信可以是单跳也可以是多跳通信;簇之间的连接可以是单跳或多跳,前者假定簇头可以直接与基站通信。(2)簇头的特性:影响分簇算法的簇头特性包括移动性、簇头节点的类型和簇头充当的角色等。具体而言,当簇头移动时其簇成员也会动态更改,因此也需要动态维护簇结构。而簇头静止时则可以得到稳定的簇结构并有利于簇内和簇间网络管理。如前所述,簇头可能是特殊的功能较强的节点,也可能是普通节点按照某种规则选举得到的。簇头的角色包括充当簇内业务转发的代理、执行数据聚集/融合功能以及选举更高层的簇头等。(3)分簇过程的特性:分簇过程涉及的特性包括执行分簇过程的方式、分簇的目标、簇头选择方法和分簇算法的复杂性。分簇过程执行的方式包括分布式和集中式两种方式,并以前者较为常见。分簇的目标和簇头选择方法前文已介绍过,不再赘述。根据分簇目标提出了大量分簇算法,这些算法的复杂性和收敛速率依赖于网络规模和分簇方法。三、无线传感网络的分簇算法一般来说,无线传感网络包含大量的传感节点,少则上百多则成千上万。因此,分簇算法对于改善无线传感网络的性能至关重要。在此根据算法收敛时间将分簇算法分为两大类:收敛时间可变的算法和收敛时间恒定的算法。1、负载平衡节点id分簇算法很多分簇算法,如LCA(LinkClusteringAlgorithm)、RCC(RandomCompetitionbasedClustering)等,的收敛时间是O(n)量级的,n为网络中传感节点中的数量,因此对于规模较大的网络,收敛速度较慢。相比而言,收敛时间可变的分簇算法能够对分簇特性施加更多的控制,下面简要介绍其中一些典型的分簇算法。(1)基于节点ID的分簇算法:LCA是由Baker较早提出的一种用于高频特遣部队(HFITF)通信网络的经典分簇算法,形成的簇为1跳有头簇,目标是最大化网络连接以便构造能够有效管理节点移动的网络拓扑。LCA算法中规定,每个节点分配唯一的标识符(ID),邻居节点中具有最高ID的节点成为簇头,并且如果一个节点是它的某个邻居节点的具有最高ID的邻居节点,则该节点也成为簇头。该分簇算法的一种实现是首先选择最高ID的节点作为簇头,如果次高ID的节点所覆盖的范围内存在没有被最高ID的簇头节点覆盖的节点,那么次高ID节点也将成为簇头,否则继续检查下一个ID较高的节点,直到所有节点属于某个簇。采用这种方法可以方便地构造分簇网络结构,但是它将会产生过多的簇头,特别是当节点按ID递增的顺序线性排列时,此时除第一个节点外,其它节点都为簇头。最小ID启发式算法是由Grela和Tsai提出的一种简单的分簇算法,它基于LCA算法的设计思想,并对其进行了改进来减少簇头的数量。该算法规定,相邻节点中具有最小ID的节点作为簇头,其一跳邻居节点成为该簇头所在簇的成员节点,并不再参与簇头选举过程。此外,在某些特殊情况下,簇头可以将其职责交付给其簇内具有最小ID的成员节点。这种分簇算法计算简单,实现方便,算法收敛较快。在移动环境下,最小ID算法的簇头更新的频率较慢,维护簇所需花费的开销的较小。其缺点在于这种算法倾向选择具有较小ID的节点作为簇头,将使这些节点消耗更多的电池能量,从而会减少整个网络出现分割的时间,此外该算法没有考虑负载平衡等因素。(2)考虑能量耗费和稳定度的分簇算法:基于ID的分簇算法倾向于选择ID较小的节点作为簇头,使得这些节点的负担较重,很容易耗尽能量。为此,需要在簇头间实施负载平衡,使所有节点都可以较公平地充当簇头。而对于最高节点度算法,由于节点的邻居节点数经常发生变化,簇头负载分布特性较好,但簇结构很不稳定,需要设法提高簇结构稳定性。基于以上考虑,通过对最小ID启发式算法进行改进来实现负载平衡节点ID分簇算法和负载平衡节点度分簇算法。在负载平衡节点ID分簇算法中,将限制簇头的生存时间在一个预算值之内,如果节点充当簇头的时间超过预算值,该簇头将其簇头角色转让给其它节点。负载平衡节点度分簇算法下,节点只需保存两个本地变量:当前的节点度和选举度,选举度表示该节点被选举为簇头时的节点度。算法运行时,节点将计算当前节点度与选举度之间的差值,如果差值的绝对值超过某一规定的门限值,则簇头降级为普通节点,从而提高了簇结构的稳定性。(3)基于信道接入的分簇算法:Ting-ChaoHou等人提出了一种基于信道接入的被动分簇算法(ABCA,AccessBasedClusteringAlgorithm),簇的形成依赖于媒体接入控制协议。由于ABCA根据节点接入信道的结果来做出分簇决定,因此它不需要发送显示的分簇消息,而是将与分簇相关的状态信息附加到数据分组中,从而引入更少的控制开销,算法收敛较快并具有较稳定的簇结构。在簇形成过程中,每个节点都试图接入控制信道来声明自己是簇头,一个节点如果在它的所有邻居节点中最先成功地发送了簇头声明控制消息,那么它将成为簇头。收到簇头声明消息,并且自己还没有成为簇头的节点将成为该簇头节点的成员节点。一旦一个节点成为簇头并且它至少有一个成员节点,它将一直充当簇头直到它离开网络或者出现故障。当一个节点刚刚加入网络或想改变其簇时,它可以根据接收到的Hello消息来选择一个邻居簇头作为簇头。由于这种分簇方法依赖于控制信道上运行的MAC协议,不需在节点间交换大量的消息来确定簇头,减少了分簇开销。(4)GS3:GS3(Geography-awareAlgorithmforScalableSelf-configurationandSelf-healing)旨在将无线网络配置成蜂窝网络结构。该算法的作者认为应该考虑簇的地理范围,定义包含簇中所有节点的圆周半径作为集合尺寸的度量。较大的簇半径会减少簇数量,但是会增加能耗并降低无线信道的空间重用率。假定系统包含两种节点:大型节点和小型节点。大型节点负责发起簇形成过程并作为小型节点的管理者。为了形成蜂窝六边形结构,将区域划分成半径相等的小区,并且某节点一旦成为某小区的簇头,该簇头要重新定位到该小区的中央。GS3与其他分布式算法的不同之处在于它可以事先预测网络中簇头的布局和数量。GS3是自愈的并因此适用于静态网络和动态网络。(5)能量高效的分级分簇算法(EEHC,EnergyEfficientHierarchicalClustering):EEHC是一种用于WSN的分布式随机分簇算法,目标是最大化网络寿命。簇头收集和聚集簇内传感节点的信息并向基站上报融合的数据。分簇包括两个阶段:初始阶段和扩展阶段。在初始阶段形成单级簇,节点以概率p向邻居节点声明自己为簇头,收到声明通告的任何非簇头节点变为最近簇头所在簇的成员节点。不属于任何簇(没有收到任何声明通告)的节点也将成为簇头。在第二阶段,扩展分簇过程以形成多级簇。即在簇头节点中按照上述分簇方式构成更高级的簇。算法设法确保簇头和基站在h跳内可达。数据聚集发生在每一级的簇头,最后由最高级簇头将最终的聚集数据发往基站。通过多级分簇极大减少了传输开销和能量耗费,特别适合于大规模无线传感网络。2、利用混合分簇实现分布式分簇这类分簇算法的收敛时间与网络中节点的数量无关。这些算法通常采用本地化策略,节点独立执行算法并且基于自身状态和邻居节点的状态决定簇头和簇成员,下面列出几种常用的这类分簇算法。(1)低能量自适应分级分簇(LEACH,LowEnergyAdaptiveClusteringHierarchy):无线传感网络的节点数量庞大,并且常常需要在无人职守地在恶劣环境中工作。因此,需要高效地使用节点能量以延长网络的有效操作时间。LEACH是一种用于无线传感网络的分簇协议,其目标是尽可能将能量消耗均匀地分配到各个节点上,以延长网络的寿命。考虑到簇头的能量耗费远大于普通节点,因此希望节点以近似相等的概率来轮流充当簇头。LEACH中,簇头的选举基于随机种子的方法,即每个节点n在第r+1个循环周期随机选择一个(0,1)的数字,并与门限值T(n)比较,如果小于该值,则该节点成为簇头。该算法假设节点能量相同并且功能相同,否则能量较多的节点充当簇头的概率应较大,以确保所有节点大致在相同的时间耗尽能量。成为簇头的节点使用CSMA协议向整个网络发出广播消息,其它传感节点基于信号强度来选择相应的簇头和簇。使用这种方法,簇产生的通信开销相对较少,适合于节点数量众多的传感网络,但是不能保证簇头合理地分布在网络中。另外,考虑到传感网络中通常具有中心节点,可以由中心节点收集节点的相关信息来实施集中式的分簇算法以优化簇结构,但是开销较大。(2)簇建立算法(ACE,AlgorithmforClusterEstablishment):ACE利用一种类似神经网络的方法来获得簇头和生成簇。它的主要思想是允许节点在希望成为簇头之前评估其作为簇头的可能性,并且如果它不适合作为簇头则放弃簇头角色。算法主要包含产生新簇和节点迁移这两个重要部分。在节点决定成为簇头时会产生新簇,然后广播邀请消息招募邻居节点。一个节点收到招募消息后可以加入该簇,并且允许节点同时加入多个簇。迁移过程是选择最佳簇头的过程。每个簇头定期检查邻居节点充当簇头的能力,簇内具有最大邻居节点并且与其他簇交叠最小的节点被认为是最佳的簇头候选者。ACE的收敛时间为O(d),d为网络的平均节点密度。ACE较好适应节点的移动、加入和离开。(3)混合的能量高效的分布式分簇(HEED,HybridEnergy-EfficientDistributedClustering):HEED是一种具有能量意识的分布式分簇算法,具有较高剩余能量的节点优先成为簇头。HEED中簇头能较均匀分布在网络中且可以根据节点传输范围调整簇头选择的概率以确保簇头之间的连接。在HEED中每个节点对应一个簇并能够直接与簇头通信,算法分成三个阶段:初始化阶段、循环阶段和终结阶段。初始化阶段中算法首先设置一个预定的簇头比例来限制声明充当簇头的数量。每个节点成为簇头的概率与剩余能量成正比。在循环阶段,节点通过多次迭代找到能够以最小传输功率与之通信的簇头,如果找不到簇头则自己充当簇头并向邻居节点发送声明消息。在此阶段节点可能临时充当簇头(成为簇头的概率小于1)并且可以在找到更低成本簇头的情况下降为普通节点,每循环一次,节点成为簇头的概率翻倍直到为1结束。在终结阶段每个节点确定自己的状态,或