@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^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",

}