# Fast-Converging Scheduling and Routing Algorithms for WiMAX Mesh Networks

Salim Nahle, Naceur Malouch

► To cite this version:

Salim Nahle, Naceur Malouch. Fast-Converging Scheduling and Routing Algorithms for WiMAX Mesh Networks. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. pp.238-249, 10.1007/978-3-642-20798-3_18. hal-01285694

HAL Id: hal-01285694

https://hal.science/hal-01285694

Submitted on 29 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast-Converging Scheduling and Routing Algorithms for WiMAX Mesh Networks

Salim Nahle and Naceur Malouch

Université Pierre et Marie Curie - Laboratoire LIP6/CNRS
4, Place Jussieu 75252 Paris Cedex 05
Email: {name.surname}@lip6.fr

**Abstract.** In this paper, we present fast converging algorithms that fit well WiMAX mesh networks. First, a centralized scheduling algorithm is presented. It calculates schedules by transforming the multi-hop tree into a single hop, and then repartitioning the different schedules in the multi-hop tree. Second, a routing metric called Multiple Channel One Pass (MCOP) is introduced. MCOP chooses routes by explicitly accounting for the coding and modulation schemes on each route as well as the number of available channels. In addition, the route construction is performed in a way that reduces the impact of the bottlenecks on throughput. Numerical simulations show the superior performance of MCOP as compared to other routing metrics especially when the available number of channels is more than two.

**Keywords:** WiMAX, Mesh Networks, scheduling, routing

## 1 Introduction

Wi-Fi has been adopted as the default technology for Wireless Mesh Networks (WMN). Wi-Fi based mesh networks, however, expose scalability and limited coverage issues. With the reduced transmission range of Wi-Fi devices, many access points are required to ensure connectivity in a small zone. This in turn, increases interference, reduces the throughput and renders ensuring QoS difficult. Wi-Fi WMNs' performance drops down significantly beyond three hops [1]. This is mainly due to the non-deterministic medium access of the IEEE 802.11 standard. A possible solution that overcomes these issues, and consequently increases the throughput capacity and ensures QoS in WMN, is the use of WiMAX mesh networks [2]. As opposed to the Point-to-Multi-Point (PMP) mode, WiMAX MESH mode allows direct transmissions between Subscriber Stations (SSs) that communicate through a multi-hop tree rooted at the base station (BS). The way the tree is built and schedules are performed has a deep impact on the capacity that a WiMAX backbone may offer.

WMNs are mainly used to provide broadband access, and thus routing and scheduling operations must be sufficiently rapid so as no delay is added with each change in the network configuration. For this purpose we present in this
paper two disjoint fast-converging routing and scheduling algorithms. First, the proposed centralized scheduling algorithm calculates schedules by transforming the multiple-hop tree into a single hop. This is achieved by replacing each SS path by one link. On each link, the maximal end-to-end rate on the corresponding path is used. It calculates therein the allocations for all the SSs. The different schedules are then repartitioned in the multi-hop tree. Finally, the allocations are repartitioned on the available orthogonal channels to increase capacity. Second, a routing metric called Multiple Channel One Pass (MCOP) is introduced. MCOP chooses routes by explicitly accounting for the coding and modulation schemes that are called burst profiles in WiMAX terminology. WiMAX employs an adaptive modulation and coding scheme (AMC) to choose the best burst profile on a particular link in function of the signal-to-noise ratio (SNR) and the bit error rate (BER).

Besides, MCOP accounts to the number of available channels in choosing routes. Moreover, the route construction is performed in a way that reduces the impact of the bottlenecks on throughput. In fact, we have found by simulations, that routing metrics that are used in single-channel mesh networks do not fit multiple-channel networks [3]. This is mainly due to the accumulation of traffic close to the BS, and hence the creation of bottlenecks. The bottleneck node may be the BS itself. Nevertheless, we have seen that it can be any other SS, since the bottleneck node depends, in addition to the traffic, on the burst profiles of ingoing and outgoing links. Numerical simulations show the superior performance of MCOP as compared to other routing metrics especially when the available number of channels is more than two.

