无线传感网络,也叫无线传感器网络,它类似于小规模互联网,是一种由大量具有无线通信能力的小型或者微型传感器自组织构成的互连网络。无线传感网络作为当今信息领域新的研究热点,已有大量相关的研究工作。其中,由于传感器节点的电源容量较小且不可充电,因此提高能量利用率和延长无线传感网络的生命周期成了主要的研究目标。LEACH是一种经典的、影响最为广泛的分布式、自组织的分簇协议。LEACH协议的基本思想是使用分布式的建簇算法,即所有的节点都参与簇头的决策中,这种机制实现起来比较简单,并且能将网络的能耗平均进行分配;使用的数据摘要和融合技术也大大降低了减少了传输能耗。但它也存在不足之处:忽略了节点的剩余能量和地理位置的巨大影响,使得快死亡和处于稀疏区域的节点都能以一定的概率被选举成为簇头;p值是需要人为预先设定的,但是要设定出一个能使分簇效果非常好的p值是非常难做到的。超图是一种能有效表现节点之间关联和依赖关系的基本数据结构。超图模型已被广泛应用于图片检索以及视频分割等领域,但在无线传感网络领域却鲜有研究与应用。而且传统的超图划分算法也有很明显的弊端:需要人为预设聚类个数,没有一个合理的评判划分质量的标准。本文针对LEACH算法的以上缺点,从聚类思想的角度出发,将图模型和无线传感网络结合起来,基于超图理论和分割聚类算法,提出了一种新型的分簇算法,主要基于节点剩余能量和密集度进行建模和分簇。考虑到传统超图划分算法的弊端和不足,本文研究并提出了模块度函数这个新概念,从簇内高内聚簇间低耦合的角度定义了模块度的计算公式,将其作为超图划分的寻优标准,同时也是超图终止划分的条件之一。除此之外,本文还设计并实现了一种超图多层次迭代聚类分割算法,对无线传感网络建模成的超图不断迭代二分,最终形成一种较好的网络拓扑结构。考虑到算法的计算复杂度问题,本文对算法中的最优切割点进行了优化,使得最优切割点的计算复杂度只与包含切割点的超边呈线性相关,大大降低了超图划分的时间复杂度。最后,本文对算法和LEACH算法进行了仿真实验并做了三个方面的对比分析,实验结果表明本文算法在节点能量的利用效率和网络生存期均优于LEACH算法,验证了本文算法的合理性和有效性。