抗竊聽攻擊的傳感器網絡空間范圍聚集查詢處理算法*

胡震海，王立松

(南京航空航天大學計算機科學與技術學院，江蘇 南京 210016)

1 引言

無線傳感器網絡作為物聯網的重要組成部分，被廣泛應用于醫療衛生、智能家居、國防軍事等領域。無線傳感器一般具有廉價、體積小、質量小、能量有限、無線通信、較弱的計算能力和簡易的操作系統等特點[1]。無線傳感器能夠被靈活地布置，通過無線傳輸方式交換數據形成一個能夠存儲、計算、傳輸部署區域感知數據的多跳自組織網絡。無線傳感器的便捷部署，節省了人力物力，具有廣泛的應用前景。

無線傳感器網絡中，用戶經常提交空間范圍聚集查詢以獲取網絡中某區域的統計信息。相比較傳統的數據收集方式，數據聚集的收集方式節省了能量開銷。

一方面傳感器節點大都采用電池供電，常被部署于環境惡劣和無人值守的地方，部署后更換難度比較大。鑒于傳感器節點的更換難度以及有限能量，我們在采用傳感器節點存儲與傳輸感知數據的同時，應盡量延長傳感器節點的生命周期。另一方面由于傳感器容易被監聽，故在實際應用部署中可能會面臨隱私數據泄露和篡改問題。例如，在軍事領域中，傳感器網絡被部署獲取偵查區域數據，監測數據被監聽或篡改會帶來意想不到的后果；智能家居中，傳感器被部署于居民住宅內，用以統計區域內居民水煤電的用量情況，借以幫助市政單位做出決策。所以，應用無線傳感器獲取數據時，能量高效且考慮隱私的空間范圍聚集查詢成為廣泛應用中關鍵的一環。

現有的無線傳感器網絡聚集查詢隱私保護方法大都基于預先構造好的拓撲結構和全網絡的所有節點來處理，且常采用加密的形式對感知數據進行保護。拓撲結構的維護以及加密的方式都增加了傳感器節點的能耗。

針對以上問題，本文提出一種抗竊聽攻擊的傳感器網絡空間范圍聚集查詢處理PCPDA(Part of the area based on Cluster Privacy-preserving Data Aggregation)算法，對無線傳感器網絡中部分區域采用空間范圍聚集查詢方式收集感知數據。基站將查詢消息發送至指定區域，指定區域內采用邊查詢邊聚集的方式，動態地按照既定路線廣播查詢消息，收集感知數據，最后將聚集消息返回給基站。這種基于路線的收集方式，不依賴于預先構造好的拓撲結構，且在未采用任何加密措施的情況下，保護了傳感器節點原始數據的隱私性。

2 預備知識

傳感器網絡中的隱私保護既需要通過隱私保護策略來防止數據泄露和篡改，同時也需要通過數據管理技術來完成數據聚集、數據查詢，并且需要進行性能優化以減少能量損耗。傳感器網絡中的隱私保護策略主要包括數據擾動技術、數據加密技術和數據匿名化技術，數據管理技術主要從數據存儲、路由建立、查詢策略等方面進行性能優化[2]。故我們需要在保證傳感器網絡的隱私數據不被泄露的情況下完成數據聚集。

傳感器網絡在完成數據聚集情況下的隱私保護加密策略主要包括端到端加密策略和逐跳加密策略。

(1)逐跳加密：He等人[3]提出2種協議CPDA(Cluster-based Private Data Aggregation)和SMART(Slice-Mix-AggRegaTe)，CPDA中無線傳感器網絡組織成簇結構，簇內節點通過在感知數據中添加私有隨機數來保證感知數據的隱私性，簇頭節點利用多項式的代數性質來計算所需的聚合值。SMART中采用數據分片技術，將分片后j-1份數據片通過逐跳加密機制傳輸給相鄰的j-1個節點，節點對所收到的分片數據進行聚合，并根據所構造的TAG樹，將聚合結果傳輸給下一個節點，直至Sink節點。

SMART采用文獻[4]中提出的隨機密鑰分配策略，該密鑰策略主要由3部分組成：①密鑰預分配：密鑰池中有K個密鑰，傳感器網絡中的每個傳感器節點從池中隨機選取k個密鑰。②發現共享密鑰：每個節點找出它們鄰居中擁有相同密鑰的節點，如果2個節點擁有相同密鑰，則建立安全鏈接。③建立路徑密鑰：沒有相同密鑰的鄰居節點，可以通過多跳方式建立安全鏈接。

