一种基于Voronoi图和支持向量机的无线传感器网络节点定位算法

摘要

对无线传感器网络，基于Voronoi图的定位算法已被应用。然而，无线传感器网络中节点位置的定位精度需要进一步优化。通过文献分析，本文提出了一种基于Voronoi图和支持向量机的节点定位算法。该算法的基本思想是：首先利用定位区域中的Voronoi图和锚节点将区域划分为若干部分，通过将目标节点定位于各个区域中获得其初始位置范围，然后使用支持向量机精确地优化目标节点的位置。通过仿真和实际实验对所提定位算法的定位性能进行了分析。实验结果表明，本文提出的定位算法在定位精度方面优于基于最优区域选择策略的基于Voronoi图的定位方案和基于加权Voronoi图的定位方案。因此，本文所提定位算法的性能得到了验证。

关键词 无线传感器网络，Voronoi图，支持向量机，定位精度，Voronoi图和支持向量机

引言

无线传感器网络（WSNs）由于其自身特性具有许多优势，目前已被广泛应用于多个领域。其定位技术已成为当前研究的焦点，并在许多领域中显示出其重要性。在医疗保健领域，没有定位技术就无法获取患者病灶的位置；在建筑领域，没有定位技术就难以确定建筑物的故障位置；在森林保护领域，如果无法精确地获取传感器节点的位置，就难以确定准确的灾害位置并实现高效灾害处理。目前，全球定位系统（GPS）是最常见的定位方法，能够精确定位自身位置，但传感器节点受限于成本和功耗等因素；无法在每个节点上安装全球定位系统，因此在一般的定位方案中并不使用。基于无线传感器网络的节点定位近年来已成为研究热点，并且已有大量基于此的算法被研究和应用。

定位算法的研究可分为两类：基于测距的定位算法和基于非测距的定位算法。Khalaf‐Allah提出了一种基于到达时间（TOA）的直接定位方法。Yang et al.提出了一种基于到达角度（AOA）的定位方法，该方法利用小波变换辅助定位。Chen et al.提出了一种基于接收信号强度指示（RSSI）的无线传感器网络定位算法，然后采用加权质心算法提高定位精度。在Khalaf‐Allah、Yang et al.和Chen et al.中，介绍了几种基于测距的定位算法的应用。Liu et al.提出了一种基于APIT（Approximate Point‐in‐triangulation Test）算法的无线传感器网络定位方法，通过减少实际锚节点的数量来降低能耗。Stojkoska和Vesna提出了一种基于多维缩放（MDS）的无线传感器网络定位算法，然后通过距离校正提高了定位性能。基于距离向量（DV）‐ Hop算法的节点定位算法也受到了许多研究人员的关注。Cai et al.提出了一种数学加权DV‐Hop定位模型，并使用遗传算法求解该模型。Cai et al.还提出了一种名为N2‐3DDV‐Hop（非支配排序遗传算法II与三维（3D）距离向量跳数结合）的新方法，该方法在3D‐DV‐Hop算法基础上引入了多目标模型和非支配排序遗传算法II（NSGA‐II）。Wang et al.提出了一种结合非支配排序（NSGA‐II）的高斯误差修正多目标定位模型，命名为基于NSGA‐II的高斯误差修正多目标定位模型（GGA‐II）‐DVHop。在Liu et al.、Stojkosa和Vesna、Cai et al.以及 Wang et al.中，介绍了基于非测距的定位方法的应用。上述介绍的算法基本应用于静态节点的定位。目前，基于移动节点的定位算法也已被众多学者研究和应用。

根据调查分析，基于Voronoi图的定位算法已经得到改进，但定位精度仍需提高。因此，本文提出了一种基于Voronoi图和Voronoi图和支持向量机（VD‐SVM）的改进算法。本工作的主要贡献可总结如下：
1. 通过沃罗诺伊划分对位置区域进行分割，确定某一目标节点的位置范围。
2. 对划分的每个子区域使用支持向量机（SVM）。
3. 在室内和室外环境中验证所提出的节点定位方法的性能。

本文其余部分结构如下。第“相关工作”节回顾了基于VD‐SVM的节点定位系统的一些相关工作。第“节点定位算法”节介绍了所提出的模型，并描述了如何确定节点位置。第“定位算法仿真与实验”节讨论了实验设计和结果。最后，第“结论”节给出了本研究的主要结论以及对未来工作的简要讨论。

