Voronoi diagram and convex hull based geocasting and routing in wireless networks

Publisher Website
Google Scholar
Abstract
In this paper, we propose a general algorithm (based on an unified framework for both routing and geocasting problems), in which message is forwarded to exactly those neighbors which may be best choices for a possible position of destination (using the appropriate criterion). We then propose and discuss new VD‐GREEDY and CH‐MFR methods and define R‐DIR, modified version of existing directional methods. In VD‐GREEDY method, these neighbors are determined by intersecting the Voronoi diagram of neighbors with the circle (or rectangle) of possible positions of destination, while the portion of the convex hull of neighboring nodes is analogously used in the CH‐MFR method. Routing and geocasting algorithms differ only inside the circle/rectangle. The proposed methods may be also used for the destination search phase allowing the application of different routing schemes after the exact position of destination is discovered. VD‐GREEDY and CH‐MFR algorithms are loop free, and have smaller flooding rate (with similar success rate) compared to directional method. We proposed to use dominating set concept to reduce flooding ratio significantly, with a marginal impact on success rate and hop count. Simulations, involving the proposed and some known algorithms, are performed for two basic scenarios, one for geocasting and reactive routing, and the other for proactive routing, and both showed that our methods have higher success rate and lower flooding rate compared to existing methods. Copyright © 2006 John Wiley & Sons, Ltd.

This publication has 20 references indexed in Scilit: