基于偏差迭代的干扰源定位算法

侯当云，吕伟杰

（天津大学电气与自动化工程学院，天津300072）

基于偏差迭代的干扰源定位算法

侯当云，吕伟杰*

（天津大学电气与自动化工程学院，天津300072）

针对无线传感器网络易受干扰攻击而导致网络通信受阻甚至瘫痪等问题，为确定干扰源位置进而消除干扰、保障网络正常通信，提出了偏差迭代定位算法。在确定初始估计位置后，通过参与定位的三个候选节点的位置信息即可求出干扰源估计位置与实际位置的大致偏差，对不满足精度要求的初始估计位置进行迭代直到偏差小于规定阈值为止。该算法不依赖网络本身或者外部设备等复杂的硬件设施和技术支持，对现存方法中存在的定位误差大、网络耗能高等问题进行了改善。仿真实验证明，该算法在不同网络环境下定位效果均优于现存算法。

无线传感器网络；定位；偏差迭代；阈值；仿真

EEACC：7230doi：10.3969/j.issn.1004-1699.2015.12.015

无线传感器网络WSNs（Wireless Senor Networks）是由部署在监测区域内大量的廉价微型传感器，通过无线通信方式形成的一个多跳的自组织网络［1］。其巨大的发展前景和应用价值已经引起军事部门、工业界、学术界的广泛关注，同时，由于无线媒介的开放性、广播性等本质特征导致网络可以轻易的受到非法窃听、篡改消息和拒绝服务等许多安全威胁［2］，因此保证网络通信的安全性和可靠性变得日益重要。在无线传感器网络受到的各种威胁当中，干扰攻击（jamming）对网络的危害最大，干扰攻击的发起者称之为干扰源（jammer）。干扰攻击是一种通过占用网络节点通信信道，使其不能进行正常数据转发的拒绝服务攻击，敌人可利用无线网络的开放性等本质特征，轻易的在网络中设置干扰。为应对干扰攻击，传统方式通过采用直接序列扩频DSSS（Direct Sequence Spread Spectrum）和跳频序列扩频FHSS（Frequency Hopping Spread Spectrum）［3］等方法来增强网络防御能力从而抵抗干扰对网络造成的不利影响。但考虑到基于802.11的无线局域网、自组织网络以及基于802.15.4的无线分布式传感器网络在频宽、能耗以及计算能力方面的受限性［4-6］，并且对物理层的设计不仅复杂而且需要很强的技术支持，使得这些传统方法在实际应用中并不常用。

为了保证无线网络通信的可靠性，消除干扰带来的不利影响，找到干扰源所在的位置变得尤为重要。干扰源位置一旦确定，就可以通过对其进行彻底销毁或者通过设计路由协议避开被干扰区域从而完全消除干扰攻击对无线传感器网络的影响［7］。

1　相关工作

为了消除干扰对网络的攻击，我们首先需要了解各种网络攻击模型［8］。其次是网络对攻击的检测问题。本文假设是在固定攻击模型下，网络可以准确检测到干扰激活后进行的，因此不再考虑干扰的检测阶段。最后的关键问题是干扰源定位，定位问题是无线传感器网络中一个热点问题。

WSNs定位方法一般分为：基于测距（rangebased）的定位和测距无关（range-free）的定位。基于测距的定位算法主要是通过测量和传输节点俘获的一些物理属性，如信号强度［9］、到达时间差等信息进行定位。其中具有代表性的是chen等人［10］提出的基于接收信号强度的定位算法，通过测量节点接收信号强度RSS（Received Signal Strength）值，利用RSS与距离之间的关系来估计干扰源位置。但是在Jamming攻击环境下，被干扰区域的通信已被全部或者部分损坏，并且网络中存在的多路径衰退效应使得测量和传输准确的RSS值难度大大提高，因此基于测距的定位在实际环境中定位效果差不适宜于干扰定位。

