Distributed joint flow-radio and channel assignment using partially overlapping channels in multi-radio wireless mesh networks

Abstract

Equipping mesh nodes with multiple radios that support multiple wireless channels is considered a promising solution to overcome the capacity limitation of single-radio wireless mesh networks. However, careful and intelligent radio resource management is needed to take full advantage of the extra radios on the mesh nodes. Flow-radio assignment and channel assignment procedures should obey the physical constraints imposed by the radios as well as the topological constraints imposed by routing. Varying numbers of wireless channels are available for the channel assignment procedure for different wireless communication standards. To further complicate the problem, the wireless communication standard implemented by the radios of the wireless mesh network may define overlapping as well as orthogonal channels, as in the case of the IEEE 802.11b/g family of standards. This paper presents Distributed Flow-Radio Channel Assignment, a distributed joint flow-radio and channel assignment scheme and the accompanying distributed protocol in the context of multi-channel multi-radio wireless mesh networks. The scheme’s performance is evaluated on small networks for which the optimal flow-radio and channel configuration can be computed, as well as on large random topologies.

1 Introduction

Wireless mesh networks (WMNs) have attracted the attentions of the research community and the industry due to the increased coverage, self-configuration and self-healing possibilities they offer at reduced deployment, hardware and software costs compared to conventional star topology-based access networks. Today, many WMN deployments and testbeds exist at various scales and with various hardware and software configurations. Through theoretical and practical methods, researchers have quickly realized that WMNs with single-radio nodes have severely limited capacities due to the interference intensified by the multi-hop nature of these networks [5, 9, 11]. Multi-hop flows cause intra- and inter-flow interference in a WMN, and there is also interference from foreign wireless networks operating in close proximity of a WMN.

A widely accepted approach to mitigate intra- and inter-flow interference is to equip the mesh nodes with multiple radios that support multiple frequencies (channels) so the radios can be tuned to different channels. However, for two radios to communicate reliably with each other, they must be tuned to the same channel.

As discussed in Sect. 2, most studies in the literature restrict themselves to orthogonal channels. However, as previous research [6, 13–15] has shown, using partially overlapping as well as orthogonal channels for channel assignment better utilizes the spectrum and can increase the overall capacity and aggregate throughput in the WMN.

Another important factor that affects the performance of channel assignment is the flow-radio assignment. Flow-radio assignment is the scheduling of available radio resources on each of the multi-radio mesh nodes to application-level flows. It determines the radio of a multi-radio node on which the incoming packets of a specific flow will be received, and the radio on which the outgoing packets of the same flow will be transmitted (if the node under consideration is not the sink for the flow). Channel assignment, which is the assignment of available wireless channels to the radios of a multi-radio node, is performed after the flow-radio assignment. And for flow-radio assignment to be performed by a node, the node has to know (either a priori or by observation), the application-level flows passing through it. As explained in Sect. 3, we assume end-to-end paths in the mesh network are known a priori.

In this study, we aim to minimize the intra-flow and inter-flow interference in the wireless mesh network. Intra-flow interference is the interference between the consecutive hops of a single (end-to-end) flow in a multi-hop wireless network. Inter-flow interference is the interference between receptions and transmissions belonging to different flows. By decoupling the flow-radio assignment from channel assignment, we balance the traffic load on the radios. And subsequently during channel assignment, we can distribute the amount of total traffic on different channels evenly and keep heavily loaded channels as spectrally as well as spatially far from each other as possible. In order to reach these goals, while performing the flow-radio assignment and subsequently during channel assignment, we take the flow magnitudes into account. This makes DFRCA traffic load-aware.

As a consequence of the constraint that two radios must be tuned to the same channel for them to communicate with each other, flow-radio assignment, which determines the radio a flow to a neighboring node will use, has a direct impact on the performance achievable by the channel assignment. In the worst-case scenario, the channel assignment procedure may be obliged by the flow-radio assignment to use only one channel, making it ineffective. This scenario occurs when all the WMN’s active (traffic-carrying, utilized) radios are connected in a single subgraph (as explained later in Sect. 4.2).

Despite the prominent impact of the flow-radio assignment on the performance of the channel assignment, few studies [6, 19] in the literature have attempted to jointly address these two problems; to the best of our knowledge, our distributed joint flow-radio and channel assignment (DFRCA) scheme discussed here is the first to do so in a distributed fashion. The main contributions of our study are as follows:

• To the best of authors’ knowledge, the joint handling of the flow-radio assignment and channel assignment problems within the framework of a distributed protocol is the first in the literature.

• Unlike most existing studies, we consider overlapping as well as orthogonal channels for channel assignment.

• We observe and take into account the WMN’s traffic patterns, making the proposed scheme traffic-aware.

• The distributed scheme we propose is highly configurable and adaptable to different WMN topologies, to different wireless medium characteristics and to different wireless communication standards.

• We propose novel realistic metrics for assessing the interference and residual capacities of the receivers.

The remainder of the paper is organized as follows: Sect. 2 summarizes the existing literature addressing the channel assignment problem. Section 3 gives a formal definition of the channel assignment problem in the context of multi-radio WMNs. Section 4 discusses our proposed solution for the joint flow-radio and channel assignment problem. Section 5 introduces the metrics used for performance evaluation and gives the simulation results obtained for the proposed distributed scheme as well as for random and single-channel configurations. Section 6 concludes the paper.

2 Related work

The channel assignment problem in the context of multi-radio multi-channel WMNs has been extensively studied in the literature; however, most of the existing works consider only orthogonal wireless channels due to the complexity of the channel assignment problem. A proof of the NP-hardness of this problem by reducing the multiple subset sum problem to it can be found in [22].

In [13–15], Mishra et al. introduce the concept of the I-factor to analytically model the extent of overlap between two wireless channels. In [15], the authors extend the linear programming (LP)-based formulation of [4], which performs joint channel assignment and routing in multi-radio WMNs, to use partially overlapped channels as well as non-overlapping (orthogonal) channels.

In [21], Raniwala et al. propose a multi-channel WMN architecture (called Hyacinth) based on nodes equipped with multiple 802.11 radios and the associated distributed channel assignment and routing algorithms. Hyacinth’s 802.11 interfaces operate on non-overlapping channels and the distributed channel assignment algorithm assumes that the connectivity graph of the multi-radio nodes is a tree.

In [20], Ramachandran et al. propose a centralized algorithm (called BFS-CA) for channel assignment in multi-radio WMNs to minimize interference from co-located wireless networks. They define an interfering radio with respect to a multi-radio node of the WMN as a simultaneously operating radio visible to the WMN node but external to the WMN, and estimate interference on a specific channel with the number of interfering radios on that channel.

In [25], Skalli et al. propose an interference-minimizing centralized channel assignment scheme (called MesTiC) that considers traffic patterns of the mesh network and connectivity issues. Like [20], MesTiC relies on using a default channel for topological connectivity and network management purposes. Like [21], MesTiC assumes that WMN traffic is directed towards a gateway node that provides access to the wired network.

Another centralized algorithm specific to the infrastructure multi-radio WMNs, where the outgoing traffic is directed to a gateway node, is POCAM [32] (Partially Overlapped Channel Assignment for MRMC-WMN). POCAM is a backtracking search algorithm for channel assignment and does not address the flow-radio coupling problem. POCAM assumes a tree routing topology rooted at the gateway node.

