Joint Topology Control and Channel Assignment Employing Partially Overlapping Channels in Multirate Wireless Mesh Backbone

Abstract

Many efforts have been done to better exploit multiple radios and multiple channels to improve system performance in wireless mesh networks. However, in the case of the IEEE 802.11b/g/n family of standards, there are only three non-overlapping channel, the simple use of orthogonal channels cannot effectively eliminate the interference. The simultaneous use of multiple partially overlapping channels has been certified as an effective way to further eliminate interference and improve network performance in 802.11-based wireless mesh networks. Good network topological structure can lead to low interference, load balancing and high throughput. This research looks into the problem of topology control and partially overlapping channel assignment to improve the performance of multi-radio multi-channel multirate wireless mesh networks. We propose an optimal topology control algorithm and greedy channel assignment algorithm to maximize the network capacity (in term of each node’s traffic delivery ratio). Simulation results present that our topology control and partially overlapping channel assignment method can dramatically improve system throughput.

1 Introduction

Wireless mesh networks (WMNs) have attracted a lot of interests of the research community and the industry due to the increased coverage, self-organization, and self-configuration possibilities they offer to reduced deployment, hardware and software cost. There are numerours applications of WMNs, such as broadband home networking, metropolitan area networks, transportation systems, health and medical systems, security surveillance systems, etc. The throughput is the main concern of WMNs, as more and more applications (i.e. real-time multimedia applications) need high bandwidth. In this paper, we focus on the issue of topology control and channel assignment in the case of 802.11-based wireless mesh backbone. There is a set of mesh routers, some of which are called gateway routers, because they can access the Internet through wired connections. Each router has a communication requirement gathering from mesh clients. The connections between gateways and mesh nodes form a forest (each tree is rooted in a gateway). Our task is to build the routing forest, assign channel to each link of the forest, such that the actual per-node throughput of the system is maximized. The per-node throughout follows the definition of nominal capacity in [1].

Topology control is frequently studied in wireless networks. Its main concern is to build a logic topology that fulfills certain requirements, such as well connectivity, low interference, balanced load, and high throughput. Some existing literature, such as fault tolerant method, shortest path tree (SPT) method, load balancing method and heuristic method have already been brought forward for building logical topologies for WMNs. However, these methods may not be suitable for our object (maximizing per-node throughput). In this paper, topology control process is to construct the routing forest, and prepares for the channel allocation. It aims to minimize the sum active time of all links in the system, and this is consistent with the goal of maximizing the per-node end-to-end throughput of the network.

To improve the capacity of WMNs, some researchers focus on allowing the mesh networks to equip each node with multiple radios and use multiple channels (MRMC). In spite of this, MRMC cannot fundamentally solve the problem and the reason is that traditional communication system designs emphasize orthogonality and assign orthogonal channels to paralleled transmitting nodes in close proximity. However, this is severely limited. Currently, WMNs operate in two unlicensed frequency spectrum bands: 2.4 GHz Industrial, Scientific, and Medical (ISM) band, and 5 GHz Unlicensed National Information Infrastructure (UNII) band. Each standard (802.11/a/b/g) defines a fixed number of channels for use by mesh routers and mobile users, with the channels partially overlapping with each other. For example, IEEE 802.11b/g has 11 frequency channels. There is only 5 MHz’s gap between the center frequencies, and each channel occupies a bandwidth of 22 MHz. The signal falls within about 11 MHz for each side of the center frequency. As a result, an 802.11b/g signal on any channel overlaps with several adjacent channels (also known as adjacent channel interference). Since 802.11b/g provides only three non-overlapping channels, the condition becomes more severe. As a consequence, there is an urgent need to extend the channel assignment to some overlapping frequency channels.

Partially overlapped channels can improve network performance by allowing more channels to be used simultaneously in wireless mesh networks [2]. In this paper, we investigate topology control and channel assignment by exploiting the gain of using partially overlapping channels in wireless mesh backbone. We first analyze the relationship between network throughput and channel assignment by using partially overlapping channels. Then, an optimal topology control algorithm is proposed to generate high quality links such that the total active time of all links is minimized. Finally, a heuristic algorithm is proposed to assign overlapping channels to links in the system such that the system throughput can be maximized.

The rest of this paper is organized as follows. The related work is discussed in Sect. 2. Section 3 describes the system model and formulates the problem concerned. The proposed topology control and channel assignment method is presented in Sects. 4 and 5. We investigate the performance of our solution through simulations and analyze the results in Sect. 6. Finally, Sect. 7 concludes this paper.

2 Related Work

The topology control algorithms that minimize interference level can be found in [3,4,5,6]. They expected to minimize the interference level, to improve more spatial reuse, so as to improve the network throughput. In [3], the author proposed an optimization model on the basis of interference and link capacities that found out the aggregate end to end throughput for a given network topology having static traffic on all the possible disjoint multiple paths. Then they proposed new optimized Interference Aware Pruned Two Path (IA-P2P) topology control scheme which used their network optimization model and pruned some links in the physical topology to select the best two among multiple completely disjoint paths for each owner. Some researches work on directly improving the network throughput, or solving robustness against failures. In [4], a capacity-optimized cooperative (COCO) topology control scheme was proposed to improve the system throughput in MANETs by jointly considering both upper layer network capacity and physical layer cooperative communications. In [5], authors investigated the joint optimization of channel allocation, power control and routing under SINR model for multi-channel multi-radio wireless mesh networks. They applied bio-inspired optimization techniques to channel allocation and power control. Authors in [6] proposed a heuristic method known as fault-tolerant interference-aware topology control (FITC) to solve robustness against failures and throughput improvement in a distributed fashion. In their method, they first guaranteed that the network was K-Connected using the graph modification, routing and channel assignment. Then, power control, rate adaptation, channel selection and scheduling were applied to enhance the network throughput.

Recent studies indicate that utilizing partially overlapping channels to facilitate interference mitigation can improve the full-range channel utilization and the network throughput. Utilizing partially overlapped channels is Some works have been done to improve the network performance by exploiting partially overlapping channels for wireless mesh networks [7,8,9,10,11,12]. In [7], authors formulated the channel assignment, interface assignment and scheduling problem concerning partially overlapped channels as a linear mixed-integer program. Their results show that the aggregate network capacity increases by 90% when all partially overlapped channels within the 802.11b frequency band are used. A further step was made later in [8] and [10], where the authors addressed the flow allocation along with channel assignment. Their results revealed that partially overlapped channel-based design allows more flexibility in wireless resource allocation and it can make efficient use of the spectrum by providing superior channel assignment and flow allocations. Apart from the optimization approaches, heuristics approaches were also proposed to handle the channel assignment and/or scheduling problem, e.g., [11]. Their conclusions also shown the partially overlapped channel schemes bring enhancement of network throughput. In [9], authors proposed a new channel assignment scheme named CAEPO by considering the traffic-aware interference between channels as the main factor. They turned it into a metric according to the overlapping degree between channels. Besides that, packet loss ratio was another major factor in the development of their proposed method. Xiang and Luo [12] revisited the joint channel assignment and link scheduling problem using the physical interference model. They cautioned that partially overlapped channels should be applied carefully in practice. Because the resulting complexity of assigning these extra channels may offset the marginal improvement brought by them.

In general, partially overlapping channel assignment schemes published can roughly be classified into two types: one is traffic-relevant load-aware channel assignment schemes [13,14,15], which assume a known traffic profile in the network or pre-determined paths for flows so that the load on each link is known before performing channel assignment. The task is to compute a channel assignment scheme to make sure that the load can be delivered in time. The other is traffic-irrelevant channel assignment schemes [16,17,18,19,20,21], which assume dynamic traffic in the network and assign channels for all links with the goal of minimizing total network interference. Ours belongs to the second type. Of course, there is also research on partially overlapping channel assignment for scenarios in the absence of information exchange. For example, a graphical game and uncoupled learning based distributed partially overlapped channel selection method was proposed in [19], which was different from our proposed algorithm as ours is centralized for easy implementation.

Though Ding et al. [17] presented a weighted conflict graph by taking into account both the channel separation and the physical distance, its interference indicator was a 0–1 variable that cannot accurately reflect the degree of interference from different adjacent channels with different Euclidean distances. Partially overlapped interference graph was used to model interference between links in [19] which was essentially the same as weighted conflict graph in nature. The objective of the formulated channel assignment problem was to minimize the total number of interfering link pairs or minimize the maximum link interference. Wang and Shi [21] focused on utilizing partially overlapping channels (POCs) to improve network capacity and proposed a traffic-irrelevant channel assignment algorithm, which assigned channels for all links in the network while minimizing total network interference. Wang and Shi [22] explored how to exploit POCs to perform end-to-end channel assignment, and they distinguished the application scenarios in which POCs can help to improve network performance, and the application scenarios in which POCs should be avoided in order not to bring in more overhead but little performance promotion.

3 Problem Specification

The wireless mesh backbone discussed in this paper consists of a set of mesh routers, some of which are gateway routers because they have wire connection to the Internet. We consider a wireless mesh backbone network, it consists of a set of mesh routers (each router has aggregated the communication requirements from end users). Some routers are called gateway routers because they have wire connection to the Internet. These gateway routers are denoted as $W=\{g_1,g_2,\ldots ,g_m\}$. For simplicity, we call these gateway routers gateways, non-gateway routers mesh nodes and nodes for both of them. The set of mesh routers in the network is represented with $W \cup V$, and $V= \{v_1, v_2,\ldots , v_n\}$ denotes the set of non-gateway routers.

