Localization In Wireless Sensor Networks Based On A Spring Model

A wireless sensor network (WSN) consists of a large number of sensor nodes with limited energy, limited computing capability and limited memory. It functions to transfer the physical information to a digital data network. It has been used in a wide variety of applications including environmental monitoring, body health monitoring, object tracking, traffic controlling, etc. In-network studies of wireless sensor networks include network routing, data fusion, topology control, etc. All these applications and most of the in-network studies require the locations of sensor nodes. Therefore, network localization research is very important in wireless sensor networks.A large scale wireless sensor network is required in many applications such as lunar sensor network for lunar rover navigation. The large computational complexity, communication complexity and time complexity are big problems for a large scale sensor network. In order to solve these problems, this dissertation proposes a spring model for a wireless sensor network. It also creates a localization algorithm based on a spring model method (LASM) to reduce the complexity, while maintaining the localization accuracy in large scale sensor networks. The algorithm simulates the dynamics of the physical spring system to estimate the positions of nodes. The sensor nodes are set as particles with masses and are connected with neighbor nodes by virtual springs. The virtual springs will force the particles to move to the original positions, the node positions correspondingly, from the randomly set positions. Therefore, a blind node position can be determined from the LASM algorithm by calculating the related forces with the neighbor nodes. The computational and communication complexity are O(1) for each node, since the number of the neighbor nodes does not increase proportionally with the scale of the network.Some of the wireless sensor networks have properties of low computational capability and memory, dynamic nodes joining/leaving, etc. In order to match these properties, this dissertation proposes some derivate algorithms based on the basic LASM algorithm. A simpler iterative algorithm is proposed to lower the amount of calculation and storage in each iteration. Three patches of the basic LASM algorithm are proposed to avoid local optimization, kick out bad nodes and deal with node variation. Simulation results show that the computational and communication complexity are almost constant despite the increase of the scale of the network. The time consumption has also been proven to remain almost constant since the calculation steps are almost unrelated to the scale of the network.The actual geographical environment affects the performance a lot when executing a localization algorithm in wireless sensor networks. This dissertation takes this into consideration, analyze nodes'RSSI (Received Signal Strength Indication) measuring errors, and then propose related methods to handle them when running a localization algorithm. This dissertation pays attention to the parameter error of RSSI theoretical model and the obstacle error between neighbor nodes. Based on the analysis of the two mentioned errors, this dissertation proposes an online parameter modification method for RSSI theoretical model and another method to reduce the effect of those small obstacles. It shows by both theoretical analysis and simulations that this method can get low localization errors when the size of obstacles is small.This dissertation proposes an application of the above localization algorithm: location aware energy efficient heard node selection algorithm in wireless sensor networks. In this algorithm, three aspects are taken into consideration: the candidate head node's single residual energy, the total energy spent in the network if this candidate head node is chosen, and the quality of balance of the residual nodes'energy. To adapt the actual sensor nodes with limited memory and computing capacity, a simplified model is also introduced. Simulation results show that this new head node selection algorithm can achieve balanced energy consumption and greatly prolong the life time of the network.To verify the performance of localization algorithm and network communication, this dissertation designs and implements a prototype of wireless sensor network localization system. The network is constituted by common sensor nodes and iPhones/iPod Touches. The common sensor nodes are used to collect data and run the localization algorithm. The iPhones are used to send tasks to the common sensor network, get location data and display them. The experiment result shows the high network communication ability, high localization accuracy and low complexity.