胡 慶， 王志偉， 周 林

(重慶郵電大學 通信與軟件技術(shù)研究所，重慶 400065)

基于雙向樹的WSNs端到端位置隱私保護*

胡 慶， 王志偉， 周 林

(重慶郵電大學 通信與軟件技術(shù)研究所，重慶 400065)

針對多源節(jié)點的情況下的無線傳感器網(wǎng)絡(WSNs)端到端位置隱私保護進行研究，提出了一種基于雙向樹形拓撲結(jié)構(gòu)的隱私保護方案(BTBLPS)。該方案采用最短路徑方式進行真實數(shù)據(jù)包傳輸，然后在最短路徑的交叉點上產(chǎn)生雙向的假包傳輸分支。其中，臨近源節(jié)點一側(cè)分支上的假包傳輸方向是從分支末端節(jié)點傳輸?shù)浇徊纥c，而臨近基站的一側(cè)恰好相反，以此來達到同時對源節(jié)點和基站的位置隱私進行保護的目的。理論分析與仿真結(jié)果表明:所提的方案是可行的，并且具有良好的安全性能。

端到端； 雙向樹形拓撲； 最短路徑； 假包； 位置隱私

0 引 言

從無線通信、片上系統(tǒng)(SOC)以及微機電系統(tǒng)(MEMS)的最新研究進展中發(fā)現(xiàn)，低成本無線傳感器網(wǎng)絡(wireless sensor networks, WSNs)[1]已經(jīng)得到了廣泛應用。在WSNs中，部署在目標區(qū)域中的傳感器節(jié)點感知到事件時，會將產(chǎn)生的消息經(jīng)過一個多跳的路由發(fā)送給基站,基站將接收到的消息進行處理后通過衛(wèi)星或互聯(lián)網(wǎng)發(fā)送給用戶。顯然，基站承擔著網(wǎng)關(guān)的作用，一旦失效將會導致整個網(wǎng)絡的癱瘓。同時，源節(jié)點距離被監(jiān)測事件是最近的。如果被破壞，不僅信息無法被采集而且被監(jiān)測對象也將面臨嚴重的安全威脅。因此，保護源節(jié)點和基站的位置隱私尤為重要。然而，以往的研究通常獨立地著重于源節(jié)點或基站位置隱私，并且主要集中在單源節(jié)點情況,而實際網(wǎng)絡遠非如此，以監(jiān)測熊貓棲息的WSNs為例，多個熊貓有可能會同時出現(xiàn)在某個區(qū)域(如水源或竹林等)，那么,這個區(qū)域就會出現(xiàn)多個向基站發(fā)送數(shù)據(jù)包的源節(jié)點。

例如：針對源位置隱私，Ozturk C等人通過使用“熊貓—獵人”博弈模型作為傳感器網(wǎng)絡的應用場景，提出了幻影路由方案[2]。在方案中，通過使用隨機行走策略避免攻擊者定位到源節(jié)點。Song Sejun等人提出了一種匿名化隱私保護方案E-LPG[3]。通過利用隱形的蟲洞技術(shù)把消息傳輸進行空間分散。同時，采用隨機延遲轉(zhuǎn)發(fā)技術(shù)把消息傳輸進行時間分散，以打亂消息隊列的傳輸順序?qū)崿F(xiàn)隱藏目標運動的原始軌跡。Zhou Liming等人提出了兩種基于隨機行走的源位置隱私保護策略：多路徑隨機行走(MRW)[4]和混淆區(qū)域方案(CAS)[5]。兩者的不同在于前者通過引入多條隨機路徑保護源位置隱私，而后者通過引入多個混淆區(qū)域保護源位置隱私。

針對基站位置隱私：Nezhad A A等人提出了一種匿名拓撲發(fā)現(xiàn)的方法，這種方法可以隱藏Sink節(jié)點的位置[6]。與傳統(tǒng)協(xié)議不同的是，此協(xié)議允許所有節(jié)點廣播路由發(fā)現(xiàn)消息，從而可以隱藏Sink節(jié)點的位置。Yao Lin等人提出了一種基于多條最短路徑的匯聚節(jié)點位置隱私保護方案[7]。通過利用分支路徑把攻擊者引向遠離匯聚節(jié)點的方向。Chen Honglong和Lou Wei提出了四種端到端位置隱私保護方案：隨機向前轉(zhuǎn)發(fā)、雙向樹、動態(tài)雙向樹和曲折雙向樹[8]。然而，上述四種方案也僅僅只適用于單源節(jié)點情況。

