Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks

摘要

Given a wireless Ad-Hoc network modeled as a unit disk graph U in the plane, we present a localized distributed algorithm that constructs a bounded degree planar power spanner of U with a bounded stretch factor. More specifically, for an integer parameter k ≥ 8 and a power exponent constant p ∈ [2,5], our algorithm constructs a planar power spanner for the network of degree bounded by k + 5 and a stretch factor bounded by 1 + 2~P sin~p (π/k). This significantly improves the previous best results in the literature by Song et al..