基于Delaunay三角剖分的Ad Hoc网络路由算法

A Routing Algorithm for Ad Hoc Networks Based on Delaunay Triangulation

Delaunay三角剖分已广泛地应用于计算流体力学、统计学、气象学、固体物理学、计算几何学等多个领域.随着无线AdHoc网络的发展,一些研究者提出了可以保证网络任意节点对之间分组顺利传输的几何路由协议,而这些协议的网络基础拓扑同样可以用Delaunay三角剖分的思想来实现.提出了一种新型的用于发现移动节点间通信路径的在线路由算法GLNFR(greedyandlocalneighborfacerouting).利用局部构造法,构造出局部化的Delaunay三角剖分作为网络的基础拓扑.在该网络拓扑中进行的GLNFR路由算法可以保证节点间分组的顺利传输,对网络变化具有更好的可扩展性和适应性.在NS(networksimulator)模拟器上仿真了该路由算法.结果表明,在分组成功传输率和路由分组开销性能方面,这一在线路由协议要优于先前提出的一些几何路由协议.

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.