Deterministic Greedy Algorithms for Optimal Sensor Placement

Abstract

A sensor is a device which can be sensitive to any physical stimulus, such as light, heat, or a particular motion, and responds with a respective impulse. A graph is an abstract representation for a set of objects of any kind where some object pairs are connected by links. The interconnected objects are called vertices or nodes. In this paper, one of the antiquated and classical examples of a Non-Deterministic Polynomial hard (NP-hard) optimization problem in computer science, the “Set Coverage Problem,” is discussed. Monitoring spatial constraints in real-world networks with huge data requires the best sensor placement for a given network. For any typical network, it has been proven that a greedy placement algorithm achieves a minimum of 63% optimal reduction in total variance. The focus in this paper is on sensor-optimization problem with the help of two approximation algorithms inherited from traditional greedy approach with supporting experimental results.