网站首页  词典首页

请输入您要查询的论文:

 

标题 非变换簇的WSN分簇路由算法
范文 张岩



摘 要: 针对LEACH算法簇头选取及能量消耗方面的不足,提出一种基于能量、距离和节点度的分簇路由算法CMEDD,通过均匀分簇减少重建过程,对簇头选举公式进行改进,合理选择簇头,从而均衡节点能耗。采用基于代价因子的单跳和多跳相结合的方式建立最优路径进行数据传输。仿真结果表明,与LEACH算法和RMCRW算法相比,CMEDD算法能够有效均衡节点能耗,可相对延长网络生存周期。
关键词: 无线传感器网络; 能耗均衡; 簇头选取; 网络生命周期
中图分类号: TN711?34; TP393 文献标识码: A 文章编号: 1004?373X(2015)18?0026?04
Abstract: Aiming at the insufficiency of cluster head selection and energy consumption of LEACH algorithm, a CMEDD clustering routing algorithm based on energy, distance and node degree is proposed to simplify the reconstruction process by uniform clustering, improve the way to select cluster head, and select the cluster head reasonably, so that the energy consumption of the nodes can be balanced. Moreover the optimal path was set up by the mode combining single hop and multi hop based on cost factor to transmit data. The simulation results show that compared with LEACH algorithm and RMCRW algorithm, the CMEDD algorithm can more effectively balance the node energy consumption and prolong the network lifetime relatively.
Keywords: wireless sensor network (WSN); energy consumption balance; cluster head selection; network lifecycle
无线传感器网络中,传感器节点多采用能量有限的电池供电,使得整个网络对数据的存储处理和传输能力受到了限制。所以如何有效使用传感器节点能量,以及如何延长网络的生命周期就成为设计无线传感器网络路由协议的一个重点,其中从管理的角度上对网络进行层次化管理是目前该领域的一个研究热点。
文献[1]提出了无线传感网拓扑控制典型的低功耗自适应算法LEACH,与平面拓扑算法相比,该协议可以延长网络生命期约30%。但是LEACH 算法没有考虑能量不平衡问题,存在很大改进空间。
针对LEACH算法存在的问题,学者们提出一系列改进的算法[2?7]。文献[2?4]均提出基于剩余能量的自适应分簇算法,算法选择剩余能量最大的节点作为簇头,平衡能耗。文献[5]提出了基于节点能量阈值的簇头竞争算法,当簇头节点的剩余能量值降低到特定阈值下时,算法就启动新一轮簇的建立过程。文献[6]利用节点到基站的距离作为簇头选择的权重对LEACH算法进行改进。文献[7]LEACH?EI算法,考虑节点初始能量和当前能量2个因素,利用动态分簇的方式计算能量阈值,根据能量阈值选择簇头。文献[8]ECRED算法通过引入备选簇头减少簇的重建,用以降低簇头选举的能耗。文献[9]RMCRW算法提出基于环的簇头选举方式,引入权值控制簇头转发路径,达到节能目的。另外也有研究者将已有的一些优化算法如遗传算法、蚁群算法等应用到路由算法的设计中,从而延长网络寿命。
在深入研究无线传感器网络LEACH及其相关改进协议的基础上,本文设计了一种基于能量、距离、节点度的算法(A Cluster Head Make up?Energy?Distance?Density Algorithm Improved Based on LEACH Algorithm,CMEDD)。
1 网络模型
1.1 本文采用的节点模型假设如下:
(1) 基站距离较远且能量无限,位置不发生改变;
(2) 节点同构且初始能量相等,一经部署其位置不再发生改变;
(3) 节点发送功率可以进行调整,即具有调节无线收发器工作能耗的控制功能;
(4) 节点能够支持多种MAC协议(如TDMA等);
(5) 传感器节点具有足够的计算能力,即具有一定的数据融合功能。
1.2 能耗模型
节点[l]位的数据包传送长度为[d],通信模型为[9]:
[ETx(l,d)=lEelec+lEFSd2, d式中:[Eelec]为单位[bit]数据收发能耗;[dcrossover]为模型划分阈值,d大于[dcrossover]选择多路衰减模型,其功放能耗为[Eamp],d小于[dcrossover]选择自由空间模型,其功放能耗为[Efs]。设[EDA]为簇头节点数据融合能耗;[dtoBS]为簇头到基站的距离;[N]为节点总数;[M]为正方形区域边长,一轮工作总能耗为[Etotal],则:[Etotal=l(EelecN+EDAN+kEampd4toBS+NEelec+NEfs12πM2k)] (2)
2 CMEDD算法描述
2.1 簇头选择
在分簇结构的无限传感器网络中簇头个数[k]是影响分簇路由算法网络能耗的一个重要参数。CMEDD算法采用文献[10]中簇头个数[k]的取值算法。本算法规定首轮成簇及广播工作由基站完成,基站按照最佳簇头个数将网络化分成[k]个虚拟网格,进而基站在每个网格内随机选取一个节点作为本簇的簇头,同时生成一个邻居列表消息Message_neighbour,并将此信息广播给各自簇(网格)内成员节点 [11]。基站公布本次的信息匹配之前,所有节点不知道自己所属的簇区域,因此基站发布的Message_neighbour消息覆盖范围要确保网络内所有节点都能接收到。
基站可以从第1轮各簇头发送的数据确定所有节点及基站之间的距离关系,为第2轮及以后的簇头选举提供必要数据。在经过[Nk]轮的工作之后,由于各种随机事件使得簇内节点能量可能差异较大。为了均衡网络能耗并延长其使用周期,在随后的簇头选举中将综合考虑到节点剩余能量、簇内节点平均距离及节点距基站距离、节点度等三方面因素:
(1) 节点剩余能量
在每一轮的工作结束时,每个节点查看自身的[En(r)]值,并向簇头报告,簇头计算簇内的平均能量值,并向簇内广播。
(2) 簇内节点平均距离及节点距基站距离
其次分析节点与簇内其余节点以及与基站之间的距离参数[Dn]:
在网络运行中传感器节点一经部署其位置不会改变,因此每个节点的距离参数只需要计算1次。节点位置信息的传递是在簇建立过程中对能量消息的传递中一起进行的,从而减少了信息交互中的通信损耗。
(3) 节点度析节点的度
节点为布尔感知模型[12],即每个节点都具有一个固定的感知半径[R],其感知范围是以节点为圆心,[R]为半径的圆。簇内处于某节点感知半径内的节点为此节点的一步通信节点。 一步通信节点个数称作节点的度[Measuren]。一步通信节点较多,即其周围节点分布较为密集,则该节点当选簇头的概率也应随之增大。节点的度调节参数[Mn]的模型及约束条件如下:
改进后的公式使得当前节点的剩余能量越大、节点到基站以及到其他节点之间的平均距离的关系参数越大,节点的度越大,则阈值[Tn]越大,从而该节点当选为簇头的几率越大,反之当选为簇头的几率越小。
2.2 簇间路由
网络中的簇头节点与普通节点一样也有通信模型阈值[dcrosscover],当传输距离小于此值时,其能耗与距离平方成线性关系。网络中簇头选取完毕则存在[G=V,E],[V=v1,v2,…,vk],[V]为簇头集,[E]为可直接通信的两节点间的通信能耗。则距离基站较远的簇头节点直接向基站发送数据能量会损失较快,不利于网络能量均衡。CMEDD算法在簇头向基站传输数据时,按照代价因子公式寻找下一跳中转接点。
假定在网络中[vi,vj]均为簇头,则簇头节点[vj]作为簇头节点[vi]的下一跳中转节点的代价因子为:
[fcost(vj)=Ei,j·si,j·sjEvj] (11)
式中:[Ei,j∈E];[Evj]为簇头节点[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算法进行对比。仿真实验在Matlab R2014a环境下进行,以随机方式在监测区域内部署传感器节点,假设节点分布在坐标为[0,0]到[100,100]的区域内。仿真实验使用参数取值分别为:N=100,M=100,数据包长度l=500,基站的坐标(50,175),Efs=10 pJ,Eamp=0.001 3 pJ,节点初始能量E0=2×1010 pJ,EDA=5×103 pJ,Eelec=50×103 pJ。
无线传感器网络的生命周期着重从首节点能量耗尽所用时间进行考虑。基于这一原因实验对网络节点数分别为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算法在均衡网络能耗方面有一定优势,但是仍然存在一些问题,如在网络运行中簇头进行数据融合的高效性以及在较大网络中算法的安全性和可扩展性都有待进一步的研究。
参考文献
[1] HEINZELLNAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application?specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660?670.
[2] KUBISCH M, KARL H, WOLISZ A, et al. Distributed algorithm for transmission power control in wireless sensor networks [C]// Proceedings of the 2003 IEEE Wireless Communications Networking. Washington,USA: IEEE Communications Society, 2003: 16?20.
[3] BAI L, ZHAO L, LIAO Z. Energy balance in cooperative wireless sensor networks [C]// Proceedings of the 14th European wireless conference. Prague, Czech Republic: IEEE, 2008: 143?145.
[4] LI Y L, DING L W, LIU F. The improvement of LEACH protocol in WSN [C]// Proceedings of the 2011 International Conference on Computer Science and Network Technology. Harbin, China: IEEE, 2011: 1345?1348.
[5] AKYILDIZ I F, SANKARASUBRAMANIAM Y, SU W, et al. A survey on sensor networks [J]. Proc IEEE Communications Magazine, 2007, 40(8): 102?114.
[6] ENAMI N, MOGHADAM R A, DADASHTABAR K. Neural network based energy efficiency in wireless sensor networks: A survey [J]. International Journal of Computer Science & Engineering Survey, 2010: 1(1): 39?53.
[7] 白凤娥,王莉莉,马艳艳,等.无线传感器网络路由协议LEACH的算法分析[J].太原理工大学学报,2009,40(4):348?352.
[8] 张诗悦,吴建德,王晓东,等.一种能耗均衡的无线传感器网络分簇路由算法[J].计算机工程,2014,40(8):6?9.
[9] 鲁松,徐文春,杨云.一种分环多跳的无线传感器网络分簇路由加权算法[J].山东大学学报:工学版,2012,42(4):24?28.
[10] CHANDRAKASAN A, REX M, BHARDWAJ M, et al. Power aware wireless microsensor systems [C]// Proceedings of the 32nd European Solid?State Device Research Conference. [S.l.]: IEEE, 2002: 47?54.
[11] 沈梦南,耿生玲,刘震.基于LEACH的无线传感器网络混合优化协议算法[J].计算机应用,2014,34(8):2148?2154.
[12] 陈炳才,么华卓,杨明川,等.一种基于LEACH协议改进的簇间多跳路由协议[J].传感技术学报,2014,27(3):373?377.
随便看

 

科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

 

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间:2025/3/16 10:03:46