Greedy routing with guaranteed delivery using Ricci flows

Rik Sarkar, Xiaotian Yin, Jie Gao, Feng Luo, Xianfeng David Gu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

93 Scopus citations

Abstract

Greedy forwarding with geographical locations in a wireless sensor network may fail at a local minimum. In this paper we propose to use conformal mapping to compute a new embedding of the sensor nodes in the plane such that greedy forwarding with the virtual coordinates guarantees delivery. In particular, we extract a planar triangulation of the sensor network with non-triangular faces as holes, by either using the nodes' location or using a landmark-based scheme without node location. The conformal map is computed with Ricci flow such that all the non-triangular faces are mapped to perfect circles. Thus greedy forwarding will never get stuck at an intermediate node. The computation of the conformal map and the virtual coordinates is performed at a preprocessing phase and can be implemented by local gossip-style computation. The method applies to both unit disk graph models and quasi-unit disk graph models. Simulation results are presented for these scenarios.

Original languageEnglish (US)
Title of host publication2009 International Conference on Information Processing in Sensor Networks, IPSN 2009
Pages121-132
Number of pages12
StatePublished - Nov 16 2009
Event2009 International Conference on Information Processing in Sensor Networks, IPSN 2009 - San Francisco, CA, United States
Duration: Apr 13 2009Apr 16 2009

Other

Other2009 International Conference on Information Processing in Sensor Networks, IPSN 2009
CountryUnited States
CitySan Francisco, CA
Period4/13/094/16/09

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Greedy routing with guaranteed delivery using Ricci flows'. Together they form a unique fingerprint.

Cite this