In this paper, the use of multi-radio and multiple partially overlapping channels is considered and it is based on 802.11b/g/n standard. The number of channels available is limited in the current network protocols. We use C to denote the set of partially overlapped channels (POCs), $C = \{1, 2, \ldots , 11\}$. In addition, each node is able to be equipped with q ($q \ge 1$) wireless transceivers, any of which can work on any channel provided by the current network protocols. Multi-interface and multi-channel characteristics enable more concurrent transmissions. When one radio is transmitting or receiving packets on one channel, another radio on the same node can simultaneously undertake transmission on another different channel.

We assume the communication link is bi-directional and all traffic is to/from the Internet. The traffic demand of mesh node v ($v \in V$), is denoted as $\lambda _v$. Limited by the actual bandwidth, only certain percent of traffic demand can be satisfied. We use $\alpha$ ($0 \le \alpha \le 1$) to denote the traffic delivery ratio, it means that for node v, only $\alpha \lambda _v$ can deliver from mesh node to the gateway.

Firstly, a logical topology should be built so that each mesh node can route their traffic to the Internet via the gateways. It means that all the mesh nodes should connect to the gateways (directly or through other mesh nodes). In our model, a mesh node only have one single path routing to the gateway, the routes of all mesh nodes to gateways form a set of trees (a forest) and gateways are the roots of these trees. The forest is performed and represented by $G(W \cup V, E)$. The traffic of the end user will converge at the tree node, which will further relay the traffic to their parent node in the direction of the gateway. A subtree which rooted at node v is called $T_v$, v’s corresponding traffic load is denoted as L(v). Thus

$$\begin{aligned} L(v) = \sum _{u \in T_{v}} \alpha \lambda _{u}. \end{aligned}$$

(1)

All mesh routers are assumed to use the same transmission power (we do not consider power adjustment). Node u can communicate with node v if they are within each other’s transmission range. The data rate of a link $l_v$ (the link concerning node v to its parent) is determined by strength of the signal received, which can be represented as a function.

$$\begin{aligned} R(l_{v})=f(P, d(u,v)). \end{aligned}$$

(2)

Here, P is the fixed transmission power, and d(u, v) is the physical distance between u and v. Table 1 gives the values of f() when node’s transmission power is 20 dBm. It is obtained by Huawei Technologies Co. Ltd. in real environment and shows the relationship between transmission range and data rate.

Table 1 Transmission range, receive power and data rate when transmission power is 20 dBm

As shown in Table 1, the interference range (cochannel interference) is 73 m when the transmission power is 20 dBm. Since nodes may use multiple radios, two node’s interference is defined based on their specific transceivers. Whether two nodes on specific radios interfere with each other depends on both the physical distance between them and the channels that their radios use. With the use of POCs for communication, the actual interference distance of a node decreases with the increasing of channel distance. Supposing the interference range of a node is $D_I$ when two nodes use the same channel, then two nodes u and v interferer with each other when the following condition is satisfied,

$$\begin{aligned} d(u,v) \le \varDelta _s D_I. \end{aligned}$$

(3)

Here, s is channel separation between $c_u$ and $c_v$ ($c_u$ means the specific radio’s channel of node u), $s= |c_u- c_v|$. $\varDelta _s$ is the channel overlapping degree. In IEEE 802.11-based standard, Table 2 shows the channel overlapping attenuation index which was calculated by Burton in [23].

Table 2 Channel overlapping degree

Since communication links are bi-directional, two links $l_1$ and $l_2$ interfere with each other iff one end-node of $l_1$ interferes with one end-node of $l_2$ (based on the specific radios that two nodes use for communication of these two links). Link $l_v$’s collision set is defined as the set of links that interfere with or is interfered by it, including $l_v$ itself, and is denoted as $I(l_v)$,

$$\begin{aligned} I(l_{v})= \{l_{u}| l_{u} \, {\hbox {interferes with or is interfered by}} \,\, l_{v} \}. \end{aligned}$$

(4)

In wireless communication system, two interfering links cannot transmit data simultaneously due to the signal interference. In order to guarantee successful transmissions, any two links in the same collision set can not be active simultaneously (we consider the most conservative case). That is, the sum of active time of all links in a collision set per unit time cannot exceed one. In each unit of time, the link $l_v$ is active for a time duration of

$$\begin{aligned} t_{l_{v}} = \frac{L(v)}{R(l_v)}. \end{aligned}$$

(5)

