A Heuristic Algorithm for Static Wavelength Assignment in WDM Optical Networks

摘要

In this paper, we present a heuristic algorithm for assigning wavelengths to static lightpath requests in WDM optical networks. Given the network and lightpath requests, the problem is to assign wavelengths to the lightpaths so as to minimize the number of wavelengths used. The problem is posed as a graph-coloring problem, which is next solved using the heuristic. The proposed heuristic starts with assigning a color to the first node of the auxiliary graph represented by an array of linked list. Subsequently, the algorithm colors other nodes by checking the color of the adjacent nodes through the node-color array and finding the first unused color from the color array. The time complexity of the heuristic is computed as O(n~2), where n is the number of lightpaths to be assigned wavelengths.