Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Efficient graph planarization in sensor networks and local routing algorithm
 
conference paper

Efficient graph planarization in sensor networks and local routing algorithm

Huc, Florian  
•
Jarry, Aubin
•
Leone, Pierre
Show more
2012
2012 Ieee 8Th International Conference On Distributed Computing In Sensor Systems (Dcoss)
8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS)/IWSN/WiSARN/PWSN

In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under light constraints on the edge lengths and induces a total exchange of at most 6n node identifiers. Its total computational complexity is O(n Delta), with Delta the maximum degree of the communication graph. The second algorithm that we present is a simple and efficient algorithm to route messages in this planar graph that requires routing tables with only three entries. We support these theoretical results by simulations showing the robustness of our algorithms when the coordinates are inaccurate.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/Dcoss.2012.64
Web of Science ID

WOS:000309235500020

Author(s)
Huc, Florian  
Jarry, Aubin
Leone, Pierre
Rolim, Jose
Date Issued

2012

Publisher

Ieee

Publisher place

New York

Published in
2012 Ieee 8Th International Conference On Distributed Computing In Sensor Systems (Dcoss)
ISBN of the book

978-0-7695-4707-7

Total of pages

10

Start page

140

End page

149

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event name
8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS)/IWSN/WiSARN/PWSN
Available on Infoscience
February 27, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/89920
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés