Interference Aware Channel Assignment in WMN using A Game Theoretic Approach

Interference Aware Channel Assignment in WMN using A Game Theoretic Approach

Nutan M. Dhande 1 ,Vinay S. Kapse 2

Department of Computer Science & Engineering Tulsiramji Gaikwad-Patil College

of Engineering & Technology,Nagpur(MH)

Abstract The Wireless Mesh Network (WMN) has already been recognized as a promising broadband access network technology from both academic and commercial perspective. In order to improve the performance of WMNs, extensive research efforts have been dedicated towards finding means to increase the number of simultaneous transmissions in the network while avoiding signal interference among radios. In case of WMNs based on IEEE 802.11 b/g standards, most recent research works have relied upon the usage of orthogonal channels for solving the Channel Assignment (CA) problem. In this paper, we explore the possibility of exploiting Partially Overlapped Channels (POCs) by introducing a novel game theoretic distributed CA algorithm. The proposed algorithm CoCAG is shown to achieve near-optimal performance in the average case.

KeywordsWireless Mesh Networks (WMNs), channel assignment problem, partially overlapped channels, game theory, potential games.

1. INTRODUCTION

   Wireless Mesh Networks (WMNs) have attracted tremendous interest from researchers involved in both academia and industry [1]. While a WMN consists of a multi-hop environment, its concept and target differ from those of the conventional Mobile Ad hoc Networks (MANETs). In a typical WMN, there are two types of nodes, namely Mesh Routers (MRs) and Mesh Clients (MCs). MRs are responsible for network routing and bridging while MCs are light-weight nodes performing simple client functions. One key feature of the WMN is the backbone network composed by MRs in which they are usually static and have no constraints on energy consumption. Due to these attractive features, WMNs are expected to appear as a promising technology in the Next Generation Networks (NGNs) in order to deploy ubiquitous Internet access. To promote this phenomenal prospect, a number of standards have already been developed for WMNs for different access ranges, namely IEEE 802.15.4, IEEE 802.11s and IEEE 802.16j [1]. Since IEEE 802.11 is one of the most popular access technologies for commercial end-users, we are interested in WMNs based on this technology. One of the most promising techniques in Multi-Radio Multi-Channel (MRMC) field is Partially Overlapped Channel Assignment by using IEEE 802.11 b/g technology, which can increase

   the network throughput by exploiting more simultaneous transmissions. According to this standard, there are eleven channels available for communication on the 2.4 GHz band. By exploiting all eleven channels in a systematic approach to avoid the interference among adjacent channels, we can achieve a higher number of simultaneous transmissions than restricting ourselves with the use of only three orthogonal channels. Note that this approach is not as straightforward as it seems at the first glance. Unless it is carefully planned, adjacent channel interference may become significant in severely degrading network performance instead of improving it. In this paper, we use game theory to design a systematic approach to utilize partially overlapped channels in WMNs while minimizing the adverse effect of adjacent channel interference. Game theory is a mathematical tool, particularly useful, in the network engineering field to model highly complex scenarios that may include complex traffic models, mobility, unpredictable link quality, and so forth, in which pure mathematical analysis has met limited success. This mathematical tool provides researchers with the ability to model individual or independent decision makers called players. Every player interacts with other players and has an impact on their decisions. The dynamics of WMNs and MANETs closely resemble to this observation.

   Wireless ad hoc network is characterized by a distributed, dynamic, self-organizing architecture. Each node in the network is capable of independently adapting its operation based on the current environment according to predetermined algorithms and protocols. Analytical models to evaluate the performance of ad hoc networks have been scarce due to the distributed and dynamic nature of such networks. Game theory offers a suite of tools that may be used effectively in modeling the interaction among independent nodes in an ad hoc network. In this article we describe how such games can be set up and discuss recent advances in this area.

   In such a multi-radio multi-channel (MRMC) environment, the key challenging problem for capacity optimization is channel assignment. Consider a wireless mesh network operating with the interface devices built on IEEE 802.11b/g technology. Fig. 1 gives an overview of the frequency spectrum of this category which works in the 2.4 GHz frequency band having a total of 11 channels available for communication. The frequency bandwidth of each channel is 44 MHz and the dotted lines correspond to the centre frequencies of corresponding channels. The distance

   between the centre-frequencies of two consecutive channels is 5 MHz. Increasing channel separation for simultaneous transmissions corresponds to decrease in spectrum overlapping which lead to less interference. If two channels have a separation of 5 channels or more, then they work as orthogonal channels. For example, channel 2 is orthogonal with respect to channels 7 and above. The maximum number of available orthogonal channels in IEEE 802.11b/g is 3. These are channels 1, 6 and 11. The reason why partially overlapped channels (POCs) are neglected is because they create a significant amount of interference which is often difficult to handle. On the other hand, as the number of orthogonal channels is very limited, it now becomes infeasible to design an efficient channel assignment algorithm without the aid of POCs for MRMC environment. Recent works show that a systematic approach to exploit POCs can lead to better spectrum utilization and maximize network capacity and throughput Their research also reflects that the effect of interference from adjacent channels is reduced as the geographical distance is increased. Therefore, instead of prohibiting the usage of channels with overlapped spectrum, POC based design makes a smart compromise between geographical positioning of neighboring nodes and interference tolerance level of radio interfaces. The primary idea is to provide nodes with full access of all working channels in the available spectrum let it decide whether a specific channel is usable or not. This increases channel diversity and upgrades overall network capacity. In this way, network capacity can be improved up to 90% if all the 11 channels can be utilized in 802.11b.

   Fig.1: Partially Overlapped Channels (POC) in IEEE 802.11b/g.

   The specific objectives of this paper include:

   • To analyze CA problem from the game theoretic perspective.

   • To model the interference among MRs and Traffic between them in de-centralized game.

   • The objective of the game is to maximize the network throughput.

   • To derive the negotiation based optimal CA Algorithm based upon the properties of a potential game in game theoretic approach.

   • To do the comparative study of proposed approach with existing approach [7].

     Section 2 include related work that has been done in past on channel assignment. This section covers wireless network mainly WMN and existing WMN channel assignment schemes. In section 3 Existing Methodology of channel assignment lgorithms and important issues for channel assignment are discussed. This section is the corner stone of proposed work. section 4 proposed methodology interference and Traffic aware optimal partially overlapping channel assignment schemes. Chapter 5 covers implementation of proposed methodology and algorithm procedure. Chapter 6 Result and Discussion of proposed scheme. Chapter 7 concludes the work of this study and points out future works.

2. LITERATURE REVIEW

   Several channel assignment schemes were proposed in past. In this section we review some of the important existing Channel Assignment schemes for WMN as follows.

   • Centralized Channel Assignment and Routing Algorithms for Multi-Channel WMNs.

   • Breadth-First-Search Channel Assignment Algorithm (BFS-CA)

   • Multiple Radio Channel Assignment Utilizing Partially Overlapped Channel.

   • Partially Overlapped Channel Assignment on Wireless Mesh Network Backbone.

   • A Game Approach for Multi-Channel Allocation in Multi-Hop Wireless Networks

   • Channel Assignment Strategies for Multi-radio Wireless Mesh Networks: Issues and Solutions

     1. Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks (HYACINTH)

        In [15], the authors are mainly concerned with the channel assignment problem in Multi-Radio Wireless Mesh Networks. They propose and evaluate one of the first multi- channel multi-hop wireless ad-hoc network architectures that can be built using standard 802.11 hardware by equipping each node with multiple network interface cards. Their main contributions are as follows:

        • The first work of its kind that deals with channel assignment and routing in multi-radio wireless mesh networks.

        • An iterative algorithm that switches between channel assignment and routing problem that terminates when convergence is observed.

          A novel link-wise channel assignment scheme that assign channels to network interfaces on either side of the link based on the expected link load.

     2. Breadth First Search Channel Assignment Algorithm (BFS-CA)

        In this CA scheme, the authors explore the interference to wireless deployments due to co-located wireless networks and propose an algorithm (BFSCA) by using nodes with multiple radios and assigning them channels using multi- radio conflict graphs. Their contribution is as follows:

        • A dynamic, interference-aware channel assignment algorithm that minimizes interference between mesh network and co-located wireless networks.

        • A multi-radio conflict graph (MCG), an extension to the well known conflict graph

          model, is used to model the interference relationship between multi-radio routers in a wireless mesh network.

     3. Multiple Radio Channel Assignment Utilizing Partially Overlapped Channel.[7]

        Through this paper, the authors explore the issue of channel assignment with POCs in consideration for MRMC environments. Authors attempt to provide an estimation of the workability of POC based channel assignment schemes on various topologies in wireless mesh networks (WMNs). This is the first algorithm for this targeted issue. The main contributions of these schemes include:

        1. Given the topology of an MRMC-WMN, a heuristic algorithm is used to allocate channels to maximum number of links such that it minimizes interference.

        2. The issues of efficient spectrum utilization is dealt by considering both POCs and orthogonal channels.

        3. The effect of different topological factors influencing the channel assignment results, such as node density, network load etc. was analyzed comparatively.

        4. Finally the capacity improvements were derived by comparing the performance of our POC based algorithm with the one using only orthogonal channels.

     4. Partially Overlapped Channel Assignment on Wireless Mesh Network Backbone

        There are two main components in this channel assignment algorithm, namely the network traffic load and the I-Matrix. The former is calculated beforehand and used as an input file to the Algorithm. This components purpose is to describe which links should be assigned channels and, most importantly, in which priority this should occur. The latter is initially set to zero and is used as a systematic method to assign channels to the links assuring that interference will not happen until the possibility of using non-interfering links is exhausted. By exploiting the I-Matrix in a unique manner, they cover disconnected nodes, connecting them to the network in such a fashion that the disconnected node will

        connect to a neighbor using one of the channels already assigned to the neighbor, as long as it does not cause self- interference. Regarding the evaluation metrics, they use the number of non interfering links assigned to a given topology. They also use a metrics, the number of nodes connected to the gateway. And finally, the network throughput is measured at the gateway.[8]

     5. A Game Approach for Multi-Channel Allocation in Multi-Hop Wireless Networks

        Channel allocation was extensively investigated in the framework of cellular networks, but it was rarely studied in the wireless ad-hoc networks, especially in the multi-hop ad- hoc networks. In this paper, the competitive multiradio channel allocation problem in multi-hop wireless networks in detail is done. Authors modeled the channel allocation problem as a static cooperative game, in which some players collaborate to achieve high date rate. Authors propose the min-max coalition-proof Nash equilibrium (MMCPNE) channel allocation scheme in the game, which aims to max the achieved date rates of communication links. They analyze the existence of MMCPNE and prove the necessary conditions for MMCPNE. Furthermore, they proposed several algorithms that enable the selfish players to converge to MMCPNE. Simulation results show that MMCPNE outperforms CPNE and NE schemes in terms of achieved data rates of the multi-hop links due to cooperation gain.[9]

        1. Nash Equilibrium

           In a Game Theoretic approach each player is a rational and self-interested player, who will always choose action that maximizes its payoff. Thus the multi-radio channel allocation problem is formulated as a static game, which corresponds to a fixed channel allocation among the players. In single-hop networks, the multi-radio channel allocation problem can be formulated as a static non-cooperative game (e.g., in [3]).The payoff of player ui is denoted by

           as the utility of ui in the strategy matrix X, i.e.,

           . In order to study the strategic interaction of the players in static non-cooperative game, the concepts of Nash equilibrium [9] was introduced. Nash equilibrium is the most widely used solution concept for strategic game in game theory. A strategic game is a model of interactive decision making in which each decision maker choose his plan of action once and for all and these choice are made simultaneously. If game is played repeatedly and players converge to a solution, then it has to be a NE.

        2. Game Theory

           Game theory is the mathematical model to analyze the interaction between a group of players who behave strategically. The ability to model individual, independent players whose strategies affect every other players in the group makes game theory a powerful and useful tool to

           analyze the performance of wireless mesh networks. In other words, game theory is concerned with finding the best strategies for individual players in such dynamic, distributed and unpredictable wireless networks . A game is usually specified by four objects:

           • A set of players , which is a finite set {1, 2, 3, …n}.

           • The strategy space, , available to each player i. When a player chooses an action, he can use either a pure or a mixed strategy. If the actions of the player are determinitic, he is said to use a pure strategy. A mixed strategy is a probability distribution over a players pure strategies.

           • The payoffs, , associated with any strategy combination (one strategy per player).

           • All players are rational and each player chooses action that yields him the greater payoff. If the game is not deterministic, the players chooses action that maximize his expected payoff.

     Below are some of the important terms in game theory approach.

     1. Non-Cooperative and Cooperative Game: In non cooperative games, the actions of the single players are considered and in cooperative games the joint actions of the players are considered.

     2. Complete and Incomplete Information Game: Non- cooperative games can be classified as complete information games or incomplete information games, based on whether the players have complete or incomplete information about their opponents in the game. In games with complete information the preferences of the players are common knowledge, that is all the players know all the utility functions. But in a game of incomplete information the players do not know some relevant characteristics of their opponents which include their payoffs, strategy spaces etc.

     3. Zero-sum and Non Zero-sum Game: In a (two player) zero-sum game, the payoffs of the player I are just the negative of the payoffs of player II; that is

     . If the sum of the payoffs is not equal to zero,

     , then it is a non-zero sum game.

     1. Channel Assignment Strategies for Multi-radio Wireless Mesh Networks: Issues and Solutions [11]

     As highlighted earlier, the central goal of channel assignment for multi-radio mesh networks is to improve the aggregate throughput of the network, taking into account the effects of traffic and interference patterns, as well as maintaining topological connectivity. Based on our observations of the impact of traffic patterns and network connectivity on the performance of a WMN, below we

     propose an innovative scheme called MesTiC, which stands for (mesh-based traffic and interference aware channel assignment). It has the following important features:

     • MesTiC is a fixed, rank-based, polynomial time greedy algorithm for centralized

     • Channel assignment, which visits every node once, thereby mitigating any ripple effect.

     • The rank of each node is computed on the basis of its link traffic characteristics,

       Topological properties, and number of NICs on a node.

     • Topological connectivity is ensured by a common default channel deployed on a separate radio on each node, which can also be used for network management.

