In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a suboptimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergence time by more than 60% in comparison to stateless algorithms.

Campoccia, F., Mancuso, V. (2010). A fast heuristic for solving the D1EC coloring problem. In EUC 2010.

A fast heuristic for solving the D1EC coloring problem

Campoccia, Fabio;MANCUSO, Vincenzo
2010-01-01

Abstract

In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a suboptimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergence time by more than 60% in comparison to stateless algorithms.
dic-2010
EUC 2010
Hong Kong SAR, China,
Dec 11, 2010 - Dec 13, 2010
2010
8
Campoccia, F., Mancuso, V. (2010). A fast heuristic for solving the D1EC coloring problem. In EUC 2010.
Proceedings (atti dei congressi)
Campoccia, F; Mancuso, V
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/52308
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact