On the Complexity of Distributed Self-Configuration in Wireless Networks

We consider three distributed configuration tasks that arise in the setup and operation of multi-hop wireless networks: partition into coordinating cliques, Hamiltonian cycle formation and conflict-free channel allocation. We show that the probabilities of accomplishing these tasks undergo zero-one phase transitions with respect to the transmission range of individual nodes. We model these tasks as distributed constraint satisfaction problems (DCSPs) and show that, even though they are NP-hard in general, these problems can be solved efficiently on average when the network is operated sufficiently far from the transition region. Phase transition analysis is shown to be a useful mechanism for quantifying the critical range of energy and bandwidth resources needed for the scalable performance of self-configuring wireless networks.