6533b7d8fe1ef96bd126ad16
RESEARCH PRODUCT
A fast heuristic for solving the D1EC coloring problem
Vincenzo MancusoFabio Campocciasubject
Mathematical optimization:QA Mathematics::QA75 Electronic computers. Computer science [Q Science]TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESChannel allocation schemesHeuristic (computer science)Computer scienceSettore ING-INF/03 - Telecomunicazioni:T Technology (General) [T Technology]Topology (electrical circuits)Greedy coloringEdge coloringTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESStateful firewall:Q Science (General) [Q Science]TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYConvergence (routing)Simulated annealing:TK Electrical engineering. Electronics Nuclear engineering [T Technology]Channel assignment Edge coloring Simulated annealing.MathematicsofComputing_DISCRETEMATHEMATICSdescription
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 sub optimal 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-01-01 |