Static & Dynamic Channel Assignment for Interference Analysis in Wireless Mesh Networks

Static & Dynamic Channel Assignment for Interference Analysis in Wireless Mesh Networks

Revathi M

PG student -Communication Systems Jayaram College of Engg & Tech Trichy,India

Mrs. Deva Priya S Associate Professor, ECE Dept, Jayaram College of Engg & Tech

Trichy, India

Abstract This paper used to adapt the physical and protocol model which is used to analyze the interference characteristics in multihop wireless networks. The Physical model which is used as a reference model for Physical layer behavior which treat the interference as noise, but it is limited by its complexity. The Protocol model is simple but it produces an infeasible solution. The Reality Check a new mechanism which is introduced to produce a feasible solution for the protocol model and used to calculate the maximum interference range. In order to minimize the interference channel assignment is used in routers with multi- radios, wireless mesh networks which uses the Multi-Radio conflict graph. The channel assignment scheme used is BFS-CA, Breadth First Search channel assignment, which is used to minimize the interference in wireless mesh networks.

Key WordsBreadth First search channel assignment, Multi radio conflict graph model, Physical model, Protocol model, Reality check

1. INTRODUCTION

   Physical and Protocol model are two widely used models to characterize the interference relationship in wireless networks. The physical model also called as the signal to interference and noise ratio model, which is based on the practical transceiver in communication systems that treat the interference as noise. Under this model a transmission is successful if and only if SINR should exceed a certain threshold at the receiver. The rate calculation is based on the Shannons capacity formula which takes into account the interference due to simultaneous transmissions by other nodes. The physical model is the accurate representation of the physical layer behavior. The difficulty associated with the physical model is its computational complexity in obtaining the solution, when it involves in the cross layer optimization.

   model is widely used to characterize the physical layer behavior. Under the protocol model a transmission is successful if and only if when the intended receiving node fall inside the transmitting range of the transmitting node and falls outside the interference range of the other non intended transmitter. The setting of the transmission range depends on the signal to noise ratio threshold. The setting of the interference range is rather heuristic.

   If we consider the first case if the receiving node falls inside the interference range of the non intended transmitter the node cannot receive correctly from the transmitter due to interference. But based on the capacity formula there exists some capacity even in the interference. If we consider the second case when the node falls outside the interference range of the other non intended transmitter the protocol model assumes that there is no interference but there exists small amount of interference from other transmitters and the aggregate of these interference is not a negligible in achievable rate calculation. So the Protocol model produces an infeasible solution. Reality check mechanism is used to produce a feasible solution for the protocol model under the scheduling and power control used in the physical model.

   To minimize the interference between the routers with multiple radios in wireless mesh network we use BFS-CA scheme which consider the Multi-radio conflict graph model.

