Heuristics for Mixed Strength Sensor Location Problems

Heuristics for Mixed Strength Sensor Location Problems

Rex K. Kincaid (College of William & Mary, USA) and Robin M. Givens (Randolph Macon College, USA)
DOI: 10.4018/IJORIS.2020040104

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.
Article Preview
Top

Introduction

The merger of the locating and dominating requirements for a set of nodes on a network has led to a wealth of research activity in the last 20 years. The introduction of locating sets is generally attributed to Hakimi (1964), although Jordan (1869) and Hua (1962) both had earlier contributions. The origination of dominating sets is usually traced to Ore (1962). Combining the ideas of location and domination have led to a number of distinct problems including, locating-dominating sets (Colbourn, Slater, & Stewart, 1987; Slater 1987), identifying codes (Cohen, Honkala, Lobstein, & Zémor, 2001), open locating-dominating sets (Seo & Slater, 2010; Seo & Slater, 2011) and metric locating dominating sets (Henning & Oellermann, 2004).

The detection and location of anomalies in a network is of central concern in a wide variety of application arenas. In sensor applications, sensors are placed at particular node locations designed to detect and locate anomalies that arise in the network. One way to lower initial costs and long-term maintenance costs for a collection of sensors, is to minimize the number of sensors needed to appropriately monitor the network. Unfortunately, these location–domination problems are, in general, computationally intractable (Givens, Kincaid, Mao, & Yu, 2017; Sweigart, 2019). A finite, connected, simple graph G(V, E) with node set V and edge set E provides a convenient model of a network or physical space. Nodes represent locations or regions and edges represent connections or communication ranges between those locations. The edges are assumed to be of unit length unless otherwise noted.

The focus of this paper is open locating dominating (OLD) sets that allow non-uniform weights (sensor strengths). However, it is helpful to consider three related problems to understand the difference between OLD sets and other location domination problems. Let an open neighborhood of a node IJORIS.2020040104.m01, IJORIS.2020040104.m02, be the set of nodes adjacent to node v, excluding v. A closed neighborhood of a node v is denoted by IJORIS.2020040104.m03 and is the union of IJORIS.2020040104.m04 with v. Let IJORIS.2020040104.m05 denote a subset of nodes in a graph IJORIS.2020040104.m06.

In (Seo & Slater, 2011) a set S is a Locating-Dominating (LD) set if every node not in S has at least one neighbor in S and there is no distinct pair of nodes not in S with the same set of neighbors in S. Hence, S is a LD set if both of the following conditions are met.

  • LD 1 For all IJORIS.2020040104.m07, IJORIS.2020040104.m08.

  • LD 2 For all IJORIS.2020040104.m09 such that IJORIS.2020040104.m10, IJORIS.2020040104.m11.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing