一种新的分环多跳均匀分簇协议分析及NS2仿真

王春梅

(滨州学院信息工程系，山东 滨州　256603)

一种新的分环多跳均匀分簇协议分析及NS2仿真

王春梅

(滨州学院信息工程系，山东 滨州256603)

摘要：针对实际应用中存在的圆形无线传感器网络，设计了一种分环多跳的均匀分簇协议CBMBC，理论证明了CBMBC的簇头异构特性比簇头同构的情形下节省能量。通过NS2仿真，证明了将网络划分成三层环时可以比划分两层环时延长网络的寿命，但是计算复杂度会相应提高。

关键词：无线传感器网络；均匀分簇协议；NS2仿真实验

无线传感器网络的一些实际应用中，存在节点均匀分布在圆形区域中，基站位于圆心处的理想网络模型。其为圆形网络模型的一个基础模型，适用于二维的平面区域。为了降低对此类网络划分骨干网的难度，很多学者为理想网络模型设计了很多理想的分簇算法[1-8]。这些分簇算法的主要思想就是将这些圆形的网络区域划分成多个同心环，称这一结构为圆环模型。基于圆环模型提出了很多非均匀分簇的算法，即根据不同的划分原则来划分大小规模不等的簇。文献[6]中第一次提出了非均匀分簇的算法来解决能耗不均问题。文献[7]中在能量同构的无线传感器网络多跳通信模式下提出了一种非均匀分簇算法。文献[8]在能量同构的无线传感器网络单跳通信模式下提出了一种非均匀分簇算法。这两种算法都没有考虑普通节点与簇头节点间能耗的均衡性。针对以上算法的缺陷，设计了一种分环多跳的均匀分簇协议CBMBC。在不同环上设置大小均等的簇规模，使得每一层环中簇头的能量同构，不同环中簇头的能量异构，每层环上的普通节点将收集的数据以单跳方式发送给簇中的簇头，位于外环上的簇头则通过位于相邻内环上的簇头将数据以多跳的方式发送给位于圆环中心的基站，以此来均衡簇头节点间的能耗。此外，根据普通节点的能耗和每层环上簇头和基站的相对距离设置簇头的初始能量，使普通节点的死亡时间和其簇头节点尽量保持同步，以此来均衡普通节点和簇头节点间的能耗。因此，网络中所有节点的能量在网络死亡的时候都能够得到充分利用，避免了浪费。

1问题描述

将N个节点均匀分布在一个半径为R的圆形区域内。基站位于圆形区域中心。在这些节点中，布置了大量的普通节点用来监测收集数据，另外布置一些功能更强的、具有更多能量的节点作为簇头。普通节点收集完数据后以单跳的形式将其发送给簇头，簇头将融合处理后的数据通过内环中的簇头以多跳的方式发送给基站。由于和基站的距离不同，导致簇头节点的能耗也不同。内环簇头由于要转发大量外环簇头转发的数据，能量消耗会很大。因此，假设簇头节点的初始能量是相同的，则距离基站较近的内环簇头就会快速死亡而缩短网络寿命。

解决这种问题的一种可行解决方法是将网络划分成很多环，在同一环中，设计规模大小均等的多个簇。根据到基站的不同距离，为不同环中的簇头设置不同的初始能量，使得内环簇头的能量较高，而外环簇头的能量较低，但是在同一环内的簇头则是能量同构的。根据普通节点的能量以及簇头所在的位置设置簇头节点的能量，可以使得整个网络中所有节点的存活时间尽可能同步，从而可以更好地延长网络寿命。

2算法系统模型

2.1　网络模型

将圆形的网络监测区域划分成多个宽度相等的环。在每个环中划分很多大小均等的簇，并且各个环中的簇的规模也是相等的。将簇头的位置和所需具备的能量预先计算出来，并放置在对应位置上。每个簇由簇头和其周围的普通成员节点组成。

图1　圆环模型

采用如下合理假设来简化网络模型：

