| 本文已被：浏览 5722次 下载 8647次 |
码上扫一扫！ |
|
|
| 基于Delaunay三角剖分的Ad Hoc网络路由算法 |
|
贺鹏1,2, 李建东1,2, 陈彦辉1,2, 周雷1,2
|
|
1.综合业务网国家重点实验室(西安电子科技大学),陕西,西安,710071;2.西安电子科技大学,信息科学研究所,宽带无线通信实验室,陕西,西安,710071
|
|
| 摘要: |
| Delaunay三角剖分已广泛地应用于计算流体力学、统计学、气象学、固体物理学、计算几何学等多个领域.随着无线Ad Hoc网络的发展,一些研究者提出了可以保证网络任意节点对之间分组顺利传输的几何路由协议,而这些协议的网络基础拓扑同样可以用Delaunay三角剖分的思想来实现.提出了一种新型的用于发现移动节点间通信路径的在线路由算法GLNFR(greedy and local neighbor face routing).利用局部构造法,构造出局部化的Delaunay三角剖分作为网络的基础拓扑.在该网络拓扑中进行的GLNFR路由算法可以保证节点间分组的顺利传输,对网络变化具有更好的可扩展性和适应性.在NS(network simulator)模拟器上仿真了该路由算法.结果表明,在分组成功传输率和路由分组开销性能方面,这一在线路由协议要优于先前提出的一些几何路由协议. |
| 关键词: 局部化Delaunay三角剖分 路由 单位圆图 平面图 无线Ad Hoc网络 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60372048, 60496316 (国家自然科学金基金); the National High-Tech Research and Development Plan of China under Grant No.2005AA123910 (国家高技术研究发展计划(863)); the National Grand Fundamental Research Program of Education of China under Grant No.104171 (国家教育部科学技术研究重点项目);the Foundation of Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institute of China (高等学校优秀青年教师教学科研奖励计划) |
|
| A Routing Algorithm for Ad Hoc Networks Based on Delaunay Triangulation |
|
HE Peng,LI Jian-Dong,CHEN Yan-Hui,ZHOU Lei
|
| Abstract: |
| Delaunay triangulation has been widely used in many fields such as computational fluid dynamics, statistics, meteorology, solid state physics, computational geometry and so on. With the development of Ad Hoc networks, some researchers proposed geometric routing protocols to guarantee the delivery of the packet between any pair of nodes in the network, and the underlying network topology is also constructed by the ways of Delaunay triangulation. In this paper, a novel online routing algorithm GLNFR (greedy and local neighbor face routing) for finding communication paths between the mobile nodes is proposed. The localized manner is used to form the local Delaunay triangulation as the underlying topology of a wireless network on which the GLNFR routing algorithm could guarantee the delivery of the packets. It has better scalability and adaptability for the change of networks. Experiment on NS (network simulator) has been conducted. The results show that the delivery success rate of packets and routing protocol overhead under such novel routing protocols performs better than others proposed previously. |
| Key words: local Delaunay triangulation routing unit disk graph planar graph wireless ad hoc network |
