基于时间驱动簇头选择非均匀分簇路由算法✴

柳 平,石中华,吕金风

(汕头大学电子工程系,广东汕头 515063)

随着传感技术、嵌入式技术以及低功耗无线通信技术的发展,生产具备感应、无线通信以及信息处理能力的微型无线传感器已成为可能.这些传感器节点之间通过相互协作,将其监测和感应的多种环境信息(如温度和湿度等)传送到基站进行处理,无线传感器网络广泛应用在国防军事、救急和环境监测等领域[1,2].

与无线移动自组网不同,无线传感器网络一般具有较大的节点密度且没有IP地址,同时由于受到成本和体积等原因限制,无线传感器节点的处理能力低和无线带宽以及电池容量等资源匮乏.在大多数应用中,传感器节点被部署后就无法对其充电,这使得如何提高网络生存时间成为无线传感器网络研究主要方向之一.

1 相关研究

无线传感器网络的主要任务是把传感器节点收集数据发送到基站,这是节点消耗能量主要部分.在文献[3]中,提出了直接传送即网络中的每个节点把收集到数据直接传送到基站,这种方法简单,然而,对于远离基站的节点,将消耗更多能量,很快就死亡.在文献[4]中定义网络生存时间是网络中第一个节点死亡的时间,所以均衡节点能量消耗尤其重要.Heinzelman等人提出 LEACH分簇协议[5],每个簇包含一个簇头和多个簇成员节点,簇头周期轮换,将整个网络的能量负载平均分配给每个节点,延长网络生存周期.Younis等提出了一种混合式的分簇协议HEED[6],算法首先根据剩余能量来概率性选择一些候选簇头,然后以簇内通信代价的高低来竞争产生簇头.但需要在簇内进行多次消息迭代,由此带来的通信开销比较显著.文献[7]提出了EECS分簇协议,节点在选择簇头时不是简单地选择距离自身最近的簇头,而是考虑候选簇头到基站的距离,这样使得靠近基站的簇头将有更多的簇成员节点,远离基站的簇头有比较少的簇成员节点,有利于均衡簇头间负载.

上述介绍路由协议属于簇头单跳传送数据协议,对于大型网络,簇头离基站较远,通过单跳将消耗更多能量.文献[8]指出,采用簇头组成的骨干网实现多跳路由的方式更有利于节约能量,然而这种做法带来了能量消耗不均衡的问题:靠近基站的簇头由于转发大量来自其它簇头的数据而负担过重,过早耗尽自身能量而死亡,造成网络分割降低网络存活时间,研究者称这个问题为“热区”问题[9].Soro等人首次在文献[10]提出利用非均匀分簇的思想解决这个“热区”问题,假设网络拓扑环绕基站的两层同心圆环,内环簇头靠近基站,需要承担数据转发任务,通过减少的簇成员数量降低簇内处理中消耗的能量,为簇头间数据转发保留能量.但是他们考虑是一个异构网络,簇头的分布是事先设计好的,不适合随机部署的网络.李成发等人在文献[11]和[12]中提出了EEUC算法以及文献[13]提出了MRPUC算法,它们是一种基于竞争的多跳非均匀分簇算法,仿真结果显示了较好的结果.但此算法在簇头选举时存在以下不足:①很多能量较少的节点被激活参与竞选却不能获胜,浪费能量;②随机激活无法保证获胜节点最优;③每个竞选节点都会发送和接收竞争广播等消息并进行计算,网络开销大.

为了很好解决EEUC算法在簇头选举时存在的不足,本文提出一种基于时间驱动簇头选择非均匀分簇路由算法,该算法直接通过节点广播成为簇头消息产生簇头,广播时间与其剩余能量成反比,减少了由竞争产生簇头带来的能量消耗,保证了选出簇头有较高剩余能量且每轮产生簇头数目波动小.

2 网络模型

研究的网络分布在一正方形区域内,由个随机分布的传感器节点组成,其应用场景是网络周期性的数据收集,并且该传感器网络具有如下性质:①传感器节点部署后不再移动,基站部署在区域外的一个固定位置.②所有节点具有相似的数据处理、通信等功能,并且地位平等,都有一个唯一的标识(ID).③根据接收者的距离远近,节点可以自动调节其发射功率.④链路是对称的,若已知对方发射功率,节点根据接收的信号强度计算出发送者离自身的距离[11].