The total active time of all links in collision set $I(l_v)$ is defined as (normalized) collision time of $l_v$, and denote it as $t(I(l_v))$, which is:

$$\begin{aligned} t(I(l_{v}))= & {} \displaystyle \sum _{l_{u}\in {I(l_{v})}} t_{l_{u}} \nonumber \\= & {} \displaystyle \sum _{l_{u}\in {I(l_{v})}} \frac{L(u)}{R(l_u)} \nonumber \\= & {} \displaystyle \sum _{l_{u}\in {I(l_{v})}} \frac{\displaystyle \sum \nolimits _{u \in T_{v}} \alpha \lambda _{u}}{R(l_u)} \nonumber \\= & {} \alpha \displaystyle \sum _{l_{u}\in {I(l_{v})}} \frac{\displaystyle \sum \nolimits _{u \in T_{v}} \lambda _{u}}{R(l_u)} . \end{aligned}$$

(6)

Since any two links in a collision set cannot be active at the same time in order to guarantee successful transmission. It means that for any mesh node v in V, its normalized collision time can not exceed one. That is,

$$\begin{aligned} t(I(l_{v}))= \alpha \displaystyle \sum _{l_{u}\in {I(l_{v})}} \frac{ \displaystyle \sum \nolimits _{u \in T_{v}} \lambda _{u}}{R(l_u)}\le 1. \end{aligned}$$

(7)

From inequality (7), we can get

$$\begin{aligned} \alpha \le \displaystyle {\frac{1}{\displaystyle \sum \nolimits _{l_{u}\in {I(l_{v})}} \frac{\displaystyle \sum \nolimits _{u \in T_{v}} \lambda _{u}}{R(l_u)}}}. \end{aligned}$$

(8)

In this paper, the nominal capacity we concern is the maximal possible traffic delivery ratio. It is the maximal possible value of $\alpha$ that meets inequality (8) for each node $v \in V$. That is,

$$\begin{aligned} TP=\displaystyle \min _v { \displaystyle {\frac{1}{\displaystyle \sum \nolimits _{l_{u}\in {I(l_{v})}} \frac{\displaystyle \sum \nolimits _{u \in T_{v}} \lambda _{u}}{R(l_u)}}}}. \end{aligned}$$

(9)

In a scenario of wireless mesh backbone network, we are given some gateways and a set of mesh routers, and |C| partially overlapping channels. The problem of our concern is that, first we should design the network topology. It means the connection of all mesh routers to the gateway. Thus, the connections between this gateways and mesh nodes form a forest and each tree is rooted at one gateway. Then, we should assign channel to each link of the forest, such that the network throughput defined in Eq. (9) is maximized.

4 Topology Control Algorithm

As discussed in Sect. 3, we should first construct an optimal network topology to generate high quality links. Our objective is to maximize the Eq. (9). According to last section’s analysis, expected active time of link $l_v$’s collision set is the sum of all links’ active time in the set (here, expected active time means each node’s delivery ratio is one). Node v’s traffic delivery ratio is inversely proportional to the total expected active time. To maximize the traffic delivery ratio means to minimize the total expected active time of all links in the collision set. Therefore, link’s expected active time plays an important role in computing the traffic delivery ratio. In the topology construction stage, we should minimize each link’s expected active time. That means to minimize total expected active time of all links (delivery ratio of each node is one),

$$\begin{aligned} T(L)= \sum _{l_v \in E} {t_{l_v}}, \end{aligned}$$

(10)

here, E denotes the link set of the forest.

This equation can be translated as following,

$$\begin{aligned} T(L) = \sum _{v_x \in V} {T(v_x)}, \end{aligned}$$

(11)

here, $T(v_x)= t(g_a,v_1)+t(v_1,v_2)+\cdots +t(v_y,v_x)$ is the transmission time of $v_x$’s traffic demand between $v_x$ and gateway $g_a$ (supposing node $v_x$’s traffic need be relayed by $v_y,\ldots , v_2, v_1$ to the gateway $g_a$). Equation (11) shows that we should minimize each mesh node’s transmission time of its traffic to gateway.

As follows, we present the topology construction strategy which can achieve minimal total mesh nodes’ transmission time. Let $T^\delta (v_i)$ denote the optimal transmission time between mesh node $v_i$ and gateway set (maybe through multi-hop, the gateway that produces the minimal value), the equation below can be used to get a possible route for $v_i$ and compute its transmission time:

$$\begin{aligned} T^*(v_i)= \min \left\{ \min _{g_a \in W} t(g_a,v_i), \min _{1 \le i \le n, j \ne i } \{T^\delta (v_j)+ t(v_j,v_i)\}\right\} , \end{aligned}$$

(12)

