基于能量异构的WSN多链路算法*

王卫星　黄虹　孙道宗　李亮斌　胡子昂

(1.华南农业大学 电子工程学院, 广东 广州 510642; 2.华南农业大学 南方农业机械与装备关键技术省部

共建教育部重点实验室, 广东 广州 510642)

基于能量异构的WSN多链路算法*

王卫星1,2黄虹1孙道宗1,2李亮斌1胡子昂1

(1.华南农业大学 电子工程学院, 广东 广州 510642; 2.华南农业大学 南方农业机械与装备关键技术省部

共建教育部重点实验室, 广东 广州 510642)

摘要：为了有效均衡网络能耗,提升网络生命周期,提出了一种基于能量异构的多链路算法EHMCA.该算法采用两级异构的网络结构,网络区域被划分为若干等宽子区域,根据各层间距确定最优簇域半径,簇域内根据高级节点的能量和全网平均能量来确定簇首的阈值,各层之间采用簇间多跳路由并行传输机制,因此，在整个网络区域，簇首通过层间多跳多链路并行传输方式和最优簇域内单跳传输的模式将数据传送给基站.算法仿真结果表明,EHMCA的网络性能明显优于其他3种算法,从而验证了EHMCA算法的有效性和实用性.

关键词：无线传感器网络;网络分层;能量异构;分簇;多链路

无线传感器网络(WSN)已经广泛应用于灾难预测、安全管理、环境监测、交通管制以及精细农业的数据采集和处理等方面[1-2].与传统的传感器网络相比,WSN具有以下特点和要求[3-5]:①传感器节点成本低、部署密集、能量受限;②延长网络生命周期,降低节点能耗,提高传输效率;③根据节点初始能量的不同,WSN可分为同构传感器网络和异构传感器网络.由于WSN中的节点资源有限,要求节点能够智能地控制拓扑结构,保持数据传输的完整性,增加节点能力异构.因此,高可靠性、低开销、易于维护的路由算法能够有效地优化网络性能,拓展WSN的应用领域[6-9].针对WSN中通信能耗大、传输时延长、数据冗余以及传统同构传感器网络无法应用在节点能力异构网络等缺陷,文中提出了一种基于能量异构的多链路算法(EHMCA).首先采用两级异构的网络结构,将WSN分为两层结构,簇首成为网络架构的上层,普通节点成为网络架构的底层.然后以基站(BS)为中心将网络区域划分为若干等宽子区域,同时为网络中的每个节点分配唯一的层号和节点编号,根据各层间距确定最优簇域半径,簇域内根据高级节点和全网平均能量确定阈值,并根据阈值选择簇首,簇首广播当选簇头的消息,簇域内成员节点以单跳方式加入该簇;远离基站的层内簇首采用簇间多跳路由并行传输机制向下一层簇首传送数据.因此,整个网络形成了簇首通过层间多跳多链路并行传输方式和最优簇域内单跳传输的模式将数据传送给基站.最后通过仿真验证EHMCA的性能和有效性.

1相关研究

无线传感器网络根据网络拓扑结构可分为平面路由算法和分簇路由算法，平面路由算法主要包括泛洪算法、闲聊算法[10]，其特点是节点功能相同、结构简单；分簇路由算法包括LEACH算法[11]、LEACH-C算法[12]、HEED算法[13]等，其特点是节点可拓展性强、结构复杂.基于数据融合技术(如多传感器的信息融合技术[14])的路由算法的应用更为广泛.WSN低功耗单跳分簇路由算法LEACH是基于数据分层的路由算法,其结构如图1所示.LEACH算法以动态“轮”为工作周期,每轮选择新的簇首,通过单跳方式直接与基站通信,并运用数据融合技术来减少数据的发送量,从而将网络的能量损耗均匀分布在所有节点上.EACH算法中节点到基站的数据传输包括簇的建立和数据就绪两个阶段,节点随机选举簇首、簇成员节点根据事先设置的时分复用(TDMA)时间表进行数据采集并传输给簇首,簇首将接收到的数据融合后直接传输给基站,在一定程度上减少了通信能耗,均衡分担了路由任务,延长网络寿命.LEACH算法簇首选举的随机性导致了簇首分布不均匀、网络整体负载不均衡、未考虑节点的剩余能量,使得单跳模式下的LEACH算法只适用于较小的网络规模,不适用于大规模网络及突发性的通信网络.

