# Decentralized Constraint Satisfaction

K. R. Duffy1, C. Bordenave2and D. J. Leith1.

1: Hamilton Institute, National University of Ireland Maynooth 2: Department of Mathematics, University of Toulouse.

Abstract**—We show that several important resource allocation**
problems in wireless networks fit within the common framework of Constraint Satisfaction Problems (CSPs). Inspired by the requirements of these applications, where variables are located at distinct network devices that may not be able to communicate but may interfere, we define natural criteria that a CSP solver must possess in order to be practical. We term these algorithms decentralized CSP solvers. The best known CSP solvers were designed for centralized problems and do not meet these criteria.

We introduce a stochastic decentralized CSP solver, proving that it will find a solution in almost surely finite time, should one exist, and also showing it has many practically desirable properties. We benchmark the algorithm's performance on a well-studied class of CSPs, random k-SAT, illustrating that the time the algorithm takes to find a satisfying assignment is competitive with stochastic centralized solvers on problems with order a thousand variables despite its decentralized nature. We demonstrate the solver's practical utility for the problems that motivated its introduction by using it to find a non-interfering channel allocation for a network formed from data from downtown Manhattan.

## I. Introduction

A Constraint Satisfaction Problem (CSP) consists of N
variables, ~x := (x1*, . . . , x*N ), and M clauses, i.e. {0, 1}-
valued functions, (Φ1(~x)*, . . . ,* ΦM(~x)). An assignment ~x is a solution if all clauses simultaneously evaluate to 1. In the context of wireless networks, we show that CSPs provide a unifying framework that encompasses many important resource allocation tasks. Examples include: allocation of radio channels so that transmissions by neighbouring WLANs (Wireless Local Area Networks) or mobile phone cells do not interfere; the selection of packets to be XORed on each link in network coding; and finding a non-colliding schedule of time-slots in a WLAN. Unlike in traditional CSPs, however, in network applications each constrained variable xiis typically co-located with a physically distinct device such as an access point, base-station or a link. The resulting communication constraints impose severe restrictions on the nature of the algorithm that can be used for solving the CSP. These restrictions are violated by existing CSP solvers, leading us to define a new class of algorithms that we term *decentralized CSP solvers*. We constructively establish the existence of decentralized solvers by introducing a family of randomized algorithms belonging to this class.

Roughly speaking, decentralized CSP solvers must be capable of finding a satisfying assignment, ~x, while updating each variable xi based solely on knowledge of whether all of the clauses in which xi participates are satisfied or at least one This material is based upon works supported by Science Foundation Ireland under Grant No. 07/IN.1/I901.

clause is unsatisfied. The following example gives a concrete illustration of the origins of these constraints.

## 1 A. Motivating Example: Channel Allocation

802.11 WLANs are ubiquitous, but their deployments are unstructured and they operate in an unlicensed frequency band.

Within this band, an 802.11 WLAN can select one of several channels, typically 11, to operate on. In the vast majority of WiFi routers channel selection is, at present, based on operator selection without any quantitative instruction from the router. Self-selection of this channel is the task we consider here. Co-ordinated selection is hampered by the fact that the interference range of a typical 802.11 device is substantially larger than its communication range. Consequently, WLANs can interfere but may be unable to decode each others messages (illustrated schematically in Fig. 1). Discovery by a WLAN of the existence of interfering WLANs via its wired back-haul may be prevented by firewalls and, in any case, these WLANs may not know their physical location. These practical restrictions mandate a decentralized channel-selection algorithm.

We can identify the task of each WLAN self-selecting a non-interfering channel with a CSP with communication constraints imposed by the network topology. Let xi be the channel selected by WLAN i ∈ {1*, . . . , N*} and define M = N(N − 1)/2 clauses, one for each pair of WLANs, that evaluates to one if the WLANs are on non-interfering channels or are out of interference range and is zero otherwise.

Due to the unstructured nature of the deployment, the lack of shared administrative control and communication constraints, a WLAN cannot rely on knowing the number or the identity of interfering WLANs or the channels that they currently have selected. A practical CSP solver for this task can only rely on each WLAN being able to measure whether: (i) all of the neighbouring WLANs have selected a different channel from it; or (ii) if one or more neighbours have selected the same channel.

In certain settings, a limited amount of communication of variable values between the stations hosting them may be feasible. For example, it may be possible for stations hosting a link or for a WLAN to overhear beacons or traffic from a subset of its interferers, or for an access point to communicate with other, nearby access points. Algorithms for channel selection that are proposed in the literature assume the existence of end-to-end communication for centralized solutions, for message passing in decentralized or gossiping solutions, or to co-ordinate global restart in simulated annealing proposals e.g. [1], [2], [3], [4] and references therein. This arXiv:1103.3240v4 [cs.AI] 9 Oct 2012