一种基于融合器的多跳能量均衡算法

2017-02-09张净霞陈俊杰

东南大学学报（自然科学版） 2017年1期

关键词：能量消耗路由生命周期

张净霞陈俊杰

(东南大学仪器科学与工程学院, 南京 210096)

一种基于融合器的多跳能量均衡算法

张净霞陈俊杰

(东南大学仪器科学与工程学院, 南京 210096)

为了解决现有的分簇算法能量消耗不均衡问题,提出了一种新的基于融合器的多跳能量均衡 (MEB) 算法．该算法采用定时器并且考虑节点的剩余能量来优化簇头选举,通过选举簇中最多能量的节点作为融合器,对簇头转发的传感数据进行数据融合,然后通过由融合器构建的多跳路由树发送到基站．该算法同时达到了簇内和簇间的能量均衡．仿真结果表明,MEB算法第1个节点死亡的时间比LEACH算法延长了80%左右,比TB-LEACH算法延长了60%左右．MEB算法第1个节点死亡到最后1个节点死亡经历的时间非常短．因此,MEB算法实现了整个网络的能量均衡,提高了网络的稳定度,延长了网络的生命周期．

无线传感器网络;能量均衡;融合器;多跳

在无线传感器网络中,传感节点的能量有限,因此需要仔细地对应用和协议进行设计,通过优化能量消耗来延长网络的生命周期[1]．分簇算法是一种设计无线传感器网络中各种能量高效的协议．LEACH(low-energy adaptive clustering hierarchy)算法是分簇算法中最广泛使用的算法[2]．LEACH算法通过将传感器网络划分成若干个簇,由簇头负责簇内数据的融合和转发,所以LEACH算法能够优化网络的能量消耗来延长网络的生命周期．由于簇头在传感器节点中间随机轮转,簇头比普通传感节点能量消耗要多,因此会造成节点过早死亡．HEED(hybrid energy-efficient distributed clustering)协议是一种分布式分簇算法[3],该算法根据节点的剩余能量和节点等级来选择簇头．HEED算法是用来设计需要延长网络生命周期、规模扩展、容错和负载均衡的传感器网络协议．

文献[4]通过簇头重构来实现负载均衡,簇头重构就是本轮簇头按照一定的规则产生下一轮簇头来实现簇头在轮间的迁移,从而使得簇头均匀地分布在网络中,延长了网络的生命周期．文献[5]提出了DSBCA(balanced clustering algorithm with distributed self-organization)算法,该算法通过考虑节点连通密度和位置形成能量均衡簇,但需要利用RSSI(received signal strength indicator)计算节点与基站间的距离．文献[6]提出了CATD(clustering algorithm based on time delay)算法,该算法通过定时器的时间延迟使得簇头数量优化和在网络中均匀分布,通过多跳机制构成了一个路由树转发数据,该算法节省了网络能量，均衡了网络负载,延长了网络的生命周期．文献[7]提出了OLBHC(optimal load balancing hierarchical clustering)路由协议,OLBHC能够用均衡方法降低能量消耗,利用标记矩阵储存邻居节点的连接状态,然后应用优化算法选择网络中最优簇，该算法延长了节点的平均能量周期．文献[4-7]利用簇头均匀分布,通过构建均衡簇和多跳方式实现负载均衡．

文献[8]提出了TB-LEACH(time-based cluster-head selection algorithm for LEACH)算法,该算法利用定时器发送广播信息来竞争簇头,通过优化簇头数量来实现簇间能量均衡,但是TB-LEACH竞选簇头时没有考虑节点的剩余能量．文献[9]提出了LEACH-B(LEACH-balanced)算法,该算法通过2次选择簇头来优化簇头数量,平衡了系统能量消耗,延长了网络生命周期．文献[8-9]通过簇头数量优化来实现能量均衡,延长了网络的生命周期．文献[10]提出了IBLEACH(intra-balanced LEACH)协议,该协议考虑帧间的能量均衡,通过分配簇头的负载到簇内的普通节点,延长了整个网络的生命周期．

上述的分簇算法中,数据融合都是在簇头进行,数据传输都是基于单跳或者构建了基于簇头之间的多跳路由树,这使得网络中所有节点之间的能量消耗并不均衡．为了实现网络所有节点之间的能量消耗均衡,同时克服TB-LEACH选择簇头时不考虑剩余能量的缺陷,本文提出了一种新的实现能量均衡的多跳能量均衡(MEB)算法．MEB算法基于TB-LEACH算法选举簇头,同时考虑了节点的剩余能量．为了降低簇头的负担,选举簇中能量最多的节点作为融合器进行数据融合．最后,构建基于融合器的多跳路由树,将采集的数据传输到基站．

