Optimal Channel Assignment Algorithm for Least Interfered Wireless Mesh Networks

Introduction

Wireless Mesh Networks (WMNs) are a special type of Next-Generation Networks (NGN) that provides one of the most promising solutions to improve network coverage, provide community broadband Internet access services and reduce deployment cost. Thus, this network architecture has emerged as a reliable and cost efficient for providing large coverage area through mutli-hop wireless communications and for improving wireless ad-hoc Networks, Local Area Networks (LAN), Personal Area Networks (WPAN) and Metropolitan Area Networks (WMAN).

In such networks, communications between two nodes can be supported by intermediate nodes called Mesh Routers (MRs). Figure 1 illustrates a relatively static infrastructure of a WMN composed by Mesh clients (MCs), Mesh Access Point (APs), MRs and Mesh Gateways (MGs) (Akyildiz et al., 2005).

Figure 1.

A WMN infrastructure

The mesh networking concept can be implemented by IEEE 802.11 and IEEE802.16 technologies and may lead to new applications that were previously unattainable with traditional solutions. Interference is a major factor having a direct impact on network capacity. This factor limit the number of simultaneous communication when using single channel. Thus, network performance and capacity are improved when MRs are equipped with multiple wireless interfaces built on the same or different wireless access technologies. This can be achieved if a special care is taken while the assignment of channels to the radio interfaces.

Recently, considerable interest has been given to WMNs design problem. Most of these studies have focused on routing (Biswas & Morris, 2005), interference measurement and capacity analysis (Gupta et al., 206), power control (Narayanswamy et al., 2002), topology control (Burkhart et al., 2004), link scheduling (Brar et al., 2006), channel/radio assignment (Subramanian et al., 2007) and nodes placement (Mountassir et al., 2012). Among these topics, the channel assignment has received extensive attention.

In a Multi-radio Multi-channel Wireless Mesh Network (MRMC-WMN), Channel Assignment (CA) consists of affecting channels to the radio interfaces in order to achieve efficient utilization of channel and reduce interference. This issue is a significant combinatorial optimization problem that, being NP-hard (Raniwala et al., 2004), must be solved by using meta-heuristic algorithms instead of traditional methods.

CA schemes can be classified as Fixed, Dynamic or Hybrid algorithms that have to maintain network connectivity and increase aggregate bandwidth while minimizing interference. Fixed assignment schemes assign channels to interfaces either permanently or for long time intervals. Dynamic assignment strategies allow interfaces to be assigned any channel and can frequently switch from one channel to another. Hybrid approach combines both static and dynamic channel assignment properties by applying a fixed assignment for some interfaces and a dynamic assignment for other interfaces.

In this paper, we address the Fixed Channel Assignment problem. This provides a low delay because of the rare channels switching.

Therefore, our contributions can be summarized as follow:

• 1.

  We first mathematically formulate the new channel assignment model where two conflicting objective functions are simultaneously optimized; maximizing total links number and minimizing interference level.

• 2.

  The CA problem being NP-hard, we use a meta-heuristic method to search near optimal solution of the proposed model.

The rest of the paper is organized as follow: We first present related works. Then we present the formulation of our model. We also propose a multi-objective optimization of the proposed model and present experimental results. We conclude our work and give directions for future research.