A Comprehensive Study on Channel Assignment in Wireless Mesh Networks

A Comprehensive Study on Channel Assignment in Wireless Mesh Networks

Kusuma M1

M.Tech (CNE)student, Acharya Institute of Technology, Soldevanahalli, Bangalore560090, Karnataka, India.

Umapathi G R2

Professor G-1, Department of Information Science and Engineering, Acharya Institute of Technology,

Bangalore560090, Karnataka, India.

Abstract

Wireless Mesh Network is a mesh network implemented over a Wireless LAN where nodes dose not just send and receive data, but also serve as a relay for other nodes and each node collaborates in propagating data on the network. . While single radio mesh nodes operating on a single channel suffer from capacity constraints, equipping mesh routers with multiple radios using multiple non overlapping channels can significantly alleviate the capacity problem and increase the aggregate bandwidth available to the network.The goal of channel assignment algorithms in multi-radio mesh networks is to minimize interference, maximize throughput and load balancing. Design issues in multi-channel assignments can be mainting connectivity, routing and fault tolerance. In this article we examine the classification of channel assignment for wireless mesh networks. We discuss knowledge based channel assignment and switching frequency schemes in multi- radio Wireless mesh networks.

Keywords: Multi-radio multi-channel assignment, wireless mesh networks, knowledge based CA, switched frequency based CA.

1.Introduction

Wireless multi-radio multi-channel mesh networks have the potential to provide ubiquitous and ultra- high-speed broadband access in urban and rural areas, to both fixed and mobile users, with low operation and management costs. Such mesh networks can achieve significantly higher performance compared to single-radio single-channel mesh networks, by exploiting spatial diversity through multiple radio interfaces located in mesh nodes, each operating in different channels, and

directional antenna [1].Channel assignment in a wireless multi-radio mesh networks influences its overall performance, since it determines the level of interference between links internal to the mesh- network(intra-network interference), but also the interference from external sources. In multi-radio multi-channel WMNs, the channel assignment problem is to assign each radio a channel such that the network capacity is maximized for better performance.

In WMNs, the most crucial problem is capacity degradation due to wireless interference. An effective approach to this problem is to employ multiple non- overlapping channels in the network. In multi- channel WMNs, nodes are equipped with multiple radios and are allowed to transmit on different channels concurrently without causing collisions and interference. It is such parallel transmissions that improve the network capacity [2].

Architecture of WMNconsists of three levels: at the top level: Gateways, intermediate level: Mesh routers and bottom level: Clients, as shown in Fig.1.1.Gateway serves as a bridge between wireless mesh network components and other networks such as the internet. Mesh routers used to rout data packets from/to the other WMN components. Most of these routers are placed on the streetlight and on roof of houses [4], which serve as access points to cover large area as possible. The mesh clients comprise any wireless device or stationary uses WMNs services, and may form a client mesh network among both themselves and mesh routers which often are laptops, cell phones, etc. In WMNs each mesh router isequipped with several wireless network-interface cards (NICs) or radio interfaces, and each radio can be assigned to one orthogonal channel. Two radios can communicate and transmission with each other if they are assigned the same channel.

Fig1.1 Wireless Mesh Network Architecture

The rest of this paper is organized as follows. In Section II, we provide objectives of MR-MCA, Section III we provide a channel allocation in WMN such as knowledge based channel assignment and switching frequency channel assignment. Finally we conclude the paper with future research avenue in Section IV.

2.Multi Radio Multi Channel Assignment in WMNS

1. The objectives of Multi Radio-Multi Channel Assignment (MR-MCA) in WMNs

   In order to improve the capacity of wireless mesh networks, each node in a network is equipped with multiple radio interfaces to assign multiple channels help increasing the throughput of network and minimize the interference [5].

   The main objectives of MR-MCA in WMNs are:

   1. Interference Minimization

      Interference is one of the important challenges that faces channel assignment in WMNs. When two nearby wireless links assigning same channels (same frequency), they cannot transmit data at the same time. Each radio has a transmission range and an Interference range, with the former less than the latter. A transmission from radio X to radio Y is successful if Y is in the transmission range of X and not in the interference range of radios other than X that are currently transmitting. Physical Model can be described as : atransmission is successful if the Signal of Interference and Noise Ratio (SINR) of the transmitter at the receiver is larger than a threshold value; and the interference and noise power at the

      receiver consists of noises generated by other ongoing transmissions and the ambient noise in the network[5].

   2. Throughput maximization

      Most researchers recently focus on using MR-MCA to improve the network throughput (rate of transmission) in WMNS by increasing the number of parallel transmission in the network.

   3. Load balancing

      The load balancing is a balancing a workload amongst multiple nodes and objective of load balance is to assign channels to nodes meanwhile take into account the traffic load balance among channels in the network and mitigate the interference.

2. Design Issues in Multi-Channel Assignment

   Some key design issues in MR-MCA to be considered are:

   1. Maintaining connectivity

      Maintaining the network structure will help to avoid separation of the network into sub-networks is useful for network resources; thereby, enhancing the performance of the network through the exchange of information and ease of maintenance operations many advantages are originated from connectivity of WMNs to ensure reliable mesh connectivity, network self-organization and topology control algorithms [5].

   2. Routing

      Routing in some cases depends on CA and vice versa. Recently, the researchers trends to design joint routing and CA schemes that optimize the route by selecting the channels along the end to end path. Successfully installing Routing protocol is to avoid congestion and minimize the interference in the network [5].

   3. Fault tolerance

The fault tolerance is an autonomous (automatic) solution process issued by the router due to unexpected fails in software and/or hardware components such as, router to router disconnection due to external interference or temporary obstacles. So it is necessary for CA approach to support fault tolerance such that the network can operate in self-

healing fashion [5].

3.Classification of Channel Assignments in Wireless Mesh Network

3.1. Knowledge-Based Channel Assignment (KCA)

For instance, the link between nodes A and B in the connectivity graph in Fig.3.1.1 (a) is represented by a vertex lAB in the conflict graph of Fig.3.1.1 (b). An edge is placed between two vertices in the conflict gaph if the corresponding links in the connectivity graph interfere.

AB

Channel assignments in wireless mesh networks are classified into Knowledge-Based Channel Assignment (KCA) and Switching-Frequency Channel Assignment. Knowledge-Based Channel Assignment consists of Centralized and Distributed approach as shown in fig 3.1. Here we assign the channel entirely based on knowledge of collecting the information on the channels to be assigned [5].

A

B C

D

AC DA

BC

1. Centralized approaches

   Current channels information status of each node in WMN is sent to a central unit. The information includes the interference level, default channel available to that node and assigned channel to that particular node. This information is used by the centralized unit. This is used to assign channels to radios. Channel information of nodes is sent to central entity which assigns channels based on this information. Network fails completely when the channel assignment server is failed then the network fails completely. According to the problem formulations the centralized approaches are classified into graph-based, network flows and network partitioning approaches [5].

   Knowledge Based CA

   Centralize

   Distributed

   Graph based

   Network flows

   Peer oriented

   Network Partition

   Gateway oriented

   Fig 3.1 Knowledge-based Channel Assignment Graph-based approachesThe concepts of MR- MCA in WMNs are modeled by a graph with a vertex set and an edge set. A conflict graph is one of these approaches used in CA problem. In the conflict graph concept, we use the terms vertex and edge Instead of node and link as in the connectivity graph.

   Fig 3.1.1(a): Connectivity Graph Fig 3.1.1(b):Conflict Graph

   Network Flows Approaches this approach assumes the traffic rates that are at either end-to-end nodes or at each source nodes. This method includes the traffic load information and assuming constant traffic rates is the limitation of network flows approach, where the traffic pattern is characterized by random on/off sources and are usually burst.

   Network Partition Approaches network partition approaches is straightforward and simple. Using this approach, the radios and links in Multi radio multi- channel assignments in WMN are divided into separate sub networks which help in using each sub networks as a single channel. A set of different channels are assigned to these sub networks to reduce the problem of interference. All links in a partition are fixed to a common channel which decreases the network throughput and interference in the network is reduced which becomes the disadvantage to this approach.

2. Distributed approach

   Here local channel information of each node is measured and to calculate the channel assignment this information is exchanged with other nodes [6]. The distributed approach is more feasible. It is further classified into gateway-oriented and peer oriented approaches.

   Gateway-Oriented Approaches coordinates the network traffic across the central sinks through the appointment of certain number of gateways in the network. The advantage of these approaches is the opportunity to utilize the gateway nodes to simplify

   the CA approach. Gateway oriented approaches limitation is the incapability of accommodating other kinds of traffic patterns.

   Peer-Oriented Approaches in peer oriented approach, different types of network traffic are accommodated and no restrictions are made on them, hence is flexible to use in network. The channel assignment is difficult to fault tolerance. It has the capability of adapting to various kinds of traffic patterns, making it applicable for most of the current WMNs [7].

