\documentclass[conference]{IEEEtran}
\usepackage{amsfonts,amsmath}
\usepackage[mathscr]{eucal}

\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/}}

\DeclareMathOperator{\card}{Card}
\DeclareMathOperator{\esp}{E}
\providecommand{\herm}{\ensuremath{\mathrm{H}}}
\providecommand{\trans}{\ensuremath{\mathrm{T}}}
\providecommand{\up}[1]{\textsuperscript{#1}}

\begin{document}
\title{Low complexity uplink multi-user user pairing and best band selection for transmit beamforming mobiles}
\author{%
  \IEEEauthorblockN{Laurent Mazet, Mohamed Kamoun, Patrick Labb\'e and Anahid Robert}
  \IEEEauthorblockA{Motorola-Labs Paris -- Parc Les  Algorithmes, Saint Aubin -- 91193 Gif sur Yvette Cedex -- France \\
    $\{$laurent.mazet, mohamed.kamoun, patrick.labbe, anahid.robert$\}$@motorola.com}
}

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

\maketitle

\begin{abstract}
IEEE 802.16e and IEEE 802.11n has adopted Multiple Transmit Multiple Receive (MTMR) transmission schemes either for increasing the link robustness or the throughput by exploiting the spatial diversity of the Multiple Input Multiple Output (MIMO) channel. We propose a new user pairing strategy for close loop transmission modes in MIMO uplink channels. 

The proposed user pairing strategy is achieved based on optimizing the orthogonality of the zero forcing maximum ratio combining single user decoding vectors which tremendously reduces the search complexity compared to a full matrix dual user MMSE approach (approximate complexity gain is $n^2$ versus $n!$). Moreover, the proposed method avoids the computation of the sum capacity for each pair of users considered resulting in an additional arithmetical complexity saving. In that case, simulation results highlight a scheduling gain from 5\% to 13\% on the achievable capacity/throughput.
\end{abstract}

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

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

Last generation of Wi-Fi IEEE~802.11n and WiMax IEEE~802.16e wireless systems rely on multiple transmit and receive antenna schemes (\emph{a.k.a.} MIMO: Multiple-Input Multiple-Output) to improve their link robustness or throughput implementing closed loop method taking advantage of the channel knowledge at the transmitter side.
Though initially applied for single link designs, multi-user schemes such SDMA are now considered but few contributions deal with the impact of uplink scheduling on the overall system performance\cite{Xi-Zoltowski-2006,Hara-Brunel-kazuyoshi-2006}.

Blabla...



\section{Multiple user MIMO schemes}
\label{sec:multiple-user-sdm}

Let consider the case of an uplink transmission where two single streams 2Tx antennas MS are transmitting simultaneously to a two 2Rx antennas BS. Each of the MS are using per carrier SVD-MIMO TxBF to the BS.

In order to schedule \emph{two active users} at the same time picked among a larger pool of $N$, we propose to select the two users that have their channel eigen-vectors -- corresponding to the maximum eigenvalue of their channels -- the most \emph{orthogonal} to each other.

User pairing is thus achieved based on optimizing the orthogonality of the zero forcing Maximum Ratio Combining (MRC) single user decoding vectors.

One advantage of such scheme is that it reduces tremendously the search complexity of the best couple compared to a full matrix obtained in the framework of dual user MMSE approach. The gain is approximately of the order of $n^2/n!$.
Moreover the proposed method avoids the computation of the sum capacity for each pair of users considered resulting in an additional arithmetical complexity saving.
Note that the proposed scheduling technique is sub-optimum in the sense that the selection is not providing the best solution in terms of MMSE since interference between the users is not taken into account in the pairing process.

It is important to notice that, we take directly benefit of the fact that eigen-beamforming is the solution that achieves the maximum channel capacity in presence of interference and noise \cite{Andersen-2000}.

\subsection{Notations}
Denote by ${}^\trans$ and ${}^\herm$ respectively the transpose and the complex conjugate transpose operators. Capital bold face is used to indicate matrices, small boldface letters are used to indicate vectors and small letters are used to indicate complex or real scalars.

We consider the uplink of a multi-user system, with $K$ simultaneous transmitting MSs to a single BS. Each MS is equipped with $N_T$ antennas to perform beam forming and the receiver has $N_R$ antennas. Let consider first a single carrier with a MIMO channel composed of independent Rayleigh fadings. Received signal vector at the receiver, called $\mathbf{r}$ can be written as:

\begin{equation}\label{Sys_Model}
\mathbf{r} = \sum_{i=1}^K \sqrt{P_i^{(s)}} \; \mathbf{H}_i \mathbf{u}_i s_i + \mathbf{n}
\end{equation}

where $s_i$ is the transmitted symbol from the $i$-th transmitter with $\esp[|s_i|^2]= 1$ and $P_i^{(s)}$ represents the total transmit power of each user, $\mathbf{H}_i$ is the $N_R \times N_T$ channel matrix from the $i$-th transmitter to the receiver and $\mathbf{n}$ is the noise vector with $\esp[\mathbf{n}\mathbf{n}^{\dagger}]= P^{(n)}\mathbf{I}$. We define $\mathbf{u}_i$, a $N_T \times 1$ vector as the transmit beamforming vector used by MS $i$. It is known that the maximum channel capacity obtained when $\mathbf{u}_i$ is the eigenvalue corresponding to the maximum eigen-value of  $\mathbf{H}_i^{\dagger}\mathbf{H}_i$ (see \cite{Andersen-2000}).

Additionally, $\mathbf{H}_i$ can be written as :

\begin{eqnarray}\label{Channel_decompose}
\mathbf{H}_i & = & \mathbf{V}_i \mathbf{\lambda}_i \mathbf{U}_i^\herm \\ \nonumber
      & = & \lambda_i \mathbf{v}_i \mathbf{u}_i^\herm  + \sum_{k \neq 1} \lambda_{i,k} \mathbf{v}_{i,k} \mathbf{u}_{i,k}^\herm
\end{eqnarray}
where $\mathbf{u}_{i,.}$ and $\mathbf{v}_{i,.}$ are respectively the column vector of $\mathbf{U}_i$ and $\mathbf{V}_i$ and $\lambda$, $\mathbf{u}_i$, and $\mathbf{v}_i$ are the strongest singular value and its associated vectors.
where $\mathbf{u}_{i,.}$ and $\mathbf{v}_{i,.}$ are respectively the column vector of $\mathbf{U}_i$ and $\mathbf{V}_i$, $\lambda$ is the strongest singular value and $\mathbf{u}_i$, and $\mathbf{v}_i$ its associated vectors.

As a consequence, equation (\ref{Sys_Model}) yields:

\begin{equation}\label{Sys_Model_Sim}
\mathbf{r} = \sum_{i=1}^{K} \sqrt{P_i^{(s)}} \lambda_i \mathbf{v}_i s_i  + \mathbf{n}
\end{equation}

\subsection{Scheduling algorithm description}
As we mentioned before, scheduling is done to authorize two users that have \emph{orthogonal} or \emph{near to orthogonal} channel eigen-vectors -- associated to the maximum channel eigen-value -- to send data at the same time. The procedure can be summarized as follows:


\begin{enumerate}
\item Over all active users, compute eigen-vectors associated to maximum eigenvalue of multi-user channels at the base station.
\item For each eigen-vector, compute the inner product with all available eigen-vectors.
\item The chosen couple is the one with the least value of inner product, \emph{i.e.} the \emph{most orthogonal}.
\item Eliminate the chosen couple from the list and go to step 2. and repeat till all the couples are computed.
\item Authorize each precomputed couple to send at the same time consecutively.
\end{enumerate}

\section{Detection scheme and capacity evaluations}
Several equalizers are considered in this section and the corresponding capacity expression are detailed. These capacity formulas are used for the evaluation of the scheduling method.
\subsection{Projection: zero forcing}
When using the receive weights $\mathbf{v}_k^\herm$ for zero forcing detection, the output of the $k$-th receive beamformer is:
\begin{eqnarray}
\hat{s}_k & = & \mathbf{v}_k^\herm \mathbf{r} \\ \nonumber
       & = & \sqrt{P_k^{(s)}} \lambda_k s_k  + \mathbf{v}_k^\herm \sum_{i \neq k}\sqrt{P_i^{(s)}} \lambda_i \mathbf{v}_i s_i  + \mathbf{v}_k^\herm \mathbf{n}
\end{eqnarray}
Since the scheduling algorithm considered aims at pairing users such that $\mathbf{v}_k$ and $\mathbf{v}_i$ are orthogonal or near to orthogonal, the second term in the above equation is close to zero. The throughput of system can therefore be evaluated as (\cite{Telatar-1999}):
\begin{eqnarray}
\mathcal{C} & = & \log_2(1+SINR) \\ \nonumber
    & = & \log_2(1+ \frac{P_k^{(s)} \lambda_k^2}{\sum_{i \neq k}P_i^{(s)} \lambda_i^2 \|\mathbf{v}_k^\herm\mathbf{v}_i\|^2 + P^{(n)}})
\end{eqnarray}
with $\|\mathbf{v}_k^\herm \mathbf{v}_i\|^2$ that is close to zero. This detection method has the advantage of being simple and almost interference free.

\subsection{MMSE}
Here the MMSE equalizer aims at performing a scalar MMSE detection per user considering the interference as Gaussian noise.
Let's denote $\mathbf{g}_k$ the MMSE equalizer corresponding to system model (\ref{Sys_Model_Sim}). It can be written as :
\begin{equation}
\mathbf{g}_k= \left(\lambda_i^2 \mathbf{v}_k \mathbf{v}_k^\herm + \frac{P^{(n)}}{P_k^{(s)}} \mathbf{I} \right)^{-1} \lambda_i \mathbf{v}_i
\end{equation}

Consequently
\begin{eqnarray}
\hat{s}_k & = & \mathbf{g}_k^\herm \mathbf{r} \\ \nonumber
      & = & \sqrt{P_k^{(s)}} \lambda_k \mathbf{g}_k^\herm \mathbf{v}_k s_k + \mathbf{g}_k^\herm \sum_{i \neq k}\sqrt{P_i^{(s)}} \lambda_i \mathbf{v}_i s_i + \mathbf{g}_k^\herm \mathbf{n}
\end{eqnarray}

Derivation of the capacity is straight-forward and it is not mentioned here.

\subsection{Joint MMSE}
We define the Joint MMSE equalizer as the full matrix MMSE equalizer.
Equation (\ref{Sys_Model_Sim}) can be written in a matrix form as:
\begin{equation}
\mathbf{r} = \mathbf{V} \mathbf{s}+ \mathbf{n}
\end{equation}
with $\mathbf{V} = [\sqrt{P_1^{(s)}} \lambda_1 \mathbf{v}_1, \sqrt{P_2^{(s)}} \lambda_2 \mathbf{v}_2 \dots \sqrt{P_K^{(s)}} \lambda_K \mathbf{v}_K]$ of size $N_R \times N_T$ and $\mathbf{s} = [s_1, s_2 \dots s_K]^\trans$. Joint MMSE detection can be computed as :
\begin{eqnarray}
\hat{\mathbf{s}} & = &  \mathbf{G}^\herm \mathbf{r} \\ \nonumber
     & = & \mathbf{M} \mathbf{s} + \mathbf{G}^\herm\mathbf{n}
\end{eqnarray}
Here $\mathbf{G}$ is the linear MMSE equalizer: $\mathbf{M} = \mathbf{G}^\herm \mathbf{V}$. Channel throughput in this case is computed as follows (\cite{Telatar-1999}):
\begin{eqnarray}
\mathcal{C} & = & \mathcal{H}(\mathbf{r}) -  \mathcal{H}(\mathbf{r} | \mathbf{s}) \\ \nonumber
    & = & \log_2(\det(\mathbf{M} \mathbf{M}^\herm + \mathbf{G}^\herm \mathbf{G})) - \log_2(\det(\mathbf{G}^\herm \mathbf{G}))
\end{eqnarray}
where $\mathcal{H}$ is the entropy.

\subsection{Successive Interference Cancellation (SIC)}
The capacity of a SIC is usually derived considering perfect interference removal. Since interferences are successively canceled, only one term remains in the capacity formula which can be expressed as follows:
\begin{equation}
  \label{eq:capa_sic}
  \mathcal{C}  = \log_2(\det(I+\tilde{\mathbf{H}}^\herm\tilde{\mathbf{H}}))
\end{equation}
For two user, it can be simplified as:
\begin{displaymath}
  \mathcal{C}  = \log_2\left(1 +
    \frac{P_1^{(s)}}{P^{(n)}}\lambda_1^2 +
    \frac{P_2^{(s)}}{P^{(n)}}\lambda_2^2 +
    \frac{P_1^{(s)}}{P^{(n)}}\lambda_1^2\frac{P_2^{(s)}}{P^{(n)}}\lambda_2^2(1-|<v_1,v_2>|^2)
  \right)
\end{displaymath}

\section{System modelization and simulation results}
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 antennas 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 break-point 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|c|c}
      \emph{Syst. assumptions}           & \emph{802.11n} & \emph{802.16m} \\
      \hline\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    \\
    \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 defined in the channel 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{Capacity results}
For the simulations presented below, a set of 20 users is considered. Several detection strategies are benchmarked: the simplest receiver is based on projection (ZF), the second receive is a simple MMSE receiver, the third one is a joint MMSE receiver and the last is a complex SIC receiver in a $2\times2$ MIMO context. Note that the influence of the number of obstacles is not discriminating on the final capacity gain (the impact is less than 0.3\%). The results are averaged using 100 sets of users and 100 channel realizations per user.

To help highlight the interest of such pairing/scheduling techniques, we also implemented an arbitrary method that performs a random user coupling/sequencing.
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).

\begin{figure}[htbp]
  \centering
  \begin{minipage}[b]{0.45\linewidth}
    \centering
    \includegraphics[width=\linewidth]{Result_20_2x2_Projection}
    \caption{Distribution of capacity gain with ZF receiver}
    \label{fig:Projection}
  \end{minipage}
  \hspace{0.05\linewidth}
  \begin{minipage}[b]{0.45\linewidth}
    \centering
    \includegraphics[width=\linewidth]{Result_20_2x2_MMSE}
    \caption{Distribution of capacity gain with MMSE detector}
    \label{fig:MMSE}
  \end{minipage}
\end{figure}

\begin{figure}[htbp]
  \centering
  \begin{minipage}[b]{0.45\linewidth}
    \centering
    \includegraphics[width=\linewidth]{Result_20_2x2_JointMMSE}
    \caption{Distribution of capacity gain with Joint MMSE receiver}
    \label{fig:JMMSE}
  \end{minipage}
  \hspace{0.05\linewidth}
  \begin{minipage}[b]{0.45\linewidth}
    \centering
    \includegraphics[width=\linewidth]{Result_20_2x2_SIC}
    \caption{Distribution of capacity gain with SIC receiver}
    \label{fig:SIC}
  \end{minipage}
\end{figure}

Figures \ref{fig:Projection}, \ref{fig:MMSE}, \ref{fig:JMMSE} and \ref{fig:SIC} present the comparison of the capacity gain distribution observed for the various detection schemes both for an arbitrary and the proposed pairing/scheduling method.
The vertical lines appearing on the plots mark the location of the average gain associated to each distribution.
For all receiver structures studied, the proposed pairing/sequencing method outperforms the random scheduling.
The average gain varies depending on the receiver complexity: 13\% for the projection, 12\% for the MMSE and 5\% for the joint MMSE or SIC structures.
Though the gain is modest for full MMSE receivers note that it comes at a cost of a very small additional complexity paid in the paring process.

\section{Throughput results}
Based on the evaluation methodology described in \cite{Mazet-2007-1}, we compare the sum throughput of single-user SVD-MIMO OFDMA versus multi-user TxBF OFDMA for different antenna configurations and user pairing strategies.

In the simulations conducted a perfect channel knowledge is assumed at the transmitter. The PHY parameters are derived from the WiMAX Release-1 reference system specification \cite{tech.wimaxforum07,website.wimaxforum}. Bit interleaved convolutionally encoded modulation for BPSK, QPSK, 16QAM, 64QAM constellations are used. We consider 1536 carriers for a bandwidth of 20MHz. One or two spatial streams (subscribe stations is assumed to support up to two antennas) are allocated to 1 to 2 users using beamforming on their main signal value vectors. SCME urban-micro channel models are used applying COST-231 Hata path loss model.

Note that, for the sake of simplicity, we do not take into account the interference between cells and all users are assumed localized at equal distance from the base-station in the range assessment evaluations.

\subsection{System deployment model}
\label{sec:syst-depl-model}

The system simulation summary appears in Tab.~\ref{tab:simul-envir-summ-1}. This model applies to any duplexing mode proposed for 802.16e amendment \cite{spec.802.16e}.

\begin{table}[htbp]
  \centering
  \caption{Simulation environment summary}
  \begin{tabular}{l|l}
    \emph{Parameters} & \emph{Value} \\
    \hline\hline
    Operating frequency & 2500MHz \\
    BS-to-BS distance & 1.5km \\
    Minimum mobile-to-BS distance & 35m \\
    BS height & 32m  \\
    Mobile terminal height & 1.5m \\
    Propagation model & COST-231 \\
    & mod. Hata (suburban) model \\
    BS thermal noise figure & 5dB \\
    Mobile terminal noise figure & 7dB \\
    Thermal noise density & -174dBm/Hz  \\
    BS antenna gain incl. cable Loss & 15dB \\
    Mobile terminal Maximum PA power  & 200mW (23dBm) \\
    Signal bandwidth & 20MHz \\
    \# of BS Tx/Rx antennas & 1 or 2 \\
    \# of MT Tx/Rx antennas & 2 \\
    Modulation constellation & BSPK, QPSK, 16QAM \\
    & and 64QAM \\
    FEC & Conv. code (o171, o133) \\
    Puncturing rate & 1/2, 2/3, 3/4 and 5/6 \\
    Performance target & PER of 5\% over 1kB packet \\
  \end{tabular}
  \label{tab:simul-envir-summ-1}
\end{table}

\subsection{Pathloss model}
\label{sec:pathloss-model}
The proposed path loss model is based on the well known COST-231 modified Hata model for systems supporting carrier frequencies less than or equal to 2.5GHz.
The COST-231 modified Hata model at 2.0GHz is used to simulate the IEEE~802.16m reference system in suburban mode ($L=126.2+36\log_{10}(R)$) for a 2.5Ghz carrier frequency.

\subsection{Evaluation methodology}
\label{sec:eval-meth}

For the simulations a band AMC like OFDMA system with sub-channels composed of  14 adjacent carriers is used: in 20MHz, 100 chunks are considered for a total of 1536 useful carriers transmitted.
In order to evaluate the throughput versus distance behavior of the proposed user paring and best band selection scheme, we assume that all users have the same path loss (are at the same distance from the BS) but experience a different channel. We also assume that the Channel State Information is perfectly known at the base station and at the mobile terminal side. Statistical beamforming transmission averaged over the chunk is used to limit the overhead for explicit vectors feedback.

For user $i$, when considering frequency slot $k$, we defined statistical beamforming as the weight vectors extracted from the following $\mathbf{V}_{k,i}$ matrix:
\begin{gather}
  \mathbf{R}_{k,i} = \frac{1}{\card(\mathscr{S}_k)} \sum_{l\in\mathcal{S}_k} \mathbf{H}^\herm_i(l)\mathbf{H}_i(l) \\
  \mathbf{R}_{k,i} = \mathbf{V}_{k,i} \mathbf{\lambda}_{k,i}\mathbf{V}^\herm_{k,i}
\end{gather}
where $\mathbf{R}_{k,i}$ is an estimate of the correlation matrix of the channel $[\mathbf{H}_i(l)]_{l\in\mathcal{S}_k}$ seen by user $i$ over the set of subcarrier $\mathcal{S}_k$ defining the  frequency chunk $k$. Matrix $\mathbf{V}_{k,i}$ is composed of the eigen-vectors of $\mathbf{R}_{k,i}$.

All simulations are performed for the uplink and the base-station is equipped with a linear equalization scheme (joint MMSE per carrier). This means that, for two paired users, the equalizer $\mathbf{G}_{k,(i,j)}(l)$ on subcarrier $l$ is chosen as:
\begin{align}
  \forall l\in\mathscr{S}_k \qquad &
  \tilde{\mathbf{H}}_{i,j}(l) = [\;\mathbf{H}_i(l)\tilde{\mathbf{V}}_{k,i}\quad \mathbf{H}_j(l)\tilde{\mathbf{V}}_{k,j}\;] \\
  & \mathbf{G}_{k,(i,j)}(l) = (\tilde{\mathbf{H}}_{i,j}(l) \star \tilde{\mathbf{H}}_{i,j}(l)^\herm + \sigma^2\mathbf{I})^{-1} \star \tilde{\mathbf{H}}_{i,j}(l)
\end{align}
where $\tilde{\mathbf{H}}_{i,j}$ is the equivalent channel for user $i$ and $j$ beamformed respectively by $\tilde{\mathbf{V}}_{k,i}$ and  $\tilde{\mathbf{V}}_{k,j}$. Note that, for single-user configuration (\emph{i.e.} no user $j$), $\tilde{\mathbf{V}}_{k,i}$ is a matrix of 1 or 2 columns depending on the number of used stream extracted from $\mathbf{V}_{k,i}$ and for multi-user configuration, $\tilde{\mathbf{V}}_{k,i}$ and $\tilde{\mathbf{V}}_{k,j}$ are respectively the main eigen-vectors extracted from $\mathbf{V}_{k,i}$ and $\mathbf{V}_{k,j}$.

\subsection{Best band selection and pairing algorithm evaluation}
\label{sec:pairing-algos}

We consider a larger pool of users (\emph{i.e.} 1000 users) than the number or users served per OFDM symbol: the total number of users are allocated over 5 different time slots when using SDMA user pairing and 10 different time slots when no spatial multiplexing is used. The bandwidth is subdivided into 100 frequency chunks of 14 adjacent carriers each. Note that single-user multi-stream transmissions is considered when no UL SDMA is applied. CIR is almost constant on each chunk since the occupied bandwidth is much smaller than the frequency coherent bandwidth of the SCME channel.
The evaluation carried out is preformed on a chunk basis and in reality one would allocate several sub-channels per user. The expected impact in terms of performance shift is anticipated to be marginal.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.65\linewidth]{ft_scheduler}
  \caption{Time scheduling, frequency scheduling and user pairing}
  \label{fig:time-sched-freq}