1 无线电能量模型

为了分析MEB算法的能量消耗,本文采用与LEACH算法相同的无线电能量模型．假设节点传输l个比特信息,发射器和接收器通信距离为d,所消耗的能量为

(1)

ERx(l)=lEelec

(2)

节点对l个比特的数据进行融合,所消耗的能量为

EDA(l)=lEDA

(3)

式中,EDA为每个比特的数据融合所消耗的能量．

从无线传感器网络的节点感知、处理和数据通信3方面来看,节点消耗的能量主要集中在数据通信上,而发送信号消耗了通信的大部分能量．发送信号所消耗的能量与节点之间的距离d有很大的关系,当d≤d0时,节点功率放大器采用自由空间模型,节点消耗的能量较少．当d>d0时,节点功率放大器采用多径路径模型,节点消耗的能量较多．

2 MEB算法

MEB算法的执行过程由轮组成,每轮分为簇建立阶段和稳定阶段，与LEACH,TB-LEACH算法的簇建立阶段类似,MEB算法的簇建立阶段将网络中的节点划分为若干个簇,每个簇的节点选举出自己的簇头．MEB算法对TB-LEACH算法簇头选举的函数进行了优化．在簇稳定阶段,非簇头节点按照簇头发送给自己的TDMA调度,在自己的时间片内发送数据给簇头．簇头接收的数据经过处理(数据融合),发送数据给基站．MEB算法在簇稳定阶段与LEACH,TB-LEACH算法有2点不同:①MEB算法增加了数据融合节点(融合器)的选择,融合器是指包括簇头在内的剩余能量最多的簇内节点;②LEACH,TB-LEACH算法是单跳传输,簇头直接发送数据给基站,而MEB算法是多跳传输,构建了基于融合器的多跳路由树．

2.1 簇头的优化选择

在LEACH算法中,簇头的选择基于阈值与一个随机数的比较．TB-LEACH算法为了优化簇头数量,选择簇头时不再基于阈值,而是基于一个时间延迟的定时器．每个节点都利用定时器发送广播信息来竞争簇头,发送广播信息的时间间隔是由定时器随机产生．由于定时器的时间短,因而具有最小随机数的节点成为簇头的概率较大．TB-LEACH算法定时器产生随机数的公式为

Tt=rand(0,1)

(4)

根据文献[2]的证明,簇的数量太多或者太少,每轮消耗的平均能量都较大,因此簇头数有一个优化值kopt．在TB-LEACH算法中,当竞争簇头的个数k>kopt时,所有的定时器停止,节点不再竞争簇头．

由式(4)可知,TB-LEACH算法选择簇头是随机的,不考虑节点的当前能量,这样能量少的节点可能频繁地成为簇头而导致能量耗尽死亡．在一些节点死亡后,系统变得不稳定,可靠性降低．因此簇头的选择需要考虑节点的剩余能量,这样簇头选择在能量较多的节点之间轮转,使得同一时刻节点的能量差异减小,使节点的能量负载均衡,节点能够在理想情况下同时死亡,提高了系统的可靠性．因此MEB算法对TB-LEACH算法的簇头选举方法进行了改进,使定时器产生的随机数包含节点的剩余能量信息,节点剩余能量越多，定时器产生的随机数越小,成为簇头的概率越大,则式(4)改进为

(5)

式中,α为时间调节因子;R为节点的剩余能量;I为节点的初始能量;rand(0,β)为最佳簇头调节因子．rand(0,β)在产生的随机数相同时,调节簇头的个数．本算法中α=1,β=0.000 01．同样地,在MEB算法中当竞争簇头的个数k>kopt时,所有的定时器停止,节点不再竞争簇头．

2.2 融合器的选择

融合器的选择是在非簇头节点发送数据给簇头节点阶段进行的．非簇头节点在TDMA调度分配给自己的时隙时,发送采集数据和剩余能量信息给簇头,簇头比较自己和所有成员节点的剩余能量信息,选举出能量最多的节点作为融合器．如果簇头的剩余能量比所有成员节点的剩余能量多,那么簇头自身作为融合器．如果选择簇头节点作为融合器,那么MEB算法融合器选择方法与LEACH,TB-LEACH算法相同．如果选择非簇头节点作为融合器,那么在LEACH 和TB-LEACH算法中,数据稳定阶段簇头的能量消耗为

(6)

式中,N为网络中所有节点数量;dtoBS为从簇头到基站的距离．

