Study On Distributed Localization Schemes For Wireless Sensor Networks

Recent advances in micro-electro-mechanical system (MEMS) technology, wireless communications and digital electronics have enabled the development of low-cost, low-power, multifunctional sensor nodes that are small in size and communicate untethered in short distances. These tiny sensor nodes which consist of sensing, data processing, and communicaiting components, leverage the idea of wireless sensor networks based on collaborative effort of a large number of nodes. There are many potential applications of sensor nodes of wireless sensor networks: military surveillance, environmental monitoring, traffic surveillance, medical treatment, building and structures monitoring, even anti-terrorism, etc.Through distributed coordination, wireless sensor networks are expected to revolutionize the ways in which we understand and construct complex physical systems. Fundamental to such coordination is localization, or the ability to establish spatial relationships among objects. Certainly, a viable solution to the node localization problem imposes many challenges. At physical level, changes in the surrounding environment introduce error in the sensor measurements. At network level, nodes need to determine their locations in a reliable manner while operating under stringent constraints in computation, communication and energy resource.In this dissertation, we discuss the distributed localization scheme suitable to wireless sensor networks. The main contributions of this dissertation are: this dissertation addresses the background of localization and the challenges involved in localization for very large, ad hoc deployed wireless sensor networks, summarizes the proposed localization algorithms. As well as, it briefly introduces other open research issues in wireless sensor networks.In this dissertation, we address the challenges involved in localization for very large, ad hoc deployed wireless sensor networks. Although several localization technologies have been proposed in the past few years, none currently satisfies all our requirements because no single localization system is simultaneously scalable, ad hoc deployable and accommodating of the hardware constraints of very small devices. Our thesis is that all these issues can be solved simultaneously by a self-configuring localization system that autonomously adapts to its environmental dynamics and differentiated service quality. Our approach is based on localized adaptive algorithms that self-configure to exploit both the local processing on each sensor node, as well as the redundancy across densely-deployed sensor nodes. For the typical range-free localization algorithm, DV-Hop, we detailedly analyze the characteristics of localization errors utilizing the Cramer-Rao Bound theorem, and compute the errors of hop distance estimation theoretically and experimentally. Based on this work, an improved scheme for this algorithm is proposed. The principle of the improved scheme is to introduce the concept of beacons collinearity degree to the phase of beacons selection. Furthermore, in the implemention of the improved scheme, a way of chosing collinearity degree adaptively is put forward. Simulation results show that the improved scheme reduces 10 to 45 percents in average localization error, and 35 to 50 percents in variance of localization error.Based on the characteristics of the DV-Hop localization algorithm, an improved scheme for this typical range-free localization algorithm is proposed in this thesis. The principle of the improved scheme is to introduce the beacons collinearity degree to the phase of beacons selection. Furthermore, an adaptive collinearity degree based on the localized network topology and simulated annealing based location estimates are proposed. Not only the topology of beacons but also the relation of unknown nodes and beacons are considered in the phase of beacons selection. Through simulation studies, we demonstrate that the improved algorithm is more reliable and robust to irregular network topology than previous algorithm, especially when the beacon ratio is relatively low or the topology is sparse.A novel distributed acquiring sensors positions approach approach based on multi-hop beacon nodesto the localization of sensors in wireless sensor networks is proposed in this thesis. The principles of proposed algorithm are acquiring the beacons utilizing the distance vector routing scheme, and then selecting some beacons as references according to the collinearity of beacons and the relative location relation of the self-node and beacons. Finally, a weighted-based location estimate strategy is utilized, which is independent of the complex optimize computation. The extensive simulation study shows that the proposed algorithm is self-adaptive, distributed, and scalable, and robust, especially the computation complexity and the robustness. It also exhibits fine performances on computation complexity and variance of localization, which is suitable for the node localization in large-scale wireless sensor network. As the network density varies form 4 to 14, the maximum localization errors and variance reduce form 1/6 to 1/2, 1/3 to 1/2 respectively, comparing to DV-Hop.Fine-Grained localization algorithm is also discussed. As Introudcing the rigidity graph theory into the localization problem, a category based on the localizable corroborative body is proposed. A novel localization algorithm based on the localizable corroborative body is proposed in this thesis. The advantage of this strategy is that the localization information of the multi-hop beacons can be utilized as well as spread and accumulation of localization error are avoided. In this dissertation, we addressed the theorem foundation of the proposed algorithm and the algorithm for the construction of localizable corroborative body. Simulation results show that the proposed algorithm is self-adaptive, distributed, scalable and robustness. As the distance estimation error waries form 0.025 to 0.30 times communication range, the average localization error varies from 0.02 to 0.36 times communication range, It also exhibits fine performances on localization error, which is suitable for the node localization in large-scale wireless sensor network.Based on the localization scheme described above, we firstly propound the concept of differential localizing services. That is, different QoS of localization are supported demand on the localization requisition and localization scene. In this way, the power consumption can be reduced greatly while keeping the requried localization accuracy, which proposes a novelty approach for sysmetical solution of localization in wireless sensor networks.This thesis finally summarizes the research work, and discusses those potential research topics in future.