刘　伟，董恩清，宋　洋

(山东大学(威海)机电与信息工程学院，山东威海264209)



无线传感器网络节点三维定位的翻转模糊检测

刘伟，董恩清，宋洋

(山东大学(威海)机电与信息工程学院，山东威海264209)

摘要:为了解决基于测距的无线传感器网络节点三维定位中可能会发生翻转模糊的问题，本文提出并证明了节点三维定位的翻转模糊检测问题，可以等价为判断是否存在一个平面和所有参考节点的测距误差球都相交的问题(Existence of Intersecting Plane，EIP)．为了求解EIP问题，本文进一步提出了公切面法(Common Tangent Plane，CTP)和正交投影法(Orthogonal Projection，OP)两种求解方法．CTP方法采用的是边界检测原理，OP方法则将EIP问题转化为一个角度计算问题，并用坐标变换的方式来求解．经过理论分析和大量的仿真证明，CTP方法虽然具有较好的检测效果，但是计算复杂度太大;而OP方法在几乎获得与CTP方法相同的检测结果的情况下，能够大大降低求解EIP问题的计算复杂度．

关键词:无线传感器网络;节点三维定位;翻转模糊;公切面;正交投影

1　引言

节点定位技术［1～5］是无线传感器网络实际应用的重要支撑技术之一．无线传感器网络节点的定位过程就是未知节点通过与锚节点(事先已知自身位置的节点)或已经完成定位的未知节点通信，获得相关信息并采用一定的定位方法求出自身位置的过程．根据是否依靠测量距离，节点定位方法可以划分为基于测距和无需测距的两种方法［6］．其中基于测距的方法，由于定位精度高在无线传感器网络节点定位中被广泛采用．不过基于测距的方法在定位过程中可能产生节点的翻转模糊［7～10］，并且，如果定位过程中发生翻转模糊，就可能引起节点定位的雪崩效应，导致整个网络节点的定位失效．因此，有必要采取一定的措施去判断节点翻转模糊［11，12］是否会发生，从而减小其对整个网络节点定位过程的影响．

依据信息处理的实现方式，无线传感器网络节点定位方法可以划分为集中式和分布式两种方法．集中式方法需要中心节点的参与，其扩展性能不好，而分布式方法只需在未知节点自身处完成定位过程，扩展性能好．因此，相对于集中式方法，分布式方法被广泛地应用在无线传感器网络节点定位中［13］．而本文提出的翻转模糊检测方法也主要适用于分布式的定位方法．

目前，针对无线传感器网络节点定位中翻转模糊检测的研究都是集中在二维空间．在二维空间中主要采用鲁棒四边形的方法来检测节点的翻转模糊［14，15］．鲁棒四边形的方法通过判断未知节点和三个参考节点(包括邻居锚节点和已完成定位的邻居节点)组成的一个四边形是否满足一定的几何条件(鲁棒性条件)，来确定未知节点的定位是否会发生翻转模糊．文献［16］对上述的四边形进行几何分析，量化其满足鲁棒性条件的概率分布．在实际定位中，由于未知节点到参考节点的三个测量距离均存在误差，而文献［14～16］中的鲁棒四边形方法在理论分析时仅假设其中的一个测距有误差，而另外两个测距是精确的，这是不符合实际情况的．为此文献［17］对三个测距均有误差的情况进行了理论分析，并提出了一种改进算法．文献［18］则通过增加一个参考节点的方式来组成四个四边形，然后采用文献［17］中的方法判断这四个四边形的鲁棒性，只有当这些四边形全部满足鲁棒性条件才能认为未知节点在定位时不会发生翻转模糊．

在二维空间中，判断节点翻转模糊的鲁棒四边形方法一般只适用于采用三个参考节点的三边定位．相对于三边定位方法，在节点的二维定位中使用多于三个参考节点的多边定位方法更能得到较小的平均定位误差，因此在基于测距的无线传感器网络的节点定位中，大多采用多边定位方法．目前针对二维空间多边定位方法中节点翻转模糊问题研究的还是非常少，虽然文献［17］首次提出了一种适合于多边定位的鲁棒四边形方法，但是其计算复杂度不仅太大，而且判断效果较差．文献［19］将节点二维定位中的翻转模糊问题等价为判断是否存在一条直线和若干圆(以参考节点为圆心，以参考节点到未知节点的测距误差绝对值的最大值为半径)都相交(Existence of Intersecting Line，EIL)问题，并取得了较好的检测效果．

