A wireless ad-hoc network can be represented as a
graph in which the nodes represent wireless devices,
and the links represent pairs of nodes that
communicate directly by means of radio signals. The
interference caused by a link between two
nodes~$u$ and~$v$ can be defined as the number of
other nodes that may be disturbed by the signals
exchanged by $u$ and~$v$. Given the position of the
nodes in the plane, links are to be chosen such that
the maximum interference caused by any link is
limited and the network fulfills desirable
properties such as connectivity, bounded dilation or
bounded link diameter. We give efficient algorithms
to find the links in two models. In the first model,
the signal sent by~$u$ to~$v$ reaches exactly the
nodes that are not farther from~$u$ than~$v$ is. In
the second model, we assume that the boundary of a
signal's reach is not known precisely and that our
algorithms should therefore be based on acceptable
estimations. The latter model yields faster
algorithms.
%0 Journal Article
%1 bghw-cimn-08
%A Benkert, Marc
%A Gudmundsson, Joachim
%A Haverkort, Herman
%A Wolff, Alexander
%D 2008
%J Computational Geometry: Theory and Applications
%K connected geometric_spanner interference link_diameter myown wireless_ad-hoc_networks
%N 3
%P 179--194
%R 10.1016/j.comgeo.2007.06.004
%T Constructing Interference-Minimal Networks
%V 40
%X A wireless ad-hoc network can be represented as a
graph in which the nodes represent wireless devices,
and the links represent pairs of nodes that
communicate directly by means of radio signals. The
interference caused by a link between two
nodes~$u$ and~$v$ can be defined as the number of
other nodes that may be disturbed by the signals
exchanged by $u$ and~$v$. Given the position of the
nodes in the plane, links are to be chosen such that
the maximum interference caused by any link is
limited and the network fulfills desirable
properties such as connectivity, bounded dilation or
bounded link diameter. We give efficient algorithms
to find the links in two models. In the first model,
the signal sent by~$u$ to~$v$ reaches exactly the
nodes that are not farther from~$u$ than~$v$ is. In
the second model, we assume that the boundary of a
signal's reach is not known precisely and that our
algorithms should therefore be based on acceptable
estimations. The latter model yields faster
algorithms.
@article{bghw-cimn-08,
abstract = {A wireless ad-hoc network can be represented as a
graph in which the nodes represent wireless devices,
and the links represent pairs of nodes that
communicate directly by means of radio signals. The
\emph{interference} caused by a link between two
nodes~$u$ and~$v$ can be defined as the number of
other nodes that may be disturbed by the signals
exchanged by $u$ and~$v$. Given the position of the
nodes in the plane, links are to be chosen such that
the maximum interference caused by any link is
limited and the network fulfills desirable
properties such as connectivity, bounded dilation or
bounded link diameter. We give efficient algorithms
to find the links in two models. In the first model,
the signal sent by~$u$ to~$v$ reaches exactly the
nodes that are not farther from~$u$ than~$v$ is. In
the second model, we assume that the boundary of a
signal's reach is not known precisely and that our
algorithms should therefore be based on acceptable
estimations. The latter model yields faster
algorithms.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Benkert, Marc and Gudmundsson, Joachim and Haverkort, Herman and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/20445cfac31f97f1a07685ffd488cf05f/awolff},
doi = {10.1016/j.comgeo.2007.06.004},
interhash = {5b74916acfb5d202922c0a96ac16204f},
intrahash = {0445cfac31f97f1a07685ffd488cf05f},
journal = {Computational Geometry: Theory and Applications},
keywords = {connected geometric_spanner interference link_diameter myown wireless_ad-hoc_networks},
number = 3,
pages = {179--194},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/bghw-cimn-08.pdf},
succeeds = {bghw-cimn-06},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Constructing Interference-Minimal Networks},
volume = 40,
year = 2008
}