基于SMART的隱私保護加密過程分為3個步驟：分片、混合和聚集。①分片：節點隨機選取自身相鄰或h跳范圍內的節點，目標節點將自身數據分割成j份，自身保留1份數據，將其余j-1份數據通過安全通道隨機分發到h跳范圍內的節點。②混合：節點接收加密的數據分片后，使用發送節點的公鑰解密，接收節點等待一段時間，確保其余的分片數據到達，然后將接收到的分片數據相加。③聚集：節點數據混合后沿著拓撲樹將數據聚集到Sink節點。

在SMART的基礎上,文獻[5]提出了一種改進的傳感器網絡隱私保護協議PECDA(Privacy-preserving and Energy efficient Continuous Data Aggregation)。PECDA不需要對查詢區域內所有節點進行分片，對于所構造的拓撲樹，在數據分片階段只需對葉子節點進行分片。由于葉子節點只包括自身的感知數據，為避免其感知數據泄露給父親節點，數據分片階段只需對葉子節點進行分片，葉子節點將分片后的j-1份數據通過安全鏈接傳輸給鄰居節點。

文獻[6]中提出的DADPP(Data Aggregation Different Privacy-levels dim Protection)，根據不同的隱私級別，將同一簇內的所有節點劃分為多個組，各組內的節點有相同的隱私級別。 每個組分別對原始數據進行預處理，然后發給簇頭節點，簇頭節點聚集所有組預處理后數據，最后匯聚至基站。文獻[7]提出的iPDA(integrity-protecting Private Data Aggregation)利用SMART中切分重組的思想來保護數據的隱私，并通過構造不相交的聚合路徑/樹來收集感知數據，利用冗余數據進行完整性驗證。文獻[8]提出的ESPART(Energy-Saving Private-preserving AggRegaTion)對SMART進行了改進，一方面基于所構造的樹結構本身降低通信量從而節省能量，另一方面隨機分配節點時間片，降低信息傳輸過程中的碰撞率，同時限制串通數據范圍，降低了數據丟失對聚集精準度的影響。文獻[9]在文獻[3]的基礎上提出一種適應性較強的數據融合方法LSDA(Lightweight Secure Data Aggregation)，該方法采用分片重組技術，根據網絡通信量調整簇內節點分片大小。文獻[10]提出一種低能耗隱私數據安全融合方法LCSDA(Low energy-Consuming Secure Data Aggregation)，該方法根據最短路徑原則為簇內節點選取鄰居節點，并借助prim算法建立簇內數據的融合路徑。

(2)端到端加密：文獻[11]提出一種簡單的求和同態加密策略，采用該策略實現端到端加密機制的SUM聚集。該策略包含加密函數Enc()和解密函數Dec()，其中：Enc(m,k,M)=m+kmodM，Dec(c,k,M)=c-kmodM。節點Si與Sink節點共享密鑰ki，k是ki由計算得到的，M是系統參數，用m1、m2表示傳感器節點S1和S2的原始感知數據。文獻[12]提出的SP(Secret Perturbation)模式系列與方案AHE(Add Homomorphism)思路類似，其中BSP(Basic Secret Perturbation-based)模式通過添加輔助數據項，不僅實現了AHE功能，還能夠應對重放攻擊；FSP(Fully-reporting SP-based)模式中，Sink節點減去所有節點的秘密擾動數據和可得到正確的聚集結果；O-ASP(Optimal Adaptive SP-based)模式和D-ASP(Distributed Adaptive SP-based)通過對FSP的優化減少了數據傳輸的通信量。文獻[13]提出SIES(Secure In-network processing of Exact Sum)方案，通過加同態加密技術和數據共享[14]等技術實現密文數據的聚集操作，SIES通過SECOA(SECure Outsourced Aggregation)[15]來驗證聚集結果的完整性。壓縮數據收集是基于壓縮感知理論的一項重要突破，由于其開銷低的特性，已經在傳感器網絡中被用作數據收集的方法。在存在開放無線介質情況下，壓縮數據收集易受到各種攻擊的影響，文獻[16]提出一種高效的具有隱私保護能力的壓縮數據收集方案，該方案在壓縮數據收集過程中，采用同態加密的方式避免流量跟蹤和保證消息的機密性。無線傳感器網絡常通過端到端或逐跳的方式驗證數據，檢測虛假數據的注入。前者，檢測工作發生在消息聚集后，且只能在Sink節點進行。端到端的檢測方式效率不高，容易致使大量合法數據丟失。對此，文獻[17]提出一種基于端到端同態加密形式的隱私保護策略，并且通過逐跳的方式進行數據安全檢測，以此降低對Sink節點的依賴。