2. SCHEDULING AND POWER CONTROL

   Scheduling can be done in frequency domain if the available spectrum is divided into sufficiently large number of small bands. Scheduling can also be done in time domain if the time frame is divided into sufficiently large number of time slots. If we consider the scheduling in frequency domain, denote

   But in the cross layer optimization SINR is a non convex function with respect to the transmission power. As a result a solution to the cross layer optimization using the physical

   =

   1 (1)

   0

   model is difficult to develop. Most of the current approaches to cross layer optimization, which uses physical model follow a simplified layer by layer or layer decoupled approach and produce a sub optimal solutions or instead focus on providing asymptotic lower and upper bounds.

   Then, for a band m Mi, node i cannot use it for transmission or reception from multiple nodes. Due to self interference node I cannot use it for both transmission and reception. Putting these constraints together, we have,

   + 1 , (2)

   To overcome the complexity issue associated with the physical model, the protocol model also called as a disk graph

   i

   Where T m is the set of nodes that are within the maximum

   , , (8)

   transmission range from node i on band m.

   Denote as the transmission power at node i when node

   i transmits the data to node j on band m. when node i does not

   m

   1

   (9)

   transmit the data to node j on band m pij should be 0. The

   maximum allowed transmission power limit Pmax on one band,

   Where dij is the physical distance between nodes i and j, R max

   we have

   and RI

   max

   T

   j

   maximum transmission and interference range

   , , (3)

   respectively, and Im is the set of nodes that may contribute

   towards nonnegligible interference at node j. For a successful

   Denote Pi the maximum total transmission power at node i on all bands. We have Pi Pmax and,

   transmission the interference from any other transmitter is considered negligible under the protocol model and the

   (4)

   achieved rate is

   = log 2 1 + (10)

   1. Scheduling the feasibility constraints under the Physical Model

      Under the physical model a transmission is successful if and only if the SINR at the receiving node exceeds a certain threshold . For the transmission from node i to node j on band m, the SINR at node j is,

      When the transmission power Pmax is used at node i,this node has the maximum transmission range RTmax which can be computed based on the minimum required receiving power at the receiving node j. when the transmission power p is less than Pmax, the same minimum required receiving power should

      =

      (5)

      be met. If node I can transmit to node j on band m. the

      + , ,

      transmission range is given by,

      m

      where is the ambient Gaussian noise density, g is the propagation gain from nodes i to j, and Tk is the set of nodes to which node k can transmit on band m.

      = 1

      (11)

      Under the physical model, a transmission from nodes i to j on band m is successful if and only if SINR at node j

      exceeds a threshold . Then we have,

      Which is a function of transmission power p. similarly the

      interference range is

      , , (6)

      = 1

      (12)

      hich is the sufficient and necessary condition for successful transmission under the physical model.

      For a successful transmission the achievable rate by this sijm is at most

      = log2 1 + , , (7)

3. A REALITY CHECK MECHANISM FOR PROTOCOL MODEL SOLUTION

   Protocol model produce infeasible solution. Reality check mechanism which is used to obtain a revised solution for the protocol model which is feasible. Under the protocol model,

   the impact of interference from neighboring nodes is binary

   and is solely determined by whether or not the node falls

   The actual data rate depends on several other parameters such as modulation, coding schemes, BER constraints, detector schemes and will be lower than that obtained by Shannon capacity formula

   1. Scheduling Feasibility constraints under the Protocol Model

      Under the protocol model, a transmission is successful if and only if the receiving node is within the transmission range of the intended transmitting node and is outside the interference range of each nonintended transmitting node. When power control is employed at each transmitting node, the transmission range and interference range can be varied and different from others. As a result the interference relationship among nodes become more complicated. The conditions for successful transmission from nodes i to node j with an interfering transmission from nodes k to h can be formulated as:

      within the interference range of non-intended transmitter. However, as nonzero interferences are neglected achievable rate calculated under the protocol model may be larger than the actual achievable rate. So the solution obtained under this model may not infeasible in practice, the results based on the protocol model may be incorrect. To find out the actually achievable result under the protocol model solution, it is necessary to go through the validation process. Reality check is a mechanism for a protocol model solution, the goal of this is to produce an achievable result. Reality check can also be viewed as a revised result based on the given protocol model solution.

      For a given protocol model solution, the knowledge of scheduling and power control for each node in the network is known. Under Reality check instead of using achievable rate computed by (10) which neglects the impact of interference we use (7) to recompute the achievable result to

      obtain a feasible routing solution. This new routing along the original power control and scheduling offer a feasible solution.

      Reality check result is defined as the achievable objective for a given protocol model solution.

4. WIRELESS MESH ARCHITECTURE

Figure.1 Wireless Mesh Architecture

Depending on the number of radios at each mesh router, the routers are classified into two categories: (1) Multi-Radio mesh routers (MRs); and (2) Single-Radio mesh routers (SRs). Each MR and SR in the network be equipped with one radio, called the default radio, and tuned to the same channel .At least one router in the mesh is designated as a gateway. The gateway is used to connect with an external network. Access Points (APs) is used to connect with the user devices and are collocated with mesh routers.

