Title | ||
---|---|---|
GPS-Free Greedy Routing With Delivery Guarantee and Low Stretch Factor on 2-D and 3-D Surfaces |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/JIOT.2014.2320260 | IEEE Internet of Things Journal |
Keywords | Field | DocType |
greedy routing,low stretch factor,gps-free greedy routing,conformal map theory,flat metric,delivery guarantee,2d surfaces,wireless networks,radio networks,interior concave,3d surfaces,convex hull boundary condition,distributed embedding scheme,virtual coordinates,wireless sensor networks,telecommunication network routing,yamabe flow,local connectivity,convex shape,internet,routing protocols,global positioning system,boundary conditions,measurement,greedy algorithms | Stretch factor,Topology,Mathematical optimization,Embedding,Computer science,Convex polygon,Convex hull,Greedy algorithm,Yamabe flow,Greedy embedding,Distributed computing,Routing protocol | Journal |
Volume | Issue | ISSN |
1 | 3 | 2327-4662 |
Citations | PageRank | References |
2 | 0.40 | 25 |
Authors | ||
3 |