Exact algorithms to minimize interference in wireless sensor networks

Finding a low-interference connected topology is a fundamental problem in wireless sensor networks (WSNs). The problem of reducing interference through adjusting the nodes’ transmission radii in a connected network is one of the most well-known open algorithmic problems in wireless sensor network optimization. In this paper, we study minimization of the average interference and the maximum interference for the highway model, where all the nodes are arbitrarily distributed on a line. First, we prove that there is always an optimal topology with minimum interference that is planar. Then, two exact algorithms are proposed. The first one is an exact algorithm to minimize the average interference in polynomial time, O(n3Δ), where n is the number of nodes and Δ is the maximum node degree. The second one is an exact algorithm to minimize the maximum interference in sub-exponential time, O(n3ΔO(k)), where is the minimum maximum interference. All the optimal topologies constructed are planar.