Earticle

초록

영어

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.

목차

Abstract
 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

키워드

저자

• Babacar Diop [ Department of Computer Science Faculty of Applied Sciences and Technology University Gaston Berger, BP. 234 Saint-Louis, Senegal ]
• Dame Diongue [ Department of Computer Science Faculty of Applied Sciences and Technology University Gaston Berger, BP. 234 Saint-Louis, Senegal ]
• Ousmane Thiaré [ Department of Computer Science Faculty of Applied Sciences and Technology University Gaston Berger, BP. 234 Saint-Louis, Senegal ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Control and Automation

• 간기

  월간

• pISSN

  2005-4297

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605