Development of real-time algorithms for mobile positioning


Student thesis: Master's Thesis

View graph of relations


  • Ka Wai CHEUNG


Awarding Institution
Award date15 Jul 2004


Accurate localization of mobile station (MS) is of considerable interest in wireless Communications, especially since the first ruling of the Federal Communications Commission (FCC) for detection of emergency calls in the United States (US) in 1996. In addition to emergency management, the mobile location information is also useful in monitoring of children, fleet management asset tracking, interactive map consultation and location based information broadcast. Time-of-arrival (AOA), received signal strength (RSS), time-difference-of-arrival (TDOA) and angle-of-arrival (AOA) determined at the MS or the wireless network are commonly used measurements for mobile positioning. However, the relationship between these measurements and the MS position I nonlinear. Solving the non-linear equations directly involves intensive computations and the solution is highly sensitive to measurement errors. In this thesis, a series of accurate and real-time mobile positioning algorithms using different types of location-bearing measurements have been developed. The proposed positioning algorithms can be divided into two categories: linearized weighted least squares (WLS) and multidimensional scaling (MDS). In the linearized WLS approach for TOA or RSS measurements, the nonlinear equations are reorganized into a set of linear equations by introducing an intermediate variable, which is a function of the MS position, and the linear equations are then solved by WLS. The linearization technique borrows the idea of spherical interpolation, which is a linearized algorithm for TDOA measurements, but the algorithms can only give suboptimal performance. Linearization is also applied in the AOA measurements without introducing any intermediate variable and the resultant linear equations are solved by WLS as well. It is proved that the AOA-based WLS algorithm can achieve optimal estimation accuracy. In order to improve the accuracy of the linearized WLS algorithms for TOA, RSS or TDOA measurements, the relation between the MS position and the intermediate variable is exploited. In ding so, the MS position is determined by minimizing a constrained weighted least squares (CWLS) function based on the technique of Lagrange multipliers, where the relation forms the constraint. It is proved that the estimation accuracy of the CWLS-based algorithms for the three types of measurements attains the corresponding Cramer-Rao lower bounds for sufficiently small measurement errors. This technique can also be considered as the generalized and extended version of the existing TDOA-based positioning algorithm called linear-correction least squares (LCLS). On the other hand, a mobile positioning algorithm is devised using TOA or RSS measurements via modifying the classical MDS technique, which is a multivariate data analysis approach. The MDS algorithm is simple to implement but the performance is suboptimal. Apart from algorithm development, the performance measures of the proposed positioning algorithms, namely, the bias and variance, have also been derived and verified by computer simulations.

    Research areas

  • Mobile computing, Computer algorithms, Mobile communication systems, Geographic information systems