Graph theory tools for battery level management in sensor networks

Abstract

In this paper, we deal with the link between graph theory and sensor networks. Graph theory provides a powerful framework for modeling and analyzing complex networks, while sensor networks offer a distributed system of interconnected devices that collect and transmit data. The use of a well-established theoretical framework to this application has led to sig\-ni\-fi\-cant advancements in understanding the behavior, optimization and management 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. Thus, we aim to develop an algorithmic method that allows the identification of those sensors with low battery 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 algorithmic method starts considering the coordinates of every sensor and its battery level. After that, a weighted matrix is constructed based on come criteria such as the euclidean distance or the communication cost between each pair of sensors. Next, we have constructed the Voronoi diagram in order to analyze the influence area of every sensor. Then, we have considered the Delaunay graph associated to the previous diagram where the weight of the edges is given by the weighted matrix obtained before. After the previous steps, we have implemented several routines. The first one is devoted to locating the sensors with low battery level. The second one obtains the shortest path from one of those vertices to another vertex with a non-low battery level in order to avoid losing data. The third one applies the edge contraction operation deleting the vertices of sensors with low battery level. The last one computes the minimum spanning tree in order to collect the data from all the sensors of the network.

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.