Distributed Downlink Power Control by Message-Passing for Very Large-Scale Networks

Abstract

Downlink power control is revisited by assuming very large-scale networks. In very large-scale networks, conventional centralized power control schemes quickly become impractical owing to the huge computational burden and limited backhaul capacity. Alternative distributed power control schemes have been proposed; however, these schemes suffer from poor performance when compared with the centralized power control. In this work, a completely new approach to distributed downlink power control is proposed using a belief-propagation (BP) framework. The proposed BP approach includes two tasks: first, the sum rate maximizing power control problem is modeled as a factor graph representation. Second, a message-passing algorithm is constructed on the basis of the factor graph, which efficiently computes a near-optimal solution in a distributed manner. The practical issues for implementing the proposed BP approach are extensively discussed in terms of the computational complexity, signaling overhead, convergence, and latency. Surprisingly, the simulation results verify that the average sum rate performance of the proposed BP-based power control is nearly equivalent to that of centralized power control schemes. The proposed BP-based power control even outperforms the centralized binary on/off power control and approaches the performance of geometric programming power control, which is the best-known centralized power control, within only 0.8% of the average sum rate.

1. Introduction

Transmit power control has been one of the classic research topics attracting continuous attention throughout the rapid evolution of modern wireless cellular systems. Early works on power control have studied various centralized or distributed power control schemes for voice-centric wireless cellular systems [1, 2]. Power control has mainly focused on supporting quality of service (QoS) of each served user, for example, guaranteeing minimum signal-to-interference-plus-noise (SINR) ratio. As the interests of wireless services have recently shifted from voice services to data services, the main goal of power control has also gradually focused on maximizing the data rate to efficiently deliver various data-centric services for serviced users with the aid of adaptive modulation and coding techniques [3, 4]. Thus, maximizing the sum rate of the users has become a key objective for wireless service providers because it is directly related to the their revenues.

Unfortunately, the power control problem that targets sum rate maximization and determination of the optimal power values has led to relatively few theoretical achievements, considering the steady and widely received attention to the topic. The principle reason lies in the mathematical difficulties of the problem. The nonconvex form of the objective function renders the optimization problem mathematically intractable. As an initial approach, power control for a simple two-cell case, that is, $N=\mathrm{2}$ , has been analyzed in [5–7], where N denotes the total number of cells in the network. A useful and interesting result found in [6, 7] is that the binary choice of completely turning each cell on or off maximizes the sum rate of the two-cell network, which is referred to as binary on/off power control. Motivated by this result, the binary on/off power control is generalized to a general $N>\mathrm{2}$ case. Although its optimality for the general N case is proven only with a low-SINR assumption, the simulation results have empirically shown that the sum rate performance is very close to that of the optimal case, even for medium- and high-SINR cases [4, 8]. Other approaches in [9, 10] approximate the objective function to a simplified form assuming a higher SINR. Various modifications of the objective functions and the corresponding iterative algorithms to search for an optimal solution have been provided; however, global optimality is not guaranteed.

Recently, a powerful mathematical technique called geometric programming (GP) has been proposed for power control problems, as discussed in [11]. It has been revealed in [11] that the original nonconvex optimization problem of power control falls into a class of GP problems under a high-SINR assumption. Despite the apparent nonconvexity of the objective function, a logarithmic change renders the original problem into a standard form of a convex optimization problem. Then, this can be efficiently solved with well-known convex optimization techniques. More meaningful results should be found for low- and medium-SINR cases, which represent most of the real-world wireless communication environments. Thus, [11] also provides a brute-force method, which attempts to tackle the original objective function directly. The proposed successive convex approximation method that performs iterative GPs solves the optimization problem without any assumptions of the SINR. With the computational burden that increases with the precision of the solutions and problem size, it has been observed that the global optimum values are found empirically in most cases.

However, most of the aforementioned works require centralized control, which includes a broadband backhaul for sharing the channel state information (CSI) and a high-speed computing core for processing the related information. A fundamental shift from the voice-centric networks to data-centric networks accelerates the cell population and cell-size reduction surprisingly fast beyond the extent of our conjecture. As an early peek at the Beyond-4G (B4G) networks, the 3GPP long-term evolution (3GPP-LTE) network in the extremely hot spots such as Gang-Nam area, Seoul, Korea, has been deployed with an extremely high density: a very large number of small cells are populated with a radius of at most 200~300 m. Thus, the centralized power control methods quickly become impractical in this type of very large-scale networks (i.e., very large N), considering the huge computational burden and limited backhaul capacity. This motivates the strong needs for distributed power control as a self-organizing nature for the upcoming B4G networks. In [4, 12], a simple distributed power control algorithm has been developed in the frame of the binary on/off power control. The key step in the distributed binary on/off power control algorithm is to predict the total intercell interference power by simply averaging the potential interference over a large number of interfering sources. The proposed distributed algorithm is very easy to implement in practical systems. However, the simulation results exhibit a notable performance gap compared with centralized power control [12] because the dynamic interactions between neighboring cells are largely averaged out and thus ignored at the cost of the simplicity of the algorithm.

Meanwhile, recent research interests in this field have been extensively diversified. In [13–17], power control issues for interference mitigation and sum rate maximization have been studied in the context of cognitive radio systems. More complicated forms of cellular networks have been considered: heterogeneous networks [18], relay-assisted multihop networks [19, 20], or both [21]. Admission or congestion control is jointly considered with power control in [22, 23]. Some practical issues such as battery storage constraints of battery-powered base stations [24] and imperfect channel knowledge at transmitters [25, 26] have been studied. In addition, power control for specific traffic types, for example, video streaming, has been investigated in [27, 28]. In spite of the extensive applications of power control, there has been no breakthrough progress in mathematical techniques recently; existing mathematical techniques mostly based on geometric programming have been reused or marginally improved.

