Channel Assignment Schemes Optimization for Multi-Interface Wireless Mesh Networks Based on Link Load

1. Introduction

In recent years, wireless mesh networks (WMNs) were deployed as a type of next generation wireless broadband networks. WMNs provide wireless broadband accessibility to extend the Internet connectivity to the last mile and improve the network coverage. WMN consists of a set of mesh routers and mesh clients (Fig. 1). Mesh routers are usually stationary and form multi-hop wireless backbone network (i.e. mesh routers are interconnected with each other via wireless medium). Some or all of the mesh routers also serve as access points for mobile users (mesh clients) under their coverage. Usually one or more mesh routers have direct connections to wired network and serve as Internet gateways for the rest of the network. These nodes are called mesh gateways. Compared to traditional wireless LANs, the main feature of WMNs is their multi-hop wireless backbone capability (Conti et al., 2007).

Traditionally, wireless networks are equipped with only one IEEE 802.11 radio interface. However, a single-interface inherently restricts the whole network by using only one single channel (Fig. 3a). In order to communicate successfully, two neighboring routers have to build a logical link which operates on a common channel. Due to that, all wireless nodes have to use only one radio interface, all logical links in network must use the same channel. If two neighboring links operate on the same channel and transfer data simultaneously, then they definitely interfere with each other. The network capacity and the performance may degrade significantly because of the interference (Gupta & Kumar, 2000). The key factor for reducing the effect of interference is the using of non-overlapping channels (standard IEEE 802.11b/g provides 3 and standard IEEE 802.11a up to 12 non-overlapping channels) (Ramachandran et al., 2006). In practice, IEEE 802.11b/g defines 11 communication channels (number of communication channels varies due to regulations of different countries) but only 3 of them are non-overlapping (Fig.2).

Figure 1.

WMN architecture

Figure 2.

Channel spectrum occupation in IEEE 802.11b/g

Using multiple non-overlapping channels in single interface network disconnects the subset of nodes using one channel from other nodes that are not using the same channel (Fig. 3b). For this reason this approach generally requires MAC layer modification and per packet channel switching capability for radio interfaces (Marina & Das, 2005). Before every data transmission a channel selection mechanism evaluates the available channels and selects a channel to transmit. There are also some problems introduced with channel switching mechanism. These problems include multi-channel hidden terminal problem, broadcast problem, deafness problem and channel deadlock problem (Raniwala et al., 2004).

One of the most promising approaches lies in using multiple radio interfaces and multiple non-overlapping channels (Fig. 3c). This solution is better than previous one, because of providing the effective usage of given frequency spectrum (Conti et al., 2007). This architecture overcomes deficiencies of single interface solution. It allows using of multiple interfaces per node to allow the simultaneous transmission and reception on different radio interfaces tuned to different channels, which can essentially improve network capacity. However, the number of radio interfaces is always much higher than the number of effective channels, which causes an existence of many different links between mesh routers operating on the same channel. For this reason, the suitable channel assignment method is needed to maintain the connectivity between mesh nodes and to minimize the effect of interference (Raniwala et al., 2004).

The channel assignment (CA) in a multi-interface WMN consists of a task to assign channels to the radio interfaces by such a way to achieve efficient channel utilization and to minimize the interference. The problem of optimally assigning channels in an arbitrary mesh topology has been proved to be NP-hard (non-deterministic polynomial-time hard) based on its mapping to a graph-coloring problem. Therefore, channel assignment schemes predominantly employ heuristic techniques to assign channels to radio interfaces belonging to WMN nodes.

The channel assignment algorithms can be divided into three main categories: fixed, dynamic and hybrid, depending on the frequency with which it is modified by the channel assignment scheme. In a fixed scheme, the CA is almost constant, while in a dynamic one it is continuously updated to improve performance. A hybrid scheme applies a fixed scheme for some radio interfaces and dynamic one for the others (Yulong Chen et al., 2010).

Figure 3.

Different types of WMNs

