Properties of Greedy Geographical Routing in Spontaneous Wireless Mesh Networks

The goal of this paper is to analyze greedy geographical routing in spontaneous wireless mesh networks. Although we use a simplistic model based on the unit disk graph, our analysis yields several interesting properties. First, we can approximate the dependence of the packet loss probability on the mean node rank with a Fermi-Dirac-like function. When the mesh network grows, it becomes opaque to packets, the effect which is independent of the average node rank. We also show that greedy geographical routing in mesh networks does not exhibit the behavior of percolating systems. Finally, we propose an analytical model of greedy geographical routing and use it to derive the probability of packet loss. Our analysis provides a basis for further improvements of simple greedy forwarding.