# An Obstacle-Tolerant Path Planning Algorithm for Mobile-Anchor-Node-Assisted Localization
## 1 Introduction  
Wireless sensor networks (WSNs) consist of a number of sensing devices with external physical information and network communication capabilities. WSNs are deployed in an area to be detected, and they collect and report environmental information for users. The scope of application of WSNs includes the military, intelligent h, health care, and ecological detection [1]. In the application of WSNs, localization is a critical technique that enables unknown nodes (or ordinary nodes) to obtain their own location information to further optimize applications such as routing protocols and object tracking [2; 3]. The Global Positioning System (GPS) is a tool that obtains location information. However, each unknown node equipped with a GPS transceiver will result in a substantial increase in costs. A viable method is utilizing a few anchor nodes. Anchor nodes are nodes that know their locations, being equipped with GPS transceivers. Anchor nodes broadcast messages including their location information to unknown nodes. Unknown nodes then use distance measurement technology to obtain the relative distance or angle relationship with the anchor nodes. Thereafter, the positions of these unknown nodes are calculated via localization algorithms [2; 3; 4; 5; 6]. The minimum number of required anchor nodes must ensure that each unknown node receives at least three messages from different anchor nodes, which is still costly. An alternative is using a dynamic anchor node, also known as a mobile anchor node (MAN), with a pre-planned path to continuously broadcast location informationto replace multiple static anchor nodes. The locations where the MAN broadcasts messages are called beacon points. This localization architecture is called mobile-anchor-node-assisted localization (MANAL) [2]. MANAL comprises a GPS-equipped MAN and numerous unknown nodes [7; 8], as shown in Figure 1.  
Path planning is a critical issue in MANAL. The fundamental requirement for a MAN is to ensure that all the unknown nodes can receive three (non-colinear) packets, thereby enabling unknown nodes to calculate their own positions. Most environments have obstacles that involve communication-signal shadowing. For example, electromagnetic waves collide with obstacles on the transmission path, thereby resulting in reflection, diffraction, and scattering as well as in the unknown nodes being rendered incapable of receiving packets from a MAN. To solve the problem of obstacle blocking, reference [8] proposed an intuitive method, in which a MAN changes its movement direction when it encounters obstacles, detours around the obstacles, and broadcasts packets to unknown nodes. However, this method cannot guarantee that all the unknown nodes will receive three packets for locating their position. In addition, a MAN is required to additionally broadcast substantial location information when changing the direction of movement, thereby resulting in excessive wastage of power for the MAN and unknown nodes. To reduce costs and guarantee that all the unknown nodes in the sensing area receive at least three messages from MAN, there are optimal placements for beacon points. The optimal path of MAN is based on the optimal placement of beacon points. Obviously, the MAN's path problem is one of the Hamiltonian path problems [9] that visits each vertex of the graph exactly once. The Hamiltonian path problem is a well-known NP-complete problem [10; 11] and therefore MAN's path is also an NP-complete problem. Therefore, this study presents an obstacle-tolerant path planning (OTPP) approach, which uses the divide and conquer strategy to divide the entire area into multiple unit squares, thereby optimizing the position of the beacon point and the required number of beacon points for each unit square. Lastly, all the beacon points are visited by MAN. To summarize, the contributions of this study are as follows:  
1.