Joint Channel Assignment and Routing in Multiradio Multichannel Wireless Mesh Networks: Design Considerations and Approaches

Abstract

Multiradio wireless mesh network is a promising architecture that improves the network capacity by exploiting multiple radio channels concurrently. Channel assignment and routing are underlying challenges in multiradio architectures since both determine the traffic distribution over links and channels. The interdependency between channel assignments and routing promotes toward the joint solutions for efficient configurations. This paper presents an in-depth review of the joint approaches of channel assignment and routing in multiradio wireless mesh networks. First, the key design issues, modeling, and approaches are identified and discussed. Second, existing algorithms for joint channel assignment and routing are presented and classified based on the channel assignment types. Furthermore, the set of reconfiguration algorithms to adapt the network traffic dynamics is also discussed. Finally, the paper presents some multiradio practical implementations and test-beds and points out the future research directions.

[ProQuest: [...] denotes non US-ASCII text; see PDF]

Omar M. Zakaria 1,2 and Aisha-Hassan A. Hashim 1 and Wan H. Hassan 2 and Othman O. Khalifa 1 and M. Azram 1 and Lalitha B. Jivanadham 2 and Mistura L. Sanni 1 and Mahdi Zareei 2

Academic Editor:Sabrina Gaito

1, Department of Electrical and Computer Engineering, International Islamic University Malaysia, 50728 Kuala Lumpur, Malaysia

2, Malaysia-Japan International Institute of Technology (MJIIT), Department of Electronic Systems Engineering, Universiti Teknologi Malaysia, 54100 Kuala Lumpur, Jalan Semarak, Malaysia

Received 27 November 2015; Accepted 9 May 2016; 20 June 2016

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Wireless Mesh Network (WMN) is a multihop wireless network characterized by low deployment cost that consists of mesh routers and Internet gateways. It is a special ad hoc network with static topologies where unlike the general ad hoc networks mesh routers have no energy limitations. WMN deployments are found in surveillance [1, 2], building automation, remote healthcare delivery [3, 4], and smart grids [5-7]. Mesh routers are the fundamental part of wireless mesh network, which gives routing support for network traffic of mesh clients. Mesh routers can also be equipped with multiple radios to increase the network capacity and to reduce the interference level over the network. The availability and flexibility of IEEE 802.11 components make it a good candidate for wireless mesh deployment. 802.11-based networks provide a cheap and flexible wireless access capability and are easy to deploy in campuses, airports, and hospitals. Backhaul links in 802.11-based WMN can be operated on one of the several nonoverlapping channels (i.e., 12 channels for 802.11a and 3 channels for 802.11b). Furthermore, the cost-effectiveness of network interface cards made it possible to use multiple radios and channels to increase the throughput. Multiple radio configurations allow the utilization of the available multiple orthogonal channels (partially overlapped channel also can be considered as in [8, 9]). The network architecture of multiradio wireless mesh networks (MR-WMNs) is illustrated in Figure 1. Multiradio mesh routers are connected through wireless backhaul links over multiple orthogonal channels. Mesh clients are connected to mesh routers through different set of links referred to as network access links. Mesh clients are user entities with no routing functionality. In the rest of this paper, the term link will refer to backhaul link. The gateway is a mesh router that connects the mesh components with external networks.

Figure 1: The multiradio wireless mesh networks architecture.

[figure omitted; refer to PDF]

Recently, MR-WMN has attracted numerous numbers of research efforts to utilize the advantages that this network is offering. Several proposed approaches on channel assignment (CA) algorithms, multichannel MAC protocols, multichannel routing metrics, links scheduling (LS), multichannel multicast protocols, power and topology control, and network planning exist in the literature. However, the designs that are considering combinations of these issues have shown more efficient performance such as joint routing and link scheduling [10], joint CA and power control [11], joint QoS multicast routing and CA [12], joint gateway selection, transmission slot assignment, routing and power control [13], joint CA, power control and routing [14], joint CA, power control and rate assignment [15], joint routing and topology control with directional antennas [16], and partially overlapped CA [8, 9].

CA algorithms aim to assign channels to the radio interfaces and links with the objective of minimizing the overall contention and interference over the wireless links. CA can either be solved as a separated problem as in [17, 18] or jointly solved with routing as in [19, 20]. Furthermore, it can be developed as centralized solutions [19, 20] and distributed solutions [21, 22]. The availability of the entire network view makes centralized solution more effective than distributed solutions, which only relayed on local information. Typically, CA algorithms must have knowledge on network load in order to assign channels to links. However, some other algorithms do not require any traffic information, as in [23], where the interference is minimized by conserving a k -connected topology.

Joint design approaches in WMNs are surveyed in many works in the literature such as [24-27]. However, none of the works in the literature have comprehensively investigated the Centralized Joint Channel Assignment and Routing (C-JCAR) approaches. This motivates us to undertake an in-depth review of different C-JCAR proposals in the literature. Figure 2 shows the research direction of this paper. The rest of the paper is organized as follows. Section 2 discusses key design issues, models, and approaches for C-JCAR algorithms. Section 3 presents reviewed works under two subsections of C-JCAR approaches and reconfiguration CA/routing algorithms. Section 4 investigates some practical implantations and test-beds for MR-WMNs. Finally, Section 5 describes the future research directions and concludes the paper.

Figure 2: Organization of the paper.

[figure omitted; refer to PDF]

2. Design Issues, Modeling, and Approaches for C-JCAR

This section identifies the key design issues from link and network layers for C-JCAR approaches to address and clarifies interference model and network model to be used in problem formulation and algorithms. It also presents the mathematical formulation of the problem including optimization objectives, constraints, and fairness. Besides, this section also gives the general classifications to C-JCAR algorithms.

2.1. Key Design Issues

2.1.1. Channel Assignment Schemes

Based on the underling hardware, CA can be implemented in one of three schemes. If the implemented technology does not support any link-level synchronization then only Static CA (SCA) can be implemented and channels are assigned to radio interfaces for a long term. However, if synchronous coordination is supported at link layer then SCA can be implemented with link scheduling (LS) and the wireless link can be active on specific time slots only; let us refer to this case by SCA-LS. Dynamic CA (DCA) is the general case where radio interfaces are capable of switching their channel in a small time compared with the time slots. Thus, wireless links can operate on different channels at different time slots. To illustrate the difference between the three CA schemes, Figure 3 shows the possible channel allocation on a wireless link. As it is shown in Figure 3, for SCA links are allowed to be active on one channel only at all times. In SCA-LS links are allowed to be active on one channel only and on specific time slots. However, if DCA is adopted links can operate on different channels on different time slots.

Figure 3: CA types on a wireless link.

[figure omitted; refer to PDF]

2.1.2. Traffic and Routing Issues

As in load-aware algorithms, the aggregated traffic loads over mesh routers are required as an input. This traffic information can either be measured/estimated online as in [28, 29] or assumed based on a historical profile [19]. WMNs can be used to deliver two types of traffic, the Internet traffic and peer-to-peer traffic. Internet traffic is the traffic received or directed to the Internet [20, 30-33]. Either outbound traffic (to the gateway) [20, 30] or inbound traffic (from the gateway) [31] can be considered in finding the network configuration. In [28], specific software such as IPFIX system [34] is used at the gateway to collect the traffic information. The upper and lower bound of the traffic demand are assumed to be available for each mesh router [33]. A traffic profiler at each mesh router collects the traffic information and sends it to a centralized entity [29, 35] where peer-to-peer traffic is assumed. References [36, 37] assume the traffic load is elastic and only information on source-destination communication pairs are considered.

Routing algorithms in wireless ad hoc networks are categorized as proactive (table-driven), reactive (on-demands), and hybrid algorithms. In proactive algorithms such as [38-40], routing table is built individually through exchanging routing information with other nodes in the network. In reactive algorithms such as [41-43], no routing tables are maintained and instead each node triggers the route discovery process whenever it has traffic to deliver to a destination. Hybrid algorithms [44-47] implement the concepts of proactive and reactive routing protocols. Ad hoc routing protocols are extended to be used in WMNs. The routing decisions in these protocols are decentralized process and each node is responsible to make its routing decision. On the other hand, in centralized routing paradigm routing decision is performed at a centralized entity and nodes build their routing/forwarding table based on the updates received from a centralized entity. In WMNs, if traffic is identified per mesh client then mesh routers must maintain a forwarding entry for each mesh client and layer-2 addresses are used to identify each flow. This is similar to 802.11s standard with Hybrid Wireless Mesh Protocol (HWMP) where path selection is based on layer two addressing. However, path selection is usually associated with scalability issues. On the other hand, if the traffic is identified per mesh router and flow is defined as aggregated traffic that originated from one mesh router to another mesh router, then layer-3 routing is used. In most cases, centralized routing approaches follow the latter definition of flow. A TCP-level flow path selection is assumed in [28]. However, this introduces more overheads to the routing layer. Centralized routing proposals built routing tables based on source-destination manner, where both source and destination addresses are required in the routing decision. With centralized routing in MR-WMN, modification is required on the routing table structure and the Address Resolution Protocol (ARP). However, a complicated routing scheme is required for dynamic CA especially if no static binding is applied between radio interfaces and neighbors. For better exploitation of the topology structure of MR-WMN, multipath routing is assumed in most related works to achieve load balancing. However, the out-of-order problem and the configuration complexity are the main drawbacks of multipath scheme.

2.1.3. Topology and Connectivity Issues

Several mechanisms have been used in the literature to control the topology formations in WMNs. This includes power control [48-50], the use of directional antennas [16, 51], and routing [23, 52-54]. Furthermore, in multiradio architecture CA is another factor that determines the physically connected topology. An overview of the topology control mechanisms and issues in MR-WMNs is presented in [55]. In centralized algorithms, the full network topology is assumed to be available at the centralized entity. Topology can be obtained using existing routing protocol such as OLSR [28] or the network management protocol as in [32]. In order to define different possible types of topology formation, let us define logical links as the set of potential links that directly connect mesh routers if proper channels are assigned to their radios, and let us define the physical links as the actual wireless links with a designated channels assigned to it. Since inappropriate mapping can lead to disjoint topology, mapping the logical link onto physical link must be carefully determined. Furthermore, assigning channels to all logical links affects the channel diversity on the network. This is due to node-radio constraint (elaborated more in next subsections), more specifically with a small number of radio interfaces. On the other hand, physical links need to be mapped onto the active links, where active links are the set of links carrying traffic and are determined by routing algorithm. Figure 4 shows two types of physical and logical links mapping. In Figure 4(a), channels are assigned to each logical link as in [19, 29, 37]. In Figure 4(b) channels are assigned to a number of logical links only as in [20, 36, 56, 57]. However, some works allow multiple physical links to exist between adjacent mesh routers [30, 56] which need to be considered in the routing procedure. Meanwhile, connectivity must also be addressed in CA algorithms to prevent isolating parts of mesh routers from receiving the control messages and the configuration updates from the centralized controller. Connectivity is achieved in [19, 29, 37] by assigning a channel to each virtual link or by dedicating a radio on a common channel at each mesh router [58].

Figure 4: Topology formation, logical-to-physical links mapping.

(a) 1-to-1 mapping

[figure omitted; refer to PDF]

(b) 1-to-any mapping

[figure omitted; refer to PDF]

2.2. Interference and Network Modeling

2.2.1. Interference Modeling

Interference plays an important role in wireless networks and has a significant impact on the network performance. MR-WMNs are proposed to reduce the contention on the communication channel and to distribute the transmission over several channels. CA algorithms tend to exploit the channel diversity to reduce the interference levels in the network. Several interference models are proposed in the literature to model the interface in the wireless networks. Three different interference models are presented in this section, namely, the interference-range model, the protocol model of interference, and the physical model of interference. In order to explore these interference models let us assume that all radios in the network have fixed transmission power with omnidirectional antennas and the signal propagation model is based only on frequency and distance. Each radio will have a fixed transmission-range ( _{R T} ) and two radios can form a wireless link if they are within the transmission-range of each other; see Figure 5(a). The receiver radio at each wireless link can correctly receive and decode the transmission in the absence of any interfering radio.

