基于模糊算法和最短路径的LEACH改进协议

刘泳志,刘国繁

(1．湘潭大学 信息工程学院，湘潭 411105；2.湖南工程学院 电气信息学院，湘潭 411104；3. 湖南省风电装备与电能变换协同创新中心，湘潭 411104)

基于模糊算法和最短路径的LEACH改进协议

刘泳志1,刘国繁2，3

(1．湘潭大学 信息工程学院，湘潭 411105；2.湖南工程学院 电气信息学院，湘潭 411104；3. 湖南省风电装备与电能变换协同创新中心，湘潭 411104)

无线传感器网络是由部署在监测区域的大量传感器节点通过无线通信形成的自组织网络系统，传感器节点存在着电源能量、计算和通信能力有限等制约因素.为了均衡无线传感器网络中节点能量的消耗，延长无线传感器网络的工作寿命，提出一种基于模糊算法和最短路径的LEACH改进协议ILAFASP.该协议簇头选举时，采用模糊算法考虑相对节点剩余能量、相对集中度、相对节点度计算出每个节点的优先度，根据优先度选举簇头；在数据传送阶段，在源节点和基站之间建立最短多跳数据传输路径，减少簇头数据传输的能耗.仿真表明，该协议能够均衡节点能量的消耗，延长整个网络的工作寿命.

无线传感器网络；模糊算法；LEACH协议；CMRAOL协议；多跳通信

无线传感器网络WSN(Wireless Sensor Network)是由部署在监测区内的大量微型传感器节点组成，通过无线通信方式形成一个多跳的，自组织网络系统[1].无线传感器网络中的节点的能量、信息处理能力和通信能力都十分有限.如何降低WSN的能量消耗、延长网络寿命一直是WSN研究的热点[2].在WSN的能量消耗中，数据通信能量消耗所占比例最大[3]，因此如何减少通信过程的能量消耗[4-5]成为WSN研究的一个重要问题.

Leach(Low Energy Adaptive Clustering Hierarchy)协议[6]是最具代表性的一种基于分簇的自适应层次型路由协议，由于簇头随机选取且直接与基站进行通信，消耗能量较多，为此，很多人提出了改进的算法：文献[7] 提出了一种ESSCSTA协议，该协议采用休眠机制结合最小生成树将数据发送给基站，减少数据传输能量消耗.文献[8]提出了CMRAOL(Cluster head Multi-hops Routing Algorithm On LEACH)协议，该算法中引入能量因子和距离因子修正LEACH算法的阈值函数，采用簇间多跳通信方式，延长了网络寿命.本文针对簇头节点能量消耗过大，数据传输路径不合理等问题，提出一种基于模糊算法和最短路径的无线传感器网络分簇路由协议ILAFASP(Improved LEACH algorithm based on fuzzy algorithm and the shortest path)，该协议能有效地均衡节点能量消耗，提高网络的生存时间.

1 网络模型

假设N个传感器节点随机分布在二维的正方形区域内，区域内的节点周期性地搜集周围的信息，并且具有以下性质：

(1)传感器网络为静态网络，节点一经部署后就不能移动；

(2)基站的能量是无限的；

(3)所有节点都有一个唯一的ID；知道自身在区域中的坐标；具有相同的通信半径且可以调节；具有相同的初始能量且不能补充能量；具有数据融合和功率控制功能.

(4)簇内节点与簇头节点采用单跳方式通信，簇头与基站之间采用单跳和簇头间多跳相结合的方式进行通信.

2 能量消耗模型

(1)

传感器节点接收kbit数据所消耗的能量为：

Erx(k)=Erx-elec(k)=kEelec

(2)

其中，ξfs、ξmp分别为自由空间模型和多路径衰减模型下的放大系数，单位分别为J/(bit·m2)和J/(bit·m4)；Eelec为1 bit数据在发送或者接收过程中所消耗的能量.

3 ILAFASP协议设计

ILAFASP协议与LEACH协议一样，采用轮循环机制，每轮分为两个阶段：成簇阶段和数据传输阶段.在成簇阶段，监测区域中的节点自组织成簇，每一个簇中只有一个簇头，负责收集、融合和转发其簇内普通节点采集的数据；数据传输阶段包括簇内数据传输和簇间数据传输，簇内节点发送采集的数据给簇头，簇头对候选中继节点进行比较，选择最佳的中继节点以减少簇间数据传输的能耗.每隔一个周期，整个网络进入成簇阶段，且不断循环，直至区域内所有节点的能量耗尽.下面对两个阶段做详细说明.

3.1 成簇阶段

模糊算法对被控对象数学模型的信息要求不高[10]，通过对多个因素的综合评价得出一个优先度AD(advance degree)，这一特点可以用于簇头的选举.在选举簇头时，根据模糊算法原理，先输入节点自身的相关参数，再计算出这个节点当选簇头的优先度，根据区域内各节点优先度的大小设置节点广播当选簇头消息的时间，选择优先度大的节点当选簇头.

