基于分布式模糊控制器的无线传感器 网络容错非均匀分簇算法

王出航, 沈玮娜, 胡黄水

(1. 长春师范大学 计算机科学与技术学院 , 长春 130032; 2. 长春工业大学 计算机科学与工程学院, 长春 130012)

0 引 言

无线传感器网络广泛应用于环境监测、 应急反应、 军事监控以及太空探索等领域[1-2]. 有效节能是无线传感器网络需亟待解决的问题, 而分簇是其有效方法之一[3-4]. 可将无线传感器网络中地理位置相近的节点分成不同的簇, 每个簇中选出一个簇头负责收集簇内成员数据进行融合, 然后发送至基站. 分簇算法可提高网络的可扩展性和能量效率, 减小路由延迟, 延长网络生命周期[2]. LEACH(low energy adaptive clustering hierarchy)[5]是最早被提出的一种经典分簇算法, 其通过周期性随机选择簇头节点, 产生合适比例的簇头, 从而均衡网络能耗. 但LEACH算法中簇头直接与基站通信, 且低能量的节点可能被选为簇头, 导致簇头尤其是远离基站的簇头能量耗尽很快. 为了解决LEACH算法存在的缺陷, DSBCA算法[6]基于剩余能量、 节点连通密度和选举时间参数计算节点权值, 权值大的节点被选为簇头, 然后根据簇头与基站的距离及其连通密度计算通信半径, 组织簇成员, 从而形成更平衡的簇结构, 并延长网络的生命周期. 但DSBCA算法中簇头仍直接与基站通信, 导致簇头能量耗尽很快, 且簇头的更换仅在簇内进行, 导致能耗不均衡. 文献[7]提出了一种LEACH优化分簇算法, 在簇头选举时考虑节点的剩余能量, 使剩余能量高的节点成为簇头的几率变大, 并通过直线方程求出簇头的下一跳路由, 通过多跳的方式与基站进行通信, 提高簇头能量利用效率的同时增强了网络可靠性. 但该算法中簇头间采用多跳方式传输数据, 导致邻近基站的簇头承担较多数据中继任务而过早能量耗尽, 产生“热点”问题. 以上均匀分簇方法通常适于节点分布均匀的无线传感器网络, 而实际部署的无线传感器网络通常节点分布不均匀.

为了解决均匀分簇算法存在的“热点”等问题, 文献[8]根据节点剩余能量、 节点到基站距离、 节点度和节点到簇头距离等因素选择簇头, 从而将网络划分为大小不等的簇, 然后簇头基于剩余能量、 到基站距离构造基于最小生成树的最优传输路径, 通过簇内单跳、 簇间多跳的通信方式将数据传输到基站. 文献[3]提出一种改进的非均匀分簇路由算法WUCH, 考虑节点剩余能量和节点到基站的距离选举簇头, 将网络分为不同规模的簇, 在规模较大的簇内选取双簇头, 主簇头负责收集簇内数据, 副簇头负责转发数据, 在数据传输阶段构造基于改进的最小二叉树进行数据多跳传输, 减小规模较大簇的簇头节点收集与传输数据的负担, 从而减小节点能量消耗. 上述算法中采用不同的竞争半径产生不均匀的簇, 竞争半径内最优的节点称为簇头, 但计算竞争半径时很难确定最优参数. 此外, 基于竞争的簇头选举会增加网络开销, 而且算法采用的路由方法比传统的最短路径多跳方法产生更多的信标报文. 为了处理簇头竞争半径计算中可能出现的不确定性, 文献[9]提出了模糊能量感知的非均匀分簇(EAUCF)算法. EAUCF算法将节点剩余能量和节点与基站距离输入模糊推理系统, 计算得到节点的竞选半径, 使竞选半径范围内剩余能量高的节点成为簇头, 成簇时非簇头节点加入与簇头距离近的簇, 仿真结果表明, 该算法具有良好的性能, 能有效延长网络生命周期. 但EAUCF算法中, 当靠近基站节点较多时, 将导致靠近基站的簇头耗能极快. 为了克服该问题, 文献[10]提出了一种改进的EAUCF算法----FBUC算法. 上述算法都是基于通信半径来约束簇大小, 无法确保最优的簇成员数, 从而导致簇内通信负载不均衡. 针对该问题, 文献[4]提出了一种基于模糊方法的负载均衡的非均匀分簇算法DUCF. DUCF算法中的模糊推理系统利用剩余能量、 节点度及节点与基站距离选举簇头, 输出为节点成为簇头的机会和簇大小值, 从而使不同簇具有不同簇大小以保证负载均衡, 并提高网络生命周期.

上述算法都假设节点只有在能量耗尽时才死亡. 而实际上, 无论簇头还是成员节点由于多种原因(如电源不稳、 物理损坏等)均可能失效和工作异常, 而一旦簇头出现故障, 则其不能正确收集和转发数据, 从而极大降低网络性能. 文献[11]采用备份簇头解决该问题, 一旦簇头发现其出现故障或能力低于某个级别, 则由备份簇头接管其职责, 使成簇更安全. 文献[12]提出了一种采用备份簇头列表的方法来容错, 当发现簇头发生故障时, 从备份簇头列表中选出最优的节点成为簇头.

本文融合文献[4]和文献[12]的思想, 提出一种分布式模糊控制的非均匀容错分簇(distributed fuzzy controller based unequal clustering algorithm with fault tolerance, DFUC)算法. 考虑节点的剩余能量、 节点中心度以及节点与基站距离, 运用模糊控制器和节点本地信息计算节点成为簇头的机会和簇大小值, 使具有最大机会值的节点成为簇头, 并根据簇大小值决定某成员节点是否加入, 从而形成大小合适的簇. 在数据传输阶段, 采用TDMA(time division multiple access)方式进行簇内数据的收集, 并容忍簇头和成员节点的临时和永久故障, 簇间采用最短路径多跳方式进行数据传输, 当簇头出现永久故障时, 最优的备份簇头成为簇头, 成员节点出现永久故障时, 将该节点从网络中移除.

1 相关模型

1.1 网络模型

DFUC算法通过形成大小合适的簇均衡能量消耗, 通过TMDA机制容错, 从而延长整个网络的生命周期. 为简化, 假设无线传感器网络具有如下性质：

1) 网络部署后所有节点都是静态的, 节点能量受限而基站能量不受限；

2) 网络节点同构, 即具有相同的初始能量, 相同的处理、 存储、 发送和接收能力；

3) 节点间可通过接收信号强度指示RSSI计算近似距离；

4) 网络部署开始时, 基站先向全网节点发送HELLO报文, 然后每个节点以其通信半径R广播自己的HELLO报文, 基于这些交互信息, 每个节点计算得到与基站的距离及节点中心度；

5) 每个节点具有唯一的标识, 则节点集可表示为S={s1,s2,…,sn}, 其中si表示第i个节点.

1.2 能量模型

为便于性能分析和比较, 本文采用文献[3-4]和文献[12]中的能量模型, 即

对于分簇无线传感器网络, 在数据传输阶段的能量消耗主要有两个因素, 即簇内传输和簇间传输. 其中簇内传输的能量消耗Eintra由三部分构成, 即

Eintra=EMemToCh+EChrx+EDA,

(3)

其中:EMemToCh表示成员节点与簇头通信的能量消耗;EChrx表示簇头从其簇成员节点接收数据消耗的能量;EDA表示数据融合的能量消耗. 成员节点与簇头通信的能量消耗EMemToCh为

(4)

其中:n表示网络的簇头数;mi表示某簇i内的成员节点数, 每个簇可能都不相等;Etx表示第i个簇内节点j发送数据到其簇头消耗的能量. 簇头从其簇成员节点接收数据消耗的能量EChrx为

(5)

其中:mi表示第i个簇内成员节点数;n表示网络内簇的数量;Erx表示接收能量. 数据融合的能量消耗EDA为

(6)

其中:k表示数据位数;EpDb表示单位数据融合消耗的能量.

