传感器网络虚假数据过滤的最优覆盖度分析

刘志雄　刘华富

(长沙学院数学与计算机科学系　湖南 长沙 410022)



传感器网络虚假数据过滤的最优覆盖度分析

刘志雄刘华富*

(长沙学院数学与计算机科学系湖南 长沙 410022)

虚假数据过滤是传感器网络安全领域的一个重要问题。当前算法通常由t个拥有不同密钥分区的节点协同对数据进行加密，但其所采取的随机部署节点方式无法确保每个事件源都被t个密钥分区所覆盖，从而导致稀疏区域的事件无法上报给sink。提出利用覆盖算法对节点进行部署，基于覆盖质量及网络开销推导和证明了最优节点覆盖度Δ。实验结果表明，采用Δ覆盖比随机部署的密钥覆盖有效性提高约70%。

无线传感器网络虚假数据过滤节点部署最优覆盖

0　引　言

无线传感器网络WSN广泛地应用在交通管理、珍稀动物追踪以及人体心脏监控等领域中[1]。通常情况下，传感节点部署在恶劣的区域或者是敌对环境中，攻击者往往利用俘获的秘密信息伪造事实上不存在的虚假数据并发送给邻居节点[2]。如不加防范，这类攻击将极大地消耗网络资源，并引起错误的警报[3]。

为了应对虚假数据注入攻击，国内外研究人员提出了一些解决策略[3-12]。它们的大致思想都是借鉴数字签名，在每个产生的数据报告中捎带t个MAC(Message Authentication Code)，然后由中间节点和sink实施过滤。然而，由于受到部署区域不规则等复杂因素的影响，上述方案所采取的随机部署策略往往在网络中形成部分稀疏区域(如：边界地带)[10]，从而因检测节点数量不够造成部分突发事件无法上报到目标节点。

本文利用覆盖算法对节点进行部署，推导并证明了适用于虚假数据过滤的最优节点覆盖度Δ。理论分析及仿真实验表明，与随机部署及其他覆盖算法相比，Δ覆盖能以较高概率保证每个事件源被t个密钥分区同时覆盖。

1　相关工作

文献[3]率先对虚假数据过滤进行了研究，提出了基于对称密钥及过滤验证的SEF方案。该方案假设存在一个大小为n·m的密钥池，其中n为密钥分区数量，每个分区包含m个密钥。给节点预置一个密钥分区，并随机部署在监控区域中。多个节点协同对感知事件加密，并生成包含t个MAC的报告。转发过程中，中间节点利用对称密钥对MAC进行校验。然而，由于实际部署网络的形状通常是不规则的，SEF所采取的随机部署策略往往可能在边界地带等形成部分稀疏区域，故没有足够的节点来完成数据感知和数据产生。

