טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentWinterman Nofar
SubjectOptimization Methods for Solving Sensor Network Localization
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Amir Beck
Full Thesis textFull thesis text - English Version


We consider the Sensor Network Localization (SNL) problem which consists of estimating

the coordinates of radiating sensors using several anchor nodes, in order to minimize the

errors in sensors' positions to fit noisy range measurements. We adopt the least squares

methodology to the squared range measurements, and provide computationally efficient

algorithm, named Alternating Minimization Trust Region (AMTR), to solve the SNL

problem which is a nonconvex problem. The AMTR algorithm is based on the Alternating

Minimization (AM) method in the sense of creating subproblems in which the objective

function is minimized over a single block of decision variables while the other variables

are kept fixed. We show that each subproblem can be rewritten as a generalized trust

region subproblems (GTRS) or as an extension of the GTRS problem, which consists of

minimizing a quadratic function subject to a quadratic constraint and a linear inequality

constraint. First we provide the details of an algorithm that computes the global solution

of the GTRS problem based on its necessary and sufficient optimality conditions. We then

exploit the special structure of the extended problem and devise an efficient algorithm

to solve it as well. Finally, we present the results of the numerical experiments which

demonstrates the good convergence performances of the AMTR algorithm and emphasizes

the efficiency and accuracy of this algorithm compared to other existing methods.