Localization and Localizability in Sensor and Ad-hoc Networks

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.