The rest of the paper is organized as follows. In section 2, we present a scheduling algorithm for WiMAX mesh networks. Section 3 discusses the impact of routing on multi-channel WiMAX meshes. Section 4 describes MCOP. In section 5, we present our simulations and discuss the results. In section 6, we present the related work before concluding the paper in section 7.

# 2 Fair Scheduling Algorithm

## 2.1 Overview: Scheduling in IEEE 802.16 mesh mode

IEEE 802.16 introduces two scheduling mechanisms: centralized and distributed. We focus, in this work, on the centralized scheduling which is performed using two main types of messages: the Mesh Centralized Scheduling (MSH-CSCH) message and the Mesh Centralized Scheduling Configuration (MSH-CSCF) message. Each node gathers its children's requests and reports them along with its own in a MSH-CSCH request to its parent. The parent node is called Sponsoring Node (SN) in the WiMAX terminology. The whole process repeats recursively until the requests are propagated towards the BS. The BS then determines the flow assignments and broadcasts a MSH-CSCH Grant, which is rebroadcasted by intermediate nodes until all the SS nodes in the network receive it. SSs determine their scheduling in a recursive manner by using a common algorithm that divides the frame proportionally.
## 2.2 Scheduling Algorithm

Fairness among users is a crucial issue in WMNs that are mainly used for providing wireless broadband access. In this section we propose a scheduling algorithm that allocates the resources (channels and time slots) in a fair way among different SSs. For this purpose we identify two key objectives that must be fulfilled:

1. Guaranteed allocations per flow: The algorithm ensures that the allocated resources (time slots) are sufficient to realize a fair end-to-end rate. Suppose that $SS_i$ and $SS_j$ are respectively $n_i$ and $n_j$ hops distant from the BS, $\alpha_{i,k}$ is the number of minislots to be allocated on link<fnref n="1" /> $k$ of the path<fnref n="2" /> of $SS_i$ ($\forall k \in \{1, 2, \dots, n_i\}$), on behalf of $SS_i$ (link $k$ is also used by other SSs), $r_i$ is the end-to-end data rate of $SS_i$. The scheduling algorithm must ensure that $\alpha_{i,k}$ and $\alpha_{j,k}$ ($\forall k \in \{1, 2, \dots, n_j\}$) are sufficient to guarantee the end-to-end rate, regardless of the number of hops of $SS_i$ and $SS_j$.

2. Maximum utilization of resources: In the purpose of maximizing the network utilization, the scheduling algorithm properly chooses the values of $\alpha_{i,j}$. Assume, for example, that $SS_i$ is 3 hops from the base station, where each link $l_j$ on its path supports a data rate $r_{l_j}$ ($j \in \{1, 2, 3\}$), known from the burst profile information carried by the control messages. Given that $r_{l_1} > r_{l_2} > r_{l_3}$, it may be sufficient to allocate the same $\alpha_{i,j}$ for all the links in order to satisfy the first condition. Nevertheless, this will result in resource wastage since the overall rate is bounded in this case by the lowest link rate $r_{l_3}$, and is $r_{l_3}/3$. Our algorithm searches to ensure the required end-to-end data rate with the minimal number of time slots. It guarantees $r_i$ for every $SS_i$ by choosing the values of $\alpha_{i,j}$ to be inversely proportional to the link rates. The intuition behind that is maintaining the same throughput on each link. The second scheduling condition can be expressed as follows:

$$ \alpha_{i,1}r_{l_1} = \alpha_{i,2}r_{l_2} = \dots = \alpha_{i,n_i}r_{l_{n_i}} = r_i \quad \forall i. \quad (1) $$

This latter condition can be used for calculating the maximal end-to-end rate (MEER) for each SS, as we will see in the following section.

## 2.3 Maximal End-to-End Rate

