一种基于迭代投票的无线传感器网络安全定位算法*

张 品，毛文敏，徐 静

(杭州电子科技大学 通信工程学院，浙江 杭州310018)

0 引 言

无线传感器网络的众多应用，如，环境监测、目标追踪、网络路由等都是基于网络传感器节点的位置信息［1］。无线传感器网络常处于敌对环境中，无线传感器的位置信息极易受到攻击。因此，无线传感器网络的节点安全定位至关重要。

无线传感器网络安全定位技术近几年来成为了研究热点之一，并取得了大量的成果。文献［2］概述了现有的主要无线传感器网络安全定位算法。传感器网络节点安全定位的研究大致分为四大类:1)基于顽健观测的安全定位策略，如，VM 定位机制［3］，SeRLoc［4］，SLA［5］;2)基于顽健计算的安全定位策略，如，AR－MMSE［6］;3)基于恶意信标节点检测/隔离的安全措施，如，Liu D 检测算法［7］，DRBTS［8］;4)基于位置校验的安全措施，如，GFM 和TI 校验算法［6］。Srinivasan A 等人提出的DRBTS 中，每个检查点(信标节点)通过监听信道来监督邻居信标节点的服务情况，并根据每次的观察结果更新监督对象的声誉值;在此基础上，未知节点通过学习机制收集邻居信标节点的声誉信息，再根据这些信息采用信任分级和集体投票方法选出可信任的信标节点。

在DRBTS 中需进行位置信息传递，加大了节点坐标泄露的可能性，从而使恶意节点窃取、篡改节点位置坐标，造成未知节点错误的节点位置定位。针对节点的安全定位，本文提出了一种无需进行坐标信息传递的安全定位算法，此算法通过迭代投票的方式选出可信的信标节点，从而实现安全定位。

1 定位原理

假设无线传感器网络中有三种节点:信标节点，未知节点和恶意节点。未知节点nv为待定位的节点，N(v)为nv的邻近信标节点和节点nv的集合，共有n 个元素，R 为未知节点nv的通信半径，所有节点分布在二维平面内，每个节点ni都拥有唯一的身份标识IDi。本文提出的迭代投票算法主要基于以下原理进行安全定位:

1)若N(v)中的信标节点是可信的，则信标节点到未知节点nv的距离小于通信半径R;任意两信标节点的距离小于2R。

2)若信标节点nx，ny，nz是可信的，通过三边定位法［9］计算出的其他任意两个信标节点ni，nj的坐标pi，pj，必接近ni，nj的实际坐标。因此，当前信标节点的可信性可以通过以此节点为基准，计算出的其他信标节点坐标的准确性来加以判断。由于不进行节点坐标交换，计算出的节点坐标准确性可以通过以下方法加以描述:通过pi，pj计算得到距离d'ij=|pi－pj|，两节点间的实际距离为dij，两者之间的误差为|d'ij－dij|。若|d'ij－dij|小于ε(ε 为定位误差阈值)，则认为计算出的节点坐标准确，当前节点nx，ny，nz可靠。如图1 所示，信标节点A，B，C 是可信的，D，E 为另两个信标节点，利用三边定位法计算出D，E 的节点坐标D'，E'在其实际坐标附近，则|d'DE－dDE|＜ε。

图1 原理2 示意图Fig 1 Schematic diagram of principle 2

2 算法步骤

2.1 测距阶段

在测距阶段，N(v)中的每个节点ni测出到其他节点的距离，并剔除部分节点。具体步骤如下:

1)N(v)中的每个节点利用某一特定测距方法(如TDOA，TOA，RSSI)测出到其他节点的距离dij(i≠j)。所有的距离可以形成n×n 的距离矩阵Md

2)每个节点ni向待定位节点nv发送其到其他节点距离信息{IDi‖IDj‖dij}，其中，k 为合法节点共享的一组密钥，{}k为利用密钥k 对信息进行加密。

3)根据定位原理1，去除距离矩阵Md中相应的不可信信标节点。N'(v)表示剩余节点的集合，其元素个数为n'。

2.2 迭代投票阶段

在这一阶段，每个节点ni都有一个投票器votei来记录其得票数，初始值为0。根据迭代算法计算出的定位距离误差，对节点进行投票。具体步骤如下:

1)在N'(v)中任意选取三个信标节点nx，ny，nz;

