Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks

•We develop novel heuristics for channel assignment in wireless mesh networks.•They are the first such solution algorithm to consider cumulative interference.•They consistently return near-optimum results.•They are orders of magnitude faster than an exact solution method.•They are also applicable to...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2016-06, Vol.251 (3), p.771-782
Main Authors: Chaudhry, Aizaz U., Chinneck, John W., Hafez, Roshdy H.M.
Format: Article
Language:English
Subjects:
Assignment problem
Channel assignment
Channels
Coloring
Exact solutions
Graph coloring
Heuristic
Heuristics
Interference
Links
Mathematical analysis
Minimum coloring
Studies
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We develop novel heuristics for channel assignment in wireless mesh networks.•They are the first such solution algorithm to consider cumulative interference.•They consistently return near-optimum results.•They are orders of magnitude faster than an exact solution method.•They are also applicable to other kinds of multi-hop wireless networks. Communication links connect pairs of wireless nodes in a wireless network. Links can interfere with each other due to their proximity and transmission power if they use the same frequency channel. Given that a frequency channel is the most important and scarce resource in a wireless network, we wish to minimize the total number of different frequency channels used. We can assign the same channel to multiple different links if the assignment is done in a way that avoids co-channel interference. Given a conflict graph which shows conflicts between pairs of links if they are assigned the same frequency channel, assigning channels to links can be cast as a minimum coloring problem. However the coloring problem is complicated by the fact that acceptably small levels of interference between pairs of links using the same channel can accumulate to cause an unacceptable level of total interference at a given link. In this paper we develop fast and effective methods for frequency channel assignment in multi-hop wireless networks via new heuristics for solving this extended coloring problem. The heuristics are orders of magnitude faster than an exact solution method while consistently returning near-optimum results.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2015.12.016