# Utility-Based Wireless Routing Algorithm for Massive MIMO Heterogeneous Networks
## 4 Preallocated Sequential Routing
### Proposed Algorithm  
The system constructs an initial antenna allocation in the first place. In order to evaluate the utility of each BS, all non-MBSs are directly connected to the MBS \(BS_{1}\). Then, antennas are preallocated to BSs. \(D_{ij}\) is a two-dimensional matrix composed of the distance between two BSs. Each BS will get initial preallocated antennas for subsequent topological connection. First, the initialization algorithm sets \(U_{MAX}\) (maximum system utility) and \(U_{total}\) (utility after N-th antenna allocated) as zero (Step 1-2). Subsequently, in each round of the first for loop (Step 3-22), PSR allocates one antenna to the BS with the maximum utility. To achieve this, in the second for loop (Step 4-20), it calculates the utility of each BS after adding an antenna. Then, PSR assigns one antenna to \(BS_{i}\) temporarily and stores the number of antennas in \(s_{t}(i)\) (Step5). Then, in the third for loop (Step 6-14), the total utility of the system after accumulating the antenna is calculated. This loop calculates the total energy efficiency, \(U_{total}\), of the system. When the utility of \(BS_{i}\) is added, the antenna of \(s_{t}\) is used (Step 7-9), and when the utility of \(BS_{j}\) is added, \(s(i)\) is used (Step 10-12). After \(U_{total}\) is obtained, Step 15 compares \(U_{total}\) with \(U_{MAX}\). If \(U_{total}\) is larger, it becomes the new \(U_{MAX}\) (Step 16), and then \(i\) is temporarily stored in \(i_{s}\) (Step 16). Then, \(U_{total}\) is set to zero for the next round, while \(U_{MAX}\) retains the result as the maximum value of the previous round of the system. After the second for loop is over, the antenna is allocated to the \(BS_{i_{s}}\) that can obtain maximum utility (Step 21). The \(N_{i}\) antennas are allocated in sequence until the allocation is completed, and the initial preallocated antenna set, \(s(i)\), is obtained. ```
1:\(U_{MAX}=0\);
2:\(U_{total}=0\);
3:forN = 1:\(N_{i}\)do
4:fori = 2: I do
5:\(s_{t}(i)=s(i)+1\);
6:forj = 2: I do
7:ifj == i then
8:\(U=U(A(s_{t}(i)))\);
9:\(U_{total}=U+U_{total}\);
10:else
11:\(U=U(A(s(i)))\);
12:\(U_{total}=U+U_{total}\);
13:endif
14:endfor
15:if\(U_{total}>U_{MAX}\)then
16:\(U_{MAX}=U_{total}\);
17:\(i_{s}=\mathrm{i}\);
18:endif
19:\(U_{total}=0\);
20:endfor
21:\(s(i_{s})=s(i_{s})+1\);
22:endfor
```  
**Algorithm 1** Initialization. Next, we detail the main function. PSR has to calculate each \(BS_{i}\) in the increasing order of its distance to MBS. \(SET_{I}=\{BS_{1},\ldots\}\) is the set of the \(i\)-th BS's subtree, where \(BS_{i}\) is a non-MBS root node, and it is then redistributed according to the subfunction. In the main algorithm, PSR cycles through all BSs to adjust the parent nodes of all BSs in each round of the first for loop (Step 2-16). \(\Delta U^{MAX}\), the median value of the subsequent utility, is initializedas zero (Step 3). In Step 4, the candidate node set \(V_{i}\) of the \(BS_{i}\) is listed, which contains all the BSs \(BS_{i}\) whose distances to \(BS_{i}\) and \(BS_{1}\) are not larger than the original \(D_{i,1}\). This is because if \(BS_{i}\) is connected to any \(BS_{j}\) where \(D_{i,j}\) is greater than \(D_{i,1}\), then under the same antenna allocation, \(U\big{(}l_{i,j}(A)\big{)}\leq U(l_{i,1}(A))\). Therefore, choosing a BS closer to MBS and having \(D_{i,j}<\,D_{i,0}\) will have a better chance of obtaining a larger utility. In the second for loop (Step 5-14), PSR needs to analyze the utility of the candidate nodes in \(V_{i}\) in turn. If the \(BS_{i}\) is connected to the \(m\)-th candidate node, the antenna allocation of the subtree where the candidate node is located will change accordingly. As all BSs will eventually be connected to the MBS through the multihop network, the first BS that is non-MBS is specified as the subtree root node, that is, \(m_{a}\) (Step 6). Next, Step 7 accumulates the preallocated antennas obtained by \(BS_{i}\) to \(m_{a}\). Then, the subfunction is executed to calculate the maximum utility of the subtree and \(U1\) is obtained (Step 8).