# Improved Branch-and-Bound Antenna Selection Algorithm for Massive MIMO
## 3 Efficient Antenna Selection via Enhanced Branch-and-Bound Optimization
### Branch-and-Bound Antenna Selection  
The BAB algorithm is an efficient method for search space reduction. Compared to exhaustive search methods, its key mechanism for significantly reducing computational complexity lies in establishing well-designed pruning criteria. By eliminating child nodes that fail to satisfy search constraints through these pruning conditions, the algorithm effectively enhances search efficiency. When utilizing the BAB algorithm to maximize channel capacity through receive-side antenna selection, the optimal subset \(S_{opt}\) is initialized as an empty set, lower bound \(B=-\infty\), while the initial candidate antenna set \(K=\{1,\;2,\;\cdots,N_{r}\}\). Each row in the current candidate antenna set is evaluated for its channel gain magnitude \(\Delta_{k}\). These gains are sorted in descending order, following which the row corresponding to the maximum gain value in the channel matrix is selected, analogous to the greedy algorithm. This selected row, combined with \(N_{t}\) transmit antennas, forms a sub-channel matrix \(\mathbf{H}_{s}\). The corresponding channel capacity \(C_{s}\) of this sub-matrix is then calculated. If the value of \(C_{s}\) is less than \(B\), prune the corresponding antenna element. If the value of \(C_{s}\) outperforms \(B\), add this row to subset \(S_{opt}\) and update the candidate set to \(K=\{1,\ 2,\ \cdots,N_{r}\}\setminus S_{opt}\). This iterative process continues until the size of subset \(S_{opt}\) equals the threshold \(d\), at which point the search terminates and \(B\) is updated with the current \(C_{s}\) value. The complete BAB algorithm workflow is formally summarized in Algorithm 1. It is evident that when applying the BAB search algorithm to antenna selection, the process incrementally incorporates antennas with higher gain into the optimal antenna subset starting from an empty set. Specifically, in our constructed search tree, the tree depth corresponds to the predefined size of the optimal antenna subset. The search initiates from the root node and proceeds upward layer by layer. At each hierarchical level, the optimal node is selected and added to subset \(S_{opt}\) until the search reaches the leaf nodes. However, certain limitations in the BAB search procedure remain non-negligible: (1) Since the channel capacity value corresponding to the first generated child node cannot be known a priori, initializing the lower bound \(B\) to negative infinity is theoretically justified. However, the update of \(B\) only occurs upon reaching leaf nodes, which substantially weakens the pruning constraints imposed by \(B\) throughout the search process. This may result in unnecessary exploration of non-optimal nodes. (2) The parameter \(d\) requires a predefined configuration. Moreover, the algorithm must be executed repeatedly for different \(d\) values to obtain their corresponding optimal antenna subsets. ```
1:Input : \(N_{r},\ N_{t},\ d\). 2:Initialization : Set the selected antenna subset \(S=\varnothing\), \(S_{opt}=\varnothing\); candidate set \(K=\{1,2,\ldots,N_{r}\}\); \(B=-\infty\). 3:for\(i=1\) to \(|K|\)do  Calculate \(\Delta_{k,\ i},\ k\in K\) endfor  Sort \(\Delta_{k,\ i}\) in descending order to get an ordered index vector \(J\). for\(i=1\)to \(|J|\) \(j=\left\lceil J\right\rceil_{i}\)  Create child node \(S=S\cup j\). \(C_{s}=\log_{2}\det\left(\mathbf{I}_{N_{t}}+\frac{\rho}{N_{t}}\mathbf{H}_{s}^ {H}\mathbf{H}_{s}\right)\); \(\mathbf{H}_{s}\) represents the channel submatrix associated with child node \(S\). if\(C_{s}\)\(<\) B, then  Prune the child node to avoid further searching and break the loop. else if\(C_{s}>B\),then  if\(|S|=d\),then  Update \(S_{opt}=S,\ C_{opt}=C_{s},\ B=C_{s}\), break. else \(K=\ \{1,2,\ldots,N_{r}\}\setminus S\), go back to step 3. endif  endif endif endfor
```  
**Algorithm 1**Antenna selection based on BAB search method  
```
1:Input : \(N_{r},\ N_{t},\ d\). 2:Initialization : Set the selected antenna subset \(S=\varnothing\), \(S_{opt}=\varnothing\); candidate set \(K=\{1,2,\ldots,N_{r}\}\); \(B=-\infty\).