The main objective of this chapter is to give to reader the compact information about problems connected with optimal using of radio interfaces and radio channels in wireless mesh networks. The optimal using is computed from several different points of view, e.g. network topology, number of data flows, number of nodes by comparison of selected QoS parameters. In the second part of the chapter, the new proposed centralized channel assignment concept called First Random Channel Assignment algorithm (FRCA) is compared with two other channel assignment techniques (CCA, LACA) by the same QoS parameters.

The rest of this chapter is organized as follows. In section 2, the related work is summarized. In section 3, the methods and simulation results to find the optimal number of radio interfaces per node are introduced. In section 4 the mathematical background and graph based mathematical model is described and in the next section different types of channel assignment methods based on links load are analyzed. Section 6 concludes the chapter.

2. Related work

There exist a large number of studies which address the channel assignment problem in wireless mesh networks. Several works have proposed MAC protocols for utilizing multiple channels (So & Vaidya, 2004, Gong & Midkiff, 2005), but these multi-channel protocols require changes to existing standards and therefore cannot be deployed by using existing hardware. In (Adya et al., 2004) was proposed a link-layer solution for transmitting data over multiple radio interfaces, but this approach is designed for scenario where the number of radio interfaces is equal to the number of channels. In (Gupta & Kumar, 2000) the performance of multi-channel ad-hoc networks was studied, where each channel was assigned to an interface. In (Draves et al., 2004) several methods for increasing the performance in single-channel per interface were proposed. The most studies is focused only to one problem - to find the efficient channel assignment method, but did not suggest the optimal number of radio interfaces per node. In (Husnain et al., 2004) were compared different static centralized algorithms, but for evaluation of optimal number of radio interfaces was used only one parameter - total interference (number of links in conflict graph). (Raniwala et al., 2004) proposed centralized channel assignment and routing method, where results about number of radio interfaces were shown but only for network cross-section goodput. In (Chi Moon Oh et al., 2008) the study of optimal number of radio interfaces was created but only for grid network, using simple channel assignment method and for one QoS parameter (throughput).

3. The study of optimal number of radio interfaces

In this section several simulations were created to find the optimal number of radio interfaces for static WMN. In this study we focus only to one problem - to find the optimal number of radio interfaces for different conditions therefore, for channel assignment we used simple CCA approach (section 5.1).

Nowadays the availability of the cheap off-the-shelf commodity hardware also makes multi-radio solutions economically attractive. This condition provides the using much more radio interfaces per node, which shows the investigating of optimal number of interfaces as a reasonable argument.

We have included in our simulations several QoS parameters, data flows, number of nodes and network topologies to find the optimum number of radio interfaces for services which required the real time transmission (e.g. video conference).

3.1. Simulation environment

A simulation WMN model was developed in NS-2 network simulator, with additional function to support multi-channel and multi-interface solution (Calvo & Campo, 2007). Each mesh node used the number of interfaces between 1 to 8 and the same number of channels. Two different network topologies were created. The first one was grid topology, which consisted of 25 static wireless mesh nodes placed in an area of 1000 x 1000 meters. Transmission range for each node was set to 200 meters (Fig.4a). The second topology consists of 25 nodes, which were randomly placed in an area of 1000 x 1000 meters (Fig.4b). For simulation evaluations, ten random topologies and computed average values of chosen QoS parameters were studied. We have used the WMN with 25 nodes, because of the typical number of mesh nodes in WMN (25 to 30) (Skalli et al., 2006). For traffic generation, 5 CBR (Constant Bit Rate) flows were used and the packet size was set to 512 bytes. The same radio default parameters as in (ns-2, 2008) were used, except that we set the channel data rate to 11 Mbit/s. Simulation parameters are summarized in Table 1.

Parameter	Value
Test Area	1000x1000 m
Mac protocol	IEEE 802.11
Propagation model	Two ray ground
Routing protocol	AODV
Antenna type	Omni-directional
Traffic type	CBR
Packet size	512 bytes
Simulation time	100 seconds

Table 1.

Simulation parameters

Figure 4.

Grid (a) and random (b) topology of static WMN created in NS-2 simulator

3.2. Simulation results

