基于復數域的高效完整性保護數據融合算法

賈宗璞 王冠瓊 彭維平 郭海儒

(河南理工大學計算機科學與技術學院 河南 焦作 454000)

基于復數域的高效完整性保護數據融合算法

賈宗璞 王冠瓊 彭維平 郭海儒

(河南理工大學計算機科學與技術學院 河南 焦作 454000)

隨著WSNs的快速發展，其應用的領域越來越多。很多領域對數據的隱私性和完整性保護有著極高的要求，所以對傳感器網絡的安全性要求也更高了。設計一種能夠同時兼顧數據隱私性和完整性保護的數據融合算法顯得尤為重要，由此提出了一種基于復數域的高效的新數據融合安全算法，在保留原有復數域算法特點的同時，加入分布式驗證數據完整性機制，使算法能夠快速、高效地檢測出被篡改的虛假數據。理論分析與仿真結果表明：算法在不增加能耗的同時，能夠降低盲目丟棄率，提高安全性，并能更快速地檢測出惡意數據。

數據融合 完整性保護 隱私保護 復數域

0 引 言

在WSNs的實際應用中，有大量的數據冗余與碰撞存在數據的采集與傳輸過程中，不僅影響有效數據的采集，而且網絡會過早的死亡。因此，數據融合機制被應用于WSNs中以減少能耗和數據冗余。數據融合中典型的算法就是TAG[1]。

基礎的數據融合技術一般不保護數據的隱私性和完整性。但是在實際應用中，由于傳感器節點資源有限，包括電池能量、計算能力以及存儲容量等方面，使得節點被輕易地攻擊或俘獲，進而影響WSNs大規模應用，因此在實際中考慮安全的WSNs意義重大[2]。例如醫院的病房監控系統，節點可以獲取病人的脈搏、體溫、血壓等數據，這些數據屬于病人不想被他人獲取的個人隱私。又或者，惡意節點通過篡改病人的這些數據，來引發報警系統。WSNs數據融合隱私保護和完整性驗證機制就是為了防止隱私數據的泄露以及確保正確的數據融合。

Przydatek等人[3]對WSNs中的安全數據融合技術進行了首次研究，使用Merkle hash樹監察數據正確性，并提出“融合—承諾—證明”框架。Chen等人[4]提出一種可恢復的數據融合方案RCDA，該方案在Mykletun等人[5]提出的隱密數據融合方案和Boneh等人[6]提出的聚合簽名方案基礎上，著重于基站能夠恢復被融合后的節點數據，由于該方案的通信開銷和能量消耗略高，限制了其在大規模的WSNs的應用。Du等人[7]為了保證融合節點數據的正確性，在網絡中添加監督節點，但是監督節點浪費了部分節點資源，同時限制了網絡拓撲。Gao等人[8]在文獻[7]的基礎上進行改進，在簇內設置紅黑兩個簇頭，紅黑簇頭將MAC值上傳至父節點，由父節點對比MAC值判斷數據正確性，雖然該算法比文獻[7]適應性更好，但監督節點的加入，提高了對網絡結構的要求，限制了應用范圍。iPPHA算法[9]在直方圖融合基礎上，構建另一顆融合樹傳輸冗余信息，在基站處對數據完整性進行驗證。He等人分別擴展了PDA算法[10]中提出的SMART和CPDA方法，提出了兩種能夠兼顧隱私保護和完整性驗證的數據融合方案iPDA[11]和iCPDA[12]，但是在增加完整性驗證功能后，增大了算法復雜度和通信開銷。周強等人[13]提出的ICKPDA算法，通過節點的私密種子隱匿原始數據，又使用數據聚焦和分片技術增強對數據的隱私保護，最后在基站通過數據間的關聯特性驗證數據完整性，該算法用安全級別的降低來減少節點能量的消耗，適用于對安全需求不高的，需要長時間工作的無線傳感網絡。趙丹等人[14]提出的CBIPDA算法，利用復數的虛實部關聯特性保護數據完整性，但是在基站統一驗證，使得網絡只能在基站發現惡意數據，一旦發現就會丟棄整個融合結果。

本文提出了一種基于復數域的高效的新數據融合安全算法，在保留原有復數域算法特點的同時，加入分布式驗證數據完整性機制，使算法能夠快速、高效地檢測出被篡改的虛假數據。

1 網絡模型與算法實現

1.1 網絡模型

