# Optimized Gateway Placement for Interference Cancellation in Transmit-Only LPWA Networks
## 4 Algorithms for Multiple GWs Placement
### Algorithm of Weight Bipartite Graph (WBG)  
Inspired by [8], two sets of vertices are defined. The first set is composed of all possible optional points (OPs), where an OP is defined as point of intersection of the boundaries of a pair of decoding  
Figure 5: The capture margin of the \(\tau\) with fixed \(z\). Figure 6: The location margin of \(\delta\). The blue region shows the location of GW: with location margin (**b**); and without location margin (**a**). cresents. The second set of vertices contains all possible ordered pairs of SNs, such as \(v(s_{i}s_{j})\), \((i\
eq j)\). Since every pair of SNs generates two crescents, the ordering of pairs is necessary to distinguish between the two crescents. The first sensor in the ordered pair is the one that is captured. Weighted edges of the two subsets of vertices are applied according to the following rules. 1. If an OP is strictly inside of the capture region and outside of ICD region (inside of the ICD circle) decided by an ordered pair of SNs \((s_{i},s_{j})\), \((i\
eq j)\), an edge with a weight of \(\alpha\) exists between the vertices OP and \(v(s_{i}s_{j})\). In other words, an edge is weighted by \(\alpha\) if the OP is inside a capture circle but outside the decoding crescent. 2. If an OP is inside or on the boundary of the capture region and inside or on the boundary of ICD region (outside of the ICD circle) decided by an ordered pair of SNs \((S_{i},s_{j})\), \((i\
eq j)\), which means in or touching a crescent, the edge between the OP and \(v(s_{i},s_{j})\) has a weight of \(\beta\). 3. Otherwise, there is no edge between the OP and \(v(s_{i},s_{j})\). We now walk through the WBG algorithm (Algorithm 1) for an example of three SNs and two GWs, when \(z\leq\frac{1}{\tau^{2}}\), as illustrated in Figure 7. The capture circle and ICD circle for any ordered pair of SNs are calculated and we get the crescent region where the GW can decode both collided packets sent by the pair of SNs with capture effect and IC method, as shown in Figure 7a. In Figure 7b-d, the OPs are generated by the crescents corresponding to groups of sensor pairs \(\{s_{1}\) and \(s_{2}\), \(s_{2}\) and \(s_{3}\}\), \(\{s_{1}\) and \(s_{3}\), \(s_{1}\) and \(s_{3}\) and \(\{s_{1}\) and \(s_{3}\), \(s_{2}\) and \(s_{3}\}\), respectively, such as \(\{p_{1},p_{2},\cdots,p_{12}\}\) in Figure 7b. Because there are too many OPs in the example, some of them are omitted here. As an example of weight calculation, \(P_{11}\) in Figure 7b is on the boundary of two decoding crescents, which gives two edges each with weight \(\beta\). \(P_{11}\) can also be located (it is not labeled) in Figure 7a, where it can be seen that \(P_{11}\) is strictly inside the ICD circle of \((s_{1},s_{3})\) and also inside the capture circle of \((s_{1},s_{3})\). Therefore, \(P_{11}\) gains an additional weight of \(\alpha\), for total weight of \(2\beta+\alpha\). Figure 7: Crescent of each pair of SNs and location of 3 SNs and 2 GWs. The crescent region where the GW can decode both collided packets sent by the pair of SNs with capture effect and IC method, are shown in (**a**). In (**b–d**), the OPs are generated by the crescents corresponding to groups of sensor pairs \(\{s_{1}\) and \(s_{2}\), \(s_{2}\) and \(s_{3}\}\), \(\{s_{1}\) and \(s_{2}\), \(s_{1}\) and \(s_{3}\}\) and \(\{s_{1}\) and \(s_{3}\), \(s_{2}\) and \(s_{3}\}\), respectively, such as \(\{p_{1},p_{2},\cdots,p_{12}\}\) in (**b**). ```
0:\(N\) SNs locations, \(\{s_{1},s_{2},\cdots,s_{N}\}\in\Re^{2}\); \(M\) the number of GWs;
0: The locations of number of \(M\) GWs, \(\{g_{1},g_{2},\cdots,g_{M}\}\in\Re^{2}\).