Multi-path GEM for routing in wireless sensor networks

Qiang Ye, Yuxing Huang, Andrew Reddin, Lei Wang, Wuman Luo

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)


Wireless sensor networks are expected to be used in many different applications such as disaster relief and environmental control. Efficient routing protocols need to be thoroughly studied before wireless sensor networks are widely deployed. GEM is an ingenious routing algorithm that is based on the idea of graph embedding. Using a well designed virtual coordinate system, GEM provides a remarkably simple route selection mechanism. However, GEM does not survive edge failures well. In this paper, we propose R-GEM and S-GEM that use the idea of GEM and improve its reliability performance significantly. Both of them outperform GEM in all of the experimental scenarios. Specifically, in the case that 2% of all edges in the network fail to transfer packets, when only disjoint pairs are taken into consideration, GEM leads to a path error rate of 10% while R-GEM and S-GEM only result in a path error rate of 2%.

Original languageEnglish
Title of host publicationWireless Algorithms, Systems, and Applications - Third International Conference, WASA 2008, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540885811, 9783540885818
Publication statusPublished - 2008
Externally publishedYes
Event3rd International Conference on Wireless Algorithms, Systems, and Applications, WASA 2008 - Dallas, TX, United States
Duration: 26 Oct 200828 Oct 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5258 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference3rd International Conference on Wireless Algorithms, Systems, and Applications, WASA 2008
Country/TerritoryUnited States
CityDallas, TX


  • Graph embedding
  • Multi-path
  • Reliability
  • Sensor networks


Dive into the research topics of 'Multi-path GEM for routing in wireless sensor networks'. Together they form a unique fingerprint.

Cite this