# Link Interference and Route Length Based Dynamic Channel Allocation Algorithm for Multichannel Wireless Mesh Networks

Authors: Zhengping Li; Didi Zhang; Hao Shi
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In this paper, the theoretical analysis showed that the length of the route and the interference of links were the main factors that influence the throughput of the network. Then, a dynamic channel allocation algorithm base on the length of routes and the interference of links was proposed to enhance the system throughput. In the proposed algorithm, ant colony algorithm was used to collect the information of network, such as the length of routes and the interference of links. Then, the priority of link access channel was decided according to the collected information. The simulation results showed that the proposed algorithm could improve the whole network throughput obviously.


---

## Body

## 1. Introduction

Wireless mesh networks (WMNs), evolving from ad hoc network with comparative static characteristics, could be regarded as a wireless version of the Internet. WMN could also be involved into self-organizing network (SON) of mobile network to enhance the network performance. Compared with their wired counterparts, WMNs have a serious capacity limitation, and the interference is the primary factor that affects the capacity of the network. A multichannel WMN consists of a number of stationary wireless routers, where each route is equipped with multiple network interface cards. Usually, the number of radio interfaces is much more than the number of effective channel, which leads to the results that different and links among mesh routers and mesh clients to operate on the same channels. This case severely affects the network overall performance. Therefore, researchers had done great work with the purpose of improving the capacity of WMNs. [1, 2] proposed a centralized channel assignment concept called the first random channel assignment algorithm (FRCA). [3, 4] proposed a distributed channel allocation algorithm. [5, 6] proposed a traffic-aware channel assignment algorithm. [7] proposed multiple channel allocation algorithm basing on the link priority determined by the information of link interference and link services. [8, 9] proposed an ant colony intelligence-based dynamic channel allocation algorithm (ACI-DCA), but the algorithm was just adept to single-hop networks, not adept to multihop networks. There are only a few algorithms involving the channel allocation problem in multihop networks. [10] came up with a cross-layer channel allocation algorithm (CLCA), which considered not only the interference of route but also the connectivity of network, and it transmitted packets on route with least interference to others. In this paper, route interference and route length-based dynamic channel allocation algorithm was proposed to combat the interference in wireless mesh networks [11, 12]. The proposed algorithm requires the information of the network topology and the interference of the link and route. This information could be collected with the ant colony-based intelligent algorithm [8]. Since CLCA studied a similar problem with the proposed algorithm, the comparison was done between CLCA and the proposed algorithm.The rest of the paper was organized as follows. Section2 described the ant colony algorithm. Section 3 described the mathematical derivation of the algorithm. Section 4 described the channel allocation algorithm. Section 5 showed the simulation results. Finally, in Section 6, a simple conclusion was given.


## 2. Ant Colony Intelligence Algorithm

Ant colony intelligence algorithm was developed by Dr. Eberhart and Kennedy. In this paper, the ant colony intelligence algorithm was modified to collect the information of the whole networks. The core idea of the ant colony intelligence algorithm was that the ant packet migrated through all the nodes in the networks as soon as possible and collect the information of the network. According to the information of the ant packet collected, some wise decisions were made to improve the performance of the network.The ant packets were generated by the nodes in the network with a node selection algorithm. Each node generated a random numberZi following uniform distribution between the interval a,b, and i denoted the node ID. That was Zi~Ua,b;i=nodeID. If Zi was smaller than a threshold number TH, this node would generate an ant packet. TH must be within the interval a,b and could be used to control the number of ant packets in the networks. The larger of TH, the more of ant packets would be generated in the networks. After generating the ant packets, the packets would be forwarded in the networks as follows.An ant packet started from nodei and was passed to node i’s neighbors. The ant packet was passed to the neighbor nodes which had been passed by ant packets with least times. If more than one neighbor node had the same least passing times, a neighbor node was randomly selected to passing the ant packet. According to the above rules, when the ant packets were transmitted in the network, they collected the information of the nodes, for example, service volume information, the interference links, and the hops of the route passed the link and some other important information. If two ant packets passed the same nodes, they could exchange the collected information through the buffer on the nodes. This process helped the ant packet passed nodes to know the whole network’s information which was employed to make channel allocation.


