## Wireless Reliability Fairness OptimizationWe present an algorithm for wireless reliability fairness optimization that optimizes the min-max outage probability first published in INFOCOM 2011 (See longer version in IEEE/ACM Transactions on Networking). An overview survey is available in Wireless Network Optimization by Perron-Frobenius Theory. ## The Problem StatementAn outage event occurs at the $l$th receiver when the received SINR falls below a given reliability threshold, i.e., $\mbox{SINR}_l(\mathbf{p})<{\beta}_l$ for $l=1,\dots,L$. So we are interested to minimize the worst-case outage probability to ensure reliability fairness, which is formulated as follows : \begin{equation} \begin{array}[c]{rl} \mbox{minimize} & \displaystyle\max_{l}P(\mbox{SINR}_l(\mathbf{p})<{\beta}_l)\\ \mbox{subject to} & p\in\mathcal{P}\\ \mbox{variables:} & \mathbf{p}. \end{array} \tag{*} \end{equation}where $\mbox{SINR}_l(\mathbf{p})=R_{ll}G_{ll}p_l/(\sum_{j \ne l}R_{lj}G_{lj}p_j+n_l)$ for all $l$ where $R_{lj},\forall l,j$ are random variables that model fading, and $\mathcal{P}$ models general power constraint set, e.g., a single total power constraint. ## Analytical SolutionUnder the Rayleigh fading model, the above nonconvex stochastic program can be simplified because the outage probability (please see Kandukuri and Boyd TWC 2002 for more details) of the $l$th receiver can be given analytically by : $$ \displaystyle P(\mbox{SINR}_l(\mathbf{p})<{\beta}_l)=1-e^{\frac{-v_l\beta_l}{p_l}}\prod_{j\neq{l}}\left(1+\frac{\beta_lF_{lj}p_{j}}{p_l}\right)^{-1} $$where \[F_{lj}= \begin{cases} 0,&l=j\\ G_{lj}/G_{ll},&l\neq{j}. \end{cases}\] $$ \mathbf{v}=\left(\frac{n_l}{G_{ll}},\cdots,\frac{n_L}{G_{LL}}\right). $$Next, we give an analytical solution by applying nonnegative matrix theory and nonlinear Perron-Frobenius theory. For illustration, consider the single total power constraint, then the optimal value and solution of (*) are, respectively, given as follows: $$ 1-e^{-\rho(\mathbf{B}(\mathbf{p}^\star)+\frac{1}{\bar{p}}\mathbf{v}\mathbf{1}^\top)} $$ $$ \mathbf{p}^\star=\mathbf{x}(\mathbf{B}(\mathbf{p}^\star)+\frac{1}{\bar{p}}\mathbf{v}\mathbf{1}^\top) $$where $\mathbf{x}(\cdot)$ is the right eigenvector corresponding to the Perron-Frobenius eigenvalue $\rho(\cdot)$, and we define \[B_{lj}= \begin{cases} 0,&l=j\\ \frac{p_l}{p_j}\mbox{log}\left(1+\frac{\beta_{l}F_{lj}p_{j}}{p_{l}}\right),&l\neq{j}. \end{cases}\]Observe that the spectrum of $\mathbf{B}$ and its rank-one perturbation capture the optimality entirely. For details of the proof and general idea, please refer to INFOCOM 2011. Interestingly, this nonlinear Perron-Frobenius theory approach solves an open problem in Kandukuri and Boyd TWC 2002 for the interference-limited special case. ## The AlgorithmUsing the nonlinear Perron-Frobenius theory, an optimal algorithm is given below to solve the stochastic program (for details: see INFOCOM 2011): 1) Update Power $\mathbf{p}(k+1)$: $p_{l}(k+1)=-\mbox{log}P(\mbox{SINR}_l(\mathbf{p}(k))>{\beta}_l)p_{l}(k) \quad \forall \, l$. 2) Nomalize Power $\mathbf{p}(k+1)$: $\mathbf{P}(k+1)\leftarrow\displaystyle\frac{\mathbf{p}(k+1)\cdot\bar{p}}{\mathbf{1}^\top\mathbf{p}(k+1)} \quad \mbox{if}\ \mathcal{P}=\{\mathbf{p}\mid\mathbf{1}^\top\mathbf{p}\leq\bar{p}\}$. $\mathbf{P}(k+1)\leftarrow\displaystyle\frac{\mathbf{p}(k+1)\cdot\bar{p}}{\max_{j}p_{j}(k+1)} \quad \mbox{if}\ \mathcal{P}=\{\mathbf{p}\mid p_{l}\leq\bar{p} \quad \forall \, l \}$. ## The MATLAB CodeThe algorithm below is for the stochastic problem with a single total power constraint. It can be easily modified for a general power constraint set. clear; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Problem parameter initialization % L: number of users. % G: channel gain. % F: nonnegative matrix. F_{lj} = G_{lj} if l ~= j, and F_{lj} = 0 if l = j % n: noise vector % v: nonnegative vector. v_l = n_l/G_{ll} % beta: a vector that is a weight assigned to links to reflect priority. % pmax: upper bound of the total power constraints. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% L = 4; G = zeros(L,L); F = zeros(L,L); n = rand(L,1); v = zeros(L,1); beta = rand(L,1); pmax = 4; for l = 1:1:L for j = 1:1:L if l~= j G(l,j) = 0.1+0.1*rand(1,1); else G(l,j) = 0.6+0.3*rand(1,1); end end end for l = 1:1:L for j = 1:1:L if l ~= j F(l,j) = G(l,j); else F(l,j) = 0; end end v(l) = n(l)/G(l,l); end itenum = 15; power_evolution = []; p = rand(L,1); power_evolution = [power_evolution;p']; pnew = zeros(L,1); for i = 1:1:itenum for l = 1:1:L tmp = 0; for j = 1:1:L % Algorithm step 1: update power for each user in a distributed way tmp=tmp+log(1+beta(l)*F(l,j)*p(j)/p(l));; end pnew(l)=(tmp+v(l)*beta(l)/p(l))*p(l); end % Algorithm step 2: normalize power centrally at the base station pnew=(pmax/sum(pnew)).*pnew;; power_evolution = [power_evolution;pnew']; p = pnew; end % plot the power evolution figure plot1 = plot(1:1:(itenum+1),power_evolution(:,1),'-o',1:1:(itenum+1),power_evolution(:,2), '-^',1:1:(itenum+1),power_evolution(:,3),'-+',1:1:(itenum+1),power_evolution(:,4),'-*','linewidth',1.5); legend('User 1',''User 2','User 3','User 4'); ## A Tiny Numerical ExampleThe problem parameters are set randomly in the code above. The following figure, obtained by running the code directly, plots the power evolution for a 4-user case, from which we can see a fast convergence. |