# Multicast in Multi-channel Wireless Mesh Networks

Ouldooz Baghban Karimi, Jiangchuan Liu, Zongpeng Li

► To cite this version:

Ouldooz Baghban Karimi, Jiangchuan Liu, Zongpeng Li. Multicast in Multi-channel Wireless Mesh Networks. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chen-nai, India. pp.148-159, 10.1007/978-3-642-12963-6_12. hal-01056316

HAL Id: hal-01056316

https://inria.hal.science/hal-01056316

Submitted on 18 Aug 2014

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
# Multicast in Multi-Channel Wireless Mesh Networks

Ouldooz Baghban Karimi¹, Jiangchuan Liu¹, Zongpeng Li²*

¹ School of Computing Science, Simon Fraser University

² Department of Computer Science, University of Calgary
{oba2, jcliu}@cs.sfu.ca, zongpeng@ucalgary.ca

**Abstract.** We study high-throughput multicast solutions for wireless mesh networks (WMN). Two techniques in WMN design are considered for combating wireless bandwidth limitations and wireless interference, respectively: introducing multiple mesh gateways and exploiting the diversity of wireless channels. We target a cross-layer solution that jointly (a) selects appropriate channels for each mesh node to use, at judiciously tuned power, and (b) computes the optimal multicast flows associated with the channel assignment. Our solution is obtained by first formulating the WMN multicast problem into a mathematical program, and then designing an iterative primal-dual optimization framework for it based on Lagrange relaxation and primal problem decomposition. Solution algorithms for the decomposed sub-problems are designed to complete the solution. In particular, a progressive channel assignment heuristic is introduced at the MAC/PHY layer. Through extensive simulations, we demonstrate the effectiveness of the proposed solution framework and the sub-problem heuristics. In particular, a throughput improvement of up to 100% is observed when compared to straightforward approaches of utilizing multiple wireless channels for multicast routing.

**Keywords:** Wireless Mesh Networks, Multicast, Multi-Channel Communication, Primal-Dual Optimization

## 1 Introduction

Wireless mesh networks (WMN) are emerging as a promising solution for broadband connectivity, due to its flexibility and cost-effectiveness in bringing a large number of users online, in comparison to competing solutions that depend on a wireline infrastructure [1, 3]. In a WMN, Internet gateways, mesh routers and client nodes are organized into a mesh topology. Data flows are routed between the clients and the gateways through wireless links, in a multi-hop fashion. A notable challenge in WMN is to provide support for multicast applications that surged on the Internet during the past decade, such as file dissemination, video conferencing and live media streaming. Such applications usually serve a large number of users, and consume high network bandwidth.

* This research is supported by an NSERC Discovery Grant, an NSERC Strategic Project Supplemental Competition Grant, an AI-TF New Faculty Award, and a MITACS Project Grant.
We consider two techniques for addressing the high-throughput requirement of mul-
ticast applications in WMNs. The first is to use multi-gateways. A gateway is directly
connected to the Internet, and hence serves as the data source for users in a WMN. A
single gateway design makes the gateway node a bottleneck, and is prone to congestion
during high network activities. Having multiple gateways can dramatically improve the
network performance at a reasonable cost. The second is to exploit the diversity in wire-
less channels, and provide a multi-channel multicast solution. Wireless interference is
a critical limitation on throughput of WMN applications [8]. Utilizing distinct channels
at neighboring nodes for transmission can help reduce interference to minimum. For
example, the IEEE 802.11b/g protocol defines 13 channels within a 2.4GHz frequency
band [5]. The further apart two channels are, the less interference exists between them;
in particular, channels 1, 6 and 13 are totally orthogonal.