## 3. Mathematical Analysis

According to the information of the network, letS denoted the whole network’s throughput. i denoted the link ID and j represented the route of network, and it equaled to the integer from 1 to N, and n was the number of links in the networks. C denoted the total number of available channels. M was the number of routes in the networks.
(i)
τi indicated the number of the channels occupied by link i(ii)
Si indicated the throughput of link i(iii)
Ii denoted the interference link set of link i(iv)
gi denoted the number of the interference links of link i(v)
Ri represented the set of the route through link i(vi)
αi represented the number of elements in the set Ri(vii)
Qi represented the set of links passed by route j(viii)
δij indicated the number of channels occupied by the services of route j on link i(ix)
Gj indicated the sum of the interference links of all the links passed by route j(x)
Θ indicated the mean value of the interference links of the links in the network(xi)
qi indicated the channel accessing probability of link i(xii)
φj indicated the service success transmission probability of route j(xiii)
Hj indicated the number hops of route j(xiv)
Hmax and Hmin indicated the maximum and the minimum hops of route of the routes in the networks, respectively(xv)
Di indicated the mean number of hops of the routes passing link i(xvi)
Fi indicated the mean number of interference links of the routes passing link iSupposing every link had enough services at timet, the number of available channels was not enough, so if link i did not occupy the idle channel, the channel would be occupied by other links in Ii (hypothesis ①).So(1)S=∑i=1NSi.Supposing each channel transmits one packet in per time unit. Then, the networks’ throughput could also be denoted with the sum of the number of the occupied channels.(2)S=∑i=1Nτi.According to hypothesis ①,τi could be denoted with Ii,
(3)τi=fIi=N−∑k∈Iiτk.According to equations (2) and (3),
(4)S=C∗N−∑k∈I1τk+⋯+∑k∈Iiτk+⋯+∑k∈INτk.Let(5)S′=∑k∈I1τk+∑k∈I2τk+⋯+∑k∈Iiτk+⋯+∑k∈INτk.Then(6)S=C∗N−S′.S′ was the total number of channels occupied by all the interference links of each link. Let the number of interference links of link i be gi. So τi would appear gi times. Then S′ could be reorganized as follows.
(7)S′=∑i=1Ngiτi.Supposingg1~gN was arranged in the order from small to large (hypothesis ②).Extracting ag1S from S′, then
(8)S′=g1S+g2−g1τ2+⋯+τN+gi−gi−1τi+⋯τN+⋯+gn−gn−1τN.Since(9)gi−gi−1τi+⋯+τN=gi−gi−1S−τ1−⋯−τi−1.Then equation (8) was simplified as
(10)S‘=g1S+g2−g1S−τ1+⋯+gi−gi−1S−τ1+⋯+τi−1+⋯+gN−gN−1S−τ1−⋯−τN−1.Extractinggi−gi−1S2≤i≤N(11)S′=g1+g2−g1+⋯+gi−gi−1+⋯+gN−gN−1S−g2−g1τ1+⋯+gi−gi−1τ1+⋯+τi−1+⋯+gN−gN−1τ1+⋯+τN−1.Then equation (11) makes further simplifying
(12)S′=gNS−g2−g1τ1+⋯+gi−gi−1τi+⋯+gN−gN−1τN−1.Then according to equations (6) and (12), the following formula could be gotten.
(13)1+gNS=C∗N+gN−g1τ1+⋯+gN−giτi+⋯+gN−gN−1τN−1.Supposing the service would be successfully transmitted to the terminal (hypothesis ③).Then(14)τi=∑j∈Riδij.According to equations (13) and (14), the following formula could be gotten.
(15)1+gNS=C∗N+gN−g1∑j∈R1δ1j+⋯+gN−gi∑j∈Riδij+⋯+gN−gN−1∑j∈RN−1δij.Links forward the services of the same route are equal, that was(16)δi1j=δi2ji1,i2∈Qj.According to equations (15) and (16), the following formula could be gotten.
(17)1+gNS=C∗N+∑i∈Q1gN−giγ1+⋯+∑i∈QjgN−giγj+⋯+∑i∈QMgN−giγM.Since the number of element in the setQj was Hj. So equation (17) was simplified as follows.
(18)1+gNS=C∗N+H1gN−∑i∈Q1giγ1+⋯+HjgN−∑i∈Qjgiγj+⋯+HMgN−∑i∈QMgiγM.The above formula could be further simplified(19)1+gNS=C∗N+gN∑j=1MHjγj−∑j=1M∑i∈Qjgiγj.According to hypothesis ③, the following formula could be gotten.(20)S=∑j=1MHjγj.According to equations (19) and (20), the following formula could be gotten.
(21)S=C∗N−∑j=1M∑i∈Qjgiγj.According to equation (21), the expectations of the throughput could be expression as follows.
(22)ES=C∗N−∑j=1M∑i∈QjEgiγj.Since the nodes were uniformly distributed in the networks, the following formula would get:(23)θ=Egj=Egi1≤i,j≤N.SinceHj indicates the number of hops of route j.
(24)∑i∈QjEgi=Ljθ1≤j≤M.Then, according to equations (22) and (24), the following formula could be gotten.
(25)ES=C∗N−θ∗∑j=1MHjγj.SinceGj=∑i∈Qjgi, the following formula could be gotten from equation (21).
(26)S=C∗N−∑j=1MGjγj.Supposing the links and it interference links access channel with equal probability (hypothesis ④).Then linki access channel probability could be denoted as follows.
(27)qi=1gi.According to equation (27), the route j success transmission service probability could be denoted as follows.
(28)φj=∏i∈Qjqi=∏i∈Qj1gi.According to equations (23) and (28), the expectations of the φj could be expressed as follows.
(29)Eφj=∏i∈Qj1Egi=∏i∈Qj1θ.Since the number of element in the setQjwas Lj. So equation (29) was simplified as follows.
(30)Eφj=1θLj.According to equation (30), the conclusion could be drawn that the shorter the route, the higher the service success transmission probability.Di indicated the mean number of hops that decided link i’s priority, Fi indicated the mean number of interference links of the routes passing link i. So if the number of elements in the set Ri was one, then, the following formula could be gotten.
(31)Di=Hii∈Ri,(32)Fi=Gii∈Ri.Supposing the linki was occupied by multiple routes, and αi represented the number of elements in the set Ri. So, the following formula could be gotten.
(33)Di=∑β∈RiHβαi,(34)Fi=∑β∈RiGβαi.When the network topology was fixed,g1~gN, H1~HM, N, M, and C were constant. From equation (25), conclusions could be drawn that the routes with smaller hops had a higher influence on whole network’s throughput. From equation (26), the conclusion could be drawn that the routes with less interference links had a higher influence on the whole network’s throughput. Since the shorter the route, the higher the service success transmission probability, the channel allocation algorithm should choose the links with shorter route access channel with higher priority, and let the links in route with lower interference access channel with larger probability, which was a benefit to improve the throughput of network.