同理, 簇间传输的能量消耗计算也包括两种情况, 如果簇头直接与基站通信, 则其能量消耗Esinter为

Esinter=Etx(CH,BS).

(7)

簇头通过多跳方式与基站通信时的能量消耗Eminter为

(8)

其中:nm表示簇头到基站的跳数;CH(i)表示从簇头到基站多跳路径上的第i个簇头.

1.3 模糊控制器模型

采用Mandani模糊控制器[4,9-10]， 结构如图1所示. 由图1可见, 清晰输入值剩余能量、 节点中心度、 节点到基站的距离被模糊推理引擎通过给定的隶属度函数模糊化为合适的语言变量, 然后模糊输入变量根据IF-THEN规则库在推理系统中进行控制处理. 输出量为成为簇头机会(chance)和簇大小(size), 模糊推理引擎的输出仍然是模糊语言变量, 通过采用质心法解模糊, 从而获得清晰输出量“机会”和“大小”值.

图1 模糊控制器结构Fig.1 Structure of fuzzy controller

2 DFUC算法设计

DFUC算法采用模糊控制器计算节点成为簇头的机会和簇大小值, 使具有最大机会值的节点成为簇头, 并根据簇大小值形成所需规模的簇, 同时按各成员成为簇头的机会大小值排序, 构建备份簇头列表. 采用TDMA方式进行簇内数据的收集, 当簇头出现永久故障时, 最优的备份簇头成为新的簇头. 算法分为簇形成阶段和数据传输阶段.

2.1 簇形成阶段

在簇形成阶段, 网络中的所有节点都有机会成为簇头, 且每个节点在该阶段都运行如图1所示的模糊控制器, 得到成为簇头的机会和簇大小值. 该阶段分成两个子阶段： 簇头选举子阶段和簇建立子阶段.

2.1.1 簇头选举子阶段 网络中的所有节点先被指定为簇成员节点, 然后为“剩余能量”、 “节点中心度”、 “节点到基站距离”这3个输入变量指定模糊语言变量, 其中剩余能量“Energy”和节点中心度“centrality”的模糊语言变量为“低”、 “中”、 “高”(low, middle, high)； 节点到基站距离“Distance”的模糊语言变量为“近”、 “中”、 “远”(near, middle, far). 且“低”、 “近”、 “高”、 “远”采用梯形隶属函数, 模糊语言“中”采用三角形隶属函数. 这些隶属度函数基于文献[4,9-10]的实验结果及本文的实验结果. 模糊输出变量“成为簇头的机会”“Chance”采用9个模糊变量, 即“很低”、 “低”、 “较低”、 “低中”、 “中”、 “高中”、 “较高”、 “高”、 “很高”(very low, low, rather low, low middle, middle, high middle, rather high, high, very high). 其中“很低”和“很高”采用梯形隶属度函数, 其他输出语言变量采用三角形隶属度函数. 第二个输出变量“簇大小”“Size”采用7个模糊语言变量, 分别是“很小”、 “小”、 “较小”、 “中”、 “较大”、 “大”、 “很大”(very small, small, rather small, middle, rather large, large, very large). 其中“很小”和“很大”采用梯形隶属度函数, 其他均采用三角形隶属度函数.

清晰输入值先被模糊推理引擎通过给定的隶属度函数模糊化为合适的语言变量, 然后模糊输入变量通过IF-THEN规则库进行处理. 共有27条规则, 表1列出了DFUC算法的模糊IF-THEN规则. 模糊推理引擎的输出仍是一个模糊语言变量, 采用质心法解模糊, 从而获得清晰输出量“机会”和“大小”.

