1/2005 : Distributed Construction of an Underlay in Wireless Networks
European Workshop on Wireless Sensor Networks, Istanbul, Turkey
A wireless network consists of a large number of nodes that use wireless communication links to collectively perform certain tasks in various application domains (industry, military, etc.). Since wireless nodes are irregularly scattered over a large application area, a suitable wireless multihop routing protocol is needed to facilitate the communication between arbitrary nodes. Many geographic routing protocols use a planar graph as the underlying network topology. This paper presents an efficient algorithm for the localized computation of such an underlay, namely, the Short Delaunay Triangulation (SDT). The SDT contains all edges of the Delauany Triangulation that are shorter than the communication range. The great asset of the Short Delaunay Triangulation is its spanning property: It approximates the shortest path of the Unit Disk Graph by a constant factor. Our distributed algorithm for constructing the SDT surpasses alternative underlay construction algorithms and requires point-to-point communication links only.
author = "Hannes Stratil",
title = "Distributed Construction of an Underlay in Wireless Networks",
journal = "European Workshop on Wireless Sensor Networks, Istanbul, Turkey",
year = "2005",
month = "Jan."
Get EWSN2005.pdf - Adobe PDF-format, (143.5977 KB; posted at July 09 2013)