3. EXISTING METHODOLOGY

   Transmission and Interference Model: Wireless mesh network consist of fixed routers that provide a strong backbone to network to aggregate traffic and retransmit traffic to mesh gateways which in turn provide access to internet over a large coverage area. In, turn wireless mesh routers plays a role of a relaying nodes to and fro from mesh gateways forming multi-hop wireless mesh network. The gateways are interface to wired internetworking which contains infrastructure resources such as file servers and application servers. The link between gateway and the wired network is point-to-point IEEE 802.11 standard or IEEE 802.16.

   Each wireless mesh router consists of multiple radios which can be tuned to any 3 IEEE 802.11b non-overlapping channels or 12 IEEE 802.11a/g non-overlapping channels. For two nodes to have successful communication, the two nodes should be in direct communication range of each other. Moreover the NICs of two mesh points should be tuned to same frequency. The two nodes in interfering range of each other can interfere with each other if they are tuned to same channel.

   Transmission and Interference from nearby wireless mesh nodes can be described using two models. These are protocol model and physical model.

   1. Protocol Model

      Let Rt and Ri denote the fixed transmission range and interference range of all wireless interfaces respectively where Ri > Rt (approximately Ri = 2Rt). Let distance (u,v) represent the Euclidean distance between two nodes u,v V. For two nodes u,v V, direct communication is only possible if the distance (u,v) Rt and at least one of the interfaces of the node operate in same channel. We assume that wireless links are symmetric that is if u can transmit to v than v can also receive successful transmission from u. Two links e1(u1,v1) and e2(u2,v2) interfere with each other if

      both edges operate on a common channel and any of the distances distance (u1,u2), distance(u1,v1), distance(v1,u2), distance(v1,v2) <=Ri.

   2. Physical Model

      The transmission is successful if SNRij (Signal to Noise Ratio) is greater than SNRthres (Threshold) where SNRij denotes the signal-to-noise ratio at node nj for transmission received from node ni. The total noise, Nj, at nj consists of the ambient noise, Na plus the interference due to other ongoing transmission in the network.

   3. System Model

      The CA issue defined as an optimization problem in terms of mapping available communication channels to network interfaces in order to maximize the communication capacity while minimizing signal interference. Note that Interference range is defined as the distance within which interference occurs. In a multi-channel environment, four different types of interference and their influence on the network capacity should be addressed. To describe easily, let us consider two pairs of nodes where each pair has a sender and a receiver. Let the sender and receiver of the first pair be S1 and R1, respectively. The sender and receiver of the second pair are denoted by S2 and R2, respectively. To illustrate our considered system model, first we describe the following terms.

      • Co-channel Interference: Co-channel interference occurs in case that all four nodes involved in the afore-mentioned pairs are operating in the same channel. Because of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), this type of interference is less harmful for the network capacity than Adjacent Channel Interference. Consider the following scenario: node S1 is starting to transmit a packet to R1. S1 checks if the medium is busy or idle. If it detects that the medium is busy, the node will withdraw its attempt to transmit by postponing it. However, if the medium is idle, it will proceed with the transmission. While S1 is sending data to R1, consider a scenario in which S2 also attempts to send a packet to R2. S2 will detect the busy medium. Hence, S2 will withdraw the transmission attempt and wait over a back off period. Later on, it will attempt again and if the transmission between S1-R1 is already finished, S2 will finally succeed with the signal transmission to R2. In this scenario, we have a contention based access.

      • Orthogonal Channels: Consider another scenario whereby S1-R1 and S2-R2 are using two orthogonal channels. Again, S1 detects an idle medium and starts the packet transmission. Meanwhile, S2 will also detect an idle medium since it is operating on a distinct channel. Both pairs are able to successfully transmit their packets simultaneously, because there is no overlapping frequency band between those channels. Limitation of this approach is that only three pairs of nodes can communicate in this

        manner since only three out of the eleven available channels, namely channels 1, 6, and 11, are orthogonal.

      • Adjacent Channel Interference: This kind of interference seriously degrades the network capacity. Here, we consider S1-R1 and S2-R2 assigned to channels 1 and 3, respectively. S1 begins transmitting first, S2 will detect an idle medium in channel 3 and also starts to send its packet. However, since channels 1 and 3 share a common frequency band, the reeivers may not be able to successfully decode the packets, causing a transmission error that severely degrades the network throughput.

      • Self Interference: Self-interference is defined as a node causing interference to one of its own transmissions. This case will occur in multiple radio nodes using Omni directional antennas. Considering the afore-mentioned types of interference, the authors in [6] developed a schematic procedure for CA. This model is called as I-Matrix and it determines whether it is possible or not to assign channels to a given link exploiting POC. To adopt this model, we need to define four key components, namely Interference Factor, Interference Vector, Interference Matrix, and finally Threshold Interference.

   4. Channel Assignment

      1. MCG for Channel Assignment

         Conflicts Graph are used extensively to model interference in cellular radio networks [15]. A conflict graph for a mesh network is defined as follows: Consider a graph G, with nodes corresponding to routers in the mesh and edges between the nodes corresponding to wireless links. A Conflict graph, F has vertices corresponding to the links in G and has an edge between two vertices in F if and only if the links in G denoted by the two vertices in F interfere with each other.

         At a first glance, the problem of assigning channels to links in a mesh network appears to be a problem of vertex colouring the conflict graph. However, vertex colouring fails to assign channels correctly because it does not account for the constraint that the number of channels assignable to a router must be equal to its radios. The conflict graph does not correctly model routers equipped with multiple radios. Therefore, authors extend the conflict graph to model multi- radio routers. In the extended model, called the multi-radio conflict Graph (MCG), we represent edges between the mesh routers as vertices as in the original conflict graph.

      2. Co-ordinated and Non-Coordinated Interfering Links

         In[17] the authors have broadly classified interfering links as coordinated and non-coordinated, depending on the geometric relationship between the interfering link and target link. For a directional link l(i,j)-i being transmitter and j is the receiver the directional link l(i,j) is a coordinated interfering link if the Euclidean distance d(i,j) is less than

         the carrier sensing range (Rcs). On the other hand, link l(i.j) is a non-coordinated interfering link if d(i,j)Rcs and {d(i,j) and/or d(i,j) and/or d(j,j)} Rcs. Garetto et al.

         [31] have shown that non-coordinated interference results in significantly higher transmission losses and unfair capacity distribution amongst the links, as compared to co-ordinated interference. We highlight the fact that compared to coordinated interference, non-coordinated interference has a severe impact on the channel utilization and consequently on the network capacity. This leads to the hypothesis that a channel assignment scheme which prioritizes the minimization of non-coordinated interference over coordinated interference can significantly improve the network capacity.

      3. Channel Switching used in Channel Assignment

   The dynamic channel assignment requires frequent switching of channel. This switching is inefficient, since they require channel switching which causes significant delays. The delay can in order of milliseconds with IEEE

   802.11 network cards. This is higher than normal packet transmission time which is in the order of microseconds. Additionally these approaches are unsuitable to be used with commodity IEEE 802.11 hardware. Since they require modification MAC layer or hardware. Unlike of all these previous proposals our architecture does not perform channel switching on a packet-by-packet basis, our channel assignment lasts for a larger duration such as several minutes or hours and hence does not require resynchronization of communicating network cards on a different channel for every packet.

   3.4.4 Traffic Aware Topology design for Wireless mesh network

   The wireless gateways experience a maximum load. The maximum traffic is induced on wireless link at gateways. Hence seeing the high traffic the channels assigned to gateway links should be first and then other. Our channel assignment procedure creates the clusters near gateways nodes. Gateways nodes are cluster head and all nodes that are at 2 hop distances from gateway node are the clusters members of cluster. Now while assigning channels to cluster first the channel are assigned to links that are close to gateway since they experience maximum traffic. Than the incident links are visited in decreasing order of traffic load. If interference link refers to lower numbered cluster than channel selected by neighbour cluster is used from that is bounded.

   1. Interference Model

      The I-Matrix at each node is the ultimate measurement that helps our channel assignment algorithm in determining whether a channel is assignable or not. It measures the interferences from all the possible channels for each channel with the nodes current radio usage. They describes here the

      steps that lead to generate the matrix. They include the calculations of the interference factor, interference vector and the I-Matrix.

      1. Interference factor (I-Factor)

         In [7], Author explore the interference factor, fi,j to provide a measure of the effective spectral overlapping level between channels i and j. This interference factor takes into account both the geographical distance and the channel separation between the two transceivers using these two channels. Our definition of interference factor refers to the effective interference from adjacent channels considering the Interference Range as a reference distance metric. To be noted, our definition of interference factor is different from the normalized I-Factor. The I-Factor measures the extent of overlap between channels i and j given by the fraction of a transmitted signals power on channel i that will be received on channel j. On the other hand, we quantified our metric as a ratio of interference range and geographical distance between the operating radios. If the geographical distance is greater than the interference range associated with the channel separation, they consider the two channels i & j as non-interfering, even though they have spectrum overlapping. This gives us the opportunity of better spatial reuse of channels with overlapping bandwidths. Since the interference range depends on the signal strength of the receiver in a broad sense, that ours is a derived metric from the I-Factor. A good number of prior experiments have been done to measure the interference ranges (IR) for different channel separations. The IR table used for our algorithm is as follows:

         TABLE 3.5.1 Interference Range [7]

         	0	1	2	3	4	5
         IR()	13.26	9.21	7.59	4.69	3.84	0

         Here IR() refers to the interference range for a channel separation of , where = |i – j|. Let, d refer to the distance between the two radios operating on channels i & j. If the two radios tuned to channels i & j belong to the same node then the value of d will be zero. They define the interference factor as follows:

         1. fi,j =0 : when >5 or d> IR()

            When channels i & j do not have overlapping spectrum or their operating distance is beyond the interference range; the corresponding value of interference factor is equal to zero, which implies that channels i & j are non-interfering.

         2. 1< fi,j < : when 0 <5 and d< IR()

            When two radios communicating on channels i & j are within the interference range and the channel separation is

            lss than 5, they interfere with a factor inversely proportional to the distance between two operating radios. In this case we calculate the interference factor from the following equation

            fi ,j = IR()/d (1)

            Equation (1) indicates that fi,j decreases as the geographic distance increases.

         3. fi,j =: when 0< <5 and d=0.

         Due to the self-interference problem discussed in [7]. Two parallel transmissions on channels I and j within the same node will fully interfere with each other if their channel separation is less than 5.

      2. Interference Vector (I-Vector)

   After calculating the interference factors for all the distinct

   11 channels with respect to a specific channel within a particular node clearly an interference vector signifies the effect of interference from each of the 11 channels with respect to a particular channel i. The table also keeps track of the distance (di) to the nearest radio operating on channel i from the current node. Therefore, if the node itself has a radio tuned on channel I then di will be equal to zero. Table

   3.5.2 shows the interference vector corresponding to channel 3.

   1. I- Matrix

      Combining all the interference vectors for each channel, the I-Matrix . Each node keeps track of its own I-Matrix. Either a column or a row corresponding to channel i refer to the interference effects from all other channels. After each link assignment, each node updates the I-Matrix for the newly assigned channel.

   2. Threshold Interference (Th)

   In [7] Author defines a threshold (Th) value which specifies the tolerance level of interference for the radios. By limiting the value of Th to 1, they disregard any channel within IR() from being considered for assignment. If they want to increase the tolerance level, they may specify Th >1.

4. PROPOSED SOLUTION BASED ON GAME THEORY

   In this section, we model our MRs as players. The main objective of such modeling is to derive an optimal CA using the mathematical analyses provided by the Game Theory framework, and then compare this result against existing heuristic algorithms.

   Each MR is considered as a decision maker of the game, and we model the interactions among them as a Cooperative Channel Assignment Game (CoCAG). The game is composed of a finite set of players, denoted by A =

   {a1, a2. . . aN} and all the players have a common strategy space S = Si, i. In this context, we map the channel(s) assigned to a given MRs radios to its chosen strategy. Formally, the strategy of the ith player is si = {ki,1, . . . , ki,c,

   . . . , ki,|C|}, where |C| is the number of channels for the

   channel set C and ki,c is a binary value. ki,c is set to one, if channel c is assigned to one of the players radio. Otherwise, ki,c is set to zero. The game profile is defined as the Cartesian product of the players strategy vector, = ×iAsi

   = s1 × s2 × ×sN. Note that a game profile includes

   one strategy for each player. Also, si is specially defined as the strategy set chosen by all other players except player i.

   The objective of the game is to maximize the network throughput. We define a joint metric, Mi, for each player i, that translates the network link configuration and topology to a numerical value. This metric is directly proportional to the number of assigned links in each node. Each links capacity is evaluated according to the number of interfering links. Two topology control factors, k and h, are included, since the network should not be evaluated only by its number of links but also how efficiently these links connect the MRs towards the WMN GateWay (GW), i.e., the hop count. Mi is defined as follows:

   where

   • k is a connectivity factor set to one, if the node can indirectly reach the GW, zero otherwise.

   • R is the link data rate (in Mbps).

   • n is the number of interfering links.

   h is the hop count from the node to the GW.

5. Algorithm / Procedure used

   Procedure : GTAMN (G, noOfNode, noOfRadio ) Step 1. InitializeWMN (noOfNode, noOfRadios) Step2.InitializeStrategySetForAllNode(noOfNode, noOfRadios)

   Step 3. NGateway = Gateway of mesh topology

   Step 4. Execute Co-operative channelAssignment(G, NGateway)

   Step 5. Optimal Partially Overlapping channel(G;)

   Procedure: InitializeWMN(noOfNode, noOfRadios)

   1. (for i = 0, i < no. of nodes, i++)

   2. Set node identity

   3. Assign no. Of Radios

   4. End for

   5. i = noOfNode

   6. While ( i > 0)

   7. Set neighboring node to p nj node 8. i–

   9. End while

   Procedure: InitializeStrategySetForAllNodes(noOfNode, noOfRadios)

   1. i = noOfNode

   2. while ( i > 0 )

   3. for ( j = 0 , j < noOfRadios , j++ )

      1: si = {0}ai A 2: while T = 0 do

      3: Randomly select ai with prob. 1/N

      i

      i

      i

      i

      4: s rand random strategy {ki, 1, . . . , ki,c, . . . , ki,|C|} 5: while s rand valid strategy do

      i

      i

      6: s rand random strategy 7: end while

      8: if p(s rand , s t) random number [0, 1] then

      i i

   4. Rij = Radio j of ith node

   5. Rij = -1;

   1. End for

   2. End while

   9: s t+1 s rand

   i i

   i i

   10: else

   i i

   i i

   11: s t+1 s t

   12: end if

   i

   i

   13: Broadcast ai ID + s t+1

   Procedure: ExecuteCoOperativeChannelAssignment

   1. While all nodes are visited

   2. ni = getNodeUsingBFS(G,S)

   3. For each link e in sorted list do

   4. Ch Get_channel (e)

   Procedure: ChannelAssignment(CA)-

   1. for each link e in sorted list do

   2. ch Get Channel(e)

   3. if ch = Valid Channel then

   4. e.Assign Channel(ch)

   5. for all nodes: Update I-Matrix(ch)

   6. else

   7. cannot assign channel

   8. end if

   9. for each end

   10. for each node list L not connected to Gateway (GW) do

   11. order nodes in ascending order of hops to GW

   12. for each node n L do

   13. for each link e n do

   14. ch Get Co Channel(e)

   15. if ch = Valid Channel then

   16. e.Assign Channel(ch)

   17. for all nodes: Update I-Matrix(ch)

   18. else

   19. cannot assign channel

   20. end if

   21. for each end

   22. for each end

   23. for each end

   The following negotiation based algorithm converges to NE with a high probability. Let assume identical MRs, each of which has a unique identification parameter aiID for routing purpose. In addition, the finalization criteria, T , is based on following different parameters, e.g., the maximum number of negotiations, time limit, or utility function threshold. Here maximum numbers of negotiations are the finalization criteria, T.

   Procedure: OptimalPartiallyOverlappingChannels(G)

   14: Update T

   15: end while