图1　LEACH算法的分簇结构Fig.1　Clustering structure of LEACH algorithm

PEGASIS[15]是传感信息系统中一种高效收集能量信息的算法,由LEACH算法发展而来,其结构如图2所示.为避免频繁地选举簇首,PEGASIS算法采用了贪婪算法,将网络中的所有节点组织成一条链,形成一个簇首,通过有效的链式结构来减少簇内直接与基站通信的节点数量,均衡网络能耗.采用PEGASIS算法的网络中传感器节点是同构且静止的,节点通过信号强弱和能量大小来确定其位置信息,相邻节点了解彼此之间的位置信息,并选择距离最近的邻节点作为下一跳节点,靠近基站的节点被选为簇首节点,采用最佳链路进行数据传递,利用数据融合技术来减少数据的发送和接收,使得其网络生命周期优于LEACH算法.然而,固定不变的簇首是整个通信过程中的瓶颈,链路过长导致数据传输时延.

图2　PEGASIS算法的链路传输结构Fig.2　Chain-transmission structure of PEGASIS algorithm

HEE-PEGASIS算法[16]的网络节点分布如图3所示,该算法结合了LEACH算法的簇首选择及网络区域划分和PEGASIS算法的链路传输数据的思想,网络区域内的节点采用贪婪算法的思想,以距离基站最远的节点为链路的链尾,距离基站最近的节点为链路的链首,根据节点自身位置信息和邻节点的位置信息依次加入该链路,直到网络中所有节点都加入该链路.HEE-PEGASIS算法缩短了节点与簇首之间的通信距离,簇间建立以基站为树根的层次路由树结构来进行数据传输,以固定轮次进行簇的重组.其优势在于利用静态分簇优势减小开销、采用多跳方式向基站发送数据以及将整个区域分成多个等宽区域以节省簇首节点的能量消耗,提高节点能量的有效性.

图3　HEE-PEGASIS算法的网络节点分布Fig.3　Distribution of network nodes of HEE-PEGASIS algorithm

2EHMCA的网络模型

2.1 　EHMCA的提出

LEACH算法中簇首与基站的直接通信增加了网络能耗和数据传输时延,PEGASIS算法中链首的唯一性导致链首节点能耗过大,缩短网络生命周期.为此,文中提出了基于能量异构的WSN多链路算法(EHMCA),该算法包括簇的建立和稳定传递两个阶段.根据WSN的特点,文中主要通过以下措施来优化算法的网络性能,包括均衡节点能量、拓展网络规模、减少通信能耗、延长网络寿命.

(1)划分节点层次区域.将网络区域划分为若干均衡子区域,以汇聚节点为中心等间距沿纵轴将网络区域划分为K层,同时为每层中的每个节点分配唯一的层号和节点编号,节点随机分布于K个等宽子区域内.

(2)选择簇首.假设网络是两级异构的,网络中的节点分为普通节点和高级节点,普通节点的初始能量配置低于高级节点.文中根据子区域中节点层次的坐标、高级节点的剩余能量、最优簇域半径和节点自身坐标来确定该层的簇首,簇首根据最优簇域通信半径进行广播,使相应的成员节点建立连接并组成簇.

(3)搭建簇间路由.网络中簇首节点了解相邻层簇首的位置信息,第k层簇首节点通过比较与第k-1层簇首节点的距离和剩余能量信息来选择下一跳链路节点.在链路选择传输过程中,在相邻下一跳簇首节点处进行数据融合,簇首节点通过多跳链路并行传输方式将数据传输给汇聚节点,从而完成整个网络的搭建.

(4)组建网络模型.在100×100的网络区域中,节点随机分布于K层中,网络区域内的节点根据位置信息和剩余能量信息来确定分簇的结构,根据层间距确定簇首传输的路径,从而确定节点的网络区域模型,如图4所示.

图4　EHMCA的分簇及传输结构Fig.4　Clustering and transmission structure of EHMCA

2.2　算法分析

