一种基于QoS的LEACH改进算法

杨海俊, 李鲁群

(上海师范大学 信息与机电工程学院,上海 200234)



一种基于QoS的LEACH改进算法

杨海俊, 李鲁群

(上海师范大学 信息与机电工程学院,上海 200234)

改进了经典分簇算法LEACH,提出了QBL(QoS-based LEACH)算法,以节约能耗为主要目标,旨在延长网络寿命、减小时延、提高网络可靠性.首先在簇头竞争时采用了新的权重计算方法,其次采用了不均匀分簇的策略,此外簇内只安排部分成员完成监测任务,并在簇间通信时采用基于权重的最短路径方法.仿真实验证明:QBL算法在分簇情况、网络寿命、时延、可靠性方面均有较为突出的表现.

WSN; 拓扑控制; 分簇; QoS

0 引 言

无线传感器网络(WSN)集计算、通信、传感等技术于一身,具有节点受限、自组织性、面向应用、以数据为中心等特点,广泛地应用于军事、交通、医疗等多个领域.打破传统网络协议体系严格的分层机制,WSN研究中出现了层间互联的跨层设计,且WSN的QoS体系也有所不同.

在WSN中,拓扑控制是位于MAC层与网络层之间的夹层,对MAC协议和路由协议、数据融合、目标定位、同步机制等都有积极的影响.拓扑控制算法常被分3种:控制节点功率的平面型,选择骨干节点的层次型,及常与层次型结合使用的启发机制.

本文作者对LEACH算法进行了改进,提出了一种基于QoS的拓扑控制算法(QBL),以减小能量消耗为主要目的,并改善端到端的延迟,提高传输可靠性.

第1节阐述分簇拓扑控制算法的相关工作,第2节介绍网络模型并提出问题,第3节描述QBL算法的设计和实现,第4节对两种算法进行仿真对比,第5节进行总结并指出以后的研究方向.

1 相关工作

层次型拓扑控制算法又称为分簇拓扑控制算法,把传感器节点分为簇头和成员节点,成员节点收集的数据由簇头进行融合后发送至基站.簇头与基站进行通信时,成员节点关闭通信模块以节约能量.该类算法扩展性好、可减少碰撞、有利于延长网络寿命、适用于大规模网络等优点,因此出现了很多相关研究.

LEACH算法[1-2]是最具代表性的分簇算法之一,它引入“轮”的机制,每一轮分为簇建阶段和稳定阶段.在建簇阶段,各节点在区间[0,1]内生成一个随机数,如果该随机数小于公式(1)中的T(n)值,则此节点宣布成为簇头.

(1)

其中p表示簇头的百分比,r表示当前轮数,G是最近1/p轮中还未当选过簇头的节点集合.

HEED[3]在簇头选举时考虑了节点剩余能量,把节点通信能耗作为主要参考因素,将节点邻居信息和节点密度作为次要参数.DESC[4]根据簇头节点剩余能量更新簇,主要参考了到邻居节点距离、邻居数目两方面的因素.DWEHC[5]中簇头的选举主要依据到邻居节点的距离和剩余能量,且簇内通信采用了分级的多跳方式.MOCA[6]采用分布式的多跳分簇,保证了簇之间一定程度的重合.ARC[7]主要针对网络连通性和覆盖度,也采用“轮”的机制,在每轮中根据需要调节占空比和节点发射功率来更新拓扑结构.CPCP[8]在选择簇头时更注重网络覆盖率,适用于监测区域需要长时间完全覆盖的应用.

另外,还有LEACH-G(LEACH based on “game of life”)[9]、LEACH-T(LEACH based on Three factor)[10]、S-HEED(Stable-based HEED)[11]等算法.

2 网络模型和问题描述

2.1 能耗模型和网络模型

采用文献[1-2]提供的能耗模型,若传感器节点A与B之间的距离为d,记A发送kbit的数据给B时消耗能量为ETx(k,d),而B接收来自A的kbit数据消耗的能量为:

(2)

ERx(k,d)=ERx-elec(k)=k·Eelec.

(3)

其中,Eelec表示电路的能量消耗;εfs和εmp分别表示采用自由空间和多路径衰减信道模型功率放大器需要的能耗;d0表示传输距离的阈值,当d

