面向多跳无线网络的多干扰源定位算法

王棋萍，魏祥麟，范建华，王统祥，胡飞

(1.解放军理工大学通信工程学院，江苏 南京 210007；2.南京电讯技术研究所，江苏 南京 210007)

面向多跳无线网络的多干扰源定位算法

王棋萍1，魏祥麟2，范建华2，王统祥1，胡飞1

(1.解放军理工大学通信工程学院，江苏 南京 210007；2.南京电讯技术研究所，江苏 南京 210007)

提出一种面向多跳无线网络的多干扰源定位算法，主要包括3个步骤：基于梯度下降法的分组投递率谷点推定、基于梯度上升法的接收干扰强度(RJSS,

jamming signal strength)峰点推定和聚类分析。首先，算法从多个初始节点出发，采用梯度下降法，沿着分组投递率梯度下降最快的方向逼近干扰源，直至到达分组投递率谷点；然后应用功率自适应动态调整技术，采用梯度上升法，沿着接收干扰强度上升最快的方向继续逼近干扰源，直至接收干扰强度峰点（也称为RJSS停止节点）；最后通过对无法与RJSS停止节点通信的邻居节点进行聚类分析，确定干扰源的数量和位置。模拟实验表明，与现有算法相比，所提算法可以有效降低多干扰源定位过程的定位误差；并且，当干扰源间距符合限定条件时，算法定位结果更优。

多跳无线网络；干扰攻击；干扰源定位；聚类

1 引言

作为实现泛在网络连接的一种可行方式，多跳无线网络在近年来发展迅速且得到了一些实际部署。但无线信道的开放共享特性使多跳无线网络容易受到多种干扰攻击，进而造成网络性能恶化和服务质量下降。干扰攻击是一种通过占用网络节点通信信道，使其不能进行正常数据转发的拒绝服务攻击[1]。为了有效应对干扰攻击，国内外研究者从物理层通信模式、链路层调度策略、网络层路由算法和应用层服务质量调整等角度提出了包括信道级、链路级和网络级在内的干扰消除或规避方法[2～6]。这些方法多数需要利用干扰源精确位置或所在区域信息以采取对应抗干扰手段[7,8]。为此，如何高效、准确地定位干扰源成为近年来学术和工业界研究的热点问题之一。

干扰源定位是指多跳无线网络中的被干扰节点，利用主动测量和被动监听得到的多个协议栈层次的观察结果，利用无线信道传播特性和干扰区域几何知识，协作推断干扰源的相对或绝对位置的过程。现有的干扰源定位算法大致可以分为2类，即测距类和非测距类方法[9]。测距类定位算法通过选择合适位置节点的物理属性，建立其关于干扰源位置的关系，最终定位干扰源位置。非测距算法则根据干扰区域附近内外节点的位置信息，利用几何知识对干扰源位置进行估计。这2类算法大多针对单个干扰源提出，无法应用于多干扰源并存场景。

为了达到高效、大范围的干扰，攻击者可以选择在网络中的不同位置发起干扰攻击。在多个干扰源的协同工作下，网络干扰区域增大，节点受干扰强度增强。针对这种场景，Cheng等[10]提出了一种称为X射线的干扰区域定位算法。X射线定位算法包括干扰区域映射、干扰区域骨架化和干扰源位置确定3个步骤。该算法通过干扰区域骨架化，利用分叉点的位置信息反映干扰源的物理位置，由于区域边界受噪声影响较大，因此，X射线干扰区域定位算法定位精度偏低。另外，网络范围内的信息收集使X射线定位算法的通信复杂度很高，时效性差。

为了提高定位精度且减小定位开销，本文提出了一种新颖的多干扰源定位算法。该算法包括3个主要步骤：基于梯度下降法的分组投递率谷点推定、基于梯度上升法的接收干扰强度峰点推定和聚类分析。首先，算法从多个初始节点出发，采用梯度下降法，沿着分组投递率下降最快的方向逼近干扰源，直至到达分组投递率谷点；然后应用功率自适应动态调整技术，采用梯度上升法，沿着接收干扰强度上升最快的方向继续逼近干扰源，直至接收干扰强度峰点（也称为RJSS停止节点）；最后对无法与RJSS停止节点通信的邻居节点进行聚类分析，并将聚类中心作为干扰源的估计位置。本文的主要贡献在于：1) 提出了基于聚类分析的干扰源定位方法，可以在无需估计干扰源数量的情况下实现多干扰源准确定位；2) 设计了接收干扰强度梯度峰点推定过程，使聚类分析的开始节点更加靠近干扰源实际位置；3) 给出了干扰源间的距离与多干扰源可定位性的关系；4) 通过大量实验分析，验证了所提出定位算法定位精度显著优于现有定位算法。

2 相关工作

为了定位多跳无线网络中的干扰源，近年来，国内外研究者提出了一系列方案解决单个干扰源定位问题。在不采用特定专有设备的条件下，Pelechrinis等[11]发现越靠近干扰节点，分组投递率就越低，并基于这个观察结果，采用梯度下降方法设计了基于PDR梯度下降的定位算法。基于该算法在高干扰功率场景下产生的较大误差，Wang等[12]应用功率自适应调节技术提出了一种基于PDR梯度下降的改进算法。基于干扰攻击导致的网络拓扑状态变化和节点状态改变，Liu等[13]提出了一个称为虚拟力迭代定位的干扰节点定位算法。虚拟力迭代定位算法首先估计干扰节点的传输范围，然后产生一个估计的圆形干扰区域，之后迭代，改变估计的干扰区域的中心来覆盖最多的被干扰节点。虚拟力迭代定位算法假设估计的干扰节点位置等于真实的位置时，估计的区域与实际干扰区域重合。通过估计干扰攻击发生前后的监听范围，Liu等[14]提出利用节点的监听范围解决一个最小平方问题来定位干扰节点。这种方法有效的前提是监听范围和网络及节点状态的改变仅是由干扰导致的。Liu等[15]还将干扰节点定位问题建模为一个非线性最优化问题，并提出使用基因算法或者模拟退火算法最小化干扰节点定位误差。

基于无线传输的广播特性，一些基于几何学知识的干扰节点定位方法被陆续提出，包括质心定位、权重质心定位、虚拟力迭代定位、凸壳定位、阿尔法壳定位等。在质心定位方法(CL,centroid localization)中，干扰节点的邻居节点被称为被干扰节点。CL收集所有被干扰节点的坐标值，并将其均值作为干扰节点的估计位置。考虑到不同被干扰节点距离干扰节点的距离不同，其感受到的干扰强度也不相同，研究者提出了权重质心定位，一定程度上提高了定位精度[16]。Sun等[17,18]提出了一种基于几何覆盖理论的干扰节点定位算法。GCL算法利用计算几何中的凸壳理论，特别是最小包容圆方法，对攻击者进行定位。Cheng等[19]基于凸壳理论，利用最小边界圆和最大内切圆来定位干扰节点。Xiong等[20]将干扰节点定位问题建模为一个最小平方问题，并基于线性回归方法提出了一种健壮的干扰节点定位算法。利用干扰节点引起的拓扑变化，Liu等[21]首先基于最大生成树分割网络拓扑，然后基于拓扑分割结果和适应性最小平方和算法定位多个干扰节点。Rau等[22]结合基于序列改变检测技术的本地检测和基于最小平方法的全局检测方法提出了一种混合干扰节点定位方法。

Cheng等[10]基于网络干扰区域提出了一种X射线多干扰源定位方法，用以定位多个干扰源。该算法是一种基于干扰区域骨架化，利用分叉点对干扰源进行近似估计的集中式定位算法。骨架用与原始形状连通性和拓扑结构相一致的曲线表达物体形状，它是所有最大圆盘的圆心的集合，最大圆盘即是完全包含在物体内部，并且至少与物体边界相切于两点的圆。因此，干扰区域骨架化保留了区域的轮廓和位置信息。X射线多干扰源定位算法主要包括3个步骤：区域映射、区域骨架化和干扰源估算。

3 问题分析与模型假设

3.1 问题提出

多个干扰源通过协同工作，可以增加干扰强度并扩大干扰范围，进而增加对多跳无线网络的危害。在多干扰源并存场景下，各个干扰源的干扰区域可能存在重合，使干扰区域往往不再符合某个简单的几何形状。在这种场景下，如果无法判断干扰源数量并分割各自干扰区域，而是仅根据单个干扰源的假定进行定位，那么得到的最终位置显然是错误的。图1(a)和图1(b)分别表示2个干扰源各自的影响，图1(c)表示两者共同存在的场景。可以看出，多干扰源并存时，多个节点的受干扰情况都发生了变化，干扰区域的特征更加复杂。因此，在此场景下，直接应用单干扰源定位方法无疑会带来较大的定位误差。注意到，当干扰源间距较大，干扰区域不存在重叠时，可以应用单干扰源定位算法对各干扰源分别进行定位。为此，本文只研究干扰区域重叠场景下的多干扰源定位问题。

图1 多干扰源共存的干扰区域示意

由上述分析可知，与单干扰源定位相比，多干扰源定位面临更复杂的问题。如何在干扰源数量未知且干扰区域存在重叠的场景下，精确定位各个干扰源的位置是本文需要解决的主要问题。

3.2 模型假设

本节限定了本文使用的网络模型、攻击模型以及传播模型。

3.2.1 网络模型

本文对多跳无线网络的基本设定如下。

1) 节点静态性：一旦网络部署完毕，每个传感器节点的位置不再发生变化。

2) 位置感知：每个节点都能感知自己和邻居节点的位置坐标。这可以通过位置服务以及多跳无线网络中的协议交互实现。

3) 节点同构：网络中的节点具有相同的计算、传输和存储能力。传感器节点的通信范围相同。

4) 发射功率自适应：在限定的功率范围内，节点可以适度增加发射功率，提高接收节点的接收信噪比。

3.2.2 攻击模型

假定每个干扰源配置全向天线，发送相同功率的信号，且干扰源位置是固定不变的。假设网络中有n个干扰源，干扰源间的距离Dij满足

其中，Ri和Rj分别为干扰源i和j的干扰半径，ω是一个变量，ω越小，干扰源间的距离越大。为了实现有效干扰，ω一般为0.5。当ω小于0.5时，干扰区域重叠区域过大，进而使总的干扰区域面积减小，这与多干扰源协作的目的相违背，因此，本文暂不考虑此场景。当干扰源间距离大于Ri+Rj时，会使干扰区域不重叠，此时只需采用单干扰源定位算法即可估计干扰源的位置。

3.2.3 传播模型

本文采用式(2)所示的自由空间传播模型。

其中，PRX为节点接收功率，PTX为射频端发射功率，GTX、GRX分别为天线的发射增益和接收增益，d为发射节点和接收节点之间的距离，λ表示传送的无线电波的波长。

4 面向多跳无线网络的多干扰源定位

4.1 基本设想

多干扰源定位无法基于圆形干扰区域的假设，利用网络节点的物理属性和位置信息建立与干扰源的联系。为了准确定位多个区域重叠的干扰源，首先需要确定多个干扰源所在的大致区域，然后根据聚类分析方法定位干扰源。本文提出的多干扰源定位算法包括3个步骤：基于梯度下降法的分组投递率谷点推定、基于梯度上升法的接收干扰强度峰点推定和聚类分析。首先，从多个不同的起始节点发起定位过程，沿分组投递率下降方向逼近干扰区域中心；然后，采用功率自适应方法，沿接收干扰强度上升方向进一步细化干扰区域；最后，通过对停止节点的损失邻居进行聚类计算得到干扰源所在位置。

注意到，在多干扰源定位场景中，选择较多的起始节点可以提高定位精度，但也会带来更大的计算和通信耗费。为此，本文在网络节点中随机选取个节点作为初始节点，其中，N为网络中节点的数量。

4.2 算法设计

4.2.1 基于梯度下降法的分组投递率谷点推定

在无线通信中，分组投递率(PDR,packet delivery ratio)被定义为被正确接收的分组数目与已发送的分组数目的比值[9]。分组投递率能反映网络中节点的通信质量，通信质量越好，分组投递率越高。由于干扰信号的强度随着距离的增大呈下降趋势，所以距离干扰源越远的节点受到干扰信号的影响越小，从而会满足所需的信噪比要求，使节点的PDR值增大。

多跳无线网络部署区域各个位置的PDR值构成了一个PDR标量场。这个标量场中的各个谷点(局部极小值)则代表了距离干扰源距离较近的那些难以正常通信的节点。为了推定这些谷点的位置，本文采用了梯度下降方法。

初始节点确定后，通过比较节点与其邻居节点的PDR值，路径沿PDR值下降最快的方向逼近干扰源，直至达到PDR谷点。在干扰源作用下，位于干扰源附近区域的节点丧失了通信能力，其PDR值近似下降为0，因此，PDR谷点推定的路径无法到达距离干扰源最近节点的位置。图2展示了PDR梯度下降的过程，图2中的箭头表示梯度下降的方向。由于干扰区域中心的部分节点受干扰程度较强，无法完成分组的传输，因此，PDR谷点推定路径只能到达距离干扰源较远的节点，如图2中矩形框所示。为了描述方便，将PDR下降过程停止的节点称为PDR停止节点。

