Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2006-11-22
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
We propose bi-directional face traversal algorithm $2FACE$ to shorten the path the message takes to reach the destination in geometric routing. Our algorithm combines the practicality of the best single-direction traversal algorithms with the worst case message complexity of $O(|E|)$, where $E$ is the number of network edges. We apply $2FACE$ to a variety of geometric routing algorithms. Our simulation results indicate that bi-directional face traversal decreases the latency of message delivery two to three times compared to single direction face traversal. The thus selected path approaches the shortest possible route. This gain in speed comes with a similar message overhead increase. We describe an algorithm which compensates for this message overhead by recording the preferable face traversal direction. Thus, if a source has several messages to send to the destination, the subsequent messages follow the shortest route. Our simulation results show that with most geometric routing algorithms the message overhead of finding the short route by bi-directional face traversal is compensated within two to four repeat messages.
Miyashita Mark
Nesterenko Mikhail
No associations
LandOfFree
2FACE: Bi-Directional Face Traversal for Efficient Geometric Routing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with 2FACE: Bi-Directional Face Traversal for Efficient Geometric Routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 2FACE: Bi-Directional Face Traversal for Efficient Geometric Routing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-368341