无线传感器网络分簇拓扑控制算法*

龙昭华， 陈丹丹， 蒋贵全

(重庆邮电大学 计算机科学与技术学院，重庆 400065)

0 引 言

1 HEED与EEUC拓扑控制算法

HEED[5](hybrid energy-efficient distributed)算法是一种使用固定簇半径的分簇协议[6]，该协议中给出了无线传感器网络中的3个最重要的需求：延长生命周期、可扩展性和负载均衡，并通过将能量消耗均匀分布到整个网络中来达到延长网络生命周期的目的。HEED协议中簇首选举主要依据主、次2个参数。主参数依赖于剩余能量，用于随机选取初始簇首节点集合，拥有较多剩余能量的节点将有较大的概率暂时成为簇首节点，而最终该节点能否成为簇首取决于剩余能量是否比周期内其他节点的能量多，即迭代过程是否比周围节点收敛的快。次参数依赖于簇内通信代价，用来确定落在多个簇范围内的节点最终选择哪个簇首加入，以及平衡簇首之间的负载[7]。

EEUC[8]算法是一种基于非均匀分簇的无线传感器网络路由协议，它采用多跳通信方式防止离基站远的簇首节点过早死亡，并且以主动方式均衡节点能耗[9]，该协议会预先设置一个是否成为候选簇首的阈值T，普通节点根据此阈值决定自身是否成为候选簇首。未参与竞选的节点则进入休眠模式，直到簇首竞选过程结束。令Si为任意的一个候选簇首节点，Si根据自身到基站的距离信息来计算其自身竞争区域的大小，区域半径记为Ri。候选簇首节点之间按照规则1进行竞争簇首。

规则1：在竞选簇首节点过程中，如果候选簇首Si宣告其竞选成功，那么，在其竞争半径Ri之内的所有候选簇首节点需退出竞选过程。

2 双簇首能量均衡算法

通过对经典的分簇算法进行研究与分析，尽量避免其不足之处，提出了一种基于双簇首能量均衡(DCHEB)的无线传感器网络分簇拓扑控制算法，本算法引进了双簇首的思想，每个簇有主簇首节点(MCH)和副簇首节点(VCH)。主簇首负责簇内的数据采集，副簇首节点负责簇间的数据传输。这样一来就使得原来单个簇首节点的簇内数据采集和簇间数据传输的2个任务分给现在的主副簇首节点去完成，这大大降低了簇首的能量消耗，可以达到延缓簇的重组的目的。

2.1 基本思想

1)在网络初始化的时候建立一个圆形的网络，基站位于其中心[10]；然后以基站为中心按照本文算法提供的方案进行层次的划分并计算出每层的簇的个数和层间距，传感器节点均匀地分布在整个网络中，节点根据自身的坐标、剩余能量以及所在的层次来确定该层的主副簇首节点。这样可以确保每个簇的节点个数相对平均，主簇首节点位于合适的位置上，从而可以在一定程度上均衡簇内和簇间的能量消耗，进而可以延长整个网络的生命周期。

2) 进行主副簇首节点选举时，首先基站广播簇首选择消息，各节点会把自身的相关信息(坐标、剩余能量)发送给基站，基站根据节点的信息和已划分好的层次通过集中式的策略来进行主副簇首节点的选举[11]。通过这种方式可以使主簇首节点位于较为合适的位置上，从而达到簇内的各节点的能量消耗相对均衡。

2.2 DCHEB算法通信模型简介

设r为传感器节点单跳通信的最大距离，本文采用的通信模型分2种情况：当传输距离小于r时，发送节点的能耗与传输距离的平方呈正比；大于r时，则与传输距离的四次方呈正比。这2种情况分别为：自由空间传输模型和多路衰减模型。所以，根据传输距离的大小，发送节点传输kbit的信息所消耗的发送能量如式(1)[12]所示，接收kbit的信息所消耗的能量由式(2)所示

由表2可以看出，该数据为平衡面板数据，截面数为31，跨期为11，属于短面板。被解释变量中，人均教育支出均等化指数均值为0.972，人均医疗卫生和人均社会保障与就业均等化指数均值都为0.999，接近于1，说明教育、医疗卫生和社会保障与就业基本公共服务均等化供给程度相对较高。

(1)

ERx(k)=Eelec·k,

(2)

式中Eelec为射频电路和接收电路每发送或接收单位数据所消耗的能量，J/bit；εfs为自由空间传输参数，εamp为多路衰减传输参数，它们的单位是J/(bit·m2)。

r为一个门限距离，亦即接收电路和发送电路之间距离的临界值，当两者间的距离小于r时，使用自由空间模型；当两者间的距离大于r时，使用多路径衰减模型。本文的通信模型将统一采用自由空间模型，假定每个簇首的节点通信范围都能包含所划分好的簇，使得网络中的每个节点都至少有一个簇加入。

2.3 簇的划分方案

本文提出了一种新的簇的划分方案，此方案有利于使得主副簇首节点位于合适的位置，而且使得每个簇的节点个数相对平均，这样会使得簇间和簇内的节点的能量消耗相对均匀和延长边缘节点的死亡时间，可以有助于延长网络的生存周期。

1)算出网络中的最佳簇首个数，计算公式如下

(3)

2)将网络区域平均分为K个簇域，簇域采用扇形区域，第n层簇的个数设为Pn，如图1所示，可以得到下面等式

(4)

图1 层间距Rn与层簇数Pn示意图

式中S为传感器网络区域面积；K为最优簇首数目；Pn为第n层簇的数目；Ri为第i层的间距。

