非变换簇的WSN分簇路由算法.doc

非变换簇的WSN分簇路由算法 张岩 （西安文理学院信息工程学院，陕西西安710065） 摘要：针对LEACH算法簇头选取及能量消耗方面的不足，提出一种基于能量、距离和节点度的分簇路由算法CMEDD，通过均匀分簇减少重建过程，对簇头选举公式进行改进，合理选择簇头，从而均衡节点能耗。采用基于代价因子的单跳和多跳相结合的方式建立最优路径进行数据传输。仿真结果表明，与LEACH算法和RMCRW算法相比，CMEDD算法能够有效均衡节点能耗，可相对延长网络生存周期。 关键词：无线传感器网络；能耗均衡；簇头选取；网络生命周期 ：TN711?34；TP393：A：1004?373X（xx）18?0026?04 ：xx?03?25 基金项目：西安市科技计划项目（CXY1443WL19）；国家自然科学基金资助项目（41301413） 无线传感器网络中，传感器节点多采用能量有限的电池供电，使得整个网络对数据的存储处理和传输能力受到了限制。所以如何有效使用传感器节点能量，以及如何延长网络的生命周期就成为设计无线传感器网络路由协议的一个重点，其中从管理的角度上对网络进行层次化管理是目前该领域的一个研究热点。 文献1提出了无线传感网拓扑控制典型的低功耗自适应算法LEACH，与平面拓扑算法相比，该协议可以延长网络生命期约30%。但是LEACH算法没有考虑能量不平衡问题，存在很大改进空间。 针对LEACH算法存在的问题，学者们提出一系列改进的算法2?7。文献2?4均提出基于剩余能量的自适应分簇算法，算法选择剩余能量最大的节点作为簇头，平衡能耗。文献5提出了基于节点能量阈值的簇头竞争算法，当簇头节点的剩余能量值降低到特定阈值下时，算法就启动新一轮簇的建立过程。文献6利用节点到基站的距离作为簇头选择的权重对LEACH算法进行改进。文献7LEACH?EI算法，考虑节点初始能量和当前能量2个因素，利用动态分簇的方式计算能量阈值，根据能量阈值选择簇头。文献8ECRED算法通过引入备选簇头减少簇的重建，用以降低簇头选举的能耗。文献9RMCRW算法提出基于环的簇头选举方式，引入权值控制簇头转发路径，达到节能目的。另外也有研究者将已有的一些优化算法如遗传算法、蚁群算法等应用到路由算法的设计中，从而延长网络寿命。 在深入研究无线传感器网络LEACH及其相关改进协议的基础上，本文设计了一种基于能量、距离、节点度的算法（AClusterHeadMakeup?Energy?Distance?Densi?tyAlgorithmImprovedBasedonLEACHAlgorithm，CMEDD）。 1网络模型 1.1本文采用的节点模型假设如下： （1）基站距离较远且能量无限，位置不发生改变； （2）节点同构且初始能量相等，一经部署其位置不再发生改变； （3）节点发送功率可以进行调整，即具有调节无线收发器工作能耗的控制功能； （4）节点能够支持多种MAC协议（如TDMA等）； （5）传感器节点具有足够的计算能力，即具有一定的数据融合功能。 1.2能耗模型 节点l位的数据包传送长度为d，通信模型为9： 2CMEDD算法描述 2.1簇头选择 在分簇结构的无限传感器网络中簇头个数k是影响分簇路由算法网络能耗的一个重要参数。CMEDD算法采用文献10中簇头个数k的取值算法。本算法规定首轮成簇及广播工作由基站完成，基站按照最佳簇头个数将网络化分成k个虚拟网格，进而基站在每个网格内随机选取一个节点作为本簇的簇头，同时生成一个邻居列表消息Message_neighbour，并将此信息广播给各自簇（网格）内成员节点11。基站公布本次的信息匹配之前，所有节点不知道自己所属的簇区域，因此基站发布的Message_neighbour消息覆盖范围要确保网络内所有节点都能接收到。 基站可以从第1轮各簇头发送的数据确定所有节点及基站之间的距离关系，为第2轮及以后的簇头选举提供必要数据。在经过Nk轮的工作之后，由于各种随机事件使得簇内节点能量可能差异较大。为了均衡网络能耗并延长其使用周期，在随后的簇头选举中将综合考虑到节点剩余能量、簇内节点平均距离及节点距基站距离、节点度等三方面因素： （1）节点剩余能量 首先引入节点剩余能量参数E(n)： 式中:En(r)为节点n在r轮的剩余能量；Eeverage(r)为r轮时刻簇内平均能量。则： 在每一轮的工作结束时，每个节点查看自身的En(r)值，并向簇头报告，簇头计算簇内的平均能量值，并向簇内广播。 （2）簇内节点平均距离及节点距基站距离 其次分析节点与簇内其余节点以及与基站之间的距离参数D(n)： 式中：节点n坐标为(x,y)；(x)i,yi为簇内其余节点的坐标值；(xtoBS),ytoBS为基站的坐标值；D1(n)为节点n到簇内其余节点的距离之和；D2(n)为节点n到基站的距离，则： 在网络运行中传感器节点一经部署其位置不会改变，因此每个节点的距离参数只需要计算1次。节点位置信息的传递是在簇建立过程中对能量消息的传递中一起进行的，从而减少了信息交互中的通信损耗。 （3）节点度析节点的度 节点为布尔感知模型12，即每个节点都具有一个固定的感知半径R，其感知范围是以节点为圆心，R为半径的圆。簇内处于某节点感知半径内的节点为此节点的一步通信节点。一步通信节点个数称作节点的度Measure(n)。一步通信节点较多，即其周围节点分布较为密集，则该节点当选簇头的概率也应随之增大。节点的度调节参数M(n)的模型及约束条件如下： 各节点根据各项参数调整各自成为簇头的阈值，经过对比阈值较大者成为簇头。 调整后的阈值公式为： 改进后的公式使得当前节点的剩余能量越大、节点到基站以及到其他节点之间的平均距离的关系参数越大，节点的度越大，则阈值T(n)越大，从而该节点当选为簇头的几率越大，反之当选为簇头的几率越小。 2.2簇间路由 网络中的簇头节点与普通节点一样也有通信模型阈值dcrosscover，当传输距离小于此值时，其能耗与距离平方成线性关系。网络中簇头选取完毕则存在G=V,E，V=v1,v2,?,vk，V为簇头集，E为可直接通信的两节点间的通信能耗。则距离基站较远的簇头节点直接向基站发送数据能量会损失较快，不利于网络能量均衡。CMEDD算法在簇头向基站传输数据时，按照代价因子公式寻找下一跳中转接点。 假定在网络中vi,vj均为簇头，则簇头节点vj作为簇头节点vi的下一跳中转节点的代价因子为： 式中：E(i,j)E；E(v)j为簇头节点vj的当前能量；sij为vi,vj之间距离，且sij?dcrosscover；Sj为vj到基站的距离，j=1,2,?,k。节点vi从属于集合V并且与自身距离小于dcrosscover的节点中找到代价因子最小的节点vj，作为自己的下一跳中转节点。vj再以同样的方式找到自己的下一跳中转节点，从而形成一条通向基站的通信链路。则vj可作为vi的中转节点，vi向vj发送数据符合自由空间模型，通信链路上的总体能量消耗远小于多路衰减模型。 3算法仿真与性能验证 为了验证CMEDD算法的有效性，对CMEDD，RMCRW和LEACH算法进行对比。仿真实验在MatlabRxxa环境下进行，以随机方式在监测区域内部署传感器节点，假设节点分布在坐标为(0,0)到(100,100)的区域内。仿真实验使用参数取值分别为：N=100，M=100，数据包长度l=500，基站的坐标（50，175），Efs=10pJ，Eamp=0.0013pJ，节点初始能量E0=21010pJ，EDA=5103pJ，Eelec=50103pJ。 无线传感器网络的生命周期着重从首节点能量耗尽所用时间进行考虑。基于这一原因实验对网络节点数分别为100，200时三种算法运行期间存活节点数进行仿真，其仿真图分别如图1，图2所示。 如图1所示，模拟环境与初始能量相同，100个节点时LEACH算法运行16轮，第17轮出现节点能量耗尽；RMCRW算法运行20轮，第21轮出现节点能量耗尽；而CMEDD算法运行22轮左右开始出现能量耗尽的节点。CMEDD算法首节点死亡轮数较LEACH算法延长了37.5%、较RMCRW算法延长了10.1%。说明同样的运行时间，CMEDD算法节点能耗更低，并使节点能耗的分布更加均匀，即有效延长了节点的生存时间。由图2可知，在各项参数保持不变的环境下，将节点数增至200，CMEDD，RMCRW和LEACH三种算法的首节点死亡轮数分别为31，28和23，即CMEDD算法首节点死亡轮数较LEACH和RMCRW分别提高了34.8%和10.7%。说明本算法对网络密度具有较好的适应性。综合分析图1，图2可以看出，CMEDD算法节点生命曲线与LEACH和RMCRW相比较而言坡度较大，说明节点能耗更为均衡。 当网络节点分别为100和200时，CMEDD算法与LEACH和RMCRW算法节点的能量消耗曲线如图3，图4所示。 分析图3，图4可知，初始阶段三者能耗差别较小，但随着运行轮数的增加，CMEDD算法的节点存活数目及平均能量逐渐高于LEACH和RMCRW算法，即CMEDD算法对网络密度具有良好适应性。 4结语 本文提出了基于能量、距离及节点度的非变换分簇的一种能耗均衡的路由算法（CMEDD）。算法给出了分簇方式、簇头选择公式及簇间路由形式，首轮由基站选择簇头，第2轮以后利用基于节点的剩余能量、节点到基站以及到其他节点之间的平均距离和节点的度3项参数的阈值公式选取簇头；数据传输阶段簇头根据代价因子选择中继节点，从而实现单、多跳结合的路由方式，降低网络能耗。仿真实验及对比表明，CMEDD算法能够有效均衡网络能耗、延长网络生命周期。 CMEDD算法在均衡网络能耗方面有一定优势，但是仍然存在一些问题，如在网络运行中簇头进行数据融合的高效性以及在较大网络中算法的安全性和可扩展性都有待进一步的研究。 参考文献 1HEINZELLNANWB，CHANDRAKASANAP，BALAKRISH?NANH.Anapplication?specificprotocolarchitectureforwire?lessmicrosensorworksJ.IEEETransactionsonWirelessCommunications，xx，1（4）：660?670. 2KUBISCHM，KARLH，WOLISZA，etal.Distributedalgo?rithmfortransmissionpowercontrolinwirelesssensor?worksC/ProceedingsofthexxIEEEWirelessCommunica?tionsNetworking.Washington，USA：IEEECommunicationsSo?ciety，xx：16?20. 3BAIL，ZHAOL，LIAOZ.Energybalanceincooperativewire?lesssensorworksC/Proceedingsofthe14thEuropeanwirelessconference.Prague，CzechRepublic：IEEE，xx：143?145. 4LIYL，DINGLW，LIUF.TheimprovementofLEACHproto?colinWSNC/ProceedingsofthexxInternationalConferenceonComputerScienceandNetworkTechnology.Harbin，Chi?na：IEEE，xx：1345?1348. 5AKYILDIZIF，SANKARASUBRAMANIAMY，SUW，etal.AsurveyonsensorworksJ.ProcIEEECommunicationsMagazine，xx，40（8）：102?114. 6ENAMIN，MOGHADAMRA，DADASHTABARK.Neuralworkbasedenergyefficiencyinwirelesssensorworks：AsurveyJ.InternationalJournalofComputerScience&Engi?neeringSurvey，xx：1（1）：39?53. 7白凤娥，王莉莉，马艳艳，等.无线传感器网络路由协议LEACH的算法分析J.太原理工大学学报，xx，40（4）：348?352. 8张诗悦，吴建德，王晓东，等.一种能耗均衡的无线传感器网络分簇路由算法J.计算机工程，xx，40（8）：6?9. 9鲁松，徐文春，杨云.一种分环多跳的无线传感器网络分簇路由加权算法J.山东大学学报：工学版，xx，42（4）：24?28. 10CHANDRAKASANA，REXM，BHARDWAJM，etal.Pow?erawar