面向多跳WSNs的基于LSSVR的节点定位算法*

王自力,郑 鑫

(1.驻马店职业技术学院信息工程系,河南 驻马店 463000;2.黄淮学院信息工程学院,河南 驻马店 463000)

面向多跳WSNs的基于LSSVR的节点定位算法*

王自力1*,郑 鑫2

(1.驻马店职业技术学院信息工程系,河南 驻马店 463000;2.黄淮学院信息工程学院,河南 驻马店 463000)

多跳无线传感网络WSNs(Wireless Sensor Networks)中的多类应用均需要准确的位置信息。为此,提出面向多跳WSNs的基于最小二乘支持向量回归机定位算法LSSVR-LA(Least-Squares Support Vector Regression location algorithm)。LSSVR-LA算法先引用转发区域概念,并通过转发区域建立测距模型,然后再利用Secant 算法估计传感节点与锚节点间距离,最后将这些距离作为LSSVR输入,建立了基于LSSVR定位算法模型。最终,估计未知节点的位置。实验数据表明,提出的LSSVR-LA算法的定位精度得到有效地提高。

无线传感网络;测距;Secant 算法;最小二乘支持向量回归机;定位

随着无线通信和低功耗集成技术的迅速发展,无线传感网络WSNs(Wireless Sensor Networks)得到广泛应用。WSNs由微型、低功耗、小电池供电的传感节点组成。通常,传感节点以随机方式分布于监测区域,进而感测环境,并收集环境数据[1-4]。

由于能量受限,传感节点通常需要以多跳方式将数据传输至信宿。然而,任何数据必须具备相应的位置,若离开了位置,其数据将无任何意义[5]。因此,估计传感节点位置是多跳WSNs应用的基础。

目前研究人员已对定位算法进行了较深入研究[6-7]。为了更准确地估计传感节点位置,多数定位算法要求传感节点需至少获取离3个锚节点的距离信息。在多跳WSNs中,多数传感节点难以与锚节点能直接通信,通常需要利用最短路径估计传感节点与锚节点间距离。

现有的定位算法可划分为测距定位算法和非测距定位算法两类。测距算法主要包括基于RSSI、到时时间ToA等,通过接收信号参数,估计距离。而非测距定位算法主要是通过网络连通性测距[7],如DV-HOP技术[8]。

目前,针对多跳WSNs的节点定位,分析算法(Analytical Algorithms)[9-11]得到广泛应用。具体思路:先估计平均跳距和跳数,它们的乘积作为测距值。然而,估计平均跳距存在较大误差,不同拓扑结构,平均跳距不同,且差异大。

为此,本文针对多跳WSNs网络,提出基于最小二乘支持向量回归机定位算法LSSVR-LA(Least-Squares Support Vector Regression location algorithm)。首先,分析了Analytical Algorithms的不足,然后再讨论LSSVR-LA算法。LSSVR-LA算法先引入转发区域概念,并建立测距模型,然后由Secant 算法测距,最后由LSSVR系统估计传感节点位置,实验数据表明,提出的LSSVR-LA算法降低了定位误差。

1 网络模型及问题描述

1.1 网络模型

图1显示了M个锚节点和N个传感节点分布于2-D平方区域S。菱形表示锚节点,正方形表示传感节点。锚节点已知自己位置,而传感节点对自己位置信息未知。假定传感节点均匀分布于S。所有锚节点和传感节点具有相同的通信半径,且表示为R。当节点在自己通信范围内时,节点就能与其直接通信,否则只能通过多跳通信。

图1 网络模型

1.2 问题描述

本文提出基于锚节点的传感节点定位算法。因此,此类算法要求传感节点至少获取离3个锚节点间的距离。为此,每个锚节点广播自己的位置。假定第k个锚节点的位置(ak,bk)。如果第i个传感节点离锚节点距离小于或等于R,它就接收此锚节点位置,且跳数nh=1。否则,要以nh≥1跳数才能收到些锚节点位置信息。

目前,多数定位算法均采用,式(1)估计第i个传感节点离第k个锚节点的距离di,k:

(1)

式中:hav为预定平均跳数尺寸。

实际上,式(1)依赖于密集的WSNs,且依赖于式(2)的成立:

(2)

式中:h表示第个跳距离。

然而这类算法存在不足。通常,有两种算法计算hav。第一种就是通过泊松限制理论的分析[9-11],如hav=E{h};第二种是利用锚节点间短路径计算均值:

(3)

式中:nk,表示第k个和第个锚节点间的跳数。很明显,hav并不等于跳距均值,即

因此,跳距可能存在误差,这降低了定位精度。为此,本文通过寻找更准确的hav,进而提高定位精度。

2 LSSVR-LA

LSSVR-LA算法先利用Secant算法测距,然后引用LSSVR定位算法估计未知节点位置。

2.1 基于Secant测距

首先引用变量:转发区域F。假定Dk(R)和Di(R)分别表示第k个锚节点和第i个传感节点的通信区域,如图2所示。

图2 转发区域示意图

而第k个锚节点与第i个传感节点间的转发区域F等于它们通信区域的交集,即F=Dk(R)∩Di(R)。位于F内的节点负责将消息从第k个锚节点转发至第i个传感节点。

从图2可知,转发区域F依赖于锚节点ak与传感节点si的距离di,k。接下来,通过转发区域F估计di,k。

从图2可知,距离di,k越大,转发区域F越小。利用解析几何和三角转换,可计算转发区域F:

(4)

图3 两跳转发HELLO包的示意图

(5)

(6)

2.2 锚节点信息广播

锚节点周期地广播HELLO包,其包含了锚节点位置和跳数以及距离项。假定锚节点ak的坐标位置为(xk,yk),其跳数和距离值分别表示为n、d。n和d的初始值均为零。

当传感节点接收来自锚节点广播的HELLO包后,首先确认之前是否已接收同样的包。若没有,则存储该锚节点位置信息和跳数,并估计距离,再将跳数加1,将估计距离加入HELLO包,再转发出去。如果已接收HELLO包,则将已存在的跳数nold和现在所接收的跳数n进行比较。如果nold大于n,则更新nold,即nold←n。否则,对HELLO包不进行任何处理,直接转发。处理HELLO包流程图,如图4所示。

图4 处理HELLO包的流程图

2.3 最小二乘支持向量回归机LSSVR定位算法

在获取与锚节点间的测距信息后,再利用LSSVR估计节点位置。LSSVR算法定位步骤如下:①先估计样本网格节点离锚节点距离;②利用距离与样子节点坐标间关系,建立回归模型;③利用式(6)估计的距离作为LSSVR的输入,其输出就为未知节点位置。LSSVR的定位算法框图如图5所示。

图5 基于LSSVR的定位算法流程图

LSSVR定位算法主要由核函数选取、样本节点位置的抽样、样本集的训练、定位模型的建立、测距和定位6个阶段组成。

首先,引用径向基函数RBF(Radial Basis Function)作为核函数[12],定义如式(7)所示:

(7)

(8)

第五步,测距。利用式(6)进行测距,并作为LSSVR的输入;

最后,定位。将已估算的距离数据输入到LSSVR,系统输出则为传感节点位置估计值。

3 仿真与分析

本小节分析LSSVR-LA定位算法性能。在定位区域A=100 m×100 m内随机分布100个传感节点,锚节点数M从10～50变化,通信半径R从15 m～50 m变化。为了更好地分析LSSVR-LA性能,选择基于粒子群优化的加权质心定位算法RSSI-WP[13]和基于RSSI差分校正的最小二乘-拟牛顿定位算法[14]进行参照。

同时,选择归一化平均定位误差作为性能指标,其定义如式(11)所示。

(9)

图6 归一化平均定位误差

①锚节点数对归一化平均定位误差的影响

假定通信半径R=30 m,锚节点数从10～50变,步长为5 m,实验数据如图6所示。

从图6可知,归一化平均定位误差随锚节点数增加而下降。原因在于:锚节点数越多,获取的距离信息越多,这越有利于提高定位精度。与RSSI-WP和RSSI-DLN相比,LSSVR-LA算法的归一化平均定位误差分别下降了近28%～36%、16%。这主要是因为:LSSVR-LA算法通过Secant迭代算法提高了测距精度,并利用LVSSR算法进行定位,通过训练样本,提高了定位精度。而RSSI测距易受外界环境影响,误差较大。

②通信半径R对归一化平均定位误差的影响

本小节分析通信半径R对归一化平均定位误差的影响,且锚节点数为20,通信半径R从15 m～50 m变化,实验数据如图7所示。

图7 归一化平均定位误差随节点通信半径的变化曲线

从图7可知,归一化平均定位误差随通信半径呈U型变化趋势。当通信半径处于较小区间时,通信半径的增加有利于提高定位精度,降低误差。而当通信半径R大于30 m后,半径的增加反而提高了归一化平均定位误差。从图7可知,当R=33 m时,归一化平均定位误差最低。此外,与RSSI-WP和RSSI-DLN相比,LSSVR-LA算法的定位精度得到提高。与RSSI-WP算法相比,LSSVR-LA算法的归一化平均定位误差下降了近36%。

③算法复杂度

为了表述算法复杂度,记录了算法运行时间。在同等条件下,算法运行时间越长,复杂度越高。3个算法的运行时间如表1所示,其中R=30 m,锚节点数为35。从表1可知,LSSVR-LA算法的定位误差最低,但运行时间并非最低,略高于RSSI-WP。原因在于:LSSVR-LA算法需要采集样本,并对样本进行训练,这增加了运行时间。

表1 算法的运行时间

4 总结

针对多跳无线传感网络的定位问题,提出基于最小二乘支持向量回归机定位算法LSSVR-LA。LSSVR-LA算法先分析了传统的多跳测距的不足,然后利用Secant算法测距,最后由LSSVR估计传感节点位置。通过定位精度和算法复杂度实验,实验数据表明,LSSVR-LA算法提高了多跳WSNs的定位精度,并没有增加算法复杂度。后期,将进一步提高定位精度,并优化算法,降低算法复杂度。

[1] 李娟,刘禹,钱志鸿,等. 基于双通信半径的传感器网络DV-Hop定位算法[J]. 吉林大学学报(工学版),2014,44(2):502-508.

[2] 金纯,叶诚,韩志斌. 无线传感器网络中DV-Hop定位算法的改进[J]. 计算机工程与设计,2013,34(2):401-405.

[3] 王新生,赵衍静,李海涛. 基于DV-Hop算法的改进研究[J]. 计算机科学,2011,38(2):76-78.

[4] Lachowski R,Pellenz M E,Penna M C,et al. An Efficient Distributed Algorithm for Constructing Spanning Trees in Wireless Sensor Networks[J]. Sensors,2015,15(1):1518-1536.

[5] Tomic S,Mezei I. Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]//Process IEEE 10th Jubilee Int Symp Intell Syst Inform,2012:389-394.

[6] Elgamel M S,Dandoush A. A Modified Manhattan Distance with Application for Localization Algorithms in Ad-Hoc WSNs[J]. Ad Hoc Netw,2015(33):168-189.

[7] Zou D B,Wang Y B. Adaptive Energy-Aware Routing Framework in Transmission Cost Constrained Wireless Sensor Networks[C]//Proc IEEE Global Commun Conf(GLOBECOM),2013:534-538.

[8] 张佳,吴延海,石峰,等. 基于DV-Hop无线传感网络定位算法[J]. 计算机应用,2010,30(2):323-326.

[9] Huang B,Yu C,Anderson B D O,et al. Estimating Distances Via Connectivity in Wireless Sensor Networks[J]. Wireless Commun. Mobile Comput,2014,14(5):541-556.

[10] El Assaf A,Zaidi S,Affes S,et al. Efficient Range-Free Localization Algorithm for Randomly Distributed Wireless Sensor Networks[C]//Proc IEEE GLOBECOM,Atlanta,GA,USA,2013:201-206.

[11] El Assaf A,Zaidi S,Affes S,et al. Range-Free Localization Algorithm for Heterogeneous Wireless Sensor Networks[C]//Proc IEEE WCNC,Istanbul,Turkey,2014:2805-2810.

[12] 张晓莲,唐加山. 基于改进RSSI测距的LSSVR三维WSN定位算法[J]. 电视技术,2014,38(19):131-135.

[13] 王新芳,张冰,冯友兵. 基于粒子群优化的改进加权质心定位算法[J]. 计算机工程,2012(1):90-92.

[14] 程秀芝,朱达荣,张申,等. 基于RSSI差分校正的最小二乘法-拟牛顿定位算法[J]. 传感技术学报,2014,27(1):123-128.

王自力(1978-),男,汉族,河南驻马店人,硕士,副教授,研究方向为计算机应用及物联网技术;

郑鑫(1977-),女,汉族,河南驻马店人,硕士,副教授,研究方向为计算机应用及物联网技术。

Least-SquaresSupportVectorRegression-BasedLocalizationAlgorithminMulti-HopWirelessSensorNetworks*

WANGZili1*,ZHENGXin2

(1.Department of Information Engineering,Zhumadian Career Technical College,Zhumadian He’nan 463000,China;2.Information Engineering Institute,Huanghuai University,Zhumadian He’nan 463000,China)

In multi-hop wireless networks,location based applications require an accurate localization algorithm. Therefore,Least-Squares Support Vector Regression-based Localization Algorithm(LSSVR-LA)is proposed in this paper. LSSVR-LA introduces a forwarding area,and construct ranging model by forwarding area. Then,the distance between sensors and anchor nodes are estimated by Secant algorithm. The distance is used as the input vector of LSSVR machine,and localization model-based LSSVR is constructed. Numerous simulation results show that LSSVR-GF-RSSI algorithm reduces at least 12% in average localization error compared with traditional localization algorithm.

wireless sensor network;ranging;secant algorithm;least-squares support vector regression;localization

TPT393

A

1004-1699(2017)11-1747-05

项目来源:河南省高等学校青年骨干教师计划项目(2015GGJS-300)

2017-04-05修改日期2017-07-17

10.3969/j.issn.1004-1699.2017.11.022