Figure 5: (a) Transmission-range and (b) interference-range model.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

The interference-range model is the simplest model where each radio has its interference range ( _{R I} ) where _{R I} = Δ · _{R T} : Δ > 1 (default Δ = 2 ). A directional transmission on a wireless link is successfully completed if the receiving radio is not within the interference range of another active transmitting radio, as shown in Figure 5(b). Thus, in order to successfully receive the transmitted signal from radio ( v ) to radio ( x ) on wireless link ( v , x ), (1) must be true: [figure omitted; refer to PDF]

On the other hand, interference in protocol model does not assume a fixed interference range. Instead, the interference is determined based on the Euclidean distance between interference radios, transmitting radio, and receiver radio. Thus, a directional transmission on a wireless link can be successfully completed if the distance between the interfering radio and the receiving radio is larger than the link's length. Thus, in order to successfully receive a signal transmitted from radio v to radio x on wireless link ( v , x ) in protocol model (see Figure 6(a)), (2) must be true: [figure omitted; refer to PDF]

Figure 6: Interference based on (a) protocol model and (b) physical model.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

In comparison with the previous two models, the physical model is the most realistic model, where concurrent transmissions from multiple interfering radios are accounted in this model. In order to successfully receive the transmitted signal the SINR (signal-to-interference-and-noise ratio) at the receiving radio must be greater than a predefined threshold. Thus, v radio can successfully receive the transmitted signal from radio x on wireless link ( v , x ) (see Figure 6(b)), if (3) is true: [figure omitted; refer to PDF] where N is the thermal noise power in the frequency channel, _{β v x} is an SINR-threshold which is determined based on the considered modulation and coding schemes, and _{P v} is the received power from v at x . SINR-threshold is chosen in a way that the resulting BER is higher than acceptable BER by the modulating technique. SINR-threshold is based on the experimental observation and can be mapped onto a bit error probability [59]. The physical model of interference is extended in [60] to include the shadowing effect of the RF signals. The work of [60] studied the minimum required number of channels to achieve interference-free channel assignments under realistic interference model called SINR model with shadow.

In the conventional 802.11 MAC protocol with Carrier Sense Multiple Access-Collision Avoidance (CSMA/CA), wireless links are bidirectional since the sender still needs to receive acknowledgement messages from the receiver (if RTS-CTS is enabled, it also receives CTS message). Therefore, all transmissions causes that interfere with the sender or the receiver must be avoided for successful transmission. In this model, sending and receiving nodes on a link are potential source of interference to another link transmission. Figure 7 shows the set interfering radios to wireless link ( v , x ) based on the 802.11 bidirectional model.

Figure 7: Interference based on interference-range model for 802.11.

[figure omitted; refer to PDF]

2.2.2. Network Modeling

Network in MR-WMN architecture can be modeled using either a router-to-router model [20, 56, 57] or a radio-to-radio model [31, 36, 61]. In router-to-router model, the network is modeled as a directed graph G ( V , E ) , where V represents the set of mesh routers in the networks and E is the set of directed links. A directional link exists between two mesh routers if direct communication is possible between them. In radio-to-radio model, vertices represent the radio interfaces. A link exists between two vertices, if radios can communicate directly and are placed in two adjacent mesh routers. Radio-to-radio model is usually used if the radio interfaces are heterogeneous and support different technologies or if different radios operate on different subsets of channels. Figure 8 illustrates the difference between radio-to-radio and router-to-router model for single channel. For multichannel scenarios, each link between two radios must be replicated into the number of available orthogonal channels supported by the mesh router or radio pairs [31].

Figure 8: Router-to-router versus radio-to-radio models.

[figure omitted; refer to PDF]

2.3. Problem Formulation and Approaches for C-JCAR

2.3.1. Optimization Objective Functions and Fairness

The C-JCAR algorithms have been designed in the literature for different optimization objectives and metrics; below is the set of optimization objective functions and metrics:

(i) Maximize aggregated network throughput [29, 31, 33, 36, 62].

(ii) Maximize achievable scaling factor ( λ ) [20, 30, 31, 56, 61].

(iii): Maximize the aggregated utility of flows [37].

(iv) Minimize the maximum interference on all channels [20, 63].

(v) Maximize the minimum unutilized capacity on links [57].

(vi) Maximize the cross-section good-put [19].

(vii): Minimize the path length and link contention [32, 64].

Fairness is also another objective to be considered. Fairness ensures a fair resource allocation among network users or traffic. Several fairness constraints are introduced for C-JCAR. To elaborate the fairness constraints let us assume FL is the set of flows in the network and let _{ω f} , _{∅ f} be the demanded load and the actual achieved load of flow f ∈ F L ; the four types of fairness constraints in the literature are as follows.

(i) Min- λ Fairness . This constraint is to ensure that each flow achieves at least λ of its demands. The Min- λ fairness constraint is presented in [figure omitted; refer to PDF]

(ii) Max-to-Min Fairness . This constraint is to constrain the deference between the highest and the lowest achieved loads. Then, for a given μ the Max-to-Min fairness constraint is given in [figure omitted; refer to PDF] where _{∅ m i n} is the lowest and _{∅ m a x} is the highest load.

(iii) Proportional Fairness . This fairness can be used as an optimization objective function and it is given as in [figure omitted; refer to PDF]

(iv) Bounded Fairness . This fairness configuration bounds each flow with specific upper and lower bound.

Min- λ fairness is considered in [20, 29-31, 56, 61] where flows may have different demands. Other fairness constraints such as Max-to-Min fairness, proportional fairness, and bounded fairness are used in [37, 62] and [33], respectively.

2.3.2. Mathematical Formulation Constraints

The general set of constraints to be considered in the mathematical formulation of the C-JCAR problem can be divided into six sets as follows.

( 1) Flow Routing Conservation Constraints . These constraints ensure that for each traffic flow f from source to destination the net amount of traffic out of each mesh router is equal to the flow rate ( _{f r} ) if the mesh router is the source of the traffic and ( - _{f r} ) if it is the destination and otherwise 0. More constraints can be added to the problem to determine the routing scheme (for multipath or single-path).

( 2) Radio Constraints . These constraints ensure that the number of channels assigned to each incident link on a mesh router (at any given time slot for dynamic CA) does not exceed the number of radio interfaces at that node. This integer-value constraint can be relaxed to linear constraints to ensure that the total load on the links on each node is not higher than the number of radios on that node multiplied by the channel capacity.

( 3) Interference Constraints (or Capacity Constraints/Schedule-Ability Constraints) . These constraints ensure that the amount of data flows on interfered links does not exceed a specific value. This is to constraint the maximum contention level over the collision domains if contention-based MAC is considered or to ensure a feasible interference-free link scheduling if contention-free MAC is used.

( 4) Link Capacity Constraints . These constraints ensure that the traffic load on a wireless link is not exceeding the link capacity. This constraint is implicitly considered under the interference constraints if only sufficient condition for schedule-ability is considered.

( 5) Fairness Constraints . These constraints ensure fairness in allocating resources to different traffic flow demands.

Apart from the above-mentioned constrained, other constraints on the topology can also be introduced. The remaining part of this section will be discussed with regard to the radio and interference constraints. The Notations depicts a set of notations for mathematical formulation employed in the derivation.

If CA and interference-free scheduling is computed for all links in time slotted system, the allocated capacity of a wireless link l can be obtained by [figure omitted; refer to PDF] where _{t l} is number of time slots when l is active, T is the total number of time slots, and _{C l} is the channel capacity at link l . However, in contention-based networks and without supported time slotting, it is not possible to allocate a dedicated bandwidth (capacity) to a link. Instead, virtual link capacity may be estimated for each active link. By considering that the link capacity is equal for all links and all links can utilize the maximum channel capacity ( _{C O} ) with the absence of interference transmission, the virtual capacity for each link l can be calculated as [figure omitted; refer to PDF] In [57] the virtual capacity (effective capacity) of a link is defined as follows: [figure omitted; refer to PDF] The link capacity constraints in [19, 57] are given as follows: [figure omitted; refer to PDF]

To find a virtual link capacity, independent set of edges is considered in [37]; however, this approach is not applicable in multiradio multichannel since radio constraints are not considered in the channel allocation for the independent sets.

Among the interference models mentioned in the previous section, the protocol and interference-range models are binary pairwise models, where the interference between any two links either exists or does not exist. The interference constraints with necessary condition for interference-free scheduling can be presented as [figure omitted; refer to PDF] where θ is the interference constant that depends only on the interference model. For instance, θ in the interference-range model is a function of the ratio between the transmission and interference range ( _{R T} / _{R I} ), where it represents the maximum number of links interfering with a specific link but not a pairwise interfere. Interference constraints can also be considered for sufficient condition only, as follows: [figure omitted; refer to PDF]

Thus, for any solution that satisfies the sufficient condition, there is a feasible link scheduling (proof is stated in [20]). The interference constraint with sufficient condition is used in [30, 33, 36, 56, 57, 62]. Figure 9 demonstrates that it is possible to have feasible interference-free links scheduling even though only necessary conditions are satisfied. Let us assume that the channel capacity is equal to 1 and the number that associated with each link represents the amount of traffic load carried on each link.

Figure 9: Example of links scheduling (sufficient condition is not satisfied).

[figure omitted; refer to PDF]

From Figure 9, the link flows do not satisfy the sufficient condition of link scheduling (larger than 1). However, a feasible scheduling exists as obtained in Figure 9. It can be concluded from the previous example that solutions based sufficient conditions will have an optimality gap. Using the notation (see Notations), interference and radio constraints with different CA schemes are presented in Table 1.

Table 1: Mathematical formulation (interference & radio constraints).