## 4. The Principle of Channel Allocation

### 4.1. The Principle of Channel Allocation

According to the information of the network, such as the length of route, the interference of links, and the interference of the routes, links were assigned with different priority as follows:(1)
The smaller ofDi, the higher priority of link i. If Dx1=Dx2, it would be gotten that the link x1 and the link x2 had the same priority value. This was defined as primary priority value(2)
Among the links with the same primary priority value, the links with lesser interference links had a higher priority value. This was defined as the secondary priority value(3)
Among the links with the same primary and secondary priority value, the links with larger service had a higher priority value. This was defined as the third priority valueConsidered the factors that the channel assigned with greedy algorithm which would cause the congestion in the network and increase the end-to-end delay, the routes with less interference links had a higher influence on the whole network’s throughput, and the following algorithm was proposed to solve the problem.Gmax and Gmin denoted the maximum and the minimum value of the Gj, respectively, and Hmax and Hmin indicated the maximum and the minimum hops of the routes in the networks, respectively. Zi indicated the set of the routes with hop i, and ∂i indicated the element number of Zi. ICi indicated the idle channels for link i. Then defined two interference threshold Td1=∑i∈ZHmin+2Gi/∂Hmin+2, if the route with hops Hmin+2 was not existence then replace it with hops Hmin+1, in the same way, until the hops was Hmin and Td2=∑i∈ZHmin+4Gi/∂Hmin+4underassumptionthatHmin+4<Hmax, if the route with hops Hmin+4 was nonexistence then replace it with hops Hmin+3, in the same way, until the hops was Hmin. A random value Rdijj∈ICi for each idle channel of link i was generated following the uniform distribution from 0 to 1 to determine whether link i access channel jj∈ICi. Pt1 and Pt2 were two channel access threshold values. Pt1 and Pt2 were gotten with the following formulas.
(35)Pt1=Gmax−Td2Gmax−Gmin,(36)Pt2=Gmax−Td1Gmax−Gmin.Ui indicated the number of available channels that could be occupied by link i, and Iqijx was a indicative function of the set Rdij. So how many channels could be occupied by link i was shown as follows.
(37)Ui=∑j∈IiIRdijRdij≤Pt1Gmin<Fi≤Td1,∑j∈IiIRdijPt1<Rdij≤Pt2Td1<Fi≤Td2∑j∈IiIRdijPt2<RdijTd2<Fi≤Gmax.,


