一种基于残差分析过滤的安全定位算法

2017-06-19刘宏立

重庆邮电大学学报(自然科学版) 2017年3期

关键词：传感残差梯度

滕云，刘宏立，徐琨

(湖南大学电气与信息工程学院，长沙 410082)

一种基于残差分析过滤的安全定位算法

滕云，刘宏立，徐琨

(湖南大学电气与信息工程学院，长沙 410082)

在无线传感网络节点定位中，恶意锚节点的出现会降低网络定位性能，为了解决这个问题，根据节点定位过程中的恶意锚节点攻击特性和定位计算中的残差问题，提出一种基于残差分析和过滤的无线传感网络安全定位算法。建立了基于距离的安全定位模型，对网络定位中的残差问题进行了分析，并且通过残差特性过滤掉网络中恶意锚节点，利用剩余锚节点信息和梯度下降法对未知节点实现高精度定位。仿真表明，此算法在多个性能指标下都能取得相对较高的定位精度，并且在高强度的恶意攻击下也能保持较高的定位性能。此算法不但能有效地抵御恶意攻击对节点定位的破坏，还显著地加强了网络的定位安全性。

无线传感网络；安全定位；梯度下降法；残差分析；过滤

0 引言

无线传感网络(wireless sensor network，WSN)是由大量成本低廉，存储空间、计算能量有限的传感节点组成。他们能在短时间进行数据通信，具有功耗低，组网快捷的特点而被广泛运用到民用和军事领域，如森林防火、战场监控[1]、环境监测[2]和洪水监控等。传感器节点的位置对于无线传感网络十分重要，因为节点定位对于大多数基于位置的路由协议和应用都起着关键的作用，所以研究人员对定位技术已经产生了广泛的兴趣并针对不同方向进行了研究。如WSN的定位效率[3]和定位精度[4]等问题。

基于距离[5](range-based，RB)的定位算法中，定位节点使用不同邻居节点的距离信息估计它们的位置，然后通过三边测量法、三角测量法或者最大似然估计法[6]进行定位。但是，由于WSN的特点原因，无线传感网络节点经常部署在无人监控的区域中，甚至是恶意危险的环境中，使其很容易受到攻击者的各种恶意攻击[7]，这些攻击往往通过信号干扰或者捕获网络中的锚节点来对定位过程进行破坏，使网络中的节点不能够准确地定位，从而导致整个网络无法正常工作。因此，安全定位对WSN有着重要作用。

针对在恶意环境下的无线传感网络安全定位问题，研究人员已经提出了多种安全定位策略[8]。文献[9]通过分析多径效应和外部干扰对接收信号强度指示(received signal strength indication, RSSI)的影响，提出采用频率分割集来克服多径效应对RSSI的影响，通过改善RSSI的测距精度来提高定位的精度。文献[10]提出了一种基于到达时间差(time difference of arrival, TDoA)的2步法安全定位算法，通过锚节点之间的检测和信誉分级找出并过滤恶意锚节点，最终实现了高精度的定位结果。文献[11]提出了一种名为Beta信誉系统(Beta reputation system)的安全定位算法，使用信誉系统筛选锚节点，并利用加权泰勒展开式的最小二乘算法来获得最终的定位位置，该算法有效地减轻了恶意锚节点对网络节点定位的影响。但是利用信誉机制筛选锚节点会给网络节点带来很大的能量消耗，影响了网络运行效率。文献[12]针对WSN定位中遇到的独立攻击，利用最速下降法和恶意锚节点检测技术选出最优锚节点数据，并结合牛顿迭代法实现了快速高精度的三维安全定位。

本文提出的安全定位算法是一种过滤算法，结合梯度下降法和残差分析过滤的方式，利用残差特性过滤掉网络中的恶意锚节点，对未知节点进行高精度迭代定位。本文算法与文献[13]提出的结合梯度下降法和异常检测方式的算法有相似之处。但由于过滤算法方式的区别使得在定位精度上有一定区别，仿真结果表明本文所提出的算法能得到更好的定位精度。

1 安全定位模型

在基于测距的定位算法中，未知节点需要通过通信方式收集邻居锚节点的距离和位置信息集{(x,y),d}，然后通过三角测量或者三边测量来计算未知节点的位置。

d2(x,y)=(x-xi)2+(y-yi)2

(1)

当n≥3时，根据公式(1)列出这n个方程，利用最小二乘法(least square, LS)就能得到未知节点M的准确值。

(2)

(3)

(4)