In wireless multihop networks, it has been largely considered that the end-to-end rate (throughput) of a multihop flow is bounded by the minimum link-rate (throughput) on the path of this flow [4]. This might be right in 802.11-based networks where the access to the channel is non-deterministic as the case of the CSMA/CA 802.11 MAC. Nevertheless, in WiMAX mesh networks it is possible to achieve a higher end-to-end rate on a multihop flow, by explicitly accounting for data rates on the different hops constituting it and also by satisfying equation (1) in assigning time slots among different links.

<footnote n="1">¹ A link $i$ refers to the link between $SS_i$ and its parent.</footnote>

<footnote n="2">² A path of an SS corresponds to its route towards the BS, which is unique in the WiMAX mesh case.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Network example: $f_1$ is 3 hops</figcaption></figure>

Consider the network graph given in figure 1, $f_1$ is a 3-hops flow between nodes (SSs) 1 and 4. Given the link rates $r_1 = 1$ Mbps, $r_2 = 2$ Mbps and $r_3 = 4$ Mbps, then assuming an equal share for each link will result in an end-to-end data rate $r = 0.33$ Mbps. This leads to channel underutilization. The optimal channel utilization is achieved by satisfying equation (1). Accordingly, $\alpha_{1,1}$, $\alpha_{1,2}$ and $\alpha_{1,3}$, being the portions of the total time $T$ allocated to $f_1$ on links $l_{1,2}$, $l_{2,3}$ and $l_{3,4}$ respectively, are computed as: $\alpha_{1,1} = (4/7)T$, $\alpha_{1,2} = (2/7)T$ and $\alpha_{1,3} = (1/7)T$. For $T = 1$ second, the obtained MEER of $f_1$, is $r = 0.57$ Mbps which is equivalent to 72% rate improvement (relative to $r = 0.33$ Mbps).

MEER of a multihop flow $f_i$ that corresponds to $SS_i$, which is $n_i$ hops, where $r_{l_j}$ is the rate on link $l_j$ of the path of $SS_i$ can be expressed as follows:

$$r_i = \frac{1}{\frac{1}{r_{l_1}} + \frac{1}{r_{l_2}} + \dots + \frac{1}{r_{l_{n_i}}}} \quad (2)$$

### Proof:

Let $\alpha_{i,j}$ be the portion of the total time $T_i$ allocated to $f_i$ on link $l_j$, then satisfying equation (1) we obtain: $\alpha_{i,1}r_{l_1} = \alpha_{i,2}r_{l_2} = \dots = \alpha_{i,n_i}r_{l_{n_i}} = r_i$. Similarly, $\alpha_{i,1} = r_i/r_{l_1}$, $\alpha_{i,2} = r/r_{l_2}$, ..., $\alpha_{i,n_i} = r_i/r_{l_{n_i}}$. Recall that the sum of $\alpha_{i,j}$ is $T_i$: $\alpha_{i,1} + \alpha_{i,2} + \dots + \alpha_{i,n_i} = T_i$. For obtaining the end-to-end data rate it is sufficient to replace $T_i$ by 1 and $\alpha_{i,j}$ by $r_i/r_{l_j}$ and we are done $r_i/r_{l_1} + r_i/r_{l_2} + \dots + r_i/r_{l_{n_i}} = 1$.

## 2.4 Mesh scheduling

Scheduling multihop links in a way that satisfies the previously mentioned objectives is not straightforward. The proposed scheduling algorithm performs the following steps:

1. The BS calculates MEER of each SS as well as $\alpha_{i,j}$ values by satisfying equation (1).

2. It transforms the multihop mesh network into a single-hop one, by using MEER of each SS.

3. Then, it distributes the available minislot space among the SSs that form a single cell. At this stage, any fairness model can be applied (max-min,
proportional, maximum throughput). This can be accomplished by assigning weights for each SS on an end-to-end basis.

4. Then, having the number of minislots allocated for each SS ($SS_i$), these minislots are distributed among the links that constitute its path towards the BS according to the calculated $\alpha_{i,j}$ values.

5. Finally, each link $i$ in the mesh tree is allocated the aggregation of its share on different flows that use it.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Scheduling example</figcaption></figure>

For a better understanding, let's consider the mesh network in figure 2(a). Given a set of SSs and a BS with the rates on the different links, the algorithm calculates MEER and the corresponding $\alpha_{i,j}$ on all the links on the route from an SS towards the BS. These values are given in figure 2(b). Figure 2(c) shows the single-hop network that is obtained by using MEER of every SS. Figure 2(d) shows the number of time slots of each SS (for its own traffic in the uplink direction). Note that we suppose that all the SSs must be served in the same manner. The calculations for the downlink direction are the same. The second line in the table of figure 2(d) shows the repartition of the time slots of each SS among the links of its path. They are calculated by using $\alpha_{i,j}$ on each link. For instance, the 7 slots of $SS_5$ are repartitioned on links $l_{5,3}$ (4 slots) $l_{3,1}$ (2 slots) $l_{1,BS}$ (1 slot) since $\alpha_{i,j}$ values are respectively 0.57,0.26 and 0.14. Finally the allocations on each link (for different SSs) are added (line 3). The obtained allocations on each link are shown in figure 2(e).
### 3 Impact of Routing on Multi-Channel WiMAX Mesh Networks

The way the mesh tree is constructed has a significant impact on the throughput capacity. In fact, routing metrics designed for single-channel WiMAX Mesh networks, do not necessarily fit multiple-channel meshes. This is mainly due to the creation of bottlenecks close to the BS. Consequently, even with using several orthogonal channels, there is an upper bound on the gain that can be obtained in term of fair throughput. This limit is referred to as *multiple channel gain* (MCG) and expressed as follows:

$$MCG = \frac{T}{MAX\left\{MAX_i\left(\frac{T_i}{L_{SS}}, \frac{T_{BS}}{L}\right)\right\}} \quad (3)$$

Where T corresponds to the whole scheduling period needed to satisfy the demands of all SSs. $T_i$ is the time needed for $SS_i$ to communicate with its parent and its children in the uplink and downlink directions. $T_{BS}$ is the transmission time needed for the BS. $L_{SS}$, $L$ are the number of network cards for an SS and the BS respectively. $T_i = \sum_{j \in Child_i} w_{jj} + w_{ii}$, where $w_{ii} = \frac{d_{ii}}{r_{ii}}$ is the time needed to transfer the traffic on link $l_{ii}$. $d_{ii}$ and $r_{ii}$ are respectively the traffic demand and the achievable data rate on the link between $SS_i$ and its parent $SS_i$. The SS with the maximum $T_i$ or the BS constitutes the bottleneck of the multi-channel network. This is represented in the denominator of equation 3.

We can deduce from MCG, the number of channels ($\gamma$) beyond which no more increase in fair throughput can be obtained. $\gamma$ is the upper bound of MCG. For more details on the calculations refer to [3]. As a conclusion, the routing has to take into account these bottlenecks in order to realize full advantage of available multiple channels. In the next section, we propose a routing metric that explicitly accounts for these bottlenecks in the tree construction.

### 4 Multiple Channel One Pass routing

MCOP aims at maximizing fair throughput capacity while establishing routes in a distributed manner. The name MCOP is used since the entrance of a new node does not cause recalculations at already joined nodes.

The IEEE 802.16 Mesh mode uses Mesh Network Configuration (MSH-NCFG) and Mesh Network Entry (MSH-NENT) messages for advertisement of the mesh network and for helping new nodes to synchronize and join the mesh network. Active nodes within the mesh periodically advertise MSH-NCFG messages which are used by new joining nodes. Among all possible neighbors that advertise MSH-NCFG, the joining node (which is called Candidate Node CN in the 802.16 Mesh mode terminology) selects a potential Sponsoring Node to connect to. This latter is called candidate sponsoring node CSN. MCOP algorithm chooses among the CSNs the SS that minimizes the bottleneck of the fair throughput capacity. In other words, the joining node, that knows the actual state of the tree
**Algorithm 1** *MCOP*