相关工作

自从支持向量机（SVM）得到正式支持以来，由于其在文本分类任务中的出色表现，它已成为机器学习的主流技术。近年来，SVM被广泛应用于定位领域。王等人提出了基于SVM的无线传感器网络（WSN）数据融合定位算法；基于到达时间/到达时间差（TOA/TDOA）定位技术，该文章提出了一种SVM数据融合模型，并基于搜索算法优化参数，以改进基于最小二乘支持向量机的定位算法。萨马迪安提出了无线传感器网络的概率支持向量机定位方法，首先利用支持向量机优化定位方法，然后通过吸引力/排斥力势场定位（ARPoFiL）方法进一步优化定位精度。毛等人提出了一种基于测距的SVM“一对一”节点定位算法，该算法利用SVM的基本二分类原理，扩展为多类别分类，从而实现节点定位。SVM也广泛应用于Wi‐Fi室内定位。余等人研究了基于SVM的室内定位，并对指纹库进行定位。利文萨和贾亚什里提出了基于信标的支持向量机在无线传感器网络中的定位方法，主要通过唤醒SVM的学习概念来提高定位精度。朱和韦提出了一种适用于大规模无线传感器网络的快速基于支持向量机的定位算法；该算法构建了一个通过引入相似性度量构造最小生成树，并根据特征空间中的最大相似性将支持向量分组。为了解决非测距定位算法中因距离测量误差导致定位性能下降的问题，唐等人提出了基于支持向量机的无测距定位（RFSVM）算法。朱和韦提出了一种基于磷虾群算法的参数优化算法（KH‐SVM），因为支持向量机的分类性能决定了定位精度，而参数的选择是决定性因素。

Voronoi图（泰森多边形或狄利克雷图）由连接两个相邻点的垂直平分线构成的一组连续多边形组成。作为一种通用的基本几何数据结构，它被广泛应用于节点覆盖和网络定位中。吉春等人提出了一种在无线传感器网络中无需距离测量的基于Voronoi图的节点定位算法。该算法对接收到的锚节点的接收信号强度进行排序，并利用单位圆盘图（UDG）地图计算每个锚节点的Voronoi区域；各区域交集的质心即为节点的位置。为了验证移动机器人的定位能力，宋和刘提出了广义Voronoi图，然后使用隐马尔可夫模型进行推理。拉斯拉等人提出了一种基于半对称透镜（HSL）的新定位算法，利用无线传感器网络中半对称透镜的几何特性。在此算法中，Voronoi图被用来缓解传感器节点无法定位的问题。杨和刘提出了一种基于三维沃罗诺伊图的序列定位校正算法。利用Voronoi图划分空间区域以构建虚拟锚节点的顺序列表，并将信标节点之间的接收信号强度指示方法作为参考，用于校正未知节点的测距和位置序列。卢等人提出了一种名为基本完整沃罗诺伊图定位方案（BCVD）的新定位算法。全文主要介绍了完整沃罗诺伊图背后的原理问题。在迪和强中，介绍了所引入的Voronoi图在水下传感器节点定位中的应用。上述文献主要介绍了Voronoi图在各个方面的应用以及对Voronoi图算法的改进，以提高定位精度。

无论是在室内环境还是室外环境，通过Voronoi图进行的位置定位都是粗粒度的定位，因此定位结果存在较大误差。目前，许多学者对Voronoi图进行了改进，或将其与其他算法相结合以提高定位精度，但仍存在一些问题。为了实现定位在更精细的环境中，本文采用Voronoi图与支持向量机相结合的方法进行定位，能够在相对较低的能量消耗和复杂度条件下进一步提高定位精度。最后，与子霄等人和蔡等人提出的定位算法相比，所提出的VD‐SVM算法性能更优。

节点定位算法

网络初始化

网络初始化的目的是确保网络中节点信息的稳定性。当网络中节点的信息保持稳定时，节点在其广播和接收信息过程中能够保证信息的准确性。网络初始化的步骤如下：

步骤1. 网络中的所有节点估计自身的位置信息，并通过接收信号强度指示距离信息测量节点i与其邻居节点之间的距离di。