在LEACH,TB-LEACH和MEB算法中,没有竞选成为融合器的普通非簇头节点的能量消耗为

(7)

式中,dtoCH为非簇头节点到簇头节点之间的距离.假设基站离传感器网络较远,那么dtoBS>dtoCH,进而推导出ECH>Enon-CH．消耗在簇头的能量比消耗在非簇头的能量大得多,因此,为了均衡网络负载,需要降低簇头的能量消耗．

在MEB算法中,数据稳定阶段簇头的能量消耗为

(8)

在MEB算法中,融合器的能量消耗为

(9)

显然有EDA>Enon-CH,融合器比普通非簇头节点消耗的能量多,因为它承担了数据融合和中转的作用,融合器分担了簇头的能量消耗,均衡了网络负载．

2.3 基于融合器的多跳路由树

多跳传输是实现网络能量均衡的一种重要方法,融合器直接将数据转发给基站会消耗自身较多的能量,因此融合器选择基站方向距离自己最近的融合器作为下一跳节点,而离基站最近的融合器直接将数据传送给基站．多跳传输将长距离传输分为短距离各个分段传输,每次数据转发都是短距离传输,结合第1节的无线电能量模型,节点采用的是自由空间模型,而接收信息所耗费的能量较少,所以多跳传输可以减少能量消耗,同时均匀地消耗网络能量．

多跳传输路由树的构建如图1所示．由图中可以看出，本文算法将基于簇的拓扑和基于树的拓扑相结合,从而构建了数据传输的最佳方案．

图1 多跳融合器路由树的构建

3 仿真结果及分析

为了评估算法的性能,采用软件OPNET14.5仿真了MEB,LEACH和TB-LEACH算法．网络规模为100 m×100 m,基站的位置为(50,175),100个节点在网络中随机分布,如图2所示．普通节点的初始能量为0.5 J,基站的能量不受限．其他参数的设置如表1所示．

图2 100个节点的随机网络

参数参数值MAC协议IEEE802．11DCF协议发射功率/W0．005信道模型(d≤d0)自由空间模型信道模型(d>d0)多径模型数据包大小/bit4000控制包大小/bit200最优簇数量kopt5运行无线电路耗能Eelec/(nJ·bit-1)50自由空间路径εfs/(pJ·bit-1·m-2)10多径路径εmp/(pJ·bit-1·m-4)0．0013每个信号的融合耗能EDA/(nJ·bit-1)5距离阈值d0/m87

能量效率是对传感器网络的重要度量,主要通过网络能量消耗的均匀性和网络的生命周期来表示．通常把第1个节点死亡时间作为网络生命周期最重要的衡量指标．

图3为分布在网络区域内的节点死亡时间三维趋势图,反映了网络内节点的负载均衡程度．x,y轴所决定区域的节点按图2随机分布,z轴反映了节点的死亡时间．节点死亡时间越接近,所有节点死亡时间的偏差越小,则网络内节点的能量消耗越均匀,负载均衡程度越好．图3中曲面表面变化趋势较小,则较为平坦．

图3(a)为LEACH算法的所有节点死亡时间三维分布趋势图．从图中可以看出,第1个节点死亡时间大约为800轮,远离基站的节点比靠近基站的节点死亡早.由于簇头节点选择的随机性和单跳传输的原因,LEACH算法节点死亡的先后次序波动非常大,趋势较为陡峭,整个网络节点能量消耗极为不平衡．

图3(b)为TB-LEACH算法所有节点死亡时间三维分布趋势图．与LEACH算法相比,TB-LEACH算法的簇头数量已经优化,网络能量均衡程度有了很大的提高,节点死亡的先后次序较为平缓,同时第1个节点死亡延长了100轮左右．与LEACH算法相似的是,远离基站的节点比离基站近的节点死亡早．

(a) LEACH算法

(b) TB-LEACH算法

图3(c)是MEB算法的所有节点死亡时间的三维分布趋势图．从图中看出,与前2种算法相比,节点的死亡次序在小范围内波动,非常平缓,这反映了本算法的网络负载均衡程度非常好．第1个节点在1 460轮左右死亡,网络的稳定程度较前2种算法提高了很多．

图4比较了3种算法的网络生命周期．从图中可以看出,MEB算法第1个节点的死亡时间比LEACH 算法延长了80%左右,比TB-LEACH算法延长了60%左右．MEB算法中50%节点的死亡时间比LEACH算法延长了40%左右,比TB-LEACH算法延长了35%左右．从图中也可以看出,MEB算法第1个节点死亡到最后1个节点死亡经历的时间非常短,网络能量消耗很均匀．

图4 系统的网络生命周期

