SDP-Based Approach for Channel Assignment in Multi-Radio Wireless Networks

The authors consider the following channel assignment problem in multiradio multi-channel wireless networks: Given a wireless network where k orthogonal channels are available and each node has multiple wireless interfaces, assign a channel to each link so that the total number of conflicts is minimized. This paper presents an integer semidefinite programming formulation for the problem and show that it is equivalent to an optimal channel assignment. By relaxing integrality constraints, the authors can find a lowerbound on the optimal channel assignment.