图2 PDR谷点推定过程

4.2.2 基于梯度上升法的接收干扰强度峰点推定

为了重构节点间的通信，Kim等[23]提出了功率自适应调节技术。在干扰场景中，通过不断增加发射节点的功率，提高接收节点的接收信噪比，可以部分恢复节点间的通信。由于干扰源的干扰功率随着距离的增大而减弱，距离干扰源越近，节点收到的干扰功率越大，所以节点的RJSS值能反映节点与干扰源的距离信息。其中，RJSS是指被干扰节点收到的干扰源信号强度，可以采用文献[24]所提方法进行测量和估计。

类似于PDR标量场，本文可以定义RJSS标量场，最靠近干扰源的节点是RJSS标量场的峰点(局部极大值)。在RJSS标量场中，通过增大PDR停止节点的发射功率，重建这些节点与比它们更靠近干扰源的邻居间的通信，进而可以进一步逼近干扰源所在位置，直至达到RJSS峰点。为了描述方便，后文也将RJSS峰点称为RJSS停止节点。

假设在功率自适应调节技术中，节点所能到达的最大功率值为Pmax=Pnode+Pthreshold，其中，Pnode为节点初始功率，Pthreshold为节点所能增加的最大功率。在最大发射功率范围内，PDR停止节点以步长逐渐增大发射功率，直到该节点能与其邻居节点j通信，且其RJSS小于该邻居节点j的RJSS，则节点j替代PDR停止节点，重复上述操作。因此，路径沿着RJSS增加最快的方向逼近干扰源。在最大发射功率增量范围内，当节点的RJSS值达到局部最大时，结束路径搜索。图3展示了一个RJSS梯度上升过程。其中，实线箭头表示PDR谷点推定的路径，虚线箭头表示RJSS峰点推定的路径。初始节点确定后，路径先后沿着PDR减小最快和RJSS增加最快的方向靠近干扰源，直到到达RJSS停止节点，如图3矩形框所示，RJSS停止节点围绕在各个干扰源附近。

图3 RJSS峰点推定过程

图4为RJSS信息交互的协议示意。其中，T为发送节点，R为接收节点。发送节点T的初始功率为MIN_POW，并以增量step不断增加发送功率，直到能与邻居节点R进行通信。T向邻居节点R发送包含id、接收干扰强度RJSS_T和节点发送功率power的数据帧RJSS_INFO，R成功接收分组信息后，从信息中读取发送节点的RJSS值，若R的接收干扰强度大于T的接收干扰强度，则R向T发送包含自身id和RJSS值的数据帧RJSS_INFO_ACK，否则R不发送任何信息。

图4 RJSS信息交互

4.2.3 聚类分析

由上文分析可知，RJSS停止节点位于干扰源附近，但仍与干扰源存在一定距离。因此，必须对RJSS停止节点进行进一步处理，提高定位精度。

如图5所示，在未受干扰状态下，RJSS停止节点的邻居节点分布在以其位置为中心，以其传播距离为半径的圆形区域内。当网络受到干扰攻击，RJSS停止节点以最大发送功率传输信息时，部分邻居节点的接收信噪比增大，满足通信要求，可以重建与RJSS停止节点的通信，如白色圆点所示。其余邻居节点在最大发射功率下的接收信噪比仍小于信噪比阈值，无法与RJSS停止节点传递信息，如灰色圆点所示。

图5 RJSS停止节点邻居节点分类

注意到，该类无法与RJSS停止节点通信的邻居节点分布在各个干扰源周围，可以较好地反映干扰源的位置。因此，通过收集所有RJSS停止节点在最大发送功率下仍无法通信的邻居节点信息，按照其物理位置进行分类，聚类数目作为干扰源的估计数量，聚类中心作为干扰源的估计位置。

聚类分析是一种将研究对象分为相对同质的群组的统计分析技术。聚类的方法主要包括两大类：层次聚类和非层次聚类。K-means是一种以确定的聚类数量K和选定的初始聚类中心为前提，使各样本到其判属类别中心距离之和最小的非层次聚类。该算法处理效率较高，特别是当样本分布呈类内团聚状时，可以达到很好的效果。然而，在本文研究的多干扰源定位场景中，由于干扰源数目未知，无法确定类数，因此，K-means聚类无法直接解决丢失邻居节点的分类问题。文献[25]基于样本的几何结构，设计了一种新的评估聚类有效性的指标，在此基础上提出了一种确定样本最佳聚类数的方法。因此，样本最佳聚类数确定后，即可对样本进行K-means聚类分析。为此，本文采用文献[25]所提出的聚类方法。