Operating mode	Network model	Interference (capacity) constraints	Node-radio constraints
SCA	Router-to-router model general	LP: Necessary condition ∑ l [variant prime] ∈ { I ( l ) ∪ l } g ( l [variant prime] ) C l [variant prime] <= θ , ∀ l ∈ L Sufficient condition ∑ l [variant prime] ∈ I ( l ) g ( l [variant prime] ) C l [variant prime] <= 1 , ∀ l ∈ L	IP: ∑ i ∈ C h m i <= K ( u ) , ∀ u ∈ N LP: ∑ l : h ( l ) = m o r t ( l ) = m g ( l ) C l <= K ( u ) , ∀ u ∈ N
Router-to-router model [37]	LP: Link virtual capacity (effective capacity) ∑ l [variant prime] ∈ { I ( l ) ∪ l } V C ( l [variant prime] ) <= C l , ∀ l ∈ L & g ( l ) > 0 g ( l ) V C ( l ) <= 1 , ∀ l ∈ L
DCA/SCA-LS	Router-to-router model general	IP: Necessary & sufficient condition y t ( l ) + y t ( l [variant prime] ) <= 1 , ∀ l ∈ L & l [variant prime] ∈ I ( l ) Sufficient condition ∑ l [variant prime] ∈ ( I ( l ) ∪ l ) y t ( l [variant prime] ) <= 1 , ∀ l ∈ L , t ∈ T Or LP: relaxation Necessary condition ∑ l [variant prime] ∈ { I ( l ) ∪ l } g ( l [variant prime] ) C l [variant prime] <= θ , ∀ l ∈ L Sufficient condition ∑ l [variant prime] ∈ I ( l ) g ( l [variant prime] ) C l [variant prime] <= 1 , ∀ l ∈ L	IP: ∑ l ∈ L : t ( l ) = u o r h ( l ) = u y t ( l ) <= K ( u ) , ∀ u ∈ N LP: ∑ l ∈ L : t ( l ) = u o r h ( l ) = u g ( l ) C l <= K ( u ) , ∀ u ∈ N
Router-to-router model [56]	IP: Necessary & sufficient condition If n , m interfere with each other ∑ l [variant prime] ∈ ( E ( n ) ∪ E ( m ) ) y t ( l [variant prime] ) <= 1 , ∀ n , m ∈ N ; t ∈ T LP: Sufficient condition ∑ l [variant prime] ∈ I ( l ) g ( l [variant prime] ) C l [variant prime] <= 1 , ∀ l ∈ L
Radio-to-radio model [31]	IP: Necessary & sufficient condition y t ( l ~ ) + y t ( l ~ [variant prime] ) <= 1 , ∀ l ~ [variant prime] ∈ I ( l ~ ) LP: Sufficient condition ∑ l ~ [variant prime] ∈ I ( l ~ ) g ( l ~ [variant prime] ) C l ~ [variant prime] <= 1 , ∀ l ~ ∈ L ~	IP: ∑ l ~ ∈ L : t ( l ~ ) = u o r h ( l ~ ) = u y t ( l ~ ) <= K ( u ) , ∀ u ∈ N LP: ∑ l ~ ∈ L ~ : t ( l ~ ) = r o r h ( l ~ ) = r g ( l ~ ) C l ~ <= 1 , ∀ r ∈ R
Radio-to-radio model [36]	LP: Sufficient condition (both interference and radio constraints are considered) ∑ l ~ [variant prime] ∈ ( I R ( l ~ ) ∪ l ~ ) g ( l ~ [variant prime] ) C l ~ [variant prime] <= 1 , ∀ l ~ ∈ L ~
Radio-to-radio model [61]	Each critical maximum independent set (MIS) is a set of links which satisfy interference and radio constraints and only one critical independent set is allowed to be active at any time slot. Therefore, interference and radio constraints are implicitly considered in the LP formulation

