A Heuristic Search based Optimal Wavelength Assignment Algorithm to Minimize the Number of Sonet ADMs in WDM Rings

J. Sethuraman, A. Mahanti, and D. Saha (India)


ADM, Grouppath, A*, H-I, H-II, 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-I and H-II to solve it . Heuristic H-I is an admissible heuristic and can always ensure optimal result where as H-II 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-I & H-II) performs better than BFLI.

Important Links:

Go Back