DOI: 10.11817/j.issn.1672-7207.2015.08.024

无线传感器网络中基于双支持向量回归的分布式定位算法

王其华^{1, 2}，郭戈¹

(1. 大连海事大学 信息科学技术学院，辽宁 大连，116026；

2. 大连海洋大学 信息工程学院，辽宁 大连，116023 )

摘要：针对无线传感器网络中节点定位误差问题，提出一种基于双支持向量回归的分布式定位算法。在保持锚节点连通性的基础上，以锚节点跳数和位置信息为训练样本。结合拉格朗日法和KKT(Karush-Kuhn-Tuchker)条件，把原问题的优化转化为对偶形式，使用双支持向量回归技术确定跳数信息到节点间距离的映射函数。最后，采用最小二乘法估计待定位节点的位置，在不同锚节点和通信半径的情况下对传感器目标节点进行定位实验测试。实验结果表明：该方法减小了测量误差，能有效提高节点自身定位精度。

关键词：无线传感器网络；双支持向量回归；定位算法；跳数

中图分类号：TP393             文献标志码：A         文章编号：1672-7207(2015)08-2930-07

Distributed localization algorithm based on twin support vector regression in wireless sensor networks

WANG Qihua^{1, 2}, GUO Ge¹

(1. School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China;

2. School of Information Engineering, Dalian Ocean University, Dalian 116023, China)

Abstract: Aimed at solving the problem of node localization error in wireless sensor networks, a novel approach to distributed localization was proposed based on twin support vector regression. By optimizing the connectivity of anchor nodes, the hop counts and the position information among anchor nodes were taken as training samples. Combined with the Lagrange method and Karush-Kuhn-Tuchker (KKT) conditions, the twin support vector regression was adopted to attain mapping model between hop count and distance by converting the optimization of the original problem into dual form. The least square method was used to obtain estimation position of unknown nodes. The experiments of sensor localization on different anchor nodes and the radius in WSN were carried out. The simulation results show that the location accuracy is improved by reducing measurement error.

Key words: wireless sensor networks; twin support vector regression; localization algorithm; hop counts

无线传感器网络(wireless sensor networks, WSN)是近年来新兴的热点领域，它综合网络技术、现代传感技术、通信技术和嵌入式计算机技术等诸多学科，能够实时感知、采集和处理监测区域内的目标信息，周期性地以多跳方式把数据发送给终端设备，广泛应用于环境监测、医疗监护，目标跟踪和海上救援等行业^[1-2]。节点位置的定位是WSN中理论研究和实际应用的基础，离开节点的位置信息，监测数据就失去应有价值。如果为每个节点配置GPS模块，则成本过高，不符合现实。传感器节点的能量供应、通讯距离和计算能力有限，节点在位置定位时，必须考虑传感器的这些局限性。因此研究适合WSN特点的定位算法具有重要的理论研究和实际应用价值。目标定位已成为WSN中重要的研究方向，根据是否需要测量节点之间的距离，定位算法分为测距定位和非测距定位2种方法。常用的测距定位技术有到达时间(TOA)、到达时间差(TDOA)、角度到达(AOA) 和接受信号强度(RSSI)等^[3-4]。测距定位算法容易受到多径、非视距和多址等因素影响，产生测距误差，造成误差积累^[5]，从而影响定位精度。非测距定位主要利用传感器节点间的连通性，该方法简单方便，且不受测距误差的影响；非测距方法缺少传感节点间距离信息，定位精度通常较低。例如，文献[6]提出DV-Hop方法，利用平均跳距离实现节点定位问题；文献[7]基于接受信号强度和网络连通性改进质心定位算法。文献[8]研究了目标定位中的半定规划优化问题，将凸优化方法用于非测距定位获取较高定位精度，但网络通信开销较大，影响网络生命周期。通过对以上定位算法优缺点的分析可以看出，在设计非测距定位算法时需充分利用网络连通信息，减少误差累积对定位精度的影响。近年来，支持向量机回归(SVR)^[9-12]在处理小样本预测、非线性回归和局部最优问题中展现出良好的性能，其在位置定位方面的理论研究已经引起研究人员的广泛关注。基于统计学习理论的支持向量回归定位技术，把定位问题转化为凸二次优化问题，避免维数灾难，适合小样本学习和预测。文献[13-14]运用支持向量机理论解决定位问题。文献[15] 把WSN定位看作支持向量机分类问题，改进距离无关的定位算法。文献[16]研究在模糊条件下运用最小二乘支持向量法预测数据，使用等式作为约束条件，其所求解不具有稀疏性。文献[17]以最小二乘支持向量回归(LSSVR)为基础，改进传统支持向量回归算法。文献[18]把位置估计看作机器学习问题，利用支持向量回归定位(LSVR)技术实现物理信号强度到位置的映射，获得较好的定位结果。文献[19]充分利用网络的连通性，将泰勒展开式和核回归相结合，提出一种支持向量回归定位算法，但实际结果表明网络并没有真正实现全网连通。上述文献虽然考虑了定位精度和通信开销问题，但仍存在一定的局限性。研究多以网络始终连通性为前提，未能充分利用网络的全局拓扑信息，过多依赖传感器节点的局部邻居信息，导致定位精度下降；同时，由于支持向量回归约束参数较多，计算复杂性问题也没有得到很好的解决。借鉴文献[19]的思想，充分利用网络的连通信息，本文作者提出一种无需测距的分布式双支持向量回归定位方法(TSVR)。主要研究了WSN中的双支持向量回归位置定位问题，考虑对锚节点连通性的优化预处理，建立跳数信息和距离的映射模型，利用锚节点的连通信息和位置作为训练样本，通过双支持向量回归策略，解决两个规模较小的二次规划寻址问题，分别确定函数的下界和上界；然后根据回归函数估计待定位节点与锚节点间的距离，运用最小二乘法估计目标节点位置；最后用仿真验证算法的有效性和实用性。

1  问题描述及相关模型

无线传感器网络节点部署如图1所示。考虑一随机部署的无线传感器网络节点位置的定位问题，设传感器网络S由M个锚节点和N个未知节点组成，S记为，S=(s₁，s₂，…，s_M，…，s_M+N)。假设锚节点可以移动，在一定范围内邻居节点相互通信，非邻居节点通过多跳方式转发信息。定义集合A={s_m|m=1，2，…，M}，集合。节点s_k位置表示为，，任意2个节点之间的欧式距离定义为

        (1)

表示节点s_k和s_i之间的最小跳数，则所有传感节点到锚节点的最小跳数可以用矩阵P表示，其行向量P_k表示为，，其中，。本文研究的重点是通过锚节点的测量向量和位置信息确定非线性函数模型，未知节点利用此回归函数模型估计节点自身位置。节点定位问题可以转化成支持向量回归问题，使用传统的支持向量回归技术，约束变量多，计算量大，不适合大型的无线传感网络；为此，文献[17] 采用最小二乘支持向量方法求解下式：

            (2)

其中：，为输入向量；，为输出值；ω为权重向量；b为偏置参数，非线性映射，H为特征空间。运用最小二乘支持向量方法，问题(2)的优化问题变成

         (3)

式中：C为惩罚因子，该值决定了对误差的重视程度；ξ为容忍误差向量。用Lagrange法把式(3)转化为线性方程组求解：

          (4)

其中：n为样本数；；I_n为n维单位向量；为Lagrange因子向量；；为满足Mercer条件的核函数。求解式(4)可以确定LSSVR回归模型。优化目标函数(3)与经典的SVR不同，只有等式约束，问题的求解简单、速度快，但所求的解不具有稀疏性。

图1  无线传感器网络节点部署

Fig. 1  Deployment of WSN nodes

如前文所述，本文研究问题可以描述为：对于非线性模型(2)，给定和，考虑WSN通信和计算能力的局限性，设计合理的分布式控制定位算法和回归策略，确定双支持向量回归函数参数，估计，提高节点定位性能。其中：；。

2  分布式双支持向量回归定位(TSVR)

支持向量机理论是以结构风险最小化原理为基础，通过有限的样本信息，在模型的复杂性和学习能力之间寻找最佳值^[20-21]，解决维数灾难问题，提高其泛化能力。以支持向量机理论为基础，提出分布式双支持向量回归定位算法，该算法主要有4部分组成。

1) 预处理阶段。首先对锚节点的连通性进行预处理，保证锚节点的连通性。

2) 测量阶段。锚节点发送自己的位置信息给其他锚节点，每个节点获取到其他节点的最小跳数信息。

3) TSVR阶段。每一个锚节点s_i利用支持向量回归估计自己的SVR_i距离模型，并将该模型的参数发送到所有待定位节点s_n。

4) 定位阶段。每一个未知节点根据TSVR阶段的距离模型计算节点本身与锚节点的距离，通过最小二乘法估计位置信息。

预处理阶段保证锚节点的连通性，以便获取所有节点的最小跳数，TSVR阶段确定距离函数映射关系，定位阶段运用最小二乘法完成节点的定位。

2.1  网络连通性预处理

锚节点的位置坐标已知，计算锚节点间的距离，用矩阵幂算法判断锚节点是否连通，适当移动锚节点，加强网络连通性。

设传感器节点s_i的坐标位置为(x_i，y_i)，通信半径为R_C,其通信区域定义为 ≤R_C，则传感器节点s_i和s_j之间的通信关系可以表示为，

            (5)

无线传感器网络中任一节点的移动，都可能使网络的拓扑结构发生变化，若所有节点位置随之发生变化，网络总体能耗很大。此阶段要保证锚节点间网络的连通性，通过移动个别锚节点，消除孤立节点，方法如下：

要使锚节点传感器s_i和其他锚节点间能够通信，距离需满足，即a_ij=1。假设锚节点可以移动，如果a_ij=0，说明两节点不能通信，数据得不到有效的融合，节点s_i需向距离最近的邻居锚节点s_j方向移动到合适的位置。为节省能量，移动的距离需最短，移动后节点位置、原来位置和节点s_j位置 3点在一条直线上能保证移动距离最短，运用三角比例法确定节点s_i移动后的位置为

                (6)

2.2  测量阶段

经过网络连通性预处理后，网络的连通性得到优化，锚节点间的信息可以有效的融合，连通性预处理为测量阶段提供可靠的通信基础，接下来描述测量阶段详细过程。

令为锚节点s_i与其他锚节点的跳数信息向量，所有锚节点的跳数信息向量用矩阵P表示，，其中，，，；同样，令d_i表示锚节点之间的几何距离向量， 。所有锚节点的几何距离信息用矩阵，其中，，，。令表示未知节点s_n和所有锚节点的跳数信息向量，其中。

测量阶段的通信过程如下：首先，每个锚节点广播邻接跳数消息给所有的传感器节点，跳数的初始值为0，当节点收到邻居节点发送的跳数信息，跳数增加1，用Dijkstra算法最终确定节点间的最小跳数，这样每个锚节点和未知节点能获取相应的跳数信息向量P_i和P_n。然后，每个锚节点发送自己的位置送信息给所有锚节点，该信息包括该节点的跳数信息向量P_i和位置信息向量p_os(s_i)，这样锚节点就收集到网络的连通信息和锚节点位置信息。在此阶段网络通信的过程中，共发送个消息，时间复杂度约为。锚节点的数量远小于待定位置节点的数量，与使用汇聚节点收发信息的集中式算法相比，网络内传感节点的通信量减少，有效节省网络能耗，延长系统寿命。

2.3  训练阶段

锚节点收集到跳数信息向量P_i和位置信息向量p_os(s_i)后进入训练阶段，在此阶段锚节点用收集到的M个训练数据对建立双支持向量回归距离模型，确定函数距离和跳数信息的映射关系。式(2)表示成下面的2个非线性映射函数：

             (7)

           (8)

在满足Mercer定理的条件下，用核函数代替高维特征空间的映射函数，锚节点通过训练数据确定2个非线性函数上界和下界，如图2所示。函数(7)和(8)利用锚节点间的信息P拟合锚节点间的距离d_i，其中，ω_i和b_i为非线性函数待定参数，φ(·)是高维特征空间函数映射。在此阶段的目标是估计参数ω_i和b_i，确定函数模型(7)和(8)，利用锚节点位置向量和节点间跳数向量将跳数转化为距离。式(7)转化为式(9)的优化求解：

                   (9)

式中：C₁＞0；ε₁为不敏感参数；ξ为松弛向量；1为样本维数1的向量；D为距离矩阵；是核矩阵，在满足Mercer定理的条件下用核函数代替高维特征空间函数映射，其中，。把式(9)写成拉格朗日函数形式：

              (10)

其中，为拉格朗日乘子向量。函数L₁分别对，，ξ求偏导数并置零。

     (11)

 (12)

          (13)

联立式(11)和(12)可得：

  (14)

简化为

    (15)

其中：，， ，，I为样本维数的单位矩阵。

由KKT条件得：

    (16)

               (17)

原优化问题(9)的对偶形式可表示为

               (18)

其中：。求得α₁后，通过μ₁确定函数(7)的映射关系为

          (19)

采用类似方法，通过优化下式确定函数(8)：

                        (20)

运用拉格朗日乘数法、对偶原理以及KKT条件，确定函数(8)的函数形式：

        (21)

结合式(19)和式(21)，最后确定的距离预测回归函数为

    (22)

式(22)是由2个支持向量回归函数确定的，解决2个规模较小的二次规划问题，求解时约束变量较少，计算量小，具有良好的泛化能力。

