Optimizing Sensor Configurations for Ground-level and Aerial Intrusion Detection by Applying the Minimum Vertex Cover Problem

Overview

Improving ground-level and aerial intruder detection is a growing concern in the advent of threats such as drones for which current detection methods are inadequate. This research adopted a novel approach to detection via implementation of optimized motion sensor configurations generated through an original application of the minimum vertex cover problem to graphs modeling strategically devised gridding patterns superimposed on 2D and 3D spaces. The theoretical phase pursued the generalized forms and cardinalities of minimum vertex covers of devised gridding patterns applied to spaces of any dimensions. For 2D spaces, these findings translate to an explicit statement of B(G) for the G1, G3, and G4 gridding patterns, which are subgraphs of the m,n King graph. It is shown that B(G1)=mn-[(m+1)/2][(n+1)/2]; B(G3)=3kl-2(k+l)+4 for m=2k, n=2l; B(G3)=3kl-2k-l+4 for m=2k+1, n=2l; B(G3)=3kl-k-l+4 for m=2k+1, n=2l+1. Additionally it is shown that B(G4)=m[n/2] for even m and for odd m and n, m>n. For 3D spaces of m,m,m dimensions subject to the devised H1 gridding pattern, these findings translate to B(H1)=4n³ for m=2n and B(H1)=4n³+3n² for m=2n+1. In practice, the derived generalizations can be used to formulaically generate sensor configurations offering different levels of route reconstruction specificity. Performed ground-level and aerial intrusion simulations quantitatively demonstrate that the applied gridding patterns yield high route reconstruction specificity. The theoretical methods are adaptable to irregular geometries and independent of the type of motion sensor employed. This novel, large-scale use of motion sensors, which can be adapted to infrared, laser, and acoustic sensors, among others, is potentially an alternative to existing, unreliable detection methods.

Competition history

• ISEF 2015 Category not listed · Entry MATH033I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.