本文与文献[4]使用相同的无线通信能量消耗模型,该模型给出一个阈值do,当发送节点与接收节点距离小于时do,发送节点发送数据的能量损耗与距离的平方成正比,否则与距离的4次方成正比.上述两种能量衰减模型分别称为自由空间模型(free space)和多路衰减模型(multipath fading).例如节点a向节点b发送k比特数据,两者相距距离为d,节点a发送数据能量消耗由发射电路损耗和功率放大损耗两部分组成,即

而b接收a数据能量消耗为

式中:Eelec表示无线收发电路所消耗的能量;εfs和 εmp分别为这两种模型中功率放大所需的能量.

本文采用了数据融合技术减少发送和接收的数据量,用 EDF表示融合单位比特数据消耗能量.假设邻近节点采集数据有较高的冗余度,簇头可以将其簇成员发送来的数据融合成一个长度固定的数据包,而簇与簇之间数据不发生融合.

3 本文路由算法

在网络建立阶段,基站需要用足够大的发送功率向全网络广播信息,消息包括其发送功率.网络中节点根据基站的发送功率计算出到基站的近似距离,利用此距离不仅可以调节向基站发送数据所需的发送功率,还可以用它计算其竞争半径.

该算法包括分簇和数据传输两个阶段,分簇又可以分为簇头选择和簇的形成两部分,数据传输也分为簇内数据传输和簇头间数据传输.为了使簇内信息进行交流,本文引入了簇内信息交流阶段,它们在每一轮中有对应时隙,如图1所示.

图1 每轮时隙图Fig.1 Time slot at each round

3.1 簇头选择

在无线传感器网络中,每轮进行簇头选择时,首先传感器节点根据剩余能量计算出其广播成为簇头消息CLUSTER_ HEAD_MSG 的时间,其表达式为

式中:T1为网络中簇头选择时间;Ei表示节点i剩余能量;Ea,Emin和Emax分别表示上一轮节点所在簇平均剩余能量、簇内节点最小剩余能量和最大剩余能量;ni∈(0,1)随机数,用于避让相同剩余能量节点广播消息引起的冲突.

在每轮簇头选择时,所有节点按照自身发送时间来广播CLUSTER_ HEAD_ MSG 消息.因此,剩余能量高的节点,先广播其消息,它的广播半径不是最大的竞争半径,而是自身的竞争半径,可以节省能量,如节点i竞争半径为

式中:dmax和dmin分别表示节点到基站距离的最大值和最小值;di为节点i到基站的距离;Rp为最大竞争半径;c∈(0,1)为调节参数.

当普通节点接收到CLUSTER HEAD_MSG 消息,此节点将不广播CLUSTER_ HEAD_ MSG消息并记录发送者的信息.簇头接收到CLUSTER_ HEAD MSG消息后,不做处理.经过时间T1后,网络中簇头全部选出.

3.2 簇的形成

簇头选择完成后,普通节点如果只接收到一个簇头发送来的CLUSTER HEAD MSG 消息,就选择该簇头.如果接收到多个簇头发送来的CLUSTER_ HEAD_ MSG 消息,就选择簇内通信代价最小亦即接收信号强度最大的簇头.普通节点选择自身簇头后,就发送加入消息JOIN_CLUSTER_ MAG 通知该簇头.簇头接收到该消息后,进行构建TDMA调度并将它发送给簇内所有节点,确保簇内所有节点发送数据没有碰撞,同时可以让节点除了自身发送时间外进行休眠,节省节点能量.

3.3 数据传输

簇头首先收集从簇内成员节点发送来数据,并进行数据融合,然后把数据发送给中继簇头或基站.中继簇头只是简单转发来自其它簇头的数据,而不能进行数据融合.

