# An efficient interference aware partially overlapping channel assignment and routing in wireless mesh networks.

1. IntroductionAs the technology nurtures the wide range of different gadgets, the number of clients utilizing Wireless Mesh Networks (WMN) for Internet access has also been increased to a large extent. This is because of the diverse applications provided by WMNs. A few of these samples are: military applications, Municipal Wireless Mesh Networks, public safety agencies and mining [1-3]. The network would work fine until the current frequency distribution is not disturbed in anyways. But it is also the necessity of the technology to host all the clients coming into the scope of a network, and maintaining the transparency at the same time. Interference plays a major role when the network comes into the picture of frequency sharing among many different clients. In order to avoid interference and fair bandwidth distribution [14], the number of clients accessing the network would have to be limited, and then there is no point in praising the technology. It is the technology which needs to be evolved at the right phase to overcome the interference, and provide the maximum utility to the network clients as well as taking care of unpredictable network scaling.

While the IEEE 802.11 standards, which were formed during 1990s, uses 3 non-overlapping channels of the frequency spectrum, and the remaining 8 channels are left unused. To suit the current network fan-out scenario, it is a must to utilize the available bandwidth effectively and efficiently. Using the multi-channel and multi-radio, it is possible to achieve the maximum performance, without bandwidth degradation. Multi-radio refers to a dedicated NIC assigned to each link on the mesh node and each link is assigned with a unique frequency (channel) for parallel data transmission.

In this paper, we work for the hybrid multi-channel and multi-radio Wireless Mesh Networks (MCMR-WMNs) that avoid interference to improve the network connectivity and enhance the throughput. The hybrid wireless mesh network is based on 3 tiers of devices: 1) the lowest tier includes Wi-Fi, Wi-Max, Cellular networks, conventional clients and mobile nodes. 2) The second tier includes routers that relay packets between the user and Gateway. 3) The highest tier is Gateway. Routers with gateway capability are connected to the internet with wired connection.

Interference is a threat behind utilizing the network bandwidth proficiently and achieving the effective throughput. In MCMR-WMNs, the key challenge is the interference [13] of simultaneous data transmission that will worsen the network parameters and sequentially the capacity of the network. Hence we concern minimizing the interference, improving throughput, and scaling the network by effectively assigning the available channels to the respective radios and then finding optimal path to the destination.

We consider IEEE 802.11b/g based wireless mesh network operating in 2.4 GHz frequency band. The IEEE 802.11b/g standard has a total of 11 frequency channels available for transmission, of which 3 are orthogonal channels. (Figure 1) Each channel of the spectrum specifies the center frequency used by the transceiver and the AP within the range; Channel 1 uses 2.412 GHz and channel 2 uses 2.417 GHz. The Guard band that separates two center frequencies is only 5MHz and the signal approximately make up to 22 MHz of the available frequency spectrum. This obviously leads to overlapping the adjacent channels which, when used for data transmission, causes interference and leads to collision of data. To use multiple channels of the available bandwidth, only one out of 5 consecutive channels can be employed simultaneously.

This proves that only 3 orthogonal channels are available, and can be used with the existing channel utilization techniques to prevent interference. A solution defined for this problem is the Partially Overlapped Channel (POC) assignment [12], where the channels can be selected with 2 other channels apart, and the two simultaneous transmissions are 10m apart. This also gives the same throughput in analysis [5], when compared with the existing nonoverlapping channel assignment technique. In a dense wireless mesh networks, using all the available channels that are assigned properly with spatial separation would result in a higher performance than the orthogonal channels.

The following sections of the paper are organized as follows. In Section II, we describe previous work in centralized and distributed channel assignment algorithms. Section III, elaborates the types of interference and its consequences on network parameters. The channel assignment with Partially Overlapped Channel model using edge coloring algorithms and Routing algorithm using SINR metric are explained in section IV. Section V elaborates simulation and performance evaluation. Finally we conclude our paper with summary of our findings and the future plan in section VI.

2. Related Study

There are number of channel assignment problems [15] that have been proposed to reduce interference and increase throughput. Most of the channel assignment algorithms are combined with either routing or congestion control techniques. A centralized load-aware channel assignment was proposed by Raniwala et al [6] which uses central controller. All information about traffic and routing paths are informed to the central controller; whereas in the model we propose, the gateway does not require any such knowledge for channel assignment except the set of active links. This centralized load aware [11] channel assignment is combined with routing algorithms.

