A HEURISTIC SEARCH BASED OPTIMAL WAVELENGTH ASSIGNMENT ALGORITHM TO MINIMIZE THE NUMBER OF SONET ADMS IN WDM RINGS

摘要

In WDM rings, determining minimum number of ADMs is NP-Hard. The best known algorithm namely, Breadth first least interference (BFLI) heuristic gives optimal results in only 77% cases. In this paper, we analyze the problem and suggest a new set covering formulation for minimizing the number of ADMs in WDM rings and use best first search algorithm (A~*) with the help of a two heuristics namely H-Ⅰ and H-Ⅱ to solve it . Heuristic H-Ⅰ is an admissible heuristic and can always ensure optimal result where as H-Ⅱ is an inadmissible heuristic which gives optimal results in most of the cases. We establish through experiments that the search algorithm with the proposed heuristic functions (H-Ⅰ & H-Ⅱ) performs better than BFLI.