Skip to Main content Skip to Navigation
Journal articles

Centroid virtual coordinates - A novel near-shortest path routing paradigm

Thomas Watteyne 1, 2 Isabelle Augé-Blum 2 Mischa Dohler 1, 3 Stéphane Ubéda 4 Dominique Barthel 1
2 SWING - Smart Wireless Networking
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
4 AMAZONES - Ambient Middleware Architectures: Service-Oriented, Networked, Efficient and Secured
CITI - CITI Centre of Innovation in Telecommunications and Integration of services, Inria Grenoble - Rhône-Alpes
Abstract : Geographic routing has received increasing attention in the context of Wireless Sensor Networks since it frees the network from the energy-demanding task of building and maintaining a structure. It requires however each node to know its position, which may be a prohibitive assumption for many applications. To this end, some prior work has focused on inferring a node's location from a set of location-aware anchor nodes. In this work, we free ourselves from positioning techniques and anchor nodes altogether, and introduce and analyze the concept of virtual coordinates. These coordinates are chosen randomly when a node is switched on, and are updated each time the node relays a packet. As this process goes on, the virtual coordinates of the nodes converge to a near-optimal state. When using a greedy geographic approach on top of these coordinates, we show that the number of hops to reach the destination exceeds the shortest path by a few percent only. Moreover, our approach guarantees delivery even when nodes appear/disappear in the network, and under realistic transmission models. We analytically prove the correctness of our protocol. Moreover, extensive simulations are used to show that our position-free solution outperforms existing geographic protocols - such as Greedy-Face-Greedy (GFG) or Greedy Perimeter Stateless Routing (GPSR) - in terms of energy-efficiency, path length and robustness.
Document type :
Journal articles
Complete list of metadata
Contributor : Stephane Ubeda <>
Submitted on : Thursday, July 16, 2009 - 9:34:38 AM
Last modification on : Thursday, April 15, 2021 - 5:16:02 PM




Thomas Watteyne, Isabelle Augé-Blum, Mischa Dohler, Stéphane Ubéda, Dominique Barthel. Centroid virtual coordinates - A novel near-shortest path routing paradigm. Computer Networks, Elsevier, 2009, 53 (10), pp.1697-1711. ⟨10.1016/j.comnet.2008.12.017⟩. ⟨inria-00404280⟩



Record views