Critical link identification and prioritization using Bayesian theorem for dynamic channel assignment in wireless mesh networks

Abstract

Wireless Mesh Networks (WMN) is a key backhaul technology used in 802.11 networks to provide ubiquitous coverage to isolated areas that require high-speed connectivity. The multi-radio feature of WMN has enabled the mesh routers to derive the full benefits of multiple channels for providing parallel transmissions in a single collision domain. However, co-channel interfering links badly affect the channel capacity and force the mesh routers to switch the radio interface to other less interfering channel. In dynamic channel assignment, if the channel switches occur frequently, the traffic disruptions lead to excessive packet delays and drops. These problems are mostly observed in specific dense areas, where traffic saturation occurs. The existing schemes lack in properly identifying the bandwidth starved links. Therefore, the focus of this paper is to enhance the throughput and minimize the packet drops by critically identifying the bottleneck links and prioritize them for better channel assignments. The proposed metric exploits the statistical inference on dropped packets to determine the effect of interference on the achievable capacity of the links. The traffic load and the effective capacity are collectively used to identify the saturated links. The proposed metric has been evaluated through extensive simulations. The results demonstrate the validation of proposed metric with a considerable increase in performance.

1 Introduction

Wireless Mesh Networks (WMN) is a key backhaul technology used in 802.11 networks to provide ubiquitous coverage to isolated areas that require high speed connectivity. The multi-radio feature has enabled the mesh routers to derive the full benefit of multiple available channels for providing parallel transmissions and thus increasing the overall network carrying capacity. However, in addition to the benefits, the WMNs pose challenges in channel assignments due to the interference and network dynamics. In WMN, most of the traffic flow from mesh routes to mesh gateway or vice versa, and it is assumed that it makes a tree shaped traffic pattern and links closer to the gateway are likely to experience heavy traffic load. Based on this supposition, the best available channels are assigned to these incident links. However, this assumption is not realistic and this may not happen every time, especially when the topology is imbalanced and the traffic is not evenly distributed. The approaches that prioritize the links for channel assignment on the basis of hop distance towards gateway may not produce better results for every type of topology. Similarly, the approaches based on measurement of management frames may not accurately identify the problematic links. Furthermore, the links experiencing heavy traffic may lead to congestion, if the interference in the vicinity is high. Therefore, in order to increase performance of WMN, such links need to be identified that may become the performance bottleneck and prioritize them in assigning better channels.

For improved channel assignment, accurate information about interference and traffic characteristics is critical. The unsuccessful communication between a pair of mesh routers may have multiple reasons, at the data link layer; the major causes are queue drops and link errors. Interference from the WMN’s co-located links operating on the same channel or from the external sources can cause link drops and excessive delays. Link drops may have some other reasons, such as lossy channels [1], but that is out of scope of this research and here after term ‘link drops’ will only be used for the drops that are due to interference.

The proposed Critical Link Identification and Prioritization (CLIP) metric is designed in a way that it considers accurate packet losses in order to efficiently capture the effect of inter-flow, intra-flow interference and external interference and infer the true forwarding capacity of the links. The proposed metric exploits the Bayesian estimation approach on dropped packets to determine the effect of interference on the achievable capacity of the links. The traffic flow and the effective capacity are collectively used to identify the saturated links and accordingly to calculate a criticality value.

The major contribution that makes this approach different from previous research is the accurate detection of saturated links in the WMNs, which require more bandwidth in order to enhance the performance. The metric can handle network dynamics, where links criticality changes with the variation in traffic. In such situations, the traffic variations result in internal interference in the vicinity and decisively affect the link capacity. Another contribution of this approach is its dependency on data frames rather than management frames that provides a true picture of the aggregate interference.

2 Related work

The IEEE 802.11 standard has a limited number of channels. In multi-radio (MR) WMNs, the simultaneous use of these channels allows parallel transmissions in a single collision domain. However, the true increase in performance can be achieved subject to the efficient use of these limited channels. Therefore, assigning best available channels to the links that require more bandwidth is realistic. All the wireless links do not have the same magnitude in carrying network traffic. Therefore, a mechanism is needed to identify the links which require more bandwidth [2]. The link ordering is used to identify such links that require priority in assigning the channels. This issue has been discussed in multiple researches through different approaches, such as rank [3–5], cost [6] and weight [7, 8] based algorithms with several variants including the location of mesh routers, the number of wireless links, number of channels, the traffic load on links, number of radio interfaces on the mesh router and the level of interference. However, majority of the previous work is based on the assumption that the mesh routers which are near to the wired network, such as gateways, require more bandwidth/priority in assigning the channels as they are handling more traffic.

