Localization and Localizability in Sensor and Ad-hoc Networks

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Localization and Localizability in Sensor and Ad-hoc Networks"

By

Mr. Zheng Yang


Abstract

Location awareness is essential for many applications of wireless sensor 
networks. Sensor networks are by nature used to provide spatio-temporal 
information of physical world. Hence, it is important to associate sensed data 
with locations, making data geographically meaningful. This thesis presents a 
systematic study on the localization and localizability issues. Localization is 
an autonomous mechanism of node location computation. Network localizability 
answers whether or not a network can be localized; i.e., the locations of all 
network nodes can be uniquely determined under certain constraints. In brief, 
localization emphasizes location computation while localizability considers 
location uniqueness.

We first investigate error control in localization, a key factor that 
determines the success of a localization approach in practice. We propose the 
concept of Quality of Trilateration (QoT) to quantitatively evaluate 
trilaterations under inaccurate distance measurements. QoT takes both geometry 
and ranging errors into accounts. With the help of QoT, the proposed 
localization approach succeeds in alleviating error propagation, a main source 
of location error in multi-hop networks.

Distributed localizability testing is also studied in this thesis. We analyze 
the limitation of trilateration and propose a novel approach WHEEL, which not 
only identifies localizability, but also, similar to trilateration, computes 
node locations. WHEEL is based on the global rigidity of wheel graphs. It 
inherits the simplicity and efficiency of trilateration, while at the same time 
recognizes more localizable nodes. More than that, we prove WHEEL is the 
optimal among all distributed approaches. WHEEL is believed to be a nice 
substitute of the widely-used trilateration.

Finally, we propose the concept of node localizability. Node localizability 
focuses on the location-uniqueness of a single node. Indeed, network 
localizability is a special case of node localizability in which all nodes are 
localizable. Applying rigidity theory, we study the conditions of a node being 
localizable. For the first time, it is possible to answer the fundamental 
questions of localization: how many nodes in a network are localizable in a 
partially localizable network and which they are.


Date:			Tuesday, 29 June 2010

Time:			10:00am – 12:00noon

Venue:			Room 3501
 			Lifts 25/26

Chairman:		Prof. Chun Man Chan (CIVL)

Committee Members:	Prof. Yunhao Liu (Supervisor)
 			Prof. Lionel Ni
 			Prof. Qian Zhang
                         Prof. Susheng Wang (ECON)
                         Prof. Xiaohua Jia (Comp. Sci., CityU.)


**** ALL are Welcome ****