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

劉志雄　劉華富

(長(zhǎng)沙學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系　湖南 長(zhǎng)沙 410022)

?

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

劉志雄劉華富*

(長(zhǎng)沙學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系湖南 長(zhǎng)沙 410022)

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

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

0　引　言

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

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

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

1　相關(guān)工作

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

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

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

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

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

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

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

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

隨機(jī)部署無法為當(dāng)前過濾機(jī)制提供足夠的t-k cover，考慮采取覆蓋算法對(duì)節(jié)點(diǎn)進(jìn)行部署。為敘述簡(jiǎn)便，將t個(gè)密鑰分區(qū)同時(shí)覆蓋記為t-k cover，并將某種部署算法能保證每個(gè)事件源都被t個(gè)密鑰分區(qū)同時(shí)覆蓋的概率記為pt-k。當(dāng)pt-k值太小時(shí)無法滿足過濾機(jī)制的要求，太大時(shí)所需節(jié)點(diǎn)覆蓋度越高，從而引起較大的網(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è)全局密鑰池G={Ki:0≤i≤N-1}，密鑰池大小為N，分為n個(gè)不重疊的密鑰分區(qū){Ui,0≤i≤n-1}，每個(gè)分區(qū)包含γ個(gè)密鑰(N=n×γ)。每個(gè)節(jié)點(diǎn)從全局密鑰池中任取一個(gè)密鑰分區(qū)進(jìn)行裝載，則Δ(Δ≥t)個(gè)傳感器節(jié)點(diǎn)中至少有t個(gè)節(jié)點(diǎn)擁有互不相同密鑰分區(qū)的概率為：

(1)

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

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

(2)

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

(3)

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

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

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

(4)

顯然有：

(5)

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

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

(6)

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

(7)

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

(8)

因?yàn)?，?dāng)24k2≤n時(shí)：

(9)

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

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

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

3　仿真實(shí)驗(yàn)

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

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

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

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

4　結(jié)　語(yǔ)

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

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

[2] 劉明，曹建農(nóng)，鄭源,等.無線傳感器網(wǎng)絡(luò)多重覆蓋問題分析[J].軟件學(xué)報(bào)，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。國(guó)家自然科學(xué)基金項(xiàng)目(61379117)；湖南省教育廳科學(xué)研究重點(diǎn)項(xiàng)目(13A114)。劉志雄，博士，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)。劉華富，教授。

TP393

A

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