Require: $p$, parent of the $SS_w$.

1: **procedure** PARENTSELECTION($p, r$)

2: $SS_w \leftarrow \text{MESH-NCFG}$ and $\text{MESH-CSCH}$

3: *metric* $\leftarrow 0$

4: **for** all $i \in CSN$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;calculate $T$ and $MCG$ ($T, MCG$)

6: $a \leftarrow MCG$

7: **if** $a > m$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;$a \leftarrow m$

9: **end if**

10: **if** metric $< a \div T$ **then**

11: &nbsp;&nbsp;&nbsp;&nbsp;metric $\leftarrow a \div T$

12: **end if**

13: **end for**

14: $\text{send}(p, \text{MSH-NENT});$

15: **end procedure**

(number of nodes, burst profiles of data links) based on the *MSH-NCFG* and *MSH-CSCH*, calculates locally the *MCG* for every possible tree. Note that if there are *n* candidate SN, then it does only *n* calculations.

The algorithm is sequential, its details are given in Algorithm 1. Nodes that are closer to the BS starts earlier than others. An *SS* that does not have a neighboring node (a candidate SN in range) waits until another *SS* which is in its range, connects to the mesh tree, and follows it.

For better understanding, we explain hereafter the algorithm line by line. Each CN $SS_w$ accumulates the knowledge of the actual mesh tree through the MESH-NCFG and MESH-CSCH messages (line 2), and thus it knows the number of channels available for use ($m$). For each possible SN in the set $CSN$, it calculates $T$ and multiple channel gain $MCG$ as explained in section 3 (line 5). It assumes that all the $SSs$ have the same load, so it affects $x$ bits for every $SS$ and does the calculations accordingly. In fact, $Thr_{MC} = MCG * Thr_{SC}$ where $Thr_{SC}$ is the single channel throughput and $Thr_{MC}$ is the multi-channel throughput. Nevertheless, $MCG$ may be greater than $m$. In this case the gain $a$ of using $m$ channels is limited to $m$ (line 8). Now it compares $Thr_{MC}$ for each possible path and chooses the one that maximizes throughput capacity. In fact the algorithm uses $a/T$ as a metric, since it is proportional to $Thr_{MC}$ where $1/T$ is proportional to $Thr_{SC}$. Finally it sends a mesh network entry to this parent $p$.

## 4.1 Discussion

It is worthwhile noticing that the *MCOP* algorithm may lead to quasi-optimal routing topologies if we permit the recalculations of paths after the arrival of a
new SS. Nevertheless, this may also lead to route flaps when many SSs switch simultaneously to the new joining node. In this case, convergence of the algorithm is crucial to the performance. Studying the convergence of the algorithm is one of our future directions, though initial results are optimistic, especially when using an indexing strategy that gives priorities to lower hop SSs to connect to the new SS. Next, we study the performance of this algorithm without recalculations, and as we will see, the results are also very interesting even with this simple algorithm that needs no changes in the configuration of the MESH mode in the IEEE 802.16 standard.

# 5 Performance Evaluation

In this section we study the performance of the *MCOP* algorithm by comparing it to routing metrics, namely *MEER* [5], *Hop Count* and *Blocking* [6]. We suppose that a number of orthogonal channels *m* is available. The evaluation metric is the achievable fair capacity which is the maximal fair throughput (maximum equal share).

