1 Introduction

A wireless mesh network is composed of gateway, client nodes and wireless transceiver with the advantages of low installation and maintenance cost, easy network building and high communication speed, it is considered as one of the key technologies for future wireless mobile network access. It solves the problem of “last mile” broadband network access, which has been widely used in the construction of wireless enterprise backbone networks, and also applied in remote areas, harsh environments and other areas for network deployment [1,2,3]. Within the communication range, the nodes of the wireless ad hoc network can be moved arbitrarily, and the information transfer between two predefined nodes can be done by ways of the intermediate nodes, which is also known as a multi-hop network. In a power distribution scenario, such network can be built by using the existing lamp posts, e.g., in the streets, for the purpose of power automated information collections [4].

Single-radio single-channel (SRSC) technology is usually used in a traditional ad hoc network, where frequent channel switching not only results in larger time delay, but also requires complicated node synchronization and channel switching mechanisms. With the increase of communication distance, the number of hops is increased, and the data transmission rate is significantly reduced. In addition, as the node density increases, the network load will be increased dramatically, these problems can therefore cause network congestion and channel interference to affect network throughput [5]. MRMC technology can solve these problems in wireless ad hoc networks, where the network nodes can use multiple orthogonal channels to communicate to reduce interference between the links. However, in practical applications, the number of available channels is often higher than the number of node interfaces, so how to allocate the channels to the RF interfaces is a key issue in using MRMC technology. An efficient channel allocation scheme is to assign the available channels to each link, the assignment criteria is to optimize network performance, e.g., to reduce the interferences between wireless links and packet loss, and to increase network throughput etc.

At present, there are lots of research results available on MRMC assignment. Typical channel allocation algorithms can be divided into three categories: static-, dynamic- and the mixed channel allocation algorithms [6]. Static channel allocation is to assign a channel to each RF interface, which remains unchanged. There are two types of static channel allocations: one is to assign the same channel to the radio interfaces of all the nodes, the benefit is to ensure the connectivity of the entire network, but it will have large inter-channel interference in the data transmission [7]. Another way is to assign different channels to the RF interfaces, which can reduce inter-channel interference in the network, but is more complicated than the first method. Dynamic channel allocation allows a RF interface to use any of the channels, and the RF interface can be switched from one channel to another at any time, but in order to maintain the connectivity of the network, any two nodes must negotiate before communication. In dynamic channel allocation, the inter-channel interference, throughput, link stability, transmission delay and other factors should be considered by the nodes, the assigned channels are required to be adjusted with any changes of network environment. Moreover, the implementation process is more complex, but dynamic channel allocation can enhance the flexibility and reliability of data transmission [8]. Mixed channel allocation is the combination of static and dynamic channel allocations, the node interfaces can switch the channels according to the changes of network environment and traffic loads etc.

This work is based on a project which supported by the Department of Science and Technology, State Grid, China. The motivation is to use 1.8 GHz with about 10–20 MHz bandwidth to form wireless mesh networks to be applied in small cities for transmission of the power distribution and utilization traffic. The key technology here is based on WiFi. The contribution of this work is that we proposed a multi-radio multi-channel (MRMC) assignment algorithm based on topology control and link interference weight for power distribution wireless mesh networks. The topology control is based on Kruskal algorithm to form the minimum spanning tree considering the nodes isolation by the buildings. The link interference weight in the algorithm is related to the load weight in the link where the load weight of a node is decided by the node level and the hops to the gateway. Finally the interference weights for the link are calculated for all the available channels, assign the concurrent link the channel which has the minimum interference weight.

2 Network Minimum Spanning Tree and Channel Allocation Algorithm

This work is based on the actual environment of the power distribution network in Dongying City, China, where the substation is served as a gateway, and the ring network cabinets, lighting poles are served as the static nodes to constitute the power distribution wireless mesh network which covers 3500 × 3000 m2 with 22 nodes in total, in which node 1 is served as the gateway as shown in Fig. 1, which is connected to the network control center by using optical fiber. Compared to those nodes in a wireless ad hoc network, the nodes in this power distribution network are normally static. Moreover, the nodes located in different streets are isolated by the buildings. In this paper, the algorithm proposed is for more universal wireless mesh ad hoc network, however we use the algorithm to solve an engineering issue for the power distribution network without thinking node mobility and the inter-connections among the nodes located in different streets.

Fig. 1
figure 1

Minimum spanning tree for the power distribution network

Full size image
  1. 1.

    Network Minimum Spanning Tree

The network minimum spanning tree is formed by the following steps:

  1. a.

    Based on the node distribution on the network topology, we assume that the communication distance between two adjacent nodes is 500 m, and the interference distance is 750 m, then the nodes with less than or equal to 500 m are connected to form a mesh network.

  2. b.

    The gateway node uses Kruskal algorithm to form the minimum spanning tree among the nodes based on the existing topology with the shortest path distance selection metric.

  3. c.

    Considering the special case in the power distribution network, in which the nodes are located at the road side of streets, they are isolated by the buildings. Therefore, the final minimum spanning tree is constructed as shown in Fig. 1

  4. 2.

    Channel Allocation Algorithm

