\chapter{Pilot Assignment Problem}\label{section:formulation}

The achievable rate for each user is damaged by the interference among pilot-sharing users. In this regard, the PA management is required constantly to ensure the network performance. While the pilot resources are repeatedly managed for each coherence interval, the large-scale channel parameters for some users are assumed to be preserved even if the interval is updated. In order to alleviate the computational loads, the latest assignments for those cases can leverage the  non-orthogonal PA task. 
The initial setup policy is conducted so that the results of previous assignments for static users are maintained in the new PA.
To this end, such users are preassigned with the same pilot sequence as the previous assignment, and it is assumed that $N_p$ of users are orthogonally preassigned to all of the pilot resources.

\begin{figure}[!]
    \centering
    \includegraphics[width=\columnwidth]{figures/fig3-1_toyexample_preassign.eps}
    \caption{An example of 6-user PA with preassignment.}%\vspace*{-.5em}
    \label{fig:3.1}
\end{figure}

% \subsection{Pilot-Sharing}
For ease of description, a simple example in Fig. \ref{fig:3.1} is considered where two pilots are assigned to six users and both are preassigned to user 1 and user 4, respectively.
Let a set $\mathcal{P}_a$ be indices of preassigned users to which the $a$-th pilot sequence is dedicated, i.e., $\mathcal{P}_1 =\{1\}$  and $\mathcal{P}_2 =\{4\}$. The PA problem is characterized by a combinatorial optimization to select pilot-sharing groups that share the same pilot sequences as the preassigned users. 
The PA solution is obtained so that the number of pilot-sharing users is as uniform as possible over pilot sequences. Since $K-N_p$ remaining users need the assignment, it is grouped into ${(K-N_{p})}/{N_{p}}$ members, and there are ${K-N_p \choose K/N_{p} -1}$ different feasible groups. Let $\mathcal{K}_{i}$ denote the $i$-th feasible group ($i=1,\ldots, {K-N_p \choose K/N_{p} -1}$). In the example, we have ${4 \choose 2}=6$ feasible groups, i.e., $\mathcal{K}_{1}=\{2,3\}, \dots, \mathcal{K}_{6}=\{5,6\}$. %toy example 그림 만들어서 설명하자
% feasible group 중에는 같은 유저를 포함하는
Since each user is assigned a single pilot, the feasible groups are selected so that the elements do not overlap in one solution.
For the concrete indication of the PA, an integer variable $x_i$ is associated with the pilot sequence assigned to users in group $\mathcal{K}_i$. Thus, It holds that $x_i=a$ if the group $\mathcal{K}_i$ is matched with $a$-th pilot and $x_i=0$ otherwise. In addition, the corresponding state vector $\mathbf{x}=[x_1,\dots,x_{6}]$ is defined. Fig. \ref{fig:2_toy} shows the example for the case where $\mathcal{K}_1$ and $\mathcal{K}_6$ are used for PA among the feasible groups. The corresponding solution is  $\mathbf{x}=[1,0,0,0,0,2]$. % 솔루션이 유효하기 위해선 할당에 사용된 feasible group 간에 멤버 중복이 발생하지 않아야 한다.

\begin{figure}[!]
    \centering
    \includegraphics[width=\columnwidth]{figures/fig2_toy_example}
    \caption{The relationship among variables in a 6-user PA example.}%\vspace*{-.5em}
    \label{fig:2_toy}
\end{figure}

Among the valid states, PA tasks are purposed to find the optimal solution that maximizes the network-wide utility such as sum-rate.
A partial sum-rate denoted by $R_{i a}$ is defined corresponding to the pilot-sharing members if users in  $\mathcal{K}_i$ are assigned to the $a$-th pilot and given as
\begin{equation}
    {R}_{i a} \triangleq \sum_{k \in \mathcal{K}_i} R_{k} + \sum_{l \in \mathcal{P}_a} R_{l} \, .\label{eq:weight_rate}
\end{equation}

\section{Generic Formulation}

% Where $i$ and $a$ belong to the set of indices of feasible groups $\mathcal{I}$ and pilot resources $\mathcal{A}$,
% Each set of indices of feasible groups and pilot resources is denoted as $\mathcal{I}$ and $\mathcal{A}$, respectively.
Let $\mathcal{I}$ denote the set of indices for feasible groups and $\mathcal{A}=\{1,\dots,N_\mathrm{p}\}$ be the set for pilot resources. the corresponding PA problem is formulated as
\begin{subequations}
\begin{align}
\text{\textbf{(P1)}}\ \max_{\mathbf{x}} & \sum_{i \in \mathcal{I}} \sum_{a \in \mathcal{A}} {R}_{i a} \mathbbm{I}\left(x_{i}=a\right) &&\\
\text{subject to~} & x_i \in \mathcal{A} \cup \{0\} \, ,~\forall i \in \mathcal{I} \, ,\\
&\sum_{i \in \mathcal{I}}\mathbbm{I}\left(x_i=a\right)\leq 1 \, , ~\forall a \in \mathcal{A} \, , \label{eq:const_one} \\
&\sum_{\mathclap{\ i^{\prime} \in \mathcal{N}(i)}} \mathbbm{I}\left(\left(x_i \neq 0\right) \land \left(x_{i^{\prime}} \neq 0 \right)\right)=0 \, , ~\forall i \in \mathcal{I} \, , \label{eq:const_neigbor}
%&\mathbbm{I}\left(x_i \neq 0\right)+\mathbbm{I}\left(x_{i^{\prime}} \neq 0\right) \leq 1,~i^{\prime} \in \mathcal{N}(i), \forall i, 
\end{align}
\end{subequations}
where $\mathbbm{I}(\cdot)$ is the indicator function that yields one if the input statement holds true and zero otherwise, $\land$ is the logical intersection, and $\mathcal{N}(i)$ is the set of neighborhoods of the $i$-th group, i.e., $\mathcal{N}(i) = \{i^{\prime}:\mathcal{K}_i \cap \mathcal{K}_{i^{\prime}} \neq \emptyset, i^{\prime} \neq i \}$. 
The constraint in \eqref{eq:const_one} indicates that at most one group is allocated to each pilot. Furthermore, the constraint in \eqref{eq:const_neigbor} means that feasible groups containing the same users are not used simultaneously for a PA solution.
% , since each user is assigned a single pilot rather than multiple pilots.
% Furthermore, the constraint in \eqref{eq:const_neigbor} means that only a single pilot is assigned to each user.

