Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks |
| |
| Affiliation: | 1. Department of Industrial Engineering, Bo?aziçi University, Bebek, ?stanbul 34342, Turkey;2. Department of Computer Engineering, Bo?aziçi University, Bebek, ?stanbul 34342, Turkey;1. Institute of Informatics and Telematics (IIT), Italian National Research Council (CNR), Via G. Moruzzi 1, Pisa, Italy;2. Converging Networks Laboratory, VTT Technical Research Centre of Finland, Kaitoväylä 1, 90590 Oulu, Finland;1. Federal Institute of Education, Science and Technology from Rio Grande do Sul, Farroupilha, RS, Brazil;2. Federal University of Santa Maria, Santa Maria, RS, Brazil;1. School of Mathematics and Statistics, University of Sheffield, Sheffield S3 7RH, UK;2. School of Biosciences, University of Nottingham, Sutton Bonington Campus, Loughborough LE12 5RD, UK;3. Laboratory for Fundamental and Applied Research in Chemical Ecology, University of Neuchtel, Neuchtel 2000, Switzerland |
| |
| Abstract: | Coverage is a fundamental task in sensor networks. We consider the minimum cost point coverage problem and formulate a binary integer linear programming model for effective sensor placement on a grid-structured sensor field when there are multiple types of sensors with varying sensing quality and price. The formulation is general and can be adapted to handle situations where sensing is perfect, imperfect or uncertain, and the coverage requirements are differentiated. Unfortunately, the new model suffers from the intractability of the binary integer programming formulations. We therefore suggest approximation algorithms and heuristics. Computational results indicate that the heuristic based on Lagrangean relaxation outperforms the others in terms of solution quality. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
