Approximation algorithms for conflict‐free channel assignment in wirelessad hocnetworks
Peng‐Jun Wan, Chih‐Wei Yi, Xiaohua Jia, Dongsoo Kim · Wireless Communications and Mobile Computing · 2006
Abstract Conflict‐free channel assignment is a classic and fundamental problem in wirelessad hocnetworks. It seeks an assignment of the fewest channels to a given set of radio nodes with specified transmission ranges without causing either primary collision or secondary collision. It is NP‐hard even when all nodes are located in a plane and have the same transmission radii. We observe that a prior analysis of the approximation ratio of a classic greedy heuristic, FIRST‐FIT in smallest‐last ordering, is erroneous. In this paper, we provide a rigorous and tighter analysis of this heuristic and other greedy FIRST‐FIT heuristics. We obtain an upper bound of 13 on the approximation ratios of both FIRST‐FIT in smallest‐last ordering and FIRST‐FIT in radius‐decreasing ordering. Such upper bound can be reduced to 12 if all nodes have quasi‐uniform transmission radii. When all nodes have equal transmission radii, we obtain an upper bound of 7 on the approximation ratios of FIRST‐FIT in smallest‐last ordering, FIRST‐FIT in distance‐increasing ordering, and FIRST‐FIT in lexicographic ordering. In addition, for nodes with equal transmission radii, we present a spatial divide‐and‐conquer heuristic with approximation ratios of 12. All these heuristics, except FIRST‐FIT in smallest‐last ordering, are modified to heuristics for maximum independent set with the same approximation ratios. Copyright © 2006 John Wiley & Sons, Ltd.