无线传感器网络中竞争能量辅助的节能分布式分簇算法

无线传感器网络中竞争能量辅助的节能分布式分簇算法

“集群分离技术”将节点分为集群或集群。每个集群有一个集群头和许多集群节点。集群将网络划分为两层结构。集群节点形成顶层，成员节点形成底层。集群节点将数据发送给集群节点，并将数据整合到其他集群节点。集群技术是一种优化能耗的拓扑数据结构，它可以减少冗余数据的存储，延长网络的使用寿命，有效地集成网内数据，减少数据报告的延迟，提高网络的可扩展性。由于集群节点总是远程传输数据，因此需要更多的能量。因此，网络定期重新排列，选择能量丰富的节点来执行集群节点，并将负载均匀地分布到所有节点。集群路径是传感器网络的一个热门研究领域。其研究重点是集群分割算法。一般来说，集群分割算法可以控制每个节点的常数级消息的通信能力，这是分布式算法比集中分发算法的主要优点。分布分发算法通常需要当地计算集群分发算法，以控制集群数据的占用，这是分布式算法比集中算法的主要优势。虽然分布分发分割算法通常需要在本地计算簇头竞争，但数据计算的能力远低于数据结构。因此，对于传感器网络，数据处理的能力往往可以忽略不计。此外，集群技术对网络的吞吐量没有负面的影响。正如heed协议验证所示，在高通信负载下，由于降低信噪比竞争，网络的吞吐量显著增加。1网络模型和问题描述1.1聚合节点的确定本文不妨假设n个传感器节点按均匀分布随机高密度部署在一个监测区域A内,具有如下性质:1)传感器网络为高密度静态网络,节点部署后可扩充.所有传感器节点都被事先编排唯一的ID号,编号不妨为1,2,…,n,唯一的汇聚节点Sink编号为*,Sink节点位置任意.2)节点的能量可异构,但不能补充,即不要求所有节点的初始能量E具有相同值.3)所有节点不能获知其位置信息.4)通常各节点通信半径为rC,但各节点无线发射功率可调.例如,BerkeleyMotes节点是一种典型的实例,它经由标准的ioctl()系统调用直接设置发射功率级别.5)网络中节点的时间是同步的.1.2eadeeg协议的分簇算法文献对国外典型的无线传感器网络分簇算法进行了详细的分析和比较.我国学者对无线传感器网络分簇技术也展开了大量研究,其中文献提出的一种基于簇结构的无线传感器网络数据收集协议EADEEG(anenergy-awaredatagatheringprotocolforwirelesssensornetworks)是近年来提出的颇有新意的算法.该协议采用了一种全新的簇头竞争机制,能够更好地解决节点能量异构问题,提出了一种以邻居节点的平均剩余能量与节点本身的剩余能量的比值作为节点竞争簇头参数的簇头产生算法,该方法使簇分配更加均匀且延长了网络寿命.但通过仔细分析,EADEEG存在以下有待进一步改善的问题.问题1.EADEEG协议的分簇算法在某些情况下会在检测区域产生一些缝隙区域,如图1所示,缝隙区域中尽管存在节点5,该节点由于剩余能量小于邻居6,7,8,9的平均能量而超时(指t越过T的值),不能竞争簇头,但又收不到邻近的任何簇头1,2,3,4发出的簇头申明消息,不能属于任何簇而成为“孤点”,周围的缝隙区域也变得不可监测.问题2.在EADEEG协议的分簇算法中,为了保证由所有簇头节点形成的子图是连通的,文献中将簇间通信半径设置为2rC,以确保由簇头形成的子图的连通性.但图1显示,有簇头节点1并不能与簇头2,3,4中的任何一个簇头连接,因为它们之间的距离都大于2rC.可见这种假设并不能保证分布式分簇算法产生的簇头集合的连通性.问题3.由EADEEG分簇算法产生的簇头数量下界由于同样的原因也必须重新估算.2bpec分布式分簇算法描述本文提出了一种以邻居节点的平均剩余能量与节点本身的剩余能量比值为主要参数、以节点的“度”作为节点竞争簇头的辅助参数的分布式分簇算法(AdistributedalgorithmoftheclusteringtechniqueBasedontheParametersusedforElectingCHs),简称为BPEC分布式分簇算法.BPEC分簇算法基本解决了EADEEG算法存在的问题.在描述BPEC分簇算法之前,本文定义传感器节点的状态呈现候选态、簇头节点态和簇成员态3种,分别用“白球”、“黑球”和“灰球”表示.表1列出了为BPEC设计的所有报文格式及其描述:另外,假定传感器网络中各节点各自将节点的局部数据信息保存在数据结构NLI中,其数据结构形式说明如下:intID;/*全网唯一的整数值标识*/floatEr;*节点剩余能量值*intd;/*邻居节点个数,也称为度*/charstate;/*黑球表示簇头,灰球表示簇成员,初始均为白球*/}NODEDATA;intparent;/*指示器指示其所属簇头*}NLI;/将节点的邻居相关信息保存在NT中.其数据结构形式说明如下:intID;/*全网唯一的整数值标识*/charstate;/*簇头或簇内成员状态*/NeighborhoodTableNT;对BPEC分布式分簇算法描述如下:首先,每轮分簇开始时,进入邻居信息获取时段(neighbordiscoveryphase),事先规定持续时间长度为TND;然后进入其核心阶段,即簇头确定时段(headdecisionphase),事先规定持续时间长度为THD;最后进入节点归属时段(nodeattachmentphase),用于非簇头节点决定其归属于哪个簇的时段,事先规定持续时间长度为TNA.网络中的每个节点先进行时间同步,再同时启动算法完成下列步骤.第1步:节点以通信半径rC广播SensorMsg报文,该报文包含该节点的ID号、节点的剩余能量值Er.然后,节点接收所有邻居节点广播的SensorMsg报文内容,计算并更新节点本地信息数据结构NLI中的平均剩余能量Ea和节点的“度”d的值.不妨任取某一节点vi,vj为其邻居,则先计算Ea值:,这里,用Er表示节点j的剩余能量.再对节点按下列式(1)计算该节点可能有资格发送簇头申明消息HeadMsg的时刻t:情形1.当节点满足条件:Er>Ea时,有:情形2.当节点满足条件:Er≤Ea时,有:这里,式(2)中的E是节点的初始能量,ρ是一个均匀分布在[0.9,1]之间的一个随机实数,其作用是减小两个节点可能取相同t值的概率.下面证明的定理给出了结论:.说明BPEC分簇算法用于网络簇头的竞争阶段共用了THD时间,其中前半段时间(从0持续到THD2)确定大部分簇头,而THD的后半段时间(从THD2持续到THD)则在第1批簇头没能覆盖的区域节点中,按节点的剩余能量与该节点初始能量之比值为大者,选择作为剩下的少量簇头.第2步:TND超时后本轮进入簇头竞争时段,持续THD时间(从0持续到THD).BPEC算法这样来产生簇头:节点如果在时刻t到达时,还没有收到任何邻居节点发出的HeadMsg报文,则该节点向邻居节点广播HeadMsg报文,申明自己是簇头;否则该节点立刻放弃簇头竞争,而成为非簇头节点角色.节点一旦确定了自己的角色,就修改节点本地信息数据结构NLI的State栏,如果是簇头,则由白球“White”变为黑球“Black”;如果是非簇头节点,则由白球“White”变为灰球“Gray”.第3步:簇头确定阶段后,本轮进入节点归属时段,持续TNA时间.对非簇头节点而言,可能已经收到几个来自不同簇头节点的HeadMsg报文,该节点通过查找自己的邻居表NT,向剩余能量最多的簇头发送JoinMsg报文,申请加入该簇,其中state栏为“Gray”的节点还需进一步更新parent栏,使该指示器的取值指向所属簇头的ID.而对簇头节点来说,接收来自其所有簇内成员节点的JoinMsg报文,并且将不属于本簇的节点在自己的邻居表NT中删除,同时更新节点的本地信息NLI的d值.至此,分簇过程完毕.BPEC分簇算法具有如下特点:1)BPEC分簇算法是一个完全分布式的并行算法,扩充性好,更适合于大规模的无线传感器网络.2)BPEC分簇算法利用,在前THD/2时间内并行产生了大部分簇头,作为节点竞争簇头的主要参数因子Ea/Er,保证了剩余能量“相对”比较突出的节点充当簇头,而不是简单地选择节点的剩余能量“绝对”最大者作为簇头,这样做的结果是若干“轮”后,各节点均衡地消耗能量,从而延长整个网络的寿命.3)作为节点竞争簇头的另一个参数因子1/(d+1),由于节点随机均匀播撒在检测区域,所以区域内部每个节点的“度”d的值接近,该参数对t的影响不大,但是对于一些位于监测边界的节点,由于这些节点的度明显趋小,势必增大了t的值,从而避免了位于边界的节点成为簇头.4)对一些暂时未能覆盖的“缝隙”区域,利用公式在后THD/2时间内并行产生了剩余的簇头.由于“缝隙”区域包含的节点较少,所以,作为节点竞争簇头的参数因子Er/E,客观上拒绝了低能量的节点成为簇头.3bec分簇算法的原理WSNs网络拓扑可利用无向连通图G(V,E)来描述,其中V表示传感器节点的集合,E表示两个节点间的双向链路集,链路距离为节点的通信半径rc.定义1.如果一个集合V的子集合S可以连通集合V内所有节点,即u∈V,v∈S,du,v≤rc,式中du,v表示节点u和节点v的距离,rc表示通信半径,则称子集合S“覆盖”了集合V.定义2.无向连通图G(V,E)中任一个节点v的邻居节点集合为N(v),N(v)={udu,v≤rc,u∈V}.定义3.在无向连通图G(V,E)中取一个节点集合S⊆V,如果u∈S,v∈S,有(u,v)E,则称S是一个独立集.定义4.在无向图G(V,E)中存在一个独立集S,如果添加任意一个节点u∈V-S到S中,都会使S不再是一个独立集,则称S是图G(V,E)的最大独立集(maximumindependentset).定义5.支配集(dominatingset)是指可以覆盖无向图全网节点的节点集合,它是V的子集.无向图G(V,E)的支配集S有以下性质:v∈V,N(v)∩S≠,即网内任意一个节点要么本身属于支配集,要么该节点至少有一个邻居节点属于支配集.显然,本文对无线传感器网络分簇的过程实际上就是对无向连通图G(V,E)构造支配集的过程,支配集中的节点就是本文要找的簇头节点,如果支配集中的节点是连通的,则构造的支配集就是连通支配集.下面证明上述BPEC算法产生的簇头节点集合构成了支配集.定理1.按式(1)(2)计算节点发送簇头申明消息的时刻,满足不等式:.证明.已知节点的初始能量E>0,节点的剩余能量Er≥0,节点邻居的平均剩余能量Ea≥0,节点的“度”d是大于等于1的正整数.当节点满足条件Er>Ea时,有,这时,Er>Ea,有,所以,当节点满足条件Er≤Ea时,有并且,,所以,不等式成立.类似于文献引理1的证明方法可以得到结论,由BPEC分簇算法产生的任意一个簇内有且只有一个簇头.定理2.由BPEC分簇算法产生的簇头节点集合C是无线传感器网络G(V,E)的最大独立集.证明.首先证明C是独立集.反证法:假设C不是独立集,即在C中存在两个簇头节点u和v,满足(u,v)∈E,亦满足du,v≤rc,但由BPEC算法可知,必有u或v之一属于簇成员节点,与假设矛盾.故由簇头组成的集合C必为独立集.因为在无线传感器网络G(V,E)中的节点运行BPEC算法后,所有节点要么属于簇头集合C,要么属于某簇的成员节点,所以V中的节点均为成员节点,取其中任一节点加入C中都会破坏C的独立集性质,所以,C为最大独立集.引理1.最大独立集S同时也是无向图G(V,E)的支配集,即对于任意一个节点v∈V,N(v)∩S≠,表示空集.证明.显然,添加任意一个节点vS都会破坏S的独立性质,则v必然有一个邻节点在S中,因此,最大独立集S是图G(V,E)的支配集.定理3.由BPEC分簇算法产生的簇头节点集合C是无线传感器网络G(V,E)的支配集.证明.由引理1直接得证.另外由图论理论可以得到结论,对于图G(V,E)内任意一个节点v和图G(V,E)的最大独立集S,与v相邻的,属于S中的节点数小于6个,即N(v)∩S<6.就节点的通信半径rc来说,上述定理2、定理3说明:1)由BPEC分簇算法产生的簇头节点集合C覆盖了网络所有的节点;2)由BPEC分簇算法产生的集合C中的任意两个簇头节点在通信半径rc内都不连通;3)由BPEC分簇算法产生的每一个簇头支配一个簇,所有非簇头节点属于并且仅属于一个簇内;4)BPEC分簇算法的节点归属阶段,每个非簇头节点收到的HeadMsg报文不会超过6个,与节点总数无关.定理4.如果‖A‖为网络监测区域的面积,由BPEC分簇算法产生的簇头集合为C,则集合C的簇头数量有明确的上下界,上界为,下界为,期望值为.证明.如图2所示,簇头A的6个邻居簇头节点(B,C,D,E,F,G)构成一个正六边形,任意两个节点间的距离为rc+ε,其中,ε是一个很小的值.当任意两簇头之间的距离不大于通信半径rc时,簇头A将被其6个邻居节点所覆盖.图2(a)表示了簇头数量最多的情况.簇头A所代表的簇是一个边长为的正六边形,其簇面积为,故整个网络中最密集的簇覆盖集的簇头数量为.如图2(b)所示,簇头A的6个邻居簇头节点构成一个正六边形.任意两个簇头节点间的最远距离为,当任意两簇头间距离大于时,将会有区域不能被撒布的节点通信覆盖,这与已知矛盾.图2(b)表示了相邻簇间重叠面积最小的情况,簇头A代表的簇是一个边长为rc的正六边形,将其各边向外扩张rc/2距离,则得到一个边长为,其面积等于的正六边形,它包含了簇头A代表的边长为rc的正六边形,故整个无线传感器网络中,最稀疏的簇覆盖集合的簇头数量为.因此,对于任意一个簇Ci,其实际簇面积满足,考虑到节点的均匀分布,因此整个网络中实际簇头数量的期望值为.定理5.在BPEC分簇算法中,整个网络的广播消息量复杂度为O(n).证明.在BPEC分簇算法中,每一轮(round)开始阶段所有节点都会发送一条SensorMsg控制报文,消息量为n;在每一轮的簇头选择阶段,对于簇头节点需要发送1条HeadMsg簇头申明消息,在每一轮的节点归属时段,对于成员节点都需要发送1条JoinMsg消息用于加入簇,两者相加,消息量也为n.则BPEC分簇算法整个广播消息量为2×n,所以,整个网络的广播消息量复杂度为O(n).定理6.在BPEC分簇算法中,整个网络的时间复杂度为O(1).证明.在BPEC分簇算法中,由于采用分布式并行算法,网络的时间复杂度就是单个节点的时间复杂度,而BPEC分簇算法单个节点的时间复杂度为常数,与网络的规模n无关,所以,整个网络的时间复杂度为O(1).另外由图论的基本性质可得到引理2的证明.引理2.对无向连通图G(V,E)的最大独立集S而言,如果S内的节点数不小于2,则S内的任意一个节点v三跳之内必存在至少一个最大独立集节点,即N3(v)∩S≠.定理7.由BPEC分簇算法产生的簇头节点集合C是无线传感器网络G(V,E)的一个最大独立集,则C内的任意一个簇头节点v三跳之内必存在至少一个最大独立集节点,即N3(v)∩S≠.证明.由引理2得知,C内的任意一个簇头节点v三跳之内必存在至少一个最大独立集节点.因此,节点v三跳之内必然存在一个最大独立集节点u,其可能的连接形式如图3所示:定理7的结论作为本文构造无线传感器网络连通支配集的理论基础.因此,由BPEC分簇算法产生的簇头集合是一个支配集,只要将无线射频信号通信半径rc调节到原来的3倍,不妨设新的通信半径为Rc,这里Rc=3×rc就可保证簇头集合为连通支配集合.这是将簇头节点不借助其他辅助节点构成汇集树的基础.值得一提的是,Zhang等人首先对节点的覆盖与连通之间的关系进行了分析,并证明了如果节点的通信半径大于两倍节点的感知半径,则节点对整个凸区域的全覆盖就保证了所有节点的连通性.这一结论并不能应用到BPEC产生的簇头集的连通性.因为尽管网络所有的节点保证了对凸区域的全感应覆盖,但由BPEC分簇算法产生的簇头集中的所有簇头节点并不能保证对整个凸区域的全覆盖.另外,本文讨论的连通支配集问题是一个典型的点覆盖问题,它要求连通支配集(簇头集合)覆盖所有的簇头节点,而不是感知覆盖整个区域.4实验结果分析下面主要仿真分析BPEC和EADEEG分簇算法产生簇头的实验值和理论分析值的关系.假定n个传感器节点随机均匀分布于一个边长为a的正方形监测区域A内,每个节点的通信半径定为rcm.根据定理4,BPEC分簇算法期望产生的簇头数目为实验时分为高密度(500个节点播撒在边长为a=100m的正方形检测区域)和低密度(100个节点播撒在边长为a=100m的正方形检测区域)两个实验场景.以下的实验结果(如图4所示)均为100次独