To achieve a completely non-interference network links after channel allocations, in practice the number of channels required is often greater than the number of available channels, so we should find a suitable channel allocation scheme to minimize the interference in the entire network, but we should keep in mind to ensure that the whole network is connected first.

In this work, channel allocation is based on load weight calculation for each link, the load weight of a link is the sum of the load weights in its terminal nodes. A node load weight is related to its load weight coefficient which is decided by the node level and the hops between the node to gateway. The hops are fixed when the network topology is determined, in which we define that the hop number of the gateway is 0, the hop numbers of the other nodes are decided by the network minimum spanning tree as shown in Fig. 1. The less the hop number, the higher the node priority level (PL). The nodes which are close to gateway have to transmit more traffic, they have therefore more higher PLs. In this work, we use PL A to denote the level of node A, which is equal to the hop number of the node A to the gateway.

The load level of a node is only decided by whether the traffic from the other nodes to the gateway by way of it or not. Let’s assume that the load level of node A is r A , c is for the number of the nodes to transfer their traffic by way of node A to the gateway, then the load level of node A is calculated by

$$r_{A} = \sum\limits_{c = 1}^{N} {I_{c,A} }$$
(1)

where N is the total number of nodes in the network. When a node in the network transmits data by way of node A, I c,A is equal to 1, else it is 0.

The load coefficient of node A is calculated using the load level r A to divide by its PL, namely the hops [9]. In this paper, we define the hop number of the gateway is 0, then the load coefficient LC A of node A is calculated by

$$LC_{A} = \frac{{r_{A} + 1}}{{PL_{A} + 1}}$$
(2)

After calculation of all the load coefficients for the network nodes by (2), we can get load weight w A for node A by just normalizing all the load coefficients. The number of hops, load levels, load coefficients, and load weights for all the nodes in Fig. 2 are calculated and listed in Table 1. The load weight \(w_{{l_{AB} }}\) for link l AB between nodes A and B in the minimum spanning tree can be calculated as

$$w_{{l_{AB} }} = w_{A} + w_{B}$$
(3)

where w A and w B are the load weights for nodes A and B, respectively. Then all the links are sorted according to the link load weights from large to small values, if there are totally K available channels for all the links, they are assigned to the first K links with higher link load weights. After this, a link interference weight is calculated starting from the (k + 1)th link because we have assumed that the n available channels are orthogonal. The interference \(WD_{{e_{ij} ,k}}\) weight for link e ij and e uv at channel k can be expressed as

$$WD_{{e_{ij} ,k}} = \sum\limits_{{e_{ij} ,e_{uv} \in E,e_{ij} \ne e_{uv} }} {[I_{k} (e_{ij} ,e_{uv} )(w_{{e_{ij} }} + w_{{e_{uv} }} )]}$$
(4)

where I k (e ij , e uv ) is the interference between link e ij and e uv using the same channel k, \(w_{{e_{ij} }}\) and \(w_{{e_{uv} }}\) are the load weights for links e ij and e uv , respectively. Let the wireless network topology be expressed as an undirected graph C = {N, E}, where N is the node set, E is the link set. For nodes u, v ∊ N, if there is a communication link e uv  ∊ E, it means that nodes u and v can communicate to each other on the same channel within the transmission range. The communication condition between nodes u and v in the link e uv with channel k is expressed as

$$p_{uv} = \left\{ {\begin{array}{*{20}l} {k,} \hfill & {e_{uv} \in E} \hfill \\ 0 \hfill & {else} \hfill \\ \end{array} } \right.$$
(5)

where p uv represents the channel label assigned for link e uv . When e uv  ∊ E, assign channel kto link e uv , then p uv  = k.

Fig. 2
figure 2

Multi-radio multi-channel allocation scheme

Full size image
Table 1 Number of hops, load levels, load factors, and load weights for each node
Full size table

The potential link interference matrix QC of C = {N, E}, for ∀qc ij  ∊ QC can be calculated as

$$qc_{ij} = qc_{ji} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {i\;{\text{and}}\;j\;{\text{links}}\;{\text{interfere}}\;{\text{with}}\;{\text{each}}\;{\text{other}}} \hfill \\ 0 \hfill & {i\;{\text{and}}\;j\;\begin{array}{*{20}c} {{\text{links}}\;{\text{do}}\;{\text{not}}} \\ \end{array} \;{\text{interfere}}\;{\text{with}}\;{\text{each}}\;{\text{other}}} \hfill \\ \end{array} } \right.$$
(6)

For a multi-radio multi-channel wireless network, the link interference matrix QC obtained by (6) is a potential interference matrix, only two links using the same channel are the potential interference links in the network. By combining (5) and (6), the potential interference between e ij and e uv links can be calculated as

$$I(e_{ij} ,e_{uv} ) = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {QC(e_{ij} ,e_{uv} ) = 1\quad {\text{and}}\quad p_{ij} = p_{uv} \ne 0} \hfill \\ 0 \hfill & {\text{else}} \hfill \\ \end{array} } \right.$$
(7)