1. Switching-Frequency Channel Assignment

1. Fixed channel assignment schemes (FCA)

   In this scheme channels are assigned to interfaces either permanently or channels are assigned for long time intervals with respect to the interface switching time. Fixed channel assignment schemes divided into common channel assignment and varying channel assignment.

   Switching Frequency Based CA

   Fixed CA

   Hybrid C A

   Dynamic CA

   CCA

   VCA

   LLP

   IACA

   C-HYA

   CLIC

   SSC

   D-HYAHYA

   Fig 3.2.1 Switching Frequency Based CA

   Common Channel Assignment (CCA) same set of channels are assigned to radio interfaces of each node in Common Channel Assignment [8]. The connectivity of the network is same as that of a single- channel approach. Network throughput is increased by the use multiple channels. Whenthe number of non-overlapping channels is greater than the number of network interface cards (NICs)2 used per node, the gain becomes limited. Even though this scheme seems to be simplest, it fails to account for the various factors affecting channel assignment in a WMN.

   Varying Channel Assignment here in this scheme the interfaces of different nodes are assigned

   to different sets of channels [8]. Performing the channel assignment leads to network partitions and topology changes. This increases the distance between the mesh nodes. Therefore, in this scheme, assignments have to be done carefully. Further this varying channel assignment approach is divided into Centralized Channel Assignment and A Topology Control Approach.

   • Centralized Channel Assignment a centralized channel assignment algorithm for WMNs (C-HYA) is proposed Based on Hyacinth, a wireless mesh net- work architecture [8]. Traffic is mainly directed towards gateway nodes. Channels are assigned ensuring the network connectivity and bandwidth limitations of each link assuming the traffic load is known. Expected traffic load is been estimated initially in this algorithm and iterates over both channel assignment and routing. Iteration is continued until the bandwidth allocated to each virtual link matches its expected load. Thus increasing the time complexity of the scheme, the assignment of Channels on links may cause a ripple effect [8].

   • Topology Control Approach to enable an efficient and flexible topology formation, to exploit the static nature of mesh routers and ease of coordination, a traffic independent channel assignment scheme is proposed. A Connected Low Interference Channel Assignment (CLICA) computes the priority for each mesh node and assigns channels. The algorithm overrides the priority of a node and ensures network connectivity.

2. Dynamic channel assignment schemes

   Interfaces can frequently switch from one channel to another using Dynamic assignment strategy. Hence a coordination mechanism has to ensure that they are on a common channel when nodes need to communicate with each other. This mechanism requires all nodes to visit a predetermined channel to negotiate channels for the next phase of transmission[10].

   Slotted Seeded Channel Hopping (SSCH)in this mechanism, all neighboring nodes meets periodically in the same channel by switching channels synchronously in a pseudo-random sequence [10].

   Distributed Channel Assignment Scheme to improve the aggregate throughput and achieve load

   balancing, distributed channel assignment algorithms is proposed[10]. The algorithm builds on a spanning tree network topology Based on the Hyacinth architecture, in such a way that each gateway node is the root of a spanning tree, and every mesh node belongs to one of these trees. The problem with this approach consists of: Neighbour-to-interface binding (dependence among the nodes is eliminated in order to prevent ripple effects in the network) and Interface-to-channel binding (to balance the load among the nodes and relieve interference)

3. Hybrid multi-channel allocation

In Hybrid multi-channel assignment, each node has two interfaces where one interface from each router uses the dynamic channel allocation strategy, while the other interfaces se the static channel allocation strategy. High throughput paths from end-users to gateway are provided by the links that works on static channels. The links working on dynamic channels provides the network connectivity and the networks adaptively to the changing traffic.

Interference Aware Channel Assignmentto improve the capacity of the WMN backbone and to minimize interference dynamic centralized interference-aware algorithm (IACA) is proposed. It is based on the multiradio conflict graph (MCG). One radio on each node is assigned to operate on a default common channel throughout the network ensuring a common network connectivity graph. interference and bandwidth estimation are computed based on the number of interfering radios, where an interfering radio is visible to a mesh router. The channel assignment scheme works on a rank-based strategy. The rank for every available channel is based on interference and load.

