A novel heuristic algorithm for node localization in anisotropic wireless sensor networks with holes

The node localization is a crucial technology that affects practicality, accuracy and effectiveness of the wireless sensor networks (WSNs). Sensor nodes are often deployed non-uniformly in anisotropic WSNs with holes in various applications such as monitoring area terrain. The existence of holes will invariably affect the Euclidean distances between nodes and result in low accuracy of node localization. In this paper, a Heuristic Multidimensional Scaling (HMDS) algorithm is proposed to improve accuracy of node localization in anisotropic WSNs with holes. By exploring the virtual node and constructing the shortest paths between nodes, the Euclidean distances between nodes are obtained via employing the heuristic approach such that they can be used to calculate more accurate locations of the nodes. The HMDS algorithm greatly reduces the communication complexity and computational complexity compared with the MDS-MAP algorithm. Simulation results demonstrate that the HMDS algorithm requires fewer anchors to obtain the node locations. The HMDS algorithm is suitable for four different topologies, including the semi-C-shape topology, the O-shape topology, the multiple O-shape topology and the concave-shape topology and is exceedingly accurate and efficient comparing with state-of-the-art methods in anisotropic WSNs with holes.