基于分片的輕量級數(shù)據(jù)融合隱私保護算法

王 軍，徐彥惠+，李 莉

(1.沈陽化工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 沈陽 110142； 2.沈陽化工大學(xué) 遼寧省化工過程工業(yè)智能化技術(shù)重點實驗室，遼寧 沈陽 110142)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless networks，WSN)是由大量具有數(shù)據(jù)采集、數(shù)據(jù)處理、數(shù)據(jù)存儲和無線通信等功能的資源受限的微型傳感器節(jié)點以自組織和多跳路由方式構(gòu)成的信息傳輸網(wǎng)絡(luò)[1]。

數(shù)據(jù)融合技術(shù)是WSN的關(guān)鍵技術(shù)之一，該技術(shù)的意義在于其直接決定了網(wǎng)絡(luò)的生存周期[2]。通過數(shù)據(jù)融合，去除冗余信息，進而減小傳輸數(shù)據(jù)量，實現(xiàn)能量的節(jié)約，增加網(wǎng)絡(luò)生命周期，達到數(shù)據(jù)高效收集的目的[3]。

W.B.He，X.Liu等提出了CPDA(lightweight-cluster-based private data aggregation)算法和SMART(slice-mix-aggregate)算法[4]。CPDA計算開銷很大，而且SMART也很昂貴，通信開銷太大，并且對數(shù)據(jù)丟失很敏感[5]。

針對上述算法的不足本文提出了一種基于分片的輕量級數(shù)據(jù)融合隱私保護算法L-CPDA(a lightweight-cluster-based private data aggregation)。在分片前通過數(shù)據(jù)擾動技術(shù)提高數(shù)據(jù)安全性，根據(jù)簇內(nèi)節(jié)點數(shù)目的不同對數(shù)據(jù)進行動態(tài)分片，同時對網(wǎng)絡(luò)中的孤立節(jié)點進行數(shù)據(jù)擾動。這樣能夠降低計算與通信消耗。

1 相關(guān)工作

He等分別擴展了PDA算法，提出了兩種能夠兼顧隱私保護和完整性驗證的數(shù)據(jù)融合方案iPDA和iCPDA[6]，但是在能驗證完整性的同時，計算復(fù)雜度大大增加。苘大鵬等提出了E-CPDA(energy-efficient cluster-based privacy data aggregation)[7]，由簇頭選取協(xié)作節(jié)點，協(xié)作節(jié)點起到輔助完成數(shù)據(jù)融合的作用,在計算量、通信消耗方面都優(yōu)于CPDA，E-CPDA是以4個節(jié)點成簇舉例，但當(dāng)簇內(nèi)節(jié)點數(shù)量大于4個時，沒有給出一般性的計算方法。宋蕾等針對節(jié)點能耗和精度的問題提出一種基于博弈論的數(shù)據(jù)融合算法DFABGT(data fusion algorithm based on game theory)[8]。簇內(nèi)節(jié)點以收益和能耗為效益函數(shù)的輸入?yún)?shù)進行博弈。本算法能有效提高精確度，降低節(jié)點能耗，但該算法的數(shù)據(jù)融合是基于貝葉斯理論[9]的，計算相對復(fù)雜，計算量較大。

綜上所述，L-CPDA算法是針對現(xiàn)有算法普遍存在計算量大和通信量大的問題提出的一種輕量級數(shù)據(jù)融合隱私保護算法，采用動態(tài)分片的方式，根據(jù)簇內(nèi)節(jié)點的數(shù)量對節(jié)點進行動態(tài)分片，簇內(nèi)只有成員節(jié)點進行數(shù)據(jù)分片操作，簇頭節(jié)點只需接收成員節(jié)點發(fā)送的混合分片結(jié)果，不進行分片操作，同時，L-CPDA為了算法的安全性，利用隨機數(shù)對節(jié)點的原始數(shù)據(jù)進行擾動提高數(shù)據(jù)的隱私性。

2 CPDA算法描述

CPDA算法是由He等提出的經(jīng)典保護數(shù)據(jù)隱私的機制。實現(xiàn)CPDA方案需要進行3個步驟：簇的形成、簇內(nèi)串通、簇頭融合。CPDA算法運用噪聲干擾來實現(xiàn)對數(shù)據(jù)的保護。在簇內(nèi)融合時，CPDA算法將節(jié)點自身采集到的數(shù)據(jù)與自身產(chǎn)生的隨機數(shù)和節(jié)點之間的共享種子進行噪聲運算，得到節(jié)點的擾動數(shù)據(jù)，再將得到的擾動數(shù)據(jù)與簇內(nèi)其它節(jié)點計算所得的擾動數(shù)據(jù)進行串通交換。簇內(nèi)各節(jié)點將擾動數(shù)據(jù)相加得到一個中間值，各個節(jié)點將該值發(fā)送至簇頭，最后由簇頭節(jié)點利用多項式的性質(zhì)計算出最終的融合結(jié)果。