In [8], Hoque et al. propose a new interference model derived in a broad sense from the I-factor [15] model of Mishra et al., and propose the concept of the I-Matrix. I-Matrix is a table maintained separately for each multi-radio node of the WMN. Each row of the I-Matrix holds the interference effects (costs) from all other channels for a specific channel. Using the I-Matrix tables, a centralized load-aware channel assignment algorithm which iteratively assigns channels to the links is proposed. The proposed algorithm makes use of the partially overlapped channels. As a channel is assigned to a link, the I-Matrices of all of the multi-radio nodes are updated. The flow-radio coupling problem is not addressed.

Both [6] and [19] propose mixed integer linear programs (MILP) for the joint channel and flow-radio assignment problem, and use partially overlapping and orthogonal channels. In [6], the proposed formulation incorporates network traffic information and is load aware, with the objective to maximize aggregate end-to-end throughput while minimizing queueing delays. With its problem domain specification the joint channel and flow-radio assignment problem, and with its load aware formulation, [6] is the closest effort to our study; however, as indicated, it is a MILP formulation, while we propose a set of distributed tunable algorithms for the same domain.

In [26], Subramanian et al. develop semi-definite programming (SDP) and integer linear programming (ILP) models to obtain bounds on the optimal solution of the channel assignment problem using orthogonal channels, and they generalize their ILP model for overlapping channels. They propose a Tabu search-based centralized algorithm and another centralized algorithm based on a greedy heuristic for the Max $K$-cut problem. Without considering the flow-radio assignment problem or the network traffic patterns, they derive a greedy distributed algorithm from the centralized Max $K$-cut based one.

In [7, 12, 33], distributed schemes for jointly addressing channel assignment and routing in multi-radio wireless networks are proposed. The distributed scheme proposed in [24] considers only the channel assignment problem. Common to [7, 12, 24, 33] is that they only use orthogonal channels for channel assignment and do not consider the flow-radio assignment problem.

Also in [34], a joint MRMC assignment, macro and micro-time scheduling and routing scheme, called $M4$, is proposed. Similar to [33], $M4$ uses only non-overlapping channels and does not address the flow-radio assignment problem, whereas DFRCA makes use of all available channels (both overlapping and non-overlapping) and addresses the flow-radio assignment problem.

In [17], a cluster-based topology control and channel assignment algorithm (CoMTaC), which is based on the usage of default radio interfaces operating on default channels, is proposed. Each cluster selects its default channel by passively monitoring the traffic load on each channel as in [20]. A multi-radio node bordering multiple clusters has its second interface tuned to the default channel of the highest priority neighbor cluster. For selecting the channels of the non-default radio interfaces, each node estimates the interference on each channel using the average link layer queue length as an interference metric. CoMTaC does not address the flow-radio assignment problem.

Ko et al. in [10] propose a distributed channel assignment algorithm and the accompanying distributed protocol for multi-radio 802.11 mesh networks. They employ a greedy heuristic for channel selection that uses only local information and do not consider flow-radio assignment or routing. They do not use network traffic information and perform channel assignment using only physical topology information. Similar to the I-factor concept used in the current paper, they model interference between wireless channels using a linear cost function $f(a,b)$ ($a$ and $b$ being the wireless channels) and use overlapping channels.

In [18], Rad et al. propose an optimization model (JOCAC) that is solved by exhaustive search for joint channel assignment and congestion control of TCP traffic in an infrastructure multi-radio WMN. The solution to the model is searched exhaustively either in a centralized manner on a gateway node to yield an optimal solution, or in a distributed manner on each multi-radio node to yield a partially optimal solution. JOCAC assumes a tree routing topology like [21] and does not address the flow-radio assignment problem in a setting where the traffic does not concentrate on gateway nodes.

3 Problem definition

In a multi-hop multi-radio WMN, each node has $D$ half-duplex radios ($D$ is $2$ in most of the scenarios). Out of $M$ channels available (e.g. $M=11$ for 802.11b/g in the FCC domain), which channels should be assigned to these radios, considering also the assignment (coupling) of flows to radios? We propose a distributed algorithm to decide on flow-radio coupling and to compute the channels to be assigned to radios. We assume that each transmitter uses a given fixed power while transmitting a radio signal and that the wireless medium has only slow-fading characteristics. We also assume traffic sources and destinations are identified a priori in the network, together with the rate of the traffic flowing among them, which can be achieved by traffic monitoring. We assume fixed rate traffic (CBR traffic) and we assume that node positions are fixed and known. Additionally, we assume routing is given a priori, i.e., the end-to-end paths are already known.

Because spatial distances between multi-channel multi-radio (MC-MR [30]) nodes are given a priori and transmission powers are fixed, the problem of minimizing interference is resolved into a joint flow-radio coupling and channel separation optimization problem. For a given node, the channel assignment problem might be resolved as a function of the co-channel and adjacent channel interference, which in turn is modeled using the ideas given in [15] and [29], and as a function of the known traffic patterns.

3.1 Formal notation

3.1.1 Node definition

A node has $D$ radio interfaces and is denoted by $n_i$ (or just by $i$ where appropriate), where $i \in [1,\left| N\right| ].$ N  denotes the set of multi-radio nodes in the WMN. The $kth$ radio of $n_i$ is denoted by $(i,k)$. The position of $n_i, P_i$ is given as a point in the chosen coordinate system. The transmission range of a node is $d_T$ and its interference range is $d_I$, where $d_I \ge d_T$.

3.1.2 Flow definition

We assume there are a multitude of multi-hop application-level flows (e.g., TCP/UDP flows) between various pairs of nodes in the mesh network. We call the node from which a multi-hop flow originates as the traffic source for that specific flow, and the node to which the multi-hop flow is addressed as the traffic destination. Multiple application flows may intersect at a mesh node, which implies that a mesh router may be responsible for routing packets belonging to multiple application flows.

Because routing (the paths end-to-end flows will follow) is assumed to be given, and end-to-end traffic patterns between node pairs are known a priori (which can also be measured by traffic monitoring), we decompose end-to-end flows into one-hop unidirectional flows using the available routing information. Our flow definition is based on these one-hop flows. If multiple end-to-end flows pass through the adjacent nodes $i$ and $j$ in the same direction (e.g. from $i$ to $j$), then the magnitude of the one-hop unidirectional flow from $i$ to $j$ used in our flow model is the sum of the magnitudes of all of those end-to-end flows. Hence, we consider aggregate flows between two adjacent nodes. Throughout the discussion below, $F$ denotes the set of these one-hop unidirectional (aggregate) flows between neighbor nodes. A flow between nodes $i$ and $j$ (where the definition of a flow imposes that $i$ and $j$ are one-hop neighbors) is denoted by $f_{i,j,k,l,x}$ or $f_{i,j}$. In the former notation, $k$ is the identification of the radio interface of node $i$ on which the flow is coupled. Similarly, this flow is coupled on the $l$th radio interface of node $j. x$ denotes that the $k$th radio of $i$ and the $l$th radio of $j$ are operating on channel $x$. This notation is employed in contexts where the channel of the wireless link carrying the flow is relevant. The latter notation just denotes the fact that the flow is between nodes $i$ and $j$, and the channel of the wireless link carrying the flow is irrelevant. $\left| f_{i,j} \right|$ denotes the magnitude of the flow from $i$ to $j$.

3.1.3 Physical layer parameters

The number of available wireless channels is $M$, for which a typical value for IEEE 802.11b/g is $11$ in the Federal Communications Commission (FCC) domain. The channel separation between two consecutive orthogonal channels is $O_\Delta$, which is five for 802.11b/g.

