【作者】 刘伟；

【导师】 董恩清；

【作者基本信息】 山东大学 ， 通信与信息系统， 2015， 博士

【摘要】 无线传感器网络是一种由大量结构简单、廉价的传感器集成无线通信接口所组成的网络,它在环境监测、灾难救助、目标跟踪等领域都有广泛的应用前景。在这些应用中,传感器节点的自我定位非常重要,因为没有和具体的坐标联系在一起的监测信息通常是没有意义的。同时,如基于地理信息的路由等无线传感器网络协议也需要节点的位置信息作为支撑。因此节点定位问题是无线传感器网络的重要研究内容之一。根据是否需要测量节点之间的距离,无线传感器网络的节点定位方法可以划分为基于测距和基于非测距的两种方法。其中基于测距的方法,由于定位精度高在无线传感器网络节点定位中被广泛采用。不过基于测距的方法在定位过程中面临可能发生节点的翻转模糊的问题,而且,如果节点在定位过程中发生翻转模糊,就可能产生节点定位的雪崩效应,严重时甚至会导致整个网络节点的定位失效。因此,有必要采取一定的措施去判断节点是否会发生翻转模糊,从而减小其对整个网络定位过程的影响。无线传感器网络节点定位中的翻转模糊指的是,当参考节点(包括锚节点和已经定位的邻居节点)间的位置几乎共线(二维定位)或共面(三维定位)时,由于测距误差的存在,导致未知节点的定位存在两个关于某一条直线(二维定位)或平面(三维定位)成镜像关系的估计位置。目前,在无线传感器网络节点的定位中,针对翻转模糊的研究主要集中在两个方面：翻转模糊的检测方法和翻转模糊的处理方法。本文也将从以上两个方面开展无线传感器网络节点定位的翻转模糊研究。本文的主要工作和创新点如下：(1) 无线传感器网络节点二维定位中的翻转模糊检测方法研究目前,无线传感器网络节点二维定位中的翻转模糊检测方法主要可以分为三大类,即：鲁棒四边形检测方法、共线度检测方法和直线存在检测方法。其中,鲁棒四边形检测方法通过判断未知节点和三个参考节点组成的一个四边形是否满足一定的几何条件,来确定未知节点的定位是否会发生翻转模糊。根据定位过程中使用的参考节点的数量,无线传感器网络的节点定位方法可以分为三边定位方法和多边定位方法。三边定位方法只使用三个参考节点,多边定位方法则至少使用三个参考节点。由于使用的参考节点数量更多,多边定位方法一般更能得到较小的平均定位误差,因此在基于测距的无线网络的节点定位中,大多采用多边定位方法。鲁棒四边形检测方法通常只适用于三边定位方法,其用于多边定位方法中计算复杂度较大,而且检测效果较差。共线度检测方法和直线存在检测方法均适用于三边定位方法和多边定位方法。不过,由于共线度检测方法在检测的过程中,通常只考虑了参考节点的位置,而没有考虑未知节点的位置,因此,其检测效果不好。而直线存在检测方法同时考虑了参考节点和未知节点的位置,因此具有较好的检测结果。直线存在检测方法的主要原理是将节点翻转模糊问题等价为判断是否存在一条直线与若干圆(以参考节点为圆心,以参考节点到未知节点的测距误差绝对值的最大值为半径)都相交的EIL (Existence of Intersecting Line)问题。因此,直线存在检测方法主要是对EIL问题进行求解。针对目前求解EIL问题的公切线方法(Common Tangent Algorithm, CTA)计算复杂度较高的问题,本文采用正交投影理论对EIL问题进行表示,证明了该问题实际上可以等价为在二维空间中存在某一直线,如任意两个圆在该直线的正交投影线段有重叠部分时,就认为可能存在节点的翻转模糊。根据该结论,本文进而提出了一种基于正交投影检测节点翻转模糊的方法(Orthogonal Projection Algorithm, OPA)。由于该方法将EIL问题转化为一个角度计算问题,可以用坐标变换的方式简化计算过程。经理论分析和大量数据仿真证明本文提出的OPA方法与CTA方法的检测结果是等价的,但计算复杂度得到大幅度降低。(2)无线传感器网络节点三维定位中的翻转模糊检测方法研究据我们所知,至今为止还没有学者专门对无线传感器网络节点三维定位中的翻转模糊检测方法进行研究。而在实际应用中,传感器节点往往分布在三维空间内,需要得到节点的三维空间信息,如海洋、山地、森林及各种空间飞行器等。因此非常有必要研究节点三维定位中的翻转模糊检测方法。针对无线传感器网络节点三维定位中的翻转模糊检测问题,本文提出并证明了无线传感器网络节点三维定位中的翻转模糊检测问题可以等价为判断是否存在一个平面与若干球(以参考节点为球心,以参考节点到未知节点的测距误差绝对值的最大值为半径)都相交的EIP (Existence of Intersecting Plane)问题。为了求解EIP问题,本文提出并证明了EIP问题可以等价为在上述测距误差球中存在三个球的一个公切面,如该公切面与其余的球都相交时,就认为可能存在节点的翻转模糊。在此定理的基础上,本文进而提出了一种求解EIP问题的公切面检测方法(Common Tangent Plane Algorithm,CTPA),但是理论分析和仿真结果证明CTPA方法虽然具有较好的检测效果,但是计算复杂度太大。为了解决CTPA检测方法计算复杂度太大的问题,本文首先定义了三维空间中球到直线的正交投影的概念。该定义表示三维空间中,球有一条和直线平行的直径,从该直径的两个端点分别向该直线做垂线,两个垂足之间的线段称为球在该直线上的正交投影线段。根据上述的定义,我们提出并证明了EIP问题可以等价为在三维空间中存在某一直线,如任意两个球在该直线的正交投影线段有重叠部分时,就认为可能存在节点的翻转模糊。在此证明的基础上,本文进而提出了另外一种求解EIP问题的基于正交投影的检测方法(Orthogonal Projection Algorithm for Three-dimensional,OPA-3D)。理论分析和大量的仿真证明,OPA-3D方法在几乎获得与CTPA方法相同的检测结果的情况下,能够大大降低求解EIP问题的计算复杂度。(3)无线传感器网络节点定位中的翻转模糊处理方法研究对于在定位中检测出有可能发生翻转模糊的未知节点,研究翻转模糊检测方法的文献大多数采用的都是悲观的处理方式,即直接不对该未知节点进行定位,从而防止其影响后续未知节点的定位精度。这种处理方式虽然提高了节点的定位精度,但是也会降低网络中节点的定位数量,这在某些实际应用中是不可接受的。为此,有必要对翻转模糊的处理方法进行研究。根据算法的计算模式,节点定位算法可以分为集中式算法和分布式算法两类。集中式算法要把所有的数据信息传送到某个中心节点,由中心节点负责计算所有未知节点的位置信息。而分布式算法,未知节点只需与邻居节点进行通信,在节点自身处即可完成计算。由于集中式定位算法需要较大的通信开销,而且其扩展性能较差,因此,在无线传感器网络的节点定位过程中广泛使用的是分布式的定位算法。目前,提出的节点翻转模糊的处理方法大多数都是属于集中式的处理算法,分布式处理算法较少并且计算复杂度较大。本文提出了一种基于拓扑约束的分布式处理翻转模糊的定位方法(Distributed Localization Algorithm based on Topological Constraints, DLA-TC)。DLA-TC方法分为两个阶段。第一阶段对网络中所有的未知节点进行翻转模糊检测,检测方法采用本文提出的基于正交投影的检测方法(在节点二维定位和三维定位时分别采用OPA方法和OPA-3D方法),对检测出的不会发生翻转模糊的节点用最小二乘法进行定位。这一阶段的目的是为了对第二阶段的处理提供更多的拓扑约束。第二阶段,对于那些可能发生翻转模糊的节点,根据网络的拓扑约束生成一个目标函数,然后用粒子群优化方法(Particle Swarm Optimization,PSO)寻找目标函数的最小值,对其进行定位。仿真结果证明了无论是在节点二维定位中,还是在节点三维定位中,我们提出的DLA-TC方法在定位精度和节点定位率两个方面均能获得较好的效果。更多还原

【Abstract】 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.更多还原