测距无关定位算法则依靠尽可能少的信息，如已知的部分节点位置信息、节点转发跳数等进行定位，其中经典算法包括纯质心定位算法CL（Centriole Localization）及考虑权重的质心定位算法［11］WCL（Weight Centriole Localization），liu等人［12］提出的虚拟力迭代定位法。针对已有算法定位准确性不足，孙言强等人［13］提出了基于几何覆盖的干扰攻击定位算法GCL（Geometry Covering based Localization），找出一个最小包容圆使其能覆盖所有的边界节点，则圆心处作为估计干扰源位置。由于几何算法不依赖网络本身或其他设备等复杂的测距知识、算法简单且定位精度高，因此开始成为研究定位问题的主要方向。

结合现有算法的不足之处，本文提出的算法无需任何测距上的先验知识和硬件设施，把定位中的优化问题抽象成简单的数学模型，只需参与定位的部分节点自身的位置信息即可求出干扰估计位置和实际位置的大致偏差，简单可行，同时有效的减少网络能量的消耗。

2　网络模型

本节主要介绍参与干扰源定位的网络模型和攻击模型。

2.1网络模型

无线传感器网络广泛应用于军用、民用，等大规模、大范围场合，为节约成本提高安放效率传感器节点由飞机高空随机撒播。在一定区域撒播下大量节点后，节点会通过自组织的方式相互连通构成网络。为了表征无线传感器网络节点的状态，对其进行如下假设：①节点的固定性，网络一旦形成，节点位置固定不变；②位置感知能力，网络形成后，节点可以准确感知自己所在的位置；③检测性，可以准确感知到干扰的存在，因此不再考虑干扰的检测阶段。

2.2攻击模型

恒定干扰通过持续的发送无线电信号来扰乱正常网络的通信信道，本文主要针对恒定干扰对网络的影响进行研究。对恒定干扰我们做如下假设：①位置固定，干扰一旦激活，位置固定不变；②传播模型，以全方位球形辐射模式向网络持续发送恒定功率的无线电信号，干扰半径r的大小代表干扰功率的大小。

干扰一旦激活，如图1所示，网络节点状态即被划分为三种，处在干扰范围内的节点成为被干扰节点，失去全部通信能力成为网络的通信“黑洞”；远离干扰范围的节点为正常节点，不受干扰影响保持正常通信；其中处于干扰范围边缘的点成为边界节点，这类节点通信并没有被完全破坏，保持部分通信能力，可以向网络外部传输其俘获的各种信息，成为定位干扰源的关键节点。

3　本文算法分析

3.1问题分析

干扰激活后可利用网络拓扑变化形成的边界节点来进行干扰源的定位，这是因为边界节点处于干扰范围的边缘使得边界节点的通信能力并没有被完全破坏，可向外部传输其准确的位置信息。

我们利用质心法求出干扰源初始估计位置，确定初始估计位置后，干扰源估计位置与实际位置之间可能存在偏差，因此利用偏差迭代定位算法确定干扰源的最终估计位置。我们设定偏差阈值为0.001，即横纵坐标的偏差均小于0.001，利用最小二乘法求出干扰源估计位置与实际位置的大致偏差，若精度不满足要求，则将校正后的坐标代替估计坐标，进行下一步的矫正，直到偏差小于规定阈值迭代结束。得到最终干扰源估计位置，此时偏差满足阈值要求，最接近干扰源的真实位置。

3.2偏差迭代定位算法

设干扰源J的实际位置是（x0,y0），初始估计位置（x̂0,ŷ0），边界节点位置为（xi,yi）。可将干扰源初始估计位置与实际位置偏移表示为（Δx0,Δy0），J到边界节点的距离为ri，为了计算J的位置，定义了一个最大似然估计函数f，并选择这个函数的一个局部最小值，设f=ri-r̂i。

式中：实际距离

估计距离

如上所述，J的真实位置可由近似分量和增量两部分表示：

因此有：

按泰勒级数对式（4）右边函数展开得：

为消除非线性，展开式（5）中消去了一阶偏导数之后的各项，偏导数计算为：

把式（3）～（6）带入式（2）中得：

为简化公式（7），引入下述变量：

这样式（7）可表示为：

在式（9）中等号左边为已知量，右边为未知量，设：

式（9）可表示为：

由此，得出：

