TY - GEN
T1 - Ad-hoc routing using virtual coordinates based on rooted trees
AU - Ben-Asher, Yosi
AU - Feldman, Moran
AU - Feldman, Sharoni
PY - 2006
Y1 - 2006
N2 - An ad hoc routing algorithm must be able to locate and maintain a path from a source to a destination node while overcoming sudden changes in the network topology and explore alternative paths in case of path breaks. One "classic" type of solution is to constantly maintain an approximate routing table at each node and use it to dynamically search for a routing path to the destination. Another, more efficient type of algorithms uses geographical/geometrical coordinates at each node (obtained by GPS devices) to forward packets and explore alternative paths to the destinations. Recently it was shown that the exact GPS coordinates can be replaced by "virtual" grid like coordinates computed based on the number of links/hops between the nodes. Computing these grid-like coordinates is a costly process eliminating the advantages of the geographical routing over the more classic types of algorithms. We propose a different type of virtual coordinates based on dynamic embedding of the ad-hoc connectivity graph by a minimal set of rooted trees. We give a novel ad hoc routing algorithm called MRA (Metrical Routing Algorithm) that uses the tree like coordinates to efficiently find minimal cover of the nodes by rooted trees and based on the tree coordinates forward packets to their destinations. Similar to geographical routing our algorithm allows oblivious transfer of packets to any destination avoiding the use of routing tables. The proposed method is compared to the well known AODV (Ad Hoc on Demand Distance Vector Routing) obtaining significant improvements in terms of number of messages, number of concurrent sessions, duration of the sessions, nodes' densities, queue sizes and resilience to sudden movements of the nodes. We have built a sophisticated simulator that has been carefully designed for a fair comparison between the two algorithms
AB - An ad hoc routing algorithm must be able to locate and maintain a path from a source to a destination node while overcoming sudden changes in the network topology and explore alternative paths in case of path breaks. One "classic" type of solution is to constantly maintain an approximate routing table at each node and use it to dynamically search for a routing path to the destination. Another, more efficient type of algorithms uses geographical/geometrical coordinates at each node (obtained by GPS devices) to forward packets and explore alternative paths to the destinations. Recently it was shown that the exact GPS coordinates can be replaced by "virtual" grid like coordinates computed based on the number of links/hops between the nodes. Computing these grid-like coordinates is a costly process eliminating the advantages of the geographical routing over the more classic types of algorithms. We propose a different type of virtual coordinates based on dynamic embedding of the ad-hoc connectivity graph by a minimal set of rooted trees. We give a novel ad hoc routing algorithm called MRA (Metrical Routing Algorithm) that uses the tree like coordinates to efficiently find minimal cover of the nodes by rooted trees and based on the tree coordinates forward packets to their destinations. Similar to geographical routing our algorithm allows oblivious transfer of packets to any destination avoiding the use of routing tables. The proposed method is compared to the well known AODV (Ad Hoc on Demand Distance Vector Routing) obtaining significant improvements in terms of number of messages, number of concurrent sessions, duration of the sessions, nodes' densities, queue sizes and resilience to sudden movements of the nodes. We have built a sophisticated simulator that has been carefully designed for a fair comparison between the two algorithms
UR - https://www.scopus.com/pages/publications/33845449934
U2 - 10.1109/SUTC.2006.1636153
DO - 10.1109/SUTC.2006.1636153
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:33845449934
SN - 0769525539
SN - 9780769525532
T3 - Proceedings - IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing
SP - 6
EP - 13
BT - Proceedings - Thirteenth International Symposium on Temporal Representation and Reasoning, TIME 2006
T2 - IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing
Y2 - 5 June 2006 through 7 June 2006
ER -