基于隨機虛擬環的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算法的安全周期與通信開銷呈正相關。實驗結果表明，在源節點距離基站較近時，算法的安全性能得到明顯提升。