PGA:一种基于最优路径的Ad Hoc网络地理路由算法

PGA:Optimal-path-based Geographic Routing Arithmetic in Ad Hoc Networks

本文提出了一种基于最优路径的Ad Hoc网络的地理路由算法PGA及其改进算法H-PGA,该算法在路径的构造、路由、路由恢复各个方面都应用了最优路径路由的概念,较好地解决了地理路由算法中的凹节点问题。在网络节点数n较大的情况下,依然保持很高的报文投递率(n=400、网络度为4时,报文投递率为96%),且实际路径很接近最短路径路径。同时H-PGA路由表的大小与n～1/2成线性关系,单个节点的协议带宽消耗也为O(n～1/2),这使得H-PGA可以适用于较大的应用范围。

A new optimal-path based geographic routing arithmetic in Ad hoc networks （PGA） and its modified version H-PGA are purposed in the article. The concept of optimal path is applied in all parts of my arithmetic, including route path construction, routing, route recovering, gets the concave node problem in geographic routing well resolved. Even in large network, my arithmetic obtains high delivery ratio yet （ 96% when n=400, network degree= 4）, and real path length is comparable with shortest path. On another hand, table size of H-PGA is linear with √n, the protocol loads of single node is about O（√n） too. It give the arithmetic more application value.