基于改进的质心定位的LSSVR算法的设计

周成纲，饶国勇

(1.绍兴职业技术学院,浙江 绍兴 312000； 2.景德镇学院 信息工程系，江西 景德镇 333000)



基于改进的质心定位的LSSVR算法的设计

周成纲1，饶国勇2

(1.绍兴职业技术学院,浙江 绍兴 312000； 2.景德镇学院 信息工程系，江西 景德镇 333000)

针对无线传感中基于质心算法的节点定位存在误差比较大,算法效率低的缺点,提出了一种基于加权的LSSVR的节点定位算法；首先,对未知节点构建节点序列相关度,采用Kendall的Tau指标来估计未知节点的位置,提高了未知节点的定位精度,其次引入了LSSVR概念,构建改进质心算法的LSSVR定位模型,降低了噪声影响,大幅度提高定位精度；仿真实验表明该算法与基本的LSSVR算法在定位精度上有了明显的提高,在锚节点,未知节点所占比例不断增大的情况下该算法定位精度具有很大的提高,降低了算法的计算复杂度,具有较高的应用价值。

无线传感; 序列相关度; LSSVR; 节点定位

0 引言

节点定位一直以来都是无线传感网中的研究热点,主要包括两个方面:距离有关定位算法和距离无关定位算法。前者主要依靠锚节点和未知节点之间直接距离进行定位，后者是通过节点的估算来进行定位,其中质心算法是一种计算简单,消耗硬件能量低的距离无关定位算法,其缺点是定位误差比较大[1],杨新宇[2]提出了一种利用信号强度比值的加权质心定位算法.其定位精度可提高5.12%～11.23%;赵栋栋[3]提出了根据跳数对锚节点组成的三角形多次求解质心,取得了比较好的定位效果;吕振[4]提出利用了信标节点与未知节点之间距离的倒数之和作为信标节点的权值来实现对未知节点的定位；刘玉军[5]提出多信标节点质心定位修正算法,通过该算法计算得到多组未知节点估计坐标,并在此基础上利用质心定位修正算法计算节点坐标修正值; 施伟[6]提出一种基于接收信号强度(RSSI)的改进加权质心定位算法;王缓缓[7]提出用初次质心定位结果来取代未知节点通信半径内距未知节点最远的锚节点,采用二次定位来减小由于锚节点导致未知节点的估计位置的情况;王振朝[8]提出在该算法中采用节点距离倒数之和代替距离和的倒数作为权值,该算法具有一定的有效性。

本文在质心算法上构建节点序列相关度,通过Tau指标来求解未知节点的估计位置,其次引入了LSSSVR,构建质心定位算法的LSSVR定位模型。

1 质心定位算法简述

在无线传感网质心算法中,质心是众多的锚节点构成的多边形的几何中心点,其值是通过多边形顶点的坐标的平均值。如图1所示,黑色实心表示锚节点,空心节点表示待定位的节点,G为锚节点{A,B,C,D,E}构成的质心节点。

图1 无线传感网中节点和质心示意图

选取图中的5个锚节点,分别为A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4),E(x5,y5),这5个图的形成的五边形的质心G(x,y)坐标为:

(1)

质心定位算法的原理:首先通过锚节点的组成的多边形的区域计算质心的坐标,然后以此来确定未知节点的位置。假设在某一段时间内,未知节点探测到与K个锚节点进行信息通讯,将锚节点的坐标表示为Anchorj(x,y)=(xj,yj),因此未知节点P(x,y)的坐标为:

(2)

从式(2)中可以发现质心算法优点是设计简单,容易实现,缺点是未知节点的定位精度取决与周围锚节点的分布密度,当锚节点结构均匀分布,则未知节点自身定位的精度就会越高,反之,则会降低,这说明未知节点的定位取决于质心定位的精度。同时质心算法的定位精度在一定程度上与无线传感网中的锚节点数量有关。锚节点数量所占的比例越大,与未知节点能够连通的锚节点就越多,因此,质心算法估计的位置就越接近未知节点的真实位置[9]。文献[10]提出在锚节点密度低的区域增加锚节点数量,以此提高定位的精度。

2 改进的质心定位算法

2.1 节点间序列相关度

根据锚节点与未知节点在定位上具有的某种关系,本文采用Kendall的Tau指标来进行节点定位之间的相关度的说明,设定两个定位序列S={s1,s2,…,sn}和T={t1,t2,…,tn},那么Kendall阶次相关系数为:

(3)

Kendall的Tau指标为:

(4)

其中:

(5)

(6)

(7)

(8)

2.2 序列加权的节点定位算法