As a completely new approach to the distributed optimization problem of power control, this paper introduces a new mathematical tool rigorously developed in the field of statistical physics. The cavity method has been proven to be a very useful mathematical tool to explain the macroscopic behaviors of very large-scale particle systems that consist of a large number of dynamically interacting particles, for example, the magnetization of ferromagnets and the phase shifts in water [29, 30]. Motivated by the structural analogies between high density B4G wireless cellular networks and very large-scale particle systems, factor graph models and message-passing algorithms from the cavity method are introduced to enable probabilistic descriptions of the distributed optimization problem and provide very useful approximate solutions. Some early works have confirmed that this effort leads to very successful achievements in the field of wireless communications [31–34]. More general overviews of the graphical models and message-passing algorithms can be found in [35–37].

The key contributions of this work are summarized as follows.

• (i)

Graphical model representation: a typical power control problem of wireless cellular networks is newly modeled as a factor graph representation, where the dynamically interacting nature of the neighboring cells is well captured. The resulting factor graph breaks down into a large number of subgraphs of local optimization problems, which enables distributed optimization.

(ii)

Distributed message-passing algorithm: a distributed power control algorithm is built on the locally tree-like factor graph as a class of sum-product algorithms, also known as belief-propagation (BP). The proposed BP-based power control algorithm efficiently computes good estimates of the marginal probability in a distributed manner from the complex joint probability distribution of the global optimization problem.

(iii)

Near-optimal performance: the beauty of the BP-based power control originates in the near-optimal performance, despite its distributed nature. The simulation results verify that the performance of the proposed BP-based power control is almost the same as that of the centralized power control by GP in [11], which is the best-known power control to the best of the author's knowledge. Surprisingly, the proposed BP-based power control even outperforms the centralized version of binary on/off power control in [4, 8].

(iv)

Practical implementations: for implementing the BP-based power control in real-world wireless communication systems, important practical issues have been extensively studied. This study includes the computational complexity of the message-passing algorithm, required signaling overhead in the backhaul, and convergence time. The detailed investigation has revealed that (i) the computational complexity at each cell does not increase with the network size, (ii) the required information sharing is minimized by passing messages only between pairs of neighboring cells and only in the form of beliefs, and (iii) the convergence time is very fast, requiring only a few iterations of message-passings. This emphasizes the usefulness of the proposed BP-based power control for practical implementations.

The remainder of this paper is organized as follows. Section 2 describes the wireless cellular system model. Conventional power control schemes are briefly reviewed in Section 3. In Section 4, a factor graph representation and the corresponding message-passing algorithm are proposed. Detailed discussions of practical implementation issues follow in Section 5. Various simulation results are provided in Section 6. Finally, Section 7 summarizes the conclusions.

Notations. $\mathbb{I}\left(·\right)$ denotes an indication function that becomes 1 when the statement is true and becomes 0 otherwise. A big-O operator $O\left(·\right)$ is used to denote a limiting behavior of a system complexity with respect to related parameters.

2. System Model

As shown in Figure 1, a downlink wireless cellular network, consisting of N synchronized cells, is considered. The transmit points (TPs) or base stations are located at the center of cells while the user equipment (UE) or mobile stations are randomly located within the cells. In each cell, single active UE is served at a time by the associated TP with the transmit power of the nth TP denoted by $P_n$ . A spectral reuse of one is considered. While receiving the desired signal from the serving TP, UE experiences interference from the transmit signal of the TPs in the neighboring cells. The SINR at the UE in the nth cell is written as

$$\begin{array}{cc}& \text{SIN}{\text{R}}_n=\frac{G_{n,n}{P}_n}{{\sum }_{m\in \Phi \left(n\right)}^{}{G}_{n,m}{P}_m+Z_n},\end{array}$$

(1)

where $G_{n,m}$ denotes the channel power gain from the TP in the mth cell to the UE in the nth cell, $\Phi \left(n\right)$ denotes the set of neighboring cell indices around the nth cell by assuming that only the neighboring cells in the first-tier are counted as dominant interfering sources, and $Z_n$ denotes the noise power at the nth UE. The channel power gain $G_{n,m}$ is modeled to be inversely proportional to the distance between the TP and the UE $d_{n,m}^{\alpha }$ , where α represents a path loss exponent according to different propagation environments. The channel power gain is accurately measured and fed back to the serving TP in terms of the long-term channel statistics, for example, the reference-signal-received-power (RSRP) (in commercial 3GPP LTE systems, a RSRP is defined as a linear average of reference signal power measured at UE [38]. A RSRP is critical physical layer information to support various radio resource managements. Thus, accuracy requirements for a RSRP are very tight for user devices. A RSRP is measured and averaged typically over hundreds of msec, and its reporting range is defined from −140 dBm to −44 dBm with 1 dB resolution [39]) feedback in 3GPP-LTE systems.

Figure 1

Wireless cellular network model.

Any information between the cells can be transferred through the backhaul, which is typically implemented with optical fibers in commercial networks. By considering the finite bandwidth and nonzero latency of the backhaul, only the neighboring cells are assumed to transfer and receive messages forming a semidistributed network framework.

By denoting the power allocation vector by $\mathbf{P}=\left\{P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_N\right\}$ , the sum rate is then computed as

$$\begin{array}{cc}& R\left(\mathbf{P}\right)={\displaystyle \sum }_{n=\mathrm{1}}^N‍\log \left(\mathrm{1}+\frac{G_{n,n}{P}_n}{{\sum }_{m\in \Phi \left(n\right)}{G}_{n,m}{P}_m+Z_n}\right).\end{array}$$

(2)

An individual power constraint is considered, which limits the maximum power of each TP to $P_{\text{MAX}}$ . The optimum power control problem that needs to be solved is simply formulated as

$$\begin{array}{l}\text{maximize}\hspace{1em}R\left(\mathbf{P}\right)\\ \text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\hspace{1em}\mathrm{0}\le P_n\le P_{\text{MAX}},\hspace{1em}\forall n,\end{array}$$

(3)

