Development of node positioning algorithms for wireless sensor networks

Abstract

Wireless sensor network (WSN) has numerous remote monitoring and control applications and sensor positioning is a fundamental and crucial issue in WSN operation and management. In this thesis, a number of algorithms are devised for node localization in WSN with the use of the noisy distance measurements between nodes as well as anchor position information. Assuming that the sensors are within communication range and that all pairwise distance measurements are available, the subspace method constructs a multidimensional similarity matrix from the distance measurements. By utilizing its noise subspace, a set of linear equations can be formed and solved to produce the position estimates of the sensors. Furthermore, the subspace method is modified to be computationally more attractive and to be able to operate in distributed manner. Moreover, the subspace method performance is enhanced by applying a weighted least squares technique. which enables the subspace method to attain the Cram´er- Rao lower bound (CRLB) for sufficiently high signal-to-noise ratio (SNR). Theoretical performance analysis of the proposed algorithms is also produced to evaluate their statistical properties. Semidefinite relaxation (SDR) algorithm can be used for localization, by converting the corresponding maximum likelihood cost function into a convex optimization problem and by relaxing some of the constraints. The equivalence of two existing SDR algorithms for single-sensor localization in the literature is proved. In timeof- arrival based WSN, the positions of anchors and the propagation speed contain measurement errors in practice. SDR algorithm, which takes the anchor position and propagation speed uncertainty into account, is applied for WSN localization. Connections with existing SDR algorithms is provided; and the CRLBs of sensor position with uncertainties are also derived. In some WSNs, a centralized processing unit may be unavailable. Centralized positioning algorithm cannot be applied; hence, distributed algorithms are needed. Two-step weighted least squares (TSWLS) is a computationally simple algorithm, which constructs a set of constrained linear equation with the use of distance measurements, anchor positions and the anchor position covariance. In the first step, it estimates the sensor position by neglecting the constraint. In the second step, the constraint is included to improve the accuracy of the first-step-position-estimate. Sensors connect to at least three anchors and apply TSWLS to obtain their position estimates; and the corresponding covariance is calculated. These sensors become anchors and transmit the position estimates and the covariance to their connected sensors. This process repeats, until the position estimates converges. Simulation results show that it can attain the CRLB for sufficiently high SNR. In some scenarios, non-line-of-sight (NLOS) distance measurements are present due to obstructions and sources of large positioning errors, and therefore need to be mitigated. Belief propagation (BP) is a distributed Bayesian algorithm which allows each sensor to store a distribution of its position and transmit messages to its connected sensors. By recursively updating the position distribution with receiving messages, each sensor finally gets its position estimate upon convergence. BP is employed to WSN localization with NLOS distance measurements. Simulation results show that the proposed algorithm is comparable to the CRLB of the sensor positions ,in which perfect NLOS identification is assumed and only line-of-sight distance measurements is used.

Date of Award	2 Oct 2008
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Hing Cheung SO (Supervisor)