Minimizing the maximum Interference in k-connected wireless networks

Thumbnail Image
Mehrpour, Sahar
Journal Title
Journal ISSN
Volume Title
Given a set P of n points in R^d, we consider the k-connected interference minimization problem, in which the objective is to assign a transmission radius to each node in P such that the resulting network is k-connected and the maximum interference is minimized. We show for any n and any 1 <= k < n, Omega(sqrt(kn)) and Omega(k log n) are lower bounds on the worst-case minimum maximum interference in the symmetric and asymmetric models, respectively. In the symmetric case, we present polynomial-time algorithms that build a k-connected network on any given set of n nodes with interference O(sqrt(kn)) in one dimension and O(min{k sqrt(n), k log lambda}) in two dimensions, where lambda denotes the ratio of the longest to shortest distances between any pair of nodes. In the asymmetric case, we present a polynomial-time algorithm that builds a strongly k-connected network with maximum interference O(k log lambda) in two dimensions.
Wireless networks, K-connectivity, Topology control, Interference minimization