因为在最大似然估计函数线性化过程中存在误差，解得的偏移向量为干扰源估计位置与实际位置的大概偏差。参与最后求解的方程组中有三个未知量，因此至少需要三个方程组即三个边界节点的位置信息，可在网络拓扑变化后的边界节点中选择。

4　算法性能分析

我们使用仿真工具搭建一个100 m×100 m仿真平台，在该区域随机撒播节点。节点通信半径设定为20 m，每个节点装有全向天线可以与自己通信范围内的所有邻居节点进行通信。将干扰放置在仿真平台的中心。每次随机撒播完节点在特定的干扰场景下调用这四种定位算法，把本文提出的算法和已有算法CL，WCL以及GCL进行比较，在100次随机试验中评估算法的定位效果。

4.1评价指标

干扰源估计位置和真实位置之间的欧氏距离定义为单次定位误差，如式（12）所示。把单次定位误差相加求平均，即为平均定位误差，如式（13）所示。

单次定位误差由于采样少而存在随机性，平均定位误差更能代表算法的优劣。为了保证评估效果的准确性，我们把平均定位误差指标作为评价的主要指标。这也是在现存定位方法中首次提出采用平均定位误差作为评价指标。

4.2实验分析

4.2.1干扰源功率对定位精度的影响

节点密度相同，调整干扰功率：在100 m×100 m区域内随机撒播200个节点（100 m×100 m，N= 200），使干扰半径r分别为20 m、30 m和40 m。每种算法随机运行100次，仿真结果如图2所示。

图2　R干扰功率对算法精度的影响（N=200）

在功率变化的三种情况下CL定位算法定位效果最差，本文提出的定位效果最好。当干扰功率增大时，四种算法的平均定位误差都有减小的趋势，说明四种算法的定位精度都与干扰功率大小有关，这是因为当干扰功率增大时，被干扰节点和边界节点的数目也相应增加，参与定位的候选节点数增加，从而在一定程度上使定位误差减小。通过仿真图的曲线波动情况可以看出，在不同的干扰功率情况下本文提出的算法曲线平稳、波动最小，因而定位精度最高且适应性最强，这是传统单次定位误差所无法评估的。

4.2.2节点密度对定位精度的影响

干扰功率一定，调整节点的密度：在100×100区域随机撒播100，150，200，250个节点，干扰激活后干扰半径保持30 m不变。每种情况下四种算法随机运行100次，仿真结果如图3和图2中（2）所示。在不同的节点密度下，本文提出的算法定位精度仍然最好。并且随着节点的密度增大，四种算法的定位误差都有减小的趋势，这是由于当节点密度增大时，被干扰节点和边界节点的数目增加并且参与定位的候选节点分布区域更趋近于圆，从而使四种算法的定位精度都有所提升。由此可以看出节点密度越大定位误差越小，反之则定位误差越大。从四种算法的平均定位误差曲线图可以看出本文算法曲线平稳震荡小，表明随机定位效果好。

图3　R节点密度对算法精度的影响（r=30 m）

4.3机理分析

在实际网络环境中，当干扰源位置处于网络边缘，或者节点随机撒播以及传播过程中功率损耗不同造成的各方向上边界节点密度不均匀时，形成的边界节点将不再包围干扰源或者造成不同方向边界节点分布密度差异很大，因而CL、WCL和GCL的定位误差都将大大增加。但是本文提出的算法在几何定位的基础上进行优化，只要确定的边界节点的绝对位置信息即可缩小定位误差，而对整体的边界节点相对位置信息无任何附加要求，因而即使干扰源位置边缘化或边界节点密度不均匀时，依然可以达到良好定位效果。

5　结语

由于无线传感器网络的本质特征导致网络易受干扰攻击而导致通信失败或网络瘫痪，为消除干扰保证网络正常通信，我们对干扰源定位问题进行了进一步的研究，在固定网络模型和干扰模型的基础上，把定位问题转化成简单的数学优化问题。通过仿真验证，本文提出的算法比现存几种算法定位精度显著提高。但是对于无线传感器网络来说，其网络模型和干扰攻击模型是多种多样的，在以后的研究中，我们可以对移动的干扰模型和联合干扰模型的定位问题进行进一步的探索。