本文算法與CBIPDA算法都采用TAG[1]算法建立網絡模型，網絡模型相同，在這里不作贅述。本文算法密鑰由隨機密鑰分配機制分配[15]。

1.2 算法描述

算法流程如圖1所示。

無線傳感器網絡工作時，由QS節點通過μTEsla[16]認證技術廣播查詢信息，各節點收到查詢信息后開始進行數據融合。假如a為傳感器節點收集的數據，構造的復數形式為：R=s+bi=a+k+bi。其中，實數部分k為該節點與融合節點之間的共享密鑰，用于隱藏并保護數據隱私；虛數部分b用于數據完整性驗證，且b=n×a(其中n是一次查詢任務中網絡中共享的一個全局變量，其數值在每一次查詢中隨機改變)。通過這種方式將虛數部分與實數部分關聯起來，假如惡意節點只篡改實數部分數據，虛數部分會隨著實數部分的改變而改變，完整性驗證機制依然奏效。

本文算法核心闡述如下：

(1) 節點初始化

Sense a

//節點a

Mask(a,k)

//k為該節點與融合節點之間的共享密鑰,用于隱匿真實數據

s=a+k ;

//實數域

GetCmpxNum(s,b)

//虛數b

R1=s+bi=a+k+b*i;

//b=n*a,n為一次查詢任務中網絡中共享的全局變量

Cj=Ek(R1) ;

//加密數據

Transmit(Cj)

(2) 計算融合結果

receive (Cj)

//融合節點接收數據

Drc (Cj)

//解密數據

Add ( )

Agg=R1+R2+…+Rn

//復數域數據融合結果

(3) 計算真實融合結果

Disjoin (Agg)

//分離實數域與虛數域

Agg = Aggr + Aggi

Ksum= Compute (sum of keys of all source nodes)

RAgg = Aggr - Ksum

//得到實數中的真實數據和

SUMi= (RAgg * n)i

//通過實數中的真實數據和RAgg，計算虛數部分b和

(4) 完整性驗證

if SUMi= Aggi

return RAgg ;

//完整性驗證通過，返回真實數據

else

reject RAgg ;

//數據被篡改，拒絕接收

DAgg = Drc (Agg) ;

//加密融合結果

Transmit(DAgg ) ;

1.3 實例描述

如圖2所示假設葉子節點1、2、3采集到的數據為d1、d2、d3，經加密處理后，融合節點5接受到的為：

D1=d1+k1,5+nd1i

D2=d2+k2,5+nd2i

D3=d3+k3,5+nd3i

圖2 網絡模型

假設融合節點5的融合結果為Agg5，Agg5由實數部分Agg5r和虛數部分Agg5i兩部分構成。根據融合節點與子節點共享的密鑰計算出密鑰之和ksum=k1,5+k2,5+k3,5，則可以得到真實的融合結果RAgg5=Agg5r-ksum。由RAgg5可得出虛數域融合結果為SUMi=(n×RAgg5)i，比較SUMi與Agg5i是否相等鑒別數據完整性，若相等，則完整性驗證通過，隱私保護處理后上傳數據；若不相等，則完整性遭到破壞，丟棄。通過這種方式，數據層層傳遞，最終傳送到QS處。具體實例如下：

(1) 數據未被篡改

假如d1=25，d2=30，d3=32，k1,5=478，k2,5=708，k3,5=624，n=10。則：

D1=d1+k1,5+nd1i=25+478+10×25×i=503+250i

D2=d2+k2,5+nd2i=30+708+10×30×i=738+300i

D3=d3+k3,5+nd3i=32+624+10×32×i=656+320i

Agg5=D1+D2+D3=1897+870i

Agg5r=1897

Agg5i=870i

ksum=k1,5+k2,5+k3,5=478+708+624=1810

RAgg5=Agg5r-ksum=1897-1810=87

SUMi=(n×RAgg5)i=10×87×i=870i

即SUMi與Agg5i相等，完整性驗證通過，可以上傳改數據。

(2) 數據未被篡改

數據被篡改可以分為三種清空：

① 只有實數域被篡改

假設D1被篡改后變為：D1=530+250i

經過計算可得：

Agg5=1954+870i

Agg5i=870i

RAgg5=1924-1810=114

SUMi=(n×RAgg5)i=10×114×i=1140i

即SUMi與Agg5i不相等，完整性驗證不通過，丟棄該數據。

② 只有虛數域被篡改