(1)构建质心参考节点。由于未知节点的定位与多个锚节点的坐标所构成的质心节点的定位有关,因此,将锚节点组成的多边形划的顶点存储在某一个数据数组中,整个数组记为质心参考点。

(2)参考点序列的建立。首先根据式(9)求出每一个多边形的质心参考坐标(ηx,ηy),确定质心参考点的定位序列。

(9)

(3)未知节点的定位序列构建。通过与锚节点的距离远近得到未知节点的定位序列。在图2中,(U1,U2,U3,U4)分别代表未知节点,(A,B,C,D,E)分别代表锚节点,每一个未知节点序列为Ui(X/y)中的X表示接收到来自各个锚节点的信号的次序,y表示未知节点与锚节点间的距离,因此可以得到未知节点到锚节点的序列等级。

图2 未知节点序列构建

(4)未知节点位置估计。未知节点通过序列S按照式(4)计算阶数序列表T={T1,T2,…Tk}中所有序列的相关度,构成每一个序列的集合(TN)。通过相关度在[-1,1]区间变换后的值作为权重,通过参考节点η进行加权估算未知节点(x,y)的位置为:

(10)

3 基于质心定位的LSSSVR的定位算法

3.1 LSSVR误差分析

在理想的LSSVR模型中输入的样本是没有噪声干扰,因此得到的输出样本是也是非常精确的。但在实际环境中,LSSVR通过少量的训练样本来获得反应未知节点的目标定位的映射关系,由于噪声的影响,LSSVR模型的输入就存在一定的误差,因此基于LSSVR的定位算法的误差反映了模型的预测能力,误差越小,精度就越高。

3.2 基于质心定位的LSSVR模型的建立

为了进一步降低误差,本文在LSSVR模型上,改进训练学习过程,将网格进行划分,以一定的步长来构建以未知节点为中心的参考节点的密度,从而提高LSSVR模型的定位精度。通过公式(10)获得未知节点的大概位置以及相应的网格节点形成的训练样本。模型建立步骤如下,流程如图3所示。

4)定位模型的获得: 将训练样本Ux和Uy作为定位模型的输入,获得相应的训练样本的定位模型X-LSSVR,Y-LSSVR。

5)未知节点样本:将校正后的未知节点S与锚节点Mi(i=1,2,…m)之间距离di,组成距离向量w=(d1,d2,…dM)。

6)未知节点定位:将距离向量w输入到定位模型中,分别计算输出值(x′,y′)。

图3 基于改进的质心定位算法的LSSVR定位模型

4 仿真实验

本文选择本实验选取100 m*100 m的空旷区域,选取30个节点,其中10个节点为锚节点,剩余的20个为未知节点。搭建计算机硬件平台CPU为酷睿i3,4GDDR,500 G,软件平台采用Matable2010。为了进一步验证本文算法具有的优越性,将本文的算法与其他的质心定位算法进行比较。图4为本文算法的定位效果。从图中可以发现本文算法下的定位的精度有了明显的提高,位置节点的实际未知与计算位置平均相差不大,有1～2个节点的出现的偏差不大,适合在多节点情况下的无线传感节点定位中的应用。

图4 本文算法定位仿真效果

4.1 与基本的LSSVR定位算法相比

将本文的算法与基本的LSSVR算法通过50次的蒙特卡洛计算,得到的结果如图5所示,从图中可以发现本文算法的平均误差范围在5.14%～8.27%,而基本的LSSVR算法的平均误差范围在8.18%～12.03%。本文算法相比与基本的LSSVR算法相比定位精度提高了15.29%～24.31%。这说明本文的算法在定位误差方面具有更高的稳定性和可靠性。

图5 两种算法的定位误差比较

由于质心定位过程中存在步长选择和路径损失两个因素的影响,因此本文算法与基本LSSVR算法在这两个方面进行了对比,对比结果如表1～2所示。从表1中发现,本文算法伴随着步长的增加对定位误差的影响小于基本的算法,这说明在条件允许的情况下步长的增加能够提高训练网格的精度,从而能够提高未知节点定位精度。从表2中发现伴随着路径损耗系数的增大,本文算法的定位误差精度小于基本LSSVR算法平均3%,随着路径损失越大,定位误差精度只差越明显,这说明在同样的路径损耗下本文算法优于基本LSSVR算法。

表1 步长对两种算法定位误差的影响

表2 路径损失对两种算法定位误差的影响

4.2 与其他定位算法的比较

将本文算法与最新的误差定位方面的算法进行比较,通过与文献[5],文献[6]算法的比较来进一步说明本文算法的优点。

1)未知节点比例变化的定位误差比较：

