# Online Distributed User Association for Heterogeneous Radio Access Network
## 5 Performance Analysis  
In this section, we give an analytic model of the performance for the online algorithms by considering \(load_{1}\). The analysis for the \(load_{2}\) follows the same line. We first prove the fact that the BS utility function is submodular and monotone. Then, we show that the UE utility function exhibits the same outcome as BS utility. As a concrete example, we analyze the logarithmic UE utility \(\mathcal{U}_{i}(.)=\log(. )\), \(\forall i\in\mathds{U}\), which is commonly used in wireless networks to provide proportional fairness among UEs [17]. The utility of the BS is defined as the sum utility of its associated UEs. Under the logarithmic utility, the BS utility function becomes:  
\[\mathcal{V}_{j,k}(N_{j,k})=\sum_{i\in N_{j,k}}\log\Big{(}\frac{\eta_{i,j,k}}{ |N_{j,k}|}\Big{)},j\in\mathds{B},k\in\mathds{K},N_{j,k}\subset\Omega_{j,k} \tag{14}\]  
Definition 1: The UE utility function \(\mathcal{U}_{i}(\cdot)\) is submodular and monotone. Lemma 1: \(\mathcal{V}_{j,k}(N_{j,k})=\sum_{i\in N_{j,k}}\log(\frac{\eta_{i,j,k}}{|N_{j,k} |})\)_, \(k\in\mathcal{K},j\in B_{k},N_{j,k}\subset\Omega_{j,k}\) is submodular and monotone._  
Proof: Our proof is, in essence, similar to the proof given in Ref. [19]. Here, we present it for completeness. For submodularity, we have the following definition:  
For every \(N,O\subseteq\Omega\) with \(N\subseteq O\) and every \(i\in\Omega\) we have that \(\mathcal{V}(N\cup\{i\})-\mathcal{V}(N)\geq\mathcal{V}(O\cup\{i\})-\mathcal{V} (O)\). Let us first consider the case \(N\
eq\emptyset\). We have  
\[ \begin{array}{l}\mathcal{V}_{j,k}(i|N)=\mathcal{V}_{j,k}(N\cup\{i\})- \mathcal{V}_{j,k}(N).\\ =\sum_{l\in N\cup\{i\}}\log(\frac{\eta_{i,j,k}}{|N|+1})-\sum_{l\in N}\log( \frac{\eta_{i,j,k}}{|N|})\\ =\log(\eta_{i,j,k})+|N|\log|N|-(|N|+1)\log(|N|+1).\end{array}  \tag{15}\]  
For \(\mathcal{V}_{j,k}(i|N)\geq\mathcal{V}_{j,k}(i|O)\), is equivalent to \(|N|\log|N|-(|N|+1)\log(|N|+1)\geq|O|\log|O|-(|O|+1)\log(|O|+1)\). To show the marginal gain, \(\mathcal{V}_{j,k}(. )\) is a decreasing function, and we need to show that \(n\log n-(n+1)log(n+1)\) is a decreasing function for \(n>0\). \[ \begin{array}{l}f(n)=n\log n-(n+1)\log(n+1)\\ f^{{}^{\prime}}(n)=\log(n)-\log(n+1)\end{array}  \tag{16}\]  
The function \(f^{{}^{\prime}}(n)\) clearly is a decreasing function \(\forall n>0\). For the other case \(N=\emptyset\), we need to show that \(0\geq|O|\log|O|-(|O|+1)\log(|O|+1)\). The proof is straightforward, as \(|O+1|\geq|O|\) and \(\log(|O+1|)\geq\log(|O|)\), \(\forall\ |O|>0\). Thus, the expression \(\mathcal{V}_{j,k}(N)\geq\mathcal{V}_{j,k}(O)\) holds true for all cases. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Different Combinations of \(d\)** & **Average Jain’s Fairness** & **Total Number of Probe** \\ \hline \(d1=2\), \(d2=2\) & 0.9985 & 4 \\ \(d1=2\), \(d2=3\) & 0.9995 & 5 \\ \(d1=2\), \(d2=4\) & 0.9997 & 6 \\ \(d1=3\), \(d2=2\) & 0.9985 & 5 \\ \(d1=3\), \(d2=3\) & 0.9984 & 6 \\ \(d1=3\), \(d2=4\) & 0.9998 & 7 \\ \We conclude that \(\mathcal{V}_{j,k}(. )\) is submodular. From (16), it is clear that \(f^{{}^{\prime}}(n)\) is decreasing \(\forall n>0\). Hence, \(\mathcal{V}_{j,k}(. )\) is monotonically decreasing. We conclude that \(\mathcal{V}_{j,k}(. )\) is _submodular and monotone._  
Now, we prove the fact that the UE utility function, \(\mathcal{U}_{i}(. )\), is similar to the marginal gain of the BS utility function--that is, \(\mathcal{V}_{j,k}(i|N)\). The UE \(i\)'s utility for BS \(j\) belongs to tier \(k\) is given as \(\log\left(\frac{\eta_{i,j,k}}{|N+1|}\right)\), which is equal to  
\[\mathcal{U}_{i}(.)=\log(\eta_{i,j,k})-\log(|N+1|) \tag{17}\]  
Now, we establish the similarity between Equations (15) and (17). Equation (15) can be re-written as:  
\[\mathcal{V}_{j,k}(i|N)=\log(\eta_{i,j,k})-((|N|+1)\log(|N|+1)-|N|\log|N|)\]  
The expression \(\log(|N+1|)\) from (17) and \((|N|+1)\log(|N|+1)-|N|\log|N|\) from Equation (15) exhibits a similar trend.