Internal node and shortcut based routing with guaranteed delivery in wireless networks

Several distributed routing algorithms for wireless networks were described recently, based on location information of nodes available via Global Positioning System (GPS). In a greedy routing algorithm, the sender or node S currently holding the message m forwards m to one of its neighbors that is the closest to the destination. The algorithm fails if S does not have any neighbor that is closer to destination than S. The FACE algorithm guarantees the delivery of m if the network, modeled by unit graph, is connected. The GFG algorithm combines greedy and FACE algorithms. We further improve the performance of the GFG algorithm, by reducing its average hop count. First we improve the FACE algorithm by adding a sooner-back procedure for earlier escape from FACE mode. Then we perform a shortcut procedure at each forwarding node S. Node S uses the local information available to calculate as many hops as possible and forwards the packet to the last known hop directly instead of forwarding it to the next hop. The second improvement is based on the concept of dominating sets. The network of internal nodes defines a connected dominating set, and each node must be either internal or directly connected to an internal node. We apply several existing definitions of internal nodes, namely the concepts of intermediate, inter-gateway and gateway nodes. We propose to run GFG routing, enhanced by shortcut procedure, on the dominating set, except possibly the first and last hops. We obtained localized routing algorithm that guarantees delivery and has very low excess in terms of hop count compared to the shortest path algorithm. Experimental data show that the length of additional path can be reduced to about half that of existing GFG algorithm.