[inria-00430145, v1] Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic

Author manuscript, published in "INFOCOM 2009 (2009)"Convex Partition of Sensor Networks and Its Use inVirtual Coordinate Geographic RoutingGuang Tan Marin Bertier Anne-Marie KermarrecINRIA/IRISA, Rennes, France. Email: {guang.tan, marin.bertier, anne-marie.kermarrec}@irisa.frAbstract— Virtual coordinate geographic routing is an appeal- with assistance of some global data structure [6], [8], [19];ing geographic routing approach for its ability to work without when encountering a dead-end, the protocol uses a scopedphysical location information. We examine two representative flooding to guarantee delivery. This approach obviates the needsuch routing protocols, namely NoGeo and BVR, and showfor GPS devices (or localization services) and planarizationthrough experiments and theoretical analysis their limitationalgorithms, thus greatly improving its applicability. Moreover,in adapting to complex field topologies, in particular fieldswith concave holes. Based on the new insights, we propose a those protocols have been shown to offer a high greedydistributed convex partition protocol that divides the field to forwarding success rate (GFSR), which is an important factorsubareas with convex shapes, using only connectivity information. in routing performance.A new geographic routing protocol, called CONVEX, that buildsNevertheless, a question that remains unanswered is howupon the partitioning protocol is then described. Simulationswell those protocols adapt to ...