4.3 算法描述

面向多跳无线网络的多干扰源定位算法伪代码如算法1所示。步骤1)是节点初始化；步骤4)到步骤13)比较节点i与其邻居节点的PDR值，若邻居节点的最小PDR值小于该点的PDR值，则用该邻居节点代替节点i，重复上述步骤，直至达到PDR谷点；步骤15)到步骤31)以step的增量持续增加PDR停止节点发射功率，在节点重建与邻居节点的通信的基础上比较各自的RJSS值；在步骤32)到步骤37)中，若节点在最大发射功率范围内不能搜寻到RJSS值更大的邻居节点，则以该点作为RJSS谷点或RJSS停止节点，记录该节点的丢失邻居节点，否则用RJSS值更大的邻居节点代替PDR停止节点，重复步骤15)到步骤31)；步骤38)对所有停止节点的丢失邻居节点进行聚类分析，估计干扰源数量和位置。

算法1基于面向多跳无线网络的多干扰源定位算法

输入N：网络中节点总数；σ=1，δ=1；σ、δ为循环条件，满足该条件时进入循环，否则，退出循环

输出O_ES：估计干扰源坐标

4.4 算法分析

4.4.1 复杂度分析

假设节点间平均距离为d，网络半径为R。对于每个初始节点，PDR谷点推定和RJSS峰点推定过程的平均跳数是。假定一跳的通信开销为c，初始节点数量为M，其平均邻居数量为ns，则算法总的通信开销为。从存储角度来说，假定每个节点用4 byte存储每个邻居的PDR值，用4 byte存储每个邻居的RJSS值，则每个节点的存储开销为8ns，总的存储开销上界为8Nns，其中，N是节点总数。聚类分析的时间复杂度为O(knt)，其中，k为最佳聚类数量，n为输入样本数量，t为迭代次数。

4.4.2 收敛分析

从某个初始节点开始的PDR谷点推定过程会停止于此节点的网络范围内的PDR谷点，且由于算法采用某个时刻的测量结果，因此不会出现震荡情况。同样地，从PDR停止节点开始的RJSS峰点推定过程也同样停止于其网络范围内的RJSS峰点，也不会出现震荡情况。而K-means算法则随着迭代次数到达而停止。为了保证定位效果的准确性，5.3节讨论了定位算法对干扰源间的距离的要求。总之，算法会在估计的时间开销、通信开销和存储开销之内收敛，并给出多个干扰源的估计位置。

5 算法验证与结果分析

本节设计了一系列模拟实验，用于验证所提出的多干扰源定位算法的性能。首先，介绍了实验设定；然后，在多干扰场景下，对本文提出的多路径搜索定位算法以及现有的几种定位算法分别进行仿真比较；最后，探讨参数对算法性能的影响，并进行分析讨论。

5.1 实验设定

本文采用Matlab搭建了一个多跳无线网络模型。假设网络部署在L×L的区域内，N个网络节点均匀分布在N个l×l的网络栅格中，M个干扰源随机部署在网络中。仿真中使用的主要参数如表1所示。

表1 实验仿真参数

对比基准。本文选择X射线多干扰源定位算法和质心定位算法与本文提出的算法进行定位性能比较，分析算法的优劣。

对比测度。本文采用平均绝对误差(MAE,mean absolute error)来衡量算法的定位性能，定义如式(3)所示。

5.2 实验结果与分析

5.2.1 性能验证

首先实验验证了所提出的多干扰源定位算法的性能，并在相同场景中与现有的X射线多干扰定位算法和质心定位算法进行了性能比较。图6为算法的仿真结果，其中，实线折线、虚线折线分别为PDR谷点推定路径和RJSS峰点推定路径。初始节点沿着上述2段路径逼近干扰源，RJSS停止节点如图6矩形框所示，由于节点的发射功率增量有限，RJSS停止节点与附近干扰源仍存在一定距离。对停止节点丢失的邻居节点进行聚类分析，聚类中心作为估计干扰源位置，如菱形所示。

图6 本文算法多干扰源定位算法定位结果

图7为X射线多干扰源定位仿真结果。图7中折线围成的区域为干扰区域，三角形节点为骨架的分叉点，矩形方框为聚类中心，即为估计干扰源的位置。

