A variable neighbourhood search heuristic for point coverage, sink location and data routing in wireless sensor networks

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

2009 2nd International Conference on Communication Theory, Reliability, and Quality of Service, CTRQ 2009, Colmar, Fransa, 20 - 25 Temmuz 2009, ss.81-86, (Tam Metin Bildiri) identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/ctrq.2009.33
  • Basıldığı Şehir: Colmar
  • Basıldığı Ülke: Fransa
  • Sayfa Sayıları: ss.81-86
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

In this work point coverage, sink location and data routing problems are considered in an integrated way and two new mixed integer programming formulations are proposed. Since these models are computationally difficult to solve, a hierarchical solution procedure is proposed. In the top level, best sensor locations are sought by variable neighbourhood search. Given the sensor locations, a simpler formulation can be obtained and a Lagrangean Heuristic is used to solve the sink location and data routing model efficiently. Experimental results indicate that the performance of hierarchical solution approach is very good. Index Terms-Mixed integer linear programming; routing; point coverage; sink location; wireless sensor networks. © 2009 IEEE.