Riggio et al. [9] have proposed a channel assignment scheme as an Interference and Traffic aware Channel Assignment (ITACA). The channel assignment starts from the gateway router in case of homogeneous traffic on all the links and primarily selects the links that are near to the gateway and have minimum delay. The delay is calculated using Expected Transmission Time (ETT) metric. The ETT metric works on control channel and provides the delay values of beacon frames [10]. In ITACA, the control channel is different from the data channel and delay value of control channel is not a reasonable aspect for taking the decision about a data channel. In case of saturation in the network, the channel assignment is performed according to the aggregate traffic on the links. For identification of saturation, the variation of traffic ratio from its mean value is compared against a pre-defined threshold. However, network saturation occurs when the traffic load exceeds the available capacity of the wireless link as described by the authors in [11, 12]. The same fact has also been highlighted in [13] that the bandwidth allocated proportional to the carrying traffic can significantly reduce the saturation; therefore alone the heavy traffic may not accurately represent the network saturation in ITACA.

In another link ordering approach [14], authors have used Expected Transmission Count (ETX) for measuring the link quality. The ETX indicates the number of retransmissions required for a packet to be delivered successfully. The ETX is based on the probe frames and is used for routing path selection in single channel networks; however, these cannot be directly applied to MR-MC scenarios. Avallone et al. [2] have prioritized the links based on the existing flow given by its maximum channel capacity into number of links in the collision domain; where the number of links represents the utilization of collision domain. The utilization of collision domain based on only the number of links may not be an accurate measure of capacity, unless otherwise the flow on these links is also given a due weight [15]. In another approach [5] has defined the link ranks according to the numbers of mesh routers in the downstream, that use incident link to reach to gateway. A link that has more mesh routers down in the hierarchy is given highest priority. This, ultimately, gives higher priority to the links that are closer to the gateway, because those links are carrying traffic of the other mesh routers that are beneath them. This type of link ordering is well suited for static channel assignment approaches where traffic is not known in advance. Considering network dynamics, this approach may not perform well due to different intensity of interference. All the channels are initially assigned equal bandwidth, however, the intensity of interference reduces carrying capacity of the links and thus effective bandwidth is minimized [16].

The major challenge faced in the aforementioned approaches is identification and priority of the wireless links that require more bandwidth. Multiple researches in their experiment results have demonstrated that link ordering and channel selection criteria have performance effect on the average packet delay [17]. The correct identification of such bottleneck links and their priority in assigning the correct channels considerably improves the network capacity by permitting simultaneous transmissions. In order to overcome the limitations of current link ordering mechanisms, further research is needed to enhance the work in this domain.

3 Formulation of clip metric

To determine the critical links, it is desirable to have accurate traffic information and correct link drop measurements. The following subsections define the network model, method of calculating the traffic load, packet drops and accordingly the proposed CLIP metric. Table 1 represents the common notations and their meanings used in this paper.

Table 1 Notations and their meanings

3.1 Network model

A WMN is formed by a set of N mesh routers where N = {1, 2, 3…n} and each mesh router is equipped with three radio interfaces. The number of channels available to the network is C where C = {1, 2, 3…c} and C_Max is the maximum bandwidth of each channel. IEEE 802.11a and IEEE 802.11b offer 12 and 3 orthogonal channels of 54 and 11 Mbps of maximum bandwidth respectively. All mesh routers are assumed to be static in nature and operate at the same transmission power thus forming same transmission range. Hence, an incident link ‘l’ remains active as long as it is operating on a single channel. The link l ₁ is called interfered link, if it lies in a collision domain where another link l ₂ exists with the same channel assigned as of link l ₁. The collision domain is a collective physical region of transmission range of the transmitter and receiver.

3.1.1 Connectivity graph

