Optimal Mode Selection in D2D-Enabled Multi-Base Station Systems
Yuan~Liu
~\IEEEmembership{Member
~IEEE
%Device-to-device (D2D) communication can increase network throughput by spatial reuse of cellular resources (spectrum efficiency) and prolong the battery life of devices by reducing transmit power (energy efficiency). In this paper, we consider device-to-device (D2D) communication underlaying uplink cellular networks with multiple base stations (BSs), where each user can switch between traditional cellular mode (through BS) and D2D mode (by connecting proximity user), namely mode selection. We impose load balancing constraints on BSs to efficient resource usage. The joint problem of mode selection and user association is formulated as a combinatorial problem and NP-complete. We adopt a graph-based approach to solve the problem globally optimally in polynomial time. To further reduce complexity, we also propose a distributed algorithm based on dual method. We show that the proposed distributed algorithm achieves nearly the same performance as the proposed optimal graph based algorithm.
CL2015-2583.tex
%\documentclass[10pt,conference]{IEEEtran}
\documentclass[10pt, final, journal, letterpaper, twocolumn]{IEEEtran}
%\documentclass[12pt, draftclsnofoot, journal, letterpaper, onecolumn]{IEEEtran}

\usepackage{cite}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{graphicx}
%\usepackage{epstopdf}
%\usepackage{hyperref}
\usepackage{color}
\usepackage[normalsize]{subfigure}

\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\begin{document}

\title{Optimal Mode Selection in D2D-Enabled Multi-Base Station Systems}
\author{Yuan~Liu,~\IEEEmembership{Member,~IEEE}
%\thanks{Manuscript received 11 September, 2015; accepted 20 December, 2015. This work was supported in part by the Natural Science Foundation of China under Grant 61401159, in part by the open research fund of Key Lab of Broadband Wireless Communication and Sensor Network Technology (Nanjing University of Posts and Telecommunications), Ministry of Education, under Grant NYKL201501, and in part by the Fundamental Research Funds for the Central Universities. The associate editor coordinating the review of this manuscript and approving it for publication was A. Lioumpas.}
\thanks{Y. Liu is with the School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510641, China (email: eeyliu@scut.edu.cn).}
}

\maketitle

\begin{abstract}
%Device-to-device (D2D) communication can increase network throughput by spatial reuse of cellular resources (spectrum efficiency) and prolong the battery life of devices by reducing transmit power (energy efficiency).
In this paper, we consider device-to-device (D2D) communication underlaying uplink cellular networks with multiple base stations (BSs), where each user can switch between traditional cellular mode (through BS) and D2D mode (by connecting proximity user), namely mode selection. We impose load balancing constraints on BSs to efficient resource usage. The joint problem of mode selection and user association is formulated as a combinatorial problem and NP-complete. We adopt a graph-based approach to solve the problem globally optimally in polynomial time. To further reduce complexity, we also propose a distributed algorithm based on dual method. We show that the proposed distributed algorithm achieves nearly the same performance as the proposed optimal graph based algorithm.
\end{abstract}

\begin{keywords}
Device-to-device (D2D) communication, mode selection, load balancing, graph theory, distributed algorithm.
\end{keywords}

\section{Introduction}

The explosive growth of mobile users and their traffic requirements force researchers to seek new paradigms to revolutionize the traditional cellular networks. Device-to-device (D2D) communication recently has emerged as a promising technique for improving system performance. The idea is to enable two mobile devices in proximity of each other to establish a direct connection and to bypass the base station (BS). By incorporating D2D communication into cellular networks, mobile users can operate on \emph{D2D mode} (i.e, two users establish a direct local link) or traditional \emph{cellular mode} (i.e., two users communicate through BS), which may be controlled by either network or users. D2D communication gains many benefits, like spectrum/energy efficiency improvement, coverage extension, and cellular offloading.
%Recently, D2D has been standardized by the Third Generation Partnership Project (3GPP) Long Term Evolution Advanced (LTE-A) \cite{3gpp1,3gpp2}.

However, D2D communication poses a set of new technical challenges, such as interference management and mode selection which are quite different from those of traditional cellular networks. There are a number of works for interference management by resource allocations \cite{Zulhasnine2010,Yu2011,Min2011,Xu2013,Feng2013,YuanICC2014}.
%For instance, authors in \cite{Zulhasnine2010} studied the channel assignment problem and proposed a greedy heuristic algorithm. In \cite{Yu2011}, power allocation was studied to maintain minimum and maximum signal-to-interference-plus-noise ratio (SINR) constraints of users. In \cite{Min2011}, authors proposed a predefined interference limited area where D2D users do not transmit for avoiding strong interference to  cellular users. Channel reuse was investigated by a combinatorial auction approach in \cite{Xu2013}. A three-step resource allocation scheme was proposed in \cite{Feng2013} to coordinate interference.   Two pricing algorithms for distributed power allocation of D2D users were proposed in \cite{YuanICC2014} to guarantee that the aggregate interference from D2D users at the BS is kept below a threshold.
%
To take full advantage of D2D communication, each user needs to carefully switch between cellular mode and D2D mode. This is known as mode selection which is the unique problem in D2D-enabled cellular networks. In \cite{DopplerWCNC2010}, a mode selection procedure was proposed to limit interference caused by D2D communication.
%The authors in \cite{Hakola} designed mode selection taking into account the network information, such as link gains, noise levels and SINR. A coalition game was proposed in \cite{Akkarajitsakul} for mode selection.
In \cite{XiangGCW2012}, a distance-dependent mode selection algorithm with power optimization was analyzed. Joint mode selection and channel assignment based on stochastic framework was considered in \cite{Han2012}. Joint mode selection and power allocation was studied in \cite{Jung2012} by using exhaustive search all possible mode combinations of users. The authors in \cite{Chien2012} studied joint mode selection and resource allocation as as a mixed integer non-linear programming (MINLP) problem. Heuristic algorithms were proposed for joint mode selection, channel and power allocation in \cite{Guanding2014,Chenfei2014}.

In view of the related works based on mode selection \cite{DopplerWCNC2010,XiangGCW2012,Han2012,Jung2012,Chien2012,Guanding2014,Chenfei2014},
it is found that the previous efficient solutions for the resource allocation problems are always not optimal due to the combinational nature of mode selection. Additionally, most of the related works considered single-BS case. If with multiple BSs, the problem becomes more complex since it involves BS selection which tightly couples mode selection. Moreover, if with multiple BSs, load balancing is crucial for efficient and fair utilization of network resources, which also has not been considered in the D2D-enabled cellular networks yet.
%Last but not least, for uplink communication, most previous works resort to centralized resource allocation and scheduling

Motivated by the above understanding, in this paper, we consider D2D communication underlaying \emph{uplink} cellular network assisted by multiple BSs. The considered system model is general and can be specified as a multicell scenario with multiple macro BSs or a small cell scenario where a macro BS coexists with multiple small BSs.
In the network, each user can switch between cellular mode and D2D mode. The main contributions of this paper are summarized as follows:
%
%\begin{itemize}
    We formulate the joint optimization problem of mode selection and BS selection in D2D-enabled multi-BS cellular networks. This joint problem has not been considered in the literature.
    %The distinct feature about our problem formulation is that we impose load balancing constraints at multiple BSs for efficient resource usage and balanced traffic load.
    The studied problem is a combinatorial problem and NP-complete. We adopt a centralized graph approach to solve the problem \emph{globally optimally} in polynomial time.
   To reduce the complexity and signaling overhead, we further propose a distributed algorithm which solves the original problem in the dual domain via Lagrangian dual decomposition. Simulation results show that the distributed algorithm performs very closely to the centralized algorithm.
%\end{itemize}

%The remainder of the paper is organized as follows. Section II describes the system model and the problem formulation. Section III presents the optimal centralized algorithm by graph theory. Two distributed algorithms are detailed in Section IV. Extensive simulations are provided in Section V. Finally, Section VI concludes the paper.

\section{System Model and Problem Formulation}

%%
%\begin{figure}[t]
%\begin{centering}
%\includegraphics[scale=1]{system.eps}
%\vspace{-0.1cm}
% \caption{An example of system model with two BSs and two users. The solid and dash lines represent possible communication links and interference links, respectively. }\label{fig:system}
%\end{centering}
%\vspace{-0.3cm}
%\end{figure}
%%

We consider a D2D-enabled cellular network consisting of $M$ users and $N$ BSs. The considered multi-BS system model is general, which can be a multicell with multiple macro BSs or a small cell where a macro BS coexists with multiple small BSs (i.e., heterogeneous cellular networks). $\mathcal U=\{1,\cdots,M\}$ is the set of users and $\mathcal B=\{1,\cdots,N\}$ is the set of BSs. Each user consists of one dedicated transmitter and one dedicated receiver. In the following, we use ``user", ``transmitter", and ``receiver" interchangeably for convenience. Each user $i$  can associate with one BS by cellular mode or its own receiver by D2D mode. For notational convenience, we define $\mathcal B^+\triangleq\{0,1,\cdots,N\}$. That is to say, if a user's associated BS is $0$, the user does not connect any BS and operates on D2D mode. In this paper we focus on \emph{uplink} communication.
%
%The wireless channel is modeled by small-scale fading, shadowing, and path loss. We assume that the transmission is based on slotted basis, and the channel gain remains unchanged in a transmission slot but may vary from one slot to another.
To simplify the problem, we do not consider power control and assume that the transmit power of users are fixed.

Let $g_{ij}$ denote the channel gain between user $i$'s transmitter and BS $j$, $h_{ij}$ the channel gain from transmitter $i$ to receiver $j$, $p_i$ the transmit power of transmitter $i$, and $n_0$ the power of the background noise. In this paper, we consider the Rayleigh block fading where the fading is assumed to occur identically (with Rayleigh distribution) and independently from one block to another but can be considered constant within each block.
Each user $i$'s performance is characterized by a utility function $u_i(\gamma_{ij})$, which is a function of the received signal-to-interference plus noise ratio (SINR) $\gamma_{ij}$ that depends on its association $\mathcal B^+$:
%
\begin{eqnarray}\label{eqn:sinr}
  \begin{cases}\gamma_{ij}=\frac{p_ig_{ij}}{\sum\limits_{k\in\mathcal U, k\neq i}p_kg_{kj}+n_0},~j\in\mathcal B,~{\rm for~ cellular~mode}\\
  \gamma_{ij}=\frac{p_ih_{ii}}{\sum\limits_{k\in\mathcal U, k\neq i}p_kh_{ki}+n_0},~j=0,~{\rm for~ D2D~mode}.\end{cases}
\end{eqnarray}
%

%Note that in general $h_{ij}\neq h_{ji}$ since the latter represents the channel gain from user $j$'s transmitter to user $i$'s receiver.
The utility $u_i(\gamma_{ij})$ can be defined as many popular metrics, such as rate $u_i(\gamma_{ij})=R_i(\gamma_{ij})$, weighted proportional fairness $u_i(\gamma_{ij})=w_i\log R_i(\gamma_{ij})$, and energy efficiency $u_i(\gamma_{ij})=\frac{R_i(\gamma_{ij})}{p_i}$, where $R_i$ is user $i$'s rate.
Since the transmit power of users are assumed to be fixed, all values of SINRs are deterministic through \eqref{eqn:sinr}, and so are the utilities. Thus different utility functions do not affect the proposed algorithms.

%We illustrate an example of two users and two BSs in Fig. \ref{fig:system}: If Tx 2 associates with BS 2 then the links of Tx 2 to BS 1 and Tx 1 to BS 2 are interference; If Tx 2 associates with BS 1 then the links of Tx 1 to BS 1 and Tx 2 to BS 2 is interference; Moreover, if Tx 2 connects Rx 2 then the link of Tx 1 to Rx 2 is interference.

We denote $b_j$ as the maximum number of users that BS $j$ can support, or referred as to \emph{effective load}, and we assume that $b_j$ is a constant in each transmission slot. The operator adjusts $b_j$ to guarantee a certain degree of load balancing.
%\footnote{ Notice that there is no single figure of metric to measure the performance of load balancing. The considered load balancing metric is practically valid if the users have full buffers so that the load on a BS is directly proportional to the number of users associated with it.}
We let $\sum_{j\in\mathcal B}b_j=B$ and in general $B\leq M$ in D2D-enabled cellular network.

Each user can switch between cellular mode and D2D mode. Let $x_{ij}$ be the binary association variable with $x_{ij}=1$ indicating the connection of user $i$ to BS $j$ and $x_{ij}=0$ otherwise, $\forall i\in\mathcal U$, $\forall j\in\mathcal B^+$. Our goal is to determine the joint of user association and mode selection that maximizes the overall network utility. Mathematically, the problem can be formulated as
%
\begin{subequations}\label{eqn:p1}
\begin{align}
\textbf{P1}:~~\max_{\mathbf x}~&\sum_{i\in\mathcal U}\sum_{j\in\mathcal B^+}x_{ij}u_i(\gamma_{ij}) \\
{\rm s.t.}~~ &\sum_{j\in\mathcal B^+}x_{ij}\leq1,~~\forall i\in\mathcal U \label{eqn:x} \\
&\sum_{i\in\mathcal U}x_{ij}\leq b_j,~~\forall j\in\mathcal B \label{eqn:bj} \\
& x_{ij}\in\{0,1\},~~\forall i\in\mathcal U,\forall j\in\mathcal B^+, \label{eqn:binary}
\end{align}
\end{subequations}
%
where $\mathbf x\triangleq \{x_{ij}\}$; the constraint \eqref{eqn:x} states that each user can associate with at most one BS; the constraint \eqref{eqn:bj} ensures load balancing for BSs.


%\begin{remark}
%If without the load constraint \eqref{eqn:bj}, the problem becomes simple and the optimal solution follows the traditional max-utility association, i.e., each user simply associates with the strongest SINR over $\mathcal B^+$. On the other hand, if the network exists only one BS, the solution is also trivial.  That is, each user selects cellular or D2D mode by max-utility association, then the BS selects at most $b_j$ associated users with higher utilities and offloads other associated users into D2D mode.  Therefore, the load constraint \eqref{eqn:bj} imposed at multiple BSs significantly complicates the problem.
%\end{remark}

\section{Centralized Algorithm}

\textbf{P1} is an integer programming problem and NP-complete due to the combinational nature \cite{West}.
%Finding its optimal solution needs exhaustive search or branch-and-bound method and results in exponential complexity.
In this section, we propose a graph theoretical  approach to solve the problem \emph{globally optimally} in polynomial time.

Before beginning, we assume that a central controller is available so that the centralized resource allocation can be employed and the full network information can be perfectly gathered at the central controller. This is possible since the central controller can be embedded at a server in the core network for macrocells, e.g., radio network controller (RNC) which executes the task of resource management in universal mobile telecommunications system (UMTS).

Then, we show that \textbf{P1} is equivalent to a maximum weighted bipartite matching (MWBM) problem. To this end, we first briefly review some preliminaries of MWBM in graph theory \cite{West}.
%
%\begin{itemize}
   \emph{Bipartite graph:} A graph whose vertices are partitioned into two disjoint groups so that every edge connects a vertex in one group to one in another. If each edge is assigned a weight, the graph is the \emph{weighted bipartite graph}.
   \emph{Matching:} A set of mutually disjoint edges, i.e., any two edges do not share a common vertex. If every vertex in the graph is included in the matching, the matching is a \emph{perfect matching}.
   \emph{MWBM problem:} It is to find an optimal matching in a bipartite graph such that the sum weights of the matching is maximum.
%\end{itemize}

\begin{theorem}\label{thm:graph}
The problem \textbf{P1} is equivalent to a MWBM problem.
\end{theorem}

\begin{proof}
Let $\mathcal G\triangleq(\mathcal V_1\times \mathcal V_2,\mathcal E,\mathcal W)$ be the weighted bipartite graph, where $\mathcal V_1$ and $\mathcal V_2$ are the two disjoint groups of vertices; $\mathcal E$ is the set of edges; $\mathcal W$ is the weighting function such that $\mathcal W:\mathcal E\rightarrow \mathbb{R}_+$. As depicted in Fig. \ref{fig:CL2015-2583-graph2}, we first let the transmitters be the vertices and put them in $\mathcal V_1$, and the receivers and BSs be the vertices in $\mathcal V_2$. In addition, we duplicate the vertex corresponding to each BS $j$ with $b_j$ identical vertices in $\mathcal V_2$. To make the graph balanced, some virtual vertices (the dotted circles in Fig. \ref{fig:CL2015-2583-graph2}) are added in $\mathcal V_1$ so that $|\mathcal V_1|=|\mathcal V_2|=M+B$, where $|\cdot|$ denotes the cardinality of a set. Each transmitter in $\mathcal V_1$ connects all possible (duplicated) BSs and its dedicated receiver in $\mathcal V_2$ by edges. Moreover, for each receiver in $\mathcal V_2$, we establish edges to connect it with the virtual vertices.   For every edge connecting the virtual vertices, its weight is zero.
%Moreover, for the edges not connecting the dedicated transmitter-receiver pairs, the weights are assigned to be zero.
That it, only the edges connecting each transmitter $i$ to the BSs and its dedicated receiver $j\in\mathcal B^+$ are assigned positive weights which are defined as the utility $u_i(\gamma_{ij})$. If a transmitter connects the duplicated $b_j$ BSs, the weights are the same as the connection to BS $j$.
%Note that in an optimal matching, the case of a dedicated transmitter connecting another receiver does not happen. This is because if a dedicated transmitter connects another receiver (with zero weight), the sum weights can be increased if the dedicated transmitter connects its dedicated receiver (with positive weight), according to the defined weighting process.

Based on our graph construction method in above, we find the following equivalences: (i) The concept of a matching implies no violating the exclusive association constraints \eqref{eqn:x} and \eqref{eqn:binary}; (ii) The duplicated vertices in a matching satisfies the load balancing constraint \eqref{eqn:bj}; (iii) The weight of each edge is actually the utility of an association. Consequently, the problem in \textbf{P1} is exactly equivalent to the MWBM problem that is to find an optimal matching $\mathcal F^*\in\mathcal E$ so that the sum weights of $\mathcal F^*$ is maximum.
%
This completes the proof.
\end{proof}

%
\begin{figure}[t]
\begin{centering}
\includegraphics[scale=0.6]{CL2015-2583-graph2.eps}
\vspace{-0.1cm}
 \caption{An example of the bipartite graph with $M$ users and two BSs ($b_1=3$ and $b_2=2$). The weights of dash edges are zero.}\label{fig:CL2015-2583-graph2}
\end{centering}
\vspace{-0.3cm}
\end{figure}
%

After mapping \textbf{P1} to the MWBM problem, the well-known Hungary algorithm \cite{West} can solve the problem optimally with complexity of $\mathcal O((M+B)^{3})$, which is polynomial in the system parameters $M$ and $B$.

%Finally, we present the proposed solution for \textbf{P1} in Algorithm 1. In the algorithm, each BS and receiver $j$ should measure the SINRs $\gamma_{ij}$ by using pilot signals from every transmitter $i$, then send the SINRs to the central controller. Meanwhile, each user $i$ sends its utility $u_i$ and each BS $j$ reports the maximum supportable user number (or effective load) $b_j$ to the central controller. Collecting $u_i(\gamma_{ij})$ and $b_j$ for all $i$ and $j$, the central controller computes the optimal association $\mathbf x^*$ and broadcasts it to all users and BSs.

%From above analysis, it is observed that the central controller only needs to collect the values of all $u_i(\gamma_{ij})$ and $b_j$ but not complete network information. Moreover, $b_j$'s are always preset at the operator, and if the users have an identical utility function, e.g. (weighted, logarithmic, or average) achievable rate, then the signaling are only the SINRs $\gamma_{ij}$ which can be estimated by the BSs and receivers.

%%
%\begin{algorithm}[!t]
%\caption{Optimal Algorithm for \textbf{P1}}
%\begin{algorithmic}[1]
%%\STATE \textbf{initialize:} Fixed transmit power of every user.
%\STATE \textbf{Input:} Each user and BS measure SINR $\gamma_{ij}$ and then report the values $u_i(\gamma_{ij})$ and $b_j$ to the controller.
%\STATE \textbf{Output:} The controller solves the MWBM problem according to Theorem \ref{thm:graph} and then broadcasts the optimal link selection $\mathbf x^*$ to the users and BSs.
%\end{algorithmic}
%\end{algorithm}

%\begin{remark}
%The key of the proposed algorithm is mapping the original problem \textbf{P1} into a MWBM problem. After that, there exist many other approximate or heuristic algorithms solving the problem efficiently. We choose the Hopcroft-Karp algorithm because it has the lowest complexity to achieve global optimum (to the best of our knowledge). Performance comparison of different graph-based algorithms is beyond the scope of this paper.
%\end{remark}

So far the proposed graph-based approach solved \textbf{P1} globally optimally, but it needs a central controller for centralized processing.
%Moreover, the complexity will be high if the user number $M$ and sum loads of BSs $B$ go to large.
Nevertheless, the proposed centralized algorithm gives a performance upper bound and provides a simulation benchmark for the proposed distributed algorithms in next section.

\section{Distributed Algorithm}\label{sec:distributed}

%In this section, we propose two distributed algorithms, where network nodes only need local information for individual strategies.

%\subsection{Dual Based Algorithm}
In this section, we propose an efficiently suboptimal solution for \textbf{P1}, which works in a totally distributed manner. The idea is to solve the primal problem in dual domain via Lagrangian dual decomposition.

Let $\lambda_j$ denote the Lagrange multiplier corresponding to the load balancing constraint \eqref{eqn:bj} and $\boldsymbol\lambda\triangleq\{\lambda_j\}$. The Lagrangian function of of \textbf{P1} can be written as
%
\begin{equation}\label{eqn:La}
L(\mathbf x, \boldsymbol \lambda)=\sum_{i\in\mathcal U}\sum_{j\in\mathcal B^+}x_{ij}u_i(\gamma_{ij})+\sum_{j\in\mathcal B}\lambda_j\left(b_j-\sum_{i\in\mathcal U}x_{ij}\right).
\end{equation}
%
The dual function is then
%
\begin{eqnarray}\label{eqn:dual}
g(\boldsymbol\lambda)\triangleq\begin{cases}\max\limits_{\mathbf x}&L(\mathbf x, \boldsymbol\lambda)\\
{\rm s.t.} &\sum\limits_{j\in\mathcal B^+}x_{ij}\leq1,~~\forall i\in\mathcal U\\
&x_{ij}\in\{0,1\},~~\forall i\in\mathcal U,\forall j\in\mathcal B^+.
\end{cases}
\end{eqnarray}
%
The dual problem of \textbf{P1} is given by
%
%\begin{subequations}\label{eqn:ming}
%\begin{align}
%\min_{\boldsymbol\lambda}~&g(\boldsymbol\lambda) \\
%{\rm s.t.}~~ &\boldsymbol\lambda\succcurlyeq0.
%\end{align}
%\end{subequations}

\begin{eqnarray}\label{eqn:ming}
\begin{cases}  \min_{\boldsymbol\lambda}&g(\boldsymbol\lambda) \\
{\rm s.t.}~ &\boldsymbol\lambda\succcurlyeq0.
\end{cases}
\end{eqnarray}

Define $\lambda_0\equiv0$ for $j=0$ corresponding to D2D mode, maximizing $L(\mathbf x, \boldsymbol \lambda)$ is equivalent to maximizing the following objective:
%
\begin{equation}
\tilde{L}(\mathbf x, \boldsymbol \lambda)=\sum_{i\in\mathcal U}\sum_{j\in\mathcal B^+}x_{ij}u_i(\gamma_{ij})-\sum_{j\in\mathcal B^+}\lambda_j\sum_{i\in\mathcal U}x_{ij}.
\end{equation}
%
The above Lagrangian can be decomposed into $M$ sub-Lagrangian, and each sub-Lagrangian corresponds to one user and is expressed as
%
\begin{equation}\label{eqn:Li}
L_i(x_{ij})=\sum_{j\in\mathcal B^+}x_{ij}\left(u_i(\gamma_{ij})-\lambda_j\right).
\end{equation}
%
To maximize each sub-Lagrangian $L_i(x_{ij})$, the optimal $x_{ij}^*$ for each user $i$ can be determined by
%
\begin{eqnarray}\label{eqn:x-opt}
x_{ij}^*=\begin{cases}
  1,&{\rm if}~j=j^*=\arg\max\limits_{j\in\mathcal B^+} ~u_i(\gamma_{ij})-\lambda_j \\
  0,&{\rm otherwise}.
\end{cases}
\end{eqnarray}

The above analysis yields considerable insights as follows: The Lagrange multiplier $\lambda_j$, $j\in\mathcal B$, can be interpreted as the price announced by BS $j$ regarding on its loads. Then $u_i(\gamma_{ij})-\lambda_j$ can be treated as user $i$'s surplus, which is the difference between the utility by associating BS $j$ and its payment $\lambda_j$. If $j=0$ and $\lambda_0=0$, user $i$ operates on D2D mode and its surplus is just the utility (without payment), which coincides with the common sense of economics.

For the dual problem \eqref{eqn:ming}, the Lagrange multiplier $\lambda_j$ can be individually updated by each BS $j$ according to the following rule:
%
\begin{equation}\label{eqn:subgradient}
\lambda_j^{(t+1)}=\left[\lambda_j^{(t)}-\epsilon\left(b_j-\sum_{i\in\mathcal U}x_{ij}^{(t)}\right)\right]^+,~\forall j\in\mathcal B,
\end{equation}
where $[\cdot]^+\triangleq\max\{\cdot,0\}$ and $\epsilon$ is the properly designed step size. Since the dual problem in \eqref{eqn:dual} is always convex by definition, the subgradient method in \eqref{eqn:subgradient} is guaranteed to converge to the globally optimal solution to the dual problem \eqref{eqn:ming}.

%Finally, we present the distributed algorithm in Algorithm 2.
In the distributed algorithm, every BS and receiver measure the SINRs and send to the transmitters via a feedback channel before the iteration. In each iteration, each user $i$ determines its association according to \eqref{eqn:x-opt} based on local information $\gamma_{ij}$ and the broadcasted information $\lambda_j$ for all $j$; Each BS updates its multiplier according to \eqref{eqn:subgradient} which only needs the local information, and then announces the new multiplier to the users. Thus the proposed dual-based algorithm can be implemented in a totally distributed fashion.
%
Note that the distributed algorithm incurs less signaling overhead compared to the proposed centralized algorithm. Specifically, each user only needs to send a beacon signal to its most favorable BS (if cellular mode is selected) rather than all BSs; at the BS side, only the price is needed to broadcast.
%{\color{blue}In addition, the complexity of the distributed algorithm mainly depends on the step-size of the dual updating \eqref{eqn:subgradient}. If the diminishing step-size rule is selected, the complexity is $\mathcal O(B^2)$, which is much lower than that of the centralized algorithm $\mathcal O((M+B)^3)$.}


%The complexity of dual updating in \eqref{eqn:subgradient} is $\mathcal O(N^q)$ \cite{Boyd}, where $q$ is a constant. Combining the complexity in \eqref{eqn:x-opt}, the total complexity is $\mathcal O(M(N+1)N^q)$.
%Since $N\ll M$ and $N\ll B$, this significant reduces the complexity compared to Algorithm 1.

%
%\begin{algorithm}[!t]
%\caption{Dual Based Algorithm for \textbf{P1}}
%\begin{algorithmic}[1]
%\STATE \textbf{Initialize} $\boldsymbol\lambda$ as non-negative values.
%\REPEAT \STATE \emph{User Action:} Each user decides its connection via \eqref{eqn:x-opt};
%\STATE \emph{BS Action:} Each BS updates its price via \eqref{eqn:subgradient}.
% \UNTIL{$\boldsymbol\lambda$ converge.}
%\end{algorithmic}
%\end{algorithm}

%
%Note that there are several rules for choosing step size $\epsilon$, like constant step size, square-summable but not summable, and diminishing step size \cite{Boyd}. They have difference convergence speeds (case-dependent) but all guarantee to the global optimum. Dynamically choosing the step size $\epsilon$ in the dual updating process only influences the convergence speed but not the final results, and seems to be out of the scope of this paper.

We note that due to the nonconvexity of \textbf{P1}, the optimal solution obtained in dual domain may not be the same as the primal optimum. This means that the so-called ``duality gap" exists, i.e., the difference between the optimal value of the primal
problem and that of the dual problem is non-zero. However, the proposed dual-based algorithm yields a good solution to the primal problem \textbf{P1} in some sense.

%\subsection{Price Based Algorithm}
%
%In this subsection, we propose a price based algorithm, which decomposes the primal problem \textbf{P1} to $N$ BS-subproblems and $M$ user-subproblems. The user-subproblems are the same as \eqref{eqn:Li} and thus the optimal solution is \eqref{eqn:x-opt}. The key of the proposed algorithm here is the updating rule of prices $\lambda_j$'s which is different from the dual updating.
%
%We first explain our motivation of the proposed pricing algorithm: By observing the simulation of the subgradient-based dual updating of $\lambda_j$'s in \eqref{eqn:subgradient}, we find that a small variation of the dual variables $\lambda_j$'s may result in a quantum leap on the association $\mathbf x$. In this case, though the dual variables $\lambda_j$'s converge to an optimum, the corresponding association $\mathbf x$ in dual domain could be far from the primal optimum due to the non-zero duality gap.
%
%Then we introduce the proposed price based algorithm. The algorithm is iterative-based distributed process, that is, the BSs adjust their prices $\lambda_j$'s and the users subsequently choose the association in each iteration. Specifically, each BS $j$ checks the demand from the users. If the demand exceeds its supply, i.e., $\sum_{i\in\mathcal U}x_{ij}> b_j$, the BS raises its price $\lambda_j$ by a given step size and announces the new price to the users. Each user decides its association according to \eqref{eqn:x-opt} for given prices $\lambda_j$'s. Formally, we detail the method in Algorithm 3. Similar to Algorithm 2, the proposed Algorithm 3 is also totally distributed and we ignore the details here.
%
%
%%
%\begin{algorithm}[!t]
%\caption{Auction Based Algorithm for \textbf{P1}}
%\begin{algorithmic}[1]
%\STATE \textbf{Initialize} $\boldsymbol\lambda=\mathbf 0$.
%\REPEAT \STATE \emph{User Action:} Each user decides its connection via \eqref{eqn:x-opt};
%\STATE \emph{BS Action:} For each BS $j\in\mathcal B$
%\IF{$\sum_{i\in\mathcal U}x_{ij}> b_j$}
%\STATE $\lambda_j^{(t+1)} = \lambda_j^{(t)}+\delta$, where $\delta$ is a positive step size.
%\ELSE
%\STATE $\lambda_j^{(t+1)} = \lambda_j^{(t)}$.
%\ENDIF
% \UNTIL{$\boldsymbol\lambda$ converge.}
%\end{algorithmic}
%\end{algorithm}
%
%Note that the core of Algorithm 3 is that the step size $\delta$ is chosen to be small enough for all BSs such that at most one user changes its association in every iteration. In other words, if each BS $j$ is overloaded, i.e., $\sum_{i\in\mathcal U}x_{ij}> b_j$, the optimal pricing strategy is to keep the $b_j$ users with relatively higher utilities being served by the BS and the remaining users to change their decisions. This can be interpreted by a simple example: If the network has only one BS with supply $b_j=1$  and two users associating with the BS. In this case, the BS raises its price by $\delta$. The two users will be driven away if $\delta$ is large and the surplus of the BS is zero. Obviously, the solution to this case is not optimal. This also interprets our motivation aforementioned.
%
%Since the prices are non-decreasing, the convergence of Algorithm 3 is ensured.
%
%The auction based distributed algorithm requires the same signaling overhead as the dual based distributed algorithm. The details are given in above subsection and we omit here.



%\begin{remark}
%The goal of this section is to design distributed algorithms for solving the global optimization problem instead of game theoretical analysis. The ``price" in the two proposed algorithms is used to interpret the interaction information between the BSs and users. We do not consider the incentive issues and leave it as future work.
%\end{remark}

\section{Simulations}

%In this section, we evaluate the proposed algorithms using simulation.

We consider a two-dimensional plan of node locations, where the $N=4$ BSs are fixed at the coordinates $(0.25, 0.25)$, $(-0.25, 0.25)$, $(-0.25,-0.25)$, $(0.25,-0.25)$ of kilometer (km), and the $M=50$ users are uniformly distributed in the square with $1$ km of length of a side. The transmitter-receiver distance of each user is randomly distributed between $0$ and $0.2$ km. We set the path loss exponent for large-scale fading to be $4$ and the standard deviation of lognormal shadowing to be $5.8$ dB. The small-scale fading is modeled by Rayleigh fading process. A total of $2000$ different channel realizations with different locations and transmitter-receiver distances of users are used. Here we use the average throughput per user (total throughput divides the number of users) as the utility function for all users. Without loss of generality, we let the effective loads $b_j=b$ and the utility as the rate $u_i(\gamma_{ij})=R_i(\gamma_{ij})$ for all $i$ and $j$.
%Moreover, we adopt diminishing step size rule for the dual based Algorithm 2 and empirically set the step size to be $\delta=10^{-4}$ for the price based Algorithm 3.

%%
%\begin{figure}[t]
%\begin{centering}
%\includegraphics[scale=.65]{setup.eps}
%\vspace{-0.1cm}
% \caption{Two-dimensional plan of a random user locations where triangles and lines represents BSs and transmitter-receiver pairs, respectively. Here we set $r=200$ for example. }\label{fig:setup}
%\end{centering}
%\vspace{-0.3cm}
%\end{figure}
%%
%
%%
%\begin{figure}[t]
%\begin{centering}
%\makeatletter\def\@captype{figure}\makeatother
%\subfigure[$r=100$ m.]{\includegraphics[width=3in]{three100.eps}
%\label{fig:three100}}
%\subfigure[$r=200$ m.]{\includegraphics[width=3in]{three200.eps}
%\label{fig:three200}} \vspace{-0.1cm} \caption{Performance comparison of the three proposed algorithms, where $p_i=5$ dB for all $i$.} \label{fig:three}
%\end{centering}
%\vspace{-0.3cm}
%\end{figure}
%%

%
\begin{figure}[t]
\begin{centering}
\includegraphics[scale=.55]{CL2015-2583-three200.eps}
\vspace{-0.1cm}
 \caption{Performance comparison of the proposed algorithms, where $p_i=-5$ dB for all $i$.}\label{fig:CL2015-2583-three200}
\end{centering}
\vspace{-0.3cm}
\end{figure}
%

We first evaluate the proposed  algorithms in Fig. \ref{fig:CL2015-2583-three200}. First, it is observed that the duality gap of the distributed algorithm really exists. However, the effect of the duality gap is negligible since the performance loss is less than $0.1\%$ compared with the globally optimal algorithm, which demonstrates the effectiveness of the distributed algorithm. Moreover, as expected, the throughput performance is increasing with the effective loads $b$ since more users can associate with the BSs.
%Finally, we observe that shorter transmitter-receiver distance (i.e., smaller $r$) leads to higher throughput since path loss dominates users' performance.

%
\begin{figure}[t]
\begin{centering}
\includegraphics[scale=.55]{CL2015-2583-rate_dB.eps}
\vspace{-0.1cm}
 \caption{Performance comparison of different algorithms with $b=10$.}\label{fig:CL2015-2583-rate_dB}
\end{centering}
\vspace{-0.3cm}
\end{figure}
%

Then we evaluate different algorithms in Fig. \ref{fig:CL2015-2583-rate_dB} where we set the effective loads of BSs as $b=10$. Here the traditional cellular communication without D2D mode is considered as the benchmark, which can be regarded as a special case of the proposed algorithms. We observe that average throughput is increasing with transmit power, but the performance will be bounded at the high transmit power due to the mutual interference. We also find that D2D mode dominates the performance in uplink transmission since the transmitter-receiver distances of users are usually very small and they prefer D2D mode compared to associating with BSs.
%Moreover, it is observed that the effect of cellular mode is increasing with $r$. That is, larger transmitter-receiver distance of a user means that the user is more likely to prefer associating with BSs.

%%
%\begin{figure}[t]
%\begin{centering}
%\includegraphics[scale=.65]{dual_variables.eps}
%\vspace{-0.1cm}
% \caption{Convergence performance of Algorithm 2 with $b=5$, $p_i=5$ dB and $r=100$ m. Each line represents one BS.}\label{fig:dual_variables}
%\end{centering}
%\vspace{-0.3cm}
%\end{figure}
%%

%For a given channel realization, we investigate the convergence performance of the proposed Algorithm 2 in Fig. \ref{fig:dual_variables}, where each line represents one BS's dual variable and we set $b=5$, $p_i=5$ dB and $r=100$ m. It observes that the algorithm converges with about $70$ iterations in this example.

%We also investigate the convergence performance of the proposed Algorithm 3 in Fig. \ref{fig:price} for a given channel realization, where each line represents one BS's price and we set $b=5$, $p_i=5$ dB and $r=100$ m. We find that the BSs' prices are convergent with about $60$ iterations in this example. It is also observed that the prices are updated with a non-decreasing manner.

%%
%\begin{figure}[t]
%\begin{centering}
%\includegraphics[scale=.65]{price.eps}
%\vspace{-0.1cm}
% \caption{Convergence performance of Algorithm 3 with $b=5$, $p_i=5$ dB and $r=100$ m. Each line represents one BS.}\label{fig:price}
%\end{centering}
%\vspace{-0.3cm}
%\end{figure}
%%

\section{Conclusion}

In this paper, we studied the optimal mode selection for D2D communications underlaying uplink cellular network with multiple BSs. To ensure fair and balanced utilization of resources, we imposed load balancing constraints in the BSs. We formulated the joint optimization problem of mode selection and user association as a combinatorial problem and NP-complete. We first solved this problem globally optimally in a centralized manner by using a graph based approach. To reduce complexity and signaling overhead, we further proposed a distributed algorithm which performs almost the same performance compared with the globally optimal one. Simulation results verified the proposed algorithms.

In this paper we consider the uplink case. It is also important and interesting to consider the problem in downlink case, which however needs to involve another dimensional resource allocation (like antennas, frequencies and/or slots). This will greatly complicate the problem and we would like to consider it for our future work.

\bibliographystyle{IEEEtran}
\bibliography{IEEEabrv,CL2015-2583-mode}
\end{document}

CL2015-2583.bbl
% Generated by IEEEtran.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{10}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{Zulhasnine2010}
M.~Zulhasnine, C.~Huang, and A.~Srinivasan, ``Efficient resource allocation for
  device-to-device communication underlaying lte network,'' in \emph{Proc. IEEE
  WiMob}, 2010, pp. 368--375.

\bibitem{Yu2011}
C.~Yu, K.~Doppler, C.~B. Ribeiro, and O.~Tirkkonen, ``Resource sharing
  optimization for device-to-device communication underlaying cellular
  networks,'' \emph{{IEEE} Trans. Wireless Commun.}, vol.~10, no.~8, pp.
  2752--2763, 2011.

\bibitem{Min2011}
H.~Min, J.~Lee, S.~Park, and D.~Hong, ``Capacity enhancement using an
  interference limited area for device-to-device uplink underlaying cellular
  networks,'' \emph{{IEEE} Trans. Wireless Commun.}, vol.~10, no.~12, pp.
  3995--4000, 2011.

\bibitem{Xu2013}
C.~Xu, L.~Song, Z.~Han, Q.~Zhao, X.~Wang, and B.~Jiao, ``Efficiency resource
  allocation for device-to-device underlay communication systems: A reverse
  iterative combinatorial auction based approach,'' \emph{{IEEE} J. Sel. Areas
  Commun.}, vol.~31, no.~9, pp. 348--358, 2013.

\bibitem{Feng2013}
D.~Feng, L.~Lu, Y.~W. Yi, G.~Li, G.~Feng, and S.~Li, ``Device-to-device
  communications underlaying cellular networks,'' \emph{{IEEE} Trans. Commun.},
  vol.~61, no.~8, pp. 3541--3551, Aug. 2013.

\bibitem{YuanICC2014}
Y.~Liu and S.~Feng, ``Interference pricing for device-to-device
  communications,'' in \emph{Proc. IEEE ICC}, 2014.

\bibitem{DopplerWCNC2010}
K.~Doppler, C.-H. Yu, C.~B. Ribeiro, and P.~J��anis, ``Mode selection for
  device-to-device communication underlaying an {LTE-Advanced} network,'' in
  \emph{Proc. IEEE WCNC}, 2010.

\bibitem{XiangGCW2012}
S.~Xiang, T.~Peng, Z.~Liu, and W.~Wang, ``{A distance-dependent mode selection
  algorithm in heterogeneous D2D and IMT-advanced network},'' in \emph{IEEE
  Globecom Workshops}, 2012.

\bibitem{Han2012}
M.~H. Han, B.~G. Kim, and J.~W. Lee, ``Subchannel and transmission mode
  scheduling for {D2D} communication in {OFDMA} networks,'' in \emph{Proc. IEEE
  VTC}, 2012.

\bibitem{Jung2012}
M.~Jung, K.~Hwang, and S.~Choi, ``Joint mode selection and power allocation
  scheme for power-efficient device-to-device {(D2D)} communication,'' in
  \emph{Proc. IEEE VTC}, 2012.

\bibitem{Chien2012}
C.~Chien, Y.~Chen, and H.~Hsieh, ``Exploiting spatial reuse gain through joint
  mode selection and resource allocation for underlay device-to-device
  communications,'' in \emph{Proc. IEEE WPMC}, 2012.

\bibitem{Guanding2014}
G.~Yu, L.~Xu, D.~Feng, R.~Yin, G.~Y. Li, and Y.~Jiang, ``Joint mode selection
  and resource allocation for device-to-device communications,'' \emph{{IEEE}
  Trans. Commun.}, vol.~62, no.~11, pp. 3814--3824, 2014.

\bibitem{Chenfei2014}
C.~Gao, X.~Sheng, J.~Tang, W.~Zhang, S.~Zou, and M.~Guizani, ``Joint mode
  selection, channel allocation and power assignment for green device-to-device
  communications,'' in \emph{Proc. IEEE ICC}, 2014.

\bibitem{West}
D.~West, \emph{Introduction to Graph Theory}.\hskip 1em plus 0.5em minus
  0.4em\relax Prentice Hall, 2001.

\end{thebibliography}
