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

Peng‐Jun Wan, Chih‐Wei Yi, Xiaohua Jia, Dongsoo KimCommunications 2006

Abstract

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. Copyright © 2006 John Wiley & Sons, Ltd.
BibTeX
@inproceedings{wan2006approximation,
  author = {Peng‐Jun Wan and Chih‐Wei Yi and Xiaohua Jia and Dongsoo Kim},
  title = {{Approximation algorithms for conflict-free channel assignment in wireless ad hoc networks: Research Articles}},
  booktitle = {Communications},
  year = {2006},
}

Loading related content...

Figure