一种用于源位置保护的幻影路由设计

许 勇，查千明，柯梦雅，刘 芬

安徽师范大学 数学计算机科学学院，安徽 芜湖 241000

1 引言

无线传感器网络（Wireless Sensor Network，WSN）作为物联网底层重要感知部分，广泛应用于军事、工业、农业、生态等方面。WSN由大量传感器节点通过自组织和多跳方式组成，节点通常部署在恶劣的环境中，用于资源监测、实时信息获取等方面。因其特殊的应用背景，WSN的安全性往往是其部署时必须考虑的重要问题。

WSN的安全问题主要分为两个方面：一是面向上下文的隐私保护，主要是对网络通信中的上下文信息，如时间、位置进行保护；二是面向传输内容的隐私保护，主要是保护传输内容所表达的隐私信息。其中面向上下文的隐私保护又可以分为位置隐私保护和时间隐私保护。位置隐私保护中最重要的是源节点的位置隐私保护，即对采集信息的感知节点进行位置隐藏。源节点位置主要受到全局流量攻击和局部流量攻击，而传统的信息加密技术无法抵御此类攻击。因此，源节点的位置隐私保护通常采用随机游走、幻影路由等方法。由于源节点位置隐私问题已成为WSN部署的关键制约因素之一，对其研究具有重要意义。

2 相关工作

关于源节点位置隐私保护，国内外学者已有大量研究。Kamat[1]等人率先提出了幻影路由方案(Phantom Routing Scheme,PRS)，该方案分为随机游走阶段和洪泛阶段，通过随机游走寻找幻影源，然后幻影节点以洪泛的方式传递信息。该方案在一定程度上起到了保护源节点位置隐私的作用，但采用完全随机行走策略，无法保证幻影节点远离源节点，且洪泛会导致数据分组以幻影节点为中心进行扩散，消耗大量能量。Zhang[2]提出定向随机路由协议(Directed Random Walk,DRW)。该协议有两种类型，基于扇区的定向路由游走策略和基于跳数的随机游走策略，两种策略都是将邻居节点划分到不同集合中，其中基于跳数的随机游走，将节点的邻居节点分为两个集合P和Q。划分的原则是，若邻居节点到汇聚节点的最短路径路由跳数不小于该节点到汇聚节点的跳数，将该邻居划分到Q集合中；若小于则划分到P集合中去。该协议在集合Q中选取幻影节点，以达到幻影节点远离源节点的目的。但是，由于该协议依旧采用完全的随机游走，不一定能够保障幻影节点远离源节点。刘学军[3]等人在此基础上提出基于最小能耗路由的源节点位置隐私保护协议，节省了网络消耗。Yao[4]提出定向贪婪行走的源位置隐私保护策略,降低了消息延迟时间和能源成本。

Wang[5]等人提出了基于位置角度的幻影路由方案（Phantom Routing with Location Angle，PRLA），该方案能使幻影节点远离源节点，但也不可置否的泄露源节点的方向信息。在PRLA方案中，首次给出了可视区的概念，并指出攻击者只要达到可视区范围内就表示源节点位置已经暴露。程娟[6]等人提出了基于源节点有限洪泛的源位置保护协议（PUSBRF）以及EPUSBRF，该方案通过定向步产生幻影节点，以此避开可视区；但若是监测目标变化太快，则网络中源节点的有限洪泛次数会剧增，从而消耗大量的能量。周永廖[7]等人提出基于幻影路由的增强型源位置隐私保护协议，使幻影节点与源节点距离增大，以此提高源节点安全性能。Long[8]等人通过树的迂回路由策略使网络生存时间得到最大化。通过创建与攻击者完全同质分支的树，利用这些传感器节点作为中间桥梁，使得幻影节点远离汇聚节点。Kumar[9]等人提出一种幻影节点的选取方法，使幻影节点、源节点、汇聚节点具有一定角度，以此来达到幻影节点远离源节点的目的。Yao和Wen[10]提出了定向增强随机游走策略，通过比较各个节点到汇聚节点的距离，选择最小距离的节点以保证源节点到基站距离最小。Rios[11]等人对无线传感器网络位置隐私方案进行了分析介绍。Huang[12]等人通过基于幻影的伪正态分布的方式提高幻影路由方案的安全性。另外，通过随机延迟转发[13]或在网络中注入垃圾包[14]等方法来迷惑攻击者，使攻击者难以快速定位源节点的位置，但其缺点是增加大量的通信开销，甚至有可能会引起网络阻塞。

