Approximation Algorithm for Wireless Network Interference Minimization - Aslanyan, Hakob L. (Mathematical Problems of Computer Science, 2021)
Interference minimization problem in wireless sensor and ad-hoc networks are considered. That is to assign a transmission radius to each node of network, to make it connected and at the same time to minimize the maximum number of overlapping transmission ranges on each node of network. Additional means of topology control besides the connectivity is blocking the long line connections at the receiver level. We propose a polynomial time approximation algorithm which finds connected network with at most O((opt log n)2 ) interference where opt is the minimal interference of the given network, and n is the number of network nodes. The lower bound for this problem, where a general distance function is considered, has been proven to be O(log n) . The algorithm is known which finds a network where maximum interference is bounded by O( n) .