多可利用节点加权网格扫描安全定位算法

唐弢，郭庆，李含青

(哈尔滨工业大学通信技术研究所，黑龙江哈尔滨150001)

无线传感网络(WSN)是由部署在监测区域内的大量微型、低成本、低耗能的传感器节点组成的多跳无线网络、实现监测区域内敏感数据采集、处理和传输［1］.在WSN中，位置信息在WSN的监测活动中具有至关重要的作用，事件发生位置或获取信息节点位置是传感器节点监测消息中所必须包含的重要信息，没有位置信息的监测消息往往毫无意义.因此，确定事件发生的位置或确定获取消息的节点位置是WSN最基本的功能之一，对WSN应用的有效性起着关键作用［2］.

无线传感器网络中的定位问题可以描述为:在一个存在多个已知自身位置节点的多跳网络中，通过定位系统、利用可用的信息找到未知节点的位置.定位算法主要分基于测距定位算法和非测距定位2种:前者是利用接受信号强度(RSSI)、到达时间(TOA)、到达时间差(TDOA)、到达角度(AOA)等测距信息定位，具体算法如环形RSSI(ROCRSSI)定位算法等;后者是利用网络的连通度定位，如质心算法等［3］.

在无线传感器网络的某些应用网络中，存在着因对网络攻击而导致定位不准确或无法定位的情况，例如战场环境中的定位.战场环境下网络中的安全问题可以分为内部攻击和外部攻击两类:内部攻击是指网络中的某一节点发送错误的测量信息;外部攻击是指恶意节点伪装成其他节点发送错误位置或测量信息.因而无论是内部还是外部攻击，其最终的形式都是使节点的实际位置与声明位置不符，或给出错误的测量信息(如强度、时间等)［4-5］.另外，在网络中存在着多径的情况.多径问题是由建筑物反射等引起的，可以使未知节点在定位时误认为有多个锚节点存在，并且其中一个发送的是错误的信息.因而，多径也可以视为影响安全问题的一种因素.本文针对网络中的攻击和多径问题，提出一种新的安全定位算法“多可利用节点加权网格扫描安全定位算法(MANWS)”，解决了在有遮蔽战场环境下的定位问题.

1 网络模型和基本假设

本文假设存在一个多跳分布式无线传感网络.该网络主要针对于有遮挡的战场环境，如森林中的战场跟踪与监测等，因而存在着安全和多径问题.

在定位系统中通常有2种类型的节点:未知节点(unknown node)和锚节点(anchor).未知节点是指在网络中节点位置未知并且本身没有特殊的硬件设备可以获得自身信息的节点;锚节点是指节点可以通过GPS等外部设备或确知的实际布置因不需要定位系统计算就能直接得到自身的物理位置.其中，锚节点是整个定位系统的基础［6］.在网络中，各节点(包括未知节点和锚节点)的信息传播范围均为一个以自身实际位置为中心、R为半径的圆，即节点的通信半径为R.实际中，通信范围并不是一个规则的正圆而是一个不规则图形［7］，这并不对本算法的定位精度等指标产生影响，因而为方便表达选用简化的传播模型.同时，每个节点可以发现与自己距离1跳和2跳的节点.其中，1跳是指距节点距离在［0，R］内的节点;同理，2跳是指距节点距离在(R，2R］内的节点.另外，在节点上应安装RSSI测距设备和天线，以测量两节点之间的距离和角度.

式中:β是pass loss指数，通常由场地测量得来，表1给出了β的一些典型值，障碍物越多其数值越大，因此随着距离的增加接收到的平均能量下降的速度会越来越快(本文β=3).由式(1)可得:

式中:pt为传送信号的强度，Gt、Gr分别是发送者和接收者的天线增益，L(L≥1)为系统损失，λ为波长.通常情况下，Gt=Gr=1、L=l［8］.

表1 pass loss指数β的几种典型值Table 1 Typical value of the pass loss parameter β

pass loss通常由dB作为计量单位，因此根据式(1)可得

2 MANWS算法

MANWS算法主要分为锚节点检测和未知节点定位2个部分，具体流程如图1所示.下面将对算法做出详细的阐述.

2.1 锚节点检测

选择二维坐标系网络中任意2个锚节点ni和nj，且两节点之间的距离小于R，如图2所示.假设ni和nj相互间的到达角度分别为aij和aji.

图1 算法总体流程Fig.1 The process of algorithm

图2 锚节点ni和nj几何关系模型Fig.2 The geometry between ni＆nj

这里对nj的安全性进行判定，假设两锚节点之间的距离为dij，则有

式中:距离d和角度a分别由节点装载的RSSI装置和天线得到.如图2所示，如果不存在测量误差和攻击，显然可得

然而，在实际中测量会存在一定的误差，导致节点非恶意时相加的结果不为0，此时需要引入门限值来指导攻击节点的判断结果.设门限值为λ，则nj安全判定条件为

对于内部攻击，测量距离和角度都是错误的，所以可以由式(6)直接判定;而对于外部攻击，其测量距离是正确的，只是声明位置与实际位置不符，因而nj是否为攻击节点可以由式(7)进行判定.

式中:(xi，yi)、(xj，yj)分别是ni、nj的坐标.由于以上在进行判定时使用的锚节点ni可能是恶意节点，所以需应用轮盘法对nj通信范围内的每个锚节点进行计算，最后得到nj的可信度:

式中:M为nj可通信节点个数，N为网络中锚节点个数.

以上讨论了内部和外部攻击的情况，下面介绍网络中存在多径时此算法的应用.两锚节点间多径情况如图3所示，从ni获得的信息可以看出，nj有2个位置:原本位置和反射点，即(xij，yij)和(xij'和yij');同样的，有(xji，yji)和(xji'和yji').因而对nj的判断条件为

图3 多径情况下节点几何模型Fig.3 The geometry of network in multi-path

使用轮盘法遍历所有nj的可通信节点，只要有一个符合式(9)，则可以说明nj为可信任节点.由于多径情况的特殊性，此步骤可以在判定内部与外部攻击之前进行，从而去除衍生的反射点.

2.2 定位算法

假设网络中有N个锚节点和K个未知节点，且N≪K.定位算法可分为以下3个步骤:寻找锚节点、确定权值和对未知节点定位.

2.2.1 寻找锚节点

未知节点收集它所监听到的所有锚节点信息.若坐标为(xS，yS)的未知节点S可监听到的所有锚节点集合为LHS，相应锚节点坐标分别为(xi，yi)，则这些锚节点在以(xS，yS)为圆心、以R为半径的圆内，将之称为1跳锚节点，其集合为

收集LHS1中所有1跳锚节点的邻居锚节点作为2跳锚节点，相应锚节点坐标分别为(xj，yj).2跳锚节点在以(xS，yS)为圆心、以R和2R为内外半径的环形中，其集合为

因而，对于未知节点S，1跳锚节点有L1个，其集合为LHS1;2跳锚节点有L2个，其集合为LHS2.

2.2.2 确定权值

图4 未知节点区域Am×n网格划分Fig.4 The grid of unknown node area Am×n

权值的确定是多可利用节点加权网格扫描安全定位算法中最重要的部分之一.算法中，利用RSSI值对距离进行估计，并将距离的倒数作为权值.以下将对1跳锚节点和2跳锚节点两方面进行讨论.

1)当被估计距离范围为［0，R］时，未知节点S能直接接收到LHS1集合中锚节点发出的信号.则未知节点S接收到固定锚节点L1i的信号强度平均值pi为

