一种容忍恶意锚节点独立攻击的安全定位算法*

罗 臻，刘宏立，徐 琨

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

随着无线通信技术、计算机技术以及网络技术的快速进步，无线传感器网络(Wireless Sensor Networks)得到了稳定的发展，并获得广泛应用，例如水下监视［1］、军事侦察、交通监控［2］、环境监测［3］、森林火灾探测以及事故搜救［4］等。准确地知道传感器节点的位置是这些应用得以实现的基础，国内外研究者就此提出了很多种定位方法［5］，大多数方法依赖于一组信标或锚节点的已知位置信息来确定剩余节点的位置。在这些方法中，锚节点发送包含自己位置的信标信号，当其他节点接收到这一信号时就可以估计出它到锚节点的距离。常用的距离度量物理量有以下几种:接收信号强度(RSS)、到达时间(TOA)、到达时间差(TDoA)、到达角(AOA)和跳计数［6］。一旦定位节点接收到足够的信标信号，它们就能通过三角测量法或三边测量法来确定自己的位置。然而这些定位方法都是假设传感器网络部署在非攻击的环境中，但实际上，无线传感器网络经常会被部署在恶意危险的环境中，那么传感器节点的位置信息就会遭受到各种类型的攻击。在恶意危险的环境中，攻击者可能会希望阻止节点的准确定位，以此来阻碍整个网络的正常运行。所以，需要设计能够精确定位并对攻击具有鲁棒性的安全定位算法。同时，由于定位节点本身有限的计算能力和能量，这样的安全定位算法也应该尽可能少的耗费资源。

位置验证作为安全定位的一种策略已在相关的文献中有所体现。S.Capkun等人提出的使用移动基站的位置验证方法和其他一些距离边界协议能够有效地抵御攻击［7－8］。在恶意危险环境中的安全定位问题同样引起了人们的注意。文献［9］中提出了一种改进的DV-Hop算法，通过利用设计好的非线性公式来处理虫洞攻击导致的不合理跳数，减轻了攻击的影响。文献［10］中提出了一种安全定位算法，其结果符合大多数锚节点发送的信息。文中还提出一种基于投票的算法，从信号处理的角度来看，该算法与用于对象检测的Hough变换有些类似［11］。在本文中，我们提出了一种计算简单的基于梯度下降法和异常检测技术的迭代安全定位算法，算法中迭代更新的矢量解释以及异常检测技术与文献［12］提出的定位算法和文献［13］提出的寻找数据最小截平方和(LTS)的方法有相似之处。

1 无线传感器网络安全定位分析及建模

我们考虑基于Range-Based的无线传感器网络安全定位问题。设网络中有m个锚节点A1，A2，…，Am，有 n个未知节点 S1，S2，…，Sn。每个锚节点的位置已知，其位置为［xi，yi］T，i=1，2，…，m。未知节点S1的真实位置为L=［x，y］T，与之通信的锚节点个数为q个，接收到的锚节点的位置信息为 Ii=［xi，yi］T，i=1，2，…，q，未知节点 S1和锚节点之间距离的估计值为di。这些距离的估计值通常会带有噪声，我们设此噪声为均值为0，方差为σ2的加性高斯噪声。给定一组带噪声的测量值{(Ii，di)}，i=1，2，…，q，未知节点S1位置的估计值 ^L=［^x，^y］T可以通过用最小二乘法(LS)解以下超定方程组获得:

恶意锚节点 Aj在发送其位置 Ij=［xj，yj］T的时候，可能故意发送错误的位置信息。在这样的情况下，LS估计值 ^L=［^x，^y］T可能和真实位置 L=［x，y］T相差很远。因此，我们需要能够容忍这种攻击的安全定位算法。

不失一般性，我们假设每个恶意锚节点只改变距离di值，因为改变任何其他参数都可以转化为等效的改变di值。我们假设每个恶意锚节点添加一个独立均匀分布的干扰给距离的估计值di，并发送这些错误信息给定位节点。设是定位节点和锚节点之间的实际距离。定义

其中φi是均值为0，方差为σ2a的独立均匀分布随机变量，表示恶意锚节点造成的干扰;ωi是均值为0，方差为σ2的加性高斯噪声。定位节点S1从q个锚节点接收到测量值{(Ii，di)}，i=1，2，…，q，并使用这些测量值来确定其位置。

2 安全定位算法

在本章中，我们将提出一种结合梯度下降法和异常检测技术的迭代安全定位算法。当不存在恶意锚节点，测量噪声是加性高斯噪声的情况下，测量得到定位节点真实位置的概率密度函数为

则定位节点位置的最大似然估计为:

其对数似然函数为:

不考虑后面的2个常数项，其最大似然估计就是最小化下面的非线性函数。

即

其中，f(x，y)对应于式(2)中的指数部分。因此，最大似然估计值^L等同于式(1)的最小二乘解。

我们首先采用迭代梯度下降法搜索LS解。算法开始时，随机给出估计值的初始值^L(0)。在第k步迭代中，根据当前估计值 ^L(k－1)的值，计算f(x，y)的梯度，然后向梯度的负方向移动一步以更新估计值。设λ(k)表示当前位置估计值的代价函数梯度的负值

其中▽(·)表示关于位置L的导数。则

其中γ(k)是第k次迭代的步长，(λ(k))/(|λ(k)|)是梯度负方向的单位向量。那么

每次迭代都会得出一个新的估计值，这个估计值将更接近定位节点的真实位置。如前所述，由于恶意锚节点的存在，LS估计有较大的误差。因此，一旦梯度下降法收敛到LS解，我们就进入到异常检测阶段。

异常检测阶段:在实际中，各恶意锚节点造成的独立干扰趋于平均，使得LS解接近真实位置。因此，当定位节点位置的估计值接近LS解时，恶意锚节点产生的向量λi(k)将大于正常锚节点产生的向量。我们在原有梯度的基础上排除掉模值较大的向量，并使用剩余的向量来计算新的梯度。

在式(3)中，每个锚节点对应一个λi(k)，由于LS解接近真实位置，那些正常锚节点对应的|λi(k)|较小，而恶意锚节点对应的|λi(k)|较大，我们对所有|λi(k)|进行排序，那么从某一个|λi(k)|开始，其大小比它前一个|λi－1(k)|有明显的增加，当这个增加值大于我们设定的差分阈值β时，我们就认为其后的所有λi(k)是由恶意锚节点产生的，其作用是将位置估计值 ^L(k－1)=［^x(k－1)，^y(k－1)］T向远离真实位置 L=［x，y］T的方向拉动，于是我们舍弃这些λi(k)，保留前面模值较小的λi(k)重新求和，生成新的梯度向量λ(k)，然后用新的梯度向量λ(k)进一步进行迭代计算出最终的估计值。如图1所示，I1、I2为正常锚节点，I3为恶意锚节点，L(k－1)为异常检测之前得到的位置估计值，λ1(k)、λ2(k)、λ3(k)是关于 I1、I2、I3的向量，由于 I3是恶意锚节点，定位节点估计的距离d3和其实际的距离差别较大，由此产生的|λ3(k)|将大于由正常锚节点 I1、I2产生的|λ1(k)|、|λ2(k)|，于是我们可以利用这个特性，滤除掉I3产生的攻击。

图1 异常检测示意图

由上可知，本算法利用梯度模的大小来滤除恶意锚节点产生的攻击，但实际上梯度模的绝对大小并不能衡量锚节点是否是恶意的。由式(3)可知，梯度模的绝对大小和锚节点的位置，每一步迭代的结果以及所使用的测距方法有关;迭代次数越多，迭代结果越精确，测量噪声越小，那么梯度模的大小就越小。区分恶意锚节点的关键在于梯度模的相对大小，只有当相对大小超过差分阈值β时，算法才会认为存在恶意锚节点并滤除掉。

3 算法仿真及性能分析

我们通过仿真对本文提出的算法与LS算法、LMdS算法和投票算法进行了比较。假设20个锚节点随机部署在一个尺寸为100 m×100 m的区域中，加性高斯噪声的标准差为σ=1 m。对于LMdS算法，子集个数和每个子集中的节点数分别为M1=20和n=4。对于基于投票的算法，每个小格的尺寸为1 m×1 m，所以n1=100。对于本文提出的算法，差分阈值β选择不恰当就可能导致算法不能滤除掉所有的恶意锚节点，或者在滤除掉的节点中包含有正常锚节点，在这里我们选取β=1，此值是通过在0.5到2之间多次实验所得出的最佳值，迭代次数M=100。进入异常检测阶段的门限阈值为0.9。得到的结果均为500次仿真得出的平均值。我们采用以下线性递减的步长［14］:

同时，初始迭代位置的选择也会影响算法的收敛情况。因为在实际中，很难知道定位节点位置的先验知识，所以初始位置通常选择特殊点，在这里我们选择(0，0)作为初始位置。当选择的初始位置接近真实位置时，算法就会收敛得较快，当选择的初始位置离真实位置较远时，算法就会收敛得较慢，迭代次数就会较多。

