\documentclass[conference]{IEEEtran}
\usepackage{amsmath,amssymb,amsfonts,mathrsfs,amscd,amsthm}
%\usepackage[cmex10]{amsmath}
%\usepackage{algorithmic}
%\usepackage[tight,footnotesize]{subfigure}
%\usepackage[caption=false,font=footnotesize]{subfig}

\usepackage[dvips]{epsfig}
\DeclareGraphicsRule{.eps.gz}{eps}{.eps.bb}{`gunzip -c #1}
\DeclareGraphicsExtensions{.eps}
\graphicspath{{figures/}{eps/}{pdf/}{png/}{images/eps/}{images/pdf/}{images/png/}}

\newcommand{\up}[1]{\textsuperscript{#1}}

\begin{document}

\title{Multi-User strategy for interference mitigation in uplink cellular transmission}
\author{%
  \IEEEauthorblockN{Laurent Mazet, Mohamed Kamoun and Patrick Labb\'e}
  \IEEEauthorblockA{Motorola-Labs Paris -- Parc Les  Algorithmes, Saint Aubin -- 91193 Gif sur Yvette Cedex -- France \\
    $\{$laurent.mazet, mohamed.kamoun, patrick.labbe$\}$@motorola.com}
}

\thanks{This work was fund by the French project URC}
%\IEEEspecialpapernotice{}

\maketitle

\begin{abstract}
Recently, IEEE 802.16e and IEEE 802.11n have adopted MIMO transmission
schemes either for increasing the link robustness or the throughput by
exploiting the available spatial degrees of freedom. In this standards,
some STBC modes have been chosen in order to take benefit from the
wireless channel diversity in single link communications. However in
multi-user context, it has been show that STBC schemes
offer little interest when combined with scheduling.

In this contribution we propose to alleviate this effect by a user grouping
mode where multiple-users transmit on the same time frequency resource. We
derive a simple CSI based metric combined with a pairing strategy which
restores most of the single-link STBC gains.  Simulation results highlight that
with a simple linear MMSE receiver and a double user pairing strategy, a
capacity gain of 80\% is achievable using spatial multiplexing compared to a
pure TDMA single link approach.
\end{abstract}

\begin{IEEEkeywords}
STBC, SDM, WLAN, WIMAX, Interference management
\end{IEEEkeywords}

\section{Introduction}
\label{sec:introduction}

Latest WMAN standard IEEE~802.16e proposes Space Time Block Code (STBC) transmission
modes\cite{ieeeIT.tarokh99,ieeeJSAC.alamouti98} as a mean to reduce the
occurrence probability of deep fadings through coherent combination of
channel coefficients on different transmit branches. This technique
increases the link robustness and  coverage range which motivates their
use in cellular systems.

However, in a multi-user context, the STBC gain when considering
scheduling is challenged \cite{vtcfall.gozali02}. This comes from the
variance reduction incurred by the use of STBC of the equivalent channel
power distribution seen at reception. Indeed a more stable equivalent
channel results in a loss in multi-user diversity and thus penalizes the
expected gain from a clever scheduler considering the overall cell
capacity. This phenomenon is known as the \emph{channel hardening} effect 
\cite{ieeeIT.howchwald04,isit.kobayashi04}.


In this contribution we propose to recover multi-user diversity gain of STBC
modes in uplink by allowing two or more users to transmit on the same 
time frequency resource and by using an interference aware pairing 
strategy which minimizes the impact of concurrent
transmissions. This paper is organized as follows:
In section~\ref{sec:Mulituser-vs-spatial-diversity}, the channel
hardening effect is illustrated through probability density function and
cumulative distribution function analysis (pdf and CDF) of the received
SNR. Closed forms are derived in the context of Rayleigh channels and
are used for justifying the benefit of the proposed scheduling
strategies for spatially multiplexed STBC users.

Section~\ref{sec:Code_Design} details the performance assessment of the
considered Spatial Diversity Multiplexing STBC (SDM-STBC) scheme and the
 metric expression used for uplink Mobile Subscriber (MS)
grouping. Evaluation of the proposed method is performed in
section~\ref{sec:deployment} where a single cell cellular deployment is
considered using classical IEEE~802.16e and IEEE~802.11n system
parameters.

\section{Multiuser versus spatial diversity: a closed form approach}
\label{sec:Mulituser-vs-spatial-diversity}

\subsection{System description and hypothesis}
\label{subsection:System_description_and_hypothesis}

The goal of this section is to illustrate the channel hardening effect when considering maximum
SNR scheduler \cite{vtcspring.torabi08} in a multi-user deployment.
This scheduler is known to be equivalent to the proportional fair
scheduler (PFS) for large values of time constant \cite{isspit.gesbert03,vtcspring.berger03,vtcspring.holtzman00}.
In this analysis we neglect the effects interference between users by
assuming that is included in the thermal noise.
Let's consider one base station (BS) serving K mobile subscribers (MS). Denote by $h^k_{i,j}$ the complex channel coefficient between the $i$\up{th} antenna at the BS and the $j$\up{th} antenna of the $k$\up{th} user. Assuming a Rayleigh fading distribution, $h^k_{i,j}$ are independent zero mean unitary variance Gaussian random variables. Moreover, we consider quasi static fading so that the channel response remains constant during one time slot and is drawn independently at each new realization. Finally, define $\gamma^k(s)$ as the SNR of the signal arriving from user $k$ within time slot $s$ and $\overline{\gamma^k}$ its average.

\subsection{Statistical approach: pdf and CDF calculation}
\label{subsection:Statistical_approach}

Depending on the considered transmission scheme, it is possible to derive the statistics of the SNR from the statistics of the channel coefficients:
\begin{itemize}
\item In the SISO case, the received SNR for user $k$ is:
  \begin{equation}
    \gamma^k_{SISO}(s) = \overline{\gamma^k}|h^k_{1,1}|^2
  \end{equation}
\item In the STBC case, the received SNR expression for user $k$  using an Alamouti scheme is:
  \begin{equation}
    \gamma^k_{STBC}(s) = \frac{\overline{\gamma^k}}{2}\sum_{i,j=1,2}|h^k_{i,j}|^2
  \end{equation}
\end{itemize}
Using the same approach and neglecting the inter-user interference, when two MSs are transmitting simultaneously with Alamouti,
the statistics of the SNR experienced at the BS in uplink (UL) is given by:
\begin{equation}
  \gamma^{(k1,k2}_{2xSTBC}(s) = \frac{\overline{\gamma^{k1}}}{2}\sum_{i,j=1,2}|h^{k1}_{i,j}|^2+
  \frac{\overline{\gamma^{k2}}}{2}\sum_{i,j=1,2}|h^{k2}_{i,j}|^2
\end{equation}
In the sequel this scheme is referred as 2xSTBC.
Note that since all the users are transmitting with the same power and are considered as independent units, no normalization of the total transmitted energy is performed in the SNR calculus.

We consider here that users are emitting successively on a slot by
slot basis following a maximum SNR scheduler as stated previously. 
%(PFS) \cite{vtcspring.berger03,vtcspring.holtzman00}.
For sake of simplicity and to follow classical hypothesis, we assume that each user has the same average SNR ($\overline{\gamma_k} = \overline{\gamma}$). Following this hypothesis, the user scheduled for time slot $s$ is the one who maximizes the following criteria:
\begin{equation}
  K = \mathop{\mathrm{arg\!max}}_{k} \left\{\gamma_k(s)\right\}
\end{equation}

In the case of a Rayleigh channel, it is possible to obtain an analytical expressions of $\gamma_k$ in the SISO, STBC and 2xSTBC cases.
Since $h^k_{i,j}$ are normally distributed, $|h^k_{i,j}|^2$ follow a chi-square law with 2 degrees of freedom.
On the same assumptions, $\gamma^k_{STBC}$ and $\gamma^k_{2xSTBC}$ are following chi-square distribution with 4 and 8 degree of freedom respectively. The probability density function can be inferred in each case:
\begin{itemize}
\item In the SISO case, the pdf yields:
  \begin{equation}
    f_{\gamma_{SISO}} = \frac{1}{\overline{\gamma}} \exp{-\frac{\gamma}{\overline{\gamma}}}
  \end{equation}
\item In the STBC case, the pdf becomes:
  \begin{equation}
    f_{\gamma_{STBC}} = 4 \frac{\gamma}{\overline{\gamma}^2} \exp{-\frac{2\gamma}{\overline{\gamma}}}
  \end{equation}
\item In the 2xSTBC case, the pdf is:
  \begin{equation}
    f_{\gamma_{2xSTBC}} = \frac{8}{3} \frac{\gamma^3}{\overline{\gamma}^4} \exp{-\frac{2\gamma}{\overline{\gamma}}}
  \end{equation}
\end{itemize}

Thus, the probability that the SNR is below a given value is directly linked to the expression of the cumulative distribution function what can be inferred by integrating the pdf:
\begin{equation}
  F_{\gamma '}(\gamma) = P( \gamma ' < \gamma ) = \int_0^\gamma f_{\gamma '}(\gamma ') d\gamma '
\end{equation}

Finally, the cumulative distribution function of the SNR for a system of K users is given by:
\begin{itemize}
\item In the SISO case, the CDF becomes:
  \begin{equation}
    F_{\gamma_{SISO}} = \left[1-\exp(\frac{\gamma}{\overline{\gamma}})\right]^K
  \end{equation}
\item In the STBC case, the CDF becomes:
  \begin{equation}
    F_{\gamma_{STBC}} = \left[1 - (1+\frac{\gamma}{\overline{\gamma}}) \exp ( -\frac{2\gamma}{\overline{\gamma}})\right]^K
  \end{equation}
\item In the 2xSTBC case, the CDF becomes:
  \begin{equation}
    F_{\gamma_{2xSTBC}} = \left[1 - (1+ 2 \frac{\gamma}{\overline{\gamma}} + 2 \frac{\gamma^2}{\overline{\gamma}^2} + \frac{\gamma^3}{3\overline{\gamma}^3}) \exp ( -\frac{2\gamma}{\overline{\gamma}})\right]^K
  \end{equation}
\end{itemize}

\subsection{Conclusion on the performance of the different systems}
\label{subsection:Conclusion_on_the_performance_of_the_different_systems}

Average SNR CDF of the SISO, STBC and 2xSTBC systems are presented in figure~\ref{fig:Multiuser-vs-Spatial-diversity}. The first set of curves describe the behavior of a system including only one user (K=1). The second set of curves presents the performance of a system with K=50 users. For sake of comparison, the CDF achievable by a system operating with an optimal transmit beamforming based on a perfect Channel State Information (CSI) has been included. This clearly illustrates the inherent trade-off between spatial and multi-user diversity: in the multi-user case, classical STBC result more in a penalty than an advantage. Note that STBC performance remains superior than a pure SISO scheme for 50 concurrent users.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.8\linewidth,height=0.7\linewidth]{Multiuser-vs-Spacial-diversity}
  \caption{Cumulative Distribution Function (CDF) of the effective SNR for some different transmission modes and different number of users K.}
  \label{fig:Multiuser-vs-Spatial-diversity}
\end{figure}

Moreover, the double Alamouti distributed STBC over 2 different users yields better performance in a multi-user transmission scheme.
This transmission scheme is a straightforward extension of the single user one known as SDM-STBC code and studied in the framework of IEEE 802.11n \cite{icct.rouquet03,icc.rouquet03}.
This study highlights the fact that the gain in multi-user diversity is not to be sought in enhancing the signal strength of the received signal and indicates that a performance improvement can be obtained through clever interference aware scheduling approaches.

\section{Code design: combining STBC and SDM}% in multi-user context}
\label{sec:Code_Design}

%\subsection{Combining STBC and SDM: the original single user scheme}
\subsection{Original single user scheme}
\label{subsection:Combining_STBC_and_SDM_for_single_user}

The single user hybrid scheme consisting in combining spatial multiplexing of two alamouti independantly coded streams provides the advantage of increasing the link robustness while maintaining a rate $1$ encoding \cite{icct.rouquet03,icc.rouquet03}.
Since the Alamouti encoding is applied on two separate streams, these two streams will represent two distinct users in our proposed uplink transmission scheme.
A Linear Minimum Mean Square Error (LMMSE) receiver is used at the BS for retreiving the data.

For sake of simplicity, we restrict our study to the multiplexing of Alamouti codes, but similar analysis can easily be conducted with any space-time block code. In this configuration, an hybrid system with $N$ antennas at the transmitter can convey simultaneously $N/2$ streams, each stream being transmitted over two antennas and two time intervals iusing an Alamouti coding. Thus an overall data rate of $N/2$ is achieved, instead of 1 for Alamouti coding, and of $N$ for a classical SDM scheme.

Let's consider a system with two 2 transmit antennas MSs resulting in an equivalent 4 transmit elements scheme (see figure.~\ref{Spatial Division Multiplexing of two Alamouti codes}).

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.9\linewidth]{SDM_STBC}
  \caption{Spatial Division Multiplexing of two Alamouti codes}
  \label{Spatial Division Multiplexing of two Alamouti codes}
\end{figure}

Four complex symbols are transmitted: $s_1$, $s_2$ belonging to the first user and $s_3$, $s_4$ belonging to the second user according to the following code matrix:
\begin{equation}
  C =
  \begin{bmatrix}
    s_1 & s_2 & s_3 & s_4 \\
    -s_2^* & s_1^* & -s_4^* & s_3^*
  \end{bmatrix}
\end{equation}
where the symbols of the $n$\up{th} column of $C$ are sent from the $n$\up{th} antenna.

We assume that the system operates in a quasi-static flat fading environment, and we denote by $\mathbf{h}_{n}$ the $M \times 1$ vector formed of the channel coefficients between the transmit antenna $n$ and the $M$ receive antennas. We also denote by $\mathbf{y}_1$ and $\mathbf{y}_2$ the $M \times 1$ signals received on the 1\up{st} and 2\up{nd} time slots, and by $\mathbf{n}_1$ and $\mathbf{n}_2$ the corresponding additive noise components. The received signal can be expressed as:
\begin{equation}\label{eq:equivalent_channel}
  \underbrace{
    \begin{bmatrix}
      \mathbf{y}_1 \\ \mathbf{y}_2^*
    \end{bmatrix}
  }_{\mathbf{y}}
   =
  \underbrace{
    \begin{bmatrix}
%    \left\[ \begin{array}{cc|cc}
        \mathbf{h}_1 & \mathbf{h}_2 & | &\mathbf{h}_3 & \mathbf{h}_4 \\
        \mathbf{h}_2^* & -\mathbf{h}_1^* & | & \mathbf{h}_4^* & -\mathbf{h}_3^*
%    \end{array} \right\]
      \end{bmatrix}
  }_{
    \begin{bmatrix} \mathbf{H}_1 | \mathbf{H}_2 \end{bmatrix}
  }
  \times \underbrace{
    \begin{bmatrix}
      s_1 \\ s_2 \\ s_3 \\ s_4
    \end{bmatrix}
  }_{
    \mathbf{s}
  }
  + \underbrace{
    \begin{bmatrix}
      \mathbf{n}_1 \\ \mathbf{n}_2^*
    \end{bmatrix}
  }_{
    \mathbf{n}
  }
\end{equation}
The channel matrix $\mathbf{H} = \begin{bmatrix} \mathbf{H}_1 | \mathbf{H}_2 \end{bmatrix} $ is comprises two orthogonal sub-matrices $\mathbf{H}_1$ and $\mathbf{H}_2$ such as:
\begin{equation}
  \mathbf{H}_1^H \mathbf{H}_1 = \left ( \| \mathbf{h}_1 \|^2 + \| \mathbf{h}_2
  \|^2 \right ) \mathbf{I}_2 \doteq c_1 \mathbf{I}_2
  \label{H1^H H1}
\end{equation}
and
\begin{equation}
  \mathbf{H}_2^H \mathbf{H}_2 = \left ( \| \mathbf{h}_3 \|^2 + \| \mathbf{h}_4
  \|^2 \right ) \mathbf{I}_2 \doteq c_2 \mathbf{I}_2
  \label{H2^H H2}
\end{equation}

The four transmitted symbols can be recovered by exploiting equation~\eqref{eq:equivalent_channel}. If we compare the characteristics of the hybrid system to a SDM one with same number $N$ of transmit antennas, we first
notice that the number of unknown is the same whereas the number of observations is twice more since we consider two time slots. Thus for any ZF or LMMSE based receiver the minimum number of receive antennas required for the combination of SDM and STBC is equal to $N/2$ instead of $N$. Moreover the hybrid scheme also benefits from the orthogonality of each Alamouti code, and in consequence benefits from transmit diversity.

Different strategies can be applied to recover the transmitted signals, from optimal Maximum Likelihood to ZF or MMSE equalization. In the following, we focus on ZF or MMSE based receivers.
%possibly combined with the V-BLAST detection scheme, to get reasonable complexity. 
%pas de V-BLAST apres donc c pas la peine d'en parler

\subsection{Zero-Forcing Receiver}
\label{subsec:Zero-forcing_receiver}

In order to recover the four transmitted symbols $s_1$, $s_2$, $s_3$, and $s_4$, ZF equalization can be applied to the hybrid system~\eqref{eq:equivalent_channel} by applying the Moore-Penrose pseudo-inverse matrix of $\mathbf{H} $ to the received signal $\mathbf{y} $.

The pseudo-inverse $\mathbf{H}^{\#}$ of the channel matrix defined by
\begin{math}
  \left ( \mathbf{H}^H \mathbf{H} \right )^{-1} \mathbf{H}^H
\end{math}
 can be rewritten as a function of the sub-matrices $\mathbf{H}_1$ and $\mathbf{H}_2$:
\begin{equation}
  \mathbf{H}^{\#} =
  \begin{bmatrix}
    \mathbf{H}_1^H \mathbf{H}_1 & \mathbf{H}_1^H \mathbf{H}_2 \\
    \mathbf{H}_2^H \mathbf{H}_1 & \mathbf{H}_2^H \mathbf{H}_2
  \end{bmatrix}^{-1}
  \begin{bmatrix}
    \mathbf{H}_1^H \\ \mathbf{H}_2^H
  \end{bmatrix}
\end{equation}
Let us introduce the orthogonal matrix
\begin{math}
  \mathbf{P} = \mathbf{H}_1^H \mathbf{H}_2
  \label{H1^H H2}
\end{math}.
Due to the orthogonality of this matrix, $\mathbf{P}$ verifies the relation
\begin{equation}
  \mathbf{P} \mathbf{P}^H = \mathbf{P}^H \mathbf{P} = c_3 \mathbf{I}_2
\end{equation}
where
\begin{equation}
  c_3 = \left | {\mathbf
  h}_1^H \mathbf{h}_3 + \mathbf{h}_2^T \mathbf{h}_4^* \right |^2 + \left |
  \mathbf{h}_1^H \mathbf{h}_4 - \mathbf{h}_2^T \mathbf{h}_3^* \right |^2
\end{equation}

We can thus derive an analytic expression of the pseudo-inverse of the channel matrix:
\begin{equation}
  \mathbf{H}^{\#} = \frac{1}{c_1 c_2 -c_3}
  \underbrace{
    \begin{bmatrix}
      c_2 \mathbf{I}_2 & -\mathbf{P} \\
      -\mathbf{P}^H & c_1 \mathbf{I}_2
    \end{bmatrix}
  }_{\mathbf{W}_2^{ZF}} \
  \underbrace{
  \begin{bmatrix}
    \mathbf{H}_1^H \\ \mathbf{H}_2^H
  \end{bmatrix}
  }_{\mathbf{W}_1^{ZF}}
\end{equation}
such as no matrix inversion is required.

The Zero-Forcing receiver can then be decomposed into two stages. We first filter the received signal $\mathbf{y}$ by $\mathbf{W}_1^{ZF}$ to remove the contribution from the other signal within each Alamouti code. Second we apply the filter $\mathbf{W}_2^{ZF}$ to the resulting signal in order to recover the two transmitted streams. These two stages lead to the same SNR within each Alamouti code, {\it i.e.}
\begin{eqnarray}
  \mbox{SNR}_1 & = & c_1-c_3/c_2 \quad \textrm{for the 1\up{st} stream,} \nonumber \\
  \mbox{SNR}_2 & = & c_2-c_3/c_1 \quad \textrm{for the 2\up{rd} one.} \label{ZF_SNR}
  \label{Eq::SNRS}
\end{eqnarray}
The second term in the expression of the SNRs \eqref{ZF_SNR} corresponds to the cost of spatial multiplexing compared to the SNR achieved by the classical Alamouti scheme.

\subsection{Minimum Mean Square Error Receiver}
\label{subsec:MMSE_receiver}

In the previous subsection we have derived an analytic form of the ZF receiver. We now conduct a similar study for the MMSE receiver based on the filter $\mathbf{W}$:
\begin{equation}
  \mathbf{W} = \left ( \mathbf{H}^H \mathbf{H} + \sigma_n^2 \mathbf{I}_4  \right )^{-1}
  \mathbf{H}^H ,
  \label{MMSE_Rx}
\end{equation}
to be applied to the received signal $\mathbf{y}$~\eqref{eq:equivalent_channel}. $\sigma_n^2$ denotes the variance of the additive white gaussian noise and the symbols are assumed to be adequately normalized.

We can easily prove that $\mathbf{W}$ can be expressed without matrix inversion as
\begin{equation}
  \mathbf{W} = \frac{1}{d_1 d_2 -c_3}
  \underbrace{
    \begin{bmatrix}
      d_2 \mathbf{I}_2 & -\mathbf{P} \\
      -\mathbf{P}^H & d_1 \mathbf{I}_2
    \end{bmatrix}
  }_{\mathbf{W}_2^{MMSE}} \
  \underbrace{
    \begin{bmatrix}
      \mathbf{H}_1^H \\ \mathbf{H}_2^H
    \end{bmatrix}
  }_{\mathbf{W}_1^{MMSE}}
\end{equation}
with
\begin{eqnarray*}
  d_1 = \| \mathbf{h}_1 \|^2 + \| \mathbf{h}_2 \|^2 + \sigma_n^2 = c_1 + \sigma_n^2 \\
  d_2 = \| \mathbf{h}_3 \|^2 + \| \mathbf{h}_4 \|^2 + \sigma_n^2  =  c_2 + \sigma_n^2
\end{eqnarray*}
First stage of filtering using $\mathbf{W}_1^{MMSE}$ is performed in a same way as for ZF detection to benefit from the orthogonality within each Alamouti code. Second stage based on the $\mathbf{W}_2^{MMSE}$ filter then takes into account the variance of the additive noise to better detect the two transmitted streams and is specific to MMSE equalization.

\subsection{Application to multi-user context}
   \label{subsection:Extrapolation_to_multiuser_context}

Assuming that each mobile subscriber embeds two antennas, we propose to assign each of the Alamouti block to a specific user so that the equivalent system presents four transmit antennas. As presented in \eqref{ZF_SNR}, the SNR of each Alamouti block has two terms:
\begin{itemize}
   \item the first one $c_1$ (resp. $c_2$) corresponding to the SNR that each user would have if he was emitting solely,
   \item the second one $c_3/c_2$ (resp. $c_3/c_1$) corresponding to a term of interference, melting the channel characteristics of both users.
\end{itemize}

In order to increase the average capacity of the system,
%given the monotonic behavior of all the operators implied in this section,
we can expect that increasing the SNR of each user would help in fulfilling our goal. In this way, reducing $c_3$ for each pair of users through a selection process will improve the final system capacity and thus the aggregated throughput.
According to the SNR expressions given in equations\ref{Eq::SNRS}, we choose to base our pairing strategy on the following metric: $c_3/(c_1c_2)$ which respects symmetries introduces in 2xSTBC encoding.
This way, each user experience the same \emph{corrective} term: $1-c_3/(c_1c_2)$. Defining ($\mathbf{h}_{i1}$,$\mathbf{h}_{i2}$) as the channel experienced by user $i$ (replacing $\mathbf{h}_1$ and $\mathbf{h}_2$ in \eqref{eq:equivalent_channel}) and ($\mathbf{h}_{j1}$,$\mathbf{h}_{j2}$) as the channel seen by user $j$ (replacing $\mathbf{h}_1$ and $\mathbf{h}_2$ in \eqref{eq:equivalent_channel}), our interference metric $I_m(i,j)$ between these two users is defined by:
\begin{equation}\label{eq:metric}
  I_m(i,j) = \frac{
    \left| \mathbf{h}_{i1}^H \mathbf{h}_{j1} +
      \mathbf{h}_{i2}^T \mathbf{h}_{j2}^* \right|^2 +
    \left| \mathbf{h}_{i1}^H \mathbf{h}_{j2} -
      \mathbf{h}_{i2}^T \mathbf{h}_{j1}^* \right|^2
  }
  {
    \left( \| \mathbf{h}_{i1} \|^2 + \| \mathbf{h}_{i2} \|^2 \right)
    \left( \| \mathbf{h}_{j1} \|^2 + \| \mathbf{h}_{j2} \|^2 \right)
  }
\end{equation}

$I_m$ is of course a sub-optimal metric to perform the overall capacity optimization. However it provides a substancial performance improvement as will be shown in the next section.

The simulations presented in the next section depicts the performance of this proposed metric using various varying complexity scheduling strategies compared to a exhaustive capacity based optimization. It is shown that in the majority of cases, the use of the suboptimal metric is sufficient\footnote{the calculation of $I_m$ involves a number of multiplication and addition increasing linearly with the number of received antennas as a function}.

\section{Assessment of the multiuser STBC}% on a realistic deployment}
\label{sec:deployment}

\subsection{System modelization and characteristics}
\label{subsec:system_characteristics}

Here a single cell deployment is considered serving a given number of users. The antennas at the BS are supposed isotropic: from 2 up to 8 antenna configurations are captured.  A two slopes classical path loss model is adopted:
\begin{footnotesize}
  \begin{equation}
    PL = \left\{
      \begin{array}{l}
        20\log_{10}\left(\frac{4\pi f}{c}\right) + 20\log_{10}(d) \;\textnormal{if}\; 0 < d \leq d_{BP} \\
        20\log_{10}\left(\frac{4\pi f}{c}\right) + 20\log_{10}(d_{BP}) + 10\alpha \log_{10}\left(\frac{d}{d_{BP}}\right) \;\textnormal{else}
      \end{array}
    \right.
  \end{equation}
\end{footnotesize}
where $d$, $d_{BP}$ and $\alpha$ are respectively the distance, the breakpoint distance and the path loss exponent. The different parameters of the system are recalled in Tab.~\ref{tab:params}.

\begin{table}[htbp]
  \centering
  \caption{System parameters.}
  \label{tab:params}
    \begin{tabular}{l|l|l}
      Syst. assumptions                  & 802.11n & 802.16e \\
      \hline
      Center frequency                   & 5.2GHz  & 2.4GHz  \\
      Emitting power at the BS           & 0.2W    & 10W     \\
      Signal bandwidth                   & 20MHz   & 20MHz   \\
      \hline
      Break Point distance (BPd)         & 10m     & 10m     \\
      Path loss exponent after BPd       & 3.5     & 2.5     \\
      Shadowing Std Dev before BPd       & 3       & 3       \\
      Shadowing Std Dev after BPd        & 5       & 5       \\
      \hline
      Antenna Gain (Rx Tx)               & 0dB     & 0dB     \\
      Noise Figure at the receiver       & 10dB    & 10dB    \\
      \hline
    \end{tabular}
\end{table}

Shadowing is taken into account in the simulations through a ray-tracing approach more suited for a single cell deployment. A set of obstacles are dropped over the cell with a random attenuation and aperture (the distribution is given by the channels parameters). Assuming a dominant line of sight component, the losses due to shadowing effect are directly computed by summing the loss of each obstacle on the path.

\subsection{Presentation of the sequencing/pairing algorithms}
\label{subsec:sequencing_algorithms}

The following paragraphs presents the different algorithms designed to optimize the sequencing and pairing of users \emph{i.e.} to pick for each time slot the best couple of active user so that the system capacity is increased by means of the inter-user interference reduction. We assume that a total of $N=2p$ users are present in the cell.

\paragraph{Fair algorithm. } This algorithm is designed to keep the original sequencing of the different users and, for each time slot, find the best one to schedule simultaneously with the objective of minimizing the metric defined in \eqref{eq:metric}. The advantage of this algorithm is that it boils down to a simple overlay on any existing algorithm incurring a very low arithmetical complexity increase since the number of operations varies like $p(p-1)/2$.

For instance, if the user $i$ is scheduled for the next time slot, the paired users will be defined as:
\begin{equation}
   (I,J) = (i, \mathop{\arg\min}_{j, j\neq i}\left\{I_m(i,j)\right\})
\end{equation}

\paragraph{Best couple. } A way to improve the previous algorithm consists in scheduling not only the best second user when the first one is scheduled by an independent method but to pick the pair scheduled by minimizing $I_m$ over the next time slot. This method is thus defined so that the pair scheduled for a given time follows:
\begin{equation}
   (I,J) = (\mathop{\arg\min}_{i,j}\left\{I_m(i,j)\right\})
\end{equation}
where $i$ and $j$ are all possible active users. This algorithm is more complex than the previous one since its complexity varies like $1/6p(p+1)(4p-1)-1$.

\paragraph{Exhaustive. } The exhaustive search tests all the combinaison of users on all time slots. Calculating the capacity of each of these sequences, the algorithm returns the best one. If this method provides the optimum solution, the complexity of this method is exponential: the number of operations grows like $(2p)!/2^p/p!$. Practically speaking, it would not be reasonable to think that this method would result in an implementable solution on a BS: this method is presented here as a benchmarking reference.

\subsection{Numerical results}
\label{sec:numerical_results}
The simulations in this section are conducted for a various number of users and a various number of Rx antennas. The influence of the number of obstacles is not discriminating on the final capacity gain (less than 0.3\% of gain increase). The number of set of users per configuration and the number of channel tested is adjusted so as to produce a smooth distribution (5000 sets of users and 1 channel per user).

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.7\linewidth]{gain_distribution_example}  \caption{Representation of the gain distribution.}
  \label{fig:gain_distribution_example}
\end{figure}

Finally the best trade-off between complexity and performance is provided by the fair algorithm which also present the advantage of being implemented as an overlay to existing scheduling. The gain in performance of this method are summarized in
Fig.~\ref{fig:fair_gain_summary} as a multi-vari chart for various antenna configurations and size of the pool of users.
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.7\linewidth]{fair_gain_summary}
  \caption{Mean gain observed with the fair algorithm (nU stands for number of users).}
  \label{fig:fair_gain_summary}
\end{figure}
To help highlight the interest of such pairing/scheduling techniques, we also implemented an arbitrary method that performs the user sequencing randomly. Both methods were first compared on the basis of the gain provided over a classical TDMA scheme: a null gain corresponds to no improvement over TDMA, whereas a 100\% gain is equivalent to perfect spatial multiplexing with no interference (or perfect interference cancellation).

Fig.~\ref{fig:gain_distribution_example}
provides the gain distribution for the various scheduling approaches considered
(list sorted from the worst to the best performing one): arbitrary, fair, best couple and exhaustive. The average gain varies depending on the trade-off between spatial diversity (linked to the number of Rx antenna) and the multi-user diversity (linked to the number of users).

\section{Conclusion}
\label{sec:conclusions}
In this contribution we presented the performance of STBC uplink modes
in multi-user context. A new user pairing stratey based on simples
metrics derived from the CSI has be designed in order to improve the
gains of STBC transmissions by filling efficiently the degrees of
freedom of the multi-user channel.  

\bibliographystyle{IEEEtran}
\bibliography{abbrev,alien,standard,conf}
\end{document}
