基于分环多跳的无线传感网分簇路由算法.doc

·· 通信学报 第29卷
第3期 刘志等：基于分环多跳的无线传感网分簇路由算法 ··

第29卷第3期 通信学报 Vol.29No.3
2008年3月 JournalonCommunications March2008

基于分环多跳的无线传感网分簇路由算法
刘志,裘正定
(北京交通大学信息科学研究所,北京100044)
摘要：为了提高无线传感网在大区域情形下的能量效率，提出了一种分环多跳分簇路由算法RBMC（ringbasedmulti-hopclusteringroutingalgorithm）。RBMC算法采用分环的方式实现簇头间的多跳通信，通过在不同环内构建大小不同的簇解决传感器网络中存在的“热点”问题，在不同的簇头选举策略下，能够同时满足节点能量同构及异构两种情形。仿真结果表明，在大区域环境下，分环多跳分簇路由算法能在很大程度上均衡节点能量消耗，延长网络的生命周期。
关键词：传感器网络；分簇路由；分环模型；能耗均衡
中图分类号：TP393文献标识码：B文章编号：1000-436X(2008)03-0104-10
Ringbasedmulti-hopclusteringroutingalgorithmforwirelesssensornetworks
LIUZhi,QIUZheng-ding
(InstituteofInformationScience,BeijingJiaotongUniversity,Beijing100044,China)
Abstract:Aringbasedmulti-hopclusteringroutingalgorithm(RBMC)forwirelesssensornetworks(WSN)wasproposed.ThemaintaskofRBMCwastoprolongthelifetimeofthenetwork,balanceenergyconsumptionbetweennodes.ThemainideaofRBMCwastodividetheWSNfieldintoconcentricringsandbuildunequalsizeofclustersindifferentrings.Fromtheobjectiveofminimumenergyconsumptioninfirstringandbalanceofitbetweenfirstringandotherrings,theoptimalchoiceofclusternumbersforeachringwasdeduced.Viaadoptionofdifferentalgorithmsforclusterheadelection,RBMCcouldbeappliedtohomogeneousandheterogeneousenergysettings.ThesimulationresultsprovethegoodperformanceofRBMCinlargeareaWSNscenarios.
Keywords:wirelesssensornetworks;clusteringrouting;ringbasedmodel;balanceenergyconsumption

1引言
收稿日期：2006-06-28；修回日期：2007-12-28
能量受限是传感器网络最显著的特点之一。实验表明，传输一个比特所消耗的能量比运算处理一个比特消耗的能量大[1]。采用高效的路由算法，可以大大提高无线传感网（WSN,wirelesssensornetworks）的能量效率，分簇路由算法被认为是比较符合传感器网络的特性的高效算法。有关分簇的问题很早便有论述，如文献[2~9]，这些算法基本都是启发式的，其目标是生成具有最小数量的簇，同时使得任意一个簇中的任意节点到簇头的跳数至多为d跳，算法的复杂度在O(N)量级（N为网络中的传感器节点总数）。针对传感器网络的特性，Heinzelman提出了LEACH（low-energyadaptiveclusteringhierarchy，低能耗自适应分簇层次算法）算法[10]。其核心思想是让每个节点轮流担当簇头，从而使得网络中的能量消耗尽可能均匀，减少网络失效时刻的能量浪费。LEACH算法只考虑了单跳模型，因此只适合于小型WSN网络。文献[11]提出了M-LEACH（multi-hopvariantofLEACH，多跳LEACH）算法，簇内的节点不是以单跳的方式传输数据到簇头，而是通过簇内其他节点转发。文献[12]提出了一个多跳簇头模型，采用从下到上的策略，逐层生成每一层的簇头，最终得到一个多层结构的WSN网络。文献[13]采用基于代价的目标函数对传感器网络设计进行了分析，推导出单跳和多跳的适用