基于模糊理论的无线传感器网络多层分簇式路由算法*

陆亚芳,易可夫,冯 绪,万江文

(北京航空航天大学仪器科学与光电工程学院,北京 100191)



基于模糊理论的无线传感器网络多层分簇式路由算法*

陆亚芳,易可夫,冯 绪,万江文*

(北京航空航天大学仪器科学与光电工程学院,北京 100191)

为了进一步降低无线传感器网络的能量消耗,延长网络寿命,提出一种基于模糊理论的多层分簇式路由算法(MLFC)。新算法根据通信距离与能量的相关性将网络划分为多层,采用模糊算法根据节点的能量、分布密度和中心度在每层中选出多个簇头,其余节点分别加入同层中距离最近簇头形成的簇,簇头逐层传递数据,建立起自组多跳路由。仿真实验结果表明,多层分簇式路由算法可以更好地均衡无线传感器网络各节点的负载,能明显提高节点的生命周期,延长网络寿命。

无线传感器网络;路由算法;模糊理论;分簇

无线传感器网络WSNs(Wireless Sensor Networks)是由大量具有感知、计算和通信能力的微型传感器节点通过自组织方式构成的无线网络。它已经开始在环境监测、智慧城市、精细农业等众多领域发挥重要作用。WSNs的传感器节点一般是由电量有限的电池供电,降低能量消耗是WSNs的关键问题之一,当前仍然是研究的热点。

合适的网络通信路由是降低WSNs能量消耗的有效途径之一,目前已经有一些旨在降低能耗的分簇式路由算法[1-9]发表。LEACH算法[1]是最早提出来的分簇式路由协议,它采用轮循环方式,各节点成为簇头的概率都相同,使得网络中的节点能够相对均衡地消耗能量。但是,由于LEACH算法中簇头采用单跳方式与基站BS(Base Station)通信,距离基站远的节点会不可避免地过度消耗能量。HEED协议[6]根据主次参数均匀选择簇头以均衡节点的通信负载,采用多跳方式与基站通信,克服了LEACH协议单跳通信方式带来的距离基站远的节点能量消耗过快的问题。但是,多跳路由会使距离BS近的簇头因大量转发远距离簇头信息而过快消耗能量。为解决上述问题,EEUC[7]、DEBUC[8]、UCDP[9]等算法采用非均匀分簇方式,减少靠近BS的簇的通信半径,减轻其数据转发的任务,一定程度上均衡了通信负载。

从节点分簇,到多跳通信,再到非均匀分簇,通过更合适的路由来降低WSNs能耗的研究在不断深入。在不明显增加计算量的前提下,研究更为合理的分簇及簇头通信方式,很有必要。

如果在选举簇头之前,先将网络分层,在层中综合考虑节点能耗、分布密度和中心度等多种因素选出簇头,再由簇头建立层间通信多跳路由,应当可以进一步地均衡节点通信负载、降低网络能耗。

模糊算法在不需要复杂的数学建模的情况下,即可将多个因素综合评价以得出优先级,这一特点可以用于综合考虑WSNs节点的多种因素并选出簇头。由此,提出一种基于模糊理论的无线传感器网络多层分簇式路由算法MLFC(Efficient Multi-Layer Routing Protocol Through Fuzzy Logic Based Clustering Mechanism),首先,根据与BS的距离将网络划分为多层,各层中簇头数量与该层和BS的距离成反比;然后,各层中采用模糊算法综合考虑节点剩余能量、分布密度和中心度,合理选择簇头;最后,簇头逐层传递数据,建立起多跳路由。这种算法,复杂度不会有明显增加,却能更有效地均衡网络负载和降低能耗。

1 网络与能量模型

1.1 网络模型[10]

MLFC算法对无线传感器网络做出如下假设:①节点被随机地分布在检测区域内,所有节点的初始能量都相同。②节点可根据需要调整自身的发射功率。③节点通过RSSI方式可知道与其他节点的距离。④节点具有足够的计算能力来完成算法。

1.2 能量模型[11]

根据发送节点和接收节点之间的通信距离分别采用自由空间模型和多径衰减模型。节点发送k比特数据到距离d的接收器消耗的能量Et和接收器接收k比特数据消耗的能量Er分别为

(1)

Er=kEelec

(2)

上述中Eelec代表收发器的能量消耗,Eamp1和Eamp2分别代表自由空间模型和多径衰减模型放大电路的能量损耗,d0是两种模型的通信距离分界值。

2 基于模糊理论的多层分簇式路由算法

