Mobile anchor nodes path planning algorithms using network-density-based clustering in wireless sensor networks

Motivated by the improvement of the localization performance and the utilization rate of virtual beacons in heterogeneous WSNs, in this paper, we propose three Mobile Anchor nodes Path Planning (MAPP) algorithms, namely, IMAPPP-NDC, SMAPP-NDC and MMAPP-NDC. Different from most of the existing MAPP algorithms which divide the region of interest (ROI) into several layers or areas and make mobile anchor nodes traverse the ROI layer by layer or one area after another, the proposed MAPP algorithms combine network-density-based clustering, inter-cluster path planning and intra-cluster path planning together to improve localization performance and the utilization rate of virtual beacons based on the mathematical analysis of the relationship between the communication range r of a sensor node and the side length a of the regular hexagon movement trajectory. In addition, SMAPP-NDC and MMAPP-NDC algorithms employ obstacle avoidance mechanisms to steer clear of obstacles and provide non-collinear beacon points around obstacles.