Heuristics for Mixed Strength Sensor Location Problems

Rex Kincaid, Robin Givens

OAI: oai:igi-global.com:250248 • DOI: 10.4018/IJORIS.2020040104

Location-detection problems are pervasive. Examples include the detection of faults in microprocessors, the identification of contaminants in ventilation systems, and the detection of illegal logging in rain forests. In each of these applications a network provides a convenient modelling paradigm. Sensors are placed at particular node locations that, by design, uniquely detect and locate issues in the network. Open locating-dominating (OLD) sets constrain a sensor's effectiveness by assuming that it is unable to detect problems originating from the sensor location. Sensor failures may be caused by extreme environmental conditions or by the act of a nefarious individual. Determining the minimum size OLD set in a network is computationally intractable, but can be modelled as an integer linear program. The focus of this work is the development and evaluation of heuristics for the minimum OLD set problem when sensors of varying strengths are allowed. Computational experience and solution quality are reported for geometric graphs of up to 150 nodes.

Business Process Management Business and Management Business Information Systems