综上,可以得出Rn的解为

(5)

2.4 主副簇首的选举

在对簇首节点选举策略的选择时，则应考虑以下几个方面：

1)簇首选举策略应该尽量采取分布式的方案[13],网络中的各个节点都可以根据本地地信息进行自主选择簇首节点，并且簇首节点的选举算法应该尽量简单，以节约能量消耗。

2)尽量使被选择担当簇首的节点均匀地分布在整个网络中，并且可以监测整个网络的运行情况。

3)网络中被选举出担当簇首的节点数目应该尽可能接近于最佳簇首个数。

4)簇首选举过程中应使能量消耗尽可能的少。

主副簇首选举的流程如图2所示。

图2 主副簇首节点选举流程图

通过此阶段的选举，可以确保被选举成为簇首节点的节点比较均匀地分布在整个网络中，并且能够监测整个网络的运行情况。在此阶段之后，被选举出的主簇首节点会发送广播消息来组建自己的簇。簇一旦建立完成后，这种簇结构就不会再发生改变。当簇首发生异常，不再适合继续担当簇首节点时(包括主、副簇首节点)，不需要再通过基站在全网中进行选举了，而是在自己所在簇的周围(也包括簇内)，即在小范围内按照一定的方式选举出新任的簇首节点，亦即网络运行阶段中的簇首选举[14]。

3 仿 真

本文设置的仿真环境：以基站为中心，坐标为原点(0，0)m，把300个传感器节点均匀分布到半径为200 m的圆形感知区域的4个象限中。

在上面仿真环境中全部的普通节点负责收集信息，并且按照固定的周期进行数据传输，每个数据包均设置为2 000 bit，全部节点的原始能量都设置为0.5 J。其他参数设置为εelec=50 nJ/bit，εfs=10 pJ/bit/m2，εmp=0.001 3 pJ/bit/m4。

3.1 网络生存时间对比

HEED协议在接近20 s的时候网络中的全部节点死亡，EEUC协议在接近100 s的时候网络中的全部节点死亡，而DCHEB在接近160 s的时候网络中的全部节点才会死亡,如图3。

图3 网络的生存时间对比图

3.2 网络能耗的对比

HEED协议在接近20 s的时候整个网络的能量消耗完，EEUC协议在接近100 s的时候整个网络的能量消耗完，而DCHEB协议在将近160 s的时候整个网络的能量才消耗完，如图4。

图4 网络的能量消耗对比图

本节采用Matlab仿真工具对HEED,EEUC和DCHEB 3种算法，分别从整个网络的生存时间、整个网络的能量消耗2个方面进行仿真分析。分析表明:DCHEB协议的性能总体上要优越于HEED,EEUC。

4 结束语

本文引入了双簇首的思想，由于每个簇内有主副簇首2个簇首节点，则可以使簇首节点的数据采集和转发数据2项工作平均分配到主副簇首节点上去，从而使主副簇首节点的能量消耗要比一个簇首节点时慢很多，从而可以延缓簇首重构的时间，减少簇首重构的次数，达到节约网络

能量，延长网络的生存时间的作用。但是DCHEB算法仍然存在一些不足之处，比如：会导致距离基站较近的节点也会因为要转发相对较多的数据量而消耗大量的能量，导致整个网络中能量消耗不均匀，出现比距离基站较远节点提前死亡的情况，这也是以后研究中需要考虑的主要方面之一。

参考文献:

[1] Xie X,Zhang H.Topology algorithm research based on energy and power control for topdisc algorithm[C]∥Second International Conference on Computer Modeling and Simulation,2010:37-40.

[2] Shirali M,Meybodi M R,Tarigh H D.Topology control scheduling:Based on the distributed learning automata[C]∥2010 IEEE 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM),2010:1-4.

[3] Hu X,Ren D R,Wang H,et al.Adaptive clustering algorithm based on energy restriction[C]∥2011 IEEE International Conference on Intelligent Computation Technology and Automation(ICICTA),2011:949-951.

[4] 胡 静，沈连丰.基于博弈论的无线传感器网络分簇路由协议[J].东南大学学报:自然科学版,2010,40(3):441-445.

[5] Younis Ossama,Fahmy Sonia.HEED,A hybrid,energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):336-379.

[6] 崔 英.无线传感器网络分簇路由协议的研究与实现[D].北京：北京交通大学,2012.

[7] 吕 涛，朱清新，朱玉玉.一种能耗均衡的无线传感器网络分簇算法[J].计算机应用,2012,32(11):3107-3111.

[8] 李成法，陈贵海，吴 杰.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报，2007,30(1):27-35.

[9] 柴宝杰,马宝英,范书平,等.无线传感器网络中改进的 EEUC 路由算法[J].微计算机信息,2012(9):149.

[10] 戴世瑾，李乐民.高能量有效的基于分簇的无线传感器网络路由协议倡[J].计算机应用研究,2010,27(6):2201-2203.

[11] 杨 军，张德运，张云翼，等.基于分簇的无线传感器网络数据汇聚传送协议[J].软件学报,2010,21(5):1127-1137.

[12] 徐小良，裘君娜.异构传感器网络中一种能量有效的簇头选择算法[J].传感技术学报,2009，22(3):395-400.

[13] 何永刚，徐汀荣，彭 俊.无线传感器网络分簇方法的优化[J].计算机工程与应用，2011,47(1):92-95.

[14] 唐一梅，李志军，胡 江，等.一种低能耗层次型传感器网络拓扑控制算法[J].自动化学报，2010,36(4):543-549.