This thesis studies range-based WSN localization problem in 3D environments that induce coplanarity. In most real-world applications, even though the environment is 3D, the grounded sensor nodes are usually deployed on 2D planar surfaces. Examples of these surfaces include structures seen in both indoor (e.g. floors, doors, walls, tables etc.) and outdoor (e.g. mountains, valleys, hills etc.) environments. In such environments, sensor nodes typically appear as coplanar node clusters. We refer to this type of a deployment as a planar deployment. When there is a planar deployment, the coplanarity causes difficulties to the traditional range-based multilateration algorithms because a node cannot be unambiguously localized if the distance measurements to that node are from coplanar nodes. Thus, many already localized groups of nodes are rendered ineffective in the process just because they are coplanar. We, therefore propose an algorithm called Coplanarity Based Localization (CBL) that can be used as an extension of any localization algorithm to avoid most flips caused by coplanarity. CBL first performs a 2D localization among the nodes that are clustered on the same surface, and then finds the positions of these clusters in 3D. We have carried out experiments using trilateration for 2D localization, and quadrilateration for 3D localization, and experimentally verified that exploiting the clustering information leads to a more precise localization than mere quadrilateration. We also propose a heuristic to extract the clustering information in case it is not available, which is yet to be improved in the future.
Aspnes @cite_46 investigated the localization and localizability of a network in 2010. They defined the term and showed that it is sufficient and necessary condition for a WSN graph to be localized in 2D. Even though global rigidity is defined for all dimensions, the sufficient and necessary conditions for a WSN to be localized in 3D have not been found yet.
@cite_46
2004805323 2114533345 2110862165 2093172757
Abstract In the studies on the localization of wireless sensor networks (WSN), it has been shown that a network is in principle uniquely localizable if its underlying graph is globally rigid and there are at least d + 1 non-collinear anchors (in d -space). The high possibility of the loss of nodes or links in a typical WSN, specially mobile WSNs where the localization often needs to be repeated, enforces to not only have localizable network structures but also structures which remain localizable after the loss of multiple nodes links. The problem of characterizing robustness against the loss of multiple nodes, which is more challenging than the problem of multiple link loss, is being studied here for the first time, though there have been some results on single node loss. We provide some sufficient properties for a network to be robustly localizable. This enables us to answer the problem of how to make a given network robustly localizable. We also derive a lower bound on the number of the links such a network should have. Elaborating it to the case of robustness against the loss of up to 2 nodes, we propose the optimal network structure, in terms of the required number of distance measurements. In a wireless sensor network (WSN), connectivity enables the sensors to communicate with each other, while sensing coverage reflects the quality of surveillance. Although the majority of studies on coverage and connectivity in WSNs consider 2D space, 3D settings represent more accurately the network design for real-world applications. As an example, underwater sensor networks require design in 3D rather than 2D space. In this paper, we focus on the connectivity and k-coverage issues in 3D WSNs, where each point is covered by at least k sensors (the maximum value of k is called the coverage degree). Precisely, we propose the Reuleaux tetrahedron model to characterize k-coverage of a 3D field and investigate the corresponding minimum sensor spatial density. We prove that a 3D field is guaranteed to be k-covered if any Reuleaux tetrahedron region of the field contains at least k sensors. We also compute the connectivity of 3D k-covered WSNs. Based on the concepts of conditional connectivity and forbidden faulty sensor set, which cannot include all the neighbors of a sensor, we prove that 3D k-covered WSNs can sustain a large number of sensor failures. Precisely, we prove that 3D k-covered WSNs have connectivity higher than their coverage degree k. Then, we relax some widely used assumptions in coverage and connectivity in WSNs, such as sensor homogeneity and unit sensing and communication model, so as to promote the practicality of our results in real-world scenarios. Also, we propose a placement strategy of sensors to achieve full k-coverage of a 3D field. This strategy can be used in the design of energy-efficient scheduling protocols for 3D k-covered WSNs to extend the network lifetime. In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly In this paper, we address the problem of agent loss in vehicle formations and sensor networks via two separate approaches: (1) perform a ‘self-repair’ operation in the event of agent loss to recover desirable information architecture properties or (2) introduce robustness into the information architecture a priori such that agent loss does not destroy desirable properties. We model the information architecture as a graph G(V, E), where V is a set of vertices representing the agents and E is a set of edges representing information flow amongst the agents. We focus on two properties of the graph called rigidity and global rigidity, which are required for formation shape maintenance and sensor network self-localization, respectively. For the self-repair approach, we show that while previous results permit local repair involving only neighbours of the lost agent, the repair cannot always be implemented using only local information. We present new results that can be applied to make the local repair using only local information. We describe implementation and illustrate with algorithms and examples. For the robustness approach, we investigate the structure of graphs with the property that rigidity or global rigidity is preserved after removing any single vertex (we call the property as 2-vertex-rigidity or 2-vertex-global-rigidity, respectively). Information architectures with such properties would allow formation shape maintenance or self-localization to be performed even in the event of agent failure. We review a characterization of a class of 2-vertex-rigidity and develop a separate class, making significant strides towards a complete characterization. We also present a characterization of a class of 2-vertex-global-rigidity. Copyright © 2008 John Wiley & Sons, Ltd.