Region Decomposition Based Node Localization Algorithm For Anisotropic Wireless Sensor Networks

Node localization is one of the key technologies of wireless sensor networks’ applications. Among the existing localization algorithms, range-free algorithm is more suitable for large-scale wireless sensor networks because of its low cost and little influence from environment. However, such localization algorithm performs well only in isotropic networks, which has denser node distribution. When the network is anisotropic, holes or obstacles will lead that the estimated distance between nodes deviates from their Euclidean distance, causing a serious decline in localization accuracy of the algorithm.Based on analysis of the reason that range-free DV-Hop algorithm causes serious localization error in anisotropic networks, this paper develops a region decomposition based node localization algorithm for anisotropic wireless sensor networks(HCD-DV-Hop algorithm). Its main idea is first decomposing an anisotropic network into several different isotropic networks by using the proposed anisotropic region decomposition algorithm, thus avoiding the holes or obstacles’ influence on the shortest communication path between nodes. Then DV-Hop algorithm is used in each sub-network for node localization. The hop count based decomposition algorithm first uses the proposed concave/convex node recognition algorithm and cleansing criterion to obtain the optimal concave and convex nodes in the network, followed by segmentation of the network’s boundary. At last, the neighbour boundary nodes of optimal concave nodes flood the network with decomposition messages, thus the anisotropic network is decomposed into several simple isotropic networks. The implementation of this algorithm only depends on the network’s connectivity information and doesn’t need any additional hardware facilities. Simulation results show that no matter how node communication radius and the ratio of anchor node change, compared with original DV-Hop algorithm, the proposed HCD-DV-Hop algorithm can effectively reduce node localization error in anisotropic networks, performing better localization result.