This paper introduces two new algorithms for the minimum connected dominating set (MCDS) problem with constraints applicable to wireless network design, based on simulated annealing and tabu search principles. Each algorithm is tested on a selection of random graphs and shown to produce significantly smaller connected dominating sets when compared to a number of established methods. The simulated annealing algorithm is found to favour large, sparse graphs while the tabu search heuristic prefers smaller dense instances. In conclusion, we consider the adaptation of these algorithms to hybrid techniques and comment on the possible use of hyper-heuristics.
Computer and Systems Architecture | Digital Communications and Networking | Hardware Systems | Systems and Communications
Morgan, M. & Grout, V. (2007), ‘Metaheuristics for Wireless Network Optimisation’. [Paper presented to the 3rd IARIA/IEEE Advanced International Conference on Telecommunications (AICT 2007) 13th -19th May 2007]. Mauritius: IEEE
Digital Commons Citation
Morgan, Mike and Grout, Vic, "Metaheuristics for Wireless Network Optimisation" (2007). Computing. Paper 63.