# Optimized Gateway Placement for Interference Cancellation in Transmit-Only LPWA Networks
## 4 Algorithms for Multiple GWs Placement
### Algorithm of Weight Bipartite Graph (WBG)
1: Compute capture circle and ICD circle for each ordered pair of SNs \((s_{1},s_{2}),(s_{1},s_{3}),\cdots,(s_{n},s_{n-2}),(s_{n},s_{n-1})\) according to Equations (8) and (12) separately, and get the crescent region;
2: Compute the intersection points between any two ICD crescents decided by any two different pairs of SNs, and get the set \(P=\{p_{1},p_{2},...,p_{i}\}\), which is the set of all of OPs
3: Construct a weight bipartite graph G = (P, S, E) conforming to the follows: * \(P=\{p_{1},p_{2},...,p_{i}\}\) is the set of vertices composed of OPs; * \(S=\{v_{(s_{1},s_{2})},v_{(s_{1},s_{3})},\cdots,v_{(s_{1},s_{n})},\cdots,v_{(s_{ n},s_{n-1})}\}\) is another set of vertices decided by ordered SNs pairs; * \(E=\{e_{1},e_{2},...,e_{i}\}\) is the set of weighted edges connecting each \(p_{i}\) and \(v(s_{i},s_{j})\). If an OP, \(p_{i}\in P\), is inside of the capture circle and inside of an ICD circle, set an edge with weight value of \(\alpha\) for \(e_{i}\); If an OP, \(p_{i}\in P\) is inside of the capture region and outside of ICD circle, i.e., \(p_{i}\in P\) is in the crescent, the edge \(e_{i}\) is set by weight value of \(\beta\); Otherwise, there is no edge between the \(p_{i}\) and \(v_{(s_{i},s_{j})}\);
4:for\(k=1\) to \(M\)do
5: Compute the sum of weight values of the edges that connect to each \(p_{i}\in P\);
6: Get the OP, \(p_{j}\), which has the maximum sum of weight values of edges;
7: Set the location of \(k^{th}\) GW to be location of the \(p_{j}\) with the maximum sum of weight values of edges;
8: For each of the \(e_{j}\) connected to \(p_{j}\), if the weight value of the \(e_{j}\) is \(\beta\), remove the edge \(e_{j}\), vertices of \(p_{j}\), and all of the connected vertices \(v_{(s_{i},s_{j})}\) and \(v_{(s_{j},s_{i})}\) even if they are not connected; if the weight value of edge \(e_{j}\) is \(\alpha\), remove the edge \(e_{j}\), vertices of \(p_{j}\) and all of the connected vertices \(v_{(s_{i},s_{j})}\) only;
9: Get the new sets of \(P\), \(S\) and \(E\);
10:endfor
```  
**Algorithm 1** Algorithm of WBG  
Figure 7(a) shows the complete bipartite graph, where \(\alpha=1\) and \(\beta=2\). The weights of the edges joining \(P_{11}\) and \(V_{s_{1},s_{3}}\) and joining \(P_{17}\) and \(V_{s_{1},s_{3}}\) are 1 and 2, respectively, as shown in Figure 7(b). The OP with maximum sum of weight values is selected as the first optimized location of GW, such as \(P_{5}\) in Figure 7(a), which has a sum of 5. In Step 7, assuming \(P_{5}\) was selected, \(V_{s_{2},s_{1}}\) and \(V_{s_{3},s_{2}}\) are removed, because they are each connected to \(P_{5}\) with an edge of weight 2. However, the reverse order vertices \(V_{s_{1},s_{2}}\) and \(V_{s_{2},s_{3}}\) must also be removed, because this first-placed GW will be able to decode all two-way collisions from \(s_{1}\) and \(s_{2}\) and all two-way collisions from \(s_{2}\) and \(s_{3}\), regardless of order. All edges connected to \(V_{s_{2},s_{1}}\), \(V_{s_{1},s_{2}}V_{s_{3},s_{2}}\) and \(V_{s_{2},s_{3}}\) are removed, leaving what is shown in Figure 7(b). Next, based on Figure 7(b), the second optimized location of GW could be selected, such as \(P_{17}\), because only one pair of SNs is left and \(P_{17}\) connects to it.