A graph theoretical approach to robust and efficient localizability in wireless sensor networks

Abstract

In the localization of wireless sensor networks it has been observed that there are network topologies on which any localization technique may produce large positional errors even if the distance measurements are perfect. This has motivated researchers to study the conditions which ensure the unique localizability of a network. One common issue in sensor networks is the high possibility of node failures which may cause a previously localizable network to become non-localizable. To address this, in the first part of thesis, we propose some level of robustness by introducing the notion of a p-node robustly localizable network: a localizable network which retains its localizability upon the loss of any set of p-1 nodes. We characterize such networks, using graph theory, by deriving a set of necessary and (distinct) sufficient conditions for the network graph. We also propose several approaches to restore the p-node robust localizability of the network after its topology is changed. It is well-known that, even with perfect distance measurements, there are networks which cannot be localized in polynomial time. This motivates us to seek some efficiency properties for network localization beyond mere localizability. Hence, we focus on two common criteria of computational efficiency and distributedness and study network topologies which can be localized with low computational complexity and in a distributed fashion. In this light, in the second part of thesis, we focus on bilaterative networks, a superset of trilaterative networks. Bilaterative networks are localizable with simple calculations and in a sequential and distributed manner. However, the localization algorithms which can localize bilaterative networks may not finish in polynomial time with respect to the node count. Our contribution in this context is to analyse the computational complexity of bilaterative localization techniques. By constructing a random graphical model of the network, we show that with a probability close to 1 a bilaterative localization technique will finish in polynomial time on almost any random network without exponential-size memory requirements. The focus of the last part of thesis is on the distributed map-stitching techniques. These techniques generally work in three steps aiming to reduce the localization computational complexity; (1) splitting the network into small subnetworks; (2) localizing each subnetwork locally; (3) stitching the local maps together. A pair of subnetworks is stitchable if they satisfy certain constraints. To the best of our knowledge, in existing map-stitching techniques, two subnetworks are declared as stitchable if they share at least 3 nodes. However, from the graph-theoretical studies related to localizability, there are also other configurations with fewer number of common nodes than 3 (including zero) where the union of the two subnetworks is localizable. We propose a novel stitching technique that can serve all stitchable configurations not been addressed so far. This considerably expands the class of networks which can be localized in a distributed manner. Based on this technique, we propose a new localization algorithm which outperforms all the existing distributed localization algorithms in terms of the number of localized nodes while keeping the positional error at a comparable level. Show more