基于随机虚拟环的WSNs源位置隐私保护算法

白乐强 孙圣杰 曹科研 张士宏

1(沈阳建筑大学信息与控制工程学院 辽宁 沈阳 110168) 2(东软集团股份有限公司 辽宁 沈阳 110179)

0 引 言

无线传感器网络(Wireless Sensor Networks,WSNs)[1]是一种大规模的分布式网络，作为物联网的重要组成部分，在工程监测、医疗卫生、物流运输、航空航天、动物保护、国防军事等领域有着广阔的应用前景。一般来说，无线传感器网络是由传感器节点和基站节点组成，各个传感器节点之间及基站节点通过自组织、动态拓扑相互关联，彼此之间通过无线通信进行信息传递。WSNs采用的无线多跳的通信方式，容易遭受来自网络攻击者的监听和袭击，引发严重的位置隐私泄露问题[3]，因此WSNs中的位置隐私保护成为现今一个重要的研究方向。

Ozturk等[4]第一次提出WSNs中源节点的位置隐私问题，为解决此问题提出了基于洪泛的幻影路由算法。Kamat等[5]为降低通信开销、提高安全周期，提出了基于单径路由的幻影路由算法。陈娟等[6]研究发现基于单径路由的幻影路由算法在随机路由阶段产生的幻影源节点集中在某些区域，为此提出了一种基于源节点有限洪泛的源位置隐私保护算法。Wang等[7]为增加攻击者回溯时间，提高安全周期，提出一种基于环形路由的源位置隐私保护算法。Jia等[8]为增加幻影源节点的位置选择的多样性，提出了基于角度和动态调整节点发射半径的源位置隐私保护算法。

本文提出基于随机虚拟环的WSNs源位置隐私保护(ABRVR)算法，改善幻影路由算法中源节点距离基站节点较近时安全周期低的问题。ABRVR算法通过建立以基站节点为圆心的随机虚拟环，分散数据传输的路径，以此来达到保护源节点的目的。实验结果表明当源节点距离基站节点较近时该算法能够有效保护源位置隐私。

1 系统模型

1.1 网络模型

本文的网络模型与熊猫-猎人位置隐私保护模型[4]相似。网络模型满足以下条件：

(1) 无线传感器网络中有且仅有一个基站节点，且基站节点位于网络中心。(2) 无线传感器网络中的任意传感器节点位置固定，不可移动。(3) 网络中任意的节点的ID是唯一的。(4) 无线传感器网络中传送的所有数据包都是经过加密的，攻击者不能破解数据[9]。(5) 无线传感器网络中任意节点通过定位算法获得自己的坐标[10]。

1.2 攻击者模型

根据已有的数据追踪攻击策略，可把攻击者分为谨慎攻击者和耐心攻击者两类。研究表明耐心攻击者对数据的追踪能力更强大[6]，本文采用耐心攻击者模型。在巨大的利益驱动下，攻击者配备了精良的装备。对攻击者模型做出如下假设：

(1) 攻击者在追踪数据发送的源节点时，不会对网络运转造成影响，不会破坏网络中的传感器节点。

(2) 攻击者的监听范围有限，与传感器节点的通信半径相同[11]。

(3) 本文数据包的内容都经过加密处理，攻击者不能解密数据包、篡改数据包的内容。

1.3 符号定义及数学模型

1.3.1符号定义

本文提出的ABRVR算法的符号定义如表1所示。

表1 ABRVR算法符号定义

1.3.2预期幻影源节点SPE数学模型

如图1所示，设源节点的坐标为S(XS,YS)，基站节点的坐标为B(XB,YB)，预期幻影源节点SPE的坐标SPE(XE，YE)，虚拟环的半径为R。

图1 预期幻影源节点示意图

设(x，y)为直线LBS的任意一点，则直线LBS的方程可表示为：

y=kx+b

(1)

其中k、b可表示为：