In this section results of experiments are presented. The purpose of simulation was to determine the optimal number of radio interfaces for different WMN topologies, different number of data flows and different number of nodes to achieve the network capacity increasing expressed in enhancement of QoS parameters.

We chose four QoS parameters for simulation evaluation:

• Average End-to-end Delay: The average time taken for a packet to reach the destination. It includes all possible delays in the source node and in each intermediate host, caused by queuing at the interface queue, transmission at the MAC layer, routing discovery, etc. Only successfully delivered packets are counted.

• Average Throughput: The sum of data packets delivered to all nodes in the network in a given time unit (second).

• Packet Loss: Occurs when one or more packets being transmitted across the network fail to arrive at the destination.

• Average Jitter: The delay variations between all received data packets.

3.2.1. Different network topologies

In this simulation we created two different network topologies of WMN (grid topology and random topology). Ten random topologies were created and average values of chosen QoS parameters were computed.

Figure 5.

Average values of end-to-end delays for various radio interfaces and different network topologies

Figure 5 shows the average values of end-to-end delay for various numbers of radio interfaces and two different network topologies. From results it is obvious that the highest value of end-to-end delay (0.92 sec) was reached in the grid WMN with one radio interface. The lowest value of delay (0.0097 sec) was achieved in grid WMN with seven radio interfaces. In WMN with random topology, the lowest value of delay (0.049 sec) was achieved in WMN with six radio interfaces. The best values of average delay were achieved in WMN with random topology, but differences between values of random and grid topologies were small for higher number of radio interfaces. From results it may be concluded that optimal number of radio interfaces which guarantee the maximum allowable average delay 150 ms (ITU-T, 2003) for both network topologies is five, because more than five interfaces improved value of end-to-end delay only slightly, but the complexity of node is increased considerably.

Figure 6 shows the average values of network throughput for various numbers of radio interfaces and two different network topologies. The lowest value of average throughput was achieved in grid WMN, where nodes have used for transmission only one radio interface. In this case, the value of average throughput was 504.28 kbps. In the case where WMN with random topology and one radio interface was used, the lowest value of average throughput (739.3 kbps) was achieved. The highest value of throughput (2019.9 kbps) reaches the grid WMN with seven radio interfaces. The best value of average throughput in random WMN topology (1964.2 kbps) was achieved by WMN with seven radio interfaces. Again, the optimal number of interfaces for both network topologies was chosen as five.

Figure 6.

Average values of throughput for various radio interfaces and different network topologies

As we can see from Fig.7, the highest value of packet loss (75.1%) was reached in grid WMN with one radio interface. The lowest value of packet loss was achieved in WMN with seven radio interfaces. This value was 3.5% for the random topology and 2.5% for grid topology. As in the previous case, we can conclude the optimal number of radio interfaces as five, where grid topology achieved 9.8% of packet loss and 7.6% for random topology.

Figure 8 shows the average values of time jitter for different types of topologies and various number of radio interfaces. From results it is obvious that the highest value of average jitter was reached in the network with one radio interface. For the random topology this value was 0.7 sec and for grid topology it was 0.8 sec. On the other hand the lowest values of average jitter were achieved in grid WMN with seven interfaces (0.3 sec) and in random WMN with six interfaces (0.05 sec). As an optimal number of radio interfaces, the number of six was selected with average jitter value 0.11 sec for random topology and 0.14 sec for grid topology.

Figure 7.

Values of packet loss for various radio interfaces and different network topologies

Figure 8.

Average values of jitter for various radio interfaces and different network topologies

3.2.2. Different number of data flows

Simulation model consisted of 25 static wireless mesh nodes placed in grid in area 1000x1000 m (Fig.4a). Transmission range for each node was set to 200 m. As traffic transmission, the 5, 10, 15 and 20 CBR flows were simulated and packet size of 512 bytes was used. Data flows were created between random chosen node pairs.

Figure 9 shows the average values of end-to-end delay for different number of data flows. From results it is obvious that the best performance was achieved in multi-interface WMN with six interfaces, when the number of flows changed. The highest value of average end-to-end delay (for all data flows) was reached by WMN with one radio interface. For small number of data flows (5), WMN with 5 interfaces reached the best performance, whilst for 10 data flows the best performance was reached by 6 interfaces. For more data flows (15 and 20) the system performance is unsatisfactory regardless of number of interfaces.

Figure 9.

Average values of end-to-end delay for various radio interfaces and different number of data flows

Figure 10 shows the simulation results of average values of network throughput for the 5, 10, 15 and 20 data flows. The lowest value of average throughput was achieved in grid WMN with only one radio interface. From results it is obvious that the highest value of average throughput was reached in the multi-interface WMN with six radio interfaces. In the WMN with more than six interfaces the network performance is decreasing.

Figure 10.

Average values of throughput for various radio interfaces and different number of data flows

As we can see from Figure 11, the best value of packet loss was reached in multi-interface WMN with six radio interfaces. The highest value of packet loss was reached in WMN, where nodes used for transmission one radio interface.

Figure 12 shows the average values of jitter for the different number of data flows. The highest values were achieved in WMN, where nodes have used for transmission only one radio interface. The best value of average jitter for all data flows was achieved in WMN with five or six radio interfaces.

Figure 11.

Values of packet loss for various radio interfaces and different number of data flows

Figure 12.

Average values of jitter for various radio interfaces and different number of data flows

3.2.3. Different number of nodes

In this simulation the static grid WMN was used (Fig. 4a), but with changing number of nodes. Six different NxN grid networks were created, where N was changed from five to ten. Transmission range for each node was set to 200 meters. For traffic transmission, 15 CBR flows were used and the packet size 512 bytes was set. Data flows were created between random chosen node pairs.

Results from previous sections (3.1.1 and 3.1.2) shows that the best values for almost all QoS parameters were achieved in WMN with six radio interfaces. For this reason the simulation model for different number of nodes only for WMN with six radio interfaces was created. Figure 13 shows the average values of end-to-end delay for six radio interfaces and six different network topologies. The best value of average end-to-end delay was reached in multi-interface WMN with 25 nodes (5x5). The highest value of average end-to-end delay was achieved by WMN with 100 nodes (10x10). Results show that increasing number of nodes increase value of end to end delay.

Figure 13.

Average values of end-to-end delay for different number of nodes

The lowest value of average throughput (Fig. 14) was achieved in WMN with 100 static nodes. The best values of throughput were reached in configuration 6x6 and 7x7 nodes.

Figure 14.

Average values of network throughput for different number of nodes

The highest values of packet loss (Fig. 15) were achieved in WMN with 10x10 nodes. The lowest value of packet loss was achieved in the WMN with 6x6 nodes.

Figure 15.

Values of packet loss for different number of nodes

As we can see from figure 16 the best value of average jitter was achieved WMN with 25 nodes and the highest value was reached in 9x9 grid network.

Figure 16.

Average values of jitter for different number of nodes

These simulations showed unacceptable values for almost all simulated QoS parameters. Average delay combined with average jitter achieved in all networks (from 25 to 100 nodes) doesn’t allow using several CBR services running simultaneously. This conclusion is certified by enormous packet loss in networks (over 55 % in the best solution).

3.3. Results summary

The results show the benefits of using multiple radio interfaces per node. This solution can improve the capacity of WMN. Simulation results show that by increasing the number of interfaces it is possible to increase network capacity by enhancing of QoS parameters. For all simulations of WMN with common channel assignment method, the number of six radio interfaces appears as an optimum solution, because further increasing of the number of interfaces improved the capacity of WMN only slightly and using more than seven radio interfaces decreased the network performance. These results can be used as a base to another research channel assignment methods, where using of suitable CA algorithm can additionally improve network performance.

4. Theoretical background

Optimal channel assignment in WMNs is an NP-hard problem (similar to the graph coloring problem). For this reason, before we present the channel assignment problem in WMNs, let us first provide some mathematical background about graph coloring problem.

4.1. Graph coloring