We first formulate the multi-gateway multi-channel multicast problem in WMNs as a mathematical programming problem, which jointly considers channel assignment and transmission power tuning at the MAC/PHY layer, as well as multicast routing at the network layer. Two important regions that the formulation is based on, the channel capacity region and the routing region, are both convex. Furthermore, the objective function that models the utility of multicast throughput is strictly concave. Therefore, the entire optimization model we obtain is a convex program, if we can freely select the frequency band for a channels. However, with pre-defined channels such as in IEEE 802.11, the optimization model contains discrete variables, which complicates the solution design.

In order to provide an efficient and practical solution the the optimization model, we
apply the classic Lagrange relaxation technique [4, 20], and derive an iterative primal-
dual optimization algorithm that leads to a cross-layer multicast solution. Towards this
direction, we first relax the link capacity constraints that couple the channel region
and the routing region, and decompose the overall optimization into two smaller sub-
problems, one for channel assignment at the MAC/PHY layer, and one for multicast
routing at the network layer. Our primal-dual solution framework then iteratively refines
the primal solution, with help of the Lagrange dual that signalizes capacity demand at
each wireless link. The dual is updated during each iteration based on the latest primal
solutions.

To complete the solution defined by the primal-dual framework, we need to precisely define the channel region and the routing region, and design a solution algorithm for each of the channel assignment and routing sub-problems. We formulate the channel assignment problem as a mathematical program, in which channel capacities are computed from their signal-to-noise-and-interference ratio (SINR), and the computation of SINR in turn appropriately takes into account the separation between different wireless channels used at neighboring mesh nodes. The main challenge in solving this mathematical program lies in the presence of discrete channel assignment variables. We design an efficient heuristic, progressive channel assignment, for overcoming this difficulty. Finally, we discuss both multicast tree based and network coding based solutions for
the multicast routing sub-problem. Extensive simulations, with various network sizes, were conducted for evaluating the effectiveness of both the overall primal-dual optimization framework and the sub-problem solutions. Throughput improvement of up to 100% were observed, when the proposed solution is compared to straightforward channel assignment schemes such as orthogonal channel assignment and consecutive channel assignment.

The rest of the paper is organized as follows. We review related research in Sec. 2. Sec. 3 presents the optimization problem formulation for multicast in WMN. Sec. 4 introduces the problem decomposition and the overall primal-dual solution framework. Sec. 5 presents solutions for the sub-problems. Sec. 6 is simulation results and Sec. 7 concludes the paper.

## 2 Related Work

There have been significant research on wireless mesh networking in recent years. Channel assignment has consistently been a focus with diverse static and dynamic solutions being proposed [15] [7] [6] [12] [13]. Given the tight coupling of different layers in such networks, joint optimization across layers have attracted great interest [5] [10] [13]. Alicherry et al. [3] presented a joint orthogonal channel assignment and unicast throughput maximization framework. Rad et al. [13] investigated channel allocation, interface assignment and MAC design altogether. Merlin et al. [11] further provided a joint optimization framework for congestion control, channel allocation, interface binding and scheduling to enhance the throughput of multi-hop wireless meshes. Their framework accommodates different channel assignments, but neighboring channel interference has yet to be addressed. Recently, Chiu et al. [5] proposed a joint channel assignment and routing protocol for 802.11-based multi-channel mobile ad hoc networks. While sharing many similarities with wireless meshes, the mobility concern and associated overheads are not critical in mesh networks given that the mesh routers and gateways are generally static.

Our work was motivated by these pioneer studies; yet our focus is mainly on throughput maximization in the multicast context. For multicast routing, Nguyen and Xu [14] systematically compared the conventional minimum spanning trees or shortest path trees in wireless meshes. Novel approaches customized for wireless meshes have also been proposed [16] [21] [20]. Our work is closely related to the latter two. In [21], two heuristics for multicast channel assignment were proposed, which also applies to a multi-gateway configuration. They however did not explicitly address route optimization. In [20], routing and wireless medium contention were jointly considered. The impact of link interferences and power amplitude variations on each link were also closely examined, but were limited to single channel usage. Our work differs from them in that we examine both multicast routing and channel assignment in a coherent cross-layer framework, and present effective solutions. We also explicitly explore the potentials of multi-gateway configurations.
# 3 The Multi-Channel Multicast Problem Formulation

