Loop-free greedy routing in ad hoc or sensor networks using muti-hop geographic information
Kun Yu, Shanyue Bu · 2009
Geographic routing has remarkable advantage in ad hoc networks, special in sensor networks, in which planar graph algorithms are usually employed to get rid of the concave node problem. In this paper a new direct greedy routing protocol is proposed which needs not any planar graph. Nodes route towards the destination according to muti-hop neighbors' location information. With loop free node information propagation, the protocol achieves great success ratio of packet delivering which is comparable to that of guaranteed face routing. Moreover, the routing algorithm is loop free, so stateless routing can be attained straightforwardly. Experiments demonstrate that though the initial protocol is low efficient, the amended one improves the routing astonishingly which delivering path length can be close to the shortest possible path when the network has 1000 nodes or lesser. Average path length of our routing is shorter than that of face routing GFG and its routing table cost is O(l), l is maximal distance of location information propagation, so the protocol has excellent scalability and can be applied in large networks. The protocol can not only be applied in planar networks, but is available for networks in 3D space too.