假设监测区域为M×M的二维正方形,并假设WSN具有如下性质:1) 全网只有一个基站,位置固定;2) 节点一旦部署完成将保持静止不动;3) 节点可依据与接收者的距离调整发射功率;4) 节点可根据接收信号的强度RSSI近似计算出与发送者之间的距离;5) 所有传感器节点同构,不能补充能量,不具备定位功能,但能融合数据,节点ID唯一;6) 基站具备较强的计算、存储、通信能力,电量可持续使用,且所有节点都可以接收到基站的发射信号.

2.2 问题描述

LEACH存在很多优点:它对节点的硬件要求较低,节点不用存储大量的信息;簇头随机选取,节点当选簇头的机会均等,一定程度上实现了能耗平衡;簇头选举不需要依赖全局信息或者上层控制,实现较为容易.但LEACH算法中也存在一些缺点:

1) 选举簇头没有考虑剩余能量.簇头节点担任工作较多,若能量少的节点当选簇头,容易耗尽能量而死亡,不利于延长网络寿命.

2) 由于簇头选取随机,容易导致成簇不均匀,且无规律可循,不利于网络能耗的均衡.

3) 采用簇间多跳的方式与基站通信时,距基站较近的簇头耗能更快(“热区问题”),因为它们既要融合本簇的数据又要转发其他簇的数据.

3 QBL算法

针对LEACH存在的不足,提出了一种基于服务质量的LEACH算法,记为QBL(QoS-Based LEACH).QBL算法以减小能量消耗为主要目的,旨在有效延长了网络寿命,并致力于改善端到端的延迟、传输可靠性等指标.QBL依然使用了“轮”的概念,每一轮依然分为簇的形成阶段Te和稳定阶段Ts.

(1)QBL算法选举簇头时依据的条件依次是:剩余能量较多,与邻居通讯能耗较少,距离基站较近.

(2)针对“热区问题”,QBL使距基站较近的簇头成员数目较少,以节约能量供转发数据使用,而距离基站较远的簇头成员数目则较多.

(3)为了进一步节约能量,QBL在每个簇内只选择部分成员完成检测任务,其余节点休眠.并在簇间通信阶段采用基于权重的最短路径算法,再次考虑了剩余能量和通信能耗两个因素.

QBL算法中相关消息类型定义如下:Gather_Msg:初始化时基站广播收集信息;Start_Msg:基站宣布开始竞选簇头;Reply_Msg:节点回复消息;Neighbor_Msg:节点收集邻居信息;Head_Msg:节点宣布自己是簇头;Join_Msg:节点请求加入某簇;Routing_Msg:建立簇间通信路径时簇头广播Level值.

3.1 网络初始化

在初始化阶段,基站和节点相互通信获得必要信息,为后续分簇提供基础.

1) 基站向所有节点广播Gather_Msg,节点Vi据此计算到基站的距离dtoBS(i),存储该值并回复Reply_Msg给基站.

(4)

式中N表示检测区域的节点总数,dtoBS(i)表示节点Vi到基站的距离.

LEACH算法最优簇头数目kopt的计算如公式(5)所示.

(5)

(6)

其中p表示簇头节点所占百分比,带入kopt,可进一步演变为:

(7)

3) 基站节点广播Start_Msg,将dtoBS和Dopt的值广播给所有节点,这样所有节点知道的信息包括:dtoBS、Dopt和dtoBS(i).

3.2 簇的生成

在建簇阶段,节点通过广播获得邻居节点信息,根据权重建成簇.

1) 节点计算dopt(i),并相互通信获得邻居信息.首先,计算最佳发射半径dopt(i),

(8)

其中

(9)

dopt(i)的计算以dtoBS为依据,当dtoBS(i)

然后,所有节点Vi以dopt(i)为发射半径广播Neighbor_Msg,广播内容包括ID、剩余能量Er(i).收到该广播的节点Vj回复Reply_Msg,并存储Vi到自己的距离ditoj,显然有ditoj=djtoi.接着节点Vi计算邻居节点剩余能量的平均值Eavg,

(10)

其中Nb(i)表示Vi的邻居数目.

图1 邻居节点关系图