Considering the above facts and assumptions, the mesh network is modeled using connectivity graph G = (V, E) where G structures the WMN. In this directed graph, V is a set of vertexes V = {1, 2, 3 … v} that represent the mesh routers and E is a set of edges E = {1, 2, 3 … e} that represent the links between the mesh routers. In connectivity graph, two vertexes have an edge between them if both are in transmission range of each other and are using the same channel.

3.1.2 Multi-radio conflict graph

The interference in multi-radio channel assignment problem is formulated by using Multi-radio Conflict Graph (MCG) [9]. In constructing the MCG, the connectivity graph is first converted into multi-radio connectivity graph, where each radio interface of each mesh router is represented as a separate mesh router. Later on, the links between each mesh router of multi-radio connectivity graph are represented with vertices in the MCG. The edge between two vertices in MCG exists, if these links in original multi-radio connectivity graph interfere with each other. Any two links interfere, if both are operating on the same channel and are in the interference range of each other. The detail of constructing the MCG is discussed in [9].

3.2 CLIP metric preliminaries

The traffic profiles [18, 19] are used in the proposed approach to record the traffic load. The traffic profiles provide more accurate and real time information of the traffic and also do not involve any network overhead. The profiles are locally maintained by all mesh routers and are periodically shared with the central entity -Channel Assignment Server (CAS). For sharing of traffic profiles, query relay messaging can easily be enabled in a testbed and practical implementations through protocol independent Application Programming Interfaces (such as OpenMapi) and Internet Control Message Protocol (ICMP) respectively [20, 21].

3.2.1 Traffic profiles

Each mesh router maintains three types of traffic profiles for its non-default radio interface. These profiles record necessary control information of each MAC Service Data Units (MSDUs) that is sent or received by the radio interface from all of the directly attached links. On each channel switch, the profiles are initialized to zero. Therefore, it records the packet information only for the duration, during which a particular channel is used on a radio interface. The control information that is recorded contains source, destination address and the number of packets transmitted by nodes in a WMN. Figure 1 shows an example scenario where A, B, C, D and E are the leaf nodes of a WMN and the profiles maintained by each node is shown in red, green and yellow for sent, received and forwarded packets respectively. Since, leaf nodes do not maintain forwarded packets the corresponding profile remains blank and is represented with white in the corresponding figure. The dashed line represents change of channel on the link; in this case it is the link between nodes C and F. Once, the channel is changed on a link, the nodes reset relevant traffic profile which is periodically calculated and observed for another channel switch, if necessary.

Fig. 1

A sample WMN with Traffic profiles being maintained at each node. Red and Green represent sent and received packets respectively whereas the yellow ones are the packets that are relayed forward. Leaf nodes do not contain yellow markers

3.2.2 Link error matrix

The CAS, using the traffic profile, periodically updates Link Error Matrix (LEM) for recording link drops. The packets sent by the transmitter but not received at the receiver are termed as drops [22]. Therefore, the sent and received records of traffic profiles are correlated in order to obtain the number of packets that are dropped during communication. Equation 1 represents the packet drops over a link l.

$$\begin{aligned} Droped\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) = Sent\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) \hfill \\ \quad {-}Received\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) \hfill \\ \end{aligned}$$

(1)

In the above equation, Sent is the total sent packets of the transit and sent traffic profiles of the sender mesh router. Whereas, Received is the total received packets of the transit and received traffic profiles of the receiver mesh router of the incident link l. The packets that are received but dropped due to buffer overflow are counted separately using buffer manager [23]. These packets are independently given weight because these packets have reached to the receiver and have consumed the bandwidth.

3.3 Critical link identification and priority (CLIP) metric

CLIP metric consists of two steps: (1) link capacity estimator and (2) traffic load estimator. At network startup, there is no traffic flow on the links; however, with a period of time as the traffic flows it dynamically affects other links in the vicinity. Therefore, the traffic is collected and evaluated at each periodic interval. The occurrence of an event in a system is a result of previous behavior of the system; therefore, Bayesian probability is used that considers the previous behavior and current event. The link capacity estimator exploits the Bayesian inference on the packet losses to estimate an aggregate interference on the link. The Bayesian estimation is used in various researches for channel quality prediction [24] and interference mitigation [25] in multi-hop networks. This interference is then correlated with the maximum channel bandwidth in order to get the achievable/effective link capacity. The estimated traffic load is compared with estimated link capacity and the links with traffic load greater than the link capacity are identified as critical links.

