The channel assignment problem in ad hoc wireless networks is investigated. The problem is to assign channels to hosts in such a way that interference among hosts is eliminated and the total number of channels is minimised. Interference is caused by direct collisions from hosts that can hear each other or indirect collisions from hosts that cannot hear each other, but simultaneously transmit to the same destination. A new class of disk graphs (FDD: interFerence Double Disk graphs) is proposed that include both kinds of interference edges. Channel assignment in wireless networks is a vertex colouring problem in FDD graphs. It is shown that vertex colouring in FDD graphs is NP-complete and the chromatic number of an FDD graph is bounded by its clique number times a constant. A polynomial time approximation algorithm is presented for channel assignment and an upper bound 14 on its performance ratio is obtained. Results from a simulation study reveal that the new graph model can provide a more accurate estimation of the number of channels required for collision avoidance than previous models.
M. X. Cheng et al., "New Graph Model for Channel Assignment in Ad Hoc Wireless Networks," IEE Proceedings -- Communications, vol. 152, no. 6, pp. 1039-1046, Institute of Electrical and Electronics Engineers (IEEE), Dec 2005.
The definitive version is available at http://dx.doi.org/10.1049/ip-com:20059053
Keywords and Phrases
Adjacent Channel Interference; Channel Allocation; Optimisation; Polynomial Approximation; Ad hoc networks (Computer networks); Computational complexity; Graph coloring; Number theory
International Standard Serial Number (ISSN)
Article - Journal
© 2005 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.