基于指纹模式匹配的无线传感器网络密钥预分配方案

吴旭婧,许 勇,张亚楠

(安徽师范大学数学计算机科学学院,安徽芜湖241003)

基于指纹模式匹配的无线传感器网络密钥预分配方案

吴旭婧,许 勇,张亚楠

(安徽师范大学数学计算机科学学院,安徽芜湖241003)

随着无线传感器网络(WSN)的广泛应用,其安全问题尤其突出,WSN的密钥分配和管理受到越来越多研究者的重视。通过收集节点的部署信息对区域进行划分,提出一种根据指纹识别进行模式匹配的密钥预分配方案。该方案将网络划分成多个较小区域,同时将密钥种子池分成多个与其对应的子密钥种子池。节点通过挑选相应区域内种子生成模式和文本,根据匹配成功时生成的指纹函数值建立通信密钥。安全性分析结果表明,与传统的随机密钥预分配方案相比,该方案具有较高的网络连通率及较低的存储能耗。

无线传感器网络;部署信息;区域划分;指纹识别;模式匹配;密钥预分配

1 概述

无线传感器网络(Wireless Sensor Network, WSN)集微机电系统技术、片上系统技术、无线通信技术等多种技术于一体,是当今研究的热点问题之一［1］。WSN由大量廉价的微型无线传感器节点组成,通常被部署在无人维护和极易受到威胁的环境。它们通过分布式部署、自组织方式采集和监控管理区域内的信息。与传统的网络相比,WSN节点在计算能力、存储空间、带宽大小、通信能量等方面资源受限,节点本身更易被俘获。因而一些传统的对节点资源有较高要求的加密方法,如公钥加密体系、基于密钥分发中心(KDC)的安全体系等不适用于无线传感器网络,设计适合无线传感器网络的安全方案显得十分必要［2-3］。以提供安全、可靠的保密通信为目标的密钥分配和管理方案成为无线传感器网络不可忽略的一个问题。

目前普遍认为可行的方法是密钥预分配方案,即把密钥预置装入传感器节点。文献［4］提出了一种基于经典随机图理论的随机密钥预分配方案(简

称E-G方案),该方案在减少对节点资源要求的同时获得高连通率,且不需节点的任何先验信息,但安全性一般。文献［5］对E-G方案进行改进后提出Q-composite方案,部署后2个相邻节点至少需要共享q个密钥才能直接建立配对密钥,网络的抗毁性增强。文献［6］利用节点的部署和位置信息,提出了基于区域的随机密钥预分配方案DR-KPS,提高了网络的连通性,但密钥池的划分较为复杂。本文方案在改进区域划分［7］的基础上,提出一种新的基于指纹识别和模式匹配［8-9］的WSN密钥管理方案。该方案利用节点的位置信息［10-11］增加相邻节点的连通性,利用模式匹配有效减少经典方案中节点存储能耗较大的问题,利用指纹对照有效减少共享密钥发现阶段计算能耗较大的问题。

2 模式匹配与指纹提取

假设有一个文本串X=x1x2…xn和模式Y=y1y2…ym,其中,m≤n,模式匹配即为确定模式Y是否在文本X中出现。解决模式匹配最简单直接的方法是移动模式经过整个文本,每次将长度为m的模式与部分文本进行比较,这种传统的方法耗时较长且计算较为复杂,为O(mn)。结合不确定性算法中的指纹提取函数,可以将运行时间简单的缩短为O(m+n),适用于WSN节点资源受限的特点［12］。基于指纹提取的模式匹配是将模式指纹Ip(Y)划过文本,与文本块中指纹Ip(X(j))进行比较。指纹提取函数满足以下特点:

(1)文本的O(n)个指纹都易于计算。

(2)新块X(j+1)的指纹可以方便从X(j)中计算得到,且X(j+1)与X(j)满足递归式:

Ip(X(j+1))=(2IpX(j)-Wpxj+xj+m)(modp)其中,Wp=2m。

3 WSN密钥预分配方案

本文方案基于以下假设:(1)所有节点只能与处于其通信范围内的其他节点进行通信;(2)短时间内基站处于安全位置。

3.1 网络初始化

其中,nA为节点生成的随机数,基站收到节点的位置信息LocA后,根据网络中节点的分布情况,将大的地理区域划分为M×N较小的区域domain(i,j),同时将密钥种子池划分为与地理区域相对应且不重叠的M×N个子密钥种子池subset(i,j),各地理区域与子密钥种子池对应一个区域标识GID。基站将该节点所属区域标识GIDA返回给各节点:

图1 区域划分及密钥选取

3.2 通信密钥的发现

网络初始化结束后,为与相邻节点建立通信密钥,节点广播自己的区域标识GIDA。

A通信半径内节点B收到A广播的数据包,根据是否与A同一区域,分2种情况:

(1)B与A属于同一区域。B节点收到数据包后,比较GIDA与GIDB是否相等,若相等,则属于同一区域。B节点查找该节点存储的区域标识GIDB对应的密钥种子池subset(i,j),使用池内种子seedi随机生成长度为m的的连续片段作为模式Y(B),将该片段对应的SeedIDi片段Y′(B)发送给A,Y′(B)长度相对较小。

(2)B与A不属于同一区域但所选子密钥种子池区域有部分重合。B从重合区域中随机选取一个区域GIDselect,和属于同一区域的方法类似,使用该区域种子生成模式片段Y(B),将对应的SeedIDi片段Y′(B)发送给A。

A根据解密收到的数据包选取GIDB或GIDselect对应区域种子seedi,使用seedi随机生成长度为n(n＞m)的文本片段作为模式匹配的文本X(A),提取相应的指纹函数值比较Y′(B)对应的模式Y(B)与X(A)是否匹配。若匹配成功,则用指纹值和匹配成功的位置生成通信密钥进行通信,按以下步骤生成通信密钥:

若生成通信密钥,则将p和匹配位置l加密传送给B。

B通过解密A发送回的数据包计算通信密钥kA,B=H(Ip(Y(B)),l)。所有通信密钥生成结束后,为防止节点被俘获泄露通信密钥信息,节点需删除存储的匹配文本X(A)和模式Y(B),通信密钥的生成基本上实现“一次一密”。

3.3 密钥路径的建立

通信密钥发现结束后,传感器网络构成一个共享密钥图G(V,E),图G由找到共享密钥的邻居节点和其安全链路构成。没有找到匹配建立通信密钥的节点通过其他存在共享密钥的邻居节点经过若干跳后建立双方的一条密钥路径。为发现与目标节点通信的密钥路径,源节点挑选一系列已经与它建立共享密钥的中间节点,并发送请求给所有中间节点。如果中间的某一节点与目标节点有一个直接的共享密钥,这条密钥路径就已找到。否则,中间节点将继续转发请求,此过程类似路由发现过程。该过程为减少通信开销,可以把广播范围限定在3跳之内。

4 性能分析

4.1 连通性分析

图2 网络连通率与邻居节点数的关系

4.2 存储开销分析

节点的存储开销即为建立通信密钥所需的存储空间。本文方案的存储开销主要为模式匹配过程中生成的匹配文本的存储。图3为网络的连通性与节点存储密钥数量之间的关系。本文方案和其他方案不同,节点存储的是用来匹配的文本X(A),M=N= 4,种子密钥池中种子数S=32,子种子密钥池种子数s=2,模式长度m=3,只有当m＜n时才可进行模式匹配,其他方案中密钥池大小为10 000。从图中看出,当节点存储的文本长度约达到37时,网络中有较高的连通概率(约为0.99)。而达到同样概率,EG方案需存储的密钥环长度约为213,Q-composite方案约为255。通过比较,本文方案存储性能有很大程度提高。

图3 网络连通率与节点存储密钥数量的关系

4.3 计算开销分析

节点的计算开销是节点生成通信密钥时计算所消耗的能量。本文方案的计算开销主要为辅助密钥的生成和匹配操作所需开销。辅助密钥的计算为网络初始化时节点生成初始密钥Kmaster、生成用于加密通信消息的派生密钥以及找到匹配时通信密钥的计算。在模式匹配过程中,节点计算Wp,Ip(Y(B))和Ip(X(A)1)耗费的时间为O(m)。根据Ip(X(A)l)计算Ip(X(A)l+1)时,只需常数个加减法运算,逐个匹配时(2≤l≤n-m+1),计算每个Ip(X(A)l)仅需O(1)的时间,总共需要O(n)的时间,因此,本文方案中模式匹配的时间为O(m+n),适合于WSN节点计算能力有限的特点。

4.4 通信开销分析

节点的通信开销是节点生成通信密钥时发送和接收消息所消耗的能量。本文方案中区域内任意节点只与通信范围内节点通信产生开销。在网络初始化时,节点将位置信息Loc发送给基站并接收基站分配的区域标识GID产生通信开销。通信密钥发现阶段时,设区域密度为D,节点的通信半径为R,每个节点向通信范围内的πDR2-1个节点广播挑战信息,收到广播的节点对其进行判断并决定是否生成模式与其文本匹配。通信过程中节点标识NID、区域标识GID和种子长度seedi较短,因此产生的通信开销较小。

4.5 安全性分析