图8展示了3种定位算法在100次实验后的平均绝对误差值(MAE)。由图8可知本文提出的定位算法MAE为5.201 2，定位精度最高。X射线定位和质心定位的平均绝对误差分别为27.480 9和 103.207。其中，质心算法是以估计干扰源与各个干扰源间距离的平均作为平均绝对误差。在X射线定位中，环境噪声会造成干扰边界的波动，从而影响区域骨架的形状，导致定位性能的降低。质心定位算法没有对干扰源数量进行正确估计和对干扰区域进行合理的划分，因此，简单地对被干扰节点进行坐标平均无法定位干扰源的位置。

图7 X射线多干扰源定位

图8 多干扰场景中的定位算法精度比较

5.2.2 参数影响

本节主要讨论了干扰源间距和干扰源发射功率和干扰源位置对算法性能的影响。

在干扰源间距分别为{100,80,60,40}的4个干扰场景中，本文算法的平均定位误差如图9所示。随着干扰源间距的减小，定位误差增大。这是因为当干扰源间距减小时，RJSS停止节点间距减小，导致丢失邻居节点交织分布，通过聚类分析得到的聚类数可能不等于实际干扰源数量，因此，定位的误差增大。

图9 干扰源间距对MAE的影响

图10所示的在不同干扰源发射功率下算法的平均绝对误差。由图10可知，随着干扰源发射功率的增大，算法的定位精度降低。这是因为干扰源功率的增大导致路径搜索无法深入干扰区域内部，RJSS停止节点和丢失邻居节点与相应干扰源的距离增大，聚类中心偏离干扰源位置。此外，干扰源发射功率的增大导致干扰重叠区域扩大，丢失邻居节点交织分布，因此聚类分析不准确，定位误差增大。

图10 干扰源发射功率对MAE的影响

为了评估干扰源分布位置对算法定位的影响，在不同的干扰源分布位置，对面向多跳无线网路的多干扰源定位算法进行了仿真。图11是干扰源分别位于区域中心、区域边界和区域角落时算法平均绝对误差。从图11中可以看出，当干扰源分布在区域中心时，算法的定位误差最小。这是因为干扰源的边缘化分布导致RJSS停止节点的边缘化和丢失邻居节点的减少，从而影响聚类中心的计算。

图11 干扰源位置对MAE的影响

5.3 讨论

由实验分析可知，面向多跳无线网络的多干扰源定位算法的定位性能与聚类效果有关。聚类效果越好，则定位越精确。

聚类计算是通过对RJSS停止节点在最大发送功率下失去的邻居节点按照其位置属性进行分类，聚类中心为干扰源估算位置。如图12(a)所示，当干扰源相距较远，逼近各个干扰源的RJSS停止节点距离较大，丢失的邻居节点呈类内团聚状分布时，通过聚类分析可以准确地将其分类，聚类中心为相应干扰源的估计位置。当干扰源距离较近，RJSS停止节点距离较小，其丢失的邻居节点混合分布在一起，如图12(b)所示，通过聚类分析无法将其正确划分为2类，导致干扰源数量估计错误。可见，各个干扰源间的距离影响聚类的效果。

假设在最大发射功率下，RJSS停止节点与其丢失的邻居节点间的平均距离为d0，干扰源距离丢失邻居节点的平均距离为dj_neighbor，则d0和dj_neighbor应满足

其中，PT是节点初始发送功率，IN_MAX是节点发射功率最大增量，PJ是干扰源发射功率，SNR_threshold为接收信噪比阈值。则丢失邻居节点与干扰源的距离dj_neighbor满足

图12 丢失邻居节点分布

停止节点与附近干扰源的平均距离dj_node为

根据式(5)和式(6)，可得停止节点与附近干扰源的最大距离dj_node_max满足

因此若要通过聚类分析，正确划分丢失邻居节点，使聚类数等于干扰源数目，聚类中心能反映干扰源的近似位置，则干扰源间的距离D应满足

其中，dnode_mean为节点间平均距离。由式(7)和式(8)可知，干扰源发射功率、节点发射功率最大增量影响算法的精确度。当干扰源间距不变时，干扰源发射功率的增大或者节点发射功率最大增量的减小均会使RJSS停止节点与干扰源的最大距离增大，从而使算法定位性能降低。

6 结束语

