# Adaptive Allocation Algorithm for Multi-Radio Multi-Channel Wireless Mesh Networks
## 3 Mathematical Formulation of Adaptive Channel Allocation Problem
### Network Mathematical Model  
In this section, we formulate the mathematical model for the network. Suppose that the WMN is described as graph topology \(G=(V,E)\). The graph \(G\) is a mathematical structure consisting of two sets, \(V\) and \(L\). The set \(V\) is the set of vertices (or nodes) in our WMN. As mentioned before, we shall refer to a node as an AP. Therefore, \(V=\{AP_{1},AP_{2},\cdots,AP_{N}\}\) where \(N\) is the network's total number of APs. Elements of \(E\) represent the wireless links between APs; consequently, \(E=\{l_{ij}:l_{ij}=(AP_{i},AP_{j}),AP_{i},AP_{j}\in V\}\). One element in \(V\) functions as the GW. We suppose that the AP is called \(AP_{GW}\). The maximum number of NICs that can be installed in \(AP_{i}\) is \(m_{i}\). The set of non-overlapped channels (\(NOC\)) in WMN is defined as \(C_{NOC}=\{c_{1},c_{2},\cdots,c_{k}\}\), where, \(k\) is the total number of channels.  
Let \(F\) be the interference matrix between links.  
\[F=\|f_{ijpq}\|,i,j,p,q\in\{1,2,\cdots,N\}\]  
where  
\[f_{ijpq}=\begin{cases}1,&\text{if $l_{ij}$ is interfered $l_{pq}$,}\\ 0,&\text{otherwise.}\end{cases}\]  
To utilize the maximum throughput through the network, we calculate the traffic between APs through links, and suppose that \(t_{ij}\) is the expected throughput between \(AP_{i}\) and \(AP_{j}\) where \(i,j\in\{1,2,\cdots,N\}\).  
In the proposed model, the number of distributed NICs per each AP is calculated through our procedure. Let \(n_{i}\) be the number of NICs calculated by our method for \(AP_{i}\).  
Suppose that \(C\) is the matrix of interfered channels, such that  
\[C=\|C_{ij}\|,i,j\in\{1,2,\cdots,k\}\]  
where  
\[c_{ij}=\begin{cases}1,&\text{if $i=j$,}\\ 0,&\text{otherwise.}\end{cases}\]  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Definition** \\ \hline \(l_{ij}\) & link between the access point (AP) \(AP_{i}\) and \(AP_{j}\) \\ NOC & non-overlapped channels \\ \(F\) & interference matrix between links \\ \(t_{ij}\) & expected throughput between \(AP_{i}\) and \(AP_{j}\) \\ \(C\) & the matrix of interfered channels \\ \(m_{i}\) & the maximum number of network interface cards (NICs) that can be allowed to \(AP_{i}\) \\ \(n_{i}\) & the output assigned number of NICs to \(AP_{i}\) \\ \(ch_{ij}\) & the assigned channel to \(l_{ij}\) \\ \(FNIC\) & maximum number of hosts per one NIC \\ \(Flink\) & total interference of gateway (GW) adjacent links \\ \(FStop\) & number of channel re-allocations \\ \hline \hline \end{tabular}
\end{table}
Table 1: Formulation notations.  
For the standard of the IEEE802.11 ax protocol with the orthogonal frequency-division multiplexing (OFDM) [23], a radio signal is divided into smaller sub-signals in the OFDM and placed at different frequencies on separate orthogonal channels. This uses the available spectrum effectively and is less susceptible to interference [24; 25].  
In this work, we suppose that each AP is associated with the most extreme number of hosts as we designed the network according to the greatest burden for each AP. To compute the total number of NICs appointed to each AP in the whole network, certain critical physical constraints should be applied to the algorithm, and these constraints are as follows:  
1. The total number of NICs over the network should not exceed \(M=\sum\limits_{i}^{N}m_{i}\).
2. The output number of assigned NICs for \(AP_{i}\) should be at least one. Suppose it will be \(n_{i}\), therefore, \(1<n_{i}<m_{i}\) where \(i\in\{1,2,\cdots,N\}\).
3. Each link \(l_{ij}\) should be assigned to a channel \(ch_{ij}\), where \(ch_{ij}\in\{c_{1},c_{2},\cdots,c_{k}\}\).
4. The maximum number of assigned channels is \(k\).
5. The chosen channel for the link \(l_{ij}\) at both APs' NIC must be the same \(ch_{ij}=ch_{ji}\).
6. The number of channels assigned to the links adjacent to \(AP_{i}\) must be \(n_{i}\) or less.