基于最优Path的Ad Hoc网络地理路由算法

对基于地理信息的自组网路由中的凹节点问题做了分析,并提出了一种新的解决方案——PGA算法及其改进算法.算法采用了最优Path的思想,在Path构造、基于Path的最优寻路、路由恢复等多个方面都应用了最优Path的概念,较好地解决了凹节点的问题.通过证明,该算法具有无环性,从而实现了基于局部路由信息的无状态路由,展示了算法的可扩展性和易维护性.实验表明,即使在大型网络中,算法依然可以保持很高的报文投递率、较短的路径长度、可接受的路由表大小及可控的协议带宽开销,同时该路由算法在动态环境中具有较强的鲁棒性.

Optimal Path Based Geographic Routing in Ad Hoc Networks

Routing in ad hoc networks is still a difficult problem by now because of the energy and bandwidth restriction. Using location information, routing can only be based on local information. But concave problem often emerges in the geographical routing algorithms. By analysis of concave-node problem in geographic routing in ad hoc networks, a new algorithm called PGA as well as its improveed versions. In this method, the concept of optimal path is used in all phase of routing, including path construction, routing based on optimal path and routing recovery. The mechanism is very effective to handle the concave node problem. The routing needs only some local path information. The path construction and routing algorithm can be proved to no loop, i.e. the algorithm guarantees the routing can't cause loop path, so the routing is stateless. All of them lead to the algorithm scalability and maintainability. Experiments demonstrate that even in large network, the algorithm is able to achieve high packet delivery success rate, short path length, acceptable routing size and controllable protocol communication cost. In the meanwhile, the routing algorithm is robust enough in dynamic environments. So it can be widely applied in ad hoc or sensor networks.