目前，在二维空间中，对于检测出在定位中有可能发生翻转模糊的未知节点，大多数采用的是悲观的处理方式，即直接不对该未知节点进行定位，从而防止其影响后续未知节点的定位精度［8，10，16～19］．这种处理方式虽然提高了节点的定位精度，但是也会降低节点的定位数量，这在某些实际应用中是不可接受的．为此，研究者们提出了一些乐观的处理方式．文献［20］提出了一种鲁棒半正定方法用来处理翻转模糊的节点．文献［21］使用的是一种二阶段的模拟退火方法．文献［22］提出了一种OFA(Optimistic localization scheme with Flip Avoidance)方法，该方法利用计算出的两个节点位置(真实点位置和节点翻转模糊位置)与其他邻居节点的相互通信关系来消除翻转模糊节点．文献［23］则提出了一种距离冲突方法用于处理节点的翻转模糊．

据我们所知，至今为止还没有学者专门对无线传感器网络节点三维定位的翻转模糊检测方法和处理方法进行研究．而在实际应用中，传感器节点往往分布在三维空间内，需要得到节点的三维空间信息，如海洋、山地、森林及各种空间飞行器等．由于计算复杂度等原因，如将目前大多数二维定位中的检测和处理翻转模糊的方法简单地扩展到三维是不合适的，因此非常有必要研究三维节点定位的翻转模糊检测和处理方法．

在本文中，我们只是针对无线传感器网络节点三维定位中的翻转模糊检测问题进行讨论，至于无线传感器网络节点三维定位的翻转模糊处理问题将是我们下一步研究的方向．借鉴文献［19］的思想，我们提出并证明了无线传感器网络节点的三维定位翻转模糊检测问题可以等价为判断是否存在一个平面和若干球(以参考节点为球心，以参考节点到未知节点的测距误差绝对值的最大值为半径)都相交(Existence of Intersecting Plane，EIP)问题．为了求解EIP问题，本文提出了公切面法(Common Tangent Plane，CTP)和正交投影法(Orthogonal Projection，OP)两种求解方法．

2　三维定位中节点的翻转模糊问题