为了实现对多跳无线网络中多干扰源的精确定位，本文提出了面向多跳无线网络的多干扰源定位算法。该算法根据分组投递率和接收干扰信号强度与干扰源位置的关系，应用功率自适应技术，从多个起始节点出发，先后进行分组投递率谷点推定和接收干扰信号强度峰点推定，最后通过对RJSS停止节点损失邻居进行聚类分析，从而确定干扰源的数量和位置。为了验证算法性能，使用Matlab搭建了模拟实验环境并设计了一系列模拟实验，通过与现有定位算法的定位性能对比，该算法可以实现多干扰源的精确定位。此外，实验还研究了其他参数对算法的性能影响，结果表明当干扰源间距符合限定条件时，面向多跳无线网路的多干扰定位算法具有良好的定位结果。下一步将建立多干扰源定位的理论模型，并对定位算法性能进行定量分析。

[1]XU W,TRAPPE W,ZHANG,et al.The feasibility of launching and detecting jamming attacks in wireless networks[C]//MobiHoc05:Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc networking and Computing.2005:46-57.

[2]PELECHRINIS K,KOUFOGIANNAKIS C,KRISHNAMURTHY S.On the efficacy of frequency hopping in coping with jamming attacks in 802.11 networks[J].IEEE Transactions on Wireless Communications,2010,9(10):3258-3271.

[3]NOUBIR G,LIN G.Low-power DoS attacks in data wireless lans and countermeasures[J].ACM SIGMOBILE Mobile Computing and Comm,2003,7(3):29-30.

[4]XU W,TRAPPE W,ZHANG Y.Channel surfing:defending wireless sensor networks from interference[C]//IPSN’07:Proc Sixth Int’l Conf.Information Processing in Sensor Networks.2007:499-508.

[5]MA K,ZHANG Y,TRAPPE,W.Mobile network management and robust spatial retreats via network dynamics[C]//First Int’l Workshop Resource Provisioning and Management in sensor Networks.2005:242.

[6]PELECHRINIS K,KOUFOGIANNAKIS C,KRISHNAMURTHY S.On the efficacy of frequency hopping in coping with jamming attacks in 802.11 networks[J].IEEE Transactions on Wireless Communications,2010,9(10):3258-3271.

[7]NIKA A,ZHANG Z,ZHOU X,et al.Towards commoditized real-time spectrum monitoring[C]//Hotwireless’14.2014.

[8]YANG Y,JIN M,WU H.3D surface localization with terrainmodel[C]//IEEE Infocom 2014.2014:46-54.

[9]孙言强,王晓东,周兴铭.无线网络中的干扰攻击[J].软件学报,2012,23(5):1207-1221.SUN Y Q,WANG X D,ZHOU X M.Jamming attacks in wireless network[J].Journal of Software,2012,23(5):1207-1221.

[10]CHENG T Z,LI P,ZHU S C,et al.M-cluster and X-ray:two methods for multi-jammer localization in wireless sensor networks[J].Integrated Computer-Aided Engineering,2014,21:19-34.

[11]PELECHRINIS K,KOUTSOPOULOS I,BROUSTIS I,et al.Lightweight jammer localization in wireless networks:system design and implementation[C]//IEEE Global Telecommunication Conference,2009.

[12]WANG Q P,WEI X L,FAN J H,et al.A step further of PDR-based jammer localization through dynamic power adaption[C]//WiCOM 2015,2015:651-654.

[13]LIU H B,XU W Y,CHEN Y Y,et al.Localizing jammers in wireless networks[C]//PERCOM 2009.Washington:IEEE Computer Society,2009:1-6.

[14]LIU Z H,LIU H B,XU W Y,et al.Exploiting jamming-caused neighbor changes for jammer localization[J].IEEE Trans Parallel Distrib Syst,2012,23(3):547-555.

[15]LIU Z H,LIU H B,XU W Y,et al.An error-minimizing framework for localizing jammers in wireless networks[J].IEEE Trans Parallel Distrib Syst,2014:25(2):508-517.

[16]BLUMENTHAL J,GROSSMANN R,GOLATOWSKI F,et al.Weighted centroid localization in Zigbee-based sensor networks[C]// IEEE Int’l Symp on Intelligent Signal Processing Alcala de Henares.2007:1-6.

[17]SUN Y Q,WANG X D,ZHOU X M.Geometry-covering based localization for jamming attack in wireless sensor networks[J].Journal on Communications,2010,31(11):10-16.