The graph coloring theory is used as a base for the theoretical modeling of channel assignment problem. At the beginning we must define two related terms: communication range and interference range. Communication range is the range in which a reliable communication between two nodes is possible. The interference range is the range in which transmission from one node can affect the transmission from other nodes on the same or partially overlapping channels. The interference range is always larger than the communication range (Fig. 17) (Prodan & Mirchandani, 2009).

Figure 17.

Communication range and interference range

Consider an undirected graph G(V, E) that models the communication network. A graph G, is defined as a set of vertices V and a set of edges E. Each vertex in graph represents a mesh router and each edge between two vertices represents a wireless link between two mesh routers. The color of each vertex represents a non-overlapping channel and the goal of the channel assignment is to cover all vertices with the minimum number of colors such that no two adjacent vertices use the same channel (Husnain Mansoor Ali et al., 2009).

4.2. Connectivity graph

The vertices set V consists of the network nodes, which may have multiple radio interfaces (not necessarily the same), while the edges/links set E includes all the communication links in the network. A link e between a pair of nodes (v_i, v_j); where v_i, v_j є V exists if they are within the communication range of each other and are using the same channel. The graph G described above is called the Connectivity graph (Fig. 5). The links presented in the network topology are referred to as the logical links (Husnain Mansoor Ali et al., 2009).

4.3. Interfering edges

To include the interference in network model, we introduce the concept of Interfering edges. Interfering edges for an edge e (IE(e)) are defined as the set of all edges which are using the same channel as edge e but cannot use it simultaneously in active state together with edge e. All edges are competing for the same channel hence the goal of channel assignment algorithm is to minimize the number of all edges e thereby increasing capacity (Husnain Mansoor Ali et al., 2009).

4.4. Conflict graph

In this subsection the concept of conflict graph is introduced. A conflict graph G_c(V_c, E_c) consist of the set of edges E_c and the set of vertices V_c. The vortices V_c have a one relation with the set of edges E_c of the connectivity graph (i.e. for each edge e ∈ E_c, there exists a v_c ∈ V_c). As for the set E_c of the conflict graph, there exists an edge between two conflict graph vertices v_ci and v_cj if and only if the corresponding edges e_i and e_j of the connectivity graph, are in IE(e) set of each other. Hence, if two edges interfere in the connectivity graph, then there is an edge between them in the conflict graph. The conflict graph can now be used to represent any interference model. For instance, we can say that two edges interfere if they use the same wireless channel and they are within interference range. If we want use any other interference model based on signal power, then that can also be easily created by just defining the conditions of interference. Total interference can now be described as the number of links in the conflict graph (i.e. the cardinality of E_c).

The above mentioned concepts of connectivity graph, interfering edges and conflict graph are illustrated in Fig.18. For a graph G(V, E), we find the IE for all the links and then create the conflict graph G_c(V_c, E_c) (Husnain Mansoor Ali et al., 2009).

Figure 18.

Connectivity graph, interfering edges and conflict graph

5. Channel assignment algorithms for WMN

As has been already mentioned, CA in a multi-interface WMN consists of assigning channels to the radio interfaces in order to achieve efficient channel utilization for minimizing interference and to guarantee an adequate level of connectivity. Nowadays, there exist many approaches to solve the channel assignment problem. These approaches can be divided into three main categories (Conti et al., 2007):

1. Fixed (static) channel assignment approaches – channels are statically assigned to different radio interfaces. The main concern includes the enhancement of efficiency and guaranteeing of the network connectivity.

2. Dynamic channel assignment approaches – a radio interfaces are allowed to operate on multiple channels, implying that a radio interfaces can be switched from one channel to another one. This switching depends on channel conditions, such as the value of interference. The basic issues are the switching delay and the switching synchronization.

3. Hybrid channel assignment approaches – in this approach the radio interfaces are divided into two groups, the first is fixed for certain channels and the second is switchable dynamically while deploying the channels.

In this section several channel assignment approaches are compared by QoS parameters mentioned in the previous section.

5.1. Common channel assignment

