无线传感器网络的图论聚类算法研究

无线传感器网络从出现至今，己经从最初的节点研制、网络协议设计，发展到了智能群体的研究阶段，同时也已成为国内外一项新的IT热点技术。该技术吸引了大量的学者对其展开多方面的研究,并取得了一些进展，包括众多的节点平台和大量的通信协议。然而，目前还没有形成一套完整的理论和技术体系来支撑这一新兴领域的发展,还有众多的科学与技术问题尚待突破,这也是信息领域面临的一项极具有挑战性的课题。

1  无线传感器网络中的聚类问题

由于无线传感器网络存在能量约束，而减少需要传输的数据量能够有效地节省节点能量，因此，在从各个节点收集数据的过程中，可以利用节点的本地计算与存储能力对数据进行融合处理，去除冗余信息，达到降低能量消耗的目的。此外，由于节点易失效,无线传感器网络同时也需要采用数据融合技术来对多份传感数据进行综合，以达到提高信息准确度的目的。

当传感器分布在一个比较大的区域，而且数量也比较大的时候，传感器的数据如何向融合中心传递是一个需要解决的问题。目前比较流行的是采用三层网络来解决，图1所示是三层分级传感器网络的结构示意图。无论如何，虽然采用三层网络结构虽然必须进行分簇,但仍然是一种相对比较合理的处理方式。

 现在通常采用的分簇方法是聚类算法。聚类是一种众所周知而且已经被广泛使用的数据分析技术。所谓聚类,就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。现在文献中的大部分算法都是基于单一环境的，然而，很多应用中的数据源大都分布在网络环境下,而且在聚类前将这些数据釆集到一个中心位置并不是一个合适的选择，而通过无线通信方式连接的传感器网络就是这样的环境,在这里，将数据集中起来进行聚类非常困难，而且可扩展性也不好。这其中的原因有很多，比如无线传感器网络中有限的通信带宽以为感知节点正常运行提供能量的电池能源很有限；无线传感器网络是以AdHoc方式进行通信的，只允许相邻的感知节点之间进行通信。这就需要数据分析算法也要以同样的方式进行通信，目前，这样的聚类算法还没有。

通常,聚类技术包括以下几类：划分方法(Parti-tioningmethod)、层次方法(Hierarchicalmethod)、基于密度的方法(Density-basedmethod)，基于网格的方法(Grid-basedmethod)和基于模型的方法(Model-basedmethod)。这些方法应用于无线传感器网络中，都没有考虑到节点布局的复杂性，所以效果都不是非常理想。

本文以传感器网络节点布局为复杂的图结构，提出采用图论的方法来选择合理的节点作为簇，以达到花费最小能量代价，完成信息到融合中心的传递的目的。其具体算法框图如图2所示。 

2  图论聚类算法的实现

2.1  图广度优先搜索算法

根据节点的总数目N和需要分成的簇数M,便可以得到每个簇的节点数为N/M,在整个图的广度优先搜索的过程中，记录下搜索的节点数，达到N/M后记所有节点，并将累计节点数重新清零，直至整个图完全遍历完，这样就可以将相邻的节点分成M个子图，每个子图为一个簇。其图广度优先搜索算法的具体过程如下：

首先,从图中某个顶点出发(设为vi)访问vi,再从vi出发，依次访问vi的所有未被访问的邻接点，再从这些邻接点出发，依次访问它们的所有未被访问的邻接点，如果图中仍有未被访问的顶点，则从中选择一个作为起点，重复上述过程，直到所有顶点均被访问过为止。

2.2  广度优先搜索算法的VC＋＋实现屋

广度优先搜索算法的VC＋＋实现代码如下：

2.3  簇内节点信息传递的最优路径实现

对于簇内的信息传递，其目标也是用最小的能量代价将信息传给簇头，本文选择普里姆算法来实现簇子图的最优构造。普里姆算法是图的最小生成树的一种构造算法。

假设W_N=(V,{E})是一个含有N个顶点的连通网，T_v是W_N上最小生成树中顶点的集合，T_E是最小生成树中边的集合。显然，在算法执行结束时，Tv=V,而T_E是E的一个子集。在算法开始执行时，T_E为空集，Tv中只有一个顶点，因此，按普里姆算法构造最小生成树的过程是：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，并逐条加在生成树上，直至生成树中含有N-1条边为止。

找出子图的最小生成树后,可选择直接连接节点最多的节点作为簇头，其他节点的信息则间接或直接传给簇头，最后由簇头传给数据融合中心。

3  算法性能分析

本文在一台PC机上用VC++6.0编程环境实现了该算法，其机器配置为Windows XP professional操作系统，1GHz内存，120GHz硬盘，CPU主频为2.0GHz。本文用多线程工作方式来模拟无线传感器网络的工作环境。仿真过程中，将无线传感器网络基于图论的分布式聚类算法(上面的线条)与将所有数据传回sink节点进行计算的集中式K-平均算法(下面的线条)在性能上进行了比较，最后给出了随着网络节点数目的增加，算法执行时间的变化情况。图3所示是图论分布式聚类算法与集中式K-平均算法的性能比较曲线。

图3中，横坐标为节点数目，纵坐标为时间(单位为s)，从该仿真实验中可以明显看出，其图论分布式聚类算法比集中式K-平均算法的性能要优越。 

4  结论

基于图论的分布式聚类算法与将所有数据传回sinK节点进行计算的集中式K-平均算法在性能相比有较大提高，聚类算法的使用可以降低无线传感器网络在信息传递过程中的能量消耗。下一步的工作将改进簇内部信息传递的方式,进一步降低信息传递过程中的能量消耗。