# Green Small Cell Operation of Ultra-Dense Networks Using Device Assistance +
## 3 Belief Propagation
### Belief Propagation Optimization Algorithm  
Following the results of [27], when \(\frac{1}{\tau}\rightarrow\infty\), \(p(\mathbf{x})\) concentrates around the maxima of \(F(\mathbf{x})\), and then, we have:  
\[\lim_{\frac{1}{\tau}\rightarrow\infty}\bar{\mathbf{x}}=\operatorname*{argmax}_{ \mathbf{x}}F(\mathbf{x}) \tag{9}\]  
where \(\bar{\mathbf{x}}=\{\bar{x}_{1},\cdots,\bar{x}_{j},\cdots,\bar{x}_{j}\}\), and \(\bar{x}_{j}=E[X_{j}]\) means the marginal expectation of the random variable \(X_{j}\). In principal, standard BP can be seen as a process to calculate the estimated marginal probability distribution with respect to the random variable \(X_{j}\). Thus, when the marginal probability distribution of \(p(\mathbf{x})\) is estimated, an approximated solution of the optimization problem can be found. **Definition 2** (Belief). : _The belief \(b_{j}(x_{j})\) is the estimated marginal probability distribution of \(p(\mathbf{x})\) with respect to \(X_{j}\)._  
Thus, we leverage the BP algorithm to find \(b_{j}(x_{j})\). On the constructed factor graph, belief messages are passed through the edges between APs and UEs. After the belief message is repeatedly passed between APs and UEs, the set of turned-on APs is determined according to the estimated marginal probability distribution. It is well known that when a factor graph is acyclic, \(b_{j}(x_{j})\) converges to the true marginal probability distribution of \(p(\mathbf{x})\) with respect to \(X_{j}\)[26]. However, as shown in Figure 2, the constructed factor graph usually has cycles, e.g., AP 2, UE 3, AP \(j\), UE \(i\), and AP 2. In this case, BP yields an approximated result; thus, we compare our simulation results with the optimal value obtained from the exhaustive search in Section 5. Now, we present the algorithm below. 1. **Initialization. ** At time \(t=0\), messages \(b_{j\to i}(t,x_{j})\) for \(\forall j\in\mathcal{J}\) and \(\forall i\in\mathcal{I}\) are set to have an arbitrary distribution. For instance, we use the uniform distribution, such as: \[b_{j\to i}(t,x_{j})\sim U(0,1).\] (10)
2. **UE update. ** After the initialization, UE \(i\in\mathcal{I}\) generates and sends the belief messages to its neighboring APs \(j\in\mathcal{N}(i)\) where \(\mathcal{N}(i)\) denotes the neighbor APs of UE \(i\). At \(t>0\), the message update is defined by: \[b_{i\to j}(t,x_{j}) = E\left[\exp(\frac{1}{\tau}f_{i}(\mathbf{X}))|x_{j}\right].\] (11) Therefore, when the expectation (11) is calculated over independent \(x_{j^{\prime}}\), \(\forall j^{\prime}\in\mathcal{N}(i)\), the message update can be presented by \[b_{i\to j}(t,x_{j}) = \sum_{\mathbf{x}\in\{\mathbf{x}|x_{j}\}}\left(\exp(\frac{1}{\tau }f_{i}(\mathbf{x}))\prod_{j^{\prime}\in\mathcal{N}(i)\setminus\{j\}}b_{j^{ \prime}\to i}(t,x_{j^{\prime}})\right)\] (12)  
Figure 2: Example of a factor graph consisting of variable nodes, AP \(j\), \(\forall j\in\mathcal{J}\), and factor nodes, UE \(i\), \(\forall i\in\mathcal{I}\). where for given \(X_{j}=x_{j}\). Furthermore, in (12) \(\exp(\frac{1}{t}f_{i}(\mathbf{x}))\) is calculated for given \(X_{j}=x_{j}\). Since (12) has both a sum and a product, BP is called the sum-product algorithm. Equation (12) is the product of the factor with belief messages from AP \(j^{\prime}\in\mathcal{N}(i)\), \(j^{\prime}\
eq j\), to UE \(i\), marginalized over all random variables, except \(x_{j}\). To calculate \(f_{i}(\mathbf{x})\), at \(t=1\), we assume that \(S_{j}=1\),\(\forall j\in J\). At \(t\geq 2\), \(S_{j}\), \(\forall j\in J\), is initialized to one and incremented by the number of associated UEs where each UE is associated with AP \(j=\text{argmax}_{j^{\prime}}\,b_{i\to j^{\prime}}(t,x_{j^{\prime}}=1)\). 3. **AP update. ** AP \(j\in\mathcal{J}\) generates and sends the belief messages to all neighboring UE \(i\in\mathcal{N}(j)\), where \(\mathcal{N}(j)\) denotes the neighbor UEs of AP \(j\).