\section{Unconstrained Optimization Formulation}
The constraints in \textbf{(P1)} are associated with the groups assigned to individual pilots. 
This point of view motivates the introduction of a new function that considers the entire constraints. To represent them in an analytical way, a penalizing function for ${a}$-th pilot, $\mathcal{F}_{a}\left(\mathbf{x}\right)$, is defined to return a negative infinite value when the input vector $\mathbf{x}$ violates constraints related to \eqref{eq:const_one} and \eqref{eq:const_neigbor} as
\begin{subequations}
\begin{empheq}[left={\hspace*{-.6em}\mathcal{F}_{a}\left(\mathbf{x}\right)\triangleq\empheqlbrace}]{align}
    {-\infty} &\ \text{ if } \textstyle\sum\limits_{i \in \mathcal{I}}\mathbbm{I}\left(x_{i}=a\right)>1 \, ,\label{eq:case_one}\\
    %-\infty &{}\nonumber\\[-5pt]
    {}&\ \text{ or } \exists i ~\text{s.t. } \textstyle\sum\limits_{\mathclap{\ i^{\prime} \in \mathcal{N}(i)}} \mathbbm{I}\left(\left(x_i \neq 0\right) \land \left(x_{i^{\prime}} \neq 0 \right)\right)\neq 0 \, ,\hspace*{-2em}\label{eq:case_neighbor}\\
    0\ &\ \text{ otherwise} \, .
\end{empheq}
\end{subequations}
%\begin{subequations}
%\begin{numcases}{\mathcal{F}_{a}\left(\mathbf{x}\right)\triangleq }
%    -\infty & if $\sum\limits_{i \in \mathcal{I}}\mathbbm{I}\left(x_{i}=a\right)>1$,\label{eq:case_one}\\[3pt]
%    -\infty & if $\exists i ~\text{s.t. } \sum\limits_{\mathclap{\ i^{\prime} \in \mathcal{N}(i)}} \mathbbm{I}\left(\left(x_i \neq 0\right) \land \left(x_{i^{\prime}} \neq 0 \right)\right)\neq0$,\hspace*{-2em}\nonumber\\[-1em]\label{eq:case_neighbor}\\
%    0 & otherwise.
%\end{numcases}
%\end{subequations}
% Note that \eqref{eq:case_neighbor} corresponds to the case where $\mathcal{K}_{i}$ is assigned to the $a$-th pilot when any neighbor group of $\mathcal{K}_{i}$ is used to the assignment associated with \eqref{eq:const_neigbor}. The constraint in \eqref{eq:case_one} corresponds to the constraint in \eqref{eq:const_one}. However, the neighbor groups are not considered since \eqref{eq:case_neighbor} includes such a case.
Note that the case \eqref{eq:case_one} is associated with the constraint in \eqref{eq:const_one}, but specifically focuses on the ${a}$-th pilot. The case \eqref{eq:case_neighbor} corresponds to that some neighboring groups are used in a PA solution so violating the constraint in \eqref{eq:const_neigbor}. 
Likewise, a utility function $\mathcal{R}_i$ is defined to represent the weight for the objective function by the value of variable $x_i$ as
% \begin{numcases}{\mathcal{R}_{i}\left(x_i\right)\triangleq }
%     R_{i a} & if $x_i = a$, and $a \in  \{0, \cdots, N_\mathrm{p}\}$,\\
%     0 & otherwise.
% \end{numcases}
\begin{equation}
    \mathcal{R}_{i}\left(x_i\right) \triangleq \sum_{a \in \mathcal{A}}{R}_{i a} \mathbbm{I}\left(x_{i}=a\right).\label{rrr}
\end{equation}%\vspace*{-.7em}

An unconstrained optimization formulation from \textbf{(P1)}  is obtained from \eqref{rrr} as
\begin{align}\label{eq:p1prime}
    \text{\textbf{(P2)}}\ 
    \max_{\mathbf{x}} &     \sum_{i \in \mathcal{I}} \mathcal{R}_i (x_i) 
    + \sum_{a \in \mathcal{A}} \mathcal{F}_a(\mathbf{x}) \, .
    % \text{subject to} & \nonumber \\
    % &x_i \in [0, T], \ \forall i.
\end{align}
The optimal solution of (\textbf{P2}) is identical to that of (\textbf{P1}). Since this is factorized as a simple sum of utility functions and penalizing functions, this allows us to establish a distributed approach to solve the problem. 
The optimal states are found locally by individual functions, and their information is exchanged for comparison with each other.
The state variables are repeatedly corrected to deactivate all the penalizing functions and are expected to converge to a global solution that optimizes the total sum of the utility functions. % Some state variables that have inconsistent assignment are repeatedly corrected to be consistent over all functions and are expected to converge to a valid global solution that optimizing the total sum of the functions.
In the next chapter, we presents an efficient solution for \textbf{(P2)} based on a cooperative consideration over a graphical representation of the overall optimization task.