6. RESULT AND DISCUSSION

   1. Aggregate Throughput Vs Topology

      Figure 6.5.1 Aggregate Throughput Vs Topology

      The above graph shows a comparison for throughput calculated for Topology on fixed and different data rates. The above graph shows that the proposed scheme outperforms POC at variable and Fixed Data Rate. Since Proposed scheme gives first priority to gateway in mesh topology because of maximum traffic on a gateway & next priority to neighboring node to assign only non-interfering channel in BFS, throughput at gateway is maximized which results in increase in overall throughput of network. Using topology of 9 Nodes, results show that 5 % of throughput of previous approach is inreased when channels are assigned using proposed approach at fixed data rate and topology of 16 Nodes, results show that 8 % of throughput of previous approach is increased when channels are assigned using proposed approach at fixed data rate

   2. Aggregate Delay Vs Topology

      Figure 6.5.2 Aggregate Delay Vs Topology (2-MR)

      The above graph shows a comparison for delay calculated for Topology on fixed and variable data rate. The above graph shows that the proposed scheme outperforms POC. The delay experienced by our proposed scheme at data rate is 60% less than POC fixed data rate in 16-node.

   3. Aggregate Throughput Vs Flows Id

      Figure 6.5.3 Aggregate Throughput Vs Flow ID

      The above graph shows a comparison for throughput experienced by a particular flow. The above graph shows that the proposed scheme outperforms POC. The per flow throughput is higher than POC at variable and Fixed Data Rate. Because proposed scheme gives first priority to gateway in mesh topology because of maximum traffic on a gateway & next priority to neighboring node to assign only non-interfering channel in BFS

   4. Interference Estimation using Queue Length

      The following graph shows a comparison for interference estimation experienced by a particular flow. It is easy to show that a larger value of the average queue length of the interference operating on a particular channel is always inductive of high interference, irrespective of cause of increase in queue length.

      Figure 6.5.4 Interference Estimation using Queue length

      The interference was calculated based on queue length. The above graph shows the interference experienced by each node within network. The average queue length was observed throughput simulation at each node. The above graph shows that the interference experienced by proposed scheme is less than POC at variable and fixed data rate.

   5. SNIR Vs Time

   Figure 6.5.5 SNIR Vs Time in seconds

   The above graph shows a SNIR experienced by network over a time in seconds. The simulation is performed with the packet size of 1024 bytes. The interference was calculated based on SNIR. The interference is low if SNIR is large. The above graph shows that interference experienced by proposed scheme is less than POC at variable Data Rate.

