The Study Of Node Localization Algorithm In Wireless Sensor Networks

As early as the late 1970s, the U.S. Defense Advanced Research Projects Agency (DARPA) presents the original idea of Wireless Sensor Networks (WSNs). With nearly three decades' development of MEMS (micro-electro-mechanical systems), embedded systems, processors, wireless technology and storage technology, a new generation of wireless sensor networks have emerged. Wireless sensor networks are composed of numerous tiny sensor nodes, which have limited sensing, computing, storage and communication capabilities. When these nodes are organized in an appropriate manner, and their output are organically associated and integrated, the whole network can provide much higher ability than a single node. Wireless sensor networks can be widely used in environmental monitoring, industrial control, battlefield surveillance, disaster relief and rescue, anti-terrorism and other occasions. The U.S. National Research Council reports that "The use of Embedded (Networked) Systems throughout society could well dwarf previous milestones in the information revolution."Recent years, wireless sensor networks have become a hot research spot, in which routing protocol, synchronization, node localization, topology control and applications are the important research fields. Node localization is a basic capacity of wireless sensor networks. WSNs are essentially intended to observe spatio-temporal characteristics of the physical world. It is meaningful only when the collected data are associated with their locations. Locations of sensor nodes are fundamental to providing location stamps, locating and tracking point objects, forming clusters, and facilitating routing, etc. However, it is really difficult to design and implement a "best" positioning algorithm, mainly because of the magnificent size of WSNs (hundreds of thousands of nodes) and the limited computing, communications, storage capacity and energy, which makes common positioning strategies (such as GPS or manual configuration, etc.) can not be applied to sensor networks.At present, numerous localization algorithms have been proposed, these algorithms are broadly divided into the "range-based" and "range-free". Range-based approaches are using a measurement technology to get the accurate distance or angle measurements, and then locate the unknown nodes with trilateration ( mul-tilateration ) or triangulation methods. Range-free approaches normally rely on proximity, near-far information or less accurate distance estimation to infer the lo- cations of unknown nodes. The most common method is to use signal propagation model to estimate the distance, as the transceiver is the only available ranging device for most of the common sensor nodes, and the model usually is isotropic. However, an increasing number of studies show that in such a intensive low-power WSNs, the propagation of the wireless signal leads a serious departure from the ideal model. Receiver signal strength is heavily dependent on the direction and is different with different nodes or different environment. Therefore it is unlikely to infer the distance according to the received signal strength. This means that all the localization methods depending on the ideal propagation model need to be reconsidered.As WSNs usually run in open environments, use wireless communications and only have very limited resources, it is vulnerable to various kinds of attacks. Attackers may disseminate false reference positions in the network, or mislead unknown nodes to get false distance/angle measurements by tricks like modifying distance, jamming communication and creating wormhole. However, most of the node localization algorithm does not have the capacity to resist attacks; and a few secure localization algorithms can be applied only to specific types, or the computational complexity and communication complexity are very high, which are not suitable for power constrained WSNs.Through this dissertation, we study the node localization. The first work of this dissertation is to build a simulation environment according to the RIM (Radio Irregularity Model). After a large number of simulated experiments, we got the relationship between RSS and distance with different link status. Based on the previous research work, we provide a Link-State Based Annulus (LSBA) localization algorithm, and then gives a panorama of performance comparison among LSBA and other four localization algorithms: Centroid, DV-HOP, Amorphous and APIT in terms of estimation accuracy, convergence speed, computational complexity and communication cost in the simulated realistic environment. Simulation results show that LSBA achieves the best tradeoff among all the four metrics in WSNs with moderate number of anchors, and has good adaptability to irregular node deployment as well.The second work of this paper is to design and implement a robust node localization algorithm, which is capable of dealing with various location and distance attacks and as well as other kinds of information distortion caused by node malfunction or abnormal environmental noise. Bilateration deals with location attacks, node malfunction and exceptional measurements in a unified way by considering the set of samples consisting of reasonable samples and unreasonable samples and trying to use reasonable samples to locate unknown nodes. It first distinguish the possible correct or false (that is, too much error) information; then it only use the possibly correct information to do localization. This dissertation also evaluates and compares Bilateration with three multilateration based localization algorithms, and the simulation results show that Bilateration achieves the best comprehensive performance and is more suitable to real wireless sensor networks.