GPS-Free Greedy Routing With Delivery Guarantee and Low Stretch Factor on 2-D and 3-D Surfaces

This paper focuses on greedy routing in wireless networks deployed on 2-D and 3-D surfaces. It introduces a distributed embedding scheme based on the conformal map theory. The proposed scheme identifies the convex hull of each boundary and employs Yamabe flow to compute flat metric under convex hull boundary condition to establish virtual coordinates. Such virtual coordinates are then used for greedy routing. Since the proposed embedding algorithm maps the outer boundary to a convex shape and an interior concave void to a circle-like convex polygon, it effectively eliminates local minimum and attains guaranteed delivery. At the same time, it introduces a small distortion only and consequently achieves a low stretch factor. Our simulations show that its stretch factor is lower than any existing greedy embedding algorithms. Moreover, the proposed scheme is merely based on local connectivity and consumes a small constant storage, thus scaling to arbitrarily large networks.