仿真结果如图。其中，图2(a)为当恶意锚节点数占20%时，定位误差与攻击强度σa之间的函数关系;图2(b)为当恶意锚节点数占60%时，定位误差与攻击强度σa之间的函数关系。

图2 攻击条件下的定位算法比较

从图2(a)中我们可以看到，当恶意锚节点数小于50%时，随着攻击强度的增加，LS算法的定位误差成线性增长，其他3种算法的定位误差基本不变，而本文提出的算法优于其他两种算法;当恶意锚节点数达到60%时，LMdS算法和投票算法的定位误差随着攻击强度的增加有所增大，而本文提出的算法仍然能保持一个较理想的定位精度。仿真表明，本文提出的算法对独立的攻击具有较好的鲁棒性，其平均定位误差受攻击强度σ2a影响较小。

尽管平均定位误差是衡量算法是否有用的一个指标，但更重要的可能是算法是否能够定位到节点的真实位置。为了从不同的角度衡量算法的准确性，我们比较了其定位到真实位置的概率。由于噪声、步长等的影响，我们决定如果最终的估计距真实位置在σ2m以内，就认为该算法定位到了正确的位置。图3给出了各算法定位到真实位置的概率与恶意锚节点数目的函数关系。我们可以看到，当恶意锚节点数目小于50%时，LS算法的准确率最低，但基本能保持在75%以上。当恶意锚节点数目超过50%时，其他几种算法的准确率快速下降，而本文提出的算法比其他几种定位算法的准确率要高。

图3 攻击条件下不同算法收敛到正确估计的概率(σa=6 m)

与此同时，我们提出的算法的计算复杂度与恶意锚节点的数目没有任何关系，它只随迭代次数的增加成线性增长，在每一步迭代中，只需要计算当前估计值与各锚节点之间的距离。迭代步长的选择对算法的收敛速度有一定的影响，选择合适的步长能够缩短算法的收敛时间。

4 结论

本文提出了一种用于无线传感器网络的安全定位算法。该算法结合梯度下降法和异常检测技术，通过滤除掉不符合条件的测量数据来确定节点的位置。我们通过仿真证明了该算法的有效性。仿真结果表明，在恶意危险的环境下，本文提出的方法比现有方法具有更高的定位精度，且效果较为明显。

［1］ Cayirci E，Tezcan H，Dogan Y，et al.Wireless Sensor Networks for Underwater Surveillance Systems［J］.Ad Hoc Networks，2006，4(4):431－446.

［2］ Szewczyk R，Osterweil E，Polastre J，et al.Habitat Monitoring with Sensor Networks［J］.Communications of the ACM，2004，47(6):34－40.

［3］ 孙启永，张文，李海波，等.基于微电极阵列和无线传感器网络的水环境重金属检测系统研究［J］.传感技术学报，2013，26(7):907－911.

［4］ 段翠翠，王瑞荣，王建中，等.基于无线传感器网络的高危生产区人员定位系统［J］.传感技术学报，2012，25(11):1599－1601.

［5］ 彭宇，王丹.无线传感器网络定位技术综述［J］.电子测量与仪器学报，2011，25(5):389－399.

［6］ Niculescu D，Nath B.DV Based Positioning in Ad-Hoc Networks［J］.Telecommunication Systems，2003，22(1－4):267－280.

［7］ Capkun S，Rasmussen K，Cagalj M，et al.Secure Location Verification with Hidden and Mobile Base Stations［J］.IEEE Transactions on Mobile Computing，2008，7(4):470－483.

［8］ Capkun S，Hubaux J P.Secure Positioning in Wireless Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):221－232.

［9］ Liu D，Ning P，Liu A，et al.Attack-Resistant Location Estimation in Wireless Sensor Networks［J］.ACM Transactions on Information and System Security，2008，11(4):1－39.

［10］刘彩霞，黄廷磊.WSN中抵御虫洞攻击的改进的DV-Hop算法研究［J］.传感技术学报，2011，24(10):1473－1478.

［11］ Barinova O，Lempitsky V，Kholi P.On Detection of Multiple Object Instances Using Hough Transforms［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2012，34(9):1773－1784.

［12］ Takizawa Y，Davis P，Kawai M，et al.Self-Organizing Location Estimation Method Using Received Signal Strength［J］.IEICE Transactions on Communications，2006，B89－B(10):2687－2695.

［13］ Rousseeuw P，Driessen K.Computing LTS Regression for Large Data Sets［J］.Data Mining and Knowledge Discovery，2006，12(1):29－45.

［14］ Chang D，Chu F.A New Variable Tap-Length and Step-Size FxLMS Algorithm［J］.IEEE Signal Processing Letters，2013，20(11):1122－1125.