# Marginal Contribution-Based Distributed Subchannel Allocation in Small Cell Networks
## 4 Distributed Algorithm for Subchannel Allocation
### Marginal Contribution-Based Best-Response Algorithm  
MCBR is described in Algorithm 1. Here, we assume that all SBSs are synchronized and time is divided into time slots of a fixed duration. Each time slot is further divided into two phases, called the _sensing_ phase and the _payload_ phase. Here, we consider the sensing phase alternating with the payload phase. During the sensing phase, SBSs learn the utilities for different subchannels and make the decision to select the subchannel providing with highest utility. In the payload phase, the SBS transmits on the selected subchannel. In the sensing phase of time slot \(t\), a link \(i\) is selected to update its strategy. During this sensing phase, all other links keep transmitting on the subchannel used in the previous time slot \(t-1\). The link \(i\) selects a new subchannel for sensing according to the subchannel selection probability vector \(\mathbf{p}_{i}\). Here, \(\mathbf{p}_{i}=\{p_{i,1}(t),\ldots,p_{i,K}(t)\}\), where each element \(p_{i,k}(t)\) is the probability of choosing subchannel \(k\) at time slot \(t\) by link \(i\). The SBS for link \(i\) measures the utilities on the new sensing subchannel and the subchannel allocated in the previous time slot, i.e., for strategies \(s_{i}=k^{\prime}\) and \(s_{i}=k_{t-1}\), according to Equation (11). Note that, in order to calculate the two utilities, link \(i\) only needs to receive capacity reports of links \(j\in\mathcal{J}_{i}\) that are transmitting on those two subchannels. Now, the subchannel with highest utility is determined based on the BR dynamics, such that,  
\[\text{BR}_{i}(\mathbf{s}_{j})=\arg\max_{s_{i}\in\{k^{\prime},k_{t-1}\}}u_{i}^{ \text{MC}}(s_{i},\mathbf{s}_{j}) \tag{12}\]  
From Equation (12), link \(i\) would best respond to switch to the new sensing subchannel \(k^{\prime}\) if the utility \(u_{i}^{\text{MC}}(s_{i}=k^{\prime},\mathbf{s}_{j})>u_{i}^{\text{MC}}(s_{i},=k_{t-1 },\mathbf{s}_{j})\). Otherwise, link \(i\) would stay with the subchannel selected in the previous time slot, i.e., subchannel \(k_{t-1}\). ```
01: Initialization: (at time slot \(t=0\))
02: Get synchronization
03: Set subchannel selection probability of each link as \[p_{i,k}(t)=\frac{1}{K},\ \ \ \ \ \forall i\in\mathcal{M},k\in\mathcal{K}\]
04: Randomly select a subchannel \(k_{t}\) for all links \(i\) according to the subchannel selection probability vector \(\mathbf{p}_{i}\)
05: In **sensing phase** of time slot \(t=1,2,\ldots\):
06: Select a link \(i\) in predetermined round-robin fashion
07: Select a new sensing subchannel \(k^{\prime}\) according to \(\mathbf{p}_{i}\)
08: Receive capacity reports of links \(j\in\mathcal{J}_{i}\) for strategies \(s_{i}=k_{t-1}\) and \(s_{i}=k^{\prime}\)
09: Measure utilities according to Equation (11) for strategies \(s_{i}=k_{t-1}\) and \(s_{i}=k^{\prime}\)
10: Determine a subchannel \(k_{t}\) with the highest utility according to Equation (12)
11: Update subchannel selection probabilities such that, \[p_{i,k}(t)= \begin{cases}p_{i,k}(t-1)+\beta\tilde{r}_{i}(1-p_{i,k}(t-1)),\text {if }k=k_{t}\\ p_{i,k}(t-1)-\beta\tilde{r}_{i}p_{i,k}(t-1),\ \text{ otherwise}\end{cases} \] where \(0<\beta=\frac{1}{K}<1\) is learning step-size, and \(\tilde{r}_{i}\) is normalized utility increment given by \[\tilde{r}_{i}=\frac{u_{i}^{\text{MC}}(s_{i}=k_{t},\mathbf{s}_{j})}{u_{i}^{\text{ MC}}(s_{i}=k_{t},\mathbf{s}_{j})+u_{i}^{\text{MC}}(s_{i}=k_{t-1},\mathbf{s}_{j})}\]
12: In **payload phase** of time slot \(t\):
13: Link \(i\) transmits on subchannel \(k_{t}\)
14: Set \(t\gets t+1\), go to step 05
```  
**Algorithm 1** MCBR used by SBSs for links it handles. At the end of the sensing phase, the SBS for link \(i\) chooses the subchannel with the highest utility for transmission in the payload phase (the rest of time slot \(t\)) and updates the subchannel selection probabilities in \(\mathbf{p}_{i}\) according to the received utility as shown in step 11.