JOCAC algorithms [7] assign channels, based on average congestion price on links. JOCAC is described as a network utility maximization problem and it can be implemented either in a distributed or centralized manner. In [4, 5], Mishra proved that the capacity of the network can be increased when both non-overlapped and POC are used for channel assignment. Authors demonstrated that good spatial re-use of same POC gives better performance. MMAC protocol [8] was proposed by J. So et al for controlling multi-channel assignment using a single transceiver. The MMAC protocol uses orthogonal channels and it uses two channels for data packets and one for control packets. Also power saving mechanism is integrated with MMAC protocol for efficient energy saving. In [9], authors used Load-Aware CAEPO, which uses partially overlapped channels along with orthogonal channels. They proposed grouping algorithm which selects one group leader within its interference range. Each group leader selects the best channel from the channels available. In [18], authors used CSROR which selects resource aware routing approach for packet dropping attacks. Q-SMS routing scheme [20] estimate residual capacity to make appropriate admission control decisions to provide QoS support in MANETs.

A good routing algorithm and routing metric mitigate and detect the interference experiences on the network. The traditional hop count metric may not give a good result in WMN, because it doesn't consider wireless link quality metrics such as packet loss rate, interference and load; it also gives equal consideration to all the links.

The Expected transmission count (ETX) metric of a link is calculated based on the number of attempts required to deliver packets successfully over a given link. ETX is computed for each link using delivery ratios of the link in both directions [16].

ETX = 1/[d.sub.f] x [d.sub.r] (1)

Where [d.sub.f] and [d.sub.r] are the forward and reverse delivery ratios. The [d.sub.f] is the probability measure of a data packet successfully reaches at the destination. The [d.sub.r] is the measured probability that the ACK of the packet is reached successfully. ETX does not take load, interference and data rate of link. So, it is suitable only for the single channel multi hop network and it doesn't suit for multi-channel multi hop network.

Expected transmission time (ETT) is better than ETX, as it considers data rate (bandwidth) of link into account. ETT of a link is defined as a bandwidth adjusted ETX [17]. Let S denote the packet size and B the bandwidth of the link. Then ETT is computed by

ETT = ETX x S/B (2)

The ETT does not explicitly consider the impact of traffic coming from other nodes. The disadvantage of ETT is that the contending traffic raises the loss rate of packet due to congestion, and it also decreases the available bandwidth.

The weighted cumulative expected transmission time (WCETT) [17] is designed to ameliorate the ETT metric. WCETT considers channel diversity, so it can be used in multi radio mesh networks. The WCETT metric of a path p is defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Where [X.sub.j] is the sum of the Expected transmission time values of links that are on channel j. k is the number of orthogonal channels and [alpha] is a tunable parameter subject to 0 [less than or equal to] [alpha] [less than or equal to] 1. WCETT enhances the performance of multi radio and multi rate wireless networks, compared to other metrics such as, hop count, ETX and ETT. The main disadvantage of WCETT is that it does not take the interflow interference into an account.

In [19], authors proposed Link Quality and MAC-Overhead Aware Predictive Preemptive Ad hoc On-Demand Multipath Distance Vector (LO-PPAOMDV) routing protocol, which is based on new metric combine two routing metrics (Link Quality, MAC Overhead). This routing algorithm finds congestion free routes using cross layer approach.

Many types of link metrics have been proposed in WMN to minimize interference and load on the link. Each link metric has some advantage and limitation, and gives better results in particular environment. In our work, the first proposal is that the channel assignment problem using the graph edge coloring method and we propose a new routing metric called signal-to-noise plus interference ratio (SINR) value which measures interference in each link and then routing algorithm works based on the interference information.

3. Interference

Interference plays a vital role in WMNs, which will lead to undesirable consequences. Concurrent transmissions of nodes situated close to each other in WMN increases interference and reduce the network throughput. The interference degrades the capacity of the network. For a restricted-bandwidth continuous-time stochastic channel that may endure noise, Shannon-Hartley Theorem provides the channel capacity (in bps)

C = Blog(1 + [S/N]) (4)

Where B is the channel bandwidth (in Hertz) and S/N is the signal-to-noise ratio. This theorem also helps to discern the different types of interferences. Consider four nodes [X.sub.1], [X.sub.2], [Y.sub.1] and [Y.sub.2]. Let [X.sub.1] and [X.sub.2] be sending nodes and [Y.sub.1] and [Y.sub.2] be receiving nodes. All four nodes are situated within the interference range of each other.

3.1 Co-Channel Interference

Co-channel interference is generated when two different communicating pairs of nodes within the transmission range of each other that use the same channel simultaneously as shown in figure 2. Consider [X.sub.1] - [Y.sub.1] and [X.sub.2] - [Y.sub.2] are assigned to channel 6 and following are the sequence of events: Node [X.sub.1] wants to send data to [Y.sub.1]. It senses the medium (Channel 6) and checks if it is busy or idle. In the event of the medium is busy, the node will wait for its transmission. If the medium is idle, it will start the data transmission. When [X.sub.1] is sending data to [Y.sub.1] and at the same time [X.sub.2] also tries to send a data to [Y.sub.2], applying the same medium sensing procedure. In this case, the medium (Channel 6) will be busy. Hence, [X.sub.2] waits for a back-off period and keep attempting till the data transmission between [X.sub.1] and [Y.sub.1] is completed. When [X.sub.2] identifies the medium as free, it proceeds in transmitting the data. The CSMA/CA Co-channel interference is less harmful compared to adjacent channel interference.

3.2 Self-Interference

Self-Interference is caused when two different nodes connected to a common node, assigned with same frequency as shown in figure 3. Consider [X.sub.1] is sending packet to [Y.sub.1] and [Y.sub.2] simultaneously and the node [X.sub.1] is equipped with two radios. If both the interfaces are assigned to channel 6 and [X.sub.1] attempts to simultaneously transmit packets on both the NICs. In this case, the interference will be severe, irrespective of the distance of the receiving node whether it is located near or far. If mutually orthogonal channels are assigned to links in a single node, self-interference can be avoided.

3.3 Adjacent channel Interference

Adjacent channel interference occurs when the frequency of one transmission partially overlaps with the neighboring channel as shown in figure 4. Consider [X.sub.1] - [Y.sub.1] and [X.sub.2] - [Y.sub.2] are assigned to channels 6 and 8, respectively. [X.sub.1] starts transmitting first, [X.sub.2] will notice the medium as free in channel 8 and also begins to transmit its packets. Since the channel 6 and 8 share the frequency band, the receiving nodes [Y.sub.1] and [Y.sub.2] can't decode the packets correctly, causing a transmission error that severely decreases the network throughput.

4. System model

The Figure 5 illustrates the relationship between the components used in our framework; it shows how the data flows among the components and the interaction between the Channel assignment and routing algorithms using SINR computation. The interference of each link is calculated during the channel assignment and this information is stored into the interference database. In our work, the channel assignment is completed before the routing algorithm is processed, and the channel assignment algorithm can greatly minimize the interference by simultaneous transmission which aids the routing algorithm to divert traffic between nodes. The Channel assignment and routing problem can be combined together and optimized jointly to improve overall network performance. The impact of the interference can be controlled using routing metric and algorithm.

4.1 Channel Assignment Algorithm

The efficiency of channel assignment primarily depends on the number of simultaneous transmissions in WMN and the number of simultaneous transmissions is limited by interference. The problem of reducing the signal interference and collision is represented as a graph coloring problem. Adjacent edges in the graph are assigned different colors and different channels will be allocated from 1 to 11. The physical graph of wireless mesh network in concern is represented as an undirected graph G = (V,E); where V represents set of wireless routers, and E represents undirected edges between wireless mesh routers. We represent this channel assignment problem as an edge coloring problem of graph theory.

Definition 1: For an undirected graph G, conventional edge coloring algorithm assigns colors to the edges of G in such a way that no two adjacent edges are assigned with same color.

Definition 2: For an undirected graph G, strong edge coloring algorithm assigns colors to edges of G in such a way that no two edges in the neighborhood of utmost 2 hops is assigned with same color.

Chromatic Index: The chromatic Index (K) of the graph G is the minimum number of colors required to color the edges of a graph.

We assume static mesh routers each equipped with multiple radios. The transmission power of every mesh node is assumed to be the same. Since we use IEEE 802.11 b/g standard, the total number of available channels are 11. The mesh gateway node is assigned with the responsibility of assigning channel to the mesh routers, which first constructs a physical graph G and a set of active links A. If a link e connecting the nodes u and v, needs to be assigned to a channel c; it computes the total signal to noise plus interference ratio, with respect to the channel c for both the nodes. This process repeats for all 11 channels. Whichever channel provides the minimum value of interference will be chosen for the assignment. Initially it assigns channel (colors) to links connected to the mesh gateway. Each time, nodes at a particular distance are selected and the edges linked to them are given a color. In this paper color and channel are used interchangeably.

Algorithm: Channel Assignment Using graph Edge Coloring Method Input: Let G = (V, E) denote the network V = Set of routers E [member of] V X V is the set of undirected edges Let A = (V, [E.sub.A]) Sub-graph of G selected by the algorithm. Output: Channels assigned to edges present in A 1. Let K = List of available channels (K = 11) 2. Let [u.sub.i] = Root of the mesh network for i = 1 to N 3. Let h = Number of edges incident on [u.sub.i] from A 4. For all edges e [member of] [E.sub.A] do 5. Color(e) = 0 6. while count [not equal to] h + 1 do 7. for i = 1 to N do 8. AssignColor (A, G) Procedure AssignColor (G1 = (V1, E1) G2 = (V2, E2)) 1. for i = 1 to N do 2. if [there exists] orthogonal channel c [member of] K, then color the edges of [u.sub.i] 3. continue 4. for i = 1 to [parallel] uncolored edges attached to [u.sub.i] in G1 [parallel] do 5. let l be uncolored edge attached to [u.sub.i] 6. c1 = Least interference color not used by links in G2. 7. c1 is selected based on signal-to-noise interference calculation 8. Assign c1 to link l 9. if such color does not exist, then color with minimum interference is greedily assigned to link l.

Vizing's theorem computes the number of colors in the edge-coloring problem of every undirected graph using at most one larger than the maximum degree d of the graph. Misra and Gries [10] describe an NP-complete algorithm for coloring edges of any graph with d + 1 colors, where d is the maximum degree of the graph.

The edge coloring algorithm assumes that there are N routers present in the network and it stores interference value in database for each link. Initially each link is assigned with zero which indicates the uncolored edge.

4.2 Complexity of Edge Coloring

The graph in figure 6 is a Line graph and doesn't consist of loops. The graph doesn't contain any parallel or multiple edges. It is a simple graph with no pair-wise intersecting edges. There exist a finite number of colors to completely color the connection graph.

Facts: 1. Every line graph is claw-free. 2. A r-regular line graph is NP-complete given r is odd. A clique graph can be constructed by treating each maximal clique as equivalent of a vertex of the graph.

[section] The connection graph in figure 6, the edge coloring problem is NP-complete. This is a simple graph with every vertex of maximum degree 4. We need to prove the following lemma to conclude the NP-completeness of the problem.

Lemma: Let G be a simple, connection graph, v be a vertex, [contains as member] v and every vertex including v have degree [less than or equal to] 4. If G-v is 4-edge colorable, then so is G.

Proof of Lemma: Assume G-v is 4-edge colorable. Define [X.sub.i] (i = 1, 2, 3, 4) as the list of neighbors of v not assigned by color "i.". Therefore the 4-edge coloring of G-v is

Min [4.summation over (i=1)] [[absolute value of [X.sub.i]].sup.2] (5)

subject to the constraints [absolute value of [X.sub.i]] = 1, 1 [less than or equal to] i [less than or equal to] 4

If G-v is not 4-edge colorable, then

[4.summation over (i=1)][absolute value of [x.sub.i]] = 2 * degree(v) - 1 < 2 * 4 (6)

[??][4.summation over (i=1)][absolute value of [X.sub.i]] < 8 [??] [there exists]i & j [contains as member] [absolute value of [X.sub.i]] = 0 & [absolute value of [X.sub.j]] [greater than or equal to] 4 (7)

Define H [DELTA](G - v) such that all edges colored by i or j are contained in G. For any vertex not in [X.sub.i], the connected component of H containing that vertex must be a path. Interchange the color of [X.sub.i] and [X.sub.j] => [[absolute value of [X.sub.i]].sup.2] + [[absolute value of [X.sub.j]].sup.2] becomes smaller => contradiction => G-v is 4-edge colorable. Without loss of generality, assume [X.sub.k] = {u} and G' [DELTA] G obtained by detecting the edge of uv and the edges of color 4. This implies that G'-v is 4-1 = 3 colorable and deg[v.sub.G'] [less than or equal to] 3 and deg[v'.sub.G'] [less than or equal to] 2 is 3 colorable by induction.

Reconstructing the edges deleted earlier and assigning color4 to the edge uv, G achieves 4-edge coloring.

The Theorem: [there exists] ([DELTA]G -1) edge coloring algorithm in O([n.sup.2]) time of the connection graph in question.

Proof: Need to show that, for any simple graph G, [DELTA]G [less than or equal to] [gamma](a) [less than or equal to] [DELTA]G + 1 Where [gamma] is the chromatic index.

Let k = [DELTA]G + 1 (k = 4 in our case), therefore any vertex of G satisfies the lemma above

* Edges from G can be eliminated one by one until only one edge if left => the resulting graph is K-edge-colorable clearly.

* If n is the number of vertices, we have ([DELTA]G + 1), edge-coloring algorithm in O([n.sup.2]) time. Merging the vertices of degree [less than or equal to] [[DELTA]G/2] implies [DELTA]n = O(m), where m is no of edges => the edge coloring algorithm runs in O(nm) time.

This concludes that the problem is NP-Complete for our connection graph.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the transmission power of node [X.sub.1]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote channel gain for nodes [X.sub.1] and [Y.sub.1], which depends on the distance between nodes [X.sub.1] and [Y.sub.1] and path loss index. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the thermal noise at the receiver [Y.sub.1]. The SINR at receiver [Y.sub.1] is given by

[SINR.sub.X1Y1] = [P.sub.X1][G.sub.X1Y1]/[N.sub.Y1] + [summation over Z1[not equal to](X1,Y1)][P.sub.Z1][G.sub.Z1Y1] (8)

In this model, the available channel (color) is 11 means that K = 11. For square topology (figure 10) if K = 4, then the edge coloring problem is NP-complete. In random topology, nodes located close to each other, so nodes get more interference compared to square topology. Even though chromatic index for random topology is three, because of the interference as the algorithm uses 11 channels.

The part of the random topology is selected to show the interference aware edge coloring in figure 7. The channel 9 assigned to link L1. So, the channel 9 cannot be given to links L2, L3, L4, L5 and L6 because they are within the interference range. For random topology (figure 9) if K = 11, then strong edge coloring problem is deterministic and colorable by finite number of colors by Vizing's theorem.

4.3 Routing based on SINR computation

In Traditional shortest path routing, the shortest route between the source and destination is determined based on the length of the path. The good routing protocol has to compute the shortest path which satisfies the following criteria: minimum path length, minimum end-to-end delay and maximum data rate. The good routing metric should be able to measure the link qualities and then helps the routing protocol in meeting the criteria. The design of a new routing metrics for wireless networks is challenging due to the fact that the wireless links are having the following unique characteristics:

Packet loss: If two communicating nodes are located with greater distance or any obstacle in the environment, then it leads to channel fading and increased loss ratio in links. Packet loss causes more delay and reduces the throughput.

Packet transmission rate: Based on the load and loss ratio on wireless link, Packet transmission rate may vary from time to time.

Interference: IEEE 802.11b/g standard operating in 2.4GHZ unlicensed spectrum may suffer from interference external to the wireless network such as microwave ovens and Bluetooth. Also, data transmission on one link may interfere with transmission in neighbouring links. Therefore, the routing metric should capture both inter-flow and intra-flow interferences, to choose the interference free path for routing packets.

The protocol interference model is used widely to obtain the interference information and it can be easily applied in theoretical analysis. But the protocol interference model is not perfect when compared with the physical interference model. The SINR is based on the physical interference model and it is particularly based on the exact transceiver design of systems. But, it is quite complex and difficult to apply in graph theory based algorithms. In spite of the complexity, the SINR model fetches good accuracy in interference calculation. Hence, the signal-to-noise plus interference ratio is proposed as a new routing metric to find interference on a wireless link. The SINR value is considered as link cost in routing algorithms. Our objective is to reduce the total cost of routing and at the same time to ensure that the total load on each wireless link is less than its capacity.

Using the channel assignment based on the graph coloring, the significant amount of reduction in the interference observed on simultaneous transmissions. In general, Routing from source (end-user) to destination (gateway) may take multiple hops, and the Mesh Gateway is connected to internet which provides broadband access to the source (end-user). The routing algorithm retrieves the topology from the channel assignment algorithm to accurately estimate the cost of the link. The SINR value of each link is calculated and stored into the database. The routing algorithm retrieves the SINR information from the database and the shortest route is constructed based on the least interference path.

4.4 Problem Formulation

The channel assignment algorithm is used as an input to the SINR based routing and the routing algorithm finds the best route from the user to any one of the gateway. A good routing protocol has to find an optimal path with in short span of time and it should also reduce the update frequency into the routing table to efficiently manage the network resources. It must be able to guarantee some level of quality of service. Note that, the considered grid topology consists of two gateways. If the value of SINR is high, then it indicates that there is a low interference in that link. The cost of each link is estimated from the SINR computation (Eq.6) and the capacity of each link is represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The capacity is calculated using Shannon's formula given in the equation

4. The flow of data from node [X.sub.1] to its neighbour [Y.sub.1] over wireless link ([X.sub.1], [Y.sub.1]) is represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

The channel gain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is estimated by a commonly used model [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the physical distance between nodes [X.sub.1] and [Y.sub.1] and a is the path loss index. The SINR threshold is represented by [beta].

The cost of each link is estimated by interference experienced on that link as a result of simultaneous transmission and noise. The higher SINR value the better the quality of the link. Therefore, our objective is to maximize the SINR value and using the SINR based routing to deliver all the packets transmitted to gateway by the end user nodes, without exceeding the capacity of the link. The Routing problem is represented as follows:

Max [summation over (X1,Y1)] [SINR.sub.X1Y1] (10)

Subject to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

0 [less than or equal to] [f.sub.X1Y1] [less than or equal to] [C.sub.X1Y1] (12)

[f.sub.X1Y1] [member of] [Z.sup.+] (13)

Where [d.sub.x1] represents the data rate at which packets are produced at node [X.sub.1] per seconds. The equation 11 ensures flow maintenance at each node. Second constraint (Eq. 12) ensures that the flow of data on a link should not exceed its channel capacity. Third constraint specifies that the packet flow is an integer value. When only the topology information is considered, the context is reduced to interference aware edge coloring problem. To provide fair and efficient solution, the second constraint compares the traffic on wireless link with available capacity.

Algorithm: Proposed routing algorithm Input: Network topology, active links and the SINR value from the database Output: Shortest path from end users to WMN Gateway Algorithm 1. Read network configuration and set of active links from the channel assignment. 2. Set cost of all links to zero. 3. Read SINR value from the interference database. 4. Covert SINR value to the link cost and assign the cost to link. Minimum cost of any link is [beta] threshold (value 1). 5. Find the route to any one of the gateway (destination). 6. If more than one gateway nodes are available, and then find the route with a least interference. i.e. Optimal route. 7. If not, then the route is established with gateway.

Table 1 shows link cost estimation based on measured SINR values. In Figure 8, algorithm of proposed SINR based routing is represented.

5. Simulation

5.1 Simulation Results: Channel assignment algorithm

NS2 based simulation is used to simulate the Interference Aware Edge Coloring problem. The NS2 version NS2.33 and, the patch for multi-channel multi-radio is included. Diverse types of topologies like square, random were used in the simulation, and the comparison of the orthogonal channel inputs with POC inputs were observed. The area dimension for our simulation is within 1000m x 1000m flat grid topology. The physical distance between two nodes is 200m in square topology; the transmission range is 250m for all the nodes and the interference range is 550m. But, the random topology distance between two nodes can differ randomly. Each node is equipped with multiple radios and data transmission rate is 11Mbps. The thermal noise power is set to -90 dB; The Beta threshold is set to -16dB and the packet size is set to 1000bytes. Free space path loss model is used to predict signal strength. At -10 dB, network performance is optimal. The simulation was performed in 300s and the traffic types used in our simulation are Ftp and Cbr.

To evaluate the channel assignment algorithm, the network throughput and the aggregate network capacity were evaluated. In Figure 11, the network throughput for the number of radios is compared and it has been observed that, the Interference Aware Edge Coloring channel assignment using 11 channels demonstrated the better throughput with spatial channel re-use. This shows that our method delivers the maximum throughput with more number of channels. When the number of radios and channels are increased, the network throughput also increased. Figure 12 shows, the aggregate network capacity for WMN. As the network capacity is increased dramatically after 5 channels, this clearly demonstrates that POC increases overall network performance in wireless mesh networks.

5.2. Simulation results of Routing using SINR

We have used grid topology consists of 16 nodes shown in figure 13 for interference aware routing. AODV routing algorithm is modified to use SINR value as a link metric instead of hop count to find the shortest route. When the source desires to transmit data to the destination but does not already contain the path to destination in its routing table, then it starts route discovery process. As part of the discovery process, the source sends route request packets (RREQ) throughout the network.

The route request packet contains the link cost from the database, a RREQ identifier, the originator address, the originator sequence number, the destination address and the destination sequence number. The link cost contains the cost to travel from the source node to the next hop and it also contains the total cost that RREQ packet has traversed so far. To uniquely identify a route request, the RREQ ID is combined with the source address. It ensures that RREQ packet is rebroadcasted only once, even though the node accepts the RREQ multiple times from its neighboring nodes. When the node receives the RREQ packet, it sends the route reply (RREP) back to the source node if it is the destination with sequence number equal to or greater than that contained in the RREQ. If the node has valid path to the destination, then it generates RREP packet to the source node. Otherwise, the node rebroadcasts the RREQ packet.

The source address and RREQ ID are verified to ensure that the RREQ packet has been received already. If it is received already, the packet is rejected. Upon reception of the RREP packet, the node will update or create its path to the destination. The link cost is updated and RREP packet will be forwarded to the source node. Finally, the source node will receive the RREP packet, if path exists from the source node to the destination. The data packets are transmitted to the destination on the discovered path.

When the link break happens, the upstream node propagates the RERR packets to the source node. Upon receiving the RERR, the source will reinitiate route discovery process.

We assume nodes 0 and 2 are gateways and the end-users are connected to router 14 and 9, the routing algorithm calculated shortest path as shown in figure 13. The routing algorithm finds route 9-8-4-G0 and 14-15-11-7-3-G2 as optimal and less interference path based on the SINR value. The shortest path 14-10-6-G2 based on the minimum hop count experiences higher interference level, packet drops may happen compared to the optimal path 14-15-11-7-3-G2. Nodes 1, 5, 6, 9 and 14 are assumed as sources and optimal path to the Gateway is given by:

The performance of routing algorithm is compared with the ETX and ETT metrics as benchmarks. We evaluate the following metrics, to verify the performance of SINR routing:

1) Packet delivery ratio2) End-to-End Delay3) Routing Overhead.

The simulation results of routing algorithm is shown in figure 14, 15 and 16. Packet delivery ratio is estimated by counting the number of packets delivered successfully to the destination. In figure 14, the packet delivery ratio for number of channels is compared. It must be noted that the packet delivery ratio is increasing as the number of channel increases and maintains the same PDR after 4 channels. 90% of the packets delivered to the destination when the SINR metric is used in Multi-Channel WMN. End-to-End delay is the average delay it takes for a data packet to travel from the source to the WMN gateway.

Figure 15 shows how end-to end delay changes against the number of channels. It includes the delay made by the route discovery process and the queue delay. The routing overhead generated by our routing algorithm is shown in figure 16. It shows how many times the packets are retransmitted due to the interference on routing path. The routing overhead is estimated by number of retransmission needed per connection between an end user and WMN Gateway. The simulation results in Figure 16 show that our method requires lesser retransmissions compared to other two metrics. Hence, the shortest path estimated using our SINR interference method is more reliable.

6. Conclusion

This work presents joint channel assignment and routing in Wireless Mesh Networks which uses the POC in addition to the orthogonal channels and a new routing metric called signal-to-noise plus interference ratio (SINR) value. We considered the channel capacity constraints for each traffic flow. From the simulation, we conclude that, Partially Overlapped Channels can improve the overall performance of the network. Moreover, the comparison with ETX and ETT shows the performance and the effectiveness SINR metric and the proposed method. The frequency band of IEEE802.11b/g is to be completely utilized. This method supports more number of parallel transmissions. In future, we are planning for the following cross layer framework: 1) Physical/Transport Cross layer design to adjust the transmission rate of the source to avoid congestion in the network. 2) Network/Transport Cross layer design to support traffic engineering.

