Skip to Main content Skip to Navigation
Conference papers

Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic Routing

Guang Tan 1 Marin Bertier 1 Anne-Marie Kermarrec 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : Virtual coordinate geographic routing is an appealing geographic routing approach for its ability to work without physical location information. We examine two representative such routing protocols, namely NoGeo and BVR, and show through experiments and theoretical analysis their limitation in adapting to complex field topologies, in particular fields with concave holes. Based on the new insights, we propose a distributed convex partition protocol that divides the field to subareas with convex shapes, using only connectivity information. A new geographic routing protocol, called CONVEX , that builds upon the partitioning protocol is then described. Simulations demonstrate significant performance improvement of the new routing protocol over NoGeo and BVR, in terms of transmission stretch and maintenance overheads.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Guang Tan <>
Submitted on : Thursday, November 5, 2009 - 5:59:30 PM
Last modification on : Tuesday, June 15, 2021 - 4:27:28 PM
Long-term archiving on: : Thursday, June 17, 2010 - 7:32:19 PM


Files produced by the author(s)


  • HAL Id : inria-00430145, version 1


Guang Tan, Marin Bertier, Anne-Marie Kermarrec. Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic Routing. INFOCOM 2009, Apr 2009, Rio de Janeiro, Brazil. ⟨inria-00430145⟩



Record views


Files downloads