网络的安全性表现在部分传感器节点被俘获时,攻击者利用节点存储的信息窃听其他节点间的通信。本文方案的安全性主要基于以下3点:(1)使用密钥种子seedi用于匹配的模式和文本从而生成密钥,而不直接预置密钥,模式和文本的生成过程随机使通信密钥的生成具有不可预测性,即使节点被俘获,攻击者只能窃取该节点与其建立通信密钥节点的通信密钥,不能计算出其他节点间的通信密钥,网络受影响范围不大。(2)通信密钥生成结束后,节点删除模式和文本,该操作增加了破解密钥的难度,通信密钥发现过程中即使俘获部分信息,也很难推算出通信密钥。(3)基于区域的设计使某一区域内节点被俘获,也只会增加局部区域被攻击的概率,不会对整个网络安全产生影响。

5 结束语

本文在区域划分的基础上,提出一种通过提取指纹进行模式匹配的密钥预分配方案,并将其与E-G和Q-composite方案进行比较。实验结果表明,该方案提高了邻居节点发现共享密钥的概率及网络连通性能。此外,网络存储方面的性能也得到改善,节点存储的密钥环长度大大减小。方案中模式长度m和匹配文本长度n的选择以及区域划分的数量是需重点考虑的因素。此外,如何减少通信代价及提高网络的扩展性是下一步研究的主要内容。

［1]苏 忠,林 闯,封富君.无线传感器网络密钥管理的方案和协议［J］.软件学报,2007,18(5):1218-1231.

［2]米 波,曹建秋,段书凯,等.无线传感器网络密钥管理问题综述［J］.计算机工程与应用,2011,47(13): 77-82.

［3]马祖长,孙怡宁,梅 涛.无线传感器网络综述［J］.通信学报,2004,25(4):114-124.

［4]Eschenauer L,Gligor V D.A Key-management Scheme for Distributed Sensor Networks［C］//Proceedings of the 9th ACM ConferenceonComputerandCommunications Security.New York,USA:ACM Press,2002:41-47.

［5]Chan H,Perrig A,Song D.Random Key Predistribution Schemes for Sensor Networks［C］//Proceedings of 2003 Symposium on Security and Privacy.Washington D.C., USA:IEEE Press,2003:197-213.

［6]刘志宏,马建峰,黄启萍.基于区域的无线传感器网络密钥管理［J］.计算机学报,2006,29(9):1608-1616.

［7]李长庚,刘 波,欧兰英,等.基于区域划分的WSN混沌密钥管理方案［J］.计算机工程,2012,38(8): 95-97.

［8]翁年凤,刁兴春,曹建军,等.不确定模式匹配研究综述［J］.计算机科学,2012,38(12):1-5.

［9]廖 阔,杨万麟.点模式指纹匹配算法研究与实现［J］.电子科技大学学报,2004,33(2):154-157.

［10]孔贝贝,唐小虎.基于地理位置的蜂窝状密钥管理方案［J］.计算机应用研究,2010,27(4):1514-1520.

［11]Liu D,Ning P.Location-based Pairwise Key Establishments for Static Sensor Networks［C］//Proceedings of the 1st ACM Workshop on Security of Ad Hoc and Sensor Networks.New York,USA:ACM Press,2003:72-82.

［12]Alsuwaiyel M H.算法设计技巧与分析［M］.吴伟昶,译.北京:电子工业出版社,2010.

编辑 索书志

Key Pre-distribution Scheme of Wireless Sensor Network Based on Fingerprint Pattern Matching

WU Xujing,XU Yong,ZHANG Yanan
(College of Mathematics and Computer Science,Anhui Normal University,Wuhu 241003,China)

With the widely application of the Wireless Sensor Network(WSN),the security problem is more and more prominent.The distribution and management of WSN receive more and more attention.This paper proposes a key predistribution scheme which matches patterns according to the fingerprint identification by dividing the network after collecting the deployment information.The scheme divides the network into several domains,and the seed pool is divided into multiple sub-seed pools relatively.Nodes select seeds from relative areas to generate patterns and texts,and use fingerprint function values as communication keys when match successfully.The performance and security analysis shows that the scheme can substantially improve a network’s connectivity and reduce storage consumption compared with the traditional random key pre-distribution scheme.

Wireless Sensor Network(WSN);deployment information;regional dividing;fingerprint identification; pattern matching;key pre-distribution

吴旭婧,许 勇,张亚楠.基于指纹模式匹配的无线传感器网络密钥预分配方案［J］.计算机工程, 2015,41(3):106-109.

英文引用格式:Wu Xujing,Xu Yong,Zhang Yanan.Key Pre-distribution Scheme of Wireless Sensor Network Based on Fingerprint Pattern Matching［J］.Computer Engineering,2015,41(3):106-109.

1000-3428(2015)03-0106-04

:A

:TP309

10.3969/j.issn.1000-3428.2015.03.020

安徽省2013年千人培养计划基金资助项目(151408)。

吴旭婧(1990-),女,硕士研究生,主研方向:网络与信息安全;许 勇,教授;张亚楠,硕士研究生。

2014-03-24

:2014-05-20E-mail:kidaulthood@163.com