Graph theory applications: addressing battery challenges in sensor networks

Abstract

This paper deals with the link among graph theory and sensor networks. Graph theory offers a robust platform for representing and studying intricate networks, whereas sensor networks consist of interconnected devices that gather and share data in a distributed manner. Leveraging a well-established theoretical framework for this purpose has resulted in notable progress in comprehending the dynamics, enhancement, and administration of sensor networks.

The main goal of our paper is to take advantage of some graph-based tools to ease the battery level management in sensor networks and to solve some fault situations. Thus, we aim to develop an algorithmic method that allows the identification of those sensors with low battery level and, later, proceed with changes in the topology that avoid possible failures in the communication. In order to do so, we explore several graph procedures such as minimum spanning trees and shortest path algorithms. We have also used the edge contraction operation, graph coloring techniques and some computational geometry tools such as Voronoi diagrams and Delaunay triangulation.

Our algorithm initiates by assessing the coordinates and battery statuses of each sensor. Subsequently, we generate a weighted matrix based on various criteria such as Euclidean distance or communication expenses between sensor pairs. Following this, we construct the Voronoi diagram to delineate the influence region of each sensor. Then, we use the Delaunay graph corresponding to the Voronoi diagram, where edge weights are determined by the previously derived weighted matrix. Upon completing these preliminary steps, we implement several procedures. The first procedure aims to identify sensors with depleted battery levels. The second procedure determines the shortest path between such low-battery vertices and other vertices with sufficient power to prevent data loss. The third procedure involves the edge contraction operation, eliminating vertices associated with sensors having low battery levels. The fourth one computes the minimum spanning tree to efficiently retrieve data from all sensors within the network. Finally, the last procedure assumes that there have been a failure in several sensors throughout a period of time and it generates the different Delaunay graphs associated to the network during that period.

We believe that the tools and algorithms considered in this paper may be useful and helpful for understanding the link between graph theory and sensor networks. In addition, this link may provide new methods to deal with various challenges in network optimization, routing, clustering, localization and coverage. We would also like to point out the importance of further research in this field to unlock the full potential of graph-based approaches in sensor networks.