7. CONCLUSION AND FUTURE WORK

The results are studied with respect to Aggregate throughput, Aggregate Delay and Aggregate Queue length experienced by the mesh network when POC and Our Proposed Work is operated. BFS algorithm is used in proposed work, because BFSCA gives first priority to gateway to assign channels to its links due to maximum traffic experienced by it. This allows non-interfering channels to be assigned to the gateway. Then next priority is given to neighboring node to assign non-interfering channel. At last nodes farther away from gateway are assigned minimal interfering channels which are selected using game theoretic approach. The Interference matrix is used to find channel separation and the minimum interfere-ring channel that is suitable for that particular link. In the game theoretic approach the game theory randomly selects strategy and assigns valid strategy to players i.e. mesh node.

From the simulated results SNIR of our proposed work is high as compared to POC CA scheme. The average queue length was calculated at each interfaces of each node. From queue length results it is seen that the total interference experienced by each flow through our proposed channel assignment scheme is less than POC CA scheme. Aggregate throughput, Aggregate Delay experienced by simulating our proposed channel assignment scheme is better than POC.

Future Scope

The game theoretic approach is used to find the channel in wireless mesh network randomly. In game theoretic approach, for fixed data rate, there would be need of assigning channels only once at the time of network establishment. But for variable data rate, the channels assignment needs to be done whenever there is change in date rate on the links of mesh network. This will require channel switching. Since the channel switching time is considerably large enough than the packet transmission time. Frequent channel switching affects throughput adversely. It means that the throughput will get decrease. In that we do not prefer channel switching but in near future if this channel switching duration is minimized than dynamic channel assignment scheme based on traffic/date rate carried over link will increase network performance.

REFERENCES

1. Nutan M. Dhande and Vinay S. Kapse, A Survey of Interference & Traffic A ware Channel Assignment In WMN Using A Game Theoretic Approach, Proceedings 2nd National Conference On Emerging Trends in Computer Science & Information Technology 2012 organised by BDCOE, Sevagram, Wardha.

2. Nutan M. Dhande and Vinay S. Kapse, Review of Interference Aware Channel Assignment on WMN using Potential Game Approach, Proceedings National Conference on Innovative Paradigms in Engineering & Technology- NCIPET-2013, paper 19, pp. 110-114.

3. Nutan M. Dhande and Vinay S. Kapse, Interference & Traffic Aware Channel Assignment in WMN using Game Theoretic Approach, International journal of pure and applied research in engineering and technology, 2013, Volume 1(8), pp. 319-332.

4. I. Akyildiz and X. Wang, A survey on wireless mesh networks, IEEE Commun. Mag., vol. 43, no. 9, pp. S23 S30, Sep. 2005.

5. Weirong Jiang Shuping Liu Yun Zhu Zhiming Zhang, Optimizing Routing Metrics for Large-Scale Multi-Radio Mesh Networks, in Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference Shanghai, on page(s): 1550 1553,Sept 2007.

6. H. Skalli, S. Ghosh, S. Das, L. Lenzini, and M. Conti, Channel assignment strategies for multiradio wireless mesh networks: Issues and solutions, IEEE Commun. Mag., vol. 45, no. 11, pp. 8695, Nov. 2007.

7. M. Hoque, X. Hong, and F. Afroz, Multiple radio channel assignement utilizing partially overlapped channels, in GLOBECOM 09: Proc. IEEE Global Telecommun. Conf., Honolulu, HI, Nov. 2009, pp. 1 7.

8. P. B. F. Duarte, Z. M. Fadlullah, K. Hashimoto, and N. Kato, Partially overlapped channel assignment on wireless mesh network backbone, in Globecom 10: Proc. IEEE Global Commun. Conf., Miami, FL, Dec. 2010.

9. L. Gao and X. Wang, A game approach for multi- channel allocation in multi-hop wireless networks, in MobiHoc 08: Proc. 9th ACM Int. Symp. on Mobile ad hoc networking and computing, Hong Kong SAR, China, 2008, pp. 303312.

10. P. K. Dutta Strategies and Games: Theory and Practice MIT Press 1999.

11. E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, Computer Science Review, vol. 3, no. 2, pp. 65 69, 2009.