步骤2. 所有锚节点Ni都知道自身的位置，因此锚节点向邻居节点广播其自身的信息Ai（包括位置信息、节点ID、接收信号强度指示等），未知节点根据锚节点广播的信息来确定自身的位置。锚节点中包含的信息Ai可表示为：Ai= fLoci,IDi, RSSI,dig。

步骤3. 节点P（节点P的邻居节点为节点i）直接接收锚节点信息Ai，然后更新信息Ai并存储，且节点P转发新信息Ai。

步骤4. 当节点P间接接收锚节点信息Ai时，即该信息是由邻居节点转发的，首先需要确认在接收到节点q的信息之前，节点P是否已经接收过来自节点q（节点q不是节点i的邻居节点）的信息。如果此前未接收过节点q发送的信息，则接受并存储信息更新信息Ai；如果此前节点P已接收过由节点q发送的消息，则还需判断节点i到节点P的距离与节点P到节点q的距离之和是否小于先前存储的距离di，若小于，则更新并存储信息Ai，且节点P转发新的信息Ai；否则丢弃信息。

步骤5. 迭代地执行步骤3和步骤4，表示当网络中所有节点的信息保持不变时，网络已完成初始化。

构建Voronoi图模型

本文提出的定位算法通过划分定位区域，对目标节点的位置进行逐部分定位，是一种分布式节点定位方法。首先，通过构建Voronoi图对定位区域进行划分，使定位由分散的局部逐步转变为对节点的分块定位，从而实现对定位节点更好的覆盖。

为了理解Voronoi图在节点位置中的应用，对构建Voronoi图的方法和性质进行了分析。通过分析研究发现，构建Voronoi图的最快方法是德劳内三角剖分。在生成Voronoi图时，首先在区域内有若干个点。这些点生成其对偶的德劳内三角剖分。三角剖分后，每个三角形可以找到对应的外接圆，通过找出这些外接圆的中心并连接相邻的中心。最终以每个三角形顶点作为生成元形成多边形网格，即得到该区域中若干点的Voronoi图，具体实现结果如图2所示。

假设在某个区域随机部署了50个传感器节点，这些传感器节点被确定为锚节点。利用Delaunay三角法形成的Voronoi图如图3所示。从图3可以看出，所确定的区域被划分成若干部分。

确定节点的位置

假设有N个无线传感器节点Ai = fA1,A2,A3,…，ANg随机分布在目标区域中，其中有m（m\N）个锚节点Ai = fA1,A2,A3，…，Amg的坐标位置已知信息，其余节点Ai= fAm、Am+ 1、Am+ 2、…、Ang的位置信息未知，需要通过定位算法计算得出。假设节点的通信距离记为R，即节点只能与其通信范围内的锚节点进行通信。

确定目标节点所在的区域。在节点的通信过程中，信息通过RSSI信号传输。模拟信号在传输时通常采用阴影模型。

$$
10 \lg \frac{RSSI}{RSSI_0} = -10b \lg \frac{d}{d_0} + X_{dB}
\tag{1}
$$

其中，$X_{dB}$ 表示均值为0的随机分布变量，b表示路径损耗因子，$d_0$ 表示参考距离。

在公式(1)中，由于$X_{dB}$是高斯随机噪声，通常认为其对结果影响不大而被忽略，因此可以进行粗略估计，从而得出结论

$$
\frac{d}{d_0} \approx \left(\frac{RSSI}{RSSI_0}\right)^{-1/b}
\tag{2}
$$

假设待确定位置的节点能够获取周围K（1≤K≤M）个锚节点的接收信号强度指示值，然后根据接收信号强度节点的通信距离，假设

$$
RSSI_{i1} \geq RSSI_{i2} \geq RSSI_{i3} \geq \cdots \geq RSSI_{ik}
\tag{3}
$$

根据公式(1)中的模型，可以得出

$$
\frac{d_{i1}}{d_{i2}} \approx \left(\frac{RSSI_{i1}}{RSSI_{i2}}\right)^{-1/b} < \frac{RSSI_{i1}}{RSSI_{i2}}, \quad \frac{d_{i1}}{RSSI_{i1}} < \frac{d_{i2}}{RSSI_{i2}}
\tag{4}
$$

可从公式(4)获得

$$
0 < \frac{d_{i1}}{RSSI_{i1}} < \frac{d_{i2}}{RSSI_{i2}} < \frac{d_{i3}}{RSSI_{i3}} < \cdots < \frac{d_{ik}}{RSSI_{ik}}
\tag{5}
$$

