基于模糊逻辑推理的WSNs非均匀分簇算法

杨健冬,王文娟

(郑州工业应用技术学院,河南 新郑 451150)



基于模糊逻辑推理的WSNs非均匀分簇算法

杨健冬*,王文娟

(郑州工业应用技术学院,河南 新郑 451150)

为了进一步降低无线传感网络WSNs(Wireless Sensor Networks)能耗,拓延网络寿命,提出了基于模糊逻辑推理的WSNs非均匀分簇算法,记为DUCF。DUCF算法充分考虑了节点剩余能量、节点度以及离基站距离。根据经验制定模糊规则,通过模糊推理系统得到节点当选为簇头的几率和簇尺寸。DUCF算法形成非均匀簇,进而平衡簇头间的能量消耗。仿真结果表明,DUCF算法在网络寿命、能量消耗方面的性能优于LEACH、CHEF和EAUCF算法。

无线传感网;分簇;模糊逻辑推理;非均匀;剩余能量

随着现代电子技术的发展,无线传感网络广泛使用于各类应用,如康复医疗、战场、野外环境监测等[-3]。由于无线传感网络常部署于野外恶劣环境,更换节点的电池是不现实的。因此,能耗成为无线传感网络的研究热点。而相比于感测、处理数据阶段,通信阶段的数据传输消耗了更多的节点能量[4-5]。因此,通过提高数据汇聚、传输效率,可有效地节省节点能量。保存节点能量是非常重要的。一旦节点能量消耗殆尽,该节点将无法工作,此类节点也称为失效节点。此类节点影响了网络寿命。

为了存储节点能量,常采用簇结构,即将邻近节点或具有相同特性的节点汇聚成一个簇[6-7]。每个簇内选择一个节点作为簇头,并由簇头收集簇内节点的感测数据,经融合后,再传输至基站。通过簇结构,降低网络能耗。目前,研究人员提出不同的簇算法。这些算法在簇头选择或簇形成阶段存在异同。LEACH[8]就是经典的分布式簇算法。LEACH算法先计算阈值,然后产生一个随机数。如果该数大于阈值,就称为簇头。这种簇头产生策略存在随机性,并没有兼顾到节点个体特性。同时,LEACH算法也存在均匀簇的共性问题。

所谓均匀簇就是指所有簇内的节点数都相等,反之,若簇内节点数不相等,有大有小,称为非均匀簇[9]。而文献[10]提出非均匀簇算法EECS。EECS算法总是选择节点能量最高的节点作为簇头。尽管能量是无线传感网络的重要指标,但是若单一地考虑能量因素,而不兼顾其他特性,是不合理的。

此外,文献[11]提出了基于模糊逻辑的分布式簇算法CHEF。CHEF算法利用剩余能量和局部距离作为模糊逻辑的输入,其中局部距离是指节点离其所有邻居节点的距离之和。而模糊逻辑系统的输出表征节点成为簇头几率。最终,几率最高的节点成为簇头。文献[12-13]也提出了基于模糊逻辑的分布式簇算法EAUCF。这些算法充分利用了模糊逻辑算法的特性,但是并没有对簇尺寸进行控制,也忽略了簇内通信的能量消耗。同时,在选择簇头时,没有考虑到节点的邻居节点数信息。

为此,本文结合模糊逻辑系统的优势,提出基于分布式模糊逻辑推理的非均匀簇路由DUCF。利用模糊逻辑算法在处理不确定系统的优势,将节点离基站的距离、节点剩余能量以及节点度作为模糊逻辑系统的输入,进而产生节点被选为簇头的几率以及簇尺寸。通过模糊逻辑系统,产生更优的簇头。同时,依据局部信息,控制簇内节点数(簇尺寸)。仿真结果表明,提出的DUCF算法能够有效地降低能量消耗,扩延网络寿命。

1 预备知识

1.1 网络模型及约束条件

考虑如图1所示的网络模型,将网内传感节点划分不同的簇,每个簇内产生一个簇头。簇头融合本簇内成员节点的数据,然后再以直接或间接多跳方式传输至基站。

考虑同构无线传感网络,所有传感节点具有相同初始能量Einit。一旦在监测区域内部署了传感节点,传感节点就不再移动,即静态无线传感网络。每个传感节点具有相同的处理数据容量,且节点的传输半径为R。此外,基站不受能量限制,并且具有全局网络知识。

图1 网络模型

1.2 能量模型

无线电能量消耗主要有两部分组成:运行电子元器件、功率放大器所消耗的能量和接收器所消耗的能量[14]。如图2所示,在相距为d的两节点间传输q比特的数据信息,消耗的能量:

(1)

式中:Eelec运行发射器或接收器固定的能量消耗,Efrris、Etworay分别表示发射器在自空间、双径传播模型(two ray ground model)的单位功率放大器的能量消耗[14-15]。而dco的定义如式2所示:

(2)

式中:λ为波长、l为系统损耗。ht、hr分别表示发射天线和接收天线的增益系数。相应地,对于接收q比特的数据包所消耗的能量:

ERX(q)=qEelec

(3)

图2 无线电能量消耗模型

2 DUCF 算法

提出的DUCF算法将时间划分等间隔轮r(round),如图3所示。每轮由簇化阶段和数据汇聚阶段。前者又可进一步分为簇头选择和簇形成两个子阶段。将数据汇聚阶段划分等间隔的帧,每一帧内有固定的时隙,用于簇内成员节点向簇头传输数据。

图3 DUCF算法的时间模型

图4 DUCF算法模块图

2.1 簇头选择阶段

本小节详尽表述簇头选择阶段。DUCF算法利用模糊逻辑系统选择簇头。首先计算节点离基站的距离d、节点的剩余能量Eres以及节点度ρ,并将这3个变量作为模糊逻辑系统的输入,系统的输出变量ζ表征了节点成为簇头的几率,如图4所示。

图5 3个输入变量的隶属函数

距离对网络性能也存在影响。若离基站过近,节点将消耗过多的能量向基站转发数据。反之,若离基站过远,节点将需要经多次转发才能将数据传输至基站。因此,在选择簇头,应充分考虑簇头离基站的距离信息。距离变量用“邻近(Nearby)”、“可达(Reachable)”、“遥远(Distant)”表征距离语言变量,如图5(b)所示,其中“可达(Reachable)”服从梯形函数。

最后将节点度作为模糊逻辑系统的输入。节点度指节点一跳邻居节点。节点度越高,成为簇头的概率越高。节点度的隶属函数如图5(c)所示,用“低(Nearby)”、“中等(Average)”、“高(Huge)”表征节点度语言变量。

依据图4可知,模糊逻辑系统有表征成为簇头的几率ζ、簇尺寸s的两个输出变量,分别如式(4)、式(5)所示。

ζ= {very high,high,rather high,high medium,medium

low medium,rather low,low,very low}

(4)

s= {very small,small,rather small, medium,rather big

big,very big,very small,very big}

(5)

两个输出变量的几率ζ、簇尺寸s的隶属函数如图6所示。

图6 输出变量的隶属函数

知识规则库如表1所示,共有27条规则。系统输出的两个变量为模糊值,仅为语言输出变量,需要将其转换精确的数值,即去模糊化。利用文献[16]的Mamdani模糊控制的重心法,可实现去模糊化。

依据模糊逻辑系统的输出,传感节点便获取了自己的几率值ζ。然后,所有节点就在一跳传输范围内广播CH_candidate消息,其包含节点ID和几率ζ值。每个节点依据几率ζ值设置定时器,定时时间与ζ值成反比。具体而言,假定节点i,它的定时时间为Ti:

Ti=|1/ζi|×T

(6)

式中:ζi为节点i的几率值、T为定时器的基准时间。

表1 DUCF算法的规则库

从式(6)可知,几率越小,节点的定时等待时间越短,成为簇头的概率就越大。如果节点在自己定时时间内,没有收到其他节点发送的CH_won消息,节点就待定时时间完毕后,立即向一跳邻居节点广播CH_won消息,宣称自己成为簇头。如果在定时时间内,收到CH_won消息,表明一跳邻居内已有更短的定时时间,其已宣称自己为簇头。

2.2 簇头形成阶段

没有成为簇头的节点需要选择离其最近一个簇加入。具体过程如下:簇头广播CH_won消息后,邻居节点可能收到一条或多条CH_won消息。如果只收到一条,节点就向该簇头发送CM_join消息。若收到多条CH_won消息,节点就选择离自己最近的簇头回复CM_join消息。一旦发送了CM_join消息,节点就等待、并接收簇头回复CM_acceptance消息。

为了控制簇尺寸,簇头接收了CM_join消息后,需要决定是否允许该节点加入簇。如果簇内节点的节点数并没有超过簇尺寸s,簇头就向该节点发送CM_acceptance消息,表示允许该节点加入簇。否则,就发送拒绝CM_rejection消息。

节点一旦接收了CM_acceptance消息,就加入该簇。若收到CM_rejection消息,节点再向其他的簇头发送CM_join消息,重复上述过程,直到收到簇头的CM_acceptance消息。不过,更为糟糕的是,节点可能无法收到CM_join消息。在这种情况下,该节点就自己成为簇头。

