基于模糊控制的环形WSN多跳分簇路由算法

张雁东, 赵宏伟, 王出航, 杨兴旺

(1. 吉林省教育厅 教育科技产业服务中心, 长春 130022； 2. 吉林大学 计算机科学与技术学院, 长春 130012；3. 长春师范大学 计算机科学与技术学院, 长春 130032； 4. 长春工业大学 计算机科学与工程学院, 长春 130012)

0 引 言

近年来, 无线传感器网络在军事、 森林防火、 海洋监控等方面得到了广泛应用[1-3]。但由于受部署环境、 地理位置、 部署成本等因素影响, 如何对传感器网络中有限的能量进行充分利用, 延长网络工作寿命成为传感器网络的研究重点, 分簇路由算法被证明是一种十分有效的方法[4-10]。

Heinzelman等[4]最早提出了一种典型的网络分簇路由算法, 其核心思想是在网络中节点通过选择0～1之间的随机数决定是否成为簇头, 根据所选簇头对网络分簇。通过簇头收集簇内节点的信息, 并将数据信息进行处理融合后发送至汇聚节点, 该算法减少了其他节点与基站间的直接通信, 降低了能量的消耗。李建坡等[5]提出了一种基于能量迭代的非均匀分簇路由算法, 该算法在簇头选举时通过减少迭代次数以达到降低能量消耗的目的, 同时综合考虑节点能耗速度、 节点到汇聚节点的距离等因素, 选出最优簇头。Yadav等[6]提出了一种改进的LEACH算法LEACH-R, 它在簇头选举过程综合考虑节点能量、 距离、 分布密度等因素选取更加合理的簇头, 同时对簇的大小进行优化, 使簇头能耗更加均衡, 但该算法传输方式使用簇头与基站直接通信的方式, 这使传输路径加长, 使传输能耗过大而易出现能量空洞问题。蒋畅江等[7]提出了采用基于时间的簇头竞争的非均匀分簇算法, 减小基站附近节点的成簇半径实现网络能量的均衡。Batra等[8]提出了一种改进的LEACH-MAC协议, 将该协议稳定了每轮所选出的簇头个数, 避免了LEACH协议每轮选举簇头数的随机性。张长森等[9]提出了一种能量高效的非均匀分簇算法(EUCA： Energy-efficient Uneven Clustering Algorithm), 该算法针对LEACH算法中的簇头选择机制进行了改进, 提出了基于节点剩余能量的簇头选举策略, 并且对EEUC算法的成簇半径和簇间路由进行了改进, 达到延长网络周期的效果。Pant等[10]提出了一种多跳分簇路由算法Multi-hop EEBCDA, 它将网络划分为不同的网格, 使远离汇聚节点位置的簇规模更大、 节点更多, 簇头采用多跳方式传输数据, 但该算法没有考虑多跳传输时的中继节点的剩余能量, 会导致网络节点能量消耗不均匀而产生能量空洞等问题。

针对上述问题, 笔者提出基于模糊控制的环形无线传感器网络多跳分簇路由算法(FCRA: Fuzzy logic control based Clustering Routing Algorithm)。首先将网络分为间距相等的若干圆环, 以每环能耗最小为原则, 计算出每个圆环中的最佳簇头数目； 然后, 在成簇阶段运用模糊控制的方法选举每个簇的簇头, 避免了由于随机选举簇头导致环内簇头分布不均匀而造成的网络负载不均衡等问题； 最后, 簇间的路由方式根据数据包长度、 下一节点的剩余能量以及簇间通信消耗有机的结合, 计算每条传输路径的权重函数, 选择权重函数小的路径进行数据传输。

1 系统模型

1.1 网络模型

图1 网络模型Fig.1 Network model

将网络模型等效为以R为半径的圆形区域, 将其分成n个以ri(从内向外i=1,…,n)为间距的同心圆中,N个节点均匀分布在该圆形区域中, 汇聚节点SINK在圆心的位置[11]。并且假设：

1) 每个节点具有唯一的ID, 均匀分布在网络中；

2) 所有节点位置固定且能量有限, 但对汇聚节点能量没有限制；

3) 所有节点都具有相似的能力, 都能当簇头节点或普通节点；

4) 节点间可以相互通信, 可以通过接受消息的信号强度计算二者的距离。

1.2 能量模型

数据传输能耗采用文献[12-13]中模型, 节点发送数据消耗的能量为

(1)

(2)

其中l为数据长度；Eelec为收发电路的功耗系数；d为通信距离；d0为自由空间传输模型与多径衰减传输模型的临界值。当d

节点接收数据消耗的能量可表示为

Erx(l,d)=lEelec

(3)

节点进行数据融合消耗的能量可表示为

EA=lEDA

(4)

每个节点固定的能量消耗可表示为

Eid=Eelec

(5)

2 算法设计

