一种改进的WSN成簇算法

一种改进的WSN成簇算法 一种改进的WSN成簇算法 第37卷 ,,0l-37 第1期 NO.1 计算机工程 ComputerEngineering 2011年1月 January2011 ? 网络与通信?文章编号:10o0_-_3428(2lll1)o1—毗10___o3文献标识码:A中圈分类号:TP393 一 种改进的WSN成簇算法 底欣,张百j孽 (北京理工大学自动化学院,北京100081) 摘要:从保证无线传感器网络(WSN)感知覆盖性能角度出发,分析节点剩余能量,重叠感知覆盖率与簇头选择的关系,改进LEACH协 议中簇头周值选择前的信息采集过程,提出一种适用于高密度随机部署的WSN成簇算法.实验结果明,该算法可有效保持网络感知覆 从而延长网络寿命. 盖率, 关健诃:无线传感器网络成簇算法;感知覆盖率;节点剩余能量;网络寿命 ImprovedWSNClusteringAlgorithm DIXin.ZHANGBai.hai (SchoolofAutomaticControl,BeijingInstituteofTechnology,Beijing100081,China) [Abstract]Thispaperanalyzestherelationofnoderesidualenergyoverlappingsensingcover agerateandclusterheadselectionfromtheangleof ensuringWirelessSensorNetwork(WSN)perceptioncoveringperformance.Itimprovesthe informationgatheringprocessbeforeselectingcluster headthreshold,andpresentsaWireles'sSensorNetwork(WSN)clusteringalgorithmwhichi ssuitableforhigh—densityrandomdeployment. Experimentalresultshowsthatthisalgorithmcanpreservethenetworksensingcoveragerate effectively,anditcanprolognetworklifetime. [Keywords]WirelessSensorNetwork(WSN)clusteringalgorithm;sensingcoveragerate;n oderesidualenergy;networklifetime D0I:10.39690.issn.1000—3428.2011.0l_038 1概述 高效地消耗有限能量,获得最大生命周期是无线传感器 网络研究的重要问题之一ljJ.分簇组织网络结构是无线传感 器网络高效自组织的重要方法j.LEACH[31协议是一种应用 广泛的分簇拓扑控制协议,其基本思想是通过随机循环选择 簇头,将整个网络的能量负载平均分配到每个节点,从而降 低网络能量消耗,延长网络生命周期J.这种方法不仅能够 减少与基站直接通信的节点数和通信量】,有效降低节点的 工作时间,还能避免因某些节点能源耗尽而将整个网络割裂 成几个独立的部分,从而结束网络寿命的情况发生.LEACH 协议以所有节点初始能量和能耗速度相等为前提l,然而在实际 应用中,这2个条件很难满足.因此,节点的剩余能量是决定 簇头选择的另一个关键因素,HEED协议针对这个问题进行 改进,将节点剩余能量作为条件,引入到簇头选择中. LEACH协议,HEED协议都没有考虑传感器网络的感知 覆盖性能.作为一个以感知为主要功能的网络系统,感知覆 盖是最重要的性能之一,因此其他协议的不应独立于感 知覆盖性能,对网络拓扑控制和路由算法的设计应当考虑对 感知覆盖的影响"J.文献f81提出一种从簇头选择阈值修正的 角度保障网络感知覆盖的改进LEACH协议(LEACH—C). LEACH—C协议认为重叠感知覆盖率高的节点成为簇头的概 率,相比重叠感知覆盖率低的节点大,它没有考虑剩余能量 对簇头选择的影响. 本文综合考虑节点剩余能量,提出一种新的网络成簇算 法.该算法在分析了剩余能量对网络感知覆盖率影响的基础 上,提出新的簇头选择闭值修正公式.仿真结果表明,该算 法具有较好的网络感知覆盖性,从而可以更有效地延长网络 寿命. 2模型假设及定义 2.1网络模型 本文假设传感器网络节点按照均匀分布随机部署在感知 区域内,且其满足以下条件: (1)传感器节点经部署后保持相对静止,且无人值守,无 法更换能量供给. (2)节点通信具有等效性,即2个节点可以通过相同的条 件进行通信. (3)网络节点高密度部署,不存在因分布导致的监测 盲区. (4)网络节点初始能量相同. (5)节点可以自定位,可以通过定位算法实现. 2.2覆盖模型 本文采用0—1感知覆盖模型,即当感知区域中的某一点 至少位于一个传感器节点的感知半径范围内,则称其被覆盖. 它的数学描述为: ):』j?】dAN?RN(1)10VN,dau>? 其中,p(A)为点A被覆盖的概率;d是点A到某传感器节 点?的距离;是传感器节点?的感知半径. 定义l(感知区域覆盖率C)至少被一个传感器节点覆盖 的感知区域面积与感知区域总面积的比值. 感知区域中的点可能不止被一个传感器节点覆盖.对于 一 个传感器节点,其覆盖范围为以其感知半径为大小的圆盘 作者简介:底欣(1982--),男,博士研究生,主研方向:WSN覆 盖控制;张百海,教授,博士后,博士生导师 收稿日期:2010—06—20E—mail:dixhappy82@163.COI1] 第37卷第1期底欣,张百海:一种改进的WSN成簇算法111 区域,面积为积.这个范围内的点,如果被其他传感器节 点同时覆盖,称为重叠覆盖点. 定义2(节点重叠覆盖率Co.)传感器节点感知范围 内,重叠覆盖点组成区域部分面积和整个节点感知区域面积 的比值. 设节点?有个邻居节点,它的重叠感知覆盖率 .(?)计算如下: Coverlapc(2) 其中,S(N)是节点?的感知覆盖范围面积;soverlap(?)是节 计算如下: 点Jv与其邻居节点的重叠覆盖面积, soverlap(?)=?-eflap一?-rlaP+?Sjvolap一??'+(一1)?n+lmp (3) 其中,.是节点?和它的个邻居节点的感知覆盖范围 面积. 若Co=1,则称此节点被完全重叠覆盖,此时,该节 点的死亡对整个网络的覆盖范围和覆盖率不会造成影响. 2.3寿命模型 从不同角度考察无线传感器网络的工作,可以得到3种 定义寿命的方法,分别为从网络开始正常工作到:(1)第1个 传感节点不能正常工作时止;(2)传感器网络的某一项任务不 能满足时止;(3)传感器网络因某些节点停止工作而割裂成几 个互不连接的部分,从而使得网络信息不能有效汇聚时止I. 网络寿命与节点失效(能量耗尽)密切相关,因此,3种定 义方法在一定程度上等效.LEACH协议主要考查网络节点能 耗均匀对网络寿命的影响,因此以节点死亡个数为依据定义 网络寿命.而本文算法保留了LEACH协议的能耗平均特性, 并针对网络覆盖性能做了改进,因此,采用第2种定义方法 考察网络寿命.具体地,根据应用需求对网络感知性能的要 求,当网络覆盖范围低于某一个值时,不能满足监测要求, 认为此时网络寿命结束.这种对无线传感器网络寿命的定义 方式满足传感器网络应用背景需求,且网络覆盖和连通具有 等价性,因此,对网络覆盖情况的定义同样适用于连通状态, 也即网络感知性能同数据汇聚性能之问的关系.因此,这样 的寿命定义方法是合理的. 定义3网络寿命终止条件:C?Cm.,其中,.是根 据应用需求设定的网络覆盖最小值. 3算法设计 本文首先分析和定义网络节点重叠覆盖率,然后描述根 最后描述成簇过程. 据其提出的簇头选择算法, 3.1节点重叠覆盖率和剩余能量对簇头选择的影响分析 设节点失效的概率为P,因节点失效引起的网络覆盖面 积减小量为AC,则因单个节点失效引起网络覆盖面积减小 的期望为E=pAC.P与网络节点剩余能量和耗能有关,设 簇头节点每轮平均能耗的期望为e,则: P: fl,? (4I0er'‰l【4J LEACH协议以轮为单位更换簇头.不失一般性,设2个传 感器节点l,"2,.l>2_dul,Co.<c..此时,若: (1)若ef>.2,则P=P:=1,两者均有可能 死亡,此时F/,死亡后对网络覆盖影响小,,被选为簇头的概 率大于. (2)若>el2.,则Pl=0,P2=1,g/2死亡的概 率大于.,".被选为簇头的概率大于7/. (3)若dual2.>ef,则P1=P2:0,从能耗均衡的 角度考虑,被选为簇头的概率大于:. 3.2基于节点重叠覆盖率和剩余能量的簇头选择 从3.1节分析可知,簇头选择算法应当按照节点剩余能 量.和簇头平均耗能P,的关系划分为2个部分.对. 大于,的节点,应以剩余能量为簇头选择的主要依据,且其 成为簇头的概率应大于那些小于,的节点成为簇头的 概率;而对于州.小于el的节点,应以重叠覆盖率cn作 为主要依据,c0.大的节点成为簇头的概率应更大. 设为节点簇头选择修正参数,根据上述分析,对77计 算如下: fi ef l—~esi—dualif8? 77{ej【5) lC'oapif《s.dual<ej 由(5)式可知,对于ere.>ef的节点,rl>1,而对于 ere<ej的节点,<1,符合上文对节点成为簇头的概率 分析. 对于第i个节点,定义P=p×,其中,P为簇头个数 占总节点数比率,为77,归一化后的值,因此,簇头阈值 选择为: , .1if?Gf61otherwise 3.3算法的实现 3.2节的算法对LEACH协议簇头选择阈值公式做了修 正,从算法执行过程来看,成簇过程与LEACH是相同的, 不同的是簇头选择所需要的信息,因此,需要更改簇头选择 阈值计算阶段前的信息采集过程. 当传感器网络完成部署并准备开始工作时,节点首先通 过广播Hello信息,建立自身的邻居节点集,通过式(2), 式(3)计算自身的重叠覆盖率.在首次成簇时,假设e=+, 此时所有节点根据重叠覆盖率原则计算自身的簇头选择阈 值.在第r一1轮时,簇头将数据汇聚到Sink节点,最后一次 数据通信时将自身消耗的能量通知给距离Sink最近的簇头 节点.这个簇头节点根据这些信息计算这轮的e,值,并将其 通知给簇头节点,随后簇头节点将其通知给所有节点.节点 接到这个信息后,通过自身剩余能量和重叠覆盖率计算自身 的值.再次通过簇将其汇总到距离Sink最近的簇头节点. 在归一化操作后,节点将通知到每个节点.节点依据计 算自身的簇头选择阈值,并完成簇头选择. 4仿真 将LEACH和LEACH—C作为基准,与 在仿真实验中, 本文算法进行性能对比.在仿真实验中,假设在M=100的正 方形区域内按P=1/M均匀分布放置100个节点,节点的感 知半径为R=15.基站位于正方形区域的一条边外, (M/2,M/2)处.每个节点的初始能量设定为1J. 本文假设能耗樽型忽略数据处理能耗,只计算节点通信 l12计算机工程2011年1月5日 能耗,分为发送和接收2个部分,根据无线电传播方式原理, 成功发送kByte消息耗能和成功接收kByte消息耗能 E,具体计算如下: IE(七,d)=七(】ec+唧d) ()=' 其中,tk=50nJ/bit;~am=nJ/bit.传播衰减指数 umt 规定为:当d?150时,=2;当d?150时,=4.为了 避免偶然因素对仿真结果的影响,分别对每个实验进行100次 不同随机拓扑的重复实验,实验结果均取平均值. 4.1网络癌知范围覆盖率仿真 为了验证本文算法的覆盖保持性能,首先进行网络感知 覆盖率随网络工作时间推移产生的衰减实验,如图1所示. 从实验结果可以看出,3种算法的网络感知覆盖率衰减具有 相同的变化趋势,可以分为3个区间.在开始阶段,网络中 很少的节点失效,网络基本保持完全覆盖状态,而本文算法 可以将这个趋势保持更长时间.在中间阶段,网络中失效节 点个数开始大幅增加,节点间通信距离加大趋势明显,感知 覆盖率下降很快,但由于本文算法在簇头选择时考虑了覆盖 因素,仍能获得较好的覆盖率.在最终阶段,剩余节点产生 的信息量有限,因此,网络能耗趋于缓和.在这个阶段,由 于考虑了网络覆盖和剩余能量的共同作用,本文算法对覆盖 率的保持作用明显. 图1网络囊知覆盖率随工作时问的衰减变化 4.2满足感知覆盖事的两络寿命仿真 本文根据网络覆盖性能定义进行网络寿命实验.为了满 足不同的应用需求,选择一组网络覆盖率分别进行实验,不 同感知覆盖要求下的网络寿命对比如图2所示.实验结果表 明,在完全覆盖或近似完全覆盖(覆盖率高于95%)的要求下, 本文算法略强于LEACH和LEACH—C.这是因为网络完全覆 盖性能主要与网络节点分布有关,随着节点的死亡,很难保 持网络完全覆盖.在部分覆盖情况下,本文算法取得了更好 的覆盖保持效果,这是由于网络簇头选择过程中,本文算法 中重叠感知覆盖大的节点失效较多,而LEACH随机选择簇 头,失效节点没有规律,相比LEACH—C,本文算法考虑了节 点剩余能量,因此节点失效少.可见,本文算法的感知覆盖 保持效果更好. 辑 撼 担 图2不同囊知覆盖要求下的两络寿命对比 5结束语 本文提出一种改进感知区域覆盖性能的簇头选择成簇算 法,其适用于随机部署无线传感器网络.依据节点及其邻居 节点的重叠覆盖率和剩余能量,每个节点成为簇头的可能性 不同,其目的是为了使网络覆盖得到有效保持.仿真实验结 果表明,本文算法在保持网络覆盖率和延长网络寿命上均取 得了较好的效果. 参考文献 [1]AkyildizIF,SuWeilian,SankarasubramaniamY,eta1.Wireless SensorNetworks:ASurvey[J].ComputerNetworks,2002,38(4): 393—422. [21IsrarN,AwanI.CoverageBasedInterclusterCommunicationfor LoadBalancinginWirelessSensorNetworks[C]//Proc.ofthe21st InternationalConferenceonAdvancedInformationNetworking andApplications.Ontario,Canada:[S.n.】,2007. 【3]HeinzelmanWB,ChandrakasemABalaknishnanH.AnAppli— cation-specificProtocolArchitectureforWirelessMicro—sensor Networks[J].IEEETrans.onWirelessCommuni?cations,2002, 4(1):660—670. [4]樊晓平,杨玺,刘少强,等.具有能量补给的无线传感器网 络分簇路由算法『J1.计算机工程,2008,34(11):120—122. [5]岳海兵,葛洪伟.基于能量分布的异构传感器网络分簇算法[J】l 计算机工程,2010,36(1):118?120. [6]HuYu,LiWei,KangZhenhua.StudyonEnergyHierarchical RoutingProtocolsofWirelessSensorNetworks[C]//Proc.of WASEIntemationalConferenceonInformationEngineering. Taiyuan,China:Is.n,J,2009. [71YounisO,FahmyS.HEED:AHybridEnergy—efficientDistributed ClusteringApproachforAdHocSensorNetworks[J].IEEETrans. onMobileComputing,2004,3(4):660—669. [8】TsaiYuh—Ren.Coverage—preservingRoutingProtocolsforRan— dorrdyDistributedWirelessSensorNetworks[J].IEEETmns.on WirelessCommunications,2007,6(4):1240-1245. [91MahfoudhS,MinetP.AnEnergyEfficientRoutingBasedon OLSRinWirelessAdHocandSensorNetworks[C]//Proc.ofthe 22ndInternationalConferenceonAdvancedInformation NetworkingandApplication.Okinawa,Japan:[S.n.],2008. 编辑陆燕菲