Title: Depth First Search-based and power-aware geo-routing in ad hoc and sensor wireless networks

Authors: Bosko Vukojevic, Nishith Goel, Kalai Kalaichevlan, Amiya Nayak, Ivan Stojmenovic

Addresses: School of Information Technology and Engineering, University of Ottawa, 800 King Edward Avenue, Ottawa, Ontario K1N 6N5, Canada. ' Cistel Technology Inc., 30 Concourse Gate, Unit 40, Ottawa, ON K2E 7V7, Canada. ' Eion Inc., 320 March Road, Suite 500, Ottawa, Ontario K2K 2E3, Canada. ' School of Information Technology and Engineering, University of Ottawa, 800 King Edward Avenue, Ottawa, Ontario K1N 6N5, Canada. ' EECE, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK

Abstract: Depth First Search (DFS) and position-based routing algorithms were proposed in literature. These are localised algorithms that guarantee the delivery for connected ad hoc and sensor wireless networks modelled by arbitrary graphs, including inaccurate location information for a destination node. This article first optimises an existing DFS-based routing scheme by eliminating from the candidate list neighbours whose messages to other nodes were overheard. We then introduce a new set of localised routing algorithms. The new DFS routing protocol is integrated with power metrics minimise total power for routing of a message. These DFS Power Progress-based algorithms are combinations of known greedy power and DFS routing algorithms. All algorithms are further enhanced by applying the concept of connected dominating sets, which greatly reduced the search path without impacting significantly the length of effectively constructed path for real traffic. Experiments confirm the efficiency of the new enhanced DFS, power-aware and connected dominating set-based routing algorithms and ability to guarantee the delivery in arbitrary model due to the DFS routing framework.

Keywords: ad hoc networks; sensor networks; depth first search routing; power aware geo-routing; wireless networks; DFS routing; dominating sets.

DOI: 10.1504/IJAACS.2008.019199

International Journal of Autonomous and Adaptive Communications Systems, 2008 Vol.1 No.1, pp.41 - 54

Published online: 02 Jul 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article