从分析可以看出，我们可以利用加权Voronoi图来求解不等式(5)，首先利用待定位节点周围的K个节点的加权Voronoi图来接收信号。加权Voronoi图的公式可以表示为

$$
W(P_i, l_i) = \left{ x \in W(P_i, l_i) \mid \frac{d(x,P_i)}{l_i} \leq \frac{d(x,P_j)}{l_j}, j=1,2,\ldots,n, j \neq i \right}
\tag{6}
$$

其中${l_i}$表示Voronoi图在空间集合中的权重。

根据公式(5)和(6)可知，节点i位于K 1 的加权Voronoi区域内。然后依次移除已确定的区域，得到节点所在的加权Voronoi区域，并获得不等式(5)的解集，通过该解集的质心来定位节点i的估计区域位置。

节点精确定位

支持向量机是一种机器学习模式识别方法，在解决小样本、非线性等问题方面具有明显优点。本文使用支持向量机进行节点定位。支持向量机的定位可分为三个阶段：训练阶段、广播阶段和定位阶段。由于沃罗诺伊图的分区计算，我们已初步划分了区域并粗略确定了目标节点所在的区域。然后，利用SVM算法进行位置定位。

1. 训练阶段 。如果一个节点确定该区域为图4中的区域2，则该区域内的每个节点向通信范围内的锚节点发送一个数据包，并表示为无法到达通信范围外的节点。因此，每个节点可以通过信号强度指数获得其到锚节点的距离信息，并将该节点的距离信息存储在节点中。每个锚节点向汇聚节点发送一个数据包Ai= fLoci,IDi,RSSI,dig，包括该节点的位置信息、节点的ID、RSSI值以及存储在节点中的距离向量。在汇聚节点执行支持向量机训练算法，并计算出对应所有分类的支持向量机参数信息。

2. 广播阶段 。汇聚节点将训练阶段计算出的支持向量机参数信息广播给区域内的所有节点。传感器节点处理聚合节点广播的信息，该算法对所有节点进行训练，最终定位目标节点。

3. 定位阶段 。在未知节点接收到支持向量机参数信息后，节点根据其自身的距离向量进行支持向量机分类，估计该区域中的类别，并将该区域中小格子的质心坐标作为目标节点的位置坐标。

定位算法仿真与实验

仿真研究

为了验证本文提出的定位方法，我们将该方法与子霄等人和蔡等人提出的两种定位算法进行性能对比。在性能验证中，使用MATLAB 2015b进行仿真实验，网络规模设置为150 m × 150 m × 150 m。本节主要从通信半径、锚节点数量和节点总数三个方面进行性能验证分析。为确保实验结果的准确性，进行了100组实验，计算实验结果的均值。在实验验证中，将所提出的定位算法与ORSS-VBLS和W-VBLS两种定位算法进行比较，以验证所提算法的性能。

通信半径的影响

通信半径的大小会影响目标节点的未知判定，因为当通信半径过大或过小时，目标节点周围的锚节点数量会过少或过多，从而影响目标节点位置的确定，并导致定位误差增大。实验结果如图5所示；结果表明，所提出的VD-SVM定位算法的定位误差低于其他两种定位算法，W-VBLS算法的定位性能与VD-SVM算法相近。从图中还可以看出，当通信半径达到30 m后，VD-SVM算法的平均定位误差趋于稳定，这表明当通信半径控制在30至45 m之间时，定位性能更优。当通信半径在15至33 m之间时，ORSS-VBLS定位算法的平均定位误差明显高于另外两种算法。当通信半径为15 m时，平均定位误差达到最大值0.25。当通信半径为20 m时，W-VBLS算法与VD-SVM算法的平均定位误差出现交点，其值约为0.09。

锚节点密度的影响

在定位目标节点时，锚节点的数量尤为重要。如果通信范围内没有锚节点，则无法对目标节点进行定位。当固定节点数量为500时，通过实验验证了锚节点数量对定位误差的影响，结果如图6所示。从图中可以看出，随着锚节点数量的增加，本文提出的VD-SVM定位方法的定位误差逐渐减小。此外，VD-SVM定位算法的定位精度优于其他两种定位算法。当锚节点数量大于15时，ORSS-VBLS定位算法的定位精度与VD-SVM定位算法基本相近，而W-VBLS定位算法的定位误差大于另外两种算法。当锚节点数量为5时，W-VBLS算法和VD-SVM算法的平均定位误差几乎相等，数值约为0.15。当锚节点数量在5到12之间时，ORSS-VBLS算法的平均定位误差高于W-VBLS算法；但当锚节点数量在12到30之间时，W-VBLS算法的平均定位误差高于ORSS-VBLS算法。

