# Adaptive Allocation Algorithm for Multi-Radio Multi-Channel Wireless Mesh Networks
## 4 Adaptive Channel Allocation Algorithm
### The Initial Channel Allocation
#### 4.1.1 NIC Deploying Stage  
Through this stage, one NIC is deployed to an AP subjected to the maximum traffic load per previously assigned (\(t^{N}IC\)) (if this exists) is reached, and all constraints are fulfilled, so that \(FNIC\) is minimized. This step is repeated for each AP until the maximum load is reached.  
1. **NIC Initialization** 1.  Compute the load per AP from link traffic \(t_{ij}\): \[t_{i}^{AP}=\sum_{j\in G_{i}}(t_{ij}+t_{ji}).\] (4) 2. Allocate one NIC to every AP: \(n_{i}=1\) as a default. 3. Assign the traffic for each NIC by : \[t_{i}^{NIC}=\frac{t_{i}^{AP}}{n_{i}}.\] (5) 4. Set the number the allocated NICs: AN = N.
2. **NIC Deployment** 1.  Add one NIC to an AP (suppose \(AP_{s}\)) where \(t_{s}^{NIC}\) reaches the maximum load while maintaining \(m_{s}<n_{s}\). After that, \(n_{s}++\) and \(AN++\). 2. Stop the phase if \(AN=M\) or the physical constraint (\(n_{s}=m_{s}\)) is reached for every AP. 3. Recalculate the traffic : \[t_{s}^{NIC}=\frac{t_{s}^{AP}}{n_{s}}.\] (6) 4. Return to step (i).  
The output of the fixed channel allocation phase is a set of channels assigned to the deployed NICs in Section 4.1.1. This phase assigns one channel to one link such that the function \(Flink\) is minimized according to the following steps.  
1. Compute the collision for the traffic: \[col_{ij}=t_{ij}\cdot\sum_{p=1}^{N}\sum_{q=p+1}^{N}t_{pq}\cdot f_{ijpq}.\] (7)
2. Arrange the links according to the collision in a descending order.
3. Allocate \(c_{1}\in NOC\) to the most crowded link, let \(l_{ij}\) be the first link, and assign \(c_{1}\) to both \(AP_{i}\)'s first NIC and \(AP_{j}\)'s first NIC.  
4. Allocate the links' channel according to the following filtration steps: 1. _Manadatory channel allocation_: 1. _Mandatory channel allocation_: 1. _Allocate_ \(c_{p}\in NOC\) _to link_ \(l_{ij}\) _if both_ \(AP_{i}\) _and_ \(AP_{j}\) _have NICs allocated to_ \(c_{p}\)_. If there are two or more such_ \(c_{p}\) _for both_ \(AP_{i}\) _and_ \(AP_{j}\)_, select the channel that minimizes_ \(Flink\) _without consideration to un-allocated links. 2. _If_ \(AP_{i}\) _has only one NIC allocated with_ \(c_{p}\in NOC\)_, and_ \(AP_{j}\) _has no channel, then the link_ \(l_{ij}\) _is allocated_ \(c_{p}\) _and one_ \(AP_{j}\)_'s NIC allocates to the same channel. 2. _Variety channel allocation_: 1. _For each link_ \(l_{ij}\)_,_ \(AP_{i}\) _and_ \(AP_{j}\) _have both un-allocated NICs, then select_ \(c_{p}\in NOC\) _that minimizes_ \(Flink\) _without consideration to un-allocated links. 2. _if_ \(AP_{i}\) _and_ \(AP_{j}\) _have two or more NICs in allocated channels_ \(NOC_{g}\subseteq NOC\)_, then the link_ \(l_{ij}\) _is allocated_ \(c_{p}\in NOC_{g}\) _to minimize_ \(Flink\) _without consideration to un-allocated links. 3. _Priority channel allocation change_: If_ \(AP_{i}\) _and_ \(AP_{j}\) _are allocated to_ \(c_{p}\) _and_ \(c_{q}\) _sequentially and_ \(c_{p}\
eq c_{q}\) _and_ \(l_{ij}\) _is not an allocated channel, then the channel allocation priority for that link is increased. Return to step 2 after multiplying_ \(col_{ij}\) _by a constant number greater than one. 4. _Manage un-utilized NICs_: After the completion of channel allocation for every link in the network, if there are unused NICs, these NICs are switched to other APs with the maintenance of the constraints, and then return to step 2.