Relay placement in sensor networks

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.

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.