### 4.2. The Process of Channel Allocation

At the beginning of the simulation, nodes in the network randomly generated a certain number of ant packets. The ant packets rambled in the network and collected information of the number of interference links, number of routes’ hops, and the amount of service. Then, the nodes who got the information determined the priority of the link according to the collected information. The priority was updated upon the information updating by the ant packets. First, the priority values of the links were nearly zeros, links occupied idle channels if available, and there was no regulation for channel occupancy. Then, after a period of time, the link that had been passed by the ant packets would have updated priority values. Each link occupied channels according to the steps shown in Figure1.Figure 1
Channel allocation process of link.


## 4.1. The Principle of Channel Allocation

According to the information of the network, such as the length of route, the interference of links, and the interference of the routes, links were assigned with different priority as follows:(1)
The smaller ofDi, the higher priority of link i. If Dx1=Dx2, it would be gotten that the link x1 and the link x2 had the same priority value. This was defined as primary priority value(2)
Among the links with the same primary priority value, the links with lesser interference links had a higher priority value. This was defined as the secondary priority value(3)
Among the links with the same primary and secondary priority value, the links with larger service had a higher priority value. This was defined as the third priority valueConsidered the factors that the channel assigned with greedy algorithm which would cause the congestion in the network and increase the end-to-end delay, the routes with less interference links had a higher influence on the whole network’s throughput, and the following algorithm was proposed to solve the problem.Gmax and Gmin denoted the maximum and the minimum value of the Gj, respectively, and Hmax and Hmin indicated the maximum and the minimum hops of the routes in the networks, respectively. Zi indicated the set of the routes with hop i, and ∂i indicated the element number of Zi. ICi indicated the idle channels for link i. Then defined two interference threshold Td1=∑i∈ZHmin+2Gi/∂Hmin+2, if the route with hops Hmin+2 was not existence then replace it with hops Hmin+1, in the same way, until the hops was Hmin and Td2=∑i∈ZHmin+4Gi/∂Hmin+4underassumptionthatHmin+4<Hmax, if the route with hops Hmin+4 was nonexistence then replace it with hops Hmin+3, in the same way, until the hops was Hmin. A random value Rdijj∈ICi for each idle channel of link i was generated following the uniform distribution from 0 to 1 to determine whether link i access channel jj∈ICi. Pt1 and Pt2 were two channel access threshold values. Pt1 and Pt2 were gotten with the following formulas.
(35)Pt1=Gmax−Td2Gmax−Gmin,(36)Pt2=Gmax−Td1Gmax−Gmin.Ui indicated the number of available channels that could be occupied by link i, and Iqijx was a indicative function of the set Rdij. So how many channels could be occupied by link i was shown as follows.
(37)Ui=∑j∈IiIRdijRdij≤Pt1Gmin<Fi≤Td1,∑j∈IiIRdijPt1<Rdij≤Pt2Td1<Fi≤Td2∑j∈IiIRdijPt2<RdijTd2<Fi≤Gmax.,