A majority of the traffic inside the mesh is either from the user devices to the gateway or from the gateway to the user devices. This traffic pattern is typical in wireless mesh deployments. Because the traffic pattern is skewed to-and- from the gateway, the resulting traffic pattern form a tree structure in which the gateway is the root and the user devices are the leaves. Traffic flows will likely aggregate at routers close to the gateway. Therefore, in order to increase overall network throughput, it is preferable to place MRs close to the gateway and in regions of the mesh that are likely to experience heavy traffic.

The Channel Assignment Server (CAS), which is co- located with the gateway in the figure, performs channel assignment to radios uses multi radio Conflict graphs to model the interference.

1. INTERFERENCE MODELING

   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 the 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.

   As an example of a conflict graph, Figure shows the topology of a network with four nodes. Each node in the figure is labeled with its node name and its number of radios. Figure 2(b) shows the conflict graph. At a first glance, the problem of assigning channels to links in a mesh network

   appears to be a problem of vertex coloring the conflict graph. However, vertex coloring fails to assign channels correctly because it does not account for the constraint that the number of channels (colors) assignable to a router must be equal to its number of radios As an example of a conflict graph, Figure 2(a) shows the topology of a network with four nodes. Each node in the figure is labeled with its node name and its number of radios. Figure2(b) shows the conflict graph. At a first glance, the problem of assigning channels to links in a mesh network appears to be a problem of vertex coloring the conflict graph.

   However, vertex coloring fails to assign channels correctly because it does not account for the constraint that the number of channels (colors) assignable to a router must be equal to its number of radios

   Figure.2

   Network Topology with varying Channel Assignment

   As an example of why this is the case, let us assume that the four vertices in the conflict graph shown in Figure2(b) are each assigned one of three different channels using a vertex coloring algorithm. This means that the two radios represented by each vertex in the conflict graph operate on the frequency assigned to that vertex. This implies that node C in the illustrated network operates on three different channels, which is impossible because it is equipped with only two radios.

   Figure2(c) shows the multi-radio conflict graph of the network. In the figure, each vertex is labeled using the radios that make up the vertex. For example, the vertex (A 1: C

   2) represents the link between the first radio on router A and the second radio on router C. When using a vertex coloring algorithm to color the CG, we impose an important constraint: on coloring any MCG vertex, all uncolored vertices in the conflict graph that contain any radio from the just-colored vertex be removed. For example after assigning a color to vertex (A 1: C 2) in Figure 2(c), all vertices containing either A 1 or C 2 should be removed from the conflict graph. This is required to ensure that only one channel is assigned to each radio in the mesh network

   A .Channel assignment Algorithm

   The channel assignment problem for mesh networks is similar to the list coloring problem, which is defined as follows:

   Given a graph, G = (V,E), and for every v in V, a list L(v) of colors, is it possible to construct a valid vertex coloring of G such that every vertex v receives a color from the list L(v). The list coloring problem is NP-complete. Therefore, we rely on an approximate algorithm for channel assignment. Our algorithm, called the Breadth First Search Channel

   Assignment (BFS-CA) algorithm, uses a breadth first search to assign channels to the mesh radios. The search begins with links emanating from the gateway node. The rationale behind the use of breadth first search is intuitive: by using breadth first search, we satisfy our goal of giving channel assignment priority to links starting from the gateway and then in decreasing levels of priority to links fanning outward towards the edge of the network.

   Before using the BFS-CA algorithm, the channel assignment server (CAS) obtais the interference estimates from the mesh routers. It then chooses a channel for the default radios. The default channel is chosen such that its use in the mesh network minimizes interference between the mesh network and collocated wireless networks. The CAS then creates the MCG for the non-default radios in the mesh. We use a two hop interference model to create the MCG.

   B .Default Channel Selection

   The CAS chooses the default channel using the rank of a channel, c, for the entire mesh, Rc. Rc is computed as follows:

   D. Channel Re-assignment Strategy

   To adapt to the changing interference characteristics, the CAS periodically re-assigns channels. The periodicity depends ultimately on how frequently interference levels in the mesh network are expected to change.

2. SIMULATION RESULTS

   For static routing the communication between the nodes (28-22) takes place in the 6 Hop path,& for dynamic routing nodes (0-17) takes place in the 6 Hop path but the link failed in-between in node 13 so alternate routing takes place in the 7 Hop path instead of 6 Hop path using CAS which execute the Multi Radio Conflict Graph model & BFS-CA algorithm to find the alternate path, node 14 acts as the CAS to assign the channels for dynamic routing and various parameters Throughput ,Delay, Loss, & Packet data rate are measured between these two routing.

   = =1

   (13)

   Where n is the number of routers in the mesh and Ranki C is the rank of channel c at router i.

   The default channel is then chosen as the channel with the least Rc value

   1. Non-Default Channel Selection

   In this phase, the CAS uses the neighbor information collected from all routers to construct the MCG. Neighbor information sent by a router contains the identity of its neighbors, delay to each neighbor, and interference estimates for all channels supported by the routers radios.

   The CAS associates with each vertex in the MCG its corresponding link delay value. The CAS also associates with each vertex a channel ranking derived by taking the average of the individual channel rankings of the two radios that make up the vertex. The average is important because the assignment of a channel to a vertex in the MCG should take into account the preferences of both end-point radios that make up the vertex. For all vertices in the MCG, the CAS then computes their distances from the gateway.

   The distance of an MCG vertex is the average of the distances from the gateway of the two radios that make up the vertex. The distance of a radio is obtained from beacons initiated by the gateway. A beacon is a gateway advertisement broadcasted hop-by-hop throughout the mesh. Each beacon contains a hop-count field that is incremented at each hop during its broadcast.

   The distance of a router from the gateway is the shortest path length of a single beacon instance received by the router over all paths. The router communicates the distance to the CAS via periodic heartbeat messages sent every minute in the implementation.

   Figure.3 Node Generation (31 nodes)

   Figure.4 Communication between the nodes

   Figure.5 Reality check Results

   Figure.5 shows Reality check value and the maximum interference range is found for the receiving node is 11.

   Figure.6 Simulation time vs Packet Data Rate

   Figure.6 shows the result for the simulation time versus Packet Data Rate for both Static and Dynamic channel assignment scheme using Breadth First search algorithm.

   Figure.7 Simulation time vs Loss

   Figure.8 Simulation time vs Throughput

   Figure.7shows the result for simulation time versus Throughput & Figure.8 shows the result for the simulation versus throughput for both Static and Dynamic channel assignment scheme using Breadth First search algorithm

   Figure.9 Simulation time vs Delay

   Figure.9 shows the result for the simulation versus Delay for both Static and Dynamic channel assignment scheme using Breadth First search algorithm

   TABLE.1 ANALYSIS OF DIFFERENT PARAMETERS

   Sl. No	Parameters in %	Static- CA	Dynamic BFS-CA	Change in %
   1.	Packet Data Rate	76	87	11
   2.	Loss	29	19	10
   3.	Throughput	50	64	14
   4.	Delay	29	23	6

   The above tabulation shows the results of various parameters between the static and dynamic channel assignment scheme in which the packet data rate increases by 11%, loss decreases by 10%, throughput increases by 14% and delay decreases by 6%.

3. CONCLUSION

Using Reality Check Mechanism the maximum interference range was found for the receiving node for the corresponding maximum objective value by combining the physical and protocol model. Using channel assignment with multiple radios in the nodes the interference is minimized. For this the wireless mesh network is used. The channel assignment scheme used is BFS-CA, and Breadth First Search Channel Assignment which uses Multi Radio conflict graph model, dynamic channel allocation and the various parameters are calculated between the static and dynamic BFS-CA.

ACKNOWLEDGEMENT

First and foremost I thank GOD, the almighty who stands behind and strengthens me to complete the project successfully. I would like to express my sincere respect and gratitude towards my HOD Mrs.M.Geetha, M.Tech.,(Ph.D). Her wide knowledge, serious research attitude and enthusiasm in work deeply impressed me and taught what a true scientific research should be. I am very thankful for the support she extended to me and the freedom to express my views. Words are inadequate to express the gratitude to my beloved husband, children, Parents, Brother and friends for their excellent and never ending co-operation.

