SNR of transmission made on channel 6 as received on channels 1... 11.
The concept of wireless mesh networks (WMN) has emerged as a promising technology for the provision of affordable and low-cost solutions for a wide range of applications such as broadband wireless internet access in developing regions with no or limited wired infrastructure, security surveillance, and emergency networking, One concrete example is WMNs for public safety teams like firefighters who can still be connected with the help of mesh nodes mounted on street poles even if all infrastructure communications fail. The main reason for this vast acceptance of mesh networks in the industry and academia is because of their self-maintenance feature and the low cost of wireless routers. In addition, the self-forming features of WMNs make the deployment of a mesh network easy thereby enabling large-scale networks. Mesh networks which are of most commercial interests are characterized as fixed backbone WMNs where mesh nodes (routers or access points) are generally static and are mostly supplied by a permanent power source. Such a wireless mesh network architecture is illustrated in Figure 1, consisting of mesh routers, clients, and gateway nodes. Mesh routers (MR) communicate with peers in a multi hop fashion such that packets are mostly transmitted over multiple wireless links (hops). Therefore, nodes forward packets to other nodes that are on the route but may not be within direct transmission range of each other. Routers which are connected to the outside world are called gateway nodes (GWN). These GWNs carry traffic in and out of the mesh network. The collection of such routers and gateway nodes connected together in a multi hop fashion form the basis for an infrastructure WMN (also called backbone mesh). Moreover, the multi hop packet transmission in an infrastructure WMN extends the area of wireless broadband coverage without wiring the network; thus WMNs can be used as extensions to cellular networks, ad hoc networks (MANET), sensor and vehicular networks, IEEE 802.11 WLANs (Wi-Fi), and IEEE 802.16 based broadband wireless (WiMax) networks .
WMNs can be classified based on the number of radios on each mesh router. In single-radio mesh networks, each node is equipped with only one radio. In multi-radio mesh networks, multiple radios are installed on each mesh node in the backbone mesh. Depending upon the radio to channel configuration (also called interface to channel assignment), mesh networks can be further classified into single-radio single-channel (SRSC), single-radio multi-channel (SRMC), and multi-radio multi-channel (MRMC) wireless mesh networks. (Note, that we did not list multi-radio single-channel WMNs as that would mean that nodes are equipped with multiple radios but all of the radios in the network are configured on the same single channel defeating any purpose of multi-radios.) In a SRSC-WMN, as the name suggests, all nodes are configured to use the same wireless channel. This ensures network connectivity; however, capacity of the network is greatly affected as all nodes are competing to access the same channel. Therefore, interference minimization is the major issue in such networks. SRMC-WMNs can achieve parallel transmissions by assigning different orthogonal channels (OCs) to radios belonging to different nodes, thus improving network capacity. However, such networks severely suffer from network disconnections due to having a single radio at each node possibly configured at different channels. In, MRMC-WMNs, with the availability of off-the-shelf, low cost, IEEE 802.11 based networking hardware, it is possible to incorporate multiple radio interfaces operating on different radio channels on a single mesh router. This enables a potentially large improvement in the capacity of the WMN (compared to all the previous forms of mesh networks) .
Wireless mesh networks, particularly infrastructure WMNs, have some unique characteristics that set them apart from other wireless networks, such as MANETs and sensor networks. For example, nodes (at least relay nodes) in a typical infrastructure mesh network are generally static and have no significant constraints on power consumption, as opposed to MANETs, where nodes have limited energy and are mostly mobile. Similarly, due to the shared nature of the wireless medium, nodes compete with each other for channel access when they transmit on the same channel resulting in possible interference among the nodes. Unlike MANETs, where the general traffic model describes traffic flows between any pair of mobile nodes, in WMNs data flows are typically between mesh nodes and GWNs. In general, in WMNs certain paths and nodes are much more likely to be saturated as the distribution of flows over nodes is less uniform compared to that in MANETs. Therefore, load balancing is of utmost importance to avoid hot spots and to increase network utilization.
In a typical multi radio mesh network, the total number of radios within the network is usually significantly higher than the number of available channels in the network (e.g. only 11 channels are available in the U.S.A. for IEEE 802.11b/g). This forces many links to operate on the same (set of) channels, resulting in possible interference among transmissions. The existence of such interference if not accounted for, can affect the capacity of the network. Therefore, understanding and mitigating interference has become one of the fundamental issues in WMNs; recently a number of channel assignment (CA) solutions have been proposed to address this problem [5, 10-13, 15-20, 33-35].
The problem of channel assignment (frequency assignment) has been widely studied in cellular networks . However, with the proliferation of IEEE 802.11 based technologies in the wireless arena (WLANs, sensor networks, WMNs), the need for channel assignment solutions outside of cellular networks has surfaced. CA algorithms are usually designed based on the peculiar characteristics of individual networks; since the differences in characteristics are vast, CA algorithms for WMNs must be significantly different from those of cellular networks. For example, base stations in a cellular network are typically connected by cables, whereas mesh nodes in a mesh network are connected wirelessly (and usually on the same channels as are used for providing service). This brings up several interference issues in mesh networks between mesh nodes which are not found in cellular networks between base stations (as in cellular networks BSs are not competing for the shared medium as they have dedicated bandwidth for intra-BS communication). The bottleneck in cellular networks is from the base stations to the client devices, whereas, in WMNs, the bottleneck is usually inside the mesh backbone, typically along the route from the mesh routers to the gateway nodes. In addition nearby BSs are usually configured on completely orthogonal channels (OCs) to avoid interference; this is rarely possible in backbone meshes, as the nodal density of a typical WMN can be high and the number of available orthogonal channels is limited. Most existing deployed mesh networks are IEEE 802.11 technology based; among the standards of IEEE 802.11, the most widely used are IEEE 802.11b/g, which support up to 14 channels in the unlicensed Industrial, Scientific, and Medical (ISM) radio bands at the nominal 2.4 GHz carrier frequency . Out of these 14 channels, only 11 channels are available for use in the U.S.A., 13 channels are open in EU, while Japan has made all of them available. Figure 2. shows the 2.4 GHz ISM band’s division into 11 IEEE 802.11b/g channels in the U.S.A.; the channel numbers have a one-to-one relationship with the corresponding center frequency of that channel. (For example, channel 6 operates at 2.437GHz.) Each channel’s bandwidth is 22 MHz and each channel's center frequency is separated from the next channel’s by 5MHz. Therefore, in general, a channel overlaps with 4 of its neighboring channels leaving only three non-overlapping (orthogonal) channels, i.e., channels 1, 6, and 11 as depicted in Figure 2. Similarly, IEEE 802.11a operates in 5GHz ISM band and provides 12 orthogonal channels, but since it operates in a higher frequency band, it has a shorter range as opposed to 802.11b/g (higher frequencies in general have higher inabilities to penetrate walls and obstructions). Recently, the IEEE 802.11n standard was proposed which operates in both the 2.4GHz and 5 GHz bands and provides legacy support to devices operating based on previous standards (b/g). It provides data rates of up to 600Mbps using Multiple Input, Multiple Output (MIMO) technology with Orthogonal Frequency Division Multiplexing (OFDM).
Most existing research on CA algorithms in WMNs has been focused on assigning orthogonal (non-overlapping) channels [33-35] to links belonging to neighboring nodes in order to minimize the interference in the network. Since, links operating on orthogonal channels do not interfere at all, multiple parallel transmissions can be possible resulting in overall network throughput improvement. The number of non-overlapping channels in commodity wireless platforms such as 802.11b/g is very small (again, only three orthogonal channels out of total 11 channels) while nodal density in a typical MRMC-WMN is high. This realization has recently drawn significant attention to the study of partially overlapped channels (POC) for channel assignment . The basic idea is to make all channels available to nodes for channel selection as a result of which, partially overlapped channels may be employed. This could enable multiple concurrent transmissions on radios configured on POCs and therefore could increase network capacity assuming that the interference is lessened in POCs compared to completely overlapping channels.
Previously, an algorithm for channel assignment based solely on orthogonal channels had to deal with only co-channel interference. However, one of the major issues in designing efficient channel assignment schemes using POCs is the adjacent channel interference, which is the interference between two neighbors configured on adjacent (partially overlapping) channels. The effect of such adjacent channel interference has a direct relationship with the geographical location of these two nodes, i.e., the farther two nodes are apart, the less interference is created on adjacent channels. Nonetheless, the assignment of orthogonal and non-orthogonal channels in high density mesh networks needs to be carefully coordinated; the key issue lies in the fact that the interference between adjacent channels has to be considered. This needs to be done intelligently so that channel capacity is maximized, otherwise the shared nature of wireless medium can lead to serious performance degradation of the whole mesh network. Thus, recently POCs for channel assignment in wireless networks has received some attention [5, 10-13, 15-20].
Within the scope of this chapter, we focus on the problem of channel assignment using partially overlapping channels in the context of both single- and multi-radio WMNs. The rest of the chapter is organized as follows. Section 2 describes different types of interferences that may exist in a typical WMN. Section 3 demonstrates the benefits of using partially overlapping channels for channel assignment in WMNs with the help of experiments performed on a real testbed. In Section 4, we provide a comprehensive review of some of the recent well-known channel assignment schemes exploiting POCs in WMNs and classify these POC-based CA schemes according to their most prominent attributes together with the objectives and limitations of each of the approaches. In Section 5, we discuss open issues and challenges in the design of partially overlapping channel assignment schemes, followed by the chapter’s conclusion in Section 6.
2. Interference in Wireless Networks
In a typical WMN, flows on links belonging to different nodes compete with each other to access the wireless medium. This results in possible interference among the nodes therefore severely affecting network performance. Multiple types of interferences exist in WMNs depending on flow characteristics and on interface to channel configurations. We first explain what the different types of flow interferences are particularly in infrastructure WMNs. We will also present another interference classification in mesh networks based on the configuration of the channels to radios and also on the number of radios installed in nodes.
2.1. Flow based interference
2.1.1. Inter-flow Interference
This type of interference occurs when neighboring nodes carrying different flows compete for channel access when they transmit on the same channel as depicted in Figure 3(a). This effectively means that whenever a node is involved in a transmission; its neighboring nodes should not communicate at the same time.
2.1.2. Intra-flow Interference
Nodes on the path of a same flow compete with each other for channel access when they transmit on the same channel. This is referred to as intra-flow interference and is shown in Figure 3(b).
2.2. Interference based on interface to channel configuration
A wireless mesh network utilizing both orthogonal and non-orthogonal channels may suffer from interferences which can be characterized as follows.
2.2.1. Co-channel Interference (CCI)
Co-channel interference is the most common type of interference that exists in almost all wireless networks (depicted in Figure 4-a). It refers to the fact that radios belonging to two nodes, operating on the same channel would interfere with each other, if they are within the interference range of each other. This effectively means that parallel communications from two separate in-range nodes is not possible.
2.2.2. Adjacent Channel Interference (ACI)
We talk about adjacent channel interference when radios on two nearby nodes are configured to partially overlapping channels. For example, in Figure 4(b), a radio on node A is configured on channel-4 while another radio at neighboring node C is configured on channel-1; then the transmission from either node would experience some sort of partial interference. This type of interference also restricts parallel communication depending upon the channel separation and the physical distance between the two nodes.
2.2.3. Self-Interference (SI)
Self-interference is defined as a transmission from a node interfering with one of its own transmissions. This is related to situations when nodes are equipped with multiple radios in a mesh network. Parallel communication cannot be achieved using multiple radios installed on a node, unless they are configured on completely orthogonal channels as shown in Figure 4(c).
All of the above types of interferences have to be considered when designing channel assignment algorithms to exploit the full potential of the available wireless spectrum. Therefore, the first step in developing mechanisms which take advantage of the partial overlap is to build a model that captures the channel overlap in a quantitative fashion.
3. Benefits of using Partially Overlapped Channels
In this section, we will discuss the benefits of using POCs in WMNs. First, we will explain what the different scenarios are, where the use of partial overlap among channels will be useful. We follow that by a quick testbed experiment to demonstrate the effectiveness of using POCs in WMNs.
Mishra, et al., in  have performed detailed experiments to demonstrate the effectiveness of using partial overlap among channels in WMNs. The authors have measured the signal to noise ratio (SNR) of two communicating nodes configured on adjacent channels and mapped them onto a normalized [0,1] scale with 0 representing the minimum signal received. Their results are shown in Table I.
|Normalized SNR (I-factor)||0||0.22||0.60||0.72||0.77||1.0||0.96||0.77||0.66||0.39||0|
A typical bandwidth of an IEEE 802.11b channel which uses direct sequence spread spectrum (DSSS) is 44MHz. It is distributed equally on each side of the center frequency of that channel i.e. 22MHz on each side. A transmit spectrum mask (band pass filter) is applied to the signal at the transmitting station (with a typical example shown in Figure 5) which is basically used by the transmitter to limit the output power on nearby frequencies. As it can be seen in the figure, the mask is set to 0dB at the center frequency where signals are passed without any attenuation. However, at frequencies beyond 11MHz on either side of the center frequency, the signal's power is attenuated by as much as 30dB and at 22MHz as much as 50dB. The receiver also uses a band pass filter centered around the nominal transmission frequency of the channel. Three scenarios are discussed in  where the use of partial overlap among the channels can be useful in the context of wireless mesh networks:
Multi-channel communication: The first scenario is when a node can communicate with two of its neighboring nodes configured on orthogonal channels (OCs) by operating on a partial overlapping channel. Basically, for a little reduction in throughput, one can use partially overlapping channels and this can give flexibility in topology construction while reducing the extra overhead in channel switching to enable communication.
Throughput improvement: The second scenario is when nodes in a mesh network have only one radio and therefore, they can be configured to only one channel at a time. There is a possibility of network disconnection while assigning different channels to nodes in the network. Channels with partial overlap can be assigned to nodes in such a manner that improves the overall network throughput capacity. In this way, the assignment of partially overlapping channels has to be intelligent enough to utilize the maximum bandwidth available and therefore can result in significant throughput improvements.
Channel re-use: Shorter ranges for frequency reuse can be obtained if two interfering links are assigned partially overlapping channels rather than orthogonal channels. It is possible to significantly improve the overall channel re-use (i.e., by reducing the distance between nodes using POCs) by careful assignment of channels which will result in higher peak throughputs.
Later, in , the same authors have shown the advantage of using POCs in two different types of networks, i.e., WLANs and WMNs. In a WLAN setup, nearby access points can be assigned POCs such that the signal attenuation due to the overlap degrades to a tolerable level. In other words, the interference range of APs is reduced as perceived by neighboring APs operating on a partially overlapping channel. This provides efficient spatial re-use of channels and more APs can operate concurrently providing better service to clients. Similarly, in a single radio WMN environment, throughput can be improved when nodes can be configured to overlapping channels in order to avoid network disconnection and also to avoid any channel switching overhead.
3.1. Experimental evaluation
Next we will show results from experiments performed on a real testbed in order to evaluate the benefits of using partially overlapping channels in mesh networks. Our experimental testbed consists of four Linksys WRT54GLv1.1 wireless routers, each equipped with one radio. We installed the Freifunk firmware  on these routers for more freedom in our experiments. We created two point-to-point networks between two router pairs and thus formed two links each consisting of two routers as shown in Figure 6. Link-1 belongs to Pair-1 and Link-2 belongs to Pair-2. Each radio on Link-1 is fixed on channel 6; we varied the channels of Pair-2 from 1 to 6. The distance between nodes belonging to the same link is kept constant throughout the experiment. Pair-1 nodes have fixed locations while Pair-2 is moved to various distances from Pair-1 ranging from 5 to 30 meters (but Pair-2 nodes are kept equidistance to each other during the experiments). UDP and TCP traffic is generated on both links lasting for 10 seconds. The throughput on Link-2 is measured and the results are averaged over several runs. Three different IEEE 802.11b defined data rates are used for conducting the experiments, i.e. 2Mbps, 5.5Mbps and 11Mbps.
Figure 7(a), (b), and (c) show the UDP throughput on Link-2 with different channel separations for the three data rates. It can be seen that as the distance between the two interfering links is increased, the throughput increases due to the reduced amount of interference. In this setup we did not see any further improvements when nodes were more than 30 meters apart. However, the same maximum throughput can be achieved at significantly lower distances with increased channel separation between the two links. For example, at about 20 meters, Link-2 achieves the maximum benchmark throughput, when the channel separation between the two links is three. For data rates 5.5Mbps and 11Mbps, we notice similar results; however, maximum throughput can be achieved by eliminating interference at a much lower distances i.e. about 15 meters, when the channel separation is three as compared to 30 meters, when both the channels are separated by only one. Figures 8 (a), (b), and (c) show the comparable results when TCP traffic is used on all the three 802.11b data rates.
From these results, we can extrapolate the interference ranges of nodes with varying channel separations and at different data rates; this comprehension is shown in Figure 9. Each point in the graph represents the minimum distance that is required between the two links in order for them to experience no interference and achieve maximum throughput when they are on particular partially overlapping channels (with a given channel separation). We can observe that the interference ranges are decreasing with increasing channel separation and increasing data rates. From these measurements, we can empirically conclude that the interference range of nodes operating on POCs is significantly less than the range when they are on the same channel. (Similar experiments have been performed before in [3, 5-7, 16]; however, those experiments were done either on wireless card equipped computers or a computer attached to an access point. We believe, that our setup is easier to reproduce and is more representative for a WMN and thus provides a better understanding of POCs in mesh networks.)
Therefore, there is a tradeoff between efficient utilization of the wireless spectrum and a slight decrease in the throughput. An intelligent assignment of partially overlapping channels can decrease the impact of interference, eventually resulting in more efficient utilization of the spectrum.
4. Classification of POCA Schemes in Wireless Mesh Networks
Partially overlapping channel assignment (POCA) schemes can be classified based on different criteria and approaches. The criteria that we have used for classification is the interference model, which is defined as the technique for capturing interference of radios belonging to nodes operating on partially overlapping channels in a WMN. Figure 10 presents the classification on which the rest of the section is based. Note that our classification based on interference model may not create disjoint categories and thus, a particular scheme may have significant overlaps with another scheme belonging to a different category.
4.1. Interference factor model (I-Factor)
4.1.1. Revised Channel Assignment Schemes for Wireless Networks
One of the first models to capture partial interference in wireless networks was presented by A. Mishra, et al. in . They have extensively studied the practicality of using POCs in WLANs and WMNs. Through analytical formulation they have shown the benefits of POCs in terms of how they increase network capacity and improve channel-reuse. In order to model the interference generated by nodes operating on channels with partial overlaps, they have proposed a novel concept called interference factor (I-factor) capturing the extent of overlap between two communicating nodes. They define I-factor as:
where t and r are indices of the transmitting and receiving nodes, and δ denotes the difference of the frequencies of the transmitting and receiving nodes. In other words, parameter δ represents the amount of overlap between the two frequencies and is defined as a continuous variable. St(f) is the transmitter’s signal's power distribution and Br(f) denotes the frequency response of the receiver's band pass filter. In lay man terms: if we measure the area of intersection between a transmitter's signal spectrum and receiver's band-pass filter, we can calculate how much overlap there is between these signals; this is defined as the interference factor (I-factor). Since, IEEE 802.11 standards operate on a set of discrete channels, the continuous variable δ can be discretized as follows: δ = 5|i-j| (in MHz).
The authors of  have also revised two existing channel assignment algorithms in the context of WLANs and WMNs and have applied the I-factor model to these algorithms. First, an existing algorithm  was modified which is a centralized greedy-style approach for CA in WLANs using only orthogonal channels with the objective of increasing overall spectrum utilization. The algorithm employs an indicator variable to model the interference in WLANs and the authors have modified this indicator variable to capture not only the orthogonal channels (which was previously the case) but also channels with partial overlap (using their I-factor model). The actual channel assignment problem is formulated as a conflict set coloring problem where a conflict is present when clients belonging to a particular AP experience interference from neighboring clients (which are attached to their respective APs). The objective function is a min-max formulation to capture the total interference experienced by each client. The algorithm starts with a random permutation on how channels are assigned to APs; this is followed by the computation of the objective function. The best channel with minimum interference among the available channels is chosen and the process repeats for each AP. The modification lies in the interference calculation function to incorporate POCs into the algorithm. Interferences among channels with partial overlaps are calculated based on the I-factor interference model either empirically or analytically; this enables the possibility of assigning all available channels to the WLAN.
Still in , another CA algorithm which was designed for wireless mesh networks using only orthogonal channels  was modified to include POCs. It is a joint channel assignment, routing and link scheduling approach and a mathematical formulation in the form of a linear program (LP) is presented. The formulation also includes an indicator variable to model interference in the network. The authors have modified the link scheduling part of the joint mathematical formulation to change the conflict links’ constraints to include the I-factor model (partial interference). They have evaluated the performance of this modified LP to show improved throughput in WMNs. The revised algorithms demonstrate that careful use of POCs can lead to significant improvements in spectrum utilization and application performance. They have performed extensive simulations to show that the use of POCs can improve network throughput (the extent of which depends on the nodal density of the network).
4.1.2. Channel Assignment Exploiting Partially Overlapping Channels (CAEPO)
The authors in  have proposed a POC channel assignment scheme called CAEPO. The main contribution of their work is the design of a traffic-aware metric that captures the degree of overlap among the channels when measuring interference. It is a hybrid distributed channel assignment protocol, where each node collects information locally and hence performs the channel assignment locally. The proposed I-factor based metric captures the interference experienced by nodes operating on channels with partial interference. Each node measures the interference according to the degree of overlap between channels and scales it to the traffic load experienced by its neighboring node (this information is maintained by each node). Each node does this for all of its neighbors and combines the results to determine the total interference it is “suffering” due to its neighboring nodes. Thus, the interference metric at node i is calculated as:
where B(j) is the proportion of the busy time of a neighboring node j, and N(i) is the set of neighbors of node i; f[i][j] captures the extent of overlap a node operating on a particular channel has from its neighboring nodes configured on another channel. This is based on the extent of the channel separation between the channels used by the two nodes (taken from ).
More precisely, CAEPO works as follows: each node in the network is equipped with two interfaces; the first interface is configured to a fixed channel while the other interface can be dynamically switched between channels. The algorithm starts with each node assigning a fixed channel to its fixed interface and a default channel to its switchable interface using the interference estimation metric with the initial value of B(j)=1. Then, this channel assignment information, together with the interference measurements are relayed to all neighbors. After this initial channel assignment, each node periodically calculates the interference using the interference metric described above and if the fixed interface channel needs to be changed, then that information is relayed on the default channel of the switchable interface. Similarly, when a node has data to send, it switches its dynamic interface to the fixed channel of the receiver node's interface. Performance evaluations of CAEPO show improved network performance when all 11 channels of IEEE 802.11b are used.
4.1.3. Load-Aware Channel Assignment Exploiting Partially Overlapping Channels (Load-Aware CAEPO-G)
The authors of  present an extension to the previously discussed CAEPO  to make it traffic load-aware in addition to being interference-aware. A grouping algorithm is also proposed with the goal of achieving better aggregate network throughput. In the grouping algorithm, each node sends periodic hello messages; based on a node's weight (which is determined by how many hello messages it has received so far from its one-hop neighbors) the node may become a group leader. There can only be one group leader in the one-hop vicinity of any particular node. New nodes can join the group by sending a join message and similarly existing nodes can leave the group by sending a quit message to the group leader. Once the group leaders have been assigned (grouping is done), channels are assigned to links similarly to that in , with only one major difference: any update of the channel (i.e., channel switching) has to be initiated by the group leader. If a node “feels a need” to switch to a new, less contentious channel, it will send a "channel switch" request to its corresponding group leader who if agrees relays the information onwards to the other members in the group. Because of the addition of a new grouping algorithm and the load-aware feature, load-aware CAEPO-G achieves much better performance than the original CAEPO.
4.1.4. Minimum Interference for Channel Allocation (MICA)
In , the authors have introduced the concept of node orthogonality: two nodes, operating over adjacent and partially overlapping channels, are considered orthogonal if they are sufficiently physically apart. A novel interference model is proposed that captures the adjacent channel interference and also takes into account the physical distance of the two nodes configured on POCs. The proposed interference factor Ic(i,j) is defined as follows:
where Di(ci,cj) is the adjacent channel interference range between channels i and j, extracted from the physical model of the I-factor described in [3-6]. Di(ci,cj) captures both the channel separation and physical distance among the nodes to model the interference due to POCs. The proposed interference factor Ic(i,j) can be used to define node orthogonality by stating that two nodes are orthogonal if and only if their interference factor value is equal to 0.
Given a particular channel assignment, a weighted interference graph can be constructed with weights on the edges measured by the interference factor Ic(i,j); Figure 11 shows an example. Here, it is assumed that the data rate and the transmit power for all the APs are the same.
Using the weighted interference graph model, a minimum weighted interference optimization problem is formulated with the objective of minimizing the sum of weights in the interference graph. A centralized heuristic is proposed called minimum interference for channel allocation (MICA) to obtain a near-optimal solution which relaxes the formulated minimum interference problem in order to find fractional interference in polynomial time and eventually to assign POCs to APs (after rounding off the fractional solution to the nearest integer).
In addition to the above approaches, there have been other research efforts in designing MAC protocols that exploit POCs in wireless networks. One such scheme is presented in  in which some of the challenges that may be faced when using overlapping channels in the design of a MAC protocol are discussed. Analytical models are designed to capture partial interference at the MAC layer in order to improve channel utilization and to enhance network capacity. Based on the model, an efficient medium access scheme with collision avoidance mechanism is developed which increases network throughput (exploiting multiple channel transmissions).
The authors of  study the use of POCs for data aggregation in sensor networks. In a typical sensor network, the job of each sensor node is to collect the data, aggregate it and send it back to the sink for further processing. Arguably, reducing latency of data aggregation is therefore one of the fundamental issues in sensor networks. This is also called the minimum latency scheduling (MLS) problem in which a conflict free transmission schedule is designed with the objective of minimizing the overall data transmission latency. The concept of POCs is used in order to reduce the data aggregation latency; a joint tree construction, channel assignment and scheduling algorithm is proposed to solve the MLS problem. The basic idea is to compute a partially overlapping channel assignment algorithm for the sensor network, and then construct a data aggregation tree for the whole network followed by finally designing a link schedule so that the data aggregation latency is minimized.
Table II provides a side-by-side comparison for the above four POCA schemes based on their objectives, the procedures that are used in obtaining a partially overlapping channel assignment algorithm and their limitations.
4.2. Interference matrix model (I-Matrix)
The second type of interference model we consider for POCA schemes was originally presented in . The model is called I-Matrix, and is designed to measure the adjacent channel interference (ACI) among different POCs on adjacent nodes as well as self-interference (SI) among different radios on a single node. I-Matrix captures the interference that a channel belonging to a particular radio experiences due to all other possible channels (10 channels in the case of 802.11b). The proposed interference model (I-Matrix) is made up of three components, namely the interference factor, the interference vector, and the I-Matrix itself. The interference factor is derived from the I-factor of  and is the ratio of the interference range and the physical distance between two radios configured on adjacent channels (). In other words, the interference factor captures both the physical distance and the channel separation between nodes. This means that even if the respective channels of two nodes are overlapping, but their physical distance is greater than the interference range (demonstrated by IR(δ) and taken from [8, 24]), the value of fi,j will be zero. The interference factor is computed for all the channels with respect to a particular channel and put in a vector called the interference vector as shown in Table III. Similarly, each node combines all the interference vectors it has calculated for each channel and constructs the I-Matrix as outlined in Table IV.
|A. Mishra ||Maximization of the total throughput (maximizes simultaneous link activations)||Routing, channel assignment, and link flow scheduling; performed stepwise until optimal CA and routing solution is found||Complexity; ignoring switching overhead; SI not considered|
|MICA ||Minimization of the sum of the weighted interference in an interference graph||Approximate algorithm for channel allocation using integer linear programming (ILP) formulation.||Offline solution; only designed for single radio networks; SI not considered|
|CAEPO ||Minimization of the network interference||Heuristic distributed load-aware algorithm. Channel assignment based on traffic-aware interference estimation and packet loss ratio metrics||Simplistic interference model; SI not considered; scalability issues|
|Load-Aware CAEPO-G ||Minimization of the network interference||Extension of  with the addition of self-interference factor and a grouping algorithm to make CA scalable.||Simplistic interference model|
|CH||di||Interference Factor experienced at channels|
|CH||di||Interference Factor experienced at channels|
 also proposes a heuristic channel assignment algorithm exploiting POCs based on the I-Matrix model. The algorithm assigns channels to the maximum number of links with the objective of minimizing network interference. The algorithm starts with an input describing the number of links that need to have channel assignments. The links are then assigned to their respective nodes and those nodes are sorted in descending order of their degrees. For each node, its incident link is assigned a channel which has the minimum interference calculated from the I-Matrix; accordingly after the channel assignment, the interference vectors of the corresponding channel are updated. This in turn forces the node to update the I-Matrix with the new channel's interference measurements against all other channels.  shows that using POCs can improve network capacity by as much as 15% compared to when only non-overlapping channels are used.
