# Minimum Interference Channel Assignment Algorithm for Multicast in a Wireless Mesh Network
## 3 Minimum Interference Channel Assignment
### Calculating a Channel Separation of All Pairs of Nodes  
MICA first computes the channel separation of all pairs of nodes in a multicast tree. In the first step, the algorithm considers only a pair of nodes which are not a leaf node in the tree. _Channel Separation_ is defined as the difference in channel numbers which are used by the two pairs of nodes [29]. When calculating the channel separation of two pairs, MICA examines every pair of nodes in the tree to minimize network interference between two nodes. Algorithm 1 shows the algorithm of calculating channel separation of all pairs of nodes. This algorithm needs to calculate the channel separation of all pairs of nodes in the network, so the time complexity of the algorithm is \((n)\), where \(n\) is the total number of nodes in the network. ```
1:input:\(T\), a multicast tree
2:output:\(CS\)<\(u\), \(v\)>, the channel separation of all pairs of nodes in \(T\)
3:procedureCALCULATING THE CHANNEL SEPARATION OF ALL PAIRS OF NODES
4:for each pair of nodes \((u,v)\in T\)do
5:\(C_{u}\leftarrow\) the set of \(u\)'s children
6:\(C_{v}\leftarrow\) the set of \(v\)'s children
7:\(MAX_{u}\gets 0\)
8:\(MAX_{v}\gets 0\)
9:for each node \(i_{u}\in C_{u}\)do
10:\(CS\)<\(v\), \(i_{u}\)> \(\leftarrow\) channel separation between \(v\) and \(i_{u}\)
11:\(MAX_{v}\leftarrow\) a maximum value between \(MAX_{v}\) and \(CS\)<\(v\), \(i_{u}\)>
12:end
13:for each node \(i_{v}\in C_{v}\)do
14:\(CS\)<\(u\), \(i_{v}\)> \(\leftarrow\) channel separation between \(u\) and \(i_{v}\)
15:\(MAX_{u}\leftarrow\) a maximum value between \(MAX_{u}\) and \(CS\)<\(u\), \(i_{v}\)>
16:end
17:\(CS\)<\(u\), \(v\)> \(\leftarrow\) a maximum value between \(MAX_{u}\) and \(MAX_{v}\)
18:end
```  
**Algorithm 1**Calculating Channel Separation  
The purpose of the first step is to compute the channel separation of all pairs of nodes in the multicast tree. First, MICA considers all pairs of nodes \((u,v)\) in the given tree. Next, it attempts to obtain the channel separation between \(u\) and \(v\)'s children and \(v\) and \(u\)'s children. We use an interference factor to compute the channel separation of two nodes. As mentioned before, the interference factor is defined as the ratio of an interference range to a transmission range. From this definition, we can obtain the interference range by multiplying the interference factor by the transmission range. If a physical distance of two comparing nodes is within the obtained interference range, these two nodes may interfere with each other. However, we can eliminate network interference between two nodes by increasing channel separation. According to Table 1, as the value of channel separation increases, an interference factor decreases. For example, if channel separation is greater than, or equal to, 5 there is no interference between two nodes in an 802.11b network. Consequently, we can get channel separation with no interference between two nodes if we can acquire channel separation in which the physical distance of two nodes is greater than the interference range of these two nodes. Finally, we can decide the final channel separation between \(u\) and \(v\) by choosing the maximum channel separation value among \(u\) and \(v\)'s children and \(v\) and \(u\)'s children. We assume that all wireless nodes have the same transmission range 250 m in the multicast tree shown in Figure 2. As mentioned before, we do not consider leaf nodes in the first step. Therefore, we only think about the combination of all nodes except F, G, and I in the tree. For instance, we want to calculate the channel separation of S and A. MICA always looks at the opponent's children to totallyeliminate network interference between two nodes. In the case of [PERSON] and A pair, [PERSON]'s children are A and B and [PERSON]'s child is C. As a result, (S, C) and (A, B) pairs will be considered to calculate the channel separation of S and A.