which is computationally very difficult. Most of the previous approaches have attempted to soften the problem by simplifying the objective function with either high-SINR ( $\text{SINR}\gg \mathrm{1}$ ) or low-SINR ( $\text{SINR}\ll \mathrm{1}$ ) assumptions. Note that this paper directly tackles the objective function in its purely nonconvex form.

A finite resolution of power levels is considered here. With the total number of power levels L, ${\mathbf{\Omega }}_L=\left\{\mathbf{P}\hspace{0.17em}|\hspace{0.17em}{P}_n\in \left\{{\rho }_{\mathrm{1}},{\rho }_{\mathrm{2}},\dots ,{\rho }_L\right\},n=\mathrm{1,2},\dots ,N\right\}$ denotes an entire set of the possible combinations of power allocations, where ${\rho }_l$ ( $l=\mathrm{1,2},\dots ,L$ ) are discrete power levels.

3. Conventional Power Control for Wireless Cellular Systems

In this section, two categories of conventional power control techniques are introduced and reviewed in detail.

3.1. Binary On/Off Power Control

The simplest but very efficient power control method suggested in [6, 7] is to enforce a binary choice between transmitting full power and completely turning off for each cell, that is, ${\rho }_{\mathrm{1}}=\mathrm{0}$ and ${\rho }_{\mathrm{2}}=P_{\text{MAX}}$ , which is referred to as binary on/off power control. Then, the optimal power allocation in the network ${\mathbf{P}}^{\star }=\left\{P_{\mathrm{1}}^{\star },P_{\mathrm{2}}^{\star },\dots ,P_N^{\star }\right\}$ can be found by brute-force combinatorial optimization as

$$\begin{array}{cc}& {\mathbf{P}}^{\star }=\underset{\mathbf{P}\in {\mathbf{\Omega }}_{\mathrm{2}}}{\arg \hspace{0.17em}\max }R\left(\mathbf{P}\right).\end{array}$$

(4)

The optimality of the binary on/off power control has been exactly proven for the two-cell case ( $N=\mathrm{2}$ ) or in the low-SINR case for a larger number of cells ( $N>\mathrm{2}$ ). Interestingly, the simulation results have shown that very good sum rate performance can be achieved with this simple strategy [4, 8].

The main difficulty in implementing the binary on/off power control is that it requires centralized control. All CSI should be shared through the limited backhaul, and the centralized scheduler is required to perform combinatorial optimization. Specifically, the computational complexity of the related combinatorial optimization grows exponentially with the size of the network as $O\left({\mathrm{2}}^N\right)$ , which renders the practical implementation nearly impossible in very large-scale networks ( $N\gg \mathrm{1}$ ).

In response to the above practical issues, the distributed version of the binary on/off power control has been developed in parallel [4, 12]. Even in very large-scale networks, the distributed binary on/off power control can be performed without information sharing through the backhaul and the centralized scheduler. The nth cell autonomously determines whether it remains at on state or switches to off state according to the following simple criterion:

$$\begin{array}{cc}& \frac{G_{n,n}}{{\sum }_{m\ne n,m\in \mathcal{N}}{G}_{n,m}}>e,\end{array}$$

(5)

where $\mathcal{N}$ denotes the set of active cells and e denotes Euler's number. The cell remains at on state if the condition is satisfied, and it switches to off if opposite is true. At the cost of averaging out the dynamic effects of the interference statistics, the simplified criterion toward an improvement in the network performance can be drawn. Further details regarding this derivation can be found in [12]. Owing to its flipping nature without guaranteed convergence, the distributed binary on/off power control needs to be used with a carefully designed user scheduler in line with the QoS policies.

3.2. Power Control by Geometric Programming

The recent development of GP provides a very powerful mathematical framework for power control problems [11]. In high-SINR cases ( $\text{SINR}\gg \mathrm{1}$ ), the objective function in (2) reduces to $R\left(\mathbf{P}\right)=\log {\prod }_{n=\mathrm{1}}^N\text{SIN}{\text{R}}_n$ , which in turn becomes GP in the standard form. Further, well-known numerical techniques such as the interior-point method can efficiently solve the optimization problem (here, CVX, a package for specifying and solving convex programs, is used [40, 41] in the simulations). However, the objective function remains purely nonconvex for general SINR cases, which does not directly lead to a GP. The successive convex approximation proposed in [11] mitigates the issue by iteratively approximating the nonconvex function into a convex form without losing the optimality. Then, the original optimization problem is now decomposed into a series of GPs, and the optimal solution can be searched with the GP tools. More details of the algorithm can be found in [11]. Through extensive numerical experiments, the GP-based power control has empirically shown that it computes the globally optimal power allocation in most cases. Only a few choices of initial states make the algorithm result in a local optimum. The GP-based power control shows the best sum rate performance in the literature to the best of the author's knowledge.

Despite the attractive performance of the GP-based power control, some practical issues should be considered when it comes to very large-scale networks. A centralized control in very large-scale networks requires a huge signaling overhead through the limited backhaul. Moreover, the overall computational complexity of the best-known algorithm for the interior-point methods scales as $O\left((N^{\mathrm{3}}/\ln N)\ell \right)$ , where ℓ denotes the total bit length of the input data [42]. This polynomial-time complexity should be a great relief when compared with the exponentially increasing computational complexity of the binary on/off power control. However, both of them still remain beyond practical implementations, considering very large-scale networks ( $N\gg \mathrm{1}$ ).

4. Proposed Belief-Propagation Approach to Power Control

This section describes a BP approach to the power control problem. The BP approach includes a factor graph representation of the problem and message-passing algorithm constructed on the factor graph. When compared with the aforementioned power control schemes, the proposed BP-based power control inherits the distributed nature from the message-passing algorithm, which is the beauty of this approach.

4.1. Problem Formulation and Factor Graph Representation

A factor graph is a graphical tool to visually describe the conditionally dependent structure of random variables [35]. Thus, a factor graph representation is very useful, particularly in handling and analyzing very large-scale systems where a very large number of members are interacting with each other. A factor graph is basically a bipartite graph, which is constructed with two classes of nodes and connecting edges. One class of nodes denotes random variables that are referred to as variable nodes. The other class of nodes denotes functions of the related random variables that are referred to as function nodes. Edges connect two nodes from different classes. In principle, the variable nodes represent the specific states of the system, whereas the corresponding function nodes connected through the edges represent the resulting interactions in the system. With regard to the power control problem, which is the main interest of this work, the variable nodes specify power allocation in each cell. The function nodes compute the resulting contributions to the system performance, that is, the sum rate, that reflects the intercell interference between the neighboring cells.

Here are brief explanations of the proposed BP approach. The key concept of the proposed BP approach is to focus on the structural analogies between B4G wireless cellular networks and very large-scale particle systems. An objective function of the wireless optimization problem is embedded into the energy function of the statistical physics problem. The optimal solution that minimizes the energy of the system is searched by using a message-passing framework. Note that the solution also can be interpreted as a dual solution for the original optimization problem, providing the best power allocation for B4G wireless cellular networks. Detailed procedures of the proposed BP approach are as follows.

First, an energy function for the power allocation configuration P is defined as

$$\begin{array}{cc}& E\left(\mathbf{P}\right)\triangleq -{\displaystyle \sum }_{n=\mathrm{1}}^N‍\log \left(\mathrm{1}+\frac{G_{n,n}{P}_n}{{\sum }_{m\in \Phi \left(n\right)}{G}_{n,m}{P}_m+Z_n}\right),\end{array}$$

(6)

where $E\left(\mathbf{P}\right)$ is defined as the objective function of the power control problem in (2) with a minus sign to be in line with the conventions of the algorithm. The rationale behind this is that, typically in physics, we are interested in minimizing the energy of the system. This helps an intuitive understanding of the algorithm. By introducing a Boltzmann-type probability measure from statistical physics, the joint probability distribution has the form

$$\begin{array}{cc}& \mu \left(\mathbf{P}\right)=\frac{\mathrm{1}}{C}{e}^{-\beta E\left(\mathbf{P}\right)},\hspace{1em}C={\displaystyle \sum }_{\mathbf{P}}‍e^{-\beta E\left(\mathbf{P}\right)},\end{array}$$

(7)

where β is a positive constant and C is a normalization constant. The physical interpretation of the joint probability distribution is in the following. Depending on the power allocation configuration P, the system has different energies with exponentially decaying joint probability distribution, meaning that the system more likely stays in the power allocation configuration with a lower energy state. The optimal configuration ${\mathbf{P}}^{\star }$ minimizes the energy function and maximizes the joint probability distribution at the same time. This configuration is more probable than any other nonoptimal power allocation configurations and corresponds to the ground-state energy. On the other hand, β describes the softening of the joint probability distribution. In statistical physics jargon, β implies the inverse temperature of the very large-scale system that consists of a large number of particles. Large β increases the decaying speed of the joint probability distribution with respect to the energy, mostly rejecting nonoptimal power allocation configurations. In the limit of $\beta \to \infty$ (zero-temperature), $\mu \left(\mathbf{P}\right)$ is concentrated only on the optimal values for P to minimize the energy, that is, the ground-state energy of the system. By considering the numerical issues, a finite β is used for implementing the algorithm. As will be shown in Section 6, the choice of finite β still guarantees the performance of the message-passing algorithm. The joint probability distribution in (7) can be factorized as

$$\begin{array}{cc}& \mu \left(\mathbf{P}\right)=\frac{\mathrm{1}}{C}{\displaystyle \prod }_{n=\mathrm{1}}^N‍e^{\beta \log \left(\mathrm{1}+G_{n,n}{P}_n/\left({\sum }_{m\in \Phi \left(n\right)}{G}_{n,m}{P}_m+Z_n\right)\right)}.\end{array}$$

(8)

Note that the joint probability distribution is decomposed into the product of multiple local joint probability distributions.

Figure 2 illustrates the corresponding factor graph representation of the joint probability distribution in (8). Circles, squares, and solid lines, respectively, indicate the variable nodes, function nodes, and edges. The factor graph is overlaid upon the cellular structure to visualize the physical interactions between the neighboring cells. Each cell has one variable node, which corresponds to the choice of its transmit power, and one function node, which corresponds to the local probability distribution imposing the interactions between itself and its neighboring cells. For ease of understanding, m and n are used to denote the variable nodes, and a and b are used to denote the function nodes in the rest of this paper. Using the framework of factor graph representations, the joint probability distribution can be expressed as

$$\begin{array}{cc}& \mu \left(\mathbf{P}\right)=\frac{\mathrm{1}}{C}{\displaystyle \prod }_{a=\mathrm{1}}^N‍{\psi }_a\left({\mathbf{P}}_{\partial a}\right),\end{array}$$

(9)

with

$$\begin{array}{cc}& {\psi }_a\left({\mathbf{P}}_{\partial a}\right)\triangleq \exp \left(-\beta E_a\left({\mathbf{P}}_{\partial a}\right)\right),\end{array}$$

(10)

$$\begin{array}{cc}& E_a\left({\mathbf{P}}_{\partial a}\right)\triangleq -\log \left(\mathrm{1}+\frac{G_{m^{\prime }\left(a\right),m^{\prime }\left(a\right)}{P}_{m^{\prime }\left(a\right)}}{{\sum }_{m\in \partial a\mathrm{\setminus }{m}^{\prime }\left(a\right)}{G}_{m^{\prime }\left(a\right),m}{P}_m+Z_{m^{\prime }\left(a\right)}}\right),\end{array}$$

(11)

where $\partial a$ denotes the set of the neighboring variable nodes associated with the specific function node a, $m^{\prime }\left(a\right)$ denotes one neighboring variable node in $\partial a$ that resides in the same cell with a, $\mathrm{\setminus }m$ denotes the set excluding m, and ${\mathbf{P}}_{\partial a}$ denotes the local power allocation vector involved with the function node a. In the factor graphs, the degree of a node is defined as the number of connected edges at the node. Note that the degree of nodes in the factor graph in Figure 2 is seven. The degree of nodes is closely related to the computational complexity of the message-passing algorithm, which will be explained in the next section.