12. Gupta, P.; Kumar, P.R.; The capacity of wireless networks; in Information Theory, IEEE Transactions on, vol 46, pp-388-404, Mar 2000.

13. Niculescu, D. Ganguly, S. Kim, K. Izmailov, R. ; Performance of VoIP in a 802.11 Wireless Mesh Network, in Proceedings INFOCOM. 25th IEEE International Conference on Computer Communications.,pp 1-11, in April 2006.

14. K. Ramachandran, E. Belding, K. Almeroth, and M. Buddhikot, Interference-aware channel assignment in multi-radio wireless mesh networks, in INFOCOM, 2006.

15. Raniwala K. Gopalan, and T.Cker Chiueh, A Centralized channel Assignment and Routing Algorithms for multi channel WMNs, ACM SIGMOBILE Mobile Computing and Communiacations Review,2004.

16. Naveed, A. Kanhere, S.S. , Cluster-based Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks proc. LCN 2009, Rawalpindi, Pakistan, 2009.

17. V. Bukkapatanam, A. Franklin, and C. Murthy, Using partially overlapped channels for end-to-end flow allocation and channel assignment in wireless mesh netwrks, in ICC

    09: IEEE Int. Conf. on Commun., Dresden, Germany, Jun. 2009, pp. 16.

18. Naveed, A. Kanhere, S.S. Jha, S.K. Topology Control and Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks, Mobile Adhoc and Sensor Systems, 2007. MASS 2007 IEEE Conference, pages 1 9, Jan-2008.

19. A. Mishra, V. Shrivastava, S. Banerjee, and W. Arbaugh, Partially overlapped channels not considered harmful, in SIGMETRICS 06: Proc. Joint Int. Conf. on Measurement and Modeling of Comput. Syst., Saint-Malo, France, Jun. 2006, pp. 6374.

20. D. Fudenberg and J. Tirole, Game Theory. The MIT Press, Aug. 1991.

21. M. J. Osborne and A. Rubinstein, A Course in Game Theory, The MIT Press, Jul. 1994.

22. L. Gao, X. Wanga, Y. Xu, X. Gan, H. Yu, and A. V. Vasilakos, A game approach for cell selection and resource allocation in heterogeneous wireless networks, in IEEE/ACM Trans. Netw., to be published.

23. R. La and V. Anantharam, Optimal routing control: repeated game approach, IEEE Trans. Autom. Control, vol. 47, no. 3, pp. 437450, Mar. 2002.

24. S.-S. Byun, I. Balasingham, and A. V. Vasilakos, A market-clearing model for spectrum trade in cognitive radio networks, in MobiHoc 11: Proc. 20th ACM Int. Symp. on Mobile ad hoc networking and computing, Paris, France, May 2011.

25. M. A. Khan, H. Tembine, and A. V. Vasilakos, Game dynamics and cost of learning in heterogeneous 4g networks, IEEE J. Sel. Areas Commun., special issue on Game Theory in Wireless Communications, to be published.

26. A. Mackenzie, Game Theory for Wireless Engineers, 1st ed. Morgan & Claypool Publishers, May 2006.

27. F. Meshkati, A. Goldsmith, H. Poor, and S. Schwartz, A game-theoretic approach to energy-efficient modulation in cdma networks with delay qos constraints, IEEE Sel. Areas Commun., vol. 25, no. 6, pp. 1069 1078, Aug. 2007.

28. D. Niyato and E. Hossain, Integration of ieee 802.11 wlans with ieee

    802.16-based multichip infrastructure mesh/relay networks: A game theoretic approach to radio resource management, IEEE Network, vol. 21, no. 3, pp. 614, May-Jun. 2007.

29. L. Zhao, J. Zhang, and H. Zhang, Using incompletely cooperative game theory in wireless mesh networks, IEEE Network, vol. 22, no. 1, pp. 3944, Jan.-Feb. 2008.

30. T. Chen and S. Zhong, Perfectly fair channel assign ment in no cooperative multi-radio multi-channel wireless networks, Comput. Commun., vol. 32, no. 6, pp. 1058 1061, Apr. 2009

31. Y. Song, C. Zhang, and Y. Fang, Joint channel and power allocation in wireless mesh networks: A game theoretical perspective, IEEE J. Sel. Areas Commun., vol. 26, no. 7, pp. 11491159, Sep. 2008.

32. W. Yuan, W. Liu, and W. Cheng, Capacity maximization for variable width wlans: A game-theoretic

    approach, in ICC 10: Proc. IEEE Int. Conf. on Commun., Cape Town, South Africa, May 2010, pp. 15.

33. Z. Feng and Y. Yang, Characterizing the impact of partially overlapped channel on the performance of wireless networks, in Globecom 08: Proc. IEEE Global Commun. Conf., New Orleans, LA, Nov.-Dec. 2008, pp. 16.

34. , How much improvement can we get from partially overlapped channels? in WCNC 08: Proc. IEEE Wireless Commun. and Networking Conf., Las Vegas, NV, Mar.-Apr. 2008, pp. 29572962.

35. Monderer and Shapley, Potential games, Journal of Games and Economic Behavior, vol. 14, no. 1, May 1996, pp. 124143.

36. G. Arslan, M. Demirkol, and Y. Song, Equilibrium efficiency improvement in mimo interference systems: A decentralized stream control approach, IEEE Trans. Wireless Commun., vol. 6, no. 8, pp. 2984 2993, Aug. 2007.