2.1.2 簇建立子阶段 DFUC算法执行过程中, 节点可能处于成员、 簇头和备份簇头3种状态之一. 部署后, 所有节点处于成员状态, 并启动模糊控制器计算其成为簇头的“机会”和簇“大小”. 之后所有节点向其通信半径内的邻居节点广播簇头竞争报文CH_CP, CH_CP报文由报文类型、 节点ID及“机会”值构成, 其中报文类型表明这是一个簇头竞争报文. 具有比其他节点更高“机会”值的节点成为簇头, 并广播竞争成功报文CH_SUCCESS, CH_SUCCESS报文由报文类型、 节点ID构成. 节点收到CH_SUCCESS后, 更新其附近簇头列表, 并向距其最近的簇头发送加入簇报文CH_JOIN, 其由报文类型、 节点ID及簇头ID构成, 并将该簇头从簇头列表中删除. 接收到CH_JOIN报文的簇头检查其“大小”以判断是否接收新成员. 如果簇成员节点小于“大小”值, 发回成功加入报文CH_JOIN_SUCCESS, 其由报文类型、 节点ID、 成员ID及分配的时隙构成, 并将该成员依其机会值大小加入备份簇头列表. 否则, 发回加入失败报文CH_JOIN_FAIL, 包括报文类型、 节点ID和成员ID构成, 表明没有新成员节点的空间了. 当某个节点接收到CH_JOIN_FAIL报文时, 如其簇头列表非空, 则发送CH_JOIN报文给下一个最近的簇头, 直至其加入到某个簇. 最差情况下, 簇头列表空时节点仍无法加入到某簇, 则其自身选为簇头. 簇形成后, 根据模糊控制器输出每个节点的机会值大小, 按照机会值由高到低的原则形成备份簇头列表, 各簇头向簇内广播备份簇头列表报文CH_Bch, 该报文包括报文类型、 节点ID及备份簇头列表. 接收到CH_Bch的节点保存备份簇头列表, 若节点ID与列表中第一个备份簇头ID相同, 则成为备份簇头, 其他节点标记该节点为备份簇头.

表1 模糊规则

DFUC算法的伪代码如下.

算法1DFUC算法.

n=网络节点数；

si=第i个传感器节点；

si.state=init_state；

fori=1 tondo

si.RE=节点剩余能量,si.CD=节点中心度,si.DBS=节点到基站的距离；

Chance, Size=FuzzyC(si.RE,si.CD,si.RE,si.DBS)；

end for

forj=1 tondo

向邻居节点发送簇头竞争报文CH_CP=[MSG_TYPE,ID,Chance]；

根据竞争报文生成邻居节点列表ListN=[IDx,Chancex;IDy,Chancey;…]

if (sj.Chance>Lista>sID.Chance)

向邻居节点广播竞争成功报文CH_SUCCESS=[MSG_TYPE,ID]；

sj.state=CH_state；

else

while (sj簇头列表不为空)

向距离最近的簇头发送加入簇报文CH_JOIN=[MSG_TYPE,ID,CH_ID]

if (该簇头的成员数>size)

该簇头返回加入簇失败报文CH_JOIN_FAIL=[MSG_TYPE,ID,CM_ID]；

将该簇头从sj簇头列表中删除；

else

该簇头返回加入簇成功报文CH_JOIN_SUCCESS=[MSG_TYPE,CM_ID,ID,Slot]；

根据邻居列表ListN更新备份簇头列表ListB；

sj.state=CM_state；

end if；

else

该节点声明自己成为簇头；

sj.state=CH_state；

end while；

end if；

end for.

2.2 数据传输阶段

簇一旦建立, 簇成员节点即可基于分配的时隙开始数据传输. 在该阶段, 所有传感器节点都在消耗能量, 因此, 无论是簇头还是簇成员都可能出现能量耗尽的情形. 一旦有簇成员节点失效, 则节点中心度将发生变化, 从而影响节点成为簇头机会和簇大小值, 而如果簇头节点死亡, 则整个簇覆盖区域都不能被监测. 因此, 对失效的簇头和成员节点进行处理非常必要. 为了维护创建的簇, 簇成员需经常计算其模糊控制器输出, 并将成为簇头的机会值随数据同时发送给簇头. 簇头基于接收的机会值更新备份簇头列表, 更新的列表通过一个数据请求报文周期性发送给簇成员, 以确保实时更新最合适的备份簇头, 从而实现当簇头死亡时其成员能尽快被通知, 以避免网络中数据的丢失, 且成员死亡时, 簇头将其从备份簇头列表中移除. 实现过程如图2所示, 采用TDMA方式监视簇头和成员.

