互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

自组织网络分布式最小连通支配集创建算法


□ 王凌燕 张 奇 刘爱民

  摘 要:针对无线自组织分组(Ad hoc)网络中最小连通支配集(MCDS)创建NP难问题,提出了一种分布式的最小连通集创建算法DMCA。DMCA基于最大独立集(MIS)的构建,只需要周围一跳邻居的信息,在不超过三跳距离的一对支配节点之间找出一条最短路径。对DMCA算法的性能分析表明,DMCA具有常数的近似比、线性的时间和消息复杂度。详细的仿真实验以及与其他创建最小连通支配集算法的比较表明,提出的DMCA算法在节点数量与节点传输范围变化时创建的最小连通集更小。
  关键词:分布式算法; 最小连通支配集; 自组织网络
  中图分类号: TN915.04文献标志码:A
  文章编号:1001-3695(2009)06-2241-03
  doi:10.3969/j.issn.1001-3695.2009.06.073
  
  Distributed MCDS constructing algorithm in Ad hoc networks
  WANG Ling-yan1, ZHANG Qi2, LIU Ai-min1
  (1. Dept. of Computer, Chenzhou Vocational Technical College, Chenzhou Hunan 423000, China; 2. School of Computer, Zhejiang University, Hangzhou 310018, China)
  Abstract:
  For the NP-hard problem of constructing minimum connected dominating set (MCDS) in Ad hoc networks, this paper proposed a novel distributed MCDS constructing algorithm called DMCA. DMCA constructed a MCDS for Ad hoc networks based on a maximal independent set (MIS). In DMCA, each node only required the knowledge of its one-hop neighbors and there existed only one shortest path connecting two dominators these were at most three hops away. The theoretical analysis shows that DMCA was fully localized, had a constant approximation ratio, and O(n) time complexity and O(n) message complexity. Detailed simulation results and comparisons with existed algorithms show that the proposed DMCA algorithm has less size of MCDS with varying node number and transmission range. ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017