## 4 Quality-Aware Routing and Channel Assignment in Multi-Channel Multi-Gateway WOBAN
### Our Proposed Genetic Algorithm for Channel Selection  
Genetic algorithms are iterative optimization techniques influenced from the natural evolutionary process. In a genetic algorithm, the candidate solutions are embedded in _chromosomes_ whose _fitness values_ represent the quality of the corresponding solutions. The chromosomes are evolved from one generation to the other by using the _survival of the fittest_ paradigm. In every generation, the offspring chromosomes are produced from the previous generation by using two genetic operators: _crossover_ and _mutation_. The detailed description of the genetic algorithm is discussed as follows:  
_Genetic Representation:_ Let us assume that \(U\) is the number of vertices in GCL, and \(C\) is the number of available channels. We define a chromosome as a vector \((c_{1},c_{2},\dots,c_{U})\), where \(c_{i}\) is the channel/color assigned to vertex \(i\). For example, with \(U=6\), a chromosome 314,252 represents that the vertices \(\{1,2,3,4,5,6\}\) are assigned channels \(\{3,1,4,2,5,2\}\), respectively. We assume that there are \(M\) chromosomes in a _mating pool_. The initial mating pool is generated by assigning random channels in between \(1\) and \(C\) to the vertices of the GCL, such that the interface constraint is satisfied. The fitness value of the chromosomes are then calculated based on their quality metric with the assigned channels.  
_Selection and Reproduction Process:_ We use the well known _elitism_ based selection process, where the best \(M_{e}<M\) chromosomes from one generation are placed directly in the next generation. This ensures that the best chromosomes are preserved in the next generation. For the rest of the \(M-M_{e}\) chromosomes, (a) we choose \(M-M_{e}\) parent chromosomes using a _roulette wheel_ selection process (including the elitist ones), (b) which take part in crossover and mutation to generate  
Figure 6: Illustration of (**a**) \(K_{5}\) and (**b**) \(K_{3,3}\) graphs.  
offspring chromosomes. We use two-point crossover as shown in Figure 6(a). The mutation is carried out with a very low probability (assume to be 1% for our simulations), where we generate two random numbers in between 1 and \(U\) and interchange the colors of these vertices as shown in Figure 6(b). After the crossover/mutation, if the interface constraint is violated in the offspring chromosomes, we merge a few channels randomly to meet the constraint.  
The selection and reproduction process is repeated until the algorithm converges. Upon convergence, the chromosome/solution with the highest fitness value is chosen. This process is repeated for all the candidate routes, and finally the route with highest fitness value/quality is selected along with its channel assignment.  
We now calculate the reduction of the convergence time of the genetic algorithm achieved by reducing the vertices in GCL (as the genetic algorithm is applied only on GCL). As mentioned in [47], the probability that the genetic algorithm converges at generation \(t\) of chromosome length \(l\) is given by  
\[P(t,l)=\left[1-\frac{6p_{0}(1-p_{0})}{M}\left(1-\frac{2}{M}\right)^{t}\right] ^{l}, \tag{6}\]  
where \(p_{0}\) is the initial frequency of the allele and \(M\) is the population size (_mating pool_ size). Assume a scenario where \(M=1000\) and \(p_{0}=0.5\). Now, to obtain 90% probability of convergence (i.e., \(P(t,l)=0.9\)), a genetic algorithm takes 522 generations to converge with 200 bit chromosomes (i.e., \(l=200\)). However, reducing the chromosome length by 50% (i.e., \(l=100\)) ensures the algorithm to converge after 176 generations, which is about three times faster.