GRIP: Greedy Routing through dIstributed Parametrization for guaranteed delivery in WSNs

Although stateless greedy routing is well investigated in 2D wireless sensor networks (WSNs), it is widely believed to be impossible in 3D. In this paper, we aim at overcoming the impossibility through a distributed parametrization that equips a WSN with virtual coordinates favoring greedy routing. We propose a fundamentally new parametrization to embed the network domain, the resulting embedding domain allows greedy routing to have guaranteed delivery. We also present localized algorithms to realize this map in WSNs. To combat the load concentration caused by greedy routing that applies the distance greedy principle, we further propose tunable greedy routing, which relies on tuning a parameter in the greedy objective to naturally balance routing load. These two proposals form our Greedy Routing through dIstributed Parametrization (GRIP). We prove the correctness and efficiency of GRIP and use simulations to evaluate its performance in terms of complexity, load balancing, and energy efficiency.