CPDA算法雖然能在一定程度上保護采集數(shù)的隱私性，同時也能基本保證數(shù)據(jù)的精確性，但是CPDA算法仍然有一定的缺陷，CPDA算法在通信的過程中，簇內(nèi)每個節(jié)點最少要進行二次冪多項式運算，假設(shè)簇的規(guī)模是m，簇中每個節(jié)點都需要進行m-1次二項式運算，每個簇內(nèi)節(jié)點要進行m-1次解密操作和m-1次加密操作，并最終需要求解m階的逆矩陣得到融合結(jié)果，m值越大，計算就越復(fù)雜。簇內(nèi)任意兩個節(jié)點間都需要進行數(shù)據(jù)交換，因此通信開銷也會增大。所以大規(guī)模的網(wǎng)絡(luò)不適合采用CPDA算法，本文針對CPDA算法的缺陷，以保護數(shù)據(jù)隱私為前提，提出了L-CPDA算法，新提出算法在計算量和數(shù)據(jù)通信量上都比CPDA算法要更有優(yōu)勢，在隱私保護度和計算量上得到平衡。

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

本文用連通圖G(V，E) 表示無線傳感器網(wǎng)絡(luò)，其中v(v∈V) 表示網(wǎng)絡(luò)中的傳感器節(jié)點，e(e∈E) 表示無線傳感器網(wǎng)絡(luò)中的無線鏈路，將無線傳感器網(wǎng)絡(luò)中的節(jié)點個數(shù)表示為N=|V|。

4 L-CPDA算法描述

4.1 加密方法

無線傳感器網(wǎng)絡(luò)的通信鏈路通常是不安全的，為防止傳輸?shù)臄?shù)據(jù)被竊聽，保護數(shù)據(jù)的隱私，對數(shù)據(jù)進行加密是十分必要的，加密是保護數(shù)據(jù)的重要手段之一，L-CPDA與CPDA一樣，采用隨機密鑰分配機制[10]。在預(yù)分配階段，首先無線傳感器網(wǎng)絡(luò)生成有含K個密鑰的秘鑰池，節(jié)點從秘鑰池中隨機選取k個密鑰，若存在兩個節(jié)點含有相同的密鑰，記為keys，那么這兩個節(jié)點之間就建立起了一條安全鏈路，密鑰分配結(jié)束后，任意兩個WSN節(jié)點能夠共享同一個密鑰的概率為

Pconncet=1-((K-k!)2)/((K-2k)!K!)

(1)

如果兩個節(jié)點間沒有共享密鑰，則可以采取多跳的方式建立一條安全鏈路來實現(xiàn)節(jié)點間加密解密的過程。偷聽者同樣也可以從密鑰池中隨機選取k個密鑰，如果這k個密鑰中含有keys，偷聽者就可以對節(jié)點監(jiān)聽，假設(shè)加密信息被竊聽的概率為Poverhear，因此Poverhear=k/K， 假設(shè)密鑰池中有K=10 000個密鑰，每個節(jié)點選取200個密鑰，任意一對節(jié)點擁有相同密鑰的概率為Pconnect=98.3%，那么沒有相同密鑰的概率為1.5%，如果一個節(jié)點對沒有相同的密鑰，則可以使用以上文所述的路徑密鑰建立方式來形成節(jié)點間共享密鑰。如果兩個節(jié)點選擇了一個共享密鑰，那么其它的節(jié)點也擁有這個密鑰的可能性很低，通常是一個很小的數(shù)，即為Poverhear=0.2%。

4.2 算法步驟介紹

L-CPDA算法分為5個步驟，分別是：簇的形成、簇內(nèi)節(jié)點分片、簇內(nèi)節(jié)點串通、簇內(nèi)節(jié)點混合、簇間數(shù)據(jù)融合，為了表述方便，所用到的符號說明見表1。

表1 符號說明

4.2.1 L-CPDA成簇階段