We implemented using Matlab the *MCOP* routing algorithm as well as the other routing metrics. We also implemented the scheduling algorithm that uses the round robin approach defined in IEEE 802.16. The graph topologies used in these simulations are randomly generated where a set of *n* SSs and a BS are distributed in a *d* × *d* cell. The routing algorithm first constructs the mesh tree according to the routing metric (*MCOP*, *Hop Count*, *MEER*, *Blocking*). Then we apply the scheduling algorithm presented in section 2. The output of this algorithm is a set of (*link*, *number of slots*). Then by using the available channels, we use a graph coloring algorithm that reduces the scheduling time by exploiting the available number of channels and spatial reuse (more details about the channel assignment are found in [3]). The final output is a set of triplets (*t*, *active links*, *channel*) that determines for each time slot *t*, the set of active links on each channel. These schedules in time and frequency domains are broadcasted in the scheduling frames. We present simulation results for two scheduling paradigms. In the first, we do not account for channel reuse. In this case, the results correspond to the case where the BS is not aware of the exact topology. In the second, channel reuse is enabled. Notice here that only the receiver on each link is protected by forbidding all nodes that interfere with it from transmitting and hence there are no hidden terminals. Hereafter, we only present the results for single interface WiMAX Mesh networks ($L_{SS} = L = 1$). Applying the model for multiple interface networks is straightforward, and it is sufficient to replace $L_{SS}$ and *L* by their values in equation 3.

Fig. 3 displays the maximal aggregate fair throughput as a function of orthogonal (non-interfering) channels for the three routings. We vary *n* and *d* from 20 to 40SSs and from 15 to 25km respectively. Each point is the average of 50 simulations for different topologies randomly chosen. It shows how this achievable throughput, for all the metrics, increases with the number of channels until it reaches $\gamma$, beyond which no more gain is obtained. Recall that $\gamma$ is the upper
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Routing metrics comparison in terms of throughput, multiple channels, with and without frequency spatial reuse (FSR)</figcaption></figure>

bound of *MCG* as we have seen in section 3. *MCOP* can employ more orthogonal channels than the others. This is because, it takes the number of channels into account and minimizes the bottleneck accordingly as described in section 4. Otherwise, *MEER* slightly performs better for $m \le 2$ in figure 3(a) and $m \le 4$ in figure 3(b), since *MEER* routing is the optimal routing as the available number of channels is less than *MCG* because it chooses routes with maximal end-to-end data rates [5]. Hence for $m \le MCG$, there is a tradeoff when using *MCOP*, since it selects, with each network entry, paths that can exploit the $m$ available channels, rather than paths that optimize end-to-end rate as *MEER*. Consequently, if the available number of channels is not sufficient (i.e. less than *MCG* of *MEER*-based tree), *MEER* can perform better.

Moreover, *MCOP* does not allow recalculation of existing paths when a new SS joins the network, which is allowed using *MEER* that converges rapidly. In fact, we can adapt the routing algorithm (*MCOP*), to use *MEER* for the case $m \le MCG$ (of *MEER*-based tree) and *MCOP* otherwise.

As seen in the figure, *MCOP* routing outperforms all the other routing metrics even the *Blocking* metric that was particularly designed for increasing FSR, which performs even worse than *Hop Count* in the multiple channel case. The poor performance of these metrics occurs because they do not account for burst profiles in route construction which is crucial.

Note that, it is not surprising that the same fair throughput capacity is obtained whether using FSR or not, since the same routing is used in both cases, hence the same bottleneck is created.

On the other hand, an important observation from figure 3(a) is that for all the used routing metrics, the optimal throughput is obtained by employing almost the same number of channels with or without FSR. For instance, 3 channels are needed to obtain this maximal throughput in cases of *Blocking* and *Hop Count* routings and 5 channels for *MEER*. However, *MCOP* yields the best performance with 5 channels with FSR, but it needs 6 channels without it. Nev-
ertheless, there is a slight difference between the throughput capacity obtained
in both cases. This means that the gain that can be obtained with FSR is not
very big if sufficient number of channels is available, especially that accumulating
the exact information about topology requires the exchange of a non-negligible
portion of traffic for conveying the interference information.

In figure 3(b), more nodes are used which implies that more channels can
be used [7]. Besides, the used larger area enables better use of the channel. It
is clear from the figure that *MCOP* outperforms the other routing approaches
but also increases the difference especially with *MEER*. Interestingly it is able
to exploit up to 10 channels for increasing the throughput capacity. We can also
observe that as the area size increases (from 15 *km* to 25 *km*), more FSR can
be achieved, and hence whenever FSR is used, at least 1 channel is saved for
obtaining the best performance, 2 channels in case of *MEER*.

# 6 Related Work

Various joint schemes for multi-channel 802.11-based WMNs were proposed [8-10]. 802.16 networks, however, have different characteristics such as the contention-free transmissions dislike 802.11 standard where nodes need contend to the medium. Though, some works can still be considered as a benchmark for the WiMAX case since they assume TDMA link scheduling for 802.11 based WMNs [11]. These proposals either use mathematical formulations that assume global knowledge of the network, or propose distributed algorithms relying on local knowledge that is accumulated by exchanging messages in a certain neighborhood. The numerical solving of these models make them “black boxes” that results in less understanding of the system behavior, for instance the impact of bottlenecks. Knowing that the scheduling and channel assignment are NP-hard [10], we use simple yet efficient algorithms for improving the throughput capacity. These algorithms are sequential. First, a routing tree built is with *MCOP* or another metric. Then, the scheduling algorithm assigns time slots by transforming the multihop tree to single-hop cell. Then by exploiting the available number of channels, it reduces the total scheduling period. Note that it is sufficient to protect the receiver-side of a transmission by forbidding SSs that are in its range from transmission. In many works [12,11] the RTS/CTS/DATA/ACK model was assumed and hence the sender should be protected too.

In [7], the destination bottleneck constraint on the capacity corresponds to the node that is the destination of maximum number of flows. In the WiMAX case, the BS is the destination of all the flows, but it is not necessarily the bottleneck on the throughput capacity. An SS with less number of flows can be this bottleneck depending on the data rates of the links incident on it.

On the other hand, many works have addressed multiple channel WiMAX
mesh networks [13–16]. In [15], an iterative tree construction algorithm is pre-
sented. However constraints are imposed in a way that an SS cannot have more
hops (towards the BS) than a possible parent. In our work, *MCOP* prefers multi-
hopping in order to reduce the bottleneck time for exploiting well the available
channels. Jiao et al. compared different routing metrics under a proposed centralized scheduling [14]. In this paper, we showed that routing metrics designed for single channel use may not be suitable for multiple channel case due to the creation of bottlenecks and hence we proposed heuristic algorithms that reduce these bottlenecks and thus increase the multiple channel exploitation.

*MCOP* routing can exploit more channels than other routing metrics since it was fabricated to reduce the bottleneck of multiple channel use. The number of channels is even beyond the results in [12] where it is found that no more gain can be obtained beyond *L* + 1 channels where *L* is the number of radios, and also in [16] where authors recommend to use *2* * *L* channels.

# 7 Conclusions and Future Work

In this paper we have proposed scheduling and routing algorithms in the purpose of enhancing throughput capacity but also fairness among SSs in a WiMAX Mesh Network. The scheduling algorithm maximizes the utilization of the network and guarantees fairness among different SSs on an end-to-end basis. The algorithm transforms the multi-hop tree into single-hop cell by considering the maximal end-to-end rate of each SS. It can ensure any kind of fairness in the single hop network, and then by reconsidering the multiple hop tree, it distributes the shares of each SS among different links. We have also proposed a distributed routing algorithm called *MCOP*, which selects the routes that minimize the time needed for bottleneck SS with each SS entry. We have shown by simulations the efficiency of this algorithm compared to other approaches in terms of throughput capacity and fairness. *MCOP* can employ more channels than other metrics in the purpose of improving fair throughput capacity. We have also found that frequency reuse can reduce the number of channels needed to obtain the maximal capacity for large networks.

Interestingly, *MCOP* outperforms other routing metrics. This means that it is possible to remove the “black box” and understand the real behavior of wireless multihop networks. Accordingly, “simple” routing techniques can significantly enhance the performance of these systems. For instance, *MCOP* is built based on the understanding of the bottlenecks in WiMAX mesh networks. Thus, it explicitly accounts to them in the route construction, which results in improving system capacity.