[18]孙言强,王晓东,周兴铭.无线传感器网络中基于几何覆盖的Jamming攻击定位算法[J].通信学报,2010,31(11):10-16.SUN Y Q,WANG X D,ZHOU X M.Geometry-covering based localization for jamming attack in wireless sensor networks[J].Journal on Communications,2010,31(11):10-16.

[19]CHENG T Z,LI P,ZHU S C.An algorithm for jammer localization in wireless sensor networks[C]//IEEE International Conference on Advanced Information Networking and Applications.2012:724-731.

[20]XIONG K Q,DAVID T.Locating jamming attacks in malicious wireless sensor networks[C]//Performance Computing and Communications Conference(IPCCC),2012 IEEE 31st international.Austin,TX,2012:400-407.

[21]LIU H,LIU Z,CHEN Y,et al.Localizing multiple jamming attackers in wireless networks[C]//2011 31 International Conference on Distributed Computing Systems.Minneapolis,MN,USA,2011:517-528.

[22]VIKRAMADITYA R A,RAGHUVARA R,SHASHIMOHAN V,et al.A novel method for jammer localization in large scale sensor networks[C]//Wireless And Optical Communications Networks (WOCN),2010 Seventh International Conference.2010:6-8.

[23]KIM Y,MOKAYA F,CHEN E,et al.All your jammers belong to us—localization of wireless sensors under jamming attack[C]//IEEE International Conference on Communications (ICC).2012:949-954.

[24]LIU Z H,LIU H B,XU W Y,et al.Error minimizing jammer localization through smart estimation of ambient noise[C]//MASS 2012.

[25]周世兵,徐振源,唐旭清.K-means算法最佳聚类数确定方法[J].计算机应用,2010,30(8):1995-1998.ZHOU S B,XU Z Y,TANG X Q.Method for determining optimal number of clusters in K-means clustering algorithm[J].Journal of Computer Applications,2010,30(8):1995-1998.

王棋萍（1990-），女，湖南湘乡人，解放军理工大学硕士生，主要研究方向为无线网络安全。

魏祥麟（1985-），男，安徽砀山人，南京电讯技术研究所工程师，主要研究方向为数据中心网络、无线网络安全和网络异常检测。

范建华（1971-），男，安徽歙县人，南京电讯技术研究所研究员，主要研究方向为无线网络安全和认知无线电网络。

王统祥（1990-），男，山东临沂人，解放军理工大学博士生，主要研究方向为无线网络安全。

胡飞（1987-），男，江苏淮安人，解放军理工大学硕士生，主要研究方向为无线网络安全。

Multi-hop wireless network oriented multiple jammers localization algorithm

WANG Qi-ping1,WEI Xiang-lin2,FAN Jian-hua2,WANG Tong-xiang1,HU Fei1
(1.College of Communications Engineering,PLA University of Science and Technology,Nanjing 210007,China;2.Nanjing Telecommunication Technology Research Institute,Nanjing 210007,China)

A multiple jammer localization algorithm in multi-hop wireless networks was proposed.The proposed algorithm contained three steps,packet delivery ratio (PDR) valley point determination based on gradient descent algorithm,received jamming signal strength (RJSS) peak point determination based on gradient ascent algorithm and cluster analysis.Firstly,the algorithm started from a few initial nodes and moved along the gradient descent direction ofPDRto approach the jammers until reaches thePDRvalley point.Then,the algorithm moved toward the jammers using power adaptation technique based onRJSSgradient ascent process until it reached theRJSSpeak point.Finally,through applying cluster analysis on the neighbour nodes which fail to communicate withRJSSpeak points,the number and positions of the jammers can be estimated.Experimental results have verified that the proposed algorithm can improve the accuracy of localization compared with existed localization algorithms.Furthermore,the performance of the proposed algorithm is prominent when the distance of jammers accords with constraint condition.

multi-hop wireless network,jamming attack,jammer localization,cluster

s:The National Key Basic Research and Development Program of China(973 Program) (No.2012CB315806),The National Natural Science Foundation of China(No.61402521,No.61070173),The Natural Science Foundation of Jiangsu Province(No.BK20140068,No.BK20140070,No.BK20150201)

TP393

A

10.11959/j.issn.1000-436x.2016284

2015-10-20；

2016-09-19

魏祥麟，weixianglin@163.con

国家重点基础研究发展计划(“973”计划) 基金资助项目(No.2012CB315806)；国家自然科学基金资助项目(No.61402521,No.61070173)；江苏省自然科学基金资助项目(No.BK20140068,No.BK20140070,No.BK20150201)