基于模糊规则的WSNs分簇路由算法

赵梦龙,郑宇超

(1.贵州职业技术学院信息工程学院,贵阳 550003;2.华东交通大学软件学院,南昌 330013)

无线传感器网络WSNs(Wireless Sensor Networks)通过在监控区域内部署海量廉价、微型传感节点实现对环境监测的目的。传感节点自行构建网络,并通过网络将感测数据传输至控制中心[1]。而节点的数据传输效率与节点能量紧切相关。若节点能量消耗殆尽,节点将无法感测数据,更难以完成数据的传输。

然而,WSNs内的节点一般通过电池供电。由于WSNs常采用随机方式部署传感节点,即使电池耗尽,也不便更换电池[3]。因此,降低节点能耗是WSNs的一个研究热点[4]。

传输数据所消耗的能量占据了节点能耗的大部分。为此,研究人员采用层次型路由实现数据传输,进而降低能耗。作为最经典的分簇路由,低功耗自适应层次路由 LEACH(Low Energy Adaptive Clustering Hierarchy)[5]将WSNs划分多个簇。每个簇由一个簇头和簇成员构成。簇头收集本簇成员的数据,并进行一定的处理,再传输至控制中心。LEACH路由引用“轮”的方式均衡网络内节点的能耗,进而延长WSNs寿命。然而,LEACH路由产生簇头的策略存在不足。它是以随机方式产生簇头,并没有考虑到节点的剩余能量信息。为此,研究人员提出不同的LEACH路由的优化算法。

董发志等[6]采用遗传算法优化簇头的选择。在选择簇头过程中考虑了距离、节点能量信息。张雅琼利用K-Means算法进行分簇(KMCR)[7]。但是该算法在选择簇头时并没有考虑节点间的距离关系。而张静静引用粗糙C-均值聚类对LEACH路由进行改进[8],提高簇头节点分布的均匀性。

此外,文献[9]引用网格概念,将每个网格内能量最高的节点作为簇头。而文献[10]通过智能算法构建最小生成树,并依据最小生成树传输数据,进而降低能耗。而文献[11]先利用概率模型产生多个分簇集合,然后选择能量最高的节点作为簇头。

为此,提出基于模糊规则算法的分簇-能效-路由算法FLECR(Fuzzy Logic-based Energy-efficient Clustering Routing)。FLECR路由仍采用轮方式构建簇。但与LEACH路由不同,FLECR路由并非在每一轮都重新分簇,而是采用按需方式。并通过模糊规则决策该簇是否需要重新分簇。只有需要重新分簇的簇就进行构建簇,而那些无需分簇的簇就保存簇头不变,减少了频繁构建簇和执行簇头选择所消耗的能量。仿真结果表明,提出的FLECR路由有效地降低了能耗,并提高网络吞吐量。

1 预备知识

1.1 网络模型

FLECR路由采用按需方式重新分簇概念。最初先建立若干簇。然后,再依据各簇的信息,决策是否下一轮进行重新分簇。所谓重新分簇就是重新进行簇头选举以及簇形成。通过该策略,降低频繁地构建簇,减少能耗。如图1所示,在第i轮进行簇头选举,但是在第i+1轮未进行簇选举和簇形成阶段。即FLECR路由并非采用固定方式进行簇头选举,而是采用按需方式进行簇头选举。

图1 FLECR路由轮次

图2 无线电能量消耗模型

1.2 能量消耗模型

考虑自由空间和多径两类衰减情况[12],如图2所示。假定发送端与接收端间距离为d。发送端将k比特数据传输至接收端所消耗的能量Etx(k,d):

(1)

接收端接收k比特数据所消耗的能量Erx(k):

Erx(k)=kEelec

(2)

2 FLECR路由

2.1 初始分簇

(3)

在定时时间Ti内,节点si监听是否收到其他节点发送的通告消息M_Ch_adv。值得一提的是:FLECR路由规定,当节点选举成簇头时,节点就向邻居节点广播簇头通告消息M_Ch_adv。

图3 簇头选举和簇形成的流程

当收到M_Ch_adv消息,表明已有节点被选举成为簇头。节点就将该簇头加入自己的邻居簇头集Ψ。假定节点sj广播M_Ch_adv(sj)消息,节点si收到M_Ch_adv(sj)。在这种情况下,节点si就将节点sj加入邻居簇头集Ψi,如式(4)所示:

Ψi←Ψi∪{sj}

(4)

若定时时间Ti内,未收到其他节点发送的 M_Ch_adv 消息,节点si就在定时时间结束后,立即 广播通告消息M_Ch_adv(si),即宣称自己为簇头。