## 4.2. The Process of Channel Allocation

At the beginning of the simulation, nodes in the network randomly generated a certain number of ant packets. The ant packets rambled in the network and collected information of the number of interference links, number of routes’ hops, and the amount of service. Then, the nodes who got the information determined the priority of the link according to the collected information. The priority was updated upon the information updating by the ant packets. First, the priority values of the links were nearly zeros, links occupied idle channels if available, and there was no regulation for channel occupancy. Then, after a period of time, the link that had been passed by the ant packets would have updated priority values. Each link occupied channels according to the steps shown in Figure1.Figure 1
Channel allocation process of link.


## 5. Result Analysis

### 5.1. Simulation Parameter

The important simulation parameters were shown in Table1.Table 1
The simulation parameters.
node_positionNode position, including horizontal and vertical coordinates, values are generated randomly.network_rangeThe size of network, the upper limit of horizontal and vertical coordinatesnode_numberThe number of communication nodes in networkP2P_numberThe number of P2P serviceServer_numberThe number of servers of FTP serviceClient_numberThe number of clients of each FTP server.node_coverageIndicates communication and interference radius of nodes.In the practical WMNs, the interference radius is usually longer than the communication radius. For simplicity in the simulation, supposed the interference radius is equal to the communication radius in the simulation. network_range was 500, node_coverage was 50, node_number was 100, and node_position was generated by function rand, multiplied by network_range, obtaining the horizontal and vertical coordinates. Calculating the Euclidean distance,distance=x1−x22+y1−y22, comparing with node_coverage, obtaining the neighbor relationship of nodes. According to the neighbor relationship of nodes, the links and the interference relationship among links were built. Randomly choose nodes as the peers of P2P services, servers, and clients of FTP services. Then, routes were established with the shortest path routing algorithm. In the simulation, the P2P services were transmitted at constant rate, and the FTP services were transmitted based on TCP.


### 5.2. Simulation Results

In order to validate the algorithm, we carried out simulation with Matlab. Randomly choose nodes as the peers of P2P services and FTP services. Then, routes were established with the shortest path routing algorithm. In the first scenario, the P2P services were transmitted at constant rate, the FTP services were transmitted based on TCP, and the pairs of nodes with P2P service were increased. As shown in Figure2, the throughput of the proposed algorithm was higher than the CLCA algorithm. As Figure 3 shows the packet lost ratio of the proposed algorithm was lower than the CLCA algorithm. Since, the short routes had a much higher packet successful transmit probability than the long routes, and the links with low interference accessed channel with high probability which was a benefit to reduce the interference of the network. Therefore, the proposed algorithm decreased interference and inclined the end-to-end delay.Figure 2
Relationship between P2P services number and throughput.Figure 3
Relationship between P2P services number and packet loss rate.In the second scenario, the nodes as the peers of P2P services are constant, the FTP services were transmitted based on TCP, and the P2P packet generating rate was 0.2 packet per simulation time and was gradually increased later. As the simulation results in Figure4 shows that the throughput of the two algorithms increases rapidly with the packet generating rate, and the proposed algorithm increased faster than the CLCA algorithm. However, the throughput tended to decrease after reaching the peak point with the increase of the packet generating rate. Since, with the increase packet generating rate the congestion of the network is much more serious, which increase the end-to-end delay and much more packet data would be a loss. As shown in Figure 5, the packet loss ratio was increased with the packet generating rate, and the packet loss ratio of the proposed algorithm was lower than the cross-layer channel allocation algorithm.Figure 4
Relationship between packet generating rate and throughput.Figure 5
Relationship between packet rate and packet loss rate.


