在无线传感器网络中,由于没有固定的基础网络设施,传感器节点以广播的形式进行通信,容易引起广播风暴等问题。为了提高网络带宽的利用率,降低传感器能源消耗,通常利用连通支配集在无线传感器网络中虚拟出一个骨干网络,作为通信的中继节点。然而,最小连通支配集的构造作为一个全局优化问题,已被证明是一个NP难问题,因此越来越多的学者对在无线传感器网络中构造最小连通支配集这一问题开展了广泛又深入的研究。本文以静态的无线传感器网络为研究目标,结合启发式算法理论,提出了一种基于集合划分的迭代禁忌搜索启发式算法(RSN-TS)来求解最小连通支配集问题。算法主要利用集合划分的思想,将网络中不同的节点置于不同集合之中,然后利用迭代禁忌搜索启发式算法进行快速评估、迭代、交换各集合中的节点,从而获得近似最小连通支配集或求解出最小连通支配集。通过对国际公共算例的测试,并与其他学者所提出的精确算法,启发式算法的对比实验发现,本文所提出的RSN-TS算法是求解最小连通支配集问题的高效算法。此外,本文还分析了一些影响RSN-TS算法性能的关键部件,对算法中使用到的快速增量评估技术,扰动机制以及禁忌搜索算法做了不同的对比实验。