关键词: 无线传感器网络, 连通支配集, 集中式算法, 2-连通图

Abstract: In wireless sensor networks，a connected dominating set is used to construct a virtual backbone network for layered routing.It is necessary to construct a connected dominating set as a virtual backbone network to balance efficiency and fault tolerance in some important occasion.In this thesis two centralized algorithms to construct 2-connected 2-dominating set are proposed，and they are First-Loop Second-Domination（FLSD） and First-Domination Second-Loop（FDSL） respectively.In FLSD，it begins with loop formation using dominating nodes，and then based on previous formed loop，the looping-in will continue until each non-dominating node’s being dominated by at least two dominating nodes.However，in FDSL，each non-dominating node being dominated by at least two dominating nodes is achieved before the loops with all dominating nodes are formed.

Key words: wireless sensor network, connected dominating set, centralized algorithm, 2-connected graph