### Samenvatting

A fundamental problem in wireless sensor networks is to connect a given set of sensors while minimizing the \emph{receiver interference}. This is modeled as follows: each sensor node corresponds to a point in $\mathbb{R}^d$ and each \emph{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-2 | Engels |
---|---|

Uitgeverij | s.n. |

Aantal pagina's | 15 |

Status | Gepubliceerd - 2014 |

### Publicatie series

Naam | arXiv |
---|---|

Volume | 1406.7753 [cs.CG] |

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

## Citeer dit

Brise, Y., Buchin, K., Eversmann, D., Hoffmann, M., & Mulzer, W. (2014).

*Interference minimization in asymmetric sensor networks*. (arXiv; Vol. 1406.7753 [cs.CG]). s.n.