Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks

ALTINEL İ. K., ARAS M. N., Güney E., ERSOY C.

Computer Networks, cilt.52, sa.12, ss.2419-2431, 2008 (SCI-Expanded, Scopus) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 52 Sayı: 12
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1016/j.comnet.2008.05.002
  • Dergi Adı: Computer Networks
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.2419-2431
  • Anahtar Kelimeler: Approximation algorithms, Coverage, Heuristics, Integer linear programing, Sensor networks
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

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. © 2008 Elsevier B.V. All rights reserved.