首先对网络初始化, 由汇聚节点向网络中节点发布网络的整体消息ADV_SINK_MSG, 网络中节点根据接收到消息的信号强度判断自身位置。在网络中每个节点都确定好自身的信息后, 进入网络的工作阶段, 网络的工作阶段大致可以分成两个阶段： 成簇阶段以及数据传输的路由阶段。

2.1 成簇阶段

2.1.1 最佳簇数选择

在每个簇内的节点能量消耗可以分为两部分： 簇头节点消耗以及簇内普通节点消耗。

第i个圆环的节点数为

(6)

假设环内的每个簇就是以相同半径的圆覆盖, 且第i环的最优簇头数目为mi。则第i环内节点与簇头距离的均值为

(7)

第i环节点向簇头发送数据消耗的能量为

(8)

第i环簇头到基站的距离均值的平方为

(9)

第i环簇头到基站的距离的均值为

(10)

第i环簇头节点距下一跳簇头节点的距离可表示为

(11)

第i环簇头消耗的能量为

(12)

第i环每个节点消耗的能量为

Echi-node=lEtx

(13)

一个簇消耗的能量总和可通过

(14)

计算得出, 则第i环消耗的能量为

Etotal=miEclustris=miEchi-head+NiEchi-node

(15)

(16)

(17)

2.1.2 簇头选举

在计算每个圆环中的节点数目和最佳簇头数后, 接下来就是簇头选举阶段。在传统方法中, 通常采用严格的随机轮转的方式, 但在很大程度上会使簇头的选择具有随机性, 会造成簇头在某一部分分布的过于密集或稀疏, 从而导致无线传感器网络中的热点或空洞现象。

为了避免簇头选择的随机性, 采用模糊控制[14]的方法选择每个簇的簇头。如图2所示为簇头选择的模糊控制器结构, 将网络中节点的位置信息以及节点自身的剩余能量作为模糊控制器的输入, 输出为节点成为簇头的概率。

图2 模糊控制器结构Fig.2 Fuzzy controller structure

首先, 输入节点的信息, 通过模糊语言及如图3所示的隶属函数对输入的消息进行模糊化, 其中, 节点位置的模糊变量为“很远(NB)、 远(NM)、 较远(NS)、 中(M)、 较近(PS)、 近(PM)、 很近(PB)”； 节点的剩余能量模糊语言变量为“很低(NB)、 低(NM)、 较低(NS)、 中(M)、 较高(PS)、 高(PM)、 很高(PB)”, 模糊控制系统的输出簇头概率的模糊语言变量“很小(NB)、 小(NM)、 较小(NS)、 中(M)、 较大(PS)、 大(PM)、 很大(PB)”, 其中“低、 高、 远、 近、 很小、 很大”采用梯形隶属度函数, 其余为三角隶属度函数。然后, 根据表1设定if-then结构的模糊条件语句构成模糊控制规则, 对模糊化的数据进行推理后, 得到模糊控制器的输出, 模糊推理输出的是模糊语言变量。最后, 采用质心法对输出的模糊语言解模糊, 得到簇内节点成为簇头的概率。

表1 模糊规则

当计算完成节点的成簇概率后, 每个节点向其邻居节点发送报文CH_COMPETE_MSG, 包括该节点的ID、 成簇概率。邻居节点接收到报文后, 更新簇头列表, 当某个节点的成簇概率大于其他邻居节点时, 该节点成为簇头, 其他节点为候选簇头。簇头节点向其他邻居节点广播CH_SUCCESS_MSG, 其他邻居节点根据接收报文的信号强度选择加入最近的簇, 同时向加入的簇头发送加入簇的报文CH_JOIN_MSG, 构成一个簇。当一轮传输完成后, 在成簇概率列表中删除该簇头, 采用上述方式在候选簇头中重新竞选簇头。

2.2 路由阶段

当簇建立完成, 簇内节点开始传输数据, 在工作过程中, 簇头的能量消耗主要用于发送数据, 因此为了延长网络的生命周期, 应该寻找能量消耗最少的传输路径减少簇头消耗； 同时为了使簇头的能耗均衡, 应该综合考虑传输路径上其他簇头的剩余能量、 传输距离等因素。

文献[15]中证明了在多跳网络中, 当每次传输的距离相等时, 网络消耗的能量最小。由此可得： 在不同情况下, 环i中簇头节点的传输情况可通过

S(i)=「log2i⎤+1

(18)

确定。用H(k)表示簇头在每种情况下的多跳数, 每种情况下的多跳数可通过

(19)

计算得到。当采用不同的传输方法,H(k)下一跳的环数可由

(20)

算出。为了节省能量, 假设在不进行数据传输时, 簇头点处于休眠状态。对剩余的簇头节点, 通过

(21)