b=YB-kXB

设(x，y)是虚拟环上的任意一点，则虚拟环的方程可表示为：

(x-XB)2+(y-YB)2=R2

(2)

联立式(1)、式(2)，求出XE、YE：

y1=kx1+b

或

y2=kx2+b

如果|x1-XS|<|x2-XS|，则XE=x1，YE=y1，否则XE=x2，YE=y1。预期幻影源节点SPE的坐标为：SPE(x1，y1)或SPE(x2，y2)。

2 ABRVR算法过程

2.1 ABRVR算法基本描述

基于随机虚拟环的WSNs源位置隐私保护算法可以从以下四个阶段描述：(1) 网络初始化阶段；(2) 定向路由阶段；(3) 虚拟环路由阶段；(4) 最短路径路由阶段。

基站节点B进行网络初始化，每个节点得到相关信息。在源节点S初始化阶段，源节点S随机产生以基站节点B为圆心，以R(R∈[Rmin，Rmax])为半径的虚拟环。源节点S沿最短路径向虚拟环发送数据包，到达预期幻影源节点SPE的通信范围停止，停止的节点即为幻影源节点SP1。幻影源节点SP1随机产生路由角度θ(θ∈[-180°，180°])，从幻影源节点SP1开始，沿着虚拟环转发数据包，角度大于或等于|θ|停止，停止的节点即为幻影源节点SP2。幻影源节点SP2沿最短路径把数据包发送到基站。

2.2 ABRVR算法具体流程

2.2.1网络初始化阶段

网络初始化阶段主要完成的任务是获取网络中的节点信息建立信息表，获取节点的邻居建立邻居表。节点的信息表中存放节点的ID、坐标、到基站的最小跳数Hop。节点的邻居表中存放邻居节点的ID、坐标、到基站的最小跳数Teleport_Hop。基站节点B生成网络初始化信息包NetworkInitial，在整个网络范围内广播[12]。NetworkInitial={InformationType，Sink_Coordinate，Teleport_ID，Teleport_Coordinate，hop}，其中InformationType代表发送消息的消息类型；Sink_Coordinate代表基站的坐标；Teleport_ID代表数据包发送节点的ID；Teleport_coordinate代表数据包发送节点的坐标；hop代表数据包发送节点到基站节点所经过的跳数，初始值为0。

设节点Q为网络初始化阶段中收到NetworkInitial信息包的节点，其处理信息包的过程如下：

Step1节点Q读取NetworkInitial信息包，判断是否首次收到NetworkInitial信息包，若首次收到，在邻居表中存储Teleport_ID、Teleport_Coordinate、Teleport_Hop转Step 2；否则转Step 3。

Step2节点Q判断自己是否为基站节点，若是基站节点，停止转发数据包；否则存储基站坐标，更新Hop=hop+1，转Step 4；

Step3节点Q查询sender_ID是否在邻居列表中，若在邻居列表中，则更新此邻居到基站的最小跳数Teleport_Hop=hop；否则在邻居表中存储Teleport_ID、Teleport_coordinate、Teleport_Hop。节点Q判断hop+1和Hop大小，若hop+1

Step4节点Q更新NetworkInitial信息包中的Teleport_ID为节点Q的ID、Teleport_Coordinate为节点Q的坐标、hop为Hop，转发数据包。

2.2.2定向路由阶段

源节点S沿最短路径向幻影源节点SP1发送数据包。设节点Q为定向路由阶段中的任意节点，处理数据包过程如下：

Step1节点Q是源节点S，随机产生以基站节点B为圆心、以R为半径的虚拟环，计算预期幻影源节点SPE的坐标。节点Q判断自己到预期幻影源节点SPE的距离dEQ，若dEQ≤100，停止转发数据包，节点Q视为幻影源节点SP1；否则转Step 2。

Step2节点Q计算每个邻居节点到预期幻影源节点SPE的距离，从距离SPE最近的节点中随机选择一个节点转发数据包。