针对源节点位置隐私保护中存在的安全性和能耗问题，本文提出基于随机游走的多幻影路由方案MPRP（Multi Phantom node Routing Protocol）。MPRP利用可视区，并且运用划分幻影源和三角选择算法相结合的方法，以此增加了幻影节点个数，从而增加路径的多样性。仿真实验表明，MPRP降低了通信开销，并延长了节点安全时间，因此可有效提升源节点位置隐私安全性能。

3 基于随机游走的多幻影节点路由方案MPRP

MPRP方案采取熊猫猎人博弈模型[1]，即在一个大面积的自然保护区中，通过传感器网络对珍稀动物的活动进行检测，传感器节点随机分布在监测区域中。该模型对网络进行设定如下：

（1）所有节点均为静态，即不能在网络中移动。

（2）全网只有一个基站，在一段时间内只有一个源节点。

（3）基站是安全的，不能被攻击者攻破。

（4）每个节点存储、计算、能量均相同，均有各自唯一标识ID。

模型对攻击者进行如下设定：

（1）攻击者只能在某一范围内进行局部流量监听，不能对数据包进行解析，也不能干扰整个网络的运行。

（2）攻击者是可以移动的。

（3）攻击者拥有强大计算和分析能力，不受存储空间、能量消耗限制。

（4）攻击者只能被动监听，不能捕获节点信息，也不能毁坏传感器节点。

（5）攻击者首先在基站附近监听。

（6）攻击者按照算法1进行监听。

算法1 Attacker Algorithm

1.Input：攻击者监听半径r

2.Output：是否找到源节点s

3.Begin

4.攻击者在基站附近进行监听

5.do{

6.Accept（message）//进行监听消息

7.Look（around）；//在监听半径内寻找发送节点

8.Find（node）；//寻找发送节点

9.Move（node）；//移动到该节点

10.if（node==s）

11.Find（s）；//找到源节点

12.else

13.Accept（message）；//在node处监听消息

14.}while（s）

15.End

3.1 总体设计

针对上述的网络设定和攻击者设定，MPRP方案使用三阶段协议完成对源节点位置隐私保护。协议流程如图1所示。

图1 MPRP流程图

随机游走阶段，引入可视区进行非线性划分限制随机游走方位，使源节点、Sink节点、幻影节点不在同一条直线上，以达到幻影节点尽可能远离源节点的目的；配置阶段，采用改进的三角选择算法，在幻影区域内找到多个备用幻影节点；路由选择阶段，通过路由选择算法选择一个真正的幻影节点，由该节点完成向Sink节点传输信息的任务。

3.2 随机游走

当有节点发现监测目标时，该节点即成为整个网络中的数据源。源节点负责将监测的信息发送给基站，因此源节点需判断基站是否位于自己的通信范围内。如果是，直接发送，否则需通过逐跳方式进行传递。在逐跳传递过程中需寻找幻影节点用于代替源节点向Sink节点发送信息，以达到隐藏源节点位置的目的。在随机游走阶段，还使用了可视区的概念。

定义1（可视区）以源节点s作为圆心，以n×r0（n指的是路由跳数，r0表示传感器节点的通信半径，n×r0表示源节点和幻影节点之间的最短距离）为半径画圆，该圆形区域称为可视区。

图2 非线性划分

通过非线性划分限制随机游走方位，使得幻影节点尽可能的远离源节点。MPRP方案还可通过多次随机游走的方式来获得更多的不同位置的幻影节点。

3.3 配置阶段

配置阶段分为三步：首先，Sink节点通过洪泛方式通告全网并发送带有到基站距离信息和计数器功能的信息，一段时间后，每个节点均可获得到自身到基站的距离；然后，各节点将该距离信息发送给Sink节点；最后，通过三角选择算法找到幻影节点。假定在配置阶段已完成了两次成功的随机游走，即产生了两个P集合，记为P1和P2。算法2给出了配置阶段的伪代码描述。

算法2 Improved Triple Selection Algorithm

1.Input：布置传感器网络N

2.Output：n1,n2← Select(N)//候选节点

3.Begin

4.sn←Sink_node()；//通过洪泛知道各个节点的信息

5.P1,P2←Random_Walk(N)；//随机游走产生两个集合P1,P2