假設D1被篡改后變為：D1=503+275i

經過計算可得：

Agg5=1897+895i

Agg5i=895i

RAgg5=1897-1810=87

SUMi=(n×RAgg5)i=10×87×i=870i

即SUMi與Agg5i不相等，完整性驗證不通過，丟棄該數據。

③ 實數域和虛數域都被篡改

假設D1被篡改后變為：D1=530+275i

經過計算可得：

Agg5=1924+895i

Agg5i=895i

RAgg5=1924-1810=114

SUMi=(n×RAgg5)i=10×114×i=1140i

即SUMi與Agg5i不相等，完整性驗證不通過，丟棄該數據。

2 性能分析

使用MATLAB進行仿真，網絡環境具體配置為：600個節點隨機分布于400m×400m區域中，標準室內環境，無線信道對稱，背景噪聲為-105.0dBm，高斯白噪聲為4dB，節點的數據傳輸速率為1Mbps，節點的靈敏度為-108.0dBm，節點的傳輸距離為50m。

2.1 安全性分析

本文算法采用隨機密鑰分配機制[15]分配密鑰，每個節點從一個擁有K個密鑰的密鑰池中隨機選取k個密鑰，若兩個節點擁有共同密鑰時，那么這兩個節點間的鏈路是安全的。一個相同的密鑰存在任意兩個節點的概率為pconnect=1-((K-k)!)2/K!(K-2k)!。偷聽節點獲得密鑰的概率為poverhear=k/K，而k遠小于K，概率小于1%，可以滿足一般的隱私保護需求。而CBIPDA是使用MD(masterdevice)裝置在部署無線傳感器網絡時，單獨分發種子，也就是一成不變的，一旦種子被獲取，無法更換，所以在隱私保護方面本文算法優于CBIPDA。

在完整性方面，CBIPDA在基站處統一驗證數據完整性：首先，會使被篡改的數據長時間的存在于網絡中，耗費網絡能量。其次，假如數據被篡改，基站在驗證完整性時，會丟棄所有數據，那么本次查詢將沒有結果。假如攻擊者使用這種方式攻擊網絡，會使基站查詢不到結果，即網絡癱瘓。但是本文算法就不會出現這種情況，本文算法不僅保留了CBIPDA可以驗證完整性的特點，而且通過加入分布式機制，使本文算法可以快速地檢驗出被篡改的數據，并丟棄，所以在完整性方面本文算法優于CBIPDA。

2.2 高效性

2.2.1 盲目丟棄率

很多協議在基站處驗證數據完整性，一旦驗證不通過后，融合結果將直接被拋棄，進而合法節點發送的安全數據也隨之丟棄，因此盲目丟棄也是安全數據融合需要考慮的重要問題。本文算法提出一種高效的完整性驗證算法，采用分布式驗證方式，盡早丟棄錯誤數據，減少正確數據被丟棄的概率。

假定網絡結構為完全二叉樹，h為樹的深度，s為惡意節點到基站的距離，則本文算法的盲目丟棄率BR(s)為:

在CBIPDA算法中，完整性驗證是在基站處，一旦發現錯誤數據，則直接丟棄本次查詢的融合結果，因此盲目丟棄率為100%。仿真結果如圖3所示。

圖3 本文算法與CBIPDA數據盲目丟棄對比

從圖3的仿真結果可知，本文算法的盲目丟棄數據率隨著距離基站跳數的變大而變小,而CBIPDA的盲目丟棄率始終是100%。這時由于在CBIPDA算法中，完整性驗證只在基站處進行，一旦發現數據不完整，就會將數據丟棄，故盲目丟棄率始終為100%。而在本文算法中，加入了分布式驗證完整性機制，由基站統一驗證，改為在融合節點驗證，在網絡的早期，數據傳輸量小，在這個階段發現篡改數據，盲目丟棄率就會很低。例如，當跳數大于5時，盲目丟棄率小于3%。當跳數小于5時，網內傳輸的數據包數會隨著參與節點的增多呈幾何倍增加增加，同時盲目丟棄率也急劇增長，并在基站處達到最高100%。

2.2.2 惡意數據發現時間間隔

MTTD(MeanTimeToDetect)是指從虛假數據注入開始，到被發現結束，中間的時間間隔。本文算法算法是分布式驗證數據完整性，數據的融合和驗證是同時進行的，惡意數據能夠在一跳內快速地被監測到。而CBIPDA的認證是在基站統一完成的。仿真結果如圖4所示。

