基于雙向樹(shù)的WSNs端到端位置隱私保護(hù)*

胡 慶， 王志偉， 周 林

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

基于雙向樹(shù)的WSNs端到端位置隱私保護(hù)*

胡 慶， 王志偉， 周 林

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

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

端到端； 雙向樹(shù)形拓?fù)洌?最短路徑； 假包； 位置隱私

0 引 言

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

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

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

本文針對(duì)多源節(jié)點(diǎn)的情況下的端到端位置隱私保護(hù)進(jìn)行了研究分析，提出了一種基于雙向樹(shù)形拓?fù)涞奈恢秒[私保護(hù)方案(BTBLPS),目的是為了能夠在多源條件下同時(shí)對(duì)源節(jié)點(diǎn)和基站進(jìn)行保護(hù)。值得一提的是，本文研究是在局部監(jiān)聽(tīng)情況下進(jìn)行的，對(duì)于全局監(jiān)聽(tīng)不在本文考慮范疇。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

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

圖1 網(wǎng)絡(luò)模型

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

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

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

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

1.2 攻擊者模型

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

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

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

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

2 基于雙向樹(shù)的WSNs端到端位置隱私保護(hù)

2.1 基本思想

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

2.2 工作過(guò)程

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

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)絡(luò)中，每個(gè)中間節(jié)點(diǎn)都會(huì)保留一個(gè)計(jì)數(shù)器，它會(huì)自動(dòng)記錄經(jīng)過(guò)節(jié)點(diǎn)的數(shù)據(jù)包數(shù)量，當(dāng)數(shù)目達(dá)到某一閾值Threshold時(shí)，該中間節(jié)點(diǎn)就會(huì)以概率P的可能性產(chǎn)生假包分支，稱(chēng)這類(lèi)中間節(jié)點(diǎn)為交叉節(jié)點(diǎn)。

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

圖2 簡(jiǎn)單的例子

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

3.1 安全時(shí)間對(duì)比分析

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

圖3 源位置隱私安全時(shí)間

圖4 基站位置隱私安全時(shí)間

3.2 通信開(kāi)銷(xiāo)對(duì)比分析

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

圖5 能量消耗

4 結(jié)束語(yǔ)

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61171190)

TP 393

A

1000—9787(2015)03—0040—04

胡 慶(1958-)，女，四川井研人，博士，教授，主要研究方向?yàn)楣饫w傳感技術(shù)的應(yīng)用和計(jì)算機(jī)網(wǎng)絡(luò)。