6.rn1←Select_In(P1)；//在P1中随机选择一个节点rn1

7.rn2←Select_In(P2)；//在P2中随机选择一个节点rn2

8.θ1,θ2,θ3；//计算 rn1与 sn 之间夹角 θ1,rn2与 sn 之间夹角θ2,rn1与rn2之间夹角θ3

9.θ←arcsinx/H

10.do{

11.do{

12.rn1←Select_In(P1)

13.}while(θ1＞θ)

14.do{

15.rn2←Select_In(P2)

16.}while(θ2＞θ)

17.}while(θ3＞θ)

18.End

在算法2中，Sink节点的位置固定不变，当源节点确定后，经过两次随机游走产生不同的幻影集合P1和P2，分别在P1和 P2中随机选择一个节点n1和n2。通过改进的三角选择算法进行角度判断，如图3所示，当 θ1、θ2、θ3同时满足条件时，节点 n1、n2将作为幻影节点备选节点，否则将在幻影集合中重新选择节点进行判断。配置阶段完成后，可得到两个幻影节点的备选节点。

图3 三角选择示例

3.4 路由选择阶段

路由选择阶段是在两个备选幻影节点中选择一个节点作为真正的幻影节点。由于两个后备节点都满足上文所提出的要求，因此任意一个节点都可以达到隐藏源节点位置的目的。算法3给出了幻影节点的选取过程。

算法3 Routing Selection

1.Input：n1,n2

2.Output：幻影节点 p

3.Begin

4.Random function（num）；//随机生成数字0和1

5.If（num==0）

6.p=n1；//把n1作为幻影节点 p

7.else

8.p=n2；//把n2作为幻影节点 p

9.psend message to Sink node

10.End

在发送消息前，源节点预先生成随机数，然后检查配置阶段条件，最后由路由选择阶段确定的幻影节点向Sink节点发送信息，完成信息传递任务。

3.5 计算开销分析

本文提出的攻击者算法，即算法1，在监听过程中找到源节点，最好情况下的时间复杂度为O(1)，最坏情况下时间复杂度为O(n)，因此算法1平均时间复杂度为O(n)，空间复杂度为O(1)。算法2需要在P1和P2集合中分别通过循环判断选出一个满足条件的备选节点，因此算法2的时间复杂度为O(n2)，空间复杂度为O(1)。算法3在两个备选幻影节点中随机选择一个节点作为真正的幻影节点，因此该算法的时间复杂度为和空间复杂度均为O(1)。本文算法复杂度如表1所示。

表1 复杂度分析

4 安全性分析

