Skip to main content

Locating sinks in wireless sensor networks

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2009
Authors/Contributors
Abstract
We study the problem of positioning sinks, or data collection stops, in wireless sensor networks. To reduce the path lengths from sensors to sinks we introduce multiple sinks. We find a group of sinks where every sensor is within distance k of at least p sinks. We model the wireless sensor network as a unit disk graph G=(V,E) and find a distance-k total p-dominating set S⊆V for fixed positive integers k and p. If we place sinks at the positions of the vertices of S, then every sensor is within distance k of p sinks. To find a distance-k total p-dominating set of minimum size is NP-hard. We give 2(2k+1)2 and p·ln∆k approximation algorithms, where ∆k is the largest cardinality k-neighborhood. We propose several greedy based heuristics and conduct several experiments to compare the performance of our algorithms. We give a statistical performance analysis for our experimental results.
Document
Copyright statement
Copyright is held by the author.
Scholarly level
Language
English
Member of collection
Download file Size
ETD4695.pdf 760 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 1