Message-Passing for Wireless Scheduling: An Experimental Study

In the recent years, message-passing paradigm has emerged as a canonical algorithmic solution to solve network-wide problems by means of minimal local information exchange, across variety of disciplines. The primary purpose of this work is to understand trade-offs offered between network performance and protocol overhead by a class of message-passing algorithms - belief propagation and its variants. Through an extensive simulation study, for prototypical network topological models, the authors find that such class can lead to wireless network scheduling algorithms under which each node exchanges exactly one message per time-slot and achieve reasonably high performance.