here, $t(g_a,v_i)$ is the direct transmission time between mesh router $v_i$ and gateway $g_a$ if $v_i$ can directly communicate to $g_a$. Otherwise, the value is set to infinity.

The Eq. (12) means that the route can be the direct connection between client $v_i$ and gateway (if there are direct connection between them), or through another optimal link between mesh router $v_j$ and gateway.

Lemma 1

Equation (12) always produces the optimal $T^*(v_i)$ which is equal to $T^\delta (v_i)$.

Proof

Suppose $(g_b, v_1, v_2, \ldots , v_j,v_i)$ is the route that achieve optimal transmission time $T^\delta (v_i)$. It is obvious that $(g_b, v_1, v_2, \ldots , v_j)$ must be the route that achieve optimal traffic transmission time $T^\delta (v_j)$. Therefore, Eq. (12) covers all the possibilities of the routes, and can achieve optimal solution. $\square$

To construct the optimal forest topology rooted at gateways, we should connect each node to a tree. Let $V_{tree}$ denote the set of mesh nodes already connected to the forest, and $V^*$ the set of the remaining mesh nodes. Suppose for every mesh node $v_j \in V_{tree}$ and $v_i \in V^*$, it satisfies $T^\delta (v_j) \le T^\delta (v_i)$, then we can use the following equation to get a possible route for $v_i$.

$$\begin{aligned} T'(v_i)= \min \left\{ \min _{g_a \in W} t(g_a,v_i), \min _{v_j \in V_{tree}} {T^\delta {v_j}+ t(v_j,v_i)} \right\} \end{aligned}$$

(13)

Lemma 2

$T'(v_k) = T^\delta (v_k)$, if $v_k$ is the mesh node that produces the minimal value of $T^\delta (v_i), \forall v_i \in V^*$.

Proof

Through comparison of (12) and (13), the difference between them is that only part of the $T^\delta (v_j)$ (nodes that are already added into the tree) are considered when calculating $T'(v_i)$. Obviously, if $T^\delta (v_i) = T^\delta (v_j) + t(v_j,v_i)$, it must satisfy $T^\delta (v_i) \ge T^\delta (v_j)$. Therefore, only $T^\delta (v_j)$ smaller than $T^\delta (v_i)$ should be considered when calculating $T^\delta (v_i)$, which is just the method of calculating $T' (v_k)$ in Lemma 2. $\square$

Lemma 3

$T^\delta (v_k) = \min _{v_i \in V^*} {T'(v_i)}$, if $v_k$ is the mesh router that produces the minimal value of $T'(v_i), \forall v_i \in V^*$.

Proof

Suppose $T^\delta (v_k)$ is not the minimum among all the mesh nodes in set $V^*$, there must exist a node $v_l$ that produces the minimal value of $T^\delta (v_i), \forall {v_i \in V^*}$. According to Lemma 2, $T' (v_l) = T^\delta (v_l)$. Therefore, $T' (v_k)< T' (v_l) = T^\delta (v_l)< T^\delta (v_k)$. Since $T^\delta (v_k)$ is the optimal traffic transmission time, $T'(v_k)$ cannot achieve better solution than the optimal value. Therefore, the proposition is wrong. $T^\delta (v_k)$ must be the minimum among all the clients in set $V^*$. $\square$

According to Lemmas 2 and 3, the following is the algorithm for constructing the tree topology.

Theorem 1

Algorithm 1 always produces the optimal $T^\delta (v_i)$ for any mesh node $v_i$ in the network.

Proof

At the beginning, when $V_{tree}= \phi$, we can get $T^\delta (v_k)= t(g,v_k)$ for the mesh router $v_k$ which produces the minimal value $t(g_a,v_i)$. Obviously, $T^\delta (v_k)$ is optimal for mesh router $v_k$. Our algorithm adds $v_k$ to set $V_{tree}$, generate a link $(g_a, v_i)$ and deletes it from set $V^*$. The supposition $\max _{v_i \in V_{tree}} {T^\delta (v_i)} \le \min _{v_j \in V^*}{T^\delta (v_j)}$ holds.

For the following steps, when there are q mesh nodes in set $V_{tree}$, suppose $\max _{v_i \in V_{tree}} {T^\delta (v_i)} \le \min _{v_j \in V^*}{T^\delta (v_j)}$ holds. According to Lemmas 2 and 3, we can get minimal $T^\delta (v_k)$ by finding the minimal $T'(v_k)$ in set $V^*$. Then, we add mesh node $v_k$ to set $V_{tree}$ and delete it from set $V^*$. Therefor, when there are $q+1$ mesh routers in set $V_{tree}$, the supposition $\max _{v_i \in V_{tree}} {T^\delta (v_i)} \le \min _{v_j \in V^*}{T^\delta (v_j)}$ still holds.

In conclusion, the supposition $\max _{v_i \in V_{tree}} {T^\delta (v_i)} \le \min _{v_j \in V^*}{T^\delta (v_j)}$ always holds in Algorithm 1, which means we can always get optimal $T^\delta (v_i)$ in Algorithm 1. $\square$

5 Greedy Channel Assignment Method

After the forest topology is generated, we should assign channel to each link such that the system throughput defined in Eq. (9) can be maximized. Maximizing Eq. (9) means maximizing the actual delivery ratio of each node. For this purpose, we should minimize each link’s collision set active time. So the link which will potentially cause server interference to the network should be considered first. Then we select the channel that ensures the link’s collision set active time to be the minimized and allocate it to this link. Based on this analysis, we propose a heuristic channel assignment method to tackle this problem.

For assigning proper channels for these links in order to cause minimal interference into the system, there are two problems to be solved. Firstly, we should decide the processing order of the edges in the forest. The second issue is to determine which channel will be the most suitable for each link.

Since the link with the largest potential collision time will be the bottleneck of the system, it should be considered first. All links in the forest can be divided into two parts, solved link set (each link in the set has been assigned a channel), and unsolved link set. So the collision time of a link should be the sum of active time of links in collision set of two parts.

We use E to denote the link set of system, and E1 the set of links that have already been assigned channels so far (that is, solved link set). $E2= E- E1$ is used to denote the set of links not considered yet (unsolved link set). I(E1, l, i) denotes the collision set of link l in E1 while link l uses channel i ($l \notin E1$). I(E2, l) denotes the collision set of link l in E2 (supposing all links in unsolved link set use the same channel).

Definition 1

(Solved Set Interference) The active time of collision set in solved link set is defined as:

$$\begin{aligned} w_1= \displaystyle \frac{1}{|C|} \sum _{i\in C} {\sum _{l' \in I(E1,l,i)} {t_{l'}}} \end{aligned}$$

