In this section, we describe TC mechanisms for MR-MC WMNs in the existing literature. During the discussion, the mutual dependence of TC on power control, channel assignment, routing and directional antennas in MR-MC WMNs is emphasized. In other words, the described mechanisms are either directly part of the TC procedure, or act closely to the TC function.
Power control
The key of power control (PC) is to choose the transmitting power of each node in such a way that energy consumption is reduced and some properties of the communication graph (typically, connectivity) are maintained. Hence, PC can be viewed as one means to determine the network connectivity and underlying physical layer topology. Actually, TC and PC are used interchangeably sometimes in literature since both of them attempt to control the transmission range of nodes while trying to achieve a certain desirable property of the topology. In [
23], the distinction between them is identified: TC may affect layers higher than PC, by choosing not to make certain node adjacencies visible to the network layer (e.g., by filtering at the MAC layer). On the other hand, PC almost invariably results in some effect on the topology. Moreover, the objective of PC may not be same as TC but for power conservation, etc.
The mechanisms of PC can be largely classified into static power control and dynamic power control. A static power control allocation assigns power levels to the nodes that do not change frequently over time, unless there are drastic changes in the network topology. On the other hand, with dynamic power control strategies, every node changes its power level for transmission frequently over the time. Such changes can be made on per link, per destination, per TDMA slot or per packet basis. The Static power control mechanisms are simpler and more robust but often result in suboptimal performance due to their inefficient adaptation of changing traffic demands and dynamic wireless conditions. Static power control mechanisms can be further classified into uniform range power control and variable range power control [
23].
The problem of power control has been studied extensively for ad-hoc networks and SR-SC WMNs. Some power control strategies proposed for them are still appropriate for MR-MC WMNs with the purpose of reducing interference and maintaining the connectivity. These algorithms for SR-SC WMNs could be divided into two categories: one is centralized control algorithms operated by a central node with higher handling capacity and more energy resources to collect the entire network information; the other is distributed control algorithms run by all the nodes with the same configurations, only local information required. In [
24], the author proposed two centralized optimal algorithms for creating connected and bi-connected static networks with the objective of minimizing the maximum transmitting power for each node. A minimum spanning tree based topology control algorithm was proposed in [
25], which achieved network connectivity with minimal power consumption. In [
26], a distributed algorithm was developed for each node to adjust its transmitting power to construct a reliable high-throughput topology. In [
27], Hou et al. presented an analytic model to allow each node to adjust its transmitting power to reduce interference and hence achieve high throughput. Jia et al. proposed a QoS topology control mechanism for ad hoc networks in [
28], which constructs a network topology that can meet end-users’ QoS requirements with the minimal total transmission power. In [
29], the authors systematically studied the connectivity issue in ad hoc networks and proposed several approximation algorithms for computing k-connectivity topology using minimal transmission power. Finally, different definitions of interference and several algorithms which target to construct network topologies such that maximum (or average) link (or node) interference of the topology is either minimized or approximately minimized are presented [
30]. In [
31], the authors consider the problem of topology control by joint power control and routing to maximize the network throughput. Two heuristic algorithms are designed to assign transmission powers to mesh routers, such that the total interference or the maximum node interference in the network is minimized. Simulation results reveal the following relationship: the topology with minimum total interference has higher total throughput, while the topology with minimum maximal node interference has higher minimal per-node throughput.
In MR-MC WMNs, high power transmissions not only increase interference but also degrade channel reuse in a physical area. Consequently, severe problems of co-channel and adjacent channel interferences may occur [
20]. Thus, efficiency power control strategies are required to enhance the performance of MR-MC WMNs. Numerous studies have been proposed for multi-channel MAC with power control [
32‐
35]. The key ideas include that data packets are transmitted with proper power control to exploit channel reuse, control packets are transmitted with maximum power in order to warn the neighboring nodes of future communication activity between the sender and the receiver. In [
32,
36], power control approaches using directional antennas are proposed, which makes it possible for dynamic adjustment of the transmission power for both data and control packets to optimize energy consumption. The use of beam-switched antennas permits interference-limited concurrent transmissions. It also provides a node with the appropriate tradeoffs between throughput and energy consumption. A dynamic power control for MR-MC WMNs is proposed in [
19]. The author proposed a new power selection MR-MC unification protocol (PMMUP) that coordinates local power optimizations at the radios of a node. It acts as a decentralized aggregate interference prediction method for power optimization in MR-MC WMNs.
Channel assignment
With the MR-MC architecture in use, the capacity of wireless mesh networks can be improved significantly by using multiple channels to reduce the effect of interference and enhance the throughput. Efficient channel assignment (CA) is required to ensure the optimal use of the limited channels in the radio spectrum. CA influences the contention among wireless links and the network topology or connectivity between mesh nodes. In fact, there is a tradeoff between minimizing the level of contention and maximizing connectivity. The connectivity of WMN should be ensured in the process of assigning channels to the radios. Any change in the CA is likely to render certain links to be non-existent. Consequently, flows that are utilizing these links are disrupted and need to be re-routed, which in turn impacts the network throughput. The effect of these disruptions can be significant if these changes are frequent. Existing CA proposals mainly follow two approaches to ensure connectivity. One approach is to assign a default radio interface on each node configured to a default channel that connects the entire network, and remaining radio interfaces are assigned to non-default channels. This approach could ensure connectivity of the entire network by the use of an interface on each node, but it imposes heavy overhead on the network. The other approach is to assign channels to node radio interfaces such that two neighbor nodes forming a link can have a common channel for communication.
As mentioned above, efficient CA schemes should take reducing interference into account. Consequently, interference measurement is required as a crucial criterion of CA. There are two major methods to measure interference. The first one is based on topological characteristics, for example by counting number of neighbors using the same channel [
37]. The second one operates by measuring traffic load carried in the neighborhood rather than only the number of neighbors using the same channel [
6,
20,
38]. The former and the latter approaches can be viewed as traffic-independent interference estimation and traffic-aware interference estimation, respectively.
CA protocols can be broadly classified into static, dynamic, and hybrid schemes according to the description in [
38,
39]. Static CA is a fixed assignment of channels to the radios of nodes which remains unchanged over the course of network operation. Such schemes can be further subdivided into common channel assignment and varying channel assignment. Common channel assignment is the simplest scheme, in which the radio interfaces of each node are all assigned the same set of channels. The benefit is the maintaining of the connectivity of network, and the drawback is the failure to account for the various factors affecting channel assignment in a WMN. In varying channel assignment, interfaces of different nodes may be assigned different sets of channels. Static CA mechanisms are often less adaptive to changing wireless conditions such as external interference and traffic, but such mechanisms are simpler and do not incur channel switching delays.
Dynamic CA allows any interface to be assigned any channel, and the interfaces can frequently switch from one channel to another considering current interference, traffic demands, power allocation. Coordination mechanism is needed to ensure nodes which need to communicate are on a common channel. The benefit of this scheme is the potential to use many channels with fewer interfaces. The channel switching delays and the need for coordination mechanisms for channel switching are the key challenges. Such mechanisms can be further classified into per link, per packet, per time-slot based mechanisms. These CA policies pose novel design problems like multi-channel hidden terminal, sporadic disconnections. On the other hand, they have the potential to achieve better system capacity if designed properly.
When every node in the network changes channels of its radios dynamically, nodes often require tighter coordination between them to avoid disconnections, deafness problem, and multi-channel hidden terminal problem. Such issues make dynamic CA mechanisms much more complicated.
In hybrid CA schemes, some of the radios are assigned fixed channels while others switch their channels dynamically. These policies benefit from their partially dynamic design while inheriting simplicity of static mechanisms. Hybrid CA schemes can be further classified based on whether the fixed interfaces use a common channel or varying channel approach. Hybrid CA strategies are attractive because they allow for simple coordination algorithms as fixed CA and retain the flexibility of dynamic CA.
Using multiple radios and multiple channels with a centralized CA scheme in WMN was proposed by Raniwala et al. [
6]. In a subsequent publication, the authors proposed a dynamic distributed CA and routing algorithm. However, both these schemes rely on prior availability of the traffic demands of each mesh node, which is not always feasible. Alicherry et al. [
9] proposed a centralized load-aware link scheduling, CA, and routing protocol. The authors propose the division of fixed duration time frames into slots where a specific set of nodes can transmit within each time slot on specific channels assigned by a CA algorithm. The centralized nature of the proposed algorithm and the assumption of infrequent changes in traffic demands make the proposed solution less attractive. The hybrid multiple channel protocol (HMCP) proposed in [
5] requires radios to switch between channels on a per-packet basis, which requires time synchronization and coordination between mesh nodes. The breadth first search-channel assignment (BFS-CA) scheme proposed in [
20] requires certain number of Mesh Routers with certain number of radio interfaces to be placed at certain hops from the gateway, which could ensure connectivity of the entire network. The drawback of BFS-CA algorithm is that one non-overlapping channel and one radio of the mesh router is always reserved for default channel, which does not make efficient utilization of available interfaces and channels. In [
40], a cluster-based multipath topology control and channel assignment scheme (CoMTaC) is presented. It explicitly creates a separation between the CA and TC functions, thus minimizing flow disruptions. A cluster-based approach is employed to ensure basic network connectivity in [
40]. CoMTaC also takes advantage of the inherent multiple paths that exist in a typical WMN by constructing a spanner of the network graph and using the additional node interfaces. The second phase of CoMTaC proposes a dynamic distributed CA algorithm, which employs a novel interference estimation mechanism based on the average link-layer queue length within the interference domain. Partially overlapping channels are also included in the CA process to enhance the network capacity. The experimental results show that the proposed scheme outperforms existing dynamic channel assignment schemes by a minimum of a factor of 2.
In [
41], a CA algorithm termed topology-controlled interference-aware channel-assignment algorithm (TICA) was proposed to use TC based on PC for CA in MR-MC WMNs. In [
37], the authors consider the CA problem in a multi-radio WMN that involves assigning channels to radio interfaces for achieving efficient channel utilization. A graph-theoretic formulation of the CA guided by a novel TC perspective is presented, and the resulting optimization problem is NP-complete. Then, it presents an ILP (Integer Linear Program) formulation that is used for obtaining a lower bound for the optimum, and develops a new greedy heuristic CA algorithm (termed CLICA) for finding connected, low interference topologies by utilizing multiple channels. Their evaluations show that the proposed CLICA algorithm exhibits similar behavior and comparable performance relative to the optimum bound with respect to interference and capacity measures. Moreover, their extensive simulation studies show that it provides a large reduction in interference even with a small number of radios per node, which in turn leads to significant gains in both link layer and multihop performance in 802.11-based multi-radio mesh networks.
In [
42], the synergy between TC and CA is exploited to reduce the overall interference in MR-MC WMNs. It formulates CA as a non-cooperative game, with nodes selecting low interference channels while maintaining some degree of network connectivity. This game is shown to be a potential game, which ensures the existence of, and convergence to, a Nash equilibrium (NE). Next, the performance of NE topologies with respect to interference and connectivity objectives is evaluated. By quantifying the impact of channel availability on interference performance, it illuminates the tradeoff between interference reduction that can be achieved by distributing interference over multiple channels and the cost of having additional channels. Finally, it studies the spectral occupancy of steady state topologies, and shows that despite the non-cooperative behavior, the NE topologies achieve load balancing. To maximize network utilization and minimizing traffic disruption, a polynomially bound online heuristic algorithm, DeSARA, is proposed in [
43], which finds the CA for the current traffic demand by considering the existing CA of the network to minimize the reconfiguration overhead. In [
44], the authors define a utility-based framework for joint CA and TC in MR-MC WMNs, and present a greedy algorithm for solving the corresponding optimization problem. Key features of the proposed approach are the support for different target objectives and the efficient utilization of wired network gateways. Si et al. conducted an in-depth survey of the CA approaches for MR-MC WMNs in the literature [
45]. In the survey, different CA approaches are examined individually with their advantages and limitations highlighted, and categorical and overall comparisons for them are also given in detail.
Routing
As we mentioned, TC, CA, PC, and routing are coupled together in MR-MC WMNs. On one hand, CA and PC determine the connectivity between nodes since two nodes can communicate with each other only when they are on a common channel and within the transmission range of each other. As we know, routing decisions are largely made based on the network topology. Thus, CA and PC have direct impacts on routing. On the other hand, channel and transmission power should be dynamically adjusted according to the traffic status, which is determined by routing algorithm. Therefore, routing, CA, and PC should be jointly optimized for MR-MC WMNs.
In [
21], the authors proposed a novel joint topology control and routing (JTCR) protocol for MR-MC network to exploit both channel diversity and spatial reusability, which addressed joint topology control and the routing problem in an IEEE 802.11-based MR-MC wireless mesh network. An Equivalent Channel Air Time Metric (ECA TM) was proposed to quantify the difference of various adjustment candidates. The essential part of this protocol is to select a feasible adjustment candidate with the smallest metric value and then to coordinate the affected nodes through negotiation to realize the adjustment.
Tang et al. studied interference-aware TC and QoS routing in IEEE 802.11-based multi-channel wireless mesh networks with dynamic traffic [
46]. They presented a novel definition of co-channel interference to precisely capture the influence of the interference. According to this definition, they formally defined and presented an effective heuristic for the minimum interference survivable topology control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all
K-connected topologies. Then, they formulated the bandwidth-aware routing (BAR) problem for a given network topology, which seeks routes for QoS connection requests with bandwidth requirements. A polynomial time optimal algorithm to solve the BAR problem is presented under the assumption that traffic demands are splittable. For the non-splittable case, they present a maximum bottleneck capacity path routing heuristic. Simulation results show that compared with the simple common channel assignment and shortest path routing approach, their scheme improves the system performance by 57 % on average in terms of connection blocking ratio.
In [
10], the authors proposed the TiMesh MC-WMN architecture, in which the logical channel allocation, topology design, interface assignment and routing are formulated as a joint linear mixed integer optimization problem. The formulated model takes into account of the number of available NICs in routers, the number of available orthogonal frequency channels, expected traffic load between different source and destination pairs and the effective capacity of the logical links. The proposed scheme balances the load among logical links and provides higher effective capacity for the bottleneck links.
All the above studies assume channels with fixed, pre-determined width, which is the direct result of the static spectrum partition style of existing wireless technologies. In [
22], the authors proposed a joint channel width adaptation, topology control and routing protocol for MR-MC wireless mesh networks. The authors mathematically formulated the channel width adaptation, topology control and routing as a joint mixed 0–1 integer linear optimization problem. This model formulation explored the use of channels with dynamic bandwidth adaptation. It does not treat the spectrum as the set of discrete orthogonal channels but the continuous blocks, and exploits partially overlapped channels with variable widths to further improve the spectrum efficiency. The advantages of channel width adaptation are two folds. On one hand, the load can be distributed as evenly as possible across the spectrum in a fine granularity to achieve channel load balance. On the other hand, in a scenario with many interfering links, by creating more small-width orthogonal channels, contention and confliction can be reduced.
TC with directional antennas
Directional antennas is another key technology proposed as one of the viable means to enhance the performance of WMNs including increasing capacity, and range of communications, reducing the interference, conserving energy and resolving collisions [
47].
In MR-MC WMNs, the interference among transmissions operating on the same frequency channel is alleviated by using multiple radios on each mesh node and by assigning different channels to each radio, thus enabling more concurrent transmissions, compared with the single radio single channel WMNs. Although more simultaneous transmissions are allowed in MR-MC WMNs, the interference cannot be eliminated completely due to limited number of available non-overlapping channels and broadcast nature of the wireless medium [
48]. Using directional antennas in MR-MC WMN has been recognized as an attractive solution to the interference problem. The main reason is that directional antenna can focus energy in the intended direction instead of spreading it out on all directions, thus improves spatial reuse. Networks using directional antennas typically allow more parallel transmissions than those using conventional omnidirectional antennas with the same number of available non-overlapping channels, allow nodes to communicate simultaneously without interference, and potentially establish links between nodes far away from each other, and the number of routing hops can be fewer than that of omnidirectional antennas.
Antenna orientation affects the performance of MR-MC WMNs as well as PC, CA and routing strategies. Antenna orientation has an impact on network topology, thus affects channel assignment and routing strategies. Therefore, proper modeling schemes are required in designing MR-MC WMNs with directional antennas.
An MR-MC WMN using multiple directional antennas is proposed in [
49]. This study performs theoretical analysis and presented theoretical bounds on the capacity for MR-MC wireless networks with directional antenna. DMesh [
50] is a wireless mesh network architecture that incorporates directional antennas in MR-MC WMNs. DMesh assumes perfect antenna orientation between communicating node pairs. This may not be the optimum orientation to alleviate interference. DMesh dedicates an exclusive NIC for a wireless link and thus does not utilize network resources efficiently. It also affects the connectivity and results in longer routing paths, hence more interference. In [
48], the authors proposed an algorithm to produce joint decisions on routing and channel assignment with practical implementation considerations for MR-MC WMNs with switched beam antennas which require switching and synchronization. They do not take into account the directional interface assignment issue, the antennas are assumed to point to each other during communication. The authors in [
51] predefined the antenna orientation using a sectored connectivity graph and formulated their architecture mathematically as a mixed integer linear problem. The problem is then solved to acquire topology, channel assignment, interface allocation and routing decisions. In [
52], Liu et al. proposed a topology control method for MR-MC WMNs with directional antennas. The proposed three-step solution starts by constructing a set of routing trees and seeks to balance the traffic among the tree links. In the second step, it performs interface assignment for each node in the tree with the objective of balancing traffic load among the links served by each node. Finally, it performs channel assignment and antenna orientation to minimize interference while covering all the intended neighbors of the node. Based on the method proposed in [
52], the authors in [
53] presented an improved version of topology control algorithm. In [
53], the routing tree construction algorithm is improved in the first step of the solution in [
52].
Comparison of topology control mechanisms in MR-MC WMNs
In the previous sections, we have overviewed state-of-the art TC mechanisms which are classified according to their dependence on power control, channel assignment, routing, and directional antennas. Next we further compare the typical classified TC mechanisms in MR-MC WMNs with respect to their inputs, objectives, and techniques used. As shown in Additional file 1: Table S1, twelve TC mechanisms are chosen for comparison and they are identified by the first author and the index of the references, and some TC mechanism also have abbreviations named by the authors in the literature.
It can be seen from Additional file 1: Table S1 that the following parameters can be the inputs of a TC mechanism: node deployment, number of NICs and channels, power profile, antenna type, link and traffic profile, connectivity and topology constraints. Most of the TC mechanisms formulate the TC problem as a optimization problem with respective objectives. The considered objectives include the network throughput (capacity), interference, connectivity, and fairness. Since the formulated optimization problems are normally NP-hard, heuristic approaches are proposed as the viable TC mechanism to achieve the suboptimal solutions.
As we pointed out, TC, PC, CA, and routing are mutually dependent in MR-MC WMNs. Regarding the techniques used, the TC mechanisms can hence employ some or all functions of PC, CA, and routing. PMMUP (Olwal [
19]) is proposed as a new power selection MRMC unification protocol that coordinates local power optimizations at the radios of a node to maximize a variable related to the most congested (i.e., the bottleneck) logical link across the network. As shown in Additional file 1: Table S1, a variety of CA schemes are proposed in CLICA (Marina [
37]), MesTic (Skalli [
38]), Subramanian [
39], ComTac (Naveed [
40]), Komali and MacKenzie [
42]. Both CA and PC functions are employed in TICA (Chaudhry [
41]), which use a novel approach of controlling the network topology based on PC before intelligently assigning the channels to the multi-radio mesh router. Moreover, some or all the functions of PC, CA, and routing are employed in the proposed mechanisms of Alicherry [
9], TiMesh (Rad [
10]),JTCR (Chen [
21]), DeSARA (Franklin [
43]), and Tang [
46]. Such joint approach of TC mechanisms with joint optimization of some or all the functions of PC, CA, and routing often leads to NP-hard complexity. To have a realistic solutions, suboptimal heuristic mechanisms with reduced complexity have been investigated in some mechanisms such as CLICA (Marina [
37]), Alicherry [
9], DeSARA (Franklin [
43]), and Tang [
46].
The advantages of joint optimization approaches for TC are that they can take into account multiple objectives of outputs including throughput, interference, connectivity, and fairness. On the other hand, they have disadvantages because they involve more input parameters (like including traffic demands) and hence yield more complex optimization and coordination operations in the network.