{'fraction_non_alphanumeric': 0.0324733243037891, 'fraction_numerical': 0.014766608304978363, 'mean_word_length': 4.716012084592145, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Impact of Spatial Channel Reuse and Adaptive Modulation on Wireless Mesh Network Capacity

The capacity analysis based on the concept of collision domains may be applied to wireless networks with mesh topology, e.g. wireless backhaul networks for rural areas, sensor networks, etc. The strength of the method is the fact that it may be easily fitted to any MAC protocol, routing algorithm, channel allocation method, and, therefore, is a valuable tool for verification and performance analysis of such algorithms. However, simplifications assumed by some authors may lead to erroneous results, e.g. significantly underestimated capacity of the WMN. Therefore, phenomena specific to wireless networks, such as spatial channel reuse, and features specific to wireless standards, such as link adaptivity, should be included in the analysis, as presented in this paper.


Introduction
Wireless mesh networks (WMN) have become reality in recent years. The number of their applications is still growing: monitoring/surveillance systems, out-door/in-door wireless internet access, sensor networks, small community networks to be only a few examples [1]. All of them use proprietary solutions developed independently by many manufacturers, since no approved WMN standards currently exist. In 2003, interests in the Institute of Electronics and Electrical Engineering (IEEE) 802. 11 Working Group (WG) led to formation of Task Group (TG) S. 802.11s develops an amendment for wireless local area network (WLAN) Mesh, however, the standard is still in its draft phase (as of June 2011) [2]. Most of the existing solutions available on the market use a well established IEEE 802.11a/b/g/n physical layer radio interface, de facto the only WLAN standard (WiFi) used in millions of laptops, PDAs, smartphones, and other portable devices. The most important differences which make the WMN devices from various vendors incompatible are the medium access and routing protocols.
Although WMN are often seen as a cost effective (due to the lack of infrastructure) way to increase coverage, their capacity is limited due to the nature of the radio channel, which must be shared by the nodes forwarding the traffic from and to the gateway. Therefore, estimating the capacity, one of the key performance indicators of WMNs is an important question. The capacity analysis proposed for ad hoc networks cannot be directly applied to WMN due to some fundamental differences, e.g. a different traffic pattern and node density.
Due to the distributed nature of mesh networks, the existing single-hop MAC mechanisms cannot operate efficiently in an environment, where there is a high number of indirect neighbors. Such protocols have been designed for access point (AP) centric WLANs like 802.11 and do not provide any means for advanced medium reservation. Therefore, an optional deterministic MAC scheme, called mesh coordinated channel access (MCCA), has been included in the 802.11s draft standard and will be considered below.
In this paper a novel method for determining the effective capacity of mesh network is proposed and evaluated. It uses collision domains based protocol model for estimating the nominal capacity but it also takes into account the implications of spatial channel reuse, an inherent feature of WMN, as well as link adaptation implemented in modern radio interfaces. Recently, a lot of research has been carried out to investigate the capacity of ad hoc networks, but their results cannot be directly applied to WMNs due to several reasons which are explained in Sect. 2. Section 3 shortly describes 802.11s Mesh Coordinated Channel Access MAC protocol and its features. The concept of collision domains, presented by Jun et al. in [3], and its application to 802.11s MCCA is shown in Sect. 4. This is followed by discussion of nominal and effective load of the 802.11s collision domains as well as implications of link adaptation. Numerical results obtained using the approach described before are presented in Sect. 5. Finally, the work is concluded in Sect. 6, where also possible directions for future work are presented.

Related Work
In the past decade a lot of research has been devoted to determining the capacity of wireless ad hoc networks. In the fundamental work by Gupta and Kumar [4] the analytical lower and upper bounds of stationary network capacity have been derived for the single-channel (c = 1), single-radio (m = 1) case, however, the results also apply to the multi-channel, multi-radio networks, providing that m ≥ c. Since each working node exclusively occupies an area in the whole network, the capacity is bound by the number of nodes that can work simultaneously and it has been shown that the throughput capacity per node reduces significantly when the node density increases. The results were validated in [5], where the authors used NS-2 simulator and standard IEEE 802.11 MAC mechanisms to determine the influence of traffic pattern on the achievable throughput.
The results of [4] were extended by Kyasanur and Vaidya [6] to determine the network capacity bound under the assumption that m < c. The work assumes that the radios can switch the channels dynamically and demonstrates that the network capacity is dependent on the ratio c/m and not on the exact values of either c or m. Morover, when the node placement is dense enough, the capacity of a random network can be increased c times by using multiple channels. When channel switching delay is not zero, having multiple radios may be beneficial, too. In [7] the authors analyzed ad hoc networks allowing node mobility and showed that, if long delays are tolerated, the capacity remains constant with the number of nodes.
However, most of the results valid for ad hoc networks cannot be directly applied to mesh networks due to some fundamental differences. They have been identified in [3] and are discussed below: 1. In ad hoc network the traffic flows between any arbitrary pair of nodes while in WMN practically all the traffic is gateway oriented. WMN's AP acts as a hot spot and may be a bottleneck of the whole network's capacity. 2. Topology of the WMN is rather stable, with new nodes occasionally joining or leaving the network, while an ad hoc network can change dynamically in both, the number of nodes and number of links/connections. 3. There are no energetic constraints, nodes have access to external power sources. 4. As a consequence of 3. Nodes can have multiple radios which can increase throughput capacity significantly. 5. The number of nodes and the required bandwidth in WMN may be higher than in ad hoc network. 6. Most of the results focused on the theoretical analysis for the asymptotic case. The resulting capacity bounds do not reflect the exact capacity of the WMNs with an aribitrary number of nodes.
Mesh network capacity is studied e.g. in [8] and [9], where linear programming is used to model the various constraints of multi-channel, multi-radio configurations. The former assumes static channel assignment while the latter both static and dynamic schemes. For a given network topology and traffic pattern, the capacity bound can be computed by solving the linea programming model, however, the relationship between the network capacity improvement and the number of channels/radios is not addressed explicitly by the authors.
Interesting results are presented in [10], where the upper bound on the capacity of multichannel, multi-radio mesh network capacity is derived. According to the analysis adding channels can increase the network capacity linearly, while adding radios can bring quadratic improvement. With a small number of radios on each mesh node, adding more radios can improve the network capacity significantly, however, after some point, the channels become the limiting factor and adding radios will not increase the capacity further.
Most of the results presented in [3][4][5][6][7][8][9][10][11] were obtained assuming MAC mechanisms typical to IEEE 802.11 standard. However, the contention-based multiple access results in an excessive collisions in WMN and should be avoided [12,13]. Reservation-based MAC mechanisms proposed for mesh networks can not be easily incorporated in the analysis in most cases. As shown in [15,16] the collision domain approach, originally presented in [3], can be extended to include any MAC layer mechanism as well as multi-channel and multi-radio modes of operation by redefinition of the collision domain.

Overview of MCCA MAC Protocol
Current 802.11s draft standard [2] specifies two medium access control protocols, namely enhanced distributed channel access (EDCA) and mesh coordinated channel access (MCCA), of which only the first is mandatory. EDCA bases on carrier sense multiple access with collision avoidance (CSMA/CA) and is a successor of the distributed coordination function (DCF) implemented in millions of WiFi devices. While it performs satisfactory in the AP centric, single-hop environment, it fails to deliver a high throughput and fairness in a mesh 2316 R. Krenz  [12] and [13].
In contrast to the opportunistic medium usage by EDCA, MCCA (called mesh deterministic access in earlier versions of the standard draft) bases on scheduled medium usage. Stations (Mesh Points-MP) forming the WMN regularly broadcast delivery traffic indication message (DTIM) frames and the time between consecutive beacons is slotted (32 μs slots). The exchange of scheduling information is explained in Fig. 1. Mesh points perform channel reservation by requesting MCCA Opportunities (MDAOPs), whose parameters are specified in MDAOP setup request information element (IE), broadcasted by the transmitting party (MDAOP_SR3- Fig. 1, step I). The intended receiver checks the included IE and verifies if the MDAOP does not collide with other MDAOPs the receiver is aware of. If it is accepted, both the requester and the granter inform their neighborhood about the planned transmissions. The broadcasted TX-RX Times Report contains information about all MDAOPs the MP is involved in as a transmitter or receiver, its own or indicated beacons as well as other busy periods (TXRX_TR4, TXRX_TR3- Fig. 1, step II).
Together with the TX-RX Times Report MPs send an Interfering Times Report, which is a copy of the TX-RX Times Report received from the neighbors (I_TR3, I_TR4- Fig. 1, step III). Consequently, each station can obtain scheduling information of its two-hop neighbors and data packet transmission is collision-free in the entire extended neighborhood (MP1-MP6- Fig. 1).
Moreover, the hidden station problem is effectively eliminated at the same time. More details about the MCCA MAC mechanism, including frame format and other parameters can be found e.g. in [13].

Definition of Collision Domains in 802.11s MCCA
The concept of collision domains was applied to WMNs capacity calculation for the first time by Jun and Sichtiu in [3]. The method is based on the fact that the existence of gateways in WMNs introduces hot spots in the network that act as bottlenecks. Identifying the bottleneck collision domains allows computing exactly the minimum and maximum data rates available for each station for a given network topology and link layer protocol. The concept was further developed by Aoun and Boutaba in [14], by considering fairness to ensure proper operation of WMNs.
However, all the previously listed research considered 802.11 distributed coordination function (DCF) based WMNs only or did not take into account the specification of the MAC protocol at all. One of the key strengths of the collision domains approach is the ability to include any MAC layer mechanism as well as multi-channel and multi-radio modes of operation by redefinition of the collision domain. This is simply done by imposing a set of constraints (specified by the MAC protocol) on the links between stations communicating in the mesh network.
One of the contributions of this work is the application of collision domains concept to the 802.11s MCCA based WMNs, as specified in the 802.11s draft standard [2]. For clarity, let us consider a simple chain of N = 8 Mesh Points receiving and forwarding traffic from the mesh portal (MPP-in 802.11s terminology an Internet gateway). Herewith a unidirectional (downlink) traffic is assumed, the bidirectional case will be treated later in Sect. 4. The example collision domain C D 4 for link k = 4 (between MP3 and MP4) is defined as follows (see Fig. 2): 1. the requester (MP3) broadcasts a MDAOP Setup Request IE, notifying node MP4 of its request-link 4 (MP3 → MP4) is included in the collision domain, 2. the receiver (MP4) respond with a TX-RX Times Report, indicating the granted data slots to nodes MP3 and MP5-link 5 (MP4 → MP5) is added to the collision domain C D 4 , 3. the requester (MP3) sends its TX-RX Times Report, indicating the granted data slots to node MP2-link 3 (MP2 → MP3) is added to the collision domain C D 4 , 4. node MP2 sends Interfering Times Report (a copy of the MP3 TX-RX Times Report) informing node MP1 of the pending transmission in its extended neighborhood (and specifically between nodes MP3 and MP4)-link 2 (MP1 → MP2) ) is included in the collision domain C D 4 , 5. additionally, node MP1 will not accept any requests from MPP (since MP1 is in the interference range of MP3) and, therefore, link 1 (MPP → MP1) is added to the collision domain C D 4 , 6. similarly, node MP5 sends Interfering Times Report (a copy of the MP4 TX-RX Times Report) informing node MP6 of the pending transmission in its extended neighborhood (and specifically between nodes MP3 and MP4)-link 6 (MP5 → MP6) is included in the collision domain C D 4 , 7. finally, link 7 (MP6 → MP7) is added to the collision domain C D 4 , this step is done since node MP6 will restrain from requesting slots advertised by MP4 and granted to MP3.
The definition of collision domain presented above is valid for single-radio, single-channel configuration only. Since 802.11s standard allows multi-radio, multi-channel operation, the collision domains must be redefined for such networks, similar to [15].

