# An Obstacle-Tolerant Path Planning Algorithm for Mobile-Anchor-Node-Assisted Localization
## 4 Algorithm of OTPP  
### Deployment of Beacon Points in OTPP  
Table 3 presents the flow of how to deploy the beacon points by OTPP which is coherent with the following lemmas. The following lemmas prove that OTPP guarantees full coverage of localization of unknown nodes. **Definition 3**. : **Basic square with obstacles. ** _Assume that each basic square contains a maximum of one obstacle with sides of lengths \(L_{y}\) and \(W_{y}\), and the center of the obstacle lies on the position of the beacon point \(c_{0}\)._  
To determine the optimal placement of beacon points in a basic square with obstacles, we adopt divide-and-conquer approach. We first divide a basic square to four sub-squares because it is the maximum number of sub-squares which are identical and with minimum area size. To minimize the number of beacon points, the optimal location of beacon point should be able to cover all the unknown nodes in a sub-square. The union of optimal locations are called _reg_. As long as there are three non-collinear locations in _reg_ selected as beacon points, all the unknown nodes can be localized in a sub-square. Accordingly, we can obtain the following Lemma 2. **Lemma 2**. : _If all the unknown nodes \(s_{i}\) in the sub-square can be localized, then, three non-collinear beacon points need to be present, and all the three beacon points will lie within \(\text{reg}_{1}\)._ \begin{table}
\begin{tabular}{l} \hline \hline OTPP Beacon Point Deployment Algorithm \\ \hline Input: Given an \(N\times N\) sensing field and the communication range of MAN, \(\text{CR}\). \\ Output: Deployment of beacon points \\
1: Compute the maximum side length, \(d\), of a basic square based on \(\text{CR}\geq\sqrt{5/2}d\). \\
2: Compute the minimum number of basic squares to cover the sensing field. \\
3: Segment the sensing area to multiple basic squares. \\
4: For each basic square segmentation in the sensing area \\
i: Analyze the composition (\(k\)-covered area) of the basic square. \\
ii: Add beacon points into the basic square according to \(k\)-covered area. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Deployment of beacon points in OTPP. Figure 5: Obstacle shadowing results in the presence of non-three-covered areas in a basic square: (**a**) two-covered area, (**b**) one-covered and zero-covered areas where \(L_{y}<d\) and \(W_{y}\geq\text{d}\), and (**c**) one-covered and zero-covered areas where \(L_{y}\geq d\) and \(W_{y}<d\). Proof. : The localization of an unknown node's position requires at least three non-collinear beacon points [2]. Lemma 1 indicates that all the unknown nodes within the basic square can be localized. Therefore, the communication range (_CR_) of the MAN and unknown nodes are at least \(\sqrt{(5/2)}d\). Since the four sub-squares are identical, we consider sub-square \(Sq_{1}\) as representative. In sub-square \(Sq_{1}\), the maximum distance is \(\sqrt{2}d<\sqrt{(5/2)}d\). Hence, three beacon points are required to localize all the unknown nodes when no obstacles are present. When obstacles are present, to find _reg_, we extend the sides of the obstacle and hence the sub-squares are divided into three regions. _reg_ is then bounded by the two lines from the extended sides of the obstacle. The other two regions, \(A_{1}\) and \(A_{2}\), cannot guarantee to cover all the unknown nodes in \(Sq_{1}\). To cover all unknown nodes in \(A_{1}\), the locations of three beacon points are bounded to the area on the left of the obstacle which are \(A_{1}\) and \(\textit{reg}_{1}\). To cover all unknown nodes in \(A_{2}\), the locations of three beacon points are bounded to the area above the obstacle which are \(A_{2}\) and \(\textit{reg}_{1}\). The intersection of the two areas is _reg_, as shown in Figure 6.  
We may obtain the following (Corollary 1) to enable the localization of all the unknown nodes \(s_{i}\) within the entire basic square. **Corollary 1**.