Research On Flip Ambiguity In Wireless Sensor Networks Node Loealization

Wireless Sensor Networks (WSNs) consist of a large number of simple and inexpensive sensor devices equipped with wireless communication interface. WSNs have broad application prospects in environmental monitoring, disaster relief, target tracking, and other fields. In the practical application of WSNs, sensed data may be meaningless without relating to its physical location. Furthmore, some protocols of WSNs, such as routing based on geographic information also needs node location information. Therefore, node localization is one of the important research issues in WSNs.According to whether distance measurement is needed, node localization algorithms are generally divided into two categories:range-based and range-free. Due to the high positioning accuracy, the range-based algorithms have been widely used. However, a primary problem for the range-based algorithms is that flip ambiguity may occur in the process of node localization. Moreover, if flip ambiguity occurs, it could cause the avalanche effect, and results in significant degradation of the localization accuracy of the whole network. It is important for the localization process to identify possible flip ambiguity in the location estimates, and take some proper actions to prevent flip ambiguity.For an unknown node, due to the existence of ranging error, when a set of reference nodes (including anchor nodes and positioned neighbor nodes) are almost collinear (two-dimensional node localization) or almost coplanar (three-dimensional node localization), there is a probability that the unknown node can be reflected by a mirror formed from the reference nodes. The reflection process will cause a large localization error. That is just flip ambiguity of node localization. At present, the research on flip ambiguity mainly is divided into two categories:flip ambiguity detection algorithms and flip ambiguity processing algorithms. This paper will focus on flip ambiguity from the above two categories. In this paper, the main works and innovations are as follows:(1) Research on flip ambiguity detection algorithms for two-dimensional node localization in WSNsCurrently, flip ambiguity detection algorithms for two-dimensional node localization can be divided into three main categories:robust quadrilateral algorithms, collinear degree algorithms and existence of straight line algorithms. Among them, the robust quadrilateral algorithms are to construct a quadrilateral that is composed of the unknown node and three reference nodes, and then judges the quadrilateral whether satisfies certain geometrical conditions which the unknown node will not occur flip ambiguity. According to the number of reference nodes used in the process of localization, node localization algorithms are divided into two categories: trilateration localization and multilateration localization. Trilateration localization only adopts three reference nodes, while multilateration localization at least adopts three reference nodes. Due to more number of reference nodes, multilateration localization generally can get higher positioning accuracy. Therefore, multilateration localization usually is used in range-based nodes localization. The robust quadrilateral algorithms mainly are applied to trilateration localization, if they are used in multilateration localization, their computational complexity is high, and the detection effect is also poor.Collinear degree algorithms and existence of straight line algorithms are both applied to trilateration localization and multilateration localization. However, the collinear degree algorithms only consider the position of the reference nodes, without considering the location of the unknown node. Therefore, the detection effect of collinear degree algorithms is poor. The existence of straight line algorithms considers the positions of the reference nodes and the unknown nodes in the same time, thus they have better detection results.In the existence of straight line algorithms, flip ambiguity is equal to determine whether exists a straight line intersecting with all range error circles (the centers at reference nodes, the radii are equal to the maximum absolute value of range errors between reference nodes and unknown nodes) of reference nodes, which is called the existence of intersecting line (EIL) problem. Therefore, it is important to solve EIL problem in the existence of straight line algorithms. At present, the common tangent algorithm (CTA) is mainly used to solve EIL problem. In order to address the high computational complexity of CTA, by using the orthogonal projection method, we prove that EIL problem in fact is equal to determine whether exists a straight line, which enables any two circles to have overlapping orthogonal projection onto the line. According to this evidence, we propose an orthogonal projection algorithm (OPA) to slove EIL problem. OPA transforms EIL problem into an angle calculation problem, and uses the coordinate transformation to simplify the computational processes. Theoretical analysis and a great deal of data simulations show that OPA has exactly the same detection results with CTA, but the computational complexity is greatly reduced.(2) Research on flip ambiguity detection algorithms for three-dimensional node localization in WSNsAs far as we know, so far the researches on flip ambiguity detection algorithms for three-dimensional node localization in WSNs are still blank. However, In practical applications, the sensor nodes are often distributed in three-dimensional space, such as oceans, mountains, forests and various space vehicles and so on, which needs to get three-dimensional information about the nodes. Therefore, it is necessary to study flip ambiguity detection algorithms for three-dimensional node localization.In order to address flip ambiguity detection problem for three-dimensional node localization in WSNs, we have proposed and proved that flip ambiguity detection for three-dimensional node localization is equal to whether there is a plane intersecting with all range error spheres (the centers at reference nodes, the radii are equal to the maximum absolute value of range errors between reference nodes and unknown nodes) of the reference nodes, which is called the existence of intersecting plane (EIP) problem. In order to solve EIP problem, we have proposed and proved that EIP problem is equal to determine whether exists a common tangent plane of any three spheres that intersects with all ranging error spheres. According to this evidence, we further have proposed a common tangent plane algorithm (CTPA) to solve EIP problems. However, the theoretical analysis and the simulation results show that CTPA has better detection results, but the computational complexity is too high.In order to address the high computational complexity of CTPA, we firstly give a definition, which defines the orthogonal projection line segment of the sphere onto the straight line in three-dimensional space. In three-dimensional space, the sphere has a diameter that is parallel to the straight line. We draw two perpendicular lines of the straight line through two endpoints of the diameter respectively. The line segment between two perpendicular foots is called the orthogonal projection line segment of the sphere onto the straight line. Then, according to the definition, we have proposed and proved that EIP problem is equal to determine whether exists a straight line in three-dimensional space, which enables any two spheres to have overlapping orthogonal projection onto the line. On the basis of the evidence, we further have proposed an orthogonal projection algorithm (OPA-3D) for three-dimensional node localization. Theoretical analysis and a great deal of data simulations show that OPA-3D has almost the same detection results with CTPA, but the computational complexity is greatly reduced.(3) Research on flip ambiguity processing algorithms for node localization in WSNsFor the unknown nodes that may occur flip ambiguity, the literatures regarding to flip ambiguity detection algorithms mainly adopt the pessimistic processing approach, i.e., discard those positioning results with possible flip ambiguities, in order to avoid their effect on positioning accuracy of subsequent nodes. Although this approach improves the positioning accuracy, it reduces the number of the positioning nodes, which is not acceptable in some practical applications. Therefore, it is necessary to study flip ambiguity processing algorithms.In terms of computational paradigm, the localization algorithms can also be divided into centralized algorithms and distributed algorithms. The centralized algorithms require transmission of all range measurements or connectivity information between nodes to a sink node. The sink node is responsible for computing the location of all the unknown nodes. In the distributed algorithms, the unknown nodes only communicate with neighboring nodes and the whole task of node localization is completed by the unknown nodes themselves. Due to the centralized location algorithms require a large communication overhead, and their scalability is poor, the distributed algorithms are much more attractive in WSNs node localization. Currently, flip ambiguity processing algorithms mostly belong to the centralized algorithms. The distributed processing algorithms are relatively less and their computational complexity is high.We have proposed a distributed localization algorithm based on topological constraints (DLA-TC). DLA-TC is a two phase algorithm. In the first phase of DLA-TC, all the unknown nodes in the network need be executed flip ambiguity detection. The detection algorithm used is the orthogonal projection algorithm we propose (OPA is used in two-dimensional node localization and OPA-3D is used in there-dimensional node localization). For the unknown nodes that will not occur flip ambiguity, the least squares algorithm is used to locate them. The purpose of the first phase is to provide more topological constraints for the second phase. In the second phase of DLA-TC, for the unknown nodes that may occur flip ambiguity, according to the topological constraints, an objective function is created and Particle Swarm Optimization algorithm is used to find the minimum value of the objective function in order to locate those unknown nodes. The simulation results proved that either in two-dimensional node localization or in three-dimensional node localization, DLA-TC can obtain better results both in the positioning accuracy and the number of node localization.