Interference minimization in asymmetric sensor networks

Y. Brise, K. Buchin, D. Eversmann, M. Hoffmann, W. Mulzer

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

A fundamental problem in wireless sensor networks is to connect a given set of sensors while minimizing the receiver interference. This is modeled as follows: each sensor node corresponds to a point in R^d and each transmission range corresponds to a ball. The receiver interference of a sensor node is defined as the number of transmission ranges it lies in. Our goal is to choose transmission radii that minimize the maximum interference while maintaining a strongly connected asymmetric communication graph. For the two-dimensional case, we show that it is NP-complete to decide whether one can achieve a receiver interference of at most 5 . In the one-dimensional case, we prove that there are optimal solutions with nontrivial structural properties. These properties can be exploited to obtain an exact algorithm that runs in quasi-polynomial time. This generalizes a result by Tan et al. to the asymmetric case.
Originele taal-2Engels
TitelAlgorithms for Sensor Systems (10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014, Wroclaw, Poland, September 12, 2014, Revised Selected Papers)
RedacteurenJ. Gao, A. Efrat, S.P. Fekete, Y. Zhang
UitgeverijSpringer
Pagina's136-151
ISBN van geprinte versie978-3-662-46017-7
DOI's
StatusGepubliceerd - 2015
Evenementconference; 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics; 2014-09-12; 2014-09-12 -
Duur: 12 sep 201412 sep 2014

Publicatie series

NaamLecture Notes in Computer Science
Volume8847
ISSN van geprinte versie0302-9743

Congres

Congresconference; 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics; 2014-09-12; 2014-09-12
Periode12/09/1412/09/14
Ander10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics

Vingerafdruk Duik in de onderzoeksthema's van 'Interference minimization in asymmetric sensor networks'. Samen vormen ze een unieke vingerafdruk.

Citeer dit