Tree Topologies and Node Covers for Efficient Communication in Wireless Sensor Networks

Locating positions of the sensors is a primary concern for WSNs as these are susceptible to multiple forms of attacks. The problem of detecting the position of placement of sensor nodes so that the entire communication area is covered is called the sensor deployment problem. This problem is equivalently the classical NP-complete optimization graph problem called the node cover. The node cover problem finds application across a range of WSN scenarios, including sensor deployment and the monitoring of communication links. In this paper, the node coverage and link coverage problems are solved in tree-based networks and the exact values of the node and edge covers for trees such as n-centipedes, paths, stars, spike trees and banana trees are determined. Furthermore, a use case of node cover within WSNs is presented in the context of disaster response and emergency management in earthquake early warning systems.