MLFC采用轮循环机制,每一轮中可以分为以下几个步骤:①根据通信距离与能量的关系将网络划分为多个层。节点根据与基站的距离确定自己所在的层。每层的簇头数量由该层的节点数和与基站的距离决定。离基站远的层簇头少,离基站近的层簇头多,这样做的目的,是减少离基站近的传感器节点的数据转发任务,以均衡网络负载。②各层基于节点能量、密度和中心度等3个变量采用模糊算法选出多个簇头。通过模糊算法综合考虑节点的能量和位置信息,使簇头不会因为能量低而过早死亡,同时会减少簇内的通信能量消耗。③其他没有被选举为簇头的节点加入距离最近的簇头所形成的簇。④簇内节点采用单跳方式与簇头通信,簇头逐层通过多跳传递融合数据,建立起与基站之间的多跳路由,由此可以避免信号的远距离传输。⑤根据簇头剩余能量和每轮的时间重新选择簇头,建立起新的路由,进行路由的维护。

2.1 网络分层

如图1所示,根据能量模型式(1)中的d0,网络划分为L层。设d是节点到BS的距离。dmax是网络中的节点到BS的最大距离。

dmax=MAX(d(SNj,BS))

(3)

(4)

图1 网络分层示意

节点SNj所在层的层数为l

(5)

这样分层,能够使簇头逐层通信时的通信距离小于d0,以减少远距离通信带来的能量消耗。

各层的簇头个数Cl与层数l成反比,与第l层中节点的个数Nl成正比。这样可以使距离BS近和节点密度大的层中的簇头数量更多,有利于减小簇内通信的能量消耗。Cl的计算如下:

(6)

其中K为系统的预设参数。

2.2 基于模糊算法的簇头选择方法

模糊算法不需要复杂的数学建模,具有结构简单、鲁棒性好的特点[12]。

传感器网络经过分层后,在每层中根据模糊变量和模糊规则,采用模糊算法,计算出节点的优先级,选择优先度级的节点作为簇头。

2.2.1 模糊变量

(1)节点的相对能量

节点相对能量PE代表节点SNi的剩余能量Ei与SNi所在簇的剩余能量最大节点的剩余能量Emax之比。

(7)

(2)节点的相对密度

节点密度代表传感器节点附近节点的密集程度,用节点SNi在d0通信范围内的邻居节点个数Di来表示。节点密度越高,则与邻居节点数据传递时消耗的能量越低。节点相对密度PD的大小为节点SNi的密度Di与节点SNi所在簇的簇内节点最大密度Dmax之比。

(8)

(3)节点的相对中心度

节点中心度Ci代表节点SNi与邻居节点的靠近程度。它的计算公式如下:

(9)

式中xi代表节点SNi的x坐标,yi代表节点SNi的y坐标。

簇头与邻居节点越近,通信消耗的能量越少。节点相对中心度PC的大小为传感器节点SNi所在簇的簇内节点的最小中心度Cmin与Ci之比。

(10)

2.2.2 变量的模糊化

模糊化是将每一个输入值映射到相应的模糊集合,并给每个模糊集合赋予隶属函数。设定节点相对能量PEi=e*,相对密度PDi=d*和相对中心度PCi=c*。相应的模糊输入E*(e),D*(d),C*(c)可以表示为:

(11)

采用三角形和梯形隶属度函数,因为它们适用于实时系统[13]。MLFC算法中包含3个模糊输入参数:相对能量、相对密度和相对中心度;包含一个输出参数:节点优先级。节点优先级决定了该节点能否成为簇头。

在建立输入和输出参数对应的模糊子集和模糊隶属度函数时,主要是参考自然经验,确定的参数和对应的特征集如表1所示。

表1 参数和特征集

图2 模糊逻辑系统输入和输出的隶属度函数

图2(a)表示相对能量的隶属度函数及特征值之间的关系。相对能量按照一定的隶属度属于某特征值。当相对能量低于0.2时,相对能量属于“少”;当相对能量在0.3和0.7之间时,相对能量属于“中等”;当相对能量大于0.8时,相对能量属于“多”。当相对能量在0.2和0.3之间时,相对能量有两个特征值:即“少”和“中等”,它按照隶属度μ1和μ2分别属于“少”和“中等”;当相对能量在0.7和0.8之间时,相对能量有两个特征值:即“中等”和“多”,它按照隶属度μ3和μ4分别属于“中等”和“多”。图2(b)表示相对密度的隶属度函数及特征值之间的关系,图2(c)表示相对中心度的隶属度函数及特征值之间的关系,图2(d)表示节点优先级的隶属度函数及特征值之间的关系。节点相对密度、相对中心度和优先级的隶属度函数及特征值之间的关系与相对能量的类似。

