无线传感器网络分簇算法研究

无线传感器网络分簇算法研究

目前，基于微电池传感器技术的创新和低效率r的设计成功，我们可以开发出经济、低效率的无线传感器。大量传感器使用联合通信来完成大规模的传感器通信任务。然而，众所周知，传感器网络的边界是资源有限的，包括内存、算术算法、通信带宽和功率。分层结构的无线传感器网络目前大多采用2层结构,利用簇的概念来对网络进行分层.对无线传感器网络分簇,一个重要的作用是可以将网络的感知的数据进行融合后再进行传输,减少由于传输产生的能量开销,便于对簇内节点统一管理,有利于对网络进行扩展.在分簇的无线传感器网络中,存在簇头和簇内成员.簇头作为簇的中心点负责簇结构的稳定和重组,通过簇头组成骨干网,可以实现跨簇通信.本文在通过引入Adhoc网络中节点度的概念,结合节点剩余能量,最后建立簇头选择模型,实现无线传感器网络的分簇.本文组织结构如下:第一节建立簇头选择模型;第二节理论分析和性能仿真;第三节总结.1规模过大的情况下多时要注意聚合群数的约束簇头选择模型根据每个节点的权值来选择簇头,权值较小的节点优先成为簇头.节点的权值综合考虑了节点度和节点剩余能量.为了平衡整个网络的能量消耗,减少簇头的持续能量消耗,还为原有簇头引入了一定的增量增大其权值,使其再次被选举为簇头的可能性减小.节点权值的计算公式为:W(n)={a×|d(n)-m|+b×lg[(Τ(n)+0.01)(Τthr+0.01)〗+c×Δ}×(E0-ErE0)(1)W(n)={a×|d(n)−m|+b×lg[(T(n)+0.01)(Tthr+0.01)〗+c×Δ}×(E0−ErE0)(1)式中:d(n)表示节点n的节点度,节点度定义为一个节点的相邻节点数,拥有最高节点度的节点被选择为簇头,可以将网络划分为较小的簇,从而减少数据分组的延迟;m表示每个簇内理想的簇成员数.一方面,由于能力的限制,簇头无法负担过多的簇成员,即使这些簇成员都在它的传输范围内.簇的尺寸太大会使簇头的开销过大,并降低信道的空间重用率;另一方面,簇的尺寸太小又会在网络中形成过多的簇从而使建立和维护有效的簇结构变得很困难,并增加分组的延迟.因此应选择簇的尺寸是否合理,是一个分簇算法必须考虑到的因素.在其他文献中还有关于簇规模过大过小的情况下如何对簇进行约束.簇规模的大小可以用簇头的节点数来衡量,即簇头数越多,簇规模越小;簇头数越少,簇规模越大.理想的簇头数情况如下:设整个网络可以被分为h个簇,为保证全网中流量平衡,将骨干网流量带宽B2平均分配给每个簇,使得B2=B1×h,所有子网共享骨干网中的流量,以适应每个子网能同时进行通信的情况.在无线网络中,对于随机分布的n个相同的节点,每个节点在一个固定的范围内其传输能力为Wbit/s,则每个节点到随机选取的目的节点的传输流量λ(n)=Θ(W√nlgn)bit/sλ(n)=Θ(Wnlgn√)bit/s.进一步指出如果节点所处区域为单位圆,传输模式、传输范围最优的情况下传输流量可以用下式表示:λ=Θ(W√n)(2)λ=Θ(Wn√)(2)根据式(2),簇内节点的传输流量总和λc由下式表示:λc=Θ[B1√n/hλc=Θ[B1n/h√bit/s(3)簇头节点的流量λb由下式表示:λb=Θ[B2√hλb=Θ[B2h√bit/s(4)理想的情况下有λc=λbhλc=λbh,则根据式(2)和式(3)得到[B1√n/h=1h[B2h〗(5)由此得到分簇数h:h=√B2B1√n(6)因此,理想情况下簇内的簇成员数:m=nh=n√B2B1√n=√B1B2n3/4(7)T(n)表示节点n担当簇头的时间.簇头会比簇成员消耗更多的能量,节点担当簇头的时间越长,消耗的电池能量也就越多.为了避免已经消耗了过多能量的节点再次被选为簇头,从而导致其过早地耗尽能量,规定一个时间门限值Tthr,当某节点担当簇头的时间超过了Tthr时,该节点被选为簇头的可能性就迅速下降,这里用对数函数来实现.其中加0.01是为了避免对数函数的自变量为0;Δ表示一个增量.如果在上一次选举时,节点n被选为簇头,则在本次选举时,为其权值附加这个增量.若在上次选举中节点n为簇成员,则权值的计算公式中不包含这个增量.a,b,c表示权重系数,其值都为正数,且满足a+b+c=1.根据不同系统的特殊需要,可以为这几个变量选择不同的值,从而改变不同因素在簇头选取中的作用大小,使该分簇算法适用于不同类型的网络.假设E0为节点的初始能量,Er为节点的剩余能量.从式(1)中,我们可以看出当节点的能量耗尽时,节点的剩余能量接近于0,即ErE0≈0,这将导致节点被选为簇头的概率几乎为0.权值小于所有邻节点的节点被选为簇头,当权值相等时,选择ID较小的节点成为簇头.簇头的邻节点成为其簇成员,并不再参与簇头的选举过程.若一个节点的所有邻节点中比它权值小的节点都已经成为了其他簇头的簇成员,则该节点也成为簇头;因此拥有权值W(n)小的节点被选为簇头,从而可以构成簇头集,以表示{Ci},i=1,2,…,h.{Ci}中的每一个点代表一个簇头.簇生成的过程是使用簇头集{Ci}中的每一个点为簇头,且簇头节点Ci作为根节点广播“Cluster-Init”信息,其信息采用广播方式传播.算法通过建立簇成员数据库,从而生成簇.以簇的生成为例,描述如下:(1)参数和变量的初始化intv,u,w,n;BooleanVisited[];//节点被访问标志数组intClusterSet[Q];//簇选择模型for(u=0;u<Gvexnum;++u)Visited[u]=FALSE;//访问标志初始化;InitClusterSet(ClusterSet[Q]);//簇选择模型数据库初始化;(2)i簇生成(图1)以上为簇生成算法对于簇中的任意节点vij,i为簇标,其取值范围是从1到h,j为第i簇中节点标号,取值范围是从1到x,并且每个簇中节点的数目不同.最终有:h∑i=1x∑j=1vij=n(8)2性能分析2.1层次树生成的复杂度信息复杂度是为了生成簇,在节点之间传输和存储的信息量.该分簇算法的信息复杂度为O(n5/4).证明如下:m=nh=√B1B2n3/4(9)由于算法在本质上是发现和生成L层的D-维层次树(树深L<∞),所以最终生成的是深度为L且与随机标记相关的D-维平衡树的链路集合.根据文献的计算结果,为生成层次树,每个节点产生的数据量与L×n1/L相关,用ω′=λL×n1/L表示,其中n为网络节点数,λ为系数.一个簇中交换的信息量为簇平均节点数m与每个节点数据量ω′的乘积.由下式表示:m×ω′=√B1B2n3/4×λL×n1/L×ρ(10)式(10)中ρ为常量数据单位,在本文中L=2,所以可得到:2ρλ√B1B2n5/4(11)由此,我们得出其复杂度为O(n5/4).证毕2.2节点传输范围不同下面我们利用仿真工具NS2来对该分簇算法进行分析.对于无线传感器网络而言,目前并没有统一的评测标准.为了更好的分析出该分簇算法的性能,我们选择使用以下参数:①簇数和簇中平均节点数.②簇头转移次数:簇头转移次数可以衡量簇头更换频率的快慢.仿真中所用的网络参数如表1所示:图1给出了网络中节点数分别为50,100和150这三种情况下的仿真场景图.其中节点是随机撒播在固定区域中的.图2给出了两种不同簇算法平均簇数随节点传输范围的变化情况.假设B2B1=10,在网络节点数n为50的时候,由式(6)得出理想的簇数为8,从图2中可以看出,相应的节点传输距离为35m.同理,网络节点数n为100的时候,理想的簇数为10;网络节点数n为150的时候,理想的簇数为11.单个簇内所包含的节点数较多,可以产生较少的簇,从而降低分组投递的延迟,还可以简化簇结构的管理.但是较少的簇数也会降低信道的空间重用率,同时单个簇内的节点数过多也会使簇头负担加重.根据以上模拟计算的结果显示,网络参数节点数n、无线传输带宽B2B1和节点传输范围之间的关系决定了网络性能,需要在它们之间进行平衡,以得到最佳的网络的性能.当节点的传输范围较小时,簇成员与簇头的距离很近,不容易离开原簇,因此单位时间内簇头更新次数较低.从图3中可以看出,随着节点传输范围的增大,单位时间内簇头更新次数逐渐增加达到峰值.传输范围的进一步增大反而使单位时间内的簇头更新次数降低,这是因为簇头的传输范围较大,节点不容易移出原来簇头的覆盖