A Greedy Simulated Annealing-based Multiobjective Algorithm for the Minimum Weight Minimum Connected Dominating Set Problem
Received: 8 July 2024 | Revised: 29 July 2024 | Accepted: 3 August 2024 | Online: 28 August 2024
Corresponding author: Hayet Dahmri
Abstract
The minimum connected dominating set problem is a well-known NP-hard combinatorial optimization problem in graph theory, with various fields of application including wireless sensor networks, optical networks, and systems biology. This paper presents an adaptive multiobjective simulated annealing approach to address a variant of the minimum connected dominating set problem known as the Minimum Weight Minimum Connected Dominating Set Problem. This approach combines a multiobjective Pareto set with a greedy simulated annealing algorithm to tackle the problem by simultaneously optimizing two objectives, namely the cardinality and the total weight of the connected dominating set. Experimental results compared to those obtained by current state-of-the-art approaches show the superiority of our method.
Keywords:
greedy heuristic, Pareto optimality, minimum connected dominating set, minimum weight connected dominating set, simulated annealingDownloads
References
Y. Wang, W. Wang, and X.-Y. Li, "Distributed low-cost backbone formation for wireless ad hoc networks," in 6th ACM International Symposium on Mobile ad Hoc Networking and Computing, Urbana, IL , USA, Dec. 2005, pp. 2–13.
J. Zhang and C.-F. Jia, "Minimum Connected Dominating Set Algorithm with Weight in Wireless Sensor Networks," in 4th International Conference on Wireless Communications, Networking and Mobile Computing, Dalian, China, Oct. 2008, pp. 1–4.
R. Misra and C. Mandal, "Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 3, pp. 292–302, Mar. 2010.
A. Sen, S. Banerjee, P. Ghosh, S. Murthy, and H. Ngo, "Brief announcement: on regenerator placement problems in optical networks," in 22nd ACM Symposium on Parallelism in Algorithms and Architectures, Thira, Greece, Jun. 2010, pp. 178–180.
A. Sen, S. Murthy, and S. Bandyopadhyay, "On Sparse Placement of Regenerator Nodes in Translucent Optical Network," in IEEE GLOBECOM 2008 - 2008 IEEE Global Telecommunications Conference, New Orleans, LA, USA, Dec. 2008, pp. 1–6.
T. Milenkovic, V. Memisevic, A. Bonato, and N. Przulj, "Dominating Biological Networks," PLOS ONE, vol. 6, no. 8, Jul. 2011, Art. no. e23016.
J. Blum, M. Ding, A. Thaeler, and X. Cheng, "Connected Dominating Set in Sensor Networks and MANETs," in Handbook of Combinatorial Optimization: Supplement Volume B, D.-Z. Du and P. M. Pardalos, Eds. Boston, MA, USA: Springer, 2005, pp. 329–369.
D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications. New York, NY, USA: Springer, 2012.
D. S. Johnson and M. R. Garey, "A guide to the theory of NP-completeness," The Journal of Symbolic Logic, vol. 48, no. 2, pp. 498–500, Jun. 1983.
M. Morgan and V. Grout, "Metaheuristics for Wireless Network Optimisation," in The Third Advanced International Conference on Telecommunications, Morne, Mauritius, Dec. 2007, pp. 15–15.
R. Jovanovic and M. Tuba, "Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem," Computer Science and Information Systems, vol. 10, no. 1, pp. 133–149, 2013.
R. Li, S. Hu, J. Gao, Y. Zhou, Y. Wang, and M. Yin, "GRASP for connected dominating set problems," Neural Computing and Applications, vol. 28, no. 1, pp. 1059–1067, Dec. 2017.
X. Wu, Z. Lu, and P. Galinier, "Restricted swap-based neighborhood search for the minimum connected dominating set problem," Networks, vol. 69, no. 2, pp. 222–236, 2017.
A.-R. Hedar, R. Ismail, G. A. El-Sayed, and K. M. J. Khayyat, "Two Meta-Heuristics Designed to Solve the Minimum Connected Dominating Set Problem for Wireless Networks Design and Management," Journal of Network and Systems Management, vol. 27, no. 3, pp. 647–687, Jul. 2019.
Z. A. Dagdeviren, D. Aydin, and M. Cinsdikici, "Two population-based optimization algorithms for minimum weight connected dominating set problem," Applied Soft Computing, vol. 59, pp. 644–658, Oct. 2017.
S. Bouamama, C. Blum, and J.-G. Fages, "An algorithm based on ant colony optimization for the minimum connected dominating set problem," Applied Soft Computing, vol. 80, pp. 672–686, Jul. 2019.
D. Rengaswamy, S. Datta, and S. Ramalingam, "Multiobjective Genetic Algorithm for Minimum Weight Minimum Connected Dominating Set," in International Conference on Intelligent Systems Design and Applications, Delhi, India, Dec. 2017, pp. 558–567.
H. Dahmri and S. Bouamama, "Improved NSGA-II for Minimum Weight Minimum Connected Dominating Set Problem," in International Symposium on Modelling and Implementation of Complex Systems, Batna, Algeria, Oct. 2020, pp. 248–261.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671–680, May 1983.
M. O. Genc and N. Kaya, "Vibration Damping Optimization using Simulated Annealing Algorithm for Vehicle Powertrain System," Engineering, Technology & Applied Science Research, vol. 10, no. 1, pp. 5164–5167, Feb. 2020.
S. F. Sesay, C. W. Wekesa, and L. M. H. Ngoo, "Optimal Placement of Superconducting Magnetic Energy Storages in a Distribution Network with Embedded Wind Power Generation," Engineering, Technology & Applied Science Research, vol. 14, no. 2, pp. 13416–13424, Apr. 2024.
N. T. Linh and P. V. Long, "A Novel Solution Method for the Distribution Network Reconfiguration Problem based on an Objective Function and considering the Cost of Electricity Transmission," Engineering, Technology & Applied Science Research, vol. 13, no. 6, pp. 12366–12372, Dec. 2023.
A. Suppapitnarm, K. A. Seffen, G. T. Parks, and P. J. Clarkson, "A Simulated Annealing Algorithm for Multiobjective Optimization," Engineering Optimization, vol. 33, no. 1, pp. 59–85, Nov. 2000.
F. Romeo, A. K. Sangiovanni Vincentelli, and M. D. Huang, "An Efficient General Cooling Schedule for Simulated Annealing," in Proceedings of IEEE International Conference on Computer Aided Design, Jan. 1986, pp. 381–384.
M. Nazarieh, A. Wiese, T. Will, M. Hamed, and V. Helms, "Identification of key player genes in gene regulatory networks," BMC Systems Biology, vol. 10, no. 1, Sep. 2016, Art. no. 88.
E. Zitzler and L. Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach," IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, Aug. 1999.
Downloads
How to Cite
License
Copyright (c) 2024 Hayet Dahmri, Salim Bouamama, Samir Balbal
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.