2.2.3虚拟环路由阶段

幻影源节点SP1沿虚拟环向幻影源节点SP2转发数据包。设节点Q为虚拟环路由阶段中的任意节点，处理数据包过程如下：

Step1节点Q是幻影源节点SP1，随机生成角度θ。节点Q检查∠QBSP1(如图2所示)与|θ|大小关系，若∠QBSP1≥|θ|，则视为到达幻影源节点SP2；否则转Step 2。

Step2节点Q把邻居节点以直线LQB(如图2所示)为界分为顺时针集合和逆时针集合。节点Q选择与θ方向相同的集合，计算集合中每个节点到虚拟环的最短距离，从距离最短的节点中随机选择一个节点转发数据包。

图2 ABRVR算法流程示意图

2.2.4最短路径路由阶段

幻影源节点SP2沿最短路径向基站节点B转发数据包。设节点Q为最短路径路由阶段中的任意节点，处理数据包的过程如下：

Step1节点Q检查自己是否为基站节点B，若是基站节点B，停止转发数据包；否则转Step 2。

Step2节点Q从邻居表中选出到基站节点B距离最小的节点，转发数据包。

3 理论分析

源节点在定向路由阶段初始化时，建立的虚拟环的半径为R(R∈[Rmin，Rmax])，当R取Rmax时建立的虚拟环最大，如图3所示，Cmax是以B为圆心，Rmax为半径的圆。源节点发送数据包时，传输路径可能经过Cmax的任何位置，因此攻击者在Cmax内发现数据包的概率可以用攻击者的攻击范围除以Cmax的范围表示。如图3所示，Cmin是以B为圆心，(Rmax-r)为半径的圆。当攻击者出现在Cmin范围内时，攻击者攻击范围全部在Cmax内部；当攻击者出现在Cmin与Cmax之间的范围时，攻击者的部分攻击范围会落在Cmax外。

图3 虚拟环模型

(1) 攻击者出现在Cmin范围内。

如图3所示，CH是以攻击者H为圆心，r为半径的圆。CH的面积SH为：

SH=πr2

Cmax的面积Smax为：

攻击者捕获数据包的概率Pi用SH除以Smax表示：

(3)

(2) 攻击者出现在Cmin与Cmax之间的范围。

设攻击者到基站的距离为dHB(dHB∈((Rmax-r)，Rmax])，攻击者捕获数据包的概率随着dHB的变化而变化。对于dHB相同而位置不同的攻击者即攻击者在同一虚拟环上，攻击者捕获数据包的概率是相同的。设在此范围攻击者捕获数据包的概率为Pe，Pe可由dHB取各个不同值时攻击者捕获数据包概率的平均值表示。

如图3所示，在△BHF中，dBF=Rmax、dHF=r，∠HBF、∠BHF分别为：

如图3所示，△BHF≌BHD，S△BHF=S△BHD，由海伦公式可得，S△BHF为：

在CH中，朝向基站方向对应的扇形面积SDFH为：

如图3所示，CH与Cmax相交的面积SHB为：

SHB=SDFH+SDFB-S△BHF-S△BHD=

设此时攻击者H捕获数据包的概率为PH，PH可由CH与Cmax相交的面积SHB除以Smax表示。

Pe可由dHB取各个不同值时攻击者捕获数据包概率和的平均值表示：

(4)

(3) 攻击者捕获源节点的概率P。

当源节点出现在Cmax范围外时，过源节点S和基站节点B做直线LBS，LBS与Cmax相交于S′，当攻击者到达以为S′圆心，以r为半径的圆的范围时，即视为源节点被发现。如图3所示，CS′是以S′为圆心，r为半径的圆。设攻击者在捕获源节点时在Cmax范围移动了Ji跳、在Cmin与Cmax之间的范围移动了Je跳，攻击者捕获源节点的概率P为：

