定位技术是无线传感器网络(wireless sensor networks, WSNs)的关键支撑技术之一，WSN的信息采集和传输、目标跟踪、信息管理和基于地理位置的路由等许多应用中都需要准确的节点位置信息作为保障和支撑^{[1, 2, 3, 4]}。一般而言，没有位置信息的节点数据是毫无意义的。在实际应用环境中，节点通常被随机部署到复杂3D环境(如山体表面、海底或空中)。尤其是在山体表面环境中，地形可能会造成节点间连通性低、通信受阻等问题。因此，如何才能在不规则的复杂3D环境中实现高精度、低能耗的节点定位，成为了研究的重点^{[5, 6, 7, 8]}。

WSN节点定位的方法有很多。目前讨论热点是如何在减小网络配置的同时，提高定位算法的实用性^{[1, 3, 5, 8]}，比如无需锚节点的定位方法，仅仅通过节点间的连通性信息进行定位，在构建网络的过程中不用考虑可能所需锚节点的部署，这样有效地减少了网络的配置成本。同时，3D环境下网络条件更复杂，环境影响因素多，尤其是山体表面的定位，其应用广泛，但地形的限制破坏了理想网络中的诸多特性，传统的2D算法不能应对复杂的新环境。

本文针对大规模复杂3D山体表面WSN的特性，提出一种寻找特殊节点并进行三角划分的定位算法：

1) 提出了一种新的寻找特殊节点，采用全局最短路径树中各节点的子树，寻找节点特征的方法来寻找特殊节点，通过多次泛洪统计节点渡口度来判断是否为渡口节点，并通过渡口节点的连接性导出特殊渡口节点；2) 利用计算出的特殊渡口节点，采用德劳内三角化方法，将网络划分成独立、规则、平整三角区域，减少基于RSSI测距的误差；3) 在每一个三角区域上采用MDS-MAP算法对节点进行局部定位，在不使用锚节点的条件下使其能够在平整的三角子区域中准确确定传感器的相对位置。最后并将拆分成多个相对平整的三角子区域合并起来，从而确定整个网络中节点位置信息。

针对不同的应用环境，学者们已经提出了多种3D定位算法，文献^[9]提出了一个新颖的飞行移动锚节点定位算法。利用在飞机上配备了GPS接收器的锚节点，当飞行锚节点飞过传感空间时广播自己的位置信息。

文献^{[10, 11]}提出的定位算法是基于2D模型的，为了解决3D环境定位问题，通常是将3D平面节点映射到2D平面，再采用平面定位算法进行节点定位^[12]。但这种尝试性的扩展给定位算法复杂性也显著增加。

多维尺度(MDS)算法^[13]及其改进的MDS- MAP^[14]也能够很好地适应2D模型的定位。但扩展到复杂环境时就会出现模型失用等问题。

文献^[15]提出的定位算法CATL，其核心是找出节点之间最短路径的跳数偏离真正的欧氏距离的凹口节点。算法性能依赖于锚节点的正确部署，在网络节点数量较大的情况下计算开销不稳定，网络的均匀程度也对该算法的效果有一定的影响。

文献^[16]提出的SV算法能实现定位3D表面节点。该算法将3D表面的节点映射到2D面后计算出节点的坐标，再利用气压传感器还原节点的高度信息。该方法仅适用于规则的3D网络，当考虑复杂3D山体表面，由于地形原因会出现映射重复的情况，这将直接导致节点定位率下降。此外，网络在进行三角划分的时候粒度过细，将增大迭代计算的开销。

ACDL^[17]是一种基于凸面分解的定位方法。该算法是以边界凹节点作为划分依据，并没有利用全局的网络拓扑结构，因此易受到边界噪声的影响，并且该算法不适用于大规模传感器网络。

本文作者针对复杂山体表面网络特性也曾提出了相应的算法3D-CCD^[18]，对该问题进行了尝试性解决，但采用传统的基于路标节点的划分方法^[15]划分区域，往往划分的平面凸度很高。

根据复杂3D凹/凸不平表面网络的拓扑特性，利用节点间联通性特征，按照如下的步骤设计算法。

