Approximation algorithms for conflict-free channel assignment in wireless ad hoc networks

Peng Jun Wan*, Tsi-Ui Ik, Xiaohua Jia, Dongsoo Kim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


Conflict-free channel assignment is a classic and fundamental problem in wireless ad hoc networks. 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.

Original languageEnglish
Pages (from-to)201-211
Number of pages11
JournalWireless Communications and Mobile Computing
Issue number2
StatePublished - 1 Mar 2006


  • Approximation algorithm
  • Channel assignment
  • Primary interference
  • Secondary inteference

Fingerprint Dive into the research topics of 'Approximation algorithms for conflict-free channel assignment in wireless ad hoc networks'. Together they form a unique fingerprint.

Cite this