基于信息分组的TDOA安全定位算法

吴开兴,张荣华

(河北工程大学信息与电气工程学院,河北邯郸056038)

无线传感器网络(wireless sensor network, WSN)是一种新型的低功耗、自组织、短距离的无线传输网络,可以实时监测网络分布区域内各种监测对象的状态信息。在WSN的各种应用中,大多数需要确定事件发生的位置,或者需要对目标进行跟踪。随着WSN应用研究的不断深入,对定位技术提出了更高需求。其中,安全定位已经与定位精度和能耗一起成为WSN中评价定位算法性能的三个主要标准之一。安全定位技术是WSN节点定位的关键技术,是定位过程有效性的重要保障[1]。

现有针对基于TDOA测距提出的安全定位算法,或者依赖于节点的密度[2],或者计算复杂性过高[3],或者只针对某种特定的攻击[4],具有局限性。由于WSN受到的攻击种类可能多种多样,不可能对每种可能出现的特定攻击行为采取一一防范的措施[5]。本文将针对基于TDOA测距的定位提出一种抵抗轻量级攻击的定位算法AR-TDOA (Attack Resistant-Time Difference Of Arrival),采用信息分组方法隔离可疑数据,目的是在存在攻击的情况下,保证节点的可靠定位,属于被动式的安全定位思想。

1 AR-TDOA算法

节点定位过程中,为了提供初始的定位参照,需要在初始化阶段预先部署一定比例的锚节点(beacon node),锚节点可通过GPS或预设等方式实现定位,配有大功率无线发射设备,向未知节点发送包含位置信息的信标报文。

1.1 TDOA测距原理

TDOA是一种适用性较强的定位算法,通过记录信号的到达时间差来测量距离,降低了对时间同步的要求,测距精度可达到厘米级,被广泛应用于WSN定位系统。

TDOA测距原理如图1所示,发射节点同时发射无线射频信号和超声波信号,接收节点记录两种信号到达的时间 T1、T2,己知无线射频信号和超声波的传播速度分别为 c1、c2,那么两点之间的距离为

1.2 坐标计算

本文计算坐标采用的是多边测量法的极大似然估计法。此方法在测距存在一定误差的情况下仍然能够达到相当高的定位精度。在进行坐标求解时,采用多边测量法(multilateration),它是三边测量法的变形,如图2所示。

即有n(n＞3)个参考节点 P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)到未知节点M的距离分别为d1,d2,…,dn,设M的坐标为(x,y),则满足

采用极大似然估计法(Maximum Likelihood Estimation,MLE)求解,从第一个方程开始分别减去最后一个方程,得

用线性方程组表示为

使用标准的最小均方差估计法可以得到节点M的坐标为

1.3 抵抗攻击的安全定位算法设计

提出的AR-TDOA算法主要针对安全敏感的无线传感器网络应用。AR-TDOA算法是在TDOA测距技术基础上增加安全机制,充分利用节点定位系统中大都存在冗余参照信息的特性,以方差的无偏估计是否符合误差假设为安全性检验依据,对采集来的定位信息进行数据分组过滤,目的是在存在攻击的条件下仍能有效的计算正确的定位结果,降低攻击对定位的影响。

本论文拟采用两步对采集来的信息进行过滤。

首先,对采集来的定位信息三元组进行初步过滤,考虑基于TDOA测距技术定位的特点,利用待定位节点与锚节点之间的距离d必定在节点的通信范围之内的特性,粗略滤掉 d＞R的定位数据,为第二步信息分组做铺垫。

其次,综合分析、比较了多种信息分组方法的时间复杂度和定位误差之后,选择复杂度和定位精度达到平衡的4NP算法[6]作为AR-TDOA中使用的信息集分组算法,对其进行改进,利用信息的一致性对定位信息进行分组。

正常的定位信息集其定位误差或均方差满足一定规律,因此正常的定位信息集中的定位信息三元组(xi,yi,di)之间满足某种关联特征。存在攻击的定位信息集中,恶意信标发出的定位信息三元组(xi,yi,di)与正常定位信息之间不存在关联特征,这些恶意三元组(xi,yi,di)在整个定位信息集中是奇异点。正常的定位信息可以根据数据之间的一致性进行数据分类,从而很容易排除这些奇异点。

1.4 一致性检验原则

由于存在测距误差,定位系统大都采用最小二乘法(least square,LS)进行估算。LS的回归模型和估算函数分别为

LS算法简单易行,但由于其代价函数采用求总和方式,LS算法对局外点非常敏感,单个干扰数据就足于导致参数估计严重偏差。针对LS算法的脆弱性,采用统计方法对定位结果进一步分析。根据经典回归理论可知,如果测距误差的分布是已知的,则通过分析残差可以检验所给参照数据是否服从误差分布,利用这个规律可以检验定位参照集是否满足一致性检验。

1.5 改进后的4NP信息分组算法

改进后的4NP信息分组算法步骤如下：

