Network engineering using multi-objective evolutionary algorithms

[摘要] ENGLISH ABSTRACT: We use Evolutionary Multi-Objective Optimisation (EMOO) algorithms to optimise objectivefunctions that reflect situations in communication networks. These include functionsthat optimise Network Engineering (NE) objective functions in core, metro and wirelesssensor networks. The main contributions of this thesis are threefold.Routing and Wavelength Assignment (RWA) for IP backbone networks.Routing and Wavelength Assignment (RWA) is a problem that has been widely addressedby the optical research community. A recent interest in this problem has been raised by theneed to achieve routing optimisation in the emerging generation multilayer networks wheredata networks are layered above a Dense Wavelength Division Multiplexing (DWDM) network.We formulate the RWA as both a single and a multi-objective optimisation problemwhich are solved using a two-step solution where (1) a set of paths are found using geneticoptimisation and (2) a graph coloring approach is implemented to assign wavelengths tothese paths. The experimental results from both optimisation scenarios reveal the impactof (1) the cost metric used which equivalently defines the fitness function (2) the algorithmicsolution adopted and (3) the topology of the network on the performance achieved bythe RWA procedure in terms of path quality and wavelength assignment.Optimisation of Arrayed Waveguide Grating (AWG) Metro Networks.An Arrayed Waveguide Grating (AWG) is a device that can be used as a multiplexer ordemultiplexer in WDM systems. It can also be used as a drop-and-insert element or evena wavelength router. We take a closer look at how the hardware and software parametersof an AWG can be fine tuned in order to maximise throughput and minimise the delay.We adopt a multi-objective optimisation approach for multi-service AWG-based single hop metro WDM networks. Using a previously proposed multi-objective optimisation modelas a benchmark, we propose several EMOO solutions and compare their efficiency byevaluating their impact on the performance achieved by the AWG optimisation process.Simulation reveals that (1) different EMOO algorithms can exhibit different performancepatterns and (2) good network planning and operation solutions for a wide range of trafficscenarios can result from a well selected EMOO algorithm.Wireless Sensor Networks (WSNs) Topology (layout) Optimisation.WSNs have been used in a number of application areas to achieve vital functions in situationswhere humans cannot constantly be available for certain tasks such as in hostile areaslike war zones, seismic sensing where continuous inspection and detection are needed, andmany other applications such as environment monitoring, military operations and surveillance.Research and practice have shown that there is a need to optimise the topology(layout) of such sensors on the ground because the position on which they land may affectthe sensing efficiency. We formulate the problem of layout optimisation as a multi-objectiveoptimisation problem consisting of maximising both the coverage (area) and the lifetime ofthe wireless sensor network. We propose different algorithmic evolutionary multi-objectivemethods and compare their performance in terms of Pareto solutions. Simulations revealthat the Pareto solutions found lead to different performance patterns and types of layouts.

[发布机构] Stellenbosch University