改进的FCM算法在UASN分簇中的应用

江萌萌，刘广钟

(上海海事大学 信息工程学院，上海 201306)

0 引 言

水声传感器网络(underwater acoustic sensor networks，UASN)由于水下环境的潜在利益和独特的挑战而受到学术界和工业界的高度重视。UASN允许大量的应用程序变得可行又有效，包括商业开发，海洋学数据收集和海岸线保护关于水声传感器网络方面的一些重要技术的研究引起了广泛重视[1-2]。

UASN由大量便宜的便携式传感器节点以自组织的方式组成，具有有限的功率，存储和计算能力。由于水下信道的复杂性，水声传感器网络环境下的数据传输速率和网络生存时间等都会受到严重影响，同时在水下工作想要更换节点电池是不可行的，所以节点的能量消耗必然引起人们的重视[3]。提出的分簇路由协议，可以通过仅允许一些节点与基站通信来减少能量消耗。这些称为簇头的节点收集该簇中的每个节点发送的数据，并将其融合数据发送到基站[4]。

在模糊聚类算法[5-6]中，样本按一定的隶属度分类，得到了样本属于各个类别的不确定性程度，这样更能准确地反映现实世界。水声传感器网络的分簇过程类似模糊聚类分析，将水声传感器节点分簇路由问题建模为样本空间的模糊聚类划分问题。整个UASN看作一个模糊聚类的对象集合，每个传感器节点作为该集合中的一个样本，最接近模糊聚类得到的聚类中心就是UASN中的簇头节点，聚类得到的子集就是UASN中的每个簇。

1 相关工作

目前已有的分簇算法是基于节点的剩余能量，簇头的位置分布和覆盖度等准则提出的。典型的分簇路由算法有LEACH[4]、HEED[7]、APTEEN[8]、DAEA[9]、TEEN[10]等。这里主要介绍基于模糊逻辑控制的CEFL分簇算法[11]。

在CEFL算法中，使用模糊逻辑控制模型中最常用的模糊推理技术，提出了基于能量、集中度和中心性三个描述符的簇头选举分簇算法，通过精确地修改每个模糊集的形状，进一步改善网络寿命和能量消耗。模糊规则库目前包括以下规则：如果能量高，集中度高，中心性接近，节点当选机会大。但该算法存在一些缺点：首先，每个节点概率地决定是否成为簇头，所以可能选出彼此相邻的两个簇头，增加了网络中耗尽的总能量。其次，CEFL算法最后生成的簇头节点的数量不是固定的，所以有时它可能大于或小于优选值。

针对上述问题，提出一种基于改进的模糊C-均值聚类算法的水声传感器网络分簇路由协议(FCM-L)。采用FACM-L对水声传感器节点进行聚类，在计算初始化聚类中心时通过考虑节点间的相对距离和能量衰减率这两个因素，避免了FCM算法对初始化聚类中心敏感这一缺点，并构造一个有效性函数来选定最佳聚类类别数，根据已产生的最佳聚类数完成水声传感器节点分簇过程。

2 网络模型

在分簇的UASN架构中，基站远离传感器节点并且是静止的，簇头节点负责控制簇内节点的协同工作，簇内节点向相应的簇头发送数据，簇头节点将收集到的数据信息压缩融合处理后将其发送到基站。

文中对网络模型做如下假设：

(1)假设水声传感器网络是同构网络，每个节点都有唯一的ID。

(2)主要针对二维静态水声传感器网络，不考虑节点移动性。

(3)每个节点都有可能竞选簇头。

(4)每个节点都具有相同初始能量，具有数据融合功能，而且节点能根据距离的远近来调整发射功率。

(5)基站的能量是无限的，而且能覆盖整个网络。

由于簇头节点不仅要完成通信，还要进行数据融合传输信息量，所以簇头节点的能量直接导致节点间的信息传输。这里将构建水声通信系统模型考虑节点在发送接收过程中确定节点传输数据所消耗的能量。引用文献[12-13]中的能耗模型，定义如下:

发送节点的最低发送功率为：

(1)

其中，P0表示节点接收端正常接收一个数据包的最低功率；k为能量扩展因子，通常取1.5；α为与频率有关的能力衰减系数，通常α=10α(f)/10，α(f)为吸收损耗系数：

(2)

其中，f表示节点工作频率。

节点能量衰减率为：

(3)

符号含义见表1。

表1 符号含义

3 基于FCM-L的分簇路由算法设计

3.1 基于FCM-L的模糊聚类模型

文中提出一种基于改进的模糊C-均值聚类算法的水声传感器网络分簇路由协议(FCM-L)。主要思想为将水声传感器节点作为分类对象，将其分为c个部分，其中每个部分都有一个聚类中心。这里需要利用FCM算法给出一个目标函数来调整聚类中心，当该目标函数值小于给定阈值时，停止迭代，得到最后的聚类结果。设被分类对象的集合为X={x1,x2,…,xn}，X为节点集合，xi表示每个节点。

3.1.1 初始化聚类中心

考虑FCM算法对初始化聚类中心敏感，容易出现局部最优，导致簇头节点在网络中分布不均匀。所以通过计算分析数据对象两两之间的距离与能量衰减率倒数的乘积，能量衰减越快，倒数越小，所以对于下式结果越小越好，以便得到一个较好的初始聚类中心。

(4)

比较分析找出两个节点之间最小的β，创建新的数据对象集Y1，使这两个节点归入Y1，即(xi,xj)∈Y1。然后在原数据集中删除xi，xj，原数据对象集变为(x1,x2,…,xn-2)，接着计算Y1中每一个节点与数据集X中每一个节点的距离与能量衰减率，找出最小的β，将该节点归入Y1中，设置阈值γ，当Y1中的节点个数达到一定阈值,新建数据对象集Y2，重复数据对象集Y1的形成过程，直到形成k个数据对象集。将这k个聚类中心作为K均值聚类算法的初始聚类中心。

于是把数据对象集X分成c类，设c个聚类中心向量构成矩阵W：

(5)

3.1.2 构造模糊相似矩阵

模糊分类中被分类的对象集合X中的对象xi以一定的隶属度属于某一类，因此每一类就认为是对象集合X上的一个模糊子集，每一种模糊分类就是一个c×n的模糊矩阵R。使用夹角余弦法求出隶属度rij，具体求解过程参考文献[14]。每个rij∈[0,1]，于是构造模糊相似矩阵R=(rij)c×n。

3.1.3 聚类求解

聚类准则是通过不断迭代使如下目标函数达到最小值，得到最终的聚类结果:

(6)

(7)

(8)

3.1.4 确定最佳聚类数

通过上述聚类方法得到一组聚类数c，接下来将构建一个有效性函数来确定一个最佳聚类数。根据文献[16]，衡量聚类结果的好坏可根据簇内的紧凑度和簇间的分离度决定，即簇内的对象尽可能紧凑，簇间尽可能分离。具体步骤如下：

首先选取得到的不同聚类类别数c，利用簇内紧凑度和簇间分离度决定最终聚类结果。

求解簇内紧凑度：

(9)

求解簇间分离度：

(10)

根据紧凑度度量簇内的紧致性，紧凑度越小，紧致性越好；分离度度量簇间的分离性，分离度越大，分离性越好。于是构造以下聚类有效性函数：

(11)

最后参考CS(c)，它越小代表较好的聚类结果与CS(c)最小值相对应的c值就是最佳的簇头节点数。

3.2 算法描述

Step1：输入对象集矩阵—水声传感器节点和节点特性指标矩阵。

Step2：根据上述改进算法计算初始化聚类中心。

Step3：构造模糊相似矩阵R=(rij)c×n。

Step4：根据式7更新聚类中心w。

Step5：根据式8更新模糊分类矩阵R。

Step7：计算有效性函数CS(c)，选择最小的CS(c)生成最佳聚类数c，利用聚类中心得到簇头，与聚类中心最近的节点当选簇头节点，并根据聚类结果形成c个簇。

4 仿真实验

使用MATLAB进行仿真实验并与基于模糊控制理论的CEFL方法进行比较。仿真实验中将采用理想的环境，主要考虑传感器节点发送数据、接收数据和进行数据融合所消耗的能量，通过分析网络中的总能量消耗和存活节点数目评定该协议的性能。

仿真实验是由100个水声传感器节点随机分布在100 m×100 m的范围内。将从簇头节点分布和节点平均剩余能量两个方面比较文中算法与CEFL的性能。利用水声通信能量模型，P0=2×10-3J/b作为数据能被接收的最低功率，融合功率Ed=5×10-4J/b，接收功率Pr=0.2×10-3J/b，每个节点的初始能量为0.5 J/node。

从图1(圆圈表示簇头节点)可以看出，实验仿真100次后，CEFL分簇算法得到的簇头节点分布不够均匀，有些距离较远的节点可能无法与簇头节点通信，容易使节点能耗不均匀，网络生存周期比较短，这是由于CEFL算法中每个节点概率地决定是否成为簇头，可能存在两个簇头彼此相邻选择的情况。而FCM-L算法采用改进的模糊C-均值聚类算法初始化聚类中心，能有效控制分簇结果陷入局部最优。从图2可看出，同样在仿真100次后，FCM-L选出的这5个簇头节点相较于图1分布均匀，而且簇头节点的个数也比较接近最佳簇头个数，相对来说能有效延长网络生存周期。

图1 CEFL簇头选举结果

图2 FCM-L簇头选举结果

图3是两种算法的节点总能量消耗比较。FCM-L算法相较于CEFL算法，它的能量消耗趋势相对缓慢一些，因为FCM-L算法根据节点间的距离与能量衰减率得到初始化聚类中心，保证了簇头节点能均匀分布在网络中，并权衡了簇头节点的能量消耗问题。所以可以看FCM-L算法得到的总能量消耗趋势比较缓慢，而且能量消耗结束的轮数也有一定的延迟。

图3 节点总能量消耗

图4是两种算法的死亡节点数量变化的比较。可看到在第230轮左右，利用FCM-L算法第一个节点开始死亡，比CEFL算法推迟了140轮，而且在FCM-L算法中节点的死亡趋势较为平缓，所以它的生命周期较CEFL算法延迟了500轮左右。这是由于FCM-L算法以合理的簇头个数进行分簇，得到一个负载均衡的网络结构，使得整个生命周期得到延迟。而CEFL算法产生的簇头个数具有不稳定性，导致节点死亡趋势相对较快和不稳定。

图5是在不同簇头个数下所有节点的总能量消耗比较。首先c=4时，明显看出它在整个网络中的能量消耗比c=5、c=6时的趋势较快，而且在1 200轮时能量已消耗殆尽，簇头个数为5和6时消耗趋势相差不大，但是当实验进行到第800轮以后，簇头个数为5时的能量消耗趋势逐渐缓慢，充分说明如果能选出一个最优的簇头个数将有效地减缓能量的消耗。

图4 死亡节点趋势图

图5 不同簇头个数的总能量消耗

5 结束语

提出了一种水声传感器网络簇头选举方法，将水声传感器网络的分簇过程建模为样本空间的模糊聚类划分问题。使用FCM-L对水声传感器网络节点进行聚类分簇，构造一个有效性函数确定划分最佳簇头数。与CEFL相比，FCM-L算法产生的簇头节点在网络中分布更加均匀，从而实现了网络寿命的显著增加，进一步改善了能量消耗。

由于在初始化聚类中心时，在每一次创建数据对象集的时候都要计算节点间的距离，虽然这一操作可以避免簇头节点陷入局部最优，但是也带来了一定的计算复杂度。因此，在以后的研究中可以通过降低计算复杂度来重新设置初始化聚类中心，使得这种分簇路由算法更加适用于水声传感器网络。