【摘要】 在无线网络通信中,承担着繁重路由任务的虚拟骨干常常可以用一个连通控制集(CDS)来模拟。连通控制集的大小是无线网络虚拟骨干质量的重要度量。三维空间的无线网络,常常可以用一个单位球(UBG)来模拟。为了构建一个新的单位球的1-连通m-控制集,提出并证明了单位球的极大独立集的一个上界,这个上界小于现有的单位球的极大独立集(MIS)的上界。借助于这一上界,设计了一个计算三维空间无线网络的1-连通m-控制集算法,证明通过该算法获得的1-连通m-控制集S与最优的1-连通m-控制集OPT的大小满足关系■。更多还原

【Abstract】 In wireless network communication, a virtual backbone with heavy routing task can often be simulated with a connected dominating set(CDS). The size of CDS is an important measure of the quality of virtual backbones in wireless network. A wireless network in 3D space can often be simulated with a unit ball(UBG). In order to construct a new 1-connected m-dominating set of a unit ball graph, this paper proposes and testifies an upper bound of the size of a Maximal Independent Set(MIS) in a unit ball graph, and it is better than that existing work. Based on the upper bound that it designs an algorithm to compute the 1-connected m-dominating set, and proves that the relationship between the size of the 1-connected m-dominating set obtained by executing the proposed algorithm and the optimal minimum 1-connected m-dominating set is follows ■更多还原