4.2.1. Channel assignment based on I-Matrix model
In , the authors have extended the work of  by trying to remove some of the limitations in the proposed I-Matrix interference model and the channel assignment algorithm. More precisely, the CA algorithm in  sorts the links in descending order based on nodal degrees; however, this is not practical in multi hop WMNs as most of the traffic is targeted to gateway nodes. Therefore, the descending order should be based on the traffic load, implying that the busiest link should be assigned the channel first, i.e., gateway links should be first (thus being in accordance with typical WMN traffic characteristics). Another, shortcoming of  pointed out is that it suffers from the network partitioning problem, in the sense that some of the links may remain unassigned because the CA algorithm only assigns POCs and never assigns the same channel (as it tries to completely avoid the co-channel interference). To overcome this limitation, the I-Matrix model is modified to consider co-channel interference by adding a co-channel column to the matrix. This ensures network connectivity (because now the links can be assigned the same channels).
The algorithm of  consists of two phases. In the first phase, instead of the number of links as the input, links with traffic load information are provided as input and they are sorted in descending order of the traffic they carry. Then a suitable channel with the minimum interference is extracted from the I-Matrix. The second phase guarantees network connectivity in which the algorithm looks for those nodes that do not have a path to the gateway and if such nodes are found, their radios can be configured to the same channel on which one of their neighbor node’s radio is already configured on. This ensures full network connectivity at the cost of co-channel interference. They have shown through experiments that the existence of such co-channel interference does not strongly influence the network performance (as such formerly disconnected nodes are likely to be at the peripheral of the network).
Table V summarizes the I-Matrix POCA schemes. It states the objective of each algorithm, the procedures used in obtaining a partially overlapping channel assignment algorithm, and the limitations of each scheme.
|M. Hoque ||Maximization of network capacity||Greedy heuristic channel assignment algorithm based on I-Matrix interference model, links are visited in descending order of the node degrees||Simplistic interference model, network can be disconnected, CCI is not considered, topology is not preserved|
|P. Duarte ||Minimization of network interference||Extended  to incorporate traffic load into I-Matrix for channel assignment, ensures network connectivity, links are visited in descending order of the traffic load||Simplistic interference model|
4.3. Channel Overlapping Matrix Model (CO-Matrix)
In order to model orthogonal and non-orthogonal channels, a novel interference model called channel overlapping matrix is proposed in . Consider a MRMC-WMN consisting of N routers, each equipped with I radios and C available frequency channels. For any two routers a,b ∇ N, a channel assignment vector xab of size C x 1 can be defined which defines the channel on which the two routers are communicating (that particular element in the matrix becomes 1). Similarly, a vector of size I x1 defines an interface assignment vector yab, which tells which radio belonging to a particular router a is used to communicate with router b (by changing the value of that element in the vector to 1). To model the partial overlap among channels, a C x C channel overlapping matrix W was proposed whose mth row, rth column entry can be calculated as:
where Fm(w) denotes the power spectral density (PSD) function of the band-pass filter for channel m and consequently the same for channel n. Based on this channel overlap matrix, the authors have formulated a linear mixed-integer program consisting of few integer variables in order to solve a joint channel assignment, interface assignment and scheduling problem when the whole spectrum of the IEEE 802.11 frequencies is to be used.
4.3.1. Channel Assignment based on Channel Overlapping Matrix Model
Another channel assignment algorithm based on the channel overlapping matrix was proposed in . Here, a joint channel assignment and flow allocation problem in MRMC WMNs is considered.  formulates this joint problem into a mixed integer linear program with the objectives of maximizing aggregate end-to-end throughput while minimizing queuing delays in the network (given that the traffic characteristics are known). In order to model the partially overlapping channels, the I-factor of  is used, capturing the overlap between two different nodes configured on two different channels. Based on the I-factor a C x C symmetric channel overlapping matrix O is proposed:
where oij represents an entry in the ith row and jth column of the matrix O. To model the impact of interference, a physical model is employed .
Table VI provide a side-by-side comparison of the two algorithms surveyed above based on their objectives, the methodology used to assign POCs, and their limitations.
|A. Rad ||Minimization of the maximum link utilization||Joint CA, interface assignment and flow scheduling algorithm based on channel overlapping matrix to model POCs / linear mixed-integer program formulation||SI is not considered, extensive computational complexity|
|V. Bukkapatanam ||Maximization of the aggregate end-to-end flow allocations||Joint CA and flow allocation algorithm based on CO matrix / mixed integer linear program formulation||extensive computational complexity, offline solution; no bounds on completion|
4.4. Conflict Graph based Model (CGM)
4.4.1. Channel Assignment with Partially Overlapped Channels
A weighted conflict graph model is proposed in  to more accurately model interference among nodes operating on overlapping channels. In order to measure the partial interference, a metric called interference factor (IF) is defined:
where t1 and t2 are the throughputs of two links (link-1 and link-2) each belonging to a pair of nodes which are placed at various locations to measure interference when the other link is idle. Similarly, t'1 and t'2 are the corresponding link throughputs when both links are active. As it can be seen from the formula, a higher IF value indicates lower interference. Experimental studies of  measured link interference (IF) and found out that for a particular channel separation, the interference between two links degrades quickly (higher IF factor) even with a slight increase in distance. From this IF metric, the interference range of two links separated by a fixed number of channels can be extracted. Multiple interference ranges are calculated for all five possible channel separations under different IEEE 802.11b bitrates (i.e., 2Mbps, 5.5Mbps, and 11Mbps).
The concept of interference range is then applied to formulate the channel assignment problem into a weighted conflict graph model where the edges in the conflict graph are labeled by the minimum channel separation that two interfering links must have in order to have a conflict free communication. This weighted graph serves as an input to select the edges having minimum weights, eventually minimizing the overall network interference. A greedy partially overlapping channel assignment algorithm is proposed to solve the weighted conflict graph problem. The algorithm consists of two parts, namely select and assign. During select, the link with the minimum expected interference among all available links is selected. In the assign phase, a channel is assigned to this link with the minimum interference to all previously assigned channels. These steps are repeated until all links are covered, i.e., all links are assigned channels. In addition, the authors in  have also designed a novel genetic algorithm for channel assignment which produces slightly better results compared to the greedy algorithm for solving the assignment using the conflict graph. In order to map the partially overlapping channel assignment algorithm, a channel assigned to a single link is considered as a DNA sequence and the channel assignments of the all the links are mapped to an individual. In a typical genetic algorithm, a generation consists of a set of individuals; therefore, in this case, it will be a series of channel assignment solutions. An example of this mapping of the channel assignment problem to a genetic algorithm is shown in Figure 12 .
The procedure for encoding the channel assignment scheme into an individual in a genetic algorithm requires first to sort the links, convert them to fixed length binary strings (a DNA sequence), and then to concatenate the binary strings together to form a single individual. The fitness function is defined as the inverse of the total interference in the network. The algorithm starts with randomly generating N channel assignment schemes (individuals). The selection strategy selects two individuals (from the N sized population) by using the roulette wheel selection method and then choosing the better one of them according to the tournament selection strategy. These two strategies are commonly referred to as the stochastic selection strategy. After the selection stage, a reproduction step is performed in which one-point crossover and two-point crossover and mutation is applied to the selected two individuals. Both the greedy and genetic channel assignment algorithms are evaluated on various sets of topologies. The greedy algorithm is faster but the genetic algorithm provides better results and thus can generate better channel assignment schemes which eventually result in improved network capacity.
4.4.2. Partially Overlapped Channel Assignment (POCAM)
In , a new partially overlapped channel assignment for multi-radio multi-channel wireless mesh networks called POCAM is proposed, where the interference model stems from measurements of commercial radios using real testbeds. An extensive set of testbed experiments were performed to analyze the effect of partial interference and self-interference in WMNs. Through these tests it is shown that the self-interference issue is worse than it is usually assumed as it still needs to be considered even if the two radios on the same node are configured on non-overlapping channels. The proposed POCAM algorithm consists of two steps and incorporates the traffic load distribution. First, a transformation of the partially overlapped channel assignment problem into a weighted conflict graph (WCG) is performed followed by calculation on that weighted conflict graph. The WCG is a graph G = (V,E) where V represents the number of nodes in a WMN. For each edge in E, edge weights are assigned based on a table in  capturing interference ranges against each channel separation. The WCG is constructed with links represented as vertices in the conflict graph and there is a weighted edge between two vertices in the conflict graph if those two links interfere. The WCG formulation becomes a constraint satisfaction problem (CSP) which is an NP hard problem. CSPs are usually solved by applying backtracking search algorithms , thus  shows a design of three heuristics specially tailored for WMN characteristics.
4.4.3. Minimum Interference Channel Assignment
The authors in  propose a centralized channel assignment algorithm based on the tabu-search heuristic  which is used to find quasi-optimal solution for a graph coloring problem. The objective of the channel assignment algorithm is to minimize the overall network interference by assigning channels to links in a WMN. Network interference is captured as a graph coloring problem by assigning colors (channels) to the vertices of a conflict graph using K colors while maintaining interface constraints. The interface constraints limit the number of different channels assigned to interfaces belonging to a single node by the number of interfaces on that node. The proposed tabu-search based channel assignment algorithm consists of two phases. In the first phase, the algorithm starts with a random solution by assigning random colors to each vertex in the conflict graph, followed by a series of solutions which are created with the objective of minimizing overall network interference by assigning colors to vertices such that the conflicts is minimized. In each iteration, a tabu list of the colors (channels) that have already been assigned is maintained to avoid their assignment a second time and to achieve fast convergence. This phase terminates after a certain number of iterations (solutions). In the second phase, the interface constraints are satisfied by a merge operation in which, those nodes who have been assigned more distinct colors (channels) to links than how many radios they have, have their colors merged to bring them to be equal to their number of radios. To ensure network connectivity by this merge operation, the just changed color is propagated to all the other links that were assigned the old color to repeat the merge operation on them (those links must be part of the common node).
A distributed greedy heuristic channel assignment algorithm based on Max K-cut is also proposed by the authors . Given a conflict graph, the max K-cut problem deals with dividing vertices into K partitions to maximize the number of edges that lie in different partitions. Two formulations of their proposed channel assignment problem are provided, one is a semi-definite programming (SDP) formulation and the other is a linear programming formulation in order to obtain tighter lower bounds on optimal network interference. The linear programming formulation is modified to capture partial interference that exist when overlapping channels are being used and in order to make the formulation compatible to POCs. The SDP formulation however turns out to be too complex and therefore, it is not been evaluated.
Mishra et al., in  formulate the channel assignment problem as a weighted variant of the graph coloring problem incorporating realistic channel interference based on the I-factor model. The channel assignment problem is formulated as a weighted graph coloring problem with APs representing vertices in the graph and potential interference among them is represented by an edge between the vertices in the weighted graph. The weight on each edge depicts the significance of using different colors for the vertices that are connected by that edge. The weights are defined as the number of clients attached to an AP, scaled by the degree of interference between the chosen channels (I-factor). Therefore, the goal of the weighted graph coloring solution is to minimize the objective function. A higher weight translates to higher amounts of partial overlap between the channels; the algorithm attempts to assign different channels or channels with higher spatial difference to the edges in the graph. An edge weight of zero means that there is no interference among the clients of the corresponding APs. It is proved that the proposed weighted graph coloring problem is NP-hard, therefore, two distributed channel assignment techniques are proposed with the objective of minimizing the overall network interference. The first technique tries to minimize each individual AP’s interference and does not require any inter-AP communication. It consists of two steps; i.e. an initialization and an optimization step. The initialization step starts with assigning the same channel to all the APs. In the optimization step (which is incremental in nature), each AP performs the greedy optimization trying to minimize its local maximum interference by taking the maximum weight edge (which eventually minimizes the objective function). The algorithm stops when the network achieves an acceptable “coloring” configuration. The second channel assignment algorithm requires collaboration among APs and is intended to minimize interference by reducing the number of clients that are experiencing interference. Simulations and testbed experiments show that the proposed channel assignment algorithms achieve 45.5% reduction in interference when the network is sparse. The algorithms are scalable and provide better performance than existing channel assignment algorithms.
A heuristic-based channel assignment and link scheduling algorithm is proposed in  to enhance network capacity by exploiting partially overlapping channels in WMNs. Since, finding optimal channel assignment and link scheduling together for a given network is NP-hard, heuristic based policies are summoned to provide a sub-optimal solution. The problem is divided into two parts; first channel assignment is performed and then based on that an optimal link scheduling is explored. For the channel allocation, a genetic algorithm  is used. The authors have also studied some of the factors that influence the performance of POCs in channel assignment in a wireless mesh network (such as node density and node distribution).
All of the above three POCA schemes make use of graph-theory to model partial overlap among nodes in MRMC-WMNs except  which is designed for single radio WMNs. The approaches then apply a heuristic for channel assignment. Table VII provides a side-by-side comparison of the three POCA schemes based on their objectives, methodology, limitations.
|POCAM ||Minimization of network interference||Weighted conflict graph, constraint satisfaction problem, heuristic based backtracking search algorithm||Simplistic interference model, no SI is considered|
|Y. Ding ||Minimization of network interference||Weighted conflict graph, graph coloring, greedy CA algorithm, genetic algorithm based on partially overlapped channel assignment||SI is not considered, extensive computational complexity, edge weight assignment is difficult, does not consider traffic load|
|A. Subramanian ||Minimization of network interference||Conflict graph, Max K-cut, SDP and ILP formulation, tabu based CA and heuristic based greedy CA algorithm||Extensive computational complexity, SI is not considered, ignores switching overhead|
4.5. Summary of all POCA approaches
In this section, we provided a survey of existing POCA schemes in WMNs and summarized them based on their objectives, methodologies and limitations. Table VIII presents an overall summary of all the POCA approaches examined; the table shows the comparison of these schemes based on the following six questions:
Implementation: Is the proposed POCA centralized or distributed?
Multi-radio support: Is the POCA scheme designed for multi-radio WMNs?
Interference: What type of interference does the proposed POCA capture?
Routing dependency: Is the POCA dependent on a particular routing algorithm?
Channel switching frequency: How frequently are the channels switched?
Connectivity: Does the algorithm ensure network connectivity?
5. Open issues in POCA design
In spite of a reasonable amount of research in the late literature, there are still some challenges and open issues that need to be addressed in designing efficient channel assignment schemes exploiting POCs, particularly in WMNs. Below, we outline what we believe some of these challenges and open issues are.
5.1. Capturing self interference
As explained in Section 2.2, self-interference restricts parallel communication originating from a node having more than one radio unless these radios operate on completely orthogonal channels (OCs). Since, there are only three OCs for IEEE 802.11b/g in the 2.4GHz band, there is a need to further investigate how the self-interference issue can be better addressed. Few CA schemes have addressed self-interference in multi radio MWNs and we believe that there is room for improvement.
5.2. Modeling interference of POCs
More robust and efficient modeling schemes are required to intelligently capture the interference experienced by neighboring nodes operating on POCs in MRMC-WMNs. Although existing approaches do partially capture one or two types of interferences in a WMN, they are not complete solutions (they do not capture all the different types of interferences realistically). Furthermore issues arising from geographical positions of neighboring nodes and the availability of variable data rates still pose major challenges for POCA algorithms.
5.3. Lack of simulation tools
Most existing simulators [29-31] still do not support underlying physical models and easy POC evaluation scripting to capture partial interference between adjacent nodes in WMNs. However, we believe the reason for the lack of this feature is because the concept of POCs in CA schemes is relatively new and is still progressing and evolving to its maturity.
5.4. Multi-rate capability
To the best of our knowledge, there is no partially overlapping channel assignment algorithm that has been proposed to explore the multi-rate capability of IEEE 802.11 based hardware in MRMC-WMNs. Almost all the aforementioned works have assumed a fixed transmission rate (homogeneous links) which make the problem of channel assignment simple, whereas a POCA scheme with adaptive rates could potentially achieve significantly better performance.
|Characteristics||Implementation||Multi-radio Support||Interference||Routing Dependency||Channel Switching Frequency||Focus on Connectivity|
|A. Mishra ||Centralized||No||ACI||No||Dynamic||No|
|Load-Aware CAEPO-G ||Distributed||Yes||ACI||Yes||Hybrid||Yes|
|M. Hoque ||Centralized||Yes||ACI and SI||No||Dynamic||No|
|P. Duarte ||Centralized||Yes||ACI, SI and CCI||No||Dynamic||Yes|
|A. Rad ||Centralized||Yes||ACI and CCI||Joint||Fixed||Yes|
|V. Bukkapatanam ||Centralized||Yes||ACI||Joint||Fixed||Yes|
|POCAM ||Centralized||Yes||ACI and SI||No||Hybrid||Yes|
|Y. Ding ||Centralized||No||ACI||No||Dynamic||No|
|A. Subramanian ||Both||Yes||ACI||No||Dynamic||Yes|
In this chapter, we have discussed the problem of assigning channels with partial overlaps to radios in single- and multi-radio WMNs. We have characterized different types of interferences that may exist in a WMN depending on the flow characteristics and on the particular configuration of interfaces to channel assignments. We then presented IEEE 802.11 standard constraints on communications and evaluated the benefits of using partially overlapped channels (POCs) for the design of efficient channel assignment schemes with the help of experiments performed on a real testbed. Our, and previous experiments demonstrated that the use of POCs: i) improves network capacity by enabling more parallel communications and ii) provides more efficient utilization of the available spectrum. We have also provided a survey of some of the existing POC assignment schemes in WMNs and have classified them based on the interference models that they employ. Finally, we discussed some of the challenges and open issues in designing efficient channel assignment schemes utilizing both orthogonal and non-orthogonal channels in WMNs.