Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks

Abstract

We propose a novel localized algorithm that constructs a bounded degree and planar spanner for wireless ad hoc networks modeled by unit disk graph (UDG). Every node only has to know its 2-hop neighbors to find the edges in this new structure. Our method applies the Yao structure on the local Delaunay graph [1] in an ordering that are computed locally.