期刊文献+

无线网络中一种简单的弱连通支配集构造策略

Simple construction strategy for weakly connected dominating set in wireless networks
下载PDF
导出
摘要 通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O(|N|+|E|)。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。 This paper proposes a central construction algorithm of weakly connected dominating sets in wireless networks by constructing edge dominating sets, simultaneously gives two pruning strategies to reduce the size of the produced set.The time complexity of the algorithm is O(|N|+|E|).It proves the correctness of the algorithm and shows the effectiveness of the algorithm.Compared to existed results,the algorithm proposed produces weakly dominating sets with smaller size.
作者 王康 禹继国
出处 《计算机工程与应用》 CSCD 北大核心 2011年第20期81-84,共4页 Computer Engineering and Applications
基金 国家自然科学基金(No.10471079) 山东省中青年科学家奖励基金(No.2005BS01016) 山东省科技攻关计划(No.2009GG10001014) 山东省教育厅科研项目(No.J07WH05)~~
关键词 无线网络 弱连通支配集 边支配集 wireless networks weakly connected dominating set edge dominating set
  • 相关文献

参考文献14

  • 1Duckworth W, Mans B.Randomised algorithms for finding small weakly-connected dominating sets of regular graphs[C]// LNCS 2653 : CIAC, 2003 : 83-95.
  • 2Chen Y P, Liestman A L.Approximating minimum size weakly connected dominating sets for clustering mobile ad-hoc networks[C]// Proceedings of 3rd ACM International Symposium on Mobile Ad-Hoc Networking and Computing.New York: ACM Press, 2002:165-172.
  • 3Dubhashi D, Mei A, Panconesi A, et al.Fast distributed algorithms for (weakly)connected dominating sets and linear-size skeletons[J].Journal of Computer and System Sciences, 2005,71 : 467-479.
  • 4Ephremides A, Wieselthier J, Baker D.A design concept for reliable mobile radio networks with frequency hopping signaling[J]. Proceedings of the IEEE, 1987,75 : 56-73.
  • 5Clark B N,Colbourn C J,Johnson D S.Unit disk graphs[J].Discrete Mathematics, 1990,86:165-177.
  • 6Dunbar J E,Grossman J W,Hattingh J H,et al.On weakly connected domination in graphs[J].Discrete Mathematics, 1997, 167/ 168: 261-269.
  • 7Guha S,Khuller S.Approximation algorithms for connected dominating sets[J].Algorithmica, 1998,20(4) :374-387.
  • 8Wu J, Li H L.On calculating connected dominating set for efficient routing in ad hoc wireless networks[C]//Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 1999:7-14.
  • 9Han B, Jia W.Effieient construction of weakly-connected domi nating set for clustering wireless ad hoc networks[C]//IEEE GLOBECOM/EXPO, San Francisco, CA, USA, 2006.
  • 10Chen Y Z, Liestman A L.Maintaining weakly-connected domi nating sets for clustering ad hoc networks[J].Ad Hoc Net works, 2005,3 (5) : 629-642.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部