从网络的任意一个节点发出一则消息，通过这个消息的传播获得了一棵全局最短路径树。如果网络中的节点是各向均匀的，则任意一个节点周围的节点分布是均匀的，信息向各个方向传播的概率是相等的，所获得的最短路径树也是均匀的。然而，由于凹/凸不平地形的限制，信号的传播会受到障碍物等阻挡。为了将信号传遍整个网络，当消息从一座山传播到另一座山时，就很可能经过在山谷的节点；从山的一侧翻越到另一侧，很可能经过山脊的节点。这样，3D凹/凸不平表面网络的平衡就会被破坏，信息从山谷和山脊到达的节点更多，信息经过山谷和山脊的可能性更大，也就是说网络不是同构的而是异构的。如果仅仅通过子树节点的数量来计算是不合适的，因为信息是从一个点发出的具有孤立性。同时，从山谷和山脊传播出去的信息在很短的几个跳数内就能展开到一个平面，覆盖很多的节点。因而，可以利用该性质来判断山谷和山脊节点。将3D凹/凸不平表面网络中大量信息的山谷节点和山脊节点称为“渡口节点”(port nodes)。一个节点可能是渡口节点的衡量标准称为渡口度(port degree, PD_i)。可以通过PD_i的值判断一个节点是否是渡口节点。进而，根据渡口节点的连接，可以得到其中在山谷点和山脊点的渡口节点为特殊渡口节点，利用这些特殊渡口节点(special port node, SPN)进行3D凹/凸不平表面网络的三角划分，就能得到较为平整山体平面表面结构。

选择已经找到的路标节点(SPN)。每个路标节点异步泛洪，发送一个信息，并构建全局最短路径树。这个信息带有一个跳数的基数，所以每个路标节点能够通过这个信息知道自己在这棵树中处于哪一层。如果某个路标节点是第一次从一个确定的泛洪中收到一个消息，那么它就将这个消息的发送者当做它的父节点，并且回复一个确认消息。若一个节点p在一段确定的时间内收到了来自上一节点的信息并将信息转发，但没有收到过下一节点确认信息，它就将视自己为叶子节点。从叶子节点开始，依此向上回送一个报告给这棵树，报告自己的层数。

由于判断渡口节点最重要的是节点层数和节点数量的关系，使用影响因子来表示每个子节点对父节点的影响。节点对p其k级父节点的影响因子：

然后，计算每个节点的综合影响因子，节点p的综合影响因子为：

式中， $\{ {q_{p,1}},{q_{p,2}}, \cdots ,{q_{p,m}}\} $是节点p子树上大于3层的所有节点；N代表节点p子树上大于3层的所有节点数目。在每一次节点泛洪和在一定跳数h范围内，其子树影响的综合影响因子 ${\rm{IAff(}}p{\rm{)}}$达到一个预定阈值 ${\rm{TreeThres}}$点时，渡口度PD(p)的值增加1。

在每一次路标节点泛洪中，从所有已完成识别的叶子节点开始，向其父节点发送信息。父节点收到信息后，计算和统计所有的孩子节点，将他们的层数加1，并计算自己的综合影响因子 ${\rm{IAff(}}p{\rm{)}}$，再将自己和所有孩子的层数信息发送到其父节点。当信息到达点p时，使用k跳以内的结果计算自己的综合影响因子。若p点综合影响因子 ${\rm{IAff(}}p{\rm{)}}$达到阈值PD(p)，则其渡口度 ${\rm{CountThres}}$的值增加1。完成10%的节点一次异步泛洪后，如果PD(p)值达到某一阈值${\rm{CountThres}}$，则p点即为渡口节点。图 2中的★是渡口节点，●是普通节点。

图 2

图 2 节点识别

通过图 2可知，得到的渡口节点沿着山顶向山脚排列，把网络沿山脊划分成两部分，有利于平面的定位和方便进行三角化，以此来扩大平面的面积，减少计算开销和部署开销。还要对渡口节点进行一些筛选，保留尽可能靠近山顶和山脚的节点，称为特殊渡口节点(SPN)。