現有基于數據聚集情況下的隱私保護策略，采用數據加密技術，并且都是基于全網絡節點下的靜態查詢。針對以上問題，本文提出一種抗竊聽攻擊的傳感器網絡空間范圍聚集查詢處理算法，該算法不依賴于某種加密策略，采用邊查詢邊聚集的方法，動態地收集感知數據，能夠在完成數據聚集情況下保證節點原始數據的隱私性。

3 抗數據竊聽攻擊的動態傳感器網絡空間范圍聚集查詢PCPDA

PCPDA利用窗體查詢收集部分區域節點的感知數據并保證節點原始數據的隱私性。查詢窗體內，采用基于分簇的動態查詢方法，窗體內以邊查詢邊聚集的方式進行。

3.1 算法思想

為了避免現有算法的一些問題，本文提出一種抗竊聽攻擊的傳感器網絡空間范圍聚集查詢處理算法，該算法可分為3個階段：

(1)查詢發起節點(Sink節點)利用位置路由協議[18]將查詢消息發送至查詢區域。

(2)查詢區域內采用分簇的方法，簇內每個節點獲得的感知數據皆為其遍歷過的所有節點的感知數據的和，所以攻擊者無法獲得節點的原始感知數據。

(3)感知消息聚集后，利用位置路由協議發送回Sink節點，當Sink節點接收到聚集數據后，得到的便是聚集區域的感知數據之和。

為了不失一般性，如圖1所示基于一般的網絡分布情況，采用PCPDA收集查詢區域的感知數據。以Sink節點為查詢起始節點，用Ci(i=0,1,2…)表示簇頭節點，用a,b,c…表示數據節點，其收集過程如下所示：

(1)Sink節點發出查詢消息和隨機數num，利用位置路由協議將查詢消息和num發送至查詢區域的一個數據節點a。

(2)a收到查詢消息和num后，根據其維護的鄰居信息選取第1個網格內的簇頭節點C0，用于收集該簇內數據節點的感知數據。

定義1NA(m)為節點m的后繼子區域(借助網格描述)，NC(m)為NA(m)后繼子區域的簇頭節點，NA(m)中除了NC(m)其余為數據節點。后繼子區域需滿足如下約束：后繼子區域的所有節點均是節點m的鄰居節點，子區域內所有節點能夠互相通信。

(3)數據節點a將查詢消息發送至C0，由于無線廣播特性，網格內所有節點均能收到查詢消息。網格中所有節點都收到查詢信息后，按照路線行進方向排序數據節點，數據節點的聚集方式采用依次疊加的方法。如圖1所示第1個網格內，節點a將感知數據與num相加后的結果Da發送給節點b。Da到達節點b后，與感知數據Db相加，然后將相加后的結果發送給節點c，以此類推，直至將子區域內所有數據節點的聚集結果發送給簇頭節點。

(4)簇頭節點C0收集完子區域的感知數據后，將會計算下1個簇頭節點C1和子區域，將查詢消息發送至子區域NA(C0),將子區域NA(a)的聚集結果發送至NA(C0)中的第1個節點m(按照路線行進方向排序后)。節點m與NA(C0)查詢結果融合后，與步驟(3)類似，簇頭節點C1將收集NA(C0)區域內所有數據節點的感知數據。C1收集完NA(C0)區域內所有節點感知數據后，將會繼續計算下1個簇頭節點和子區域。

(5)按照步驟(3)繼續收集區域未遍歷節點的感知數據，直至遍歷完查詢區域內所有節點，獲得整個查詢區域的查詢結果。

(6)查詢區域內的最后1個簇頭節點Cn利用位置路由協議將查詢結果發送回Sink節點。

Figure 1 Execution procedure of the PCPDA algorithm圖1 PCPDA算法執行示意圖

3.2 算法設計

窗體查詢區域內的傳感器網絡表示為SN={C1,C2,…,Cn}，假設節點的通信半徑用R來表示。

(1)基于網格(子區域)查詢結果收集策略。