本文針對多源節(jié)點的情況下的端到端位置隱私保護進行了研究分析，提出了一種基于雙向樹形拓撲的位置隱私保護方案(BTBLPS),目的是為了能夠在多源條件下同時對源節(jié)點和基站進行保護。值得一提的是，本文研究是在局部監(jiān)聽情況下進行的，對于全局監(jiān)聽不在本文考慮范疇。

1 系統(tǒng)模型

1.1 網(wǎng)絡模型

本文的網(wǎng)絡模型與“熊貓—獵人”博弈模型[2]相似，如圖1所示。在目標區(qū)域中分布著大量用于監(jiān)測多個熊貓生活習性的傳感器節(jié)點。熊貓被發(fā)現(xiàn)時，距離它最近的傳感器節(jié)點將會把相關(guān)消息周期地發(fā)送給基站，其中周期間隔為Ts。同時，假設一個特殊獵人不僅可以反向追蹤數(shù)據(jù)包定位到源節(jié)點，也可以跟隨數(shù)據(jù)包傳輸方向追蹤到基站。具體假設如下：

圖1 網(wǎng)絡模型

1)整個網(wǎng)絡中節(jié)點相對均勻分布，且所有節(jié)點配置相同，它們具有相同的計算能力、存儲容量和通信半徑。

2)如果兩個節(jié)點之間的距離小于節(jié)點通信半徑時，節(jié)點能相互通信。

3)網(wǎng)絡中僅有一個基站，且基站具有的能力遠大于普通節(jié)點。

4)每個節(jié)點都有它的路由表，路由表中記載著節(jié)點到基站的最小跳數(shù)信息。

1.2 攻擊者模型

為了能夠獲得源節(jié)點或基站的位置，攻擊者配備了先進裝備和技術(shù)，具體特征假定如下：

1)攻擊者的目的在于捕獲源節(jié)點或基站，因此，不能影響網(wǎng)絡功能的正常運行,并且監(jiān)聽半徑和普通節(jié)點的通信半徑相同。

2)攻擊者在網(wǎng)絡中隨機行走直到監(jiān)聽到節(jié)點發(fā)送的數(shù)據(jù)包后隨機決定追蹤源節(jié)點或基站。

3)攻擊者硬件配置優(yōu)良，具有強大的存儲能力和計算能力，能夠快速檢測出消息的發(fā)送者并定位到發(fā)送者的位置。

2 基于雙向樹的WSNs端到端位置隱私保護

2.1 基本思想

本文針對多源節(jié)點的情況下的WSNs端到端位置隱私保護進行研究，利用的假包分支路徑來保護端到端位置隱私?；舅枷耄壕W(wǎng)絡中所有的真實數(shù)據(jù)包都是以最短路徑的方式傳輸?shù)交?。由于?jié)點分布的均勻性和密集性，并且在多源節(jié)點分布相對密集的情況下，不同的源節(jié)點向基站傳輸數(shù)據(jù)包時，相鄰源節(jié)點之間的傳輸路徑必定存在相交的情況。就在這些交叉節(jié)點上利用虛擬消息產(chǎn)生樹形分支。針對源位置隱私保護，分支結(jié)構(gòu)在源節(jié)點一側(cè)的交叉節(jié)點上進行設計。其中，虛擬消息的傳輸方向是從葉節(jié)點向梗節(jié)點傳輸。這樣即使攻擊者反向跟蹤數(shù)據(jù)包，這些分支將會誘使攻擊者偏離真實傳輸路徑，從而保護源位置隱私。同樣的,在基站一側(cè)的交叉節(jié)點上設計樹形分支;不同的是,虛假消息的傳輸方向是從梗節(jié)點向葉節(jié)點傳輸,這樣就能把根據(jù)數(shù)據(jù)包傳輸方向追蹤基站的攻擊者誘導到虛假路徑上，進而保護基站位置隱私。

2.2 工作過程

WSNs節(jié)點部署完成以后，首先進行網(wǎng)絡的初始化，其次是數(shù)據(jù)包傳輸過程。在初始化過程中，基站進行泛洪廣播，目的是為了實現(xiàn)鄰居節(jié)點的發(fā)現(xiàn)和發(fā)現(xiàn)每個節(jié)點到基站的最小跳數(shù)信息。在本文中，Ni表示節(jié)點i的鄰居節(jié)點組合，CLi表示節(jié)點i的近鄰列表，α表示傳輸路徑上產(chǎn)生分支節(jié)點比例。數(shù)據(jù)包的發(fā)送過程如下述：

1)Initiation：Next_hop=Null,Leaf_node=Null,Counter=Null.