Figure 2

Factor graph for downlink power control problem.

4.2. Distributed Power Control Algorithm

A message-passing algorithm for distributed power control is developed on the basis of the constructed factor graph. Specifically, a sum-product type algorithm is considered because it can be intuitively interpreted with probabilistic language. The sum-product algorithm efficiently computes the marginal probability of each variable in the system by iteratively passing the messages along the connected nodes of the factor graph. In probabilistic language, a message can be interpreted as a believed marginal probability observed from a neighboring node. The marginalization of the complex multivariate system can be simply replaced with delivering beliefs between associated node pairs. Further, the algorithm easily infers the optimal value of each variable in a distributed manner. This explains the reason for sometimes calling the sum-product algorithm belief-propagation. See [35–37, 43] for more details on sum-product algorithms. Here, the definitions and mathematical notations follow the conventions of a message-passing framework.

Message-passings are iteratively performed between function nodes and variable nodes. At function node a, a message is updated according to the predefined rule, and the computed message is passed to the neighboring variable nodes $n\in \partial a$ , where $\partial a$ denotes the set of all the variable nodes connected to a. Similarly, at variable node n, a message is updated and passed to the neighboring function nodes $a\in \partial n$ , where $\partial n$ denotes the set of all the function nodes connected to n. For a probabilistic implication, a variable message ${\nu }_{n\to a}\left(P_n\right)$ conveys the information on how much the variable node n believes that the power value $P_n$ is the optimal value for itself, while a function message ${\widehat{\nu }}_{a\to n}\left(P_n\right)$ conveys the information on how much the function node a believes that the power value $P_n$ is the optimal value for the variable n. All the messages are L-tuples. For example, ${\nu }_{m\to a}(P_m)$ denotes an L-tuple message from variable node m to function node a including all the probability values on each choice; that is, $\mathbb{P}\left\{P_m={\rho }_{\mathrm{1}}\right\},\mathbb{P}\left\{P_m={\rho }_{\mathrm{2}}\right\},\dots ,\mathbb{P}\left\{P_m={\rho }_L\right\}$ . Specific message update rules for the function nodes and variable nodes are, respectively, expressed by

$$\begin{array}{cc}& {\widehat{\nu }}_{a\to n}^{\left(t\right)}\left(P_n\right)\propto {\displaystyle \sum }_{{\mathbf{P}}_{\partial a\mathrm{\setminus }n}}‍{\psi }_a\left({\mathbf{P}}_{\partial a}\right){\displaystyle \prod }_{m\in \partial a\mathrm{\setminus }n}‍{\nu }_{m\to a}^{\left(t\right)}\left(P_m\right),\end{array}$$

(12)

$$\begin{array}{cc}& {\nu }_{n\to a}^{\left(t+\mathrm{1}\right)}\left(P_n\right)\propto {\displaystyle \prod }_{b\in \partial n\mathrm{\setminus }a}‍{\widehat{\nu }}_{b\to n}^{\left(t\right)}\left(P_n\right),\end{array}$$

(13)

where the superscript $\left(t\right)$ indicates the iteration index, ∝ denotes the equality up to a normalization, and $\mathrm{\setminus }n$ and $\mathrm{\setminus }a$ imply the sets excluding n and a, respectively. The function ${\psi }_a\left({\mathbf{P}}_{\partial a}\right)$ implies the evaluation of the function node a for the set of variable nodes $\partial a$ , which is defined in (10).

Here are detailed explanations of the message update rules. The message update rule for variable nodes in (13) is quite simple. To compute the message from variable node n to function node a, the incoming messages from the other neighboring nodes $b\in \partial n$ except a are simply multiplied. Since messages are L-tuples, the computations are repeated over all possible $P_n\in \left\{{\rho }_{\mathrm{1}},{\rho }_{\mathrm{2}},\dots ,{\rho }_L\right\}$ . On the other hand, the message update rule for function nodes in (12) is more complex than that for variable nodes. To compute the message from function node a to variable node n, the incoming messages are basically multiplied as in the variable nodes. However, they should be summed over all the possible configurations of ${\mathbf{P}}_{\partial a\mathrm{\setminus }n}$ , where ${\mathbf{P}}_{\partial a\mathrm{\setminus }n}$ implies power allocation values of all variable nodes that are associated with a except n.

At the start of the algorithm, variable messages are initialized with a uniform distribution, meaning ${\nu }_{n\to a}^{\left(\mathrm{0}\right)}(P_n)=\mathrm{1}/L$ . At each iteration, messages are updated using the update rules above and are passed among the connected nodes in parallel. The BP estimate of the node n at time t is defined as

$$\begin{array}{cc}& {\mu }_n^{\left(t\right)}\left(P_n\right)\propto {\displaystyle \prod }_{a\in \partial n}‍{\widehat{\nu }}_{a\to n}^{\left(t\right)}\left(P_n\right).\end{array}$$

(14)

If a factor graph is a tree, it is proven that the sum-product algorithm eventually converges at a specific number of iterations which is dependent on the size of the tree, and the BP estimates become exact marginals. Interestingly, the sum-product algorithm is known to provide a good estimate of the marginal even for locally tree-like factor graphs as shown in Figure 2 [36]. By setting the maximum number of iterations of the algorithm at $t_{\text{MAX}}$ , the optimal value for the variable n can be determined by the maximum a posteriori (MAP) criterion as

$$\begin{array}{cc}& P_n^{\star }=\underset{P_n\in \{{\rho }_{\mathrm{1}},{\rho }_{\mathrm{2}},\dots ,{\rho }_L\}}{\arg \hspace{0.17em}\max }{\mu }_n^{\left(t_{\text{MAX}}\right)}\left(P_n\right).\end{array}$$

(15)