在簇间传输数据开始时,每个簇头以相同的功率向全网络广播一条消息NODESTATE_MSG ,包含ID、当前剩余能量和它到基站的距离.如果簇头i收到由簇头j广播的NODE_STATEMSG 消息,就可以计算出它们之间的近似距离dij.同时定义簇头的中继簇头集合RCH(i)为

如果RCH(i)为空集,则节点直接与基站通信.

由于采用的无线通信能量消耗模型,发送数据能量消耗与距离的平方或4次方成正比,由于采用了多跳传输,可以假设与距离的平方成正比.簇头i选择中继簇头从能量开销指标如式(6)和中继簇头剩余能量考虑,首先找到与簇头i最小能量开销Erelay两个簇头,然后从中选出剩余能量最大的簇头作为中继簇头.

为了减轻靠近基站边缘地区节点转发数据的负担,引入了一个阈值 TD_MAX ,若簇头到基站的距离小于TD_ MAX ,它就直接与基站进行通信,否则通过其它簇头转发把数据送到基站.

簇间传输数据结束后,进入簇内信息交流阶段,各簇簇内成员节点把自身剩余能量发送到簇头,簇头接收并计算出簇内平均剩余能量Ea、簇内节点最小剩余能量Emin和最大剩余能量Emax,然后向簇内广播一条包含Ea,Emin和Emax的消息 CLUSTER_ENERGY_MSG.

4 算法分析

本文算法是一个分布式动态算法,以节点剩余能量选择簇头,在每轮中,该算法簇头选择的消息复杂度为O(N).假设共选出了k个簇头,则它们就广播k条CLUSTER_HEADMSG 消息,而N-k个簇成员发送N-k条JOIN_CLUSTER_ MAG 消息.消息的开销为k+N-k=N,所以其复杂度为O(N).

该算法比EEUC算法消息开销小,且不需要设置文献[11]中普通节点成为候选簇头的概率阈值,它对于EEUC算法有很大影响,阈值过大,会增加消息的开销,阈值过小,使候选簇头过小,导致选出的簇头不是最优,同时本文算法广播消息不是以最大竞争半径广播,将节省节点能量.

本文算法中参数Rp和c取值对网络生存时间的影响与文献[11]一样,c的值越大,候选簇头的竞争半径差异越大,因此簇成员数目间的差异越明显.算法中所产生的簇的数目由Rp和c共同决定,固定Rp,当c增大时,每个簇头竞争半径随之减小,所生成的簇的数目将增加.固定c,当Rp增大时,每个簇头竞争半径随之增大,所生成簇的数目将减小.Rp和c优化取值可以优化网络中节点的能量消耗,延长网络存活时间.用理论化的方法选择最优参数值还要进一步研究.

5 仿真和分析

为了说明算法效果,对算法进行仿真测试,选择的仿真参数设置取自文献[11],如表1所示.

图2是LEACH、EEUC和本文算法网络生存时间的比较,从图中可以看出,本文算法的网络生存时间最长,EEUC次之,LEACH最差.从第一个节点死亡到最后死亡节点的时间跨度可以反映网络中节点能量均衡情况,跨度越短说明网络能量使用越高效,本文算法跨度最短,EEUC略差于本文算法,LEACH跨度很大.原因是本文算法采用时间驱动簇头选择,可以降低消息复杂度和节省节点能量.EEUC算法采用随机数和阈值机制产生候选簇头,再由候选簇头竞争产生簇头,这将消耗大量能量.LEACH算法随机产生簇头,没有考虑节点剩余能量,可能选出簇头能量低,这样会加速节点死亡.

表1 仿真参数Tab.1 Simulation parameters

图2 网络生存时间Fig.2 Network lifetime

图3 簇头数量对比Fig.3 The number of cluster head comparison

图3是3种算法生成簇头数量对比,从图中可以看出,EEUC和本文算法产生的簇头数量稳定,LEACH簇头数量的波动范围最大,这是因为LEACH单纯采用随机数与阈值的机制产生簇头,因此簇头数量变化比较明显.EEUC和本文算法簇头数量变化比较集中,这是因为2种算法均采用了局部区域竞争的方法,有效地控制了算法所生成的簇头数量.但是,本文算法产生的簇头数量更集中,主要原因是由时间驱动直接产生簇头,不像EEUC算法由随机数与阈值的机制产生候选簇头,因此本文算法产生的簇头数量更加稳定.

