Depth First Search-based and power-aware geo-routing in ad hoc and sensor wireless networks
Bosko Vukojevic, Nishith Goel, Kalai Kalaichevlan, Amiya R. Nayak, Ivan Stojmenović · International Journal of Autonomous and Adaptive Communications Systems · 2008
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.