為了能夠遍歷整個查詢區域，采用劃分網格(子區域)的思想，將整個區域劃分成多個網格(子區域)，依靠網格的依次遞進，使得查詢消息發送至整個查詢區域中的所有節點，借此來收集部分區域的感知數據。由于無線通信的廣播特性，網格中的所有節點均能收到消息。采用按序聚集感知數據策略，將當前網格中所有的節點按照當前前進方向矢量排序。

(2)網格大小。

當查詢消息傳至當前網格的最后1個節點，需確定下1個網格時，約定下1個網格的所有節點需滿足在當前節點的通信范圍內。由于無線通信的廣播特性，網格中節點接收到查詢消息后，按照排序后的順序依次聚集節點的感知數據。

(3)簇頭的選取。

由算法執行過程可知，簇頭節點Ci會將已遍歷過節點的聚集結果和查詢消息發送給Ci+1，因此簇頭的選取是算法執行過程的關鍵一步。由算法執行的約束條件可知，NA(Ci)中所有數據節點需在Ci通信范圍內，所以NA(Ci)的數據節點均在Ci維護的鄰居信息中，將NA(Ci)中的數據節點根據路線行進方向進行排序，選取排序后的末尾節點作為Ci+1。

(4)如何處理空洞。

如圖2所示，查詢節點收集完網格EFGH中數據節點的感知數據后，需將查詢消息和部分查詢結果發送至下1個查詢節點。由于網格EFGH下方的區域GHKI不存在節點的鄰居節點，區域GHKI成為空洞區域，導致查詢處理過程中斷。為了避免該問題，利用位置路由協議繞過該空洞區域，即節點e以矩形區域IKLM的中心為目的位置(其中KM之間的距離為R)，利用位置路由協議將查詢消息和部分查詢結果發送至該矩形區域中的1個節點。圖2中，節點e通過f、g到達區域IMLK中的節點，然后從該節點開始繼續后續的查詢處理過程。若矩形區域IMLK中不存在節點或位置路由協議無法將查詢消息和部分查詢結果發送至區域IMLK中的節點，則采用上述方法類似的思想，以IMLK下方的區域LMNQ的中心為目的位置(其中LN之間的距離為R)，利用位置路由協議將消息發送至該區域中的1個節點。

Figure 2 Bypassing the void region圖2 繞過路由空洞

3.3 能耗分析

本節從理論上對PCPDA、SMART和PECDA進行能耗分析。為了表述方便，對下文要用到的符號及其含義進行說明，如表1所示。

Table 1 Meaning table of variables表1 基本符號及其含義

采用PCPDA收集查詢區域SRS中的所有節點的感知數據。整個查詢過程的能耗可分為2個部分：(1)查詢消息的發送，即子區域SRi中的簇頭節點SRCi將查詢消息廣播至子區域SRi+1內所有節點(其中i為1～n-1)，用Equery表示；(2)感知數據聚集階段的能耗，用Edata表示。

SMART與PECDA的能耗主要包括數據分片傳輸安全通道的建立、查詢消息的分發和感知數據聚集3階段。這里主要針對SMART和PECDA中查詢消息發送與數據的聚集過程與PCPDA進行對比分析。假設SMART與PECDA中葉子節點所占比例為p，同PCPDA用Equery表示查詢階段消耗的能量，Edata表示數據聚集階段消耗的能量。

為了便于分析，用E(PCPDA)、E(SMART)和E(PECDA)表示3種算法總的能耗，Equery(PCPDA)、Equery(SMART)和Equery(PECDA)分別表示3種算法查詢階段的能耗，Edata(PCPDA)、Edata(SMART)和Edata(PECDA)分別表示3種算法聚集階段的能耗。

定理1E(PCPDA)

證明

PCPDA中：

(1)

Dist(SRCi-1,n)≤R,?n∈Num(SRi),1≤i≤n

(2)

Dist(n,SRCi)≤R,?n∈Num(SRi),1≤i≤n

(3)

式(1)～式(3)為子區域的約束條件。

E(PCPDA)=Equery+Edata

(4)

其中，

Equery=Sq*E*n

(5)

(6)

SMART中：

E(SMART)=Equery+Edata

(7)

其中，

Equery=Sq*E*N

(8)

(9)

PECDA中：

E(PECDA)=Equery+Edata

(10)

其中，

Equery=Sq*E*N

(11)

(12)

由式(5)、式(8)、式(11)可推出：

Equery(PCPDA)

(13)

由式(6)、式(9)、式(12)可推出：

Edata(PCPDA)

(14)

由式(13)、式(14)可得結論。

□

3.4 隱私分析

