2-连通2-支配集的集中式构造  

On constructing 2-connected 2-dominating set using two centralized algorithms

作　　者：孙立山[1] 张瑞宏[1] 武文斌[1] 

机构地区：[1]哈尔滨工业大学电气工程及自动化学院,哈尔滨150001

出　　处：《计算机工程与应用》2009年第15期107-110,176,共5页Computer Engineering and Applications

摘　　要：在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。提出构造网络2-连通2-支配集的两种集中式算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点都要变成2-被支配点,然后再使图中所有支配点构成回路。In wireless sensor networks,a connected dominating set is used to construct a virtual backbone network for layered routing.lt 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.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]