采用MEB算法能够使得能量消耗较为均衡,是因为基于节点剩余能量的簇头选择使得能量多的节点有更高的概率成为簇头．能量较少的节点成为非簇头节点,消耗的能量少,延迟了能量少节点的死亡时间．融合器的选择降低了簇头的能量，簇头不会很快死亡．另外,多跳路由使得簇头与簇头、簇头与基站之间的通信采用自由空间模型,使得离基站较远的簇头的能量消耗降低．而LEACH,TB-LEACH算法采用单跳路由,离基站较近的节点死亡比较早,因为这些远离基站的节点担当簇头的过程中采用了多径模型,节点能量衰减较快,而离基站较近的节点担当簇头的过程中采用的是自由空间模型,能量消耗较少,节点最后死亡．

4 结语

本文提出了一种基于融合器的多跳能量均衡MEB算法．该算法通过优化簇头选举和基于融合器的多跳传输的机制,最终实现了网络内的能量均衡．仿真结果表明,与LEACH和TB-LEACH算法相比,MEB算法均衡了网络节点的能量消耗,延长了网络的生命周期．所以,在网络稳定度要求较高的场合,MEB算法具有较高的应用价值．本文假设节点初始能量相同,研究的是同构网络的能量高效问题．如何实现异构网络的能量高效和动态重构性是下一步的工作．

References)

[1]Tyagi S, Kumar N. A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks [J].JournalofNetworkandComputerApplications, 2013, 36(2): 623-645. DOI:10.1016/j.jnca.2012.12.001.

[2]Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks [J].IEEETransactionsonWirelessCommunications, 2002, 1(4): 660-670. DOI:10.1109/twc.2002.804190.

[3]Younis O, Fahmy S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks [J].IEEETransactionsonMobileComputing, 2004, 3(4):366-379. DOI:10.1109/tmc.2004.41.[4]Kim N, Heo J, Kim H S, et al. Reconfiguration of clusterheads for load balancing in wireless sensor networks [J].ComputerCommunications, 2008, 31(1): 153-159. DOI:10.1016/j.comcom.2007.10.039.

[5]Liao Y, Qi H, Li W. Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks [J].IEEESensorsJournal, 2013, 13(5): 1498-1506. DOI:10.1109/jsen.2012.2227704.

[6]Shang F. A multi-hop routing algorithm based on integrated metrics for wireless sensor networks [J].AppliedMathematics&InformationSciences, 2013, 7(3): 1021-1034. DOI:10.12785/amis/070321.

[7]Wang T S, Zhang G X,Yang X C, et al. Hierarchical clustering routing protocol based on optimal load balancing in wireless sensor networks [J].LectureNotesinComputerScience, 2013, 8299:227-240. DOI:10.1007/978-3-642-45293-2_17.

[8]Hu J, Jin Y, Dou L. A time-based cluster-head selection algorithm for LEACH[C]//IEEESymposiumonComputersandCommunications. Marrakech, Morocco,2008:1172-1176.

[9]Tong M, Tang M. LEACH-B: An improved LEACH protocol for wireless sensor network[C]//6thInternationalConferenceonWirelessCommunicationsNetworkingandMobileComputing. Chengdu, China, 2010:1-4.

[10]Salim A, Osamy W, Khedr A M. IBLEACH: Intra-balanced LEACH protocol for wireless sensor networks [J].WirelessNetworks, 2014, 20(6):1515-1525. DOI:10.1007/s11276-014-0691-4.

A multi-hop energy balancing algorithm based on aggregator

Zhang Jingxia Chen Junjie

(School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China)

To resolve the energy unbalancing problem in the current clustering algorithms, a new multi-hop energy balancing (MEB) algorithm based on the aggregator is proposed. The proposed algorithm utilized timers and considered node residual energy to optimize the cluster head selection. It selects the maximum residual energy node from the intra-cluster nodes as the aggregator, fuses data from the sensing data that cluster heads relay and then forwards data to the sink through the multi-hop routing tree constructed by the aggregators. The algorithm simultaneously realized intra-cluster and inter-cluster energy balancing. The simulation results show that the MEB algorithm can enhance first node dies (FND) by about 80% compared with the low-energy adaptive clustering hierarchy (LEACH) algorithm and by about 60% compared with the time-based cluster-head selection algorithm for LEACH (TB-LEACH). The MEB algorithm costs very short time from the death of the first node until the death of the last node. Therefore, the MEB algorithm achieves energy balancing for the entire network, improves the network stability, and prolongs the network lifetime.

wireless sensor networks; energy balancing; aggregator; multi-hop