3.3.1 Link capacity estimation

The maximum bandwidth of a channel depends on IEEE 802.11 standard and the modulation scheme that is used. The a and b flavors of 802.11 offer up to 54 and 11 Mbps of bandwidth respectively, but the actual available bandwidth of a virtual link is much lower depending upon the interference in collision domain. Interference from the WMN’s co-located links operating on the same channel or adjacent channel may result in excessive link drops and link delays. The link drop is inversely proportional to link capacity, so hypothesis of this research is that packets not received by any mesh router are due to link error. To calculate the level of belief for the above hypothesis, Bayesian estimator approach is applied for estimating the interference on a channel by using the link dropped packets. The Bayesian theorem states the probability of an occurrence based on evidence. The probability is updated every time by a new piece of evidence. The new probability is called posterior probability and it is derived from evidence, prior probability and a normalizing factor [26]. Equation 2 mathematically represents the Bayesian theorem.

$$P({\text{A }}| B) = \frac{{P(B| {\text{A}}) P\left( {\text{A}} \right)}}{P\left( B \right)}$$

(2)

$P({\text{A }}| B)$ is the conditional probability where A is the event and B is the evidence, thus this defines the probability of A provided B is assumed true. $P(B| {\text{A}})$ represents the probability of B given that A is true. $P\left( {\text{A}} \right)$ and P(B) are the probabilities of A and B independently. $P\left( {\text{A}} \right)$ represents the prior probability and P(B) is a normalizing constant that represents the probability of B in all circumstances.

The Bayesian theorem requires evidence at network initialization as there is no evidence available, therefore, the proposed approach activates and progresses after an interval in order to get traffic profiles populated. From these profiles, the packet drops are calculated as discussed in Sect. 3.1. The packets drops are further bifurcated into packets that are dropped due to interfered link and ones dropped due to queue overflow at the receiver. These drops act as an evidence for applying them into the Bayesian theorem. Equation 3 represents the mapping of proposed approach to the Bayesian theorem.