图2 数据传输与容错Fig.2 Data transmission and fault tolerance

由图2可见, 成员一旦接收到一个数据请求报文则发送其数据包, 如果簇头在帧尾没有收到请求的数据, 则给该成员打上错误标记. 簇头在下一个周期时隙发出另一个请求, 如果还未收到请求的数据, 则认为该成员永久故障, 并将其从备份簇头列表中移除. 同理, 成员在所分配的时隙等待来自其簇头的数据请求, 如果成员在帧尾没有接连收到数据请求报文, 则认为簇头可能出现临时故障, 它将等待下一相应时隙接收数据请求报文, 如果还未接收到数据请求报文, 则认为簇头出现永久故障. 于是, 成员检查其接收的簇头最近更新的备份簇头列表, 并将第一个节点作为簇头发出加入簇报文, 等待确认报文. 该节点也可能失效, 一旦未接收到确认报文, 则以列表的下一个节点为簇头发出加入簇报文, 直至最后加入到某个簇头.

3 仿真实验与分析

下面将本文DFUC算法与LEACH算法[5]、 DUCF算法[4]及WUCH算法[3]进行性能比较. LEACH算法是一个标准分簇协议, WUCH算法是一种新的非均匀分簇协议, DUCF算法是无线传感器网络分布式基于模糊逻辑的非均匀分簇协议. 在MATLAB仿真环境下, 100个节点随机分布在面积为(200×200)m2的测试区域中, 基站坐标为(100,100). 仿真参数为： 数据位数为4 000, 节点初始能量为1 J,Eelec=50 nJ/bit,εfs=10 pJ/bit,εmp=0.001 3 pJ/bit,d0=87 m, 数据包大小为500个字节, 控制包大小为25 个字节.

每个控制包大小为25个字节, 数据包大小为500个字节, 比控制报文大很多, 仿真实验中也包含了这些控制包的通信代价, DFUC算法和DUCF算法中所有节点上的模糊控制器的运行能耗忽略不计， LEACH算法期望的簇头百分数为0.1, 传感器节点的通信半径取40 m, 以确保网络中的所有节点都能就近加入一个簇.图3为存活节点数随运行轮数的变化曲线,图4为剩余总能量随运行轮数的变化曲线.

图3 网络存活节点数对比Fig.3 Comparison of number of network surviving nodes

图4 剩余总能量对比Fig.4 Comparison of total residual energy

由图3可见, 随着网络运行轮数的增加, DFUC算法与其他3种算法相比能很好地均衡网络能耗, 从而有效延长网络生命周期. 这是因为DFUC算法综合考虑了节点剩余能量、 节点中心度及与基站的距离确定簇头及簇的大小, 并在数据传输阶段提高了容错能力, 降低了重新成簇的能耗.图4对比了4种算法的剩余总能量随运行轮数增加的变化情况. 由图4可见, 由于DFUC算法在簇形成阶段和数据传输阶段综合考虑了多种影响因素, 因此本文算法波动较小、 生存时间更长.

综上所述, 本文提出了一种基于模糊控制理论的无线传感器网络非均匀分簇算法DFUC, 基于剩余能量、 节点中心度、 节点与基站的距离等多个参数, 通过模糊控制器计算输出成为簇头机会和簇大小值, 使最优节点成为簇头并限制簇的大小, 成员节点构成备份簇头列表. 通过TDMA机制, 实时更新该列表使最合适的节点成为备份簇头. 一旦簇头失效, 则其结果总能确保一个备份簇头替代簇头. 通过算法的网络存活节点数及网络剩余总能量进行了仿真测试, 结果表明, 相对于LEACH算法、 DUCF算法与WUCH算法, DFUC算法可获得较长的生命周期, 性能优于其他算法, 更适于实际应用.