Login | Register

Multiple sink positioning in sensor networks


Multiple sink positioning in sensor networks

Mihandoust, Shahab (2008) Multiple sink positioning in sensor networks. Masters thesis, Concordia University.

[thumbnail of MR40948.pdf]
Text (application/pdf)
MR40948.pdf - Accepted Version


We study the problem of positioning multiple sinks, or data collection stops for a mobile sink, in a sensor network field. Given a sensor network represented by a unit disc graph G = ( V, E ), we say a set of points U (sink node locations) is an h -hop covering set for G if every node in G is at most h hops away from some point in U . Placing sink nodes at the points of a covering set guarantees that every sensor node has a short path to some sink node. This can increase network lifetime, reduce the occurrence of errors, and reduce latency. We also study variations of the problem where the sink locations are restricted to be at points of a regular lattice (lattice-based covering set), or at network nodes (graph-based covering set). We give the first polynomial time approximation scheme ( PTAS ) for the h -hop covering set problem, the h -hop lattice-based covering set problem, and the h-hop graph-based covering set problem. We give a new PTAS for the lattice-based disc cover problem, based on a new approach deriving from recent results on dominating sets in unit disc graphs. We show that this gives a (3 + f)-approximation algorithm for the disc cover problem, and gives the first distributed algorithm for this problem. We give a (5 + f)-approximation algorithm for the h -hop covering set problem in unit disc graphs, that does not require a geometric representation of the graph. Finally, we give a (3+f)-approximation algorithm for the h -hop covering set problem for unit disc graphs that runs in time quadratic in the number of nodes in the graph, for any constant f and h . In addition to showing how well a lattice-based approach for a disc cover problem approximates the optimal solution, we prove a geometric theorem that gives an exact relationship between the side of a triangular lattice and the number of lattice discs that are necessary and sufficient to cover an arbitrary disc on the plane.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Mihandoust, Shahab
Pagination:xi, 86 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Narayanan, Lata
Identification Number:LE 3 C66C67M 2008 M54
ID Code:975740
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:14
Last Modified:13 Jul 2020 20:08
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top