(14)

Definition 2

(Potential Interference) The active time of collision set in unsolved link set is defined as:

$$\begin{aligned} w_2= \displaystyle \sum _{l' \in I(E2,l)} {t_{l'}} \end{aligned}$$

(15)

Then we use judge metric which is $w= w_1+w_2$ to determine which link should be considered first. The link whose judge metric w is the largest (supposing link $l*$) will be selected and added to the solved link set.

Secondly, a proper channel should be chosen to link $l*$ and it is based on the collision time of this link. We will select the channel which makes the total active time of all links in the collision set of link $l*$ minimized. Namely, the channel which minimizes Eq. (6) (link $l*$ has been added to the solved link set) will be selected. This two-step strategy will be repeated until all links are solved. The detail of this procedure is shown in Algorithm 2.

The quality of channel assignment can be further improved by repeatedly executing Algorithm 2. In each new round, when we compute $w_2$, each link in unsolved link set E2 use the channel which is assigned in last round. The algorithm will be stopped when no more change can be made (no link change its channel in new round) or will be tried for certain times. Through our experiment, our greedy algorithm will converge rapidly and be fairly stable.

6 Performance Evaluation

In this section we evaluate the performance of our proposed topology control and channel assignment method using partially overlapping channels. The simulator using C++ programming language has been developed to evaluate the performance improvement of employing topology control and partially overlapping channels.

6.1 Simulation Configurations

In the simulation, we assume IEEE 802.11b protocol is used in the network. In the protocol, there are three orthogonal channels out of eleven available channels. We investigate the performance of our proposed method under one gateway situation in the first three subsections. In these settings, the simulations are conducted in a 200 m $\times$ 200 m region, with one gateway router and some non-gateway routers. The gateway is placed on the top left corner of the region, and the mesh routers are randomly and uniformly distributed inside the region. In the last subsection, we evaluate the influence of different number of gateways under different distribution patterns. The channel capacity is set to be  54 Mbps, which is the highest data rate. Each router has a total traffic demand of 1 Mbps. All nodes use the same transmission power level. Rate adaptation is introduced in our system model. Each link will select the most suitable data rate based on the sender’s transmission power and the distance between two end nodes. The table of transmission range and interference range by transmission power and data rate is shown in Table 3. It is obtained by Huawei Technologies Co. through outdoor experiments in real environment. The entry is indicated by the pair of data rate and transmission power (TX power). For example, supposing all nodes use 17 dBm as the transmission power, if the distance from $v_i$ to $v_j$ is less than 12 m, they can use data rate of  54 Mbps for communication.

Table 3 Transmission range and interference range versus transmission power and data rate