圖4 本文算法與CBIPDA的MTTD對比

從圖4可知，網絡中的節點數越多即網絡規模越大，隨著網絡規模的增大，CBIPDA算法的MTTD逐漸變大，持續增長，也就是說發現惡意節點的時間會越來越長，這是因為CBIPDA在基站處對數據進行完整性驗證，因此隨著從葉子節點到達基站傳輸數據時間的增加，CBIPDA檢驗出虛假數據時間也隨之增加。而本文算法的MTTD一直在5s以內波動，這是因為數據完整性在融合節點進行驗證，所需要的時間只是父融合節點接收到子節點數據的時間，這個時間波動不大，而且不受網絡規模的影響。

2.3 通信開銷

文獻[17]表明節點發送1bit數據消耗約4 000nJ的能量，處理器執行一條指令消耗約為5nJ能量。換言之，發送1bit數據的能耗相當于處理器處理800條指令的能耗，所以暫不考慮在融合節點計算上多出的能量消耗。

TAG算法是經典的融合算法，設TAG算法數據通信開銷為o(n)，其中，N表示網絡中的節點數量。若各算法發送的數據包大小相等，則可通過發送數據包的數量來衡量通信量。

1)iPDA

iPDA是經典的分片算法，通過將原始數據至少取L=2，來實現對數據的隱私保護。iPDA構建了兩顆不相交的融合樹，即每個節點需要傳送L-1+L個分片，需要2L-1個消息用于傳送數據分片，另外還需要一個消息傳送融合后的數據，所以該算法的通信開銷為o(2Ln)，因L=2，故數據通信開銷為o(4n)。

2)CBIPDA

CBIPDA算法通過為節點添加私有種子保護節點數據穩私。

節點無需對數據進行分片和串通，只需要在融合之前構造出自身復數形式的數據即可。其他階段皆按照TAG算法進行融合，所以數據通信開銷與TAG算法相同，為o(n)。

3) 本文算法

本文算法通過將原始數據構造成復數域形式保護數據隱私性，也無需對數據進行分片和串通，同時加入分布式完整性驗證機制，驗證數據完整性，提高算法的高效性。在數據融合階段，它基于TAG算法按照相同機制進行融合，所以建樹后數據通信開銷與TAG算法相同，為o(n)。仿真結果如圖5所示。

圖5 本文算法與CBIPDA、iPDA數據通信量比較

圖5說明了本文算法、CBIPDA算法和iPDA算法的通信開銷與無線傳感器網絡中節點數據之間的關系。雖然三種算法的通信開銷都隨著節點數目的增加而增加，但是在節點數據一定時，iPDA算法的通信開銷是其他兩種算法的四倍，而本文算法和CBIPDA算法的通信開銷幾乎一致。即本文算法在沒有增加通信開銷的同時，提高了算法的高效性，使算法更早的發現惡意數據。

2.4 可擴展性

不同的數據融合安全機制對網絡規模變化的適應性不同。本文算法之所以比CBIPDA算法更能適應大規模的WSNs的原因是：本文算法能更早地發現網絡中的惡意數據，并及時剔除。而CBIPDA算法將所有數據傳送到基站，由基站統一驗證數據完整性，不能及時清除惡意數據，隨著網絡規模的擴大，惡意數據在WSNs中存活的時間更長、傳輸的距離更遠，同時需要參與該數據的傳輸、處理、融合節點更多，浪費很多中間節點的能量。

3 結 語

本文算法是對CBIPDA的改進。本文算法在不增加網絡能耗的前提下，采用分布式驗證的方法，更早地發現惡意數據和丟棄惡意數據，降低盲目丟棄率，在保證數據融合安全性的同時提供高效的數據完整性認證機制。且相比與CBIPDA算法，本文算法具有更好的可擴展性，適合于大規模的無線傳感器網絡。

[1]MaddenS,FranklinMJ,HellersteinJM.TAG:Atinyaggregationserviceforadhocsensornetworks[C] //Proceedingsofthe5thSymposiumonOperatingSystemsDesignandImplementation.NewYork,USA,2002:131-146.

[2]ShiE,PerrigA.Designingsecuresensornetworks[J].IEEEWirelessCommunications,2004,11(6):38-43.

[3]PrzydatekB,SongD,PerrigA.SIA:Secureinformationaggregationinsensornetworks[C] //Procofthe1stInternationalConferenceonEmbeddedNetworkedSensorSystems.LosAngeles,USA,2003:255-265.

[4]ChenCM,LinYH,LinYC,etal.RCDA:RecoverableConcealedDataAggregationforDataIntegrityinWirelessSensorNetworks[J].IEEETransactionsonParallelandDistributedSystems,2012,23(4):727-734.

[5]MykletunE,GiraoJ,WesthoffD.PublickeybasedcryptoschemesfordataconcealmentinWirelessSensorNetworks[C]//ProcoftheIEEEInternationalConferenceonCommunications.Istanbul,Turkey,2006:2288-2295.

[6] Boneh D,Gentry C,Lynn B,et al.Aggregate and verifiably encrypted signatures from bilinear maps[C]//Proc of Cryptographic Techniques.Warsaw,Poland,2003:416-432.

[7] Du W,Deng J,Han Y S,et al.A witness-based approach for data fusion assurance in wireless sensor networks[C]//Proc of Global Telecommunications Conference.San Francisco,USA,2003:1435-1439.

[8] Gao F,Zhu W T.A dual-head cluster based secure aggregation scheme for sensor networks[C] //Proc of IFIP International Conference on Network and Parallel Computing.Shanghai,China,2008:103-110.

[9] 陳偉,于樂.一種支持完整性驗證的隱私保護直方圖融合算法[J].電子學報,2014,42(11):2268-2272.

[10] He Wenbo,Hoang Nguyen,Liu Xue,et al.Pda:Privacy-preservingdata aggregation in wireless sensor networks[C]//Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOMM).2007:2045-2053.

[11] He Wenbo,Hoang Nguyen,Liu Xue,et al.iPDA:An Integrity-Protecting Private Data Aggregation Scheme for Wireless Sensor Networks[C]//Proceedings of IEEE Military Communications Conference,2008:1-7.

[12] He Wenbo,Liu Xue,Nguyen H,et al.A cluster-based protocol to enforce integrity and preserve privacy in data aggregation[C]//Proc of the 29th IEEE International Conference on Distributed Computing Systems.Piscataway:IEEE P-ress,2009:14-19.

[13] 周強,楊庚,李森,等.一種可檢測數據完整性的隱私數據融合算法[J].電子與信息學報,2013,35(6):1277-1283.

[14] 趙丹,楊庚.一種基于復數域的數據融合完整性保護算法[J].計算機技術與發展,2012,22(8):150-154,158.

[15] Eschenauer L,Gligor D G.A key-management scheme for distributed sensor networks[C]//Proc of the 9th ACM Conference on Computer and Communication Security.New York:ACM Press,2002:41-47.

[16] Perrig A,Szewczyk R,Wen V,et al.SPINS:Security protocols for sensor networks[C]//Proc of Mobile Computing and Networking,Rome:ACM,2010:189-199.

[17] Szewczyk R,Ferencz A.Energy implications of network sensor designs.Berkeley[R].Berkeley Wireless Research Center Report,2000.

EFFICIENT INTEGRITY PROTECTION DATA FUSION ALGORITHM BASED ON COMPLEX FIELD

Jia Zongpu Wang Guanqiong Peng Weiping Guo Hairu

(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

With the rapid development of wireless sensor networks, they are applied to more and more fields. As there is a very high demand for data privacy and integrity protection in many fields, a higher requirement for the security of sensor networks is put forward. Therefore, it is very important to design a data fusion algorithm that can take into account both data privacy and integrity protection. In this paper, we propose an efficient and safe new integrity protection data fusion algorithm based on complex field. While retaining the characteristics of the original complex field algorithm, we add distributed data integrity verification mechanism, which enables the algorithm to quickly and efficiently detect the tampered false data. Theoretical analysis and simulation results show that the algorithm can reduce the blind discard rate, improve the security and detect the malicious data more quickly without increasing energy consumption.

Data aggregation Integrity protection Privacy protection Complex filed

2015-10-25。河南省科技攻關項目(132102210123)；河南省重點科技攻關項目(122102310309)；河南理工大學博士基金項目(B2009-21)。賈宗璞，教授，主研領域：計算機專業教學和計算機網絡技術，計算機測控技術，信息系統。王冠瓊，碩士生。彭維平，副教授。郭海儒，副教授。

TP309

A

10.3969/j.issn.1000-386x.2017.04.013