• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Localized Delaunay triangulation with application in ad hoc wireless networks
【24h】

Localized Delaunay triangulation with application in ad hoc wireless networks

机译：局部Delaunay三角剖分及其在ad hoc无线网络中的应用

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

摘要

Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RING) or Gabriel graph (GG) is used as such planar structure. However, it is well-known that the spanning ratios of these two graphs are not bounded by any constant (even for uniform randomly distributed points). Bose et al. (1999) recently developed a localized routing protocol that guarantees that the distance traveled by the packets is within a constant factor of the minimum if Delaunay triangulation of all wireless nodes is used, in addition, to guarantee the delivery of the packets. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we model the network as a unit-disk graph (UDG), in which a link uv exists only if the distance /spl par/uv/spl par/ is at most the maximum transmission range. In this paper, we present a novel localized networking protocol that constructs a planar 2 5-spanner of UDG, called the localized Delaunay triangulation (LDEL), as network topology. It contains all edges that are both in the unit-disk graph and the Delaunay triangulation of all nodes. The total communication cost of our networking protocol is O(n log n) bits, which is within a constant factor of the optimum to construct any structure in a distributed manner. Our experiments show that the delivery rates of some of the existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. Our simulations also show that the traveled distance of the packets is significantly less when the FACE routing algorithm is applied on LDEL, rather than applied on GG.
机译：当基础网络拓扑是平面图时，几种本地化的路由协议可保证数据包的传递。通常，相对邻域图（RING）或加百利图（GG）被用作这种平面结构。但是，众所周知，这两个图的跨度比不受任何常数的限制（即使对于均匀的随机分布点）。 Bose等。 （1999年）最近开发了一种本地化路由协议，该协议可确保如果使用所有无线节点的Delaunay三角剖分，并且保证包的传递，则包的行进距离在最小的恒定因子之内。但是，以分布式方式构造Delaunay三角剖分是昂贵的。给定一组无线节点，我们将网络建模为单位磁盘图（UDG），仅当距离/ spl par / uv / spl par /最多为最大传输范围时，链路uv存在。在本文中，我们提出了一种新颖的本地化网络协议，该协议构造了UDG的平面2 5跨度的UDG，称为本地化Delaunay三角剖分（LDEL），作为网络拓扑。它包含单元盘图中和所有节点的Delaunay三角剖分中的所有边。我们的网络协议的总通信成本为O（n log n）位，这在以分布式方式构造任何结构的最佳常数内。我们的实验表明，当使用局部Delaunay三角剖分代替某些先前提出的拓扑时，某些现有的局部路由协议的传递速率会提高。我们的仿真还表明，当FACE路由算法应用于LDEL而不是GG时，数据包的行进距离显着减少。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号