is an MINLP problem, which is NP-hard in general. In Section \[sec:alg\], we first reformulate the problem to a obtain a simpler form, and then develop effective algorithms for optimal and suboptimal solutions.

Reformulation and Power Allocation \[sec:alg\]
----------------------------------------------

In this section, we reformulate Problem OPT-Power to obtain a simpler form, and derive an upper bound and a lower bound for the total BS power. The reformulation also leads to a simple heuristic algorithm. Finally, we introduce power allocation algorithms for three connection scenarios.

### Problem Reformulation

Due to the monotonic logarithm functions and the binary indicators $I_m^k$, constraint (\[eq:cntrate\]) can be rewritten as: $$\label{eq:StSNR}
  \gamma_m^k I_m^k \ge \Gamma_m^k I_m^k, \;\; m=0, 1, \cdots,M,$$ where $\Gamma_m^k = \Gamma_m =: 2^{R_{tar}/B_m} - 1$ is the minimum SNR requirement at user $k$ that connects to BS $m$. To further simplify the problem, define $Q_l^m = \sum_{i=l}^L P_i^m$, with $Q_{L+1}^m=0$. Then power $P_l^m$ is the difference $$\begin{aligned}
\label{eq:QrepP}
  P_l^m=Q_l^m-Q_{l+1}^m.\end{aligned}$$ Problem OPT-Power can be reformulated as: $$\begin{aligned}
\mbox{minimize} && \hspace{-0.2in} \sum_{m=0}^M Q_1^m \label{eq:ObjFun2} \\
%\mbox{subject to:} && \hspace{-0.2in} \frac{H_m^k(Q_l^m-Q_{l+1}^m)}{N_0+H_m^kQ_{l+1}^m}I_m^k\ge \Gamma_m I_m^k, \nonumber \\
\mbox{subject to:} && \hspace{-0.2in} H_m^k(Q_l^m \hspace{-0.025in} - \hspace{-0.025in} Q_{l+1}^m) / \hspace{-0.025in} \left( N_0 \hspace{-0.025in} + \hspace{-0.025in} H_m^k Q_{l+1}^m \right) I_m^k \ge 