传感器密度的影响

本文中，在固定的无线传感器网络区域内，随机部署的传感器节点的密度对定位精度有影响。在传感器节点稀疏部署的情况下，存在通信范围内可通信的节点较少，这会影响定位的准确性。节点密度在一定程度上会影响节点间的通信，从而导致节点定位精度下降。通过实验分析，如图7所示，三种定位算法的定位误差随着节点数量的增加而减小，可以得出结论：与ORSS-VBLS和W-VBLS相比，VD-SVM定位算法的整体定位误差较小。在我们确定的区域内，定位误差范围较为稳定，节点部署数量约为300，表明当节点数量约为300时，在确定范围内节点数量较为合适。

实验评估

实验设备

实验验证阶段所需的设备包括传感器节点、汇聚节点和笔记本电脑。实验所用的传感器节点如图8(a)所示，基于采用ARM-Cortex-M3技术制造的STM32W108 ZigBee节点，符合ZigBee/IEEE802.15.4标准，能够满足用户对低成本、低功耗无线传感器网络的需求。其主要功能是向汇聚节点广播信息。所需的汇聚节点如图8(b)所示，以STM32W108为控制核心，无线传输速率高达250 kbps/s，支持从11至26信道中随机选择。它提供一个连接到PC终端的串口，其主要功能是将从传感器节点接收到的信息发送至PC终端，进行数据采集和处理。

传感器节点和(b) 链路节点)

实验场景

实验还在真实无线传感器网络上进行测试。为了验证所提出的定位方法在真实环境中的性能，选择了室内会议室和室外两种场景。前一节通过仿真实验将本文提出的VD-SVM定位算法与另外两种定位算法进行了比较，但仿真实验验证的环境是理想的。为进一步验证本文所提出定位算法的性能，图9和图10展示了在真实环境中验证的节点部署。如图9所示，选择一个20 m × 20 m的室外开阔区域作为实验场景，在该区域内随机部署了20个节点（包括3个聚合节点和17个传感器节点）。该区域内还有三台计算机，用于连接聚合节点，接收节点发送的数据信息，并处理信息。为了更清楚地了解环境部署情况，图9(b)是室外环境部署的逻辑图。如图10所示，选择了一个5 m × 5 m的室内实验环境。由于室内环境的位置区域有限，仅在该环境中随机部署了八个节点（包括一个汇聚节点和七个传感器节点），并有一台笔记本电脑连接到汇聚节点。图10(b)是室内环境部署的逻辑图。

实验涉及的节点包括两种传感器节点和汇聚节点，其中传感器节点分为锚节点和目标节点。锚节点在部署区域内以一定时间间隔广播自身的位置信息，接收到广播信息的汇聚节点将数据传输至PC终端。

VD-SVM算法需要首先利用Voronoi图确定目标节点的目标区域，然后使用SVM算法对其进行精确定位。为了验证所提出定位算法的定位性能，在实验场景中对该算法进行了验证。实验主要分为两部分：一是对VD-SVM定位算法在参数变化下的性能分析；二是将VD-SVM定位算法与ORSS-VBLS和W-VBLS定位算法进行对比的实验验证。

VD-SVM的性能分析

为了验证本文提出的定位算法的性能，我们通过改变参数来分析该算法的性能。在本文提出的定位算法中，我们通过实验确定通信半径和节点功率，以确保其定位性能。在不同的室内外定位区域使用不同的通信半径。在定位过程中，传感器节点的部署通常较为密集。如果每个节点以高功率进行通信时，会加剧节点间的干扰，降低通信效率，并造成节点能量的浪费。然而，如果传输功率过小，则会影响网络的连通性，降低定位性能。因此，在定位过程中，我们使用某种算法来控制节点的传输功率，即确定更合适的传输功率。通信半径的设置根据定位区域的大小进行调整。因为如果节点的通信半径过小，网络可能会不连通；通信半径过大，虽然能保证其连通性，但网络结构呈现出很强的网状网络特征。因此，通过两个实验分析了锚节点比例和通信半径对定位精度的影响，以及锚节点比例和通信半径对能耗的影响。