\end{figure}

Four user allocation strategies are evaluated in the single user context and multi-user context:
\begin{enumerate}
\item The first scheduler arbitrary allocates 1 or 2 users per time and frequency slot. It corresponds to a lower bound on the achievable performance. It is referred as \emph{Arbitrary} is the following curve legends.
\item The second scheduler starts by allocating 10 users per frequency slot arbitrary then, it applies our user pairing method, packing 10 users two by two over the 5 consecutive time slots. It is referred as \emph{User Pairing}.
\item The third scheduler performs only a best band selection, optimizing user allocation per frequency slot without taking into account of the fact that, in some cases, two users  transmitting simultaneously may interfere. It is referred as \emph{Frequency Selective}. Frequency slot allocation is made by maximizing average capacity sequentially: if $\tilde{c}_i(k)$ defined as:
  \begin{equation}
    \label{eq:average_slotted_capacity}
    \tilde{c}_i(k) = \frac{1}{\card(\mathscr{S}_k)} \sum_{l\in\mathcal{S}_k} \log_2(\det(\mathbf{I} + \sigma^{-2}\mathbf{H}_i(l)\mathbf{H}^\herm_i(l)))
  \end{equation}
is maximum, user $i$ gets slot $k$. Once a user is served, he can't claim for another slot. Only one other user can potentially get it however, the second user is selected using the same criteria.
\item The fourth scheduler starts by performing a frequency scheduling and then applies our user pairing method, packing 10 users two by two over five consecutive time slots. It is referred as \emph{FS+UP}.
\item The last scheduler operates a best band selection taking into account user interference. This means that, for slot $k$, the scheduler chooses user $i$ which maximizes $\tilde{c}_i(k)$ then, it looks for user $j$ maximizing the average capacity of the MIMO channel created by the two users $\tilde{c}_{(i,j)}(k)$.
\begin{gather}
  \forall l\in\mathscr{S}_k \qquad \mathbf{H}_{(i,j)}(l) = [\;\mathbf{H}_i(l)\quad \mathbf{H}_j(l)\;] \nonumber\\
  \tilde{c}_{(i,j)}(k) = \frac{1}{\card(\mathscr{S}_k)} \sum_{l\in\mathcal{S}_k} \log(\det(\mathbf{I} + \sigma^{-2}\mathbf{H}_{(i,j)}(l)\mathbf{H}^\herm_{(i,j)}(l)))