Table 1 provides a quick reference for the various symbols used throughout the paper.

Table 1 Definitions of symbols and abbreviations

3.2 Relation between flow-radio assignment and channel assignment

As explained in Sect. 3.1, DFRCA first derives one-hop aggregated flows from the application-level flows observed in the network. Hence when we refer, in the context of DFRCA’s procedures, to a flow between two mesh nodes, a one-hop aggregated flow between two neighbor nodes is implied. This aggregated flow possibly carries packets from multiple application-level multi-hop flows. As discussed in detail in Sect. 4.1, before assigning channels to radios, DFRCA first intelligently schedules radios to each of these flows. And while scheduling radios to flows, one of the objectives that DFRCA keeps is to maximize the expected number of disjoint subgraphs, which can later be assigned to different (possibly orthogonal) channels [see Sects. 4.2, 4.3 for the details on these subgraphs]. DFRCA requires proper shielding among the radio interfaces of a mesh node that will prevent crosstalk among them.

As detailed in Sect. 2, in the context of multi-radio channel assignment the radio scheduling problem, the assignment of radios to flows, is overlooked in the literature despite its prominent impact on the performance of channel scheduling. And many existing works [10, 13–15, 17, 18, 20, 24, 34] either assume uniform traffic between each pair of neighboring mesh nodes or do not consider the traffic patterns at all. However, as discussed in Sect. 4.2, a channel assignment scheme can better allocate the available spectrum among the radios by carefully obtaining balanced disjoint subgraphs, a goal DFRCA achieves during the flow-radio assignment phase [see Sect. 4.1]. DFRCA tries to obtain disjoint subgraphs carrying an equal amount of traffic with the aim of minimizing the maximum total intra-subgraph interference. This makes DFRCA traffic-aware.

Careful flow-radio assignment also helps to eliminate unnecessary links between mesh routers, further reducing interference. Considering the established routes and the traffic patterns in the mesh network, DFRCA does not allocate superfluous radio resources to establish a wireless link between two mesh routers between which no traffic exists. This gives the subsequent channel assignment phase a smaller problem instance, i.e., smaller number of radios to allocate channels for.

In previous studies, the channel assignment problem was addressed in various levels of granularity: flow, link and segment. In flow-based schemes [31, 35], channel assignment is performed at the granularity of an end-to-end multi-hop flow, meaning that all packets belonging to the same multi-hop flow are scheduled on the same channel, whereas in link-based schemes [16, 26, 27], the level of granularity is a link between two radios and packets of a multi-hop flow can potentially traverse a multitude of different wireless channels.

Another class of channel assignment schemes has recently been proposed mostly in the context of cognitive radio networks (CRNs), where channel assignment is performed at the granularity of segments. These segment-based approaches [36–38] partition an end-to-end flow into multiple segments opportunistically according to the availability of fallow spectrum in different regions of the network. Because DFRCA tries to identify disjoint subgraphs and assigns channels to them, its operation is similar to these segment-based approaches. However unlike previous work, by aggregating multi-hop flows into one-hop flows and intelligently scheduling radios to these one-hop flows through flow-radio assignment, DFRCA controls in a distributed fashion the subgraphs formed prior to channel assignment. Unlike the case in CRNs, DFRCA has control on the segmentation of the network.

4 A distributed scheme for joint flow-radio and channel assignment

Our distributed joint flow-radio and channel assignment scheme consists of four phases, and each multi-radio node executes each phase in parallel. During the phases, a node shares information with its $k$-neighborhood, $k$ being a parameter of our distributed scheme. $k$ is chosen in relation to the interference range, $d_I$. A typical value for $k$ is $2$, which implies that a node initially exchanges messages only in its $2$-neighborhood. Only at the final phase, where final channel selections are announced in the WMN, might a node have to exchange messages outside its $k$-neighborhood to assure that radio links are actually established. The scheme consists of the following four phases:

• 1. Flow-Radio Assignment Phase

• 2. Transmitter Announcement (TA) Phase

• 3. Channel Selector Election (SE) Phase

• 4. Conflict Elimination (CE) Phase

4.1 Flow-radio assignment phase

A single node is free to assign each aggregated single-hop flow entering or exiting itself to one of its radios independently without having to consider other nodes. The heuristic used for flow-radio assignment evenly distributes the total traffic (inbound and outbound) among the radios, so that the flows will have a greater chance of being assigned to different channels, reducing co-channel interference. This method also promotes the higher utilization of the available radio resources of a node and increases available capacity in the WMN. Algorithm 1 outlines the heuristic used to address the flow-radio assignment subproblem.

In Algorithm 1, src[$f$] and dst[$f$] denote the source and the destination nodes of the flow $f$, respectively. Algorithm 1 tends to leave flows with relatively large bandwidth demands on their own radios and in this way, gives the channel assignment procedure a chance to decouple relatively high traffic flows, reducing interference. It also assigns flows between the same pair of nodes to the same radios on these nodes (see Line 17), as long as the capacity constraints of the radios are not violated. A flow from node $i$ to $j$ and another flow from $j$ to $i$ are coupled on the same radios of $i$ and $j$. Hence, it concentrates all flows between two neighboring nodes on the same radios.

Algorithm 1 treats (aggregated) flows as atoms, meaning that it does not divide a flow among multiple radios in a node. This approach ensures that all packets belonging to the same single-hop flow are transmitted and received by the same radios respectively at the sending and receiving nodes. This is also true for a multi-hop flow, which is decomposed into single-hop flows by the single-path routing protocol. Hence, Algorithm 1 ensures that all packets of a multi-hop flow experience similar channel conditions in exactly the same order, although they may be transmitted on different wireless channels and at varying levels of interference. This method mitigates packet reordering problems that adversely affect the performance of reliable transport protocols or real-time applications.

Because Algorithm 1 is a heuristic that schedules all packets of an outgoing (or incoming) flow on the same transmitter (or receiver), it may fail to find a feasible schedule. Algorithm A.1 (see FlowBalancer in Online Resource $1$) tries to balance a node’s overflown and underflown radios if capacity constraints are violated. Algorithm A.1 achieves this goal by exchanging flows on an overflown radio with flows on an underflown radio without violating radio capacity constraints and it never splits the incoming/outgoing packets of a flow among multiple radios of a node as this would greatly increase packet reordering problems in the flow. All of the incoming packets of a flow are received on the same radio on a node, and all of the outgoing packets of a flow are transmitted by a potentially different radio of that node. Splitting the incoming/outgoing packets of a flow among different channels on a multi-radio node causes packet reordering problems due to the different channel conditions experienced by consecutive packets. Please refer to Online Resource $1$ for supplementary Algorithms A.1–A.1.4.

4.2 Transmitter announcement phase

The TA-Phase collects information about all flow-radio assignments in a $k$-hop neighborhood. Because flow-radio assignment information is disseminated in the $k$-neighborhood of each node during this phase, at the end of it, each node has an estimate on the number of (single-hop) flows that can be decoupled from each other considering only its $k$-neighborhood.

In this context, decoupling flows means putting each flow in a $k$-neighborhood on a different channel, which mitigates inter-flow interference and, in the context of multi-hop flows, intra-flow interference. Of course, decoupling may not be feasible if there are not enough wireless channels and/or radios in a $k$-neighborhood. The channel configuration performed by such a $k$-neighborhood local algorithm may also fall far from a global optimum solution if the WMN’s neighboring nodes do not perceive similar $k$-neighborhoods. However, for routing topologies where $k$-hop neighbors share similar $k$-neighborhoods, the TA-Phase, given in Algorithm 2, achieves intelligent channel assignment by correctly estimating the number of flows to be decoupled in the $k$-neighborhood.