2)Build the neighbor set Ni and the closer listCLi.Randomly select a node fromCLiasNext_hop.

3)Leaf_node←RandomSelect(Ni,Next_hop).

4)While receive a message m do

5)Forward(m,Next_hop).

6) ifHi>αHsand Counter(i)≥Thresholdthen

7)SetTTL(branch_req,L).

8) Sendbranch_reqtoLeaf_nodewith probability P.

9) else ifHi<αHsandCounter(i)≥Thresholdthen

10)SetTTL(sink_dummy,L).

11) Sendsink_dummytoLeaf_nodewith probability P.

12) end if

13)end while

在網(wǎng)絡中，每個中間節(jié)點都會保留一個計數(shù)器，它會自動記錄經(jīng)過節(jié)點的數(shù)據(jù)包數(shù)量，當數(shù)目達到某一閾值Threshold時，該中間節(jié)點就會以概率P的可能性產(chǎn)生假包分支，稱這類中間節(jié)點為交叉節(jié)點。

具體數(shù)據(jù)包發(fā)送過程用一個簡單的例子來描述。如圖2所示，圖中S1,S2和S3表示源節(jié)點，K1～K9表示交叉節(jié)點。數(shù)據(jù)包沿著最短路徑從源節(jié)點向Sink節(jié)點發(fā)送，其中灰色箭頭表示假包傳輸方向。當真實數(shù)據(jù)包傳輸路徑在交叉節(jié)點相交時，概率性產(chǎn)生路徑長度L=4的假包分支。其中，位于源側(cè)的分支，假包傳輸方向從葉節(jié)點向最短路徑上的梗節(jié)點傳輸，而位于Sink一側(cè)分支的假包傳輸方向則相反。產(chǎn)生假包分支的目的主要在于增加逐跳追蹤攻擊者攻擊到源或基站的難度，以此來延長網(wǎng)絡的平均安全時間。

圖2 簡單的例子

BTBLPS方案的源側(cè)分支生成算法步驟如下:

1)Initiation：Stalk_node=Null,Leaf_node=Null.

2)while receive abranch_reqmessage do

3) SetStalk_nodeas the sender ofbranch_req.

4)TTL←GetTTL(branch_req).

5) ifTTL>0 andLeaf_node=Nullthen

6)Leaf_node←RandomSelect(Ni,Next_hop) .

7)SetTTL(branch_req,TTL-1).

8)Forward(branch_req,Leaf_node).

9) else ifTTL= 0 then

10)SetTTL(source_dummy,L).

11) Become a fake source and periodically sendsource_dummytoStalk_node.

12) end if

13)end while

14)while receive asource_dummymessage do

15)TTL←GetTTL(source_dummy).

16) ifTTL>0 then

17)SetTTL(branch_req,TTL-1).

18)Forward(source_dummy,Stalk_node).

19) end if

20)end while

BTBLPS方案的基站一側(cè)分支生成算法步驟如下：

1)Initiation：Leaf_node=Null.

2)while receive asink_dummymessage do

3)TTL←GetTTL(sink_dummy).

4) ifTTL>0 then

5) ifLeaf_node=Nullthen

6)Leaf_node←RandomSelect(Ni,Next_hop).

7) end if

8)SetTTL(sink_dummy, TTL-1).

9)Forward(sink_dummy,Leaf_node).

10) end if

11)end while

3 仿真結(jié)果分析

本文使用NS2進行仿真實驗，分別對BTBLPS,Shortest path和FRW(forward random walk scheme)三種路由方案進行仿真對比分析。假設有3000個傳感器節(jié)點均勻部署在4 500 m×4 500 m區(qū)域內(nèi)。節(jié)點的通信半徑R為150m，每個節(jié)點的鄰居節(jié)點平均個數(shù)為7.29，α=0.5。基站的位置部署在區(qū)域的中間，當消息傳輸路徑在某一節(jié)點相交時，以概率P=1的可能性生成長度L=10的假包分支。

3.1 安全時間對比分析

圖3、圖4顯示了僅有兩條最短路徑情況下三種方案的源節(jié)點和基站的位置隱私保護安全時間。從圖中可以看出，隨著數(shù)據(jù)包傳輸路徑長度增大，三種方案的安全時間都隨之增加，其中BTPLPS增加幅度更大，這是因為隨著傳輸路徑的延長，方案產(chǎn)生的假包分支條數(shù)增加，從而導致安全時間變長。此外，基站位置隱私保護的安全時間明顯高于源位置隱私。這是因為攻擊者在移動到接收者之前，需要等待數(shù)據(jù)包中繼信息以確定包的傳輸方向，而對于反向追蹤源節(jié)點來說，攻擊者能夠通過無線射頻定位技術(shù)檢測出消息的發(fā)送者并迅速移動至發(fā)送者的位置。

