A Fast Distributed Approximation Algorithm for Minimum Spanning Trees in the SINR Model

Free registration required

Executive Summary

A fundamental problem in wireless networks is the Minimum Spanning Tree (MST) problem: given a set V of wireless nodes, compute a spanning tree T, so that the total cost of T is minimized. In recent years, there has been a lot of interest in the physical interference model based on SINR constraints. Distributed algorithms are especially challenging in the SINR model, because of the non-locality of the model. In this paper, the authors develop a fast distributed approximation algorithm for MST construction in an SINR based distributed computing model.

  • Format: PDF
  • Size: 145.38 KB