์๋ฌธ์ ๋ณด
์ด๋ก
์์ด
When several low power sensors are randomly deployed in a field for monitoring targets located at fixed positions, managing the network lifetime is useful as long as replacing battery of dead sensors is not often feasible. The most commonly investigated mechanism for coverage preserving while maximizing the network lifetime is to design efficient sleep scheduling protocols, so that sensors can alternate their state between being active or not. Maximizing lifetime of a sensor network while satisfying a predefined coverage requirement is an optimization problem, which most of times cannot be optimally solved in polynomial time. In this paper, we address this problem by using set cover approach. We propose a greedy algorithm that distributes sensors among disjoints and non-disjoints set covers with the requirement that each set cover satisfies full targets coverage. The algorithm is an improvement of the classical greedy set cover algorithm, and its approximation ratio is verified to be not worse than ๐๐๐โก(๐). Simulation results show good performance over some other solutions found in the literature. We provide also a comparison of several greedy techniques found in the literature addressed in the context of different design choices linked to the target coverage problem.
๋ชฉ์ฐจ
1. Introduction
2. Target Coverage Problem
2.1. Assumptions
2.2. Problem Definition
2.3. Maximum Set Cover Problem
2.4. Non-disjoint Sets Constraint
3. Sensors Selection Mechanism
3.1. Theoretical Bound
3.2. Sensors Cost Evaluation
4. Using Greedy Algorithms
4.1. Greedy Minimum Set Cover
4.2. Approximation Ratio of Greedy-MSSC
4.3. Greedy Maximum Set Cover
4.4. Complexity Analysis
5. Simulation Results
5.1. Experiment 1
5.2. Experiment 2
5.3. Experiment 3
5.4. Experiment 4
6. Related Works
6.1. Sensors Placement Optimization Problem
6.2. Sleep Scheduling Mechanisms
6.3. Connected Target Coverage
6.4. Target Coverage under QoS Constraint
7. Conclusion
Acknowledgement
References