which means that there exists interference between links e ij and e uv if the links are assigned the same channel. For a particular channel k, (7) can be expressed as

$$I_{k} (e_{ij} ,e_{uv} ) = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {QC(e_{ij} ,e_{uv} ) = 1\quad {\text{and}}\quad p_{ij} = p_{uv} = k} \hfill \\ 0 \hfill & {\text{else}} \hfill \\ \end{array} } \right.$$
(8)

Finally we can use Eq. (4) to calculate the interference weight for link e ij using channel k, which is the sum of the load weights of the links which are within link e ij interference range, and they are assigned the same channel k (k = 1, 2, …, K), then assign a channel which is with the minimum interference weight to the current link. Repeat this work until all links are assigned with the available channels. Figure 2 shows multi-radio and multi-channel allocation scheme for the power distribution network in which we assume that there are five channels available in total, then the gateway is with four radios, and the rest nodes are with two radios except node 18 which has three radios. As a summary, the algorithm implementation steps for channel allocation are as follows:

  1. 1.

    Count the numbers of hops PL A for node A to the gateway based on the network minimum spanning tree;

  2. 2.

    Calculate Load level for each node by Eq. (1);

  3. 3.

    Calculate load coefficient for each node by Eq. (2);

  4. 4.

    Calculate load coefficient for each link by Eq. (3);

  5. 5.

    Calculate potential link interference matrix QC by Eq. (6);

  6. 6.

    Calculate potential interference I(e ij , e uv ) between links e ij and e uv using Eq. (7);

  7. 7.

    Calculate interference weight for link e ij and e uv at channel k using Eq. (4);

  8. 8.

    Assign a channel with the minimum interference weight to the concurrent link. Repeat this work until all links are assigned with the available channels.

3 Performance Evaluations

The NS2 platform is applied to evaluate the performance of the channel allocation schemes proposed in this paper. The network topology and channel allocations shown in Figs. 1 and 2 are set in NS2, respectively. The simulation parameters in NS2 are set as in Table 2. In order to evaluate our proposed channel allocation algorithm, two other typical algorithms are selected for the sake of comparison, namely CCA (Common Channel Assignment) and CHYA (Centralized Hyatinch) algorithms [10]. For simplicity, the algorithm proposed in this work is called ABC algorithm.

Table 2 Parameter configuration in NS2 simulation
Full size table

Figure 3 shows the average delays for the channel allocation algorithms with different traffic data rates, it can be seen that CCA algorithm is with largest delays, and our ABC algorithm is with the smallest ones. By increasing data transmission rates, the average delays of all the algorithms are increased first, after a specific data rate, they remain almost unchanged due to network capacity limitations. Therefore from the perspective of time delay, our ABC algorithm performance is much better than CCA and CHYA algorithms, especially in higher node data transmission rates. The reason behind is that the greater the transmission rate, the more severe interference between the links, our ABC algorithm can effectively reduce the interference, therefore it can improve its delay performance of the network.

Fig. 3
figure 3

Delay comparisons with different channel allocation algorithms

Full size image

Figure 4 shows the throughput for three algorithms with different data transmission rates, it can be seen that our proposed ABC and CCA algorithms are with the largest and smallest throughputs, respectively. By increasing data transmission rates, the throughputs are increased first for all the algorithms, but after the data rates being increased to a certain extent, the throughputs of all the three algorithms remain almost unchanged which is due to the channel has basically reached saturation. So from the perspective of throughput, our proposed ABC algorithm is much better than CCA and CHYA algorithms.

Fig. 4
figure 4

Throughput comparisons with different channel allocation algorithms

Full size image

Figure 5 shows the delay variations with the three different channel allocation algorithms for 1 Mbps data rate. It can be seen that the delays of our ABC algorithm with respect to time is much more stable and kept at small values, while the delays of the other two algorithms fluctuate greatly with larger values. Therefore, our proposed ABC algorithm is much better with respect to its delay variations with time.

Fig. 5
figure 5

Delay variations with different channel allocation algorithms for 1 Mbps data transmission rate

Full size image

4 Conclusion

In this paper, we propose a multi-radio multi-channel allocation algorithm based on topology control and link interference weight calculations for wireless mesh networks. The load weight for each link is the sum of the load weights of its terminal nodes. The load weight for a node is related to its load weight coefficient which is decided by the node level and the hops between the node to the gateway. Finally the interference weights for a link are calculated for all the available channels, assign the concurrent link the channel with minimum interference weight. Our proposed algorithm is compared with the common channel assignment algorithm (CCA) as well as the centralized Hyatinch algorithm (CHYA) by using NS-2 simulation platform. Simulation results show that our proposed algorithm is with smaller average delay and delay variations as well as larger throughput, therefore, its performance is much better than the two typical channel allocation algorithms available.

Note that in this paper we proposed a general MRMC allocation algorithm for wireless mesh networks, however our simulation work is for a project aimed to a practical power distribution network where the nodes are static, they are located at the roadsides of the streets and also isolated by the buildings between the streets.