Project proposal

Local Search based DCOP Algorithms for Communication Networks
Supervisors : Dr. Youssef Hamadi*, Dr. Bilel Derbel** and Prof. El-Ghazali Talbi**

* Microsoft Research (UK) - INRIA Joint Center
** Dolphin INRIA Project Team, University of Lille 1

Location: INRIA Lille Nord Europe (Villeneuve d'Ascq, France)
Local contact e-mail : bilel dot derbel at lifl dot fr
Duration : 3 months

Generally speaking, the goal of this project is to study the power of local search algorithms for distributed constraint optimization problems (DCOP) arising in communication networks.

A distributed constraint optimization problem can be roughly defined as a problem in which a set of agents must distributively choose values for a set of variables such that the cost of a set of constraints over the variables is either minimized or maximized. For instance, given a graph G and a palette of colors C, a coloring of G is an assignment of a color from C to each node of G in such a way the number of adjacent nodes having the same color is minimized. In DCOP, this problem can be formulated as follow: there is one agent per node that controls the color assigned to that node. The goal of agents is to collaborate distributively by exchanging messages in order to find a good color assignment. Many problems arising in communication networks (e.g. ad-hoc and sensor networks) can be modeled as coloring-like DCOPs. In particular, this project is motivated by the modeling and the solving of frequency assignment problems in multi-channel dynamic networks using DCOP algorithms.

Many DCOP algorithms exist in the literature. One can classify these algorithms into two classes: complete algorithms and incomplete algorithms. Complete algorithms allow us to resolve a given problem in an optimal way, but these algorithms are resource (time, memory, message) consuming. Incomplete algorithms do not give a guarantee on the solution optimality, but they are in general more efficient to solve large instances and often output a good quality solution. In this project, we are interested in incomplete distributed local search DCOP algorithms which have been proved well suited for coloring-like problems.

The purpose of this project is to design new local search distributed algorithms to solve coloring-like distributed problems in radio communication networks. More specifically, we are interested in cognitive radio network devices scattered in a given area and able to communicate together using a set of possibly changing frequencies. The goal is to assign the frequencies that should be used by each node during specific time slots in order to optimize a network function (e.g., throughput) while avoiding interferences.  In addition, since the set of available frequencies can change over time, we also want to design an algorithm that adapts with the network dynamics. Roughly speaking, available frequencies (spectrum) in a given time period can be seen as a color palette given to nodes/edge. Hence, a frequency assignment problem can be seen as a distributed coloring problem where the quality of the coloring determines how 'good' the network will act. Of course, our objective is to find a high quality solution using efficient distributed algorithms.

There are two major issues to tackle in our project. First, we want to model our frequency assignment problem as a DCOP where each agent controls one node in the network. The modeling is in fact not a trivial task since the network topology and the set of available spectrum (frequencies) can change over time. As a first step, a simple graph-based model where the communication topology is abstracted away could be considered. The second major issue is to solve the modeled problem. To achieve this goal, we want to design/experiment efficient distributed local search algorithms. This work will be conducted by using and extending existing algorithms. In particular, the proposed algorithms/solutions are to be implemented on top of the FRODO software. FRODO is a Java-based framework providing a set of easy to use XML configuration files to encode and to solve DCOP instances. This latest task is to be conducted in tight collaboration with the FRODO administrators at EPFL (Ecole Polytechnique Fédérale de Lausanne, Suisse).