The Common channel assignment (CCA) is a simplest fixed channel assignment approach (Adya et al., 2004). In this CA approach all radio interfaces of each node were tuned to the same set of channels. For example, if every node has two radio interfaces then each node uses the same two channels (Fig. 19). The main benefit of this approach is the network connectivity. The connectivity is the same as that of a single interface approach, while the using of multiple radio interfaces can improve network throughput. However, if the number of non-overlapping channel is much higher than the number of radio interfaces, the gain of the CCA may be limited. CCA scheme presents a simplest channel assignment approach but it fails to account for the various factors affecting CA in a WMN. This solution will decrease the utilization of network resources (Yulong Chen et al., 2010).

Figure 19.

Example of common channel assignment approach

5.2. Load aware channel assignment

Load aware channel assignment (LACA) represents a dynamic centralized channel assignment and routing algorithm, where traffic is mainly directed toward gateway nodes (Raniwala et al., 2004), assuming that the offered traffic load on each virtual link is known. Algorithm assigns channels by such a way to ensure the network connectivity while takes into account the bandwidth limitation of each link. At the beginning, LACA estimates the total expected load on each virtual link based on the load imposed by each traffic flow. In the next step CA algorithm visits each virtual link in decreasing order of expected traffic load and greedily assigns it a channel. The algorithm starts with an initial estimation of the expected traffic load and iterates over channel assignment and routing until the bandwidth allocated on each virtual link matches its expected load. While this CA approach presents a method for CA that incorporates connectivity and flow patterns, the CA scheme on links may cause a “ripple effect”, whereby already assigned links have to be revisited, thus increasing the time complexity of the scheme.

An example of node revisiting is illustrated in Fig. 20. In this example each node has two radio interfaces. The channel list of node A is [1, 6] and channel list of node B is [2, 7]. Because nodes A and B have no common channel, a channel re-assignment is required. Link between nodes A and B needs to be assigned one of the channels from [1, 2, 6, 7]. Based on the channel expected loads, link between nodes A and B is assigned channel 6, and channel 7 assigned already to link between nodes B and D is reassigned to channel 6 (Raniwala et al., 2004, Yulong Chen et al., 2010).

Figure 20.

An example of channel revisit in LACA approach

5.3. First random channel assignment

The First Random Channel Assignment algorithm (FRCA) is a dynamic and centralized load aware channel assignment and routing algorithm for multi-interface multi-channel WMN (Pollak, Wieser, 2012). This approach takes into account the network traffic profile. FRCA algorithm assigns radio channels to links considering their expected loads and interference effect of other links, which are in interference range and which are tuned to the same radio channel.

FRCA algorithm consists of two basic phases:

1. Initial phase

2. Optimization phase

In the first phase, algorithm estimates initial loads on all links based on the initial routes created by routing algorithm. After load estimation, FRCA randomly assigns channels to all nodes for each radio interface.

In the second phase, FRCA algorithm uses similar steps as in the first phase, but channel assignment and routing iterations are based on results from the first phase. If some of the link load is higher than link capacity, the algorithm goes back and tries to find better solution. Algorithm’s iterations end when no further improvement is possible. In optimization phase, FRCA uses greedy load-aware channel assignment algorithm similar to the one used in LACA algorithm (Raniwala et al., 2004). In this algorithm virtual links are visited in decreasing order of the link expected load. To find routes between nodes, FRCA uses shortest path routing based on minimum hop count metric (Kaabi et al., 2010).

5.3.1. Link load estimation

This approach is based on the concept of load criticality. The method assumes perfect load balancing across all acceptable paths between each communicating pair of nodes. Let P(s, d) denote the number of acceptable paths between pair of nodes (s, d), P_l (s, d) is the number of acceptable paths between (s, d) which pass a link l. And finally, let B(s, d) be the estimated load between node pair (s, d). Then the expected traffic load Φ_l on link l is calculated as (Raniwala et al., 2004):

$${\Phi }_l={\displaystyle \sum _{s,d}\frac{P_l(s,d)}{P(s,d)}\cdot }B(s,d)$$E1

This equation implies that the initial expected traffic on a link is the sum of the loads from all acceptable paths, across all possible node pairs, which pass through the link. Because of the assumption of uniform multi-path routing, the load that an acceptable path between a pair of nodes is expected to carry is equal to the expected load of the pair of nodes divided by the total number of acceptable paths between them. Let us consider the logical topology as shown in Fig. 21 and assume that we have three data flows reported in table 2.