文獻[4]給出了密鑰分配的2個重要性能：任意2個鄰居之間至少有1個相同密鑰的概率為Pconnect,第3方節點擁有相同密鑰的概率為Poverhear：

(15)

Poverhear=k/K

(16)

4 仿真分析

本節通過仿真對算法進行分析，在文獻[19]的仿真器上實現了PCPDA與現有算法里的SMART和PECDA，其中硬件環境為2.6 GHz CPU，8 GB內存，軟件環境為Ubuntu操作系統、eclipse開發環境。傳感器節點分別以均勻分布和非均勻分布的方式部署在矩形監視區域中。

仿真參數選擇如下：根據文獻[20]，無線通信發送和接收1 byte的能量消耗公式為：Et=α+γ*dm，Er=β,其中,α和β為捕獲通信電子消耗的能量，γ為功率放大器消耗的能量，m為路徑損耗指數，d為傳輸距離。采用文獻[21]中的參數：γ=10 pJ/bit/m2，α=45 nJ/bit，β=135 nJ/bit，m=2。其他參數如表2所示。

Table 2 Simulation parameters表2 仿真參數

4.1 時間延時

時間延時是性能評估的一個重要指標。基于KIPDA(K-Indistinguishable Privacy-preserving Data Aggregation)[22]，比較了現有算法和PCPDA的時鐘周期數。由圖3可知，現有算法的時間延時高于PCPDA的。因為SMART中需要對查詢區域內所有節點進行分片、混合和聚集，PECDA僅需對葉子節點進行分片、混合和聚集，相比SMART，PECDA一定程度上降低了時間開銷。PCPDA查詢過程中由于無需對節點感知數據分片后再聚集，縮短了查詢過程中的時間延時，提升了效率。

Figure 3 Influence of the number of network nodes on the time delay圖3 網絡節點數對時間延時的影響

4.2 通信開銷和能量消耗

Figure 4 Influence of the number of network nodes on communication overhead圖4 網絡節點數對通信開銷的影響

圖5和圖6分別展示了網絡節點密度、查詢區域大小條件下能量的損耗。

Figure 5 Influence of the number of network nodes on energy loss圖5 網絡節點數對能量損耗的影響

Figure 6 Influence of query region size on energy loss圖6 查詢區域大小對能量損耗的影響

可見，算法PCPDA的能耗小于SMART和PECDA的。主要差異來源于SMART和PECDA中需要建立安全通道，對節點感知數據進行分片分發。隨著查詢區域變大，查詢區域內的節點數變大，PCPDA、SMART、PECDA因分發查詢消息和聚集感知數據，因此3種算法的總能耗隨著查詢區域的增大而變大。圖7和圖8分別展示了感知數據大小、查詢消息大小對3種算法能耗的影響。由式(13)、式(14)可知，算法PCPDA在查詢階段、聚集階段的能耗皆小于SMART和PECDA的。由圖7和圖8可知，3種算法的能耗隨著查詢消息的增大而增大，隨著感知數據的增大而增大。

Figure 7 Influence of the sensing data size on energy loss圖7 感知數據大小對能耗的影響

Figure 8 Influence of the query message size on energy loss圖8 查詢消息大小對能量損耗的影響

另外，由于SMART和PECDA依賴預先構造好的拓撲樹，拓撲結構的變化對其能耗的影響比較大。由圖9可知，在不同的拓撲結構下，SMART和PECDA在能耗方面有著不同的表現，而PCPDA在不同拓撲下的能耗則相對穩定。

Figure 9 Influence of different network topologies on energy loss圖9 不同網絡拓撲對能量損耗的影響

5 結束語

現有傳感器網絡聚集查詢隱私保護算法通過數據加密來保護節點感知數據的隱私性，且全網絡中所有節點參與查詢處理。數據的加解密操作增大了節點計算能耗，且在很多情況下，用戶只對傳感器網絡中部分區域的聚集結果感興趣，此時如果還采用全網絡隱私保護聚集查詢方法，必然大大增加節點的資源開銷。針對現有算法的一些問題，本文提出一種抗竊聽攻擊的傳感器網絡空間范圍聚集查詢處理算法，該算法在未采用任何數據加密情況下，不僅完成了節點數據的聚集查詢，而且查詢過程中保證了感知數據的隱私性。由于聚集過程中無任何加解密操作，節省了節點的能量，加快了聚集效率。仿真結果和理論分析表明，PCPDA在能量損耗和隱私性保護方面均優于現有的一些算法。