Abstract

In this thesis, I study relay placement in energy-constrained wireless sensor networks. The goal is to optimise balanced data gathering, where the utility function is a weighted sum of the minimum and average amounts of data collected from each sensor node. I define a number of classes of simplified relay placement problems, including a planar problem with a simple cost model for radio communication. The computational complexity of these classes is studied, and all classes are proved NP-hard; in some cases even finding approximate solutions is NP-hard. I also present algorithms for finding k-optimal solutions to the relay placement problem. These algorithms have been implemented, and their performance has been studied empirically; the implementation is freely available.

Keywords

wireless sensor networks · relay placement · balanced data gathering · energy constraints

Tiivistelmä

Tutkin tässä työssä linkkisolmujen sijoittelua energiarajoitteisissa, langattomissa anturiverkoissa. Tavoitteena on optimoida tasapainotettua datankeruuta, jossa hyötyfunktio on painotettu summa anturisolmuista kerättyjen datamäärien minimistä ja keskiarvosta. Määrittelen useita linkkisijoitteluongelmien luokkia, näiden joukossa on muunmuassa ongelmaluokka, jossa linkit sijoitetaan tasoon ja radiokommunikaatiokustannukset lasketaan yksinkertaisen mallin perusteella. Tutkin näiden luokkien laskennallista vaativuutta, ja osoitan kaikki luokat NP-koviksi; joissain tapauksissa jopa approksimatiivinen ratkaiseminen on NP-kova ongelma. Esitän myös algoritmeja linkkisijoittelun k-optimaaliseen ratkaisemiseen. Nämä algoritmit on toteutettu, ja niiden suorituskykyä on tarkasteltu kokeellisesti; toteutus on vapaasti saatavilla.

Avainsanat

langattomat anturiverkot · linkkisolmujen sijoittelu · tasapainotettu datankeruu · energia

Publication

Department of Computer Science, Series of Publications C, report C-2005-64, University of Helsinki, Department of Computer Science, Helsinki, Finland