The following decimation procedure is introduced in order to improve the accuracy of the message-passing algorithm working on the locally tree-like factor graph [36]. Let the network share an arbitrary but predefined decision order. Message-passings obtain the estimates of the optimal values of all the variables in the network. Instead of making decisions in all the cells in a single round of message-passings, the decisions are partitioned into K subgroups with the predefined decision order and performed sequentially by multiple rounds of message-passings. Specifically, upon the decisions of the cells in turn, the cells hold their optimal decision values $P_n^{\star }$ during the next rounds of message-passings. This can be implemented by locally adding a specific function node that is strongly biased toward the decision value, that is, an indicator function $\mathbb{I}\left(P_n=P_n^{\star }\right)$ , at the corresponding variable node. According to this local modification of the factor graph, the update rule in (13) is slightly changed at the corresponding variable nodes as

$$\begin{array}{cc}& {\nu }_{n\to a}^{(t+\mathrm{1})}\left(P_n\right)\propto \mathbb{I}\left(P_n=P_n^{\star }\right){\displaystyle \prod }_{b\in \partial n\mathrm{\setminus }a}‍{\widehat{\nu }}_{b\to n}^{\left(t\right)}\left(P_n\right).\end{array}$$

(16)

The next round of message-passings attempts to find the optimal decisions for remaining variable nodes. However, this round is performed with an improved accuracy because computed messages are now conditioned on all the decision values in the previous rounds of message-passings, reducing the dependencies between variables. This procedure continues until all the optimal values for variable nodes are found successively. To summarize, the proposed BP-based downlink power control algorithm is described in Algorithm 1.

Algorithm 1: Belief-propagation-based downlink power control algorithm.

( $$\mathit{1}$$ ) Set an entire set of variables $$\mathbb{U}=\left\{\mathrm{1,2},\dots ,N\right\}$$ in the factor graph $$\mathbb{G}$$

( $$\mathit{2}$$ ) Set disjoint subsets of variables $${\mathbb{D}}_k$$ , $$\left({\mathbb{D}}_{\mathrm{1}}\cup {\mathbb{D}}_{\mathrm{2}}\cup \cdots \cup {\mathbb{D}}_K=\mathbb{U}\right)$$ with a decision ordering

( $$\mathit{3}$$ ) for   $$k=\mathrm{1,2},\dots ,K$$   do

( $$\mathit{4}$$ )  Initialize variable messages $${\nu }_{n\to a}^{\left(\mathrm{0}\right)}(P_n)=\mathrm{1}/L$$

( $$\mathit{5}$$ )  for   $$t=\mathrm{1,2},\dots ,t_{\mathrm{MAX}}$$   do

( $$\mathit{6}$$ )   for  each node $$\left(n,a\right)\in \mathbb{G}$$   do

( $$\mathit{7}$$ )    Update function messages $${\widehat{\nu }}_{a\to n}^{\left(t\right)}(P_n)$$ using (12)

( $$\mathit{8}$$ )    if   $$n\notin {\mathbb{D}}_{\mathrm{1}}\cup \cdots \cup {\mathbb{D}}_{k-\mathrm{1}}$$   then

( $$\mathit{9}$$ )     Update variable messages $${\nu }_{n\to a}^{\left(t+\mathrm{1}\right)}(P_n)$$ using (13)

( $$\mathit{10}$$ )   else

( $$\mathit{11}$$ )    Update variable messages $${\nu }_{n\to a}^{\left(t+\mathrm{1}\right)}(P_n)$$ using (16)

( $$\mathit{12}$$ )   end if

( $$\mathit{13}$$ )   Update BP estimates $${\mu }_n^{\left(t+\mathrm{1}\right)}\left(P_n\right)$$ using (14)

( $$\mathit{14}$$ )  end for

( $$\mathit{15}$$ ) end for

( $$\mathit{16}$$ ) for   $$n\in {\mathbb{D}}_k$$   do

( $$\mathit{17}$$ )  Choose the optimal value $$P_n^{\star }$$ using (15)

( $$\mathit{18}$$ )  Fix $$P_n=P_n^{\star }$$ and modify the factor graph $$\mathbb{G}$$ adding a function node $$\mathbb{I}\left(P_n=P_n^{\star }\right)$$

( $$\mathit{19}$$ ) end for

( $$\mathit{20}$$ ) end for

( $$\mathit{21}$$ ) return optimal power allocation $${\mathbf{P}}^{\star }=\left\{P_{\mathrm{1}}^{\star },\dots ,P_N^{\star }\right\}$$

5. Implementations of BP-Based Power Control

Some important practical issues in implementing the proposed BP-based power control are discussed in terms of the computational complexity, signaling overhead, convergence, and latency, which will clearly explain the beauty of this approach for distributed controls.

5.1. Computational Complexity

By investigating the proposed BP-based power control algorithm, most of the computational complexity originates from the updates of the function messages as in (12). Specifically, the required number of summations at function node a corresponds to the possible combinations of power allocations chosen by its neighbor sets $\partial a$ , resulting in a computational complexity of $O\left(L^{\mathrm{6}}\right)$ . Updating a single L-tuple message requires a computational complexity of $O\left(L^{\mathrm{7}}\right)$ . By considering repetitions of the message-passing procedure, the overall computational complexity of the proposed BP-based power control in Algorithm 1 is $O\left(K{t}_{\text{MAX}}{L}^{\mathrm{7}}\right)$ . Note that each cell is only responsible for updating one function message and one variable message; thus, the computational complexity in each cell does not increase with the network size N. As an example, this implies that the proposed BP-based power control can be distributively implemented in commercial 3GPP LTE networks at an eNB (an evolved Node-B (eNB) corresponds to a base station in the 3GPP LTE network architecture) level. The other centralized mechanisms should be implemented at a higher level of network entities, normally requiring high processing power and more space with high network deployment costs.

5.2. Signaling Overhead

The required information sharing for the algorithm increases the burden to the backhaul, reducing the data throughput. The minimization of information sharing becomes critical, particularly when the network size grows, and the number of cells increases. When compared with the centralized mechanism, the proposed BP-based power control requires information sharing only between the local pairs of neighboring cells. Moreover, the information is shared in the form of beliefs, which are basically probability values between zero and one, whereas the CSI typically consists of several complex numbers. Thus, this enables a great reduction in the signaling overhead.

