# High Throughput and Acceptance Ratio Multipath Routing Algorithm in Cognitive Wireless Mesh Network
## 3 Multipath Routing and Spectrum Allocation Algorithm
### Primary Path Spectrum Allocation Algorithm  
When the primary path \(\alpha(s_{i},d_{i})\) is constructed, a channel on each link of the path is allocated. The primary path spectrum allocation algorithm (PPSR) is proposed in this section. The PPSR algorithm is seen in Line 16 of Algorithm 1. For each link (\(u\),\(v\)) in the primary path \(\alpha(s_{i},d_{i})\), if the link (\(u\),\(v\)) is allocated a channel, then its previously allocated channel is used continually. If the link (\(u\),\(v\)) is not allocated a channel, then the channel on the link is allocated through Equation (10). However, when the primary path is allocateda channel, the situation that is shown in Figure 1 may occur. The following example illustrates the situation, and the solution is also presented. We assume that \(\gamma_{1}\) = (_A_,\(B\),_S_), \(\gamma_{2}\) = (_C_,\(D\),10), and \(\gamma_{3}\) = (_IJ_,12) is the accepted wireless request. The primary path of \(\gamma_{1}\), \(\gamma_{2}\), and \(\gamma_{3}\) are \(A\xrightarrow{2}B\), \(C\xrightarrow{4}D\), and \(I\xrightarrow{4}J\), respectively. The new arriving wireless request is \(\gamma_{4}\) = (_E_,\(G\),_6_). Table 1 shows the results of the wireless link weight when the link (_E_,_F_) and (_F_,_G_) are allocated different channels. The calculating formula of \(f_{1}^{4}(F,G)\) is given by  
\[f_{1}^{4}(F,G)=\frac{(|\delta^{4}(F,G)|+1)}{(|\epsilon^{4}(F,G)|+1)(|\varphi^{ 4}(F,G)|+1)}=\frac{2+1}{(0+1)(0+1)}=3 \tag{10}\]  
For the convenience of depiction, the backup path of the accepted wireless request is not shown in Figure 1. Hence, \(\epsilon^{4}(F,G)=\phi\) and \(\varphi^{4}(F,G)=\phi\). We can see from Table 1 that the primary path \(E\xrightarrow{3}F\xrightarrow{3}G\) of \(\gamma_{4}\) is constructed by the PPC algorithm. Interflow interference is not considered by the PPC algorithm, which means that the available bandwidth of the wireless link (_E_,_F_) and (_F_,_G_) is shown in Equations (11) and (12) before the link (_E_,_F_) allocated on channel 3. \[ \begin{split}\text{B}_{\psi}^{3}(E,F)&=B^{3}(1- \frac{l_{(A,B)}^{3}}{B^{3}})=17(1-\frac{9}{17})=9\\ \text{B}_{\psi}^{3}(F,G)&=B^{3}(1-\frac{l_{(A,B)}^{3 }}{B^{3}})=17(1-\frac{9}{17})=9\end{split}  \tag{11}\]  
We can see that the available bandwidth of (_E_,_F_) and (_F_,_G_) can meet the needs of the bandwidth constraints of \(\gamma_{4}\). However, after the available bandwidth of links (_E_,_F_) and (_E_,_F_) is allocated to channel 3, then the available bandwidth of link (_F_,_G_) is given by  
\[\text{B}_{\psi}^{3}(F,G)=B^{3}(1-\frac{l_{(A,B)}^{3}}{B^{3}}-\frac{l_{(E,F)}^{ 3}}{B^{3}})=17(1-\frac{8}{17}-\frac{6}{17})=3 \tag{13}\]  
We can see that the available bandwidth of link (_F_,_G_) could not meet the need of the bandwidth constraints of \(\gamma_{4}\). To solve the problem shown in Figure 1, the allocated channel of the link was adjusted. The basic idea was to sort the link (_u_,_v_) on each channel according to the non-descending order of the \begin{table}
\begin{tabular}{c c c c c} \hline (_u_,_v_) & _x (u_,_v_) & _R (u_,_v_) & _\(\delta^{k}(u,v)\)_ & _\(f_{1}(u,v)\)_ \\ \hline (_E_,_F_) & 3 & (\(|\)A_,_B_) & \(|\){(_A_,_B_)}\(|\) & 2 \\ (_F_,_G_) & 3 & (\(|\)A_,_B_) & \(|\){(_A_,_B_)}\(|\) & 2 \\ (_F_,_G_) & 4 & (\(|\)C_,_D_),(_IJ_),\(|\) & (\(|\)C_,_D_),(_IJ_),\(|\) & 3 \\ \hline \end{tabular}
\end{table} 
Table 1: The link weight of (_E_,_F_) and (_F_,_G_). Figure 1: The situation of bandwidth constraints cannot be met. value of \(f_{1}^{k}(u,v)\). If the link (\(u\),\(v\)) on channel \(k\) with the residual bandwidth \(\mathrm{B}_{\varphi}^{k}(u,v)\) was larger than the bandwidth constraint \(b_{i}\), and less \(f_{1}^{k}(u,v)\) was found, then the channel \(k\) was allocated to link (\(u\),\(v\)). The fundamental idea of the PPSR algorithm is as follows: for all of the links (\(u\),\(v\)) of \(\alpha(s_{i},d_{i})\), if the link (\(u\),\(v\)) is allocated a channel, then the link keeps the same allocated channel.