We first construct mathematical programming formulations of the optimal multicast problem in WMNs, with multi-gateways and multi-channels. Envisioning two different physical layer technologies for selecting a frequency band for a channel, we present two corresponding optimization models. The first one is based on flexible frequency bands enabled by variable frequency oscillators, such as assumed in software-defined radios. This ideal radio model leads to optimal multicast throughput that can be computed precisely, through the classic primal-dual optimization framework. The second model is rather similar, but makes a more realistic assumption on frequency bands based on the state-of-the-art IEEE 802.11 standard: each transmission has to use one of the 13 pre-defined channels.

## 3.1 Network Model and Notations

We model a WMN as a graph $G = (V, E)$, with nodes $V$ and links $E$. Assume $T \subseteq V$ is the set of gateways. Each gateway has a high-bandwidth connection to the Internet, and can be viewed as a data source. Let $S$ be the set of data transmission sessions. We define five vectors of variables. The first four are: the vector of data flows $\mathbf{f} = \langle f_e^i | i \in S, e \in E \rangle$; the vector of multicast throughput $\mathbf{r} = \langle r^i | i \in S \rangle$; the vector of link capacities $\mathbf{c} = \langle c_e | e \in E \rangle$; and the power assignment vector $\mathbf{p} = \langle p_u \le p_{u,max} | u \in V \rangle$. The last one is on channel assignment. We assume that each node is equipped with one radio with capacity $b$, which can transmit at different frequencies with adjustable power. In the flexible channel model, we have the vector of centre frequencies $\mu = \langle \mu_u | u \in V \rangle$. The frequency band of the channel used by $u$ is then $[\mu_u - b/2, \mu_u + b/2]$. In the case of fixed channels, we have the vector $\gamma = \langle \gamma_u \in \Gamma | u \in V \rangle$ to represent the channel assignment at each node. Here $\Gamma$ represents the set of pre-defined channels, such as the 13 in the IEEE 802.11 standard.

## 3.2 The Flexible Channel Model

Two capacity regions are fundamental to our multicast problem formulation: the *channel region* and the *routing region*, at the MAC/PHY layer and the network layer, respectively. The channel region $H$ defines a set of (**c**, **h**) such that channel assignment in **h** can support link capacity vector **c**. The routing region $R$ defines a set of (**r**, **f**) such that the throughput vector **r** can be supported by flow rates in **f**. Detailed characterization of the two regions are not immediately relevant to the overall optimization structure, and are postponed to Sec 5.1 and Sec 5.3 respectively, where we select optimal solutions from each region.

The multicast throughput for each session is measured as the data receiving rates at the receivers, which are equal for receivers across the same session. A basic physical rule that establishes a connection between the routing region and the channel region is that the aggregated data flow rates have to be bounded by the corresponding link capacities. Furthermore, we follow the convention [20] in modeling throughput utility,
and adopt the concave utility function $log(1 + r_i)$ for session throughput $r_i$. Then, the
throughput maximization problem can be formulated as:

$$
\begin{align}
\text{Maximize} \quad & U(r) = \sum_{i \in S} U(r_i) = \sum_{i \in S} \log(1 + r_i) \nonumber \\
\text{Subject to} \quad & (c, \mu, p) \in H \nonumber \\
& (r, f) \in R \nonumber \\
& \sum_{i \in S} f_e^i \le c_e, \forall e \in E \tag{1}
\end{align}
$$

The first constraint (c, μ, p) ∈ H models the dependence of effective channel bandwidth on channel assignment and power assignment at each node. The second constraint (r,f) ∈ R models the dependence of multicast throughput r on the routing scheme f. ∑i∈S f i e ≤ c e , ∀ e ∈ E model link capacity constraints. The objective function U(r) is concave, and both the routing and channel regions are convex regions. Therefore, convex optimization methods [4] can be used to compute the optimal solution (μ*, p*, f*). In Sec. 4 and Sec. 5, we present a primal-dual solution based on Lagrange relaxation and iterative primal-dual optimization.