2)利用nx，ny，nz的坐标px，py，pz和到其他所有信标节点ni(ni∈N'(v)，i≠x，y，z)的距离dxi，dxj，dxz，通过三边定位法计算出节点ni的坐标pi;

3)根据步骤(2)中计算出的坐标，计算除被选中的三个节点nx，ny，nz外，其他任意两个节点ni，nj之间的定位距离误差|d'ij－dij|;

4)若|d'ij－dij|＜ε，则信标节点nx，ny，nz各得一票，其投票器加1;

5)重复步骤(1)～(4)，经过num 次迭代，每个信标节点ni(ni∈N'(v))共获得的投票数为|votei|。

2.3 得票数表更新阶段

每个未知节点nv经过num 次迭代，形成每个信标节点ni(ni∈N'(v))的得票数表TVv(table of votes)，如表1 所示。未知节点交换得票数表，进行TVv更新，具体步骤如下:

表1 得票数表Tab 1 Table of votes

1)每个未知节点向其他未知节点发送自己的得票数表{IDv‖TVv}k;

2.4 未知节点定位阶段

未知节点nv根据TVN'v中信标节点的投票数进行定位。具体步骤如下:

1)未知节点选取获得投票数最多的三个信标节点na，nb，nc;

2)利用na，nb，nc的坐标pa，pb，pc和距离dvi(i=a，b，c)，通过三边定位法计算出nv的坐标p'v。

3 算法仿真

本文提出的迭代投票算法，迭代次数num 的大小将直接影响到定位误差和算法复杂度。假设误差阈值ε=10 m，如图3所示，即使在恶意节点数为时，通过14 次迭代定位误差≤0.1;15 次迭代误差≤0.05;16 次迭代误差≤0.01。

图2 节点分布图Fig 2 Deployment of nodes

图3 恶意节点数与迭代次数关系图Fig 3 Diagram of relationship between malicious nodes and iteration numbers

若迭代次数num=10，误差阈值ε=10 m，比较本文提出的迭代投票算法与未使用迭代投票的定位误差。如图4所示，本文提出的迭代投票算法极大地提高了节点定位精度。

图4 定位误差比较图Fig 4 Comparison of localization error

4 结 论

在安全定位算法中，进行节点间交换位置信息，增加了位置信息被窃听、篡改的可能。本文提出的算法在无须节点间交换位置信息的条件下，通过迭代投票选出可信的信标节点，实现安全定位。通过实验仿真，迭代投票安全定位算法能在较少的迭代次数下获得很小的定位误差，大大提高了定位精度。

［1］ Jiang Jinfang，Han Guangjie，Shu Lei，et al.A novel secure localizations scheme against collaborative collusion in wireless sensor networks［C］∥Proc of IEEE IWCMC，Istanbul，2011:308－313.

［2］ Zeng Yingpei，Cao Jiannong，Hong Jue，et al.Secure localization and localization verification in wireless sensor networks［C］∥Proc of the 2009 IEEE 6th International Conference on Mobile Ad－Hoc and Sensor Systems，Macau，2009:864－869.

［3］ Capkun S，Hubaux J P.Secure positioning in wireless networks［J］.IEEE Journal on Selected Areas in Communications，2006，24(2):221－232.

［4］ Lazos L，Poovendran R.SeRLoc:Secure range－independent localization for wireless sensor networks［C］∥Proc of the 2004 ACM Workshop on Wireless Security，Philadelphia:ACM，2004:21－30.

［5］ Anjum F，Pandey S，Agrawal P.Secure localization in sensor networks using transmission range variation［C］∥Proc of 2nd IEEE International Conference on Mobile Ad－Hoc and Sensor Systems，Washington:IEEE Computer Society，2005:195－203.

［6］ Liu D P，Ning W K Du.Attack－resistant location estimation in sensor networks［C］∥Proc of IPSN 2005，Los Angeles:IEEE Computer Society，2005:99－106.

［7］ Liu D，Ning P，Du W.Detecting malicious beacon nodes for secure location discovery in wireless sensor networks［C］∥Proc of International Conference on Distributed Computing Systems，Columbus:IEEE，2005:609－619.

［8］ Srinivasan A，Teitelbaum J，Wu J.DRBTS:Distributed reputationbased beacon trust system［C］∥Proc of the 2nd IEEE International Symposium on Dependable，Autonomic and Secure Computing，Indianapolis:IEEE，2006:277－283.

［9］ 戴 欢.无线传感器网络定位算法及其应用研究［D］.无锡:江南大学，2012.

［10］Zhong S，Jadliwala M，Upadhyaya S，et al.Towards a theory of robust localization against malicious beacon nodes［C］∥Proc of IEEE INFOCOM，Phoenix，2008:1391－1399.