2.2.3 模糊规则

MLFC算法采用模糊IF-THEN分类规则,例如,相对能量多、相对密度高并且相对中心度高,则节点的优先级非常高。MLFC算法包含3×3×3=27条模糊规则,如表2所示。

表2 模糊规则

2.2.4 解模糊化

解模糊化是把由模糊规则生成的输出量转变成能实际使用的变量。MLFC采用重心法进行解模糊化。公式如下:

(12)

sup代表节点的优先度,μsup(x)是节点优先级的模糊集成员函数,x表示优先级的具体值。

2.2.5 模糊算法计算示例

SNi节点的优先级sup的值为:

2.3 簇的形成

节点被选为簇头后,向邻居节点广播信息,邻居节点接收到信息后加入距离最近的簇头形成的簇,并向簇头发送加入信息。这样节点与簇头节点的通信代价最小。在周期内,簇内节点将信息发送给簇头节点,簇头节点将收集到的数据融合处理后打包发送给基站,其中数据融合消耗的能量为EDA。

2.4 路由的建立

层间路由如图3所示。CHli是第l层的簇头,它把要传送给BS的数据转发给距离最近的第l-1层的簇头CH(l-1)j。簇头CH(l-1)j再把要传送给BS的数据转发给距离最近的第l-2层的簇头CH(l-2)k。依次传递,直到第1层的簇头CH1p把数据转发给BS。从而建立起簇头与BS之间数据逐层传递的多跳路由。

图3 路由建立示意

2.5 路由的维护

①当第l层中某簇头的能量低于簇内各节点剩余能量的平均值的一半时,在l层内部进行新的簇头选举和并建立新簇,同时重新建立起l+1层到l层和l层到l-1层的簇头数据转发路径;②经过T时间,整个网络建立起新一轮的路由。

3 仿真结果

采用MATLAB仿真分析算法的性能,并与LEACH、EECU算法做比较。

算法的仿真参数如表3所示。

表3 仿真参数

3.1 模糊算法模型

模糊算法的仿真结果如图4所示。当节点的相对能量为0时,无论相对中心度和相对密度怎么变化,节点的优先级都很小。当节点的相对能量到达一定数值时,节点的优先级会随着相对密度和相对中心度的增加而增加。这说明,节点相对能量是决定节点优先级的最重要因素,同时,相对密度和中心度也会对优先级产生明显影响。

图4 MLFC算法模糊推理模型仿真结果

3.2 簇头能量消耗

图5是MLFC算法与LEACH和EEUC算法的簇头能量消耗的对比曲线。前20 s的簇头能量消耗数据更具有可比性。MLFC和EEUC算法的簇头能量消耗比LEACH算法平稳并且明显低。LEACH算法是采用轮询方式以等可能概率随机选取簇头,所以簇头消耗的能量波动较大。MLFC和EEUC算法在进行簇头选择时是有条件的并且相对稳定,所以簇头能量消耗相对平稳。MLFC和EEUC采用多跳路由,相对LEACH算法节省了能量。MLFC算法的簇头能量消耗比EEUC算法更低。因为MLFC算法在选择簇头时通过模糊算法综合考虑了节点的能耗和地理位置信息,降低了簇头给簇内节点发送控制信息的能耗,并且进一步减少了簇内通信的能量消耗。因此,MLFC算法具有更好的均衡能耗的效果。

图5 3种算法的簇头能量消耗曲线

3.3 网络能耗

图6是MLFC算法与LEACH和EEUC算法网络剩余能量的对比曲线。MLFC采用模糊理论综合考虑节点剩余能量、中心度和密度等多个因素,合理选择簇头,减少了簇内节点通信消耗的能量,并且,簇头将融合数据逐层传递给基站,建立多跳路由,减少与基站通信之间的能量消耗。因此,MLFC网络能量消耗速度比LEACH和EEUC算法都要低,起到了减少能量消耗的作用。

图6 3种算法的网络剩余能量对比

3.4 网络生存周期

图7是MLFC算法与LEACH和EEUC算法的网络存活节点数量的对比曲线,图中MLFC算法的第一个节点死亡时间明显晚于EEUC和LEACH算法。MLFC算法将网络划分为多层,距离基站近的层中簇头多,减少了靠近基站的簇头的转发任务,均衡了网络中的负载,从而使得网络中节点的存活时间明显延长。