A node starts the TA-Phase by exchanging flow-radio assignment information in its $k$-neighborhood. For this purpose, it broadcasts (on a common channel) a TA (Transmitter Announcement) message containing $C$, the flow-radio coupling information of itself, with a $TTL$ set to $k$ (see Algorithm 2). A node that receives an announcer node’s TA message for the first time, decrements the $TTL$ and broadcasts the message, unless the message’s $TTL$ is zero. As the node receives TA messages from its $k$-hop neighbors, it constructs its $k$-hop neighborhood set, $H_k$, and buffers the $k$-neighborhood flow-radio assignment information in $(N_k, F_k)$.

After the TA messages have been exchanged, the node proceeds to calculate the set of disjoint $k$-neighborhood subgraphs, $\Psi$, using Algorithm A.2 (see FindSubgraphs in Online Resource $1$). The term subgraph defines a set of radios (vertices) connected with incident flows (edges). Two disjoint subgraphs in a node’s $k$-neighborhood share no common radios [see Fig. 1(a)]. Hence, if there are enough physical channels, each subgraph may operate on a distinct channel. Outside the node’s $k$-neighborhood these two subgraphs may be connected, in which case they will have to operate on the same channel [see Fig. 1(b)].

Fig. 1

$k$-neighborhood subgraphs, $\Psi = \left\{ \psi _1, \psi _2, \psi _3 \right\}$, of $n_i$. a $n_i$ perceives that it may be possible to operate $\psi _1, \psi _2$ and $\psi _3$ on distinct (possibly non-overlapping) channels. b However, two or more subgraphs may in reality be connected outside $n_i$’s $k$-neighborhood

Algorithm A.2 operates by aggregating radios which are connected by flows into distinct subgraphs. If two radios are connected via a path of flows, then they are put into the same subgraph. And if two radios are not connected via a path of flows in the $k$-neighborhood, then they belong to different subgraphs. Algorithm A.2 leaves the flows whose transmitters are not in $n_i$’s $k$-neighborhood out of $\Psi$. This procedure is motivated by the effort to reuse channels outside the $k$-neighborhood of a node under consideration.

After computing $\Psi$, the node constructs the conflict graph of $\Psi , G_c(\Psi ,E)$, using Algorithm A.3 (see FindConflictGraph in Online Resource $1$). An edge $(\psi _1,\psi _2)$ is added to $G_c(\Psi ,E)$ whenever a transmitter radio in $\psi _1$ interferes with a receiver radio in $\psi _2$ (see Fig. 2). Algorithm A.3 constructs $G_c(\Psi ,E)$ by checking every flow in $\psi _2$ against every flow in $\psi _1$ and adding the edge $(\psi _1,\psi _2)$ to $G_c(\Psi ,E)$ if the receiver of at least one flow in $\psi _2$ is in the interference range of at least one transmitter in $\psi _1$.

After computing $G_c(\Psi ,E)$, the node then calls a greedy vertex colouring heuristic to find the set of colour classes, $\Psi _c$, of $G_c(\Psi ,E). |\Psi _c|$, which approximates the chromatic number of $G_c, (\chi (G_c))$, is an upper bound on the minimum number of channels needed for all the subgraphs in $\Psi$ to decouple. Considering $\chi (G_c)$ instead of $\chi (\Psi )$ promotes the spatial reuse of the channels inside the $k$-neighborhood.

Fig. 2

$k$-neighborhood subgraphs of $n_i$. a $\Psi$ of a linear topology, where $d_I = d_T$. b $G_c(\Psi ,E)$ for Fig. 2(b). $(i,k) \Longrightarrow (j,l)$ denotes that transmitter $(i,k)$ interferes with receiver $(j,l)$

By the end of the TA-Phase, the set of one-hop neighbors, $H_1$, and the set of $k$-hop neighbors, $H_k$, are available for the remaining phases of the distributed scheme.

4.3 Channel selector election phase

In this phase, a node determines the subgraphs of its $k$-neighborhood (a subset of $\Psi$) for which it will select channels, and becomes the manager of those subgraphs. The node also estimates the managers of the remaining subgraphs in $\Psi$. Such nodes are called remote managers with respect to the node under discussion. Having estimated the number of distinct channels needed in its $k$-neighborhood, the node then proceeds to determine those channels.

The SE-Phase begins by sending and receiving broadcast SE (Selector Election) messages in the $k$-neighborhood. Each node tells its $k$-hop neighbors the subgraph count in its $k$-neighborhood, $|\Psi |$, and its set of colour classes, $\Psi _c$. The node builds two tables using the SE messages it receives. The first table, $M_{|\Psi |}$, holds the subgraph counts of the nodes in the $k$-neighborhood, and the second table, $M_{\Psi _c}$, holds their sets of colour classes. After these two tables are built, the node iterates over all the radios in each of its colour classes to determine the manager that will select a channel for each radio, using Algorithm A.4 (see Online Resource $1$).

In Algorithm A.4, the node that contains the radio in one of its colour classes and has the highest subgraph count (highest $|\Psi |$) is selected as the manager. Nodes with higher subgraph counts are given priority for selecting channels because they can decouple more subgraphs. Of the nodes with equal subgraph counts, outside the delegation range (explained later in this section) spatially closer nodes are preferred. Inside the delegation range nodes with smaller ids are preferred. Because radios in a subgraph must operate on the same channel, once the manager of a radio is determined, all other radios in the same subgraph are assigned the same manager. As the node determines the managers of the radios in its $k$-neighborhood, it builds a set of remotely managed colour classes, $S_R$, and a set of the colour classes it manages, $S_i$. It notes the selected manager of each colour class in the table $M_I$.

As will be explained later in this section, a manager uses its colour classes to select channels for the radios it manages. For channels selected by different managers of the same $k$-neighborhood to be as spectrally far as possible from each other, a mechanism for coordinating the colour classes of these spatially close managers is needed. For this purpose, we define the delegation range, $d_D$. Inside a circular region of radius $d_D$ in a node’s $k$-neighborhood, the colour classes, hence the channel selections, of managers are coordinated. This coordination ceases outside $d_D$. Increasing $d_D$ decreases the parallelism achieved by the distributed channel assignment procedure. However, especially for long chain topologies, increasing $d_D$ also substantially decreases the intra-flow interference in the network (the effects of $d_D$ on such interference are explored in Sect. 5).

In Fig. 3, we give an example for the coordination need that may arise between managers. The node $m$ announces to $m'$ its set of colour classes, $\Psi _c = \{\psi _{c1}, \psi _{c2}\}. m'$ determines its own colour classes, $\Psi '_c = \{\psi '_{c1}\}$, which implies that it is responsible for selecting a channel for the radios in $\psi '_{c1}$. However, $m'$ realizes that $\psi '_{c1} \cap \psi _{c1} \ne \varnothing$, and delegates the management of the radios in $\psi '_{c1} \setminus \psi _{c1}$ to manager $m$ because $m$ is inside the delegation range. Algorithm A.5, which outlines these steps, stores the delegation mappings in $M_D$ to be used during the CE-Phase.

Fig. 3

Coordination need for colour classes of $k$-neighbor manager nodes from the point of view of $m'$

