2011 | OriginalPaper | Chapter
Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius
Author : Matias Korman
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider a topology control problem in which we are given a set of
n
sensors in ℝ
d
and we would like to assign a communication radius to each of them. The radii assignment must generate a strongly connected network and have low receiver-based interference (defined as the largest in-degree of the network). We give an algorithm that generates a network with
O
(logΔ) interference, where Δ is the interference of a uniform-radius network. Since the radius of each sensor only depends on its neighbors, it can be computed in a distributed fashion. Moreover, this construction will never assign communication radius larger than
R
min
to a sensor, where
R
min
is the minimum value needed to obtain strong connectivity. We also show that Ω(log
n
) interference is needed for some instances, making our algorithms asymptotically optimal.