L-CPDA采取和CPDA一樣的成簇方式，簇的形成過程如圖1所示。在圖1(a)中，網(wǎng)絡(luò)中的傳感器節(jié)點布置好之后，查詢服務(wù)器向鄰居節(jié)點發(fā)送HELLOW消息，接受到HELLOW消息的節(jié)點以pc的概率決定自己是否成為簇頭，此處pc是一個預(yù)設(shè)的數(shù)，如果節(jié)點成為簇頭，它將像查詢服務(wù)器一樣，繼續(xù)向其它鄰居節(jié)點發(fā)送HELLOW消息，否則，在等待特定的時間后，將會從鄰居節(jié)點獲得HELLOW消息，選擇加入一個簇，如圖1(b)所示。存在這樣的情況：如果節(jié)點分布密集，其它節(jié)點同時收到不同簇頭節(jié)點發(fā)送的HELLOW消息，那么它將通過發(fā)送JOIN消息隨機選擇其中一個作為簇頭。如圖1(c)所示，節(jié)點6同時收到節(jié)點3和節(jié)點8的消息，從中隨機選擇一個簇頭加入。以此類推，重復(fù)這個過程，經(jīng)過一段時間就形成了若干個簇群，這些簇最終就形成了一棵融合樹。CPDA中用mc表示一個最小的簇(mc=3)。對于不滿足條件，無法成簇的節(jié)點，在圖1(d)中節(jié)點12所在的簇規(guī)模m

圖1 簇的形成

4.2.2 簇內(nèi)節(jié)點分片

在簇的形成過程中，利用一個非在線的裝置，使每個節(jié)點產(chǎn)生一個隨機數(shù)ai，這個隨機數(shù)只有節(jié)點本身與查詢服務(wù)器知道，對其它節(jié)點是透明的，利用隨機數(shù)對節(jié)點采集到的原始數(shù)據(jù)進行數(shù)據(jù)擾動，可提高數(shù)據(jù)的隱私性。

將簇建立好之后，每個簇內(nèi)包含一個簇頭節(jié)點和若干個成員節(jié)點，當(dāng)簇的規(guī)模m滿足2n

(2)

將加密的分片數(shù)據(jù)記為Enc(ki,j，fi,j)， 對于前文提到的簇的大小m<3，被劃分到節(jié)點集W中的節(jié)點，也只需進行數(shù)據(jù)擾動操作，不進行數(shù)據(jù)分片操作。在圖2中以節(jié)點0和節(jié)點3為簇頭的簇的規(guī)模滿足21

圖2顯示根據(jù)簇的規(guī)模不同，簇內(nèi)節(jié)點分片的情況。

圖2 簇內(nèi)節(jié)點分片

4.2.3 簇內(nèi)節(jié)點串通

簇內(nèi)節(jié)點串通分3個步驟：首先，簇內(nèi)的簇頭和每個成員需要等待一段時間，保證接收到所有的分片。之后，簇內(nèi)成員節(jié)點或簇頭利用和發(fā)送分片數(shù)據(jù)的節(jié)點之間的共享密鑰將收到的數(shù)據(jù)解密，例如節(jié)點i解密來自節(jié)點j的分片數(shù)據(jù)可以表示為Dec(ki,j，fi,j)。 簇內(nèi)的節(jié)點將自己所留的一片分片數(shù)據(jù)和解密后的所有分片數(shù)據(jù)求和，由于簇頭節(jié)點未進行分片，只需將自身的數(shù)據(jù)和解密后的分片數(shù)據(jù)求和。最終簇內(nèi)成員節(jié)點和簇頭都得到了一個新的數(shù)據(jù)混雜結(jié)果，用di表示，由于節(jié)點集W中的節(jié)點沒有足夠的節(jié)點，只能進行數(shù)據(jù)擾動運算而不進行分片操作，這樣會減少通信開銷和數(shù)據(jù)的傳輸量，同時節(jié)點也具有一定的隱私保護能力。簇內(nèi)節(jié)點串通情況如圖3所示。

圖3 簇內(nèi)節(jié)點串通

4.2.4 簇內(nèi)數(shù)據(jù)混合

在數(shù)據(jù)混合階段，為了確保所有的混合信息都能被收到，節(jié)點i在收到其它節(jié)點發(fā)送的混合分片數(shù)據(jù)以后，會等待特定的時間，確保節(jié)點i能接收到所有的分片數(shù)據(jù)，簇內(nèi)的各個成員節(jié)點將自己計算的混合數(shù)據(jù)融合結(jié)果di發(fā)送至簇頭，簇內(nèi)成員節(jié)點將數(shù)據(jù)上傳完畢之后，簇頭節(jié)點將收到的混合數(shù)據(jù)與自身所計算的混合數(shù)據(jù)進行相加數(shù)據(jù)融合，得到這個簇的最終混合數(shù)據(jù)Ri。

