Michele Battelli

Localization techniques in multi-hop wireless networks with emphasis on wireless sensor networks

Date: January 2007

This thesis presents a study of localization techniques in multi-hop wireless networks with emphasis on wireless sensor networks. Localization is defined as computing the coordinates of the nodes in the network with respect to a suitable reference system.

Localization, also known as ``node positioning problem,'' is a challenging problem especially in resource constrained networks such as sensor networks. Its importance for the correct functioning of geographic-based routing and position aware application and services make localization an interesting field of study in wireless networks. Despite the effort of the research community and the variety of solutions proposed so far in literature, the problem is quite open and requires further investigation.

In this work we first present different techniques to determine the coordinates of the nodes in a multi-hop wireless network classifying them under different aspects and technologies.

A fundamental taxonomy of localization protocols distinguishes between range-free and range-based solutions: the former are protocols in which no information about distance between nodes is available to the localization process; the latter rely on distance and/or angle measurements between nodes to estimate a node's position.

We will develop our solution to the localization problem which falls in the range- and angle-based category. Particular attention will be paid to error propagation, which leads to corrupted final positioning of the nodes in most localization algorithms.

We consider networks where nodes are capable of measurements of distance and angle of arrival from nodes within their transmission radius. The first solution proposed in this work is a simple localization protocol named Range-Based Centroid (RBC), that starting from a single node (the beacon)with given coordinates localizes all the nodes in the network with reasonable accuracy.

We then propose a novel localization protocol that achieves greater accuracy by containing the propagation of the localization error as the process progresses away from the source node that started the process ---often called the emph{beacon}. Our new protocol, termed MEC$^{2}$ (for emph{Minimum Enclosing Circle Containment}), is investigated analytically and via simulations.

Clearly the initial localization process of the wireless sensor nodes in the coordinates system has a fundamental role for the future functioning of the network and should not be affected by misbehaving or malicious elements such as malfunctioning or hijacked nodes.

Therefore, we propose a technique to improve the reliability of the localization process in wireless sensors networks allowing nodes to spot a malicious neighbor attempting to corrupt the positioning process.

This technique, named ByLo, performs as pre-processing to any localization algorithm and its roles is that of reducing the impact of malicious nodes in the localization process by denying them participation to the coordinates computation.

When the localization process safely terminates and all the nodes in the network are aware of their position, the next step consists in the ''management'' of the coordinates.

Location managements techniques allow nodes to discover the coordinates of emph{other nodes} in the network and utilize them to direct traffic and perform geographic routing or enable position-aware services.