By the end of the SE-Phase, in $S_i$ and $S_R$ the node contains an estimation of its $k$-neighborhood channel selectors (which $k$-hop neighbors will select channels for which sets of radios). The node can now intelligently assign channels to the subgraphs it is responsible for $(S_i)$ by efficiently using the channel space available in its $k$-neighborhood. The channel allotment heuristic is given in Algorithm 4, which starts by building the weighted conflict graph, $G_c(S_A, E)$, of $S_A = S_R \cup S_i$. $G_c(S_A, E)$ is later used in the SE-Phase for intelligently mapping selected channels to the colour classes of the $k$-neighborhood. The computation of $G_c(S_A, E)$ is similar to that of $G_c(\Psi , E)$ and is given in Algorithm A.6 (see Online Resource $1$). The weight of the undirected edge $(\psi _{c1},\psi _{c2})$ in $G_c$ estimates the total physical interference between the colour classes $\psi _{c1}$ and $\psi _{c2}$ assuming both colour classes operate on the same wireless channel and is calculated as follows:

$$\begin{aligned} \begin{aligned} W_{(j',l')}(\psi _c) =&\sum _{ \begin{aligned}&f_{i,j,k,l} : (i,k) \in \psi _{c} \\&d(P_i, P_{j'}) \le d_I \end{aligned} }{ \frac{1}{ d^{\alpha }(P_{i}, P_{j'})} } \\ \\ W(\psi _{c2},\psi _{c1}) =&\sum _{ f_{i',j',k',l'} : (j',l') \in \psi _{c2} }{W_{(j',l')}(\psi _{c1}) } \\ \\ W_E [ (\psi _{c1}, \psi _{c2}) ] =& \,W(\psi _{c1}, \psi _{c2}) + W(\psi _{c2}, \psi _{c1}), \end{aligned} \end{aligned}$$

(1)

where $W(\psi _{c2},\psi _{c1})$ is an estimation of the total physical interference caused by all transmitters in $\psi _{c1}$ on each receiver of $\psi _{c2}$. The edge weights of $G_c$ are stored in the dictionary $W_E$ by Algorithm A.6.

Algorithm 4 then prepares a list of channels, $L$, to be used in the $k$-neighborhood by calling Algorithm A.7 (see Online Resource $1$). To minimize interference between subgraphs (grouped as colour classes) in the $k$-neighborhood, Algorithm A.7 fills $L$ with $|S_A|$ channels as spectrally far as possible from each other. After $L$ is filled, Algorithm A.8 (see Online Resource $1$) is called to prepare a dictionary of channel lists, $M_L$, which maps manager ids in the $k$-neighborhood to the estimated channel selection lists. The list of channels to be used for colouring $S_i$ is then given by $M_L$[$i$]. To determine the $|S_i|$ channels to be used out of $L$, Algorithm A.8 employs the heuristic given in Algorithm A.9, whose main motivation is to select $|S_i|$ channels as spectrally far as possible from each other. For example, if $L = [1, 6, 11]$ and two channels are to be selected $(|S_i| = 2)$, the heuristic selects channels $1$ and $11$. Or if $L = [5, 6, 7 ]$, the heuristic selects channels $5$ and $7$.

At the end of the channel allotment, as the final step of the SE-Phase, the channels in $L$ are distributed to the colour classes in $S_A = S_R \cup S_i$ using $G_c(S_A, E)$ with the heuristic given in Algorithm A.11 (see Online Resource $1$). For traversing $G_c$, vertex weights, $W_V$, are calculated. The weight of a vertex is the sum of the incident edge weights. A vertex with a higher weight implies a colour class (a set of subgraphs) that puts/receives higher levels of interference on/from the other colour classes that are incident to it in $G_c$ than a vertex with a lower weight. Hence, vertices with higher weights are given priority over vertices with lower weights during traversal. Breadth-first traversal of the graph starts with the heaviest vertex (see Algorithm A.12 in Online Resource $1$). Next, the incident vertices of the currently visited vertex are visited. As each vertex is visited, the channel minimizing the total interference between the previously visited vertices and the current vertex is assigned to the vertex (see Algorithm A.11). This minimum-interference-channel is selected according to the cost function given in (2) for the current vertex $v$:

$$\begin{aligned} I_c(v) = \sum _{w : w \in S_A \wedge M_V[ w ] \ne -1 }{ \frac{W_E[ (v,w) ]}{|c - M_V[ w ] |} }, \end{aligned}$$

(2)

where $c$ is a channel in $L, M_V$ is the dictionary that holds the colour class-channel mappings and $W_E$ is the edge weights of $G_c$. $M_V\text {[} w \text {]} = -1$ indicates that $w$ has not been visited yet. This scheme ensures that heavily interfering subgraphs are given priority for channel assignment and are assigned channels as spectrally far as possible from each other.

4.4 Conflict elimination phase

After the SE-Phase completes, manager nodes will have determined candidate channels for the radios they are responsible for. However, radios connected with a path in $(N, F)$ may have been assigned different channels if the nodes responsible for assigning channels are neighbors of greater than $k$ hops in $(N,F)$, and if those nodes have selected conflicting channels for the radios. If these radios are actually assigned different channels, then the physical links that should exist between them will break. We call this situation a conflict, and the goal of this CE-Phase is twofold:

• 1. Eliminating any conflicts that may have arisen in the SE-Phase.

• 2. Announcing the selected channels to the other neighbors that have delegated this task to the manager nodes.

During the CE-Phase, the selected channel information will be negotiated and any conflicts will be resolved. Algorithm 5 outlines the CE-Phase, and it tries to determine the channel selected by the node with the largest number of subgraphs in its $k$-neighborhood and is the most heavily loaded node with the smallest node id. Layer 3 or layer 2 addresses can be employed as the node ids and we assume that the employed ids are unique throughout the network.

A node starts the CE-Phase by announcing the channel selections of the radios for which it is a manager by sending unicast CS (Channel Selection Announcement) messages. A CS message contains the selected wireless channel, the subgraph count $(|\Psi |)$ of the origin node, the magnitude of the total inbound/outbound traffic on the origin node $(X)$ and the node’s unique id (see Algorithm A.13). If the node is a manager for one of its own radios, then it sends the associated CS message to all one-hop neighbors of that radio on the radio’s subgraph. If the node is a manager of a remote radio that is not connected to any of the node’s own radios in the node’s $k$-neighborhood, then the node sends the associated CS message in a multi-hop manner to the owner of the remote radio.

As the node receives a CS announcement, it determines the manager of the associated radio by selecting the node among the announcers with the highest subgraph count and the highest traffic but with the smallest id (see Algorithm A.14). If a new CS announcement changes the previously selected manager for a radio, then the node receiving the announcement announces the new selection to all one-hop neighbors on that radio’s subgraph. Otherwise, the receiver of the announcement makes no new announcements.

5 Validation and evaluation

To validate our distributed scheme and evaluate its performance, we simulate it in a custom environment based on the CSIM for Java [1] simulation engine, which is a library for developing discrete-event simulations. We develop a packet-based simulator that can truly simulate our distributed scheme using message exchanges among nodes simulating our multi-radio routers. Next, we first describe how we validate our scheme using small topologies, for which it is easy to compute the optimal configurations. Then we introduce the metrics to evaluate our scheme. Finally, we present our simulation results to assess the scheme’s performance.

5.1 Validation using small networks

We ran simulations on five small networks (Fig. 4) to validate the correctness of the proposed scheme. In Fig. 4, circles represent two-radio nodes and arrows represent flows of equal magnitude between these nodes. The channels configured by the distributed scheme at the end of simulations are indicated atop the flow arrows. In each scenario, the interference range is equal to the transmission range. The simulation parameters used for these networks are given in Table 2. As evident from Fig. 4, the proposed scheme is able to find optimal channel configurations for these networks.