If nodes can transmit using pre-defined channels only, we can modify the mathematical program in (1), by replacing the frequency vector $\mu$ with the channel assignment vector $\gamma$. Since $\gamma$ is an integer vector, the mathematical program can not be directly solved to optimal using conventional convex optimization methods, in polynomial time. Nonetheless, the solutions in Sec. 4 and Sec. 5 will be flexible enough to compute approximate solutions, based on a heuristic channel assignment method.

4 The Primal-Dual Solution Framework

The overall solution framework we propose for solving (1) is an iterative primal-dual schema, which switches between solving primal sub-problems and updating dual variables. We describe in Sec. 4.1 how to decompose the primal problem while introducing dual variables, and then present the primal-dual solution framework in Sec.4.2.

4.1 The Routing vs. Channel Assignment Decomposition

A critical observation of the optimization problem (1) is that, the channel region *H* and the routing region *R* characterize variables from the MAC/PHY layer and the network layer respectively, and are relatively independent. The only coupling constraint between them is *f* ≤ *c*. We can apply the Lagrange relaxation technique [4, 9] to remove *f* ≤ *c* from the constraint set, and add a corresponding price term into the objective function: *L* = *U*(*r*) + ∑*e*∈*E* α*e* [*c*<sub>*e*</sub> − ∑*i*∈*S* *f*<sub>*e*</sub><sup>*i*</sup>]. Here α is a vector of Lagrange multipliers, which can be viewed as prices governing the link capacity supply — the larger α<sub>e</sub> is, the tighter bandwidth supply at link *e* is.

After the relaxation, the resulting optimization problem is naturally decomposed
into two smaller, easier-to-solve sub-problems, including the Channel Assignment Sub-
problem at the MAC/PHY layer:

$$ 
\begin{array}{ll}
\text{Maximize} & \displaystyle\sum_{e \in E} \alpha_e c_e \\
\text{Subject to} & (c, \gamma, p) \in H
\end{array}
\qquad (2) $$

and the Routing Sub-problem at the network layer:

$$ 
\begin{array}{ll}
\text{Maximize} & U(r) - \displaystyle\sum_{e \in E} (\alpha_e \sum_{i \in S} f_e^i) \\
\text{Subject to} & (r, f) \in R
\end{array}
\qquad (3) $$

It is interesting to observe that, given a link $e$ with high price $\alpha_e$, the routing sub-problem will automatically attempt to reduce the amount of flow $f_e$ through $e$ during the next round, since its objective function implies minimizing $\sum_{e \in E} \alpha_e \sum_{i \in S} f_e^i$. On the other hand, the channel assignment sub-problem will automatically attempt to create more capacity for $e$, since its objective function is to maximize $\sum_{e \in E} \alpha_e c_e$.

## 4.2 The Primal-Dual Solution Schema

The primal-dual approach iteratively updates the primal ($f, \mu, p$) and dual ($\alpha$) solutions. During each iteration, we solve the two primal sub-problems given the current dual vector $\alpha$, and subsequently update $\alpha$ with the newly computed primal vectors as below. Here $t$ is the round number, and $\beta$ is the step size vector.

i. Set $t = 1$; initialize $\alpha(0)$, e.g., set $\alpha_e(0) = 0, \forall e \in E$

ii. Solve primal sub-problems (2) and (3).

iii. Update the dual domain variables as below:

$$ \alpha(t) = \max(0, [\alpha(t-1) + \beta(t)(\sum_{s \in G} \sum_{t \in T_s} f_e^t)]) $$

iv. Set $t = t + 1$ and return to step ii, until convergence.

**Theorem 1.** The primal-dual algorithm above converges to an optimum primal solution ($f^*, \mu^*, p^*$). of the optimization problem (1), as long as the regions $R$ and $H$ are convex and the step sizes $\beta(t)$ are appropriately chosen.

*Proof.* The constraint $f < c$ is linear, the objective function in (1) is strictly concave. The convexity of the capacity regions $R$ and $H$ then ensures that the update in the dual domain (iii) is a sub-gradient for the dual variables in $\alpha$. Therefore as long as the step sizes are appropriate chosen, the dual update converges [9, 20]. Strong duality further assures that the convergence point of the primal-dual algorithm corresponds to a global optimum of the network optimization problem in (1). $\beta[t] \ge 0, \lim_{t \to \infty} \beta[t] = 0$, and $\sum_{t=1}^{\infty} \beta[t] = \infty$. A simple sequence that satisfies the conditions above, is $\beta[k] = a/(mk + n)$, for some positive constants $a, m$ and $n$. $\square$
# 5 Solving Channel Assignment and Routing Sub-Problems

In order to obtain a complete solution under the primal-dual schema, we need to design algorithms for solving each of the two primal sub-problems. We next discuss how to solve the channel assignment sub-problem in Sec. 5.1 and Sec. 5.2, and the routing sub-problem in Sec. 5.3

## 5.1 The Channel Assignment Sub-problem

We now construct a detailed model for the channel capacity region $H$, and discuss how the resulting channel assignment problem from (2) can be solved. The effective link bandwidth are determined by the signal-to-noise-and-interference ratio (SINR) of the transmission; following the Gaussian channel capacity model [20]:

$$c_e = b \log_2(1 + SINR_e), \quad SINR_e = \frac{G_{ee}P_e}{(\sum_{l \neq e} I_{le} \cdot P_l \cdot G_{le}) + \sigma^2}$$

Here $G_{ee}$, $P_e$ and $\sigma^2$ are gain, power and noise associated with a link respectively. $G_{le}$ and $\sigma^2$ denote the interference coefficient and noise from link $l$ to link $e$ respectively. $I_{le}$ is the channel correlation coefficient, which depends on the separation between channels used by $l$ and $e$, e.g., the separation between channels 1 and 4 is 3.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Power leakage for neighbouring 802.11g channels</figcaption></figure>

The correlation $I_{\gamma\gamma'}$ between two channels $\gamma$ and $\gamma'$ are known for all possible channel separations, as shown in Fig. 1 [2]. From this figure, the correlation between any two channels, either flexibly selected or pre-defined, can be found. For example, for the 13 IEEE 802.11 channels, $I_{\gamma_1\gamma_1} = 1.0$, $I_{\gamma_1\gamma_2} = 0.7906$, $I_{\gamma_1\gamma_3} = 0.5267$, and $I_{\gamma_1\gamma_7} = 0$. Furthermore, we assume the total budget at each node $v$ is $p_{v,max}$ and $O(v)$ is the set of outgoing links from node $v$. Then, the channel assignment problem for capacity maximization can be formulated as:
$$ \text{Maximize} \sum_{e \in E} \alpha_e c_e \qquad (4) $$

$$ \text{subject to} \quad c_e = b \log_2(1 + \text{SINR}_e), \forall e \in E $$

$$ \text{SINR}_e = \frac{G_{ee}p_e}{(\sum_{l \neq e} I_{\gamma_l \gamma_e} p_l G_{le}) + \sigma^2}, \forall e \in E $$

$$ \sum_{e \in O(v)} p_e \le p_{v,max}, \forall v \in V $$

$$ \gamma_e \in \Gamma, \forall e \in E $$

Without the discrete variables in $\gamma$, (4) can be solved using known techniques, such as using geometric programming or through a power control game [20]. The new challenge in (4) is to compute good channels for vector $\gamma$. In Sec. 5.2, we present a heuristic solution for efficiently solving $\gamma$, and evaluate its performance later in Sec. 6.

## 5.2 Heuristic Channel Assignment Algorithm

We design a heuristic channel assignment algorithm based on the interference factor $\varphi_{\gamma} = \sum_{\gamma' \in \Gamma} I_{\gamma \gamma'}/d_{\gamma}'$, for a given candidate channel $\gamma$. Here $d_{\gamma'}$ is the distance to the nearest node transmitting at channel $\gamma'$. In measurement-based systems, $d_{\gamma \gamma'}$ is not necessary because the node can sense if a channel is in use in the range of this node and signal strength could be used instead. In coordination-based systems, $d_{\gamma \gamma'}$ could be found based on the coordination information. We assume $d_{\gamma'} = \infty$ if channel $\gamma'$ is not in use in the network.

Our heuristic solution, Algorithm 1, performs a breadth-first-traversal of the WMN. At each node, candidate channels are sorted by the interference factor to already assigned channels at other nodes. Different options are possible in selecting the channel. A greedy algorithm selects the channel $\gamma$ with the smallest $\varphi_{\gamma}$ value, i.e., as apart from neighboring channels in use as possible. We propose a progressive channel assignment approach instead, and select a channel $\gamma$ with the highest $\varphi_{\gamma}$ below an acceptable threshold $\varphi_{th}$. The rational here is to look beyond channel assignment at the current node, and to leave good candidate channels for neighbor nodes.

Algorithm 1 consists of a double loop. The outer loop iterates through nodes in the network, and the inner loop iterates through all possible channels. The number of channels is 13 and therefore the total number of iterations is $13|V|$.

## 5.3 The Routing Sub-problem

The multicast flow routing problem at the network layer has been extensively studied in the literature during the past decade. Two classes of solutions have been proposed. The first class includes multicast tree based solutions. Since achieving optimal multicast throughput using multicast trees corresponds to the NP-hard problem of Steiner tree packing, one needs to resort to efficient approximation algorithms, such as the KMB
<caption>**Algorithm 1:** Progressive Channel Assignment</caption>

**Initialization:**
$\Gamma(v) := \emptyset, \forall v \in V$;
$\varphiSet := \emptyset$;
**forall the** $v \in V$ **do**
    **forall the** $\gamma \in \Gamma$ **do**
        Compute $\varphi_{\gamma}^v$;
        **if** $\varphi_{\gamma}^v \le \varphi_{th}$ **then**
            $\varphiSet := \varphiSet \cup \varphi_{\gamma}^v$;
        **if** $\varphiSet = \emptyset$ **then**
            Choose $\gamma_v$ with smallest $\phi_{\gamma_v}$ and activate it on node $v$;
        **else**
            Choose $\gamma_v$ from $\varphiSet$ with largest $\phi_{\gamma_v}$ and activate it on node $v$;
            $\varphiSet := \emptyset$
    **end**

algorithm. The second class includes network coding based solutions. By assuming information coding capabilities for nodes in the network, the complexity of the optimal multicast problem decreases from NP-hard to polynomial time solvable [9]. In particular, *conceptual flow* based linear programming models have been successfully developed for multicast in various network models [9, 20]. In this section, we apply similar techniques and formulate our routing sub-problem into a convex program with all-linear constraints, which can be solved using general convex optimization algorithms such as the interior-point algorithm [4], or tailored subgradient algorithms [9].

We model flows from each of the gateways to different destinations as conceptual flows that do not compete for link bandwidth. $e_l^{i,j}$ denotes the conceptual flow rate on link $l$ in $i$th multicast session to its $j$th destination. $I(v)$ is set of incoming links to node $v$ and $O(v)$ is the set of outgoing links from node $v$. The multi-gateway multicast routing sub-problem with network coding can be stated as below. For compact LP formulation, the convention of assuming a virtual feedback link from multicast receivers to sources is followed [9].