Figure 21.

Multi-interface and multi-channel WMN

Because we have three different communications node pairs, we have

$${\Phi }_l=\frac{P_l(a,g)}{P(a,g)}\cdot {\gamma }^{(a,g)}+\frac{P_l(i,a)}{P(i,a)}\cdot {\gamma }^{(i,a)}+\frac{P_l(b,j)}{P(b,j)}\cdot {\gamma }^{(b,j)}$$E2

Source (s)	Destination (d)	γ^(s, d) (Mbps)
a	g	0.9
i	a	1.2
b	j	0.5

Table 2.

Traffic profile with three data flows

(source, destination)	(a, g)	(i, a)	(b, j)
Possible paths	a-c-g	i-e-a	b-f-j
	a-c-d-g	i-e-d-a	b-f-i-j
	a-d-g	i-d-a	b-e-i-j
	a-d-c-g	i-d-c-a	b-e-i-f-j
	a-d-h-g	i-d-e-a	b-e-d-i-j
	a-d-i-h-g	i-d-g-c-a
	a-e-d-g	i-h-d-a
	a-e-i-h-g	i-h-g-c-a
P (source, destination)	P(a, g) = 8	P(i, a) = 8	P(b, j) = 5

Table 3.

Possible data flows between communicating nodes

In the next step we calculate P(s, d) for each flow. We need to determine all the possible paths between source and destination. Table 3 shows all possible paths between communication node pairs for the WMN topology in Fig. 21. Values P(s, d) and the corresponding link traffic load (Φ_l) is calculated using equation (2). Results are shown in table 4. Based on these calculations, we can estimate the load between each neighboring nodes. The result of calculation Φ_l is the expected traffic load of link l (i.e. the amount of traffic expected to be carried over a specific link) (Badia et al., 2009, Conti et al., 2007, Raniwala et al., 2004).

l	Pl(a, g)	Pl(i, a)	Pl(b, j)	Φl (Mbps)
a-c	2	3	0	0.675
c-g	2	2	0	0.525
c-d	2	1	0	0.375
d-g	2	1	0	0.375
a-d	4	3	0	0.9
g-h	0	1	0	0.15
d-h	1	1	0	0.2625
a-e	2	2	0	0.525
d-e	1	2	1	0.5125
d-i	1	3	1	0.6625
h-i	2	2	0	0.525
e-i	1	2	2	0.6125
b-e	0	0	3	0.3
b-f	0	0	2	0.2
f-i	0	0	2	0.2
i-j	0	0	2	0.2
f-j	0	0	2	0.2

Table 4.

The results of calculation Φ_l on specific link l

5.3.2. Link capacity estimation

The link capacity (channel bandwidth available to a virtual link) is determined by the number of all virtual links in its interference range that are also assigned to the same radio channel. So when estimating the usable capacity of the virtual link, we should consider all traffic loads in its interference range. According to the channel assignment rules, the higher load a link is expected to carry, the more bandwidth it should get. On the other side, the higher loads its interfering links are expected to carry, the less bandwidth it could obtain. Thus, the link capacity should be proportional to its traffic load, and be inversely proportional to all other interfering loads. Thus, the capacity bw_(i) assigned to link i can be obtained using the following equation:

$$b{w}_{(i)}=\frac{{\Phi }_i}{{\displaystyle \sum _{j\in Intf(i)}{\Phi }_j}}*C{}_{ch}$$E3

where Φ_i is the expected load on link i, Intf(i) is the set of all virtual links in the interference range of link i (i.e. links i and j operates on the same channel). C_ch is the sustained radio channel capacity (Badia et al., 2009, Conti et al., 2007, Raniwala et al., 2004).

5.4. Simulation results