可以推得

‖Li-L‖

那么，定义目标函数

(5)

因此，定位问题就等价于寻找使目标函数λ(L)达到最小值的点L0。

2 安全定位算法

2.1 梯度下降法

基于上述安全定位模型分析，目标函数λ(L)是一个凸函数，因此可以用梯度下降法对(5)式求解非线性最小值点。首先，随机给出估计值的初始值L(0)。在第k步的迭代计算中，根据当前估计值L(k-1)的值，估计第k步的值。求解第k次的梯度向量

(6)

(6)式中：▽(·)表示位置值L的导数。于是可以得到第k步的刷新估计值

(7)

(7)式中：γ(k)是第k次迭代的步长；(g(k))/(|g(k)|)表示梯度负方向的单位向量，即梯度下降第k次迭代的搜索方向。那么根据目标函数(5)求得的第k次搜索方向为

(8)

(8)式中：L为第(k-1)次迭代得到的估计坐标值。每次迭代都会得出一个新的估计值，这个估计值都会更接近未知节点的真实坐标值。

2.2 基于残差分析的过滤算法

由于WSN中存在着一部分的恶意锚节点，使得未知节点得到的部分距离测量值不准确，定位所需的信息集{(xi,yi),di}与(1)式不相容，所以使用梯度下降法无法得到精确解，最终估计值会出现很大的误差，因此考虑使用一种过滤算法，在迭代计算的过程中，通过算法找到恶意锚节点，并且将其滤除，使用剩下的信息集对未知节点进行定位运算。

分析定位迭代计算中的残差问题。根据安全定位模型，第i个锚节点对应的定位残差为

(9)

(9)式中，[xest,yest]T表示第k次迭代得到的估计位置值。那么可以求得所有锚节点的定位残差总和为

(10)

于是在一次迭代运算中，所有锚节点对应的定位残差平均值为

(11)

最终，可以得到每个锚节点的残差偏差值，

(12)

残差偏差的值代表了每个锚节点对应的残差以残差平均值为中心的分散程度。残差偏差越大，说明其对应的锚节点贡献的结果越偏离其他大多数锚节点。

在恶意攻击存在的情况下，梯度下降法不能保证每一个锚节点对应的定位残差绝对值很小，总会存在一部分的锚节点对应的定位残差会大于其他的锚节点。根据安全定位模型，恶意锚节点的存在必将增加总定位残差。因此，可以利用这个原则，在迭代计算收敛于LS解时，计算每个锚节点对应的Δdi残差大小或者ei，并对它们的大小按升序排列，剔除掉残差较大或者残差偏差很大的锚节点，利用剩余锚节点计算未知节点的坐标，这样能够减小定位误差。

为了选择过滤的参考参数，对根据残差大小和根据残差偏差大小剔除锚节点2种方式进行了仿真对比，仿真条件如下： 40个锚节点和一个未知节点随机分布在大小为100 m×100 m的区域内，测量噪声标准差η=2 m，初始迭代点L(0)在区域中随机选取，恶意锚节点数占总锚节点数的40%，所有的仿真结果都通过1 500次运行取平均值得到。2个方法都滤除50%锚节点。

图1显示了2种过滤参数在不同的攻击强度下的平均定位误差。从图1中可以看出，在所有攻击强度下，根据残差偏差大小过滤锚节点得到的定位误差明显小于根据残差大小过滤的情况。

图1 不同攻击强度下的定位误差对比图Fig.1 Comparison chart of positioning errors at different attack intensities

然而在迭代计算结果收敛于LS解之前，恶意锚节点参与了未知节点坐标计算，所以这个估计值得到的定位残差Δdi或者残差偏差ei都不能完全反映真实的情况，因此，需要对残差和残差偏差进行综合考虑，剔除掉残差和残差偏差都较大的锚节点。

为了证明此综合过滤方法的有效性，对此算法与根据残差偏差大小过滤的算法进行了仿真比较。如图2所示，在不同的攻击强度下，此算法在定位精度上要明显优于残差偏差大小过滤法。

图2 综合过滤与残差偏差大小过滤的定位误差比较Fig.2 Comparison of positioning errors between synthetic filtering and residual deviation

