傳感器網(wǎng)絡(luò)虛假數(shù)據(jù)過濾的最優(yōu)覆蓋度分析

劉志雄　劉華富

(長沙學(xué)院數(shù)學(xué)與計算機科學(xué)系　湖南 長沙 410022)

?

傳感器網(wǎng)絡(luò)虛假數(shù)據(jù)過濾的最優(yōu)覆蓋度分析

劉志雄劉華富*

(長沙學(xué)院數(shù)學(xué)與計算機科學(xué)系湖南 長沙 410022)

虛假數(shù)據(jù)過濾是傳感器網(wǎng)絡(luò)安全領(lǐng)域的一個重要問題。當(dāng)前算法通常由t個擁有不同密鑰分區(qū)的節(jié)點協(xié)同對數(shù)據(jù)進(jìn)行加密，但其所采取的隨機部署節(jié)點方式無法確保每個事件源都被t個密鑰分區(qū)所覆蓋，從而導(dǎo)致稀疏區(qū)域的事件無法上報給sink。提出利用覆蓋算法對節(jié)點進(jìn)行部署，基于覆蓋質(zhì)量及網(wǎng)絡(luò)開銷推導(dǎo)和證明了最優(yōu)節(jié)點覆蓋度Δ。實驗結(jié)果表明，采用Δ覆蓋比隨機部署的密鑰覆蓋有效性提高約70%。

無線傳感器網(wǎng)絡(luò)虛假數(shù)據(jù)過濾節(jié)點部署最優(yōu)覆蓋

0　引　言

無線傳感器網(wǎng)絡(luò)WSN廣泛地應(yīng)用在交通管理、珍稀動物追蹤以及人體心臟監(jiān)控等領(lǐng)域中[1]。通常情況下，傳感節(jié)點部署在惡劣的區(qū)域或者是敵對環(huán)境中，攻擊者往往利用俘獲的秘密信息偽造事實上不存在的虛假數(shù)據(jù)并發(fā)送給鄰居節(jié)點[2]。如不加防范，這類攻擊將極大地消耗網(wǎng)絡(luò)資源，并引起錯誤的警報[3]。

為了應(yīng)對虛假數(shù)據(jù)注入攻擊，國內(nèi)外研究人員提出了一些解決策略[3-12]。它們的大致思想都是借鑒數(shù)字簽名，在每個產(chǎn)生的數(shù)據(jù)報告中捎帶t個MAC(Message Authentication Code)，然后由中間節(jié)點和sink實施過濾。然而，由于受到部署區(qū)域不規(guī)則等復(fù)雜因素的影響，上述方案所采取的隨機部署策略往往在網(wǎng)絡(luò)中形成部分稀疏區(qū)域(如：邊界地帶)[10]，從而因檢測節(jié)點數(shù)量不夠造成部分突發(fā)事件無法上報到目標(biāo)節(jié)點。

本文利用覆蓋算法對節(jié)點進(jìn)行部署，推導(dǎo)并證明了適用于虛假數(shù)據(jù)過濾的最優(yōu)節(jié)點覆蓋度Δ。理論分析及仿真實驗表明，與隨機部署及其他覆蓋算法相比，Δ覆蓋能以較高概率保證每個事件源被t個密鑰分區(qū)同時覆蓋。

1　相關(guān)工作

文獻(xiàn)[3]率先對虛假數(shù)據(jù)過濾進(jìn)行了研究，提出了基于對稱密鑰及過濾驗證的SEF方案。該方案假設(shè)存在一個大小為n·m的密鑰池，其中n為密鑰分區(qū)數(shù)量，每個分區(qū)包含m個密鑰。給節(jié)點預(yù)置一個密鑰分區(qū)，并隨機部署在監(jiān)控區(qū)域中。多個節(jié)點協(xié)同對感知事件加密，并生成包含t個MAC的報告。轉(zhuǎn)發(fā)過程中，中間節(jié)點利用對稱密鑰對MAC進(jìn)行校驗。然而，由于實際部署網(wǎng)絡(luò)的形狀通常是不規(guī)則的，SEF所采取的隨機部署策略往往可能在邊界地帶等形成部分稀疏區(qū)域，故沒有足夠的節(jié)點來完成數(shù)據(jù)感知和數(shù)據(jù)產(chǎn)生。