REFERENCES

[1]. Y.Shi, Y.Thomas Hou, Jia Liu, Sastry Kompella Bridging the gap between Protocol and Physical Models for Wireless Networks-, July 2013

1. R.L. Cruz and A.V. Santhanam, Optimal Routing, Link Scheduling and Power Control in Multi-Hop Wireless Networks, Proc. IEEE INFOCOM, pp. 702-711, Mar./Apr. 2003.

2. R. Draves, J. Padhye, and B. Zill, Routing in Multi-Radio, Multi- Hop Wireless Mesh Networks, Proc. ACM MobiCom, pp. 114-128, Sept./Oct. 2004.

3. T. Elbatt and A. Ephremides, Joint Scheduling and Power Control for Wireless Ad-Hoc Networks, Proc. IEEE INFOCOM, pp. 976-984, June 2002.

4. C.C. Chen and D.S. Lee, A Joint Design of Distributed QoS Scheduling and Power Control for Wireless Networks, Proc. IEEE INFOCOM, Apr. 2006.

[6]. Interference-Aware Channel Assignment in Multi- Radio Wireless Mesh Networks, K. Ramachandran, E. Belding-Royer, K. Almeroth, and M Buddhikot, Proc. IEEE INFOCOM, Apr 20068.

[7]. Jain, J. Padhye, V. Padmanabhan, and L. Qiu Impact of Interference on Multi-Hop Wireless Network Performance, K Proc. ACM MobiCom, pp. 66-80, Sept. 2003.

1. A.Raniwala and T. Chiueh, Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network,Proc.IEEE INFOCOM, pp. 2223-2234, Mar. 2005.

2. Y. Shi and Y.T. Hou, Optimal Power Control for Multi-Hop Software Defined Radio Networks, Proc. IEEE INFOCOM, pp. 1694-1702, May 2007.

3. J.Tang, G.Xue, C.Chandler,& W.Zhang, Interference-Aware Routing in Multihop Wireless Networks Using Directional Antennas, Proc. IEEE INFOCOM, pp. 751-760, Mar. 2005.

[11]. W. Wang, Y. Wang, X.-Y. Li, W.-Z. Song, and O. Frieder, Efficient Interference-Aware TDMA Link Scheduling for Static Wireless Networks, Proc. ACM MobiCom, pp. 262-23, Sept. 2006.

[12]. Cognitive Radio Communications and Networks: Principles and Practices, A.M. Wyglinski, M. Nekovee, and Y.T. Hou, eds. Academic Press/Elsevier, 2010.

1. Y. Yuan, P. Bahl, R. Chandra, T. Moscibroda, and Y. Wu,Allocating Dynamic Time-Spectrum Blocks in Cognitive Radio Networks, Proc. ACM MobiHoc, pp. 130-139, Sept. 2007.

2. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, pp. 245-248. W.H. Freeman, 1979.

3. A.J. Goldsmith and S.-G. Chua, Adaptive Coded modulation for Fading Channels, IEEE Trans. Comm., vol. 46, no. 5, pp. 595-602, May 1998.

BIOGRAPHIES

Revathi Madhan. completed her B.E in

J.J college of Engg & Tech, she is doing her M.E communication Systems in Jayaram college of Engg & Tech and her research area of interest is Wireless Networks.

Mrs.S.Deva Priya. completed her B.E in Arulmigu Meenakshmiamman college of Engg, & tech. She completed her M.E in Embedded systems in SASTRA University and she is doing her Ph.D in Mobile Communication in Anna University Trichy. She is working in Jayaram college of Engg & Tech for about

14 years. She had attended 12 international conferences, and 10 national conferences. She is a Life member in ISTE and member in IEEE, and she published 4 books. Her research area of interest is Embedded Systems, SOC, Mobile Communication, DSP, wireless communication.