无线传感器网络是计算、通信和传感器这三项技术相结合的产物,它随着微处理器和无线通信技术的发展,在军事、医疗、环境等方面具有广泛的应用潜力。由于传感器节点能量有限,节点的失效会导致网络链路失败,因此在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。本文采用集中式算法研究连通支配集的构造,主要适用于具有中心控制或管理节点的无线传感器网络。对于1-连通1-支配集的构造,本文详细系统地比较了单方向搜索和多方向搜索两种集中式算法。通过比较得出,单方向搜索算法运行的时间短,多方向搜索算法构造的连通支配集小。为了提高网络的容错性和可靠性,本文提出两种2-连通2-支配集的集中式构造算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点的状态都为2-被支配,然后再使图中所有支配点构成回路。仿真结果表明算法先回路后支配适用于节点密度较低的网络,而算法先支配后回路适用于节点密度较高的网络。在某些特殊领域,需要构造容错性更高和可靠性更好的网络,本文提出k -连通k -支配集的集中式构造算法, k适用于任意自然数。该算法被称作先支配后连通,即首先保证图中所有节点都变为支配点或k-被支配点,其次选择一个边缘支配点着色,然后对其它支配点逐点着色,着色的条件是该点是已着色节点的邻接点,且和已着色节点均为k-连通,若不满足此条件,添加适当的支配点再接着着色,直到图中所有支配点均被着色为止。最后通过计算机编程实现,证明了该算法的有效性。