$$\begin{aligned} & P\left( {\left. {Ch_{intf} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right|D\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) \\ & = \frac{{P\left( {\left. {D\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right|Ch_{intf} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) P\left( {Ch_{intf} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right)}}{{P\left( {D\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right)}} \\ \end{aligned}$$

(3)

The algorithm calculates the posterior probability of channel interference (Ch _intf ); packet drops due to link errors are used as evidence. Similarly, at network startup, there is no prior probability available; therefore, uniform, prior probability of ½ is used for both the link error and queue overflow. However, after first iteration the calculated posterior probability is input as a prior probability for the next iteration. It is worth to mention here that both packet drops and interference are usually calculated as ratio, but to counterbalance its usage in Bayesian, both are mapped to probability. For normalizing constant in Eq. 3, queue drops are also been given due weight as represented in Eq. 4.

$$\begin{aligned} & P\left( {D\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) \\ & = P\left( {\left. {D\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right|Ch_{intf} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) P\left( {Ch_{intf} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) \\ & \quad + P\left( {\left. {D\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) } \right|Q_{full} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) P\left( {Q_{full} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right) \\ \end{aligned}$$

(4)

The interference reduces channel capacity [27], therefore, the probability of interfered channel is mapped to the maximum capacity. The estimated Link Interference (LI) is calculated by multiplying the maximum capacity (Ch _Max ) with the posterior probability as represented in Eq. 5.

$$LI\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) = Ch_{Max} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) XP\left( {Ch_{intf} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)} \right)$$

(5)

$$ELC\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) = Ch_{Max} \left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) - LI\left( {{\text{l}}\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)$$

(6)

The Estimated Link Capacity (ELC) of an interfered channel is obtained by subtracting the estimated Link Interference (LI) from the maximum capacity (Ch _Max ) as represented in Eq. 6.

3.3.2 Traffic load calculation

In practical networks, the traffic is not always uniformly distributed and inappropriate assignment of channels cause saturation in specific areas. The saturated areas are the major capacity bottlenecks and become the reason for network throughput degradation. To identify such area/links accurate traffic load information is critical. The load of each downstream link that is passing through the mesh router is used as traffic load [28]. Each mesh router calculates Estimated Traffic Load (ETL) on links of all the directly attached neighboring mesh routers. To estimate the traffic load on a link, the CAS, using traffic profiles, measure the traffic volume passing though an incident link. This includes the traffic which is received on all attached links and for which the current mesh router is used as a transit mesh router. The estimated load is defined as aggregate of traffic of mesh router’s own load and transit load as represented in Eq. 7.

$$ETL\left( {{\text{l}}_{{{\text{x}} \to {\text{y}}}} } \right) = TL_{\text{x}} + \mathop \sum \limits_{i = 0}^{n} TL\left( {l_{{{\text{i}} \to {\text{x}}}} } \right)$$

(7)

$$ETL\left( {l_{{{\text{x}} \leftrightarrow {\text{y}}}} } \right) = ETL\left( {l_{{{\text{x}} \to {\text{y}}}} } \right) + ETL\left( {l_{{{\text{y}} \to {\text{x}}}} } \right)$$

(8)

The $TL_{\text{x}}$ is the traffic of router x and $TL\left( {l_{{{\text{i}} \to {\text{x}}}} } \right)$ is the load of neighbors, where i correspond to the directly connected neighbor mesh routers of x that have a gateway hop count equal or greater than x whereas y is a mesh router that has equal or less gateway hop count than x. The aggregate load of the bidirectional link is the load in both of the directions as represented in Eq. 8.

3.3.3 Criticality ratio computation

The links, having more traffic but mostly interfered, are the capacity bottleneck for the network. Such links are identified by comparing the estimated traffic load with estimated channel capacity. The links with greater traffic load as compared to the available channel capacity are candidates that need to switch the channel. To prioritize the handling of such links, the criticality ratio (CR) of a link is calculated in Eq. 9.

$$CR\left( {l\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right) = \frac{{ETL\left( {l_{{{\text{x}} \leftrightarrow {\text{y}}}} } \right)}}{{ELC\left( {l\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)}}$$

(9)

The $ETL\left( {l_{{{\text{x}} \leftrightarrow {\text{y}}}} } \right)$ is the estimated traffic load on bidirectional link $l_{{{\text{x}} \leftrightarrow {\text{y}}}}$ calculated using Eq. 8 and $ELC\left( {l\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array} } \right)$ is the estimated link capacity of $l\begin{array}{*{20}c} {\text{Ch}} \\ {{\text{x}} \leftrightarrow {\text{y}}} \\ \end{array}$ while it was assigned channel Ch, calculated using Eq. 6.

3.3.4 Prioritization algorithm

The algorithm takes the MCG and Traffic Profiles as input as represented in Algorithm 1. The traffic load and LEM are populated by correlating the traffic profiles of both end mesh routers of an incident link (vertex). This helps in finding the Traffic Load and Drops as represented at line 3–5. To find the Link Interference (LI), the probability, that a channel is interfered, is calculated by using the packet drops.

The interfered channel probability is then multiplied by the maximum capacity (Ch _Max ) at line number 6. The difference of LI and Ch_BW is used as effective capacity (LinkCapacity) that is available to an incident link as shown at line 7.

The TrafficLoad is compared with LinkCapacity to identify the bottleneck links and the ratio of both TrafficLoad and LinkCapacity represents the priority of a link in assigning a new channel as represented at line 8–9. Line 10 represents the priority queue (Q), which is used to save the bottleneck links in their descending order of ratios.

4 Design of proposed metric

The link ordering metric is a significant component of any channel assignment approach. It should fully capture the characteristics of WMN in order to provide a better solution. Specifically, in dynamic environments where links criticality changes when assigned channel’s capacity cannot handle variation in traffic load. These traffic variations also affect internal interference in the vicinity. Figure 2 represents the flowchart for working of CLIP metric. To find criticality ratio of a link, the CAS performs two steps. In the first step, the traffic load of links is calculated. For this information, the sent matrix of traffic profile is used; which represents the traffic that current router has relayed further to either gateway or other router in the previous interval. The gateway combines mutually traffic loads of both the end mesh routers of an incident link in order to get an aggregate load of a link. The second step is to find the effective capacity of a link; this is further classified in two steps. In the first step, packets drops are calculated, whereas, in the second step effective capacity is estimated based on these packet drops. For packet drops, the sent and received matrices from traffic profiles of sending and receiving mesh routers are correlated.

Fig. 2

Flowchart of CLIP metric

The packet drops of both the end mesh routers of an incident link are summed up for aggregate packet drops of a link. Packet drops are further bifurcated into packets that are dropped either due to interfered link or as a result of queue overflow at the receiver. For estimation of interference on the channel, Bayesian estimator is applied to the drop packets that are due to interfered link. The estimated interference is then mapped to the maximum capacity of the channel in order to find the effective capacity. Subsequently, the CAS compares traffic load with the effective capacity, in case of greater load the link is declared as bottleneck link.

5 Channel assignment

To assess the effectiveness of CLIP, it is applied in a centralized channel assignment scheme [9] that assigns the best available channel to the high priority links identified by the CLIP. The CLIP suggests priority of the links, thus selecting the links first that have more expected traffic but are assigned a low capacity channel. Figure 3 represents the system diagram of complete working of CLIP in a centralized channel assignment algorithm. To get awareness of the best available channels in the link vicinity, each mesh router additionally provides channel rankings of all the supported channels to the CAS. The selection of a new channel is based on the interference level on all the supported channels in the vicinity of a mesh router. To estimate the interference on these channels, the number of interfering radios on that particular channel and their per second channel utilization are used as the metrics [9]. Every mesh router estimates the interference by turning on the monitor mode of each of its radio interface on every supported channels for a defined period of time. This timing is adjusted by taking into consideration the periodic times of management frames of the mesh routers. During this time, radio interface captures management frames and data frames that belong to both the co-located links of the mesh network or external to the mesh network but are using the same channel as the mesh network’s supported channel.

Fig. 3

System diagram for CLIP

From the captured frames, internal and external interfering radios are identified by comparing the MAC addresses with the stored entries of ARP cache of the mesh router. These frames are then dispatched to the CAS. The channel’s per second channel utilization is calculated from the packet sizes and data rates of the captured frames. From this information, the two rankings of each supported channel are figured out. One ranking represents the interfering radios and the second represents per second channel utilization.

5.1 Channel assignment algorithm

The channel assignment algorithm works dynamically and assigns single channel to all the non-default radios of mesh routers at the time of initialization. The algorithm takes the MCG, Traffic Profiles and Channel Rankings as input as represented in Algorithm 2. The input is the Queue (Q) containing Links with priority and with false visited flag as identified in Algorithm 1.

At the time of filling the Q, the visited flag of all the vertices is set to false. From line 2–5, for each vertex in Q, according to their priority, a highest rank channel (new color in MCG) is selected that does not have conflicts with its neighboring links. In line 6–7, newly selected channel is assigned to the vertex and its visited flag is set to true. The channel switching of a vertex subsequently may lead to ripple effects and force several channel switches. To cater such ripple effects and to ensure that only one channel is assigned to one radio, the protocol after coloring a vertex immediately looks for other vertices that contain either radio of the current vertex and also mark it as visited. These other verities may belong to the critical links that are prioritized for the next channel switch, thus, reducing the number of channel switches required as represented in lines 8–18

.

6 Simulation and analysis of results

The implementation of CLIP is done in simulation environment using OMNeT++. Each mesh router is equipped with three radio interfaces for backbone connectivity [9, 29]. Among these interfaces, two interfaces are reserved as data interfaces (termed as non-default radios) and remaining one is for both control and data purposes (termed as default radio). The default radio is permanently assigned a fix CC, whereas the proposed approaches are for assigning channels to the non-default radios. The link redirection procedure is also implemented that is used during the channel switch process. In redirection, before switching the channel, the mesh router broadcasts ‘Link Down’ message to all the neighboring mesh routers in order to inform them about time duration during which the incident interface will not be available for reception of data [9].

Different simulation experiments are performed by varying mesh router densities over a field size of 1000 m × 1000 m and transmission range of the mesh routers is kept 250 m [9, 29]. The MAC and physical layers in the experiments, use the specifications of IEEE 802.11a protocol [9, 29, 32] with a manually configured transmission rate of 12 Mbps and total number of channels used are twelve [9]. From the traffic load perspective, the Constant Bit Rate (CBR) transmission is used with 100 packets per second from the source mesh router with a fixed packet size of 512 Bytes [9, 30, 31]. In a simulation run, the receiver of each flow is the fixed (the gateway). The duration of the simulation is set to 30 min [9]. The simulation results are averaged for each scenario over ten runs. The varying amount of interference is considered from co-located networks by changing the Bit Error Rate (BER) and number of routers. The routing protocol used in simulations is AODV [29, 33].

The interference estimation is obtained by simulating the RFMON mode, where one of the non-default radio interfaces temporarily suspends its normal communication and listens to the media for capturing data and management frames. During the listening period, link redirection procedure is used as discussed above. The duration of management frames is set to 100 ms and for interference estimation; listening period is set to 3 s after every 10 min [9]. For dynamic channel assignment of non-default radios, the need for channel switch of the links is accessed every 10 min, while channel switch delay is set to 0.03 s [9]. The remaining simulation parameters are listed in Table 2.

Table 2 Simulation parameters

For validation of the proposed approaches, the simulation results are benchmarked against Interference and Traffic aware Channel Assignment (ITACA) [9] and External Interference aware Channel assignment (EICA) by [14]. The ITACA and EICA are the channel assignment schemes that in addition to internal interfering links also consider the existence of co-located networks. The ITACA uses hop-distance and delay for selection and priority of critical links in normal traffic scenarios, while in case of saturation, it also considers the traffic load. Similarly, the EICA uses Expected Transmission Count (ETX) for priority of critical links. To certain the efficiency and performance gain of proposed approaches from the previous work, the homogeneous deployments of simulation scenarios are made. The simulation results can be affected by different factors. To reduce the effects of errors, and random results, the consistency and reproducibility are determined through repetitive analyses of traces obtained through ten runs of each scenario, having confidence interval of more than 90%.

6.1 Experimental analysis

The performance of the proposed approach is evaluated by conducting four sets of simulation experiments. In the first set of experiments, the throughput achieved by the three approaches is compared at different number of hops. The second set of experiments examines the impact of different flows on the throughput in a multi-hop environment. In the third set of experiments, effect of end-to-end delay is analyzed in a multi-hop environment with varying the number of concurrent flows. In the last part, the packet delivery ratio is investigated in a multi-hop environment by varying the number of mesh routers.

6.2 Performance evaluation

In order to evaluate the proposed approach, three performance metrics are considered as used in existing research works [9, 30, 31, 33]. The sub-sections discuss the three performance metrics of throughput, end-to-end delay and packet delivery ratio.

6.2.1 Throughput

The first experiment has been conducted to study the effect of throughput of the network in multi-hop flows. This multi-hop comparison helps to verify the effect of interference between the wireless links effectively. In this experiment, 21 mesh routers are considered; one is dedicated as mesh gateway and remaining 20 act as normal mesh routers. In mesh networks, all the traffic is routed towards gateway in order to access the wired backbone; therefore, this topology uses gateway as sink and normal mesh routers as source or intermediate mesh routers. Fourteen flows are initiated between the routers and gateway. The potential interference between the wireless links increase when the number of hop increases.

Figure 4 shows the comparison graph of average throughput of the network topology for all the three algorithms. In this graph, average throughput in case of CLIP is affected by increased number of hops. Due to this increase, the possibility of interference between multiple hops from source to sink becomes high; as channel switching cost and queue drops are to be kept in mind but still better throughput is achievable. The average throughput achieved by CLIP, ITACA and EICA is 4.25, 3.74 and 3.35 Mbps respectively. This means the average throughput achieved by CLIP is 13.63 and 26.86% higher than ITACA and EICA respectively. This is because of the fact that the bottleneck links are accurately identified and assigned channels on priority basis. This shows the efficiency of CLIP in the multi-hop environment.

Fig. 4

Throughput effect of CLIP as the number of hops increases

In real scenarios, multiple sources can be active at the same time. In the second experiment, effect of multiple flows on network performance is analyzed. The main objective of this experiment is to verify the optimal distribution of channels between the wireless links under different traffic loads. The same 21 mesh routers topology is considered, however, to get the effect of multiple flows, different number of normal mesh routers were activated at different times. During this period, the remaining mesh routers act just as transit mesh routers and relay the data of other active mesh routers. However, the active mesh routers play the dual mesh router; as a source and relaying mesh router. The number of active mesh routers was varied from 5 to 14 at different times.

In order to consider the real life scenarios of random number of flows, the experiment started with little number of flows and gradually increased. Figure 5 represents the comparison of throughput and flow, the graph shows that from flows 5–12, the throughput increased in a linear fashion as the delivery of flows is done through a sparse network of 20 mesh routers where the interference between the flows is very less.

Fig. 5

Throughput effect of CLIPs as the number of flows increases

This gives the flows more bandwidth to carry on simultaneous transmissions. Therefore, more packets reached to the gateway in lesser time. Furthermore, when more flows are induced as flow 13 and onward, the throughput started decreasing due to the increase in interference and also due to the reason that now lesser channels are available. However, the throughput of CLIP is still higher than the ITACA and EICA; because CLIP considers both traffic and the capacity of the link while assigning better channels. The average throughput achieved by CLIP, ITACA, and EICA is 3.16, 2.72 and 2.32 Mbps respectively. This means the average throughput achieved by CLIP is 16.17 and 36.20% higher than ITACA and EICA respectively.

6.2.2 End-to-end delay

In this experiment, average network delay is analyzed for multiple numbers of flows. The main objective of this metric is to examine the effect of interference and saturation under different traffic loads. The same 21 mesh routers topology is considered, and the number of active flows is varied from 5 to 14 at different timings. Figure 6 represents the graph, during the flows 5–7, ITACA and EICA encounter almost similar delay and from flow 7 onward the delay between both started increasing, Whereas, the CLIP behave slightly different from the both. This is due to the sparse topology and less number of concurrent transmission; therefore the packets faced no interference and delay for propagation during transit. As the network load tends to increase from flow 8 onward, the delay started increasing due to increase in interference. However, from flow 12 onward, the ITACA and EICA didn’t sustained themselves whereas, the CLIP comparatively reduced the effect of interference by correctly identifying the bottleneck links and prioritizing them for new channel assignment. The average end-to-end delay faced by CLIP, ITACA, EICA is 0.33, 0.40 and 0.43 s respectively. This means the CLIP more effectively catered the effect of interference by a factor of 17.5 and 23.25% than ITACA and EICA respectively.

Fig. 6

End-to-end delay Comparison as the number of flows increase

6.2.3 Packet delivery ratio

The fourth experiment is based on the packet delivery ratio (PDR) metric that exhibits its impact in terms of different mesh router densities. The PDR is affected by both the interference and the number of hops. Figure 7 represents a plot of PDR with varying the number of mesh routers. In this experiment, the active mesh routers are exactly half of the total mesh routers. As discussed above, the gateway router acts as a sink for all the data packets, therefore the PDR is obtained from the gateway profile. As shown in the graphs, when the scale of the network is small, almost all the three approaches behave similar and yield PDR more than 95%. However, as the number of mesh routers increased and the flow is also accordingly increased, the packets started dropping. The main reason for this drop is the increase in network saturation, collisions and routing overhead. In this scenario, the CLIP identifies the saturated links and the channel selection algorithm accordingly switched the links to better channels. The CLIP metric, reduced the overhead leading to saturation and collisions. The average PDR achieved by CLIP, ITACA and EICA is 83.75, 75.10 and 70.13% respectively. This means the performance of packet delivery achieved by CLIP is 12.84 and 19.42% higher than ITACA and EICA respectively.

Fig. 7

PDR comparison as the number of mesh routers increase

7 Conclusion

This research work proposes a link ordering metric (CLIP), which identifies and prioritizes the bottleneck links for assigning channels in a dynamic channel assignment scheme. The correct identification and correct channel assignment can significantly reduce the interference and enhance performance. The CLIP is formulated based on the concept of traffic flow and effective capacity. Contrary to the previous works, the CLIP makes the use of data packets rather than management packets to cater the effect of interference on the channel capacity. A statistical technique is exploited on the reported dropped packets to find the effective capacity. The proposed metric is applied in a centralized channel assignment scheme and tested over various scenarios. The simulation results reveal throughput improvement of around 26% on average as compared to existing approaches, specifically in dense networks with multi-hop deployments. Additionally, the end-to-end delay is observed lesser to be 20% on average whereas PDR is found approximately 16% better than existing techniques.