Another way to model the interference on wireless mesh network is by using empirical interference measurement. This can be done by taking the advantage of the static nature of WMN, where the required information can be easily measured and recorded beforehand. Empirical interference measurement is presented in [37]. The packet error rate (PER) of a wireless link at a receiver is empirically determined when another link is active. Based on this measurement, the objective of the CA algorithm is to minimize the summation of the PER of one link when another link is actively multiplied with the load on each link. The objective function in [37] is as follows: [figure omitted; refer to PDF] where P E R ( _{l 1} |" _{l 2} ) is the PER at receiver node of link _{l 1} when _{l 2} is active.

To present the interference constraints using the physical model of interference two approaches can be used as presented in [62]. The first approach proposed in [65] is based on length classes that distributed links to different sets based on their lengths. For each length set ( j ), the area is divided into a set of square grid cells _{A j} . Let A ∈ _{A j} , Δ ( A ) be the set of links from j with their receiver lying inside A and operate on the same channel. The interference constraints are then presented as [figure omitted; refer to PDF] where [straight phi] is a constant number and x ( l ) is 1 if the link is active and 0 if otherwise.

The second model is weight-based model, where ^{W _{l 1 l 2}} is the receiving power at _{l 2} receiver when both links are active on the same channel; thus, [figure omitted; refer to PDF] where _{P x} ( y ) is the transmission power received at x when y is transmitting the signal. The interference constraint can be presented as [figure omitted; refer to PDF] where N ( x ) is the normalized value of x and [vartheta] ( l ) is a constant based on the receiving power at the receiver when l is active.

2.3.3. Approaches for C-JCAR

The general formulation of the C-JCAR problem can be presented as Integer Linear Programming (ILP) problem. However, the CA problem which is part of C-JCAR problem is an NP-hard [19], where, with given link loads, finding the CA for a set of radio interfaces such that the link loads are schedulable is NP-hard problem. Moreover, interference-free link scheduling problem for a given link flows is also NP-hard [66]. Therefore, the problem is then transformed into a linear programming problem by relaxing some constraints [20, 31, 36, 56, 62]. The problem can then be considered as multichannel multicommodity flow problem with constraints on radios, interference, and link capacities. The optimal solutions are obtained for feasible problems only [33, 57] or with some fairness considerations [20, 56]. Due to the NP-hardness of the problem, standard methods and solvers are not able to solve the problem for real-life network sizes. A set of heuristic algorithms [19, 29, 37, 58] and metaheuristic algorithms [33, 57] are proposed in the literature [20, 31, 56]. Furthermore, approaches can also be classified based on their execution time into online [29, 37] and offline for planning stage [33]. Figure 10 shows the set of design consideration, classification, and methods in designing a load-aware C-JCAR proposal.

Figure 10: C-JCAR: key design issues and approaches.

[figure omitted; refer to PDF]

3. Related Works

In this section, related works for CA and routing are presented in two subsections. The related works in the literature to solve C-JCAR are presented in the first subsection. The works are classified based on their CA scheme (SCA, SCA-LS, and DCA) into three categories. This is followed by a comprehensive summary table (Table 2) that compares all approaches based on the design issues presented in previous part of the paper and highlights their assumptions and limitations. The second subsection presents the set of CA or routing proposal, which deals with the reconfiguration problem (state-aware proposals). These works consider the current network configuration in finding the next one to reduce the overhead associated with the reconfiguration process. The works are divided into channel reassignment proposals, traffic rerouting proposals, and the reconfiguration policy. The latter one discusses some policies that determine when to trigger the reconfiguration process. This subsection followed by a summary table (Table 3) discusses state-aware works and highlights the approaches and the limitation of each work.

Table 2: C-JCAR proposals summary.

Work	Link layer and channel assignment	Traffic & routing	Topology	Objective & fairness	Notes/limitations
CA type:	Interference:	Technology:	Traffic type:	Traffic load:	Routing scheme:	Mapping:(1-to- x ): x	Connectivity:	Objective:	Fairness:
[19]	SCA	B-IRM	802.11	P2P	Yes	SP, MP	1	Yes	Maximize cross-section good-put	No	Optimality is not guaranteed. No accurate link capacity estimation in a heavy traffic load. Less channel diversity due to link mapping
[56]	DCA, SCA-LS	B-IRM	-	P2P	Yes	MP	0,1	Yes	Maximize λ (scaling factor)	Min-λ	Out-of-order problem and configuration complexity on routing. Switching overhead issues
[20]	SCA-LS	B-IRM	-	Internet	Yes	MP	Any	For MRs w/traffic	Maximize λ (scaling factor)	Min-λ	Radio constraints are not considered in the LP. Out-of-order problem due to multipath routing
[36]	DCA	B-IRM	-	P2P	src-des MRs	MP	Any	No	Maximize aggregated throughput	No	Out-of-order problem and configuration complexity on routing. Switching overhead issues. Optimality issue since only sufficient conditions are considered
[57]	SCA	B-IRM	802.11	P2P, Internet	Yes	SP	Any	For MRs w/traffic	Maximize min spare link capacity	Min-λ on link utilization	Using sufficient condition in MILP may not lead to global optimal solution. Single channel initial topology may lead to infeasible solution in heavy traffic load scenarios
[30]	SCA-LS	THM		Internet	Yes	MP, predefined	0,1	For MRs w/traffic	Maximize λ (scaling factor)	Min-λ	Considering only necessary condition may lead to infeasible solution. Out-of-order problem due to multipath routing
[70]	SCA	PHM (w/o accumulation)	802.11	Internet	No	MP (M-GW) L2.5 forwarding	≥1	Yes	Minimize max link utilization	No	Radio or interference constraints are not accounted in initial traffic load estimation. Assume same traffic demands in all mesh routers. Out-of-order problem due to multipath routing. Link rate assignment is considered
[31]	DCA	PRM, IRM		Internet	Yes	MP (M-GW)	Any	For MRs w/traffic	Maximize aggregated throughput	Min-λ	Out-of-order problem and configuration complexity on routing. Each radio can be operated on a subset of channels. Combination of multiple channels to single channel is possible
[32]	SCA	THM		Internet	Yes	SP	Any	Yes	Metric on hop count & interference	No	Solving subproblem with local constraints does not guarantee global optimality. Information on received power at a node when another node is transmitting is assumed available
[62]	DCA	IRM, PRM, PHM		P2P	No	SP, MP	Any	No	Maximize aggregated throughput	Max-to-Min	Equal load demand is assumed at mess routers. In single-path routing optimality is not guaranteed since mathematical formulation is for multipath
[61]	DCA	B-IRM		P2P	Yes	MP	Any	No	Maximize λ (scaling factor)	Min-λ	The quality of the solution is highly dependent on the performance of critical MIS finding algorithm
[33]	SCA	B-IRM	802.11	Internet	Lower & upper bound	MP (MGW)	Any	For MRs w/traffic	Maximize aggregated throughput	Bounded fairness	Developed for planning stage with different resources constraints. Not practical for large networks since fitness function involves solving entire network LP
[29]	SCA-LS	THM		P2P	Yes	MP (predefined)	1	Yes	Maximize aggr. achieved demands	No	Link loads used to the CA are estimated without considering radio or interference constraints. Less channel diversity due to link mapping
[37]	SCA	EM		Internet	Number of active flows	MP (SP per follow)	1	Yes	Minimize contention (CA)	No	Link loads estimated without considering radio or interference constraints. Not clearly stated where and how to implement flow rate control
[63]	SCA	B-IRM	802.11	Internet	Yes, sequence of traffic	MP	Any	For MRs w/traffic	Minimize the maximum congestion (of worst case)	No	Number of facets increase exponentially in large-scale networks; this increases the number of constraints in LP problem; however, relaxing the convex hull to box ranges affects the efficiency

Note . SCA: static channel assignment, DCA: dynamic channel assignment, LS: link scheduling, IM: interference model, IRM: interference-range model, PRM: protocol model, PHM: physical model, B-: bidirectional, THM: two-hop model, EM: empirical measurement, P2P: peer-to-peer, SP: single-path, MP: multipath, MGW: multigateway, MR: mesh router, and LL: link layer.

Table 3: State-aware channel assignment/routing proposals summary.

Work	[...]State aware	Approach	Notes/limitations
Channel reassignment	Flow rerouting
[35]	Cost is based on channel-link reassignment	Not applicable since a fully connected topology and fixed predefined paths are considered	(i) Reorder channel in the new CA to reduce the cost during migration from existing cluster to the new cluster	(i) Out-of-order problem(ii) Assigning channels to all logical links affects the channel diversity(iii) Performance degradation if the traffic load sequences are highly uncorrelated
[85]	Cost is based on channel-link reassignment	Not applicable since a fully connected topology is considered	(i) Previous channels are reassigned to links if they are among the set of channels which best reduce the interference and do not violate radio constrains	(i) Internet traffic information is collected at the gateway(ii) Performance degrades with small number of radios due to ripple effect on channel reassignment(iii) Assigning channels to all logical links affects channel diversity
[29]	Cost is based on channel-link reassignment	Not applicable since a fully connected topology and predefined paths are considered	(i) Effective data for each channel is computed and channel with the highest effective capacity is selected. If the channel is not previously assigned to that link reconfiguration cost is subtracted from the effective data value	(i) Out-of-order problem due to multipath(ii) Assigning channels to all logical links affects channel diversity(iii) The channel assigned to a link will be considered as final assignment; thus, earlier assignments are not aware of later assignments; this may lead to an improper final channel assignment(iv) Due to radio constraint some links will be forced to assign more congested channels and this will result in inefficient channel assignment
[84]	Cost is based on channel-node reassignment	Not addressed	(i) Starts from the existing CA and finds new CA by making some adjustment on the previous one(ii) Number of radio-channel reassignments is constrained to a predefined number	(i) Performance degrades with small number of radios due to ripple effect on channel reassignment(ii) Transmission rate is jointly solved with CA links to optimize the network performance
[37]	Cost is based on channel-link reassignment	Not addressed	(i) Starting from existing channel assignment, a new channel is assigned to a link if it does not violate the radio constraints and reduces the interference(ii) Number of link-channel reassignments is constrained to a predefined number	(i) Performance degrades with small number of radio interfaces and due to that reassignment is restricted to channels that do not violet the radio constraints(ii) Assigning channels to all logical links affects channel diversity(iii) Flow-level routing introduces overhead to the routing procedure and requires a routing entry of each flow in routing tables. This is impractical for high number of flows
[58]	Not addressed	Considered, where rerouting cost is based on the number of flows having different routing path	(i) Heuristic routing based on Dijkstra algorithm(ii) The number of flows which allowed having new routes is constrained to a predefined value	(i) Flow rerouting cost is not accurately defined. For instance, two new flow path assignments may result in different disruption while both are considered equally in rerouting cost

3.1. C-JCAR Proposals

3.1.1. C-JCAR Based on SCA

In [19] a heuristic algorithm is developed to solve the C-JCAR problem. Given the traffic load information for set of source-destination pairs of nodes, the algorithm finds the routing paths for each flow and assigns channels to virtual links. Multipath and single-path routing schemes are considered. The optimization objective in this work is to maximize the cross-section good-put which is determined by matching the expected load on links with virtual capacity. The virtual capacity of a link is estimated based on the total load of the interfering links. The algorithm iterates over CA and routing steps to improve the overall cross-section good-put. The algorithm retains the network configuration and tries to improve the configuration by rerouting nonconforming flows. When the allocated virtual bandwidth meets the flow demands for each flow or when the maximum number of iterations is reached, the algorithm is terminated.

C-JCAR problem in 802.11-based wireless mesh network is formulated as Mixed-Integer Linear Programming (MILP) in [57]. In this work, the virtual capacities are assigned to logical links. The MILP minimizes the maximum contention on the channel assigned to each link by maximizing the minimum difference between the effective capacity and the traffic load on each link. This leads to the reduction in overall regions interference across the network. For small-scale network, MILP can be solved using commercial software such as CPLEX [67]. However, this is not feasible for large-scale networks. Therefore, metaheuristic algorithm based on Iterated Local Search (ILS) is proposed to solve the MILP problem. This algorithm commences with logical topology consisting of single channel assigned to all logical links. Then, MILP is solved iteratively using relaxed binary routing variable to simplify computation of the cost. In each iteration, a set of variables is considered as a constant, which takes their values from previous iteration till one link is selected randomly based on worse case congestion ranking. The next phase involves finding based on the maximum relaxed routing variable values. However, the algorithm in [57] starts the solution from a single channel assumption with limited network capacity and this can result in an infeasible solution if heavy traffic load is applied. Therefore, in [68] Tabu search with iterated local search algorithm is proposed to overcome the above-mentioned problem in [57]. The Tabu-search based algorithm selects the solution with minimum number of conflicting links in each iteration and the remaining procedure in the algorithm is similar to [57]. Furthermore, [69] has extended the work of [57] to support directional antenna to reduce the interference in the topology.

The CA is jointly solved with link transmission rate assignment in [70]. A centralized greedy heuristic is designed to assign channels to given schedulable flow rates. The heuristics algorithm starts off with throughput optimization for a precomputed flow rate. The initial traffic rate on links is computed by assuming interference-free links with objective to maximum achievable aggregated throughput on the network and then solves the CA and rate assignment problems. To ensure network connectivity, a designated channel is assigned to a link between every node pair. Then, the links are stored in the queue and extracted one at a time in decreasing order of priority. Channels are assigned to links to minimize the maximum utilization. This involves first assigning the highest available transmission rate to links. However, decreasing the transmission rates on some links may help in improving the network performance. This is because reducing the interference on the network consequently reduces the size of the link's collision domain. This is since increasing the transmission rate on a link leads to a higher SINR-threshold at the receiver, as compared with greater difficulty in decoding of the received signals. This also results in more links interference with the transmission on this link and an increase with collision domain size. The flow rates obtained from precomputed flow are then scaled down to satisfy the sufficient condition of schedule ability, based on the computed CA. A layer-2.5 forwarding scheme is proposed in [70] to forward the Internet traffic to and from gateway nodes. The forwarding scheme does not maintain routing table. Instead, it assigns static flow rate to its links that forms the basis of forwarding criteria and updating of the link cost information locally. Additionally, each mesh router must know the hop vector to all its neighbors where a hop vector contains the minimum hop count to other mesh routers. The source mesh router inserts the maximum allowable hop count to each packet. The forwarding decision is determined based on the utilization of the links and the remaining allowable hop count to reach its destination.

In [32], the C-JCAR problem is decomposed into subproblems wherein the number of subproblems is equal to the number of mesh routers. The subproblem at each node is formulated as an ILP with local constraints and similar to objective function of [57]. The nodes are grouped into subsets defined as network crew that is visited based on some ranking function. For a given network crew and ranking function the nodes at each subset are visited one by one to sequentially solve the subproblem, while the channels and paths assigned in the visited nodes are considered as constants in the next subproblems. Branch-and-cut method is used to solve each subproblem. Then connectivity is tested and ensured using a postprocessing phase, which also checks for unused radio interfaces. A new metric based on contention on links, routes length, and interference is used to select the best solution over all network crew and ranking.

Genetic algorithm is used to model the C-JCAR problem in the network planning stage [33]. For a given CA, a linear program model of multichannel routing with an objective of maximizing network capacity and total traffic from/to the Internet is adopted as fitness function. For different hardware resources constraints, three types of optimization problems are formulated in [33]. In the first case, the algorithm optimizes the network by assigning channels to radios while assuming the number of radios at each node is constrained. The second case optimizes the network by assuming that the number of radios can be distributed into mesh router, where only the total number of radios in the network is constrained, while the third formulation further optimizes the network considering the gateway placement problem involving selection of mesh routers to serve as gateways. In the first case, channel assigned to each radio is presented as integer encoding with value equal to the channel assigned to it. In the second and third formulations, binary encoding is used for representing CA. Each mesh router is represented by bit string with a length equal to the total number of channels, with each bit representing the assignment of channel to one of the mesh router's radios. Then, the algorithm starts with generation of an initial population. The selection, crossover, and mutation operation are performed at each evolution cycle. A roulette wheel procedure is used for the selection operation in all formulations.

In [37], routing, channel reassignment, and TCP flows rate allocation are studied for optimization of dynamic flows in MR-WMN. Channel reassignment is recomputed for every change in the network traffic state. The channel reassignment algorithm is used to limit the number of links, which requires reassignment. The routing model allows multiple flows between pair nodes, while packets in a TCP flow follow single path. This problem is formulated as Mixed-Integer Nonlinear Program (MINLP). The objective is to maximize the proportional fairness. Heuristic algorithms are proposed to solve the C-JCAR problem. The proposal starts with finding the flow routes based on greedy heuristics. The algorithm then selects routes iteratively based on maximum path utilization fitness. Interference-free links are assumed in the routing stage and neither radio nor interference constraint is considered. A greedy CA routine is then carried out based on current CA. Finally, flow rate allocation is performed based on consideration of the routes and CA obtained from previous steps. Their later work of [71] further improves their earlier proposal by integrating the link transmission rate allocation with the solution and by determining the active links to control the network topology.

In [63] a concept of oblivious routing is used in solving the C-JCAR with scenarios when traffic is highly dynamic. The oblivious routing optimization aims at finding route configuration that optimizes the worst case network performance over a set of possible traffic demands. Based on historical traffic demands profile with a periodic variation during the day's hours, the solution starts by dividing the time intervals into time slots with each configuration bearing separate time intervals. The partitioning is conducted to optimize the network performance by characterizing the traffic demands at each time slot as a convex region with number of dimensions equal to the number of mesh routers. Initially, the traffic demand is scaled such that the total traffic load from all mesh routers at any time is constant. A local search heuristic algorithm called Hill climbing algorithm is used to partition the traffic profile into a predefined number of slots with the objective of minimizing the convex hull volume over all partitions. For a given time slot, a traffic demand is constructed as multidimensional convex hull with a number of facets. In case of a large number of mesh routers, the number of facets increases exponentially. Thus, relaxation of such convex hull to box range is constructed for such convex region. Then, robust routing is computed for each time slot. The problem is mathematically formulated as nonlinear problem with the objective of minimizing the maximum congestion over all interference sets on all channels. The problem comprises four sets of constraints, namely, interference, radio, flow conservation, and facet constraints. The formulation is transformed to LP problem by finding the dual formulation of the slave LP problem of the original problem. The flow-link-channel variable is determined by solving the routing problem using LP solver. The same channel is later assigned to all links. Then, the algorithm iteratively selects the most utilized link and assigns the channel obtained from flow-link-channel variable to that flow provided that such assignment will not disconnect the flow. Then, the simulated annealing algorithm is used to improve the solution.

Some other works in the literature tackle the C-JCAR problem based on SCA configuration. A heuristic approach is proposed for C-JCAR for cognitive-radio-based WMN using TV white space in [72]. The C-JCAR is addressed with power control in Liu et al. [73], while [74, 75] solve the C-JCAR problem for multicast traffic using genetic algorithm and genetic algorithm with simulated annealing, respectively.

3.1.2. C-JCAR Based on SCA-LS

In [20], the problem is formulated as an MILP and relaxed to LP with objective to maximize the achievable scaling factor of demands. The obtained routes from solving the LP are serving as input to the CA step. The CA algorithm is performed with the objective of minimizing interference over all channels. The obtained channel-link assignment ends with some infeasible links due to the radio constraints and a postprocessing step is carried out to redistribute the traffic load to links with feasible CA only. Thus, for each logical link, the total traffic load that passed through all channels over that link is redistributed over the common channels between the links mesh routers pairs only. The objective of solving the LP formulation is to minimize the maximum interference by redistributing traffic to the links. Then, the scaling down of traffic demand is performed. This ensures feasible link scheduling for realizing sufficient condition. Eventually, a link scheduling algorithm is also obtained.

Similar to [20], in [30] the original MILP problem is relaxed to LP with a set of four constraints. The optimization objective maximizes the fraction of traffic load demands that can be routed for each node. The LP is solved to obtain link-traffic-load assignments. Then, CA is performed to assign channels to links while the LP is solved again but with addition of constraints to force the links to assign the same channels obtained from the previous CA steps. This is accomplished by giving more weight (cost) to the assignment of different channel to a link than the one that has been previously assigned. Finally the link scheduling is performed.

In [29], CA and link scheduling are formulated as MILP problem with the objective of maximizing throughput in CA and link scheduling. The link load is first estimated by distributing the new load of each flow on all available predefined paths based on hop count without considering any interference or radio constraints. A heuristic algorithm is proposed for handling the CA problem. Channel reassignment cost is considered in this stage by minimizing the amount of current traffic affected by channel reassignment. Then a greedy heuristic algorithm schedules the link to time slots for meeting the expected load on each link. Thus, flow allocation is computed for determining the amount of traffic to be routed on each path with the objective of maximizing the amount of traffic routed for each flow.

3.1.3. C-JCAR Based on DCA

C-JCAR are formulated as an MILP for different objective functions in [56]. The problem is then relaxed to a LP problem. A prime-dual algorithm based on shortest path routing is used to solve the LP problem by finding the loads on links for the scaled down demands. The link loads are then used as an input to the CA stage. The CA algorithm is developed for two scenarios, the SCA-LS and DCA. In SCA, a greedy algorithm finds link-channel assignment followed by a greedy coloring algorithm for finding a conflict-free scheduling. In the case of DCA, packing based heuristic algorithm is used to find both CA and scheduling simultaneously.

A C-JCAR problem with a given set of elastic flow is formulated as LP problem in [36]. The objective is to maximize the throughput using radio-to-radio model. In this way, radio and interference constraints are replaced with a feasibility of the time fraction vector. The time fraction vector represents a vector of time fraction of all links and the fraction for each link must be large enough to meet the traffic load requirement on that link. The LP problem is solved to obtain the CA and routing. Then, vertex-coloring algorithm is used to obtain a feasible scheduling. More efficient coloring algorithm leads to better throughput by lifting the resulted flows from solving the LP problem.

DCA, multipath routing, and link-channel scheduling are jointly formulated as MILP in [31]. The objective is to maximize the network fairness or throughput. The work assumes that radios can operate on subset of channels. Furthermore, the possibility of combining several consecutive channels into one channel is explored so that network interface card can use the channel with larger range of frequencies. Four different interference models are considered in this work. The sufficient and necessary interference constraints for loads on interfering links to be scheduled for each interference model are obtained. This is by deriving the interference constant (which replaces θ ) for each interference model. Then, mixed IP is relaxed to a linear programming by using the sufficient condition of the interference constraint. A greedy link scheduling algorithm is developed to find a feasible link scheduling, given the flow found by the LP. The algorithm is proved within a constant factor of the optimum solution when it optimizes the fairness or the throughput. A parametric search is applied to improve the overall achieved flows. Instead of using the sufficient condition with the interference constant equal to one, the algorithm in the first instance uses the maximum possible value for the interference constant in the LP. If no feasible solution is obtained after solving the LP problem and applying the scheduling algorithm, then the interference constant is reduced by one. This is repeated until feasible solution is obtained.

In [62], joint DCA and routing are considered for multipath and single-path routing under two interference models. The first model is the pairwise model, where the interference among the wireless links can be modeled as conflict graph. This can be represented by different models such as the interference-range and the protocol models. Meanwhile, the second model is the physical model. The joint problem is formulated as LP and considered as multichannel multicommodity flow problem. The problem considers multipath routing with the objective of maximizing the total throughput of a given set of source-destination pairs, with some fairness constraints. The LP is solved to obtain the traffic load on each link. The resulting flow rates are scaled down with specific factor to obtain a feasible link scheduling. The algorithm provides a constant-approximation solution. A greedy placement approach is then used to construct link scheduling for the scaled down links. The first algorithm uses multipath routing, while single-path routing presents a modified algorithm. The LP problem is first solved to obtain load for each flow routed through multipath that is forced to follow single path that is randomly chosen for each flow. Then, for each flow path, striping is performed using the procedure presented in [76].

A joint scheduling, CA and routing, is formulated as LP multicommodity flow problem in [61], augmented with maximal independent set (MIS) constraints. First, the MR-WMN resources are constructed as multidimensional conflict graph (MDCG). Each vertex in MDCG is a radio-link-channel tuple (RLC-tuple). The problem is transformed to the problem of finding all MIS in conflict graph. This is because in general, some MIS sets have more probability to be selected in the optimal solution. These are critical MIS sets; however, finding all MIS in a graph is NP-complete problem [77]. Therefore, a heuristic algorithm based on scheduling index ordering is developed to identify the critical MIS sets. The scheduling index metric is associated with each link that is based on the network topology and network flow information. The algorithm first finds all possible shortest paths between the source-destination pairs of each flow. Then the SI for each tuple is determined based on the number of shortest paths passing through it and its interfering neighbors. The link is then ordered based on its SI. An iterative algorithm is performed starting with tuples with higher SI first. It is terminated if specific condition is reached. Thus, tuples for links associated with lower SI value will have lower possibility to be selected. The resulting maximum independent sets are used in the link capacity constraint for the multicommodity flow linear problem. The solution to the linear problem is determined by the fraction of time where each MIS will be active. Therefore, only single MIS can be active at a time. Table 2 shows a summary of the C-JCAR proposals.

3.2. Channel/Routing Reconfiguration Proposals

DCA algorithms assume that channel switching is supported with negligible delay overhead [36]. A per-packet switching with neglected overhead is assumed in [78]. However, with current hardware channel switching delay is still considerable [79]. In [80] a hybrid CA is developed and the channel switching cost is obtained by dividing the switching delay of an interface over the number of packets transmitted before the interfaces switch their channel. According to [81], the delay involved in channel switching is approximately 80 microseconds. According to [82] the switching delay in 802.11a is around 328 microseconds which is equal to the time of transmission of 1024 bytes in a rate of 25 Mbps using the same technology. Furthermore, research [83] shows that this latency can rise up to scale of seconds due to the effect of upper layer protocols. Reference [3] presented an experimental study on the interruption associated with channel switching, which is in order of 10 seconds with the use of OLSR protocol. This is due to fast link failure update in channel switching. Thus, the authors have recommended a modification to the existing routing protocol that can reduce the overhead associated with channel switching. This can be concluded as, even in a centralized routing paradigm that involves no link status update, the channel switching overhead due to synchronization issues will still be induced. This is due to the inability of radios on a link to achieve perfectly the same switching time. This will cause the link to be down for specific period of time. In addition to channel switching, traffic rerouting can also disrupt the real-time traffic, thereby causing packet drop. The small overhead and delays caused by channel reassignment or traffic rerouting may be unacceptable for the most of real-time multimedia applications. Therefore, state-aware proposals are proposed to fill this gap. There are several existing works, which deal with channel reassignment or traffic rerouting problems. The aim of these works is to reduce the reconfiguration overhead associated with channel reassignment procedures. These works are categorized as state-aware proposals.

3.2.1. Channel Reassignment Proposals

Reference [79] addresses the problem of recomputing CA after every variation in the traffic pattern. The work proposes heuristic reassignment algorithm that aims to minimize the maximum utilization in the collision domain for a given limited number of channels. The input to the algorithm is the network topology and current CA and link-flow rates serve as input to the heuristic algorithm. The collision domain of a link is defined as a set of links, which interfere with this link. The total utilization of a collision domain is defined as the summation of the flow rate over all links in that collision domain. The algorithm begins with a previous CA to find the new one. The link with the highest total utilization is selected iteratively, while the channel that reduces the total utilization over the effected collision domains is then selected. The radio constraints may lead to inappropriate assignments on some links due to the ripple effect and this can increase the utilization on the affected links. The number of channel reassignments is bounded by a predefined parameter. The work is further extended in [84] to integrate the transmission rate control. This is by starting with the highest possible transmission rate to links and then decreases iteratively till reaching the optimal configuration.

Work in [85] tackles channel reassignment problem assuming the network traffic as elastic TCP flows. This algorithm does not account for traffic loads of each flow; instead it accounts for the number of active TCP flows. This is since TCP flows tend to utilize the entire available bandwidth and is not restricted to a specific demand. Any fluctuations in the traffic may necessitate a consequent channel reassignment to account for the changes, where a simple greedy algorithm handles this problem. In finding channel for a link, the previous channel on a link is reassigned if it does not violate the radio constraints and produces the minimum interference level on that link. The algorithm traverses each edge once, except for cases when merge operation is required, and it assigns channel to it. A common minimum interference channel is assigned to a link; however, if no common channel is available, then merge operation is invoked to create and assign the common channel required. This requires violating the constraints at the radio interfaces. Such cases evolve in situations where the number of channels is higher than the number of radios on the node.

Similar to [79], the channel reassignment problem is also considered in [37] also, where the number of links that is allowed to reassign their channels is constrained. The CA algorithm assigns a channel, which reduces the interference in the iteration. To do so, the algorithm selects a channel from the set of channels which reduces the interference level and do not violate the radio constraints. If the candidate channel set is empty, then previously assigned channel is reassigned again. If the old channel is among the candidate channels, then it is reassigned again; otherwise one of the candidate channels is assigned and the reassignment counter is incremented by one. The algorithm terminates when the total number of reassignments is reached. Meanwhile, connectivity is maintained by assigning a channel for each logical link. The routing on TCP flow level adds extra overhead, which usually requires complex implementation. In their technical report [28], the routing is inserted in each packet. Thus, packets in each flow carry its route information to/from the gateway, while intermediate mesh routers forward each packet based on the included routing information. However, inserting the full route on each packet excessively increases the overhead.

A state-aware channel reassignment is proposed in [35]. Upon receiving new traffic matrix, the algorithm performs a state-aware migration to minimize the reconfiguration costs. This problem is a well-known assignment problem and it is modeled as maximum weighted bipartite matching problem while the matching is determined for less reassignment traffic disruption.

Another state-aware algorithm is introduced in [29]. In this work, the CA stage calculates the expected load on each interference region by using the expected load on each link, which is then used to sort the links. For each visited link, the expected throughput is calculated for the channel and the channel with higher expected throughput is assigned. The channel switching overhead is introduced in the expected throughput function if the evaluated channel is different than the current channel on a link. At any iteration, unassigned links incident on saturated nodes are forced to assign the last used channels that affects the channel spatial diversity.

The channel switching problem in cognitive network has been studied in [86]. As in cognitive radio networks, secondary users can operate in different licensed bands and primary users' activities may frequently force secondary users to switch their radios to other unoccupied frequency bands, which are unnecessarily continuous. The channel switching problem is formulated as MILP with the objective to reduce the frequency distance between the current and the successive channels. A heuristic approach is proposed to solve it. However, the nature of the problem is different than the channel switching problem in the traditional MR-WMN.

3.2.2. Traffic Rerouting

The traffic demand dynamics can trigger the reconfiguration of the network. In this process, some flows might need to be rerouted. This disrupts the traffic flows and results in higher packet drop where flying packets cannot find their routes to destinations. Therefore, rerouting cost should be considered in the algorithm designed for environments with high dynamic traffic variation. Many works avoided this problem by assuming the existence of multipaths between senders and receivers, so that the algorithm maintains same paths after reconfiguration [29, 35]. Other works such as in [28] take the advantage of existing links between adjacent mesh routers to use the source routing scheme where full path to the destination is inserted in each packet to overcome rerouting problem.

A heuristic algorithm is proposed in [58] to addresses the flow rerouting problem. The algorithm comprises three steps: a routing discovery for new flows, rerouting of existing flows, and assigning channels to active links. The number of rerouted flows is restricted to a predefined threshold. The algorithm starts with discovery step to find the routes to the newly coming flows. Since channel information is not considered, the traffic load on each link is distributed evenly on all channels. The link cost metric for each link is calculated and inactive links in the previous configuration are assigned with higher cost. The cost for inactive link is obtained by multiplying the normalized utilization by a predefined penalty constant. Dijkstra algorithm is employed to find routes for the new flows based on the link cost. In the second step, only a predefined number of previous flows are allowed to be rerouted. The new routes are selected if they produce less contention to the network. Lastly, the channels are assigned to active links such that maximum traffic load is minimized on each channel.

3.2.3. Reconfiguration Trigger

In reconfiguration algorithms, the algorithm must decide when to trigger the reconfiguration process. Typically, reconfiguration algorithms trigger the reconfiguration process if some set of conditions are satisfied as in [35, 84, 87]. Reference [84] proposes to use the maximum total utilization over all collision domains as an indicator for channel reassignment trigger. In [87], the triggering is based on traffic load monitored by the gateway on its adjacent links. The new CA is recomputed for when the fraction of the total load on a given channel is less than a certain threshold, while the reconfiguration trigger may also be periodic for specific interval or based on policy for aggregating similar traffic load matrices within a cluster [35].

In [35], a reconfiguration policy based on existing CA is proposed for addressing the problem of optimum utilization and reduction of cost of reconfiguration in MR-WMN. Traffic profilers at mesh nodes collect and observe the traffic information and provide the controller with traffic matrices periodically. Each traffic matrix presents the existing traffic demand between node pairs. The arriving traffic matrices are grouped into clusters where traffic matrices belonging to one cluster apply same CA configuration. Each cluster is represented with a weighted traffic matrix of all traffic matrices within the cluster. For each new matrix, the distance between the new matrix and all existing clusters is found; new traffic will then be added to the clusters if their distances are less than a predefined value from the arriving matrix. Based on the distance, the algorithm determines to add the received traffic matrix to one of the existing clusters or to form a new cluster. Channel reassignment is triggered if the received traffic matrix does not belong to the current cluster. Table 3 shows state-aware schemes with their approaches and limitations.

To disseminate the new configuration to the other part of the network a dedicated radio on each mesh router is used in [58] to exchange control information on a default channel. In [28], a simple distribution protocol is proposed. This is by taking the advantage of having a fully connected topology, where each link is assigned to a channel. A spanning tree rooted at the gateway is used to disseminate the configuration with specific control messages where higher priority is given to those messages, that is, by using 802.11e in 802.11-based WMNs.

As overall summary of the reviewed C-JCAR approaches and issues, there are few points to be highlighted that can guide the network designer to develop efficient C-JCAR solutions:

(i) The hardware capability of the mesh router and the wireless interface determine the type of CA scheme. The SCA-LS and DCA can achieve more efficient and flexible utilization of the radio spectrum resources than SCA. However, DCA require a link layer synchronous coordination that is difficult to be achieved in multihop environment with commodity IEEE 802.11a/b/g hardware. Furthermore, the switching overhead is not neglected factor and can have great impact over real-time traffic in multihop routes. On the other hand, SCA-LS also requires link layer synchronous coordination but can be operated with lower overhead if it compared with DCA. Therefore, we believe that SCA-LS is most suitable one to be implemented.

(ii) Due to scalability reasons, it is not recommended to maintain routing functionalities at layer-2. Multipath routing is recommended to apply since it is able to achieve load balancing and can lead to better exploitation of the topology structure of MR-WMN.

(iii): Topology is one important issue that can affect the performance of the network. Both CA and routing determine the physical topology of the network. 1-to-1 mapping, as has been considered by several works to maintain the network connectivity, affects the channel spatial diversity and results in underutilizing the network resources. Determining the active links is one effective step for any C-JCAR algorithm.

(iv) The unrealism of the current interference models can severely affect the quality of solutions of C-JCAR especially for those applied in multihop networks. Therefore, it is recommended to develop a new interference model based on empirical measurement. This can be easily achievable due to the static deployment of WMNs, where site survey and interference information can be easily measured and recorded beforehand.

(v) Approaches in the literature still lack an accurate modeling to the link capacity (effective capacity or virtual capacity) of wireless link under different level of traffic load, contention, interference, and location in respect to the gateway node. This is essential in order to develop efficient algorithms to optimize the traffic distribution in multichannel multihop architecture.

(vi) The majority of the C-JCAR approaches in the literature are load-aware and most works assume having a stable traffic distribution over the network. Unfortunately, this is not the case in real scenarios where the traffic is more dynamic since the traffic is aggregated from different mesh clients with different mobility degrees. Therefore, in order to reduce the effects of the traffic dynamics the C-JCAR most apply adaptive state-aware solutions and might also be integrated with a traffic prediction model and user association model to further reduce the effect of the traffic variation on the performance.

4. Practical Implementation and Test-Beds for MR-WMNs

In order to validate the optimization models for MR-WMNs, simulations approaches may not lead to realistic results. This is due to the difficulty of having an accurate characterization of the interference in multihop environment. Moreover, in order to support cross-layer solutions current hardware and protocol stack architecture need to be revised, and hence, several practical implementations and real-life test-beds are presented and implemented in the literature [4, 88-95]. Moreover, these efforts provide the researchers with practical frameworks to implement and evaluate their solution in real architectures. Most of these test-beds support multiple interfaces per mesh router and are developed using off-the-shelf 802.11 components or software-defined radios when heterogeneous technologies are implemented [96, 97].

Net-X project [98] is a popular framework developed to provide generic software architecture for MR-WMN. Particularly, it is designed to support hybrid CA configuration with two types of interfaces: (I) interfaces with SCA to receive data from neighbors and (II) switchable interfaces with DCA to transmit data to its neighbors at configurable channel switching intervals. A channel abstraction module is implemented between data link and network layer to support multiradio configuration and to coordinate the functionality of different channels. Packets are inserted to a specific channel queue of the switchable interface to be forwarded to next-hop nodes over different channels, data rates, or transmitting powers. The routing table entry contains destination IP address, next interface channel, and the output interface. A broadcast table is also maintained to select the proper output interfaces and channels to forward the broadcast packets.

MUP (Multiradio Unification Protocol) [99] is another software architecture that supports multiradio implementation using 802.11-based radios. Neighbor table is maintained at link layer that stores the MAC addresses and channel information for each neighbor interface. In [90, 91], a 20-node test-bed called KAUMesh is developed in Karlstad University in Sweden. KAUMesh is implemented based on Net-X and OLSR [38] with a modified Network Interface Controller (NIC). Mesh routers are built by single board platforms and equipped with several radios based on 802.11 with several gateway points. OLSR module is extended to support additional functionalities and its messages modified to enable exchanging the network status between mesh routers and to disseminate the channel configuration and the traffic demands in the network.

WARF [100] is a Linux based framework that designed to develop routing protocols and to perform resource monitoring and autonomous configuration over IPv6 networks. Multiradio nodes are also supported in this architecture, where a set of messages is defined for channel radio resources monitoring and configuration. This is achieved by exchanging control WARF messages piggybacked in the extension headers of IPv6 packets. WARF modules can also support cross-layer operations and different data forwarding and routing paradigm such as multipath routing.

Integrating Software-Defined Networking (SDN) [101] with WMN is researched in several works [93-95]. SDNs is an emerging architecture with a centralized controlling paradigm that enables a global control and configuration of the entire network through a set of configuration commands that are sent from SDN controllers down to the data plane. This feature enables applying global optimization strategies to WMNs. A WMN architecture based on open-flow [102] (standard protocol in SDN) is presented in [95]. The architecture is used to support flow-based routing and to reduce the overhead associated with mesh client's mobility. The architecture is implemented on KAUMesh test-bed and results show better performance than traditional schemes.

5. Conclusion and Future Research Directions

With the recent development of radio technologies nowadays, wireless technologies are expected to replace the existing wired infrastructure in the near future. In this context, WMNs are recognized to play a key role in the next-generation networks. Multiradio architecture based on IEEE 802.11 has been introduced to improve the network capacity to meet these new application requirements. In this paper, an effort is made to provide an insight into the existing approaches proposed for C-JCAR where these two problems are disclosed as vital issues to improve the network performance in multiradio architectures.

The contributions of this paper are summarized as follows. First, the key design issues for C-JCAR approaches are identified. These issues cover the topology aspects, algorithm design aspects, routing and link layer specifications, and traffic types. Second, the problem formulation and mathematical modeling are presented for the joint problem under different CA types and link specifications proposed approaches according to their link specifications and CA types. A set of optimization objectives and fairness constraints are also presented. Finally, based on the above key designed issues, joint configuration proposals and reconfiguration proposals are reviewed and followed by summary tables that highlight the design issues and present limitations and assumptions of each work. The above information can help network operator/planners to decide which approaches to be used based on the deployment scenario, network architecture, hardware capabilities, and traffic dynamics and characteristics.

For the main research direction in MR-WMNs, we argue that more effort needs to be done in the context of joint centralized approaches, because joint approaches in the literature have shown a considerable improvement to the network performance. This promotes toward integrating multiple cross-layer solutions and optimization issues in a unified centralized framework to achieve the highest network performance. In this architecture, the optimal configurations are obtained for all network components by taking the advantage of having the global network view. Several issues can be addressed in this framework such as configuring the parameters for directional antennas, transmission power and rates, mac protocols, channel assignments and spectrum management, routing decisions, network coding and adaptive modulation, users' association, and mobility management. The framework also performs other provisioning, management, and monitoring functions.

Besides the above research direction, there are still some remaining issues that still need further investigation by the C-JCAR approaches. These issues include the design of an efficient channel and route reconfiguration solution with a reconfiguration policy that adapts to the traffic dynamics and the channels status with lower reconfiguration overhead. Evolutionary techniques can be considered for this purpose. Moreover, other issues also need to be addressed in multiradio architecture such as fault-management and traffic profiling. Finally, developing an association mechanism for multiradio wireless mesh networks is also recommended for further research. Thus, mesh clients' association mechanism has to be determined based on the interference and load distribution on backhaul links in addition to the signal strength. The association problem can also be jointly solved with the C-JCAR problem to further optimize the network performance.

Notations

[figure omitted; refer to PDF]

Set of mesh routers

[figure omitted; refer to PDF]

Set of radio interfaces

[figure omitted; refer to PDF]

Set of orthogonal channels

[figure omitted; refer to PDF]

Set of links where each link [figure omitted; refer to PDF] connects two mesh routers [figure omitted; refer to PDF] and [figure omitted; refer to PDF] and operates on a channel [figure omitted; refer to PDF]

[figure omitted; refer to PDF] :

Set of links where each link [figure omitted; refer to PDF] connects two radios [figure omitted; refer to PDF] and [figure omitted; refer to PDF] and operates on a channel [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Number of time slots

[figure omitted; refer to PDF]

Interference constant (based on the interference model)

[figure omitted; refer to PDF] :

Channel capacity on link [figure omitted; refer to PDF]

[figure omitted; refer to PDF] :

Maximum channel capacity

[figure omitted; refer to PDF]

Set of links from [figure omitted; refer to PDF] interfering with link [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

The amount of load carried on link [figure omitted; refer to PDF]

[figure omitted; refer to PDF] :

Link activation variable, equaling 1 if link is active in time slot [figure omitted; refer to PDF] and 0 otherwise

[figure omitted; refer to PDF] :

Set of links from [figure omitted; refer to PDF] interfering with link [figure omitted; refer to PDF] or incident on one of [figure omitted; refer to PDF] radio pairs

[figure omitted; refer to PDF]

Transmitter mesh router of link [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Receiver mesh router of link [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Set of links incident in mesh router ( [figure omitted; refer to PDF] )

[figure omitted; refer to PDF]

Virtual capacity of link [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

The channel assigned to link [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Number of radio interfaces in mesh router ( [figure omitted; refer to PDF] )

[figure omitted; refer to PDF] :

Channel-node variable equal to 1 if there is any link [figure omitted; refer to PDF] incident on mesh router [figure omitted; refer to PDF] with channel [figure omitted; refer to PDF] and [figure omitted; refer to PDF]

[figure omitted; refer to PDF] :

PER at receiver node of link [figure omitted; refer to PDF] when [figure omitted; refer to PDF] is active.

References

[1] V. A. Siris, E. Z. Tragos, N. E. Petroulakis, "Experiences with a metropolitan multiradio wireless mesh network: design, performance, and application," IEEE Communications Magazine , vol. 50, no. 7, pp. 128-136, 2012.

[2] M. Portmann, A. A. Pirzada, "Wireless mesh networks for public safety and crisis management applications," IEEE Internet Computing , vol. 12, no. 1, pp. 18-25, 2008.

[3] S. Avallone, G. Di Stasi, "An experimental study of the channel switching cost in multi-radio wireless mesh networks," IEEE Communications Magazine , vol. 51, no. 9, pp. 124-134, 2013.

[4] I. F. Akyildiz, X. Wang, W. Wang, "Wireless mesh networks: a survey," Computer Networks , vol. 47, no. 4, pp. 445-487, 2005.

[5] Y. Xu, W. Wang, "Wireless mesh network in smart grid: modeling and analysis for time critical communications," IEEE Transactions on Wireless Communications , vol. 12, no. 7, pp. 3360-3371, 2013.

[6] P. H. Huynh, C. E. Chow, "Design and analysis of hybrid wireless mesh networks for smart grids," Advances in Intelligent Systems and Applications-Volume 1 , pp. 713-721, Springer, New York, NY, USA, 2013.

[7] H. Son, T. Kang, H. Kim, J.-B. Park, J. H. Roh, "A fair and secure bandwidth allocation for AMI mesh network in smart grid," The Computer Journal , vol. 55, no. 10, pp. 1232-1243, 2012.

[8] Y. Ding, Y. Huang, G. Zeng, L. Xiao, "Using partially overlapping channels to improve throughput in wireless mesh networks," IEEE Transactions on Mobile Computing , vol. 11, no. 11, pp. 1720-1733, 2012.

[9] P. B. F. Duarte, Z. M. Fadlullah, A. V. Vasilakos, N. Kato, "On the partially overlapped channel assignment on wireless mesh network backbone: a game theoretic approach," IEEE Journal on Selected Areas in Communications , vol. 30, no. 1, pp. 119-127, 2012.

[10] P. Cappanera, L. Lenzini, A. Lori, G. Stea, G. Vaglini, "Optimal joint routing and link scheduling for real-time traffic in TDMA wireless mesh networks," Computer Networks , vol. 57, no. 11, pp. 2301-2312, 2013.

[11] M. Yu, X. Ma, W. Su, L. Tung, "A new joint strategy of radio channel allocation and power control for wireless mesh networks," Computer Communications , vol. 35, no. 2, pp. 196-206, 2012.

[12] H. Cheng, S. Yang, "Joint QoS multicast routing and channel assignment in multiradio multichannel wireless mesh networks using intelligent computational methods," Applied Soft Computing , vol. 11, no. 2, pp. 1953-1964, 2011.

[13] K. Gokbayrak, E. A. Yildirim, "Joint gateway selection, transmission slot assignment, routing and power control for wireless mesh networks," Computers & Operations Research , vol. 40, no. 7, pp. 1671-1679, 2013.

[14] S. Avallone, "An energy efficient channel assignment and routing algorithm for multi-radio wireless mesh networks," Ad Hoc Networks , vol. 10, no. 6, pp. 1043-1057, 2012.

[15] S. Avallone, F. P. D'Elia, G. Ventre, "A new channel, power and rate assignment algorithm for multi-radio wireless mesh networks," Telecommunication Systems , vol. 51, no. 1, pp. 73-80, 2012.

[16] W. Wong, X. Chen, F. Long, S.-H. G. Chan, "Joint topology control and routing assignment for wireless mesh with directional antennas," in Proceedings of the IEEE Global Communications Conference (GLOBECOM '12), pp. 5699-5704, IEEE, Anaheim, Calif, USA, December 2012.

[17] A. P. Subramanian, H. Gupta, S. R. Das, J. Cao, "Minimum interference channel assignment in multiradio wireless mesh networks," IEEE Transactions on Mobile Computing , vol. 7, no. 12, pp. 1459-1473, 2008.

[18] K. N. Ramachandran, E. M. Belding, K. C. Almeroth, M. M. Buddhikot, "Interference-aware channel assignment in multi-radio wireless mesh networks," in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM '06), pp. 1-12, IEEE, Barcelona, Spain, April 2006.

[19] A. Raniwala, K. Gopalan, T.-C. Chiueh, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks," ACM SIGMOBILE Mobile Computing and Communications Review , vol. 8, pp. 50-65, 2004.

[20] M. Alicherry, R. Bhatia, L. E. Li, "Joint channel assignment and routing for throughput optimization in multiradio wireless mesh networks," IEEE Journal on Selected Areas in Communications , vol. 24, no. 11, pp. 1960-1971, 2006.

[21] B.-J. Ko, V. Misra, J. Padhye, D. Rubenstein, "Distributed channel assignment in multi-radio 802.11 mesh networks," in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '07), pp. 3981-3986, Kowloon, Hong Kong, March 2007.

[22] A. Raniwala, T.-C. Chiueh, "Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network," in Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 2223-2234, IEEE, March 2005.

[23] J. Tang, G. Xue, W. Zhang, "Interference-aware topology control and QoS routing in multi-channel wireless mesh networks," in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '05), pp. 68-77, ACM, Urbana-Champaign, Ill, USA, May 2005.

[24] H. Skalli, S. Ghosh, S. K. Das, L. Lenzini, M. Conti, "Channel assignment strategies for multiradio wireless mesh networks: issues and solutions," IEEE Communications Magazine , vol. 45, no. 11, pp. 86-95, 2007.

[25] X. Hong, B. Gu, M. Hoque, L. Tang, "Exploring multiple radios and multiple channels in wireless mesh networks," IEEE Wireless Communications , vol. 17, no. 3, pp. 76-85, 2010.

[26] P. H. Pathak, R. Dutta, "A survey of network design problems and joint design approaches in wireless mesh networks," IEEE Communications Surveys and Tutorials , vol. 13, no. 3, pp. 396-428, 2011.

[27] A. Musaddiq, F. Hashim, C. A. B. C. Ujang, B. M. Ali, "Survey of channel assignment algorithms for multi-radio multi-channel wireless mesh networks," IETE Technical Review , vol. 32, no. 3, pp. 164-182, 2015.

[28] J. J. Galvez, P. M. Ruiz, A. Gomez-Skarmeta Responsive Online Load-Balancing Routing and Load-Aware Channel Re-Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks , University of Murcia, Murcia, Spain, 2011.

[29] A. A. Franklin, A. Balachandran, C. S. R. Murthy, "Online reconfiguration of channel assignment in multi-channel multi-radio wireless mesh networks," Computer Communications , vol. 35, no. 16, pp. 2004-2013, 2012.

[30] M. Nekoui, A. Ghiamatyoun, S. N. Esfahani, M. Soltan, "Iterative cross layer schemes for throughput maximization in multi-channel wireless mesh networks," in Proceedings of the 16th International Conference on Computer Communications and Networks (ICCCN '07), pp. 1088-1092, IEEE, Honolulu, Hawaii, USA, August 2007.

[31] X.-Y. Li, A. Nusairat, Y. Wu, Y. Qi, J. Zhao, X. Chu, Y. Liu, "Joint throughput optimization for wireless mesh networks," IEEE Transactions on Mobile Computing , vol. 8, no. 7, pp. 895-909, 2009.

[32] C. Cicconetti, V. Gardellin, L. Lenzini, E. Mingozzi, "PaMeLA: a joint channel assignment and routing algorithm for multi-radio multi-channel wireless mesh networks with grid topology," in Proceedings of the IEEE 6th International Conference on Mobile Adhoc and Sensor Systems (MASS '09), pp. 199-207, Macau, China, October 2009.

[33] T.-Y. Lin, K.-C. Hsieh, H.-C. Huang, "Applying genetic algorithms for multiradio wireless mesh network planning," IEEE Transactions on Vehicular Technology , vol. 61, no. 5, pp. 2256-2270, 2012.

[34] B. Claise, B. Trammell, P. Aitken Specification of the Ip Flow Information Export (Ipfix) Protocol for the Exchange of Flow Information , 2013.

[35] A. A. Kanagasabapathy, A. A. Franklin, C. S. R. Murthy, "An adaptive channel reconfiguration algorithm for multi-channel multi-radio wireless mesh networks," IEEE Transactions on Wireless Communications , vol. 9, no. 10, pp. 3064-3071, 2010.

[36] X. Meng, K. Tan, Q. Zhang, "Joint routing and channel assignment in multi-radio wireless mesh networks," in Proceedings of the IEEE International Conference on Communications (ICC '06), pp. 3596-3601, Instanbul, Turkey, July 2006.

[37] J. J. Galvez, P. M. Ruiz, "Efficient rate allocation, routing and channel assignment in wireless mesh networks supporting dynamic traffic flows," Ad Hoc Networks , vol. 11, no. 6, pp. 1765-1781, 2013.

[38] T. Clausen, P. Jacquet Optimized link state routing protocol (olsr) ; 2070-1721; 2003

[39] Z. Wang, Y. Chen, C. Li, "PSR: a lightweight proactive source routing protocol for mobile ad hoc networks," IEEE Transactions on Vehicular Technology , vol. 63, no. 2, pp. 859-868, 2014.

[40] H. Le Minh, G. Sexton, N. Aslam, "Self-adaptive proactive routing scheme for mobile ad-hoc networks," IET Networks , vol. 4, pp. 128-136, 2014.

[41] J. A. N. Cordero, J. Yi, T. Clausen, "An adaptive jitter mechanism for reactive route discovery in sensor networks," Sensors , vol. 14, no. 8, pp. 14440-14471, 2014.

[42] J. Niu, L. Cheng, Y. Gu, L. Shu, S. K. Das, "R3E: reliable reactive routing enhancement for wireless sensor networks," IEEE Transactions on Industrial Informatics , vol. 10, no. 1, pp. 784-794, 2014.

[43] S. K. Singh, R. Duvvuru, J. P. Singh, "TCP and UDP-based performance evaluation of proactive and reactive routing protocols using mobility models in MANETS," International Journal of Information and Communication Technology , vol. 7, no. 6, pp. 632-644, 2015.

[44] J. Duan, X. Wang, S. Wang, S. Xu, "HHR: hierarchical hybrid routing scheme for information-centric network," China Communications , vol. 12, no. 6, pp. 141-153, 2015.

[45] C. M. S. Figueiredo, E. F. Nakamura, A. A. F. Loureiro, "A hybrid adaptive routing algorithm for event-driven wireless sensor networks," Sensors , vol. 9, no. 9, pp. 7287-7307, 2009.

[46] J. A. Guerrero Ibanez, L. A. Garcia Morales, J. J. Contreras Castillo, R. Buenrostro Mariscal, M. Cosio Leon, "HYRMA: a hybrid routing protocol for monitoring of marine environments," IEEE Latin America Transactions , vol. 13, no. 5, pp. 1562-1568, 2015.

[47] N. Kojic, I. Reljin, B. Reljin, "A neural networks-based hybrid routing protocol for wireless mesh networks," Sensors , vol. 12, no. 6, pp. 7548-7575, 2012.

[48] X. Chen, Z. Zhang, H. Luo, "Joint optimization of power control, channel assignment and scheduling in wireless mesh network," in Proceedings of the 3rd International Conference on Communications and Networking in China (ChinaCom '08), pp. 606-611, IEEE, Hangzhou, China, August 2008.

[49] A. U. Chaudhry, N. Ahmad, R. H. M. Hafez, "Improving throughput and fairness by improved channel assignment using topology control based on power control for multi-radio multi-channel wireless mesh networks," EURASIP Journal on Wireless Communications and Networking , vol. 2012, article 155, pp. 1-25, 2012.

[50] L. Yang, L. Quan, "A topology control algorithm using power control for wireless mesh network," in Proceedings of the 3rd International Conference on Multimedia Information Networking and Security (MINES '11), pp. 141-145, Shanghai, China, November 2011.

[51] Q. Liu, X. Jia, Y. Zhou, "Topology control for multi-channel multi-radio wireless mesh networks using directional antennas," Wireless Networks , vol. 17, no. 1, pp. 41-51, 2011.

[52] A. Ali, M. E. Ahmed, M. J. Piran, D. Y. Suh, "Resource optimization scheme for multimedia-enabled wireless mesh networks," Sensors , vol. 14, no. 8, pp. 14500-14525, 2014.

[53] T. Zhang, K. Yang, H.-H. Chen, "Topology control for service-oriented wireless mesh networks," IEEE Wireless Communications , vol. 16, no. 4, pp. 64-71, 2009.

[54] H. Zhang, D. H. K. Tsang, "Traffic oriented topology formation and load-balancing routing in wireless mesh networks," in Proceedings of the 16th International Conference on Computer Communications and Networks (ICCCN '07), pp. 1046-1052, IEEE, Honolulu, Hawaii, USA, August 2007.

[55] F. Liu, Y. Bai, "An overview of topology control mechanisms in multi-radio multi-channel wireless mesh networks," EURASIP Journal on Wireless Communications and Networking , vol. 2012, article 324, 2012.

[56] M. Kodialam, T. Nandagopal, "Characterizing the capacity region in multi-radio multi-channel wireless mesh networks," in Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom '05), pp. 73-87, ACM, Cologne, Germany, September 2005.

[57] A. H. Mohsenian-Rad, V. W. S. Wong, "Joint logical topology design, interface assignment, channel allocation, and routing for multi-channel wireless mesh networks," IEEE Transactions on Wireless Communications , vol. 6, no. 12, pp. 4432-4440, 2007.

[58] Y. Zhou, S.-H. Chung, H.-Y. Jeong, "Reconfiguring multi-rate wi-fi mesh networks with flow disruption constraints," Dynamics in Logistics , pp. 383-393, Springer, New York, NY, USA, 2013.

[59] A. Iyer, C. Rosenberg, A. Karnik, "What is the right model for wireless channel interference?," IEEE Transactions on Wireless Communications , vol. 8, no. 5, pp. 2662-2671, 2009.

[60] A. U. Chaudhry, R. H. M. Hafez, J. W. Chinneck, "On the impact of interference models on channel assignment in multi-radio multi-channel wireless mesh networks," Ad Hoc Networks , vol. 27, pp. 68-80, 2015.

[61] H. Li, Y. Cheng, C. Zhou, P. Wan, "Multi-dimensional conflict graph based computing for optimal capacity in MR-MC wireless networks," in Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS '10), pp. 774-783, IEEE, Genova, Italy, June 2010.

[62] M. Al-Ayyoub, H. Gupta, "Joint routing, channel assignment, and scheduling for throughput maximization in general interference models," IEEE Transactions on Mobile Computing , vol. 9, no. 4, pp. 553-565, 2010.

[63] J. Wellons, Y. Xue, "The robust joint solution for channel assignment and routing for wireless mesh networks with time partitioning," Ad Hoc Networks , vol. 13, pp. 210-221, 2014.

[64] V. Gardellin, S. K. Das, L. Lenzini, C. Cicconetti, E. Mingozzi, "G-PaMeLA: a divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks," Journal of Parallel and Distributed Computing , vol. 71, no. 3, pp. 381-396, 2011.

[65] O. Goussevskaia, Y. A. Oswald, R. Wattenhofer, "Complexity in geometric SINR," in Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '07), pp. 100-109, Montreal, Canada, September 2007.

[66] V. Kumar, M. V. Marathe, S. Parthasarathy, A. Srinivasan, "End-to-end packet-scheduling in wireless ad-hoc networks," in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04), pp. 1021-1030, Society for Industrial and Applied Mathematics, 2004.

[67] CPLEX V12. 1: User's Manual for CPLEX , International Business Machines Corporation, 2009.

[68] X. Huang, S.-L. Feng, H.-C. Zhuang, "Cross-layer fair resources allocation for multi-radio multi-channel wireless mesh networks," in Proceedings of the 5th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '09), pp. 1-5, IEEE, Beijing, China, September 2009.

[69] N. Sadeghianpour, T. C. Chuah, S. W. Tan, "Joint channel assignment and routing in multiradio multichannel wireless mesh networks with directional antennas," International Journal of Communication Systems , vol. 28, no. 9, pp. 1521-1536, 2015.

[70] S. Avallone, I. F. Akyildiz, G. Ventre, "A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless mesh networks," IEEE/ACM Transactions on Networking , vol. 17, no. 1, pp. 267-280, 2009.

[71] J. J. Galvez, P. M. Ruiz, "Joint link rate allocation, routing and channel assignment in multi-rate multi-channel wireless networks," Ad Hoc Networks , vol. 29, pp. 78-98, 2015.

[72] R. Kikuchi, K. Hosaki, M. Hasegawa, "Implementation and evaluation of a combined optimization scheme for routing and channel assignment in wireless mesh networks," in Proceedings of the 12th Annual IEEE Consumer Communications and Networking Conference (CCNC '15), pp. 619-624, IEEE, Las Vegas, Nev, USA, January 2015.

[73] K.-M. Liu, T. Ma, Y.-A. Liu, K.-H. Kou, "Fairness-oriented routing algorithm joint with power control and channel assignment for multi-radio multi-channel wireless mesh networks," The Journal of China Universities of Posts and Telecommunications , vol. 21, no. 5, pp. 55-60, 2014.

[74] M. Sharifi Jebeli, M. Dehghan, "Joint multicast routing and channel assignment in Multiradio Multichannel Wireless Mesh Networks using a multi objective algorithm," in Proceedings of the 6th Conference on Information and Knowledge Technology (IKT '14), pp. 163-170, IEEE, Shahrud, Iran, May 2014.

[75] E. Vaezpour, M. Dehghan, "A multi-objective optimization approach for joint channel assignment and multicast routing in multi-radio multi-channel wireless mesh networks," Wireless Personal Communications , vol. 77, no. 2, pp. 1055-1076, 2014.

[76] P. Raghavan, C. D. Tompson, "Randomized rounding: a technique for provably good algorithms and algorithmic proofs," Combinatorica , vol. 7, no. 4, pp. 365-374, 1987.

[77] M. R. Garey, D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness , Freeman, San Francisco, La, USA, 1979.

[78] X. Shao, C. Hua, A. Huang, "Robust resource allocation for multi-hop wireless mesh networks with end-to-end traffic specifications," Ad Hoc Networks , vol. 13, pp. 123-133, 2014.

[79] S. Avallone, F. P. D'Elia, G. Ventre, "A traffic-aware channel re-assignment algorithm for wireless mesh networks," in Proceedings of the European Wireless Conference (EW '10), pp. 683-688, IEEE, Lucca, Italy, April 2010.

[80] P. Kyasanur, N. H. Vaidya, "Routing and interface assignment in multi-channel multi-interface wireless networks," in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '05), pp. 2051-2056, IEEE, New Orleans, La, USA, March 2005.

[81] F. Herzel, G. Fischer, H. Gustat, "An integrated CMOS RF synthesizer for 802.11a wireless LAN," IEEE Journal of Solid-State Circuits , vol. 38, no. 10, pp. 1767-1770, 2003.

[82] M. Yun, Y. Zhou, A. Arora, H.-A. Choi, "Channel-assignment and scheduling in wireless mesh networks considering switching overhead," in Proceedings of the IEEE International Conference on Communications (ICC '09), pp. 1-6, IEEE, Dresden, Germany, June 2009.

[83] P. Li, N. Scalabrino, Y. Fang, E. Gregori, I. Chlamtac, "How to effectively use multiple channels in wireless mesh networks," IEEE Transactions on Parallel and Distributed Systems , vol. 20, no. 11, pp. 1641-1652, 2009.

[84] S. Avallone, G. Di Stasi, A. Kassler, "A traffic-aware channel and rate reassignment algorithm for wireless mesh networks," IEEE Transactions on Mobile Computing , vol. 12, no. 7, pp. 1335-1348, 2013.

[85] J. J. Galvez, P. M. Ruiz, A. F. G. Skarmeta, "TCP flow-aware channel re-assignment in multi-radio multi-channel wireless mesh networks," in Proceedings of the 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS '11), pp. 262-271, Valencia, Spain, October 2011.

[86] S. Arkoulis, E. Anifantis, V. Karyotis, S. Papavassiliou, N. Mitrou, "On the optimal, fair and channel-aware cognitive radio network reconfiguration," Computer Networks , vol. 57, no. 8, pp. 1739-1757, 2013.

[87] W. Fu, B. Xie, X. Wang, D. P. Agrawal, "Flow-based channel assignment in channel constrained wireless mesh networks," in Proceedings of the 17th International Conference on Computer Communications and Networks (ICCCN '08), pp. 1-6, IEEE, St. Thomas, Virgin Islands, USA, August 2008.

[88] P. Dely, M. Castro, S. Soukhakian, A. Moldsvor, A. Kassler, "Practical considerations for channel assignment in wireless mesh networks," in Proceedings of the IEEE Globecom Workshops (GC Wkshps '10), pp. 763-767, IEEE, Miami, Fla, USA, December 2010.

[89] B. Blywis, M. Guenes, F. Juraschek, J. H. Schiller, "Trends, advances, and challenges in testbed-based wireless mesh network research," Mobile Networks and Applications , vol. 15, no. 3, pp. 315-329, 2010.

[90] P. Dely, A. Kassler, "Kaumesh a multi-radio multi-channel mesh testbed," in Proceedings of 9th Scandinavian Workshop on Wireless Ad-hoc & Sensor Networks (ADHOC '09), Niagara Falls, Canada, 2009.

[91] M. C. Castro, P. Dely, A. J. Kassler, F. P. D'Elia, S. Avallone, "Olsr and net-X as a framework for channel assignment experiments," in Proceedings of the 4th ACM International Workshop on Experimental Evaluation and Characterization (WINTECH '09), pp. 79-80, ACM, Beijing, China, 2009.

[92] G. Di Stasi, R. Bifulco, S. Avallone, R. Canonico, A. Apostolaras, N. Giallelis, T. Korakis, L. Tassiulas, "Interconnection of geographically distributed wireless mesh testbeds: resource sharing on a large scale," Ad Hoc Networks , vol. 9, no. 8, pp. 1389-1403, 2011.

[93] D. Zhu, X. Yang, P. Zhao, W. Yu, "Towards effective intra-flow network coding in software defined wireless mesh networks," in Proceedings of the 24th International Conference on Computer Communication and Networks (ICCCN '15), pp. 1-8, IEEE, Las Vegas, Nev, USA, 2015.

[94] P. Dely, "Towards an architecture for openflow and wireless mesh networks," in Proceedings of the Ofelia Summer School, November 2011.

[95] P. Dely, A. Kassler, N. Bayer, "OpenFlow for wireless mesh networks," in Proceedings of the 20th International Conference on Computer Communications and Networks (ICCCN '11), pp. 1-6, Maui, Hawaii, USA, August 2011.

[96] V. Angelakis, A. Capone, A. Fragkiadakis, S. Napoli, S. Papadakis, G. Perantinos, V. Spitadakis, E. Tragos, D. Yuan, "Experience from testbeds and management platforms towards mesh networking with heterogeneous wireless access," in Proceedings of the IEEE 14th International Symposium and Workshops on a World of Wireless, Mobile and Multimedia Networks (WoWMoM '13), pp. 1-6, Madrid, Spain, June 2013.

[97] Redcomm project April 2016, http://www.redcomm-project.eu/description.html

[98] P. Kyasanur, C. Chereddi, N. H. Vaidya, "Net-x: system extensions for supporting multiple channels, multiple interfaces, and other interface capabilities,", University of Illinois at Urbana-Champaign, Wireless Networking Group, Urbana, Ill, USA, 2006.

[99] A. Adya, P. Bahl, J. Padhye, A. Wolman, L. Zhou, "A multi-radio unification protocol for IEEE 802.11 wireless networks," in Proceedings of the 1st International Conference on Broadband Networks (BroadNets '04), pp. 344-354, IEEE, San Jose, Calif, USA, October 2004.

[100] S. Kuklinski, P. Radziszewski, J. Wytrebowicz, "WARF: component based platform for wireless mesh networks," Smart CR , vol. 1, no. 2, pp. 125-138, 2011.

[101] S. Ortiz Jr., "Software-defined networking: on the verge of a breakthrough?," IEEE Computer , vol. 46, no. 7, pp. 10-12, 2013.

[102] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner, "OpenFlow: enabling innovation in campus networks," ACM SIGCOMM Computer Communication Review , vol. 38, no. 2, pp. 69-74, 2008.