טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGur Eyal
SubjectFirst-Order Methods for Solving the Sensor Network
Localization Problem
DepartmentDepartment of Applied Mathematics
Supervisors Professor Shoham Sabach
Dr. Shimrit Shtern


Abstract

A wireless sensor network is a set of low-powered transceivers located in a given area. Each sensor has the capability of monitoring its immediate surroundings for temperature, sound, movement, etc., and this data is collected for further processing. Thus, knowledge of the location of each of the sensors in the network is crucial to understand and process the collected data.


Since the number of sensors in the network can be large, it is not cost effective to equip each one of them with a GPS device, and therefore only a portion of the sensors have a known logged location - these sensors are called anchor sensors. Every sensor in the network can communicate with sensors within its radio range, and each such pair of sensors are called neighbors.


The Wireless Sensor Network Localization (WSNL) problem aims at finding the location of all sensors in the network, using anchor sensors information and noisy distance measurements between each pair of neighbors.


In this work, we address the WSNL problem, with a given anchor location, via optimization techniques that are focused on the mean square error formulation, which is known to have a statistical interpretation as minimizing the maximum-likelihood function (assuming the distances are perturbed with a normal noise). However, mathematically speaking, this formulation yields a non-convex and non-smooth optimization problem, and the existing literature on iterative algorithms for solving this type of problems is very limited. While there are more formulations of the WSNL problem, we use this formulation for three main reasons: first, as already mentioned, it has a statistical interpretation, and second, solving this model, at least in some particular cases of the WSNL problem (such as the Single Source Localization problem), yields better locations than other formulations. Last but not least, this formulation has a great basis to exploit some properties and structures of the problem that are useful in designing solution techniques.


We tackle the fact that the used formulation is non-smooth by representing the Euclidean distance as a solution of a linear optimization problem in some higher dimension, and we derive an equivalent constrained smooth and non-convex formulation. This equivalent formulation opens the gate to propose an algorithmic framework which is based on the well-known concept of Alternating Minimization. This new algorithmic framework for solving the WSNL problem is globally convergent: not only that the sequence of objective function values converges, the sequence of the location estimates converges to a unique location, which is also a critical point of the corresponding objective function. The proposed algorithmic framework has a range of fully distributed to fully centralized implementations, all with the property of global convergence. Moreover, this algorithmic framework is applicable in every network, regardless of its architecture.


To the best of our knowledge, this is the first first-order algorithm that solves the maximum-likelihood formulation that is applicable in every network architecture, and that it also enjoys the global convergence property.