5.3. Convergence and Latency

In commercial 3GPP LTE networks, the backhaul connections between eNB pairs are specifically defined as X2-interfaces. The communication reliability of the X2-interfaces can be managed within a desired precision using well-known transport protocols, for example, the stream control transmission protocol (SCTP). However, delays resulting from all message-passings are not avoidable. A typical latency for X2-interfaces is reported to be approximately 10 ms [44] in commercial LTE networks. As will be shown in the next section, the proposed BP-based power control algorithm converges very fast with only a few message-passings. Therefore, the overall latency to compute the optimal power allocation is expected to be in the order of 100 ms, which renders the algorithm easy to implement for downlink power control.

6. Simulation Results

The performance of the proposed BP-based power control is verified through extensive simulation results. As a simulation setup for a cellular network, seven hexagonal cells with a wrap-around model [45] are considered in Figure 3. Considering six first-tier neighbor cells in the hexagonal layout, the number of cell subgroups is set to $K=\mathrm{7}$ . By partitioning neighboring cells into different subgroups, transmit powers of any two neighboring cells are determined sequentially. The cell radius is set to 1,000 m by assuming an excursion radius of 10 m around the TP. Each UE is randomly dropped within a cell based on a uniform distribution over the cell area. The path loss exponent is set to 3.8 by considering the dense urban environments. The sum rates are averaged over 1,000 independent realizations of random UE drops. The simulator is developed based on MATLAB, and simulations are performed over a 64-bit Xeon 2.7 GHz CPU platform.

Figure 3

Simulation layout with a wrap-around model.

Figures 4 and 5 illustrate the optimality of the proposed BP-based power control. A binary choice of $L=\mathrm{2}$ is considered here. The sum rates are compared according to the different and independent realizations of UE drops, where the sum rates are normalized with the optimal sum rates with the optimal power allocation searched by combinatorial optimization. In 76% of the time, the proposed algorithm provides the optimal sum rate. In 90% of the time, the proposed algorithm provides near-optimal sum rates within 1.2% shortage compared with the optimal value. In 99% of the time, the proposed algorithm provides near-optimal sum rates within 6% shortage compared with the optimal value. Despite the distributed nature, the sum rate performance of the proposed algorithm approaches that of the optimal centralized control very closely in the average sense.

Figure 4

Sum rates according to different UE drops, where $P_{\text{MAX}}=\mathrm{40}$  dBm, $L=\mathrm{2}$ , $\beta =\mathrm{1.0}$ , $K=\mathrm{7}$ , and $t_{\text{MAX}}=\mathrm{4}$ .

Figure 5

Cumulative distribution function of normalized sum rates with 1,000 independent realizations of random UE drops, where $P_{\text{MAX}}=\mathrm{40}$  dBm, $L=\mathrm{2}$ , $\beta =\mathrm{1.0}$ , $K=\mathrm{7}$ , and $t_{\text{MAX}}=\mathrm{4}$ .

Figure 6 shows how the average sum rate varies with the total number of power levels L. Here, two types of quantization are considered to determine discrete power levels: one is uniform power quantization in linear scale, that is, ${\rho }_{\mathrm{1}}=\mathrm{0},\dots ,{\rho }_l=\left(l-\mathrm{1}\right)P_{\text{MAX}}/\left(L-\mathrm{1}\right),\dots ,{\rho }_L=P_{\text{MAX}}$ , while the other is uniform power quantization in dB scale, that is, ${\rho }_{\mathrm{1},\text{dB}}=\mathrm{0},\dots ,{\rho }_{l,\text{dB}}=\left(l-\mathrm{1}\right)P_{\text{MAX},\text{dB}}/(L-\mathrm{1}),\dots ,{\rho }_{L,\text{dB}}=P_{\text{MAX},\text{dB}}$ . A single power level, $L=\mathrm{1}$ , implies full power allocation in all cases, and $L=\mathrm{2}$ implies a binary choice of power allocation. As the number of power levels increases, the average sum rate also increases. The choice of a larger number of power levels improves the average sum rate, but at the cost of the increased computational complexity as discussed in Section 5.1. As shown in the figure, the uniform power quantization in linear scale always provides better sum rate performance under the same number of power levels, and its performance improvement becomes marginal when $L\ge \mathrm{4}$ . As a compromised solution between the performance and complexity, uniform power quantization in linear scale with $L=\mathrm{4}$ is used in the following simulations. (Further optimization of the power levels should improve the performance of the proposed BP-based power control; however, this requires complicated studies and is beyond the scope of this work.)

Figure 6

Average sum rates versus total number of power levels, where $P_{\text{MAX}}=\mathrm{40}$  dBm, $\beta =\mathrm{1.0}$ , $K=\mathrm{7}$ , and $t_{\text{MAX}}=\mathrm{4}$ .

Figure 7 shows how the choice of β influences the sum rate performance of the proposed BP-based power control algorithm. A small value of β, which corresponds to a high temperature, softens the conditions for the optimal solution, while a large value of β, which corresponds to a low temperature, hardens the conditions that concentrate the solution on the optimal value. In general, the proposed BP-based power control algorithm exhibits robust sum rate performances in most ranges of β. Starting from $\beta =\mathrm{0.001}$ , the sum rate remains nearly flat until $\beta =\mathrm{0.1}$ , and it slightly increases with β until $\beta =\mathrm{10}$ . However, the sum rate decreases after $\beta =\mathrm{10}$ . The disruptive performance degradation for large β results from numerical issues in the computer simulations. According to (8), β contributes to the exponent. Thus, the choice of large β leads to a huge number. For our simulation platform, MATLAB uses the double-precision floating point data type. The value range that the system can handle is from $\mathrm{2.22507}\hspace{0.17em}\times \hspace{0.17em}\mathrm{1}{\mathrm{0}}^{-\mathrm{308}}$ to $\mathrm{1.79769}\hspace{0.17em}\times \hspace{0.17em}\mathrm{1}{\mathrm{0}}^{+\mathrm{308}}$ . As observed in simulations, β (>10) makes values exceed $\mathrm{1.79769}\hspace{0.17em}\times \hspace{0.17em}\mathrm{1}{\mathrm{0}}^{+\mathrm{308}}$ , which is treated as an infinite number (MATLAB notation “inf”). The normalizing procedure in (8) enforces an undefined operation such as $\infty /\infty$ . MATLAB treats this as not-a-number (MATLAB notation “NaN”), and the resulting decisions become inaccurate in this case as shown in Figure 7. This breaking point may vary with hardware implementations. In reality, a more aggressive β aiming for the ground-state energy can be used for further performance improvement by optimizing the device implementation.