例如，在圖1所示的森林防火警報系統(tǒng)中，假設(shè)覆蓋A1、A2、A3的持不同密鑰的節(jié)點集分別為{S1，S2,…，S5}，{S6，S7，…，S9}，{S10，S11}。假設(shè)閾值t=5，若火災(zāi)發(fā)生在A1，則能由5(≥t)個持不同密鑰的節(jié)點共同產(chǎn)生數(shù)據(jù)并上報；而若當(dāng)火災(zāi)發(fā)生在其他兩個區(qū)域，則無法產(chǎn)生數(shù)據(jù)，因為監(jiān)測節(jié)點數(shù)量分別只有4個和2個(4

圖1　森林防火警報系統(tǒng)

文獻(xiàn)[4]提出了一種基于多軸劃分的方案GRSEF。該方案將節(jié)點分成t組，并采用多坐標(biāo)系對網(wǎng)絡(luò)區(qū)域進(jìn)行劃分，然后分發(fā)密鑰。與SEF不同，GRSEF限定由t個不同組的節(jié)點共同產(chǎn)生數(shù)據(jù)包，從而能有效提高虛假數(shù)據(jù)過濾的效率。然而，多軸劃分算法的計算復(fù)雜性很高，不利于節(jié)省網(wǎng)絡(luò)能量，且在成組過程中并沒有對節(jié)點的位置進(jìn)行合理規(guī)劃，從而難以確保有足夠多的節(jié)點同時感知到突發(fā)事件。

文獻(xiàn)[5]提出了一種基于星形拓?fù)涞腞SFS方案。當(dāng)檢測到突發(fā)事件時，由一種比普通節(jié)點能量強得多的特殊節(jié)點作為簇頭對數(shù)據(jù)進(jìn)行聚合，并在聚合數(shù)據(jù)后附加簇內(nèi)普通節(jié)點的MAC進(jìn)行發(fā)送。當(dāng)數(shù)據(jù)傳輸?shù)絪ink節(jié)點后，由sink對聚合結(jié)果及MAC進(jìn)行驗證。該方案不受安全閾值的限制，但不是一種轉(zhuǎn)發(fā)過濾策略，假數(shù)據(jù)包必須傳輸?shù)絪ink才能被過濾，不適用于能量有限的傳感器網(wǎng)絡(luò)。

文獻(xiàn)[6]提出了一種基于單向函數(shù)和MAC的過濾方案FFRF。在部署前，該方案給每個節(jié)點配置一個單向函數(shù)f，并基于f和一個隨機數(shù)x生成一條哈希鏈。接下來，每個節(jié)點將哈希鏈中的第一個哈希值在網(wǎng)絡(luò)中進(jìn)行公開，中間節(jié)點以一定概率隨機存儲部分源節(jié)點的第一個哈希值，用來對數(shù)據(jù)進(jìn)行驗證。由于FFRF沒有在節(jié)點密鑰和哈希值之間建立某種函數(shù)關(guān)系，從而給攻擊者提供了便利。此外，假設(shè)突發(fā)事件發(fā)生在簇與簇交替的區(qū)域，該方案將無法順利產(chǎn)生數(shù)據(jù)。

總之，已有虛假數(shù)據(jù)過濾算法所采用的隨機部署無法保證每個事件源都被足夠多的密鑰分區(qū)同時覆蓋，從而導(dǎo)致發(fā)生在稀疏區(qū)域的事件無法上報到sink節(jié)點。本文主要研究適用于虛假數(shù)據(jù)過濾的最優(yōu)節(jié)點覆蓋。

2　WSN虛假數(shù)據(jù)過濾最優(yōu)覆蓋分析

隨機部署無法為當(dāng)前過濾機制提供足夠的t-k cover，考慮采取覆蓋算法對節(jié)點進(jìn)行部署。為敘述簡便，將t個密鑰分區(qū)同時覆蓋記為t-k cover，并將某種部署算法能保證每個事件源都被t個密鑰分區(qū)同時覆蓋的概率記為pt-k。當(dāng)pt-k值太小時無法滿足過濾機制的要求，太大時所需節(jié)點覆蓋度越高，從而引起較大的網(wǎng)絡(luò)開銷[12]。

定義1在虛假數(shù)據(jù)過濾中，將D+1覆蓋比D覆蓋增加的pt-k記為In(D+1，D)。給定系統(tǒng)閾值f，若存在Δ，使得In(Δ，Δ-1) ≥f，且In(Δ+1，Δ) ≤f，則稱Δ覆蓋為最優(yōu)覆蓋。

定理1存在一個全局密鑰池G={Ki:0≤i≤N-1}，密鑰池大小為N，分為n個不重疊的密鑰分區(qū){Ui,0≤i≤n-1}，每個分區(qū)包含γ個密鑰(N=n×γ)。每個節(jié)點從全局密鑰池中任取一個密鑰分區(qū)進(jìn)行裝載，則Δ(Δ≥t)個傳感器節(jié)點中至少有t個節(jié)點擁有互不相同密鑰分區(qū)的概率為：

(1)

