@inproceedings{7847ab700a524d0685eab26f43dd248c,
title = "Interference minimization in asymmetric sensor networks",
abstract = "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\textasciicircum{}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.",
author = "Y. Brise and K. Buchin and D. Eversmann and M. Hoffmann and W. Mulzer",
year = "2015",
doi = "10.1007/978-3-662-46018-4\_9",
language = "English",
isbn = "978-3-662-46017-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "136--151",
editor = "J. Gao and A. Efrat and S.P. Fekete and Y. Zhang",
booktitle = "Algorithms 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)",
address = "Germany",
note = "conference; 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics; 2014-09-12; 2014-09-12 ; Conference date: 12-09-2014 Through 12-09-2014",
}