A fast heuristic for solving the D1EC coloring problem

Vincenzo Mancuso, Fabio Campoccia

    Risultato della ricerca: Other

    Abstract

    In this paper we propose an efficient heuristic forsolving the Distance-1 Edge Coloring problem (D1EC) for theon-the-fly assignment of orthogonal wireless channels inwireless as soon as a topology change occurs. The coloringalgorithm exploits the simulated annealing paradigm, i.e., ageneralization of Monte Carlo methods for solvingcombinatorial problems. We show that the simulatedannealing-based coloring converges fast to a suboptimalcoloring scheme even for the case of dynamic channelallocation. However, a stateful implementation of the D1ECscheme is needed in order to speed-up the network coloringupon topology changes. In fact, a stateful D1EC reduces thealgorithm’s convergence time by more than 60% incomparison to stateless algorithms.
    Lingua originaleEnglish
    Numero di pagine8
    Stato di pubblicazionePublished - 2010

    Fingerprint Entra nei temi di ricerca di 'A fast heuristic for solving the D1EC coloring problem'. Insieme formano una fingerprint unica.

    Cita questo