圖4描述了簇內(nèi)混合階段示例情況，節(jié)點0的混合結(jié)果為R0=d0+d1+d2節(jié)點3的混合結(jié)果為R3=d6+d4+d5+d3， 節(jié)點8的混合結(jié)果為R8=d7+d9+d10+d11， 節(jié)點12的混合結(jié)果即數(shù)據(jù)擾動的結(jié)果R12=d12。

圖4 簇內(nèi)數(shù)據(jù)混合

4.2.5 簇間數(shù)據(jù)融合

在這個階段，所有節(jié)點都推算出了混合結(jié)果，融合樹的建立參照TAG算法進行構(gòu)建[11]，采用TAG算法對每個簇頭建立融合樹，簇頭將混合數(shù)據(jù)Ri沿著融合樹的方向逐層向上傳遞，一層層向上融合，最后，QS節(jié)點將在得到的融合中去除掉每個節(jié)點產(chǎn)生的隨機數(shù)信息，也就是最終真正的融合結(jié)果。如圖4所示，節(jié)點3、節(jié)點8和節(jié)點12將混合結(jié)果R3、R8、R12發(fā)送給查詢服務(wù)器(節(jié)點0)，然后節(jié)點0計算出融合值R3+R8+R12， 最后節(jié)點0通過將節(jié)點的隨機數(shù)去除可以算出最終融合的真實結(jié)果為

(3)

簇間數(shù)據(jù)融合過程如圖5所示。

圖5 簇間數(shù)據(jù)融合

5 性能分析

本文主要從計算量、隱私保護性和數(shù)據(jù)通信量這3個方面對L-CPDA進行分析，并和CPDA進行比較。

5.1 計算量分析

假設(shè)一個簇中含有ABCD這4個節(jié)點，用DA表示節(jié)點進行了一次算數(shù)運算(加、減、乘、除)，用DB表示節(jié)點進行了一次加密運算，用DC表示節(jié)點進行了一次解密運算。以節(jié)點A為例，在CPDA算法中，節(jié)點進行簇內(nèi)融合時需要執(zhí)行以下任務(wù)：節(jié)點在采集到原始數(shù)據(jù)后，節(jié)點ABCD分別用自身產(chǎn)生的隨機數(shù)和公開的種子值進行數(shù)據(jù)擾動，計算方法如下

比如，教師可以組織學(xué)生參與校內(nèi)組織的“××演講大賽”，結(jié)合學(xué)生的獨特優(yōu)勢，讓學(xué)生相互合作，不斷溝通交流，互相討論稿件的創(chuàng)作以及應(yīng)該用什么樣的語態(tài)來進行演講，從而讓學(xué)生在此過程中了解團隊合作的重要性，并且明確團隊合作中應(yīng)該進行適當(dāng)?shù)姆止ぃ谝欢ǔ潭壬线€能夠提高學(xué)生的人際交往能力。正所謂“世界上沒有相同的兩片樹葉”，每個學(xué)生有其獨特的觀點，這就需要學(xué)生學(xué)會如何與他人溝通，吸收他人的意見。教師組織的這一個活動，能夠有效提高學(xué)生的溝通能力、人際交往能力，并且培養(yǎng)學(xué)生的合作意識。最重要的是能夠促使學(xué)生在學(xué)校就明確團結(jié)的重要性，為學(xué)生將來就業(yè)奠定基礎(chǔ)。

QCPDA-midnode=39DA+3DB+3DC

(4)

對于簇頭節(jié)點，在進行簇內(nèi)其它節(jié)點相同的操作之外，還要將融合運算考慮進去(實際上是3個加法運算)，所以簇頭的計算量表示為

QCPDA-cnod=42DA+3DB+3DC

(5)

在L-CPDA算法中，假設(shè)采集到的數(shù)據(jù)是20，產(chǎn)生的隨機數(shù)是4，那么經(jīng)過數(shù)據(jù)擾動后得到的綜合數(shù)據(jù)是20+4=24，進行了一次算數(shù)運算，通過計算：24/4=6,24/6=4,24-6-4=14，可以這個數(shù)據(jù)將被分為4、6、14這3個分片，這個過程進行了4次算數(shù)運算，之后簇內(nèi)成員節(jié)點將其中的兩個分片數(shù)據(jù)進行加密，此處有2個加密運算，因為假設(shè)簇的大小為4，簇頭不進行分片，所以它要接收來自簇頭以外的兩個成員節(jié)點的分片數(shù)據(jù)，收到后對它們進行解密與自己剩余的那片數(shù)據(jù)相加。所以在L-CPDA算法中簇內(nèi)每個節(jié)點的計算量為

QL-CPDA-midnode=7DA+2DB+2DC

(6)