幻影节点到源节点的距离和幻影节点个数，是影响路由方案安全性能的重要参数。本文将从这两个方面评价方案的安全性能，并将本文方案MPRP与HBDRW方案[5]、EPUSBRF方案[6和ABDRW方案[15]进行比较。

4.1 源节点与幻影节点的距离ds

HBDRW方案产生的幻影节点分布在以s为圆心，h为半径的圆周上的一段弧，弧度为因此，幻影节点与源节点的距离ds为h×r0（r0为节点的通信距离）。EPUSBRF方案产生的幻影节点在以s为圆心，h为半径的圆周上。因此，幻影节点与源节点之间的距离ds为h×r0。ABDRW方案产生的幻影节点在以s为圆心，h为半径，圆心角为θ的圆周上（本文取θ=π/4计算幻影节点个数）。所以，该方案源节点到幻影节点的距离是h×r0。

MPRP方案在源节点处随机游走h跳后，对该节点的邻居进行划分，产生的幻影节点分布在以s为圆心，h为半径的圆周上的节点及其邻居节点（以该节点为圆心，以1跳距离为半径的圆周上的节点），即在P集合中的选取幻影节点。因此，幻影节点与源节点的距离是最小为h×r0，最大为(h+i)×r0，平均距离大于h×r0。

相比HBDRW、EPUSBRF和ABDRW方案，MPRP源节点与幻影节点的距离更远，攻击者对真实源节点的定位将更加困难。

4.2 幻影节点数量n

方案产生的幻影节点数量越多，表明相应的路由路径越多，攻击者越难以找到源节点位置。所以幻影节点个数在某种程度上可以反映方案的安全性能。下面分别是HBDRW、EPUSBRF和ABDRW路由方案产生的幻影点数：

MPRP是在P集合中选取幻影节点，且P集合中幻影节点包括随机h跳以及跳数大于h的节点。因此，可得到满足条件邻居节点有πh个以及随机游走h的节点 2πh，即总节点数为 nM=3πh-4γH ，其中 γ 为 θ 弧度制，H为源节点到Sink节点的跳数。

表2是H定值50时的计算结果，从表中可以看出，上述协议在相同情况下产生的幻影节点个数：nM＞nE＞nA＞nH，即本文提出的方案可以增加幻影节点的个数。幻影节点个数越多，相应的路径越多，因此可更加有效地保护源节点位置隐私。同时，MPRP所获得幻影节点较好地避开了可视区，增加了幻影节点的个数，提高了幻影节点的质量，起到了保护源节点的作用。

表2 4种方案幻影节点个数比较

5 实验仿真

本文用MATLAB进行仿真，采用与文献[3]相同的实验环境。在仿真环境中，部署10 000个传感器节点，并且随机分布在（6 000 m×6 000 m）监测区域，基站位置固定在（0，0）处，源节点随机产生，传感器通信半径为r0=100m。

5.1 通信开销对比

如图4所示，当随机路由跳数h增加时，4种方案的通信开销也随之增加。随着h的增加，源节点与幻影节点距离增大，导致通信开销增加。当h=10时，4种方案的开销相近；当h=25时，本方案比ABDRW方案减少了2.21%，比EPUSBRF减少了4.09%，比HBDRW增加了35.68%；当h=30时，本文方案比HBDRW增加了11.3%，比ABDRW方案减少了0.85%，比EPUSBRF减少了2.61%。HBDRW的通信开销最小是因为其采用基于基站的有向路由跳数，没有增加额外的通信开销，ABDRW通过判断幻影路径是否经过可视区，选择不在可视区范围的路径，因此增加了通信开销，EPUSBRF为了避免可视区和使用有限洪泛策略，导致通信开销大大增加。MPRP引入角度计算，成功避免可视区，因此增加了部分开销。

图5给出了源节点、基站的距离与通信开销的关系。随着源节点与基站距离增加，消息传输路径随之变长，所以通信开销随之增加。由图5可以看出，MPRP较ABDRW方案平均开销降低了1.43%；与EPUSBRF方案相比，平均开销降低了2.5%；与HBDRW方案相比，平均开销增加了3.9%。比较而言，MPRP方案的通信开销介于上述几种方案之间，彼此之间的区分度不明显。

5.2 安全时间对比

安全时间是指攻击者从基站追踪到源节点所需经历的跳数[2]。图6表明安全时间随着随机路由跳数h的增加而增加。随着h的增大，幻影节点与源节点的距离随之增大，幻影节点个数越来越多（参见表2），相应的路由路径也随之增加。因此，攻击者难以迅速获取源节点的位置信息，从而延长了安全时间。从图6可以看出，4种方案安全时间最长的是MPRP，ABDRW和EPUSBRF次之，HBDRW最差。这是因为MPRP方案产生的幻影节点个数最多。当h=30时，本文方案的安全时间要比ABDRW提高了2.74%，比EPUSBRF提高4.7%，比HBDRW方案提高182%。

图7表明随着源节点与基站距离的增加，安全时间也随之增加。由于攻击者开始在基站附近监听信息，当源节点与基站的距离较远时，攻击者需逆向追踪更多跳数才有可能找到源节点，即延长了安全时间。与安全性能较差的HBDRW方案相比，MPRP方案的平均安全时间增加了156%，与EPUSBRF方案相比，平均安全时间增加了10.5%，与ABDRW方案相比，平均安全时间增加了1.49%。

图4 随机游走跳数vs.通信开销

图5 源节点距离基站的跳数vs.通信开销

图6 随机路由跳数vs.安全时间

图7 源节点距离基站的跳数vs.安全时间

6 结束语

本文提出的MPRP协议能够有效地保护源节点的位置信息安全，提高了WSN安全性能。主要工作是提出了一种选择有效的幻影节点的方法，避免了盲目游走；此外，增加了幻影节点的个数，从而达到增加幻影路径数的目的，增加了攻击者的攻击难度。由于本文采用的猎人熊猫模型只是源位置隐私保护的一种情况（目标不移动），若应用于在目标移动场景中则开销较大，下一步的工作，将研究移动目标位置隐私保护问题。