Generation of Golomb Ruler Sequences and Optimization using Genetic Algorithms

Abstract

The attractiveness of lightwave communications is the ability of silica-optical fibers to carry large amounts of information over long repeaterless spans. To utilize the available bandwidth, numerous channels at different wavelengths can be multiplexed on the same fiber. To increase system margins, higher transmitter powers or lower fiber losses are required. All these attempts to fully utilize the capabilities of silica fibers will ultimately be limited by nonlinear interactions between the information bearing lightwaves and the transmission medium. These optical nonlinearities can lead to interference, distortion and excess attenuation of the optical signals, resulting in system degradations. One of these nonlinearities is the four-wave mixing whereby two or more optical waves at different wavelengths mix to produce new optical waves at other wavelengths and generate interfering signals for other channels. This will degrade both detection and heterodyne systems. Four-wave mixing (FWM) is a nonlinear process that occurs in materials such as silica with symmetric molecular structures and leads to generation of power at new optical frequencies from two or more co-propagating waves. The most significant negative effects of FWM are parametric gain and crosstalk in long haul, multi-channel Wavelength Division Multiplexed (WDM) systems. FWM efficiency is maximized at the zero dispersion wavelengths and for closely spaced input waves. Of particular concern is the case of WDM channels that are equally spaced in frequency as any FWM products will fall on frequencies used by other channels. By using unequal channel separations, the products of FWM can be made not to fall on allocated frequencies. In an attempt to reduce FWM effect in WDM systems, many unequally spaced channel allocation methods were proposed. However, they resulted in increase of bandwidth requirement compared to equally spaced channel allocation. This is due to the constraint of the minimum channel spacing between each channel and that the difference in the channel spacing between any two channels is assigned to be distinct. As the number of channels increases, the bandwidth for the unequally spaced channel allocation methods increases proportionately. In mathematics, the term 'Golomb Ruler' refers to a set of non-negative integers such that no distinct pairs of numbers from the set have the same difference. Since the difference between any two numbers is distinct, the new FWM frequencies generated would not fall into the one already assigned for the carrier channels. However, using conventional Golomb Rulers was not efficient as the operating bandwidth would be increased significantly as the existing methods. An Optimal Golomb Ruler (OGR) is the shortest Golomb Ruler possible for a given number of marks. Therefore, applying OGR to the channel allocation problem, it was possible to achieve the smallest distinct number to be used for the channel allocation. The OGRs were used to allocate the channels so as to restrict the expansion of the bandwidth. The Golomb Rulers have to be optimized to form OGRs using an optimization technique. There are several optimization techniques, the most common for engineering problems being stimulated annealing, evolution strategies and genetic algorithms. Simulated annealing probabilistically generates a sequence of states based on a cooling schedule to ultimately converge to the global optimum. Evolution strategies use mutations as search mechanisms and selection to direct the search toward the prospective regions in the search space. Genetic algorithms generate a sequence of populations by using a selection mechanism, and use crossover and mutation as search mechanisms. Thus, the genetic algorithms provide an alternative to traditional optimization techniques by using directed random searches to locate optimal solutions in complex landscapes. The GA is a stochastic global search method that mimics the metaphor of natural biological evolution. GAs operate on a population of potential solutions applying the principle of survival of the fittest to produce better and better approximations to a solution. At each generation, a new set of approximations is created by the process of selecting individuals according to their level of fitness in the problem domain and breeding them together using operators borrowed from natural genetics. This process leads to the evolution of populations of individuals that are better suited to their environment than the individuals that are better suited to their environment than the individuals that they were created from, just as in natural adaptation. In the present study, first of all a parametric run on fiber dispersion is performed to show dependency of four wave mixing on dispersion value. For operation near the zero dispersion wavelength, the FWM efficiency is maximized and as the dispersion increases, the power of the FWM products falls, that is, FWM effect decreases with increasing dispersion and vice-versa. Thus, for WDM systems deploying dispersion-shifted fibers to compensate for the dispersion induced in the fiber, it is a must to reduce FWM effect. In this concern, two algorithms for the generation of Golomb Ruler sequences are described. In the first algorithm, the modified extended quadratic congruence (EQC) sequences are generated and the second is the algorithm based on searching. These algorithms produce Golomb Rulers for any number of marks (channels). For both the algorithms, various examples of rulers for different number of marks are provided and bandwidth expansion factors are calculated that gives the factor of the bandwidth expanded with the use of unequal channel allocation in comparison with that of equal channel allocation. The total slot bandwidth and time requirements are calculated for different number of marks and compared for the two algorithms. It is seen that the bandwidth requirements for the search algorithm are less and in addition, the time required for the generation of sequences in search algorithm remains constant irrespective of the number of marks. Both these algorithm needed large bandwidth requirements. As the number of marks increases, the bandwidth increases exponentially. Optimization of the rulers means to have the short rulers, that is, the length of the rulers is minimized so as to conserve the bandwidth. Any optimization technique could be used here but for the NP-complete problems, like the Golomb Ruler, genetic algorithms are the best optimization technique to be used. Thus here the genetic algorithms are used to produce Optimal Golomb Rulers. The length of the rulers is the objective function to be minimized. As the number of generations increases, the length of the ruler and thus the bandwidth occupied tends to decrease, thus the rulers become more and more optimized, until no further improvements are there. This is the point where we get the optimal, or the shortest ruler. It is seen that by using genetic algorithms, bandwidth requirements become nearly one-third of that of the previous conventional algorithms, for the same number of channels. The physical significance of this work is seen as the reduction of the four-wave mixing effect in WDM systems. As the difference between every pair of channels is unique, the additional frequencies produced by the FWM process do not tend to fall upon the already assigned frequencies. Hence the crosstalk, which is the main concern in WDM systems, is minimized enhancing the efficiency of the overall optical system.