对邻居的定义如图1所示,当节点Vj在节点Vi最佳发射半径dopt(i)范围内,而节点Vi不在节点Vj最佳发射半径dopt(j)范围内时,称Vj为Vi的邻居,也即Vi到Vj存在有向边.当节点Vj和Vk都在对方的最佳发射半径之内时,称Vj和Vk互为邻居.

2) 节点计算权重.节点求权重

(11)

权重wi包含we(i)、wnei(i)和wd(i) 3项因子,α、β和γ为3项因子的比重参数,α+β+γ=1.

记

图2 数据提交路径

we(i)考虑了节点剩余能量Er(i),剩余能量多的节点适合成为簇头.wnei(i)考虑了节点与邻居的位置关系,节点Vi越靠近区域中心位置,簇内通信能耗越少.wd(i)考虑了节点到基站的距离dtoBS(i),在如图2所示的区域中,显然D比C更适合当选簇头.当C做簇头时(图2中实线标注),A和B与基站通信,需要先将数据发送给C,然后再由C转发给基站或上层簇头,多走了很多“弯路”.

3) 依据权重竞选簇头.簇头竞选开始后,所有节点Vi等待时间T(i)之后,以dopt(i)为发射半径广播Head_Msg,宣布自己为簇头.

(12)

与节点权重wi成反比,故权重较大的节点等待的时间较短.如果Vi在T(i)之前已经收到Head_Msg消息则放弃竞选并等待.T(i)之后,若没有Vi收到广播,说明自己权重较大,则发送广播Head_Msg.因为节点要在Te时间内竞选出簇头并完成簇头对簇成员的工作分配,所以T(i)的值不能大于1/2·Te.

4) 簇头与簇成员相互选择形成簇.竞选失败的节点Vi一直等待,直到时刻1/2·Te+ΔT之后,根据收到的Head_Msg选择合适的簇头发送Join_Msg,若节点同时收到2个或2个以上簇头的消息,优先选择发射信号强度较强的簇头申请加入.簇头竞选成功后,对申请加入的节点进行安排.

3.3 簇内节点管理

覆盖率和最少活动节点数

(13)

其中ψ表示要求的覆盖率,rs表示节点的监测半径,该结果也可应用于对簇内成员节点的管理[13-14].

在QBL算法中,簇头收到Join_Msg消息后,首先计算k的值,显然面积S就是以簇头最佳发射半径覆盖的圆区域.然后,随机选择k-1个节点作为活动节点(簇头自身为活动节点).最后,簇头为每个活动节点建立TDMA方案,在回复允许成员加入时,告知活动节点被分配的时隙,告知其余节点在本轮中休眠.

3.4 簇间通信

簇头竞选成功后,建立到基站的多跳路径,该过程与簇头对成员节点的管理并发进行.在规模较大的网络中,簇头与基站通信采用多跳的方式更有利于节约能量[12].采用最短路径方法寻找簇头到基站的最优路径,QBL为每个簇头定义路由权值Level,

(14)

QBL算法中簇头到基站的路由算法描述如下:

首先,簇头Vi等待时间t(i)后以2·dopt(i)为发射半径广播Routing_Msg,广播内容包括ID、Level值,

t(i)=t·Level(i).

(15)

其中t随着进行轮数的增加逐渐减小,因为随着轮数的增加,节点剩余能量逐渐变小,而到基站的距离却不变,t值逐渐变小不会造成网络时延的增加.

簇头Vi收到簇头Vj广播Routing_Msg后,比较Level(i)与Li to j+Level(j)的大小,如果Level(i)>Li to j+Level(j)则将Level(i)的值更新为Li to j+Level(j),且记为父节点,记录其ID;否则Level值保持不变.

(16)

Level较小的簇头节点先进行广播,其他簇头收到Routing_Msg后自动更新自身的Level值,当所有簇头广播完后,每个簇头可得知父节点的ID.簇头Vi与基站通信时,先将数据提交给其父节点Vj,再由Vj提交给它的下一跳Vk,如此直至基站.

QBL算法流程如图3所示.

图3 QBL算法流程图

4 算法仿真和性能分析

