Battery level management is crucial for the reliable operation of sensor networks. In this paper, we present a novel framework that leverages graph theory and computational geometry to enhance battery management, optimize communication, and maintain connectivity. Our approach builds weighted Delaunay Graphs as combinatorial models for sensor networks and investigates theoretical aspects of their hamiltonicity. We introduce six algorithmic methods addressing two main objectives. The first set focuses on battery management by identifying low-battery sensors, computing minimum spanning trees and shortest paths and performing edge contraction to simplify network topology while preserving connectivity. The second set examines the hamiltonicity of Delaunay Graphs using graph labeling and combinatorial techniques to analyze the existence of Hamiltonian paths. Our methodology integrates key graph procedures such as minimum spanning trees, shortest path algorithms, edge contraction, and graph labeling with computational geometry tools like Voronoi diagrams and Delaunay triangulation. This combination allows for an accurate modeling of spatial relationships within the network and dynamic adaptation to battery constraints. A case study on monitoring a sugar cane field demonstrates the practical application of our methods. The computational study reveals the efficiency and robustness of the proposed algorithms in optimizing battery usage and improving network performance in real-world scenarios. In conclusion, our work not only addresses critical battery management challenges in sensor networks but also deepens the understanding of the interplay between graph theory and network optimization. This integrated approach paves the way for further research in both theoretical and applied domains, offering promising solutions for enhancing the sustainability and reliability of sensor networks
| Published in | Applied and Computational Mathematics (Volume 14, Issue 1) |
| DOI | 10.11648/j.acm.20251401.15 |
| Page(s) | 64-77 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2025. Published by Science Publishing Group |
Weighted Graph, Voronoi Diagram, Delaunay Graph, Sensor Network, Algorithm
| [1] | Árego, B. M., Arkin, E. M., Fernández-Merchant, S., Hurtado, F., Kano, M., Mitchell, J. S. B. and Urrutia, J. Matching points with squares. Discrete & Computational Geometry, 41(1): 77-95, 2009. |
| [2] | Akyildiz, I. F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002). A survey on sensor networks. IEEE Communications Magazine, 40(8), 102–114. |
| [3] | Ameen, A., Ali A., Khattab, M. and Aliesawi, S. (2020). Employing Graph Theory in Enhancing Power Energy of Wireless Sensor Networks. Journal of Information Science and Engineering 36, 323-335. |
| [4] | Franz Aurenhammer, F., Klein, R. and Lee, D. (2013). Voronoi Diagrams And Delaunay Triangulations. World Scientific Publishing Company. |
| [5] | Bollobás, B. (1998). Modern graph theory. Springer. |
| [6] | Friedman, H., Robertson, N., Seymour, P. (1987). The metamathematics of the graph minor theorem. In Simpson, S. (ed.), Logic and Combinatorics, Contemporary Mathematics 65, American Mathematical Society, 229–261. |
| [7] | Harary, F. (1994). Graph Theory. Reading, MA: Addison-Wesley. |
| [8] | Manoharan, J.S. (2023). A Novel Load Balancing Aware Graph Theory Based Node Deployment in Wireless Sensor Networks. Wireless Pers Commun 128, 1171–1192. |
| [9] | Pemmaraju, S. and Skiena, S. (2003). Cycles, Stars, and Wheels. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England. Cambridge University Press, 248– 249. |
| [10] | Rao, J. and Fapojuwo, A. O. A battery aware distributed clustering and routing protocol for Wireless Sensor Networks. In 2012 IEEE Wireless Communications and Networking Conference (WCNC), Paris, France, 1538- 1543, |
| [11] | Rhim, H., Tamine, K., Abassi, R. et al. (2018). A multi-hop graph-based approach for an energy-efficient routing protocol in wireless sensor networks. Hum. Cent. Comput. Inf. Sci. 8, 30. |
| [12] | Robertson, N., Seymour, P. (1983). Graph Minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B, 35 (1), 39–61, |
| [13] | Robertson, N., Seymour, P. (2004). Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92 (2), 325–357, |
| [14] | Shao, C. Wireless sensor network target localization algorithm based on two- and three-dimensional Delaunay partitions, (2021). Journal of Sensors, 4047684. |
| [15] |
Wagner, K. (1937), Über eine Eigenschaft der ebenen Komplexe. Math. Ann., 114, 570–590,
https://doi.org/10.1007/BF01594196 , S2CID 123534907 |
| [16] | Wang, Y., and Li, X.-Y. (2007). Efficient Delaunay- based localized routing for wireless sensor networks: Research articles. Int. J. Commun. Syst. 20, 767–789. |
| [17] | Watfa, M. K., Mirza, O., Kawtharani, J. (2009). BARC: A Battery Aware Reliable Clustering algorithm for sensor networks. Journal of Network and Computer Applications, 32(6), 1183–1193. |
APA Style
Millán, M., Ceballos, M., Orihuela, L. (2025). Graph-based Algorithms for Battery Management in Sensor Networks: Theoretical Insights and Practical Applications. Applied and Computational Mathematics, 14(1), 64-77. https://doi.org/10.11648/j.acm.20251401.15
ACS Style
Millán, M.; Ceballos, M.; Orihuela, L. Graph-based Algorithms for Battery Management in Sensor Networks: Theoretical Insights and Practical Applications. Appl. Comput. Math. 2025, 14(1), 64-77. doi: 10.11648/j.acm.20251401.15
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.acm.20251401.15,
author = {María Millán and Manuel Ceballos and Luis Orihuela},
title = {Graph-based Algorithms for Battery Management in Sensor Networks: Theoretical Insights and Practical Applications},
journal = {Applied and Computational Mathematics},
volume = {14},
number = {1},
pages = {64-77},
doi = {10.11648/j.acm.20251401.15},
url = {https://doi.org/10.11648/j.acm.20251401.15},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20251401.15},
abstract = {Battery level management is crucial for the reliable operation of sensor networks. In this paper, we present a novel framework that leverages graph theory and computational geometry to enhance battery management, optimize communication, and maintain connectivity. Our approach builds weighted Delaunay Graphs as combinatorial models for sensor networks and investigates theoretical aspects of their hamiltonicity. We introduce six algorithmic methods addressing two main objectives. The first set focuses on battery management by identifying low-battery sensors, computing minimum spanning trees and shortest paths and performing edge contraction to simplify network topology while preserving connectivity. The second set examines the hamiltonicity of Delaunay Graphs using graph labeling and combinatorial techniques to analyze the existence of Hamiltonian paths. Our methodology integrates key graph procedures such as minimum spanning trees, shortest path algorithms, edge contraction, and graph labeling with computational geometry tools like Voronoi diagrams and Delaunay triangulation. This combination allows for an accurate modeling of spatial relationships within the network and dynamic adaptation to battery constraints. A case study on monitoring a sugar cane field demonstrates the practical application of our methods. The computational study reveals the efficiency and robustness of the proposed algorithms in optimizing battery usage and improving network performance in real-world scenarios. In conclusion, our work not only addresses critical battery management challenges in sensor networks but also deepens the understanding of the interplay between graph theory and network optimization. This integrated approach paves the way for further research in both theoretical and applied domains, offering promising solutions for enhancing the sustainability and reliability of sensor networks},
year = {2025}
}
TY - JOUR T1 - Graph-based Algorithms for Battery Management in Sensor Networks: Theoretical Insights and Practical Applications AU - María Millán AU - Manuel Ceballos AU - Luis Orihuela Y1 - 2025/02/17 PY - 2025 N1 - https://doi.org/10.11648/j.acm.20251401.15 DO - 10.11648/j.acm.20251401.15 T2 - Applied and Computational Mathematics JF - Applied and Computational Mathematics JO - Applied and Computational Mathematics SP - 64 EP - 77 PB - Science Publishing Group SN - 2328-5613 UR - https://doi.org/10.11648/j.acm.20251401.15 AB - Battery level management is crucial for the reliable operation of sensor networks. In this paper, we present a novel framework that leverages graph theory and computational geometry to enhance battery management, optimize communication, and maintain connectivity. Our approach builds weighted Delaunay Graphs as combinatorial models for sensor networks and investigates theoretical aspects of their hamiltonicity. We introduce six algorithmic methods addressing two main objectives. The first set focuses on battery management by identifying low-battery sensors, computing minimum spanning trees and shortest paths and performing edge contraction to simplify network topology while preserving connectivity. The second set examines the hamiltonicity of Delaunay Graphs using graph labeling and combinatorial techniques to analyze the existence of Hamiltonian paths. Our methodology integrates key graph procedures such as minimum spanning trees, shortest path algorithms, edge contraction, and graph labeling with computational geometry tools like Voronoi diagrams and Delaunay triangulation. This combination allows for an accurate modeling of spatial relationships within the network and dynamic adaptation to battery constraints. A case study on monitoring a sugar cane field demonstrates the practical application of our methods. The computational study reveals the efficiency and robustness of the proposed algorithms in optimizing battery usage and improving network performance in real-world scenarios. In conclusion, our work not only addresses critical battery management challenges in sensor networks but also deepens the understanding of the interplay between graph theory and network optimization. This integrated approach paves the way for further research in both theoretical and applied domains, offering promising solutions for enhancing the sustainability and reliability of sensor networks VL - 14 IS - 1 ER -
Department of Engineering, Faculty of Engineering, Universidad Loyola Andalucía, Sevilla, Spain
Department of Engineering, Faculty of Engineering, Universidad Loyola Andalucía, Sevilla, Spain
Department of Electronic Engineering, Computer Systems, and Automation, Faculty of Engineering, Universidad de Huelva, Huelva, Spain
Information