一種用于源位置保護的幻影路由設計

許 勇，查千明，柯夢雅，劉 芬

安徽師范大學 數學計算機科學學院，安徽 蕪湖 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，即本文提出的方案可以增加幻影節點的個數?；糜肮濣c個數越多，相應的路徑越多，因此可更加有效地保護源節點位置隱私。同時，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安全性能。主要工作是提出了一種選擇有效的幻影節點的方法，避免了盲目游走；此外，增加了幻影節點的個數，從而達到增加幻影路徑數的目的，增加了攻擊者的攻擊難度。由于本文采用的獵人熊貓模型只是源位置隱私保護的一種情況（目標不移動），若應用于在目標移動場景中則開銷較大，下一步的工作，將研究移動目標位置隱私保護問題。