式中:RSSIi表示未知节点S接收到固定锚节点L1i信号的RSSI平均值.同理可得固定锚节点L1i接收到固定锚节点L1j信号强度平均值pij.令dij表示固定锚节点L1i到固定锚节点L1j之间的距离，则由式(1)可得到未知节点S到固定锚节点L1i的距离di为

因此，可以假设LHS1集合中固定锚节点L1i的权值为 ωi=1/di.

2)当被估计距离范围为(R，2R］时，未知节点S能直接接收到LHS2集合中锚节点发出的信号.与1)相同，由于LHS2集合中锚节点为LHS1集合中锚节点的邻居，又因为任意2个锚节点中的距离已知，所以任意LHS2集合中锚节点L2k的权值为

式中:dik为L2k与其在LHS1中邻居节点之间的距离，di为未知节点S到L2k在 LHS1中邻居节点L1i的距离.值得注意的是，当网络中存在LHS2集合中锚节点的邻居节点多个存在于LHS1集合中，这时需计算所有ωk中最大值作为L2k的权值.

2.2.3 未知节点定位

权值计算完毕后，开始定位过程，多可利用节点加权网格扫描安全算法的定位过程如图5所示.

在未知节点区域Am×n中，将每个网格的计分牌数值初始化，即Q=0.遍历LHS1集合中所有锚节点，若网格在其通信范围内，则计分牌加上该锚节点的权值.然后，遍历LHS2集合中锚节点，若网格距锚节点在(R，2R］内，则计分牌加上此锚节点的权值.最后，得到网格的计分牌数值为

选择记分牌上最大的数值区域作为未知节点存在区域，并将此区域的质心作为未知节点S的估计位置.

图5 多可利用节点加权网格扫描算法定位过程Fig.5 The progress of weighted grid scan location algorithm with multi available nodes

3 MANWS算法仿真与分析

为了检验算法的性能，本文对所提出的定位算法进行了一系列仿真比较.仿真中，初始网络设置为一个(100×100)m2的正方形网络，并随机产生均匀分布的网络拓扑节点，节点数量为200个，其中有50个锚节点.节点通信半径R为20 m，每一小网格为(2×2)m2的正方形.这里假定pass loss指数β值为3.

定位精度是衡量定位算法精确性的主要标准，其表达方法为

式中:Errormin是定位的平均误差，(xe，i，ye，i)和(xr，i，yr，i)分别是未知节点的估计位置和实际位置.

3.1 不存在攻击或多径

本文主要对影响定位精度的参数:锚节点数量、通信半径和小网格边长进行仿真.

在对锚节点数量仿真时，假设其他条件不变，锚节点数量由20个增加到100个，将MANWS算法定位误差与 DLE(distributed location estimation)算法［9］进行比较，得到的仿真结果如图6所示.

在对通信半径仿真时，假设其他条件不变，通信半径由10 m增加到70 m，并将MANWS算法定位误差与DLE算法比较，得到的仿真结果如图7所示.

在对小网格边长仿真时，假设其他条件不变，小网格边长由1 m增加到3.3 m，得到的仿真结果如图8所示.

由图6～8可以看出多可利用节点加权网格扫描算法的定位精度明显好于DLE算法，并受通信距离、锚节点比例和小网格边长影响.

图6 锚节点比例对定位误差的影响Fig.6 Localization error vs.anchors number

图7 通信距离对定位误差的影响Fig.7 Localization error vs.communication range

图8 小网格边长对定位误差的影响Fig.8 Localization error vs.grid scale

3.2 存在攻击或多径

假设在一个(100×100)m2的正方形网络中存在节点数量为200个，其中锚节点由20个增加到100个，其通信半径均为R=20 m，pass loss指数β值为 3，并且网络受到女巫［10］、虫孔、泛洪［7，11］等几种常见形式的联合攻击，如图9所示.具体地说，网络中存在以下情况:1)单一恶意节点宣称一个远离它实际位置θ m的错误位置信息或修改它与待定位节点间的距离来影响位置评估精度;2)多个非共谋的恶意锚点，并且它们相互独立地宣称一个远离它实际位置θ m的错误位置信息或修改它与待定位节点间的距离来影响位置评估精度;3)考虑多个恶意节点是共谋的情况;4)多径反射形成的虚拟节点.另外，假设网络中存在各种类型恶意节点总数为10个，占总节点数的5%.