模糊控制器[11]是用模糊逻辑来模仿人的逻辑思维[12]来对难以建立数学模型的系统进行控制的设备，模糊算法主要在于模糊控制器的设计[13]，基本元素是隶属函数、模糊规则表和解模糊过程[14]，下面对整个过程做详细描述.

3.1.1 簇头选举参考的模糊变量

(1)节点的相对剩余能量：

(3)

其中Ei(r)表示第r轮节点i的剩余能量，Ei-max(r)为节点i的成簇半径Rc内的所有邻居节点剩余能量最大值.

(2)节点相对集中度：

(4)

其中，n为节点i在成簇半径Rc之内邻居节点个数，di-j是节点i到其邻居节点j距离.

相对集中度：

(5)

FDi-max和FDi-min分别是节点i的邻居节点FD的最大值和最小值.RFD的值越小，说明节点i的邻居节点分布更加集中，簇内通信消耗更小.

(3)改进的相对节点度：

节点i节点度：

(6)

其中Numi是以节点i为圆心，Rc为半径的圆内所有邻居节点数，Dmax是距离节点i到最远的邻居节点距离.相对节点度：

RDi(releative degree)=Di/Di-max

(7)

其中Di-max是节点i成簇半径内的邻居节点的节点度最大值.

相对节点度不仅考虑了邻居节点的个数，还考虑了邻居节点的分布情况，其参数越大，则说明节点的邻居节点较多，且分布相对集中，有利于减少簇内通信代价.

3.1.2 变量的模糊化

本文的模糊控制器包含节点相对剩余能量，相对密集度和相对节点度三个输入参数，一个输出参数.其中三个模糊输入参数都分为三个等级：Low，Middle，high；其中相对剩余能量采用梯形隶属函数，相对密集度和相对节点度采用正态波隶属函数，如图1～图3所示.

图1 相对剩余能量的隶属函数

图2 相对集中度隶属函数

图3 相对节点度隶属函数

经过模糊化计算，输出的chance的值分为1～11一共11个等级，采用三角波隶属函数，如图4所示.

图4 chance隶属函数

模糊推理过程遵循“IF——THEN”规则，本文设定如下形式:

IFRE∈A,RFD∈B,RD∈CTHENchance∈D

其中，A,B,C分别对应三个输入变量模糊集合定义的语言值，D对应输出变量模糊集合的语言值.

节点的相对剩余能量越多，相对集中度越大，相对节点度越高，它的chance的级别也越高，其27条模糊规则如表1所示.

表1 模糊规则表

3.1.3 解模糊化

通过解模糊化将chance的模糊值转化为精确的数值，求得节点的优先度AD值.本文的解模糊化方法采用常用的质心法，其公式[15]如下：

(8)

3.1.4 簇头的选举

选举簇头时结合模糊控制算法，每个节点通过模糊算法得到每个节点的优先度AD值.根据公式(9)设置发送当选簇头消息的等待时间，时间到了，就发送当选簇头的消息，在半径Rc内的节点侦听到消息后自动放弃竞争簇头，成为普通节点.

(9)

其中，T是一固定的时间，V是介于[0.9,1]之间随机数.

首先，选择相对剩余能量较多了节点，有利于均衡节点的能耗，选择邻居节点数量多且相对密集度较大，分布集中的节点做簇头，有利于减少簇内通信能耗；此外，监测区域中各个部分节点的能耗不是均匀的，有些区域的节点消耗可能相对较大，如果与全部节点作比较，这些剩余能量较小的区域可能选不出簇头，所以以上三个参数都是在自己成簇半径Rc内的比较，选择局部区域内较优的节点作为簇头；此外，一旦某个节点发布当选簇头消息，其半径内的其他簇头则成为普通节点，这样防止了LEACH协议采用随机机制选举簇头造成的簇头过于密集的情况.

普通节点选择最近的簇头发送入簇请求，簇头收到入簇请求后将该节点加入路由表中，向簇内的成员节点发布确认消息并且分配TDMA时隙，簇内成员节点依据自己的TDMA时隙将数据发送给簇头.

3.2 数据传输阶段

簇形成之后，簇中的普通节点将采集到的数据发送给自己的簇头，由于簇内数据传输距离较短，所以普通节点和簇头节点之间采用单跳通信的方式.

而簇间数据传输由于部分簇头距离基站较远，而通信能耗随距离的增加呈几何增长，因此为了减少数据传输的能耗，ILAFASP协议簇间数据传输采用单跳与多跳相结合的方式，在源节点与基站间建立最短数据传输路径，降低簇头在簇间数据传输过程中的能耗，下面作详细叙述.

