TY - JOUR

T1 - Constructing minimum-interference networks

AU - Benkert, M.

AU - Gudmundsson, J.

AU - Haverkort, H.J.

AU - Wolff, A.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1016/j.comgeo.2007.06.004

DO - 10.1016/j.comgeo.2007.06.004

M3 - Article

VL - 40

SP - 179

EP - 194

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 3

ER -