(5)

由式(5)得，攻击者捕获数据包的概率与Ji、Je相关，当源节点传送数据包到基站的传送次数增加时，Ji、Je之和也会增加，从而使P减小即攻击者捕获数据包的概率减小；当源节点传送数据包到基站的传送次数减少时，Ji、Je之和也会减少，从而使P增加即攻击者捕获数据包的概率增大。综上，ABRVR算法的安全周期与通信开销呈正相关，通信开销越大则安全周期越高；通信开销越小则安全周期越低。

4 仿真与分析

本文用MATLAB R2017b进行仿真实验，评估算法性能。为实现传感器节点均匀分布，将6 000 m×6 000 m的区域均匀划分成100×100个大小相同的网格，10 000个传感器节点初始位于各个网格中心。为模拟自然状态下传感器节点的随机分布情况，给各个传感器节点加一个服从正态分布的随机扰动值ε(ε～N(μ,σ2))[6]，使传感器节点随机出现在网格中的任意位置。在本文的网络环境中，源节点随机选择，基站节点位于网络中心。

4.1 虚拟环半径选择范围

ABRVR算法中不同的虚拟环半径取值，对应的算法安全周期和通信开销结果不同。本文通过实验，对比虚拟环半径从100 m到3 000 m时安全周期和通信开销的变化。图4是R取值不同时的安全周期变化示意图。图5是R取值不同时的通信开销变化示意图。其中R400、R800、R1200、R1600、R2000、R2400、R2800分别代表虚拟环的半径R为400 m、800 m、1 200 m、1 600 m、2 000 m、2 400 m、2 800 m。

图4 安全周期示意图

图5 通信开销示意图

由图4、图5可知，当虚拟环半径R小于1 600 m时，安全周期显著提高，通信开销的增加在可接受范围之内，因此虚拟环半径R的最小值取1 600 m；当虚拟环半径R大于2 400 m时，安全周期提高很小，通信开销增长较大，因此虚拟环半径R的最大值取2 400 m。

4.2 通信开销

ABRVR算法虚拟环半径取值R∈[1 600,2 400]，为确保实验的公平性，单径幻影路算法和PUSBRF算法随机步跳数取25跳，APS算法幻影源环形区域范围取1 600～2 400 m，四种算法通信开销变化如图6所示。

图6 通信开销示意图

由图6可知，单径幻影路由算法和PUSBRF算法通信较小且大小相当；APS算法的通信开销相比单径幻影路由算法和PUSBRF算法明显增加；ABRVR算法的通信开销最大。单径幻影路由算法和PUSBRF算法在随机步路由阶段都是固定随机步的跳数传送数据包，在最短路径路由阶段通过最短路径传送数据包到达基站，数据包传送次数相比其他算法少，因此通信开销较小；PUSBRF算法在单径幻影路由算法的基础上做了进一步改进，通过源节点有限洪泛阶段保证数据包传输时每一跳都远离源节点，因此通信开销增大。APS算法在上述两个算法的基础上增加了圆周路由阶段，因此相比单径幻影路由算法和PUSBRF算法通信开销增加。ABRVR算法在定向路由阶段需要向虚拟环转发数据包，在圆周路由阶段需要路由随机角度，都大量增加了数据包转发次数，因此通信开销最大。

图6还表明，ABRVR算法的通信开销变化呈现先下降后上升趋势。当源节点到基站跳数在5跳到25跳时，随着源节点到基站的跳数的增加通信开销不断减少，这是由于当源节点距离基站跳数增加时，相对应的到虚拟环选择区域的距离就会越近，在定向路由阶段向虚拟环发送数据包需要转发的次数减少；当源节点到基站跳数在25跳到50跳之间时，随着源节点到基站跳数的增加通信开销不断增大，这是由于当源节点到基站的跳数增加时，源节点在远离虚拟环选择区域，在定向路由阶段向虚拟环发送数据包需要转发的次数增加。