Nevertheless, *MCOP* is proposed as a fast route construction algorithm where recalculations of paths after the entry of a new SS are not allowed. In fact, allowing recalculations exhibits well known convergence issues in routing, such as route flaps. Resolving these issues consists one of our future works. We believe that resolving them can result in quasi-optimal performance, since *MCOP* in its current version, approaches to the optimum for some topologies. Moreover, *MCOP* favors multi-hopping. This may incur some delay. In this work we have not studied delay, which consists one of our future directions. IEEE 802.16 supposes that the transmission of the same packet (corresponding to an SS) cannot occur more than once in the same frame. This means that a packet corresponding
to an SS that is 7 hops away from the BS must wait at least 7 frames to arrive
at the BS which incurs some delay. A possible improvement may be changing
the scheduling that is adopted in the standard, which assigns time slots for each
SS in a row.

References

1. Nahle, S., Malouch, N.: Graph-based Approach for Enhancing Capacity and Fairness in Wireless Mesh Networks. In: Proceedings of IEEE Globecom. (2009)

2. IEEE 802 Standard Working Group: IEEE Standard for Local and Metropolitan Area Networks–Part 16: Air Interface for Fixed Broadband Wireless Access Systems. Standard 802.16d-2004, IEEE (2004)

3. (Report, T.) http://www-rp.lip6.fr/ nahle/Files/cc.pdf.

4. Gao, Y., Chiu, D.M., Lui, J.C.: Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications. SIGMETRICS Perform. Eval. Rev. 34(1) (2006) 39–50

5. Nahle, S., Malouch, N.: Joint Routing and Scheduling for Maximizing Fair Throughput in WiMAX Mesh Network. In: Proceedings of IEEE PIMRC. (2008)

6. Wei, H., Ganguly, S., Izmailov, R., Haas, Z.: Interference-aware IEEE 802.16 wimax mesh networks. In: Proc. IEEE Vehicular Technology Conference (VTC). (2005)

7. Kyasanur, P., Vaidya, N.H.: Capacity of multi-channel wireless networks: impact of number of channels and interfaces. In: MobiCom '05, ACM Press (2005)

8. cker Chiueh, T., Raniwala, A.: Architectures and algorithms for an ieee 802.11-based multi-channel wireless mesh network. In: INFOCOM. (2005)

9. Alicherry, M., Bhatia, R., Li, L.E.: Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In: MobiCom '05: Proceedings of the 11th annual international conference on Mobile computing and networking, ACM Press (2005)

10. Raniwala, A., Gopalan, K., cker Chiueh, T.: Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. SIGMOBILE Mob. Comput. Commun. Rev. 8(2) (2004) 50–65

11. Wang, W., Li, X.Y., Frieder, O., Wang, Y., Song, W.Z.: Efficient interference-aware tdma link scheduling for static wireless networks. In: MobiCom '06: Proceedings of the 12th annual international conference on Mobile computing and networking, ACM Press (2006) 262–273

12. Kodialam, M., Nandagopal, T.: Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In: MobiCom '05: Proceedings of the 11th annual international conference on Mobile computing and networking, ACM Press (2005) 73–87

13. Zhou, M.T., Harada, H., Wang, H.G., Ang, C.W., Kong, P.Y., Ge, Y., Su, W., Pathmasuntharam, J.S.: Multi-channel wimax mesh networking and its practice in sea. In: IEEE ITST. (2008)

14. Jiao, W., Jiang, P., Liu, R., Li, M.: Centralized scheduling tree construction under multi-channel ieee 802.16 mesh networks. In: Proc.GLOBECOM 07. (2007)

15. Ghiamatyoun, A., Nekoui, M., Esfahani, S., Soltan, M.: Efficient Routing Tree Construction Algorithms for Multi-Channel WiMax Networks. In: IEEE ICCCN. (2007)

16. DU, P., JIA, W., Huang, L., Lu, W.: Centralized Scheduling and Channel Assign-
ment in Multi-Channel Single-Transceiver WiMax Mesh Network. In: Proc. IEEE
Wireless Communications and Networking Conference WCNC. (2007)