一種支持數(shù)據(jù)恢復(fù)的安全聚集算法

石魯生，朱慧博

(1．宿遷學(xué)院計算機科學(xué)系，江蘇宿遷　223800；2．南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇南京　210016)

0　引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)是由隨機分布的集成了傳感器、數(shù)據(jù)處理單元和通信單元的微小節(jié)點通過自組織方式構(gòu)成的智能系統(tǒng)[1]。數(shù)據(jù)收集是無線傳感器網(wǎng)絡(luò)投入實際應(yīng)用后的主要功能，由于資源受限的特征突出，各種收集方法一直將如何延長網(wǎng)絡(luò)生命周期、降低能耗作為重要的設(shè)計目標(biāo)。

收集數(shù)據(jù)時，數(shù)據(jù)聚集是WSN一項重要的節(jié)能技術(shù)[2]。由于傳統(tǒng)的數(shù)據(jù)聚集方法如TAG[3]等在降低能耗的同時沒有解決聚集過程中的安全問題，不具備實用價值，因此各種安全聚集算法應(yīng)運而生。例如DADPP[4]通過向原始數(shù)據(jù)中添加隨機種子和私有隨機數(shù)進行擾動，達到隱私保護目的，ESPART[5]通過對原始數(shù)據(jù)的切片和加密傳輸來保護數(shù)據(jù)隱私，SIES[6]算法使用同態(tài)加密函數(shù)保護數(shù)據(jù)隱私，并可驗證聚集結(jié)果的完整性，iCPDA[7]算法在隱私保護和完整性驗證中分別使用了安全多方計算方法和同行監(jiān)督機制，但安全的聚集算法帶來了新的問題，一是原本降低了的通信開銷大增；二是聚集類型受限嚴重，很多算法僅支持SUM一種。

可恢復(fù)數(shù)據(jù)的安全數(shù)據(jù)聚集算法RSDA(recoverable security data aggregation)，在保護數(shù)據(jù)隱私以及提供有效的數(shù)據(jù)完整性和真實性驗證基礎(chǔ)上，特別設(shè)計了數(shù)據(jù)恢復(fù)機制，從而使聚集節(jié)點在得到聚集結(jié)果的同時，能夠精確、有效地恢復(fù)聚集前的原始數(shù)據(jù)。這些原始數(shù)據(jù)的獲得讓其他后續(xù)聚集操作在執(zhí)行時，類型不再受限，同時也降低了網(wǎng)絡(luò)總的能耗開銷。

1　系統(tǒng)模型

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

由于層次化(分簇)無線傳感器網(wǎng)絡(luò)具有更好的擴展性和能量有效性[8]，RSDA算法中基于分簇的兩層網(wǎng)絡(luò)結(jié)構(gòu)模型如下：

(1)一個基站(Base Station，BS)，它擁有強大的計算和通信能力，足夠大的存儲空間，穩(wěn)定的電力供應(yīng)，并采取了嚴密的防護措施。

(2)簇頭節(jié)點(H-Sensors，HS)，負責(zé)收集簇內(nèi)節(jié)點采集到的數(shù)據(jù)，然后聚集轉(zhuǎn)發(fā)給基站。令網(wǎng)絡(luò)中簇的數(shù)目為，簇頭節(jié)點集合為。

(3)簇成員節(jié)點(L-Sensors，LS)，負責(zé)采集監(jiān)測區(qū)域內(nèi)的感知數(shù)據(jù)，再發(fā)送至簇頭。簇頭為的簇成員節(jié)點表示為，其原始感知數(shù)據(jù)用表示。

1．2攻擊模型

鑒于BS不易被捕獲，假設(shè)其是安全可信的，則將攻擊依照嚴重程度分為以下3種：

(1)竊聽無線通信。攻擊者未捕獲任何節(jié)點，但通過竊聽網(wǎng)絡(luò)中的無線通信獲取或偽造數(shù)據(jù)。

(2)捕獲LS。攻擊者可以獲取或篡改被捕獲LS的感知數(shù)據(jù)，當(dāng)然亦可攻擊其轉(zhuǎn)發(fā)的感知數(shù)據(jù)。

(3)捕獲HS。攻擊者可以獲取被捕獲HS所在簇內(nèi)所有LS的感知數(shù)據(jù)，并可篡改HS上報給基站的中間聚集結(jié)果。

1．3密鑰預(yù)分配

異構(gòu)無線傳感器網(wǎng)絡(luò)部署前，BS首先根據(jù)EC-EG[9]方案生成密鑰對(PBS，RBS)再根據(jù)Boneh[10]等的方案為Hi生成密鑰對(PHi，RHi)。其中PBS為所有BS和HS共享的公鑰，PHi是BS與Hi共享的公鑰，RBS和RHi則分別為BS和Hi的私鑰。

BS預(yù)先裝載自身的密鑰對(PBS，RBS)和每個Hi的公鑰PHi。Hi除裝載自身的密鑰對(PHi，RHi)外，還將裝載PBS和一個用于驗證簽名的哈希函數(shù)H()。

待網(wǎng)絡(luò)部署完畢，各分簇形成后，為保護每個簇成員Lij和其簇頭Hi之間的通信，同樣由基站為它們生成一個密鑰對P(Lij，RLij)。

2　可恢復(fù)數(shù)據(jù)的安全聚集算法

RSDA算法由三部分組成：簇內(nèi)數(shù)據(jù)收集和聚集；簇頭加密和簽名傳輸；基站聚集和安全驗證。

2．1簇內(nèi)數(shù)據(jù)收集和聚集

(1)Lij發(fā)送加密的dij和簽名sij給對應(yīng)的Hi；

(2)Hi接收到加密信息后，利用Lij的簽名sij驗證dij的真實性；

(3)在一定時間周期內(nèi)，Hi收集簇內(nèi)所有dij，執(zhí)行簇內(nèi)聚集，并將聚集結(jié)果di作為自身數(shù)據(jù)。

2．2簇頭加密和簽名傳輸

(1)加密簇頭Hi的di∶mi=di‖0t，其中‖為簡單連接，0t為t個0組成的二進制數(shù)，l為傳輸信息中有效感知數(shù)據(jù)的bit位數(shù)，t=l×(i-1)。

(2)計算Hi的密文：ci=(ri，ai)=(ki×G，Mi+ki×Y)，其中ki為[1，Z]內(nèi)的隨機數(shù)，Mi=map(mi)=mi×G，map()為一個將值m映射為橢圓曲線點M的函數(shù)，滿足加法同態(tài)性質(zhì)，Z，G，Y∈PBS。

(3)計算Hi的簽名：si=RHi×H(di)，其中H()為Hi預(yù)裝的哈希函數(shù)。

(4)Hi將數(shù)據(jù)對(ci，si)向基站發(fā)送。

2．3基站聚集和安全驗證

(1)并非所有簇頭的聚集結(jié)果都一跳直接傳輸至基站，當(dāng)一個簇頭接收到其他一個或多個簇頭的聚集結(jié)果時，它將把接收到的所有密文和簽名與對應(yīng)的自身密文和簽名求和，得到新的密文、簽名數(shù)據(jù)對，再向基站發(fā)送。在基站聚集后將得到最終結(jié)果(C，S)，即

(3)從M′獲得m′∶m′=rmap(M′)=m1+m2+…+mn，其中rmap()為map()的反函數(shù)。

(4)恢復(fù)di：利用解密函數(shù)

Decode(m′，n，l)∶di=m′[(i-1)×l，i×l-1]

恢復(fù)并獲取di。其中di為二進制數(shù)m′的第(i-1)×l位至i×l-1位上的數(shù)字所構(gòu)成的二進制數(shù)，i=1，2，…，n。

2．4數(shù)據(jù)恢復(fù)示例

一個基于分簇的兩層無線傳感器網(wǎng)絡(luò)如圖1所示，其中BS為基站，H1、H2、H3和H4分別為4個簇頭，每個簇包含數(shù)量不等的LS。如H2所在簇，共有L21L22、L23、L24和L255個，其他簇類似。

假設(shè)BS發(fā)出一個AVERAGE請求，啟動數(shù)據(jù)聚集。令H2所在簇內(nèi)5個LS的感知數(shù)據(jù)d21=5、d22=6、d23=4、d24=3、d25=2。H2收集到這些加密數(shù)據(jù)后，執(zhí)行簇內(nèi)AVERAGE聚集，得d2=4。其他簇類似可得d1=5、d3=2和d4=7。

l=3可滿足d1、d2、d3和d4有效數(shù)據(jù)的傳輸需求，則H2加密d2得：m2=d2‖03=(100)2‖(000)2=(100000)2，再計算密文和簽名對(c2，s2)發(fā)往。其他簇同理可得m1=(101)2、m3=(010000000)2、m4=(111000000000)2。

BS聚集所有HS的密文和簽名后，得到(C，S)，解密C可得M′=M1+M2+M3+M4，再利用rmap函數(shù)得m′=m1+m2+m3+m4=(111010100101)2，則可恢復(fù)d1、d2、d3和d4：

d1=m′[(1-1)×3，1×3-1]=(111010100101)2[0，2]=(101)2=5

d2=m′[(2-1)×3，2×3-1]=(111010100101)2[3，5]=(100)2=4

d3=m′[(3-1)×3，3×3-1]=(111010100101)2[6，8]=(010)2=2

d4=m′[(4-1)×3，4×3-1]=(111010100101)2[9，11]=(111)2=7

3　主要性能分析與仿真

3．1安全性

根據(jù)2．2節(jié)攻擊模型，分析RSDA算法的安全性。

(1)無線通信遭竊聽。此時算法的安全性能夠得到保障。因簇內(nèi)或簇間的通信都進行了加密，只竊聽無線通信，攻擊者無法破解。此外由于算法要求所有傳輸信息必須具備相應(yīng)的簽名，而攻擊者沒有密鑰無法偽造簽名，因而不可能在通信鏈路中篡改信息或注入虛假信息。

(2)LS被捕獲。如果攻擊者將被捕獲LS偽裝成正常節(jié)點或發(fā)送較為合理的偽裝數(shù)據(jù)參與聚集，目前算法都無法檢測此類攻擊，不過這種攻擊危害性很小。在RSDA算法中，除被捕獲LS外，攻擊者無法假冒其他節(jié)點的信息，也不能篡改被捕獲節(jié)點轉(zhuǎn)發(fā)的信息，其原因是無法偽造相應(yīng)的簽名。

(3)HS被捕獲。如果攻擊者捕獲了HS，情況將比較嚴重。而RSDA算法中使用了橢圓曲線加密技術(shù)，簇內(nèi)聚集時，沒有關(guān)于橢圓曲線點的加法函數(shù)，聚集無法完成，所以對橢圓曲線構(gòu)造方法一無所知的攻擊者，將無法完成任何未經(jīng)授權(quán)的聚集。

此外，在應(yīng)對共謀攻擊方面，由于采用了共享密鑰以及簽名機制，即使在網(wǎng)絡(luò)節(jié)點平均密度較低時，RSDA算法仍然較容易發(fā)現(xiàn)共謀攻擊，而且節(jié)點密度越大，發(fā)現(xiàn)共謀攻擊的能力越強。假設(shè)網(wǎng)絡(luò)中的節(jié)點均勻分布，當(dāng)節(jié)點通信半徑R=50 m，平均節(jié)點密度取不同值時，RSDA算法與iCPDA算法無法檢測出共謀攻擊的概率[7]如圖2所示。

圖2　RSDA算法與iCPDA算法應(yīng)對共謀攻擊的能力

通過以上分析可以看出，在各種攻擊面前，算法表現(xiàn)出了非常好的安全性能。特別值得指出的是，與iCPDA算法只能驗證聚集結(jié)果的完整性不同，RSDA算法通過簽名機制可以驗證所有原始數(shù)據(jù)的真實性和完整性，這為數(shù)據(jù)恢復(fù)后其他操作的進行提供了可靠的保障。

3．2數(shù)據(jù)恢復(fù)

2．4節(jié)的示例表明，基站在獲得最終結(jié)果的同時，可以恢復(fù)所有簇頭的聚集結(jié)果。因此在一些精度要求不高的應(yīng)用環(huán)境中，許多后續(xù)操作可以直接在基站執(zhí)行。因為同一簇內(nèi)的地理位置相近，所采集數(shù)據(jù)在數(shù)值上相似甚至重復(fù)的情況非常普遍，如令各簇的聚集結(jié)果如平均值作為本簇值的代表，基站可輕松獲得全部感知數(shù)據(jù)近似的最值或總和。

在精度要求較高的場合，可以借助HS的幫助完成各種后續(xù)操作。這是由于在簇內(nèi)聚集過程中，HS同樣可以還原簇內(nèi)各LS的原始數(shù)據(jù)，并進行驗證，因此基站只要命令每個HS節(jié)點執(zhí)行指定聚集函數(shù)即可。

數(shù)據(jù)恢復(fù)功能完全突破了以往各種安全聚集算法對聚集類型的限制，同時也節(jié)省了執(zhí)行后續(xù)聚集工作的計算和通信開銷，進而從總體上降低了網(wǎng)絡(luò)中的能量消耗，延長了網(wǎng)絡(luò)壽命。

3．3查詢周期

通過最終聚集結(jié)果的準(zhǔn)確性可以衡量算法查詢周期的長短，即時間效率。記AR為基站聚集結(jié)果與由真實數(shù)據(jù)所得聚集結(jié)果的比值，理想情況下，AR=1。在現(xiàn)實環(huán)境中，如果所有數(shù)據(jù)的收集、傳輸、加密和聚集工作都能在指定查詢周期內(nèi)順利完成，則AR值應(yīng)接近或達到1，但因在指定查詢周期內(nèi)一些數(shù)據(jù)的處理工作沒完成，必導(dǎo)致準(zhǔn)確性降低，且查詢周期越短，準(zhǔn)確性越差。而較長的查詢周期可以減少因無線信道內(nèi)的碰撞而造成的數(shù)據(jù)丟失，進而提高準(zhǔn)確性。因此，如果某時間點之后，算法的AR值一直穩(wěn)定在1附近，則該時間點就是算法近似的最小查詢周期。

利用TOSSIM仿真環(huán)境，將500個傳感器節(jié)點隨機部署在一個指定的區(qū)域內(nèi)，分別模擬執(zhí)行TAG、iCPDA(取0.1，0.2，0.3)和RSDA算法(n取50，100，150)各50次，計算平均值，得查詢周期和通信開銷的結(jié)果分別如圖3和圖4所示。其中pc為iCPDA算法中節(jié)點成為簇頭的概率，n為RSDA算法中簇頭的個數(shù)。當(dāng)pc分別取0.1、0.2和0.3時，RSDA算法中簇頭個數(shù)n分別為50、100和150。仿真中假定簇頭擁有遠高于一般簇成員的計算和存儲能力。

圖3　TAG、iCPDA和RSDA算法的查詢周期

如圖3，對RSDA算法，在n=150時，查詢周期大約為20 s，基本與不帶隱私保護和完整性驗證功能的TAG算法相當(dāng)，這是因為此時網(wǎng)內(nèi)HS數(shù)量較多，每個簇的成員較少，借助簇頭強大的計算能力，簇內(nèi)數(shù)據(jù)收集、加密、聚集等工作能在較短時間內(nèi)完成，從而縮短了整個網(wǎng)絡(luò)的查詢周期。當(dāng)n=100和50時，RSDA算法的查詢周期分別增大至和附近，說明隨著數(shù)量的減少，簇內(nèi)數(shù)據(jù)收集和處理的工作量增大，延長了查詢周期。iCPDA和RSDA算法的查詢周期分別隨pc和n值的增大而減小，趨勢相同，但對應(yīng)的查詢周期RSDA算法更短，且優(yōu)勢明顯。

3．4通信開銷

由于無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)通信的能量消耗遠大于計算，因此可以用通信開銷來衡量整個網(wǎng)絡(luò)的能耗。

圖4　TAG、iCPDA和RSDA算法的通信開銷

如圖4所示，3種算法的通信開銷都與查詢周期關(guān)系不大，其中功能最簡單的TAG算法通信開銷最低。iCPDA與RSDA算法的通信開銷分別隨著和值的增大而增大，因為或值的增大意味著有更多的簇，需要更多的數(shù)據(jù)傳輸?？梢娫诜执氐臒o線傳感器網(wǎng)絡(luò)中，并非越多越好。除n=50以外，RSDA算法的通信開銷只多出對應(yīng)iCPDA算法少許，相差不大。這主要是由于RSDA算法中所傳輸?shù)臄?shù)據(jù)包信息豐富，長度較長所致?？紤]到RSDA算法可以提供更高級別的安全保障，以及數(shù)據(jù)恢復(fù)為后續(xù)工作節(jié)省的能量消耗，首次聚集過程中的通信開銷是可以接受的，多次聚集后，總的通信開銷優(yōu)于iCPDA算法。

4　結(jié)束語

RSDA算法較好的實現(xiàn)了數(shù)據(jù)的隱私保護，并具備驗證數(shù)據(jù)真實性和完整性的功能。算法的數(shù)據(jù)恢復(fù)能力，使聚集節(jié)點能夠恢復(fù)聚集前的原始數(shù)據(jù)。性能分析和仿真實驗的結(jié)果驗證了算法的安全性和高效性，雖然首次聚集通信量稍大，但多次聚集后，總體能耗令人滿意。

目前的RSDA算法對于簇內(nèi)成員為一般傳感器節(jié)點，簇頭為計算、存儲、通信等能力遠高于一般簇成員的高資源傳感器節(jié)點的異構(gòu)無線傳感器網(wǎng)絡(luò)顯然更加適用，如何使其更具通用性以及如何進一步降低首次聚集過程中的能耗開銷將是今后努力的方向。

參考文獻：

[1]馮延蓬，仵博，鄭紅燕．異構(gòu)無線傳感器網(wǎng)絡(luò)中基于POMDP的實時調(diào)度算法．儀表技術(shù)與傳感器，2012(8)：101-104．

[2]王翥，魏德寶，王玲．傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合時機控制算法．儀表技術(shù)與傳感器，2012(5)：75-78．

[3]MADDEN S，F(xiàn)RANKLIN M J，HELLERSTEIN J M．TAG：A Tiny Aggregation Service for Ad hoc Sensor Networks．Proceedings of the 5th Symposium on Operating Systems Design and Implementation．NewYork，USA，2002：131-146．

[4]YAO Jian-Bo，WEN Guang-Jum．Protecting classification priracy data aggregation in wireless sensor networks．Proceedings of the 4th International Conference on Wireless Communication．Networking and Mobile Computing (WiCOM)．Dalian：China，2008：1-5．

[5]楊庚，王安琪，陳正宇，等．一種低耗能的數(shù)據(jù)融合隱私保護算法．計算機學(xué)報，2011，34(5)：792-800．

[6]Stavrns Papadopoulos，Aggelos Kiayias，Dimitris Papadias．Secure and efficient in-network processing of exact SUM queries．Proceedings of the 27th International Conference on Data Engineering(ICDE)．Hannover：Germany，2011：517-528．

[7]HE W，LIU X，NGUYEN H，et al．A cluster-based protocol to enforce integrity and preserve privacy in data aggregation．Proceedings of the 29th IEEE International Conference on Distributed Computing Systems Workshops．Montreal：QC，Canada，2009：14-19．

[8]張金榮，王越，王東，等．組合能量圓分布無線傳感器網(wǎng)絡(luò)分簇路由與拓撲形成算法．儀表技術(shù)與傳感器，2009(1)：61-64．

[9]MYKLETUN E，GIRAO J，WESTHOFF D．Public Key Based Cryptoschemes for Data Concealment in Wireless Sensor Networks．Proc．of the 2006 IEEE International Conference on Communications(ICC2006)，Istanbul：Turkey，2006：2288-2295．

[10]BONEH D，GENTRY C，LYNN B，et al．Aggregate and Verifiably Encrypted Signatures from Bilinear Maps．Proc of the 22nd International Conference on Theory and Applications of Cryptographic Techniques (Eurocrypt2003)，Warsaw：Poland，2003：416-432．