Physical layer node configuration in xlink
In this section, an overview of Wireless Mesh Networks (WMNs) is presented, and some unique features which distinguish WMNs from Mobile Ad hoc Networks (MANETs) and Wireless Sensor Networks (WSNs) are listed. The main purpose of this chapter is discussed, and the contribution is presented along with the main features of this work.
The use of Wireless Local Area Networks (WLANs) has grown tremendously in the past few years due to their ease of deployment and maintenance. However, the access points in these WLANs have to be connected to the backbone network through wired media. Wireless Mesh Networks offer an attractive alternative for providing broadband wireless Internet connectivity by using a wireless backhaul network and eliminating the need for extensive cabling.
In traditional WLANs, each Access Point (AP) is connected to the wired network while only a subset of APs is connected to the wired network in WMNs. An AP that is connected to the wired network is called Gateway (GW); APs without wired connections are called Mesh Routers (MRs), and they connect to the GW through multiple hops. Like routers in a wired network, MRs in a WMN forward each other’s traffic to establish and maintain their connectivity. MRs and GWs are similar in design, with the only difference that a GW is directly connected to the wired network, while a MR is not. Figure 1 shows a sample mesh network in a typical enterprise such as a university . The following are some unique features that distinguish WMNs from MANETs and WSNs .
Mesh routers are static
Mesh routers in a WMN are stationary; therefore, the route selection should focus on discovering links that interfere with as few nodes as possible to provide high end-to-end throughput.
Mesh routers have no power constraint
In contrast to traditional wireless networks, such as MANETs and WSNs, where nodes are typically power-constrained, MRs have abundant power at their disposal.
Mesh routers have multiple radios
With the reduced cost of radios, MRs can be equipped with multiple radios. Hence, simultaneous transmission and reception can be achieved using intelligent channel assignment to these radios.
The traffic model is different
In MANETs, traffic can be from any peer Mobile Node (MN) to any other MN, while in WMNs, traffic is between MRs and the GW.
Traffic is concentrated along certain paths
In MANETs, traffic distribution is generally assumed to be uniform, while in WMN, traffic is concentrated along the paths directed towards the GW.
Traffic volume is high
MANETs have been designed essentially for enabling communication within a small group of people, while WMNs aim to provide high-bandwidth broadband connections to a large community, and thus should be able to accommodate a large number of users accessing the Internet. Due to high estimated traffic volume in WMNs, scalability and fault tolerance become important considerations in algorithm design.
To the best of our knowledge, the proposed channel assignment algorithm is the first of its kind to use topology control based on power control for channel assignment in multi-radio multi-channel wireless mesh networks.
The main purpose of network topology control using power control is to minimize the interference between a MR and other MRs in the network by adjusting its transmission range using transmission power control. This leads to a better frequency reuse during channel assignment, which results in achieving the objective of significant improvement in the overall network throughput.
Specifically, the contribution of this work is as follows: “A new Topology-controlled Interference-aware Channel-assignment Algorithm (TICA) which intelligently assigns the available non-overlapping 802.11a frequency channels to the mesh routers with the objective of minimizing interference and, thereby, improving network throughput.” The main features of this work are as follows.
A Topology Control Algorithm (TCA) named Select x for less than x; that builds the network topology by selecting the nearest neighbors for each node in the network, with the objective of minimizing interference among MRs and enhancing frequency reuse.
A scheme that uses the minimum power as the link weight when building the Shortest Path Tree (SPT) with the required node degree with the objective of minimizing interference and enhancing frequency reuse.
A Channel Assignment Algorithm (CAA), TICA, which assigns the available non-overlapping 802.11a frequency channels to the mesh nodes with the objective of improving the overall network throughput by minimizing interference between mesh nodes as well as ensuring connectivity between them. This work was first presented in .
A centralized Failure Recovery Mechanism (FRM) for TICA which provides automatic and fast failure recovery by reorganizing the network in order to bypass the failed node and to restore connectivity. This work was first presented in .
The rest of the chapter is organized as follows. The related work on topology control and CAAs is presented in Section 2. Section 3 discusses the medium access issues encountered by IEEE 802.11  single-radio single-channel nodes. The channel assignment problem is presented in this section with respect to multi-radio multi-channel wireless mesh network. Section 4 presents the network architecture for the proposed model and the proposed topology control algorithm and CAA, along with the details of their respective phases. The FRM of the proposed CAA is also presented in this section. Section 5 provides a performance evaluation of the proposed CAA. The network topologies used for performance evaluation are discussed. The results of simulations for performance evaluation of the proposed CAA based on throughput analysis of a 36-node mesh network are presented in this section. Section 6 presents the conclusions, along with some directions for future work.
This section discusses the effects of topology control on the operation of a network, gives the taxonomy of the topology control schemes for multihop wireless networks, and presents some related well-known topology control algorithms. The section also contains a taxonomical classification of the channel assignment schemes for wireless mesh networks, and discusses some related well-known channel assignment algorithms for each class.
2.1. Topology control schemes
The importance of Topology Control (TC) lies in the fact that it affects network spatial reuse and hence the traffic carrying capacity. Choosing a large transmit power results in excessive interference, while choosing a small transmit power results in a disconnected network . Using TC through transmission power control, the network connectivity and hence the network topology is affected, interference levels are mitigated, which reduces the co-channel interference, and the opportunity of spatial channel re-use is enhanced .
2.1.1. Topology control in multi-radio WMNs
The connectivity graph in a multi-radio WMN is determined through topology control. So, the problem of TC in multi-radio WMNs involves the selection of transmission power for each radio interface of each mesh node in the network, so as to maintain the network connectivity with the use of minimum power.
2.1.2. Effect of topology control
The problem of TC is complex, since the choice of the transmit power fundamentally affects many aspects of the operation of the network .
Effect of TC on the Performance of the Network
TC via transmission power control has a multi-dimensional effect on the performance of the whole network.
The transmit power levels determine the performance of medium access control, since the spatial channel reuse depends on the number of other nodes within the interference range.
The choices of power levels affect the connectivity of the network, and consequently the ability to deliver a packet to its destination .
The power level affects the throughput capacity of the network .
Power control affects the network topology which affects the number of hops, and thus the end-to-end delay.
Effect of TC on the Performance of the MAC and Routing Protocols
In addition, the assumption of fixed power levels is so ingrained into the design of many protocols in the OSI stack that changing the power levels results in their malfunctioning.
Changing power levels can create uni-directional links, which can happen when a node i’s power level is high enough for a node j to hear it, but not vice versa.
Bi-directionality of links is implicitly assumed in many routing protocols.
Medium access control protocols in IEEE 802.11 implicitly rely on bi-directionality assumption of links.
2.1.3. Taxonomy of topology control schemes
These schemes are mainly divided into two types .
This is the basic type of TC, as all the nodes are assumed to use the same transmitting range. So, the topology control problem reduces to determining the minimum value of transmission range that ensures network connectivity. This minimum transmission range is also called the Critical Transmitting Range (CTR).
In this type of TC, nodes are allowed to choose different transmitting ranges, provided they do not exceed the maximum range. Depending on the type of information that is used to compute the topology, non-homogeneous topology control is further classified into three categories.
In such schemes, exact node positions are known. If this information is used by a centralized authority to compute a set of transmitting range assignments which optimizes a certain measure such as the energy cost, this is the case of the Range Assignment Problem and its variants. The Local Minimum Spanning Tree (LMST) algorithm  and the Enhanced Local Minimum Shortest-Path Tree (ELMST) algorithm  are examples of location-based topology control schemes.
In such schemes, it is assumed that nodes do not know their position, but they can estimate the relative direction of each of their neighbors.
In such schemes, nodes are assumed to know only the ID of the neighbors, and are able to order them according to some criterion such as link quality.
2.2. Channel assignment schemes
Channel Assignment (CA) in a multi-radio WMN environment consists of assigning channels to the radios in order to achieve efficient channel utilization (i.e. minimize co-channel interference) and, simultaneously, to guarantee an adequate level of connectivity. The problem of optimally assigning channels in an arbitrary mesh topology has been proven to be NP-hard, based on its mapping to a graph-coloring problem . Therefore, channel assignment schemes employ heuristic techniques to assign channels to radios belonging to mesh nodes. A taxonomical classification of various CA schemes for wireless mesh networks is as follows .
2.2.1. Fixed channel assignment schemes
Fixed assignment schemes assign channels to radios either permanently, or for intervals that are long with respect to the radio switching time. Such schemes can be further subdivided into two types.
Common Channel Assignment (CCA)
In CCA scheme , the radios of each node are all assigned the same set of channels. For example, if each node has two radios, then the same two channels are used at every node. The main benefit is that the connectivity of the network is the same as that of a single channel approach, while the use of multiple channels increases network throughput. However, it does not take into account the effect of interference on the channel assignment in a WMN.
Varying Channel Assignment (VCA)
In the VCA class of schemes, the radios of different nodes are assigned different sets of channels. However, the assignment of channels may lead to network partitions and/or topology changes, which may increase the length of routes between mesh nodes. Therefore, in such a scheme, channel assignment needs to be carried out carefully. The VCA approach is discussed in more detail by presenting algorithms that belong to this category.
Centralized Hyacinth (C-HYA)
C-HYA, a centralized channel assignment algorithm for multi-radio multi-channel WMNs, was proposed in . Assuming that the offered traffic load is known, this algorithm assigns channels ensuring network connectivity and satisfying the bandwidth limitations of each link.
Mesh-based Traffic and interference-aware Channel-assignment (MesTiC)
MesTiC, a fixed algorithm for centralized CA, was proposed in , and visits nodes once in the decreasing order of their rank. The rank of each node is computed on the basis of its link-traffic characteristics, topological properties and number of radios on a node.
2.2.2. Dynamic channel assignment schemes
In dynamic CA schemes, any radio can be assigned any channel but additionally, radios can frequently switch from one channel to another. Therefore, when nodes need to communicate with each other in such a scheme, a coordination mechanism is required to ensure that they are on a common channel.
Multi-channel Medium Access Control (MMAC)
MMAC   is a link-layer multi-channel protocol for nodes with a single network interface. A node equipped with a single interface can only listen to one channel at a time. Therefore, in order to use multiple channels, the interface has to be switched between channels.
When nodes require to switch channels, a pair of nodes need to listen on the same channel at the time of communication and a channel coordination method is necessary, which is not required in TICA.
Distributed Hyacinth (D-HYA)
D-HYA, a dynamic and distributed channel assignment algorithm proposed in , can adapt to traffic load dynamically. The algorithm builds on a spanning tree network topology. The gateway node is the root of the spanning tree, and every mesh node belongs to that tree. Based on per-channel total load information, a WMN node determines the set of channels that are least used in its vicinity. As nodes higher up in the spanning trees need more relay bandwidth, they are given a higher priority in channel assignment. The priority of a WMN node is equal to its hop distance from the gateway.
The CA schemes, such as C-HYA, MesTiC and D-HYA, require the traffic load to be known before assigning channels, whereas TICA requires no such knowledge for channel assignment.
2.2.3. Hybrid channel assignment schemes
Hybrid channel assignment schemes combine both static and dynamic assignment properties by applying a fixed assignment for some radios and a dynamic assignment for other radios. The fixed radios can be assigned dedicated channels while the other radios can be switched dynamically among channels.
Hybrid Multi-Channel Protocol (HMCP)
HMCP   is a link-layer multi-channel protocol for nodes with multiple radio interfaces. Out of the available interfaces at each node, X interfaces are assigned statically to X channels, and these interfaces are designated as “fixed interfaces.” The fixed interfaces stay on the specified channels for long durations of time. The remaining interfaces can frequently switch between any of the remaining channels, based on the data traffic, and are designated as “switchable interfaces.”
A co-ordination protocol is required to decide what channel to assign to the fixed interface, and also for enabling neighbors of a node X to know about the channels used by fixed interface of node X. Time synchronization and coordination between mesh nodes which is required in HMCP is not needed in TICA.
Breadth First Search - Channel Assignment (BFS-CA)
BFS-CA  is a centralized, interference-aware algorithm aimed at improving the capacity of the WMN backbone and at minimizing interference. This algorithm is based on an extension to the conflict graph concept called the Multi-radio Conflict Graph (MCG) where the vertices in the MCG represent edges between radios instead of edges between mesh routers.
BFS-CA requires certain number of MRs with certain number of radio interfaces to be placed at certain hops from the gateway, whereas TICA simply requires all MRs to have four data radios, does not require any careful router placement strategy, and works with any placement of routers as verified by a comprehensive performance evaluation.
3. Channel assignment problem
In this section, the medium access issues encountered by IEEE 802.11-based single-radio single-channel WMNs are presented, and a multiple-channel approach using multiple radios to overcome these problems is discussed. The key issue of channel assignment in Multi-Radio Multi-Channel (MRMC) WMNs is presented, along with its objectives and constraints.
3.1. IEEE 802.11 medium access issues
Since the WMN has to provide access to broadband Internet, it is expected to have higher bandwidth. Even though the physical layer can support very high bit rate, current MAC protocols are not able to utilize the entire bandwidth provided by the physical layer. The main reason for this poor performance is the suboptimal media access protocols, which were primarily designed for single-hop networks .
3.1.1. Hidden and exposed terminal problems
IEEE 802.11 Distributed Coordination Function (DCF) is one such widely accepted MAC protocol but, when used in a multihop network scenario, it results in poor performance and is therefore unacceptable. The reason is that some nodes remain starved due to hidden and exposed terminals in a multihop environment. Figure 2 illustrates these problems .
Node 2, which is outside the interference range of Node 3 and unaware of the ongoing transmission at Node 3, continues to send RTS to Node 1 causing collision. This is a case of the hidden terminal problem.
Node 4 is prevented from transmitting because of the neighboring transmission at Node 3. This is a case of the exposed terminal problem.
3.2. Wireless mesh network architectures
3.2.1. Single-radio single-channel mesh network
A Single-Radio Single-Channel (SRSC) mesh architecture suffers from hidden and exposed terminal problems. Assigning orthogonal channels to the MRs within the interference range can help alleviate the hidden and exposed terminal problems, and assist in improving the overall capacity of the network. However, considering the traffic characteristics in a WMN, frequent channel switching may be required to communicate with neighboring nodes. In such scenarios, single-radio multi-channel MAC may not provide any significant performance gains due to high channel switching delay.
3.2.2. Multi-radio multi-channel mesh network
The use of a multi-channel approach using multiple radios overcomes the problems encountered in the previous architectures . Two or more radios are employed for the backhaul link. The uplink and downlink backhaul radios operate at non-overlapping channels which eliminates the co-channel interference.
As each mesh router can be equipped with multiple radios, fixed channel assignment to these radios is a more viable solution. Efficient and intelligent channel assignment schemes have to be designed, as the number of channels is limited.
3.3. Channel assignment problem
In a typical WMN, the total number of radios is much higher than the number of available channels. Thus, many links between the mesh routers operate on the same set of channels and interference among transmissions on these channels decreases their utilization. Therefore, minimizing the effect of interference is required for the efficient reuse of the scarce radio spectrum. So, the key issue in a MRMC WMN architecture is the channel assignment problem, which involves assigning a channel to each radio of a MR in a way that minimizes interference on any given channel and guarantees connectivity between the mesh nodes .
Given the connectivity graph, the main challenge for CAA is to assign a channel to each radio in a way that minimizes interference between MRs and ensures connectivity between them. In order to achieve these goals, the CAA should satisfy the following requirements.
In order to communicate, a pair of nodes within transmission range of each other needs to have a common channel assigned to their end-point radios.
Links in direct interference range of each other should be assigned non-overlapping channels.
The number of distinct channels that can be assigned to a mesh router is bounded by the number of radios it has.
The total number of non-overlapping channels is fixed.
Since the traffic in a WMN is directed to and from the gateway, the traffic flows aggregate at routers close to the gateway. Therefore, priority in channel assignment should be given to links starting from the gateway based on the number of nodes that use a link to reach the gateway.
At first glance, the problem of assigning channels to links in a mesh network appears to be a graph-coloring problem. However, standard graph-coloring algorithms cannot satisfy all of its constraints, and it is NP-hard to find an optimal channel assignment to maximize the overall network throughput . Also, the channel assignment problem for mesh networks is similar to the list coloring problem, which is NP-complete .
4. Topology control and channel assignment algorithms
In this section, the network architecture of the proposed model is presented. The section presents the proposed topology control and channel assignment algorithms for MRMC WMNs, and details on the working of different phases of the proposed algorithms are discussed. The procedure of fault recovery with the proposed CAA is also presented in this section.
4.1. Network architecture
In our proposed model, each mesh router is equipped with five radios which operate on IEEE 802.11a channels (5 GHz band). One of these radios is used for control purpose while other radios are used for data traffic.
The control radios of all mesh nodes operate on the same non-overlapping IEEE 802.11a channel. Out of the 12 available non-overlapping 802.11a channels, channel 12 is used as the common control channel. Each mesh router is equipped with 4 data radios in order to utilize the remaining 11 non-overlapping channels available in IEEE 802.11a frequency band. Each MR communicates with its transmission range (TR) neighbors using these data radios for data transmission. So, each MR can have a maximum of 4 TR neighbors with whom it can communicate for data transmission which implies that the Maximum Node Degree (MND) per node is four. The MND of 4 is selected in order to fully utilize the 11 available non-overlapping 802.11a frequency channels. Results have shown that with 12 available non-overlapping channels, the network throughput increases until a MND of four but saturates after that .
4.2. Topology control algorithm
The proposed Topology Control Algorithm (TCA) controls the network topology by selecting the nearest neighbors for each node in the network. The objective of the proposed TCA is to build a connectivity graph with a small node degree to mitigate the co-channel interference and enhance spatial channel reuse as well as preserve network connectivity with the use of minimal power, as less transmit power translates to less interference.
4.2.1. Gateway advertisement process
Initially, the gateway broadcasts a “Hello” message, using its control radio on the control channel, announcing itself as the gateway. Each mesh node that receives this Hello message over its control radio broadcasts it again and in this way, this Hello message is flooded throughout the mesh network. The Hello message contains a hop-count field that is incremented at each hop during its broadcast. So, a mesh node may receive multiple copies of the Hello message over its control radio. However, distance of a mesh node from the gateway is the shortest path length (shortest hop count) of the Hello message received by a mesh node through its control radio over different paths. In this way, each mesh node knows the next hop to reach the gateway using its control radio.
The proposed TCA assumes the following.
Each node knows its location.
Each node uses an omni-directional antenna for both transmission and reception.
Each node is able to adjust its own transmission power.
The maximum transmission power is the same for all nodes and hence, the maximum TR for any pair of nodes to communicate directly is also the same.
Note that all nodes start with the maximum transmission power, and that the initial topology graph created, when every node transmits with full power, is strongly connected.
4.2.3. Phases of TCA
The proposed TCA consists of the following five phases.
Exchange of Information Between Nodes
In the first exchange, each node broadcasts a HELLO message at maximum transmission power containing its node ID and the node position.
Building the Maximum Power Neighbor Table (MPNT)
From the information in the received HELLO messages, each node arranges its neighboring nodes in the ascending order of their distance. The result is the Maximum Power Neighbor Table (MPNT). Then, each node sends its MPNT along with its position and node ID to the gateway node using its control radio over the control channel.
Building the Direct Neighbor Table (DNT)
For each node in the network, the gateway builds a Direct Neighbor Table (DNT). Based on information in the MPNT of node v and the MPNTs of its neighbors, if
(a) node w is in the MPNT of node v, and
(b) node w is closer to any other node y in the MPNT of node w than to node v, then gateway eliminates node w from the MPNT of node v.
If, after removing nodes from the MPNT of node v, the remaining number of nodes in the MPNT of node v is less than “x,” then the gateway selects “x” nearest nodes as neighbors of node v which results in the DNT. However, if after removing nodes from the MPNT of node v, the remaining number of nodes is greater than or equal to “x,” then the result is the DNT.
This algorithm is called Select x for less than x TCA where x is a positive integer. The Select x for less than x TCA ensures that each node has at least x neighbors, as shown in Figure 3.
Converting into Bi-directional Links
For each node in the network, the gateway converts the uni-directional links in the DNT of a node into bi-directional links. For each uni-directional link, this is done by adding a reverse link in the DNT of the neighboring node. This converts the DNT into Bi-directional DNT. This results in the Final Neighbor Table (FNT).
Calculating the Minimum Power Required
For each node in the network, the gateway calculates the minimum power, Pmin, required to reach each of the nodes in the FNT of a node, using the appropriate propagation model.
4.2.4. Propagation models
The free space model is used for short distances and the two ray ground reflection model is used for longer distances, depending on the value of the Euclidean distance in relation to the cross-over distance. The cross-over distance is calculated by 
where ht and hr are the antenna heights of the transmitter and receiver, respectively. If the distance between two nodes is less than the cross over distance, i.e. d(u,v) < Cross_over_dist, Free Space propagation model is used, whereas if d(u,v) > Cross_over_dist, Two-ray propagation model is used. The minimum power for the free-space propagation model is calculated by 
The minimum power for the two-ray propagation model is calculated by 
where Gt and Gr are transmitter and receiver antenna gains respectively, and RxThresh is power threshold required by radio interface of receiving node to correctly understand the message.
4.3. Channel assignment algorithm
4.3.1. Interference-range edge coloring
If K be the number of available colors (channels), then for K ≥ 4, the distance-2 edge coloring problem, also known as strong edge coloring problem, is NP-complete . A distance-2 edge coloring of a graph G is an assignment of colors to edges so that any two edges within distance 2 of each other have distinct colors. Two edges of G are within distance 2 of each other if either they are adjacent, as shown in Figure 4a or there is some other edge that is adjacent to both of them, as shown in Figure 4b. The distance-2 edge coloring has been used in  for channel assignment, where the authors have described the interference model as two-hop interference model. In this model, two edges interfere with each other if they are within two-hop distance. In other words, two edges e1 and e2 cannot transmit simultaneously on the same channel if they are sharing a node or are adjacent to a common edge.
To minimize co-channel interference in a wireless mesh network, it is necessary to assign channels to links such that links within interference range of each other are assigned different channels (colors). This problem can be termed as interference-range edge coloring, and the corresponding interference model can be called interference-range interference model. In a grid topology where links are of equal length, the interference-range edge coloring is similar to distance-2 edge coloring, as shown in Figure 5a. The channel assigned to link l1 cannot be assigned to links l2 and l3 as they are within the interference range of link l1. Note that l2 and l3 are also within two-hop distance of l1.
However, in a random topology where links are of different lengths due to the random nature of the topology, the interference-range edge coloring can be harder than distance-2 edge coloring as shown in Figure 5b. In this case, the channel assigned to link l1 cannot be assigned to links l2, l3 and l4 as they are within the interference range of link l1. Note that l2, l3 and l4 are within three-hop distance of l1.
In the proposed network model, the number of available channels (colors) is 11 which means that K = 11. Based on its similarity to distance-2 edge coloring problem which is NP-complete for K ≥ 4, the interference-range edge coloring problem is, therefore, also NP-complete. Therefore, we propose an approximate algorithm for channel assignment. The proposed channel assignment algorithm, TICA, is shown in Figure 6 and has the following phases.
4.3.2. Phases of TICA
In order to create the network connectivity graph with the aim of reducing the interference between MRs, network topology is controlled using the topology control algorithm.
All nodes send their MPNTs to the gateway using their control radio. Note that in order to send its MPNT to the gateway, each mesh node knows the next hop to reach the gateway using its control radio via the “gateway advertisement process.” The gateway starts with the Select 1 for less than 1 TCA and builds the FNTs of all nodes.
Based on the FNTs of all nodes, the gateway builds the connectivity graph and checks the resulting network for connectivity. A topology is said to be connected if the gateway can reach any node in the connectivity graph directly or through intermediate hops.
If the resulting network is not connected, the gateway moves to the next higher TCA by incrementing x in the Select x for less than x TCA, builds the connectivity graph and checks the resulting network for connectivity. The gateway keeps on moving to a higher TCA until it finds that the network resulting from the connectivity graph is connected.
Minimum Power-based Shortest Path Tree with a MND of Four
After ensuring that the connectivity graph is connected, the gateway builds the Shortest Path Tree (SPT), using Dijkstra’s algorithm , based on the connectivity graph. The metric for path selection is minimum power.
The node degree is defined as the number of TR neighbors of a node. The number of TR neighbors of a mesh router is bounded by the number of its radios and each node has four data radios. So, if any node in the shortest path tree has more than four links, the gateway selects those four links for that node which have the minimum weight and sets the weight of all other links to infinity. In other words, the gateway ensures that each node can have a maximum of four TR neighbors and builds a Minimum Power-based SPT (MPSPT) with a MND of 4 per node. The gateway checks the resulting MPSPT graph for connectivity. If the resulting MPSPT graph is not connected, the gateway moves to a higher TCA.
Once the MPSPT graph is determined, the gateway has to assign channels to links of the MPSPT. Now, the objective is to assign channels to the links of the MPSPT such that the interference between simultaneous transmissions on links operating on the same channel is minimized and the overall network throughput is maximized.
In order to assign channels to the links of the MPSPT graph, each link is assigned a ranking by the gateway. The ranking associated with each link is derived from the number of nodes that use a link to reach the gateway node. If l is link and n is node using link l to reach the gateway, then rank of link l, i.e. rl, is given byE4
where N is the total number of nodes in the network. In,l is 1 if node n is using link l and 0 otherwise.
In the case of two or more links that have the same rank, the link whose power of the farthest node to the gateway is smaller is given priority in channel assignment. If there are some links that still have the same rank, the link with smaller node IDs is given priority in channel assignment.
The gateway assigns a channel to each link in the order of its rank, and it begins with assigning the 11 available non-overlapping channels to the 11 highest-ranked links such that Channel 1 is assigned to the highest-ranked link. For the 12th-ranked link and onwards, the gateway checks the channel assignment of all links within the interference range of both nodes that constitute that link.
Out of the 11 available channels, channels which are not assigned to any link within the interference range of both nodes that constitute the 12th-ranked link are termed as non-conflicting channels. If the gateway finds one or more non-conflicting channels, it assigns that channel from the unassigned non-conflicting channels to the 12th-ranked link which has the highest channel number.
Least Interfering Channel
If the gateway cannot find any channel among the 11 available channels that is not assigned to any link within the interference range of both nodes that constitute the 12th-ranked link, it selects the least interfering channel and assigns it to that link. A Least Interfering Channel (LIC) is a channel which causes minimum interference within the interference range of both nodes that constitute the 12th-ranked link.
In order to find out the LIC, the gateway builds the interference level (IL) for all the 11 channels. The LIC is the channel with the minimum IL, which means that assigning this channel to the 12th-ranked link would result in minimum interference in the network.
In order to build the IL for Channel One, the gateway finds all links within the interference range of each of the two nodes that constitute the 12th-ranked link that use Channel One, and calculates IL of each link based on its rank and distance from a node of the 12th-ranked link. It sums up individual ILs of all links that use Channel One within the interference range of each of the two nodes that constitute the 12th-ranked link, to find out total IL for Channel One. This is done byE5
where i is the channel that has value between 1 and 11,
(IL)i is interference level of channel i,
m is a link using channel i that is within the interference range of a node of the 12th-ranked link,
r is the rank of link m,
R is the maximum rank assigned to a link,
d is distance from a node of link m to a node of the 12th-ranked link, and
α is the path loss exponent and is 2 or 4, depending on cross over distance.
If a link is emanating from either of the two nodes that constitute the 12th-ranked link and a channel has been assigned to that link, then the IL for this channel is set to infinity.
The LIC is the channel with the minimum interference level and is selected byE6
Similarly, the gateway assigns channels to all the links of the MPSPT.
Channel Assignment and Routing Message
Using its control radio, the gateway then sends each mesh node the Channel Assignment and Routing Message (CARM). For each channel assigned to a mesh router, CARM contains the channel number and the neighbor node to communicate with, using this channel. The CARM also contains the next hop to reach the gateway for data traffic. Based on the channel assigned to a mesh router to communicate with a neighbor and its distance to that neighbor, the mesh router applies power control and adjusts its transmission power accordingly by using the appropriate propagation model.
4.3.3. Failure recovery mechanism of TICA
When a node fails, nodes in its sub-tree lose their connectivity to the gateway and hence, the Internet through the wired world. TICA supports automatic and fast failure recovery and reorganizes the network to bypass the failed node and to restore the connectivity. In case of node failure, the FRM of TICA, which is shown in Figure 7, is initiated by the gateway.
All nodes send periodic "keep-alive" messages to the gateway on the control channel using their control radios. The keep-alive message from a node tells the gateway that the node is active. If the gateway does not receive three consecutive keep-alives from a node z, then it concludes that node z has failed and is no longer active. The gateway then deletes the MPNT for this node and deletes node z from the MPNT of all its neighboring nodes. Note that the gateway has MPNTs of all nodes, as all nodes sent their MPNTs to the gateway during the setup phase. The gateway builds the FNTs for all nodes using the Select x for less than x TCA.
Based on the FNTs of all nodes, the gateway builds the connectivity graph, the MPSPT with a MND of four, the link ranking for the links of the MPSPT and assigns the channels to all links of the MPSPT. The gateway then sends the new CARM to all nodes in the network on the control channel.
5. Performance evaluation
In this section, the performance evaluation of the proposed channel assignment algorithm is provided. Different topologies used for performance evaluation are presented. The performance of the proposed channel assignment algorithm for MRMC WMNs is compared against a “Single-Radio Single-Channel” (SRSC) scheme and a “Common Channel Assignment” (CCA) scheme for multi-radio mesh nodes. The detailed results of simulations for performance evaluation of TICA based on throughput analysis of a 36-node network are presented, and analyzed. The features' comparison of TICA with related well known channel assignment schemes is also given.
5.1. Simulation environment
For the performance evaluation via throughput analysis, xlink (version 2.30)  simulation tool is used. However, MATLAB  is used to generate the power controlled topology, the MPSPT graph, the link ranking of the MPSPT and the channel assignment for the links of the MPSPT.
Multi-interface wireless mesh nodes are created in xlink by modifying the built-in IEEE 802.11 node model in xlink, using the procedure given in . Based on the channel assignment by the gateway, the radio interfaces are configured for each node and the transmission power for each radio of each mesh node is set accordingly. All the mesh nodes at the periphery of the network send traffic to the gateway. Each of these nodes generates an 8 Mbps Constant Bit Rate (CBR) traffic stream consisting of 1024 byte packets, and sends data to the gateway node at the same time. They do not stop transmitting until the end of the simulation. So, this is a scenario in which multiple flows within the mesh network interfere with each other.
All radios are IEEE 802.11a radios and support 12 channels. The first 11 non-overlapping channels are used by the data radios, whereas the 12th channel is used by the control radio on each node. If the distance between the nodes is less than the cross-over distance, free space propagation model is used; if the distance between the nodes is greater than the cross-over distance, two-ray propagation model is used. As per , the minimum receiver sensitivity (RxThresh) is set to -65 dBm (Watts) in order to achieve a maximum data rate of 54 Mbps supported by IEEE 802.11a.
In order to achieve a strongly connected topology, the maximum transmission power for all the radios is set to 27 dBm. The maximum power transmission range is 164 meters and the maximum power interference range is 328 meters. RTS/CTS is disabled. Note that in the CCA and SRSC schemes, the mesh nodes do not control their power, transmit with the same maximum power (27 dBm) and use AODV (Ad hoc On-Demand Distance Vector)  routing protocol as their routing agent.
5.2. Network topologies
Three types of topologies are used in the evaluation. Each topology consists of 36 mesh nodes distributed in an area of 500x500 meters.
Topology 1 is a grid topology; Topology 2 is a randomly generated topology while in Topology 3, called controlled random, the physical terrain is divided into a number of cells and a mesh node is placed randomly within each cell.
Grid Topology (GT) is used to evaluate TICA in a densely populated topology. Random Topology (RT) is used to evaluate TICA in an unplanned deployment of randomly and uniformly distributed mesh nodes. Controlled Random Topology (CRT) is used to reflect real-world deployments where mesh routers are uniformly distributed for maximum coverage.
5.3. Simulation results based on throughput analysis
5.3.1. Simulation parameters
The physical layer and MAC layer settings of the node which are used during the simulation are shown in Tables 1 and 2, respectively. Note that out of the 12 available non-overlapping 802.11a channels, 11 channels are used for data traffic and channel 12 is used for control. Based on the channel assignment by the gateway node, IEEE 802.11a channels are assigned to the links between the mesh nodes and transmission power for each radio of each mesh node is set accordingly.
|Physical Layer Parameter||Setting|
|Antenna Type||Omni Antenna|
|TX/RX Antenna Height (meters)||3|
|Gain of TX/RX Antenna||1|
|Packet Capture Threshold (SIR) (dB)||10|
|Packet Reception Threshold (watts)||3.16227e-10|
|Carrier Sense Threshold (watts)||7.90569e-11|
|System Loss Factor||1|
As mentioned earlier, the maximum transmission power for all the radios is 27 dBm. In the CCA and SRSC schemes, MRs do not control their power, transmit with the same maximum power (27 dBm), and use AODV (Ad hoc On-Demand Distance Vector) routing protocol as their routing agent.
|MAC Layer Parameter||Setting|
|Minimum Contention Window||15|
|Maximum Contention Window||1023|
|Slot Time (micro seconds)||9|
|SIFS period (micro seconds)||16|
|Preamble Length (bits)||96|
|PLCP Header Length (bits)||24|
|PLCP Data Rate (Mbps)||6|
|Basic Rate (Mbps)||6|
|Data Rate (Mbps)||54|
|RTS/CTS Threshold (bytes)||10192 (disabled)|
All the mesh nodes at the periphery of the network send traffic to the gateway. Each of these nodes generates an 8 Mbps Constant Bit Rate (CBR) traffic stream consisting of 1024 byte packets and sends data to the gateway node at the same time. They do not stop transmitting until the end of the simulation, which is 600 seconds (10 minutes).
5.3.2. Simulation results
The Average Throughput (AT) in Mega bits per second at the gateway node is calculated using the following formula:
Note that TPR is the Total Packets Received in (7).
Figure 8 shows a graphical comparison of the average throughput of all schemes for ten random topologies. The results in this figure clearly indicate that the proposed algorithm TICA significantly outperforms other schemes for all different random topologies.
Controlled Random Topology
Figure 9 shows a graphical comparison of average throughput of all schemes for ten controlled random topologies. The results in this figure clearly indicate that the proposed algorithm TICA significantly outperforms other schemes for all different controlled random topologies.
The placement of the nodes and hence, the length of links in the MPSPT of a topology affects the interference range and hence, the channel assignment. In random and controlled random topologies, the random placement of nodes results in variation in the length of links in the MPSPT. This results in LICs, which may cause significant interference in the network and degrade the overall throughput.
Throughput Comparison for the three topologies
Figure 10 shows the comparison of average throughput of all schemes for the three topologies (random, controlled random and grid) for a network of 36 nodes.
Note that for random and controlled random topologies in Figure 10, the average throughput is the average over ten different random and controlled random topologies, respectively. Figure 10 shows that as compared to the CCA scheme, the throughput improvement with TICA is 3 times for random topology, 11 times for controlled random topology and 12 times for grid topology. In comparison to the SRSC scheme, the throughput improvement with TICA is 8 times for random topology, 95 times for controlled random topology and 133 times for grid topology.
The results in this figure clearly indicate that the proposed algorithm, TICA, significantly outperforms other schemes for the three topologies.
5.4. Features’ comparison of related CA schemes
The important features of the related CA schemes are summarized in Table 3. They include channel switching, topology control, power control, knowledge of traffic load, connectivity, fault tolerance and CA control.
The most significant difference between TICA and existing CA schemes is that TICA uses topology control based on power control to build the topology for CA with the objective of minimizing the interference between the MRs whereas no other CA scheme has used topology control based on power control for CA.
Another significant difference between TICA and most other existing CA schemes is that TICA performs routing in addition to CA whereas most other CA schemes rely on routing protocols and complicated routing metrics for route selection.
Unlike TICA and D-HYA, other well-known CA schemes do not possess fault tolerance and have not provided any mechanism for recovery after a node failure.
6. Conclusion and future work
The chapter finally concludes in this section along with some directions for future work.
A new topology control algorithm for multi-radio WMNs, Select x for less than x, is proposed. It controls the network topology by selecting the nearest neighbors for each node in the network.
A new channel assignment algorithm for MRMC IEEE 802.11a-based WMNs, TICA, is proposed, which is based on topology control. As verified by a comprehensive performance evaluation, the improvement in the overall network throughput with TICA is significantly higher than the CCA scheme but is much higher than SRSC scheme in all three topologies. This is due to the fact that topology control based on power control results in an efficient frequency reuse during CA, which leads to an overall improvement in the network throughput.
In the CCA and SRSC schemes, which are two commonly-used benchmark schemes, MRs do not control their power, transmit with maximum power, and use AODV routing protocol as their routing agent. TICA, on the other hand, uses topology control by selecting the nearest neighbors for each mesh node in the network, which reduces the interference among the mesh routers. It uses the minimum power as the link weight when building the SPT with the required node degree as less power translates to less interference among the mesh routers. It uses a scheme to build the IL for all the frequency channels if all the available frequency channels have already been assigned within the interference range of a link. It assigns a LIC to a link if all the available frequency channels have already been assigned within the interference range of that link. LIC is the channel with the minimum IL, which means that assigning this channel to the link would result in minimum interference in the network. In TICA, from the information in the received CARM, each mesh router applies power control and adjusts its transmission power accordingly, based on the channel assigned to that mesh router to communicate with a neighbor and its distance to that neighbor.
As per the specification of the IEEE 802.11s standard for wireless mesh networks, the mesh routing protocol has to reside in the MAC layer. TICA not only performs channel assignment but performs routing as well by providing each node with the next hop information to reach the gateway node and hence, conforms to the requirements of IEEE 802.11s.
A centralized Failure Recovery Mechanism for TICA is proposed, which supports automatic and fast failure recovery. In case of node failure, after detecting the failed node, deleting the MPNT of the failed node and deleting it from the MPNT of its neighbors, the gateway runs the TCA and builds the MPSPT. Based on the new MPSPT, the gateway calculates the link rankings and the channel assignments. The new channel assignments are communicated to the mesh nodes by the gateway via a new CARM using the control radio over the control channel.
The proposed CA algorithm, TICA, does not require modifications to the MAC protocol and therefore, can work with existing IEEE 802.11a-based interface hardware.
6.2. Future work
Following are some aspects of this work which can be extended in future.
Since TICA uses the new approach of building the interference level for all the frequency channels, it can be enhanced to model and account for the interference from co-located wireless networks.
Other algorithms for building the tree topology, such as Prim’s algorithm  and Kruskal’s algorithm , can be used for building the minimum power based tree, which may lead to a further enhancement in the overall network throughput.
TICA C-HYA BFS-CA MesTiC D-HYA HMCP CA control Centralized Centralized Centralized Centralized Distributed Distributed Knowledge of traffic load Not required Required Not required Required Required Not required Channel switching Required for failure recovery Not required Periodic channel switching required Not required Required as CA changes with traffic Per-packet channel switching required Topology Topology controlled using TCA Fixed Fixed Fixed Topology defined by spanning tree Topology changing due to channel switching Power control Yes No No No No No Connectivity Ensured by common control radio, ensured by the CA scheme Ensured by the CA scheme Ensured by common control radio Ensured by common control radio Ensured by the CA scheme Ensured by channel switching Routing Performed by the CA scheme No No No Performed by the CA scheme No Failure recovery Yes No No No Yes No
Other schemes for building the tree topology with the required node degree, such as the one proposed in , can be used which may lead to a better performance.
The propagation model used is free-space model or two-ray model depending upon the cross-over distance. The performance of the proposed algorithm may be tested under more realistic propagation models such as Shadowing, Rayleigh-fading.
The carrier sensing range is generally assumed to be twice the transmission range. However, carrier sensing range is a tunable parameter and an optimally tuned carrier sensing range can improve the network throughput in wireless mesh networks by enhancing the spatial frequency reuse and reducing collisions . The performance of the proposed algorithm can be improved by controlling the carrier sensing range.
The phenomenon of topology control based on power control impacts the per-node fairness of medium access based on CSMA/CA and hence the per-flow end-to-end throughput fairness . The proposed algorithm can be extended to ensure per-node and hence per-flow fairness.
All the traffic in a WMN is directed towards the gateway. The traffic bottleneck at the gateway is the main reason of the capacity limitation of a WMN. The use of multiple gateways can increase the capacity of the WMN by preventing the formation of traffic bottlenecks . The proposed algorithm can be enhanced by extending it for multiple gateways.
List of acronyms and abbreviations
AODVAd hoc On-Demand Distance Vector
BFS-CABreadth First Search – Channel Assignment
CAAChannel Assignment Algorithm
CARMChannel Assignment and Routing Message
CBRConstant Bit Rate
CCACommon Channel Assignment
CRTControlled Random Topology
CSMA/CACarrier Sense Multiple Access with Collision Avoidance
DNT Direct Neighbor Table
FNTFinal Neighbor Table
FRM Failure Recovery Mechanism
HMCPHybrid Multi-Channel Protocol
LIC Least Interfering Channel
MACMedium Access Control
MANETMobile Ad hoc Network
MCG Multi-Radio Conflict Graph
MesTiCMesh-based Traffic and interference-aware Channel-assignment
MMACMulti-channel Medium Access Control
MNDMaximum Node Degree
MPNTMaximum Power Neighbor Table
MPSPTMinimum Power-based Shortest Path Tree
xlinkNetwork Simulator Version 2
SPT Shortest Path Tree
TCATopology Control Algorithm
TICA Topology-controlled Interference-aware Channel-assignment Algorithm
VCAVarying Channel Assignment
WLANWireless Local Area Network
WMNWireless Mesh Network
WSNWireless Sensor Network