Wireless Reliability Fairness Optimization

We 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 Statement

An 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 Solution

Under 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 Algorithm

Using 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 Code

The 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 Example

The 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.