1) 每个节点都有唯一的节点标识(id)和其所在的环标识(Ci,i=2,3,…,k)。

2) 簇头节点对簇成员发送的数据进行融合的能力相同，对于其他环中簇头转发来的数据由于和本环中的数据相关性不大，所以不再对其进行融合，而是直接转发给内环簇头或者基站。

3) 每个普通节点每单位时间向簇头发送长度为l的包。

4) 网络寿命定义为从网络部署到第一个节点死亡的时间。

算法所用到的符号及相关定义如表1所示。

表1　符号及定义

2.2　能量模型

为简化模型，这里假设传输距离小于dcrossover，采用自由空间模型。即

(2)

节点接收端能量消耗为

(3)

假设传感器节点进行监测的能耗为Esen，簇头对数据进行融合的能耗为Ecom。

2.3　相关参数的优化设置

2.3.1簇头间数据转发能耗

因为簇头的位置决定着簇内普通节点的能耗，一般分簇时，会将簇头尽量安置在簇的中心以使得所有成员节点到簇头的传输距离最短。因此，把簇头放置在簇区域的重心的位置。由于本文采取的是簇间多跳的通信方式，外环簇头将收集处理后的数据通过内环发送至基站，假设第i层环中簇头总是将数据转发给距离该簇头最近的第i-1层环中簇头，下面介绍相互通信的两层环中簇头的平均距离。

(4)

第i-1层环中簇的簇头到基站的距离为

(5)

第i层环中簇的簇头到基站的距离为

(6)

因此，第i层环中簇的簇头到第i-1层环中簇头的最大的最近距离近似满足

(7)

第i层环中簇的簇头到第i-1层环中簇头的最小的最近距离近似满足

(8)

取式(7)和式(8)的平均值作为第i层环中簇头到第i-1层环中簇头的最佳数据转发距离，则

(9)

那么，第i层环中簇的簇头到第i-1层环中簇头进行一次数据转发每单位时间要消耗的传输能量为

(10)

第i层环中簇的簇头向第i-1层环中簇头转发数据的同时会收到第i+1层环中簇头转发来的数据，因此，当最外层即第k层环中的簇头发送了一个数据包时，第i层就会发送k-i个数据包。由此，可以得出，第i层簇头的每单位时间转发能耗为

(11)

2.3.2普通节点的传输距离

第一层环内的节点直接与汇点进行传输，故第一层环的普通节点的最远传输距离为：

(12)

第i(i=2,3,…,k)层环内普通节点的最大传输距离为

(13)

为延长网络寿命，使普通节点的能耗尽量均衡，这里普通节点的最大传输距离应满足下面的等式

(14)

又由于

(15)

通过上面的式(4)到式(15)，已知内层环的簇数目mi，便可求得dchi、R1和mi+1等参数的最优值。

2.3.3簇头节点能耗

由于N个节点随机分布在半径为R的圆形区域内，则第i层环内一个簇内的节点数为

(16)

结合式，第层簇头单位时间的能耗为

(17)

普通节点单位时间的最大能耗为

(18)

设普通节点的初始能量EiniNon已知，则各层簇头的初始能量可通过如下公式求得

(19)

2.4　理论分析

本文的网络模型中，网络在最初的阶段被划分成簇，这些簇在整个网络生命周期中保持不变，这样便节省了簇头选举和成簇过程消耗的能量。并将监测区域划分为多个同心圆环，最内层为半径为R1的圆，其余各层环宽度为r，每层环均分为mi，通过调整mi与R1可使层环内普通节点的最大传输距离dfuri近似相等，最终达到普通节点间的能耗尽可能的均衡。部署一些能量较多的节点作为簇头节点，且不同环上的簇头的能量是异构的。因为内环簇头需要对外环簇头的数据进行转发，会比外环簇头更快地消耗能量，采用这种簇头能量异构的方法，根据普通节点的初始能量和簇头所在的环的层数设置不同环上的簇头的初始能量，使簇头与普通节点的能量相当，尽量使得网络中所有的节点的存活时间是同步的，充分利用了网络中的能量资源，避免浪费。

