# A Light Signaling Approach to Node Grouping for Massive MIMO IoT Networks
## 6 Approximation Algorithm  
Solving MMAD to optimality may require more time than is available to partition the nodes and schedule their transmissions. As we will see in Section 7.2, the time to find an optimal solution increases exponentially with the size of the problem, and for many IoT scenarios the number of nodes can be very large. In some cases, it may nonetheless be possible to use optimal solutions, since it is also often the case that IoT devices  
Figure 3: Example problem instance and solution for the optimization problem. Six nodes’ dominant directions (larger circles) and maximal allowed angular shifts (smaller circles) are shown, placed on a circle around the base station (central black circle). The nodes are partitioned into two groups, red and blue, such that the minimum angular difference between any two nodes is maximized, after allowing nodes to shift to any position within the range given by their maximal allowed angular shifts. transmit only infrequently; for example, sensor data may be gathered once every hour or day, which, depending on the number of nodes, may allow enough time to solve the optimization problem. In many cases, there will not be sufficient time and/or computational resources available or justifiable to find an optimal solution before it is needed, especially in view of the current trend of moving more intelligence deeper in the network. To address such scenarios, we created a suboptimal algorithm based on the same principles as the optimization formulation. This algorithm is efficient and can be used even for scenarios with many nodes that need to be partitioned and scheduled frequently. The algorithm is listed in Algorithm 1. Since the domain of our optimization (the circle) is finite, there is an inherent additive bound on the solution as compared with the optimal solution: the deviation of the solution provided by Algorithm 1 from the optimal solution cannot be greater than \(\pi\), and hence we refer to it as an approximation algorithm in the following. ```
Input:\(\mathcal{K}\): set of nodes, each with dominant direction \(\theta(k)\) and angular spectrum spread \(\sigma(k)\) \(\mathcal{G}\): set of groups numbered \(1\ldots G\), \(G=|\mathcal{G}|\) Output: group: list of groups each node is assigned to, of length \(|\mathcal{K}|\) foreach\(k\in\mathcal{K}\)do \(min\_angle[k]\leftarrow\theta(k)-\pi\sigma(k)\) \(max\_angle[k]\leftarrow\theta(k)+\pi\sigma(k)\) \(sorted\_nodes\leftarrow\mathcal{K}\) sorted by \(min\_angle\) \(first\_node\leftarrow\text{pop}(sorted\_nodes)\) \(group[first\_node]\gets 1\) \(next\_group\gets 2\) sorted\(\_nodes\leftarrow\mathcal{K}\) sorted by \(max\_angle\) foreach\(k\in\mathcal{K}\)do \(group[k]\gets next\_group\) \(next\_group\gets next\_group+1\) if\(next\_group>G\)then \(next\_group\gets 1\)
```  
**Algorithm 1**Approximation algorithm for node partitioning based on dominant direction and angular spectrum spread. The basic idea of the approximation algorithm is to sort the nodes by angle, that is, by their dominant directions but also taking into account their angular spectrum spreads, and then assign a group to each node sequentially in a round robin fashion. In this way, nodes in the same group will be as far away as possible from each other in terms of their position in the sequence, although not necessarily in terms of their angles, since the solutions produced by this algorithm are suboptimal in general. To take the angular spectrum spreads into account, an angular shift is computed for each node \(k\in\mathcal{K}\) as \(\pi\sigma(k)\), where \(\sigma(k)\) is the normalized angular spectrum spread of \(k\). This is similar to constraint (9) in the optimization. The angular shift is first subtracted from each node's dominant direction (line 2), and the node with the minimal resulting angular position is taken as the first node and assigned to the first group (lines 5-6). Then, for the remaining nodes, the angular shift is added to each node's dominant direction (line 3) and the nodes are again sorted by the resulting angle (line 9).