\end{gather}
  It is referred as \emph{Multi-User FS}. This scheme is extremely time consuming but yields the best performance.
\end{enumerate}

We assume that all mobile subscribers are at equal distance to the base-station (i.e. experience the same path loss) in order to present curves of aggregated PHY over the air throughput versus distance. Assuming that a certain number of users will be seen by the base-station at same SNR is realistic since this is one of the goals of the ranging procedure for performing transmit power control in order to avoid AGC recalibration when switching users during the uplink phase at the base-station.

\subsection{Throughput for 1x2 antenna configurations}
\label{sec:throughput-1x2}

Figure \ref{fig:mu-ofdma-sdma-1x2} presents aggregated PHY over the air throughput versus distance for configurations using 1 Tx antenna and 2 Rx antennas.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=.8\linewidth]{mu_ofdma_sdma_1x2}
  \caption{Multi-users versus single user for 1Tx 2Rx configurations}
  \label{fig:mu-ofdma-sdma-1x2}
\end{figure}

Many comparisons can be drawn from this figure:
\begin{enumerate}
\item the yellow curve, denoted by `2 users - Arbitrary', compared to the red curve, denoted by `1 user - Arbitrary', shows the gain of user pairing which is huge close to the base-station (around 2 times the aggregated throughput) but completely disappears at cell border where the inter-user interference level becomes negligible compared to the noise level.
\item the orange curve, denoted by `1 user - Frequency Selective', compared to the red curve, denoted by `1 user - Arbitrary', and also the cyan curve, denoted by `2 users - Frequency Selective', compared to the  yellow curve, denoted `2 users - Arbitrary', illustrates the gains of best band selection. At 200m, aggregated throughputs are respectively increased by a factor of 1.5 and 1.3. Over most of the cell, this yields a throughput gain of 10Mbps to 20Mbps.
\item the green curve, denotes by `2 users - User Pairing' compared to the yellow curve, denoted by `2 users - Arbitrary', and also the blue curve, denoted by `2 users - FS + US', compared to the cyan curve, denoted by `2 users - Frequency Selective', highlights the gain of our low complexity user pairing technique. At 200m, aggregated throughputs are increased by 15\% and, over most of the cell there is a throughput gain of 12Mbps.
\item the magenta curve, denoted by `2 users - Multi-User FS' is the best technique considered when one can afford its complexity since it performs jointly user pairing and best band selection providing an idea on an upper bound on achievable throughput. 
\end{enumerate}

\subsection{Throughput for 2x2 antenna configurations}
\label{sec:throughput-2x2}

Figure \ref{fig:mu-ofdma-sdma-1x2} presents aggregated PHY over the air throughput versus distance for configurations using 2 Tx antenna and 2 Rx antennas.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=.8\linewidth]{mu_ofdma_sdma_2x2}
  \caption{Multi-users versus single user for 2Tx 2Rx configurations}
  \label{fig:mu-ofdma-sdma-2x2}
\end{figure}

The goal of this figure is to compare single user multi-stream uplink transmissions versus multi-user single stream uplink transmission. As one can see the yellow curve, denoted by `2 users - Arbitrary', crosses the red curve, denoted by `1 user - Arbitrary', at low SNR. It appears that, for ranges exceeding half the cell radius, it is better to use single user multi-stream transmission over mono-stream multi-user (SDMA).

