In this paper, we develop two methods for improving the performance of the standard Distributed Breakout Algorithm \cite{yokoo:dba} using the notion of interchangeability. We study the performance of this algorithm on the problem of distributed sensor networks. In particular, we consider how neighborhood interchangeability and neighborhood partial interchangeability \cite{freuder:interch} can be used to keep conflicts localized and avoid ``chain reactions'' where a conflict originating in one part of the problem spreads to neighboring areas. We see from the experimental results that such techniques can bring about significant improvements in terms of the number of cycles required to solve the problem (and therefore improvements in terms of communication and time requirements), especially for difficult problems. Moreover, the improved algorithms are able to solve a higher proportion of the test problems.