In this section, the performance of proposed FRCA concept is evaluated and compared with CCA (Adya et al., 2004), LACA (Raniwala et al., 2004) and a single interface architecture by using NS-2 simulator (ns-2, 2008). Simulation model consisted of 25 static wireless mesh nodes placed in an area of 1000 x 1000 m (Fig.4a). The distance between nodes was set to 200 m. The capacity of all data links was fixed at 11Mbps. All nodes have the same transmission power and the same omni-directional antenna. The transmission range was set to 200 m and interference range was set to 400 m. For traffic generation, 25 CBR (Constant Bit Rate) flows with packet size 1000 bytes were used. Flows were created between randomly chosen node pairs. For simulation evaluation, the same metrics like in section 3.1 was used.

5.4.1. Different number of radio interfaces

From previous sections the conclusion about optimal number of six radio interfaces was gained. This conclusion was based on simple common channel assignment scheme CCA, which was used in simulations. With using more sophisticated channel assignment scheme it is possible to expect that the same results in QoS parameters may be reached with less number of interfaces. So the performance evaluation of chosen CA schemes was based on changing number of radio interfaces (between 2 to 8 radio interfaces for each node).

Figure 22 shows the average values of end-to-end delay for various number of radio interfaces. From results it is obvious that the highest value of delay (792.64 ms) was reached in WMN with CCA scheme. Lowest value (101.42 ms) reached WMN with FRCA algorithm for 4 radio interfaces. For CCA scheme the optimal number of radio interfaces was 6, but FRCA and LACA reached the best performance with only 4 radio interfaces. Results show that further increasing of number of radio interfaces didn’t increase the network performance, so the optimal number of radio interfaces for LACA and FRCA algorithm is 4.

Figure 22.

Average values of end-to-end delay for various radio interfaces and different CA schemes

Figure 23 shows the average values of network throughput. The lowest value of average throughput for all radio interfaces was achieved in WMN with CCA scheme. This approach reached the best results for 6 radio interfaces. Others CA algorithms (FRCA and LACA) achieved the best performance with only 4 radio interfaces, with FRCA slightly outperformed LACA algorithm.

Figure 23.

Average values of network throughput for various radio interfaces and different CA schemes

As we can see from figure 24 the highest value of packet loss for all number of interfaces was reached in WMN with CCA approach, with the best value reached for 6 radio interfaces (63.56 %). The best result (5.86 %) reached FRCA algorithm for 4 radio interfaces, whereas algorithm LACA with the same number of radio interfaces reached value 9.47%.

Figure 25 shows average values of average jitter. The best values of average jitter were again reached with FRCA algorithm for 4 radio interfaces (124.8 ms). CCA algorithm reached the best value for 6 radio interfaces (601.25 ms) and LACA approach for 4 radio interfaces (167. 27 ms).

Figure 24.

Values of packet loss for various radio interfaces and different CA schemes

Figure 25.

Average values of jitter for various radio interfaces and different CA schemes

6. Conclusion

In this chapter, the study of optimal number of radio interfaces and new channel assignment approach was presented (FRCA). The study of optimal number of radio interfaces was created for two different topologies (grid and random), different number of data flows and different number of nodes. The study was based on increasing number of radio interfaces (1 to 8) for each mesh nodes. The results show that by increasing the number of interfaces it is possible to increase network capacity by enhancing of QoS parameters. For all simulations of WMN with common channel assignment method CCA, the number of six radio interfaces appears as an optimum solution, because the further increasing of the number of interfaces improved the capacity of WMN only slightly and using more than seven radio interfaces decreased the network performance.

For further increasing of network performances more sophisticated channel assignment algorithms were used. The new channel assignment approach called First random channel assignment (FRCA) was compared with existing channel assignment algorithms (CCA, LACA). The results show that by using the suitable CA algorithm it is possible to further increase the network capacity. From all results it can be concluded that the multi interface approach with suitable CA algorithm can dramatically increase the whole network performance. In that case, if it is used the simplest CA approach (CCA), we need to assign for each node up to 6 radio interfaces to maximize network performance, but by using suitable dynamic CA algorithm (e.g. FRCA or LACA), the network performance may be maximized with only 4 radio interfaces.

Acknowledgement

This work was supported by the Slovak Scientific Grant Agency VEGA in the project No. 1/0704/12.