OnionMap: A Scalable Geometric Addressing and Routing Scheme for 3D Sensor Networks

Geometric routing or geo-routing has been shown as a promising approach to scalable routing in sensor networks. Despite its success in 2-D networks, very few designs are available for 3-D networks that can ensure short routes using only small per-node state, without incurring high load imbalance on the nodes. In this paper, we propose a novel addressing and routing scheme, i.e., OnionMap, for 3-D sensor networks that achieve the above goals, using solely connectivity information and at a linear message cost. The key idea is to decompose a 3-D network into a set of connected layers, which are then mapped to a set of concentric sphere structures (similar to an onion). On each sphere, a discrete Ricci flow method is used to assign each node a set of coordinates that permits purely greedy routing within that sphere; across the different spheres, a layer alignment algorithm helps rotate and scale the spheres, to form a coherent global coordinate system that guides global routing. Theoretical analysis and simulation show OnionMap's advantages over state-of-the-art solutions in path stretch, per-node storage, and load balance.