# Utility-Based Wireless Routing Algorithm for Massive MIMO Heterogeneous Networks
## 4 Preallocated Sequential Routing
### Proposed Algorithm
In Step 9, \(U^{MAX}_{m_{a}}\) records the maximum value of the subtree utility of \(m_{a}\) in the first for loop last time, and \(U_{i}\) is the utility value obtained after the antennas are preallocated by the \(BS_{i}\). The difference between the three is the utility improvement (Step 9) obtained after reconnection. Subsequently, the main algorithm judges whether the utility increment is greater than the previous maximum value; if so, it is replaced (Step 11) and \(m\) is marked as a reconnected BS (Step 12). After all the loops of the second for loop are ended, if \(i^{*}\) is obtained, the \(BS_{i}\) is reconnected; \(SET_{i^{\prime}}\) and \(U^{MAX}_{m_{a}}\) are updated for the next comparison (Step 15). ```
1:\(U_{i}(\cdot),l_{i}(\cdot,\cdot),d_{i,j},BS_{i^{\prime}},U_{i}(\cdot),l_{i}( \cdot,\cdot),N_{i}\)
2:\(SET_{i}\)
3:\(U^{MAX}_{i}=0;i\in(2,1)\)
4:for\(i=2\):\(I\)do
5:\(\Delta U^{MAX}=0\);
6: create node set \(V_{i}\);
7:for\(m\in V_{i}\)do
8:\(m_{a}=SET_{C(m)}\)'s root node;
9:\(s_{m_{a}}=\sum_{i\in SET_{m_{a}}}(s_{i})\);
10:\(U1=subfunction(d_{i,j},BS_{i^{\prime}},U_{i}(\cdot),l_{i}(\cdot,\cdot),\,SET_{m_{a}}, N_{i})\);
11:\(\Delta U=U1-U^{MAX}_{m_{a}}-U_{i}\);
12:if\(\Delta U>\Delta U^{MAX}\)then
13:\(\Delta U^{MAX}=\Delta U\);
14:\(i^{*}=m\);
15:endif
16:endfor
17: update \(SET_{istar},U^{MAX}_{m_{a}}=U1\);
18:endfor
```  
**Algorithm 2** Main Algorithm. Finally, PSR calculates intermediate variable \(U1\), the maximum utility after \(BS_{i}\) connected to BS of \(V_{i}\) in subfunction in Algorithm 3. To find the total utility of the subtree, that is, the first two for loops (Step 2-20 and Step 3-19), all BSs allocate their \(N_{i}\) antennas in the order from the closest to the farthest distance from the MBS. For the \(n\)-th antenna of \(BS_{i}\), PSR sets a judgment factor \(c\) (Step 4). When \(c=0\), the number of antennas is not increased by the child node. Otherwise, one antenna is added when \(c=1\). The value of \(c\) is determined by the third for loop (Step 5-13). Then, the subfunction temporarily assigns the antenna to the child node \(BS_{j}\) and obtains \(A_{j}\) (Step 6). It checks if \(r_{n}^{\Sigma}>\sum_{j\in i^{\prime}}s_{j}\) & \(U\big{(}A_{j}\big{)}>U_{MAX}\) to ensure that the speed assigned to the child nodes does not exceed the uplink data rate (Step 7). Then, if the utility of the new allocation is greater than the known ones \(U_{MAX}\), it replaces the old value (Step 8) and becomes the allocation candidate (Step 9-10). At this time, \(j\) and \(A_{j}\) are temporarily stored in \(j^{*}\) and \(A^{*}\), and \(c\) is set to 1 (Step 11). After the third for loop, if \(c=0\), the antenna allocation is unchanged (Step 14-15) because no better utility is obtained. However, if \(c=1\)the antenna is allocated to \(j^{*}\) (Step 17). Finally, \(U1\) is returned (Step 21). The signaling overhead of PSR is acceptable because of two reasons. First, the algorithm requires limited information. Each BS's candidate parents \(V_{i}\) are only limited in an area. Second, the allocation results (each link's antenna number and data rate) of each BS do not take much overhead to transmit. ```
Input:\(d_{i,j},\ BS_{s}\), \(U_{i}(\cdot)\), \(l_{i}(\cdot,\cdot)\), \(SET_{m_{u}}\), \(N_{i}\) Output: U1, \(U_{MAX}=0\); for\(BS_{i}\in\ SET_{m_{u}}\)do
1 forn = 1:\(N_{i}\)do
2\(c\ =\ 0\); for\(j\in BS_{i}\)do
3\(A_{j}=\{N_{i}-n,s_{1},s_{2},\ldots,s_{j}+1,\ldots\ \}\);
4 if\(r_{n}^{*}>\sum_{j\
eq i}s_{j}\ \&\ U\big{(}A_{j}\big{)}>U_{MAX}\)then
5\(U_{MAX}=U\big{(}A_{j}\big{)}\);
6\(j^{*}=j\);
7\(A^{*}=A_{j}\);
8\(c\ =\ 1\);
9 endif
10 endfor
11\(c==0\)then
12 break;
13 else
14\(A^{*}=\{N_{i}-n,s_{1},s_{2},\ldots,s_{j^{*}}+1,\ldots\ \}\);
15 endif
16 endfor
17 endfor
18\(U1=\sum_{BS\ \in\ SET_{i}}U_{BS}(A_{BS})\ +U_{m_{u}}\);
```  
**Algorithm 3**Subfunction. We again use Figure 3 to illustrate PSR operation. For simplicity of presentation, each BS is assumed to have only six antennas.