首页> 外文会议>2010 IEEE 30th International Conference on Distributed Computing Systems >Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless Networks
【24h】

Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless Networks

机译:无线网络中具有最小路由成本的连接控制集的分布式构造

获取原文
获取外文期刊封面目录资料

摘要

In this paper, we will study a special Connected Dominating Set (CDS) problem ȁ4; between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in a special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. Thus, energy consumption and delivery delay can be reduced greatly. CDS has been studied extensively in Unit Disk Graph (UDG) or Disk Graph (DG). However, nodes in networks may have different transmission ranges and some communications may be obstructed by obstacles. Therefore, we model network as a bidirectional general graph in this paper. We prove that constructing a minimum MOC-CDS in general graph is NP-hard. We also prove that there does not exist a polynomial-time approximation algorithm for constructing a minimum MOCCDS with performance ratio ρlnδ, where ρ is an arbitrary positive number (ρ
机译:在本文中,我们将研究一个特殊的连通支配集(CDS)问题ȁ4;在网络中任何两个节点之间,至少存在一条最短路径,所有其中间节点都应包含在名为最小路由成本CDS(MOC-CDS)的特殊CDS中。因此,通过MOC-CDS进行路由可以确保任何一对节点之间的每个路由路径也是网络中的最短路径。因此,可以大大减少能量消耗和传送延迟。 CDS已在单位磁盘图(UDG)或磁盘图(DG)中进行了广泛的研究。但是,网络中的节点可能具有不同的传输范围,并且某些通信可能会受到障碍物的阻碍。因此,本文将网络建模为双向通用图。我们证明在一般图中构造最小的MOC-CDS是NP-hard的。我们还证明不存在用于构造性能比为ρlnδ的最小MOCCDS的多项式时间近似算法,其中ρ是任意正数(ρ

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号