假定总节点的数目保持不变,伴随着未知节点个数逐渐增多,本文算法,文献[5]算法和文献[6]算法的定位误差变化曲线如图6所示。从图中得到,本文算法在未知节点数目相对较少的时候,定位误差小于文献[5]和文献[6]算法,这主要是因为阶次加权的过程中,构建了参考节点,导致误差下降,伴随着节点数目逐渐增多,本文算法的优势逐渐体现出来,即平均定位误差明显小于其他两种算法。

图6 不同未知节点数目下的3种算法定位误差2)锚节点数目比例变化的定位性能比较：

假设总节点的个数不变,伴随着锚节点个数的比率不断变化, 本文算法,文献[5]算法和文献[6]算法的定位误差变化曲线如图7所示。从图中发现,3种算法在锚数目比较少的时候相差不是很大,这说明3种算法都能适合锚节点数目少的时候,但伴随着锚节点的数目增多,3种算法的误差逐渐拉大,文献[5]和文献[6]的算法图像波动比较大,而本文算法的图像平缓,这说明本文算法收到锚节点数量的影响不大。

图7 不同锚节点个数的3种算法定位性能

5 结束语

针对无线传感定位中的质心定位算法存在的不足,首先采用了序列加权的概念对未知节点的定位方法进行了改进,其次,引入LSSVR概念对改进后的节点定位的精度进一步改进。仿真实验说明本文算法与基本的LSSVR算法相比误差明显减低,通过与其他算法在锚节点,未知节点比例方面的定位误差相比有了显著的降低。

[1] 何艳丽.无线传感器网络质心定位算法研究[J].计算机仿真,2011,28(5):163-166.

[2] 杨新宇,孔庆茹,戴湘军.一种改进的加权质心定位算法[J].西安交通大学学报,2010,44(8):1-3.

[3] 赵栋栋,赵菊敏,李灯熬.基于质心迭代的DV-Hop定位改进算法[J].计算机测量与控制,2013,21(10):2764-2766.

[4] 吕 振,赵鹏飞.一种改进的无线传感器网络加权质心定位算法[J].计算机测量与控制,2013,21(4):1102-1104.

[5] 刘玉军,蔡 猛,高立恒.基于RSSI测距的传感器节点质心定位修正算法[J].计算机测量与控制,2014,22(9):2860-2862.

[6] 施 伟,高 军.无线传感器网络中基于RSSI的改进加权质心定位算法[J].计算机应用与软件,2015,32(12):68-70.

[7] 王缓缓,邱建文.基于区域分割的二次质心定位算法[J].2015,32(4):279-281.

[8] 王振朝,张 琦,张 峰.基于RSSI测距的改进加权质心定位算法[J].电测与仪表,2014,51(21):63-66.

[9] 李兆斌,魏占祯,徐凤麟,等. 无线传感器网络增强的质心定位算法及性能分析[J] .传感技术学报,2009,22 (4):1247-1250.

[10] Bulusu B,Heidemann J, Estrin D. Denstiny adaptive algorithms for beacon placement in wireless sensor networks[A]. In:Proceedings of IEEE ICDES[C]. Mesa, AZ,USA, IEEE Press,2001,489-498.

Design of LSSVR Location Algorithm based on Improved Centroid Location

Zhou Chenggang1,Rao Guoyong2

(1.Shaoxing Vocational&Technical College, Shaoxing 312000,China；2.Jingdezhen University Information technology department,Jingdezhen 333000,China)

Aiming at centroid algorithm’s setback of big errors and low efficiency in node positioning in wireless sensing, a weighted-based LSSVR node positioning algorithm is proposed. First of all, the place of unknown nodes is estimated by establishing node sequence correlation with Kendall’s Tau index, which has improved the positioning accuracy of unknown nodes. Secondly, LSSVR is introduced and LSSVR positioning model of improved centroid location algorithm is constructed to reduce the influence of noise. Simulation experiment shows that compared with basic LSSVR algorithm, this algorithm has significantly improved its positioning accuracy, and with the increasing proportion of anchor nodes and unknown nodes, positioning accuracy of the algorithm has been significantly improved, which has reduced its computational complexity, so this algorithm has relatively high application value.

wireless sensing; serial correlation, LSSVR, node location

2016-03-31；

2016-05-05。

浙江省教育厅科研项目(Y201534919);浙江省访问学者项目;浙江省教育技术研究规划课题(JB129)。

周成纲(1977-),男,讲师,硕士,主要从事物联网应用,移动互联方向的研究。

饶国勇(1976-)，男，江西省景德镇市人，副教授，硕士研究生，主要从事物联网技术、云计算技术、网络安全方向的研究。

1671-4598(2016)09-0224-03

10.16526/j.cnki.11-4762/tp.2016.09.062

TP3

A