Partially overlapped channels (POCs)-based design has been identified recently as an emerging technology to further eliminate interference and improve network capacity. However, there are only few studies of channel assignment algorithms for POCs. In this paper, we research on utilizing POCs to improve network capacity and propose a traffic-irrelevant channel assignment algorithm, which assigns channels for all links in the network while minimizing total network interference. Theoretical calculation approach is utilized to obtain the direct relationship between interference ranges and channel separations, which can be easily applied to mesh networks with various configurations without modification. As traffic between the Internet and clients is considered to be dominant, distance from the gateway, number of neighbors, and interference are used to determine the channel assignment order of links. Simulation results reveal that network throughput and end-to-end delay performance can be dramatically improved by fully exploiting POCs as well as orthogonal channels.
Hinweise
Competing interests
The authors declare that they have no competing interests.
1 Introduction
Wireless mesh networks (WMNs), which can extend the coverage of current wireless networks, draw close attention from academic community and industry in recent years [1]. WMNs are composed of three types of nodes: mesh clients, mesh routers, and gateway nodes [2,3]. Mesh clients are user equipment, such as PC and mobile phone. Mesh routers, with the access and relay function, form the mesh backbone and connect mesh clients with the gateway nodes. Gateway nodes are special kinds of mesh routers with the function of bridging, and they connect the whole mesh networks with external networks, such as the Internet.
Capacity is a major concern in WMNs, and its decay with increased interference is very fast. An approach to alleviate this problem is to allow the networks to use multiple channels and equip each node with multiple radio interfaces (MRMC). However, MRMC cannot fundamentally solve the problem; the reason is that traditional communication system designs emphasize on orthogonality and assign orthogonal channels to parallelly transmitting nodes in close proximity. Orthogonal channels (OCs) refer to channels that have no overlap with each other in the frequency domain, namely, the minimum channel separation between OCs is 5. Therefore, in IEEE 802.11b/g, only three channels are orthogonal, namely, 1, 6, and 11. It is often unavoidable to assign neighboring nodes with the same channel due to the limited number of OCs. The resulting co-channel interference prevents these nodes from parallel transmissions and leads to reduction in network throughput. Channels that partially overlap with each other in the frequency domain are referred to as partially overlapped channels (POCs). For example, channel 2 and channel 4 in Figure 1 are POCs, with channel separation 2. Traditional communication system designs treat POCs as a peril because the adjacent channel interference among POCs significantly affects the normal communication between nodes. However, rapid advancement of software defined radio and cognitive radio makes the interference control problem of POCs easily solvable, and nodes can select channels based on their local observations [4]. Efficient utilization of POCs allows significant enhancement in parallel transmissions and overall network throughput.
Figure 1
IEEE 802.11b/g frequency spectrum diagram.
×
Anzeige
Since the opinion that POCs utilization can lead to better utilization of the spectrum and throughput improvement was proposed by Arunesh Mishra [5], there have been growing interests in exploiting POCs to improve network performance, and the focus is mainly on exploiting partially overlapped channel assignment to reduce interference. Partially overlapped channel assignment can be divided into multicast partially overlapped channel assignment [6-11] and unicast partially overlapped channel assignment [12-19] according to service types. In this paper, we research on unicast partially overlapped channel assignment problem. The unicast partially overlapped channel assignment schemes published have at least one of the limitations listed as follows. (1) Most of them are traffic-relevant load-aware channel assignment schemes which only assign channels for links that carry data flows, when load changes in the network, channel assignment for links should update accordingly. Thus, they do not adapt to load changes. (2) Traffic between the Internet and mesh clients is considered only, and traffic between clients (peer-to-peer traffic) is omitted, or vice versa. At present, people want to access the Internet and get service from it, so the traffic between the Internet and mesh clients is dominant. As newly emerging applications get popular, there may be substantial random and unpredictable traffic caused by peer-to-peer traffic. As a result, these two traffic types will co-exist in WMNs. (3) Current partially overlapped channel assignment schemes obtain interference ranges through field measurement, but field measurement is usually conducted with specific network configuration; thus, there is no fixed relationship between interference ranges and channel separations, which leads to weak transportability of the measurement results [20].
In order to conquer the limitations of current partially overlapped channel assignment schemes, a channel assignment algorithm which assigns channels to each link in the network with the goal of minimizing total interference while maintaining network connectivity is proposed. The main contributions of this work are as follows:
(1)
Traffic-irrelevant channel assignment scheme is utilized to assign channels for all links in the network before carrying data flows which can avoid the weakness of load-aware channel assignment.
(2)
Traffic between the Internet and clients and peer-to-peer traffic are both considered as they will co-exist in WMNs in the future, where traffic between the Internet and clients is dominant.
(3)
Theoretical calculation approach is used to obtain interference ranges which can avoid weak transportability of interference ranges obtained by field measurement.
2 Related work
In general, partially overlapped channel assignment schemes published can roughly be classified into two types: one is traffic-relevant load-aware channel assignment schemes [12-15], which assume a known traffic profile in the network or pre-determined route paths for flows, therefore load on each link is known before performing channel assignment. The task is to compute a channel assignment scheme, such that the load can be delivered in time. The other is traffic-irrelevant channel assignment schemes [16-18], 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 overlapped channel assignment for scenarios in the absence of information exchange. For example, a graphical game and uncoupled learning-based distributed partially overlapped channel selection is proposed in [19], which is different from our proposed algorithm as ours is centralized for easy implementation.
For load-aware channel assignment schemes, the assumptions made on traffic load actually determine which links should be assigned a channel, and more importantly, for channel assignment algorithms that utilize traffic load to sort links, it determines in which order the channel assignment should occur. However, load on each link is difficult to predict in practice, and the channel assignment may not be suitable when load changes and may need to update accordingly.
Anzeige
For traffic-irrelevant channel assignment schemes, they are operated before any data flow transmissions in the network and assign channels for all links in the network, so there is no load on each channel/link when operating the scheme, and no matter where the sources and destinations of flows transmitted later in the network, the channel assignment for links has no need to change. Traffic-irrelevant channel assignment scheme helps avoid inadaptation to load changes of traffic-relevant channel assignment schemes.
Authors in [16,17] proposed a greedy partially overlapped channel assignment algorithm with consideration on dynamic traffic. Aiming at solving the problem that traditional conflict graph cannot model interference among POCs, an innovative weighted conflict graph is proposed. The edge weight in the weighted conflict graph represents the minimum channel separation that two links must have so that they will not interfere with each other. Partially overlapped interference graph is used to model interference between links in [18] which is essentially the same as weighted conflict graph in nature. The objective of the formulated channel assignment problem is to minimize the total number of interfering link pairs or minimize the maximum link interference. The greedy algorithm is a series of decisions, and each decision is composed of two steps - select and assign. In the select step, a link that has not been assigned a channel is chosen according to metric α(s), and in the assign step, a proper channel is assigned to the selected link according to metric β(c). Metrics α(s) and β(c) are shown in Equations 1 and 2, respectively:
where the first item denotes the total interference between link s and other links that have been assigned a channel, and the second item denotes the expected interference between link s and other links that have not been assigned a channel yet:
The following problems may exist in the above greedy partially overlapped channel assignment algorithm: (1) Interference ranges are obtained by field measurement; (2) When deciding channel assignment order, the algorithm gives higher priority to the link that has minimum expected interference with other links, but if there are several links whose expected interference values are equivalent, how to break the tie is still unknown; (3) If several channels all satisfy the minimum interference requirement, random channel selection may not yield good performance; and (4) The algorithm assumes that WMNs have dynamic traffic, that is, the connection demands have random sources, destinations, and arrival times, i.e., peer-to-peer traffic is dominant. From the analysis above, we conclude that a traffic-irrelevant channel assignment scheme which takes two types of traffic into consideration and gets interference ranges without using field measurement is still in need. In the following, we present our partially overlapped channel assignment (POCA) algorithm.
3 Interference model
In this paper, we are targeting at infrastructure mesh networks which is the most commonly used form of WMNs. Mesh clients are connected to the nearest mesh routers within one-hop distance, and multi-hop transmissions are limited among mesh routers. As the performance of WMNs is mainly decided by its backbone network, clients are usually ignored and the corresponding access routers are considered instead [21,22]. We assume that all mesh routers are stationary, which is reasonable in WMNs. Our algorithm is applied to mesh backbone, and our target is optimizing links between mesh routers, i.e., relay links. We use node and mesh router interchangeably in this paper.
The interference model proposed in [23] is used to model inference among links in this paper, i.e., let R′′(τ) be the interference range of two links e1=(u1,v1) and e2=(u2,v2) with channel separation τ, they will interfere with each other if their distance is less than R″(τ), and otherwise not. We define a binary variable I(e1,e2,τ) to represent this relationship, as shown in Equation 3:
where d(e1,e2) is the distance between links e1 and e2, which is defined as the minimum distance between any node of link e1 and any node of link e2, that is:
For a directed link, if its receiving endpoint wants to successfully receive a packet from the sending endpoint, it requires that no third node located within the interference range of the receiving endpoint is transmitting. In this case, interference is not symmetric. However, in this paper, our algorithm tries to find a traffic-irrelevant channel assignment for all links in the network, thus links between nodes are considered as undirected. Also, before a channel assignment is known, the actual interference of links is unknown, thus we use the symmetric interference model in Equation 3 to comply with IEEE 802.11-style MAC protocol and guarantee successful communication over an undirected link, i.e., the sending endpoint is also required to be free of interference as it needs to receive the link layer acknowledgement from the receiving endpoint. In a word, successful communications over a link require that any node which is within the interference range of these two endpoints of the link should not be transmitting.
In this paper, we exploit theoretical calculation approach to obtain R′′(τ). For the simplicity of discussion, we assume an open-space environment, in which the path loss of a signal is modeled by two-ray ground propagation model [24], the received power of a signal is given by:
where Pt is the transmission power at the sender, Gt and Gr are the antenna gains of the sender and receiver, respectively, ht and hr are the height of both antennas, d is the distance between the sender and the receiver, and k is the path loss parameter whose value is typically between 2 and 4.
To sense the status of a specific channel, the received power at the receiver on the same channel should be above a carrier sensing threshold CSth, thus we have:
$$ P_{r} \geq \text{CS}_{\text{th}} $$
(6)
Interference range is the distance up to which transmission from a node will interfere with others, and the co-channel interference range can be calculated from Equations 5 and 6 as below:
$$ R^{\prime} = d = \root k \of {\frac{{P_{t} \cdot G_{r} \cdot G_{t} \cdot {h_{t}^{2}} \cdot {h_{r}^{2}} }} {\text{CS}_{\text{th}}}} $$
(7)
When using POCs, only a fraction of a signal’s power on channel j can be received on channel i; the fraction depends on the extent of overlap between channels i and j, which is denoted by od(i,j) in this paper, so we have:
We define Irrr(τ)=od(i,j)k as the reduced interference range ratio, which is normalized to a scale of [ 0,1] and is used to describe the reduction in interference range observed on adjacent channel due to the utilization of POCs, where τ=|i−j|. od(i,j) can be obtained through theoretical calculation:
where PSD(f) denotes the signal’s power distribution across the frequency spectrum, i.e., the power spectrum density. If the transmitted signal’s power distribution has the exact form of the transmit spectrum mask, the PSD(f) is as follows:
The calculated reduced interference range ratio Irrr(τ) corresponding to different channel separations under path loss parameter 4 is shown in Table 1.
Table 1
Reduced interference range ratios for ideal spectrum mask
τ
0
1
2
3
4
5
6
7
8
≥9
Irrr(τ)
1
0.9376
0.8596
0.7515
0.5505
0.1714
0.1588
0.1422
0.1161
0
For arbitrary configuration on transmission power Pt and antenna, the co-channel interference range R′ can be obtained from Equation 7, and the interference range observed on channel with a separation of τ is R′′(τ)=Irrr(τ)×R′. The assumption that transmission power of all nodes in WMNs should be configured to the same value can be removed. On the use of raised cosine filter, the reduced interference range ratios corresponding to different channel separations are related to roll-off factor, as shown in Tables 2, 3, and 4. As the value range of Irrr(τ) is [ 0,1], Irrr(τ) becomes larger and larger as k increases.
Table 2
Reduced interference range ratios for raised cosine filter with roll-off factor 1
k=2
τ
0
1
2
3
4
≥ 5
Irrr(τ)
1
0.7512
0.4800
0.2246
0.0354
0
k=3
τ
0
1
2
3
4
≥ 5
Irrr(τ)
1
0.8264
0.6131
0.3695
0.1079
0
k=4
τ
0
1
2
3
4
≥ 5
Irrr(τ)
1
0.8667
0.6928
0.4739
0.1882
0
Table 3
Reduced interference range ratios for raised cosine filter with roll-off factor 0.5
k=2
τ
0
1
2
3
≥ 4
Irrr(τ)
1
0.7355
0.3741
0.0442
0
k=3
τ
0
1
2
3
≥ 4
Irrr(τ)
1
0.8148
0.5192
0.1250
0
k=4
τ
0
1
2
3
≥ 4
Irrr(τ)
1
0.8596
0.6116
0.2103
0
Table 4
Reduced interference range ratios for raised cosine filter with roll-off factor 0.25
The proposed POCA algorithm is composed of two steps: neighbor-to-interface binding and interface-to-channel binding. The neighbor-to-interface binding determines the connection relationship among nodes, that is, through which interface a node communicates with its neighbor; the interface-to-channel binding determines which channel an interface should use according to certain order with the goal of minimizing total network interference.
4.1 Neighbor-to-interface binding
In the neighbor-to-interface binding step, the node degree is computed based on the neighboring relationship in physical topology. Nodes with higher degree should avoid sharing interface with other neighbors as possible, as higher degree means more neighbors and more flows going through the node. Links that share the same interface should be treated as a whole when assigning channels.
4.2 Interface-to-channel binding
In the interface-to-channel binding step, the channel assignment order of links should be determined first, which is achieved by sorting links in ascending order using the expected interference level (EIL) defined in Equation 12, where Al is a set of links that have already been assigned a channel. If there exist several links whose EIL are equivalent, the Rank defined in Equation 13 is used to break the tie. For link l, n(l) is the number of neighbors which is defined as the number of neighboring nodes for either of the two endpoints. h(l) is the minimum hop count distance from the gateway which is defined as the average taken over the minimum hop count distance from the gateway for the two endpoints. More neighbors means higher probability of being selected as next hop by many data flows. As traffic between the Internet and clients is dominant in MRMC WMNs, links near the gateway (i.e., with less hop count distance from the gateway) are inevitably on paths to the Internet. In this case, there is higher probability of incurring congestion at these links. Therefore, Rank (l) can be regarded as quantitative representation of link congestion probability, and link with larger Rank value is more likely to become capacity bottleneck; thus, it should be given higher priority to be assigned with a proper channel.
The proposed algorithm utilizes reduced interference range ratio to quantify interference degree between POCs. When selecting proper channel for link l, the sum of interference between link l and other links that have already been assigned a channel, namely, the total network interference Intertot, is calculated for each candidate channel, and the one with the minimum value of total network interference will be assigned to link l, which can avoid the drawback of random channel selection in [16,17]:
where ir(p,l) denotes the channel interference ratio between links p and l; Al denotes set of links that have already been assigned a channel; R′′(τ) denotes the reduced interference range observed on channel with a separation of τ, which can be obtained through theoretical calculation; d(p,l) denotes the distance between links p and l; and α is a constant used to quantify the interference degree between POCs of different interfaces on the same node, which is usually set to a large value, say 10, to avoid the utilization of POCs on the same node as possible.
After the channel assignment for all links in the network has been completed, each radio utilizes cognitive radio technology [25,26] to sense the channel utilization in the neighborhood. When none of its interfering links in the neighborhood is transmitting, a node can perform interference-free data transmission on the assigned channel. The pseudo code of POCA algorithm is detailed in Figure 2.
Figure 2
Pseudo code of POCA algorithm.
×
4.3 Optimality evaluation of POCA
In this paper, we propose a simple but efficient partially overlapped channel assignment algorithm for MRMC WMNs. In order to demonstrate its optimality, we formulate the optimal partially overlapped channel assignment problem with the goal of minimizing total network interference and set it as the baseline to evaluate our algorithm.
Assuming that network topology has been pre-determined, which is the solution of the neighbor-to-interface binding problem stated above, then MRMC WMNs topology can be modeled as graph G(V,E), where V represents mesh routers and E represents wireless links. C is the set of available channels. Binary variable Al(c) is defined to represent whether channel c is assigned to link l, that is:
$$ A_{l}(c)=\left\{ \begin{array}{rcl} 1, & & \text{channel c is assigned to l}\\ 0, & & \text{otherwise} \end{array} \right. $$
(16)
When deciding channel assignment for links, two constraints need to be satisfied:
(1) The first constraint is that each link can be assigned with only one channel, which requires:
$$ \sum\limits_{c \in C} {A_{l} (c) = 1} $$
(17)
(2) The second constraint is imposed by network topology. Some links that share the same interface on a given node are required to be assigned with the same channel as below:
Channel assignment scheme satisfying the above two constraints is a feasible solution. If there is sufficient channel resource available, all links can be assigned channels without interfering with each other, i.e., interference can be totally eliminated. In reality, the channel resource that we can use is usually limited, so the goal becomes searching a channel assignment scheme that minimizes the total interference in the network with limited channel resource. The objective is defined below:
where binary variable I(e1,e2,τ) defined by Equation 3 is also used to represent interference relationship between links. It indicates whether these two links will interfere with each other under channel separation τ determined by channel assignment. Optimal partially overlapped channel assignment (O-POCA) can be formulated with the objective in Equation 19 and constraints in Equations 17 and 18. The exhaustive search is used to obtain optimal solution of the above formulation. We define normalized throughput which is the ratio between throughput of POCA and throughput of O-POCA as the metric to evaluate the optimality of our POCA algorithm, as the throughput of O-POCA is the highest throughput that can be gained by channel assignment, and it can be used as baseline.
$$ \text{NorThr} = \frac{{Thr}} {{Thr_{opt}}} $$
(20)
where 0<NorThr≤1, larger value of NorThr means better performance of POCA; and Thropt and Thr are the throughput that can be achieved by O-POCA and POCA, respectively.
4.4 Complexity analysis of POCA
As our POCA algorithm is composed of two steps: neighbor-to-interface binding and interface-to-channel binding, we compute the time required by them respectively, and then add them together.
(1)
The running time of computing node degree for all nodes takes at most O(|V|2) steps. When a node in V calculates its degree, the maximum number of neighbors it can have is |V|−1 (e.g., a complete graph), thus the time complexity required to compute degree for all nodes is O(|V|2).
(2)
The running time of neighbor-to-interface binding procedure according to node degree takes at most O(|V|2 log|V|) steps.
(3)
The running time of computing EIL (including Rank) values for all links and choosing one to be assigned a channel take at most O(c|E|2) steps, where c is the number of channels.
(4)
The running time of assigning channel for a selected link takes at most O(c|E|) steps.
Overall, the time complexity of proposed POCA algorithm is bounded by O(|V||E|2) because procedure in 3 will repeat O(|V|) steps, and the number of channels c is a constant.
5 Performance evaluation
We evaluate the proposed POCA algorithm by comparing it with channel assignment algorithm based on OCs (termed as OCA for short below) in different scenarios. Our experiments are carried out using network simulator (NS-3.19). We also modify NS to support multi-channel multi-radio and partially overlapped channels. We randomly select certain number of nodes as flow sources and set the gateway node as the destination for majority of flows, and for other flows, the destinations are randomly selected. All these can simulate situations in real WMNs, where traffic between the Internet and clients and peer-to-peer traffic coexist and traffic between the Internet and clients is dominant. The simulations are based on IEEE 802.11b standard which has 3 OCs out of 11 available channels, and the data transmission rate at the physical layer is 2 Mbps.
The following are our performance metrics, simulation results, and analysis.
5.1 Performance metrics
The performance evaluation and comparison are through the following metrics:
(1)
Average end-to-end delay: the end-to-end delay is defined as the time it takes a packet to reach the destination after it leaves the source. The average taken over all the received packets is then computed, which is the average end-to-end delay.
(2)
Network throughput: the network throughput is defined as the total amount of data bits actually received by receivers divided by the time between receiving the first packet and the last packet.
(3)
Average packet loss ratio: the packet loss ratio is defined as the number of packets delivered unsuccessfully divided by the total number of packets supposed to be delivered. The average taken over all the receivers is the average packet loss ratio.
5.2 Simulation results and analysis
We compare the performance of POCA algorithm with OCA, which are executed on the following topologies and evaluate the performance of them on the estimation of metrics listed in the ‘Perfomance metrics’ section.
5.2.1 Simulation results under grid topology
Grid topology of N×N squared grids is used, that is, each vertex is deployed with a mesh router, and each edge denotes a wireless link. Mesh routers are equipped with radios of similar capability and configuration, which means that the communication and co-channel interference ranges are uniformly set to 250 and 550 m, respectively, for all radios. The grid step is set to 250 m, which is the distance between adjacent nodes. This means that a node can communicate with its neighbors except the diagonal nodes. The node positioned in the bottom right corner is assumed to be the gateway. Traffic is generated by the constant bit rate (CBR) source, and the packet size is set to 512 bytes. In our simulations, channels 1 to 11 are used as POCs and channels 1, 6 and 11 are used as OCs.
In the first scenario, we vary the grid size from 5×5 to 10×10 and impose a certain number of CBR flows concurrently on the network to observe the impact of network size on performance. The results are shown in Figure 3a to c. From which, we can see the variation of network performance under different network scales. For the network of 5×5 size, it is too small for OCs to assign different channels to these flows, which introduces heavy interference among them, so the average packet loss ratio is higher and the network throughput is lower; it takes a long time for a packet to arrive the destination, which yields longer average end-to-end delay. When POCs are applied, interference can be further eliminated and more flows can carry out parallel transmissions; thus network performance is dramatically improved. As network scale grows larger, the network throughput both increases for POCA and OCA; this is because larger network allows more parallel transmissions, which gives them more space to exhibit their potential capability of reducing end-to-end delay and improving network throughput. If we can fully exploit the channel resources, we can achieve an improvement of network throughput by approximately 36% at most. We can also observe that the average end-to-end delay of POCA is much smaller than that of OCA, that is, packets can reach destinations quickly, which also contributes to the improvement of network throughput apart from low packet loss ratio. If POCs are exploited properly, the average end-to-end delay can be decreased by 56% at most; this is especially important for time sensitive traffic.
Figure 3
Impact of network size on performance under grid topology.(a) Network throughput comparison. (b) Average end-to-end delay comparison. (c) Average packet loss ratio comparison.
×
In the second scenario, we fix the grid size as 10×10 and vary the number of concurrent flows from 15 to 25 to observe the impact of number of flows on performance. Figure 4a shows the network throughput within networks with different number of flows for these two algorithms. From the figure, we can see that the network throughput almost linearly increases as the number of flows grows larger, but the improvement slope gets smaller. The reason is that as more flows are injected into the network, the network becomes denser, even though POCs are utilized, interference among adjacent links cannot be further eliminated. However, the superiority of POCA algorithm is obvious with respect to OCA algorithm, the network throughput improvement is about 23% or more. From Figure 4b, we can see the average end-to-end delay fluctuates within a certain value range. POCA algorithm performs better than OCA algorithm. For example, in the case that there are 25 flows, the average end-to-end delay is 2.14/3.31 s with POCA algorithm and OCA algorithm separately. The decrease ratio of POCA is about 35% compared with OCA algorithm. In the cases that there are less flows, the decrease ratio on average end-to-end delay is more obvious. As shown in Figure 4c, the average packet loss ratio for these two algorithms exhibits similar trend as average end-to-end delay, they are both stable, and the average packet loss ratio of POCA decreases 31% or more, which contributes to the network throughput.
Figure 4
Impact of number of flows on performance under grid topology.(a) Network throughput comparison. (b) Average end-to-end delay comparison. (c) Average packet loss ratio comparison.
×
From the simulations above, we can also draw conclusions that packet loss ratio is complementary to network throughput. In view of their relationship, performance results about average packet loss ratio are omitted in the following simulations.
In order to demonstrate the optimality of our proposed POCA algorithm, we repeat the simulations under grid topology and compare it with O-POCA according to the metric NorThr defined in this paper. The results are shown in Figure 5.
Figure 5
Optimality evaluation of POCA algorithm.(a) Performance under various network size. (b) Performance under various number of flows.
×
From Figure 5a, we can see that the performance of our POCA algorithm is comparable to O-POCA. When the network is small, even the optimal channel assignment cannot further eliminate interference, thus NorThr value is almost 1; as network grows larger, O-POCA has the ability to search the whole solution space to find better channel assignment than POCA, thus the throughput of POCA algorithm is a little lower than that of O-POCA, but the reduction in NorThr value never exceeds 12%. From Figure 5b, we can see that when the number of flows increases under fixed network size, the space for O-POCA to find better solutions gets smaller, thus NorThr value increases, which means that POCA can provide comparable performance as O-POCA. As O-POCA is NP complete, solving it is very time-consuming, which results in that it cannot be well applied in practice, while our POCA algorithm can be solved with polynominal time complexity and its performance is near optimal; it achieves good balance between performance and complexity.
5.2.2 Simulation results under random topology
A random WMNs topology is generated using the following method. A square region with the area of Dm×Dm is specified first which has the width [ 0,D] on the x-axis and the height of [ 0,D] on the y-axis. Then, a certain number of nodes are generated and the position (x,y) of each node is randomly specified within the square area. If the distance between two nodes falls into the transmission range (250 m), we add a link between them. Finally, we check whether the generated topology is connected or not. If not, the above process is repeated until the network connectivity is satisfied. POCA and OCA are compared in two different scenarios. One is small-scale WMNs consisting of 30 nodes over 1,000m×1,000m area, and the other is larger consisting of 60 nodes over 2,000 m×2,000 m area. Figures 6 and 7 show the comparison results in terms of network throughput and average end-to-end delay.
Figure 6
Performance comparison under 30-node random topology.(a) Network throughput comparison. (b) Average end-to-end delay comparison.
Figure 7
Performance comparison under 60-node random topology.(a) Network throughput comparison. (b) Average end-to-end delay comparison.
×
×
The following are our observations: the network throughput has similar trend with that under grid topology. The only difference is that the improvement is not so dramatic. Still, POCA outperforms OCA because it fully exploits the whole spectrum to perform channel assignment, so interference among adjacent links can be further eliminated and more flows can perform parallel transmissions. When there are 14 concurrent flows, the network throughput can be increased by approximately 19% and 9%, respectively, in 30-node network and 60-node network if we fully exploit the spectrum. We also observe that network throughput in 60-node network is more than that in 30-node network with the same number of concurrent flows; the reason is that the distribution of flows is more sparse in 60-node network, interference between flows is less, which gives flows more space to perform parallel transmissions, thus more packets can be routed to destinations more accurately, more quickly. Average end-to-end delay can be dramatically decreased, for instance, in the 60-node network using POCA; when there are nine flows or less, no interference occurs among these flows and packets can reach destinations with almost no delay. When more flows are injected into the network, average end-to-end delay increases, but it is always less than that using OCA.
6 Conclusions
In this paper, we consider about the characteristic of network traffic and propose a POCs-based assignment algorithm which utilizes theoretical calculation to obtain reduced interference ranges and assigns channels for all links in the network with the goal of minimizing total network interference. Through simulations, we demonstrate the effectiveness of the proposed algorithm in improving network performance. We plan to evaluate the performance of our proposed POCA algorithm in real testbed.
Centralized channel assignment is popular due to its simple implementation, but it is heavily dependent on the center node. If the center node fails, the normal operation of the networks will be disturbed. Distributed channel assignment is an efficient way to extend future WMNs. Our future work is to expand our centralized POCA algorithm to a distributed version. EIL and Rank in Equations 12 and 13 are used to determine node priority to be assigned a channel. Smaller EIL means higher priority, if there exists several links whose EIL values are equivalent, Rank value is used to break the tie. Larger Rank means higher priority to be assigned a channel. For a node v, it should guarantee that nodes with higher priority within its H hop distance have been assigned channels before it; as for nodes outside H hops, they are impossible to generate interference for node v. Here, \(H = \left \lceil {\frac {{R^{\prime }}} {T}} \right \rceil \), R′ is the maximum interference range with channel separation 0, i.e., co-channel interference range. T is the transmission range. The distributed channel assignment can be performed as follows:
(1)
Each node computes its own degree according to physical topology.
(2)
In MRMC WMNs, gateway node periodically broadcasts messages to notify its existence and related information. Mesh nodes that receive these messages can obtain their hop count distance from the gateway.
(3)
Nodes obtain node degree of their one-hop neighbors through ‘Information Exchange’ messages broadcasted within H hops, and then neighbor-to-interface binding can be finished according to node degree information.
(4)
Each node calculates EIL and Rank values of links originating from it and records EIL, Rank, channel assignment list, and other information of links originating from other nodes within H hops distance according to the ‘Information Exchange’ messages.
(5)
When assigning channels for a selected link, the channel which can minimize the total interference between it and links that have been assigned channels is selected and assigned. After its channel assignment, this node will notify nodes within its H hop distance about its channel information. On receiving the information, each node updates EIL and channel assignment list, etc.
(6)
Steps (4) and (5) are repeated until channel assignment for all nodes within H hop distance is completed.
The basic condition to perform the above distributed algorithm is to allow information exchange between nodes, when information exchange cannot be achieved for some reasons or in order to reduce overhead, game-theoretic approach [27,28] can be used to model partially overlapped channel assignment for MRMC WMNs with the objective of minimizing total network interference, and uncoupled learning algorithms should also be used to achieve stable solutions.
At present, routing metrics published are all proposed on the assumption that channels are orthogonal [29-34]. When using OCs, the interference range is a constant, which is usually twice the transmission range. As a result, the interference estimation is very simple, that is, if two links are within the interference range of each other, they will interfere if they operate on the same channel, and otherwise not. However, when POCs are applied, the interference range is no longer a constant. The interference relationship is related to the distance between links and the separation between channels used by links. Thus, the determination of interference relationship, the model of intra-flow interference, and inter-flow interference should be modified. As future direction, we plan to study routing metrics that can capture the characteristics of WMNs using POCs to provide route guidance for traffics.
Acknowledgements
This work was supported by the National Natural Science Foundation of China under Grant No. 61373124.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.
The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