圖3 源位置隱私安全時間

圖4 基站位置隱私安全時間

3.2 通信開銷對比分析

圖5顯示了數(shù)據(jù)包傳輸路徑長度為15時，三種方案的能耗對比。從圖中可以看出：三種方案能耗都隨著源節(jié)點數(shù)量增加而增加，且BTBLPS的能耗較FRW和Shortest path都高，這是因為BTBLPS中引入了假包，因此,導致能耗的增加。然而，方案雖然增加了一定的通信開銷，但是實現(xiàn)了同時保護端到端位置隱私的目的，并且可以通過調(diào)節(jié)α,P和L的值來均衡安全時間和能耗，以滿足合理的實際需求。

圖5 能量消耗

4 結(jié)束語

本文主要針對多源節(jié)點情況下，端到端位置隱私問題進行了相應研究，提出了一種基于樹狀網(wǎng)絡拓撲的BTBLPS。真實數(shù)據(jù)包是通過最短路徑來傳輸?shù)模ㄟ^在最短路徑上的一些交叉節(jié)點產(chǎn)生假包分支，從而把攻擊者引向錯誤的位置或方向，以此來保護源節(jié)點和基站的位置隱私。最后通過理論分析和仿真結(jié)果驗證所提方案的可行性。實驗結(jié)果表明:BTBLPS雖然增加了一定的通信開銷，但是延長了安全時間，并且能夠同時對源節(jié)點和基站的位置隱私進行保護，具有一定的應用價值。

[1] Mehta K, Liu D, Wright M.Protecting location privacy in sensor networks against a global eavesdropper[J].IEEE Transactions on Mobile Computing, 2012, 11(2):320-336.

[2] Ozturk C, Zhang Y, Trappe W.Source-location privacy in energy-constrained sensor network routing[C]∥2004 ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN) in conjunction with ACM Conference on Computer and Communications Security,2004: 88-93.

[3] Song Sejun, Park H, Choi B Y.E-LPG: Energy efficient location privacy scheme against global attackers in sensor networks[J].International Journal of Security & Its Applications, 2013, 7(2):27-46.

[4] Zhou L, Wen Q, Zhang H.Preserving sensor location privacy in Internet of things[C]∥2012 Fourth International Conference on Computational and Information Sciences (ICCIS), IEEE, 2012: 856-859.

[5] Zhou L, Wen Q, Zhang H.Protecting sensor location privacy against adversaries in wireless sensor networks[C]∥2013 Fifth International Conference on Computational and Information Sciences (ICCIS), IEEE, 2013: 1384-1387.

[6] Nezhad A A, Miri A, Makrakis D, et al.Anonymous proactive routing for wireless infrastructure mesh networks[M].US:Springer,2007:71-82.

[7] Yao Lin, Kang Lin, Shang Pengfei, et al.Protecting the sink location privacy in wireless sensor networks[J].Personal and Ubi-quitous Computing, 2013, 17(5): 883-893.

[8] Chen Honglong, Lou Wei.From nowhere to somewhere: Protecting end-to-end location privacy in wireless sensor networks[C]∥2010 IEEE 29th International Performance Computing and Communications Conference (IPCCC), IEEE, 2010:1-8.

End-to-end location privacy protection in WSNs based on bidirectional tree*

HU Qing, WANG Zhi-wei, ZHOU Lin

(Institute for Communication and Software Technology,Chongqing University of Posts and Telecommunications, Chongqing 400065,China)

Research on end-to-end location privacy protection in case of multi-source node in WSNs, propose a privacy protection scheme based on bidirectional tree topology(BTBLPS).The scheme adopts the shortest path method to transmit real data packets, and then on intersection of the shortest path produce fake packet transmission branch of bidirectional.Among them, fake packet transmission direction of branch near source node is from branch node at the end to intersection, and the side near base station, is contrary, in order to realize location privacy protection of source node and base station at the same time.Theoretical analysis and simulation results show that the proposed scheme is feasible, and has good safety performance.

end-to-end; bidirectional tree topology;the shortest path;fake packet;location privacy

10.13873/J.1000—9787(2015)03—0040—04

2014—07—25

國家自然科學基金資助項目(61171190)

TP 393

A

1000—9787(2015)03—0040—04

胡 慶(1958-)，女，四川井研人，博士，教授，主要研究方向為光纖傳感技術(shù)的應用和計算機網(wǎng)絡。