通信半径和锚节点比例对VD-SVM的影响

图11展示了锚节点比例和通信半径变化对定位精度影响的实验验证结果；从图中可以看出，节点的定位误差随着锚节点比例的增加而减小。通信半径的确定也对定位精度有一定影响。图中显示，当通信半径在5–30范围内时，R为15时定位误差较小，随着锚节点比例的增加，平均定位误差区域趋于稳定。当锚节点比例为0.2时，平均定位误差达到约0.21的最大值；当锚节点比例为0.6时，平均定位误差达到约0.1的最小值。从实验结果可以得出，合理确定通信半径的取值对定位精度有明显影响，因此，为了确保较高的节点定位精度，我们在该环境中将通信半径确定为15。

VD-SVM算法的能耗分析

本部分主要通过分析能耗，实验结果如图12所示。从图中可以看出，随着锚节点比例的增加，能耗逐渐降低；当通信半径确定为20时，能耗表现更优。当锚节点比例为0.2时，能耗达到最大值，约为25；当锚节点比例为0.6时，能耗达到最小值，约为10。当通信半径为15 m时，能耗变化较为波动；当锚节点比例在0.3至0.4之间时，能耗稳步下降；当锚节点比例在0.4至0.45之间时，能耗相对下降。由结论可知，在实验环境中，当锚节点数量相对较多时，能耗较小，而通信半径过大或过小都会导致节点定位能耗增加。因此，确定合适的通信半径值和锚节点数量更为重要。

VD-SVM与ORSS-VBLS和W-VBLS的性能比较与分析

能耗分析

真实环境验证下定位算法的能耗问题结果如图13所示。如图所示，在室外和室内环境中，整体能耗随着通信半径的增大而增加。且本文提出的VD-SVM定位方法的能耗低于ROSS-VBLS和W-VBLS算法。在图13(a)中，当通信半径为5 m时，VD-SVM的能耗约为16；当通信半径为16 m时，VD-SVM的能耗约为12；当通信半径为30 m时，VD-SVM的能耗约为21。ORSS-VBLS算法的能耗呈现波动状态；当通信半径在10至16 m之间时，能耗逐渐降低；当通信半径大于16 m时，能耗逐渐增加；其最小能耗约为16。W-VBLS算法的能耗持续上升；当通信半径约为18 m时，能耗最低，其值约为18。在图13(b)中，当通信半径在6至10 m之间时，VD-SVM方法与W-VBLS算法的能耗值相对接近；当通信半径为4 m时，能耗最低，其能耗值约为11。ORSS-VBLS的算法最高；当通信半径为10 m时，能耗约为30。

室外环境和(b) 室内环境)

通信半径的影响

真实环境中通信半径对定位精度的验证结果如图14所示。从两组实验结果可以看出，随着通信半径的增大，定位精度逐渐降低，本文提出的VD-SVM定位算法与其他两种算法相比，VD-SVM方法的定位精度优于ORSS-VBLS和W-VBLS，表明该定位算法在所提出的定位环境和条件下是适用的。在图14(a)中，ROSS-VBLS算法的平均定位误差相对较大，当通信半径在5到10米之间时，平均定位误差急剧减小。W-VBLS算法的平均定位误差最大值为0.2，最小值约为0.5。当通信半径大于10 m时，平均定位误差的变化较小。VD-SVM定位方法与W-VBLS算法的平均定位误差差异较小。当通信半径为5 m时，VD-SVM方法的平均定位误差约为0.15，W-VBLS算法的平均定位误差约为0.2。当通信半径为10 m时，VD-SVM定位方法的平均定位误差约为0.09，W-VBLS算法的平均定位误差约为0.1。当通信半径大于22 m时，三种定位算法的平均定位误差相近。

噪声的影响

