无线传感器网络节点能量受限时响应式分布分簇算法

无线传感器网络节点能量受限时响应式分布分簇算法

1网络生存期的限制无线传感器网络（无线传感器网络）是指由大量小型传感器节点在观测环境或附近无线通信的情况下形成的多跳网络。WSN具有广泛的应用前景,在军事、环境监测、工业控制、智能家居、城市交通和现代化农业等方面都有重要的研究意义和实用价值,已成为近期的热点研究领域之一。WSN中的节点通常以电池供电,其能量有限,一般不易更换或重新充电,因而提高能量使用效率、延长网络生存期变得特别重要。与普通adhoc网络相比,WSN中的节点一般移动性较低,带宽需求不高,但是具有较高的节点密度。这些特点决定了很多用于普通adhoc网络的技术不能直接用于WSN。由于网络中通常只有少量的汇聚点(sink)发布命令和收集数据,大多数节点无法直接与汇聚点通信,需要中间节点通过多跳和路由选择来实现,而在无线通信中节点所消耗的能量最大,故路由协议对网络生存期的影响至关重要。现有的路由协议从网络结构上可以分为3类:1)平面路由协议,所有节点的地位是平等的,可扩充性和实时性较差,同时维护动态变化的路由需要大量的控制信息;2)层次路由协议[4~7],按簇(cluster)将网络划分为多个小区,不需要维护复杂的路由信息,具有较好的可扩充性,易于采用数据融合技术减少网络中的冗余数据,从而降低通信量,其缺点是簇头节点(clusterhead)可能会成为网络的瓶颈;3)基于定位的路由协议,需要预先获得节点的位置信息,这对于某些应用导致成本过高。本文提出了一种响应式分布分簇算法(RDCA,responsivedistributedclusteringalgorithm)。首先给出所使用的网络模型和能量模型,接着论述算法的执行步骤,分析其性能,给出仿真结果,最后对算法的优点及存在的不足进行了讨论。2节点的工作特性本文采用两层结构的网络模型,簇头节点收集簇内成员发出的数据包并进行数据融合,得到的数据包直接发送给汇聚点,如图1所示。需要指出的是,本文提出的分簇算法只解决了簇形成问题,对簇头到汇聚点的路由方式不作任何要求,因此也可用于其他结构,如簇头之间可采用多跳方式将数据包传送至汇聚点。汇聚点有时也称为基站(BS,basestation)。此外,本文中对节点作如下假设:1)节点基本是静止的,这符合大多数应用环境;2)无线链路是对称的,即相邻的2个节点可使用相同的发射功率互相通信;3)节点不知道自己的位置,网络中没有任何辅助定位设施,算法执行所需的信息仅来自于相邻节点;4)所有节点是同构的,即具有相同的数据处理与通信能力,成为簇头的机会均等;5)节点不可充电,当初始能量耗尽后,节点即死亡;6)节点的发射功率有固定范围,在此范围内的发射功率可动态调节以节省能量;7)节点主动地、周期性地向汇聚点传送数据。整个网络活动由簇的建立期和稳定工作期2种状态组成,2种状态交替出现。分簇算法定时被激发,设经过时间Tsetup后分簇形成,接着进入稳定工作期,设时间长度为Twork。为降低成簇开销,显然应该有TsetupTwork。假定簇内节点使用TDMA方式进行通信,网络的稳定工作期划分为若干个TDMA帧,每个成员节点使用TDMA帧内的一个时隙。使用TDMA方式的好处是节点可以只在自己的时隙到来时打开收发器,其余时间关闭以节约能量。时间分配如图2所示。假设发送端消耗的能量包括信号处理与功率放大2部分,接收端消耗的能量仅用于信号处理,并且假设当2节点距离小于d0时采用自由空间路径损耗模型,大于等于d0时采用多径衰落模型。因此,当2个距离为d的节点之间发送l比特数据时,发送端所消耗的能量为接收端消耗的能量为式(1)、式(2)中Eelec指信号处理所需能量,单位为J/bit,与εmp分别指自由空间模型以及多径衰落模型下的能量损耗,单位分别为J/(bit·m2)和J/(bit·m4)。在稳定工作阶段,每个TDMA帧循环中,簇头接收来自簇成员的传感数据,加上自己的传感数据进行数据融合,形成一个单帧直接发送到Sink,因此每个TDMA帧期间簇头所消耗的能量为非簇头成员消耗的能量为式(3)、式(4)中l指每个数据包的比特数,n指簇内节点数(包括簇头),EDA指进行数据融合所需能量,单位为J/(bit·signal),dtoBS为簇头到基站的距离,dtoCH为非簇头节点到簇头的距离,这里假设dtoBS≥d0,dtoCH<d0。3植生混凝土一般算法一般来说,一个好的分簇算法需要满足以下要求:1)通过均衡负载、避免单个节点的能量过早耗尽延长网络生存期;2)快速收敛;3)减少控制信息的数量;4)簇头具有良好的分布性。RDCA算法的出发点是改进原DCA算法的负载平衡功能。在RDCA中,非簇头节点在选择簇头时使用3种不同的代价函数(CF,costfunction)进行比较,分别为:最近节点(closestnode);最大节点度(maximumdegreeofnode)和最小节点度(minimumdegreeofnode)。3.1相邻节点的选取程序算法的执行分为初始化与主体2部分,主体部分采用消息驱动机制。假设网络内每一个节点均有全网惟一的正整数为自己的识别码(ID,identificationcode),节点权值取剩余能量。需要使用到的集合与变量定义如下:Snbr:相邻节点集合,初值为空;SCH:相邻节点中簇头节点集合,初值为空;Scovered:相邻节点中被“覆盖”的节点集合,初值为空;Shigher:相邻节点中比本节点权值高的节点集合,初值为空;Sdecided:相邻节点中已经选定簇头的节点,初值为空;is_covered:是否已被“覆盖”,初值为否;is_CH:是否为簇头,初值为否。“相邻”节点的定义为:如果2个节点距离小于簇半径,则互为相邻节点(本算法采用固定大小的簇半径)。“覆盖”的定义为:如果一个节点的簇半径范围内至少存在一个簇头,则该节点被“覆盖”。类似地,如果不存在簇头,则称该节点未被覆盖。节点u初始化:首先每个节点都在簇内广播自己的权值,并收集邻居节点的ID和权值。如果没有邻居节点,则节点宣称自己为簇头并退出算法。否则选出所有权值高于自己的节点存入Shigher。如果Shigher为空,则说明自己是簇半径范围内权值最高的节点,该节点宣称自己为簇头并在簇内广播CH(u)消息。程序流程图如图3所示。主体部分会生成并处理3种消息,每种消息的处理过程如下:收到CH(v)消息:如果节点u收到节点v发出的簇头消息,则将节点v并入集合SCH和集合Scovered。如果该节点未被覆盖,则标志自己为“已覆盖”,并在簇内广播COVERED消息。如果Scovered与Snbr相等,即所有相邻节点均被覆盖,则在SCH中选择CF最小的节点作为自己的簇头myCH,发出JOIN(myCH,u)消息,随后退出算法。注意只有非簇头节点会收到其他节点的CH消息,说明见下节。程序流程图如图4所示,其中的(1)、(4)接图3。收到COVERED(v)消息:如果节点u收到节点v发出的“已覆盖”消息,则将节点v并入集合Scovered。如果节点u尚未被覆盖,且Shigher⊆Scovered,说明所有权值比自己高的邻居节点已被其他簇头覆盖,则宣称自己是簇头节点。如果节点u不是簇头Scovered与Snbr相等,即所有相邻节点均被覆盖,则在SCH中选择CF最小的节点作为自己的簇头myCH,发出JOIN(myCH,u)消息,随后退出算法。程序流程图如图5所示,其中的(2)、(3)、(4)接图3。收到JOIN(ID,v)消息:如果节点u收到节点v发出“申请加入”消息,则将节点v并入Sdecided。如果节点u为簇头,则查看所申请加入的簇头ID是否为自己,如果申请加入自己,则将节点v加入自己的簇成员列表供以后使用。如果Sdecided与Snbr相等,说明所有邻居节点均已选定簇头,则算法退出。程序流程图如图6所示,其中的(3)接图3和图5。3.2算法的时间复杂度本算法具有如下性质:1)算法是分布式执行的,且算法的执行仅依赖于相邻节点的信息因为限定了节点使用固定的发射功率发送分簇消息,因此算法执行时只有在簇半径范围内的节点(即相邻节点)能够接收到分簇信息。即消息域为1hop。2)每个非簇头节点只选取一个簇头节点当非簇头节点发现所有的邻居节点均被覆盖时(即所有邻居节点都已确定自己是簇头还是非簇头节点),才会在SCH中选择一个簇头加入,且申请加入后即退出算法,因此显然每个非簇头节点只选取一个簇头节点。3)簇头的分散性良好,任意2个簇头都不相邻假设2个节点u、v相邻,不失一般性,假设wv≥wu且IDv>IDu,则v⊆u的Shigher,因为节点在Shigher全部被覆盖后才能发出CH消息,因此节点v如果成为簇头,将先发出CH消息。当节点u收到节点v的CH消息后,即将自己的is_covered状态改为TRUE。而算法中只有is_covered状态为FALSE的情况下才可能发出CH消息,因此节点u将没有机会成为簇头。可见不可能存在2个相邻的簇头。4)算法的时间复杂度为O(d),d为网络直径无线传感器网络的拓扑结构可看作由节点与无线链路构成的无向图,记为G=(V,E)。其中V表示节点集合,E表示边的集合。∀u,v∈V且u≠v,定义h(u,v)为节点u和v之间的最小跳数。假设G由M个连通分量G1=(V1,E1),G2=(V2,E2),…,GM=(VM,EM)构成,则d=maxdi,其中di=maxh(u,v),u,v∈Vi且u≠v,i=1,2,…,M。显然,d≤n-1,且在通常情况下有dn。设每个CH、COVERED、JOIN成功发送和接收所需时间为单位时间,初始化阶段发出CH消息的为“种子”节点,显然连通图中权值最高的节点必为“种子”节点,也就是每个连通分量至少有一个“种子”节点。设网络直径为d,则最差情况下某节点u到“种子”节点的距离为dhop,因此最晚经过d个单位时间可以收到所有相邻节点的CH或者COVERED消息。如果节点u为非簇头节点,则最晚在d+1个单位时间发出JOIN消息并退出算法执行。因为所有非簇头节点最晚在d+1个单位时间内发出JOIN消息,而簇头收到所有邻居节点的JOIN消息后退出,因此所有簇头节点最晚在d+2个单位时间内退出算法执行。因此,所有节点中算法执行完毕的时间复杂度为O(d)。5)算法的消息复杂度为O(n)对于簇头节点,每次最多发送初始状态广播和CH这2个消息,而对于非簇头节点,每次最多发送初始状态广播、COVERED和JOIN这3个消息,因此每个节点的消息复杂度为O(1),整个网络的消息复杂度为O(n)。DCA算法的一个缺点就是簇头的负载平衡性不好,因为非簇头节点只能加入它所知道的第一个簇头节点,而RDCA算法通过使非簇头节点有机会选择具有最小cost的簇头节点,改善了簇头负载,避免了单个节点过早能量耗尽,从而延长了网络生存时间。关于簇头数的选取,文献通过最小化全网能量消耗给出了最优值计算公式,但该公式仅适用于簇头到汇聚点为单跳的情况,并假设网内所有节点均可互相通信,无固定的簇半径。RDCA算法与HEED、DCA等算法相同,采用固定簇半径,并通过调整簇半径的大小间接控制簇头数目,其最优值的求解还必须考虑簇间路由方式等,而本文仅讨论了成簇算法,因此关于簇头数最优值的求解将留待以后进行。4日进程网络下最大节点比例的确定使用的仿真环境为随机分布在2000m×2000m范围内的1000个节点,每个节点的初始能量服从(0,1)上的均匀分布,单位为焦耳。仿真了簇半径从25m到400m时原始的DCA算法以及CF分别为距簇头的RDCA(最短距离,closest)、RDCA(最小节点度,mindegree)和RDCA(最大节点度,maxdegree)4种条件下分簇算法产生的每簇成员节点数的标准差以及非单簇头(即簇内不止簇头一个节点)的比例。图中每个点均为100次独立实验取平均值。由图7与图8可见,RDCA(最短距离)的每簇节点数的标准差较低,而非单簇头比例较高,说明RDCA(最短距离)具有更好的负载平衡性能,而DCA、RDCA(最小节点度)与RDCA(最大节点度)之间的性能接近。图9为相同拓扑环境和初始能量下DCA算法与RDCA(最短距离)算法一次实验的分簇结果。图中清楚可见RDCA(最短距离)算法具有更好的负载平衡性能。以下是RDCA(最短距离)与LEACH协议在同样网络初始环境下的仿真结果。LEACH协议中节点i以iP(t)的概率成为簇头,iE(t)为节点i的剩余能量,k为簇头数(本实验中k取11),。这里假设每轮结束后簇成员节点将自己的剩余能量数据发送给簇头节点,簇头将簇内所有节点的剩余能量信息融合为一个数据帧并在全网广播,这样每个节点在一轮结束后均可获得全网所有节点的剩余能量信息,由此计算出totalE(t)的值。仿真使用的参数如表1所示,参数定义如前所述。令网络内节点数为300~700,假设节点在消耗完初始能量的99.9%以后死亡,而最后一个节点死亡时所经历的轮数即可认为是网络生存期,得到仿真结果如图10所示。由图10可见,RDCA(最短距离)比LEACH协议延长约40%的网络生命周期,其中一个重要原因是LEACH在分簇算法执行过程中需要将每个节点的剩余能量信息在全网内进行扩散,因而额外消耗了大量能量,而RDC