图4 基站接收到数据包总数Fig.4 Total amount of data packects received at BS

图4是3种算法中基站接收数据包数目比较,从图中可以看出,在本文算法下,基站接收的数据包随轮数线性增长且总数目最多,说该算法运行稳定,能量效率高.EEUC接收的数据包随轮数近似线性增长且总数目低,说明了算法能有效平衡节点能耗但能量效率低.LEACH算法在700轮后数据包数增加缓慢,由于节点能量消耗不均,造成网络中大量的节点死亡,减少了节点发送到基站数据包数目.

综合实验结果,本文提出路由算法具有以下优点:①分簇算法稳定,所生成簇的数目波动小;②有效平衡了网络中节点的消耗,延长网络生存时间;③基站能够从网络中获得较多数据,有利于判断环境的变化.

6 结 论

本文提出了一种基于时间驱动簇头选择非均匀分簇路由算法,它的核心思想是:首先,节点利用其剩余能量竞选簇头,避免由网络随机产生候选簇头,再由候选簇头通过竞争产生簇头的繁琐过程,同时降低了算法消息复杂度.其次,普通节点根据簇内通信代价最小选择簇头,构造出大小不等的簇,对于解决由多跳路由引起传感器网络“热区”问题很有效.实验证明,该算法比LEACH和EEUC算法更能延长网络生存时间.

本算法虽然有效解决了EEUC算法对普通节点成为候选簇头的概率取值,但未能对其它参数优化取值进行详细分析,事实上它们对于网络生存时间有很大影响,因此,在以后工作中,将对这些参数的最优取值进行研究.

[1]Estrin D,Girod L,Pottie G,et al.Instrumenting the World with Wireless Sensor Networks[C].In:Proc.of the Int′l Conf.on Acoustics,Speech,and Signal Processing(ICASSP 2001),2001.

[2]Pottie G J,Kaiser W J.Wireless integrated network sensors[J].Communications of the ACM,2000,43(5):51-58.

[3]Estrin D.Next Century Challenges:Scalable Coordination in Sensor Networks[C].In:Proc.of the MobiCOM′99,1999:263-270.

[4]Chang J H,Tassiulas L.Maximum lifetime routing in wireles sensor networks[J].IEEE/ACM Trans.on Networking,2004,12(4):609-619.

[5]Heinzelman W R,ChandrakasanA P,Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[6]Younis O,Fahmy S.HEED:A hybrid,energy efficient,distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):660-669.

[7]Ye M,Li C,Chen G,et al.EECS:An Energy Efficient Cluster Scheme in Wireless Sensor Networks[M].New York:Proceedings of the IEEE IPCCC,2005:535-540.

[8]Mhatre V,Rosenberg C.Design guidelines for wreless sensornetworks:communication.clustering and aggregation[J].Ad-Hoc Network,2004,2(l):45-63.

[9]Li C,Ye M,Chen G,et al.An Energy Effieient Unequal Clustering Mechanism for Wireless Sensor Networks[C].Proeedings of the 2th IEEE International Conference on Mobile Ad hoc and Sensor Systems.Washington,DC,2005:597-604.

[10]Soro S,Heinzelman W.Prolonging the Lifetimeof Wireless Sensor Networks Via Unequal Clustering[C].Proceedings of the 5th International Workshop on Algorithms for Wireless,Mobile,Ad Hoc and Sensor Networks,Denver,CO,2005.

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

Li Chengfa,Chen Guihai,Ye Mao,et al.An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Journal of Computers,2007,30(1):27-36.(in Chinese)

[12]ChenGuihai,LiChengfa,Ye Mao,et al.An unequal cluster-based routing protocolin wirelesssensor networks[J].Wireless Networks,2009,15(2):193-207.

[13]Gong Bencan,Li Layuan Li,Wang Shaorong,et al.Multihop Routing Protocolwith Unequal Clustering for WirelessSensor Networks[C].Computing,Communication,Control,and Management,2008.CCCM′08.ISECS InternationalColloquium on,2008:552-556.