|
Published Articles >> Table of Contents >> Abstract
Eighth IEEE Symposium on Computers and Communications
p. 51
Voronoi diagram and convex hull based geocasting and routing in wireless networks
Ivan Stojmenovic, University of Ottawa
Anand Prakash Ruhil, Jawaharlal Nehru University
D.K. Lobiyal, Jawaharlal Nehru University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISCC.2003.1214100
Send link to a friend
| Abstract |
|
A broad variety of location dependent services will
become feasible in the near future due to the use of the
Global Position System (GPS), which provides location
information (latitude, longitude and possibly height) and
global timing to mobile users. Routing is a problem of
sending a message from a source to a destination.
Geocasting is the problem of sending a message to all
nodes located within a region (e.g. circle or square).
Recently, several localized GPS based routing and
geocasting protocols for a mobile ad hoc network were
reported in literature. In directional (DIR) routing and
geocasting methods, node A (the source or intermediate
node) transmits a message m to all neighbors located
between the two tangents from A to the region that could
contain the destination. It was shown that memoryless
directional methods may create loops in routing process.
In two other proposed methods (proven to be loop-free),
geographic distance (GEDIR) or most forward progress
within radius (MFR) routing, node A forwards the
message to its neighbor who is closest to destination, or
has greatest progress toward destination (respectively).
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 V-GEDIR and CH-MFR
methods and define R-DIR, modified version of
existing directional methods. In V-GEDIR 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. We propose
memoryless and past traffic memorization variants of
each scheme. 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. Memoryless V-GEDIR and CH-MFR
algorithms are loop free, and have smaller flooding
rate (with similar success rate) compared to directional
method. Simulations, involving the proposed and some
known algorithms, are in progress and confirm our
expectations.
|
 Additional Information
|
Citation:
Ivan Stojmenovic, Anand Prakash Ruhil, D.K. Lobiyal,
"Voronoi diagram and convex hull based geocasting and routing in wireless networks,"
iscc,
p. 51,
Eighth IEEE Symposium on Computers and Communications,
2003
|
|