對于L-CPDA中的簇頭節(jié)點，簇頭節(jié)點和簇內(nèi)成員節(jié)點一樣，首先進行數(shù)據(jù)擾動，執(zhí)行了一次算數(shù)運算。不進行分片操作，接下來收到來自3個節(jié)點的兩片加密的分片數(shù)據(jù)，對這3個數(shù)據(jù)進行3次解密，再與自身的綜合數(shù)據(jù)進行相加運算，最后，簇頭節(jié)點將3個節(jié)點發(fā)送的組合數(shù)據(jù)進行融合(實質(zhì)是進行3次加法運算)，所以在L-CPDA算法中簇內(nèi)每個節(jié)點的計算量為

QL-CPDA-cnod=7DA+3DC

(7)

可以看出，L-CPDA較CPDA無論在簇內(nèi)通信量，還是在簇頭計算量上都有較大的優(yōu)勢。

5.2 數(shù)據(jù)通信量分析

(8)

而L-CPDA算法使用動態(tài)分片的方式，根據(jù)簇的規(guī)模大小決定節(jié)點的分片數(shù)，當(dāng)簇的規(guī)模滿足2n

NL-CPDA=(m-1)·(log2m)

(9)

兩種方案簇內(nèi)傳輸數(shù)據(jù)包的個數(shù)對比如圖6所示。

圖6 簇內(nèi)通信階段的數(shù)據(jù)包個數(shù)

從圖6中我們可以看出，CPDA算法簇內(nèi)串通數(shù)據(jù)量增長較快，呈現(xiàn)冪次性增長，簇的規(guī)模越大，增長的也越快。而與CPDA方案相比，L-CPDA算法簇內(nèi)串通階段數(shù)據(jù)量增長較慢，增長幅度較小，類似線性增長，所以，在簇內(nèi)數(shù)據(jù)通信量方面，L-CPDA比CPDA有較好的優(yōu)勢。

5.3 隱私保護性分析

隱私性代表了節(jié)點在通信過程中被破解的概率。在CPDA算法中，若一個簇的大小為m，簇內(nèi)的每個節(jié)點都需要將自己采集的數(shù)據(jù)與種子值進行多項式運算，再加密發(fā)送給簇內(nèi)m-1個節(jié)點，簇內(nèi)其它節(jié)點只有知道了這m-1個密鑰，這個節(jié)點的數(shù)據(jù)才會被破解。因此CPDA算法中一個節(jié)點被破解的概率為

(10)

這里的mmax表示簇的規(guī)模的最大值，mc表示簇的規(guī)模的最小值，q為竊聽率，P(m=k) 表示簇的規(guī)模為k時的概率。

在L-CPDA算法中，定義節(jié)點發(fā)送數(shù)據(jù)為出度，節(jié)點接收數(shù)據(jù)為入度，在本算法中攻擊者只有獲得該節(jié)點產(chǎn)生的隨機值和J-1個出度以及所有的入度，才能得到該節(jié)點得數(shù)據(jù)，因此可以得到

(11)

J是分片數(shù)，其中mmax表示簇的最大規(guī)模，mc表示簇的最小規(guī)模，P(in-degree=d)表示入度為d的概率，dmax表示簇內(nèi)節(jié)點的最大的入度。兩種算法的隱私度比較如圖7所示。

圖7 L-CPDA與CPDA的隱私度比較

從圖7中可以看出，L-CPDA的隱私保護性要比CPDA略低，這是由于在L-CPDA中采取了動態(tài)分片的方式，隨著簇的規(guī)模變化，分片數(shù)目也會發(fā)生變化，在通信過程中，節(jié)點的串通次數(shù)比CPDA要小，需要破解的通信鏈路變少，所以在pc=0.3的情況下，數(shù)據(jù)泄露率要高于CPDA，但是L-CPDA隱私數(shù)據(jù)被破解的概率低于0.02%，足夠保護數(shù)據(jù)的隱私。

6 結(jié)束語

為了降低無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合過程中的計算和通信消耗，本文提出了一種輕量級的基于動態(tài)分片的數(shù)據(jù)融合隱私保護算法，針對CPDA算法通信量大、計算量大的缺點進行改進。從性能分析可以看出，雖然L-CPDA算法的隱私保護性略低于CPDA，但是數(shù)據(jù)被竊聽的概率在可接受的范圍之內(nèi)；L-CPDA比CPDA通信量小，計算量低，從而能夠減少數(shù)據(jù)通信的通信量，延長無線傳感器網(wǎng)絡(luò)的生命周期，有更強的實用性。此外，本文未考慮數(shù)據(jù)完整性，這將是下一步要進行的工作。