无线传感器网络节点三维定位中的翻转模糊问题指的是当参考节点间的位置几乎共面时，由于测距误差的存在，导致未知节点的定位存在两个关于某一个平面成镜像关系的估计位置．在三维空间中无线传感器网络的节点定位至少需要四个不共面的参考节点．图1中节点A、B、C和D是位置已知的四个参考节点．其中A、B和C三点确定了一个平面m分别是它们到未知节点的测量距离．根据上述A、B、C三点和三个测距，我们可以求得未知节点可能所在的两个位置E和E'，它们是以A、B和C为球心，分别以为半径的三个球的交点，且E和E'关于平面m成镜像关系．O是直线EE'与平面m的交点．假设未知节点的正确位置为E，D到E和E'两点的距离分别为dde和d'de．D点到未知节点的测量距离用来选择未知节点的估计位置，其选择的标准是更接近dde(选择E)还是更接近d'de(选择E')．当A、B、C、D四点几乎共面时，dde和d'de相差不大．由于测距误差的存在，就有可能错误地选择E'作为未知节点E的估计位置．如果做出错误的选择，且让这种错误定位的未知节点参与其它未知节点的定位，可能导致整个网络节点的定位失效．

3　EIP问题的提出

借鉴文献［19］的思想，我们下面提出并证明了无线传感器网络节点的三维定位翻转模糊检测问题可以等价为判断是否存在一个平面和若干球(以参考节点为球心，以参考节点到未知节点的测距误差绝对值的最大值为半径)都相交(EIP)的问题．

无线传感器网络节点三维定位中的多边定位方法需用k(k≥4)个参考节点来定位一个未知节点．已知数据可以用一个集合表示，其中，pi表示第i个参考节点的位置，表示第i个参考节点到未知节点的测量距离，其中di和εi分别表示第i个参考节点到未知节点的真实距离和测距误差．如图2所示将每个参考节点沿着各自的测距方向平移εi至一个新的位置，可以得到另一个集合M'．与集合M不同，集合M'没有测距误差．因此，在集合M'中，如果平移后的k个位置不共面，那么，在未知节点定位过程中肯定不会发生翻转模糊．

在实际情况下，测距误差εi是未知的，所以无法求出参考节点平移后的位置．不过εi的取值是有界限的，故可以估计所处的区域范围．若δi表示未知节点到第i个参考节点测距误差绝对值的最大值，即δi= max|εi|，i =1，2，…，k．那么，如图2所示必然在以pi为球心，δi为半径的球内．可以用集合S ={〈pi，δi〉}，i =1，2，…，k表示这k个球．对于集合S，若存在一个平面和k个球都相交，那么pi平移后的位置珓pi有可能共面，则会发生节点的翻转模糊;否则，珓pi肯定不会共面，也不会发生翻转模糊．所以，翻转模糊问题可以等价为判断是否存在一个平面和若干球都相交(EIP)问题．

3.1三维定位中检测翻转模糊的CTP方法

借鉴文献［19］在二维空间中使用CT(Common Tangent)方法求解EIL问题的思想，这里我们将CT方法扩展为适合在三维空间中求解EIP问题的CTP方法．该方法采用边界检测的方式来求解EIP问题．其理论基础来自于我们提出的定理1．

定理1给定一个球的集合S ={〈pi，δi〉}，i =1，2，…，k．EIP问题的充要条件是在集合S中存在三个球的一个公切面，该公切面与其余的球都相交．

证明定理1的必要性是显而易见的，因此，只需对其充分性进行证明．

我们用一个集合N(S)表示与集合S中所有的球都相交的平面．这样EIP问题实际上就是判断集合N(S)是否为空集．如图3(a)所示，当N(S)不为空集时，N(S)中的一个边界平面n1(将要偏离和所有球都相交条件的平面)必然与其中的一个球(图3中为球A)相切，而与其余的球都相交．

我们将平面n1围绕球A的球心旋转(保证在旋转的过程中平面与球A一直相切)，在旋转的过程中，各球与平面的交线所包围区域的面积肯定会有所变化(增大或减小)，当首先出现有某一个球(假设为球B)与平面的交线所包围区域的面积等于0时，停止旋转，这时我们可以得到如图3(b)所示的平面n2，此时平面n2与球A和球B均相切，而且与集合S中除了球A和球B以外的其余球都相交．我们再将平面n2围绕球A和球B的两个球心的连线旋转(保证在旋转的过程中平面与球A、球B一直相切)，当首先出现某一个球(假设为球C)与平面的交线所包围区域的面积最先等于0时，停止旋转，这时我们可以得到如图3(c)所示的平面n3．平面n3就是球A、球B和球C的一个公切面，而且与集合S中除了球A、球B和球C以外的其余球都相交．定理1的充分性得到了证明．

根据定理1，我们提出了一种CTP方法求解EIP问题．CTP方法的流程图如图4所示．从图4中可以看出，CTP方法对集合S中任意三个球组成的一个子集，都需要求出其公切面，然后再判断这些公切面与其余球的相交性．求解公切面的计算复杂度为O (k3)，判断公切面与球相交性的计算复杂度为O(k)．因此，CTP方法总的计算复杂度为O(k4)，其计算复杂度非常高．

3.2三维定位中检测翻转模糊的OP方法

由于CTP方法的计算复杂度太高，为了降低求解EIP问题的计算复杂度，我们下面提出了一种计算复杂度较低的OP方法．

3．2．1基本定义及基本定理

在详细介绍OP方法之前，我们需要给出和证明如下一个基本定义和两个基本定理．

下面给出的基本定义是有关三维空间中球到直线的正交投影的概念．

定义假设三维空间中存在一个球和一条直线，那么这个球有一条直径必然和该直线平行．从这条直径的两个端点分别向该直线做垂线．两个垂足之间的线段称为球在该直线上的正交投影线段．

如图5所示，根据上面的定义，线段AB就是球O在直线l上的正交投影线段，且其长度等于该球的直径．

根据上面的定义，我们给出如下基本定理及其证明．

定理2假设在三维空间中存在一条直线和经过该直线的任意一个平面，那么可得到球在该平面上的正交投影圆，这个正交投影圆在该直线上的正交投影线段与球在该直线上的正交投影线段是等价的．

证明如图6所示，三维空间中有一个球O和一条直线l，直线l在平面p内．线段AB是球O的直径，且AB∥l．圆O'是球O在平面p上正交投影所得到的圆．线段CD是线段AB在平面p上的正交投影线段．

若线段MN为圆O'在直线l上的正交投影线段．那么MN⊥CM．因为线段CD是线段AB在平面p上的正交投影线段，所以线段AC垂直于平面p，即MN⊥AC．因此，MN垂直于平面ACM．由此可以得出MN⊥AM．同理，可得出MN⊥BN，即线段MN是球O在直线l上的正交投影线段．

若线段MN为球O在直线l上的正交投影线段．那么MN⊥AM．因为线段CD是线段AB在平面p上的正交投影线段，所以线段AC垂直于平面p，即MN⊥AC．因此，MN垂直于平面ACM．由此可以得出MN⊥CM．同理，可得出MN⊥DN，即线段MN是圆O'在直线l上的正交投影线段．

下面的基本定理是文献［24］中给出的一条定理，该定理给出了二维空间中存在与所有圆都相交的直线的充要条件．

定理3在二维空间中给定一个圆的集合Q ={〈pi，δi〉}，i =1，2，…，k．其中pi表示圆心，δi表示圆的半径，k表示圆的个数．二维空间中存在一条直线与集合Q中所有的圆都相交的充要条件是空间中存在一条直线，使集合Q中的任意两个圆在该直线上的正交投影线段有重叠部分．

3．2．2 OP方法的理论基础

OP方法的理论基础来自于下面提出并证明的定理4．该定理巧妙地给出了EIP问题的一个充要条件．

定理4给定一个球的集合S ={〈pi，δi〉}，i =1，2，…，k．EIP问题的充要条件是三维空间中存在一条直线，集合S中任意两个球在该直线上的正交投影线段有重叠部分．

证明

(1)必要性证明

如图7所示，假设三维空间中存在k个球G1，G2，…，Gk和一条直线l，其中任意两个球在直线l上的正交投影线段有重叠部分．

任取一个经过直线l的平面P，从而可以得到这k个球在平面P上的正交投影圆O1，O2，…，Ok．由于任意两个球在直线l上的正交投影线段有重叠部分，根据定理2的等价原理，平面P上的这k个圆中的任意两个圆在直线l上的正交投影线段有重叠部分．由定理3可知，在平面P上必然有一条直线m和这k个圆都相交．过直线m作一个平面Q，使Q⊥P．那么，平面Q必然和这k个球都相交．

(2)充分性证明

从另一个角度看图7，假设三维空间中存在k个球G1，G2，…，Gk和一个平面Q，平面Q和这k个球都相交．

作平面Q的任意一个垂直平面P，从而得到k个球在平面P上的正交投影圆O1，O2，…，Ok和平面Q在平面P上的正交投影直线m．由于平面Q和k个球都相交，所以在平面P上，直线m必然和k个正交投影圆均相交．根据定理3，在平面P上必然有一条直线l，使得这k个圆中的任意两个圆在直线l上的正交投影线段有重叠部分．由定理2的等价原理可知，k个球中的任意两个球在直线l上的正交投影线段有重叠部分．

3．2．3 OP方法的计算过程

根据定理4，我们提出了一种求解EIP问题的OP方法．OP方法的核心就是在三维空间中寻找满足条件的直线．根据正交投影的性质，对于一系列相互平行的直线来说，EIP问题中的k个球在这些直线上的正交投影线段的相交性是完全一致的．因此OP方法实际是寻找直线的方向向量．不失一般性，我们假设寻找的直线经过坐标原点．我们提出的OP方法把寻找直线方向向量的问题转化为了角度计算问题，转化的理论根据是如下提出和证明的定理5．

定理5对于三维空间中的一条过坐标原点的直线，可以得到其到两个坐标平面的两条正交投影直线，已知这两条正交投影直线与这两个坐标平面的共同坐标轴正方向之间的两个夹角，就能够确定这条直线．

证明如图8所示，直线l经过坐标原点，直线l1和l2分别是直线l到坐标平面xOy和xOz上的正交投影，它们与x轴正方向的夹角分别为α和β．

由于直线l经过坐标原点，所以它到两个坐标平面的正交投影l1和l2也经过坐标原点．已知直线l1和l2与x轴正方向的夹角α和β，就可以确定这两条直线l1和l2．我们过直线l1作坐标平面xOy的一个垂直平面P，那么直线l在平面P内．同理，我们过直线l2做坐标平面xOz的一个垂直平面Q，那么直线l也在平面Q内．所以平面P和平面Q的交线就是直线l．

根据定理5，OP方法可以转化为寻找满足条件的两个夹角的问题．在EIP问题中，假设各球的球心坐标为(xi，yi，zi)，半径为ri，i = 1，2，…，k．若我们所寻找的直线l在坐标平面xOy和xOz上的正交投影l1和l2与x轴正方向的夹角分别为α和β(0≤α，β＜π)．为了简便计算，本文采用坐标变换的方式求出各球在直线l上的正交投影线段．坐标变换的目的是使新坐标系的横坐标轴与直线l重合，需要两步变换．

在如图9(a)所示的原始坐标系中，直线l1和l2分别是直线l在坐标平面xOy和xOz上的正交投影，它们与x轴正方向的夹角分别为α和β．第1步坐标变换将原始坐标系Oxyz围绕z轴旋转角度α，得到如图9(b)所示的坐标系O'x'y'z'，此时，直线l位于坐标平面x'O' z'内，而直线l到坐标平面x'O'y'的正交投影l1'与x'轴重合．第2步坐标变换将坐标系O'x'y'z'围绕y'轴旋转角度β，得到如图9(c)所示的坐标系O″x″y″z″，此时，直线l与x″轴重合．

由坐标变换的公式，可以得出各球的球心在坐标系O″x″y″z″上的坐标为:

而各球心到直线l上的正交投影点在坐标系O″x″y″z″上的坐标为:

因此若任意两个球在直线l上的正交投影线段有重叠部分，则必须满足:

其中:

式(2)表示的是一个二元非线性不等式组．目前一般采用最优化的方法对多元非线性不等式组进行求解［25～27］．采用最优化方法求解需要对式(2)作一个变换，可以得到:

假设:

式(3)可以用式(4)来表示．

我们令φl(X) = max(0，fl(X) )，那么:

由式(5)可知φl(X)0，因此最优化方法求解该不等式组的目标函数可以作如下的设置:

粒子群优化方法［28］(Particle Swarm Optimization，PSO)是一种搜索性能较好的优化方法，它具有收敛速度快、可调参数少、易于实现等优点．本文采用PSO方法对式(2)中不等式组进行求解，其求解步骤如下:

①初始化各参数，包括加速常数c1和c2，最大迭代次数Tmax，粒子的速度范围［vmin，vmax］，粒子的数目s和惯性权重的范围［ωmin，ωmax］．

⑤分别根据式(7)、式(8)和式(9)更新惯性权重、粒子的速度和粒子的位置．

式(8)中，r1和r2为均匀分布在［0，1］区间的随机数．在更新过程中，如果将其置为vmin，如果将其置为vmax;如果∉［0，π］，则在［0，π］内随机生成

⑥让迭代次数t = t + 1，然后检验t是否小于Tmax，若条件满足转入步骤④，否则，说明不等式组无解，未知节点的定位不会发生翻转模糊．

最优化方法的一个缺点就是在搜索过程中不可避免地会陷入到局部最优值，无法找到全局最优．因此对于本身有解的不等式组，用最优化方法求解可能会出现不等式组无解的情况．这样会导致把有可能发生翻转模糊的未知节点误判为不会发生翻转模糊．为了降低误判率，对于检测出在定位过程中不会发生翻转模糊的未知节点，可以使用q(q1)次PSO方法搜索不等式组的解，只有当这q次都搜索不到解时，才认为未知节点的定位不会发生翻转模糊．

OP方法的流程图如图10所示．从图10中可以看出，对集合S中的每一对球，OP方法都要按照式(2)列出一个不等式，并将这些不等式合成一个不等式组，再用PSO方法进行求解．因此，OP方法总的计算复杂度仅为O(k2)．而CTP方法的计算复杂度为O(k4)，相比之下，其计算复杂度远小于CTP方法．

4　仿真分析

为了验证CTP和OP方法的性能，我们在一台CPU 为Intel Core i7-3770(3.40GHz)，内存为16GB的计算机上，用Matlab R2013a软件对其进行了仿真分析．采用的测距方法是RSSI(Received Signal Strength Indication)，其测距误差［29］可以表示为e = d×10σ/10n，其中e表示测距误差，d表示节点间的真实距离，n为路径损耗指数(文中设定为4)，σ表示高斯白噪声(文中均值为0，标准差为4)．仿真时PSO方法各参数的取值如下:

最大迭代次数: Tmax= 20;粒子的数目: s = 50;粒子的速度: vmin=－1，vmax= 1;惯性权重:ωmin= 0.4，ωmax= 0.9;加速常数: c1= c2=2．

4.1检测结果的对比分析

我们在边长为100m的正方体网络区域中放置了125个节点，其中20个为锚节点．仿真的节点分布分别为均匀分布和随机分布两种类型，通信半径结合节点间距确定为50m．均匀分布时，节点间距离是20m(存在0～2m的随机误差)．

图11是CTP方法和OP方法(q =1)对上述网络检测结果的对比．从图中可以看出，除了在节点随机分布时，有一个节点的检测结果不同(CTP方法检测可能发生翻转模糊，OP方法检测不会发生翻转模糊)以外，其余的节点检测结果是完全相同的．导致OP方法与CTP方法检测结果出现不同的原因是OP方法在用PSO方法求解不等式组时，PSO方法在搜索过程中陷入到局部最优值，从而错误得出了不等式组无解的结论．实际上从第3节可以看出，OP方法和CTP方法的基本原理是一致的，而且从图11中可以看出，两种检测方法检测结果不一致的比例(OP方法的误判率)非常的小．

为了测试OP方法的误判率，我们对上述网络进行了100次的仿真．表1和表2分别是节点均匀分布和随机分布时TCP方法和OP方法对网络进行100次检测结果的对比情况．对于未知节点的检测，我们用0表示可能发生翻转模糊，用1表示不会发生翻转模糊．表1和表2中q表示OP方法中求解不等式组时使用PSO方法的次数; N1表示CTP方法和OP方法检测结果均为0的未知节点的数目; N2表示CTP方法检测结果为0，OP方法检测结果为1的未知节点的数目; N3表示CTP方法检测结果为1，OP方法检测结果为0的未知节点的数目; N4表示CTP方法和OP方法检测结果均为1的未知节点的数目; N5表示由于参考节点小于4个，而无法定位的未知节点的数目; P表示OP方法的误判率，即:

表1　节点均匀分布检测结果对比

表2　节点随机分布检测结果对比

从表1和表2中可以看出，在所有情况下，N3均为0，因此CTP方法和OP方法检测结果的不同仅体现在N2上，即CTP方法检测结果为未知节点可能会发生翻转模糊，而OP方法的检测结果为未知节点不会发生翻转模糊．这和我们上面的理论分析是一致的．另外，从表中还可以看出，适当地增加使用PSO方法的次数q，可以降低误判率．不过随着q的增加，所需要的检测时间也增加，当q等于4时，误判率已经很低了，而且q大于4时，误判率的降低已经不明显了，因此，在实际应用中我们可以选择q的值为4．

4.2平均定位误差的对比分析

下面，我们在节点定位的过程中加入翻转模糊检测，对节点分别经过CTP方法和OP方法定位后得到的平均定位误差进行仿真对比分析．本文我们主要是对TCP方法和OP方法的检测结果进行对比，所以在仿真中对检测出的可能发生翻转模糊节点的处理采用相对简单的悲观处理方式．

球的数量和各球的半径是EIP问题中的两个主要的变量．由于在本文的仿真环境中，节点的密度保持不变，所以此仿真环境下它们在无线传感器网络三维节点定位问题中分别等价于节点的通信半径和单位检测误差．因此，为了研究这两个变量对CTP方法和OP方法检测结果的影响，我们分别采用不同节点通信半径和不同的单位检测误差，仿真分析网络的平均定位误差的变化．文中的平均定位误差采用如下公式计算:

式(11)中，e表示平均定位误差，N表示仿真的网络数目(本文为100个)，(xi，yi，zi)和(^xi，^yi，^zi)分别表示节点i的真实坐标和估计坐标，Vn表示在第n个网络中能够定位的节点的集合，|Vn|表示集合Vn中节点的数量，R表示通信半径．本次仿真网络的各参数与4.1节相同．

图12和图13分别表示在不同通信半径和不同单位检测误差的情况下，对节点分别经过无翻转模糊检测、CTP方法检测和OP方法检测(q分别为1和4)以后得到的平均定位误差曲线．其中，图12(a)和图13 (a)为节点均匀分布，图12(b)和图13(b)为节点随机分布．图12中单位检测误差为0.5m，图13中通信半径为50m．从图12和图13中可以看出，与不进行任何翻转模糊检测相比，加入翻转模糊检测后，由于去除了有可能发生翻转模糊的节点引入的高定位误差，而且避免了翻转模糊节点对其它未知节点定位的影响，所以得到的平均定位误差明显更小，也就是相对提高了整体网络节点的定位精度．另外，还可以看出，由于CTP方法和OP方法(q分别为1和4)的检测结果差别不大，导致其得到的三条平均定位误差曲线几乎重合在一起．

为了更加清晰地展现CTP方法和OP方法(q分别为1和4)检测结果的差别，下面我们把图12和图13中无翻转模糊检测的曲线去除，可以得到图14和图15所示的结果．从图14和图15中可以看出在两种节点分布下，当q =4时，OP方法和CTP方法进行翻转模糊检测后得到的平均定位误差曲线几乎是完全重合的，而当q =1时，OP方法和CTP方法检测得到的平均定位误差也非常接近．这就进一步说明了OP方法和CTP方法对翻转模糊的检测结果相差不大，当q =4时，两者几乎能够取得相同的检测结果．

4.3检测时间的对比分析

为了比较CTP方法和OP方法的计算复杂度，我们对它们的检测时间进行了仿真，仿真采用4.2节中不同通信半径的网络及其参数．

表3和表4分别是节点均匀分布和随机分布时，100个不同网络仿真的计算时间平均值．在表中，R和N分别表示节点的通信半径和参考节点的平均数，TCTP表示CTP方法检测一次所需的平均时间，TOP1表示q =1时，OP方法检测一次所需的平均时间，TOP4表示q = 4时，OP方法检测一次所需的平均时间，β1表示q =1时，OP方法与TCP方法所需时间的比值，即β1= TCTP/TOP1，β4表示q =4时，OP方法与TCP方法所需时间的比值，即β4= TCTP/TOP4．从表3和表4中可以看出，在两种节点分布的情况下，随着参考节点数目N的增加，CTP方法检测的平均时间TCTP增加的非常快，而OP方法检测的平均时间TOP1和TOP4则增加比较缓慢．另外除了通信半径为40m时，TOP4大于TCTP之外，其余情况下，TOP1和TOP4均小于TCTP，而且随着参考节点数量的增加，β1和β4的值越来越大，因此，当参考节点数量较多时，OP方法明显地更适用．这就说明了与CTP检测方法相比，OP方法在取得了几乎相同判断结果的同时，大大降低了计算复杂度．

表3　节点均匀分布时间对比

表4　节点随机分布时间对比

5　结论

节点的翻转模糊是基于测距的无线传感器网络节点定位过程中需要解决的一个关键问题．针对目前对节点翻转模糊检测方法的研究都是集中在二维空间，缺乏对三维空间检测方法研究的现状．本文将无线传感器网络节点的三维定位翻转模糊检测问题等价为EIP问题，并提出了CTP和OP两种检测方法．CTP方法有较好的检测效果，不过其计算复杂度太大．OP方法的检测效果虽然不如CTP方法，但是其具有计算复杂度较低的优点，并且OP方法的检测结果与CTP方法的检测结果相差很小，通过增加OP方法中使用PSO方法的次数q，两者的差别越来越小，当q = 4时，OP方法和CTP方法几乎能取得相同的检测结果．

对于乐观的定位方法来说，检测出有可能发生翻转模糊的节点之后，需要采用一些方法对其进行处理．而目前对节点翻转模糊处理方法的研究都是集中在二维空间，缺乏对三维空间处理方法的研究．由于计算复杂度等原因，如将目前大多数二维定位中处理翻转模糊的方法简单地扩展到三维是不合适的，因此，下一步我们将对无线传感器网络节点三维定位的翻转模糊处理方法进行研究．

参考文献

［1］H J Shao，X P Zhang，et al．Efficient closed-form algorithms for AOA based self-localization of sensor nodes using auxiliary variables［J］．IEEE Transactions on Signal Processing，2014，62(10) : 2580－2594．

［2］J A Jiang，X Y Zheng，et al．A distributed RSS-based localization using a dynamic circle expanding mechanism［J］．IEEE Sensors Journal，2013，13(10) : 3754－3766．

［3］N Deshpande，E Grant，et al．Target Localization and autonomous navigation using wireless sensor networks-a pseudogradient algorithm approach［J］．IEEE Systems Journal，2014，8(1) : 93－103．

［4］Y Z Chai，E Q Dong．A three-dimensional localization algorithm for wireless sensor networks based on the BFGS optimization［A］．Proceedings of the 17th European Wireless Conference［C］．Vienna: VDE，2011．676－680．

［5］E Q Dong，Y Z Chai，et al．A novel three-dimensional localization algorithm for Wireless Sensor Networks based on Particle Swarm Optimization［A］．Proceedings of the 18th International Conference on Telecommunications［C］．Ayia Napa: IEEE，2011．55－60．

［6］N Salman，M Ghogho，et al．Optimized low complexity sensor node positioning in wireless sensor networks［J］．IEEE Sensors Journal，2014，14(1) : 39－46．

［7］T Eren，O K Goldenberg，et al．Rigidity，computation，and randomization in network localization［A］．Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies［C］．Hong Kong: IEEE，2004．2673－2684．

［8］J Aspnes，T Eren，et al．A theory of network localization ［J］．IEEE Transactions on Mobile Computing，2006，5 (12) : 1663－1678．

［9］R Connelly．Generic global rigidity［J］．Discrete and Computational Geometry，2005，33(4) : 549－563．

［10］A Kannan，B Fidan，et al．Use of flip ambiguity probabilities in robust sensor network localization［J］．Wireless Networks，2011，17(5) : 1157－1171．

［11］A Kannan，B Fidan，et al．Derivation of flip ambiguity probabilities to facilitate robust sensor network localization ［A］．Proceedings of Wireless Communications and Networking Conference［C］．Budapest: IEEE，2009．1－6．

［12］A Kannan，B Fidan，et al．Robust distributed sensor network localization based on analysis of flip ambiguities ［A］．Proceedings of Global Telecommunications Conference［C］．New Orleans: IEEE，2008．1－6．

［13］Q J Shi，C．He，et al．Distributed wireless sensor network localization via sequential greedy optimization algorithm ［J］．IEEE Transactions on Signal Processing，2010，58 (6) : 3328－3340．

［14］D Moore，J Leonard，et al．Robust distributed network localization with noisy range measurements［A］．Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems［C］．Baltimore: ACM，2004．50 －61．

［15］F Sittile，M Spirito．Robust localization for wireless sensor networks［A］．Proceedings of the 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks［C］．San Francisco: IEEE，2008．46－54．

［16］A Kannan，B Fidan，et al．Analysis of flip ambiguities in distributed network localization［A］．Proceedings of Information，Decision and Control［C］．Adelaide: IEEE，2007．193－198．

［17］A Kannan，B Fidan，et al．Analysis of flip ambiguities for robust sensor network localization［J］．IEEE Transactions on Vehicular Technology，2010，59(4) : 2057－2070．

［18］D S Chen，X Y Li，et al．An improved quadrilateral localization algorithm for wireless sensor networks［A］．Proceedings of IEEE/ICME International Conference on Complex Medical Engineering［C］．Harbin: IEEE，2011．268－273．

［19］X Wang，Z Yang，et al．Beyond rigidity: obtain localizability with noisy ranging measurement［J］．International Journal of Ad Hoc and Ubiquitous Computing: special issue on Wireless Network Algorithm and Theory，2011，8 (1) : 114－124．

［20］S Severi，G Abreu，et al．Understanding and solving flipambiguity in network localization via semidefinite programming［A］．Proceedings of Global Telecommunications Conference［C］．Honolulu: IEEE，2009．1－6．

［21］A Kannan，G Q Mao，et al．Simulated annealing based wireless sensor network localization with flip ambiguity mitigation［A］．Proceedings of the 63rd IEEE Vehicular Technology Conference［C］．Melbourne: IEEE，2006．1022－1026．

［22］X P Wang，Y H Yang，et al．OFA: An optimistic approach to conquer flip ambiguity in network localization［J］．Computer Networks，2013，57(6) : 1529－1544．

［23］Q J Xiao，B Xiao，et al．Iterative localization of wireless sensor networks: an accurate and robust approach［J］．Computer Communications，2012，35(13) : 608－621．

［24］W Liu，E Q Dong，et al．An improved flip ambiguity detection algorithm in wireless sensor networks node localization［A］．Proceedings of the 21st International Conference on Telecommunications［C］．Lisbon: IEEE，2014．206－212．

［25］J B Jian，X L Zhang，et al．A new finitely convergent algorithm for systems of nonlinear inequalities［J］．Applied Mathematics Letters，2007，20(4) : 405－411．

［26］C He，C F Ma．A smoothing self-adaptive Levenberg-Marquardt algorithm for solving system of nonlinear inequalities［J］．Applied Mathematics and Computation，2010，216 (10) : 3056－3063．

［27］M Sahba．On the solution of nonlinear inequalities in a finite number of iterations［J］．Numerische Mathematik，1985，46(2) : 229－236．

［28］R V Kulkarni，G K Venayagamoorthy．Particle swarm optimization in wireless-sensor networks: a brief survey［J］．IEEE Transactions on Systems，Man，and Cybernetics，Part C: Applications and Reviews，2011，41(2) : 262－267．

［29］M Rahman，L Kleeman．Paired measurement localization: a robust approach for wireless localization［J］．IEEE Transactions on Mobile Computing，2009，8 (8) : 1087 －1102．

刘伟男，1979年出生于山东兖州．2009年于昆明理工大学获得硕士学位，2010年起于山东大学攻读博士学位，主要研究方向为无线传感器网络节点定位技术．

E-mail: lwsdjnyz@163．com

董恩清(通信作者)男，1965年出生于辽宁营口，博士，山东大学(威海)教授、博士生导师．2002年于西安交通大学获信息与通信工程专业博士学位．2006年～2007年在美国哈佛大学做访问学者．主要研究方向包括无线通信技术、无线传感器网络、医学图像处理等．

E-mail: enqdong@ sdu．edu．cn

Flip Ambiguity Detection for Three-Dimensional Node Localization in Wireless Sensor Networks

LIU Wei，DONG En-qing，SONG Yang
(School of Mechanical，Electrical＆Information Engineering，Shandong University，Weihai，Shandong 264209，China)

Abstract:To detect flip ambiguity for range-based three-dimensional node localization in wireless sensor networks，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 of the reference nodes，which is called the existence of intersecting plane (EIP) problem．To solve EIP problem，we further have proposed two solving algorithms: common tangent plane algorithm (CTP) and orthogonal projection algorithm (OP)．CTP adopts the principle of boundary detection，while OP transforms EIP problem into an angle calculation problem and adopts a coordinate transformation method to solve the problem．The simulation experiments demonstrate that CTP has good detection results，but its computational complexity is too high; however，OP has almost the same detection results as CTP and has lower computational complexity．

Key words:wireless sensor networks; three-dimensional node localization; flip ambiguity; common tangent plane; orthogonal projection

作者简介

基金项目:国家自然科学基金(No．81371635) ;高等学校博士学科点专项科研基金(No．20120131110062) ;山东省科技发展计划项目(No．2013GGX10104)

收稿日期:2014-06-26;修回日期: 2014-09-25;责任编辑:马兰英

DOI:电子学报URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．019

中图分类号:TP212; TN92

文献标识码:A

文章编号:0372-2112 (2016) 02-0374-11