證明：首先計算Δ個節(jié)點中恰有t個節(jié)點擁有互不相同密鑰分區(qū)的概率。在Δ(Δ≥t)個傳感器節(jié)點中，每個節(jié)點擁有一個密鑰分區(qū)，得到的Δ個密鑰分區(qū)，對于虛假數(shù)據(jù)過濾來講，是不需考慮排列順序的。因此，Δ個傳感器節(jié)點中的每個節(jié)點在一個等分為n個分區(qū)的全局密鑰池中，任取一個密鑰分區(qū)進(jìn)行裝載，每個節(jié)點擁有一個密鑰分區(qū)，允許重復(fù)，不管其順序合并成一組，得到的密鑰分區(qū)組合種數(shù)為C(n+Δ-1,Δ)。

而在Δ(Δ≥t)個傳感器節(jié)點中恰有t個節(jié)點擁有互不相同密鑰分區(qū)的組合種數(shù)為C(n,t)C(Δ-1,Δ-t)。所以，Δ(Δ≥t)個傳感器節(jié)點中恰有t個節(jié)點擁有互不相同密鑰分區(qū)的概率為：

(2)

采用類似的方法依次可解Δ個節(jié)點中恰好1，2，…，t-1個擁有互不相同密鑰分區(qū)的概率。綜上可知，Δ個節(jié)點中至多擁有t個密鑰分區(qū)的概率為：

(3)

故Δ個節(jié)點中至少擁有t個不同密鑰分區(qū)的概率為p=1-pΔ(1,2，…,t)。證畢。

定理1在傳感器網(wǎng)絡(luò)虛假數(shù)據(jù)過濾中，采用覆蓋算法對節(jié)點進(jìn)行部署，并在數(shù)據(jù)包后附帶t個MAC進(jìn)行驗證。給定f=0.05，當(dāng)覆蓋度Δ=2t時，Δ覆蓋為最優(yōu)覆蓋。

證明：由定理1可知，Δ(Δ≥t)個傳感器節(jié)點中恰有t個節(jié)點擁有互不相同密鑰分區(qū)的概率為pΔ(t)。故有下式成立：

(4)

顯然有：

(5)

由歸納法知，當(dāng)Δ≥ 2t時，In(Δ+1，Δ) ≤ 0.05=f。同理，In(Δ，Δ-1) ≥ 0.05=f成立。因此，當(dāng)Δ=2t時，Δ覆蓋為適用于傳感器網(wǎng)絡(luò)虛假數(shù)據(jù)過濾的最優(yōu)覆蓋。證畢。

定理3存在一個等分為n個分區(qū)的全局密鑰池，每個節(jié)點從中任取一個密鑰分區(qū)進(jìn)行裝載，則2t個傳感器節(jié)點中恰有t個節(jié)點擁有互不相同密鑰分區(qū)的概率使下式成立：

(6)

證明：當(dāng)t=1時，由于n≥24，有：

(7)

假設(shè)t=k時，式(6)成立，則當(dāng)t=k+1時：

(8)

因為，當(dāng)24k2≤n時：

(9)

所以式(6)成立。證畢。

圖2給出了當(dāng)t=5、n=10、ε=0.2時，P的理論分析曲線和仿真實驗結(jié)果關(guān)于Δ的變化情況，其中仿真結(jié)果是隨機測試500次取的均值。從圖中可以看出，當(dāng)Δ< 2t=10時，P隨覆蓋度的增加而迅速增大；反之，當(dāng)Δ>2t=10時，P隨覆蓋度的增加僅緩慢增大。由最優(yōu)覆蓋的定義可知，此時所增加的概率是不值得的，因此，取Δ=2t為最優(yōu)。

圖2　P的理論值與仿真結(jié)果

3　仿真實驗

為了進(jìn)一步比較隨機部署和Δ覆蓋算法的t-dk cover性能，本文利用C語言建立了模擬仿真平臺。仿真環(huán)境如下：在40×40 m2的方形網(wǎng)絡(luò)區(qū)域中，0～500個傳感器節(jié)點分別隨機部署或者按照Δ覆蓋算法部署，其他仿真參數(shù)的設(shè)置見表1所示。取15次仿真實驗的平均值作為試驗結(jié)果。

表1　仿真參數(shù)列表

如圖3所示，當(dāng)節(jié)點部署密度較小時，兩種方案的t-dk cover 性能都較差，例如，當(dāng)網(wǎng)絡(luò)中總共只部署了200個節(jié)點時，兩者的t-dk cover比率分別只有6.2%和4.1%。隨著節(jié)點部署密度增大，隨機模型的t-dk cover性能僅緩慢增強，例如當(dāng)節(jié)點數(shù)由200增到400時，合法覆蓋率僅增加了3.2%。而此時Δ覆蓋算法的t-dk cover性能則隨節(jié)點增加而迅速增大，例如在部署400個節(jié)點的條件下，其t-dk cover率增加了87%。這是因為，隨機模型沒有對節(jié)點部署進(jìn)行規(guī)劃，故而在網(wǎng)絡(luò)中特別是邊界地區(qū)形成部分稀疏區(qū)域，而Δ覆蓋算法能通過節(jié)點規(guī)劃而達(dá)到更好的t-dk cover性能。