针对本文提出的模型，如果假设其各层环上的簇头是能量同构的，称这个假设模型为簇头能量同构分簇模型CHEH。在提出的网络模型中，第二层环的簇头能耗是最大的，其能耗为ECH2。因此，初始能量最大的簇头也位于第二层环，其初始能量为

(20)

网络中节点的总能量为

(21)

其中，Enontotal为网络中普通节点的总能量。为了使得假设模型CHEH与本文提出的网络模型寿命相同，其各层环上的簇头的初始能量最小也要EiniCHk，则CHEH中节点的总能量为

(22)

所以，由式(20)到式(22)得出，本文提出的网络模型和假设模型CHEH相比，可节省的能量为

(23)

3CBMBC协议仿真

测试场景为：200个节点均匀分布在半径为50的圆形区域.将圆形区域划分成等宽的圆环，在划分好的每个环中适当的位置部署一定数量的有较高能量的节点作为簇头。

3.1　仿真参数设置

具体仿真参数如表2所示。

表2　仿真参数的设置

对于有两层环的网络，将m2分别取值为：4，6，8,…,20。当m2取不同值时，计算其他各项参数的最优值，结果如表3所示。

表3　仿真参数最优值

3.2　仿真结果及其分析

下面图2给出了两层环的网络中将第二层环分为4，6，8,…,20个簇的情形下，网络中的第一个节点死亡时的网络寿命曲线图(用轮表示)。

图2　二层环上簇数不同时网络寿命

如图2所示，当逐渐增加第二层环上簇头的数目时，网络的生命周期也是逐渐增加的，且4~6、6~8，8~10的曲线斜率大于后面阶段。因为随着第二层环上簇头数目的增加，相应地，R1会减小，也就是普通节点和簇头之间的最远距离会减小，因此减少了普通节点向簇头发送数据时的传输能耗，从而延长了网络的寿命。

前面理论部分已经分析，与LEACH等经典的动态分簇协议比较，本文提出的静态分簇算法CBMBC避免了周期性的簇轮转，避免了不必要的能耗。在相同的场景，设置相同的仿真参数配置，选取m2=16情形下(此时dch2=35.8，dfur2=16.4，R1=16.4，)，运行LEACH协议，LEACH-C协议与CBMBC协议。用alive.awk提取需要的存活节点随运行时间变化的信息。

图3所示为3种协议的网络生存时间对比曲线图。

图3　不同协议网络寿命比较

如图3所示，LEACH协议运行时，网络中大多数节点很快就死了，原因是LEACH协议没有考虑节点的异构问题，能量较少的节点很快就死亡了，而此时能量较高的节点还会剩余很多的能量且不能再被充分利用，因此造成了能量的浪费。集中式算法LEACH-C相比LEACH可以获取比较均衡的簇头分布，网络中节点能耗可以得到一定的均衡，但是LEACH-C同样没有考虑节点能量的异构性，因此网络寿命仍然很短。CBMBC将簇头节点设置成较高能量，可以充分利用簇头节点的高能量。从图2中明显看出，与LEACH和LEACH-C协议相比，CBMBC可以有效延长网络的寿命。

对有三层环的网络的仿真中，设置第二层环上的簇头数m2=6，可计算此时dch2=25.2，dfur2=17.2，R1=17.2，r=16.4，m3的最优整数值为10。通过计算可得EiniCH2和EiniCH3最优值分别为12.3和11.8，因此将第二层环和第三层环上的簇头初始能量分别设为12.3J和11.8J。图4所示为三层环的网络与两层环的网络中网络寿命的比较。

图4　两层环网络和三层环网络的寿命比较

如图4所示，为网络划分三层环时网络的寿命较长。但需要以增加簇头的能量且提高算法设计的复杂度为代价。

4结束语

