Distributed Colorings for Collision-free Routing in Sink-Centric Sensor Networks

When the environment does not allow direct access to disseminated data, a sensor network could be one of the most appropriate solutions to retrieve the map of interesting areas. Based on existing approaches, we start our study from the standard random deployment of a sensor network and then we consider a coarse-grain localization algorithm that associates sensors with coordinates related to a central node, called the sink. Once each sensor is associated with an estimated position, it starts to send data to the sink according to a designed schedule of communications that minimizes energy consumption and time by means of collisions avoidance. The outcome is a challenging combinatorial coloring problem for a specific graph class. We propose a schedule of communications based on distributed and fast coloring algorithms. The proposed solutions solve the underlying problems for the graphs of interest by means of an optimal, and in some cases near-optimal, number of colors. Finally, as the localization provides coarse-grain coordinates, different sensors might be associated with the same coordinates. Hence, in order to avoid that all such sensors perform the same actions (i.e., waste energy), a leader-election mechanism is considered.