如果簇头到基站的距离小于d0，则簇头直接与基站通信，这样可以减少不必要的数据转发能量消耗.

如果簇头到基站的距离大于d0，则采用簇间多跳通信方式.源节点在选择合适的簇头作为中继节点，中继节点将簇内数据和接收的转发数据融合后再转发给中继节点，一直传输到基站.中继节点的选择方法如下：

首先源节点i把满足公式(10)的簇头作为其候选中继节点.

(10)

其中，i为源节点，j为某个其它簇头节点.R的值为70 m.条件(10)使选取的中继节点比源节点更靠近基站，且距离源节点不至于太远(R

之后在这些候选中继节点中根据公式(11)选择Q值最大的作为其中继节点.

(11)

式(11)中的路径因子hij是指候选中继节点j到簇头节点与i基站连线的垂直距离，如图5所示.

图5 路径因子hij示意图

hij的值计算方式如下：设簇头节点i的坐标为(xi,yi)，候选中继节点j的坐标为(xj,yj)，基站坐标为(x0,y0)，则簇头节点i到基站BS的连线可表示为：

(12)

式(12)可化为如下形式：

Cx+Dy+E=0

(13)

其中：

C=y0-yi，D=xi-x0

E=xi(yi-y0)+yi(x0-xi)

那么，根据点到直线的距离公式可得：

(14)

hij的值越小，说明簇头节点j越靠近基站和源节点i的连接线，这时d(i,j)+d(j,BS)的值也越小.当hij的值为0时,d(i,j)+d(j,BS)的值最小，此时d(i,j)+d(j,BS)=d(i,BS)，传输距离最短，数据传输过程的能量消耗最小.

此外，当部分节点死亡导致簇头找不到满足公式(10)的候选簇头的极端情况时，则簇头i扩大发射功率，在满足条件d(j,BS)

4 仿真实验和性能分析

采本文用MATLAB软件对ILAFASP协议、CMRAOL协议和LEACH协议进行仿真.对三种协议的簇头节点分布情况、首个节点死亡时间、网络生存周期和网络能量消耗几个方面进行对比分析.

4.1 实验参数设置

仿真实验的参数设置如表2所示，其中，R=70 m，a、b的值，通过仿真结果的对比分别取最优值为：a=0.8，b=0.2.

表2 实验参数表

4.2 实验结果及分析

图6 CMROAL协议和ILAFASP协议节点分布图

由图6(a)可以看出，CMROAL协议的簇头在网络中分布不均匀，比如在靠近基站的区域簇头分布过于密集；而从图6(b)可以看出本文提出的ILAFASP协议中，簇头在网络中的分布比较均匀，这样更利于均衡簇头的能耗，避免簇头的过早死亡.

图7 三种协议存活节点数

图7给出了LEACH、CMRAOL和ILAFASP协议首个节点死亡时间、网络生存周期的比较.LEACH、CMRAOL、ILAFASP协议第一个节点死亡的轮数分别为241、523、756，ILAFASP协议的生存周期也大于CMRAOL协议.本文提出的ILAFASP协议有明显的优势，这是因为ILAFASP协议选取簇头时使用模糊控制算法，选择节点的相对剩余能量多，相对集中度大，相对节点度大的节点作为簇头，不仅减少簇内通信的能耗而且均衡网络节点的能耗；此外采用了时间竞争机制，使节点的分布更加均匀.在簇间数据传输阶段，选择单跳与多跳相结合的通信方式，当簇头到基站距离小于d0时，直接向基站传输数据，避免了多余的转发能量消耗；当采用多跳通信时，综合考虑了候选中继节点本身和其前向传输区域的剩余能量和路径因子，寻找一条从源节点到基站的最短路径，节省了簇头转发数据的能耗，从而在首个节点死亡时间和网络生存时间等性能上都有明显的提升.

图8 三种协议的网络剩余的总能量

图8给出了LEACH、CMRAOL和ILAFASP协议网络能量消耗情况的对比. 可以看出ILAFASP协议的网络剩余能量下降曲线比LEACH和CMRAOL协议更加平缓，且剩余总能量一直高于CMRAOL协议，在生存周期的前面绝大部分轮数高于LEACH协议，这表明ILAFASP协议能够更加有效的减少网络中节点的能耗.

5 结论

由于监测区域中节点的能量有限，如何减少和均衡网络中节点的能耗成为我们路由协议设计的最重要的问题，本文提出了一种基于模糊算法和最短路径的LEACH改进协议ILAFASP，对簇头的选举方式做了改进，结合模糊控制算法选举簇头，综合考虑节点的相对剩余能量，相对集中度和相对节点度，均衡网络节点的能耗，减少簇内通信的代价，并使簇头的分布更加合理；此外，采用单跳与多跳相结合的簇间数据传输方式，在源节点和基站间寻找一条最短数据传输路径，减少簇间数据传输的能耗，避免簇头节点在数据传输过程中能量消耗过快.通过仿真对比，ILAFASP可以有效均衡网络中节点的能耗，延长网络工作寿命.

[1] 曹建玲,任 智. 无线传感器网络路由协议综述[J]. 微计算机信息, 2010,26(7-1):3-5.

[2] 唐甲东,蔡 明. 基于LEACH协议的能耗均衡路由算法[J].计算机工程,2013,39(7):133-141.

[3] 张兴强，杨科华,罗 娟. 一种异构传感器网络下的节能分簇路由算法[J]. 计算机工程与应用,2011,47(11): 81-83

[4] 廖先林,陆 畅,姜 婷,等.一种能耗均匀的WSN分簇路由协议研究与设计[J].小型微型计算机系统, 2014,10(35):2199-2202.

[5] Jing Yan, Cailian Chen, Xiaoyuan Luo, et al.Topology Optimisation-based Distributed Estimation in Relay Assisted Wireless Sensor Networks[J]. IET Control Theory & Applications,2014,8(18): 2219-2229.

[6] Heinzelman W.R, Chandrakasan A, Balakrishnan H. Energy-efficient Communication Protocol for Wireless Microsensor Networks[C]// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000.

[7] Chauhan R, Gupta V. Energy Efficient Sleep Scheduled Clustering & Spanning Tree Based Data Aggregation in Wireless Sensor Network[C]// Proceedings of the 1st International Conference on Recent Advances in Information Technology (RAIT), 2012: 536-541.

[8] 陈炳才,么华卓,杨明川,等. 一种基于LEACH协议改进簇间多跳路由协议[J].传感技术学报,2014,27(3) :373-377.

[9] 张 淳,费树岷.能耗均衡的自组织无线传感器网络分簇算法[J].控制工程,2012,19(1):90-93.

[10]B.Baranidharan, B.Santhi.DUCF: Distributed Load Balancing Unequal Clustering in Wirelesssensor Networks Using Fuzzy Approach[J].Applied Soft Computing,2015,40:495-506.

[11]Taheri H,Neamatollahi P,Younis O M,et al.An Energy-aware Distributed Clustering Protocol in Wireless Sensor Networks Using Fuzzy Logic[J].Ad Hoc Networks,2012,10(7):1469-1481.

[12]Vilem Novak.Reasoning About Mathmatical Fuzzy Logic and Future[J].Fuzzy Sets and Systems,2012,192:25-44.

[13]Gupta I,Riordan D,Sampalli S.Cluster-head Election Using Fuzzy Logic for Wireless Sensor Networks[C]//Proceedings of the 3rd Annual Communication Networks and Services Research Conference, 2005:255-260.

[14]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.

[15]Kim J M, Park S H, Han Y J, et al. CHEF Cluster Head Election Mechanism Using Fuzzy Logic in Wireless Sensor Networks[C].Proceedings of Advanced Communication Technology, 2008: 654-659.

An Improved LEACH Algorithm Based on Fuzzy Algorithm andShortest Path.Computer Engineering and Applications

LIU Yong-zhi1,LIU Guo-fan2

(1. College of Information Engineering, Xiangtan University, Xiangtan 411105, China；2. College of Electrical Information, Hunan Institute of Engineering, Xiangtan 411104, China；3. Hunan Province Cooperative Innovation Center for Wind Power Equipment and Energy Conversion, Xiangtan 411104, China)

Wireless sensor network is a self-organized network system which is formed by the large number of sensor nodes deployed in the monitoring area. The sensor nodes have limited power, computation and communication ability.In order to balance the energy consumption of nodes and prolong the working life of the wireless sensor network,an improved LEACH algorithm based on fuzzy algorithm and the shortest path ispraposed. The cluster head of this agreement is elected by using fuzzy algorithm considering the relative residual energy of nodes, the relative focus degree and the degree of node of calculating the priority degree of each node, for cluster head electing. In data transmission phase, a multi-hop shortest path between source node and base station is set up to balance energy consumption of cluster data transmission. Simulation shows that the protocol can balance the node energy consumption and prolong the working life of the whole network.

wireless sensor network; fuzzy algorithm; LEACH protocol; CMRAOL protocol; multi-hop communication

2016-07-28

湖南省科技计划资助项目(2012SK3173);广东省普及型高性能计算机重点实验室开放课题(SZU-GDPHPCL201303).

刘泳志(1991-),男,硕士,研究方向：无线传感器网络.

刘国繁(1959-)，男，教授，研究方向：信号检测与处理、图像传输、嵌入式系统及应用.

TP393

A

1671-119X(2017)01-0010-07