为圆形网络设计的一种分环多跳的均匀分簇协议CBMBC。算法对具体的设置进行了精确的计算和分析，并理论证明了CBMBC的簇头异构特性比簇头同构的情形下节省能量。通过NS2仿真，证明了将网络划分成三层环时可以比划分两层环时延长网络的寿命，但是计算复杂度会相应提高。

参考文献：

[1]孙利民,李建中,陈渝.无线传感器网络[M].北京:清华大学出版社,2005:3-24.

[2]毛晓峰,杨眠,毛迪林.无线传感器网络应用综述[J].计算机应用与软件,2008,25(3):179-181.

[3]MuruganathanSD,MaDCF,BhasinPI,etal.Acentralizedenergy-efficientroutingprotocolforwirelesssensornetworks[J].IEEECommunicationsMagazine,2005,43 (3):8-13.

[4]YounisO,FahmyS.HEED:Ahybrid,energy-efficient,distributedclusteringapproachforAdhocsensornetworks[J].IEEETransactionsonMobileComputing,2004,3(4):366-379.

[5]DhiaMahjoub,DavidW.Matula.Employing(1-)dominatingsetpartitionsasbackbonesinwirelesssensotnetworks[C]//ProceedingofALENEX’11.[S.l.]:[s.n.],2010:98-111.

[6]SoroS,HeinzelmanW.Prolongingthelifetimeofwirelesssensornetworksviaunequalclustering[C]//InProceedingofthe19thIEEEInternationalParallelandDistributedProcessingSymposium.Colorado,USA,2005(13):236-243.

[7]XiangM.Energyefficientclusteringalgorithmformaximizinglifetimeofwirelesssensornetworks[J].IntJElectron(AUE),2009(5):1-4.

[8]袁辉勇,王志和,刘永逸.基于不均匀圆环模型的无线传感器网络分簇算法[J].信息与控制,2008,7(4):509-512.

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

[11]WangY,ZhaoQ,ZhengD.Energy-drivenadaptiveclusteringdatacollectionprotocolinwirelesssensornetworks[C]//InProceedingsoftheInternationalConferenceonIntelligentMechatronicsandAutomation.Chengdu:[s.n.],2004:599-604.

[12]黄河清,沈杰,姚道远,等.无线传感器网络自适应能量驱动簇头轮换算法研究[J].电子与信息学报,2009,31(5):1040-1044.

[13]柯志亨，程荣祥，邓德隽.NS2仿真实验一多媒体和无线网络通信[M].北京:电子工业出版社，2009:1-104.

(责任编辑杨继森)

收稿日期：2015-02-20

基金项目：山东省自然科学基金项目“基于FPGA的分数阶切换混沌系统的网络视频信息保密技术研究”(ZR2012FM034);山东省自然科学基金项目“分数阶混沌系统的特性及同步研究”(2014ZRB019UP)

作者简介：王春梅(1982—)，女，硕士，讲师，主要从事计算机应用技术研究。

doi:10.11809/scbgxb2015.07.027

中图分类号：TP393

文献标识码：A

文章编号：1006-0707(2015)07-0104-05

本文引用格式：王春梅.一种新的分环多跳均匀分簇协议分析及NS2仿真[J].四川兵工学报，2015(7):104-108.

Citation format:WANG Chun-mei.New Ring Based Multi-Hop Equal Clustering Protocol Analysis and NS2 Simulation[J].Journal of Sichuan Ordnance,2015(7):104-108.

New Ring Based Multi-Hop Equal Clustering
Protocol Analysis and NS2 Simulation

WANG Chun-mei

(Information Engineering Department, Binzhou University, Binzhou 256603, China)

Abstract:Aiming at the circular wireless sensor networks (WSN) in practical applications, a new ring based multi-hop equal clustering protocol CBMBC was proposed, the heterogeneous cluster head can save energy than the cluster head isomorphic by theoretical proof. The NS2 simulation results prove that WSN divided into three layers can prolong the lifetime of WSN compared to WSN divided into two layers, but the computational complexity will be increased.

Key words:wireless sensor networks; equal clustering protocol; NS2 simulation experiment

【信息科学与控制工程】