In the following subsection, we investigate the advantage brought topology control algorithm (not considering link’s channel assignment). We evaluate the performance of our optimal topology construction algorithm by comparing it with a general topology control method (shortest path tree, SPT). Then, we will evaluate the performance of our joint topology control and channel assignment method employing partially overlapping channels. We evaluate the performance of our method (termed as TCCA-POC when using our proposed topology control method and CA-POC when using SPT topology control method) by comparing it with the method which employs three orthogonal channels (termed as TCCA-Orth and CA-Orth separately) and only one channel (termed as TCCA-One and CA-One). We investigate the impact of the different system parameters, such as the number of mesh nodes and node’s transmission power level, on the performance of our proposed algorithms. The performance evaluation metric is nominal system throughput, which is defined in (8). In the last subsection, we will evaluate the effects of different numbers of gateways on system performance under different distribution patterns.

Therefore, four kinds of scenarios are simulated to evaluate the network performance of our proposed method, which are (1) scenarios of only considering topology control, (2) scenarios of different number of mesh nodes with the same transmission power, (3) scenarios of different transmission power levels using the same number of non-gateway routers, and (4) scenarios of different numbers of gateways under different distribution patterns. For all these scenarios, we assume that links can adaptively choose their data rate, according to their power setting and the distance between node pairs. Each simulation runs 100 times and their average is taken as the result.

6.2 Performance of Optimal Topology Construction Algorithm

The first experiment is to evaluate the performance improvement by employing optimal topology control method. In this subsection, we don’t consider channel assignment for each link. So the metric is set as the sum of expected active time of all links in the tree, that is Eq. (10). Here, each node’s traffic delivery ratio is set to one. We compare our optimal tree topology construction method (termed as Optimal-TC) with a SPT method (termed as SPT-TC). We will investigate the impact of the amount of mesh routers and transmission power. In the former case, the amounts of mesh nodes vary from 30 to 100 with a step of 10. The transmission power for each node is set to be 20 dBm. In the latter, the number of mesh nodes is set to be 90 considering the connectivity of all mesh nodes to gateway at the minimal transmission power, 8 dBm.

From Fig. 1, by comparing our optimal topology control with SPT method in two cases, we could see that the total expected transmission time of all links in the forest decreases sharply in our method. Because according to the data in Table 1, presuming the transmission power to be 20 dBm, there is a mesh node $v_i$ which is 64 m away from the gateway and the other mesh node $v_j$ which is at the midpoint of the line between node $v_i$ and gateway. In the SPT method, node $v_i$ will communicate to the gateway directly, and the transmission time will be 1 / 6. In our proposed algorithm, $v_i$ will choose $v_j$ to relay its traffic to the gateway, and the transmission time will be $1/18\,+\,1/18= 1/9$. Compared with the SPT method, our proposed method will save $33.3\%$ of the transmission time.

Figure 1a shows the comparison between two topology control methods under the conditions of different amounts of mesh nodes. From the result, we can see that the gap between SPT method and our proposed method becomes bigger with the increase of the mesh nodes in the network. It means that, when the number of mesh nodes grows up, our proposed algorithm will encourage more nodes using multiple hops (but each link with high transmission data rate) to deliver their traffic to the gateway. When there are 100 mesh nodes in the network, our proposed method can save up to $40.1\%$ of the transmission time compared with the SPT method.

Figure 1b shows the cases of different transmission power levels. From the results, we make the following observation: (1) total transmission time decreases with the increase of transmission power; (2) our proposed method outperforms the SPT method and the superiority becomes more significant when we increase the power. Large transmission power means high data rate and long transmission range. This can explain the former case. Still, with higher transmission power, the transmission range is increased and more mesh nodes will directly deliver their traffic to the gateway with low data rate (these nodes cannot communicate to the gateway directly as those of the transmission range of the gateway when power is low). So the gap between these two methods becomes bigger, and reaches $43.4\%$ when the power is 23 dBm.

Fig. 1

Total transmission time comparison only considering topology control. a Different number of mesh nodes. b Different transmission power level

6.3 Throughput Comparison in Different Numbers of Mesh Routers

In this subsection, we evaluate the effectiveness of our joint optimal topology control and channel assignment method. This experiment is to evaluate how the amount of mesh routers affects the nominal throughout of the system. We compare three channel sets (only one channel, three orthogonal channels and eleven partially overlapping channels) based on our joint method and SPT case (it means the usage of the general SPT method for topology control). The numbers of no-gateway routers vary from 30 to 100 with a step of 10. The transmission power for each node is set to be 20 dBm.

From Fig. 2, we make the following observations:

• (1) System throughput generally decreases as the increasing of node number in all three channel set schemes, due to more traffic demand and forwarded traffic load. When the amount of mesh routers increases, the total traffic demand will increase, and so will the actual traffic load of the nodes that are far away from the gateway. This will consume more bandwidth since long hops to the gateway need more relay traffic, and thus will consume more system capacity, and finally decreases the system normal capacity.