在此环境下，对多可利用节点加权网格扫描安全定位算法的进行仿真验证其安全性，并与DEL算法做出对比，如图10所示.

从图10可以看出，多可利用节点加权网格扫描安全定位算法可以抵御各种攻击，并能应用于多径问题存在的复杂环境中，与DLE算法相比，多可利用节点加权网格扫描安全定位算法具有更好的安全性.

图9 攻击模型示意Fig.9 Attack model

图10MANWS算法安全性能仿真Fig.10 Secure simulation of MANWS algorithm

4 结束语

提出了一种多可利用节点加权网格扫描安全定位算法，适用于丘陵、山脉等有遮蔽的复杂战场环境中，并且能够在精确定位的同时保证定位的安全性，从而抵御战场环境中的各种攻击.在下一步的研究工作中，将进一步研究此算法的移动性，另外一个目标是将该算法应用于三维环境中.

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，CAYIRCI E.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393-422.

［2］RAHMAN M Z，KLEEMAN L.Paired measurement localization:a robust approach for wireless localization［J］.IEEE Transactions on Mobile Computing，2009，8(8):1087-1102.

［3］汪炀，黄刘生，徐宏力，肖明军.基于RSSI校验的无线传感器网络节点定位算法［J］.小型微型计算机系统，2009，30(1):59-62.

WANG Yang， HUANG Liusheng， XUHongli， XIAO Mingjun.Localization algorithm for wireless sensor network based on RSSI-verify［J］.Journal of Chinese Computer System，2009，30(1):59-62.

［4］BOUKERCHE A，OLIVEIR H A B，NAKAMURA E F，LOUREIRO A A F.Secure localization algorithms for wireless sensor networks［J］.IEEE Communications Magazine，2008，46(4):96-101.

［5］BAGGIO A，LANGENDOEN K.Monte Carlo localization for mobile wireless sensor networks［J］.Ad Hoc Networks，2008，6(5):718-733.

［6］HU F ，TILLET J，ZIOBRO J，SHARMA N K.Secure wireless sensor networks:problems and solutions［J］.Journal on Systemics，Cybernetics and Informatics，2004，11(9):419-439.

［7］LAZOS L，POOVENDRAN R.HiRLoc:high-resolution robust localization for wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):233-246.

［8］RAGHAVENDRA C S，SIVALINGAM K M，ZNATI T.Wireless sensor networks［J］.International Journal of Distributed Sensor Networks，2007，3(4):371-371.

［9］SHEU J P，LI J M，HSU C S.A distributed location estimating algorithm for wireless sensor networks［C］//2006 IEEE International Conference on Sensor Networks，Ubiquitous and Trustworthy Computing.Washington DC，USA，2006:218-225.

［10］DOUCEUR J R.The sybil attack［C］//The First International workshop on Peer-to-peer systems(IPTPS'02).Cambridge，UK，2002:251-260.

［11］ZHANG Y，LIU W，FANG Y，WU D.Secure localization and authentication in ultra-wideband sensor networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(4):8-29.