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

Date Added: Feb 2011
Format: PDF

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. The authors 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. They derive sufficient conditions that ensure the asymptotic 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, they derive bounds on the expected number of hops that each packet traverses to reach its destination.