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 greedy routing algorithm sender or node S currently holding the message m forwards m to one of its neighbors that is the closest to destination. The algorithm fails if S does nor have any neighbor that is closer to destination than S. FACE algorithm guarantees the delivery of m if the network, modeled by unit graph, is connected. GFG algorithm combines greedy and FACE algorithms. Greedy algorithm is applied as long as possible, until delivery or a failure. In case of failure, the algorithm switches to FACE algorithm until a node closer to destination than last failure node is found, at which point greedy algorithm is applied again. In this paper we further improve the performance of 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 packer 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, an 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. The experimental data show that the length of additional path tin excess of shortest path length) can be reduced to about half of that of existing GFG algorithm.