环境中存在的噪声不可避免，会对定位精度产生一定影响。因此，为了验证其对定位精度的影响，在真实环境中进行了实验验证，结果如图15所示。在噪声影响下，VD-SVM定位算法相比ORSS-VBLS和W-VBLS两种定位算法具有更高的定位精度。两组实验结果表明，随着噪声的增大，定位误差也随之增加，噪声在两种实验场景中对ORSS-VBLS和W-VBLS算法的影响较大，两种算法的定位误差变化幅度较大，而VD-SVM算法的定位误差变化范围较小，说明VD-SVM在室内和室外均具有更强的鲁棒性。在图15(a)中，VD-SVM定位的平均位置误差范围该算法的值约为0.02–0.08。当噪声程度在0.1到0.25之间时，VD-SVM与W-VBLS的平均位置误差差异较小，随后逐渐增大。ORSS-VBLS算法的平均定位误差最大。当噪声程度为0.1时，平均定位误差约为0.1；当噪声程度为0.5时，平均定位误差约为0.15。在图15(b)中，VD-SVM算法的平均位置误差介于0.05至0.1之间。当噪声水平为0.1时，ORSS-VBLS、W-VBLS和VD-SVM算法的平均位置误差分别约为0.15、0.08和0.05；当噪声水平为0.5时，ORSS-VBLS、W-VBLS和VD-SVM的平均位置误差分别为0.2、0.18和0.1。

锚节点数量的影响

为进一步验证本文提出的定位方法在复杂环境中的定位性能，通过验证定位区域内锚节点数量对定位精度的影响，实验结果如图16所示。从图中可以看出，无论是在室内还是室外环境中，本文提出的VD-SVM定位方法的定位精度均更优。在图16(a)中，随着锚节点数量的增加，三种定位方法的定位精度逐渐提高。当锚节点数量在3到11之间时，VD-SVM算法的定位精度稳定上升，而另外两种算法的定位精度相对上升，并且在锚节点数量为4和6时，这两种算法存在交点。当锚节点数量为3时，三种算法的定位精度相对接近，其中VD-SVM算法的定位精度约为0.45，另外两种算法的定位精度约为0.4。当锚节点数量为7和9时，VD-SVM算法的定位精度分别约为0.78和0.9。当锚节点数量为11时，VD-SVM算法的定位精度约为0.98，因此几乎所有节点都能确定其位置。由于室内环境中的定位区域有限，仅部署了少量的目标传感器节点，因此本实验中将锚节点数量设置在1到5之间。在图16(b)中，三种定位算法的定位精度逐渐提高，与室外环境相比，这三种算法在室内环境中的定位精度相对稳定。当节点数量大于3时，三种算法的定位精度逐渐接近。当节点数量为4时，ORSS-VBLS、W-VBLS和VD-SVM算法的定位精度分别约为0.7、0.79和0.85。当锚节点数量为5时，VD-SVM算法的定位精度趋于接近1，而其他两种算法的定位精度趋于相等。

时间复杂度分析

通过分析VD-SVM算法的时间复杂度，即实现该算法所需的计算工作量，将所提出的VD-SVM算法与ORSS-VBLS和W-VBLS进行比较，结果如图17所示。从图中可以看出，在室内和室外环境中，VD-SVM算法的时间复杂度相对更优，但与其他两种算法相比差距较小。在图17(a)中，随着n值的增加，算法的时间复杂度也随之增加。当n在0到15之间时，VD-SVM与W-VBLS的时间复杂度值非常接近，并且在某一区间内，VD-SVM算法的时间复杂度大于W-VBLS算法的时间复杂度。然而，ORSS-VBLS算法的整体时间复杂度不稳定，当n为22时，该算法的复杂度达到500。W-VBLS和VD-SVM算法分别在n为23和25时复杂度达到500。在图17(b)中，三种算法的时间复杂度和数值具有一些相似性。当n为15时，VD-SVM、W-VBLS和ORSS-VBLS算法的时间复杂度分别约为190、200和220。当n分别为29和27时，ORSS-VBLS和W-VBLS算法的复杂度达到500。当n为30时，VD-SVM算法的时间复杂度约为470。

结论

本文提出了一种基于Voronoi图和SVM算法的定位算法。首先，通过建立Voronoi划分模型将传感器网络的定位区域划分为多个部分，并判断目标节点的初始区域和初步估计位置。为进一步提高定位精度，采用SVM算法对目标节点进行精确地定位。通过仿真和真实环境实验的验证与分析，本文提出的定位算法能够实现对目标节点较好的定位，其性能优于另外两种定位算法ORSS-VBLS和W-VBLS。下一步将对算法在大规模复杂环境中的验证与分析进行进一步研究。