利用OMNET++工具对QBL和LEACH算法进行仿真,来对比两种算法在簇的分布、网络寿命、节点耗能、时延、网络可靠性方面的表现.为了能够显示QBL算法不均匀分簇的效果,将基站设在监测区域一角.仿真区域为100 m×100 m,参数α、β、γ分别设为0.5、0.3和0.2;ψ的值设为1,节点初始能量Einit设为[0.45 J,0.5 J]之间的随机数,Eelec的值设为50 nJ/bit,εfs和εmp的值分别设为10 pJ/(bit·m2)和0.0013 pJ/(bit·m4),融合数据耗能设为5 nJ,数据包长度设为525 Bytes.

4.1 分簇仿真分析

当对100个节点进行仿真时(图4),在LEACH算法(图4a)中,簇头分布随机,成簇规模没有规律;而在QBL算法(图4b)中,距离基站近的簇区较小,距离基站远的簇区较大.当节点增加至200个时(图5),LEACH(图5a)和QBL(图5b)分簇情况区别更大.通过100个节点和200个节点的对比发现,在节点数目较多时,QBL分簇层次性更明显.

之所以能实现这种不均匀分簇,是因为QBL算法在簇头选举时给节点设置了不同的发射半径,从而得到不均匀分簇的结果.在节点数目更多规模更大的网络中,节点到基站的距离差异更大,不均匀成簇的层次性就会更加明显.

图4 100个节点时算法分簇情况

图5 200个节点时算法分簇情况

4.2 网络生存时间分析

从图6中可以发现,当节点数目为100时,对于第一个节点死亡的时间,LEACH大约在110 s,而QBL大约在120 s,比LEACH推迟了将近10 s.而对于节点几乎全部死亡的时间,LEACH是在150 s附近,QBL是在170 s之前,推迟了将近20 s,说明QBL算法有利于延长网络寿命.这是因为QBL充分考虑了节点能耗均衡性,在竞选簇头时考虑了节点剩余能量;且QBL采用不均匀分簇避免“热区问题”,更好地实现了能耗平衡.

图6 节点存活数量

4.3 网络能量消耗分析

如图7所示,随着节点数目的增加,两种算法平均每轮的能耗都在不断增加.在节点较少时,QBL的能耗比LEACH稍大,但总体上QBL较LEACH而言能耗更小,且随着网络规模的增大,QBL的优势更明显,说明QBL算法在规模较大的WSN中更具有优势.这是因为QBL在竞选簇头时,考虑了簇内通信能量消耗,并且在簇间通信时也将能耗考虑其中.但QBL算法在建簇阶段需要节点间相互通信收集邻居信息,需要额外消耗能量,故在规模较小的网络中优势不明显.

图7 能量消耗

当ψ值减小时,网络能耗随之减小,如图8所示.这是因为QBL采用了休眠机制,簇头只选择部分节点为活动节点,其余节点在本轮中休眠,ψ值越小休眠的节点越多,也就越节约能量.随着节点密度的增大,休眠的节点就会变多,节能效果就越明显.

4.4 网络时延分析

由图9可知,两种算法端到端的时延随着时间都逐渐减小,最后都趋于平稳,但QBL端到端的时延较小.因为QBL算法在竞选簇头时优先选择靠近簇区中心的节点,减小了簇内通信的时延;簇间通信时采用基于权重的最短路径算法,也有利于减小端到端的时延.

4.5 网络可靠性分析

本实验用丢包率衡量网络的可靠性,如图10所示.虽然在两种算法都采用TDMA和CMDA机制,在一定程度上避免了数据碰撞,但通信量、信号强度、时延、成簇大小等因素对丢包率都存在影响,丢包率没有一定的规律.但总的来说,QBL算法比LEACH算法丢包率更小.因为在QBL中簇间通讯路径得到了优化,簇内节点管理合理,减少了网络中路径不通的概率.其次QBL算法中网络寿命较长(见4.2),且时延较小(见4.4),这些因素使得它具有较小的丢包率.

图9 端到端的时延

图10 数据发送成功率

5 总结和展望

拓扑控制是WSN中的重要技术,如何有效利用资源提供良好的服务质量是该方向研究的重点.QBL算法主要完成的工作有:

1) 采用基于权重的簇头竞争机制,综合了剩余能量、与邻居的通信能耗、到基站的距离3个因素.

2) 采用不均匀分簇的策略,使距离基站远的簇区较大而距离基站近的簇区较小,更好地均衡节点能耗.

3) 簇头只选择部分成员完成检测任务,更加节能.并且簇间通信采用最短路径算法,再次考虑了通信能耗和剩余能量2个因素.