为了获取SPN，首先渡口节点之间在一跳以内进行异步通信，一次发送连接请求，在一跳以内的其他渡口节点收到后，就返回ACK，建立一个连接。可知建立了一个连接的节点位于划分线的端头处，建立了大于等于3个连接的节点位于划分线的交点处。这些节点有着显著的地理特征，分布在山顶山脚，因此，可以有效地找到接近于山脚和山顶的SPN。但节点还会出现聚集现象，即在一跳以内可能有很多渡口节点。为了避免这种情况，在建立节点连接的同时建立并查集，即在一跳以内的特殊节点放在一个并查集内。最后，从每个并查集内选择PD(p)最大的节点，这样选择出来的节点就是SPN。

算法 1 Find SPN node//寻找特殊渡口节点(SPN)

Initialize for all p_i.unionfind=i
        for all p_i an p_i where PD(p_i) < CountThres and PD(p_i) < CountThres
                 if p_i and p_i can connect
                     p_i.count++
                     p_i.count++
                 end if
              end for
      for all PD(p_i) < CountThres where
p_i.count ≤1 or p_i.count≥3
     for all PD(p_i) < CountThres where
             p_i.count ≤1 or p_i.count ≥3
       if p_i and p_i can connect
           p_i.unionfind=p_i.unionfind
         unionfind max.i=findmax(PD(p_i))          in unionfind.i
        end if
    end for
    end for 2.2 三角网划分网络建模

3DT-ST算法中把SPN节点连起来形成德劳内三角形。图 3展示了根据SPN进行三角化的结果。从图中可以看出，划分出的三角子网平整，规则，能够体现复杂山体表面的特征，并且能够较好地覆盖复杂山体表面区域。

图 3

图 3 用特殊渡口节点划分出的三角子区域

经过上面步骤，得到n个已划分的三角子区域 $\{ {\rm{Su}}{{\rm{b}}_1},{\rm{Su}}{{\rm{b}}_2}, \cdots ,{\rm{Su}}{{\rm{b}}_n}\} $。再对每个子区域Sub_i使用MDS-MAP算法进行定位。

设三角网子区域Sub_i中的节点个数为n_i，当开始定位算法后，启动节点的信号能量强度指示(RSSI)模块，采用最短路径搜索算法，计算整个网络中两两节点之间的距离，形成距离矩阵。再将得到的距离矩阵作为输入，并以三角子区域顶点作为协调者，使用MDS算法建立局部相对位置。

对于一个三角网子区域Sub_i中的 ${n_i} \times {n_i}$距离矩阵D_i，MDS算法先计算内积矩阵 ${B_i} = - \frac{1}{2}H{D_i}H$，其中 $H = I - \frac{1}{{{n_i}}}{e^{\rm{T}}}e$，I为n维单位矩阵，e为全1向量。然后将B_i对角化表示为$ {B_i} = X{X^{\rm{T}}} = UV{U^{ - 1}}$，其中 $X = U{V^{\frac{1}{2}}}$。

最后，矩阵中最大的两个或者3个特征值所对应的特征向量即是节点在二维或三维中的相对坐标矩阵X。

根据文献^[6]，本文采用网络的邻接约束图ACG^[19]。每个点i代表一个三角子区域Sub_i，如果Sub_i和Sub_i是邻近的两个子区域，则i,j也是邻居节点。定义d_i为与Sub_i三角网相邻的区域的数量，称为Sub_i的度。每个节点i赋权重w_i,w_i值为三角网Sub_i中的节点数量，n_ij表示公共线段上的节点个数。然后按照下列算法建立全局地图，三角网Sub_i中节点的坐标将转换到Sub_i的坐标系统中。

算法 2 Global Map Establishment

while The number of Sub regions is larger than one do
            For every two adjacent
              subsections Sub_i and Sub_j
                if d_j < d_i or d_j=d_i,and w_j < w_i then
                 Subi=Subi∪Subj
                 d_j=d_i+d_j-1,w_i=w_i+w_j-n_ij
              end if
             end for
       end while

每一次转换坐标，两个相邻的三角网被合并，直到所有三角网合并成一个大的区域后停止算法，输出为全局地图，完成全网络的节点定位。

本节通过实验对本文提出的3DT-ST算法，从节点密度、定位误差和计算能耗等方面来验证方法的可行性和鲁棒性，并与最新的SV和MDS-MAP定位算法进行性能分析对比。

