Effective coverage in sensor networks: Binary integer programming formulations and heuristics

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

2006 IEEE International Conference on Communications, ICC 2006, İstanbul, Türkiye, 11 - 15 Temmuz 2006, cilt.9, ss.4014-4019, (Tam Metin Bildiri) identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 9
  • Doi Numarası: 10.1109/icc.2006.255709
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.4014-4019
  • Anahtar Kelimeler: Ad hoc wireless sensor networks, Binary integer programming, Detection probability, Heuristics, Obstacles, Sensor field coverage
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

Coverage is a fundamental task in sensor networks. We present two binary integer programming models for the effective sensor placement on a grid-structured sensor field when there are more than one type of available sensors with varying sensing quality and price. The first model assumes perfect sensor detection. The second one is more realistic and gives an optimal placement strategy for probabilistic sensing. Both models suffer from the intractability of the binary integer programming formulations. We therefore suggest greedy and Lagrangean heuristics, which are both accurate and efficient. Computational results are also provided. © 2006 IEEE.