2.2.1能量模型

假设所选取的M×M网络是静态部署的网络,网络中节点能量是异构的,基站远离网络区域且具有充足的能量.在WSN中,可根据发射端和接收端的距离d来采用不同的能耗模型[17]:

(1)

式中,Etx为节点发送L比特的数据到距离d的位置所消耗的能量,由发射电路损耗的能量Eelect和功率放大损耗能量εfs、εmp组成.若传输距离d

(2)

第i层成员节点j的数据传输能耗为

(3)

传输总能耗为

(4)

由式(4)可知,ri越大,簇域面积越大,簇内节点传输的总能耗越大,也就是该层的总能耗越大.因此,只有簇半径取最小值M/(2K)时,该层的能耗才最小,从而K层簇内成员节点的能耗才最小,达到均衡网络能耗的目的.

在EHMCA中,传感器节点的能量是异构的,高级节点消耗的能量要超出普通节点消耗的能量,节点传输数据到基站所消耗的能量就是整个网络消耗的能量[18].设离基站最远的为第K层,第K层簇首节点CHK与基站的距离为dK(dK>d0),第K-1层簇首节点CHK-1与基站的距离为dK-1(dK-1

ECHK=(N/K-m)LEelect+(N/K-m+1)LEDA+

(5)

CHK-1向第K-2层簇首节点CHK-2发送数据的距离为rK-1=dK-1-dK-2(rK-1

ECHK-1=(N/K-m)LEelect+(N/K-m+1)LEDA+

(6)

ECH1=(N/K-m)LEelect+(N/K-m+1)LEDA+

(7)

第K层成员节点的总能耗Enon为发送数据给该层簇首节点的能耗,即

Enon=(N/K-m)LEelect+Lεfsrmin,rmin

(8)

节点均匀分布在网络区域中,假设传感器网络每轮消耗的能量Eround包括K层簇内成员节点向簇首节点发送数据的总能耗、K层簇首节点接收成员节点的总能耗、相邻层簇首节点之间并行链路传输的总能耗、数据融合的总能耗、第1层簇首节点向基站发送数据的能耗,即

Eround=KEnon+mECHK+(K-1)mECHK-1

(9)

Eround=(2N-2Km+K-1)LEelect+

(N-Km+1)LEDA+

(10)

2.2.2簇的建立

初始阶段簇的建立及簇首的选举原则应该考虑簇首选举概率、剩余能量、簇域半径大小.在异构网络中,节点的初始能量不同使得能量较多的节点当选为簇首,簇域半径的限制使得簇首分布更加均匀,网络负载更加均衡,网络生命周期更加延长.假设网络被平均分为K层,每层区域面积相等,由于根据区域面积大小来确定该区域中簇的个数,因此每层区域中簇的个数也相等.最优簇个数Nopt为

Nopt=Sopt/Sk

(11)

式中, Sk为区域k的面积, Sopt为最优面积.

由文献[11]可知LEACH算法的最优簇个数：

(12)

(13)

当节点数N=100、区域边长M=100、K=4时,可得到最优簇个数Nopt=5,从而得到最优簇域面积

簇首的选举:根据LEACH-E算法的思想[19-20],考虑平均能量和异构网络中剩余能量最大的因素,将能量比例较低的节点优先当选为候选簇首.LEACH-E算法选举簇首的阈值T(n)的计算式为

(14)

式中, P为簇首占所有节点的百分比(即当选为簇首的概率), R为网络中节点当前循环的轮数, G为网络中在1/P轮还未当选为簇首的所有节点集合, Er(i)为第i个节点的剩余能量, E(R)为第R轮网络的平均剩余能量.

LEACH-E算法的阈值计算综合考虑了节点的剩余能量和位置因素,有效改进了簇首的选举和分布不均等问题.根据LEACH-E算法的思想,EHMCA为异构网络中的高级节点和普通节点分别设置不同的阈值,采用初始能量较高的节点和平均剩余能量高的节点优先当选为簇首的方法,使簇首分布均匀,从而均衡网络能耗.

选取簇首后进入成簇阶段.第k层簇首节点CHk广播自己成为簇首的消息(该消息包含唯一标识该簇首的IDk、发送信号功率强度值和非簇首节点接收到的强度值),在第k层区域内的成员节点选择本区域内离自己最近的簇首并发送加入信息,收集完加入信息后,簇首节点根据簇域内节点的位置信息释放TDMA时序给簇内成员节点,簇内成员节点根据接收到的TDMA时序信息发出答应加入该簇的请求,直到所有成员节点都加入到该簇为止.至此,簇的建立基本完成.

2.2.3数据传输

当簇建立完成后,簇内成员节点根据时间序列向簇首发送数据,簇首接收并融合成员节点发来的数据,然后按照多跳传输方式向基站发送数据.簇首之间的多跳路径必须考虑每层区域内簇首节点的剩余能量和层间簇首的距离,从而形成了第K层簇首到基站的最佳路径.多跳路径的搭建步骤如下:

(1)将网络区域均匀划分为K层,每层簇首配对相应的层ID信息.

(2)第k层簇首节点CHk广播消息发送给第k-1层的簇首节点CHk-1,该消息包括第k层簇首的剩余能量信息、层ID信息、坐标.

(3)第k-1层的簇首节点CHk-1接收到CHk的消息后,将包含CHk-1的剩余能量、层ID和坐标的消息回传给CHk.

(4)CHk分别统计第k-1层簇首的回传信息,选择剩余能量最多、层间距离最近的簇首节点CHk-1作为下一跳节点.

(5)CHk-1收到确认消息后,融合第k-1层簇首数据和自身数据,再将融合数据传输给第k-2层的簇首节点CHk-2,依此类推完成下一跳节点的搭建,直到K层的簇首节点都将数据传送至基站为止.

3仿真结果与分析

3.1　性能指标

为验证EHMCA的有效性及在异构网络中的优越性,采用EHMCA、LEACH、PEGASIS、HEE-PEGASIS算法进行仿真,并比较其如下性能指标:①网络生命周期,指传感器节点从开始工作到死亡的时间段；②数据传输量,指随着网络时间的推移,基站接收和传输的数据量；③网络寿命,指网络区域中节点开始采集信息直至网络不能为观察者提供需要的数据为止所持续的时间；④稳定周期,指WSN节点开始采集数据直至出现第1个节点死亡时的时间.

3.2　仿真参数

为验证EHMCA的优劣性,假设网络仿真环境为M×M,基站远离网络区域,基站通过广播根据区域内接收到的信号强弱来判断节点的位置信息.由于将网络平均分为K层,故基站接收到的信号强弱也分为K个等级,在网络区域内距离基站最远的层内节点信号最弱,距离基站越近的节点信号越强,不同层次区域内根据信号强弱的不同来随机部署节点的位置,N个节点随机分布于层次区域内.在异构网络中,节点的初始能量不同,高级节点和初级节点的部署存在一定的比例,使得网络中簇首节点的网络负载更加均匀,高级节点数为mN(0

3.3　仿真结果分析

EHMCA和LEACH、PEGASIS、HEE-PEGASIS算法的网络生命周期和向基站传输的数据量如图5所示,网络寿命(运行轮数)如表1所示.从图5(a)可以看出,EHMCA的生命周期最长,明显长于其他3种算法.从网络中所有节点死亡的轮数来看,EHMCA在第2 344轮时节点才全部死亡,LEACH、PEGASIS、HEE-PEGASIS算法的节点全部死亡轮数分别为572、717、1 266.网络在运行一定轮数后的死亡节点数可以反映网络中节点的能量均衡情况,网络运行轮数越大且死亡节点越少说明网络的能量使用效率越高,网络生命周期越长.EHMCA的网络生命周期明显优于其他3种算法的主要原因可能是:①网络均匀分层缩短了簇域半径,从而缩短了传输距离;②异构网络中高级节点当选为簇首,均衡了网络能耗;③网络区域中采用多跳链路传输数据,提高了传输效率.因此,EHMCA能够提高网络性能,延长网络生命周期.从图5(b)可以看出,EHMCA向基站传输的数据量明显高于其他3种算法.在网络节点运行至第5 000轮时,EHMCA的基站接收数据量约为13 000LP,而LEACH、PEGASIS、HEE-PEGASIS的基站接收数据量约为2 000LP、2 200LP、10 000LP.由此可见,EHMCA在运行过程中基站获取消息的数量最多,并且增长趋势稳定,说明该算法运行稳定,网络能量使用效率高.EHMCA的基站接收数据量明显高于其他3种算法的原因有:①簇域内节点采用单跳传输、簇间采用多跳传输方式传输数据,减少了传输距离且优化传输路径;②异构网络节点在网络运行时进行数据融合,减少了数据传输冗余.因此,EHMCA在向基站传输数据方面具有明显的优势,能够获取更多的数据量.

从表1可知,异构网络中EHMCA的数据传输效率、网络寿命和稳定性优于同构网络中的其他3种算法,EHMCA的网络寿命比LEACH、PEGASIS、HEE-PEGASISI算法分别延长了约80%、76%、39%.这是因为EHMCA采用了均衡分层、能耗最优的分簇模式和节点能量异构的策略,缩小了簇域范围,网络区域内簇首的选举综合考虑了高级节点能量和剩余能量,使得簇首分布更加均匀,簇内数据传输可靠性和完整性增强;簇间采用了多跳链路传输方式,缩短了簇首到基站的数据传输距离和传输时延,提高了网络区域内的数据传输效率,保证了簇首与基站通信之间数据传输的实时性,减少了信息数据传输冗余,优化了整个网络的能耗和延长网络寿命.

表1　4种算法的基站接收数据量、网络寿命和稳定周期对比Table 1　Comparison of base station received data,network lifetime,network stable cycle among four algorithms

图5　4种算法的网络生命周期和向基站传输的数据量比较Fig.5　Comparison of network life time and data transmitted to base station among four algorithms

4结论

基于网络均衡分层、最优簇域半径、最优能耗分簇,并结合簇间多跳路由算法,文中提出了基于能量异构的WSN多链路算法(EHMCA).仿真结果表明,EHMCA在延长网络生命周期和网络寿命、提高数据接收效率、降低传输能耗等方面具有一定的优越性.EHMCA在真实环境如农业环境中如何监测农田环境,动态更新网络的拓扑结构,保证环境监测数据的准确性和稳定性要求,以及EHMCA的可拓展性和灵活性测试将是今后研究的重点.

参考文献:

[1]Perrig A,Stankovic J,Wagner D.Previously published works UC berkeley [J].Communications of the ACM,2004,47(6):53-55.

[2]常超.精准农业中WSN渐进融合算法研究 [D].重庆:重庆大学自动化学院,2012.

[3]Hughes Laurie,Wang Xinheng,Chen Tao.A review of protocol implementations and energy efficient cross-layer design for wireless body area networks [J].Sensors，2012,12(11):14730-14773.

[4]Akyildiz I F,Melodia T,Chowdhury K R.A survey on wireless multimedia sensor networks [J].Computer Networks,2007,51(4):921-960.

[5]Chen Y,Nasser N,Enabling N.QoS multipath routingprotocol for wireless sensor neitwoeks [C]∥Proceedings of 2008 IEEE International Conference on Communications. Bejing:IEEE,2008:2421-2425.

[6]Abdulla Ahmed E A,Nishiyama Hiroki,Kato Nei.Extending the lifetime of wireless sensor networks:a hybrid routing algorithm [J].Computing Communications,2012,35(9):1056-1063.

[7]Liu Yunsheng,Wang Zheng.Maximizing energy utilization routing scheme in wireless sensor networks based on minimum hops algorithm [J].Computers and Electrical Engineering,2012,38(3):703-721.

[8]Sanlih O,Cam H,Cheng X Z.EqoS:an energy efficient QoS protocol for wireless sensor networks [C]∥Procee-dings of Western Simulation Multi Conference.San Diego:Society for Modeling & Simulation International,2004:1-11.

[9]Zhang Ying,Fromherz M.Message-initiated constrain-based routing for wireless sensor networks [C]∥Proceedings of the First IEEE Consumer Communications and Networking Conference.Las Vegas:IEEE,2004:648-650.

[10]Haas Z J,Halpern J Y.Gossip-based ad hoc routing [C]∥Proceedings of IEEE INFOCOM 2002.New York:IEEE Communications Society,2002:1707-1706.

[11]Heizelman W,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks [C]∥Proceedings of the 33rd Hawaii International Conference on System Sciences.Maui:IEEE,2000:3005-3014.

[12]Heinzelman 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.

[13]Younis O,Fahmy S.HEED:a hybrid,energy efficient,distributed clustering approach for ad-hoc networks [J].IEEE Transactions on Mobile Computing,2004,3(4):660- 669.

[14]周卫东,刘萌萌,杨永江.基于多传感器信息融合理论的交互式多模型算法 [J].华南理工大学学报:自然科学版,2014,42(9):82-89.

Zhou Wei-dong,Liu Meng-meng,Yang Yong-jiang.An improved interacting multiple model algorithm based on multi-sensor information fusion theory [J].Journal of South China University of Technology:Natural Science Edition,2014,42(9):82-89.

[15]Lindsey S,Raghavendra C S.PEGASIS:power efficient gathering in sensor information systems [C]∥Procee-dings of 2012 IEEE Aerospace Conference.Big Sky:IEEE,2002:3-1125-3-1130.

[16]赵凌.基于PEGASIS算法的无线传感器网络路由算法的研究 [D].重庆:重庆理工大学自动化学院,2009.

[17]Kulik J,Heinzelman W,Balakrishnan H.Negotiation-based protocols for disseminating information in wireless sensor networks [J].Wireless Networks,2002,8(2):169-195.

[18]卿利,朱清新,王明文.异构传感器网络的分布式能量有效成簇算法 [J].软件学报,2006,17(3):481- 489.

Qing Li，Zhu Qing-xin，Wang Ming-wen.A distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks [J].Journal of Software, 2006,17(3):481- 489.

[19]徐丹丹.无线传感器网络分簇算法的研究 [D].南京:南京航空航天大学信息科学与技术学院,2008.

[20]郭新.无线传感器网络路由算法及数据融合技术研究 [D].广州:华南理工大学自动化科学与工程学院,2013.

Energy Heterogeneity-Based Multi-Chain Algorithm for WSN

WangWei-xing1,2HuangHong1SunDao-zong1,2LiLiang-bin1HuZi-ang1

(1. College of Electronic Engineering, South China Agricultural University, Guangzhou 510642, Guangdong, China;

2. Key Laboratory of Key Technology on Agricultural Machinery and Equipment of the Ministry of Education,

South China Agricultural University, Guangzhou 510642, Guangdong, China)

Abstract:In order to balance the energy consumption of WSN effectively and improve the network lifetime, an energy heterogeneity-based multi-chain algorithm (EHMCA) is proposed. In the algorithm, a two-stage heterogeneous network is adopted first, and the network area is divided into a number of equal sub-regions. Then, the optimal domain radius of clusters is determined according to the spacing between layers, the threshold value of the cluster head is also determined based on the energy of the advanced nodes and the average energy of the whole network, and the multi-hop routing inter-cluster parallel transmission mechanism is employed between layers. Therefore, in the whole network area, the cluster head transmits data to the base station by means of the multi-hop inter-layer multi-link parallel transmission mode and the single hop transmission mode of the optimal cluster. Simulation results show that the network performance of the EHMCA is better than those of the other three kinds of protocols, which proves that the EHMCA is effective and practical.

Key words:wireless sensor networks; hierarchical network; energy heterogeneity; clustering; multi-chain

中图分类号：TP393

doi：10.3969/j.issn.1000-565X.2015.09.012

作者简介：王卫星(1963-),男,教授,博士生导师,主要从事无线传感器网络、电子信息技术在农业中的应用研究.E-mail: weixing@scau.edu.cn

*基金项目：国家星火计划项目(2013GA780046);广东省科技计划项目(2013B020314014);广东省自然科学基金项目(2014A030313451)

收稿日期：2015- 01-23

文章编号：1000-565X(2015)09-0074-07

Foundation items： Supported by the National Spark Project(2013GA780046)，the Science and Technology Planning Project of Guangdong Province(2013B020314014)and the Natural Science Foundation of Guangdong Province(2014A030313451)