选取图 1所示的山体模型。模型的大小长宽1 000 m×1 000 m，地形落差100 m左右。节点部署采用的是均匀随机的传感器部署方式，并且保证整个网络尽可能连通的。在100 000 m²的范围内部署1 000～4 000个节点。由于算法需要测量节点之间的距离，因此可能会造成测量误差。假设测量误差的变化范围是从0%到20%。节点一跳的范围为50 m之内。

图 1

图 1 复杂山体表面

经过多次实验认为，在TreeThres=4和CountThres=30时，能够有效地寻找到渡口节点，且这些节点的几何特性较为明显的出现连接山顶和山脚的倾向。在实验数据中，均采用了上面的取值。由于部署并非十分密集，认为跳数范围为k无穷大。

定位误差：为节点的实际位置和预测位置之间的欧几里得距离。其中，(x,y,z)是节点的实际坐标，(x_e,y_e,z_e)是节点的估测坐标。定义为：

地形模型误差：z_i是节点的实际坐标位置，z_ei是节点的测量位置。定义如下：

图 4所示的是3DT-ST算法和SV算法、MDS-MAP算法的定位率结果对比图。

图 4

图 4 节点定位率随测量误差变化情况

实验结果表明，在测距误差较大时，部署节点数量分别为1 000、2 000、4 000时，3DT-ST算法和最新SV算法的定位率大致相当，比MDS-MAP的定位率高出很多。

图 5展示了在复杂3D凹/凸不平表面网络中3DT-ST算法和SV算法、MDS-MAP算法平均定位误差的比较情况。由于MDS-MAP算法在扩展到3D复杂网络中时本身存在很大的误差，所以简单的将MDS-MAP算法升级使用到复杂3D凹/凸不平表面网络中是不可取的。

图 5

图 5 节点定位误差随测量误差变化关系

结果显示，3DT-ST算法在测距误差较大时，依然能得到更有意义的效果。3DT-ST算法定位率上有较大的优势，在测距误差为5%，部署节点数量分别为1 000、2 000、4 000时，相比SV算法平均定位误差分别减小80.6%、86.3%和81.6%。从而可以得出，3DT-ST算法定位误差与网络的节点数没有直接的关系。从实验结果可以看出，由于3DT-ST算法经过特殊节点选取和三角划分策略的设计，所得的平面化效果较好，对测量误差有一定的容错能力，在测距误差逐渐增大的时候，对定位精度的影响较小。同时，在测量时由于节点部署和选择泛洪节点的随机性，得到的结果也具有一定的随机性，采用了多次测量的平均值。这说明3DT-ST算法具有较强的健壮性。

图 6展示了在不同情况下3DT-ST的计算时间。测试的计算机使用的是奔腾G620处理器，4 G内存，32位Windows操作系统和Matlab2012b。针对1 000、1 500、2 000、4 000个节点进行测试。取3次测试的平均数，得到的结果如图 6所示。

图 6

图 6 不同节点数情况的算法计算开销对比

以计算时间为标准，横坐标为节点个数，纵坐标为计算机负荷量，单位为s。实验结果显示，随着网络规模的增大，计算的时间随之增加，这是由于在节点数更多的情况下，需要耗费更多的能量去计算各个节点之间的距离。但是仅从计算的消耗量来看，3DT-ST的计算负荷在一个可以接受的范围内，并且适合于大规模复杂环境下的WSN应用。和其他一些算法(如CATL算法和SV算法等)相比，本文提出的3DT-ST算法不需要迭代，避免了因迭代次数不够而带来的误差，同时避免了在大规模复杂网络上，随着迭代次数增加而计算负荷量(计算开销)显著增加的问题。

3DT-ST算法不需要配备任何复杂的硬件传感器(如气压传感器等)，且定位过程中无需锚节点的，仅靠网络的连通性和特殊节点来定位，节点只需要感知到通信半径内的其他节点，对硬件要求低，不易受环境影响，这样大大降低了网络的部署成本。同时，3DT-ST算法在定位过程中不需要迭代过程，在复杂山体表面上能有效地降低计算开销并得到较好的定位效果。