## 5.1. Simulation Parameter

The important simulation parameters were shown in Table1.Table 1
The simulation parameters.
node_positionNode position, including horizontal and vertical coordinates, values are generated randomly.network_rangeThe size of network, the upper limit of horizontal and vertical coordinatesnode_numberThe number of communication nodes in networkP2P_numberThe number of P2P serviceServer_numberThe number of servers of FTP serviceClient_numberThe number of clients of each FTP server.node_coverageIndicates communication and interference radius of nodes.In the practical WMNs, the interference radius is usually longer than the communication radius. For simplicity in the simulation, supposed the interference radius is equal to the communication radius in the simulation. network_range was 500, node_coverage was 50, node_number was 100, and node_position was generated by function rand, multiplied by network_range, obtaining the horizontal and vertical coordinates. Calculating the Euclidean distance,distance=x1−x22+y1−y22, comparing with node_coverage, obtaining the neighbor relationship of nodes. According to the neighbor relationship of nodes, the links and the interference relationship among links were built. Randomly choose nodes as the peers of P2P services, servers, and clients of FTP services. Then, routes were established with the shortest path routing algorithm. In the simulation, the P2P services were transmitted at constant rate, and the FTP services were transmitted based on TCP.


## 5.2. Simulation Results

In order to validate the algorithm, we carried out simulation with Matlab. Randomly choose nodes as the peers of P2P services and FTP services. Then, routes were established with the shortest path routing algorithm. In the first scenario, the P2P services were transmitted at constant rate, the FTP services were transmitted based on TCP, and the pairs of nodes with P2P service were increased. As shown in Figure2, the throughput of the proposed algorithm was higher than the CLCA algorithm. As Figure 3 shows the packet lost ratio of the proposed algorithm was lower than the CLCA algorithm. Since, the short routes had a much higher packet successful transmit probability than the long routes, and the links with low interference accessed channel with high probability which was a benefit to reduce the interference of the network. Therefore, the proposed algorithm decreased interference and inclined the end-to-end delay.Figure 2
Relationship between P2P services number and throughput.Figure 3
Relationship between P2P services number and packet loss rate.In the second scenario, the nodes as the peers of P2P services are constant, the FTP services were transmitted based on TCP, and the P2P packet generating rate was 0.2 packet per simulation time and was gradually increased later. As the simulation results in Figure4 shows that the throughput of the two algorithms increases rapidly with the packet generating rate, and the proposed algorithm increased faster than the CLCA algorithm. However, the throughput tended to decrease after reaching the peak point with the increase of the packet generating rate. Since, with the increase packet generating rate the congestion of the network is much more serious, which increase the end-to-end delay and much more packet data would be a loss. As shown in Figure 5, the packet loss ratio was increased with the packet generating rate, and the packet loss ratio of the proposed algorithm was lower than the cross-layer channel allocation algorithm.Figure 4
Relationship between packet generating rate and throughput.Figure 5
Relationship between packet rate and packet loss rate.


## 6. Conclusion

In this paper, a dynamic channel allocation algorithm base on the length of routes and the interference of the links was proposed to reduce the effects of interference. In the algorithm, the links with the shorter route and less interference links had a higher priority to access channels, which was a benefit to reduce the packet loss ratio caused by end-to-end delay. The links with less interference links accessing channel with the higher probability, which was helpful to reduce the effects of interference and improved the throughput of the network. According to the mathematical analysis and the simulated results, the performance of the proposed algorithm was better than the CLCA algorithm.With the high-speed development of the wireless communication, the future wireless networks would be layered and heterogeneous. How to allocation the channel in layered heterogeneous network would be investigated further.



---

*Source: 8038588-2021-06-25.xml*