4.3 安全周期

四种算法安全周期实验条件与通信开销实验条件相同，安全周期变化如图7所示。

图7 安全周期示意图

由图7可知，单径幻影路由算法的安全周期最低，ABRVR算法的安全周期最高。单径幻影路由算法在随机步过程中，不能保证每一跳都远离源节点，造成安全周期最低。PUSBRF算法改进了单径幻影路由算法的缺点，保证了随机步过程中每一跳都远离源节点，提高了安全周期。APS算法增加了圆周路由阶段，通过圆周路由进一步增加了幻影源节点选择的随机性和地理位置选择的多样性，进一步提高了安全周期，但在最短路径路由阶段可能会经过源节点附近，影响算法性能。ABRVR算法改变上述算法以源节点为中心的传输数据过程，以基站为中心，在定向路由阶段每次随机选择虚拟环转发数据包并且保证数据传输的每一跳都远离源节点，在虚拟环路由阶段数据包沿虚拟环转发随机的角度增加了幻影源节点选择的随机性；同时，幻影源节点在虚拟环上各个位置出现的概率相同，大大增加了其地理位置选择的多样性，有效抵御攻击者的回溯攻击，因此相比其他三种算法其安全周期显著提高。

同时，由图7可知，当源节点距离基站较近时安全周期相比其他三种算法明显提高。首先，当源节点距离基站较近时，源节点向虚拟环发送数据包转发次数增加即数据传输路径增长，攻击者回溯攻击时间加长，因此安全周期提高；其次，当源节点距离基站较近时，ABRVR算法在定向路由阶段保证了数据包传送时每一跳都远离源节点和基站节点，攻击者攻击时间延长，提高了安全周期；最后，当源节点距离基站较近时，ABRVR算法在定向路由阶段选择随机的虚拟环转发数据包、在虚拟环路由阶段以随机角度转发数据包，两个阶段提高了幻影源节点地理位置选择的多样性，进一步提高了安全周期。

图7还表明，首先当源节点距离基站跳数在5跳到10跳时，安全周期呈增长趋势。当源节点距离基站跳数在5跳左右时源节点距离基站过近，对源节点位置隐私安全影响较大，造成安全周期较低；随着源节点距离基站跳数的增加，对源节点位置隐私安全影响逐渐减小，安全周期逐渐提高；其次，ABRVR算法的安全周期变化大体呈现先下降后上升趋势。在一般情况下，数据包传输的次数越多，攻击者找到源节点的时间越长；数据包传输的次数越少，攻击者找到源节点的时间越短。当源节点距离基站较近时，在定向路由阶段需要增加数据包转发的次数才能使数据包到达虚拟环，通信开销增大；当源节点出现在虚拟环选择区域时，在定向路由阶段的数据包传送次数减少，造成通信开销减少；当源节点距离基站较远时，在定向路由阶段需要增加数据包转发的次数才能使数据包到达虚拟环，因此对应安全周期的变化是先下降后上升趋势。

由式(5)得，攻击者找到源节点的概率与数据包传输的次数相关，数据包传输次数越多，攻击者找到源节点的概率越小；数据包传输次数越少，攻击者找到源节点的概率越小，因此ABRVR算法安全周期的变化呈先下降后上升趋势。综上，理论分析与实验结果相符，ABRVR算法安全周期变化呈先下降后上升趋势。

5 结 语

本文提出的ABRVR算法，改善了幻影路由算法中源节点距离基站节点较近时安全周期低的问题。该算法改变传统的幻影路由算法以源节点为中心的数据传输过程，以基站为中心，增加定向路由阶段和虚拟环路由阶段，提高了幻影源节点地理位置选择的随机性和数据包传输路径的多样性。理论分析表明，ABRVR算法的安全周期与通信开销呈正相关。实验结果表明，在源节点距离基站较近时，算法的安全性能得到明显提升。