Fig. 4

Verification of the distributed scheme on small networks of two-radio nodes where $d_I = d_T$. a $3$ Nodes $2$ Flows linear. b $3$ Nodes $3$ Flows circular. c $4$ Nodes $4$ Flows circular. d $4$ Nodes $4$ Flows multi-flow. e $7$ Nodes $6$ Flows linear

Table 2 Simulation parameters for Fig. 4

Table 3 Simulation parameters for Figs. 7, 8, 9, 10, 11, 12, 13, 14 and 15

5.2 Evaluation metrics

In this section we describe in detail the metrics used in evaluating, through simulations, the effectiveness and performance of the proposed distributed scheme. As detailed in Sect. 5.3, these metrics are computed for random and single-channel assignment schemes (configurations), as well as for the proposed algorithm configurations, to assess the performance of the proposed scheme in mitigating interference and in increasing residual capacity. The first of the proposed metrics, average protocol interference, is also used to determine whether a given flow-radio coupling and channel configuration is feasible, as explained in Sect. 5.3.

5.2.1 Average protocol interference metric

The average protocol interference metric, $I_{ap}$, uses the concept of the I-factor [15], assuming a constant transmission power for each transmitter radio. This metric can use any I-factor model [13, 15, 28], $I(x,y)$, where $I(x,y)$ is the normalized amount of interference signal power a transmitter operating on channel $x$ puts on a receiver operating on channel $y$. In this metric, we do not take the effects of slow-fading [23] into account and assume that a constant fraction of the transmission power leaks on adjacent channels (defined by the I-factor model in use) throughout the interference range of a transmitter radio (we are concerned about protocol interference). Outside the interference range of the transmitter, the interference power becomes $0$ (i.e., no interference). $I_{ap}$ is calculated as follows for a given network $(N,F)$, where $N$ is the set of multi-radio nodes and $F$ is the set of (one-hop) flows:

$$\begin{aligned} \begin{aligned} F_{f_{i, j, k, l,x}} =&\left\{ \begin{aligned}&f_{i', j', k', l', y}: f_{i', j', k', l', y} \in F \ \wedge \\&f_{i', j', k', l'} \ne f_{i, j, k, l} \ \wedge \\&\left| P_j - P_{i'} \right| \le d_I \end{aligned} \right\} \\ \\ i_{f}((j,l), x) =&{\sum _{ f_{i, j, k, l, x} \in F }\ \ { \sum _{ f_{i', j', k', l', y} \in F_{f_{i, j, k, l,x}} }{ I(x,y) } }} \\ \\ I_{ap} =&\,\frac{ \displaystyle \sum _{(j, l, x): \exists (i, k), f_{i, j, k, l, x} \in F}{i_f((j, l), x)} }{ \left| \left\{ (j, l): \exists (i, k), f_{i, j, k, l} \in F \right\} \right| }. \end{aligned} \end{aligned}$$

(3)

In (3), $F_{f_{i,j,k,l,x}}$ is the set of flows whose transmitters interfere with the receiver $(j,l)$ of the flow $f_{i,j,k,l,x}$. The definition of $F_{f_{i,j,k,l,x}}$ implies full-duplex operation of the radios. Typical interference scenarios captured by $F_{f_{i,j,k,l,x}}$ are depicted in Fig. 5(a), where the target flow in the figure corresponds to $f_{i,j,k,l,x}$. The $i_{f}((j, l), x)$ value is the total protocol interference on $(j,l)$, which operates on channel $x$. The metric, $I_{ap}$, quantifies the average protocol interference on the receiver radios in the network.

Fig. 5

Typical interference scenarios in the contexts of the evaluation metrics. a Typical interference scenarios in the context of $I_{ap}$. b Typical interference scenarios in the contexts of $I_{awp}$ and $R_{bc}$

5.2.2 Average physical interference metric

The average physical interference metric, $I_{aph}$, is similar to $I_{ap}$ but takes slow-fading into account while calculating the interference on a receiver from an interferer. More precisely, $I_{aph}$ is given by:

$$\begin{aligned} \begin{aligned} i_{f}((j,l), x) =&{\sum _{ f_{i, j, k, l, x} \in F }\ \ { \sum _{ f_{i', j', k', l', y} \in F_{f_{i, j, k, l,x}} }{ \frac{ I(x,y) }{ |P_{j} - P_{i'} |^\alpha } } }} \\ \\ I_{aph} =&\frac{ \displaystyle \sum _{(j, l, x): \exists (i, k), f_{i, j, k, l, x} \in F}{i_f((j, l), x)} }{ \left| \left\{ (j, l): \exists (i, k), f_{i, j, k, l} \in F \right\} \right| }, \end{aligned} \end{aligned}$$

(4)

where the definition of $F_{f_{i, j, k, l,x}}$ is given in (3).

5.2.3 Average weighted protocol interference metric

This metric aims to quantify the average of the flow-magnitude weighted protocol interference over all receiver radios in the network. The I-factor is again used to quantify the amount of interference between wireless channels. The average weighted protocol interference, $I_{awp}$, for a given network $(N,F)$ is defined as follows:

$$\begin{aligned} \begin{aligned} H_{f_{i, j, k, l,x}} =&\left\{ \begin{aligned}&f_{i', j', k', l', y}: f_{i', j', k', l', y} \in F \ \wedge \\&(i', k') \ne (j, l) \wedge (i', k') \ne (i, k) \ \wedge \\&\left| P_j - P_{i'} \right| \le d_I \end{aligned} \right\} \\ \\ i_w((j, l), x) =&{\sum _{ f_{i,j,k,l,x} \in F }\ { \sum _{ \begin{aligned}&f_{i', j', k', l', y} \in \\&H_{f_{i, j, k, l,x}}\end{aligned} }{ \frac{\left| f_{i', j', k', l', y} \right| }{\rho _{max}} I(x,y) }} } \\ \\ I_{awp} =&\frac{ \displaystyle \sum _{(j, l, x): \exists (i, k), f_{i, j, k, l, x} \in F}{i_w((j, l), x)} }{ \left| \left\{ (j, l): \exists (i, k), f_{i, j, k, l} \in F \right\} \right| }. \end{aligned} \end{aligned}$$

(5)

In (5), $d_I$ is a transmitter’s interference range. $H_{f_{i, j, k, l,x}}$ is the set of flows whose transmitters interfere with the receiver $(j,l)$ of the flow $f_{i,j,k,l,x}$. $i_w((j,l), x)$ is the total weighted protocol interference on $(j,l)$, which operates on channel $x$. To calculate $i_w((j,l), x)$, we consider the following rules:

• A transmission from $(i,k)$ does not interfere with the receivers of other transmissions of $(i,k)$.

• The transmissions from $(j,l)$ does not interfere with the receptions on $(j,l)$.

These rules correspond to the half-duplex operation of the radios in the network. Typical interference scenarios captured by $H_{f_{i,j,k,l,x}}$ are depicted in Fig. 5(b), where the target flow in the figure corresponds to $f_{i,j,k,l,x}$. $I_{awp}$ also takes into account that a high traffic flow will have greater interference on a given receiver than a lower traffic flow on the same channel as itself. To capture this fact within $I_{awp}$, the interference from the transmitter of a given flow on a given receiver is weighted with the normalized flow time. The maximum interference that can be put by an interferer on a receiver is $1$, which will be the case if the interferer is operating on the same channel as the receiver under consideration and transmitting a total traffic of $\rho _{max}$ bps, fully utilizing its capacity, which implies that the interferer receives no data itself.

5.2.4 Receiver binary capacity model and average residual capacity metric

In this section, we describe an average residual capacity metric for the receiver radios in the network that is closely related to the total amount of interference in the network. As the interference on a receiver increases, the residual capacity on that receiver decreases. Hence, a good scheme that performs intelligent channel planning in a WMN should utilize radios and increase their residual capacities. To define the average residual capacity metric, $R_{bc}$, for a given flow-radio coupling and channel configuration, we first define our binary capacity model, $BC$, for a given receiver $(j,l)$ operating on channel $x$ as follows:

$$\begin{aligned} \begin{aligned} i_h((j, l), x) =&{ \sum _{ (i',k',y) } \ { \sum _{ \begin{aligned}&f_{i,j,k,l,x} \in F \wedge \\&f_{i', j', k', l', y} \in H_{f_{i, j, k, l,x}}\end{aligned} }{ I(x,y) } } } \\ BC_{(j, l), x} =&{\left\{ \begin{array}{ll} 0 &\quad {\text {if}}\quad \, i_{h}((j, l), x) \ge I_{thres} \\ \rho _{max} &\quad \text {Otherwise} \end{array}\right. }. \end{aligned} \end{aligned}$$

(6)

In (6), $H_{f_{i,j,k,l,x}}$ is the set of interferer flows of $f_{i,j,k,l,x}$, as given in (5). The total protocol interference on $(j,l)$, operating on channel $x$, is given as $i_{h}((j, l), x)$. The binary capacity model assumes that if the total protocol interference on a receiver is above a specified threshold, $I_{thres}$, then the capacity of that receiver is $0$ and no reception is possible. When $I_{thres} = 1$, an interferer operating on the same wireless channel as a receiver will make it impossible for that receiver to receive and correctly decode any data.

Having defined the binary capacity model, the average residual capacity metric, $R_{bc}$, is given as follows:

$$\begin{aligned} \begin{aligned} \Delta _{(j,l),x} =&\left( \begin{aligned} BC_{(j, l), x}&- \sum _{f_{i', j, k', l} \in F}{\left| f_{i', j, k', l} \right| } \\&- \sum _{f_{j, i', l, k'} \in F}{\left| f_{j, i', l, k'} \right| } \end{aligned} \right) \\ \\ R_{bc} =&\frac{ \displaystyle \sum _{(j, l, x): \exists (i, k), f_{i, j, k, l, x} \in F \wedge \Delta _{(j, l), x} \ge 0}{ \Delta _{(j,l),x} } }{ \left| \left\{ (j, l): \exists (i, k), f_{i, j, k, l} \in F \right\} \right| }. \end{aligned} \end{aligned}$$

(7)

In (7), $\Delta _{(j,l),x}$ denotes the residual binary capacity of the receiver $(j,l)$, which is on channel $x$. $R_{bc}$ is the average of the residual capacities of the receiver radios with non-negative residual capacities.

5.3 Simulation experiments

We run extensive simulation experiments to evaluate the flow-radio and channel assignment configurations that our DFRCA scheme produces. The configurations produced by DFRCA are compared against two other types of configurations. Hence we compare three different types of configurations which are explained as follows:

• 1. Single-channel configuration All transmitter and receiver radios operate on the same channel and all flows entering and exiting a node are coupled onto the same radio of that node as long as the total magnitude of these flows is less than or equal to the maximum data rate of the radio. Each radio in the network is utilized at less than or equal to $1$; if the total magnitude of a node’s flows exceeds the maximum data rate, then the node’s radios are maximally utilized in order, starting from radio $0$.

• 2. Random configuration The following steps generate a random flow-radio coupling and channel configuration for a given network:

  • (a) Flows arriving at and departing from a node are coupled with the radios of the node in random with uniform distribution, taking care not to violate the feasibility constraint mentioned above (the total traffic bound on a radio should be less than or equal to the fastest data rate available).

  • (b) Each link carrying traffic is assigned a random channel; however, links with common end points (radios) are assigned the same randomly selected channel.

• 3. DFRCA configuration This is a flow-radio coupling and channel configuration arrived at the end of the simulation process of our proposed DFRCA scheme.

A network topology is determined by the graph $(N,F)$ and the set of the positions of the nodes, $P$. The nodes are placed on a rectangular grid and shortest-path multi-hop flows are generated between randomly selected source and destination node pairs.

Unless otherwise stated, for each simulation parameter set, $50$ random network topologies are generated. Hence in the following figures, each data point represents the average over $50$ randomly generated topologies. For the random assignment scheme, unless otherwise stated, for each of the $50$ random network topologies, $100$ random flow-radio coupling and channel configurations are generated, and the average metrics over these $100$ configurations are calculated. This implies that each data point for a random configuration is the average of $5000$ random configurations.

Fig. 6

Effects of the delegation range $(d_D)$ on $I_{ap}, I_{aph}, I_{awp}$, and $R_{bc}$ for a chain topology of $10$ nodes

In Fig. 6, we observe the effects of the delegation range $(d_D)$ on DFRCA’s performance for a chain topology of $10$ nodes. Delegation range $(d_D)$ is a tunable parameter of DFRCA. When $d_D$ is extended up to four or more times the transmission range $(d_T)$, DFRCA yields an optimum solution. For smaller chains, DFRCA is able to find optimum solutions with smaller $d_D$. In backbone WMNs [3], where the traffic is routed towards a gateway node, a routing tree rooted at the gateway node is formed and such longer isolated chains are more common. However, if intra-mesh traffic does not concentrate on a special node as with backbone WMNs, a smaller $d_D$ will suffice.

Fig. 7

Effects of the network size $(|N|)$ on ${\mathbf{a}}\,I_{ap},\,{\mathbf{b}}\,I_{aph},\,{\mathbf{c}}\,I_{awp}$, and ${\mathbf{d}}\,R_{bc}$

Figure 7 compares DFRCA against single-channel and random configuration schemes and shows how the metrics change as the network size increases when the number of available wireless channels $(M)$ is $22$. Relevant simulation parameters can be found in the second column of Table 3. For all four metrics, the single-channel configuration scheme has the worst performance and DFRCA has the best performance. For $I_{ap}$, DFRCA achieves up to $246\,\%$ improvement with respect to the random configuration scheme and up to $298\,\%$ improvement with respect to the single-channel configuration scheme, both for $16$ nodes. For $I_{awp}$, the improvements are more pronounced: up to $819\,\%$ with respect to the random configuration and more than $10$ times with respect to the single-channel configuration, again both for $16$ nodes. For the $R_{bc}$ metric, DFRCA achieves up to $233\,\%$ improvement for $16$ nodes with respect to the random configuration and up to $867\,\%$ improvement for $100$ nodes with respect to the single-channel configuration. Figure 7 shows that, interestingly, the performance of the random configuration in terms of $I_{aph}$ closely follows the performance of the single-channel configuration. The improvement achieved by DFRCA in terms of $I_{aph}$ is $153\,\%$ for $16$ nodes and $145\,\%$ for $100$ nodes with respect to the single-channel configuration.

Fig. 8

Effects of the number of available wireless channels $(M)$ on $I_{ap}$ for different network sizes. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Figure 8 shows the averages of $I_{ap}$ in relation to the increasing number of available wireless channels $(M)$ over $50$ topologies for node counts of $16, 36, 64$ and $100$. The third column of Table 3 lists the relevant simulation parameters. The single-channel configuration scheme can make no use of the increasing number of wireless channels, whereas the random configuration scheme’s performance increases as the number of available channels increases because it has more channels to select from. However, DFRCA can utilize an increasing number of wireless channels better than the random configuration even for large numbers of nodes and flows. It is important to note that the random configuration yields more or less the same performance as the single-channel configuration for $100$ nodes in terms of $I_{ap}$ when the number of available channels is $11$ (as with IEEE 802.11 in the FCC domain).

Fig. 9

Effects of the number of available wireless channels $(M)$ on $I_{aph}$ for different network sizes. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Figure 9 reveals that the random configuration scheme performs worse than the single-channel configuration scheme in terms of $I_{aph}$ when the number of available channels is $11$. This result occurs because $I_{aph}$ assumes full-duplex operation of the radios. The random configuration scheme can, to some extent, decouple flows better than the single-channel configuration scheme where all the radios in the network are on the same subgraph, however, the random configuration fails to operate those decoupled flows sufficiently spectrally away from each other for $M=11,22$. The single-channel configuration can yield less interference compared to the random configuration by coupling flows on the same radios. Our DFRCA, on the other hand, effectively decouples flows, operates them spectrally away from each other and can spatially reuse the channels, allowing improvements of at least $132\,\%$ for $M=11$ and at least $145\,\%$ for $M=55$ (both for $64$ nodes) with respect to the random configuration. The improvements with DFRCA in terms of $I_{aph}$ with respect to the single-channel configuration are at least $127\,\%$ for $M=11$ for $64$ nodes and at least $153\,\%$ for $M=55$ for $100$ nodes.

Fig. 10

Effects of the number of available wireless channels $(M)$ on $I_{awp}$ for different network sizes. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

In Fig. 10, we observe the effects of the increasing number of wireless channels on $I_{awp}$. The improvements gained with the distributed scheme are even more pronounced for the flow-magnitude weighted metric in all four cases because DFRCA is flow-aware.

Fig. 11

Effects of the number of available wireless channels $(M)$ on $R_{bc}$ for different network sizes. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Figure 11 reveals that the proposed scheme can actually increase the average residual capacity in the network as the number of available channels increases. The random configuration can also increase the residual capacities, but in all four cases, DFRCA makes more intelligent use of the increase in the number of channels despite the fact that the number of available radios per node is kept constant. With $11$ channels, there are at most three non-overlapping channels; with $22$ channels there are five non-overlapping channels (channels $1, 6, 11, 16$ and $21$) and with $33$ channels there are seven non-overlapping channels. In all four cases, DFRCA can increase the performance for up to seven non-overlapping channels.

Fig. 12

Effects of the non-overlapping channel separation $(O_\Delta )$ on $I_{ap}$ for different network sizes for $M=22$. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Fig. 13

Effects of the non-overlapping channel separation $(O_\Delta )$ on $I_{aph}$ for different network sizes when $M=22$. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Fig. 14

Effects of the non-overlapping channel separation $(O_\Delta )$ on $I_{awp}$ for different network sizes when $M=22$. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Fig. 15

Effects of the non-overlapping channel separation $(O_\Delta )$ on $R_{bc}$ for different network sizes when $M=22$. a $|N| = 16$, b $|N| = 36$, c $|N| = 64$, d $|N| = 100$

Next, we turn our attention to the relationships between the non-overlapping channel separation $(O_\Delta )$ and $I_{ap}, I_{aph}, I_{awp}$ and $R_{bc}$. $O_\Delta$ is the minimum channel separation needed to consider two wireless channels as non-overlapping (orthogonal). For IEEE 802.11b/g, when two channels are separated by at least five channels, they are considered to be non-overlapping [2], thus, channels $1, 6$ and $11$ of IEEE 802.11b/g are non-overlapping. In Figs. 12, 13, 14 and 15, we observe the effects of increasing $O_\Delta$ on $I_{ap}, I_{aph}, I_{awp}$ and $R_{bc}$, respectively, for a wireless technology that has $22$ channels. When $O_\Delta$ is $1$, all $22$ channels are non-overlapping with respect to one another. When $O_\Delta$ is $9$, there exist at most three non-overlapping channels amongst the $22$ channels of the wireless technology: $1, 10$ and $19$. The simulation parameters used in these sets are given in the fourth column of Table 3.

As Fig. 12 reveals, $I_{ap}$ increases for the random configuration scheme and DFRCA as $O_\Delta$ increases. Because the single-channel configuration uses only one channel, its performance is not affected by $O_\Delta$. For $16$ nodes and $16$ flows in the network, the improvement gained by DFRCA with respect to the random configuration is $2.25$ when $O_\Delta = 1$, and $2.09$ when $O_\Delta = 9$. However, when there are $100$ nodes and $100$ flows in the network, the improvement gained by DFRCA over the random configuration scheme is $2.01$ for $O_\Delta = 1$ and $1.6$ for $O_\Delta = 9$. Hence, as the network grows in terms of node count and flow count, the number of available orthogonal channels becomes more important for DFRCA because it intelligently utilizes these orthogonal channels to reduce interference. This phenomenon can also be observed for $I_{aph}$ and $I_{awp}$ in Figs. 13 and 14, respectively. $I_{aph}$ increases faster for $O_\Delta > 5$ at $|N| = 64$ and $|N| = 100$ [see Fig. 13(c), (d), respectively]. Similarly, $I_{awp}$ increases faster for $O_\Delta > 5$ at $|N| = 64$ and $|N| = 100$ [see Fig. 14(c), (d), respectively] than at $|N| = 16$ or $|N| = 36$.

The observations made in Figs. 12, 13 and 14 are verified in terms of the residual capacities in Fig. 15. In all four cases, there is a linear decrease in $R_{bc}$ as $O_\Delta$ increases for the random configuration scheme. However, $R_{bc}$ decreases exponentially as $O_\Delta$ increases at $|N| = 36, |N| = 64$ and $|N| = 100$ with DFRCA (Fig. 15(b)–(d), respectively).

6 Conclusions and discussion

Flow-radio coupling in multi-radio WMNs has a prominent impact on channel assignment because of the physical constraints of the radios. Jointly addressing the flow-radio assignment and channel assignment problems therefore has the potential to increase WMN capacity by mitigating inter-flow and multi-hop intra-flow interference.

The DFRCA protocol we propose effectively addresses these two problems in a joint manner. As the simulation results show, our DFRCA increases the residual capacities of the receivers and mitigates interference significantly in the contexts of half-duplex as well as full-duplex radio technologies. We evaluate DFRCA performance using different radio and interference models and with solid metrics assessing various aspects of the WMN. Our DFRCA achieves up to eight times improvement in terms of the average traffic-weighted protocol interference with respect to the random configuration scheme and up to $10$ times improvement with respect to the single-channel configuration sceheme. When the average residual capacities of the receivers are considered, our DFRCA achieves over twofold improvement with respect to the random configuration and over eightfold improvement with respect to the single-channel configuration.

The proposed DFRCA can significantly enhance the utilization of the radio resources, such as the available spectrum and radios. Using the novel concept of disjoint subgraphs of radios, the DFRCA effectively decouples flows and operates them as spectrally far as possible from each other. This DFRCA also spatially reuses channels by grouping non-interfering subgraphs in colour classes and assigning channels to these colour classes.