圖3　Δ覆蓋和隨機模型t-dk cover性能比較

4　結(jié)　語

虛假數(shù)據(jù)過濾是無線傳感器網(wǎng)絡(luò)中一個重要的安全問題。已有算法所采取的隨機部署節(jié)點方式無法確保每個事件源都被t個密鑰分區(qū)所覆蓋。提出利用覆蓋算法對節(jié)點進(jìn)行部署，分析并證明了適用于虛假數(shù)據(jù)過濾的最優(yōu)節(jié)點覆蓋度Δ。接下來的工作將研究多sink的情形。

[1] 任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報，2003,14(7):1282-1291.

[2] 劉明，曹建農(nóng)，鄭源,等.無線傳感器網(wǎng)絡(luò)多重覆蓋問題分析[J].軟件學(xué)報，2007,18(1):127-136.

[3] Ye F, Luo H Y,Lu S W,et al. Statistical En-route Filtering of Injected False Data in Sensor Networks[C]//Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM’04. Hong Kong, China, 2004,4:2446-2457.

[4] Yu L, Li J Z. Grouping-based Resilient Statistical En-route Filtering for Sensor Networks[C]//Proceedings of the 28th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM’09,2009:1782-1790.

[5] Yang X Y, Lin J, Moulema P, et al. A Novel En-route Filtering Scheme against False Data Injection Attacks in Cyber-physical Networked Systems[C]//Proceedings of the 32nd IEEE International Conference on Distributed Computing Systems (ICDCS), 2012:92-101.

[6] Naresh K, PrDadeep K P, Sathish K S.An Active En-route Filtering Scheme for Information Reporting in Wireless Sensor Networks[J].IJCSIT: International Journal of Computer Science and Informatin Technologies,2011,2(4):1812-1819.

[7] Lu R X, Lin X D, Zhu H J, et al. BECAN: A Bandwidth-efficient Cooperative Authentication Scheme for Filtering Injected False Data in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2012,23(1):32-43.

[8] Jiang J R, Sung T M. Maintaining Connected Coverage for Wireless Sensor Networks[C]//Proceedings of the 28th International Conference on Distributed Computing Systems Workshops. Washington DC: IEEE Computer Society, 2008:297-302.[9] Chen S J, Dunkels A, Osterlind F, et al. Time Synchronization for Predictable and Secure Data Collection in Wireless Sensor Networks[C]//Proceedings of The Sixth Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net 2007), Corfu, Greece, 2007:165-172.

[10] Zhang H H, Hou J C. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks[J].Ad hoc and Sensor Wireless Networks, 2005,1(2):89-124.

[11] Woehrle M, Brochoff D, Hohm T. Investigating Coverage and Connectivity Trade-offs in Wireless Sensor Networks: the benefits of MOEAs, TIK Report 294[R].Zurich:Computer Engineering and Networks Lab, ETH Zurich, 2012.

[12] Bose P, Morin B, Stojmenovic I, et al. Routing with Guaranteed Delivery in Ad hoc Wireless Networks[J]. Wireless Networks,2001(7):609-616.

ANALYSIS ON OPTIMAL COVERAGE DEGREE FOR FALSE REPORT FILTERING IN SENSOR NETWORKS

Liu ZhixiongLiu Huafu*

(DepartmentofMathematicsandComputerScience,ChangshaUniversity,Changsha410022,Hunan,China)

False report filtering is an essential security issue in security field of sensor networks. Existing algorithms usually encrypt the data report bytnodes with distinct key partitions in collaborative manner; however, the adopted random deployment mechanism cannot guarantee that every area can be covered bytkey partitions simultaneously. As a result, the events happening in sparse areas cannot be reported to sink. The paper proposes to deploy nodes through covering algorithm. It then deduces and proves the optimal coverage degreeΔbased on covering quality and network overhead. Experimental results show that usingΔcoverage can obtain a general increase in efficiency of coverage by about 70% compared with the random deploying method.

Wireless sensor networkFalse report filteringNodes deploymentOptimal coverage

2015-05-01。國家自然科學(xué)基金項目(61379117)；湖南省教育廳科學(xué)研究重點項目(13A114)。劉志雄，博士，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)。劉華富，教授。

TP393

A

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