References

[1] "http://www.tropos.com/solutions/Municipal_Utilities. html".

[2] "http://www.meshdynamics.com/documents/Mesh_Mini ng_July08.pdf".

[3] "http://www.tropos.com/solutions/Federal.html".

[4] A. Mishra, E. Rozner, S. Banerjee, W. Arbaugh, "Exploiting partially overlapping channels in wireless networks: turning a Peril into an advantage," in proceedings of the 5th ACM SIGCOMM Conference on Internet Measurement (IMC '05), USA, pp. 1-6, 2005.

[5] A. Mishra, V. Shrivastava, S. Banerjee, W. Arbaugh, "Partially overlapped channels not considered harmful," in ACM SIGMETRICS '06/Performance '06 Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems, USA, pp. 63-74, 2006.

[6] A. Raniwala, K. Gopalan T. Chiueh, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks," ACM SIGMOBILE Mobile Computing and Communications Review, Vol.8, pp. 50-65, 2004.

[7] Mohesenian Rad and Wong, "Joint Optimal Channel Assignment and Congestion Control for Multi-Channel Wireless Mesh Networks," IEEE International Conference on Communications, Istanbul, pp.1984-1989, 2006.

[8] J. So and N. H. Vaidya, "Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver," in MobiHoc '04: Proceedings of the 5th ACM International Symposium on Mobile adhoc networking and computing, USA, pp.222-233, 2004.

[9] Yuting Liu, R. Venkatesan, and Cheng Li, "Load-Aware Channel Assignment Exploiting Partially Overlapping Channels for Wireless Mesh Network," in IEEE proceedings of Global Telecommunications Conference (GLOBECOM 2010), Miami, FL, pp. 1-5, 2010.

[10] Misra J. and Gries, D. "A Constructive Proof of Vizing's Theorem." Information Processing Letters 41, pp. 131-133, 1992.

[11] F. Kaabi1, S. Ghannay2, and F. Filali, "Channel Allocation and Routing in Wireless Mesh Networks: A survey and qualitative comparison between schemes". International Journal of Wireless and Mobile Networks(IJWMN). Vol. 2, No. 2, pp. 132-150, 2010.

[12] A. Antony Franklin, Vibhav Bukkapatanam, C. Siva Ram Murthy: "On the end-to-end flow allocation and channel assignment in multi-channel multi-radio wireless mesh networks with partially overlapped channels." Elsevier Journal on Computer Communications, Vol. 34, Issue 15, pp. 1858-1869, 2011.

[13] Wooseong Kim, Mario Gerla, "Cognitive multicast with partially overlapped channels in vehicular ad hoc networks," Elsevier Journal on ad hoc Networks, Vol 11, Issue 7, pp. 2016-2025, 2012.

[14] Aizaz U Chaudhry, Nazia Ahmad, Roshdy HM Hafez, "Improving throughput and fairness by improved channel assignment using topology control based on power control for multi-radio multi-channel wireless mesh networks", EURASIP Journal on Wireless Communications and Networking, 155,2012.

[15] Ashraf Alzubir, Kamalrulnizam Abu Bakar, Adil Yousif and Albarraa Abuobieda. "Article: State of The Art, Channel Assignment Multi-Radio Multi-Channel in Wireless Mesh Network," International Journal of Computer Applications, Vol. 37, No.4, pp.14-20, January 2012.

[16] D.S.J. Couto, D. Aguayo, J. Bicket, and R. Morris. "A High-Throughput Path Metric for Multi-Hop Wireless Routing," ACM MOBICOM Conference, USA, pp.419-434, 2003.

[17] R. Draves, J. Padhye, and B. Zill. "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks," ACM MOBICOM conference, USA, pp. 114-128, 2004.

[18] Khan, S. K-K Loo "Cross layer secure and resource aware on demand routing protocol for hybrid wireless mesh networks," Spring Journal of Wireless Personal Communications, Vol.62, pp.201-214, 2012.

[19] Moussa Ali cherif, Mohamed Kamel Feraoun, Sofiane Boukli Hacene, "Link Quality and MAC-Overhead Aware Predictive Preemptive Multipath Routing Protocol for Mobile Ad hoc Networks," International Journal of Communication Networks and Information Security(IJCNIS), Vol. 5, No. 3, pp. 210-218, 2013.

[20] Haseeb Zafa, David Harle, Ivan Andonovic, Laiq Hasan, Amjad Khattak " QoS-aware Multipath Routing Scheme for Mobile Ad Hoc Network," International Journal of Communication Networks and Information Security (IJCNIS), Vol. 4, No. 1, pp. 1-10, 2012.

Sarasvathi V (1), N.Ch.S.N. Iyengar (2) and Snehanshu Saha (3)

(1) Department of Computer Science and Engineering, PESIT Bangalore South Campus, Bangalore-560100, India

(2) School of Computing Science & Engineering, VIT University, Vellore-632014, Tamilnadu, India

(3) Department of Computer Science and Engineering, PESIT Bangalore South Campus, Bangalore-560100, India

sarasvathiram@gmail.com, nchsniyengar48@gmail.com, snehangshu.saha@gmail.com

Table 1: Link cost estimation based on SINR Value Delivery rate Link Cost SINR [greater than or equal to] -16dB 90-100% 1 SINR -10dB to -15dB 79-90% 3 SINR -8dB to -10dB 50-79% 5 SINR < -8dB 0-49% 10

Printer friendly Cite/link Email Feedback | |

Author: | V, Sarasvathi; Iyengar, N.Ch.S.N.; Saha, Snehanshu |
---|---|

Publication: | International Journal of Communication Networks and Information Security (IJCNIS) |

Article Type: | Report |

Date: | Apr 1, 2014 |

Words: | 6757 |

Previous Article: | Predictive preemptive certificate transfer in cluster-based certificate chain. |

Next Article: | Uplink channel allocation scheme and QoS management mechanism for cognitive cellular-femtocell networks. |

Topics: |