• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Connected dominating set in wireless ad hoc networks.
【24h】

Connected dominating set in wireless ad hoc networks.

机译：无线ad hoc网络中的连接控制集。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A Wireless Ad Hoc Network (WANET) is dynamically formed by a collection of static or mobile hosts communicating with each other over a scarce shared wireless channel, in absence of a fixed infrastructure and a predefined central administration system. Wireless ad hoc networks can be flexibly and quickly deployed for many applications such as automated battlefield, search and rescue, and disaster relief, etc. Due to its characteristics of dynamic topology, multi-hop communication and strict resource limitation, routing in WANET presents a challenging problem and has drawn significant attentions.;Although no physical backbone is present, a virtual backbone formed by nodes in a Connected Dominating Set (CDS) can be superimposed and plays a very important role in routing, broadcasting and connectivity management in wireless ad hoc networks. However, the construction of an Minimum Connected Dominating Set (MCDS) is proven to be NP-hard. Therefore research work has been focused on designing approximation algorithms for the MCDS problem. A number of approximation algorithms are presented in this dissertation.;Firstly, in homogeneous wireless ad hoc networks, where the network topology can be represented by a Unit Disk Graph, a completely localized distributed algorithm called r-CDS is proposed to construct an MCDS, which has a constant performance ratio of 172. Applying certain pruning rules on locally redundant nodes, the size of the CDS can be further reduced.;Secondly, in a special case of heterogeneous wireless ad hoc networks where the network topology can be represented by a Disk Graph with Bidirectional links (DGB), two efficient approximation algorithms are presented to obtain an MCDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. Distributed versions of these algorithms are also implemented. The size relationship between a maximal independent set and a CDS is shown, as well as a bound of the maximum number of independent neighbors of a node in disk graphs.;Lastly, a polynomial time approximation scheme (PTAS) is presented to find a minimum d-hop connected dominating set (d-CDS) in a class of growth-bounded graphs, including unit disk graphs, unit balls, etc., which can represent a majority of existing wireless networks. Based on predefined network parameters, the growth-bounded graph can be partitioned into clusters. d-CDS is constructed for each cluster and the union of each d-CDS forms a d-CDS for the graph, with some additional nodes connecting them. Performance and complexity analysis of the PTAS are provided.
机译：无线自组织网络（WANET）由静态或移动主机的集合动态形成，这些主机通过稀缺的共享无线信道相互通信，而没有固定的基础结构和预定义的中央管理系统。无线自组织网络可以灵活，快速地部署到许多应用中，例如自动化战场，搜索和救援以及救灾等。由于其具有动态拓扑，多跳通信和严格的资源限制的特性，WANET中的路由提供了一种具有挑战性的问题，并引起了广泛的关注。尽管没有物理骨干网，但可以叠加由连接的支配集（CDS）中的节点形成的虚拟骨干网，并且在无线ad hoc中的路由，广播和连接管理中起着非常重要的作用。网络。但是，最小连接支配集（MCDS）的构造被证明是NP难的。因此，研究工作一直集中在为MCDS问题设计近似算法上。本文首先提出了多种近似算法。首先，在同类无线自组织网络中，网络拓扑可以用单位圆图表示，提出了一种完全本地化的分布式算法r-CDS来构造MCDS。其恒定的性能比率为172。在本地冗余节点上应用某些修剪规则，可以进一步减小CDS的大小。其次，在特殊情况下的异构无线自组织网络中，网络拓扑可以用具有双向链接（DGB）的磁盘图，提出了两种有效的近似算法来获得MCDS。如果网络中最大传输范围与最小传输范围的比率是有界的，则这些算法的性能比率将是恒定的。还实现了这些算法的分布式版本。显示了最大独立集和CDS之间的大小关系，以及磁盘图中节点的最大独立邻居数的界限。最后，提出了多项式时间近似方案（PTAS）以找到最小值一类增长有界图（包括单位磁盘图，单位球等）中的d跳连接控制集（d-CDS），可以代表大多数现有的无线网络。基于预定义的网络参数，可以将增长边界图划分为群集。为每个群集构建d-CDS，每个d-CDS的并集形成图的d-CDS，并带有一些其他节点将它们连接。提供了PTAS的性能和复杂性分析。

著录项

  • 作者

    Zhu, Shiwei.;

  • 作者单位

    University of Minnesota.;

  • 授予单位 University of Minnesota.;
  • 学科 Computer Science.
  • 学位 Ph.D.
  • 年度 2009
  • 页码 97 p.
  • 总页数 97
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 自动化技术、计算机技术;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号