$$
\begin{array}{ll}
\text{Max } U(r) - \sum_{e \in E} \alpha_e \sum_{s \in G} \sum_{t \in T_s} f_e^t & \\
\text{s.t.} & r^t \le \sum_{t \in T_s} \sum_{l \in I(D_j^{i,t})} e_l^{i,j}, \forall i, \forall j, \forall D_j^{i,t} \in V, \forall t \in T_s \\
& e_l^{i,j} \le f_l^i, \forall i, \forall j, \forall l \in E \\
& \sum_{l \in O(v)} e_l^{i,j} = \sum_{l' \in I(v)} e_{l'}^{i,j}, \forall v \in T_s, \forall i, j \\
& f_l^i \ge 0, e_l^{i,j} \ge 0, r^t \ge 0
\end{array}
$$
# 6 Simulation Results

We have implemented the overall primal-dual solution framework, the sub-problem solutions, to examine their performance. For comparison purposes, we have also implemented two other solutions: (a) orthogonal channel assignment and (b) consecutive channel assignment. In (a), the 13 802.11 channels are assigned to mesh nodes in a consecutive fashion (from channel 1 to 13, then back to 1), during a BFS traversal. In (b), the greedy approach of selecting a channel with maximum separation is adopted.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Maximum throughput (Mbps) vs. number of nodes</figcaption></figure>

For results shown in Fig. 2 and Fig. 3, the network area varies from $10^5$ to $10^6 m^2$, with 6 to 60 nodes equipped with radios running IEEE 802.11 protocol and transmission power of $1mW$. The area is square-shaped and the nodes are placed randomly. Half of the nodes act as receivers in a multicast session. The link capacities are computed using $c_e = b \log_2(1 + SINR_e)$. The variance of the number of nodes is intended for observing the performance of the solutions with different levels of interference. First we observe the channel assignment in different methods, our proposed channel assignment algorithm, orthogonal channel assignment (BFS on neighbours of a node then assign channels with maximum difference) and consecutive channel assignment (BFS on neighbours of a node then assign channels consecutively). An overall observation in Fig. 2 and Fig. 3 is that our solution leads both orthogonal and consecutive channel assignment methods, with a largest margin of up to 100%. The improvement increases as the network size increases. Note that the throughput of orthogonal channel assignment and our proposed algorithm could be improved by scheduling mechanisms.

Fig. 4 and 5 show results similar to those in Fig. 2 and 3, but with less number of data sessions, and therefore lower level of interference. The primal-dual solution still performs better overall, but the leading margin is less obvious. We also note the
<figure><img src="image_4.png" /><figcaption>Fig. 3. Maximum throughput (Mbps) vs. area</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. Maximum multicast throughput (Mbps) vs. number of nodes</figcaption></figure>

throughput measured is more or less unstable. That is due to the randomness in the network topologies used in the simulations. Intuitively, when interference is low and not a serious concern, a judiciously designed multi-channel transmission scheme becomes less important. We conclude that our proposed solution is more beneficial when applied in networks with high transmission activities and high interference.
<figure><img src="image_6.png" /><figcaption>Fig. 5. Maximum multicast throughput(Mbps) vs. area</figcaption></figure>

# 7 Conclusion

Multicast applications that require high throughput have recently gained popularity. We studied in this paper the challenges in achieving high multicast throughput in wireless mesh networks. Two techniques in system design were assumed: introducing multiple mesh gateways for mitigating the gateway bottleneck problem and utilizing multiple wireless channels for combating wireless interference. Our overall solution framework is a primal-dual schema based on a mathematical programming formulation of the optimal multicast problem. The framework iteratively switches between solving primal sub-problems for channel allocation and routing, and dual variable update, and gradually progresses towards optimal or approximately optimal solutions. We further presented precise models for each primal sub-problem, and discussed solutions for each of them. Simulation results confirmed the proposed solutions, in considerate throughput gains that were observed over straightforward approaches of multi-channel multicast.

# References

1. Akyildiz, F., Wang, X.: A survey on wireless mesh networks. IEEE Communications Magazine, Issue 43, No.9, 23-30 (2005)