出现这种现象的原因是：在迭代运算收敛于LS解时，由于有恶意锚节点提供的恶意信息集{(xm,ym),dm}，特别是恶意锚节点的攻击强度过高或者恶意锚节点的数量过多时，导致整体的残差平均值被拉高，这样诚实锚节点对应的残差偏差值就会高于部分恶意锚节点，于是就会出现一种现象，即部分诚实锚节点对应的残差值很小，而残差偏差值很大，那么如果只考虑残差偏差值的大小，这部分诚实锚节点就有很大可能会被过滤掉，这样必定会增大定位误差。而对2个参数进行综合考虑的话，就可以避免这部分诚实锚节点被算法滤除掉。

3 仿真结果与分析

本节对本文所提出的算法进行了仿真分析，并在相同的条件下与其他几种算法进行了比较。对比的3种算法分别是最小中位二乘法(least median square, LMS)、投票算法和梯度下降法。仿真条件为： 40个锚节点和一个未知节点随机分布在大小为60 m×60 m的区域内，测量噪声标准差η=2 m，初始迭代点L(0)选择点[0，0]T，所有的仿真结果都通过1 500次运行取平均值得到。

首先仿真了攻击强度与定位误差之间的关系。设恶意锚节点数占总锚节点数目的40%，在攻击强度为2～20 m的情况下，仿真结果如图3所示，图3中4个算法在攻击强度增加的情况下，都能稳定在理想的定位误差范围之中，而本文提出的算法在所有攻击强度下的定位误差都明显小于其他3种算法。

然后对恶意锚节点所占百分比与定位误差关系进行了仿真。设攻击强度为10 m，仿真结果如图4所示。图4中随着恶意锚节点个数的增加，定位误差都有所升高，并且当恶意锚节点数占到50%以上时，曲线斜率增幅变大。本文提出的算法在不同恶意锚节点个数情况下的定位误差比其他3种算法都要小，特别是当恶意锚节点数目过多时，本文提出的算法依然能保持在理想的定位精度范围内，并且定位误差远小于其他3种算法。

图3 定位误差与攻击强度关系比较(恶意锚节点占40%)Fig.3 Comparison of relationship between positioning errors and attack intensities

图4 恶意锚节点所占百分比与定位误差关系比较(攻击强度为10 m)Fig.4 Comparison of relationship between positioning errors and percentages of malicious anchor

最后为了检验算法定位的准确性，对定位收敛到真实位置的概率进行了仿真比较。设网络中恶意锚节点数占总锚节点数目的60%时仿真结果如图5所示。由于网络中通信噪声等因素的干扰，决定平均定位误差在3 m范围内，就认为它定位到了真实的位置。从图5中可以看出，在攻击强度小于6 m时，随着攻击强度的增加，所有算法定位到真实位置的概率下降较快，但是都能保持在70%以上。随着攻击强度的继续增加，LMS和投票法的定位准确概率持续下降，而本文所提出的算法和梯度下降法能够稳定在80%以上的范围，但是本文算法定位准确概率稍优于梯度下降法。

图5 攻击强度下定位到真实位置的概率比较(恶意锚节点数占60%)Fig.5 Comparison of probabilities of locating to real locations under attack

综合上述仿真和比较，本文提出的算法在以上参数情况下都要优于LMS、投票法和梯度下降法3种算法，并且本文提出的算法在恶意攻击强度和恶意锚节点数目很高的环境下都能保持十分理想的定位精度，而且定位误差远小于LMS和投票法。

4 结论

本文介绍了一种在恶意环境中适用于无线传感网络中的安全定位算法，算法结合了梯度下降法和基于残差分析的过滤算法，通过仿真实验证明了过滤算法的有效性，能有效地过滤掉网络中的恶意锚节点，极大减少了恶意攻击对网络节点定位的干扰。通过仿真对比，表明本文提出的算法能在恶意环境下抵御恶意攻击对网络节点定位的攻击，并且具有很强的鲁棒性。

[1] DEMIGHA O, HIDOUCI W K, AHMED T. On energy efficiency in collaborative target tracking in wireless sensor network: a review[J]. Communications Surveys & Tutorials, IEEE, 2013, 15(3): 1210-1222.

[2] 孙启永，张文，李海波，等．基于微电极阵列和无线传感器网络的水环境重金属检测系统研究[J].传感技术学报，2013，26(7): 907-911． SUN Qiyong, ZHANG Wen, LI Haibo, et al, In-Situ Heavy Metal Detection in Field Aquatic Environment Based on Wireless Sensor Network and Micro Electrode Array[J]. Chinese Journal of Sensors and Actuators, 2013，26(7): 907-911．

[3] YANG S K, SSU K F. An energy efficient protocol for target localization in wireless sensor network[J]. World Academy of Science, Engineering and Technology, 2009, 56(8): 398-407.