图7 3种算法的存活节点数量对比

4 结论

MLFC路由算法的中心思想是根据通信距离将网络划分为多层,使靠近基站的层有相对更多的簇头,缓解了多跳路由中靠近基站的节点过多承担转发任务导致过早死亡的问题;选举簇头时综合考虑节点剩余能量和位置信息,采用模糊理论合理选择簇头,更好地均衡各节点的能量消耗,同时减少簇内通信量;簇头自组建立层间的多跳路由,减少节点远距离发送数据带来的能量消耗。MLFC采取的模糊算法不需要复杂的数学计算,能够有效均衡网络负载,显著减少网络能耗和延长网络寿命。

[1] Wendi B Heinzelman,Anantha P Chandrakasan,Hari Balakrishnan.An Application-Specific Protocol Architecture for Wireless Micro sensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2]魏春娟,杨俊杰,张志美.一种分布式能量有效的无线传感器网络分簇路由协议[J].传感技术学报,2013,26(7):1014-1018.

[3]Babar Nazir,Halabi Hasbullah.Energy Efficient and QoS Aware Routing Protocol for Clustered Wireless Sensor Network[J].Computers and Electrical Engineering,2013,39(8):2425-2441.

[4]石为人,柏荡,高鹏,等.无线传感器网络簇头半径自适应调节路由算法[J].仪器仪表学报,2012,3(8):1779-1785.

[5]刘铁流,巫咏群.基于能量优化的无线传感器网络分簇路由算法研究[J].传感技术学报,2011,24(5):764-770.

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

[7]Li Chengfa,Ye Mao,Chen Guihai.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks[C]//IEEE International Conference on Mobile Adhoc and Sensor Systems Conference,Washington,DC,USA,2005:597-604.

[8]蒋畅江,石为人,唐贤伦.能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报,2012,23(5):1222-1232.

[9]孙彦清,彭舰,刘唐,等.基于动态分区的无线传感器网络非均匀成簇路由协议[J].通信学报,2014,35(1):198-206.

[10]Sival Ranjani S,Radha Krishnan S,Thangaraj C,et al.Achieving Energy Conservation by Cluster Based Data Aggregation in Wireless Sensor Networks[J].Wireless Personal Communications,2013,73(3):731-751.

[11]Jin Rencheng,Gao Teng,Song Jinyan,et al.Passive Cluster-Based Multipath Routing Protocol for Wireless Sensor Networks[J].Wireless Networks,2013,19(8):1851-1866.

[12]Vilém Novák.Reasoning about Mathematical Fuzzy Logic and Its Future[J].Fuzzy Sets and Systems,2012,192:25-44.

[13]Feng Renjian,Che Shenyun,Wang Xiao.A Credible Cluster-Head Election Algorithm Based on Fuzzy Logic in Wireless Sensor Networks[J].Journal of Computational Information Systems,2012,15(8):6241-6248.

陆亚芳(1990-),女,北京航空航天大学在读硕士研究生,研究方向为无线传感器网络技术,Julyforever899@163.com;

万江文(1963-),男,北京航空航天大学教授,博士生导师,主要研究方向为传感系统与仪器、传感网络与信息融合、定位与跟踪技术,jwwan@buaa.edu.cn。

EfficientMulti-LayerRoutingProtocolforWirelessSensorNetworksthroughFuzzyLogicBasedClusteringMechanism*

LUYafang,YIKefu,FENGXu,WANJiangwen*

(School of Instrumentation Science and Opto-Electronics Engineering,Beihang University,Beijing 100191,China)

In order to reduce the energy consumption and prolong the network lifetime of wireless sensor networks(WSNs),an efficient multi-layer routing protocol through fuzzy logic based clustering mechanism(MLFC)for WSNs is proposed.The MLFC mainly includes three steps.First,the network is divided into several layers based on the relationship between communication distance and energy.Second,cluster headers are elected among layers through fuzzy logic according to node’s remaining energy,distribution density and concentration.Nodes join the cluster formed by the nearest cluster headers.Third,data packets are transmitted to the base station layer by layer.A multi-hop routing is constructed.Experiment results show that the MLFC is of benefit to balance the nodes energy consumption and achieves an evident improvement of network lifetime.

wireless sensor networks;routing protocol;fuzzy logic;clustering

项目来源:国家自然科学基金项目(61371135)

2014-04-25修改日期:2014-06-09

10.3969/j.issn.1004-1699.2014.07.015

TP393

:A

:1004-1699(2014)07-0933-06