期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
A Distributed Design for Minimum 2-Connected m-Dominating Set in Bidirectional Wireless Ad-Hoc Networks 被引量:3
1
作者 Xiaofeng Gao bosheng xu Jun Li 《Tsinghua Science and Technology》 SCIE EI CAS 2012年第5期553-566,共14页
Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected ... Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected m-Dominating Set ((k,m)-CDS) in a network as a fault-tolerant virtual backbone to help the routing process, which will save the energy of non-dominators and improve the network performance significantly. Considering the economic cost and efficiency, we choose (2,m)-CDS as the object of this paper, which is helpful enough in practical applications and has a smaller size. We firstly study the existing algorithms for (k,m)- CDS and figure out the problems of these designs. Then we propose a new distributed algorithm named Dominating Set Based AIgorithm (DSBA) with three sub-routines: Dominating Set AIgorithm (DSA), Connection Algorithm (CA), and Connectivity Expansion Algorithm (CEA). Instead of commonly used Maximal Independent Set (MIS), we pick dominating set directly from the given graph, and then connect them by a two-step ring based connecting strategy to satisfy the 2-connectivity. We also provide the correctness and complexity analysis of DSBA. At last, we compare DSBA with the last construction Distributed Deterministic Algorithm (DDA) by several numerical experiments. The simulation results show that DSBA improves over 30 percent of the performance of DDA, proving that DSBA is more practical for real-world applications. 展开更多
关键词 connected dominating set FAULT-TOLERANCE distributed algorithm APPROXIMATION
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部