# Minimum Interference Channel Assignment Algorithm for Multicast in a Wireless Mesh Network
## 3 Minimum Interference Channel Assignment
### Finding Channel Separation of Zero  
Finding channel separation of zero is the second step. There are two situations in this step. The first scenario is that there is \(CS_{zero}\) between two nodes. The other case is that there exists no pair of nodes with \(CS_{zero}\). In this step, we first find \(CS_{zero}\) in a multicast tree. If there is no \(CS_{zero}\), we try to discover channel separation of a maximum value. The algorithm of finding \(CS_{zero}\) is represented in Algorithm 2. Like the algorithm of calculating the channel separation in Section 3.1, the time complexity of finding channel separation of zero is also \((n)\), where \(n\) is the total number of nodes in the network. \(CS_{zero}\) means that there is no channel difference between two nodes. In other words, although two nodes use the same channel number at the same time, there is no interference between these two nodes. It is very important to find \(CS_{zero}\) because available channel numbers are limited. The second step takes a multicast tree and the channel separation obtained from the first step as the input. We define two sets of nodes, \(S_{D}\) and \(S_{N}\) in this phase. While \(S_{D}\) contains nodes that acquire their own channel number, \(S_{N}\) holds nodes that do not have a channel number. These sets are the output of the second step. For each pair of nodes, \(u\) and \(v\), in a multicast tree, MICA investigates whether there is \(CS_{zero}\) or not. If it exists, the given algorithm (Algorithm 2) assigns a specific channel number, a channel number 6, to the sending interface of \(u\) and \(v\). Especially, we use a certain channel number 6 in this algorithm because this number is one of the orthogonal numbers as we mentioned before. Furthermore, it could be possible to eliminate network interference the first time as we discussed before. Then, \(u\) and \(v\) are allocated to \(S_{D}\) and the rest of the nodes except \(u\) and \(v\) are assigned to \(S_{N}\). Next, if \(S_{D}\) is not empty, the algorithm keeps searching if there is \(CS_{zero}\) between node \(i\) in  
Figure 2: Multicast tree and children of S and A.  
and all of the nodes in \(S_{D}\). Whenever obtaining \(CS_{zero}\), we can remove \(i\) from \(S_{N}\) and put it into \(S_{D}\). This procedure continues until there is no \(CS_{zero}\). Otherwise, for every \((u,v)\), we just select a channel separation of a maximum value between \(u\) and \(v\). After that, we need to assign channel number 6 to one of these nodes and the summation of channel number 6 and the maximum channel separation value to the other node as its channel number. Finally, we put \(u\) and \(v\) to \(S_{D}\) and all nodes except \(u\) and \(v\) to \(S_{N}\). ```
1:input:\(T\), a multicast tree
2:CS\(<\)\(u\), \(v>\), the channel separation of all pairs of nodes in \(T\)
3:output:\(S_{D}\), the set of nodes with a channel number for their sending interface
4:\(S_{N}\), the set of nodes without a channel number for their sending interface
5:procedureFINDING CHANNEL SEPARATION OF ZERO
6:for each pair of nodes \((u,v)\in T\)do
7:ifCS\(<\)\(u\), \(v>\) == 0 then
8: sending interface of \(u\leftarrow\) channel number 6
9: sending interface of \(v\leftarrow\) channel number 6
10:\(S_{D}\gets u\), \(v\)
11:\(S_{N}\leftarrow\) all nodes except \((u,v)\) in \(T\)
12:break
13:end
14:end
15:if\(S_{D}\
eq\varnothing\)then
16:for each node \(i\in S_{N}\)do
17:ifCS\(<\)\(i\), \(j\) == 0 for all \(j\in S_{D}\)then
18: sending interface of \(i\leftarrow\) channel number 6
19: remove \(i\) from \(S_{N}\)
20:\(S_{D}\gets i\)
21:end
22:end
23:end
24:end
25:else
26: find \(u\), \(v\in T\) such that \(CS\)\(<\)\(u\), \(v>\) is a maximum
27: sending interface of \(u\leftarrow\) channel number 6
28: sending interface of \(v\leftarrow\) channel number 6 + CS\(<\)\(u\), \(v>\)
29:\(S_{D}\gets u\), \(v\)
30:\(S_{N}\leftarrow\) all nodes except except \((u,v)\) in \(T\)
31:end
```  
**Algorithm 2**Finding Channel Separation of Zero  
Let us think about the following example to illustrate the second step.