例如，在图1所示的森林防火警报系统中，假设覆盖A1、A2、A3的持不同密钥的节点集分别为{S1，S2,…，S5}，{S6，S7，…，S9}，{S10，S11}。假设阈值t=5，若火灾发生在A1，则能由5(≥t)个持不同密钥的节点共同产生数据并上报；而若当火灾发生在其他两个区域，则无法产生数据，因为监测节点数量分别只有4个和2个(4

图1　森林防火警报系统

文献[4]提出了一种基于多轴划分的方案GRSEF。该方案将节点分成t组，并采用多坐标系对网络区域进行划分，然后分发密钥。与SEF不同，GRSEF限定由t个不同组的节点共同产生数据包，从而能有效提高虚假数据过滤的效率。然而，多轴划分算法的计算复杂性很高，不利于节省网络能量，且在成组过程中并没有对节点的位置进行合理规划，从而难以确保有足够多的节点同时感知到突发事件。

文献[5]提出了一种基于星形拓扑的RSFS方案。当检测到突发事件时，由一种比普通节点能量强得多的特殊节点作为簇头对数据进行聚合，并在聚合数据后附加簇内普通节点的MAC进行发送。当数据传输到sink节点后，由sink对聚合结果及MAC进行验证。该方案不受安全阈值的限制，但不是一种转发过滤策略，假数据包必须传输到sink才能被过滤，不适用于能量有限的传感器网络。

文献[6]提出了一种基于单向函数和MAC的过滤方案FFRF。在部署前，该方案给每个节点配置一个单向函数f，并基于f和一个随机数x生成一条哈希链。接下来，每个节点将哈希链中的第一个哈希值在网络中进行公开，中间节点以一定概率随机存储部分源节点的第一个哈希值，用来对数据进行验证。由于FFRF没有在节点密钥和哈希值之间建立某种函数关系，从而给攻击者提供了便利。此外，假设突发事件发生在簇与簇交替的区域，该方案将无法顺利产生数据。

总之，已有虚假数据过滤算法所采用的随机部署无法保证每个事件源都被足够多的密钥分区同时覆盖，从而导致发生在稀疏区域的事件无法上报到sink节点。本文主要研究适用于虚假数据过滤的最优节点覆盖。

2　WSN虚假数据过滤最优覆盖分析

随机部署无法为当前过滤机制提供足够的t-k cover，考虑采取覆盖算法对节点进行部署。为叙述简便，将t个密钥分区同时覆盖记为t-k cover，并将某种部署算法能保证每个事件源都被t个密钥分区同时覆盖的概率记为pt-k。当pt-k值太小时无法满足过滤机制的要求，太大时所需节点覆盖度越高，从而引起较大的网络开销[12]。

定义1在虚假数据过滤中，将D+1覆盖比D覆盖增加的pt-k记为In(D+1，D)。给定系统阈值f，若存在Δ，使得In(Δ，Δ-1) ≥f，且In(Δ+1，Δ) ≤f，则称Δ覆盖为最优覆盖。

定理1存在一个全局密钥池G={Ki:0≤i≤N-1}，密钥池大小为N，分为n个不重叠的密钥分区{Ui,0≤i≤n-1}，每个分区包含γ个密钥(N=n×γ)。每个节点从全局密钥池中任取一个密钥分区进行装载，则Δ(Δ≥t)个传感器节点中至少有t个节点拥有互不相同密钥分区的概率为：

(1)

证明：首先计算Δ个节点中恰有t个节点拥有互不相同密钥分区的概率。在Δ(Δ≥t)个传感器节点中，每个节点拥有一个密钥分区，得到的Δ个密钥分区，对于虚假数据过滤来讲，是不需考虑排列顺序的。因此，Δ个传感器节点中的每个节点在一个等分为n个分区的全局密钥池中，任取一个密钥分区进行装载，每个节点拥有一个密钥分区，允许重复，不管其顺序合并成一组，得到的密钥分区组合种数为C(n+Δ-1,Δ)。

而在Δ(Δ≥t)个传感器节点中恰有t个节点拥有互不相同密钥分区的组合种数为C(n,t)C(Δ-1,Δ-t)。所以，Δ(Δ≥t)个传感器节点中恰有t个节点拥有互不相同密钥分区的概率为：

(2)

采用类似的方法依次可解Δ个节点中恰好1，2，…，t-1个拥有互不相同密钥分区的概率。综上可知，Δ个节点中至多拥有t个密钥分区的概率为：

(3)

故Δ个节点中至少拥有t个不同密钥分区的概率为p=1-pΔ(1,2，…,t)。证毕。

定理1在传感器网络虚假数据过滤中，采用覆盖算法对节点进行部署，并在数据包后附带t个MAC进行验证。给定f=0.05，当覆盖度Δ=2t时，Δ覆盖为最优覆盖。

证明：由定理1可知，Δ(Δ≥t)个传感器节点中恰有t个节点拥有互不相同密钥分区的概率为pΔ(t)。故有下式成立：

(4)

显然有：

(5)

由归纳法知，当Δ≥ 2t时，In(Δ+1，Δ) ≤ 0.05=f。同理，In(Δ，Δ-1) ≥ 0.05=f成立。因此，当Δ=2t时，Δ覆盖为适用于传感器网络虚假数据过滤的最优覆盖。证毕。

定理3存在一个等分为n个分区的全局密钥池，每个节点从中任取一个密钥分区进行装载，则2t个传感器节点中恰有t个节点拥有互不相同密钥分区的概率使下式成立：

(6)

证明：当t=1时，由于n≥24，有：

(7)

假设t=k时，式(6)成立，则当t=k+1时：

(8)

因为，当24k2≤n时：

(9)

所以式(6)成立。证毕。

图2给出了当t=5、n=10、ε=0.2时，P的理论分析曲线和仿真实验结果关于Δ的变化情况，其中仿真结果是随机测试500次取的均值。从图中可以看出，当Δ< 2t=10时，P随覆盖度的增加而迅速增大；反之，当Δ>2t=10时，P随覆盖度的增加仅缓慢增大。由最优覆盖的定义可知，此时所增加的概率是不值得的，因此，取Δ=2t为最优。

图2　P的理论值与仿真结果

3　仿真实验

为了进一步比较随机部署和Δ覆盖算法的t-dk cover性能，本文利用C语言建立了模拟仿真平台。仿真环境如下：在40×40 m2的方形网络区域中，0～500个传感器节点分别随机部署或者按照Δ覆盖算法部署，其他仿真参数的设置见表1所示。取15次仿真实验的平均值作为试验结果。

表1　仿真参数列表

如图3所示，当节点部署密度较小时，两种方案的t-dk cover 性能都较差，例如，当网络中总共只部署了200个节点时，两者的t-dk cover比率分别只有6.2%和4.1%。随着节点部署密度增大，随机模型的t-dk cover性能仅缓慢增强，例如当节点数由200增到400时，合法覆盖率仅增加了3.2%。而此时Δ覆盖算法的t-dk cover性能则随节点增加而迅速增大，例如在部署400个节点的条件下，其t-dk cover率增加了87%。这是因为，随机模型没有对节点部署进行规划，故而在网络中特别是边界地区形成部分稀疏区域，而Δ覆盖算法能通过节点规划而达到更好的t-dk cover性能。

图3　Δ覆盖和随机模型t-dk cover性能比较

4　结　语

虚假数据过滤是无线传感器网络中一个重要的安全问题。已有算法所采取的随机部署节点方式无法确保每个事件源都被t个密钥分区所覆盖。提出利用覆盖算法对节点进行部署，分析并证明了适用于虚假数据过滤的最优节点覆盖度Δ。接下来的工作将研究多sink的情形。

[1] 任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003,14(7):1282-1291.

[2] 刘明，曹建农，郑源,等.无线传感器网络多重覆盖问题分析[J].软件学报，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。国家自然科学基金项目(61379117)；湖南省教育厅科学研究重点项目(13A114)。刘志雄，博士，主研领域：无线传感器网络。刘华富，教授。

TP393

A

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