Link Layer Protocols for Interface Assignment Wireless hosts have typically been equipped with one wireless interface. However, a recent trend of reducing hardware costs [12] has made it feasible to equip nodes with multiple interfaces. Nevertheless, it is still expensive to equip a node with one dedicated interface for each channel, as the number of channels may be large. Even if each channel does not have a dedicated interface, currently available commodity wireless interfaces (such as IEEE 802.11 wireless interface cards) can be switched from one channel to an- other, albeit at the cost of a switching latency, thereby allowing all channels to be potentially utilized. The link layer protocols utilize multiple channels. The link layer protocol is based on a novel

interface assignment strategy that classifies available interfaces into fixed and switchable interfaces. Fixed interfaces stay on specified fixed channels (can be different for different nodes) for long intervals of time, while switchable interfaces can be switched more frequently, as necessary, among the non-fixed channels. By distributing fixed interfaces of different nodes on different channels, all channels can be utilized, while the switchable interface can be used to maintain connectivity. A key advantage of the link-layer protocol is that it can be implemented using off-the-shelf hardware.

4. Conclusion

Employing multiple channels can effectively improve the network capacity in wireless mesh networks (WMNs). In multi-radio multi-channel WMNs, the channel assignment problem is to assign each radio a channel such that the network capacity is maximized. Since whether two nodes can communicate with each other depends on the channels they use, different channel assignments may lead to different network topologies. We study the importance of channel assignment problems on the network performance; channel assignment will increase the capacity gain due to multiple channels.

References

1. Manos Delakis and Vasilios A. Siris Channel Assignment in a Metropolitan Wireless Multi- Radio Mesh Network Institute of Computer Science, Foundation for Research and Technology – Hellas Crete, Greece 2010.

2. Tehuang Liu and Wanjiun Liao Interplay of Network Topology and Channel Assignment in Multi-Radio Multi-Rate Multi-Channel Wireless Mesh Networks Department of Electrical Engineering, National Taiwan University, Taipei 2009.

3. Dongsheng Wang, Pin Lv, Yingwen Chen and Ming Xu POCAM: Partially Overlapped Channel Assignment in Multi-Radio Multi- Channel Wireless Mesh Network National University of Defense Technology, Changsha, China 2011.

4. Ian F. Akyildiz , Xudong Wang , Weilin Wang Wireless mesh networks: a survey Broadband and Wireless Networking (BWN) Lab, School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA 2005.

5. Ashraf Alzubir, Kamalrulnizam Abu, Adil Yousif, Albarraa Abuobieda State of the Art, Channel Assignment Multi-Radio Multi- Channel in Wireless Mesh Network Science and Information systems, University Teknologi, Malaysia January 2012.

6. Seungjoon Lee, Yoo-ah Kim, Minho Shin Distributed Channel Assignment for Multi-radio Wireless Networks 2005.

7. Bong-Jun Ko, Vishal Misra Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Columbia University misra@cs.columbia.edu2007.

8. Pouria Zand,mohesen shiva The Centralized ChannelAssignment Algorithm for Multi-channel Single transceiver WMNs with IEEE 802.15.4 MACLayerSchool of E & C Eng., University of Tehran Tehran,Iran e- mail:pouriazand@yahoo.com 2008.

9. Mahesh K. Marina, Samir R. Das A Topology ControlApproach for Utilizing Multiple Channels in Multi-RadioWireless Mesh Networks Computer Science Department University of California, Los Angeles Los Angeles, CA 90095- 1596, U.S.A. 2005.

10. Habiba Skalli, IMT Lucca Institute for Advanced Studies, Samik Ghosh and Sajal K. Das, The University of Texas at Arlington Luciano Lenzini, University of Pisa, Channel Assignment Strategies for Multiradio Wireless Mesh Networks2007.

11. Krishna N. Ramachandran, Elizabeth M. Belding, Kevin C. Almeroth, Milind M. Buddhikot Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks, University of California at Santa Barbara , Lucent Bell Labs, Holmdel 2005.

12. Pradeep Kyasanura Nitin H. Vaidyab Routing and Link-layer Protocols for Multi-Channel Multi-Interface Ad Hoc Wireless Networks Dept. of Computer Science, and Coordinated Science Lab, University of Illinois at Urbana- Champaign,Dept. of Electrical and Computer Eng., and Coordinated Science Lab, University of Illinois at Urbana-Champaign 2007.

13. Stefano Avallone, Davide Pellegrino, Paolo Peruggini, Francesco Paolo DElia and Giorgio Ventre A New Channel,Power and Rate Assignment Algorithm for Multi-Radio Wireless Mesh Networks Dip. Informaticae Sistemistica, Universita di Napoli Federico II , Via Claudio 21, 80125 Napoli, Italy 2008.