# An Obstacle-Tolerant Path Planning Algorithm for Mobile-Anchor-Node-Assisted Localization
## 4 Algorithm of OTPP
### Deployment of Beacon Points in OTPP
: _Given that each sub-square \(Sq_{h}\) (\(h\in\) (1, 2, 3, 4)) requires three beacon points, twelve beacon points should be added to cover the entirety of a basic square._  
Beacon points should be added in \(\textit{reg}_{1}\)-\(\textit{reg}_{4}\) owing to obstacle blocking and to ensure that each sub-square is a three-covered area. For a two-covered area, we can further obtain the following Lemma 3. **Lemma 3**. : _When a basic square contains two-covered areas, all the unknown nodes in a basic square can be localized, and a minimum of four beacon points should be added._  
Proof. : When a basic square contains two-covered areas; the basic square can be divided into 12 regions based on the sides of the obstacle (i.e., \(\textit{reg}_{1}\)-\(\textit{reg}_{4}\) and \(A_{1}\)-\(A_{8}\)), and two-covered areas lie within \(A_{i}\), \(i\in\) (1, 2,..., 8). Therefore, adding a beacon point to \(\textit{reg}_{1}\) results in the \(A_{1}\) and \(A_{2}\) regions receiving three beacon packets, thereby enabling the localization of the unknown nodes in these regions. Similarly, the addition of a beacon point to each of \(\textit{reg}_{2}\)-\(\textit{reg}_{4}\) will enable each of the \(A_{3}\)-\(A_{8}\) regions to receive three beacon packets and enable the localization of all the unknown nodes in these regions. Therefore, four beacon points should be added to enable the localization of all the unknown nodes within the entirety of the basic square. Figure 6: The layout of beacon points in the OTPP scheme and the dots are the possible locations of beacon points. **Lemma 4**. : _When a basic square contains zero-covered and one-covered areas, twelve beacon points should be added to the entirety of the basic square._  
Proof. : The basic square contains zero-covered and one-covered regions, and can be divided into twelve regions based on the sides of the obstacle (i.e., _reg\({}_{1}\)-reg\({}_{4}\)_ and _A\({}_{1}\)-_A\({}_{8}\)_), in which zero- and one-covered areas are present in _A\({}_{1}\)_, _A\({}_{4}\)_, _A\({}_{5}\)_, and _A\({}_{8}\)_. Meanwhile, two-covered regions are present in _A\({}_{2}\)_, _A\({}_{3}\)_, _A\({}_{6}\)_, and _A\({}_{7}\)_. Hence, the addition of three beacon points to reg\({}_{1}\) will enable the _A\({}_{1}\)_ and _A\({}_{2}\)_ regions to receive three beacon packets and the localization of the unknown nodes within these regions. Similarly, the addition of three beacon points to each of _reg\({}_{2}\)-reg\({}_{4}\)_ enables each of _A\({}_{3}\)-_A\({}_{8}\)_ to receive three beacon packets. Hence, the addition of twelve beacon points enables the localization of all the unknown nodes in the basic square. However, in Lemmas 3 and 4, which consider only the number of beacon points that should be deployed within each sub-square and do not consider the optimal deployment location, the excess number of beacon points will cause the MAN and unknown nodes to incur high energy cost. **Lemma 5**. : _When a basic square contains two-covered areas, a particular layout will enable two beacon points to completely cover the entirety of the basic square._  
Proof. : Lemma 3 indicates that the addition of a beacon point to each sub-square will enable complete coverage of the entirety of a basic square. However, this placement method does not consider the area that can be covered by a beacon point and only places a beacon point in each sub-square. Therefore, if we consider \(CR\geq\sqrt{(5/2)}d\), then, _A\({}_{1}\)_, _A\({}_{2}\)_, _A\({}_{3}\)_, and _A\({}_{8}\)_ can be covered straightforwardly by placing a beacon point at the position m\({}_{1}\). In addition, all the unknown nodes in _A\({}_{1}\)_, _A\({}_{2}\)_, _A\({}_{3}\)_, and _A\({}_{8}\)_ will be able to receive at least three beacon packets. Similarly, by placing a beacon point at position m\({}_{2}\), _A\({}_{4}\)-_A\({}_{7}\)_ will be covered, and all the unknown nodes in _A\({}_{4}\)-_A\({}_{7}\)_ will receive at least three beacon packets.