• (2) TCCA-POC method performs better than TCCA-Orth and TCCA-One with the increase of the number of mesh nodes. As shown in Fig. 2, on average, the TCCA-POC achieves around $18.6\%$ higher capacity than the TCCA-Orth and around $158\%$ higher than the TCCA-One scheme. And the same case can be found among CA-POC, CA-Orth, and CA-One. This is because that our proposed method with partially overlapping channels adaptively selects appropriate channel for each link. Each link with appropriate overlapping channel will guarantee other links with larger chance to select proper channels with little interference to more links, to reduce the active time of link collision set, and finally to improve the system throughput.

• (3) TCCA-XX outperforms the CA-XX no matter what channel set is employed (here, XX are POC, Orth, and One cases). On average, TCCA-POC achieves around $76.5\%$ higher throughput than CA-POC, and up to $120.7\%$ in the case of 100 mesh nodes. Even TCCA-Orth performs better than CA-POC. These phenomena prove that our proposed topology control algorithm can achieve optimal forest topology, which will minimize the total transmission time of all links in the network and lead to optimal system performance.

Fig. 2

The nominal system throughput with different number of mesh routers

6.4 Throughput Comparison in Different Transmission Power Levels

The case of studying how transmission power used by nodes affects the network throughput is investigated in this subsection. The number of mesh routers is set to 90 to guarantee the connectivity in the minimal power case.

As shown in Fig. 3, system capacity generally grows as the increasing of transmission power levels of each node in all six cases, due to higher transmission data rate for each link and fewer hops from mesh nodes to gateways. When the transmission power increases, the nodes that are far away from the gateway can use fewer hops to relay its traffic to gateway, and this will consume less system capacity. On the other hand, the link can use higher data rate to transmit its traffic load when transmission power increases. This will reduce the expected active time of this link and leave more capacity for other links in its collision set, and finally increase its traffic delivery ratio.

The same phenomenon as last subsection we find is that the TCCA-POC method outperforms TCCA-Orth and TCCA-One in each transmission power level. As shown in Fig. 3, on average, the TCCA-POC achieves around $21\%$ higher capacity than the TCCA-Orth and around $171\%$ higher than the TCCA-Orth scheme. Finally, the same as (3) in last subsection, TCCA-XX outperforms the CA-XX in each transmission power.

Fig. 3

The nominal system throughput with different transmission power

6.5 Throughput Comparison in Different Numbers of Gateways

In this subsection, we simulate scenarios of different numbers of gateways. We place 80 non-gateway nodes and M gateways in a 200 m $\times$ 200 m region, where M varies from 1 to 5. The transmission power of each node is 20 dBm. We test two cases of distribution patterns of gateways, one case of which is that gateways are placed on the corners and center of the region, the other is random distribution. In the former case, gateways are sequentially deployed on the four corners of the square area when the number of gateways is no more than 4, and the fifth gateway is deployed on the center of the region. The results of corner distribution and random distribution are shown in Fig. 4.

Generally, system throughput grows with the increasing number of gateways in two distribution cases. The reason is that more gateways prompt mesh nodes to connect to the nearest gateway with fewer hops and high date rate. This will reduce the transmission time of mesh nodes to gateways and finally increase the network throughput.

The same as former subsections, POC-TCCA outperforms POC-CA to verify the superiority of our optimal topology control algorithm. POC-TCCA outperforms Orth-TCCA and One-TCCA is the outcome of adopting partially overlapping channels. On comparison with Fig. 4a, b, we find that random distribution of gateways can lead to better performance than corner distribution case. The reason is that random distributed gateways are closer to the mesh nodes than those in corner case, then mesh nodes can either use high data rate to communicate or connect to the gateway using fewer hops. When we place the fifth gateway on the center of the region in corner distribution, the two cases have nearly the same performance.

Fig. 4

Total transmission time comparison only considering topology control. a Gateways are corner distribution. b Gateways are random distribution

7 Conclusion

In this paper, we have studied the issue of topology control and partially overlapping channel assignment in backbone WMNs. Our task is to construct the forest topology and assign proper channels to links to achieve high throughput for multi-radio multi-channel multi-rate wireless mesh networks. We first propose an optimal topology construction algorithm to minimize the sum of expected active time of all links in the forest. Then a greedy channel assignment method is given to minimize link’s collision set active time (which will improve nominal system throughput) by employing partially overlapping channels. The simulation results have shown that our topology control method performs better than the other general method (SPT). Our joint topology control and channel assignment method using partially overlapping channels achieves higher throughput than orthogonal channels and one-channel cases with different amounts of mesh nodes, transmission power and gateway distribution.