图2  双支持向量回归

Fig. 2  Twin support vector regression

在此阶段，每个锚节点s_i发送自己的SVR_i模型参数给待定位传感器节点，其中，，总共需要发送MN个信息，所用的时间复杂度约为。

2.4  定位阶段

完成前3个阶段后，每个未定位节点根据收到的锚节点发送的M个SVR模型参数向量和跳数信息，估计出未知节点和锚节点间的距离，然后进行节点自身定位。

令代表未知节点s_k和M个锚节点之间的估计距离向量, 表示节点s_k和锚节点s_j之间的估计距离，估计距离向量由下式确定：

                (23)

估计距离确定后，用最小二乘定位法确定节点位置。假设M个锚节点的坐标为，待定位节点s_k的坐标为 (x，y)，距离估计为，建立线性方程组：

                 (24)

其中：

根据方程(24)得到节点的位置估计，。

在整个定位过程中，需要发送个通信信息，由于在网络中锚节点的数量远小于未知节点，所以该算法通信时的时间复杂度为。

3  实验仿真

使用Matlab R2012a 对TSVR算法进行仿真实验，假设在边长为100 m的正方形区域内随机部署100个传感器节点，锚节点位置是已知的，未知节点位置需要借助锚节点和相关算法获得。采用3.1节描述的方法对锚节点连通性进行优化处理，图3所示为节点通信半径为20 m的网络邻接拓扑关系。实验模拟时主要参数设置如下：C为15，ε=0.2，核函数用高斯核函数，即。将定位算法仿真结果与Dv-hop^[6]，LSSVR^[17]和LSVM^[18] 3种方法进行比较。

图3  网络拓扑结构

Fig. 3  Network topology

图4  锚节点数对定位的影响

Fig. 4  Influence of anchor nodes on location

仿真时采用2种对比策略：

1) 锚节点和未知节点所占比例不同，通信半径固定和传感器节点总数不变。

2) 锚节点和未知节点数目固定不变，通信半径可调。

锚节点数对定位性能的影响如图4所示。可见：TSVR的定位精度要优于其他3种方法。除Dv-hop定位误差较大外，其他3种算法的定位误差较小，随着锚节点数目的增加而降低，但变化幅度不大，尤其是TSVR算法，误差平稳。LSVR算法进入测量阶段之前优化锚节点的网络连通性，增加锚节点数目，训练样本相应增加，定位精度略有提高，幅度不大。样本数增加后，加大计算复杂性，所以，在实际应用中不需要大量的锚节点辅助定位，体现出双支持向量回归技术在小样本预测方面的优势。

图5所示为通信半径对定位误差的影响，从图5可以看出：当通信半径都较小时，节点的定位精度不高，原因在于通信半径较小，网络连通性出现问题，跳数和位置信息不能有效融合， TSVR算法中虽然对锚节点网络连通性进行预处理，但待定位节点的网络连通性可能较弱。随着通信半径的增大，基于信号强度的LSVR定位误差变化明显，而TSVR算法的平均定位误差相对稳定。

表1所示为4种定位算法计算时间的比较。从表1可以看出：Dv-hop算法的用时最少。相比于Dv-hop算法，其他3种定位算法都运用了支持向量机理论，所以计算量大，耗时多，但本文的TSVR算法耗时比LSSVR和LSVR要少，原因在于双支持向量回归在2次规模较小的计算中，使用的训练样本数减小，迭代过程简化，计算复杂度降低，耗时少。

图5  通信半径对定位的影响

Fig. 5  Influence of communication radius on location

表1  定位算法耗时比较

Table 1  Comparison of computation time in location algorithms               s

4  结论

1) 提出了双支持向量回归的分布式定位算法。首先优化锚节点间的连通性，通过锚节点的连通信息和位置关系确定回归函数的上界和下界，然后待定位节点根据锚节点发送的模型参数完成自身位置估计。

2) 确定的函数映射需要较少的约束参数，简化了迭代过程，计算量较小；实验结果表明，该算法能有效降低定位误差，具有较好的定位性能。

3) 提高定位精度是无线传感器网络研究的重点。后续的研究包括全局网络的连通性以及数据量化对定位性能的影响，如何对移动目标定位也是下一步研究的重点。

参考文献：

[1] Cheung K W, So H C, Ma W K, et al. Least squares algorithms for time-of-arrival-based mobile location[J]. IEEE Transactions on Signal Processing, 2004, 52(4): 1121-1130.

[2] Baggio A, Langendoen K. Monte Carlo localization for mobile wireless sensor networks[J]. Ad Hoc Networks, 2008, 6(5): 718-733.

[3] Niu R X, Varshney P K. Target location estimation in sensor networks with quantized data[J]. IEEE Transactions on Signal Processing, 2006, 54(12): 4519-4528.

[4] 杨小军. 多跳无线传感器网络下信道感知的目标定位方法[J]. 自动化学报, 2013, 39(7): 1110-1116.

YANG Xiaojun. Channel aware target localization in multi-hop wireless sensor networks[J]. Acta Automatica Sinica, 2013, 39(7): 1110-1116.

[5] Xu E Y, Ding Z, Dasgupta S. Target tracking mobile sensor navigation in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2013, 12(1): 177-186.

[6] Niculescu D, Nath B. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems, 2003, 22(1/2/3/4): 267-280.

[7] YU Hu, YAO Weizhao. Linear-regression-based weighted centroid localization algorithm in wireless sensor network[J]. Procedia Engineering, 2011, 15: 3068-3072.

[8] Biswas P, Liang T C, Toh K C, et al. Semidefinite programming approaches for sensor network localization with noisy distance measurements[J]. IEEE Trans Autom Sci Eng, 2006, 3(4): 360-370.

[9] 许建华, 张学工, 李衍达. 支持向量机的新发展[J]. 控制与决策, 2004, 19(5): 481-493.

XU Jianhua, ZHANG Xuegong, LI Yanda. Advances in support vector machines[J]. Control and Decision, 2004, 19(5): 481-493.

[10] Lee J, Choi B, Kim E. A novel range-free localization based on multi-dimensional support vector regression trained in the primal space[J]. IEEE Transactions on Neural Networks and Learning Systems, 2013, 24(7): 1-15.

[11] 陈进东, 潘丰. 基于在线支持向量回归的非线性模型预测控制方法[J]. 控制与决策, 2014, 29(3): 460-464.

CHEN Jindong, PAN Feng. Online support vector regression-based nonlinear model predictive control[J]. Control and Decision, 2014, 29(3): 460-464.

[12] Peng X J. TSVR: An efficient twin support vector machine for regression[J]. Neural Networks, 2010, 23(3): 365-372.

[13] Brunato M, Battiti R. Statistical learning theory for location fingerprinting in wireless LANs[J]. Computer Networks, 2005, 47(6): 825-845.

[14] 魏叶华, 李仁发, 罗娟, 等. 基于支持向量回归的无线传感器网络定位算法[J]. 通信学报, 2009, 30(10): 44-50.

WEI Yehua, LI Renfa, LUO Juan, et al. Localization algorithm based on support vector regression for wireless sensor networks[J]. Journal on Communications, 2009, 30(10): 44-50.

[15] Tran D A, Nguyen T. Localization in wireless sensor networks based on support vector machines[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(7): 981-994.

[16] Lin K P, Pai P F, Lu Y M, et al. Revenue forecasting using a least-squares support vector regression model in a fuzzy environment[J]. Information Sciences, 2013, 220: 196-209.

[17] Kim W, Park J, Yoo J, et al. Target localization using ensemble support vector regression in wireless sensor networks[J]. IEEE Transaction on Cybernetics, 2013, 43(4): 1189-1198.

[18] Wu Z L, Li C H, Ng K Y, et al. Location estimation via support vector regression[J]. IEEE Transaction on Mobile Computing, 2007, 6(3): 311-321.

[19] Lee J, Chung W, Kim E. A new kernelized approach to wireless sensor network localization[J]. Information Sciences, 2013, 243(18): 20-38.

[20] Vapnik V N. The nature of statistical learning theory[M]. New York: Springer-Verlag, 1995: 37-69.

[21] 张学工. 关于统计学习理论与支持向量机[J]. 自动化学报, 2000, 26(1): 32-42.

ZHANG Xuegong. Introduction to statistical learning theory and support vector machines[J]. Acta Automatica Sinica, 2000, 26(1): 32-42.

(编辑  赵俊)

收稿日期：2014-08-20；修回日期：2014-10-20

基金项目(Foundation item)：国家自然科学基金资助项目(61273107，61174060)；大连市领军人才支持计划项目(2012Z0036)；中央高校基本研究项目(3132013334)(Projects (61273107, 61174060) supported by the National Natural Science Foundation of China; Project (2012Z0036) supported by the Dalian Leading Talents; Project (3132013334) supported by the Foundamental Research Founds for Central Unversities, China)

通信作者：郭戈，教授，博士生导师，从事网络化控制、传感器网络、智能车辆群体控制等研究；E-mail：geguo@yeah.net