[4] 任枫轩. 高精度递增式无线传感网络的定位算法[J]. 重庆邮电大学学报:自然科学版,2013,02:184-186，191. REN Fengxuan, High-precision incremental localization algorithm for wireless sensor network[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2013,02:184-186,191.

[5] 彭宇，王丹．无线传感器网络定位技术综述[J].电子测量与仪器学报，2011，25(5): 389-399． PENG Yu，WANG Dan. A review: wireless sensor networks localization[J]. Journal of Electronic Measurement and Instrument, 2011, 25(5): 389-399．

[6] SALMAN N, GHOGHO M, KEMP A H. On the joint estimation of the RSS-based location and path-loss exponent[J]. Wireless Communications Letters, IEEE, 2012, 1(1): 34-37.

[7] BOUKERCHE A, OLIVEIRA H A B F, NAKAMURA E F, et al. Secure localization algorithms for wireless sensor networks[J]. Communications Magazine, IEEE, 2008, 46(4): 96-101.

[8] 叶阿勇，许力，林晖. 基于RSSI的传感器网络节点安全定位机制[J]. 通信学报, 2012, 33(7): 135-150. YE Ayong, XU Li, LIN Hui, Secure RSSI-based node positioning mechanism for wireless sensor networks[J]. Journal on Communications, 2012, 33(7): 135-150.

[9] MRAZ L, CERVENKA V, KOMOSNY D, et al. Comprehensive performance analysis of ZigBee technology based on real measurements[J]. Wireless personal communications, 2013, 71(4): 2783-2803.

[10] HAN G, JIANG J, SHU L, et al. A two-step secure localization for wireless sensor networks[J]. The Computer Journal, 2013, 56(10): 1154-1166.

[11] YU N, ZHANG L, REN Y. BRS-based robust secure localization algorithm for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2013,(11):560-572

[12] 陈宜,蒋朝惠,郭春. 一种抗独立攻击的WSN三维安全定位算法[J]. 传感技术学报,2015,28(11):1702-1707. CHEN Yi, JIANG Chaohui, GUO Chun. A 3D Secure Localization Algorithm Resistant to Non-Coordinated Attack in Wireless Sensor Network[J]. Chinese Journal of Sensors and Actuators, 2015,28(11):1702-1707.

[13] GARG R, VARNA A L, WU M. An efficient gradient descent approach to secure localization in resource constrained wireless sensor networks[J]. IEEE Transactions on Information Forensics and Security, 2012, 7(2): 717-730.

(编辑：张诚)

s：The Central State-Owned Capital Operating Budget Project of China (2013-470)；The Central Universities Basic Research Project of China (2014-004)；The National Natural Science Foundation of China (61172089)；The Planned Science and Technology Project of Hunan Province of China (2014WK3001)；The Post-doctoral Science Foundation of China (2014M562100)；The Planned Science and Technology Key Project of Hunan Province of China (2015JC3053)

A secure localization algorithm based on residual analysis filtration

TENG Yun, LIU Hongli, XU Kun
(College of Electrical and Information Engineering, Hunan University, Changsha 410082,P.R. China)

During the process of localization in the wireless sensor network, the appearance of malicious anchor nodes will destroy the performance of network positioning. In order to solve this problem, a new wireless sensor network security algorithm is proposed，which based on the characteristics of malicious anchor nodes and the residual problem in location calculation. Firstly, a distance-based security location model is established. Then the residual problem in the network location is analyzed, and the malicious anchor nodes in the network are filtered out by the characteristic of residual. Finally, the unknown nodes are realized high-precision positioning result by the information of residual anchor node and gradient descent method. The simulation results show that the proposed algorithm can achieve relatively high positioning accuracy under a variety of performance indexes, and can maintain high positioning performance even under intensified malicious attacks. So this algorithm can not only effectively resist the malicious attack on the node location, but also significantly enhance the security of network localization.

wireless sensor networks; secure localization; gradient descent; residual analysis; filtering

2016-06-11

2017-04-25 通讯作者：刘宏立 honglilin@hnu.edu.cn

中央国有资本经营预算项目(2013-470)；中央高校基本科研项目(2014-004)；国家自然科学基金(61172089)；湖南省科技计划项目(2014WK3001)；中国博士后科研基金(2014M562100)；湖南省科技计划重点项目(2015JC3053)

10.3979/j.issn.1673-825X.2017.03.004

TN212.9

1673-825X(2017)03-0307-06