Geometric routing (geo-routing) is a promising approach to scalable routing in sensornetworks. Despite its success in2D networks, very few designs are available for3D casesthat ensure producing short routes using only small per-node state, without introducinghigh load imbalance on the nodes. In this paper, we propose a novel addressing androuting scheme, OnionMap, for3D sensor networks that achieves the above goals, usingconnectivity information only. The key idea is to decompose the network into a set ofconnected layers, which are then mapped to a set of concentric sphere structures (like anonion). On each sphere, a discrete Ricci flow method is used to assign each node a setof coordinates that permit purely greedy routing within that sphere; across the differentspheres, a coordinate alignment algorithm helps rotate and scale the spheres, so as toform a coherent global coordinate system which guides global routing. Unlike someprevious schemes, OnionMap does not require the knowledge of network boundaries; onthe contrary, it produces them as a byproduct. Simulations have been conducted to confirmits efficiency in terms of stretch, per-node state, and load balancing. |