2.3 数据汇聚阶段

簇形成后,每个簇头为簇内成员节点安排TDMA时隙。簇内成员在TDMA时隙内向簇头传输感测数据。为了节省节点能量,节点仅在数据传输时隙内保持活动状态,其余时隙保持睡眠状态。当然,簇头一直保持非睡眠状态,使它能够及时汇聚簇内成员节点的数据。由于簇内节点感测的数据相似,簇头需对这些数据进行融合、汇聚,然后再向基站传输。

3 性能仿真

3.1 仿真参数及性能指标

本节评估DUCF算法的性能,利用MATLAB建立仿真平台,并与LEACH、EAUCF、CHEF进行比较。选择这3个算法作为参考原因在于:LEACH是经典的簇算法,而EAUCF和CHEF算法也采用模糊逻辑,与DUCF算法具有可比性。在仿真过程中,LEACH算法在簇头百分比设为0.1,而EAUCF和CHEF算法的簇头比例为0.3。

100个节点随机分布于200 m×200 m监测区域内。为了能更好地分析DUCF算法性能,分别考虑3个场景:基站位于监测区域中心;基站位于监测区域角落;基站位于监测区域外。此外,节点传输半径R=40 m,其他仿真参数如表2所示。

表2 仿真参数

从每轮的能量消耗、传输的消息数和网络寿命三方面分析DUCF算法,其中,传输的消息数表示在网络内有一半节点失效HND(Half Node Die)时,基站所接收到消息数。而网络寿命表示从两个方面进行分析:在第1个节点失效FND(First Node Die)前,所执行的轮数,以及一半节点失效HND前,所执行的轮数。

3.2 每轮的能量消耗

3个场景下的能量消耗情况如图7所示。从图7可知,LEACH算法消耗的能量最多。原因在于LEACH算法中簇头与基站通信采用直接方式,这加大了能量消耗。相比之下,与LEACH算法相比,CHEF算法的能量消耗有所下降,但是离EAUCF和DUCF算法仍存在较大的差距。与LEACH和CHEF算法相比,EAUCF算法的能量消耗得到有效了的下降。

图7 每轮的能量消耗

然而,EAUCF算法在选择簇头时,仅考虑节点的剩余能量,并没有考虑节点度等其他因素。与LEACH、CHEF和EAUCF算法相比,DUCF算法的能量消耗的最少。这主要因为DUCF算法在选择簇头时,充分考虑了节点的剩余能量、距离以及节点度的信息,进而选择了更优的节点作为簇头,这缩减了簇内通信的距离。同时簇头与基站通信采用多跳方式,这些措施有利于节点能量的保存。

3.3 网络寿命

本文分别利用FND和HND时各算法所完成的通信轮数表征网络寿命,实验数据如图8、图9所示。

图8 网络寿命(FND)

从图8可知,提出的DUCF算法能够有效地提高网络寿命。在场景一中,DUCF算法比LEACH、CHEF和EAUCF算法的网络寿命分别提高了71.87%、31.91%、16.07%。而在场景二中,DUCF算法在网络寿命方面的性能优势更为明显,比LEACH、CHEF和EAUCF分别提高了127.14%、116.72%、14.95%。当基站不在监测区域时,DUCF算法的网络寿命得到更大的提升。在场景三,DUCF算法的网络寿命比LEACH、CHEF和EAUCF算法分别提高了133.47%、150.0%、5.01%。

图9 网络寿命(HND)

图9分析了在HND时各算法的网络寿命。图10的实验数据进一步表明DUCF算法能够有效地提高网络寿命。在场景一中,DUCF算法比LEACH、CHEF和EAUCF算法分别提高了14.30%、31.78%、16.74%;在场景二中,提高了54.10%、51.74%、2.35%。而当基站远离监测区域时,DUCF算法在网络寿命方面的性能优势更为突出。在场景三中,DUCF算法比LEACH、CHEF和EAUCF算法的网络寿命分别提高了95.38%、91.84%、6.72%。

4 总结

本文提出了基于模糊逻辑推理的WSNs非均匀分簇算法DUCF,旨于降低能耗,提高网络寿命。具体而言,利用模糊逻辑推理输出变量“簇尺寸”,控制簇内成员节点的个数,进而平衡节点能量消耗。DUCF算法充分利用节点离基站的距离、节点度以及剩余能量因素计算簇尺寸和成为簇头的几率。仿真结果表明,DUCF算法能够有效地提高网络寿命。特别是在基站位于监测区域场景,DUCF算法在网络寿命方面的优势比LEACH、CHEF、 EAUCF算法更为显著。