Moreover, by comparing the cyan curve, denoted by `2 users - Frequency Selective' and the green curve, denoted by `2 users - User Pairing', it tells that, for high SNR, user pairing or best band selection slot selection individually behaves the same same, but at cell border (low SNR) best band selection supersedes user pairing.

From these performance curves, one can conclude that,
\begin{enumerate}
\item it is always better to serve 2 users rather than 1,
\item best band selection (BBS) gives us an huge improvement in SIMO and SIMO configurations,
\item user pairing (UP) improves performances in MIMO systems,
\item joint UP and BBS is the golden nugget on which we will focus our future studies.
\end{enumerate}

\section{Conclusions}
\label{sec:conclusions}

In this report, we detailed a scheduling scheme for the uplink of the MIMO -- channel aware systems -- that supports \emph{simultaneous transmitting} users with a very little amount of interference that helps us to benefit a very simple receiver scheme. 

Performance assessments demonstrates the potential interest of multi-user MIMO in Broadband Wireless Access systems, and it has to be proposed for standardization: IEEE~802.16m is the perfect landing zone for such technology. Moreover, by inserting it into IEEE~802.16m, this mechanism will create some hooks for future and more complex multi-user strategies.

Performance assessments also provides an interesting insight: multi-users diversity gain is restored in MIMO when considering user pairing on top of best band allocation. MAC schedulers will need to capture these considerations to fully exploit MU-MIMO SDMA in OFDMA systems (16e/m and beyond) and that leads to potential differentiators for Motorola WiMAX base-stations. Some new investigations have been started on low-complexity user UP and BBS for other MIMO schemes.



\bibliographystyle{plain}
\bibliography{abbrev,conf,journal,book,patent,standard,report,stage,alien,reference}
\end{document}