Figure 7

Average sum rates versus beta, where $P_{\text{MAX}}=\mathrm{40}$  dBm, $L=\mathrm{2,3},\mathrm{4}$ , $K=\mathrm{7}$ , and $t_{\text{MAX}}=\mathrm{4}$ .

The convergence rate of the proposed BP-based power control algorithm is depicted in Figure 8. As the maximum number of message-passings $t_{\text{MAX}}$ increases, the average sum rate also increases. The average sum rate rapidly reaches the maximum value with at most four message-passings. In the proposed BP-based power control algorithm, an initial point of power allocation is chosen by assuming equiprobable power levels as ${\nu }_{n\to a}^{\left(\mathrm{0}\right)}(P_n)=\mathrm{1}/L$ . By considering the potential optimization of the initialization procedures, the convergence rate in Figure 8 can be interpreted as worst-case results.

Figure 8

Average sum rates versus total number of message-passings, where $P_{\text{MAX}}=\mathrm{40}$  dBm, $L=\mathrm{2,3},\mathrm{4}$ , $K=\mathrm{7}$ , and $\beta =\mathrm{1.0}$ .

Figure 9 compares the proposed BP-based power control with the previous power control schemes with respect to the maximum transmit power at the TPs, $P_{\text{MAX}}$ . The sum rates of all power control schemes increase with the maximum power at the TPs; however, they eventually saturate at large $P_{\text{MAX}}$ . All the power control schemes exhibit similar sum rate performance in the noise-limited region. In the interference-limited region $\mathrm{40}\le P_{\text{MAX}}$ , which is the main interest of this work, all the power control schemes provide quite different sum rate performance, which determines the usefulness of the power control schemes. No power control, meaning full power transmission, provides the worst average sum rate, as expected. The binary on/off power control schemes notably improve the sum rate performances when compared with no power control. The performance improvement by the centralized version of the binary on/off power control is much greater than that by the distributed version owing to the sharing of all of the channel information in the network. The proposed BP-based power control outperforms the centralized version of the binary on/off power control. This is quite surprising in that distributed control normally provides worse sum rate performance than that of centralized control in return for the reduction in computational complexity and signaling overhead. Unlike the binary power control, the proposed BP-based power control does not limit the number of power levels, which explains this additional gain. Overall, the GP-based power control provides the highest average sum rate. This contributes to the best-known upper bound in terms of the average sum rates so far. Note that the performance of the proposed BP-based power control approaches very close to this upper bound within only 0.8%. On the other hand, Figure 10 compares the proposed BP-based power control with the previous power control scheme as in Figure 9, but the average numbers are computed with the lowest 5% sum rates, which corresponds to the user distributions near cell edges. Compared to Figure 9, the performance improvement of the proposed BP-based power control over the distributed binary on/off power control and full power transmission has been doubled because the impacts of efficient power control become more dominant in the interference-limited cases.

Figure 9

Average sum rates versus maximum transmit power at TPs. The BP-based power control is set with $L=\mathrm{4}$ , $\beta =\mathrm{1.0}$ , $K=\mathrm{7}$ , and $t_{\text{MAX}}=\mathrm{4}$ . The GP-based power control is implemented based on the successive convex approximation performing 4 GPs for every optimization.

Figure 10

Average sum rates versus maximum transmit power at TPs, where the average numbers are computed with the lowest 5% sum rates. The BP-based power control is set with $L=\mathrm{4}$ , $\beta =\mathrm{1.0}$ , $K=\mathrm{7}$ , and $t_{\text{MAX}}=\mathrm{4}$ . The GP-based power control is implemented based on the successive convex approximation performing 4 GPs for every optimization.

7. Conclusions

In this paper, a completely new approach to the power control problem of downlink wireless cellular networks has been proposed. The power control problem has been modeled as a simplified factor graph and efficiently solved with the proposed BP-based power control algorithm working on the factor graph.

The beauty of the proposed approach originates from its usefulness when implemented in real-world wireless communication systems. By enabling distributed control, the proposed approach breaks down the huge computational task for optimization into local tasks contributed by each cell, which otherwise should be managed by an expensive centralized network entity. In addition, the proposed approach minimizes the signaling overhead in the backhaul by sharing information in the language of belief, not in the conventional form of CSI. The rapidly converging characteristic emphasizes its usefulness furthermore. This work has challenged the common belief that distributed controls can never outperform centralized controls and surprisingly proved that it is not always true, by introducing a BP framework. The proposed distributed power control based on the BP framework provides nearly equivalent performance when compared with centralized power control schemes and even outperforms some of them if they are not fully optimized. Meaningful results provided in this paper have exemplified the usefulness of the BP framework for the optimization problems in the wireless communication fields. Together with some pioneering works that first shed light on the BP framework in this field [31–34], this paper provides a standard methodology to use a BP framework as a very powerful mathematical tool to describe and analyze the complex wireless communication systems.

Future research will include the enhancement of the optimal power levels and initialization procedure and the extension of the system model to include a multiuser transmission case or a heterogeneous cellular structure. In addition, other various applications to combinatorial optimization problems that can be encountered in cellular wireless systems where the neighboring cells interact with each other, such as radio resource allocation or scheduling problems, will be studied.