4) 在簇头分布、网络寿命、时延、可靠性等方面对QBL算法与LEACH算法进行仿真,证明QBL具有较好的性能.

在今后的研究工作中,需要合理地控制算法开销,提高算法普适性.WSN技术的发展,节点的定位功能、精确度等日益提高,也将提供有力的硬件支持,能更好地满足不同应用QoS的要求.

[1] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks [J].Wireless Communications IEEE Transactions on,2002,1(4):660-670.

[2] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol forwireless microsensor networks [C]//IEEE.System Sciences Proceedings of Annual Hawaii International Conference on.Hawaii:IEEE,2000.

[3] Younis O,Fahmy S.HEED:A Hybrid,Energy-Efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks [J].Mobile Computing IEEE Transactions on,2004,3(4):366-379.

[4] Neamatollahi P,Taheri H,Naghibzadeh M,et al.DESC:distributed energy efficient scheme to cluster wireless sensor networks [J].Wired/Wireless Internet Communications,2011,6649:234-246.

[5] Ping Ding J H A A C.Distributed Energy-Efficient Hierarchical Clustering for Wireless Sensor Networks [J].Distributed Computing in Sensor Systems,2005,3560:322-339.

[6] Youssef A,Younis M,Youssef M,et al.WSN16-5:Distributed Formation of Overlapping Multi-hop Clusters in Wireless Sensor Networks [C]//IEEE.Global Telecommunications Conference 2006,San Francisco:IEEE,2006:1-6.

[7] Xu N,Huang A,Hou T,et al.Coverage and connectivity guaranteed topology control algorithm for cluster-based wireless sensor networks [J].Wireless Communications & Mobile Computing,2012,12(1):23-32.

[8] Soro S,Heinzelman W B.Cluster head election techniques for coverage preservation in wireless sensor networks [J].Ad Hoc Networks,2009,7(5):955-972.

[9] Yang Y J,Jia B,Wang J.An Improved Algorithm for LEACH Protocol in Wireless Sensor Network [J].Journal of Beijing University of Posts & Telecommunications,2013,36(1):105-109.

[10] Li Y,Sun L J,Wang R C,et al.Improvement of LEACH Algorithm in Wireless Sensor Network [J].Journal of Computer Research and Development,2011,48(Suppl):131-134.

[11] Yang M N,Yang D,Huang C.An improved HEED clustering algorithm for Wireless Sensor [J].Journal of Chongqing University,2012,35(8):101-106.

[12] Rosenberg V M A C.Design guidelines for wireless sensor networks:communication,clustering and aggregation [J].Ad Hoc Networks,2004,2(1):45-63.

[13] Choi W,Das S K.Trade-off between coverage and data reporting latency for energy-conserving data gathering in wireless sensor networks [C]//IEEE.Mobile Ad-hoc and Sensor Systems,2004 IEEE International Conference on,Fort Lauderdale:IEEE,2004.

[14] Liu M,Cao J N,Chen G H,et al.EADEEG:An Energy-Aware Data Gathering Protocol for Wireless Sensor Networks [J].Journal of Software,2007,18(5):1092-1109.

[15] 孙彦景.无线传感器网络分簇与虚拟骨干技术 [M].徐州:中国矿业大学出版社,2010.

(责任编辑：包震宇)

An improved algorithm of LEACH based on QoS

YANG Haijun, LI Luqun

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

Based upon clustering LEACH algorithm,a QBL(QoS-based LEACH)algorithm is proposed in this article aiming at improvement in energy saving,network delay,life time and reliability.The QBL algorithm,armed with new algorithm of weighting in selecting cluster head as well as uneven clustering strategy,has only part of members within the cluster to be assigned to fulfill monitoring tasks,and adopts shortest path of weighting methods in inter-cluster communication.Simulation results show that the QBL algorithm has turned out remarkable performance in improving network delay,lifetime and reliability in simulation experiments.

WSN; topology control; clustering; QoS

2015-04-22

李鲁群,中国上海市徐汇区桂林路100号,上海师范大学信息与机电工程学院,邮编:200234,E-mail:liluqun@gmail.com

TP 393

A

1000-5137(2016)05-0527-09

10.3969/J.ISSN.1000-5137.2016.05.003