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

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.