算出其每条传输路径的权重函数gi。其中c1、c2、c3、c4为每条路径的加权因子,r为当前网络工作的轮数,Nres为下一跳所在环的第r轮存活节点数,Nint为下一跳节点所在环的初始节点数,dhop为簇头节点下一跳传输的距离,dmax为网络中节点距汇聚节点的最远距离,Eint为节点的初始能量,Eres为节点的剩余能量,H(k)为节点i将数据传输到汇聚节点的跳数,Eid为每个节点的固定消耗。

式(21)中, 第1项主要考虑网络中节点数目会随着网络工作时间的增加而减少, 当转发上一簇头节点的数据时, 节点越多会使簇头消耗的能量越多, 权重函数越大； 第2项考虑了下一簇头节点的剩余能量, 当下一簇头节点剩余能量越少, 可用于转发的能量就越少, 权重函数就越大； 第3项主要考虑每跳传输的距离, 当传输距离较大时, 能量消耗的越大, 权重函数就越大； 第4项主要考虑由于簇头节点传输数据可以采用多种情况, 但只考虑传输距离会使每次都是传输路径最短的是最佳传输方式, 所以要结合该传输距离情况下的跳数； 第5项是簇头节点的固定消耗。

由于传输时消耗了能量, 簇头节点的剩余能量发生了变化, 所以在每轮传输后要重新计算每条传输路径的权重函数。

具体的算法流程如下。

1) 分簇完成后, 各簇头节点根据式(18)～式(20)计算该节点向汇聚节点的传输情况, 不同情况下的传输跳数, 以及下一跳节点所在的环数。

2) 当簇头要向汇聚节点发送信息时, 根据步骤1)中计算的结果, 寻找到它的所有情况下的下一跳的簇头节点, 并向该节点广播报文EDGE_HEADNDE_MSG。

3) 当下一跳簇头节点接收到报文后, 向该簇头节点广播报文NEXT_HEADNODE_MSG, 包括自身位置以及剩余能量。

4) 簇头节点根据接收到的NEXT_HEADNODE_MSG消息, 根据式(21)计算该条路径的权重函数gi, 并与其他路径的权重函数相比较, 选择gi值最小的路径进行数据传输。

5) 在计算下一跳时, 重复2)～4)步, 直至下一跳节点是汇聚节点为止。

按照寻找到的路径进行数据传输, 即可实现簇头的能量消耗最小。其他环的簇头节点同样可以通过上述步骤获得最佳传输路径。

3 仿真分析

为了验证笔者算法FCRA的有效性, 将其与文献[4]中的LEACH算法和文献[8]中的Multi-hop EEBCDA算法进行比较, 主要比较了网络的生存周期及剩余能量。仿真参数如表2所示。

表2 仿真参数

3.1 网络节点生存情况

网络轮数与网络中存活节点个数的关系如图4所示。LEACH算法在602轮出现第1个死亡节点, 在1 084轮所有节点全部死亡, 这是由于簇头节点直接将数据传输给网络中的汇聚节点, 节点消耗过多的能量, 导致网络死亡过快。Multi-hop EEBCDA算法第1个死亡节点出现在747轮, 在1 127轮全部死亡, 这是由于簇头通过多跳数据传送, 但没有考虑下一跳节点是否有足够的能量接受和发送数据, 导致节点的能量消耗不均匀。FCRA算法在956轮出现死亡节点, 在1 354轮全部死亡, 与LEACH算法相比, 网络的使用寿命延长了24.9%, 证明了FCRA算法相比于传统算法可以更好的减少网络的能量消耗, 延长了节点的工作时间。

图4 网络寿命对比 图5 网络剩余能量对比 Fig.4 Comparison of network lifetime Fig.5 Comparison of residual energy

3.2 网络能耗情况

网络轮数与网络节点剩余能量的关系如图5所示。可以看出, 当网络中没有节点死亡时, LEACH算法、 Multi-hop EEBCDA算法和FCRA算法的能耗比较均匀, 当出现死亡节点时, 3种算法都有不同程度的波动, FCRA算法在网络总体能量消耗上比LEACH算法和Multi-hop EEBCDA算法更节能。这是由于FCRA算法考虑了节点在成簇阶段和传输阶段的剩余能量及位置信息, 以降低节点的能量消耗, 延长网络的寿命, 从而更好地平衡网络负载。

4 结 语

针对环形无线传感器网络的使用寿命问题, 提出了一种新的基于模糊控制的多跳路由算法(FCRA), 该算法先计算每个网络中的最佳簇数。在成簇阶段, 利用网络节点的剩余能量、 到汇聚节点的距离作为输入模糊控制器的参数, 结合最佳簇数, 选举网络中的最佳簇头节点。在传输数据阶段, 采用等间距的多跳路由方式, 由于节点位置不同, 多跳路径也不同, 给每条路径赋予一个权值。该权值主要通过下一跳节点的剩余能量、 距离以及网络中剩余节点个数确定, 选择权值最小的路径进行传输。仿真结果表明, FCRA相比LEACH和Multi-hop EEBCDA有更小的能量消耗, 从而提高网络的生命周期。