Depth first search and position based routing in ad hoc and sensor wireless networks

Abstract

Finding a solution to the routing problem in wireless ad hoc and sensor networks has proven to be a quite difficult. A number of position-based localized algorithms have demonstrated important features like guaranteed delivery, scalability, robustness, and energy conservation, just to name a few. This thesis proposes DFS, Depth First Search, routing algorithm. It is the first position-based localized algorithm that guarantees the delivery for (connected) ad hoc wireless networks modeled by arbitrary graphs, including inaccurate location information for a destination node. The DFS routing scheme is extended in order to provide QoS (quality of service) routing for wireless ad hoc networks. The goal of the DFS QoS is to minimize hop count, which resemble propagation delay requirement. Another contribution of the thesis is the introduction of a new set of localized routing algorithms. The best DFS routing candidate is integrated with recently proposed modification of power and cost-aware solutions, so called progress-based power algorithms. (Abstract shortened by UMI.)