Efficient integer programming formulations for optimum sink location and routing in wireless sensor networks

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

2008 23rd International Symposium on Computer and Information Sciences, ISCIS 2008, İstanbul, Türkiye, 27 - 29 Ekim 2008, (Tam Metin Bildiri) identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/iscis.2008.4717889
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Anahtar Kelimeler: Mixed integer linear programming, Routing, Sink location, Wireless sensor networks
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

In this work we consider routing and sink location problems in sensor networks and propose two new mixed integer programming formulations to determine optimal sink locations and data flow routes. The models basically differ in the formulations of their objective functions. We assume that the sensor field consists of a finite set of points, and sensors, which are located on a subset, cover the points of the field completely. Experimental results indicate that these new formulations are very efficient and optimal solutions can be computed easily even for large networks. We also propose Lagrangean relaxation methods to solve the formulations approximately. © 2008 IEEE.