首页 | 本学科首页   官方微博 | 高级检索  
     

无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法
引用本文:凤旺森,屈婉玲,王捍贫,张立昂.无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法[J].计算机工程与科学,2008,30(10):21-23.
作者姓名:凤旺森  屈婉玲  王捍贫  张立昂
作者单位:北京大学信息科学技术学院软件研究所,北京,100871;高可信软件技术教育部重点实验室,北京,100871
基金项目:国家高技术研究发展计划(863计划)
摘    要:在无线自组织网络中,经常选取一些节点形成虚拟主干网,用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点,虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网,并通过模拟实验评估了算法的性能。近年来,Wang Feng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。

关 键 词:2-连通是一支配集  近似算法  无线自组织网络  虚拟主干网

An Approximation Algorithm for Constructing a 2-Connected k-Dominating Virtual Backbone in Wireless Ad Hoc Networks
FENG Wang-sen,QU Wan-ling,WANG Han-pin,ZHANG Li-ang.An Approximation Algorithm for Constructing a 2-Connected k-Dominating Virtual Backbone in Wireless Ad Hoc Networks[J].Computer Engineering & Science,2008,30(10):21-23.
Authors:FENG Wang-sen  QU Wan-ling  WANG Han-pin  ZHANG Li-ang
Abstract:Some nodes are often chosen to form a virtual backbone in wireless ad hoc networks in order to support routing and other tasks such as area monitoring.Because of the inherent node(link)failures in wireless networks,virtual backbones should be fault-tolerant.Recently,researchers have suggested to construct a fault-tolerant virtual backbone with a k-connected k-dominating set,and evaluated the performance of their algorithms via simulations.Feng Wang et al.have designed an approximation algorithm to construct a 2-connected fault-tolerant virtual backbone in wireless ad hoc networks.In this paper,a constant ratio approximation algorithm is designed to find a 2-connected k-dominating virtual backbone.
Keywords:2-connected k-dominating set  approximation algorithm  wireless ad hoc network  virtual backbone
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程与科学》浏览原始摘要信息
点击此处可从《计算机工程与科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号