步骤1：生成安全定位信息集。利用蒙特卡方法从L中随机抽取K(K≥3)个元素形成集合L1,对集合L1进行一致性检验,直到集合L1通过一致性检验为止。

步骤2：集合划分。从剩余的L-L1中取出元素(xi,yi,di)放入L1中,对L1进行一致性检验,若满足则将元素(xi,yi,di)取出,放入L3;不满足则将元素取出,放入L2。直至l中所有元素取完,将L3元素并入L1中,若L1不满足一致性校验则继续转到步骤1。

步骤3：生成新簇L1,利用 L1中的元素采用极大似然估计法进行定位求解。

2 仿真结果

本节通过仿真来验证以上理论结果的正确性及检测算法的有效性,比较基于TDOA的定位算法,SeRLoc安全定位算法和AR-TDOA在受到攻击时的定位性能。在100m×100m区域内部署4个锚节点,坐标分别为(0,0),(0,100),(100,0) (100,100)。系统参数参照MIT开发的室内定位系统Cricket[8]取典型值,节点平均侦听到锚节点数为4,节点间通信距离为R,锚节点通信距离与R的比值为10,节点数N=500,未知节点随机放置,测距误差满足ε～U(-e,e)。

实验考察了不同虚假锚节点数量情况下对定位的影响,仿真中锚节点通信半径R=150m,模拟敌方虚假锚节点,向定位场景中广播错误的位置信息。整个实验重复1 000次,并取平均值。

图3为3种定位算法在不同攻击强度下的定位比较,其中 c为虚假锚节点数量,da为攻击强度,即虚假锚节点声称的坐标与真实坐标的偏差距离,de为平均定位误差,即定位结果偏离未知节点真正坐标的平均距离。由图3可以看出,攻击强度da从0逐渐增大到100m的过程中,3种定位算法的定位误差明显不同。da增大,基于TDOA测距的定位算法的定位误差明显增大,SeRLoc安全定位算法因扇形区域面积而忽略攻击强度小的定位坐标,但随着攻击强度的进一步增大,定位误差随之大幅增大。AR-TDOA算法的定位误差稍微增大到一个峰值后又回落到一个较小的稳定值,这是因为较明显的定位攻击第一步就被滤掉。

从图3中的曲线对比中可以看出,虚假锚节点数量c由1变为2时,基于TDOA测距的定位算法和SeRLoc安全定位算法的定位误差对应增大,这是由于增加了的虚假定位信息影响了定位精度。AR-TDOA算法定位误差变化相对缓和,因其采用了一致性检验原则排除虚假数据,利用符合条件的定位信息组进行定位计算。

改进前后的定位算法在计算开销与稳定性方面的比较见表1,可以看出改进后的AR-TDOA算法相对于基于TDOA测距的定位算法和SeRLoc安全定位算法在计算开销方面有少量增加,在稳定性方面优于前者。

表1 虚假锚节点攻击条件下定位比较Tab.1 Positioning comparison with malicious beacon nodes

3 结论

1)攻击强度增大,三种定位算法的平均定位误差随之增大,其定位误差大小顺序依次为TDOA＞SeRLoc＞AR-TDOA。

2)虚假锚节点数量越大,基于TDOA测距和SeRLoc的定位误差越大,但AR-TDOA算法的定位误差能保持在较小程度内。

3)AR-TDOA算法在增加少量计算复杂度的情况下,能够改善定位的稳定性。

[1]曹晓梅,俞波,陈贵海,等.传感器网络节点定位系统安全性分析[J].软件学报,2008,19(4)：879-887.

[2]LAZOS L,POOVENDRAN R.SeRLoc：Secure range-independent localization for wireless sensor networks[C]// LAZOSL L,POOVENDR AN R.Proc.of the 2004 ACM Workshop on Wireless Security.New York：ACM Press, 2004：196-207.

[3]LIU D,NING P,DU W K.Attack-resistant location estimation in sensor networks[C]//ZHAO F,COZZENS J,ESTRIN D.Proc.of the Int'l Conf.on Information Processing in Sensor Networks.Washington：IEEE Computer Society Press,2005：178-185.

[4]任秀丽,杨威,薛建生.一种基于测距的无线传感网Sybil攻击检测方法[J].计算机应用,2009,29(6)：1628-1631.

[5]BOUKERCHE A,OLIVEIR A H A,NAKAMURA E F,et al.Secure localization algorithmsfor wireless sensor networks [J].IEEE Communication Magazine,2008(4)：96-101.

[6]张起元.无线传感器网络虚假数据检测排除机制研究[D].合肥：中国科学技术大学,2010.

[7]叶阿勇.无线传感器网络节点安全定位[D].西安：西安电子科技大学,2009.

[8]PRIYANTHA N B,CHAKR ABORTY A,BALAKRISHNAN H.The cricket location-support system[C]//STEERE D C,BAPTISTA A,PU C,et al.Proc.of the 6th Annual Int' l Conf.onMobile Computing and Networking.Boston：ACM Press,2000：58-66.