期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于最小生成树的连通支配集求解算法 被引量：2

Novel connected dominating set algorithm based on minimum spanning tree
下载PDF
导出
摘要 针对无线网络中的连通支配集(CDS)问题,通过分析得到了CDS的一个重要性质,即简单连通无向图的最小CDS是该图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论,设计了一个新的连通支配集求解算法,实验表明,新算法较前人的算法有更好的性能。 Through in-depth analysis, an important property of Connected Dominating Set （CDS） in wireless network was obtained, in which the smallest CDS of a simple connected graph is the non-leaf nodes of a spanning tree with most leaf nodes. A new CDS algorithm was designed on the basis of the analysis. Simulation results show that the algorithm possess better performance than others.
作者 高文宇
机构地区 广东商学院信息学院
出处 《计算机应用》 CSCD 北大核心 2009年第6期1490-1493,共4页 journal of Computer Applications
基金 广东省自然科学基金资助项目(8151032001000013)
关键词 连通支配集 无线传感器网络 生成树算法 Connected Dominating Set （CDS） Wireless Sensor Network （WSN） spanning tree algorithm
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献12

  • 1NI S Y, TSENG Y C, CHEN Y S. The broadcast storm problem in a mobile Ad Hoc network [ C]// MobiCom'99: Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking. [ S. l. ] : ACM Press, 1999:152 - 162.
  • 2DAI F, WU J. Performance analysis of broadcast protocols in Ad Hoc networks based on self-pruning [ J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15 (11) : 1 - 13.
  • 3彭伟,卢锡城.一个新的分布式最小连通支配集近似算法[J].计算机学报,2001,24(3):254-258. 被引量：42
  • 4DAS B, HARGHAVAN V B. Routing in Ad Hoc networks using minimum connected dominating sets [C]// ICC'97: IEEE International Conference on Communications. Monreal, Quebec: IEEE Press, 1997:1-20.
  • 5LEE J, MANS B. Energy efficient virtual backbones for reception aware MANET [ C]//VTC 2006-Spring: Proceedings of the 63rd IEEE Vehicular Technology Conference. Montreal: IEEE, 2006, 3: 1097 - 1101.
  • 6许力,林志伟.基于图着色的无线自组网极小连通支配集算法[J].通信学报,2007,28(3):108-114. 被引量：17
  • 7GUHA S , KHULLER S . Approximation algorithms for connected dominating sets [ J]. Algorithmica, 1998, 20 (4): 374-387.
  • 8WU J, LI H. On calculating connected dominating set for efficient routing in Ad Hec wireless networks [ C]// Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. Seattle: ACM, 1999:7 - 14.
  • 9WAN P, ALZOUBI K, FRIEDER O. Distributed construction of connected dominating set in wireless Ad Hoc networks [ C]//IEEE INFOCOM'02. Washington, DC: IEEE press, 2002: 141-149.
  • 10CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to Algorithms[ M]. 2nd. Cambridge, MA: The MIT press, 2001.

二级参考文献22

  • 1许力,张继东,郑宝玉,杨震.移动自组网能量保护策略研究进展[J].通信学报,2004,25(9):93-103. 被引量：16
  • 2Peng Wei，J Software，2000年
  • 3Jiang MingLiang，Internet Draft（To appear），1999年
  • 4Wu Jie，Proc 3rd in Ternational Workshop on Discrete Algorithms and Methods for Mobile Computingand Communic，1999年
  • 5Ni S Y，Proc 5th Annual ACM/IEEE Int Conference on Mobile Computing and Networking，1999年
  • 6殷剑宏 吴开亚.图论及其算法[M].合肥:中国科学技术大学出版社,2004.152.
  • 7RAM R,JASON R.A brief overview of mobile ad hoc networks:challenges and directions[J].IEEE Communications Magazines.2002,40(5):20-23.
  • 8GUPTA P,KUMAR P R.The capacity of wireless networks[J].IEEE Transactions on Information Theory,2000,IT-46(2):388-404.
  • 9CORSON S,MACKER J.Mobile ad hoc networking (MANET):routing protocol performance issues and evaluation considerations[EB/OL].RFC 2501,http://www.ietf.org/rfc/rfc2501.txt,1999.
  • 10ALZOUBI K M.Virtual Backbone in Wireless Ad hoc Networks[D].Illinois Institute of Technology,Chicago,USA.2004.

共引文献53

同被引文献24

  • 1杨浩淼,孙世新,李洪伟.双线性Diffie-Hellman问题研究[J].四川大学学报（工程科学版）,2006,38(2):137-140. 被引量：12
  • 2YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor networkssurvey [J]. Computer Networks, 2008, 52(12): 2292-2330.
  • 3XUE K P, MA C S, HONG P L, et al. A temporal-credential-basedmutual authentication and key agreement scheme for wireless sensornetworks [J]. Journal of Network and Computer Applications, 2013,36(1):316-323.
  • 4WANG S S, YAN K Q,WANG S C, et al. An integrated intrusiondetection system for cluster-based wireless sensor networks[J]. ExpertSystems with Applications, 2011,38(12):15234-15243.
  • 5PANTAZIS N A, NIKOLIDAKIS S A, VERGADOS D D. En-ergy-efficient routing protocols in wireless sensor networks: a sur-vey[J]. IEEE Communications Surveys &Tutorials, 2013, 15(2):551-591.
  • 6GUERMAZI A, ABID M. An efficient key distribution scheme tosecure data-centric routing protocols in hierarchical wireless sensornetworks [J]. Procedia Computer Science, 2011, 5: 208-215.
  • 7ZHANG P F, XIAO G X,TAN H P. Clustering algorithms for maxi-mizing the lifetime of wireless sensor networks with energy-harvestingsensors[J]. Computer Networks, 2013,57(14): 2689-2704.
  • 8KACIMI R, DHAOU R, BEYLOT A L. Load balancing techniquesfor lifetime maximizing in wireless sensor networks[J]. Ad Hoc Net-works, 2013,11(8): 2172-2186.
  • 9DARABKH K A, ISMAIL S S, Al-SHURMAN M,et al. Performanceevaluation of selective and adaptive heads clustering algorithms overwireless sensor networks [J]. Journal of Network and Computer Appli-cations, 2012, 35(6): 2068-2080.
  • 10DUTTA R, BARUA R, SARKAR P. Pairing-Based CryptographicProtocols: A Survey[R]. Cryptology Eprint Archive, Report 2004/064,2004.

引证文献2

二级引证文献4

计算机应用
2009年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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