Options
Efficient CSMA based on Kikuchi approximation
Date Issued
16-11-2016
Author(s)
Swamy, Peruru Subrahmanya
Bellam, Venkata Pavan Kumar
Indian Institute of Technology, Madras
Indian Institute of Technology, Madras
Abstract
CSMA algorithms based on Gibbs sampling can achieve throughput optimality if appropriate attempt rates are employed. However, the problem of computing these attempt rates is NP-hard. Inspired by the well-known Kikuchi approximation, we propose a simple distributed algorithm, which obtains closed form estimates for the attempt rates. We also prove that our algorithm is exact for a class of graphs, called the chordal graphs. Numerical results suggest that the proposed algorithm outperforms the existing Bethe approximation based algorithms for spatial networks.