Nominal and Effective Load
The collision domain defined in the previous section may be used to compute the traffic forwarded within the domain. Assuming that each MP in the chain (see Fig. 2 If the bandwidth (the capacity of the MAC layer) for each link in the collision domain is constant and equal to B[bit/s], the throughput L d available to each MP in the chain is limited to L d < B/35 (for C D 4 ). In order to find the collision domain which is limiting for the network (bottleneck collision domain), the collision domains and corresponding loads have to be identified for every link in the network and the minimum throughput must be selected [4]. The load of collision domain presented so far leads to a pessimistic value of the throughput L d and is called the nominal load [14]. Instead, the effective load gives a more accurate estimate of the throughput by considering the spatial channel reuse, which is typical for multi-hop links in WMNs.

Impact of Link Adaptation
The physical layer of 802.11s standard is based on 802.11g (OFDM modulation) physical layer and features link adaptation (modulation and coding scheme-MCS) for better utilization of radio resources [2]. Consequently, the raw data rates may vary from 6 to 48 Mb/s (in 20 MHz channel), depending on the receiver SNR, which, in turn, is a function of propagation conditions as well as network topology.
With link adaptation every link in a specific collision domain may apply different modulation and coding scheme, which impacts the load of collision domain-now the load of every

Realistic Scenarios
The chain topology adopted so far is rather simplistic and was used for concept presentation only. In real life implementations the WMN topologies are much more complex, depending on application and deployment scenarios. Typically, the WMN consist of tens or even hundreds of nodes, connected to the wired segment via a gateway. They may be organized in a grid topology, with a gateway located at the center of the grid (Fig. 3), a model widely used in literature, which can be applied e.g. in urban environment (nodes placed on road intersections), office environment (nodes placed along corridors) as well as industrial environment (production halls, assembly rooms, warehouses). Aggregators (nodes that are traffic sources/destinations) may be located at the edges (Fig. 3a) [17] or distributed evenly on the grid (Fig. 3b), which is a more realistic scenario. The remaining nodes, as well as some or all of the aggregators act as wireless routers.
Network topology is not the only factor influencing WMN performance. Link loads and, consequently, collision domain loads are mainly determined by the routing algorithm implemented in the network. Similarly, channel allocation influences construction of collision domains in multi-channel/multi-radio networks. Therefore, the analytical model based on collision domains may be used for evaluating the performance of different routing and channel allocation algorithms. Although this model may seem similar to system level simulation, it is a truly analytical model with all its implications. First of all, the evaluation of network capacity for a given configuration/load is computationally less demanding comparing to the simulation at the packet level. At the same time the accuracy is satisfactory, both for network planning and performance evaluation, which was shown in [15] where the results obtained for chain topology using the collision domains analysis were successfully verified by packet level simulation.
An approach based on collision domains was previously used in [17], however, the practical value of the results may be questionable. The authors analyzed only the nominal capacity, which is far from the realistic scenario. As already mentioned, the actual capacity is strongly influenced by spatial channel reuse and physical layer features, i.e. adaptive modulation and coding, which is implemented in many wireless standards, including IEEE 802.11 a/b/g/n.
Including the spatial channel reuse in the analysis requires elimination of links which can transmit simultaneously with other links in every collision domain. The procedure, which Since the least loaded link is eliminated from the collision domain in this process, the capacity will never be overestimated. Figures 4 and 5 present an example of a collision domain in a 7 × 7 grid topology with 10 and 40 aggregators respectively. The dotted lines depict the links remaining in the collision domain for the link marked by the dashed line after performing the procedure which removes certain links due to spatial channel reuse (aggregators are drawn as a '+' sign on the graphs).
If the physical layer of the analyzed WMN implements link adaptation, the network is no more homogenous. Results presented previously, e.g. in [17], assumed that the throughput of all links in the network is constant, while in a realistic scenario, it varies based on the interference level at the receiving nodes. The interference level may be estimated using a propagation model adequate to the analyzed environment/scenario. Potential interferers can be identified using the procedure described in Algorithm 2.

Algorithm 1
For every collision domain C D k identified in the network For every link i ∈ C D k Find the set i ⊂ C D k of links which can transmit simultaneously with link i Decrease the load of C D k by the load L n = min(L j ) Eliminate link n from C D k End End The total interference level as well as the received signal level calculated for every receiver in the links forming the collision domain is used to assign adequate transmission rate (bandwidth) to the links.

System Model
The collision domain method described in Sect. 4 was applied to grid topology WMN compliant with IEEE 802.11s standard. Both cases, with aggregators located at the edges (Fig. 3a) as well as distributed evenly on the grid (Fig. 3b), are analyzed. The size of the grid is equal to 5 × 5, 7 × 7 and 9 × 9 nodes, with 20, 50, and 100 m distance between nodes.
All aggregator nodes generate the same traffic which is routed to the gateway node, located in the center of the grid. For each network configuration the capacity is calculated for a varying number of aggregator nodes, which are randomly placed on the grid. The results are averaged over multiple runs (in most cases 1,000 runs), since there can be many ways to distribute a given number of aggregators on the grid. The nominal capacity, the effective capacity as well as the MCS capacity are calculated for every run.
A single-radio as well as multi-radio with 2 radio interfaces per node environment is analyzed. In the single-radio case all nodes operate in a single channel, while 2, 3, 4 or 5 channels can be assigned to the network in the multi-radio case. A simple, random channel assignment algorithm is implemented, however, more sophisticated scheme could be used. The routing algorithm selects a single, shortest (with minimum number of hops) path to the gateway for every aggregator. If there is more than one path that meets the shortest path criteria, only one of them is selected randomly. Similar to channel assignment, any other routing algorithm may be implemented. This can be useful if the collision domain method is used to compare the performance of different algorithms, however, this is beyond the scope of the paper.
The propagation model can be tuned to different propagation conditions (environment) and network topology. The received power P Rx depends on the distance d between the receiver and the transmitter, the transmitted power P T x which is assumed to be equal for all nodes (20 dBm), the dumping factor (3.5-a value typical for in-door, LOS/NLOS environment) and the center frequency f c (5 GHz): Transmit and receive antenna gains are also included (both equal to 7 dBi-omnidirectional antennas).
The link adaptation procedure is based on the signal-to-interference-plus-noise ratio (SINR) at the receiver. The SINR of the transmission from node s to node r which takes place between time instants t 1 and t 2 is given as: where N is the thermal noise (−95 dBm),T is the set of nodes transmitting in the time interval t 1 , t 2 excluding node s (i.e. interfering nodes). Typical values of the minimum received signal level as well as the minimum SINR for each physical layer transmission rate are presented in Table 1.

Results
The results shown below present the capacity of WMN for different scenarios and network parameters. A MATLAB script was used to determine link loads, construct collision domains and locate the bottleneck collision domain, limiting the capacity for a given scenario. The

Fig. 6
Nominal and effective capacity of the network with 7×7 grid size and aggregators located at the edges capacity available to each node is calculated as a percentage of the nominal MAC capacity, which can be assumed equal to 1 without a loss of generality. If MCS capacity is evaluated, the "nominal"capacity corresponds to the highest PHY rate. The notation used in the figures is the following: -the nominal capacity is marked 'NC' -the effective capacity (including spatial channel reuse) is marked 'EC' -the MCS capacity (including link adaptation) is marked 'PC'.
The first group of figures (Figs. 6,7,8) show the capacity of the network with 7 × 7 grid size and aggregators located at the edges. The results presented in Fig. 6 clearly indicate that spatial channel reuse must be included in the mesh network capacity analysis, otherwise the capacity is significantly underestimated (by 50-100 %, depending on the number of aggregators and available channels). In case of a single-radio channel and 5 aggregators the capacity increases from 5.5 % (nominal capacity) to 11 % (effective capacity), while for 20 aggregators it increases from 1.4 to 2.1 %.
However, even more realistic results are presented in Figs. 7 and 8, since they take into account link adaptation procedures, based on the received SIR. While the effective capacity is the same in both cases, the MCS capacity decreases by 60-70 % for node spacing equal to 20 m and as much as 75-80 % for node spacing equal to 100 m. Specifically, in case of a single-radio channel and 5 aggregators the capacity decreases from 11 % (effective capacity) to 2.4 % (MCS capacity), while for 20 aggregators it decreases from 2.1 to 0.47% (Fig. 8).
The next group of figures (Figs. 9,10,11) show the capacity of the network with the same (7 × 7) grid size and aggregators spread evenly on the grid. Similarly to the previous case, the results presented in Fig. 9 indicate that spatial channel reuse must be included in the analysis, otherwise the capacity is significantly underestimated (by 50-100 %, depending on the number of aggregators and available channels). In the case of a single-radio channel and  Taking into account the link adaptation procedure, the results change depending on the grid spacing (see Figs. 10,11). If the distance between nodes is equal to 20 m, the MCS capac-   aggregators the effective capacity is equal to 1.2 % and the MCS capacity is equal to 0.26 % (Fig. 11). Figures 12 and 13 show the nominal and effective capacities when the grid size is varied for a different number of aggregators located at the edges. It can be easily noted that for Fig. 13 Nominal and effective capacity of the network with different grid sizes and aggregators located at the edges operating in 4 channels the increasing grid size, both the nominal and effective capacities decrease. Such behaviour can be explained by the fact that the number of hops from the aggregator to the gateway increases together with the grid size and, consequently, each collision domain load increases, decreasing the capacity. The relative capacity reduction is almost independent on the number of channels (1 channel- Fig. 12, 4 channels-Fig. 13) and the number of aggregators.
The next set of results illustrate the impact of grid size and number of channels on the MCS capacity for different grid spacing. An interesting conclusion can be drawn from the figures i.e. the MCS capacity is more susceptible to the grid size for lower grid spacing (20 m in Fig. 14 vs. 100 m in Fig. 15). When the distance between nodes is 100 m, the link throughput is limited by the received signal strength in general and the interference level is very low-the interfering nodes are located far from the node of interest. Therefore, in this case the increasing number of interfering nodes impacts the received interference level to a lesser extent than in a denser network topology.
Similar results have been obtained with aggregators spread evenly on the grid (Fig. 16, 17,  18, 19). Network capacity is 10-15 % higher in this case (which holds for nominal, effective as well as MCS capacity), because some of the aggregators located "inside" the grid (and not on the edges) share the paths toward the gateway with other aggregators located on the edges. Consequently, some of the existing collision domains have their loads increased but no new paths (and collision domains) are created for those aggregators. The observation described in the paragraph above for a network with aggregators located on the edges is even more evident here for the same reason.

Concluding Remarks
The capacity analysis based on the concept of collision domains may be applied to wireless networks with mesh topology, e.g. wireless backhaul networks for rural areas, sensor  networks, etc. The advantage of the method is that it may be easily fitted to any MAC protocol, routing algorithm, channel allocation method, and, therefore, is a valuable tool for verification and performance analysis of such algorithms. However, simplifications assumed by some authors may lead to erroneous results, e.g. significantly underestimated capacity  of the WMN. Therefore, phenomena specific to wireless networks such as spatial channel reuse, and features specific to wireless standards, such as link adaptivity, should be included in the analysis, as presented in this paper.  The collision domain method has even more advantages when compared to widely used simulation-based analysis tools (e.g. NS-2, NetSim, etc.). The computation time necessary to build and analyse collision domains for a network consisting of tens or even hundred of nodes is much shorter than simulation time necessary to analyse such a network using a MAC-level simulator. At the same time the results obtained from the analytical and simulation methods are pretty consistent [15]. On the other hand, the method has its drawback too-no other network performance indicators (e.g. packet delay, buffer occupancy, etc.) can be predicted. However, to the best knowledge of the author of this article, the collision domain approach is the only analytical tool for estimating the throughput capacity of the multi-channel and multi-radio mesh network with arbitrary topology, taking into account the specific MAC mechanism as well as spatial channel reuse and link adaptivity.
The presented results confirm that the wireless mesh network capacity is inversly related to the number of aggregators. The capacity decreases for a given number of aggregators with the increased grid size as well since more hops are necessary to reach the gateway, which results in higher load of the collision domains. The general trends are consistent with other works, however, the exact results are quite different and show, that neglecting phenomena such as spatial channel reuse and variable link bandwidth leads to significant errors in the capacity analysis.
It seems that the collision domain concept may have other applications as well. Research have already been started to formulate an efficient load-aware routing algorithm for WMN based on the presented idea, implementing all the modifications verified in this paper. The first results should be published soon.
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.