节点si的邻居簇头集Ψi不空时,表明节点si收到多个节点广播的通告消息。在这种情况下,节点就从Ψi选择剩余能量大的作为自己的簇头。同时,向该簇头发送加入消息M_join。整个流程如图3所示。

2.2 基于模糊规则的簇重构

FLECR路由先通过2.1节进行初步分簇,并产生簇头[13]。接下来,簇头依据剩余能量、相对距离以及本簇内活动节点中心度三项信息,并结合逻辑规则决策是否在下一轮进行重新选举簇头,如图4所示。

图4 模糊规则系统

将相对剩余能量、距离和相对中心度作为模糊规则系统的输入,再通过推理系统产生输出变量Out。再将输出变量Out判断是否在下一轮进行重新分簇。

2.2.1模糊变量

①簇头离信宿距离

(5)

式中:d(Chi,Sink)表示簇头Chi离信宿的直接距离。而dmax、dmin分别表示网络内簇头离信宿的最远距离、离信宿的最近距离。

②相对剩余能量

(6)

③相对中心度

引用文献[14]节点中心度,计算簇头的中心度。

(7)

式中:(xi,yi)表示簇头Chi的位置坐标。

2.2.2 模糊变量模糊化

将簇头的剩余能量、相对距离和中心度三个变量作为模糊输入值,按需参数作为输出变量。三个模糊变量的隶属度函数如表1所示。

表1 隶属度函数

依据三个输入变量制定模糊规则,如表2所示。共27条规则。

表2 规则库

接下来,通过控制轮长度限定重新分簇次数。令Li表示簇头Chi是否在下一轮进行重新分簇的标志值。若Li=1,则表示在下一轮进行重新分簇。若Li=2,则表示间隔一轮就进行重新分簇;若Li=3,则表示间隔两轮才进行重新分簇。据此,对Li进行定义,如式(8)所示:

Li=max(Out,1)

(8)

式中:Out表示模糊规则的输出。

3 性能分析

为了更好地分析FLECR路由性能,通过MATLAB R2012b建立仿真平台[15]。在边长100 m的正方形区域内随机部署100个节点,且基站位于区域中心,且基站位置为(50 m,50 m)。具体仿真参数如表3所示。

表3 仿真参数

同时,选用LEACH路由和KMCR路由作为参照,并对比分析FLECR路由与LEACH、KMCR路由的性能,包括死亡节点数、生命周期、网络能耗和吞吐量。

3.1 实验一

首先分析FLECR、LEACH和KMCR路由的死亡节点数,如表4所示。从表4可知,FLECR路由的死亡节点数出现的最晚,其在2238轮出现第一个死亡节点,比LEACH和KMCR路由进行大幅度推迟。而FLECR、LEACH和KMCR路由分别在2 441轮、1 261轮和2 243轮时有50%节点死亡。

表4 3个路由的死亡节点数出现的轮数

图5显示三个路由的活动节点数。用活动节点数表征网络的生命周期。从图5可知,在同一轮数,FLECR路由活动节点数远高于LEACH路由、KMCR路由。原因在于:FLECR路由减少重新构建簇的频率,降低能耗。

图5 活动节点数

3.2 实验二

本次实验分析三个路由的网络能耗,如图6所示。从图6可知,在执行同等的轮数时,FLECR路由的剩余能量最高,高于LEACH路由和KMCR路由。这主要是因为:FLECR路由采用按需方式决策是否重新分簇,减少了构建簇的频率。同时,依据节点能量选择簇头,延长簇头寿命。

图6 网络剩余能量

3.3 实验三

部署传感网络的根本目的在于收集监测区域内的环境数据。据此,吞吐量是评价网络性能的重要指标。

图7显示了基站在不同轮数所收的数据量。从图7可知,随着轮数的增加,基站所收的数据量线性增加。但当轮数增加至一定轮数后,数据量不再增加。

图7 网络吞吐量

此外,相比于LEACH路由和KMCR路由,提出的FLECR路由有效地提升基站所接收的数据量,增加了吞吐量。原因在于:FLECR网络生命周期更长,传感节点能够监测更多数据。

4 总结

分簇路由是降低WSNs能耗的有效方式。为此,提出基于模糊规则分簇-能效-路由FLECR。FLECR路由采用不固定时间进行分簇,依据按需方式进行簇重构。同时,引用模糊规则产生簇头。依据簇头的剩余能量、距离以及中心度决策重构簇的时间间隔,避免了频繁地重构簇,降低了能耗。仿真数据证实,提出的FLECR路由有效地提升了能效,延长了网络寿命,并增加了网络吞吐量。