Morelia test: Improving the efficiency of the Gabriel test and face routing in ad-hoc networks
Article
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
An important technique for discovering routes between two nodes in an ad-hoc network involves applying the face routing algorithm on a planar spanner of the network. Face routing guarantees message delivery in networks that contains large holes, where greedy algorithms fail. Existing techniques for constructing a suitable planar subgraph involve local tests that eliminate crossings between existing links by deleting some links. They do not test whether the deleted links actually create some crossings and some of the links are deleted needlessly. As a result, some of the routes found in face routing will have an unnecessarily large number of hops from source to destination. We consider a new local test for preprocessing a wireless network that produces a planar subgraph. The test is relatively simple, requires low overhead and does not eliminate existing links unless it is needed to eliminate a crossing, thus reducing overhead associated with multiple hops. © Springer-Verlag Berlin Heidelberg 2004.
publication date
published in
Research
keywords
Ad hoc networks; Complex networks; Telecommunication networks; Testing; Face routing; Greedy algorithms; In networks; Local tests; Low overhead; Message delivery; Multiple hops; Number of hops; Network routing
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume