Wireless Routing in Ad-Hoc Networks

Wireless networks present many challenges to standard routing algorithms. Ultimately, what we want from a routing algorithm is for it to be optimal in terms of robustness, scalability, power, and time; however, it will be shown that guaranteed delivery generally comes at the expense of any one of these desirables. This paper will exhibit a progression from routing in static networks to routing in unit distance wireless networks in order to illuminate the reality of the balance between what we want from wireless ad hoc routing algorithms and what we can expect from them. Much of the analysis presented will be on Dijkstra’s algorithm, the Bellman-Ford algorithm, Compass Routing, Face Routing, as well as localized methods to extract planar subgraphs.