Welcome to the InfoSci Platform
Heuristics for Mixed Strength Sensor Location Problems

Heuristics for Mixed Strength Sensor Location Problems

Rex K. Kincaid, Robin M. Givens
Copyright: © 2020 |Volume: 11 |Issue: 2 |Pages: 13
ISSN: 1947-9328|EISSN: 1947-9336|EISBN13: 9781799806547|DOI: 10.4018/IJORIS.2020040104
Cite Article Cite Article

MLA

Kincaid, Rex K., and Robin M. Givens. "Heuristics for Mixed Strength Sensor Location Problems." IJORIS vol.11, no.2 2020: pp.53-65. http://doi.org/10.4018/IJORIS.2020040104

APA

Kincaid, R. K. & Givens, R. M. (2020). Heuristics for Mixed Strength Sensor Location Problems. International Journal of Operations Research and Information Systems (IJORIS), 11(2), 53-65. http://doi.org/10.4018/IJORIS.2020040104

Chicago

Kincaid, Rex K., and Robin M. Givens. "Heuristics for Mixed Strength Sensor Location Problems," International Journal of Operations Research and Information Systems (IJORIS) 11, no.2: 53-65. http://doi.org/10.4018/IJORIS.2020040104

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

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.