On the Random 1/2-Disk Routing Scheme in Wireless Ad Hoc Networks

Abstract

Random 1/2-disk routing in wireless ad-hoc networks is a localized geometric routing scheme in which each node chooses the next relay randomly among the nodes within its transmission range and in the general direction of the destination. We introduce a notion of convergence for geometric routing schemes that not only considers the feasibility of packet delivery through possibly multi-hop relaying, but also requires the packet delivery to occur in a finite number of hops. We derive sufficient conditions that ensure the asymptotic \emph{convergence} of the random 1/2-disk routing scheme based on this convergence notion, and by modeling the packet distance evolution to the destination as a Markov process, we derive bounds on the expected number of hops that each packet traverses to reach its destination.

This paper has been withdrawn by the author and is replaced by an updated version under a new title: "On Asymptotic Statistics for Geometric Routing Schemes in Wireless Ad-Hoc Networks" [arXiv:1211.2496]