A Novel Energy–Degree–Distance-Based Connected Dominating Set Algorithm: Performance Comparison Across Node Placement Strategies
DOI:
https://doi.org/10.70112/ajes-2025.14.1.4269Keywords:
Wireless Sensor Networks (WSNs), Connected Dominating Set (CDS), Energy Efficiency, Node Deployment Models, Network ConnectivityAbstract
In wireless sensor networks (WSNs), constructing an energy-efficient Connected Dominating Set (CDS) is essential for ensuring reliable communication, balanced energy usage, and extended network lifetime. Existing methods often fail to consider the impact of node distribution on CDS performance. This study proposes a CDS construction algorithm that integrates residual energy, node degree, and average neighbor distance into a unified selection metric for dominator nodes. Connector nodes are subsequently selected to ensure network-wide connectivity. The algorithm was evaluated under four deployment models: grid, triangular, random, and hybrid. Key performance indicators included CDS size, hop count, average degree, energy consumption, spectral radius, and algebraic connectivity. The proposed algorithm consistently produced compact and connected CDSs across all deployment strategies. Grid and triangular models exhibited superior performance in terms of energy efficiency and connectivity, characterized by low hop count and balanced energy consumption. Even under random and hybrid placements, the algorithm maintained robust backbone structures and outperformed baseline approaches. Spectral analysis further confirmed higher algebraic connectivity and reduced spectral radius, indicating improved robustness and communication efficiency. Overall, the proposed algorithm effectively balances energy usage and preserves connectivity across diverse node placements, offering practical insights for the design of resilient and energy-aware protocols in real-world WSN applications.
References
[1]A. Lanzolla and M. Spadavecchia, “Wireless sensor networks for environmental monitoring,” Sensors, vol. 21, no. 4, p. 1172, Feb. 2021, doi: 10.3390/s21041172.
[2]S. Benoy, “Wireless sensor networks for healthcare monitoring: Challenges and opportunities,” J. Biomed. Syst. Emerg. Technol., Commentary, 2023. [Online]. Available: https://www.hilarispublisher. com/open-access/wireless-sensor-networks-for-healthcare-monitoring-challenges-and-opportunities-98539.html. [Accessed: Jul.8, 2025].
[3]J. Aponte-Luis, J. A. Gómez-Galán, F. Gómez-Bravo, M. Sánchez-Raya, J. Alcina-Espigado, and P. M. Teixido-Rovira, “An efficient wireless sensor network for industrial monitoring and control,” Sensors, vol. 18, no. 1, p. 182, Jan. 2018, doi: 10.3390/s18010182.
[4]A. Khalifeh, K. A. Darabkh, A. M. Khasawneh, I. Alqaisieh, M.Salameh, A. AlAbdala, et al., “Wireless sensor networks for smart cities: Network design, implementation and performance evaluation,” Electronics, vol. 11, no. 3, p. 409, 2022, doi: 10.3390/electronics 11030409.
[5]M. A. Rahu, S. Karim, R. Shams, A. A. Hoshu, and A. F. Chandio, “Wireless sensor networks-based smart agriculture: Sensing technologies, applications and future directions,” Sukkur IBA J. Emerg. Technol., vol. 5, no. 2, pp. 18-32, Dec. 2022, doi: 10.30537/sjet.v5i2. 1104.
[6]S. Guha and S. Khuller, “Approximation algorithms for connected dominating sets,” Algorithmica, vol. 20, no. 4, pp. 374-387, 1998,doi: 10.1007/PL00009191.
[7]P. J. Wan, K. M. Alzoubi, and O. Frieder, “Distributed construction of connected dominating set in wireless ad hoc networks,” in Proc. 21stAnnu. Joint Conf. IEEE Comput. Commun. Soc. (INFOCOM), vol. 3,2002, pp. 1597-1604, doi: 10.1109/INFCOM.2002.1019405.
[8]D. Cokuslu, K. Erciyes, and O. Dagdeviren, “A dominating set-based clustering algorithm for mobile ad hoc networks,” in Distributed Applications and Interoperable Systems (DAIS 2006), M. G. Jaatun, A. A.Lazar, and F. Eliassen, Eds. Berlin, Germany: Springer, 2006, pp.321-332, doi: 10.1007/11758501_77.
[9]G. Venkataraman, S. Emmanuel, and S. Thambipillai, “DASCA: A degree and size-based clustering approach for wireless sensor networks,” in Int. Symp. Wireless Commun. Syst., 2005, vol. 1, no. 1,pp. 508-512, doi: 10.1109/ISWCS.2005.1547753.
[10]H. Tan, W. Zeng, and L. Bao, “PATM: Priority-based adaptive topology management for efficient routing in ad hoc networks,” in Computational Science -ICCS 2005, 5th Int. Conf., Proc., Part II, V.N. Alexandrov et al., Eds. Berlin, Germany: Springer, 2005, pp. 511-518, doi: 10.1007/11428848_64.
[11]S. Balbal, S. Bouamama, and C. Blum, “A greedy heuristic for maximizing the lifetime of wireless sensor networks based on disjoint weighted dominating sets,” Algorithms, vol. 14, no. 6, p. 170,Jun. 2021, doi: 10.3390/a14060170.
[12]D. Kim, Y. Wu, Y. Li, F. Zou, and D.-Z. Du, “Constructing minimum Connected dominating sets with bounded diameters in wireless networks,” IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 2,pp. 147-157, Feb. 2009, doi: 10.1109/TPDS.2008.74.
[13]V. S. Anitha and M. P. Sebastian, “Application oriented connected dominating set-based cluster formation in wireless sensor networks,” J.Braz. Comput. Soc., vol. 17, pp. 3-18, 2011, doi: 10.1007/s13173-010-0024-0.
[14]A. R. Hedar, S. N. Abdulaziz, A. A. Sewisy, and G. A. El-Sayed, “Adaptive scatter search to solve the minimum connected dominating set problem for efficient management of wireless networks,” Algorithms, vol. 13, no. 2, p. 35, 2020, doi: 10.3390/a13020035.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Centre for Research and Innovation
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