提出DUCF算法目的在于降低能量消耗,延长网络寿命。这也是该算法的优势。当然,利用引入模糊系统,提升一定的算法复杂性,这也是后期工作的重点:在延长网络寿命的同时,降低算法复杂性。

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 归奕红. 无线传感器网络HEDSA数据聚合研究[J]. 计算机工程,2011,37(7):160-164.

[3] 沈艳霞,薛小松. 无线传感网络移动信标节点路径优化策略[J]. 传感器与微系统,2012,31(12):42-46.

[4] Zhao F,Liu J. Collaborative Signal and Information Processing:An Information Directed Approach[J]. Processing IEEE,2013,91(8):1199-1209.

[5] 周凯,孟利民,华惊宇. 基于Grover路由策略的无线传感网络剩余容量构造与研究[J]. 传感技术学报,2015,28(2):249-253.

[6] Abbasi A,Younis M F. A Survey on Clustering Algorithms for Wireless Sensor Networks[J]. Computing Communication,2012,30(15):2826-2841.

[7] Bajabder F,Awan I. Adaptive Decentralized Re-Clustering Protocol for Wireless Sensor Networks[J]. Journal Computing System,2011,77(2):282-292.

[8] Heizelman W,Chandrakasan A,Balakrishnan H. An Application-Specificprotocol Architecture for Wireless Microsensor Networks[J]. IEEE Transation Wireless Communications,2002,1(4):660-670.

[9] Mehdi M,Tayarani H. Clustering in Sensor Networks:A Literature Survy[J]. Journal Network Complication Application,2014(46):198-226.

[10] Ye M,Chen G H. EECS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks[C]//24th IEEE International Performance,Computing and Communication Conference,2015:535-540.

[11] Kim J,Park S,Han Y. CHEF:Cluster Head Election Mechanism Using Fuzzy Logic in Wireless Sensor Networks[C]//10th International Conference on Advanced Communication Technology,2013:654-659.

[12] Bagci H,Yazici A. An Energy Aware Fuzzy Approach to Unequal Clustering in Wireless Sensor Networks[J]. Application Soft Computing,2013,13(4):1741-1749.

[13] Bagci H,Yazici A. An Energy Aware Fuzzy Unequal Clustering Algorithm for Wireless Sensor Networks[C]//Proceedings of the IEEE International Conference on Fuzzy Systems,2010:1631-1639.

[14] Xinhua W,Sheng W. Performance Comparison of LEACH and LEACH-C Protocols by ns2[C]//Ninth International Symposium on Distributed Computing and Applications to Business,Engineering and Science,2010:23-32.

[15] Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks[J]. IEEE Sens,2013,13(5):1498-1506.

[16] Elbhiri B,Saadane R,El-Fkihi S,et al. Developed Distributed Energy-Efficient Clustering(DDEEC)for Heterogeneous Wireless Sensor Networks[C]//5th International Symposium on I/V Communications and Mobile Network. 2010:32-42.

Fuzzy Logic-Based Unequal Clustering Algorithm for Wireless Sensor Networks

YANG Jiandong*,WANG Wenjian

(Zhengzhou University of Industrial Technology,Xinzheng He’nan 451150,China)

In order to reduce the energy consumption and prolong the network lifetime of Wireless Sensor Networks(WSNs),distributed fuzzy logic inference-based unequal clustering routing is proposed in this paper,which is marked as DUCF. DUCF protocol fully consider the residual energy of the node,distance to base station,and the degree of node. It makes some fuzzy rules,and calculates probability of cluster head and size of cluster through the fuzzy inference system. DUCF forms unequal clusters to balance the energy consumption among the cluster headers. Simulation results show that the proposed DUCF performs better in term of network lifetime and energy consumption as compared to LEACH,CHEF and EAUCF protocols.

wireless sensor network;clustering;fuzzy logic inference;unequal;residual energy

杨健冬(1981-),男,汉族,河南郑州人,硕士,讲师,主要研究领域为计算机网络与通信,互联网技术,信息安全;

王文娟(1983-),女,河南郑州人,硕士研究生,主要研究领域为计算机网络与通讯,电子设计自动化,信息安全。

项目来源:国家自然科学基金项目(31630034);河南省基础与前沿技术研究计划项目(142300410283)

2016-10-04 修改日期:2017-02-21

TPT393

A

1004-1699(2017)06-0929-06

C:7230

10.3969/j.issn.1004-1699.2017.06.021