Probabilistic Domination in Erdős–Rényi and Random Geometric Graphs: Threshold Analysis and Energy-Efficient Applications in Wireless Sensor Networks
DOI:
https://doi.org/10.30862/jhm.v9i1.1078Keywords:
Erdős–Rényi graph, Monte Carlo simulation, random geometric graph, wireless sensor networkAbstract
Wireless sensor networks (WSNs) require efficient strategies that preserve network coverage and connectivity while minimizing communication overhead and energy consumption. However, theoretical domination properties derived from random graph models are rarely integrated with finite-network simulations and practical network-lifetime measures. This study develops a probabilistic domination framework for Erdős–Rényi and random geometric graphs and applies the resulting dominating sets to cluster-head selection in WSNs. Analytical calculations were performed to estimate domination thresholds and dominating-set benchmarks for Erdős–Rényi graphs, whereas 10,000 Monte Carlo simulations were conducted for each parameter configuration to compare greedy and randomized selection algorithms. Performance was evaluated using dominating-set size, variance, coverage ratio, normalized energy cost, first node death, and last node death. The analytical results showed that the domination threshold decreased from 0.08 for a 50-node graph to 0.03 for a 200-node graph, while the relative dominating-set size declined from 24% to 15% of the network. For an Erdős–Rényi graph with 100 nodes and an edge probability of 0.30, the greedy algorithm reduced the mean dominating-set size by 4.8% and its variance by 38.2% compared with randomized selection. In the corresponding WSN scenario, greedy cluster-head selection increased coverage from 0.93 to 0.95, reduced normalized energy cost by 12%, and improved first node death and last node death by 12.5% and 7.1%, respectively. These findings demonstrate that probabilistic domination effectively connects random graph theory with energy-aware WSN design, although broader validation across diverse parameter settings and comprehensive energy models remains necessary.
References
Alwasel, B., Salim, A., Khedr, A. M., & Osamy, W. (2024). Dominating Sets-Based Approach for Maximizing Lifetime of IoT-Based Heterogeneous WSNs Enabled Sustainable Smart City Applications. IEEE Access, 12, 44069–44079. https://doi.org/10.1109/ACCESS.2024.3379425
Amutha, J., Sharma, S., & Nagar, J. (2020, March 1). WSN Strategies Based on Sensors, Deployment, Sensing Models, Coverage and Energy Efficiency: Review, Approaches and Open Issues. Wireless Personal Communications. Springer. https://doi.org/10.1007/s11277-019-06903-z
Balbal, S., Bouamama, S., & Blum, C. (2021). A greedy heuristic for maximizing the lifetime of wireless sensor networks based on disjoint weighted dominating sets. Algorithms, 14(6). https://doi.org/10.3390/a14060170
Bonato, A., & Wang, C. (2008). A note on domination parameters in random graphs. Discussiones Mathematicae Graph Theory, 28(2), 335. https://doi.org/10.7151/dmgt.1409
Bouamama, S., Blum, C., & Pinacho-Davidson, P. (2022). A Population-Based Iterated Greedy Algorithm for Maximizing Sensor Network Lifetime. Sensors, 22(5). https://doi.org/10.3390/s22051804
Clark, L., & Johnson, D. (2011). The independent domination number of a random graph. Discussiones Mathematicae - Graph Theory, 31(1), 129–142. https://doi.org/10.7151/dmgt.1533
Ghaffari, F., Bahrak, B., & Shariatpanahi, S. P. (2022). A novel approach to partial coverage in wireless sensor networks via the roman dominating set. IET Networks, 11(2), 58–69. https://doi.org/10.1049/ntw2.12034
Ghafouri, S., & Khasteh, S. H. (2020). A survey on exponential random graph models: An application perspective. PeerJ Computer Science, 2020(4). https://doi.org/10.7717/peerj-cs.269
Glebov, R., Liebenau, A., & Szabó, T. (2015). On the concentration of the domination number of the random graph. SIAM Journal on Discrete Mathematics, 29(3), 1186–1206. https://doi.org/10.1137/12090054X
Hedar, A. R., Abdulaziz, S. N., Mabrouk, E., & El-Sayed, G. A. (2020). Wireless sensor networks fault-tolerance based on graph domination with parallel scatter search. Sensors (Switzerland), 20(12), 1–27. https://doi.org/10.3390/s20123509
Jiang, P., Liu, J., Wu, F., Wang, J., & Xue, A. (2016). Node deployment algorithm for underwater sensor networks based on connected dominating set. Sensors (Switzerland), 16(3). https://doi.org/10.3390/s16030388
Lisiecki, D., Zhang, P., & Theel, O. (2019). CONE: A connected dominating set-based flooding protocol for wireless sensor networks. Sensors (Switzerland), 19(10). https://doi.org/10.3390/s19102378
Luo, C., Chen, W., Yu, J., Wang, Y., & Li, D. (2018). A novel centralized algorithm for constructing virtual backbones in wireless sensor networks. Eurasip Journal on Wireless Communications and Networking, 2018(1). https://doi.org/10.1186/s13638-018-1068-7
Ma, C., Yang, Y., & Zhang, Z. (2007). Constructing battery-aware virtual backbones in wireless sensor networks. Eurasip Journal on Wireless Communications and Networking, 2007. https://doi.org/10.1155/2007/40154
Manman, L., Goswami, P., Mukherjee, P., Mukherjee, A., Yang, L., Ghosh, U., … Nkenyereye, L. (2021). Distributed Artificial Intelligence Empowered Sustainable Cognitive Radio Sensor Networks: A Smart City on-demand Perspective. Sustainable Cities and Society, 75. https://doi.org/10.1016/j.scs.2021.103265
Mitsche, D., & Penrose, M. D. (2021). Limit theory of combinatorial optimization for random geometric graphs. Annals of Applied Probability, 31(6), 2721–2771. https://doi.org/10.1214/20-AAP1661
Mo, S., Bao, Z., Zhang, P., & Peng, Z. (2020). Towards an efficient weighted random walk domination. Proceedings of the VLDB Endowment, 14(4), 560–572. https://doi.org/10.14778/3436905.3436915
Oikonomou, K., Koufoudakis, G., Aissa, S., & Stavrakakis, I. (2023). Probabilistic Flooding Performance Analysis Exploiting Graph Spectra Properties. IEEE/ACM Transactions on Networking, 31(1), 133–146. https://doi.org/10.1109/TNET.2022.3192310
Ojeda, F., Mendez, D., Fajardo, A., & Ellinger, F. (2023, August 1). On Wireless Sensor Network Models: A Cross-Layer Systematic Review. Journal of Sensor and Actuator Networks. Multidisciplinary Digital Publishing Institute (MDPI). https://doi.org/10.3390/jsan12040050
Othman, R. A., Darwish, S. M., & Abd El-Moghith, I. A. (2023). A Multi-Objective Crowding Optimization Solution for Efficient Sensing as a Service in Virtualized Wireless Sensor Networks. Mathematics, 11(5). https://doi.org/10.3390/math11051128
Pino, T., Choudhury, S., & Al-Turjman, F. (2018). Dominating Set Algorithms for Wireless Sensor Networks Survivability. IEEE Access, 6, 17527–17532. https://doi.org/10.1109/ACCESS.2018.2819083
Priyadarshini, R. R., & Sivakumar, N. (2021). Cluster head selection based on Minimum Connected Dominating Set and Bi-Partite inspired methodology for energy conservation in WSNs. Journal of King Saud University - Computer and Information Sciences, 33(9), 1132–1144. https://doi.org/10.1016/j.jksuci.2018.08.009
Raczek, J. (2022). Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks. Electronics (Switzerland), 11(3). https://doi.org/10.3390/electronics11030300
Sivakumar, N. R., Nagarajan, S. M., Devarajan, G. G., Pullagura, L., & Mahapatra, R. P. (2023). Enhancing network lifespan in wireless sensor networks using deep learning based Graph Neural Network. Physical Communication, 59. https://doi.org/10.1016/j.phycom.2023.102076
Sun, X., Yang, Y., & Ma, M. (2019). Minimum connected dominating set algorithms for ad hoc sensor networks. Sensors (Switzerland), 19(8). https://doi.org/10.3390/s19081919
Tang, Q., Yang, K., Li, P., Zhang, J., Luo, Y., & Xiong, B. (2012). An energy efficient MCDS construction algorithm for wireless sensor networks. Eurasip Journal on Wireless Communications and Networking, 2012. https://doi.org/10.1186/1687-1499-2012-83
Wieland, B., & Godbole, A. P. (2001). On the domination number of a random graph. Electronic Journal of Combinatorics, 8(1 R), 1–13. https://doi.org/10.37236/1581
Wong, R., Chang, W. L., Chung, W. Y., & Vasilakos, A. V. (2023). Biomolecular and quantum algorithms for the dominating set problem in arbitrary networks. Scientific Reports, 13(1). https://doi.org/10.1038/s41598-023-30600-4
Xiong, N., Huang, X., Cheng, H., & Wan, Z. (2013). Energy-efficient algorithm for broadcasting in ad hoc wireless sensor networks. Sensors (Switzerland), 13(4), 4922–4946. https://doi.org/10.3390/s130404922
Yang, Z., Shi, M., & Wang, W. (2021). Greedy approximation for the minimum connected dominating set with labeling. Optimization Letters, 15(2), 685–700. https://doi.org/10.1007/s11590-020-01628-6
Zhao, D., Xiao, G., Wang, Z., Wang, L., & Xu, L. (2021). Minimum Dominating Set of Multiplex Networks: Definition, Application, and Identification. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(12), 7823–7837. https://doi.org/10.1109/TSMC.2020.2987163
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Athraa Talib Breesam, Hussein Jameel Mutashar, Mustafa Adil Hussein, AlSeddiq Oday
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
License and Copyright Agreement
In submitting the manuscript to the journal, the authors certify that:
- They are authorized by their co-authors to enter into these arrangements.
- The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read Journal of Honai Math Posting Your Article Policy at http://journalfkipunipa.org/index.php/jhm/about
- That it is not under consideration for publication elsewhere,
- That its publication has been approved by all the author(s) and by the responsible authorities – tacitly or explicitly – of the institutes where the work has been carried out.
- They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
- They agree to the following license and copyright agreement.
Copyright
Authors who publish with Journal of Honai Math agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-NC-SA 4.0) that allows others to share the work with an acknowledgment 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 acknowledgment 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) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