2. Angelakis, V., Traganitis, A., Siris, V.: Adjacent channel interference in a multi-radio wireless mesh node with 802.11a/g interfaces. IEEE INFOCOM poster session (2007)

3. Alicherry, M., Bhatia, R., Li, L.: Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. ACM MobiCom, 58-72 (2005)

4. Bertsimas, B., Tsitsiklis, J. N.: Introduction to Linear Optimization. Athena Scientific, Belmont, Massachusetts (1997)

5. Chiu, H. S., Yueng, K. L., Lui, K.: J-CAR: An efficient joint channel assignment and routing protocol for IEEE 802.11-based multi-channel multi-interface mobile ad-hoc networks. IEEE Transactions on Wireless Communications, Vol. 8, No. 4, 1706-1714 (2009)
6. Gong, M. X., Midkiff, S. F., Mao, S.: Design principles for distributed channel assignment in wireless ad-hoc networks. IEEE ICC, 3401–3406 (2005)

7. Ko, B., Misra, V., Padhye, J., Rubenstein, D.: Distributed channel assignment in multi-radio 802.11 mesh networks. IEEE WCNC, 3978–3983 (2007)

8. Li, J., Blake, C., De Couto, D.S.G, Lee, H. I., Morris, R.: Capacity of ad-hoc wireless networks. ACM MobiCom, 61–69 (2001)

9. Li, Z., Li, B., Lau L. C.: On Achieving Maximum Multicast Throughput in Undirected Networks. IEEE Transactions on Information Theory, Vol.52, No. 6, 2467-2485 (2006)

10. Ling, X., Yeung, K. L.: Joint access point placement and channel assignment for 802.11 wireless LANs. IEEE Transactions on Wireless Communications, Vol. 5, No. 10, 2705–2711(2006)

11. Merlin, S., Vaidya, N., Zorzi, M.: Resource allocation in multi-radio multi-channel multi-hop wireless networks. IEEE INFOCOM, 610–618 (2008)

12. Mishra, A., Banerjee, S., Arbaugh, W.: Weighted coloring-based channel assignment for WLANs. ACM SIGMOBILE, 19–31 (2005)

13. Mohsenian Rad, A. H., Wong V.W.S.: Joint channel allocation, interface assignment and MAC design for multi-channel wireless mesh networks. IEEE INFOCOM, 1469–1477 (2007)

14. Nguyen, U. T., Xu, J.: Multicast routing in wireless mesh networks: minimum cost trees or shortest path trees. IEEE Communications Magazine, Vol. 45, 72–77 (2007)

15. Ramachandran, K. N., Belding, E.M., Almerot, K.C., Buddhikot, M.M.: Interference-aware channel assignment in multi-radio wireless mesh networks. IEEE INFOCOM, 1–12 (2006)

16. Rong, B., Qian, Y., Lu, K., Qingyang, R.: Enhanced QoS multicast routing in wireless mesh networks. IEEE Transactions on Wireless Communications, Vol.7, No.6, 2119–2130 (2008)

17. Approximation Algorithms. Springer, (2001)

18. Villegas, E. G., Lopez-Aguilera, E., Vidal, R., Paradells, J.: Effect of adjacent-channel interference in IEEE 802.11 WLANs. Crowncom, 118–125 (2007)

19. Wu, Y., Chou, P. A., Jain, K.: A comparison of network coding and tree packing. IEEE ISIT, 143- (2004)

20. Yuan, J., Li, Z., Yu, W., Li, B.: A cross-layer optimization framework for multihop multicast in wireless mesh networks. IEEE Journal on Selected Areas in Communication, Vol. 24, No. 11, 2092–2103 (2006)

21. Zeng, G., Wang, B., Ding, Y., Xiao, L., Mutka, M. W.: Efficient multicast algorithms for multi-channel wireless mesh networks. IEEE Transactions on Parallel and Distributed Systems, Vol. 21, No. 1, 86–99 (2010)