A novel approach to partial coverage in wireless sensor networks via the roman dominating set. Issue 2 (12th February 2022) - Ghaffari, Fatemeh; Bahrak, Behnam; Shariatpanahi, Seyed P.
Abstract: One major challenge in deploying wireless sensor networks (WSN) in real‐world applications is minimising the energy consumption by the sensors while maintaining the coverage of the monitored field. However, many applications do not need full coverage of the monitored area all the time, which can help us reduce the network's energy consumption. One approach to exploit this property is to set up a sleep/wake‐up schedule for each node such that no redundant nodes are active in an area of coverage simultaneously. This will allow the existence of monitoring holes in a controlled manner, which the authors call partial coverage . In this study, the partial coverage condition is imposed by constructing a Roman Dominating Set of awake nodes in the network. Roman domination is a method for colouring a graph's vertices with three labels (0, 1, 2), such that all the vertices with label 0 have an adjacent vertex with label 2, while the sum of the labels of nodes is minimised. Based on this formulation, a simple greedy algorithm is proposed to construct such a structure supported by three theorems. Furthermore, the performance of the authors' proposal in different scenarios is evaluated.