［1］赵仕俊，唐懿芳.无线传感器网络［M］.北京：科学出版社，2013：1-3.

［2］毕俊蕾，李致远.无线传感器网络安全路由协议研究［J］.计算机安全，2009（11）：35-38.

［3］Shiu Y S，Chang S Y，Wu H C，et al.Physical Layer Security in Wireless Networks：A Tutorial［J］.Wireless Communications，IEEE，2011，18（2）：66-74.

［4］Ian F Akyildiz，Su Weilian，Yogesh Sankarasubramaniam，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40（8）：102-114.

［5］Zhou Yun，Fang Yuguang，Zhang Yanchao.Securing Wireless Sensor Networks：A Survey［J］.Communications Surveys and Tutorials，IEEE，2008，10（3）：6-28.

［6］Loay Abusalah，Ashfaq Khokhar，Mohsen Guizani.A Survey of Secure Mobile Ad Hoc Routing Protocols［J］.Communications Surveys and Tutorials，IEEE，2008，10（4）：78-93.

［7］聂云峰，王长胜，陈崇毅.一种空间查询高效的无线传感网络路由协议［J］.传感技术学报，2015，28（5）：744-751.

［8］Konstantinos Pelechrinis，Marios Iliofotou，Srikanth V Krishnamurthy.Denial of Service Attacks in Wireless Networks：The Case of Jammers［J］.Communications Surveys and Tutorials，IEEE，2011，13（2）：245-257.

［9］杨文铂，邢鹏康，刘彦华.一种基于自适应RSSI测距模型的无线传感器网络定位方法［J］.传感技术学报，2015，28（1）：137-141.

［10］Chen Yingying，John-Austen Francisco，Wade Trappe.A Practical Approach To Landmark Deployment for Indoor Localization［C］//Sensor and Ad Hoc Communications and Networks，2006. SECON'06.2006 3rd Annual IEEE Communications Society on. IEEE，2006，1：365-373.

［11］Blumenthal J，Grossmann R，Golatowski F，et al.Weighted Centroid Localization in Zigbee-Based Sensor Networks［J］.Intelligent Signal Processing，2007.WISP 2007.IEEE International Symposium on.IEEE，2007：1-6.

［12］Liu Zhenhua，Xu Wenyuan，Chen Yingying，et al.Localizing Jammers in Wireless Networks［C］//Pervasive Computing and Communications，2009.PerCom 2009.IEEE International Conference on. IEEE，2009：1-6.

［13］孙言强，王晓东，周兴铭.无线传感器网络中基于几何覆盖的Jamming攻击定位算法［J］.通信学报，2010，31（11）：10-16.

Based on the Deviation of Iterative Algorithm in Jammer Localization

HOU Dangyun，LÜ Weijie*
（School of Electrical Engineering and Automation，Tianjin University，Tianjin 3000072，China）

Wireless sensor networks communication is susceptible to jamming attacks，which would make the network communication blocked or even palsied.In order to localize the position of the jammer and then eliminate it to guarantee the normal communication，we develop a novel algorithm，deviation of iterative localization.After determining the initial estimate position，we calculate the deviation between the estimate position and the actual position through the position of three candidate nodes.If the deviation did not meet the accuracy requirement，iterated until it less than a specified threshold.The algorithm does not depend on the network complex hardware facilities or external device support.The problems of present methods about lager positioning error，higher energy consumption and the like have been improved.Simulation shows that our algorithm under the different network environments outperforms existing algorithms.

wireless senor networks；localization；deviation of iterative；threshold；simulation

侯当云（1991-）河北省邯郸市人，天津大学硕士研究生，主要研究方向为无线传感器网络安全问题，hdy2013y@163.com；

吕伟杰（1975-）天津大学副教授，硕士生导师，主要研究方向为无线传感器网络、图像处理、现场总线等，weijielv@tju. edu.cn。

TN915.08

A

1004-1699（2015）12-1818-05

2015-06-30修改日期：2015-09-11