Minimizing the Cost of Mine Selection Via Sensor Networks

C. Liu, Guangming Cao

2009 · 16 citations · 14 references

Concepts

Abstract

In this paper, we study sensor enabled landmine networks by formulating a minimum-cost mine selection problem. The problem arises in a target defence scenario, where the objective is to destroy the intruding targets using the minimum-cost pre-deployed mines. Due to the problem complexity, we first transform it using a novel bucket-tub model, and then propose several approximation algorithms. Among them, it is shown that the layering algorithm can achieve an approximation ratio of alpha ldr f, where alpha ges 1 is the tunable relaxation factor and f is the maximum number of mines that a target is associated with, and that the greedy algorithm has an approximation ratio of Sigma <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> , where R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> is the coefficient in the related integer program. We also present a localized greedy algorithm which is shown to produce the same solution set as the global greedy algorithm. Theoretical analysis and extensive simulations demonstrate the effectiveness of the proposed algorithms.

References

14