2009 · 16 citations · 14 references
Natural SciencesMathematicsMine DesignMine PlanningOptimizationApproximation AlgorithmsCombinatorial OptimizationNetwork OptimizationApproximation ComplexityComplexityGreedy ApproximationGreedy HeuristicsMine Optimization
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.
14
Wireless sensor networks: a survey
Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam · Computer Networks · 2002 · 17.4K citations
Integrated coverage and connectivity configuration in wireless sensor networks
Xiaorui Wang, Guoliang Xing, Yuanfang Zhang et al. · 2003 · 1.3K citations · Full text
Deploying wireless sensors to achieve both coverage and connectivity
Xiaole Bai, Santosh Kumar, Dong Xuan et al. · 2006 · 582 citations
Differentiated surveillance for sensor networks
Ting Yan, Tian He, John A. Stankovic · 2003 · 508 citations